Nicolas Le Sommer
email: nicolas.le-sommer@univ-ubs.fr

Yves Mahéo
email: yves.maheo@univ-ubs.fr

Location-Aware Routing for Service-Oriented Opportunistic Computing

Keywords:

Smartphones, tablets, netbooks and laptops are intensively used every day by a large part of the population. These devices-which are equipped with Wi-Fi interfaces-can form disconnected mobile ad hoc networks (DMANETs) dynamically. These networks may allow service providers, such as local authorities, to deliver new kinds of services in a wide area (e.g., a city) without resorting to the infrastructure-based networks of mobile phone operators. This paper 1 presents OLFServ, a new location-aware forwarding protocol dedicated to service-oriented opportunistic computing in DMANETs. This protocol implements several self-pruning heuristics allowing mobile nodes to decide whether they efficiently contribute in the message delivery. The protocol has been implemented in a service-oriented middleware platform, and has been validated through simulations, which proved its efficiency.

I. INTRODUCTION

Over the last years, handheld devices such as smartphones or tablets have become widely spread and used through the population. These devices, which are equipped with wireless communication interfaces-often complemented by GPS (Global Positioning System) receivers and various sensors-, allow their users to connect to the Internet and to use services hosted in remote servers just as if they were at home using a wired connection. This kind of service provision knows a great development, but it relies on a fixed and often heavy infrastructure, and is not without constraints for the client when considering for instance the cost of resorting to licensed frequency bands (Universal Mobile Telecommunications System, General Packet Radio Service) or the limited geographical scope of a Wi-Fi hotspot.

An alternative has been envisioned since several years through mobile ad hoc networking. Mobile handheld devices can form mobile ad hoc networks spontaneously, and this ability can be exploited in order to artificially extend networks composed of some sparsely distributed infostations with a view to offering a wide service access to end-users. An illustration of this kind of network is shown in Figure 1: devices with Wi-Fi interfaces operated in ad hoc mode are present in the environment; most of them are hold by mobile users and few of them, the infostations, are fixed. In practice, because of the potentially low density of devices, their mobility and the short communication range of wireless interfaces, the topology of such networks suffers from frequent and unpredictable changes. The network is regularly fragmented in several distinct communication islands thus entailing an intermittent connectivity between devices and the impossibility to ensure an end-to-end connectivity. For these reasons, this type of network is called a DMANET for Disconnected Mobile Ad hoc Network.

In DMANETs, devices can communicate directly only when they are in range of one another. Intermediate nodes can be used to relay a message from a source to its destination following the "store, carry and forward" principle. The routes are therefore computed dynamically at each hop while the messages are forwarded towards their destination(s). Each node receiving a message for a given destination is thus expected to transmit a copy of the message to one or several of its neighbors. When no forwarding opportunity exists (e.g., no other nodes are in the transmission range, or the neighbors are evaluated as not suitable for that communication) the node stores the message and waits for future contact opportunities with other devices to forward the message. Thanks to this principle, a message can be delivered even if the client and the destination are not present simultaneously in the network, or if they are not in the same network island at emission time.

Devising an efficient routing based on the "store, carry, and forward" principle has been the subject of many research efforts in the so-called domain of Opportunistic Networking [START_REF] Nguyen | Routing in Opportunistic Networks[END_REF]. The main problem is to establish a compromise between the speed at which the message reaches its destination and the resources consumed globally in the network, namely the storage space required in the intermediate devices and the bandwidth used when transmitting messages between devices. Flooding the network with copies of the message is known to be the fastest way to attain the destination in theory but its cost is considered prohibitive. On the other hand, keeping a single copy of the message in the network and passing it from one device to its neighbor when possible is an economical solution but tends to slow down-if not jeopardize-the propagation of the message towards its destination. A common approach is to allow an intermediate device to generate a limited number of copies of the message and leverage on contextual information for selecting the best devices to which these copies are conveyed. The considered context can take various forms, related for instance to records of encounters with other devices or to device's location.

Although routing is a key aspect in DMANETs, it should not be considered as the ultimate objective but rather as a first step towards middleware tools adapted to distributed application development. Indeed, legacy applications (often based on strong connectivity assumptions) cannot be straightforwardly transposed into the specific context of DMANETs, or do not take full benefit of the pervasive aspect of DMANETs.

The effective emergence of new applications is dependent on the capacity to discover, compose and exploit heterogeneous resources spread on a disconnected network. The notion of Opportunistic Computing has been introduced to emphasize the gap between issues related to opportunistic networking, that mainly aims at forwarding message packets, and those related to application design and implementation [START_REF] Conti | From Opportunistic Networks to Opportunistic Computing[END_REF], [START_REF] Mahéo | Beyond Opportunistic Networking Protocols: a Disruption-Tolerant Application Suite for Disconnected MANETs[END_REF].

Because of its intrinsic loosely-coupled nature well adapted to opportunistic computing, a first obvious paradigm to investigate is service provisioning: hardware or software resources available in the network are abstracted as services. A service is hosted by a device that plays the role of service provider.

Other devices in the network, acting as clients, will try to discover provided services so as to be able to invoke them remotely. An intermediate selection phase may take place before invocation, when the client is able to choose between several services. Service provisioning in connected networks has been extensively explored (Web Services are a wellknown example) but in the framework of DMANETs, issues regarding discovery, selection and invocation introduced by this paradigm are seldom addressed2 . The case in which services are provided only by fixed infostations is particularly interesting because the range of services susceptible to be deployed on this kind of platforms is very large compared with what can be done on mobile devices. Indeed, infostations are stable, not as constrained as mobile devices in terms of resources (primarily regarding power), and their potential connection to the Internet allows an easy access to a huge amount of information. This paper presents OLFServ, a new opportunistic and location-aware forwarding protocol we have designed in order to support both service discovery and service invocation in DMANETs. OLFServ is a key element of a middleware platform we develop to investigate service provisioning in DMANETs [START_REF] Sassi | Towards an Opportunistic and Location-Aware Service Provision in Disconnected Mobile Ad Hoc Networks[END_REF]. Based on the location data collected by the platform from the wireless interface and/or the GPS receiver of the device, OLFServ makes it possible to perform an efficient and geographically-based broadcast of both service advertisements and service discovery requests, as well as a location-driven service invocation. OLFServ implements several self-pruning heuristics allowing intermediates nodes to decide themselves if they are "good" relays to deliver the messages they receive from their neighbors (i.e., if they contribute to bring a message closer to its destination). These heuristics aim to

• progressively refine the area where a message can be disseminated until reaching its destination; • perform source routing when it is possible;

• support the client mobility by computing the area where the client is expected to be when it receives its response; • avoid message collisions by implementing a backoff mechanism. Thanks to these heuristics, only a small subset of relevant intermediate nodes will forward the messages in given geographical areas or in given directions.

The remainder of the paper is organized as follows. Section II brings to the fore the main issues that must be addressed in order to discover and to deliver some services in DMANETs efficiently. Section III presents the assumptions on which protocol OLFServ is based, the detailed specifications of the self-pruning heuristics it implements, and how it works on an example. Section IV presents some simulations results we obtained for OLFServ. Research works dealing with routing protocols in DMANETs are presented in Section V. Section VI summarizes our contribution.

II. RATIONALE FOR SERVICE-ORIENTED OPPORTUNISTIC COMPUTING

When targeting DMANETs, the service-oriented opportunistic computing paradigm introduces new issues compared to the mere provision of message passing. These issues pertain namely to the discovery, the selection and the invocation of pervasive services, imposing de facto the design of new routing protocols suited to both discovery and delivery of services, as well as the development of middleware platforms supporting distributed computing tasks in environments where disconnections and network partitions are the rule. These aspects are discussed in the remainder of this section.

A. Service discovery

In disconnected, or partially connected, MANET, no device is stable enough, or accessible permanently, to act as a service registry. Mobile clients should therefore be responsible for discovering the services offered in the network reactively and/or proactively, and for maintaining their own list of services. The reactive discovery is usually achieved by processing the unsolicited service advertisements broadcast by service providers, while the proactive discovery is performed by broadcasting service discovery requests in the network and by processing the advertisements returned in response by providers. In such a distributed discovery process, all mobile nodes receiving an advertisement or a discovery request are not expected to rebroadcast this message systematically and immediately, because if they do so, they will generate too much network traffic and could even lead to network congestion. To cope with this problem, which is known as the broadcast storm problem [START_REF] Ni | The Broadcast Storm Problem in a Mobile Ad Hoc Network[END_REF], some heuristics must be devised in order to reduce the number of senders and to broadcast the messages asynchronously. Moreover, based on the "store, carry and forward" principle, the discovery messages can be disseminated in a wide area, even if the services are relevant only in a restricted one. Thus, it seems to be suitable to circumscribe the dissemination of these messages geographically, as well as to limit their dissemination in the network by defining a life time and a maximum number of hops.

B. Service selection

A selection process may precede the invocation, when the opportunity is given to the client application to choose among several service providers. Thus, it could be interesting to select a provider according to its location, and to transparently select another one among a set of relevant ones when the current provider becomes inaccessible. In previous works, we proposed two different solutions for this issue: one that relies on a content-based service invocation [START_REF] Mahéo | Service Invocation over Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF] and another one that relies on a dynamic and transparent update of the service references [START_REF] Sassi | Towards an Opportunistic and Location-Aware Service Provision in Disconnected Mobile Ad Hoc Networks[END_REF]. These two solutions have been implemented in the service management layer of our middleware platform.

C. Service invocation

In opportunistic networks, no end-to-end routes are maintained between a client and a provider by an underlying dynamic routing protocol such as AODV or OLSR. A priori, a node does not know which is the best next forwarder among its neighbors for reaching the destination. In order to avoid a "blind" message forwarding, some solutions have been proposed over the last years [START_REF] Leontiadis | GeOpps: Geographical Opportunistic Routing for Vehicular Networks[END_REF], [START_REF] Nguyen | Probabilistic Routing Protocol for Intermittently Connected Mobile Ad hoc Network (PROP-ICMAN)[END_REF], [START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF], [START_REF] Guidec | Opportunistic Content-Based Dissemination in Disconnected Mobile Ad Hoc Networks[END_REF], [START_REF] Musolesi | CAR: Context-Aware Adaptive Routing for Delay Tolerant Mobile Networks[END_REF], [START_REF] Boldrini | HiBOp: a History-Based Routing Protocol for Opportunistic Networks[END_REF]. These solutions mainly rely on the computation of a delivery probability based on contextual properties [START_REF] Musolesi | CAR: Context-Aware Adaptive Routing for Delay Tolerant Mobile Networks[END_REF], on a history of contacts [START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF], or on both [START_REF] Boldrini | HiBOp: a History-Based Routing Protocol for Opportunistic Networks[END_REF], [START_REF] Nguyen | Probabilistic Routing Protocol for Intermittently Connected Mobile Ad hoc Network (PROP-ICMAN)[END_REF]. Nevertheless, these solutions often consider that nodes move following regular mobility patterns, and that their future (direct or indirect) encounters can be predicted. Computing such an history and a prediction is a tricky problem, especially in an environment where people often stroll and move randomly such as in a city, questioning de facto such assumptions. Moreover, during the invocation process, such probabilities must be computed twice: once in order to deliver the invocation request to the service provider, and another time to deliver the response to the client. Indeed, the client and the intermediate nodes are likely to move during this process, the forwarding path followed by the response can therefore be different from that taken by the request.

In order to increase the message delivery ratio and to reduce the delivery time, several copies of a message are usually generated in the network. In order not to process a request or a response several times, such a redundancy should be hidden from both the client applications and the software services, and be controlled by the routing protocol itself. Moreover, a mobile node should stop forwarding a request for which it has already received a response.

Opportunistic communications introduce a certain delay in the service discovery and invocation processes. Although client applications must be able to tolerate this delay and to deal with extended disconnection periods, it is suitable to devise solutions that provide end-users with a certain quality of service in term of responsiveness. Consequently, the protocol should not implement a purely periodic and proactive message emission, but instead should adopt a reactive behavior as far as possible. It should be sensitive to events such as the arrival of a new neighbor, the reception of a new message or the location changes.

Finally, like the service discovery messages, the service invocation requests and the service responses must be circumscribed to the area where the service must be offered. Both a lifetime and a maximum number of hops must also be assigned to these messages in order to reduce their propagation.

III. THE OLFSERV PROTOCOL

In the remainder of this section, we present OLFServ, an opportunistic and location-aware forwarding protocol we have designed so as to address the issues identified in the previous section. OLFServ aims at supporting the discovery and the invocation of software services in DMANETs such as those formed by fixed infostations and handheld devices used by nomadic people. It implements an efficient and geographically-constrained broadcast of both service advertisements and service discovery requests, as well as a location-driven forwarding of service invocation requests and service responses. OLFServ is a key element of an OSGi service-oriented middleware platform we have developed in order to support service provision in "challenging" pervasive environments. This platform provides some facilities in order to compute the location of a mobile node according to the coordinates generated by the embedded GPS receiver or to the Wi-Fi signal and the location properties exhibited by the neighbor nodes as presented in [START_REF] Sassi | Towards an Opportunistic and Location-Aware Service Provision in Disconnected Mobile Ad Hoc Networks[END_REF].

A. Assumptions

The OLFServ protocol relies on 3 main assumptions: 1) Both mobile hosts and fixed infostations are aware of their geographical location and able to compare their location with that of another host. Mobile hosts are expected to indicate their destination/direction if they know them. 2) Mobile hosts are able to perceive their one-hop neighborhood. This neighborhood is obtained using specific messages (beacons) sent by each node periodically. 3) Each mobile host is able to temporarily store the messages it receives, and can associate to each of them some pieces of information, and especially the IDs of the nodes that are known to have received them.

B. Overview of the protocol 1) Heurisitics:

OLFServ is an event-driven protocol that implements selfpruning heuristics. The originality of this protocol resides in the adaptation of several well known heuristics to the context of service provisioning in DMANETs, and their combination in a coherent platform. The main implemented heuristics are the following:

Contention resolution in message forwarding: Like DFCN (Delayed Flooding with Cumulative Neighborhood) [START_REF] Hogie | A Bandwidth-Efficient Broadcasting Protocol for Mobile Multi-hop Ad hoc Networks[END_REF], which proposes a bandwith-efficient broadcast algorithm for MANETs, OLFServ introduces a backoff mechanism in order to avoid message collisions at message reforwarding time. From this point of view, a node is expected to compute a forwarding delay for each message it receives, and to forward messages when their delay expires. Moreover, a node will abstain from forwarding a message if it perceives that all of its neighbors have already received it (the message was forwarded by at least one of its neighbors before it forwards the message itself, and its one-hop neighborhood is a subset of the set of nodes that are expected to have received the message yet). In addition, in OLFServ, this forwarding delay has two components: one that is inversely proportional to the distance from the last forwarder and another one that is a random value (used in the backoff mechanism). Therefore, only the farther nodes are likely to forward a message, thus improving the geographical propagation of messages while reducing the number of emissions.

Geographically-driven message forwarding: At each step, a message will be forwarded only by the nodes closer to the destination.

Content-based message forwarding: Mobile nodes can establish some correlations between the discovery requests and the advertisements, as well as between the invocation requests and the responses. Thanks to this heuristic, a mobile node receiving an invocation request is expected to send back to the client the response it previously stored for this request instead of forwarding it towards its destination, obviously if this one is still valid.

Source routing forwarding: Nodes can estimate if a message was forwarded quickly (i.e., if a message was relayed following an end-to-end path), and to perform source routing if so. OLFServ is thus able to exploit end-to-end routes when they exist, reducing the propagation time and the number of message copies. If the source routing failed, because an intermediate node becomes unreachable, the selective and controlled broadcast is used. These last two heuristics aims at improving the quality of service offered to end-users in term of responsiveness.

2) Events:

In OLFServ, five kinds of events are considered:

• the reception of a message;

• the expiration of the forwarding delay associated with a message; • the location changes;

• the arrival of a new neighbor;

• the failure in the source routing process. The first and the last events induce a reactive behavior of the protocol regarding the message forwarding, whereas the other events induce a proactive behavior.

Before giving a detailed specification of the OLFServ protocol, let's see how the above-mentioned heuristics operate in both the service discovery process and the service invocation phase. From this point of view, let us consider the disconnected MANET depicted in Figure 2, which will, for the sake of illustration, be composed of a set of mobile devices carried by pedestrians and a fixed infostation I that offers a service that is relevant only in the geographical area represented by the dotted rectangle. Moreover, let's suppose that one of these mobile hosts, namely node C, is interested in the service proposed by I. The network, which is currently composed of the six distinct communication islands shown in Figure 2, is expected to evolve in an unpredictable manner according to the nodes' mobility. Nevertheless, in order to illustrate our purposes, we will consider subsequently that node C and node N 6 follow the materialized paths so as to reach different destinations at times t 1 , t 2 , t 3 and t 4 .

a) Service discovery: The invocation of a remote service is conditioned by the preliminary discovery of this service. Consequently, in order to call the service offered by I, node C must discover this service. For the sake of illustration, let us consider that infostation I has injected in the network an advertisement A including its location, the geographical area where the service can be accessed, a date of emission, a lifetime, a maximum number of hops this advertisement is allowed to make, and the set of nodes that are expected to receive this advertisement (i.e., I, N 1 , N 2 , N 3 , N 4 and N 5 ). Nodes N 1 , N 2 , N 3 , N 4 and N 5 , which will receive message A first, will store this message locally and will compute a forwarding delay in order not to rebroadcast message A simultaneously.

The coverage radio area of a node is partitioned in several concentric rings. The forwarding delay algorithm (see Algorithm 2) allows mobile nodes located approximately at the same distance (i.e., in the same ring) from the last relay (or from the initial sender) to compute a forwarding delay in a same range of values. In the part of the network depicted in Figure 2, nodes N 1 , N 2 and N 3 will thus compute a forwarding delay in a same range of values. This delay will be less than the one computed by N 4 , which itself will be less than the one computed by N 5 . Moreover, a node perceiving that all of its neighbors have already received the message it plans to forward will cancel its forwarding process, and will trigger it when it is notified of the arrival of a new node in its vicinity. Thus in our scenario, node N 5 will not forward advertisement A, because this advertisement is rebroadcast by node N 4 first. If we consider that all the nodes have the same communication range of radius R, we can deduce, based on geometric properties, that, in favorable conditions, only 3 nodes will forward advertisement A the first time [START_REF] Liu | A Location-Aided Flooding Protocol for Wireless Ad Hoc Networks[END_REF]. Consequently at hop n, in favorable conditions the number of forwarders will be 3 × n, and in the worst conditions (i.e., when the selected forwarders moved before forwarding their message, and become out of reach of each other), the number of forwarders will be ∑ n i=0 6 n . This property is thus independent of the density of the network.

By implementing the "store, carry and forward" principle and by exploiting the nodes' mobility and contact opportunities, advertisement A will be propagated in the whole area specified by the infostation, and only in this area. Indeed, the self-pruning heuristics implemented in our protocol prevent mobile devices from forwarding messages outside the area specified in the headers of these ones. For instance, node N 6 that left the island of infostation I at time t 1 and joined that of client C at time t 2 will broadcast advertisement A in this new island. This message will be then broadcast by the other nodes of this island whether it is still valid (i.e., the number of hops is greater than zero and the lifetime has not expired yet), except by node N 7 because it is outside the area specified by infostation I. Thus, node N 8 will not receive message A. b) Service invocation: After discovering the service offered by infostation I, client node C can invoke this service by sending an invocation request including namely the ID of the infostation, the location of this one, and its own location. Let us also consider that client C knows its speed and its direction and that it has also included them in the request it sent, thus allowing to compute with a better accuracy the area where it is expected to be when it will receive the response. Indeed, when the speed and the direction (or the destination) are unknown, the "expected area" is a circle whose center is the current position of the client and whose radius is proportional to a predefined speed (of about 2 m/s for pedestrians) and to the time expected for the response delivery (this time is estimated from the request delivery time). The notion of "expected area" was introduced in [START_REF] Ko | Location-Aided Routing (LAR) in Mobile Ad Hoc Networks[END_REF]. In contrast, when the speed and the direction are known, the "expected area" is a circle centered on the position computed from the speed and the direction indicated by the client, and whose radius is proportional to the inaccuracies of both the speed and the forwarding time (see the dotted circle in Figure 2).

The request sent by C will be received by intermediate nodes and broadcast by these ones towards infostation I following a forwarding scheme that is quite similar to the discovery forwarding scheme presented previously. The difference between these two schemes resides in the number of nodes that will rebroadcast the messages. Indeed, since the invocation process is usually achieved using a unicast communication scheme, we have introduced additional self-pruning heuristics in comparison to the service discovery process in order that only the nodes closer to the destination than the previous hop can forward the message towards the destination. Thus, the area where the message is forwarded is progressively refined until reaching the destination, and the number of messages that are replicated in the network is reduced while having a good message delivery ratio. A node, receiving a message from a neighbor node closer to the message's recipient than itself, will store the message locally and will forward this message later when it becomes closer to the recipient than this neighbor. For example N 7 and N 8 will not broadcast the request sent by node C at time t 2 because they are farther than C from infostation I. This invocation request will be received by node N 6 at time t 2 + ∆t. If N 6 joins the island of infostation I at time t 3 as shown in Figure 2, it will broadcast this request in this island because it will discover new neighbors that have not received this message yet. These neighbors will then forward this request towards infostation I.

If client C has specified its location, its speed and its possible direction of movement, OLFServ can estimate the area where C is expected to be when it should receive the response from I. So when the response is returned, this area is specified in a header of this message. The response will be then routed towards this "expected area" using a forwarding scheme comparable to that used for the invocation. When the message has reached the "expected area", it will be disseminated in this area following a broadcast scheme comparable to that used for service discovery. This technique is used since the position of the client cannot be computed with a good accuracy due to the delay induced by opportunistic communication. When a mobile device receives a response for an invocation it has previously stored locally, it stops forwarding this request in the network. In our scenario (Figure 2) the response will be routed towards node C by nodes N 2 , N 3 or N 1 because they are closer to the "expected area" than I. Moreover, if an invocation request reaches the provider within a short amount of time (i.e., if a end-to-end route is very likely to exist between the client and the provider), OLFServ tries to follow the same route by applying source routing. If the source routing process failed because an intermediate node has moved, then the node perform a broadcast towards the destination as mentioned before. Finally, if a node stored previously a response for the request sent by client C, it will send back this response (if it is still valid) instead of forwarding the request towards infostation I. For instance, N 2 can return to client C the copy of the response it holds locally, instead of forwarding the request to I. Thus, the number of message roaming in the network is reduced and the service invocation responsiveness is improved. The same process is applied when a client is looking for a service: an intermediate node can send back to the client the advertisement it holds locally that "matches" the service discovery request sent by the client.

C. Specification of the protocol

The remainder of this section presents how OLFServ reacts when one of the above-mentioned events occurs.

1) Notations: The location of a node is subsequently identified as L, the one of the last relay as L relay and the one of the destination as L recipient . The one-hop neighborhood of a node is referred to as N. The local cache of a node is identified as C. Q s and Q b are outgoing queues for the messages that must be sent using source routing techniques and for the messages that must be broadcast respectively. K m refers to the set of nodes that are known to have received message m. ∆ is the set of messages that must be forwarded and for which a forwarding delay has been computed. Finally, the messages headers can include several properties (the location of the recipient, the location of the sender, a date of emission, a lifetime, a maximum allowed number of hops, the geographical area where the message can be disseminated, etc.). A given property of a message m is identified as m[property].

2) Message reception: When receiving a message m, Algorithm 1 is applied. First, if a node receives from one of its neighbors a message it plans to forward, it checks if all of its neighbors have received this message. If so, it cancels its forwarding process. If the node has in its cache an advertisement p for the service discovery request m (or a response p for the invocation request m) then the node is expected to forward p if this one is still valid. A forwarding delay is computed for message p, and p is put in the set of Algorithm 1 Reaction on message reception.

Input:

m: the incoming message t: the current time messages that must be sent. Otherwise, if m is a response for an invocation request k (or if m is an advertisement for a discovery request k), k is removed from the local cache in order not to be forwarded later, as well as from the set of messages that must be forwarded. If message m is still valid and if the number of hops is greater than 0, message m is put in the local cache, and the set K m is updated (i.e., the set of nodes that are known to have received message m yet). Message m is put in the set of messages that must be forwarded and a forwarding delay is computed for m. When the forwarding delay δ m expires, Algorithm 3 will be applied.

C, ∆, K m , N 1: if (m ∈ ∆ & N ⊆ K m ) then 2: ∆ ← ∆ -{m} 3: else 4: if (∃ p ∈ C / p is response for m & p[li f etime] > t -p[date] & p[hops] > 0) then 5: compute forwarding delay for p 6: ∆ ← ∆ ∪ {p} 7: else 8: if (∃ k ∈ C / m is response for k) then 9: C ← C-{k} 10: if (k ∈ ∆) then 11: ∆ ← ∆-{k} 12: if (k ∈ Q s ) then 13: Q s ← Q s -{k} 14: else 15: Q b ← Q b -
3) Computation and expiration of the forwarding delay: Each mobile device computes a forwarding delay for each message it receives. This delay prevents close devices from forwarding messages simultaneously. As mentionned before, in OLFServ the forwarding delay has both a random component and a component that is inversely proportional to the distance from the previous relay. So as to compute this forwarding delay, the wireless communication range of each device has been divided in several rings (see Figure 2), so that the delays computed by hosts in ring i are greater than those computed by hosts in ring i+1. The mobile hosts of a given ring are considered as equivalent regarding the spatial propagation of messages. The algorithm used to compute the forwarding delay is described in Algorithm 2. This algorithm has mainly three parameters: the wireless communication range (W ), the ring size (rs) and α. This last parameter has Algorithm 3 Expiration of the forwarding delay.

Input: t: the current time m: the message C, N, K m , Q b , Q s 1: if (N -K m = / 0 & in m[area] & m[li f etime] > t -m[date] & m[hops] > 0) then 2: if (m[recipient] = " * ") then 3: d this→recipient ← distance(L, m[L recipient ]) 4: d relay→recipient ← distance(m[L relay ], m[L recipient ]) 5: if (d this→recipient ≤ d relay→recipient ) then 6: m[area] ← (m[L recipient ], d this→recipient ) 7: m[K m ] ← m[K m ] ∪ K m 8: m[L relay ] ← L 9: m[nb hops] ← m[nb hops] -1 10: if (t -m[date] < ε) then 11: Q s ← Q s ∪ {m} 12: ∆ ← ∆ -{m} 13: else 14: Q b ← Q b ∪ {m} 15: ∆ ← ∆ -{m} 16: end if 17: end if 18: else 19: m[K m ] ← m[K m ] ∪ K m 20: m[L relay ] ← L 21: m[nb hops] ← m[nb hops] -1 22: Q b ← Q b ∪ {m} 23:
∆ ← ∆ -{m} 24: end if 25: end if been introduced in order to define a relevant delay δ m : the delay in the largest ring is of the order of a few milliseconds, while in the smallest ring it is of the order of a few seconds typically.

When the forwarding delay of a given message has expired, Algorithm 3 is applied. If there are new nodes in the onehop neighborhood, if the client is in the area where the message can be disseminated, if the message is still valid and if the message has next hops, the message is then considered as being forwardable. The headers of the message are then updated. If the destination is known, the area where the message can be propagated is updated in order to refine this area progressively until reaching the destination. Moreover if the destination is known, the mobile device checks whether it is closed to the destination than the last forwarder, and if so, it updates the number of hops, the location of the last forwarder with its own location and the set of nodes that have already received the message, and puts the message in the outgoing message queue. If the message has expired or if the number of hops equals to 0, the message is removed from the local cache.

4) Location changes: When reaching a given location, a mobile host can trigger the forwarding of some messages. For Algorithm 4 Location changes.

Input:

t: the current time m: the message that must be forwarded

C,K m 1: if (m[li f etime] > t -m[date] & m[hops] > 0 & N ⊆ K m ) then 2: if (m[type] = response & L in m[expected area]) then 3: m[recipient] ← " *
: N ← N ∪ {n} 2: for all m ∈ C do 3: if (m[li f etime] > t -m[date] & m[hops] > 0) then 4: if (n / ∈ K m & in m[area]) then 5:
compute forwarding delay (m) 6: end if 7: else 8: C ← C -{m} 9: end if 10: end for instance, a mobile host that was far from the recipient of a message it received can trigger the emission of this message when it is at a given distance from the recipient. Similarly, when entering the area where a client is likely to be receiving its service response, a mobile host, acting as an intermediate node, can both update the message headers in order that this message can be broadcast in this whole area and trigger its emission. When the mobile host has reached a given location, Algorithm 4 is executed. We change the status of the response in order that it is broadcast by the node in the whole area specified by the provider. And for each message when we become closer to the destination than the previous node (the node from which we have received the message), we trigger a message emission.

5) New neighbor detection: When a new neighbor node is discovered, the mobile host computes a forwarding delay for all the messages that are still valid, that have next hops, if the new neighbor is not in the the list of nodes that have already received the message and if the mobile host is in the area where the message can be propagated. A new forwarding delay is computed in order to prevent the emission of the same messages by different nodes that simultaneously discover the new neighbor node in their one-hop neighborhood.

IV. EXPERIMENTS AND RESULTS

In order to evaluate our protocol, we conducted a series of simulations using the Madhoc simulator (http://wwwsop.inria.fr/members/Luc.Hogie/madhoc), a metropolitan ad hoc network simulator that features the components required for both realistic and large-scale simulations, as well as the tools essential to an effective monitoring of the simulated applications. This simulator, which is written in Java, allows us to run our middleware platform on it. In the current scenarios we focus on, service providers are fixed infostations deployed in a city, while clients are devices carried by humans.

A. Experiments and simulation setup

The simulation environment we consider is depicted in Figure 3. It is an open area of about 1 km 2 . Four infostations offering two different services are deployed in this environment. These services can be discovered and invoked in a circular area of a radius of 200 m. The first service delivers the day's weather forecast, while the second provides an access to a "yellow page" service, which can be invoked by nomadic people in order to find restaurants, shops, etc. Mobile clients are thus expected to submit the same request to the first service and different ones to the second service. In our simulations, we have considered successively 50, 100, 500 and 1000 pedestrians carrying a PDA (Personal Digital Assistant) equipped with both a Wi-Fi interface and a GPS receiver. The communication range of both mobile devices and infostations varies from 60 to 80 m. Some of the pedestrians move randomly, while others follow predefined paths. Each pedestrian moves at a speed between 0.5 and 2 m/s. In our simulations, 30% of the mobile devices act as clients of the above-mentioned services, whereas the others only act as intermediate nodes. The service providers are expected to broadcast service advertisements every 30 seconds when mobile devices are in their vicinity. After discovering the services they are looking for, the clients invoke these services every 3 minutes. In our experiments, we have assigned to all the messages a lifetime of 5 minutes and a maximum number of hops of 8. We present below the results we obtained for OLFServ in these various configurations, and we compare OLFServ with the Epidemic Routing Protocol (EPR) defined by Vahdat and Becker [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF]. The objective of these experiments was to measure the ability to satisfy the client service discovery and invocation efficiently with a small number of message copies.

B. Results

Figure 4 shows the service discovery delays we have observed in the various simulation setups we have considered. As expected, we can see that the discovery delays decrease when the number of nodes increases. Indeed, in a dense environment the connectivity disruptions are less frequent, and the impact of the opportunistic communications are reduced. The discovery process can be perceived as a long process. For instance, only 70% of the clients have discovered the service they require after 20 minutes in the second setup (30 clients and 70 relays). However, it should not be forgotten that the services can be discovered and invoked by the clients only in restricted areas and not in the whole environment (see Figure 3), with the consequence that several minutes may elapse before the clients have reached the restricted area of the service they are looking for. However, the speed of discovery inside this restricted area is significantly greater: we have observed that, in most of the situations, the discovery time is less than 10 seconds after the client has entered the area of the service it requires, and that it lasts about 1 minute in the worst case. Finally, the services are discovered more quickly with OLFServ than with the epidemic routing protocol. In OLFServ the service advertisements are broadcast by the mobile nodes, whereas in the EPR, the nodes must first exchange summary vectors with each of their neighbors before forwarding the service advertisements themselves, thus introducing a latency in the discovery process.

Figure 5 and Figure 6 present the simulation results for the two kinds of services considered (the "weather forecast" service S1 and the "yellow pages" service S2). Figure 5 gives the average number of emissions for a service advertisement (for S1 and S2) with OLFServ and with EPR. One can observe that the number of emissions increases drastically with EPR, while it remains relatively constant with OLFServ. Indeed, in EPR, when two hosts come into communication range of one another, they exchange their summary vectors to determine which messages stored remotely have not been seen by the local host. In turn, each host then requests copies of messages that it has not seen yet. In contrast in OLFServ, service advertisements are broadcast and not sent using a unicast communication model. Moreover, only a subset of the neighbor nodes are expected to rebroadcast these advertisements in turn. For S2, the number of emissions of a given service invocation request is less than the half of the number of emissions of service advertisements (see Figure 6). These results are consistent with those expected. Indeed, the invocation requests are broadcast only by the nodes closer to the destination at each hop. It must be noticed that the number of emissions of invocation requests for S1 is less than that for S2. Again, the results are consistent with those expected: all the clients interested in the "weather forecast" service submit the same request, and obtain in return the same response during the simulation. The mobile nodes that have stored a request and the associated response are able to establish a correlation between these messages, and are expected to send back to the client the stored response when they receive a new similar request. The number of requests for S1 decreases according to the number of clients. Such a phenomenon can be explained by the fact that a request is not forwarded by a node towards the destination if this node has already obtained the response associated with this request. This correlation techniques is further detailed in [START_REF] Sassi | Towards an Opportunistic and Location-Aware Service Provision in Disconnected Mobile Ad Hoc Networks[END_REF]. Finally, it must be noticed that the mobility of nodes between the successive invocations does not allow benefiting from source routing when forwarding a request towards a provider. Nevertheless, source routing has proved its efficiency in the forwarding of the responses, as shown in Figure 5. Thus, the number of messages sent in the network is reduced while offering a better service provision (see Table I).

As shown in Table I, the number of clients that have discovered the service they are looking for is greater with EPR than with OLFServ. Nevertheless, the invocation success ratio with EPR is less than with OLFServ. Indeed, with OLFServ messages are routed only in the areas where the services can be discovered and invoked, whereas with EPR, messages are routed in the whole simulation area. Consequently, with EPR, services can sometimes be discovered by the clients, but not invoked successfully due to the mobility of intermediate nodes, to the periodic exchange of messages (every 20 seconds) and to the fixed number of hops. In contrast, with OLFServ, messages are forwarded few milliseconds after their reception instead of being forwarded periodically. OLFServ thus offers a good responsiveness and delivery ratio while producing a lower network load.

V. RELATED WORK

Our work on OLFServ is related to works on broadcast protocols [START_REF] Williams | Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks[END_REF], [START_REF] Stojmenovic | Mobile Ad Hoc Networking, ch. 7: Broadcasting and Activity-Scheduling in Ad Hoc Networks[END_REF]. Indeed, some techniques that aim at reducing the number of message forwarders are adapted or integrated to the specific context of service provision in opportunistic networks.

However, the research works that follow the same objectives as OLFServ are mainly led in the opportunistic networking and/or delay/disrupted tolerant networking domain. One of the first protocol in this domain is the Epidemic Routing Protocol [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF], which can in a way be assimilated to a simple flooding, not suitable for environments with high density regions, since it would generate too much network traffic and could even lead to network congestion. This drawback is addressed by protocols implementing methods aiming to assess the capability of a neighbor node to contribute to the delivery of a given message. These methods usually use a probabilistic metric, often called delivery predictability, that reflects how a neighbor node will be able to deliver a message to its final recipient [START_REF] Wu | Broadcasting in Ad Hoc Networks Based on Self-Pruning[END_REF]. Before forwarding (or sending) a message, a mobile host asks its neighbors to infer their own delivery probability for the considered message, and then compares the probabilities returned by its neighbors and chooses the best next carrier(s) among them. In CAR [START_REF] Musolesi | CAR: Context-Aware Adaptive Routing for Delay Tolerant Mobile Networks[END_REF] and GeOpps [START_REF] Leontiadis | GeOpps: Geographical Opportunistic Routing for Vehicular Networks[END_REF], the delivery probabilities are computed using both utility functions and Kalman filter prediction techniques. CAR assumes an underlying MANET routing protocol that connects together nodes in the same MANET cloud. To reach nodes outside the cloud, a sender looks for the node in its current cloud with the highest probability of delivering the message successfully to the destination. GeOpps, which is a geographical delay-tolerant routing algorithm, exploits the pieces of information provided by the vehicles' navigation system in order to route the messages to a specific location. Like CAR, HiBOp [START_REF] Boldrini | HiBOp: a History-Based Routing Protocol for Opportunistic Networks[END_REF] also exploits context information in order to compute delivery probabilities. However, HiBOp can be perceived as being more general than CAR since it does not require an underlying routing protocol, and because it is also able to exploit context for those destinations that nodes do not know. HiBOp exploits history information in order to improve the delivery probability accuracy, and does not make predictions as CAR. Propicman [START_REF] Nguyen | Probabilistic Routing Protocol for Intermittently Connected Mobile Ad hoc Network (PROP-ICMAN)[END_REF], as for it, also exploits context information and uses the probability of nodes to meet the destination, and infers from it the delivery probability, but in a different way. When a node wants to send a message to another node, it sends to its neighbor nodes the information it knows about the destination. Based on this information, the neighbor nodes compute their delivery probability and return it. In Prophet [START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF], the selection of the best neighbor node is based on how frequently a node encounters another. When two nodes meet, they exchange their summary vectors, which contain their delivery predictability information. If two nodes do not meet for a while, the delivery predictability decreaces. When a node wants to send a message to another node, it will look for the neighbor node that has the highest amount of time encountering the destination, meaning that has the highest delivery predictability to the destination. Furthermore, this property is transitive. Unlike OLFServ, most of the abovementioned protocols rely on an history of contacts and a prediction of encounters in order to select the best next carrier(s). Computing such an history and a prediction is a tricky problem, especially in environments composed of numerous mobile devices that move following irregular patterns, such as those hold by pedestrians in a city. Although they implement various strategies aiming to select the next best carriers(s) to deliver a given message, the above-mentioned protocols are not suited to service discovery. Indeed, they implement neither self-pruning heuristics making it possible for mobile nodes to decide if they should rebroadcast a message according to their neighborhood perception, nor methods allowing to designate which subset of neighbor nodes must rebroadcast a message. If used to broadcast service advertisements or service discovery requests network-wide, they will probably induce a storm of messages and perhaps a network congestion.

Geographic routing protocols, such as GeRaf [START_REF] Zorzi | Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Multihop Performance[END_REF], LAR [START_REF] Ko | Location-Aided Routing (LAR) in Mobile Ad Hoc Networks[END_REF] and Dream [START_REF] Basagni | A Distance Routing Effect Algorithm for Mobility (DREAM)[END_REF], propose forwarding techniques similar to those implemented in OLFServ. Once a node has a message to send, it broadcasts it while specifying its own location and the location of the destination. All the nodes in the coverage area will receive this message and will assess their own capability to act as a relay, based on how close they are to the destination. Dream and LAR also propose some solutions in order to improve the message delivery in MANETs. For instance, based on location information, they can compute the area where the mobile clients are expected to be when they receive their messages. Nevertheless, on contrary to OLFServ, these protocols do not implement the "store, carry and forward" principle and therefore are not suitable for disconnected MANETs.

VI. CONCLUSION

The vision of opportunistic computing is to provide mobile users with pervasive access to software services without rely-ing on a fixed infrastructure but rather exploiting direct radio contacts between mobiles devices in a disconnected MANET. Opportunistic transmissions are performed during these contacts, enabling routing of messages between services clients and service providers. In this context, the work described in this paper focused on routing in the case where service providers are fixed infostations and where devices in the network are endowed with the capacity to geolocalize themselves. We proposed a new forwarding protocol called OLFServ, suited for service provision in disconnected MANETs. This protocol implements several self-pruning heuristics aiming to efficiently control the dissemination of service advertisements and service discovery requests, as well as to perform a geographic and source-based routing allowing cost effective delivery of service invocation requests and responses. Simulation results show that OLFServ outperforms epidemic routing in networks composed of numerous mobile devices moving randomly with respect to delivery delay, delivery ratio and number of emissions (reflecting the network throughput). In the future, we would like to investigate new complementary techniques, such as geometric localized forwarding and spanning trees, in order to forward a message from a source to a destination along different paths while reducing again the delay and the message copies, especially when some partitions of the network are temporarily stable.

Figure 1 .

 1 Figure 1. Illustration of a disconnected MANET formed by infostations and devices carried by people strolling in a city.

Figure 2 .

 2 Figure 2. Opportunistic communication in a DMANET with OLFServ.

Algorithm 2

 2 Computation of the forwarding delay. Input: m: the incoming message rs: the ring size R: the ring number δ : the default forwarding period W : the wireless communication range Output: δ m : the forwarding delay for message m 1: R ← f loor((Wdistance(L, m[L relay ]))/rs) 2: δ m ← min(δ , α * random(R * rs, (R + 1) * rs))

Figure 3 .

 3 Figure 3. Simulation environment.

Figure 4 .

 4 Figure 4. Service discovery delays.

Figure 5 .

 5 Figure 5. Service advertisement with OLFServ and EPR.

Figure 6 .

 6 Figure 6. Service invocation with OLFServ.

  Detection of new neighbor nodes.

	"
	4: end if
	5: compute forwarding delay for m
	6: end if
	Algorithm 5 Input:
	t: the current time
	n: the new neighbor
	C, N
	1

This paper is an extended version of a previous description of our work[START_REF] Mahéo | OLFServ: an Opportunistic and Location-Aware Forwarding Protocol for Service Delivery in Disconnected MANETs[END_REF]. It gives a more detailed explanation of the rationale and mechanics of the proposed protocol, as well as complementary experimentation results.

To our knowledge, except in our previous work, service provisioning in opportunistic networks has been specifically studied only by the European SCAMPI project (http://www.ict-scampi.eu).