Veeraruna Kavitha

Eitan Altman

Analysis and Design of Message Ferry Routes in Sensor Networks using Polling Models

We consider a Ferry based Wireless Local Area Network (FWLAN), in which information is forwarded from a base station to sensors, or gathered from sensors to a base station using a moving Ferry. The sensors are scattered in a large area and do not have direct radio connectivity with the base station. The ferry thus serves as a relay that enables communication between the sensors and the base station. Our goal in this paper is to design optimal routes of the Ferry moving along which it distributes/collects the messages. Our analysis and optimization results build heavily on the theory of polling systems which we extend here in order to handle the case of continuous location of the demand. We derive optimal trajectories for various scenarios: uplink, downlink and their combination. We extend some of these results to the case of several base stations and several ferries.

I. INTRODUCTION

Message Ferry is a mobile relay station that serves as "postman" to deliver to static or dynamic wireless nodes messages (or packets) and to collect messages from them. Mobile BS have been proposed in the context of mobile Ad Hoc Networks [START_REF] Tariq | Message ferry route design for sparse ad hoc networks with mobile nodes[END_REF], of Vehicular Ad-Hoc Networks (Vanets) [START_REF] Saleh Yousefi | Connectivity in vehicular ad hoc networks in presence of wireless mobile base-stations[END_REF] and of wireless (static) sensor networks [START_REF] Shi | Theoretical results on base station movement problem for sensor network[END_REF]. In the UmassDiesel project, computers have been installed in 30 out of 40 buses and these then serve as Message Ferry to deliver messages to throw boxes (see http://prisms.cs.umass.edu/diesel/).

We are concerned with a message ferry that serves as a mobile access point in a local area network which we call FWLAN (Ferry Wireless LAN); the ferry delivers and collects messages from quasi-static nodes on some geographic area ∆. By quasi-static we mean that the sensors could be mobile but on a time scale much slower than that of the cyclic rounds of the ferry. We are interested in designing optimal ferry routes. If the ferry has to reach physically each sensor that has information to transmit or to receive, then the problem can be This work was sponsored by The Indo-French Center for the Promotion of Advanced Research under CEFIPRA Project# 4000-IT-1 mapped to the classical vehicle routing problem, where a central point receives service requests from points on the plane. One or several service vehicles are then sent for handling the requests and one has to design efficient or optimal vehicle's route that pass through all the points, see [START_REF] Bertsimas | A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane[END_REF], [START_REF] Saad | A Selfish Approach to Coalition Formation among Unmanned Air Vehicles in Wireless Networks[END_REF], [START_REF] Laporte | What You Should Know about the Vehicle Routing Problem[END_REF]. There is however a fundamental difference between these problems. In the vehicle routing problem, the routes need to pass through all the points in space that require service. In contrast, the routes of the message ferry need only to pass in the transmission and reception range of the nodes. Furthermore, assuming a fixed transmission power, the range can be increased at the cost of decreasing throughput. There is another major difference: during uplink service, the ferry will not even be aware of the intended users before the start of new cycle, it is aware of an active user only when it reaches a point in the transmission range of the user.

As a first step we considered a cellular type architecture in [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF]: the ferry can accept or dispatch messages only when it arrives to one of a finite number of predetermined stops, each stop is assigned with an area (it can viewed as cell corresponding to the stop) of ∆. This architecture was analyzed using theory of polling systems with finite number of queues ( [START_REF] Altman | Queueing in space[END_REF], [START_REF] Boxma | Workloads and waiting times in single-server systems with multiple customer classes[END_REF], [START_REF] Takagi | Analysis of Polling Systems[END_REF]). Performance measures like average virtual workload in the system under stationarity, stability factor were obtained and optimal routes were derived.

In this paper we drop the cellular structure of [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF] and allow the shuttle to stop at any point on its route. Indeed, we assume that the shuttle stops whenever it finds itself at a point on its path that is closest to an user that has some packet to send or to receive. This architecture might be advantageous, as it allows the ferry to communicate with the all users at the smallest distance possible, for a given ferry route.

The new system can only be analyzed using a polling system with a continuum of queues. For such polling systems, much is known about the stability [START_REF] Altman | Queueing in space[END_REF], [START_REF] Georgiadis | Stability of Token Passing Rings[END_REF], [START_REF] Altman | Stability, Monotonicity and Invariant Quantities in General Polling Systems[END_REF], but little is known about the performance measures, e.g., average virtual workload in the system under stationarity. The only relevant results available correspond to sym-metric exhaustive polling systems which are useful for studying only the case of uplink traffic under symmetric conditions. We derive expressions for the performance of the so called "globally gated" discipline, whose restriction to finitely many queues was studied in [START_REF] Boxma | Cyclic Reservation schemes for efficient operation of multiple-queue single-server systems[END_REF], and which allows us to analyze the downlink case. We derive explicit expressions for the expected waiting times and workload without assuming any symmetric structure. In addition, we propose expressions for continuum polling with mixed service disciplines which allow us to handle combined up and downlink traffic. We extend some of these results and of the design of optimal route to the case of several base stations and several shuttles.

In designing the ferry's routes and stops, we aim at minimizing the expected waiting times at all nodes in the Pareto sense 1 . Our theoretical results in some cases, allow us to obtain optimal policies in a stronger sense.

II. SYSTEM MODEL AND NOTATIONS

We consider a geographical area ∆ in which static users are scattered. We assume that the network is sparse and there is no direct global connectivity. In order to receive messages from the users or to send messages to them, a ferry called "message ferry" or "message shuttle" moves around and serves as a postman. In order to route the data to and from outside the area, the shuttle has to pass through a BS that serves as a gateway. The ferry goes to the BS once in every cycle to collect and deposit the information. The ferry "serves" the nodes in a cyclic manner. We use throughout terms from queuing theory; by "serves" a message we mean that the ferry transmits it if the connection is downlink (i.e. the message is destined to a node), or receives it, if it is an uplink message.

Ferry's Route : The ferry moves in a closed cyclic path C repeatedly with constant speed c 1 . Each point q in the cyclic path is assigned with a set of points I(q) ⊂ ∆ that are closest to it. That is, in most of the situations, set I(q) consists of all points x ∈ ∆ such that the projection of x to the trajectory C is q. For example, if we consider ∆ to be an annular ring with the Ferry moving along a co-centric circle, then the Ferry will stop at a point on the circle if there is an active node (i.e. a node to or from which there is a message to transmit) located at the same angle. However, there can be situations in which the sets I(q) have to be defined differently and those situations are explained in appropriate locations. 1 Let W be the set of vectors of expected waiting times achieved by a class of design policies. A vector of w1 ∈ W obtained by some dominates another vector w2 if all entries of w1 are smaller than or equal to those of w2 with at least one entry being strictly smaller. A minimum vector in W in the Pareto sense is one that is not dominated by any other vector in W .

The shuttle continues with its journey after serving the user. Every time it stops and restarts it spends an extra time c 2 for acceleration. We map the ferry route to a line for analysis and assume that BS is located at 0. The indexing in this paper is done in a circular manner.

Arrival process: We consider traffic generated at the nodes which we call "uplink", and traffic that arrives to the nodes called "downlink". We shall use for both cases the term "arrival". Uplink/Downlink traffic arrives according to an independent marked point processes {T n , M n }, where T n is the arrival time of the nth point and M n = [X n , η n ] are the corresponding i.i.d. marks:

• T n is a Poisson point process with parameter λ; • X n is the location of an arrival with distribution P X ; • η n is the size of the message whose distribution can depend upon X n , it has finite first and second moments η b (x), η

b (x) everywhere. We assume that at any time there can be at maximum one user waiting at a point. This for example is the case when P X is a continuous distribution.

We use the following notations throughout the paper. The points in the area ∆ are represented by x (if it is a sample point) or X (if it is a random position). The points on the cyclic path C are represented by q or Q.

Radio channel and service time: The Ferry uses a wireless link to serve the users. It can receive/transmit the messages from/to the nodes at a distance of d from it at a rate κ(d) for some decreasing function κ(.). Further every time the ferry stops, it requires an extra time c 2 for accelerating. Thus the total time required for serving an upload/download message of size η, when the user is located at x ∈ ∆ and is associated with q(x) ∈ C is equal to its size divided by the service rate,

η κ(||q(x) -x||) + c 2 .
The point x ∈ ∆ can for example be associated with the closest point on the circular path C, i.e. in this case q(x) := arg min q∈C ||q -x||.

Throughout the paper ||.|| represents either the area (length) of the two (one) dimensional region and or the distance between two points. Pareto Optimality: All the users are served as the ferry moves on C. Any arrival at a point x ∈ ∆ has to wait for time W (q(x)) and the expected values of these waiting times E[W ](q) in general can depend upon the point q ∈ C standing at which the ferry serves them. We are interested in designing an optimal route (among some given class of trajectories) which minimizes integral of the weighted expected waiting times at all the points in the cyclic path C, i.e.

|C| 0 E[W ](q)ζ(q)dq with {ζ(q)} appropriate positive weights, as that would give a Pareto optimal solution for the problem of minimizing the expected waiting times for all the users.

We need to choose appropriate weights {ζ(q)}. If ζ(q) is chosen to be the arrival density to the points that are handled by q, i.e. λP I(q) then the integral corresponds to the total expected number of active sensors (by Little's Theorem). If we further multiply pointwise the integrand by the expected service times, i.e., if ζ(q) = λP I(q) b(q), then we obtain the total expected virtual workload in the system2 . Virtual workload has been obtained in literature for finitely many queues ( [START_REF] Boxma | Cyclic Reservation schemes for efficient operation of multiple-queue single-server systems[END_REF], [START_REF] Boxma | Workloads and waiting times in single-server systems with multiple customer classes[END_REF], [START_REF] Takagi | Analysis of Polling Systems[END_REF], [START_REF] Altman | Queueing in space[END_REF]) and is used in [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF]. These expressions are however not available in case of continuous polling systems except for the case of symmetric system with exhaustive service. The exhaustive service can only model the uplink service (more details in coming sections) and hence the existing results are not adequate to analyze this problem for all important cases. We derive the virtual workload expressions for many more interesting cases in Appendix A, so as to obtain a Pareto optimal ferry route for all scenarios.

III. FERRY MOVING IN A ANNULAR RING

We study a ferry moving in a annular ring using the theory of continuous polling systems of Appendix A. We discuss design of optimal (which minimizes the virtual workload) ferry paths C and optimal partitioning of the area into line segments {I q ; q ∈ C}. Solving this problem in complete generality will be a very difficult task. Hence we instead obtain optimal ferry path among a special class of ferry paths. Prior to discussing the optimality issues one first needs to map the FWLAN to a continuous polling. This task is taken up immediately. Later, in the first subsection of this section, we consider optimal paths among paths which are represented by a single circle placed inside the annular area. In the subsection following that, we consider a closed path consisting of N circular paths placed optimally in the area or equivalently we consider N ferries each moving in its own circular path.

The ferry moves inside an annular ring

∆ := {x ∈ R 2 : h 2 1 ≤ |x| ≤ h 2 2 } of Figures 1, 2.
Ferry moves in a predefined closed cyclic path C and each point q in the cyclic path is assigned with a line segment I(q) ⊂ ∆, which is either obtained using the nearest point basis (in subsection III-A) or is computed in some optimal sense (in sub section III-B). Thus the ferry stops at a point q in the cyclic path if there is an active user in line segment I(q) when it touches the point. We begin the study of this FWLAN by mapping it to a polling system of Appendix A. Server and path of the polling system : The ferry represents the server of the polling system. The ferry stops at a point q in its path only when there is a user with (downlink/uplink) request anywhere on the strip I(q). Thus the entire strip I(q) is modeled as a point on the server's path, in an equivalent continuous polling system.

Service times: The time c 2 for acceleration is required only when the ferry stops and hence is added to the equivalent service time. An arrival (η, X) is associated with the point q(X) := q of the ferry route if X lies in corresponding strip, i.e., if X ∈ I(q). Thus service time of an arrival (η, X) is given by :

B(X, η) = B(q(X)) = η κ(|X -q(X)|) + c 2 .
The expected service time (and the corresponding second moment) for the arrivals corresponding to a point q ∈ C,

b(q) = E[B(X, η)|q(X) = q] = E X η κ(|q -X|) X ∈ I(q) + c 2 . b (2) (q) = E[B(X, η) 2 |q(X) = q] = E X η 2 κ(|q -X|) 2 X ∈ I(q) -c 2 2 + 2c 2 b(q).
Service types: At the beginning of every cycle, the ferry collects the downlink information from the BS and distributes it across all the intended users as it traverses through its one cycle. Thus the downlink service corresponds to globally gated service (see Appendix A for details). While it is traveling via its circular path, it also collects the uplink information from all the active uplink nodes as and when it encounters one. Thus the uplink service corresponds to exhaustive service (see details of exhaustive service in Appendix A). Thus the FWLAN supporting both the uplink and downlink services is modeled by a mixed-service continuous polling system, in which the uplink requests represent the exhaustive service users while the downlink requests correspond to the globally gated service users. The respective probabilities

c 2 = 1 h 1 = 0.1 β = 2 η b = 1 η b (2) = 1.1 λ = 1e -6 (h 2 2 -h 1 2 )
Fig. 3. Optimal orbit radius for a ferry moving continuously in a annular ring that an arrival is globally gated or exhaustive is given by, p ggs = P rob(Downlink Arrival) and

p es = P rob(Uplink Arrival).
Position of arrival in the 'polling system' : The position of arrival in FWLAN is given by P X over ∆. Every arrival in the strip I(q) marks the arrival at point q of C in the equivalent polling system. The probability distribution, P Q (A) := P X (∪ q∈A I(q)) for any Borel set A ⊂ C, represents this arrival distribution. For example, if C = {q : ||q|| = l} for some h 1 ≤ l ≤ h 2 , P X ∼ U(∆) is uniform distribution and I(q) = {x : x = q} (with

x representing the angle made by the line joining 0, x with the x axis), then P Q will be uniform distribution on C.

The results of Appendix A can now be applied and the virtual workload of the ferry with uplink and or downlink arrivals can be calculated using [START_REF] Boxma | Workloads and waiting times in single-server systems with multiple customer classes[END_REF] for any given cyclic path C and the corresponding line segments {I q } q∈C .

A. Ferry moving in one circular path

The ferry moves on one concentric circle of radius l in the annular ring (Figure 1), i.e.,

C l = {q ∈ R 2 : ||q|| = l}.
In this case, in view of the fact that κ is a decreasing function of the distance d, the best possible thing is to associate every arrival (η, X) with the nearest point of the ferry route, i.e., with the point q(X) := arg min q∈Cl |q -X| of ferry route. Hence the line segments will be angular segments (see figure 1),

I(q) = {x ∈ ∆ : (x) = (q)} for all q ∈ C l .
We would now like to find the optimal radius of this circle and we are interested in optimizing the virtual workload ( 5)

l * = arg min l∈[h1,h2] V mix (l).
To simplify the computations, in this section we assume:

• uniform arrivals in annular area, P X ∼ U(∆);

• the distribution of η is independent of location of arrival and the type of arrival (uplink or downlink), i.e.,

E[η|X] ≡ η b and E[η 2 |X] ≡ η (2)
b and for both the arrivals;

• the rate function resulting from the losses in wireless medium considers only the direct path for attenuation and is calculated assuming a receive transmit antennae difference of 1, i.e.,

κ(d) = (1 + d 2 ) -α (1)
where β = 2α is the path loss factor; • The uplink and downlink arrivals occur with equal probabilities p ggs = p es = 1/2.

Since the line segments {I(q)} in this case are angular segments for calculating the moments of the equivalent expected service times of a polling system {b(q; l)} q∈Cl one will require the radius R = ||X|| of the arrival. Note that the moment b(q; l) represents the average service time of the user belonging to point q of C l . Under the assumptions of this section, radius R has density

f R (r) = 2r h 2 2 -h 2 1 (2)
and further it is easy to see that the the moments of the overall service time will be independent of the position q ∈ C l but depend upon the ferry path radius l. The service moments are for all q ∈ C l are:

b l = b(q; l) = η b h2 h1 1 + (r -l) 2 α 2rdr h 2 2 -h 2 1 + c 2 , b (2) l = b (2) (q; l) = η (2) b h2 h1 1 + (r -l) 2 2α 2rdr h 2 2 -h 2 1 -c 2 2 + 2c 2 b l .
For example for α = 1 the above can be computed as,

b l = η b 1 2 (h 2 1 + h 2 2 + 2) + l 2 - 4l(h 2 1 + h 1 h 2 + h 2 2 ) 3(h 1 + h 2 ) +c 2 b (2) l = η (2) b 15(h 2 2 -h 2 1 ) (-5h 6 1 + 24h 5 1 l -15h 4 1 (3l 2 + 1) +40h 3 1 (l 3 + l) -15h 2 1 (l 2 + 1) 2 h 2 2 (5h 4 2 -24h 3 2 l +15h 2 2 (3l 2 + 1) -40h 2 (l 3 + l) + 15(l 2 + 1) 2 )) -c 2 2 + 2c 2 b l .
Under the simplified assumptions of this section the workload for mixed service (5) simplifies to:

V mix,l = λb l λb (2) l 2(1 -λb l ) + 3λb l |C l |c -1 1 4(1 -λb l ) . (3)
From (3), it is easily seen that V mix,l depends upon l only via |C l | and the moments b l , b

(2) l and hence one can easily obtain some asymptotic characteristics of l * like :

• if the propagation coefficient β = 2α tends to zero l * tends to h 1 , i.e., the optimal path for the ferry is the inner circle (as then the moments b l , b

l depend lesser and lesser on l).

• as the speed of the ferry c 1 tends to zero l * again tends to h 1 (the second term in (3) becomes more and more significant). • as the speed of the ferry increases to infinity, optimal radius will be determined only by the moments of the service time. There are more arrivals in the upper half annular ring than the lower annular ring (see equation ( 2)) and hence the service times are improved on average if the ferry route is in the upper annular ring. Thus the optimal radius will be larger than (h 1 + h 2 )/2. Mixed service numerical example : In figure 3 we consider a FWLAN which supports both uplink and downlink services. The parameters of the FWLAN are mentioned in the figure itself and we plot the optimal radius as a function of the outer radius h 2 of the annular ring. We notice again that the optimal radius tends towards the inner circle either as the speed of the ferry decreases or as h 2 reduces. We also plot the optimizer of the expected service time,

l * b := arg min l∈[h1,h2] b l ,
in the same figure and note that the optimal radius is close to this optimizer whenever either the annular ring is large or whenever the speed of the ferry is large. This can also be understood by studying the expression for virtual workload [START_REF] Altman | Queueing in space[END_REF]. Hence in these scenarios one can obtain the optimal radius as (for β = 2)

l * ≈ l * b = 2(h 2 1 + h 2 2 + h 1 h 2 ) 3(h 1 + h 2 )
.

B. N servers moving simultaneously in the annular area

When the annular rings span over larger area, ferry moving in one circular path may not be optimal. Hence we would like to consider a ferry moving in N circular paths before completing the area. To make things simpler we assume that there will be N ferries moving simultaneously (but independent of each other) with the same speed c 1 respectively on circular paths of radii l 1 , l 2 , • • • , l N (see figure 2). Without loss of generality we also assume that the BS is placed on the entire segment {x : x = 0}, i.e., any of the ferries communicate with the BS instantaneously the moment they touch the angle 0. Throughout this paper we are neglecting the time taken for communication between the BS and the ferry(ies). Let

p := [p 1 , p 2 , • • • , p N -1 ] T and l := [l 1 , l 2 , • • • , l N ] T ,
which in turn define the line segments

I n (q) = x ∈ B(0, p n ) -B(0, p n-1 ) : q = x .
We map each ferry to a separate continuous polling system. As before, the moments of the service times for the n th ferry is

b n,p,l = η b pn pn-1 1 + (r -l) 2 α 2rdr p 2 n -p 2 n-1 + c 2 b (2) n,p,l = η (2) b pn pn-1 1 + (r -l) 2 2α 2rdr p 2 n -p 2 n-1 -c 2 2 + 2c 2 b n,p,l .
Using these moments one can estimate the N virtual workloads {V mix,n (p, l)} as a function of the vectors p, l. We now propose to chose optimal ferry paths by :

(p * , l * ) = arg min p,l N n=1 p 2 n -p 2 n-1 h 2 2 -h 2 1 V mix,n (p, l). (4)
In Table I we consider an example with 2 servers moving in the annular area and supporting uplink service. That is, this system does not support downlink service and this example is constructed in this way to study various possible scenarios. We obtain the optimal l * , p * for different values of the outer radius h 2 and the common speed of the ferries c 1 while the rest of the parameters are kept constant. We see again that the optimal radii of the ferry routes move towards the inner circle as the speed of the vehicle reduces and this effect is pronounced as the the radius of the outer circle decreases. This effect is also seen in the case of single server and can be explained using the virtual workload (5) of Appendix A:

• V depends upon the radius l via the moments of the effective service times b (1) , b (2) and the circumference |C|. Virtual workload V mix (5) is directly proportional to all three factors. • The influence of l on the two moments depends upon the path loss factor β, if β is close to zero the moments are almost independent of l while the optimal l will be above the center of the annular ring for practical path loss factors (as there will be more arrivals in upper ring than the lower one). Thus, for practical values of path loss factors the two moments reduce as l increases from the inner radius. • However the circumference |C| has a contrast effect, it increases linearly with l.

• For large values of speed c 1 , the influence of |C| on V mix reduces and hence the optimal radii will be above the center of the annular rings.

• For smaller values of speed c 1 , we see the reverse effect. • The area of the annular ring also influences, as with larger areas the average service moments will be larger and hence the influence of the moments on V mix will be larger than that of the circumference |C|.

IV. FWLAN WITH TWO BASE STATIONS

In this section we consider a slightly more sophisticated FWLAN which is equipped with two base stations. These base stations have also to be placed in optimal locations along with the design of optimal ferry routes. In this section, we consider downlink service alone and the extension to the uplink will be attempted in the future. Before we proceed with FWLAN examples with two base stations, we note here that many of the two base station examples can result in a special case of service called elevator polling (see [START_REF] Altman | On Elevator Polling with Globally Gated Regime[END_REF] which describes the scheme for discrete polling system and Appendix A which briefly describes an elevator service based continuous polling system). This polling system will have 'fair' behavior : the expected waiting time of an user in general depends upon the point standing at which the user will be served, however in elevator type services it is equal for all the users (this is true even if the arrivals are not uniform). This 'fair' behavior is a welcome feature and it might be advantageous to consider the paths and the BS locations that can result in this behavior. In Appendix A we derive the expressions for the expected waiting time for a continuous polling system with elevator gating which are applied to some interesting FWLAN examples with two base stations.

A. Ferry moving in a straight line in Rectangular area

We consider a rectangular area

∆ = [-l, l] × [-d, d].
A ferry moves in the horizontal straight line as shown in Figure 4. There are two base stations, each one of them is located at the end of the ferry path. The ferry say starts its cycle by collecting all the downlink data from the BS in the left moves towards right with speed c 1 , distributes the data to all the tagged users. Once reaching the BS in the right it collects all the data from the BS and then moves towards left. This procedure repeats. Both the base stations have access to all the data. We analyze this FWLAN using the elevator polling system.

Let the base stations be placed respectively at (p 1 , 0), (p 2 , 0). Let p := (p 1 , p 2 ). In this case the ferry path is given by C p = {(q, 0) : p 1 ≤ q ≤ p 2 }. The partitions are calculated based on the nearest distance criterion.

I(q) = I(q, 0) =    {q} ×[-d, d] p 1 < q < p 2 [-l, p 1 ] ×[-d, d] q = p 1 [p 2 , l] ×[-d, d] q = p 2
Note in this case that, both the ends of the ferry path cover not just a line segment but a rectangular strip. We make simplifying assumptions as in section III. Under these assumptions b(q; p) =

c 2 +      η b d -d (1 + y 2 ) α dy 2d p 1 < q < p 2 η b p1 -l d -d (1 + y 2 + (p 1 -x) 2 ) α dxdy 4ld q = p 1 η b l p2 d -d (1 + y 2 + (p 2 -x) 2 ) α dxdy 4ld q = p 2 , b (2) (q; p) = 2b(q; p)c 2 -c 2 2 +      η (2) b d -d (1 + y 2 ) 2α dy 2d p 1 < q < p 2 η (2) b p1 -l d -d (1 + y 2 + (p 1 -x) 2 ) 2α dxdy 4ld q = p 1 η (2) b l p2 d -d (1 + y 2 + (p 2 -x) 2 ) 2α dxdy 4ld q = p 2 . β = 2α = 2, c1 = 100 β = 2α = 2, c1 = 10 β = 2α = 2, c1 = 1 h2 (l * 1 , p * , l * 2 ) (l * 1 , p * , l * 2 ) (l * 1 , p
η b = 1, η (2) b = 1.1, λ = 1e -7
Note here that even under symmetric assumptions the service moments are not equal at all points, thus resulting in an asymmetrical polling system. With the above the overall service moments are given by,

b p = 2d(l -p 2 )b(p 1 ; p) + 2d(p 1 + l)b(p 2 ; p) +2d(p 2 -p 1 )b(p 1 +; p) b (2) p = 2d(l -p 2 )b (2) (p 1 ) + 2d(p 1 + l)b (2) (p 2 ) +2d(p 2 -p 1 )b (2) (p 1 +; p).
In the above by b(p 1 +; p) we meant the expected value at any point with its x component just greater than p 1 .

Thus the service moments can be different at different points in the ferry path. However, because of the elevator service, the expected weighting times are equal at all the points (see Appendix A). Thus, it will be Pareto optimal to optimize the common expected weighting time itself which from (6) of Appendix A equals

λb (2) p 2(1 -λb p ) + (p 2 -p 1 )c -1 1 .
Further in this symmetric case it is easy to see that p * 1 = -p * 2 . Thus,

p * 2 = arg min 0<p2≤d λb (2) -p2,p2 2(1 -λb -p2,p2 ) + 2p 2 c -1 1 .
Note here that optimal choice of p * 2 optimally places the two base stations as well as optimally designs the ferry path. In this example, it is easy to see that : [START_REF] Altman | On Elevator Polling with Globally Gated Regime[END_REF] As the speed of the ferry c 1 increases, the p * 2 moves towards l, i.e., if the ferry can move at large speeds, it is optimal to place the base stations at both the edges of the area and allow the ferry to traverse the entire width of ∆. This conclusion is also true whenever the path loss factor β is large. (2) If the ferry moves at moderate speeds and or the path loss factor is small p * 2 reduces. Thus for small path loss factors, the ferry can move in shorter line segments and cover the entire area optimally.

We simplified the problem greatly by considering that the ferry moves in a horizontal line placed at the center of the area. This simplification is good as long as the arrivals are uniform and the file sizes are distributed the same way at all points. For asymmetrical arrivals this choice of ferry route may not be good. In this case it might be better to consider a general straight line passing through points (p 1 , p 2 ) and (p 3 , p 4 ) as ferry path. The base stations are placed once again at both ends of the ferry path. One can estimate the expected waiting time in terms of the parameter p := (p 1 , p 2 , p 3 , p 4 ) in a similar way and choose p * optimally. This p * places the base stations optimally and designs the ferry routes optimally in more generality. If the breadth of ∆, 2d, is large it might be better to consider zig zag ferry paths (Figure 5) with two base stations.

B. FWLAN in Annular area

In figure 6 we consider annular area with 2 base stations placed inside the area. Two ferries move inside this area in a circular path of radius l, one of them covers the upper arc (spanning over angle θ as in Figure 6) joining the two base stations while the second one covers the lower arc. As in the previous section, each of the ferries move from one base station to the other and hence change their directions in alternate cycles. This system can again be modeled by 2 independent elevator polling systems. The optimal base station placement and ferry route design can be achieved by optimal computing (θ, l) so as to minimize the expected waiting time.

V. CONCLUSIONS

We obtained analytical expressions for the expected virtual workload in a Ferry based Wireless LAN, which allowed us to optimize the Ferry trajectories. Our analysis could handle uplink as well as downlink traffic, it further could handle the combined uplink and downlink traffic. Minimizing the average virtual workload results in a Pareto minimization of the expected waiting times in the system. In order to obtain the expressions for the workload in the system we had to extend the fundamental theory of continuous polling systems. We have further presented some extensions to the case of several base stations and or several ferries. We observe that by using two base stations, one can achieve fairness : the expected waiting times are independent of the positions of arrivals. In a polling system with continuum of queues, the server moves continuously and stops at point q only when it finds a user with request. Not much theory is available for calculating the expected virtual workload of a continuous polling system. In [START_REF] Kavitha | Theory of continuous polling systems applied to the Design of Message Ferry Routes in sensor networks[END_REF], [START_REF] Kavitha | Polling models applied to Wireless Local Area Networks with Message Ferries[END_REF] we both summarize the relevant existing results as well as derive new results related to continuous polling systems, which are useful for analyzing the FWLAN. In this appendix we summarize the same.

The server is moving continuously on a circle C of radius R with speed c 1 . The arrival process is modeled by a Poisson process with intensity λ and every arrival is associated with two marks, the position Q ∈ C distributed as P Q and the service times B. Let b(q) b (2) (q) represent the conditional first two moments of the service time B conditioned on the event that the position of arrival is at point q.

Types of Services : In a globally gated service, the server closes a fictitious gate each time it arrives at a fixed point in the circle and tags all the users that arrived before the closure of this gate. In the current cycle, i.e., till the time it retouches the fixed point, it moves along the circular path and serves only the tagged users as and when it encounters one. On the contrary in a gated/exhaustive service polling system, the users are served more immediately after their birth: they are served the first time that the server encounters them. A mixed service polling system is a system in which the servers attends some of the users with globally gated service (with probability p ggs ) and the rest with exhaustive service (probability p es = 1 -p ggs ).

Virtual Workload : We obtain the virtual workload of this mixed system as a limit of a 'corresponding' discrete polling system (see [START_REF] Kavitha | Theory of continuous polling systems applied to the Design of Message Ferry Routes in sensor networks[END_REF], [START_REF] Kavitha | Polling models applied to Wireless Local Area Networks with Message Ferries[END_REF] for details) and it equals. respectively represent the globally gated, the exhaustive and the overall average service times and b (2) is the second moment of the overall service time.

V mix = λ 2 bb
Elevator Service : A polling system with elevator service is similar to globally gated one except that the server moves in the opposite direction every time it reaches the point at which the global gate closes. The server moves in counter clockwise direction in alternate, say odd numbered cycles and in the reverse direction in the even numbered cycles. In [START_REF] Kavitha | Theory of continuous polling systems applied to the Design of Message Ferry Routes in sensor networks[END_REF], [START_REF] Kavitha | Polling models applied to Wireless Local Area Networks with Message Ferries[END_REF] it is shown for elevator service that the expected waiting time at any point q ∈ C is independent of its position q. The common expected waiting time and the virtual workload for this system (obtained in [START_REF] Kavitha | Theory of continuous polling systems applied to the Design of Message Ferry Routes in sensor networks[END_REF]) are derived to be,

E[W ](q) = λb (2) 2(1 -λb) + |C|c -1 1 and (6)
V elevator = λb λb (2) 2(1 -λb)

+ |C|c -1 1 . (7)

Fig. 1 .Fig. 2 .

 12 Fig. 1. One Ferry in an annular ring

  C n := {q : ||q|| = l n } and let B(x, p) := {y : ||y -x|| < p} represent the open ball while B(x, p) represent its closure. The first ferry caters the users in the annular ring B(0, p 1 ) -B(0, h 1 ) while the last one covers the annular ring B(0, h 2 ) -B(0, p N -1 ). Any intermediate n th ferry covers the area B(0, p n ) -B(0, p n-1 ). Let p 0 := h 1 and p N := h 2 . In this subsection we choose optimally

Fig. 5 .Fig. 6 .

 56 Fig. 4. One Ferry in Rectangular area with 2 BS

1 1 2 ++ λ 2 |C|c - 1 1 2 ( 1

 12121 (2) 2(1 -λb)+ λb|C|c -p ggs λc -1 1 E[Qb ggs (Q)] -λb) b 2 + (pggs b ggs ) 2 + p ggs p es b ggs b es (5) where |C| = 2πR, b ggs := E Q b(Q)1 {Q globally gated service} , b es := E Q b(Q)1 {Q Exhaustive service} and b = p ggs b ggs + p es b es

Virtual Workload : The total service time required by all the waiting users ([START_REF] Boxma | Pseudo-Conservation Laws in Cyclic-Service Systems[END_REF]).


Salma Ben Sassi

Nicolas Le Sommer

Towards an Opportunistic and Location-Aware Service Provision in Disconnected Mobile Ad Hoc Networks

Opportunistic networking has recently appeared as a promising method to support communication in disconnected mobile ad hoc networks. This new communication model relies on the "store, carry and forward" principle, and exploits ad hoc communication and device mobility in order to achieve a networkwide message dissemination. It allows nomadic people to communicate together without resorting to infrastructure-based networks and to have access to services offered by infostations even if they are not in the area covered by these devices. Nevertheless, to be efficient this model requires to guide the message propagation using contextual information, and especially location information. In this paper, we present the middleware solution we have defined in order to support the provision of location-aware application services in disconnected mobile ad hoc networks using opportunistic communications.

Introduction

With the significant progress achieved since many years in the domains of hardware computing and wireless communication, smartphones, personal digital assistants and netbooks have become cheaper and more powerful, and are now widely spread. However, the main use of these devices lies so far in accessing the Internet via wireless access point (i.e., hotspots) in order to send and receive email or to surf the Web. Yet, all these devices are equipped with WiFi interfaces capable of ad hoc communication, and could be used by nomadic people to communicate together without necessarily resorting to an infrastructure-based network, and to access application services offered by fixed devices embedded in their physical environment, or even by mobile devices themselves.

Opportunistic networking [START_REF] Pelusi | Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks[END_REF][START_REF] Leguay | Opportunistic content distribution in an urban setting[END_REF][START_REF] Leontiadis | GeOpps: Geographical Opportunistic Routing for Vehicular Networks[END_REF][START_REF] Boldrini | Hibop: a history based routing protocol for opportunistic networks[END_REF] has recently appeared as a relevant mean to support communication in mobile ad hoc networks (MANETs), which are in realistic conditions intrinsically disconnected due to the sparse and irregular distribution of the mobile devices and the fixed infostations that composed them. Like delay-tolerant networking [START_REF] Shah | Delivering Messages in Disconnected Mobile Ad-Hoc Networks[END_REF][START_REF] Sollazzo | TACO-DTN: A Time-Aware COntent-based dissemination system for Delay Tolerant Networks[END_REF][START_REF] Fall | A Delay-Tolerant Network Architecture for Challenged Internets[END_REF], the opportunistic networking exploits ad hoc communication and device mobility to exchange data allowing hosts to communicate with each other even if a route connecting them does not exist all the time. Indeed, in opportunistic networks, messages are not simply routed in the network. While travelling from host to host in the network, they can be stored temporarily on certain hosts and be forwarded later when the circumstances are favourable. By thus exploiting ad hoc communication and device mobility, messages can be propagated network-wide. However, application services are often relevant only in specific areas. Consequently, the messages inherent in the discovery, the advertisement and the invocation phases should be restricted to these areas instead of being propagated network-wide thus granting a sensible reduction of the network load.

In this paper, we present a flexible and extensible framework designed to support the development of location-aware application services, as well as the provision of these services using opportunistic communications. This framework defines several representations of the location concept, and several location determination methods. It also implements a location-aware and opportunistic service provision model. With this model, service providers are able to exhibit their location constraints, requirements and properties and to include this piece of information in their service advertisements. Likewise, service clients are aware of their real-time location, and able to perform service discovery, service selection and service invocation based on this location. For instance, a client application can discover and locate all service providers available in its neighbourhood and invoke the nearest one. This service application model is supported by a location-aware communication layer, where the opportunistic dissemination of application messages can be restricted to given geographical areas (i.e., the areas specified as relevant for the service discovery and invocation by the applications).

The remainder of this paper is structured as follows. Section 2 presents a framework for mobile host location and environment modelling. Section 3 describes how application services can use location information in the service discovery and invocation processes as well as in the message dissemination process. Section 4 presents the results we obtained by running our middleware platform on a mobile ad hoc network simulator. Section 5 compares our proposal with works targeting the same objectives as ours, and Section 6 provides a summary of our contribution and concludes by giving some perspectives.

Location framework 2.1 Location requirements for opportunistic service provision

The provision of application services using opportunistic communication introduces new issues that have not been identified so far with the single-hop synchronous communication model that is traditionally used for service provision. Indeed, with opportunistic communication service messages are likely to be propagated network-wide. Hence, application services can potentially be discovered and invoked in the whole network by mobile clients, even if these services must only be accessed in specific areas. Moreover, a network-wide dissemination of messages increases the global network load and reduces its scalability. A message propagation control using an expiration time and a number of hops is not sufficient for service provision, which requires a locationbased propagation control. In order to underline both the issues inherent in the service provision using opportunistic communication and the needs of having location-aware services and middleware platforms, let us consider a campus populated with several service providers offering wireless access to printing services for students (see Figure 1). For example, in order to propagate advertisement messages for printing services in the whole campus, service providers SP 1 , SP 2 and SP 3 can decide to send their messages with a high number of hops. These messages will be widely disseminated in the campus by the students' devices, but also outside the campus. Indeed, without location constraints these service advertisement messages will be stored, carried and forwarded until their number of hops is equals to zero. For example, student S 1 who is going from building A to building B can propagate the service advertisement it received from provider SP 1 in A, in a location area close to building B. These services could thus be discovered -and potentially invoked-outside the campus by service clients, even if that should be prohibited. Furthermore, service clients having no information about their own location and about the location of the providers can achieve bad provider selections and invocations. For instance, after having received an advertisement from providers SP 1 and SP 3 , student S 1 (or more precisely the middleware installed on the device used by S 1 after an action performed by the latter) can decide to select and invoke the service offered by SP 1 , whereas he is now closer to SP 3 than SP 1 , since no information allows to distinguish the services offered by SP 1 and SP 3 .

Consequently, it could be convenient to have service providers able to give their location and to define in which location area their service advertisements must be forwarded, as well as to have location-aware service clients. This way, SP 1 , SP 2 and SP 3 could specify that their service advertisements must only be propagated in the campus, and S 1 could compare its own location with the location of the providers, and thus select the nearest provider without ambiguity. Moreover, it is suitable that service providers can specify, in addition to the location area in which they can be discovered, the location area in which they can be invoked. Indeed, these two location areas can be different. For example in the scenario of Figure 1, providers SP 1 , SP 2 and SP 3 should be discovered by the students in the whole campus, but should only be invoked by their respective surrounding students (i.e., by the students who are in the building where the providers are deployed).

Similarly, the service discovery requests and the service invocation requests sent by service clients must not be disseminated in the whole network, but only in specific location areas. For that, clients should be able to specify their own location and the location areas where their service messages can be propagated. Thus, only the providers located in the location area specified by the client can receive these requests and can return a response if they provide the required service. For example, if student S 1 has not received an advertisement from service provider SP 2 when reaching building C, student S 1 could initiate a service discovery by sending in the network a service discovery request with a geographic-restricted location area and its own location, and it should receive in return only an advertisement from SP 2 . On the contrary, if he wants to discover all the services available in the campus, he should specify that its request must be propagated in the whole campus.

The key issues thus lie in the definition of the location concept and location determination methods, and in the design of service-oriented middleware platforms able to efficiently exploit location information in service discovery, service selection and service invocation, as well as in message routing. In the remainder of this section we present a location framework, and in the next section we present how this framework is used in a service management middleware layer and in middleware layer supporting opportunistic communication.

Location modelling

In many related works, the concept of location is often reduced to GPS coordinates -which are defined by a longitude and a latitude expressed in decimal degrees with respect to the World Geodetic System 1986 (WGS84), and an elevation above the WGS84 ellipsoid that is expressed in meters. Yet, in a pervasive environment similar to that considered in Figure 1, obtaining GPS coordinates is not always feasible, and this expression of location is not suitable in many cases. For instance, service providers SP 1 , SP 2 and SP 3 deployed within buildings -where GPS signal cannot be received-should not define their location and their discovery and invocation location areas using GPS coordinates, but instead with symbolic names that can be expressed as a textual address information divided into fields (e.g. street, postal code, city, etc.). The term location thus should refer to the generic concept of a place that can be identified either by a symbolic name, a position expressed in a specific coordinates system, or an area. Our location framework, supports these different representations of the location concept, and defines methods making it possible 1) to estimate the distance between two locations when specifying intermediary locations or not, 2) to determinate if a location is included in another, and 3) to return the method used to obtain (or to estimate) this location. Four kinds of locations are defined in our framework: 1) waypoints, 2) landmarks, 3) location areas identified by a symbolic name, and 4) proximity-oriented location areas.

Waypoints are locations with no particular significance. They are only described by their position in a specific coordinate system. In contrast, Landmarks are locations characterised by both a position and a symbolic name defined as textual address information divided into fields (e.g. street, postal code, city, etc.). They are typically used to identify a place on a map.

Like landmarks, the location areas are identified by a symbolic name defined as textual address information and/or by coordinates and a geometric shape. They can be typically used by providers to specify where they are to define service discovery and invocation areas, as well as by the clients to define their own location, the area in which their service discovery requests can be propagated, and the area of the provider they try to invoke if necessary. A location area can be defined as an assembly of preexisting areas. A primitive location area is mainly defined by a symbolic name and/or by coordinates and a geometric shape. A composite location area is defined so as to include other location areas, and to define how these areas are composed together using binding operators such as the union, the intersection, and difference (the default operator is the union). Architectural elements of physical environments, such as buildings, can be defined with location areas. They can be identified by an address and a position, and be described by the floors that compose it, which themselves can be structured as sets of several rooms. Thanks to such a composite modelling, a location information can be easily refined or extended by our framework when needed, thus offering several levels of precision to locate service clients and service providers.

Finally the proximity-based areas are characterised by a shape and geographic coordinates. They are mainly used by mobile clients in order to discover what services are in their neighbourhood, and by service providers to define in which area they can be accessed knowing their own position.

Location determination method

A location can be determined using several methods and technologies. The technologies used in location determination have been classified in [START_REF] Hightower | Location Systems for Ubiquitous Computing[END_REF] according to properties such as media, type of information, method, scale, cost, accuracy and point of computation. The media refers to the underlying technique (e.g., acoustic, video, electromagnetic). The type of information can be a physical position or some symbolic information; both can be absolute or relative. Symbolic location is defined to be a position relative to some known entity whose location may or may not be precisely known. In [START_REF] Hightower | Location Systems for Ubiquitous Computing[END_REF], three generic location determination methods are identified: proximity, triangulation and scene analysis or pattern recognition. These methods are also classified according to the point of computation, which can be server-based or client-based.

Our framework was designed with a similar classification in mind. All the objects modelling a location thus define a method returning an object that specifies the location type, the computation method and the technology used to obtain the location, and the point of computation. A location type can be either absolute, relative or symbolic. Landmarks and way points are absolute locations that are expressed with a position in a specific coordinate system (the default system is the WGS84), and which can be obtained using a GPS typically. Relative location is defined as a position estimation with respect to another location information. Proximity-oriented locations are examples of relative locations. Such location can be obtained using a proximity or triangulation computation methods on the basis of wireless signals for instance. Finally, symbolic locations are location areas identified by a symbolic name. In our current implementation only two kinds of technology are considered in the location determination: the GPS and the wireless communication interfaces. Wireless technologies are characterised by their communication range, their type (e.g., 802.11, 802.15), and other information such as the signal level or the noise level. Moreover, four kinds of computation methods have been identified: the direct method, the pattern-matching-based method, the proximity-based method, and the triangulation method. In the current implementation of our framework only the last method is not implemented yet. The direct method is a simple method that is used to compute the coordinates obtained from a GPS receiver. The proximity-based method is used for wireless technologies and implements a linear attenuation model. The pattern-matching-based method relies on a hierarchical pattern matching mechanism on textual address information divided into fields (e.g. street, postal code, city, etc.). The location estimation can be computed either locally or remotely by another device in the network. Indeed, if a device cannot estimate its location itself, it can ask for a remote host (or a set of remote hosts) to compute this location according to the messages they receive from the mobile device and of the characteristics of the wireless technology.

Maps projection and environment modelling

The environment modelling and maps projection are key features for the location-aware service provision. Indeed, it is often necessary to build location databases, and to deploy them on mobile devices in order to associate address information with GPS coordinates for instance, or to indicate the position of people (or service providers) on maps. Coordinate projection and conversion functions have thus been implemented in our framework. Thanks to the landmarks and location areas, our framework provides general, yet easy to use, means for environment modelling. Obviously, our framework does not perform a 3D representation of the environment like CityGML [START_REF] Groger | OpenGIS City Geography Markup Language (CityGML) Encoding Standard[END_REF], which is dedicated to 3D urban representation and that covers a very large field of places. Mobile devices do not need to be equipped with a location database natively, they can build themselves their own database (and therefore their own perception of the environment) by exploiting the location information included in service messages roaming in the network.

Figure 2 shows an application that has been developed using our framework, and that runs on a PDA. This application makes it possible, for instance for students, to model the campus, to see where they are, and to locate the application services available in the campus, such as the printing services.

Middleware support for location-aware application services

In this section, we first present how service messages are structured, and how they are handled by the service management and the communication middleware layers. Then we present how service clients and providers use the framework detailed in the previous section in order to express their location requirements, constraints and properties, and how location information is currently exploited in message routing.

Location information and service message structure

All the messages exchanged opportunistically by the devices are structured in two parts: a set of headers and a content (see Figure 3). Some of message headers are compulsory, such as origin and destination for routing purposes, number of hops to limit the propagation of messages in term of hops, and expiration time and date to define the temporal validity of messages. Other headers are optional, and are generally some complementary information specified by the application services so as to help in service selection and message routing. The content of messages depends on the type of messages. For example, the content of a service discovery request is a service pattern, whereas the content of a service advertisement is a service descriptor (see Figure 3). The service location properties and constraints mentioned in the previous section (e.g., service discovery location area, service invocation location area, and service provider location) are specified within the content of such messages. Some of these properties and constraints are also defined as optional headers by the service management middleware layer in order to specify how these messages should be processed by the opportunistic communication middleware layer.

Location management in the service management middleware layer

With our middleware platform each mobile host can maintain its own perception of the services available in the network thanks to a dedicated service register. This register is responsible for performing service discovery and service selection. The service discovery can be achieved either proactively or reactively. The reactive discovery consists in listening and analysing the unsolicited service advertisements sent by providers in the network. The proactive service discovery consists in sending service discovery requests in the network and in listening and analysing the service advertisements returned in response by providers. Figure ?? shows how a printing service, comparable to those considered in the scenario presented in Section 2.1, can describe its location properties and constraints in its own service descriptor before registration. This descriptor will be then used by the service management layer in order to build a service advertisement for this service. The first block of instructions shows how to model the place where the service provider is located using a symbolic building (called A) with one floor (floor0), and whose address is "building A, UEB Campus. The second block of instructions defines a service descriptor including the interface exhibited by the service, its non-functional properties, and its locations properties and constraints. The last block of instructions registers the service in the local service register. In short, it describes a printing service with floor0 as invocation access area and the entire campus as discovery access area.

✴✴ ❊♥✈✐r♦♥♠❡♥t ♠♦❞❡••✐♥❣ ✿ ❝❙❤❛♣❡ ✐s t❤❡ ❝❛♠♣✉s ✬s s❤❛♣❡ ✴✴ ❜❙❤❛♣❡ ✐s t❤❡ ❜✉✐•❞✐♥❣ ✬s s❤❛♣❡ ✴✴ ❝♦♦r❞✐♥❛t❡s ♦❢ t❤❡ ❝❛♠♣✉s ❛♥❞ ♦❢ t❤❡ ❜✉✐•❞✐♥❣ •❡♦❣r❛♣❤✐❝❈♦♦r❞✐♥❛t❡s ❝❈♦♦r❞ ✱ ❜❈♦♦r❞ ❀ ❝❈♦♦r❞ ❂ ♥❡✇ •❡♦❣r❛♣❤✐❝❈♦♦r❞✐♥❛t❡s ✭✹✼ ✱✻✹✺✽✽ ✱✷✳✼✹✺✶✻✮ ❀ ❜❈♦♦r❞ ❂ ♥❡✇ •❡♦❣r❛♣❤✐❝❈♦♦r❞✐♥❛t❡s ✭✹✼✳✻✹✺✵✹ ✱✷✳✼✹✽✺✷✮ ❀ ❈♦♠♣♦s✐t❡▲♦❝❛t✐♦♥❆r❡❛ ❝❛♠♣✉s ❀ ❇✉✐•✐♥❣ ❜✉✐•❞✐♥❣❆ ❀ ❋•♦♦r ❢•♦♦r✵ ❀ ❝❛♠♣✉s ❂ ♥❡✇ ❈♦♠♣♦s✐t❡▲♦❝❛t✐♦♥❆r❡❛ ✭ ✧ ❯❊❇ ❈❛♠♣✉s ✧ ✱ ❝❙❤❛♣❡ ✱ ❝❈♦♦r❞ ✮❀ ❜✉✐•❞✐♥❣❆ ❂ ♥❡✇ ❇✉✐•❞✐♥❣ ✭✧❆ ✱ ❯❊❇ ❈❛♠♣✉s ✧ ✱ ❜❙❤❛♣❡ ✱ ❜❈♦♦r❞ ✮❀ ❝❛♠♣✉s ✳ ❛❞❞ ✭ ❜✉✐•❞✐♥❣❆ ✮❀ ❢•♦♦r✵ ❂ ♥❡✇ ❋•♦♦r ✭✧ ❋•♦♦r✵ ✧ ✱ ❜✉✐•❞✐♥❣❆ ✮❀ ✴✴ ❙❡r✈✐❝❡ ❞❡s❝r✐♣t♦r ▲♦❝❛t✐♦♥ ✐♥✈♦❝❛t✐♦♥❆r❡❛ ❂ ❜✉✐•❞✐♥❣❆ ❀ ▲♦❝❛t✐♦♥ ❞✐s❝♦✈❡r②❆r❡❛ ❂ ❝❛♠♣✉s ❀ ▲♦❝❛t✐♦♥ ♣♦s✐t✐♦♥ ❂ ❢•♦♦r✵ ❀ ❙❡r✈✐❝❡❉❡s❝r✐♣t♦r ❞❡s❝ ❂ ♥❡✇ ❙❡r✈✐❝❡❉❡s❝r✐♣t♦r ✭✧ ♣r✐♥t✐♥❣ s❡r✈✐❝❡ ✧ ✱✧ ❢r ✳ ✉❜s ✳ ❝❛s❛ ✳ Pr✐♥t❙❡r✈✐❝❡ ✧ ✱ ♣♦s✐t✐♦♥ ✱ ✐♥✈♦❝❛t✐♦♥❆r❡❛ ✱ ❞✐s❝♦
Local service clients can invoke the local service register in order to discover the remote services available in its neighbourhood. For example, to discover all printing services available in a range of 200 meters, the client must create a service pattern describing the service it requires and specifying its location constraint. Figure ?? shows an example of the definition of such a service pattern using an object of type Proxymit-yArea. This service pattern will be included by the service register in a service discovery request if it has no information about a provider satisfying the required service interface and the location constraints expressed by the client. This discovery request will then be sent in the network in order to perform a proactive service discovery. The selection process aims at choosing the "best" provider to invoke among a set of providers, and at returning its reference to the client application. Meaning that we have to ensure that the selected provider is invokable (i.e, that the client is located within the invocation area when invoking) and that the chosen provider is the closest one to the client's current position and thus would be the fastest one to respond. The reference is then used by the client in order to build its service invocation request. In our framework, the asynchronous service invocation is achieved using notably the InvocationRequest and InvocationResponse messages and the ServiceInvoker and Ser-viceResponseHandler objects. To invoke asynchronously a remote service (or a set of remote services), a local client is expected to use the asyncInvoke() methods defined by the ServiceInvoker object. The first method asyncInvoke() takes as parameters a Invo-cationResquest object and a ServiceReponseHandler object. The handler object is used by the client to handle the responses it receives following an event-based programming approach. This handler takes as parameters a timeout -which should be equals to the expiration time specified in the request-and a number specifying how many responses must be handled. This handler is designed so as to receive responses from the network. When the timeout it received as parameter is triggered, the handler is expected to unregister itself from the ServiceResponseListener. A ServiceResponseListener is used to listen to a service response from the network and to dispatch them to objects of type ServiceInvoker and/or ServiceResponseHandler. The second method asyncInvoke() only takes as parameter an InvocationRequest. This method is designed to be running until a response is received from the network. When the timeout specified in the request is triggered, the method is expected to return a null value. Since temporal, spatial and contextual properties are intrinsically service-dependent, client services and service providers are responsible to specifying these properties themselves in the ServiceRequest and ServiceResponse objects respectively.

✴✴ ▲♦❝❛t✐♦♥ ♦❢ t❤❡ ❝•✐❡♥t ▲♦❝❛t✐♦♥ ❤♦st▲♦❝ ❂ ▲♦❝❛t✐♦♥Pr♦✈✐❞❡r ✳ ❣❡t❈✉rr❡♥t▲♦❝❛t✐♦♥ ✭✮ ❀ ✴✴ ❉❡❢✐♥✐t✐♦♥ ♦❢ t❤❡ ❞✐s❝♦✈❡r② ❛r❡❛ ▲♦❝❛t✐♦♥ ❞✐s❝♦✈❡r②❆r❡❛ ❂ ♥❡✇ Pr♦①✐♠✐t②❆r❡❛ ✭ ❤♦st▲♦❝ ✳ ❣❡t❈♦♦r❞✐♥❛t❡s ✭✮ ✱ ✷✵✵✮ ❀ ❙❡r✈✐❝❡P❛tt❡r♥ ♣❛tt❡r♥ ❂ ♥❡✇ ❙❡r✈✐❝❡P❛tt❡r♥ ✭ ✧ ❢r ✳ ✉❜s ✳ ❝❛s❛ ✳ Pr✐♥t❙❡r✈✐❝❡ ✧ ✱ ❞✐s❝♦✈❡r②❆r❡❛ ✮❀ ✴✴ ❙❡r✈✐❝❡ •♦♦❦✉♣ ❙❡r✈✐❝❡Pr♦✈✐❞❡r r❡❢❙r✈ ❂ ❙❡r✈✐❝❡|❡❣✐st❡r ✳ •♦♦❦✉♣ ✭ ♣❛tt❡r♥ ✮❀

Exploitation of location information while routing

As underlined in the scenario presented in Section 2.1, with opportunistic communication, service messages may be forwarded outside the area where they are relevant. In order to cope with this issue and relieve the network from irrelevant messages, we have introduced, in addition to the compulsory headers presented in Figure 3, an optional header, called restriction header, to restrain messages geographically. The opportunistic communication middleware layer is designed to compare the current location of the mobile host with the value of this header before relaying a message. Thus, mobile hosts can forward a message if and only if they are within the area described in the restriction header of this message. This header is specified by the service management middleware layer on the basis of location information specified by application services in service descriptor and service pattern and it usually represents the access area or the discovery area of the targeted providers.

Evaluations

In order to evaluate our model, we have made a series of simulations using the Madhoc simulator1 , 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, allow us to run our middleware platform on it.

In this section, we focus on a particular experiment whose objective was to measure the ability to satisfy the client service invocation efficiently using location information. For that, we compared our location-aware service discovery, selection and invocation model with a classical model that does not exploit the location properties exhibited by service providers and mobile devices. Moreover in the first case, we use an opportunistic communication protocol based on an epidemic model that implements both a hop-based and location-based message propagation control, and in the second case we use an opportunistic communication protocol relying on an epidemic model implementing only a hop-based message propagation control (messages are limited to 4-hops in our simulation). In the location-aware model, clients must await to be into the invocation area of a provider offering the service they require in order to start invoking this service, while in the other model, their service messages are forwarded by the other mobile hosts freely and thus client applications do not require to meet any conditions before invoking randomly one of the providers discovered (regardless of their positions or access areas).

The simulation environment we consider is an open area of about 1km 2 containing 4 buildings and populated with a 100 devices equipped with Wi-Fi interfaces: 10 fixed infostations located in the buildings and 90 mobile hosts that evolve from a building to an other following a random way point mobility model and taking a 5 to 10 minutes time pause in each building they reach. Each mobile host moves with a speed varying between 0.5 and 2 m/s. 70 mobile hosts are chosen periodically to act as relay nodes. Relay nodes are expected to forward immediately all service messages they receive while the other hosts are expected to forward their messages with a periodicity of 20 seconds. Each message has an expiration time of 4 minutes (when a message has expired, it is removed from the cache of messages and cannot be forwarded). Among the mobile hosts, only 60 hosts run client applications for the services offered by the infostations. When they have discovered a provider, the clients try to invoke them periodically (every 5 minutes) with a different request. In Tables 2 and1 we summarise the simulation results we have obtained. The Table 2 shows that the network load has indeed been globally reduced by half and that the message traffic is controlled and restricted within the predefined discovery and invocation areas. Furthermore, the location-awareness has an impact on the service selection and service invocation since the success invocation rate increases from 32,60% for a random invocation to 66,25% for a location-based invocation (see Table 1). The average delay for a successful invocation has also been considerably reduced attaining an average value of 20s for location-aware applications. However, Table 1 also shows that the location-aware invocation model we propose has induced an extra waiting time of 72s due to the fact that a client application is not allowed to invoke a provider until it reaches its invocation area. A possible solution for this side effect would be to initiate the invocation before attaining the invocation area.

Related work

Many recent works have focused on problem of the opportunistic message forwarding in mobile ad-hoc networks, and some of them [START_REF] Boldrini | Hibop: a history based routing protocol for opportunistic networks[END_REF][START_REF] Sollazzo | TACO-DTN: A Time-Aware COntent-based dissemination system for Delay Tolerant Networks[END_REF][START_REF] Musolesi | Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks[END_REF][START_REF] Conti | Context-aware file sharing for opportunistic networks[END_REF] have considered contextual properties in order to define "smart" forwarding policies. However, despite the spreading use of positioning devices, only few location-based message forwarding protocols have been proposed so far. GeOpps [START_REF] Leontiadis | GeOpps: Geographical Opportunistic Routing for Vehicular Networks[END_REF] is an example of such protocols. It implements a store, carry and forward mechanism dedicated to vehicular networks, and exploits location information available via navigation systems to select vehicles that are likely to carry a message towards its destination. However such a protocol is not suited for a human-based mobility model. Indeed, in contrast to vehicles, people do not necessarily follow predefined routes while they are moving, making it difficult to determine if or when they will reach a given destination. GPSR [START_REF] Karp | GPSR: Greedy perimeter stateless routing for wireless networks[END_REF], Terminode routing [START_REF] Blazevic | A Location-Based Routing Method for Mobile Ad Hoc Networks[END_REF], and GRA [START_REF] Jain | Geographical Routing Using Partial Information for Wireless Ad Hoc Networks[END_REF] are also location-based routing protocols, and they use only neighbour location information for forwarding data packets. Routing is done in a greedy way by forwarding the packet to the closest neighbour to the physical location of the destination. This local optimal choice is repeated at each intermediate node until the destination is reached or the message's time to live (TTL) expired.

As far as the exploitation of location information at the service level is concerned, few works have been achieved to the best of our knowledge. In [START_REF] Meier | Proximity-Based Service Discovery in Mobile Ad Hoc Networks[END_REF], Meier et al. present a proximity-based service discovery protocol (PDS) for mobile ad hoc networks. Like our framework, PDS proposes a discovery approach of ad hoc services that exploits the fact that the relevance of such services is often limited to a specific geographical scope. Service providers are thus expected to define the areas (so-called proximities) in which their services are available. In PDS, clients register interest in specific services and are subsequently informed whenever they come into a "proximity" within which these services are available. In PDS, proximity areas are characterised by a given shape and coordinates and are included in discovery requests in order to select relevant service providers. However unlike our framework, PDS does not support several location models, and especially the address-based model that is best suited for indoor places.

Other works have also been done in the domains of the location management and location/environment modelling. These works have led to standards such as the location API for Java (JSR 179) [START_REF]JSR 179 Location API for J2ME Specification, nokia[END_REF], the OpenGIS Location Services (OpenLS) [START_REF] Bychowski | OpenGIS Location Services (OpenLS): Core Services. Open Geospatial Consortium, marwa mabrouk[END_REF] and CityGML [START_REF] Groger | OpenGIS City Geography Markup Language (CityGML) Encoding Standard[END_REF]. JSR 179 defines a framework to express a location with GPS coordinates expressed in the World Geodetic System 84. It also makes it possible to associate a location with an address-based information thanks to the concept of landmark, and defines a publish/subscribe paradigm that enables subscribers to be notified when a given location is reached. The OpenLS specifications detail the core services and abstract data types that comprise the GeoMobility Server. This server is an open location services platform for Web services defined by the Open Geospatial Consortium2 . It notably defines functionalities to create routes and driving directions, to support map portrayal and to find points of interest using either a proximity-based model or an address-based model. It relies on a complete XML-based location modelling and querying. Nevertheless in comparison to our framework, this specification does not define a simple and flexible API that could be used by service providers to specify where they are, what is their service access areas, etc.

CityGML is a specification aiming to represent an urban environment in 3D. Different elements such as buildings or city furniture are identified using their geometrical, topological, semantic, and appearance properties. These elements can also be described using address information that conforms to the XML Schema definition of the Exten-sible Address Language (xAL) and to the rules for representing address information in CityGML. However, since CityGML is dedicated to 3D representation and thus covers a very large field of places that are unnecessary for our work such as water body or city furniture and defines lots of irrelevant properties such as topology, colour or material type.

Conclusion and future work

In this paper, we have presented a middleware platform for location-aware services. This platform implements an opportunistic communication protocol in order to support service discovery and invocation in disconnected mobile ad hoc networks. It also defines several kinds of location models and location determination methods. These models and methods are used by application services in order to specify their own location and their discovery and invocation areas, as well as by the middleware itself in order to discover what services are available in a given location area, and to select and invoke service providers according to their location properties.

The simulation results we obtained by running our middleware platform on a mobile ad hoc network simulator show that our middleware offers a more reliable and efficient service provision than a classical random invocation model, while reducing the global load of the network and thus improving the network scalability.

In the future, we plan to improve our middleware platform so as to opportunistically route messages toward targeted geographical locations, and not only limit their propagation to certain geographical locations as in our current implementation.

Fig. 1 .

 1 Fig. 1. Example of a disconnected mobile ad hoc network

Fig. 2 .Fig. 3 .

 23 Fig. 2. A service location application developed using our framework and running on an IPAQ

Fig. 4 .

 4 Fig. 4. Example of descriptor definition for a location-aware service.

Fig. 5 .

 5 Fig. 5. Example of service look-up.

Table 1 .

 1 Simulation results for the service discovery and invocation process

		Restricted	Unrestricted
		dissemination	dissemination
	Global
	network load	3537988	1948290
	(messges number)
	Invocation
	traffic load	2345738	743502
	(messges number)
	Inter-areas traffic rate	40,11%	2,31%
	Intra-area traffic rate	59,89%	97,68%

Table 2 .

 2 Simulation results for the network load

http://agamemnon.uni.lu/~lhogie/madhoc/

http://www.opengeospatial.org/

Acknowledgments This work is done in the project SARAH. This project is supported by the French ANR (Agence Nationale de la Recherche) in the framework of the 2005 ARA SSIA program. ❤tt♣✿✴✴✇✇✇✲✈❛•♦r✐❛✳✉♥✐✈✲✉❜s✳❢r✴❙❆|❆❍