Veeraruna Kavitha
email: kavitha.voletiveeraruna@sophia.inria.fr

Eitan Altman
email: eitan.altman@sophia.inria.fr

Theory of continuous polling systems applied to the Design of Message Ferry Routes in sensor networks

In this paper we focus on a class of polling systems encountered while modeling the ferry based wireless local area network (FWLAN). A moving ferry, while walking in a predetermined cyclic path, communicates with the static nodes (or users) of the network via a wireless link. The ferry is assumed to stop and communicate with a node that has a packet to send or to receive, when it is closest to that node. The location distribution of the node to which or from which a packet arrives is assumed to have a support of positive Lebesgue measure. These features imply that polling models with finite number of queues cannot be used to model the system. We study in this paper the continuous polling systems with service disciplines that model the use of the FWLAN (and that are more complex than the classical exhaustive or gated services). Our approach is based on discretization of the continuous polling model. We propose a special way of discretizing the continuous system such that: 1) the known Pseudo conservation laws can be applied to obtain the stationary expected workload of the discrete systems; 2) the limit, of these 'discretized' expected workloads, equals the stationary expected workload of the continuous system. Our results rely heavily on fixed point analysis of infinite dimensional operators.

Introduction

Polling systems are a class of queueing systems wherein a single server attends to a number of queues. Systems with a finite number of queues (called discrete polling systems) have been analyzed to a good extent and there is good understanding of their stability conditions and on the Pseudo conservation laws for a variety of discrete polling systems in [START_REF] Takagi | Analysis of Polling Systems[END_REF][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 user classes[END_REF][START_REF] Boxma | Pseudo-Conservation Laws in Cyclic-Service Systems[END_REF][START_REF] Khamisy | Polling Systems with Synchronization Constraints[END_REF][START_REF] Sidi | A queuing network with a single cyclically roving server[END_REF] etc.

Continuous polling systems are the ones in which the location of arrivals as well as of the service can occur anywhere in a continuum of locations. Continuous polling were first introduced by Fuhrmann and Cooper [START_REF] Fuhrmann | Applications of the decomposition principle in m/g/1 vacation models to two continuum cyclic queueing models[END_REF], further studied, explored by Coffman and Gilbert [START_REF] Coffman | A continuous polling system with constant service times[END_REF][START_REF] Coffman | Polling and greedy servers on the line[END_REF] and Kroese and Schmidt [START_REF] Kroese | A continuous polling system with general service times[END_REF][START_REF] Kroese | Queueing systems on the circle[END_REF][START_REF] Kroese | Single-server queues with spatially distributed arrivals[END_REF][START_REF] Kroese | Light-traffic analysis for queues with spatially distributed arrivals[END_REF] in a series of works. Stability of such polling systems is discussed in [START_REF] Altman | Queueing in space[END_REF][START_REF] Georgiadis | Stability of token passing ring[END_REF][START_REF] Altman | Stability, Monotonicity and Invariant Quantities in General Polling Systems[END_REF][START_REF] Foss | Comparison Theorems and Ergodic Properties of the Polling Systems[END_REF].

It is relatively more complicated to study continuous systems and these are usually analyzed under simplified conditions, which we refer as 'symmetric conditions': every arrival picks up an uniformly-distributed landing site on the circle, settles down there and awaits service while the server is moving at a constant speed and in a fixed direction around the circle. Further the service time requirements of the users do not depend upon the position of the user.

The work on snowplowing systems in [START_REF] Eliazar | The snowblower problem[END_REF][START_REF] Eliazar | From polling to snowplowing[END_REF] generalizes many of the above assumptions and studies a more general continuous system. For example, the incoming work-flow to the system is taken to be a general Levy random measure and the walking times are assumed to be random.

In previous literature so far, the continuous polling systems have been mostly analyzed with standard gated/exhaustive service. In such systems, the server, while moving in a cyclic path, attends the users waiting anywhere on its path the first time it encounters them. But there are other important service disciplines (e.g., globally gated, elevator service etc) which are studied in a discrete polling system. In a globally gated service discipline ( [START_REF] Boxma | Cyclic Reservation schemes for efficient operation of multiple-queue single-server systems[END_REF]), the server attends the users the first time it encounters them after they are tagged and all the users are tagged whenever the ferry reaches a global point. Elevator service ( [START_REF] Altman | On Elevator Polling with Globally Gated Regime[END_REF]) is similar to globally gated service except that the server reverses its direction at the end of every cycle. There can be applications, wherein the users need to be supported via a mixture of the above service disciplines in a continuous polling system. For example, in a Ferry assisted Wireless LAN all uplink transmissions (data uploaded to BS via the Ferry from static sources) use an exhaustive discipline while all downlink transmissions (data downloaded to a sink from the Ferry which had earlier received the same data from BS) have to be modeled using a globally gated or an elevator regime.

The central idea of this paper is to use the known Pseudo conservation laws (known for a discrete system) for obtaining the stationary expected virtual workload of a continuous system (which supports mixture of services) via discretization. We discretize the continuous polling system in a special way such that the known Pseudo conservation laws can be applied for the resulting discrete systems and the limit, of these 'discrete' stationary workloads, equal that of the continuous system. We achieved this by utilizing the fixed point equations that can result because of stationarity. We basically utilize the periodic behavior in the system, identify certain quantities whose moments must be equal at the beginning and at the end of a cycle because of stationarity (stationarity implies palm stationarity) and hence obtain fixed point equations for the stationary moments. We identify those quantities, which can further be utilized for expressing the stationary expected workload in the system. We obtained the required limit majorly via continuous parameter (the number of discretization levels is the parameter here) dependence of the fixed points. Further, we obtain an expression for the expected stationary virtual workload abandoning the standard symmetric assumptions. Discretization approach is used for mixed service systems, while, the stationary workload for Globally gated and elevator service disciplines is obtained directly.

In this paper, incoming jobs arrive to the system following a Poisson process. Our approach can be used for studying other types of continuous polling whenever one can solve the related discrete problem and use similar limiting arguments. In [START_REF] Kavitha | Continuous Polling with Rerouting and Applications to Ferry Assisted Wireless LANs[END_REF] we used the same approach to study a continuous system with rerouting.

The second part of the paper applies the Polling system results to study a Ferry assisted Wireless Local Area Network (FWLAN). Message Ferry is a mobile relay station that serves as "postman" to deliver (collect) messages to (from) the static or dynamic wireless nodes in a sparse network, where direct connectivity is not possible. 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], 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 in 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 ( [START_REF]Umassdieselnet[END_REF]). In a related paper [START_REF] Tariq | Message ferry route design for sparse ad hoc networks with mobile nodes[END_REF], the message ferry serves some fixed finite number of nodes and the routes are designed based on the mobility models of those finite number of nodes. In contrast, in our work the ferry serves all the nodes that arrive anywhere in the given area as and when they arrive and the optimal routes are designed based on the arrival process, service requirements, network architecture, radio conditions, etc.

The ferry moves periodically in the cyclic route and either halts at predetermined finite number of stops or halts on its way only when it encounters a user with a request. We refer the former as BUS mode while the later one as TAXI mode. BUS mode has been studied using discrete polling systems in [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF], while this paper focuses on TAXI mode, using the continuous polling results. In the TAXI mode, every point on the ferry path is a potential stop and each stop is assigned an area that contains all points closer to that stop than to other stops. Upon reaching a stop, the ferry collects (uplink) and dumps (downlink) data from or to the area assigned to it.

An important performance measure for FWLAN design is the expected waiting time, i.e., the average time an arrival has to wait before it's service starts. The waiting time depends on: 1) the over-all service times (the time required to complete an uplink or downlink request using wireless medium); 2) the walking time, i.e., the time taken by the ferry to traverse the cyclic path once. The over-all service times reduce if one uses longer ferry routes as, then, the users can be served by the ferry standing relatively at a shorter distance. However the walking time increases with longer routes. The objective of this paper is to study these trade-offs using stationary expected workload performance. By this, we minimize the expected waiting times at all users in the Pareto sense.

One of the important contributions of this paper is to show how theory of polling systems can be mapped to obtain interesting performance measures for some interesting configurations of FWLAN. These performance measures are used for designing optimal ferry routes (in a given class of routes) or for designing optimal number of stops (for a given type of ferry route ( [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF])) and or for designing the location of base station(s). However one can think of many more applications of this mapping. For example, in [START_REF] Saad | A Selfish Approach to Coalition Formation among Unmanned Air Vehicles in Wireless Networks[END_REF] the authors consider a wireless scenario with many ferries and user groups. Their aim was to group ferries and users into coalitions in a optimal way. Each coalition in their paper was a simple example of ferry based wireless LAN. Our results can probably be used to form these optimal coalitions for more complicated architectures.

The continuous polling models are studied in section 2 while ferry based wireless LAN examples are analyzed in sections 3 and 4. Some proofs are available in Appendices.

Continuous Polling Systems

In a continuous polling system, the server moves continuously and stops at point q only when it finds a user with a request. The server is moving continuously on a circle C of radius γ with speed α. 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. The service times in general can depend upon the position Q of the arrival. 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. However the service times of different users are independent of each other.

The server either provides pure or mixed type of service to the users. In a pure globally gated service system, the server closes a fictitious gate each time it arrives at a fixed point in the circle (we refer it as 0) and tags all the users that arrived before the closure of the gate. The time period between two consequent arrivals of the server at 0 is referred as cycle. In every cycle, the server moves along the circular path and serves only the tagged users as and when it encounters one. Note here that some times an user may be served only the second time the server encounters it after it's arrival. On the contrary in a pure gated/exhaustive service polling system, the users are served more immediately after their birth: they are served the first time, the server encounters them. In a discrete polling system, there is a difference between gated service (the server closes a local gate at every queue and leaves the queue only after serving the users that appeared before the gate closure) and exhaustive service (the server also attends the users that arrived during the service of already existing users and it leaves the queue only when the queue is empty). But the two converge to the same service in a continuous polling system with P Q continuous: at any queue (which is a point in the continuous case), the probability of a new user appearing at the same point is zero.

In a mixed service polling system, the server attends some of the users with globally gated service and the rest with exhaustive/gated service. Let pgg, pg = 1pgg respectively represent the probability that an arrival is a globally gated user and a gated user. Let bg(q), b

g (q) represent the conditional first and second moments of the service time given that the arrival is at point q and further given that the arrival is a gated user. Let bgg(q), b

g := E[b (2) g (Q)], b(2) gg := E[b (2)
gg (Q)] and b(2

) := E[b (2) (Q)]
. Notations : The variables like b, bg, bgg, f Q , τ , v represent the functions on interval [0, |C|] while terms like b(q) or τ (q) represent the function values at a point q ∈ [0, |C|]. The bar of the same variable, like bg represent the average w.r.t. to the position distribution P Q , i.e., bg = E[bg(Q)]. Similarly variables like τ (2) , τ (2) etc. are functions on [0, |C|] × [0, |C|] while τ (2) (q, q ′ ) represents the function value at (q, q ′ ). Let q ∧ |C| represent the minimum value, min{q, |C|}. The expectation with respect to the stationary measure of the process under consideration is given by E while E 0 represents the expectation with respect to Palm stationary measure.

Virtual workload of a polling system is defined as the total workload corresponding to all the waiting users, i.e., the sum of the service times of all the waiting users. It is an important performance measure and will be used in later sections for analyzing 1 Right now the position of arrival is distributed the same way for gated as well as globally gated users. But the results can easily be generalized to separate P Q,g and P Q,gg .

interesting application in delay tolerant networks. Not much theory is available for calculating the expected virtual workload of polling systems with arrivals in a continuum. In this section we derive new (stationary expected workload) results related to continuous polling systems. Throughout we consider stationary and ergodic systems. An exhaustive/gated continuous polling system is analyzed in [START_REF] Kroese | A continuous polling system with general service times[END_REF] under symmetric conditions and we summarize the same in subsection 2.1. The main contribution of this paper towards polling systems are available in subsections 2.2, 2.3 and 2.4 in the form of stationary expected virtual workload derivations for polling system respectively with a globally gated service, elevator and mixed service. These results also cover the gated/exhaustive service system under asymmetric conditions.

Exhaustive/Gated Service

An exhaustive service continuous polling system under symmetric conditions is analyzed in [START_REF] Kroese | A continuous polling system with general service times[END_REF]. They have many more results but we only present the ones relevant to this paper, i.e., the expression for expected virtual workload under stationarity. The users arrive uniformly on the circumference with |C| = 1 as a Poisson process with intensity λ, i.e., P Q is uniform. Further the service time moments bg(q), b

g (q) are assumed to be same at all points q and are equal to bg and b(2) g respectively. Then the stationary expected number of customers on the circle is given by [16, Theorem 5.1]

E[N ]g = λ bg + λ α -1 + λ b(2) g 2 1 -λ bg .
In this case they also considered the user under service. Excluding the user under service, i.e., the stationary expected number of waiting customers equal:

E[N ] w g = λ α -1 + λ b(2) g 2 1 -λ bg . (1)
From [START_REF] Baccelli | Elements of Queueing Theory[END_REF], by Wald's lemma the virtual workload, the workload due to the waiting customers, equals:

V sym g := bgE[N ] w g = λ bg α -1 + λ b(2) g 2 1 -λ bg . (2)

Globally Gated Service

In this subsection we derive the corresponding results for a globally gated service. Further we don't assume symmetric conditions and work under more general conditions as explained before. We map the circumference to a line of length |C| := 2πγ with the starting point (the point at which the global gate is closed) mapped to 0.

Computation of the moments of the Cycle time in stationary regime:

Let Cn represent the time taken to complete the n th cycle. Let N (C) represent the number of Poisson arrivals in time C. With B n i representing the service time of the i th user arrived during the n -1 th cycle, the adjacent cycles times can be related using

Cn = N (Cn-1) i B n i + |C|α -1 .
By first conditioning on N (C n-1 ) and then on C n-1 , it is easy to see that,

E   N (Cn-1) i B n i   = λE[C n-1 ] |C| 0 bgg(q)P Q (dq).
Thus under (Palm) stationarity 2 ,

c * := E 0 [Cn] = |C|α -1 1 -λ bgg . (3)
From the above it is clear that the system is stable only if the factor ρ := λ bgg is strictly less than 1. This is the usual condition for stability and throughout this paper we assume stability. In a similar way as,

  N (Cn-1) i B n i   2 = N (Cn-1) i B n i 2 + i =j B n i B n j and because E[N (Cn) 2 -N (Cn)] = λ 2 E 0 [C 2 n ] (with c (2) * := E 0 [C 2 n ]), c (2) * = λc * b(2) gg + λ 2 c (2) * b2 gg + |C| 2 α -2 + 2|C|α -1 λc * bgg.
Thus,

c (2) * = |C|c -1 1 1 -λ bgg |C|α -1 + λ b(2) gg + |C|α -1 λ bgg 1 -λ 2b2 gg .
2 Let φn represent the time at which the server visits the global gate, 0, in the n th cycle. Then Cn = φn -φ n-1 . For any stationary point process, for example in our case {φn}, there will be two associated probabilities: Stationary and Palm Stationary ( [START_REF] Baccelli | Elements of Queueing Theory[END_REF]). In general, {φn} are defined such that φ 0 ≤ 0 < φ 1 . Palm probabilities are the stationary probabilities obtained after conditioning on the event that {φ 0 = 0} (see [START_REF] Baccelli | Elements of Queueing Theory[END_REF]). Throughout the paper, the expectation under Palm stationary measure is represented by E 0 and the corresponding moments are usually denoted with a * as sub-script. In [START_REF] Baccelli | Elements of Queueing Theory[END_REF], the stationary moment of the residual cycle C 1 (which we refer as C R ) as well as the past cycle C 0 (which we refer as C P ) is obtained in terms of Palm probabilities as

E[C R ] = E[C P ] = E 0 [C 2 1 ] 2E 0 [C 1 ]
.

This result is also explicitly derived specifically for cycle times in a special polling system in Section 3.1 of [START_REF] Boxma | Waiting times in polling systems with various service disciplines[END_REF]. This result is used throughout.

Stationary Expected Virtual Workload

An user arriving at q and at an arbitrary time epoch (which is modeled as occurred at time 0) has to wait, for his service to start, on average for a time equal to the sum of three components : 1) the average residual cycle time of the ongoing cycle C R ; 2) the time taken by the server to reach the point q from 0, qα -1 ; 3) the average time taken by the server to attend the users belong to the segment [0, q] that arrived in the entire ongoing cycle C R + C P (C P represents the past cycle time of the ongoing cycle), N (CP +CR) i B i 1 {qi∈[0,q]} . Thus the stationary expected waiting time of a user given that the user arrives at point q equals (see footnote 2),

E[W ](q) = E[C R ] + qα -1 + λP Q (Q ∈ [0, q])E[C R + C P ]E[B|Q ∈ [0, q]] = c (2) * 2c * + qα -1 + λ c
(2) * c * bgg(q) where ( 4) bgg(q) := q 0 bgg(y)P Q (dy).

By Little's law ( [START_REF] Whitt | A review of l = λw and extensions[END_REF]) the stationary expected number of waiting users that belong to infinitesimal segment [qdq, q + dq] equals,

E[N ](dq) = λE[W ](q)P Q (dq)
and thus by Wald's Lemma, the stationary expected virtual workload (by virtue of independence) due to users that belong to infinitesimal segment [qdq, q + dq] equals

Vgg(dq) = bgg(q)λE[W ](q)P Q (dq).
Hence the stationary expected virtual workload in the entire system equals

Vgg = λ |C| 0 E[W ](q)bgg(q)P Q (dq) = λ c (2) * c * bgg 2 + λE[ bgg(Q)bgg(Q)] + α -1 E[Qbgg(Q)] .
By interchanging the order of the two integrals in 3), ( 4) the virtual workload simplifies to:

E[ bgg(Q)bgg(Q)], |C| 0 q ′ 0 bgg(q)P Q (dq)bgg(q ′ )P Q (dq ′ ) = |C| 0 |C| q bgg(q ′ )P Q (dq ′ )bgg(q)P Q (dq) = |C| 0 bgg - q 0 bgg(q ′ )P Q (dq ′ ) bgg(q)P Q (dq) = b2 gg - |C| 0 q 0 bgg(q ′ )P Q (dq ′ )bgg(q)P Q (dq). and so, E[bgg(Q) bgg(Q)] = b2 gg /2. From (
Vgg = λ |C|α -1 (1 + λ bgg) + λ b(2) gg 1 -λ bgg bgg 2 + α -1 E[Qbgg(Q)] . (5)
Symmetric Case: We specialize to the symmetric case where b(q) ≡ b, b (2) (q) ≡ b (2) and P Q (dq) is uniform with

|C| = 1. In this case E[Q bgg(Q)] = b/2 and V sym gg = λ bgg λ b(2) gg 2(1 -λ bgg) + α -1 1 -λ bgg .

Elevator Service

This polling system is similar to that in subsection 2.2 except that the server moves in the opposite direction every time it reaches the point at which the global gate closes.

That is, 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] Altman | On Elevator Polling with Globally Gated Regime[END_REF], authors describe the scheme for discrete polling system. The analysis of the continuous counterpart will be similar to that in 2.2 and we mention only the points of difference. Stationary moments of the Cycle time : The adjacent cycles times can once again be related using

Cn = N (Cn-1) i B n i + |C|α -1 and C n-1 = N (Cn-2) i B n-1 i + |C|α -1 .
Under stationarity Cn will be distributed same as C n-2 and C n-1 as C n-3 . Because of the IID nature of the services times {B n i } across any cycle, for the above relations to hold Cn should be distributed same as C n-1 . Thus again under stationarity,

c * = |C|α -1 1 -λ bgg c (2) * = |C|c -1 1 1 -λ bgg |C|α -1 + λ b(2) gg + |C|α -1 λ bgg 1 -λ 2b2 gg .
Expected waiting time for a random user : Here again the time the user arriving at q has to wait for his service will be equal to the sum of three components as in subsection 2.2 but the server will be moving either in clockwise direction or in anticlockwise direction with half probability. Thus the expected waiting time at any point q equals :

E[W ](q) = E[C R ] + 1 2 (qα -1 + λP Q (Q ∈ [0, q])E[C R + C P ]E[B|Q ∈ [0, q]] ) + 1 2 ((|C|-q)α -1 + λP Q (Q ∈ [q, |C|])E[C R + C P ]E[B|Q ∈ [q, |C|]] ) = c (2) * 2c * + |C|α -1 2 + λ c (2) * 2c * bgg = λ b(2) gg 2(1 -λ bgg) + |C|α -1
which is independent of the position q. As anticipated, the expected waiting times are independent of the position at which the user waits. The stationary expected workload can be derived as before and equals

V elevator = λ bgg λ b(2) gg 2(1 -λ bgg) + |C|α -1 . (6)

Mixed Service

This is a system in which the server attends some of the users with globally gated service and the rest with exhaustive service. For users with globally gated service the server closes the gate when it touches upon 0 and serves in the current cycle only those which arrived before the gate closure as in subsection 2.2. The rest of the users will be served, immediately, as in subsection 2.1. We obtain the stationary expected virtual workload of the mixed system as a limit of the same for a 'certain' set of the discrete polling systems, under an extra assumption: the service times are bounded with probability one by a constant that is less than infinity.

Theorem 1 Assume P Q (dq) = f Q (q)dq, i.e., f Q is the density of P Q .
Assume further that bg, bgg and f Q are continuous. Also, there exists a B < ∞ such that, the service times (irrespective of the position of the arrival) are bounded by B with probability one, i.e., P (B < B) = 1. Then there exists a threshold B (discussed in the proof ) and for all service times with upper bound B ≤ B, the expected stationary virtual workload for the mixed service continuous polling system, V mix , is given by the limit of the corresponding one, V σ mix , for a "certain" discrete polling system with 2σ number of queues3 :

V mix = lim σ→∞ V σ mix = λ b λ b(2) 2(1 -λ b) + pggλα -1 E[Qbgg(Q)] + λ b|C|α -1 2 + λ 2 |C|α -1 2(1 -λ b) b2 + (pgg bgg) 2 + pggpg bgg ¯ bg , (7)
where

|C| = 2πγ, bg(q) := E[bg(Q)1 {Q≤q} ] and ¯ bg := E[ bg(Q)].

⋄

Before we proceed with proving the above theorem we compare the formula (7) with the special cases considered so far. We note that, the general formula (7) matches with (2) of subsection 2.1, when specialized to the symmetric conditions and to the pure gated service (i.e., with pg = 1 = 1pgg). It also matches with with globally gated workload (5) derived in subsection 2.2, when specialized to this pure service (i.e., pg = 0 = 1pgg).

The proof of Theorem 1 is obtained using the following 3 major steps: 1)Discretization: Continuous polling system is converted to an appropriate discrete polling system in subsection 2.4.1, for which the Pseudo conservation laws and hence the expected virtual workload is known (see [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 user classes[END_REF] etc.).

Let δ σ (q) for every point q on C represent the point, in the discrete system with σ discretization levels, standing at which the server attends the possible users of point q. Let δ ∞ represent the same for continuous system. Note that δ ∞ (q) = q for all q, i.e., that δ ∞ is the identity map.

2)Fixed point equations: We express the stationary moments of the time to reach δ σ (q), for every q on the circumference C, starting from 0 (global gate point) as a fixed point (in the space of left continuous and right limit functions) of an affine linear operator in subsection 2.4.2. We obtain a common operator (F defined in subsection 2.4.2), which is further parametrized by a map, δ : [0, |C|] → [0, |C|]. The fixed point of the common operator at δ = δ σ gives the required stationary first moments for the discrete system while that at δ = δ ∞ (the identity map) corresponds to the continuous system. We show the continuity of these fixed points with respect to δ via contraction mapping theorem and hence show that the stationary moments of the discrete system converge to that of the continuous system. We obtain the convergence of second moments using similar but more complicated logic.

3)Alternate expression for Virtual Workload: We express the expected virtual workload in terms of the stationary moments of the step [START_REF] Boxma | Waiting times in polling systems with various service disciplines[END_REF]. Note, that this common expression (given by ( 19) in subsection 2.4.3) cannot be computed easily and is used only for the proof. Using this common expression, we show the convergence of the stationary expected virtual workload of the discrete system to that of the continuous system in subsection 2.4.3.

Discretization

For each integer σ, consider a discrete polling system with 2σ queues, half of which experience globally gated service while the rest half experience gated service. The circumference |C| is divided to σ equal segments {I i } σ i=1 with I 1 = [0, C/σ). All the users arriving in area I i are treated as though arriving in queue numbered 2i -1 (for gated users) or 2i (for globally gated users). Note that the globally gated users are the tagged ones, i.e., the ones that arrived before the server reached 0 in the current cycle. For every i, the server stops upon reaching the starting point, i σ := (i -1)|C|/σ, of I i and serves the users of I i (that arrived/tagged before the server reached the stop i σ ) before moving further. Hence, δ σ (q), the point standing at which the server attends the users at q, equals

δ σ (q) = σ i=1 i σ 1 {q∈Ii} with I i := [i σ , (i + 1) σ ) , i σ := (i-1)|C| σ if σ < ∞ q if σ = ∞. (8)
Within a queue, the server attends the users in a special order which we call as arrival position order. In this special order, the users within a queue are served in the order of their distance from the stop i σ of the server, i.e., the user at minimum distance is served first. So, the users are almost served in the same order as done in a continuous system. The main difference b/w the continuous system and the discretized system is that some of the users are postponed to the next cycle in the discretized system. This is mainly because of the combined effect of discretization and the gated service. But we will see that the effect of the users, whose service is postponed, reduces to zero as σ tends to ∞.

Define the following terms related to each stop and or each queue with obvious meanings as below:

b 2i-1 := E[B|Q ∈ I i , gated] = E[bg (Q)1 {Q∈I i } ] PQ(Ii) b (2) 2i-1 := E[b (2) g (Q)1 {Q∈I i } ] PQ(Ii) b 2i := E[bgg (Q)1 {Q∈I i } ] PQ(Ii) b (2) 2i := E[b (2) gg (Q)1 {Q∈I i } ] PQ(Ii) l i := P Q (I i ) λ 2i-1 := λl i pg λ 2i := λl i pgg ρ i := λ i b i and ρ := 2σ i ρ i .
In the above,

{λ 2i-1 } σ i=1 , {b 2i-1 }, {b (2)
2i-1 } respectively represent the arrival rates, the first and the second moments of the service times at the gated queues while

{λ 2i } σ i=1 , {b 2i }, {b (2)
2i } represent the same for globally gated queues. Factor ρ represents the total work load in the system, note that ρ is same for all σ and equals λ b. The discrete system is stable only when ρ < 1. The continuous system is assumed to be stable and hence the stationary moments of Theorem 2 (given in later subsections) exist and hence by the same theorem ρ < 1. Thus the discrete systems are stable for all σ. Expected Virtual Workload for discretized polling system: This type of a mixed service stable discrete polling system is considered in [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 user classes[END_REF][START_REF] Boxma | Pseudo-Conservation Laws in Cyclic-Service Systems[END_REF]. By Pseudo Conservation Laws of [START_REF] Boxma | Pseudo-Conservation Laws in Cyclic-Service Systems[END_REF][START_REF] Boxma | Workloads and waiting times in single-server systems with multiple user classes[END_REF] the expected stationary virtual workload of the σ-polling model with mixed (globally gated and gated) services is:

V σ mix = ρ σ j=1 λ j b (2) j 2(1 -ρ) + ρs (2)
2s (1) +

s (1) 2(1 -ρ) ρ 2 + σ i=1 ρ 2 i + s (1) 1 -ρ i∈gg ρ i j≤i ρ j + i∈gg ρ i j<i s j .
In the above, s (1) , s (2) represent the first and the second moment of the total walking time, {s i } represent the first moments of the walking times between consecutive queues and the remaining terms have similar definitions as before. The results of [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 user classes[END_REF][START_REF] Boxma | Pseudo-Conservation Laws in Cyclic-Service Systems[END_REF] are valid for any work conserving order at each queue and hence the results are also valid for our arrival position order.

In our case we have a 2σ stable polling system with even numbered queues experiencing the globally gated service and the odd numbered queues experiencing the gated service. Further we have fixed walking times between queues, that between the queues of the same stop is zero, s 2i-1 = 0 and s 2i = |C|α -1 /σ. Thus the expression for expected stationary virtual workload for our discrete polling system is:

V σ mix = ρ 2σ j=1 λj b (2) j 2(1-ρ) + ρ|C|α -1 2 + |C|α -1 2(1-ρ) ρ 2 + 2σ i=1 ρ 2 i + |C|α -1 1-ρ σ i ρ 2i j≤2i ρ j + σ i ρ 2i (i-1)|C|α -1 σ . (9)
We will prove that the limit of the 'discrete' expected stationary virtual workload, V σ mix , indeed equals that of the continuous system. This basically forms the proof of the Theorem 1 and this proof is given in the next two subsections. We conclude this subsection by computing the limit of (9) (proof in Appendix A):

Lemma 1 The limit of V σ mix (9) equals V mix given by ( 7) of Theorem 1.

⋄

Fixed point equations

Let T σ n (q) represent the time to reach the point, δ σ (q) of ( 8), starting from the global point 0, during the n th cycle. Let V σ n ([a, c]) represent the workload present at the be- Tgg([a,c],T ) in case of globally gated system) represent the total workload of the gated (or globally gated) Poisson arrivals that arrived in segment [a, c] ⊂ [0, |C|], such that a user at point q ∈ [a, c] can arrive during a period of time T (q). They are related in a continuous polling system by (i.e., with σ = ∞):

ginning of the n th cycle in the segment [a, c] ⊂ [0, |C|]. Let Tg([a, c], T ) (or
T σ n (q) = qα -1 + V σ n ([0, q)) + Tg([0, q), T σ n ) (10) V σ n ([a, c]) = Tgg([a, c], T σ n-1 (|C|)) + Tg([a, c], T σ n-1 (|C|) -T σ n-1 ). ( 11
)
In the above, the first term of (10) represents the time taken to walk the distance q. The second term, V σ n ([0, q]), represents the time taken to complete service of the globally gated and gated users (placed geographically before q) that arrived before the server reached 0. The third term represents the time taken to complete service of the gated users (placed before q) that arrived during the current cycle, before the server reached their respective δ σ points.

In a discrete polling system, T σ n (q) is the time till the server attends all the users belonging to the line segments placed before the point q, {I j } j<qσ/|C| , and hence is same for all the points of the same line segment and is given by:

T σ n (q) = T σ n (δ σ (q)) = δ σ (q)α -1 + V σ n ([0, δ σ (q)]) + Tg([0, δ σ (q)], T σ n ). ( 12
)
Note that the same equation at δ = δ ∞ matches with the continuous time equation [START_REF] Eliazar | From polling to snowplowing[END_REF]. The equation [START_REF] Fuhrmann | Applications of the decomposition principle in m/g/1 vacation models to two continuum cyclic queueing models[END_REF] remains the same for the discrete system also.

First Moments: By the lemma below, we obtain integral representation of the first moments of the workloads like, Tg([0, q], T σ n ) using which we obtain the integral presentation of the first moments of T σ n (proof in Appendix B).

Lemma 2 Let T : [a, c] → R + be either monotone (increasing or decreasing) or constant nonnegative random function on interval [a, c]. Assume that for any q ∈ [a, c], the service times of the new arrivals and the arrival process at around point q is independent of the system evolution before 4 time T (q). Let T ([a, c], T ) represent the total workload of the Poisson arrivals that arrived in segment [a, c] ⊂ [0, |C|], such that a user at point q ∈ [a, c] can arrive during a period of time T (q). Then with τ (q) := E[T (q)] for any q,

E[T ([a, c], T )] = λ c a b(q)f Q (q)τ (q)dq. ⋄ Let N := {1, 2, • • • , ∞}. Let τ σ n (q) := E[T σ n (q)
] represent the first moment of T σ n (q) when the number of stops equal σ and let τ ∞ n (q) represent the same for continuous system. Substituting [START_REF] Fuhrmann | Applications of the decomposition principle in m/g/1 vacation models to two continuum cyclic queueing models[END_REF] in [START_REF] Georgiadis | Stability of token passing ring[END_REF] and then applying Lemma 2, we get for any n ∈ N:

τ σ n (q) := δ(q)α -1 + δ(q) 0 v σ n (y)dy + λpg δ(q) 0 bg(y)f Q (y)τ σ
n (y)dy where (13)

v σ n (q) := λpggbgg(q)τ σ n-1 (|C|)f Q (q) + λpgbg(q) τ σ n-1 (|C|) -τ σ n-1 (q) f Q (q).
F(τ ; δ)(q) := δ(q)α -1 + λτ (|C|) δ(q)∧|C| 0 b(y)f Q (y)dy for all q ∈ C. ( 14
)
4 Note that this assumption is satisfied by our polling systems (discrete as well as continuous ones) because the system evolution is effected by an arrival only after it is served and here T σ n (q) (for which this lemma would be applied) represents the time instance at which it starts serving the users of the segment in which q resides. Let τ σ * (q), for σ ∈ N, represent the (Palm) stationary moment corresponding to τ σ n (q). By stationarity5 from equation ( 13) the stationary first moments, τ σ * , of the discrete system is a fixed point of the parametrized function F, at δ σ with σ < ∞, while that of the continuous system is fixed point of the same function at δ ∞ . Note here that b(q) = pgbg(q) + pggbgg(q).

We obtain the continuity of the stationary moments τ σ * , in uniform/sup norm, in the following (proof in Appendix B):

Theorem 2 Assume bg, bgg, f Q are continuous in q. For any δ ∈ D the map F has an unique fixed point, τ δ * , if and only if ρ < 1. Further these fixed points are continuous in supremum norm w.r.t. to parameter δ. From this continuity we get that, τ σ * = τ δ σ * , the stationary moments corresponding to discrete system with σ stops, converge to that of the continuous system as σ increases to infinity:

sup q∈C |τ σ * (q) -τ ∞ * (q)| → 0.
Indeed:

τ δ * (|C|) = δ(|C|)α -1 1 -ρ(δ(|C|) ∧ |C|)
and

τ δ * (q) = δ(q)α -1 + τ δ * (|C|) ρ(δ(q) ∧ |C|) for all q where ρ(q) := λ q 0 b(y)f Q (y)dy. ⋄
Second Moments: Let C σ n (q) represent the time taken between the n th and n -1 th visit of the point q (δ σ (q) in case of discrete systems), i.e., the cycle time w.r.t. to the point q. Note that

C σ n (q) = T σ n (q) + (T σ n-1 (|C|) -T σ n-1 (q)). (15)
These cycle times are the most important quantities required for further analysis and in this subsection we study its moments. We obtain the convergence of stationary second moments corresponding to C σ n (q) as σ → ∞. Let c 2σ * (q) represent the (Palm) stationary moments corresponding to E[C σ n (q) 2 ]. We obtain their convergence and the exact result is given in the following theorem (proof in Appendix B):

Theorem 3 Assume bg, bgg, f Q are continuous. Then there exists a threshold B on the workload threshold B, i.e., for service time requirements satisfying B ≤ B with probability one, as σ → ∞ the stationary second moments converge uniformly:

sup q∈[0,|C|] c (2σ) * (q) -c (2∞) * (q) → 0. ⋄ 2.

Proof of Theorem 1

By Theorems 2 and 3, the first stationary moments of T σ n and the second order stationary moments of C σ n , of the discretized polling system, converge towards the corresponding ones of the continuous polling system. The convergence is in supremum norm, i.e., uniformly of the positions q on the circle. We obtain the expression for the expected virtual workload using these moments for both the discrete and continuous polling systems and then using the convergence results of the Theorems 2 and 3 we complete the proof of Theorem 1.

The first two (Palm) stationary moments E 0 [C σ n (q)] and E 0 (C σ n (q)) 2 of C σ n defined in [START_REF] Kroese | Light-traffic analysis for queues with spatially distributed arrivals[END_REF] are:

c σ * (q) = E 0 [C σ n (q)] = τ σ * (|C|), c (2σ) * (q) = E 0 C σ n (q) 2 .
Convergence of τ σ * (|C|) is obtained in Theorem 2 while that of c (2σ) * is obtained in Theorem 3. Thus the stationary first moment of the residual of the cycle C σ n (q) as seen by a random user in terms of the two Palm moments is given by (see footnote 2),

E[C σ R (q)] = E 0 (C σ n (q)) 2 2 (E 0 [C σ n (q)]) 2 = c (2σ) * (q) 2 (τ σ * (|C|)) 2 . ( 16
)
Workload due to Globally Gated users: A randomly arriving globally gated user, arriving at point q, will have to wait on average for a sum of the following three: 1) the residual of the current cycle (w.r.t. to the globally gated point 0), E[C σ R (|C|)]; 2) τ σ * (q), average time taken by the server to travel from 0 to δ σ (q); 3) in a discretized system the user has to wait an extra amount of time to complete service of6 : a) the other globally gated users in [δ σ (q), q) (that would be served before him while the server is standing at δ σ (q)) and b) the service of all the gated users belonging to the same segment [δ σ (q), δ σ (q) + |C|/σ], which by Lemma 2 equals: Thus the expected waiting time of such a user for any σ ∈ N is

E Tg δ σ (q), δ σ (q) + |C| σ , C σ n + E Tgg δ σ (q), q , T σ n-1 (|C|) = τ σ * (|C|) ρg δ σ (q), δ σ (q) + |C| σ + ρgg δ σ (q),
E[W σ gg ](q) = E[C σ R (|C|)] + τ σ * (q) (17)
+1 {σ<∞} τ σ * (|C|) ρg δ σ (q), δ σ (q) + |C| σ + ρgg δ σ (q), q .

Hence, by Little's law ( [START_REF] Whitt | A review of l = λw and extensions[END_REF]) the density of the stationary number of waiting globally gated users is λpggf Q (q)E[W σ gg ](q) and by Wald's lemma the density of the expected stationary workload corresponding to globally gated users is

λpggf Q (q)E[W σ gg ](q)bgg(q).
Workload due to Gated users: A randomly arriving gated user, arriving at q, has to wait on average for: 1) residual of his own cycle , E[C σ R (q)];

2) in case of the discretized system till the users placed geographically above him are served which equals (by calculating as done for a globally gated user) τ σ * (|C|)ρg (δ σ (q), q). Therefore the expected waiting time of a gated user is:

E[W σ g ](q) = E[C σ R (q)] + 1 {σ<∞} τ σ * (|C|)ρg δ σ (q), q . (18)
Thus by Little's law ( [START_REF] Whitt | A review of l = λw and extensions[END_REF]) and Wald's lemma the expected stationary workload due to gated users is:

|C| 0 λpgf Q (q)E[W σ g ](q)bg(q)dq.
Total expected stationary virtual workload: Therefore, the total expected stationary virtual workload is given by:

V σ = λ |C| 0 ( τ σ * (q) + E[C σ R (|C|)] bgg(q)pgg + E[C σ R (q)]bg(q)pg) f Q (q)dq +1 {σ<∞} λτ σ * (|C|) |C| 0 νqf Q (q)dq with (19)
νq := ρg δ σ (q), q pgbg(q) + ρg δ σ (q), δ σ (q) + |C| σ + ρgg δ σ (q), q pggbgg(q).

In the above V ∞ represents the expected virtual workload of the random user for the continuous system while V σ with σ < ∞ represents the same for a discrete system. By the Theorems 2 and 3 the terms inside the first integral of [START_REF] Altman | On Elevator Polling with Globally Gated Regime[END_REF] (see also the equations ( 16), ( 17) and ( 18)), defining the expected virtual workload, converge towards that of the continuous polling system point-wise and uniformly in q. Terms inside the second integral, νq, converge to zero point-wise and uniformly in q as σ → ∞:

sup q∈C νq ≤ λ p 2 g ||bg || 2 ∞ + pggpg||bg||∞||bgg ||∞ + p 2 gg ||bgg|| 2 ∞ ||f Q ||∞ |C| σ .
Thus by bounded convergence theorem, the expected stationary virtual workload of the discretized polling system converges towards that of the continuous polling system as σ → ∞.

Thus the limit of the discrete stationary expected virtual workload, V σ mix of (9), given by [START_REF] Coffman | A continuous polling system with constant service times[END_REF] represents the the expected stationary virtual workload corresponding to the continuous system. This completes the proof of Theorem 1.

⋄

In the coming sections, we analyze an FWLAN using the results of this section.

Ferry Based Wireless Local Area Network (FWLAN)

Static users are scattered in a geographical area ∆. The network is sparse, there is no direct global connectivity and a message ferry facilitates the basic communication. FWLAN can operate in various architectures (in [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF] various architectures are discussed) and we consider here a basic architecture, referred as Sensor Area Network (SAN) in [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF]. This configuration 7 supports only data transfer between the users of the area and the outer world via a static gateway, base station (BS). The data transfer from the users of the area to the outer world is called uplink, while that from the outside world to the users of ∆ is called downlink. Every cycle begins at the BS where: 1) it dumps to BS the uplink data, collected from the users of LAN in the previous cycle ; 2) collects the downlink data from BS, to transfer in the ongoing cycle to the destined users (when it reaches a point on its path near the intended user).

The ferry "serves" the users: by "serves" a message we mean that the ferry transmits it if the connection is downlink (i.e. the message is destined to a user), 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 α. It stops as and when it encounters an user with a request. Every time it stops and restarts it spends an extra time ta for acceleration. The shuttle continues with its journey after serving the encountered user. Each point in the cyclic path is a potential stop and every stop q in the path is assigned with a set of points I(q) ⊂ ∆. These sets are assigned based on nearest point basis.

Arrival process: Uplink/Downlink traffic arrives according to an independent marked point processes {Tn, Mn}, where Tn is the arrival time of the nth point and Mn = [Xn, ηn] are the corresponding i.i.d. marks:

-Tn is a Poisson point process with parameter λ, -Xn is the location of an arrival. It's distribution is given by P X .

ηn is the size of the message. Its distribution can depend upon X the position of arrival and also on whether it is a uplink or a downlink arrival . It is finite with probability one and its first and second moments (conditioned on the arrival being at point x and further for uplink and downlink arrivals) are given by

η u b (x), η d b (x), η (2u) b (x), η (2d) b (x).
These arrivals8 can be uplink, downlink with probabilities p d , pu = 1p d respectively.

That is, an uplink request arrives at rate λ u := puλ while the downlink at rate λ d := p d λ.

We use the following notations. The points in the two dimensional 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. We shall use the superscript u or d to denote uplink or downlink.

Radio channel and service time: The Ferry uses a wireless link to serve the users. It can receive/transmit the messages from/to the users at a distance of d from it at a rate κ(d) for some decreasing function κ(.). Thus the total time required for transmitting a 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:

B(x) = η κ(||q(x) -x||) .
The point x ∈ ∆ is mostly associated with the closest point on the circular path C, i.e., q(x) := arg min q∈C ||q -x||, with ||.|| representing the Euclidean distance.

The ferry standing at q ∈ C has to serve all the users arriving in I(q). Thus the first two moments of the overall time required for uplink service at a point q ∈ C, bu(q) and b

(2) u (q) are given by ( for all q ∈ C):

bu(q) := E [B(X)|X ∈ I(q), uplink ] , b (2)
u (q) := E B(X) 2 |X ∈ I(q), uplink .

The corresponding for downlink, b d (q) and b

(2) d (q), can be defined in a similar way. Pareto Optimality: All the users are served as the ferry moves on C. Any arrival at a point x ∈ I(q) ⊂ ∆ has to wait for time W (q) and the stationary 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 a given class of trajectories) which minimizes integral of the weighted expected waiting times at all the points in the cyclic path C, as this would give a Pareto optimal solution (see definition of Pareto optimality and other details in Appendix C). Towards this we consider the problem of minimizing

|C| 0 E[W ](q)ζ(q)dq
where ζ(q) is a positive weight.

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 waiting users (by Little's Theorem). If we further multiply the integrand at each point q by the expected service time at that point then we obtain the total expected virtual workload in the system. In this paper the objective function to be minimized will always be the expected virtual workload (which is obtained in section 2 as Theorem 1) and a ferry path which minimized the expected virtual workload is a Pareto optimal path for the multi-objective problem where the expected waiting times at different locations are to be minimized.

Optimizers: We discuss design of optimal ferry paths C and optimal partitioning of the area into line segments {Iq; q ∈ C}. The aim of this subsection is to obtain these objects in an optimal way that minimizes the virtual workload. 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 system, so that Theorem 1 can be used. This task is taken up immediately.

Mapping to a Mixed service Continuous polling system

We begin with identifying the components of the continuous polling system.

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 a (downlink/uplink) request anywhere on the segment I(q). Thus the entire segment I(q) is modeled as a point on the server's path, in an equivalent continuous polling system.

Service times: The time ta 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 the corresponding segment, i.e., if X ∈ I(q). Thus service time of an arrival (η, X) is given by :

B(X, η) = η κ(|X -q(X)|) + ta.
The expected service times (and the corresponding second moment), for example, for uplink arrivals corresponding to a point

q ∈ C is bu(q) = E[B(X, η)|q(X) = q] = E X η κ(|q -X|) X ∈ I(q), uplink + ta. b (2)
u (q) = E[B(X, η) 2 |q(X) = q] = E X η 2 κ(|q -X|) 2 X ∈ I(q), uplink -t 2 a + 2tabu(q).
Service types: Ferry collects all the downlink messages from the BS and distributes the same in the current cycle. Thus the downlink arrivals experience globally gated service, with BS being the global gate point, 0. On the other hand, the ferry collects uplink data from the users as and when it encounters one on its path. Thus the uplink arrivals experience exhaustive/gated service and therefore pgg = p d , pg = pu.

Position of arrival in the 'polling system' : The position of arrival in FWLAN is given by P X which is a distribution over ∆. Every arrival in the segment 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 1, P X ∼ U(∆) (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.

∆ := {x ∈ R 2 : h 2 1 ≤ |x| ≤ h 2 2 }, C = {q : ||q|| = l} for some h 1 ≤ l ≤ h 2 as in Figure
Thus the FWLAN can be modeled by a mixed service continuous polling system, Theorem 1 can be applied and the stationary expected virtual workload of the ferry with combined uplink and downlink arrivals can be calculated using [START_REF] Coffman | A continuous polling system with constant service times[END_REF] for any given cyclic path C and the corresponding line segments {Iq} q∈C . The Theorem can be applied only for those cases which satisfy the hypothesis of the Theorem, like for example the service times should be bounded with probability one by B of Theorem 1. The service times will be bounded as required if: 1) the function κ is continuous in d (which usually is the case) and hence its image of a bounded set will be bounded; 2) we will need P (η < η) = 1 with an η that satisfies, η/ min κ(d) + ta ≤ B of Theorem 1.

In the following subsections, we design optimal FWLAN for a simple example. The ferry moves inside an annular ring 1 and2. 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 3.2) or is computed in some optimal sense (in subsection 3.3). In subsection 3.3, we consider N circular paths with N ferries each moving in its own circular path. All the paths are optimized jointly so as to further obtain the segments {I(q)} optimally.

∆ := {x ∈ R 2 : h 2 1 ≤ |x| ≤ h 2 2 } of Figures

SAN-TAXI example 1: 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, 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∈C l |q -X| of ferry route. Hence the line segments will be angular segments, I(q) = {x ∈ ∆ : (x) = (q)} for all q ∈ C l , (see figure 1). We would now like to find the optimal radius of this circle. The variable to be optimized, the radius, takes any value in [h 1 , h 2 ] and we are interested in

l * = arg min l∈[h1,h2] V 1 SAN -T AXI (l; h 1 , h 2 ) where V 1 SAN -T AXI (l; h 1 , h 2 )
represents the stationary expected workload in FWLAN when ferry moves in C l , which can be computed using [START_REF] Coffman | A continuous polling system with constant service times[END_REF]. To simplify the computations, in this section, we restrict ourselves to symmetric conditions, i.e., -uniform arrivals in annular area, P X ∼ U(∆), -the rate function resulting from the losses in wireless medium considers only the direct path for attenuation (assuming a height difference of 1 unit between the transmitting and the receiving antennae and with path loss factor β):

κ(d) = (1 + d 2 ) -β/2 ,
the distribution of η is independent of the location of arrival and the type of arrival (uplink or downlink) with

E[η|X] ≡ η b and E[η 2 |X] ≡ η (2) b
and such that P (η < η) = 1 with an η/κ(dmax) + ta < B, where dmax := (h 2h 1 )/2, -The uplink and downlink arrivals occur with equal probabilities pggs = pgs = 1/2. We note that the hypothesis of the Theorem 1 are satisfied under the symmetric conditions. 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∈C l one will require the radius R = ||X|| of the arrival. Under the assumptions of this section, radius R is distributed as R ∼ 2rdr/(h 2 2h 2 1 ) 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:

b l = b(q; l) = η b h2 h1 1 + (r -l) 2 β/2 2rdr h 2 2 -h 2 1 + ta, b (2) l
= b (2) (q; l) = η (2) b h2 h1 1 + (r -l) 2 β 2rdr h 2 2 -h 2 1 -t 2 a + 2tab l for all q ∈ C l .
For example for β = 2 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 ) + ta 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 )) -t 2 a + 2tab l .
Under the simplified assumptions of this section the stationary expected workload for this example can be calculated using (7) 9 :

V 1 SAN -T AXI (l; h 1 , h 2 ) = λb l λb (2) l 2(1 -λb l ) + λb l |C l |α -1 (12 -λb l ) 16(1 -λb l ) . (20)
One has to perform numerical computations using the above formula to obtain the optimal radius and this is done below. However one can get the following asymptotic characteristics of l * from the formula itself: 1) as the propagation coefficient β tends to zero, both the service moments b l and b

(2) l become independent of l, stationary expected workload essentially depends upon l only via |C l | and hence l * tends to h 1 , i.e., the optimal path for the ferry is the inner circle; 2) as the speed of the ferry, α, increases to infinity, the second term in the formula becomes negligible and hence optimal radius will be determined only by the service time moments and so the optimal radius will be above the middle of the ring, i.e., larger than (h 1 + h 2 )/2. Mixed (Uplink+Downlink) service 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 we 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 | Stability, Monotonicity and Invariant Quantities in General Polling Systems[END_REF]. Hence in these scenarios one can obtain the optimal radius as (for β = 2)

l * ≈ 2(h 2 1 + h 2 2 + h 1 h 2 ) 3(h 1 + h 2 )
. 9 The equation below is different from the one in [START_REF] Kavitha | Analysis and design of message ferry routes in sensor networks using polling models[END_REF], because of the correction in [START_REF] Coffman | A continuous polling system with constant service times[END_REF].

α = 1 α = 10 α = 50 t a = 1 h 1 = 0.1 β = 2 η b = 1 η b (2) = 1.1 λ = 1e -6 (h 2 2 -h 1 2 ) h 2
Fig. 3 Optimal orbit radius for a ferry moving continuously in a annular ring (Uplink and Downlink)

3.3 SAN-TAXI example 2: N servers moving simultaneously in the annular area

When the annular ring spans over a large area, a 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 α 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 ferry communicates with the BS instantaneously the moment it touches the angle 0. Throughout this paper we are neglecting the time taken for communication (e.g., the communication happens at high speed using a wired link) between the BS and the ferry(ies). Let Cn := {q : ||q|| = ln} and let B(x, p) := {y : ||y -x|| < p} represent the open ball, while B(x, p) represent its closure. The first ferry caters to 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, pn) -B(0, p n-1 ). Let p 0 := h 1 and p N := h 2 . In this subsection we choose optimally p :=

[p 1 , p 2 , • • • , p N -1 ] T and l := [l 1 , l 2 , • • • , l N ]
T , which in turn optimally defines the line segments {In(q); q ∈ Cn, for all n} as

In(q) = x ∈ B(0, pn) -B(0, p n-1 ) : q = x .

We map each ferry by a separate continuous polling system. With these, the moments of the overall service times for the n th ferry is

b n,p,l = η b pn pn-1 1 + (r -l) 2 β/2 2rdr p 2 n -p 2 n-1 + ta and b (2) n,p,l = η (2) b pn pn-1 1 + (r -l) 2 β 2rdr p 2 n -p 2 n-1 -t 2 a + 2tab n,p,l .
Using these moments one can estimate {V 1 SAN -T AXI (ln; p n-1 , pn)}, the N virtual workloads as a function of the vectors p, l. We now propose to choose the optimal ferry paths (and line segments {I(q)}) by :

(p * , l * ) = arg min p,l N n=1 p 2 n -p 2 n-1 h 2 2 -h 2 1 V 1 SAN -T AXI (ln; p n-1 , pn).
In the following we consider an example with 2 ferries moving in the annular area and supporting mixed service. The results are in Table 1. We obtain the optimal l * , p * for different values of the outer radius h 2 and the common speed of the ferries α 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, h 2 , decreases. This effect is also seen in the case of single server and can be partially explained using the expression V SAN -T AXI [START_REF] Altman | Stability, Monotonicity and Invariant Quantities in General Polling Systems[END_REF] for the virtual workload:

-V SAN -T AXI depends upon the radius l via the moments of the effective service times b (1) , b (2) and the circumference |C|. Virtual workload V SAN -T AXI [START_REF] Altman | Stability, Monotonicity and Invariant Quantities in General Polling Systems[END_REF] 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 (optimal for the service moments) will be above the center of the annular ring for practical path loss factors. 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 α, the influence of |C| on V SAN -T AXI reduces and hence the optimal radii will be above the center of the annular ring.

-For smaller values of speed α, we see the reverse effect.

-The area of the annular ring also influences, with larger areas the moments (especially the second) will be large and hence the influence of the moments on V SAN -T AXI will be larger than that of the circumference |C|. And so, we see from the bottom rows of the table that, the optimal radii are away from the inner circle even for lower speeds.

FWLAN with two base stations

We now consider a LAN equipped with two base stations and a moving ferry. 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. 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). This polling system will have 'fair' behavior : the expected waiting times at all the points in the server route will be equal irrespective of whether the arrivals are symmetric or non symmetric. 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 the subsection 2.3 we derived the expression for the stationary expected waiting time in a continuous polling system with elevator gating. These results are applied to some interesting FWLAN examples with two base stations in the following.

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 on the left, tags the users for whom the downlink data has to be distributed, moves towards right with speed α, distributes the data to all the tagged users. Once reaching the BS on the right it collects all the data from the BS and then moves left. This procedure repeats. We analyze this FWLAN using the elevator polling system of subsection 2.3.

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 Cp = {(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 segment. We make simplifying assumptions as in section 3. Under these assumptions

b(q; p) =      η b d -d (1 + y 2 ) β/2 dy 2d + ta p 1 < q < p 2 η b p1 -l d -d (1 + y 2 + (p 1 -x) 2 ) β/2 dxdy 4ld + ta q = p 1 η b l p2 d -d (1 + y 2 + (p 2 -x) 2 ) β/2 dxdy 4ld + ta q = p 2 , b (2) (q; p) -2b(q; p)ta + t 2 a =      η (2) b d -d (1 + y 2 ) β dy 2d p 1 < q < p 2 η (2) b p1 -l d -d (1 + y 2 + (p 1 -x) 2 ) β dxdy 4ld q = p 1 η (2) b l p2 d -d (1 + y 2 + (p 2 -x) 2 ) β dxdy 4ld q = p 2 .
Note here that even under symmetric assumptions the overall 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,

bp = 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 greater than p 1 . As the expected weighting times in this case are equal at all the points, it will be Pareto optimal to optimize the expected weighting times themselves. 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 α -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 : (1) As the speed of the ferry α 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 substantially 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 any 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 placed at (p 1 , p 2 ) and (p 3 , p 4 ). We study continuous polling systems that cater to non-standard variants of gating disciplines like, globally gated service, gated service, mixed service (a mixture of globally gated and gated service disciplines) and elevator service disciplines. We obtain an expression for the expected stationary workload. We obtain this result under more general conditions than the usual symmetric conditions. We come up with a way of discretization such that the available Pseudo conservation laws of discrete polling systems can be utilized for obtaining the results for the continuous counterparts. We expressed the expected workload as a parametrized function of moment fixed points. The later are some stationary moments obtained as fixed points of a function defined on spaces of left continuous functions with right limits equipped with supremum norm and which are further parametrized by the number of discretization levels. We show the required convergence via the continuous dependence of the fixed points on the parameter. This way we obtained a common expression, which represents the expected virtual workload for continuous as well as the discretized polling systems, at different values of the parameter. We then showed the continuity of the expected virtual workload with respect to the parameter and hence obtained the expected virtual workload for the continuous system as the limit of the expected virtual workloads of the discrete systems, when the levels of discretization tend to infinity. We applied these results to a wireless LAN in which a ferry assists data transfer between the users of the network and a base station which acts as a gateway to the external world. We provided the analytical expressions for the expected virtual workload in a system of FWLAN, taking into account the radio channel considerations, which allowed us to optimize the trajectories of the Ferry. We covered both uplink, downlink as well as their combination. Minimizing the virtual workload results in a Pareto minimization of the expected waiting times in the system. We have further presented some extensions to the case of several base stations and to routing of 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 [START_REF] Kavitha | Continuous Polling with Rerouting and Applications to Ferry Assisted Wireless LANs[END_REF], using similar approach we analyzed an FWLAN, in which the ferry also supports local communication. This FWLAN is analyzed using a continuous polling system with rerouting, whose performance is once again obtained using the discretization approach. One can further explore this discretization approach. Recall i σ = (i -1)|C|/σ, note δ σ (q) = i σ when q ∈ I i and with these,

σ i ρ 2i (i -1)|C|α -1 σ = λpggα -1 σ i E bgg(Q)1 {Q∈Ii} i σ = λpggα -1 σ i bgg(i σ )f Q (i σ ) |C| σ i σ (22)
+λpggα -1 |C| 0 bgg(q)f Q (q)bgg(δ σ (q))f Q (δ σ (q)) δ σ (q)dq ( 23)

σ→∞ → λpggα -1 σ 0 qbgg(q)f Q (q)dq = λpggα -1 E[Qbgg(Q)]. (24)
The term ( 22) is a Riemann sum and hence converges to the integral (24) while the second term [START_REF]Umassdieselnet[END_REF] converges to zero by continuity of the functions bgg, f Q via Bounded Convergence Theorem (BCT). Similarly, excluding the terms which converge to zero by BCT as in ( 23),

2σ i=1 ρ 2 i ≈ λ|C| σ σ i=1 pgb 2 g (i σ ) + pggb 2 gg (i σ ) f 2 Q (i σ ) |C| σ → 0 σ 0 pggb 2 gg (q) + pgb 2 g (q) f 2 Q (q)dq = 0. (25)
Following similar logic, with bg(q) := E[bg(Q)1 {Q≤q} ]) and from (21):

By independence E[bgg(Q) bg(Q)] = bgg ¯ bg and hence from limits ( 21)-( 26), the limit of V σ mix (9) matches with the formula (7) of the Theorem 1. Let {B i } i≤N represent the service times of these N arrivals. Any arrival can fall in point q according to distribution P Q (dq) = f Q (q)dq and the conditional expected service time of the arrival conditioned on the point of arrival is b(q) and so,

E[B i |Arrival in[a, c]] = 1 P Q ([a, c]) c a b(q)f Q (q)dq
Thus by Wald's lemma 10 ,

E[T ([a, c], T )] = E N i=1 B i =E[N ]E[B i ] = λτ c a b(q)f Q (q)dq. ( 27
)
Now we consider the other case, i.e., let every sample path of the the random function T be a monotone increasing function of q ∈ [a, c]. The proof for T , monotone decreasing, follows in similar lines. For every M , define step function,

δ M (q) = a + i M if q ∈ a + i M , i + 1 M .
Note that by monotonicity of T , T M (q) := T δ M (q) ≤ T (q) and T M (q) := T δ M (q) + 1 M ≥ T (q).

In the following the arrivals and their service times are independent 11 of T , T M and T M . More arrivals can occur during more time and hence workload during larger time will be larger. Hence and further using ( 27) f Q (q)b(q)dq 10 For applying Wald's lemma we need certain independence assumptions. These assumptions are satisfied in this proof (whenever Wald's lemma is applied) because of the following: the service times (and the number) of incoming arrivals are independent of the system evolution till the time stamp at which they are served. For example, the number of arrivals (or those tagged in case of globally gated service) at around a point say q (i.e., the users awaiting service in segment [q, q + dq]) does not influence the system evolution till the server reaches point δ σ (q), standing at which it would serve the awaiting users, i.e., till time T σ n (q). To put it the other way, for example, T σ n (q) is a stopping time for that sampled arrival process (sampled from the original gated Poisson arrival process), in which the users land in segment [q, q + dq] and which originated during the time interval C σ n (q). 11 The independence assumption holds for lower bound T M and the actual time T readily because of the reasons given in footnote 10. An upper bound is obtained by calculating the independent arrivals that would have arrived in a bigger interval i.e., T M .

E

≤ λ

M-1 i=0 f Q a + i M b a + i M τ a + i M 1 M +λ c a τ δ M (q) f Q (q)b(q) -b δ M (q) f Q δ M (q) dq → λ c a
f Q (q)τ (q)b(q)dq as M → ∞.

The last limit is obtained because the partial sums define Riemann sums and they converge to the integral and because the second integral goes to zero by uniform continuity of b, f Q functions (continuous function on compact intervals are uniformly continuous).

Similarly using the lower bound on the time T , T M , we get,

E [T ([a, c], T )] ≥ lim M→∞ E T ([a, c], T M ) = λ c a f Q (q)τ (q)b(q)dq. ( 28
)
Hence,

E [T ([a, c], T )] = λ c a
f Q (q)τ (q)b(q)dq.

⋄

Proof of Theorem 2: The operator F given by ( 14) is reproduced here.

F(τ ; δ)(q) := δ(q)α -1 + λτ (|C|)

δ(q)∧|C| 0 b(y)f Q (y)dy
We are interested in it's fixed point. The function is clearly jointly continuous in τ, δ. Further, F(τ 1 ; δ)(q) -F(τ 2 ; δ)(q) = λ (τ 1 (|C|)τ 2 (|C|))

δ(q)∧|C| 0 b(y)f Q (y)dy.

Thus for all δ ||F(τ 1 ; δ) -F(τ 2 ; δ)||∞ ≤ ρ||τ 1τ 2 ||∞.

Thus whenever ρ < 1, we have a fixed point of the operator F for all δ and hence the existence of unique stationary first moments. Under this condition, we further see by parametrized contraction mapping theorem ( [START_REF] Berger | Nonlinearity and Functional Analysis[END_REF]) that the unique fixed point τ δ * is continuous in δ.

In fact from equation [START_REF] Kroese | Single-server queues with spatially distributed arrivals[END_REF], when evaluated at q = |C|, we find that: ⋄

τ δ * (|C|) = δ(q)α -1

( 2 )

 2 gg (q) represent same quantities for a globally gated user. Let b := E[b(Q)], bgg := E[bgg(Q)] and bg := E[bg(Q)] (expectations are with respect to 1 P Q ) represent the unconditional moments. Note that b = bgpg + bggpgg. Similarly define the second moments, b

Let

  D represent the space of left continuous functions with right limits on [0, |C|] equipped with supremum norm: for any τ ∈ D, ||τ ||∞ := sup q∈[0,|C|] |τ (q)|. Consider a parametrized function F : D × D → D defined point-wise as below:

  q with ρm(a, c) := λpm c a bm(y)f Q (y)dy for m = g or gg.

Fig. 1

 1 Fig. 1 One Ferry in an annular ring Fig. 2 Two Ferries in an annular ring

= 4 . 4 ,

 44 λ = 1e -2

Fig. 4 5

 45 Fig. 4 One Ferry in Rectangular area with two base stations Fig. 5 More general paths for the ferry with two base stations

9 )Proof of Lemma 1 :ρ

 91 Appendix A: Limit of the Virtual Workload, V σ mix (Some terms of (9) are independent of σ: 2i = λpggE[B|globally gated] = λpgg bgg.[START_REF] Altman | Queueing in space[END_REF]

  ) 2 + pggpgE bgg(Q) bg(Q)

2 :

 2 Let T (q) ≡ T , with E[T ] = τ . In this case, T ([a, c], T ) is sum of the service times of all the arrivals in the interval [0, T ] that occurred in the segment [a, c] ⊂ [0, |C|]. Let N represent the number of those Poisson arrivals that belong to segment [a, c] and that arrived during the [0, T ] interval. In this case,E[N ] = E[E[N |T ]] = λP Q ([a, c])E[T ] = λτ c a f Q (q)dq.

  [T ([a, c], T )] ≤ E T ([a, c], T M )

  )f Q (y)dy = λ |C| 0 b(y)f Q (y)dy = ρand thus the stationary moments exist if and only if ρ < 1. Under this condition, one can solve the fixed point equation and complete the proof of Theorem 2.

Table 1

 1 Example : 2 Ferries moving in annular area with β = 2 h 1 = 5, ta = 10, η b = 2, η

		α = 100	α = 10	α = 1
	h 2 10	(l * 1 , p * , l * 2 ) 6.3, 7.7, 8.8	(l * 1 , p * , l * 2 ) 6.1, 7.7, 8.6	(l * 1 , p * , l * 2 ) 6, 7.8, 8.6
	15	7.9, 10.4, 12.7	7.8, 10.6, 12.7	7.8, 10.8, 12.8
	20	9.5, 13.1, 16.7	9.6, 13.5, 16.8	9.6, 13.8, 16.9
	25	11.1, 15.8, 20.6	11.3, 16.3, 20.8	11.4, 16.7, 20.9
	30	12.8, 18.5, 24.6	13, 19, 24.7	13.2, 19.5, 24.9
	35	14.4, 21.1, 28.5	14.6, 21.5, 28.6	14.9, 22.1, 28.8

The formula[START_REF] Coffman | A continuous polling system with constant service times[END_REF] was conjectured in[START_REF] Kavitha | Analysis and design of message ferry routes in sensor networks using polling models[END_REF] itself. However its proof is derived in this paper. Further, we note that there is a small error in the formula published in[START_REF] Kavitha | Analysis and design of message ferry routes in sensor networks using polling models[END_REF] (in the last term ¯ bg is wrongly misplaced with bg) and is corrected here.

In Palm stationary regime, τ σ n are same for all n, the common values are represented by τ σ * and hence we get a fixed point operator, F , to represent equation[START_REF] Kroese | Queueing systems on the circle[END_REF].

see arrival position order discussed in subsection 2.4.1 and further note that the gated users are served before the globally gated ones.

In a more complicated architecture (referred as Autonomous Network, AUN, in[START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF]), wherein the ferry also supports the local communication, i.e., the data transfers between users of ∆, is analyzed using continuous polling systems with rerouting in our paper[START_REF] Kavitha | Continuous Polling with Rerouting and Applications to Ferry Assisted Wireless LANs[END_REF].

The analysis of subsection 2.4 requires that at any time there can be at maximum one user waiting at a point. The examples considered in this section satisfy this assumption because of two reasons: i) P X is continuous, ii) The paths considered are sufficiently smooth and hence iii) we will have (will be seen in the coming paragraphs) a P Q that would be continuous.

Acknowledgments

The reviewers have pointed out a gap in the proof of Theorem 3 (of the revision 1) and we corrected the same in the final manuscript. We are thankful to the reviewers for pointing out the gap and allowing us to correct the same.

This work was sponsored by The Indo-French Center for the Promotion of Advanced Research under CEFIPRA Project# 4000-IT-1

Proof of Theorem 3: The cycle time C σ n defined in [START_REF] Kroese | Light-traffic analysis for queues with spatially distributed arrivals[END_REF] can be rewritten in the following fashion and via this expression we obtain the convergence of the required second moments (note C σ n (0) = C σ n-1 (|C|) almost surely by continuity arguments):

C σ n (q) = |C|α -1 + U σ n (q) + Tg([0, δ σ (q)), C σ n ) + Tgg ([0, δ σ (q)), C σ n (0)) (

U σ n (q) = Tgg([δ σ (q), |C|), C σ n-1 (0)) + Tg([δ σ (q), |C|), C σ n-1 )). [START_REF] Kavitha | Queueing in Space: design of Message Ferry Routes in static adhoc networks[END_REF] Required Spaces: We first identify appropriate complete metric spaces in which the above quantities reside and whose norm gives the required convergence. We start with some definitions/notations. Let (Ω, F, P ) be any probability space. Let ||.|| 2 be the L 2 norm, i.e., ||ψ|| 2 := E[ψ 2 ] for any random variable ψ. Let D represent the space of left continuous functions on [0, |C|] with right limits and equipped with supremum norm, ||f ||∞ := sup q∈[0,|C|] |f (q)|.

Let

Define the following norm on this space:

||ψ(q, .)|| 2 for any ψ ∈ Ψ .

By Lemma 3 (Ψ, ||.|| ∞,2 ) is a Banach space. Contraction Mappings and fixed points: It is easy to see that (C σ n , U σ n ) defined in ( 29)-(30) reside 12 in Ψ for all σ. It is also easy to see that these under stationarity form the fixed point of the following function, defined point-wise (i.e., for every q) by:

In the above, Tm([a, c], ψ) (with m = g or gg) represents the sum of the modified service times, B, of the users that arrived in the interval [a, c]: 1) arrivals at around q (independent arrivals as explained in footnote 10) occur for time period |ψ(q, .)| as in subsection 2.4.2 and 2) if ψ(q, .) is negative then the quantities added, B, are negative of the service times, else B are the service times themselves. Let Θ := (Θ C , Θ U ). The function Θ : Ψ 2 → Ψ 2 is affine linear (linear but for |C|α -1 term). Let Θ Lin represent the linear part. With this,

12 C σ n is a sum of two monotone functions (recall from equation [START_REF] Kroese | Light-traffic analysis for queues with spatially distributed arrivals[END_REF], Cn(q) = Tn(q) + [T n-1 |C| -T n-1 (q)]) while U σ n is a monotone function of q for all realizations, hence their moments will also have similar properties and hence both the moments are in D.

In the above, terms like ||Tg([0, δ σ (q)], ψc)|| ∞,2 imply the ||.|| ∞,2 norm of a ψ ∈ Ψ , where ψ(q, .) represents the random workload, Tg([0, δ σ (q)], ψc). Note that for any type of arrivals (i.e., with m = g or m = gg) and for any interval I and time function T ,

where B i are the service times of the arrivals in the chosen time period |T | and so it is clear that these type of terms to converges (in monotone fashion) to zero as B → 0.

In fact even the terms like 1/ B|Tm(., .)| drop to zero as B → 0. Thus there exists a B < ∞ such that

Hence Θ is a contraction for all σ and the contraction coefficient can also be chosen independent of σ, i.e., there exists B and L < 1 such that (for all B < B),

) is a complete space.

Proof: Say ψn is a Cauchy sequence. Then for any q, ψn(q, .) is Cauchy in L 2 space and hence there exist an L 2 -limit say call it ψ(q, .). Now for any q, ||ψn(q, .)ψ(q, .)|| 2 = lim m→∞ ||ψn(q, .)ψm(q, .)|| 2 .

For any ǫ > 0 there exists N such that sup q ||ψm(q, .)ψn(q, .)|| 2 ≤ ǫ for all n, m > N.

Combining the above two equations, whenever n > N sup q ||ψn(q, .)ψ(q, .)|| 2 ≤ ǫ and hence ||ψn -ψ|| ∞,2 → 0 as n → ∞. By completeness of D the map (of limits of L 2 norms) q → ||ψ(q, .)|| 2 resides in D.

⋄ Appendix C : Pareto Optimality

Let W be the set of vectors of expected waiting times achieved by a class of design policies. A vector w 1 ∈ W obtained by some policy dominates another vector w 2 if all entries of w 1 are smaller than or equal to those of w 2 with at least one entry being strictly smaller. This definition is given when w 1 has finite number of entries. We now extend the definition in an obvious way to our case, i.e., when w(q)ζ(q)dq, be a minimizer of the integral. Then w * is a Pareto optimal solution.

Proof : If it is not and there exists a vector w 1 which dominates w * . Say w 1 < w * on B with L(B) > 0 while w 1 = w * on the complement, B c . Then |C| 0 (w 1 (q)w * (q))ζ(q)dq = B (w 1 (q)w * (q))ζ(q)dq ≤ -c B (w * (q)w 1 (q))dq < 0.

and so the optimality of w * is contradicted when c > 0. When c = 0, by definition of infimum one can find a subset of B on which ζ > c > 0 and the proof follows.

⋄