Jinshan Liu
email: jinshan.liu@inria.fr

Daniele Sacchetti
email: daniele.sacchetti@inria.fr

Group Management for Mobile Ad Hoc Networks: Design, Implementation and Experiment

Keywords: H.4 [Information Systems Applications]: Communications Applications; C.2 [Computer-Communication networks]: Distributed Systems Group management, mobile ad hoc networks, middleware, mobile computing

Mobile ad hoc networks (MANET) offer a convenient basis toward realization of pervasive computing, due to its ease of deployment and inherent support for anytime, anywhere network access for mobile users. However, the development of applications over such networks is faced by the challenge of network dynamics attributed to node mobility and the scalability issue. Group management poses as a promising paradigm to ease the development of distributed applications for dynamic, mobile networks. Specifically, group management makes transparent the failures due to node mobility and assembles mobile nodes to meet target functional and non-functional properties. Various network-level grouping schemes over MANET have been investigated over the last couple of years. In this paper, we introduce the design and implementation of a generic group service for MANET, defined with respect to the various attributes of relevance. Generic group management is further demonstrated with its support of scalable service discovery in MANET.

INTRODUCTION

The development of applications over wireless ad hoc networks is confronted by the challenge of frequent changing of environments, e.g., network topology. One approach to master this complexity lies in the grouping (clustering) of nodes over the network, i.e., applications execute on top of group services that manage the execution context dynamics, including node mobility. Another advantage of grouping in mobile ad hoc networks is to achieve system scalability, with group leaders responsible for inter-group communications. There has been extensive research on group management and related group communication services in the context of fixed networks, with special emphasis on providing availability properties [START_REF] Powell | Group communication[END_REF][START_REF] Chockler | Group communication specifications: A comprehensive study[END_REF]. However, proposed solutions cannot be applied directly to mobile wireless networks due to their highly dynamic topology [START_REF] Basile | A survey of dependability issues in mobile wireless networks[END_REF]. This necessities the adaption of group membership to the specifics of mobile networks.

Group membership is primarily defined according to the functional property to be collectively achieved by the group, e.g., collaborative editing, sharing computational load, providing fault tolerance [START_REF] Powell | Group communication[END_REF]. In general, a member may leave a group because it fails, explicitly requests to leave, or is expelled by other members. Similarly, a member may join a group because it explicitly files a request or recovers from failure. A group management protocol must handle such dynamics in a coherent way, i.e., all members of the group must have a consistent view of the group's membership despite failures [START_REF] Chockler | Group communication specifications: A comprehensive study[END_REF]. The highly dynamic topology of wireless ad hoc networks introduces additional complexity in the management of group membership because connections can be transient and partitioned networks may never be rejoined together.

It can be argued that group membership in MANET may be defined as in fixed networks, assuming that the network is able to restore lost connections with the underlying routing protocol and it is sufficient to adapt the group communication service to the dynamic topology of the network [START_REF] Luo | PILOT: Probabilistic lightweight group communication system for mobile ad hoc networks[END_REF].

Such an approach does not adapt the system's functions to the network specifics, but rather modify the implementation of underlying distributed system functions. It is, however, advantageous to revise the definition of group membership to integrate the network dimensions in addition to the functional one. This enables the group to enact quality of service (QoS) requirements by bounding communication latency [START_REF] Hugues | Towards real-time event-based communication in mobile ad hoc wireless networks[END_REF] and/or supporting location-aware applications. For example, group constraints may be set according to the network's scale such as group size (e.g., [START_REF] Roman | Consistent group membership in ad hoc networks[END_REF][START_REF] Briesemeister | Localized group membership service for ad hoc networks[END_REF]) or the respective geographical positions of the group's members (e.g., [START_REF] Meier | Towards proximity group communication[END_REF]). The definition of group membership may also be extended with integrity constraints (e.g., security constraints, size) [START_REF] Meissner | Group integrity management support for mobile ad hoc communities[END_REF].

In general, group management in mobile ad hoc networks embeds a number of design dimensions related to group member attributes and the non-functional properties that are offered to applications. In this paper, we provide a characterization of the attributes of group membership in MANET (Sec. 2), and then introduce the design of a group management service that is generic with respect to the elicited attributes (Sec. 3). The assessment is based on its implementation in a middleware aimed at mobile computing (Sec. 4), and its usage for enabling scalable service discovery in MANET (Sec. 5). Finally, we conclude with a summary of our contribution and future work (Sec. 6).

ATTRIBUTES OF GROUP MEMBERSHIP

Many of the application scenarios where group membership is considered are location-dependent, i.e., ad hoc groups are formed according to the presence of nodes in a given geographical region, in addition to the functional properties supported by the group. The geographical region can be defined with respect to either a fixed geographical point or the position of a mobile node. In the former case, presence in the geographic region enacts a location-dependent application in scenarios such as business-to-consumer interactions in malls, airports and trade fair communities [START_REF] Meissner | Group integrity management support for mobile ad hoc communities[END_REF].

In the latter case, communities are formed by proximate nodes, which can be dedicated to resource sharing with QoS properties, such as enhanced data availability [START_REF] Boulkenafed | Middleware service for mobile ad hoc data sharing, enhancing data availability[END_REF] or realtime processing [START_REF] Hugues | Towards real-time event-based communication in mobile ad hoc wireless networks[END_REF][START_REF] Sha | Dynamic bandwidth management for single-hop ad hoc wireless networks[END_REF]. Group membership can also depend upon trustworthiness of group members, e.g., it is possible to restrict membership to authorized nodes to ensure secure interactions among members. Constraints on group membership may be considered at the level of the overall group (e.g., group size as in [START_REF] Meissner | Group integrity management support for mobile ad hoc communities[END_REF]) and/or at the level of group members (e.g., storage capacities of nodes). Ideally, a group management service for wireless ad hoc networks must be configurable with respect to the above attributes to support various applications. In the following, we provide a characterization of these attributes, by first defining the underlying network model that we assume.

Groups are first defined with respect to a functionality, denoted as f, which can characterize various features supported by nodes, e.g., resources and services. We use support(x, f ) to denote the fact that node x offers function f, and G f to denote a group with function f , i.e., G f = {x| x ∈ N and support(x, f )}.

Network Model

We consider a network consisting of a set of N nodes, and assume that every node x of N has a unique identifier Id(x). The following notations are used to reason about the attributes of nodes.

• P roximity(x, p) returns the geographical distance in meters between the location of node x and geographical position p.

• Distance(x, y) returns the geographical distance in meters between x and y ∈ N .

• Hops(x, y) returns hop count between x and y for any y reachable from x.

Location

We now define group membership with respect to constraints on the location of member nodes.

Location-unaware groups (e.g., in [START_REF] Luo | PILOT: Probabilistic lightweight group communication system for mobile ad hoc networks[END_REF][START_REF] Luo | PAN: Providing reliable storage in mobile ad hoc networks with probabilistic quorum systems[END_REF]), are defined only with respect to the functions offered by the group. Hence, LocationU naware(G f ) always holds.

Proximity-based groups (e.g., in [START_REF] Meier | Towards proximity group communication[END_REF][START_REF] Meissner | Group integrity management support for mobile ad hoc communities[END_REF]), refine group members to be within a given geographical area, with reference location either be fixed a priori or the position of other group members. Let pos denote a referenced geographical position and dist denotes the maximal geographical distance that is allowed, we have:

Geographical P roximity(G f , pos, dist) ⇔ ∀x ∈ G f : P roximity(x, pos) < dist Relative P roximity(G f , dist) ⇔ ∀x, y ∈ G f : Distance(x, y) < dist

Scale

Bounded groups (e.g., in [START_REF] Amis | Max-Min D-cluster formation in wireless ad hoc networks[END_REF][START_REF] Roman | Consistent group membership in ad hoc networks[END_REF][START_REF] Briesemeister | Localized group membership service for ad hoc networks[END_REF]), are defined based on the maximal number of hops (H) between nodes and a specific node (usually group leader, notated as node l ):

Bounded(G f , H) ⇔ ∀x ∈ G f : Hops(x, l) ≤ H
Group size (e.g., in [START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF]) defines the maximal number of members in a group. And we have (assuming the maximum group size is N ).

Size(G f , N ) ⇔ |G f | ≤ N

Trustworthiness

Group membership can be restricted to nodes which trust each other, meaning that each member has a decent reputation towards every other based on past experiences and peer recommendations [START_REF] Liu | Enhanced reputatation mechanism for mobile ad hoc networks[END_REF]. The group membership is thus subject to a node's reputation (Rep) among its peers in the group, which is at least δ to be considered trustworthy:

T rusted(G f , δ) ⇔ ∀x, y ∈ G f : Rep(x, y) ≥ δ
Higher trustworthiness can be achieved with signed certificates (SC ), which is managed by a trusted third party, e.g., some certificate authority (CA). Newcomers which lack previous interactions with other peers can also start with a SC. Secure group communication can be enforced through the implementation of group key agreement (GKA) within the group [START_REF] Bhaskar | Group key agreement in ad hoc networks[END_REF]. Thus we have:

SC(G f , CA) ⇔ ∀x ∈ G f : x ∈ Authorized(CA)

QoS Awareness

Groups can also be defined by certain QoS attributes, e.g., the following that appear to be the most dominant in the context of mobile wireless networks [START_REF] Liu | QoS-aware service location in mobile ad hoc networks[END_REF]: reliability, performance and transaction for service level attributes, and Group √ √ √ Table 1: Categorization of attributes CPU load, memory, bandwidth and battery for resource level attributes.

In addition, group membership can be restricted in terms of node mobility to limit the probability of a node leaving a group. For instance, the mobility of nodes has been suggested as a criterion for integration within a group [START_REF] Roman | Consistent group membership in ad hoc networks[END_REF], which possibly assumes a group-based mobility model [START_REF] Hong | A group mobility model for ad hoc wireless networks[END_REF].

In general, disconnection of a node from a group can result from the node's mobility and/or the node's resource scarcity. The former can be predicted based on the node's movement pattern, and the latter can be anticipated based on information about resource level QoS values of the node.

Attributes Categorization

The above listed attributes can be categorized by their ranges of application (see Table . 1): (1) local constraints, which apply to a single node, e.g., Geographical proximity and SC. (2) group constraints, which apply to the whole group, e.g., Relative P roximity and Size.

The difference between these two categories is that for the former, group membership can be confirmed locally (e.g., by calculating the distance from a fixed point), while for the latter one, group membership has to be confirmed in a group range (e.g., by calculating the total number of nodes), which has to be carried out during the group formation. Note that the above attributes are not exclusive of each other and may be combined for the definition of a group.

After introducing the relevant group attributes, we present the design of a group management service that is generic with respect to the aforementioned attributes.

GROUP SERVICE DESIGN

Due to the challenges posed by mobility and resource limitation of nodes, we consider the following properties necessary for group management design:

1. Resource-saving. The overhead of group management should be affordable for resource-constrained devices.

2. Distributed. Group management cannot accommodate a centralized solution where a single node is always responsible for managing the group. This is due to node mobility and necessity of load balancing.

3. Dynamic. The group management service must accommodate the highly dynamic topology of the network.

We distinguish three functions in group management:

• Group member discovery, i.e., discovering mobile nodes that are eligible for membership according to relevant membership attributes.

• Group initialization, i.e., exchanging meta-data relevant to the group's functionality and enforcing global membership constraints.

• Group dynamics management, i.e., updating group membership according to the dynamics of the network's topology.

In our work, we assume that each node in the network is able to (1) know its 1-hop neighbors and (2) detect neighbors leaving and coming by underlying routing table. By neighbors, we refer to nodes reachable in 1 hop, while peers refer to the nodes reachable in 1 or multiple hops. The two assumptions can be achieved with help of proactive routing protocols (e.g., OLSR [START_REF] Clausen | Optimized link state routing protocol[END_REF]), or having each node periodic sending beacons with reactive routing protocols. Before presenting group member discovery, we first introduce 2-hop bordercasting we use to broadcast within H hops. For broadcasting within H hops, we utilize 2-hop bordercasting (Fig. 1) to reduce the traffic overhead. Succinctly speaking, the broadcast sender, by utilizing two-hop topology information gathered from periodic beacons, selects among (1-hop) neighbors the minimal number of nodes (called bordercast nodes) that can cover all the nodes within 2 hops. Only the selected bordercast nodes repeat the process until H hops are reached. Looping is prevented in bordercasting by embedding a unique message number.

Group broadcasting

Group Member Discovery

in joining in. In the meanwhile, if it is a bordercast node assigned by the sender, it needs to determine whether to rebroadcast the disc message based on the following rule: it does not rebroadcast only if [START_REF] Amis | Max-Min D-cluster formation in wireless ad hoc networks[END_REF] it has no neighbors to rebroadcast (i.e., its only neighbor is the sender of the received disc), or (2) it can ascertain that peers further discovered by its rebroadcasting will not meet the group membership constraints (e.g., bounded group).

Contrary to non-bordercast nodes who only need to reply with their own willingness to join the group, a bordercast node needs to wait for the arrival of the responses from all its neighbors before it can respond to its preceder node (either the group initializer or a bordercast node) with a join message. The join messages include the peers intending to join the group (including itself if it intends to join), along with peer information (e.g., geographical location). Note that even if the bordercast node has received no join message indicating willingness to join, it sends back a "negative" join message to indicate so.

In the case that there are two nodes initializing group member discovery simultaneously with the same functionality and group constraints, it can be merged by selecting a new initializer from the two (e.g., by id), with the ancient initializer forwarding all join messages to the newly selected initializer. If the initializer fails during the initialization phase, the discovery process is restarted.

Group Initialization

Each group has a node named group leader responsible for (1) managing the group dynamics while enforcing group constraints (2) inter-group communication. However, before the group is formed, it is always the group initializer who does the group initialization, i.e., acting as the temporary group leader. The group initialization does not start until the initializer has received responses from all its neighbors. One vital part of group initialization is to enforce global constraints. As listed in Table. 1, there are following possible global constraints that need to enforce:

• Relative proximity, which enforces that every two nodes have to be within certain distance. This can be accomplished by calculating the distance from the geographical locations of group members included in join messages.

• Reputation, which enforces that every two nodes have good reputation towards each other. It is difficult to enforce since reputation towards a peer is considered private in most cases and it is unlikely to provide all reputation values to the leader. However, it can be accomplished by the constraint that the group leader is trustworthy enough to coordinate the interactions between group members, or recommendation from the leader is strong enough to fortify a member's reputation for others. This constraint can be locally enforced during the group member discovery.

• Size, which enforces that the total number of group members cannot exceed a certain threshold number. This can be easily achieved by calculating the number of nodes intending to join by join messages.

Note that global constraints on group membership may lead to exclusion of peers from the group, even if they have sent join messages. For instance, as the consequence of the group size constraint, some nodes can be excluded from the group if the leader has already admitted maximal nodes. For those excluded nodes, they may create a group by starting group discovery process as described above.

In the case where the group is based on signed certificate, the initialization process is complemented with a group key agreement (GKA) protocol for establishing a shared key among the group's members. The key will then be used to encrypt any message subsequently exchanged within the group [START_REF] Bhaskar | Group key agreement in ad hoc networks[END_REF].

To discover leaders of other groups, the leader periodically broadcasts (e.g., to the range of twice the group size) a message to announce its existence to potential nearby leaders of other groups with same functionality and group constraints.

Group Dynamics Management

Since leaders might drift away, leader might need to be rotated to other members, also to distribute the load of group management among members. We start by illustrating how to select the leader.

Leader Selection. Several criteria have been proposed for leader selection in ad hoc networks, including: (i) highest degree, where nodes with the maximum number of neighbors are selected as group leader. This approach has low rate of group leader change, but suffers from low input since the throughput is shared among group members [START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF]; (ii) extrema-id (e.g., [START_REF] Boulkenafed | Using group management to tame mobile ad hoc networks[END_REF]), where the node with the smallest or greatest id is assigned as the group leader. The shortcoming of this approach is its bias against nodes with extrema ids; (iii) node weight (e.g., [START_REF] Basagni | Distributed clustering for ad hoc networks[END_REF][START_REF] Chatterjee | WCA: A weighted clustering algorithm for mobile ad hoc networks[END_REF][START_REF] Vasudevan | Design and analysis of a leader election algorithm for mobile ad hoc networks[END_REF]), which is an integrated metric for evaluating the suitability of a node as a group leader. It can depend on various factors such as the resource richness and the neighbor count.

Above criteria are essentially based on group attributes as illustrated in Sec. 2. Therefore, it is natural to integrate them to evaluate a node's suitability for acting as a leader, by tuning different weights on different metrics for different scenarios. In particular, in this paper, we consider the following two metrics, which are locally available on each node for election of group leader: Note that it can be easily extended to cover other metrics, and metrics need normalization since they are in different units and are not comparable. In case of tie of overall weights, the leader is selected randomly. Leader rotation is started if some node has an overall weight higher than the current leader. This may result from multiple reasons: the current leader's weight keeps falling with longer time of being leader, or a member's resources get richer (e.g., gets power plugged-in). Change of leader requires the transfer between the old and new leaders, the information1 that is only kept in the leader (e.g., the leaders of other neighbor groups). And the new leader needs to inform the whole group the changes of leader, along with the group information including group member list.

As stated, group management over MANET requires managing mobility-induced changes in group membership, in a manner that is transparent to applications. Since a new node is detected by the network layer, an event-based mechanism can be installed on the leader to invite the new comer to join the group, on the condition that the group is able to accommodate more members. The leaving of a node can be similarly handled by the leader's sending an event-invoked group-wide announcement of updated member list.

IMPLEMENTATION

To ease the development of ambient intelligence applications, we have introduced the WSAMI (Web Services for AMbient Intelligence) middleware that supports seamless access to mobile services for the mobile user [START_REF] Issarny | Developing Ambient Intelligence Systems: A solution based on Web services[END_REF]. WSAMI allows for the abstract specification of Ambient Intelligence applications in the form of composite services, together with their dynamic composition logic according to the environment. WSAMI builds on the Web services architecture2 , and dynamic service composition is carried out by integrating services deployed on mobile, wireless terminals and on the Internet.

WSAMI Middleware for Mobile Web Services

The WSAMI core middleware can be divided into [START_REF] Issarny | Developing Ambient Intelligence Systems: A solution based on Web services[END_REF]: (i) a core broker, including the CSOAP-based SOAP container for wireless, resource-constrained devices, and (ii) the Nam-ing&Discovery (ND) service for the dynamic discovery of (possibly mobile) services that are available in the local and wide area, according to network connectivity and available resources.

We have carried out a number of experiments to investigate the performance of our lightweight Web services platform, and in particular compare it against existing Web services platforms, e.g., traditional middleware platforms being considered for the mobile environment [START_REF] Issarny | Developing Ambient Intelligence Systems: A solution based on Web services[END_REF]. Experiments show that the overhead related to the functions handling user mobility (i.e., dynamic service composition relying on service discovery and connector customization for enforcing QoS) is comparable to the cost of base Web services access.

Our prototype is being used for the implementation of demonstrator applications in the field of ambient intelligence, as part of the Ozone IST project3 . It is in particular being extended with a number of value-added middleware services for mobility management as well as for enabling intelligence-aware interfaces.

Group Service in WSAMI

The ND service discovers instances of Web services implementing a given WSAMI interface within one-hop ad hoc networks in our current prototype. The Group service then implements DiscPeer on top of the ND service, which takes as input the URI of the WSAMI document defining the function of the group, and other group constraints. DiscPeer utilizes the ND service to multicast Disc messages and to receive Join messages for realizing group service as detailed in Sec. 3.

Note that the functional specification of any group not only includes the group's specific functional operations, but also operations for handling membership constraints (e.g., conformance checking) and acting as leader, since both types of operations must be supported by the group members. The Group service is deployed on any node taking part in group management, and offers a RegGroup (resp. U nRegGroup) function for registering (resp. canceling) participation to a given group.

Note that our group service is different from WS-ServiceGroup [START_REF] Graham | Web services service groupspecification[END_REF], which is a recent proposal to standardize the terminology, concepts, message exchanges, WSDL and XML needed to express the aggregation of Web services and resources, in the following two most important aspects: (1) Group service of WSAMI aims to facilitate grouped nodes to share services, instead of to define the aggregate interface of services; (2) Group service of WSAMI defines membership via various constraints as illustrated in Sec. 2, instead of service interfaces.

Group Service Assessment

In order to evaluate our group management, we conduct experiments of group initialization of from 2 to 7 terminals, which are either laptops or PDAs. PDAs are Compaq iPaq H3970 with Intel XScale 400MHz processor and 64MB builtin RAM, running on familiar v0.74 and J2ME Personal Profile. Laptops are equipped with 500 MHz PIII CPU and 192 MB RAM, running on RedHat 9.0 and J2SE 1.4.

We measure group CPU time, which is the dedicated CPU time during the group member discovery and initialization. We compare the CPU consumption with and without the group leader calculating a group key with group key agreement5 (GKA). We thus measure the average CPU time for (i) a laptop when it acts as a leader or a nonleader (Fig. 2); (ii) a PDA when it acts as a leader or a nonleader (Fig. 3).

From the figures, it can be observed that (1) group key agreement (GKA) is expensive by inducing almost twice the CPU time; (2) a laptop consumes considerably less CPU time, which validates our choice of leader based on resource richness; (3) leaders indeed consume much more CPU time than ordinary nodes, which favors rotation of leaders among members. The rotation assures fairness among group members, especially when all members are resource-lite nodes.

CASE STUDY

This section discusses the implementation of one specific group management over MANET supporting scalable and efficient service discovery.

Scalable Service Discovery

To support scalable service discovery, a group called G ServDisc is defined with an associated membership constraint -Bounded(G f , H), i.e., all member nodes are reachable from the leader node within H hops. A service discovery process can be divided into two stages: local and global service discovery.

Local Service Discovery

Leader of a G ServDisc group has one specific functionality for service discovery: caching the description of the services available in the group. A service seeker thus always demands the group leader for a service query. When a leader receives a service query (including the service's WSDL-based functional interface and QoS parameters), it checks its cache content and sends back a hit message embedding the matching service description(s) if the group has the requested service. In order to provide users with better quality of service and balance the load among service providers, leaders select among multiple service provider candidates, if there exist, the provider that: (i) provides the service that best matches the query in terms of both functional interface and provided QoS, and (ii) is the less loaded. If the leader does not cache the description of the requested service, it initiates a global discovery, detailed as follows.

Global Service Discovery

In order to locate services available in the overall MANET in an efficient manner in terms of both response time and generated traffic, leaders need to interact with the other leaders that most likely cache the requested service description. This is achieved through (1) group profile, i.e., summary of available services in the group (2) cooperation among leaders.

We use Bloom filters [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF] to summarize the available services in the group, i.e., the set of cached WSDL-based service descriptions. Bloom filters are an efficient way of describing sets because of its compactness and independence of any predefined keywords characterizing services. Succinctly speaking, with Bloom filter, we are able to know with high possibility that if a service is provided within a group by simply checking if certain bits of the group service summary (i.e., a vector of certain length) are set to 1 6 .

As in our group management service, a leader advertises its group profile to other leaders by periodically broadcasts over N = 2 × H hops (i.e., 2 times the group size), using 2-hop bordercasting. For a newly elected leader, after it receives a beacon from a nearby leader, it demands from that leader the list of nearby group leaders, along with their profiles (e.g., Bloom filter and host capacity). In case of no beacon from any other leader, the leader broadcasts a network-wide advertisement using 2-hop bordercasting. By this means, every leader is able to obtain a global view of leaders and available services.

For less traffic overhead, our solution does not update the group profiles upon every change of available services. Instead, a request for updated profile of a leader is reactively demanded by a peer leader when the false misses (i.e., returns a Hit message while there is actually no matching service) percentage reaches a threshold value. When a leader receives a profile request, it sends either the complete bit vector or the list of bits that changed, depending on their respective storage size.

Therefore, as shown in Fig. 4, when a group member A seeks a service, it sends a query message to its leader B (message 1). B looks up its cache and sends back a hit message to A if it stores the description of the requested service. Otherwise, B looks up the Bloom filters of other nearby leaders, and send a query message to the M (M < M ax) other leaders that are likely to cache the description of the target service (message 2 and 3). C or D sends back a The NS-2 simulator7 is used to evaluate the performance of our service discovery protocol in terms of the cost of leader deployment at initialization time. Simulations are run for a duration of 500s. Each mobile terminal has a transmission range of 200m, and assumes a random waypoint mobility model with an average speed of 1m/s. OLSR [START_REF] Clausen | Optimized link state routing protocol[END_REF] is used as the underlying multi-hop routing protocol on top of the Ieee 802.11 MAC protocol. We consider a MANET of N nodes over a surface 600m × 600m. A group is bounded by H = 1 hop. In the simulation, 10% of the mobile nodes are service providers that offer E = 2 services, and each client node periodically seeks a service among the E × N × 10% services that are provided in the network.

Performance

To evaluate the performance, we measure (i) the traffic generated by the service seeker, and (ii) the traffic resulting from message forwarding. We compare our protocol with a decentralized, pull-based service discovery protocol that floods the network on demand, i.e., service query at a node is broadcasted using 2-hops bordercasting over the network. As shown in Fig. 5 and Fig. 6, Our service discovery protocol introduces a fixed cost corresponding to the deployment and updates of directories. This explains why our protocol is outperformed when there are very sporadic requests (i.e., as shown in the figures, one request every more than 200 seconds). Our protocol surpasses the decentralized, pullbased one when the rate of user request reaches a certain threshold. Note that with our protocol, the node density has low impact on the generated traffic due to the deployment of groups, since it does not affect the number of groups. By contrast, the performance of the flooding protocol suffers proportionally with the increase of node density.

CONCLUSION

Group management poses as a key middleware functionality for assisting the development of applications over mobile wireless ad hoc networks. Group management manages a dynamic network on top of which the application implements certain functions and achieve certain non-functional properties. Group management over wireless ad hoc networks has actually given rise to various studies concentrating on specific applications. However, a distinctive set of key attributes may be identified for groups, which can be exploited to design a generic group service that is customizable by applications.

This paper presents the design of such a generic group management service. At first, we introduce key attributes for group management over MANET, in particular based on applications in published literature. Those attributes amount to membership constraints related to location, group scale, trustworthiness and supported QoS of group members. We then present a group service that is generic with respect to membership constraints, and realizes three basic functions: group member discovery, group initialization and group dynamics management. Implementation of the generic group service is concretized in the context of the WSAMI middleware aimed at mobile distributed computing, which is based on the Web services Architecture. Finally, we present an example of group management built on our generic group service, which supports scalable service discovery in MANET. Our future work includes implement-ing group applications based on current middleware group service, such as collaborative editing session and group conferences.

Figure 1 :

 1 Figure 1: 2-hop bordercasting

Figure 2 :

 2 Figure 2: CPU time of a laptop

Figure 3 :

 3 Figure 3: CPU time of a PDA

Figure 4 :

 4 Figure 4: Global discovery

Figure 5 :

 5 Figure 5: Traffic at initial sender, compared with decentralized pull-based discovery

Figure 6 :

 6 Figure 6: Traffic due to message forwarding, compared with decentralized pull-based discovery

  Resource * w 1 + Elapsed time * w 2 (1) w 1 + w 2 = 1 Resource * w1 = CP U Load * w 11 + memory * w 12 + battery * w 13 + bandwidth * w 14 (2) w 1 = w 11 + w 12 + w 13 + w 14

	1. Resource richness. Powerful nodes with richer resources
	are considered more suitable as group leaders. This is
	because group leader consumes more resources such as
	battery and computing than other group members. It
	also improves group performance, because weak group
	leaders tend to be the bottleneck, e.g., group leader
	is responsible for forwarding inter-group communica-
	tion. In particular, we consider the following resource-
	related attributes: (a) CPU load; (b) memory; (c) bat-
	tery and (d) bandwidth.
	2. Time until now since last time being a leader. This
	factor contributes to load balance among peers.

The overall weight can be calculated as follows, with relative importance (e.g., w1, w11) specifically defined for different applications (e.g., by group initializer): weight =

When a node intends to create some group G f , it broadcasts via 2-hop bordercasting a disc message to its neighbors. This node, who initializes the group member discovery, is named group initializer. The disc message from a group initializer includes (1) the functional and non-functional attributes of the group it intends to create; (2) a unique group id. For example, to create a group with all nodes close to a fixed location, the initializer includes that reference location in the disc message.On receiving a disc message, the receiver node carries out conformance checking of local constraints, if it is interested

In the case of abrupt leaving of leader, the information need to be gathered again.

http://www.w3.org/2002/ws/arch

http://www-rocq.inria.fr/arles/download/ozone/

http://familiar.handhelds.org/

Readers are referred to[START_REF] Bhaskar | Group key agreement in ad hoc networks[END_REF] for details.

For more details, please refer to[START_REF] Sailhan | Scalable service discovery in MANET[END_REF]

http://www.isi.edu/nsnam/vint


Franc ¸oise Sailhan
email: francoise.sailhan@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

Scalable Service Discovery for MANET

Mobile Ad hoc NETworks (MANETs) conveniently complement infrastructure-based networks, allowing mobile nodes to spontaneously form a network and share their services, including bridging with other networks, either infrastructure-based or ad hoc. However, distributed service provisioning over MANETs requires adequate support for service discovery and invocation, due to the network's dynamics and resource constraints of wireless nodes. While a number of existing service discovery protocols have shown to be effective for the wireless environment, these are mainly aimed at infrastructure-based and/or 1-hop ad hoc wireless networks. Some discovery protocols for MANETs have been proposed over the last couple of years but they induce significant traffic overhead, and are thus primarily suited for small-scale MANETs with few nodes. Building upon the evaluation of existing protocols, we introduce a scalable service discovery protocol for MANETs, which is based on the homogeneous and dynamic deployment of cooperating directories within the network. Scalability of our protocol comes from the minimization of the generated traffic, and the use of compact directory summaries that enable to efficiently locate the directory that most likely caches the description of a given service.

Introduction

Ad hoc networks enable spontaneous connectivity among wireless devices, without requiring any particular infrastructure. In addition, ad hoc routing protocols increase connectivity by offering multi-hop communication, while supporting a continuously changing topology, leading to the automatic configuration of infrastructure-less Mobile Ad hoc NETworks (MANETs). However, effective exploitation of networked services within a MANET requires enabling the delivery of services that best match the application's requirements, still taking into account the MANET's dynamics.

The major challenges in enabling service delivery, i.e., service discovery and service invocation, within MANETs lie in:

• Enabling resource-constrained, wireless devices to discover services dynamically, while both minimizing the traffic generated by the discovery process and tolerating the intermittent connectivity of devices. • Enabling service delivery to a wide spectrum of devices, regardless of their hardware and software platforms. • Enabling service requesters to differentiate service instances according to provided non-functional properties, so that services can be matched against the applications' quality of service requirements. • Enabling service discovery in large MANETs, composed of hundreds of nodes, so as support the large class of applications envisioned for MANETs, in areas as diverse as military operations, rescue missions, pervasive computing and ambient intelligence. • Enabling bridging MANETs with infrastructure-based networks since Intranet and/or Internet connectivity remains the primary source of service provisioning. Such a feature allows devices that are located in the MANET to transparently access services offered in the interconnected networks (Internet or Intranet), and devices located outside the network to discover services provided in the interconnected MANETs.

This paper introduces a scalable service discovery protocol that meets the above requirements. The next Section first defines the mobile environment targeted by our service discovery protocol, and then evaluates existing protocols against the above requirements. Basically our service discovery protocol relies on a backbone of directories constituting a virtual network. Each directory performs service discovery in its vicinity (Section 3). Global service discovery within the overall network is then performed by the backbone which is composed of directories that cooper-ate and are dynamically deployed (Section 4). Performance evaluation of our protocol through simulation shows in particular the scalability of our protocol, considering generated traffic (Section 5). Finally, we conclude with a summary of our contribution (Section 6).

Service Discovery in the Mobile Ad Hoc Environment

MANET was initially mainly targeted at crisis applications 1 (e.g., military, emergency/rescue operations). Spurred by progress of technologies and their coming availability at low cost, ad hoc networks appear much valuable for civilian applications as well. They are in particular central to the vision of pervasive computing, due to their support for ubiquitous networking. Independent of the application domain, the mobile environment now builds upon hybrid networks, bridging MANETs and infrastructure-based networks ( § 2.1), and provides access to a rich variety of services, including services hosted by wireless nodes ( § 2.2). However, existing service discovery protocols for the wireless environment are mainly suited for small-scale MANETs. This leads us to introduce a discovery architecture structured as a virtual network in which directories cooperate towards scalable service discovery ( § 2.3).

Network architecture

We assume a MANET composed of nodes holding the same network interface 2 , with IP-level connectivity using the underlying routing protocol. We do not assume any specific routing protocol for the MANET, which may be reactive, proactive or hybrid. We simply consider that the protocol maintains routing information for nodes reachable in 1 hop, as implemented by proactive (e.g., OLSR [START_REF] Clausen | Optimized link state routing protocol[END_REF]) and hybrid protocols (e.g., ZRP [START_REF] Haas | A new routing protocol for the reconfigurable wireless networks[END_REF]). In case of reactive protocols (e.g., AODV [START_REF] Das | Ad hoc on demand distance vector routing IETF RFC 3929[END_REF]) information concerning nodes reachable in 1 hop are maintained by our service discovery protocol. Note that in case of scalable and dense ad hoc networks, proactive and hybrid protocols provide enhanced performances compared to reactive protocols. Nodes of the MANET are further heterogeneous in terms of resource capacities, and include today's wireless devices such as smart phones, PDAs, laptops, etc. We also consider that some nodes hold several network interfaces, and act as gateways with other networks, either ad hoc or infrastructurebased. This defines a hybrid network bridging MANETs and infrastructure-based networks, according to the specific networking capabilities of the wireless nodes (see Figure 1).

Service architecture

While service discovery protocols were initially introduced to deal with services provided by devices like printers or cameras, the increasing popularity of handheld devices has led to consider a rich variety of mobile services, as illustrated by scenarios in the area of pervasive computing, ambient intelligence or mobile-commerce. This further requires service-level interoperability among mobile devices, despite the heterogeneity of the supported software platforms. Interoperability among mobile devices is a long term research goal. However, pervasiveness of the Web allows assuming that a significant level of interoperability can already be achieved using the Web services architecture 3 . We thus consider a service-oriented architecture based on Web services, with wireless nodes hosting Web services, as enabled by, e.g., the WSAMI open source middleware4 [START_REF] Issarny | Developing ambient intelligence systems: A solution based on web services[END_REF] developed at INRIA in the context of the Ozone IST project 5 . We then build on standardization effort of the Web service activities that has in particular introduced XML languages for describing Web services' interfaces. Specifically, we use WSDL for service description. We further enrich WSDL to allow the specification of Quality of Service (QoS) parameters, as QoSawareness is a key requirement in the mobile environment [START_REF] Issarny | Software architecture for mobile distributed computing[END_REF]. Thus, service providers proactively provide QoS parameters together with the service's functional interface, to service requesters. Based on the work of [START_REF] Liu | QoS-aware service location in mobile ad hoc networks[END_REF], QoS specification includes both service-related and resource-related QoS parameters. Service-related QoS parameters decompose into: (i) security mechanisms supported by the service, (ii) reliability relating to the availability of the service over a specified period of time, and (iii) scalability specifying the capacity of serving additional requests for a specified period of time. Resource-related QoS parameters specify performance and capacity of the host, stating memory capacity, available energy, computation capacity, geographical localization support, connectivity (expressed in terms of the number of neighbors in the ad hoc network), and network capacity (expressed in terms of network type, mean bandwidth, and packet loss rate). Specification of the above QoS parameters is optional, and each parameter provides the following QoS attributes: name, value and expiration. The QoS expiration attribute is provided for parameters that evolve over time, and denote the point in time at which the provided QoS value is no longer valid. The QoS value is in the range [not supported, null, bronze, gold, platinum, infinite], from lowest to highest QoS level.

Discovery architecture

The major structural difference between existing service discovery architectures is the utilization or not of a central directory. For instance, well known solutions, such as Jini6 , UDDI 7 , Salutation 8 , rely on a central directory that stores information about services available in the network so as to enable service discovery and invocation. Discovery of the directory by service seekers and providers is in general based on multicasting. Then, service providers advertise their services to the central directory using a unicast message. And, to access a service, a client first contacts the central directory to obtain the service description, which is then used to interact with the service provider. Centralized resource discovery is much suited to wireless infrastructurebased networks. However, this makes the service discovery process dependent upon the availability of the central directory, which further constitutes a bottleneck. In order to increase the scalability of the discovery protocol, solutions presented in [START_REF] Castro | Locating application data across service discovery domains[END_REF][START_REF] Denny | Mobiscope: A scalable spatial discovery service for mobile network resources[END_REF] employ a distributed set of directories, which are deployed over base stations (or gateways) and are responsible for a spatial region (e.g., corresponding to a cell).

Decentralized resource discovery protocols appear better suited to ad hoc networks. Indeed, services and clients discover each others directly, as in, e.g., SLP [START_REF] Guttman | Service Location Protocol: Automatic discovery of IP network services[END_REF] and UPnP 9 . Specifically, when a client wants to access a service, it broadcasts a service query that is handled by available service providers, which is known as pull-based discovery. Alternatively, under push-based discovery, service providers broadcast service advertisements, which are possibly cached by nodes for later service invocation. The ma-jor drawback of the above decentralized solutions is that broadcasting leads to flood the network. Another approach to disseminating service information while not relying on broadcasting is to use geographic information for routing [START_REF] Klimin | A hybrid approach for location-based service discovery in vehicular ad hoc networks[END_REF]. Nodes periodically send advertisements along a geographic trajectory (basically, north-south and west-east), and nodes on the trajectory cache the advertisements. Then, when a client seeks a service, it sends a query that eventually intersects the advertisement route at a node that replies to the client. This solution assumes that the density of nodes is high enough and further leads to cache service advertisements on a large number of nodes. Hence, it incurs resource consumption that may not be accommodated by wireless, resource-constrained nodes. Resource consumption is further increased by the required support for geographical location (e.g., GPS). Yet another approach is to couple the service discovery protocol with network-layer multicast dedicated to MANET [START_REF] Kozar | Service discovery in mobile ad hoc networks: An overall perspective on architectural choices and network layer support issues[END_REF][START_REF] Helal | Konark: A service discovery and delivery protocol for ad hoc networks[END_REF]. However, multicast protocols generate a large number of control messages, and are thus primarily suitable for data-intensive applications like multimedia streaming. Hence, the use of a multicast protocol for service discovery cannot be undertaken in general and should rather be adopted when the MANET is dedicated to data-intensive services (e.g., home networking). Alternatively, one may limit service discovery to the local area and thus broadcast messages over a limited number of hops, as in GSD [START_REF] Chakraborty | GSD: a novel groupbased service discovery protocol for MANETs[END_REF]. GSD is a group-based service discovery protocol that performs local discovery of available services. To achieve global discovery, GSD classifies services into several groups, according to a service hierarchy expressed in DAML 10 , and includes in each advertisement that is broadcasted, the list of groups that the sender has seen in its vicinity. Then, the group information is used to selectively forward a service request to other nodes. This solution requires the group information to be exchanged and included in each advertisement. As a result, it increases the size of the exchanged messages and further relies on a metric that quantifies the probability of presence of the corresponding group in the vicinity. As briefly surveyed above, existing service discovery protocols for the wireless environment are mostly aimed at small-scale MANETs (i.e., comprising less than 30 nodes according to published performance). The following introduces a service discovery protocol aimed at large MANETs (i.e., comprising at least about 100 nodes). Our primary goal is to keep to a minimum the traffic generated by the service discovery process, so as to minimize consumption of resources and in particular energy. Following the above survey, our design is based on a centralized discovery architecture, as it induces less traffic. Directories are further distributed and deployed dynamically for the sake of scalability. Specifically, our discovery architecture is structured as a virtual network (see Figure 2 is composed of a subset of nodes of the MANET acting as directories. These directories represent a backbone of nodes responsible for performing service discovery. These directories are deployed so as at least one directory is reachable in at most a fixed number of hops, H, whose value is dependent upon the nodes density. Directories cache the descriptions of Web services available in their vicinity which is defined by H. Hence, wireless nodes that do not act as directories do not have to maintain a cache of service descriptions, and the network is not flooded by service advertisements. A service seeker simply sends a query to the directory for local service discovery ( § 3). If the description of the requested service is not cached by the local directory, the directory selectively forwards the query to other directories so as to perform global discovery ( § 4). Selection of directories to which service queries are forwarded, is based on the exchange of profiles among directories. The directory profile provides a compact summary of the directory's content and a characterization of the host capacity. Directory profiles allow both guaranteeing that service queries are issued to directories that are likely to cache the description of the requested service and to keep to a minimum the generated traffic. Most of the ad hoc networks deployed today are hybrid networks instead of pure ad hoc networks. Then, another critical issue lies in providing convenient features so as to enable discovery of services over a hybrid network. This is supported through mobile nodes acting as gateways between networks.

Local Service Discovery

As briefly sketched above, directories within our discovery protocol are responsible for: (i) caching the description of the services available in the directory's vicinity to answer to service queries, and (ii) advertising their presence to nodes within their vicinity.

A directory caches service advertisements that are published proactively by service providers to the directory(ies) over H hops, which define the coverage of the directory (with respect to the specific sender/directory). Management of the directory content further relies on a cache replacement policy, which is not detailed here due to the lack of space. Briefly stated, the cache is managed so as to remove first the description of the services that are the less likely to be accessed in the near future or may be retrieved from the other directories deployed in the MANET. Each service provider sets its periodicity of publicity according to: (i) the number of mobile terminals that are present in its vicinity, as known from the routing table managed by the underlying routing protocol or by the directory advertisements, (ii) the traffic load, congestions and collisions, as known by monitoring the traffic sent on the channel and the error rate, and (iii) the service's dynamic QoS attributes, as known from the service description.

When a directory receives a service query (including the service's WSDL-based functional interface and QoS parameters), it checks its cache content and sends back a hit message embedding the matching service description(s) -if any. In order to provide users with better quality of service and balance the load among service providers, directories select services that: (i) best match the query in terms of both functional interface and provided QoS, and (ii) are the less loaded, which is evaluated using a pricing-based scheme such as the one discussed in [START_REF] Liu | On service allocation in selfish mobile ad hoc networks[END_REF] ure 3). Basically, the broadcast initiator broadcasts the message to all the nodes reachable in 1 hop, and selects among those nodes, the minimal number of nodes (called bordercast nodes) that allow reaching all the nodes accessible in 2 hops and whose zone of influence does not overlap. The selected nodes will then forward the message and the target nodes will perform the same algorithm as the broadcast initiator. The process is repeated until nodes at H hops are reached.

Directory deployment

In order to deploy dynamically and homogeneously directories in the MANET, directories are elected on the fly by mobile nodes. The election process accounts for directories that are already deployed so as to keep to a minimum duplicate directories' coverage. However, a given node can be covered by more than one directory, depending on the movement of nodes. Specifically, directories advertise periodically their presence every ∆ τ time unit. Then, if for a given period of time α × ∆ τ (α being set according to the network's load), a mobile node (that is not hosting a directory) does not receive any directory advertisement, the node initiates the election of a directory.

The election process starts by broadcasting an election message over H hops, still using 2-hops bordercasting. Mobile nodes receiving the election message can either refuse or accept to act as a directory, depending on their capacity, considering that fair behavior of nodes is promoted using the aforementioned pricing-based scheme [START_REF] Liu | On service allocation in selfish mobile ad hoc networks[END_REF]. When a node is willing (resp. refusing) to act as a directory, it sends back an acceptance (resp. refusal) message to the initiator of the election, providing its capacity in terms of available resources and its context parameters characterizing the node's environment (i.e., stability level, a list of directories covering the node, a list of mobile terminals reachable in 1 hop and available bandwidth). Finally, the initiator elects a directory based on the capacity and context of the nodes that replied, and sends a notification message to the chosen node. The main selection criteria is the directory's coverage, i.e., the node that has the highest number of neighbor nodes and the smallest number of directories in its vicinity (i.e., H). This mechanism allows electing the directory that offers the best physical properties and to distribute efficiently directories since directories are elected in the network area that is the less covered.

In case, two (or more) mobile nodes initiate simultaneously an election process, the one having the smallest IP address is chosen as the coordinator (i.e., the one that processes the election), while the others stop running the election process. Elected directories change periodically to fairly distribute the load of service discovery among mobile nodes, and to account for their disconnection, either volun-tary or involuntary because of limited battery lifetime. A directory that passes on its role then initiates an election process, as defined above.

Global Service Discovery

The above directory-based service discovery allows discovering services that are (or were previously) in the vicinity of the local directory. However, nodes need to be able to locate services available in the overall MANET and even in the interconnected networks. This is achieved through cooperation among directories ( § 4.2), possibly relying on nodes acting as gateways to bridge with other networks ( § 4.3). However, efficiency of the discovery process both in terms of response time and generated traffic requires interacting with the directories that most likely cache the description of a service that is not known locally. Towards that goal, we introduce directory profiles that provide host characterization and a compact summary of the directory content ( § 4.1).

Directory profile

We use Bloom filters as a method for summarizing the content of a directory, i.e., the set of cached WSDL-based service descriptions. Bloom filters [START_REF] Bloom | Space/time trade-offs in hash coding with alowable errors[END_REF] are an efficient way of describing sets because: (i) they are compact summaries and thus induce limited storage requirements and bandwidth utilization, and (ii) unlike traditional profile-based approach to the characterization of cache content (e.g., [START_REF] Chakraborty | GSD: a novel groupbased service discovery protocol for MANETs[END_REF]), they do not require to predefine a static set of keywords characterizing some categories or types of popular services that serve generating profiles. The main idea is to compute a vector v of m bits (initially set to 0), which corresponds to a Bloom filter. First, k independent hash functions h 1 , h 2 , ..., h k , each with range {1, ..., m} are chosen. From a practical point of view, the hash functions are built by: (i) calculating the md5 signature of 128 bits [START_REF] Rivest | The md5 message-digest algorithm[END_REF] although other hash functions may be used, (ii) dividing the 128 bits into k groups of 128/k bits words, and (iii) taking the modulo m of each 32 bits word. Then, for each service description w stored in the directory, the service description is hashed with the k independent hash functions. The bits of vector v whose positions are given by the results of the k hash functions are set to 1, i.e., the bits at positions h 1 (w) h 2 (w), ..., h k (w) are set to 1 in v.

Computation of the directory's Bloom filter is based on hashing service descriptions. However, a service query may contain a subset of the service's description rather than the whole service description. Computing a hash for the complete service description is thus not sufficient. An alternative would be to hash each possible subset of the service description but the resulting computation would be too costly. Thus, we limit the number of subsets of the service description that are extracted for hashing by considering offered operations individually. Basically, we define a tree of depth 2 from the service description, where:

• The root of the tree corresponds to the service and its value is the service's name. • The root has as many child nodes as operations provided by the service, and the value of each node is the operation name • Each of the above node has as many child nodes as service-related QoS parameters defined by the service, and the value of each node is the name of the parameter followed by its value (i.e., the expiration attribute is not included).

The root and all the paths of length 1 (i.e., limited to an operation) and 2 (including a QoS parameter) of the above tree then define all the subsets of the service description. The value of each subset is given by the concatenation of the value of the nodes of the specific path, and it is hashed for inclusion in the Bloom filter.

In order to determine whether a directory caches a service description w, using the directory's Bloom filter, we consider each subset sub i (w) of the service description, as defined above. For all the subsets, all the bits at position h 1 (sub i (w)), h 2 (sub i (w)), ..., h k (sub i (w)) are checked. If they are all set to 1, the directory is likely to contain w. However, there is a non-null probability for the directory to not cache w, which is known as false positive. The probability of a false positive is given by: (1

-(1 -1 m ) knp ) k ≈ (1 -e knp/m
) k , with n (resp. m) corresponding to the number of service descriptions stored in the directory (resp. the size of the Bloom filter), and p corresponding to the average number of subsets. The value of k and m should thus be chosen so that the probability of a false positive is kept to a minimum, i.e., k ≈ m ln2 np . However, in practice, the value given to k is less than the optimal one to reduce the computation overhead of hashing. As an illustration, consider a directory that stores the description of 100 services, a service description taking 3kbits. Figure 4 gives the effectiveness of Bloom filter for such a directory, giving the probability of false positive according to the Bloom filter size for k = 1, ..., 8. One can see that a Bloom filter size of 700 bits with k ≥ 3 suffices to to have a probability of false positive that is close to 0. When the directory content is updated, the directory's Bloom filter needs to be updated accordingly. In order to minimize this cost, we use the following counterbased solution. We associate a vector c of counters with the directory's Bloom filter v, where c(i) counts the number of services that have set to 1 the bit at position i in v. For instance, if the caching of 2 service descriptions has led to set to 1 the bit at position i in v, c(i) = 2. Similarly, when a service description, w, is removed from the cache, the coun- ters that were incremented in c following the caching of w, are decremented. Then, when an element of c reaches 0, the corresponding bit in v is set to 0. As a result, the directory Bloom filter is updated at low cost.

Cooperative service discovery

When a newly configured directory D enters the network, if D is aware of at least one directory A (as known whether from the acceptation or refusal messages exchanged during the election period or from the previous vicinity of D, then D sends a request to directory A and A sends back the list of profiles (i.e., Bloom filter and host capacity) which it hold. Otherwise, directory D broadcasts an advertisement over the network using 2-hops bordercasting. Directories that receive the advertisement send back their profile (i.e., Bloom filter and host capacity). In both cases, directory D creates the corresponding list of peer directories, storing the directories' profiles. Then dually, D later sends its local profile to peer directories, once it caches a significant number of service descriptions. Each directory further periodically broadcasts an advertisement, including its profile, over N = 2×H hops (i.e., 2 times the size of the directory vicinity), using 2-hops bordercasting. This allows directories to discover peers according to their respective mobility pattern.

When two formerly separate networks N and M merge following a new wireless link between two frontier nodes (b and c), then directory(ies) Dir N 1 , • • • , Dir Nn (respectively Dir M1 , • • • , Dir Mm ) composing the virtual network of N and respectively M should exchange their profiles. Let Dir N 1 be the directory covering node b, and Dir M1 a directory covering node c. At least one directory (let Dir N 1 be this directory, without lost of generality) detects the presence of directory Dir M1 . Dir N 1 and Dir M1 then exchange the list of profiles they hold. Finally, Dir N 1 sends the list of profiles of directory(ies) composing the virtual network of N (resp. M ) to the peer directory(ies) composing the virtual network of M (resp. N ). Changes to the directory content has to be forwarded to peer directories. Scalability of our solution in particular comes from the fact that directories profiles do not have to be accurate all the time, i.e., updated upon every change to the directory's content. Instead, a request for updated profile to a directory D is reactively sent by a peer storing the profile when the percentage of false misses 11 (and hence degradation of the hit ratio) reaches a given threshold. When a directory receives a profile request, it sends either the complete bit vector or the list of bits that changed, depending on their respective size. According to the directory deploy- , leading to execute the following discovery process. When B receives the query message from A, it probes its cache and sends back a hit message to A if it stores the description of the requested service. Otherwise, cache miss at B leads B to probe the Bloom filters of known peer directories, and send a query message to the M (M < Max) peer directory(ies) that are likely to cache the description of the target service (messages 2 and 3). Specifically, let d be the number of known peer directories, at time t, directory B requests among the d directories, the l directories that minimize the following function for

1 ≤ i ≤ d: min i (f i (t) + g(t, n i )), with f i (t)
giving the remaining battery lifetime at time t, which is computed from the battery discharge curve available from the operating system API, and the battery indicator previously provided by the directory i at time t . This function is then curved so that at a given point of time (e.g., when reaching 80 % of the battery lifetime), the cost grows rapidly. Function g further accounts for the impact of forwarding the query message to n i mobile terminals upon the 11 also called false positive remaining battery lifetime. Selection of the directories to which the query message should be forwarded further takes into account the distance between the respective directories. Finally, requested directories (e.g., C and D in the figure) send back to B a Hit message (including the description of the service that matches with the request) if the requested service is stored (message 4). Notice that no miss message is sent to B to limit traffic. Finally, B sends back to A either a Hit or Miss message (message 5), the latter being sent if B does not receive any Hit message after a given timeout.

Service Discovery in the hybrid network

Several types of networks (i.e., wired networks and different types of wireless networks) can coexist in an area without being interconnected since they are administered by distinct entities in different administrative domains. A classical solution to bridge those networks is to connect wireless nodes with the wired network using a wireless access point. Another solution is based on a mobile terminal holding several network interfaces and acting as a gateway to bridge different administrative domains (e.g., wired network and ad hoc network). More precisely, one of these network interfaces communicates with mobile terminals in the MANET, whereas the other interfaces are used to communicate with external networks (e.g., wired network) and to connect these latter with the ad hoc network. Interconnected networks form a new network called hybrid network. In a hybrid network, although a mobile terminal (with one network interface in ad hoc mode) can communicate with further networks through the gateway nodes, the service discovery process is commonly limited to services available in the ad hoc network. Enabling service discovery in all the networks composing the hybrid network requires mobile terminals that act as gateways to: (i) advertise their service (e.g., with a related gateway protocol, a zeroconf protocol, or using our protocol), and (ii) act as directories, implementing the same cooperative behavior as discussed above. A gateway directory then holds the description of services available in all the networks composing the hybrid network (but the Internet), and advertises itself to the networks it bridges (but the Internet) composing the hybrid network.

Furthermore, to support service discovery in a managed network in which a network administrator deploys directories, clients and service providers behave differently. Since clients and service providers do not need to elect a directory, they can listen for directories announcements or rely on the DHCP protocol.

With our approach, services provided within the ad hoc network are visible from mobile terminals in the interconnected and external networks forming the hybrid network. This is especially useful in an enterprise network where some ad hoc networks can be created and interconnected to the Intranet network. Notice that the goal of the proposed service discovery protocol is not to perform service discovery in large scale networks such as the Internet. As a result, we assume that a client willing to access some Web service located in the Internet relies on Internet-level service discovery, such as UDDI.

Assessment

The NS simulator 12 is used to evaluate the performance of our service discovery protocol. Simulations are run for a duration of 500s, and data are collected from the beginning of the simulation to provide the cost of directory deployment at initialization time. We consider an ad hoc network of mobile terminals with transmission range t = 200m, and that is such that mobile terminals are initially uniformly distributed, and randomly move at an average speed of 1 m/s. We use OLSR [START_REF] Clausen | Optimized link state routing protocol[END_REF] as underlying multi-hop routing protocol on top of the IEEE 802.11 MAC protocol. We in particular take advantage of the routing protocol facilities for implementing 2-hops bordercasting: instead of computing bordercast nodes (also called multi-point relays), we use the bordercast nodes selected by the multi-hop routing protocol. This allows us to further reduce the traffic generated by our protocol, as electing bordercast nodes introduces extra traffic due to control messages sent periodically to indicate to a given node that it has been selected by another to be its bordercast node. In order to provide an accurate measure of the traffic generated by our service discovery protocol, we take into account both: (i) the traffic generated by the initial sender, and (ii) the traffic generated by message forwarding. The sum of both traffic gives the cost of broadcasting. In the following, each traffic is provided separately.

We first consider a MANET of N nodes over a surface S = 600m × 600m. The MANET is structured around directory whose coverage corresponds H = 1 hop. Figure 7 and 6 gives the traffic generated by our Web service discovery protocol for the above MANET, according to nodes density, considering each type of message separately. In the simulation, 10% of the mobile nodes are service providers that offer E = 2 services, and each client node periodically seeks a service among the E × N × 10% services that are provided in the network. As a result, the traffic generated by service queries and advertisements increases with the nodes density. The nodes density has a low impact on the traffic generated by the deployment of directories (i.e., election, directory advertisement, and Bloom filter exchange messages), which is stable, except for messages sent by nodes that accept to act as directories during the election process. The latter result was foreseeable since the number of election repliers is equal to: S N ×π×t 2 ×H 2 . The traffic resulting from the exchange of Bloom filters is independent of the nodes density, since the number of directories do not directly depends on that parameter. Furthermore, this traffic has a low impact on the overall traffic, while it enables discovering services known by remote directories and keeping keep to a minimum the number of requests exchanged between directories. The difference between the traffic generated by queries from service seekers and those from directory seekers comes from the fact that a directory reply includes the reply to both the directory and service query. The traffic corresponding to directory requests (i.e., service queries sent by directories to other directories) and the exchange of Bloom filters together with the difference between directories replies and service queries give the cost for enabling global discovery in the overall MANET, compared to local discovery. Figures 8 and9 compares our protocol with a decentralized, pull-based service discovery protocol that floods the network on demand, i.e., service query at a node is broadcasted using 2 hops bordercasting facilities over the MANET. Simulation parameters are the same as above. Our service discovery protocol induces a fixed cost, which corresponds to the deployment and update of directories. It appears that our protocol performs better than a decentralized, pull-based protocol when the rate of service queries reaches a given threshold. Notice that when the user's request rate increases, the performance of the flooding protocol decreases proportionally. We now consider a MANET of N = 90 nodes over a surface S = 1000m × 1000m. Figure 10 evaluates the traffic generated by our service discovery protocol according to the number of hops (i.e., value of H) defining a directory coverage. The cost of directory election, including the traffic generated by the broadcast message sent by the initiator of the election, and the replies sent by nodes accepting to act as a directory (in the simulation, all the nodes accept) is quite stable since there is a balance between the number of election initiators (which is conversely proportional to H) and the number of nodes replying to the election initiator (which is proportional to nodes density and H). The traffic induced by the exchange of Bloom filters is directly proportional to the number of directories deployed over the network. The figure also gives the cost associated with forwarding service queries and publicities (corresponding to unicast messages), which is proportional to H since the number of hops directly impact on the average distance between a client node and a directory. Taking into account the cost of directory deployment (election messages, Bloom filter exchange and directory assignment), it appears that an optimal value for H is 2. However, since the client's requests rate directly impacts on the forwarding of service queries, the value of H must take it into account and be changed on the fly, so as to be conversely proportional to the client's requests rate.

We provide in Figure 11 an evaluation of the average response time per node according to node velocity, consid- ering a topology of 1000m × 1000m composed of N = 50 and H = 2 nodes. This evaluation demonstrates that the service discovery protocol is quite insensitive to nodes velocity. This result is due to the fact that an increased mobility of directories and service providers causes a higher dissemination of the service descriptions among directories.When a client requests a directory, the probability that the requested service description is held by the requested directory is higher. The overhead (in term of delay) caused by the link failures is balanced by this fact. Note that when path failure occurs, directories are still reachable (thanks to the multi-hop routing protocol).

Conclusion

The vision of pervasive computing and/or ambient intelligence requires enabling ubiquitous computing and networking so that mobile users can seamlessly get access to digital services anywhere, anytime. MANETs are one enabler of such a vision, providing networking capabilities to mobile devices without requiring any infrastructure. However, the specifics of MANETs such as potentially highly dynamic topology and networking of heterogeneous wireless nodes whose energy needs to be saved for enhanced autonomy, require special care in the handling of distributed service provisioning. In particular, the discovery of services must allow accessing services of the overall MANET for increased availability, while limiting resource consumption in the network. Existing discovery protocols, including the most recent ones specifically designed for MANETs, tend to induce significant traffic overhead, which make them primarily suitable for networks comprising a few number of nodes (i.e., less than 30 according to published performance). This paper has introduced a scalable service discovery protocol aimed at MANETs composed of up to a hundred of nodes, and further supporting bridging with other networks, either ad hoc or infrastructure-based. While decentralized service discovery is a priori more suited to the specifics of MANETs by not assigning any specific role to given nodes, it is too costly in terms of traffic. But, centralized service discovery based on service directory(ies) either makes the protocol too much dependent on specific node(s) or induces too much resource consumption in the network.

Our solution relies on the dynamic and homogeneous deployment of cooperating service directories within the MANET. The MANET is structured around a directory backbone in which directory coverage is defined with respect to a given number of hops, which is set according to the nodes density, as known from the underlying routing protocol. Dynamic deployment of directories is then carried out so that directories cover distinct areas. Scalability of our solution further comes from the fact that: (i) our protocol minimizes the generated traffic using bordercasting, and (ii) the directory content is summarized using a Bloom filter, which provides a highly compact summary that may be exchanged with other directories, and is used to accurately locate the directory that holds the description of a given service. We have evaluated our solution through simulation, which shows the efficiency of our protocol. We are currently implementing our protocol as a middleware service of the WSAMI middleware 13 , which supports the composition of Web services deployed over mobile nodes in a hybrid network.

1Figure 1 .

 1 Figure 1. Network architecture

Figure 2 .

 2 Figure 2. Discovery architecture

Figure 3 .

 3 Figure 3. 2-hops bordercastingresponsible for being known to services providers and requesters, i.e., for advertising their presence to nodes over H hops. As directory advertisement relies on broadcasting, network flooding is avoided by limiting the broadcast to the directory coverage (i.e., H hops), and further reducing the related traffic as follows. First, when a packet has already been received, it is not forwarded. Second, we use 2-hops bordercasting to drastically reduce network traffic (see Fig-

Figure 4 .

 4 Figure 4. Probability of false positive using Bloom filters

Figure 5 .

 5 Figure 5. Global discovery

Figure 6 .Figure 7 .

 67 Figure 6. Traffic generated according to nodes density

Figure 8 .

 8 Figure 8. Comparison of messages length with decentralized, pull-based discovery

Figure 9 .Figure 10 .

 910 Figure 9. Comparison of traffic with decentralized, pull-based discovery

Figure 11 .

 11 Figure 11. Average delay comparison

  . If the directory does not cache the description of the requested service, it initiates a global discovery, as detailed in Section 4. Directories are

	Source
	1-hop bordercasting nodes
	2-hops bordercasting nodes
	Node 1-hop reachable from the source
	Node 2-hops reachable from
	the source
	Directe communication
	broadcast message

Proceedings of the 3rd IEEE Int'l Conf. on Pervasive Computing and Communications (PerCom 2005) 0-7695-2299-8/05 $20.00 © 2005 IEEE

http://www.w3.org/2002/ws/

Web Service for AMbient Intelligence.

http://www.extra.research.philips.com/ euprojects/ozone Proceedings of the 3rd IEEE Int'l Conf. on Pervasive Computing and Communications (PerCom 2005)

http://www.sun.com/software/jini

http://www.uddi.org

http://www.salutation.org

http://www.upnp.org

http://www.daml.org Proceedings of the 3rd IEEE Int'l Conf. on Pervasive Computing and Communications (PerCom 2005)

Proceedings of the 3rd IEEE Int'l Conf. on Pervasive Computing and Communications (PerCom 2005)

http://www.isi.edu/nsnam/vint

http://www-rocq.inria.fr/arles/download/ozone Proceedings of the 3rd IEEE Int'l Conf. on Pervasive Computing and Communications (PerCom 2005) 0-7695-2299-8/05 $20.00 © 2005 IEEE