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

Service Provision in Disconnected Mobile Ad hoc Networks

With the proliferation of mobiles devices equipped with communication interfaces such as IEEE 802.11 or IEEE 802.15, the mobile ad hoc networks have been recently arousing an increasing interest, and are considered from now as relevant supports for the ubiquitous and pervasive computing. The service provision in such networks arises as a critical issue for the success of these new computing paradigms. In this paper, we present both an approach and a middleware platform for the discovery and the invocation of services in disconnected, partially connected or intermittently connected mobile ad hoc networks. This approach relies on a content-based management of messages, on a flexible service invocation and on context-awareness.

Introduction

The generalisation of powerful portable devices capable of ad hoc communication are opening up new possibilities for service provision for nomadic people. Indeed beyond the application services considered so far for mobile ad hoc networks (i.e. services for emergency and/or military domains), new kinds of services relying on wireless opportunistic communications should be deployed and put at the civilians' disposal in the future.

Most of works investigating the discovery and the invocation of services in Mobile Ad hoc NETworks (MANETs) make strong assumptions regarding the communication between nodes by considering that this one is possible only if these nodes are both simultaneously active, and if a transmission route can be established between them whenever needed. This is actually equivalent to assuming that communication can only be made using a point-to-point synchronous communication paradigm, and that it can only occur in a fully connected network. By the way, a large number of works aim to define and to implement routing algorithms for MANETs in order to reuse the service provision mechanisms designed for wired-networks (e.g. Jini, UPnP, SLP). Yet when considering real mobile ad hoc networks, one can easily observe that their topology is extremely dynamic and frequently fragmented into small disconnected islands. The above-mentioned assumptions are therefore somewhat contradicted by the nature of these networks.

A number of recent research papers address specifically the problem of message delivery in disconnected, partially connected, or intermittently connected mobile ad hoc networks by focusing either on point-to-point routing in "delay-tolerant networks" [START_REF] Li | Sending Messages to Mobile Users in Disconnected Ad-hoc Wireless Networks[END_REF][START_REF] Shah | Delivering Messages in Disconnected Mobile Ad-Hoc Networks[END_REF][START_REF] Musolesi | Adapting Asynchronous Messaging Middleware to Ad Hoc Networking[END_REF] or on data flooding in such networks using epidemic [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF][START_REF] Musolesi | EMMA: Epidemic Messaging Middleware for Ad hoc networks[END_REF] or probabilistic [START_REF] Sasson | Probabilistic Broadcast for Flooding in Mobile Ad Hoc Networks[END_REF] propagation schemes. Nevertheless, none of these works address specifically the service provision issues in such networks. The lack of solution for service discovery and delivery thus motivated us to propose a new service provision approach for these networks.

The remainder of this paper is structured as follows. In Section 2 we identify the functionalities suited for service provision in disconnected, partially connected, or intermittently connected mobile ad hoc networks using a scenario, and we present our approach. In Section 3 we detail the mechanisms we have implemented in a service-oriented middleware platform in order to evaluate our proposition. In Section 4, we compare our approach with related works, and in Section 5 we summarise our contribution and we conclude this paper.

Service provision in disconnected mobile ad hoc networks

Motivating scenario

So as to point up problems inherent in the discovery and the invocation of services in disconnected, partially connected or intermittently connected mobile ad hoc networks, let us consider the scenario illustrated in Figure 1. In this scenario, students having portable devices (e.g. PDA, laptops) equipped with IEEE 802.11 network interfaces (a.k.a WiFi) are supposed to use application services while moving in a campus. These application services -that can deliver information such as course and exam timetable, campus maps, extra-scholar activities-are provided by specific devices deployed within the campus. The short communication range of WiFi interfaces and the mobility of devices generate frequent and unpredictable changes in the network topology -which is often partitioned into small disconnected islands.

In order to show the service provision process we want to provide, let us consider for the sake of illustration that a fixed device provided services such as those mentioned previously is deployed in point A (see Figure 1), and that at the time T , only three students are in the vicinity of this equipment. At this time only these students, including the student S 1 who is going to C, is able to discover and to invoke these services. Likewise, using traditional service provision mechanisms, the student S 2 , who is going to A, will be able to discover and to invoke these services only when it will be in the vicinity of the device deployed in point A. Yet, it is suitable to allow the student S 2 to discover and to invoke these services as soon as possible even if no route can be established between it and the service provider. Therefore, at the time T + ∆t 1 , when the students S 1 and S 2 will be both at B, S 1 should spontaneously advertise S 2 of the availability of the considered services, or should reply to a discovery request sent by S 2 for such services. If at the time T + ∆t 2 , S 2 invokes a service thus discovered with a request similar to that addressed by S 1 at the time T , and if S 1 is always in the vicinity of S 2 , S 1 should send to S 2 the response it obtained itself from the service at the time T , if this response is still valid obviously. To perform such tasks, the middleware platform deployed on the devices of the students S 1 and S 2 must support asynchronous communications relying on the "store, carry and forward" communication principle, and must implement a content-based management of messages so as to correlate service discovery requests with service advertisements, as well as service requests with service responses. These mechanisms should also help at reducing the service provision latency and at deciding what messages can be stored locally. This middleware platform must also take into account spatial, temporal and contextual properties in order to improve service provision and to reduce the propagation of messages in the network. The spatial, temporal, and in a less measure, the contextual properties associated with massages are used in routing protocols [START_REF] Musolesi | Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks[END_REF][START_REF] Cheng | Service Advertisement and Discovery in Mobile Ad Hoc Networks[END_REF] in order to improve the message delivery in ad hoc networks. The properties are rarely accessible by the middleware level. Yet in these networks, these information are relevant for the elements performing the discovery and the invocation of services. Indeed, these properties should help them to choose the service providers, to estimate the probability to obtain a response from a remote service provider, to enable client and providers to specify the lifetime and the range of their requests and responses, etc.

Proposition for service provision

In the remainder of this section, we describe our proposition to address the above-mentioned issues by specifying the notion of service and service provider, as well as by giving a specification of the messages exchanged in the service provision process.

A service is traditionally described by both its interface and its non-functional properties. A service S i implementing an interface I i and having a set N P i of n non-functional properties can thus be defined as

Si =< Ii, N Pi = {npj }/j ∈ [1..n] >
A same service, or a similar service, can be provided by several hosts in the network. A service S j can be considered as being similar to a service S i if and only if

I i = I j and ∀x ∈ N P i , x =∈ N P j
So as to provides a flexible service invocation scheme, a context-based service selection, hosts must be characterised by a unique identifier, which can be for instance an IMEI number or a MAC address, their contextual properties (e.g. hardware characteristics, position), the services they provide and they have discovered, as well as with the groups of which they are members. The concept of group allows a host to send the same message to a set of remote service providers without invoking them successively. A host, whose the identifier is ϕ, can be described as

Dϕ = < ϕ, LSϕ = {Si}/i ∈ [1..p], RSϕ = {Sj }/j ∈ [1..q] CPϕ = {cp k }/k ∈ [1..r], Gϕ = {g l }/l ∈ [1..t] >
where LS ϕ is the set of services provided by the device, RS ϕ the set of remote services considered as available in the network by the device, CP ϕ the set of contextual properties exhibit by the device, G ϕ the groups of which the device is member.

All the messages exchanged asynchronously by devices involved in a service provision process must include a unique identifier, temporal properties so as to decide if a message can be still considered as being valid, the identifiers of the sender and of the destination, both spatial and contextual information to control the propagation of messages in the network, the content of the message, as well as a set of properties describing this content in order to make the content-based management possible. A message can be a service discovery request, a service advertisement, a service request or a service response. These messages can be specified as follows:

Mi =< i, Oi, Di, Ci, CDi, Ti, Li, Hi, CPi >
The message M i is identified by i. The origin, the destination and the content are specified by O i , D i and C i respectively. The properties describing the content C i is specified by the field CD i . A message returned in response to another message also includes the identifier of this one. T i is the time when the message is sent. L i is the lifetime of the message. H i is the spatial property expressed in number of hops. CP i is the contextual properties exhibited by the sender O i at the time T i . A UML representation of messages is given in Figure 3.

Using the contextual, spatial and temporal properties specified in messages, each hosts is able to maintain its own view of the services available in the network, to estimate the probability to invoke a remote service provider successfully, to choose the better provider among several providers, as well as to select the most relevant invocation mode to obtain a response (invocation of a particular provider vs invocation of a group of providers).

A middleware platform for service provision in mobile ad hoc

This section presents the middleware platform we have designed in order to evaluate the proposition specified in the previous section. This platform, whose architecture is presented in Figure 2, is based on an OSGi gateway [START_REF] Alliance | Osgi service platform, release 3[END_REF]. Application-level services deployed on this middleware platform are expected to use the two middleware-level services we have designed in order to discover and to invoke remote services asynchronously. The first service (the communication service) implements the "store, carry and forward" communication principle, and offers a publish-andsubscribe interface for the management of messages. The second middleware-level service provides functionalities to manage services (e.g. description, selection, discovery and invocation of services), and uses the publish-and-subscribe mechanisms defined by the first middleware-level service in order to perform the content-based management of mes- sages. These services are further detail in the remainder of this section.

Service Management

The core of our framework is based on the OSGi framework. In this framework, services are characterised by both the Java interface they implement and their non-functional properties. Since, this framework only supports the registration, the discovery and the invocation of local services, we have defined a set of extensions in order to support a service provision process addressing the issues pointed up in the previous section. These extensions, whose a partial UML representation is given in Figure 3 (only most relevant elements and methods are specified), make it possible to describe local and remote services, to characterise service providers, to define messages exchanged in the service provision process, to perform a proactive and/or reactive service discovery and an asynchronous service invocation.

Service discovery

The proactive service discovery is performed using objects implementing the interfaces Ser-viceRegister, ServicePublisher and ServiceTracker respectively. The service register is responsible for maintaining locally a list of information about services and service providers. The service register is expected to be invoked by local services in order to discover remote services and to obtain references on service providers. When a service requested by a local service was not discovered yet, the service register creates itself a service discovery request (i.e. an object implementing the interface ServiceDiscoveryRequest) using the information specified by the local service (i.e. using the object implementing the interface ServicePattern), and sends it in the network. An object implementing the interface ServicePattern makes it possible to select services according to their description. When a service discovery request is received from the network by the service register of another node, this one checks if this request is matched by a descriptor of a local service, and if it is true, it asks to the service publisher to send in the network a service advertisement for this service. Such an advertisement should be received by the service tracker of the service requester. This one is responsible for handling service advertisement from the network and to register them with the service register.

The reactive service discovery relies on the reception of unsolicited service advertisements and on their management by the service tracker. These advertisements can be sent periodically or sporadically by a service publisher. As shown in Figure 3, service advertisements include objects implementing the interface ServiceDescritpor. Service descriptors provide information about services (e.g. the name of the interface, the properties of the service).

When the lifetime of a service advertisement is not valid, then the service register removes this descriptor and notifies the local services using the considered service that this one is not reachable from now. Thus local services can adapt dynamically their behaviour in order to take these changes into account. Like the fields source and destination, the contextual properties exhibit by hosts are specified in messages as header fields. (see Figure 3).

Service invocation

The asynchronous service invocation is achieved using notably the objects of type Ser-viceRequest, ServiceResponse, ServiceInvoker and Ser-viceResponseHandler. To invoke asynchronously a remote service (or a set of remote services), a local client is expected to use the methods asyncInvoke() defined by a Ser-viceInvoker object. The first method asyncInvoke() takes in parameters a ServiceResquest object and a ServiceRepon-seHandler object. The handler object is used by the client to handle the responses it receives following an event-based programming approach. This handler takes in parameters a timeout -which should be equals to the lifetime speci-fied in the request-and a number specifying how many responses must be handled. This handler uses the publish-and subscribe functionalities provided by the first middlewarelevel service in order to receive responses from the network. When the timeout it received in parameter is triggered, the handler is expected to unregister itself from this first middleware-level service.

Since temporal, spatial and contextual properties are intrinsically service-dependent, client services and service providers are responsible for specifying themselves these properties in the ServiceRequest and ServiceResponse objects respectively.

The communication service

With the service performing an epidemic dissemination of messages, any message sent in the network is maintained as long as possible in a local cache by as many devices as possible, so it can remain available for devices that could not receive it at the time it was sent originally. The underlying idea is that the dissemination of multiple copies of the same message may contribute to overcome the volatility of devices, while the mobility of these devices can itself help transport information between islands in a fragmented network or in distinct networks. Besides providing a caching system where messages can be maintained in mobile devices, our service also provides facilities for message advertisement, message discovery, and message transport between neighbouring devices. For example, a device can sporadically or periodically notify its neighbours about all or part of the messages stored in its cache. It can also look for specific messages in its neighbourhood, and either push messages toward or pull messages from its neighbours. In the current implementation, message dissemination is performed by broadcasting UDP datagrams. We thus assume, for the time being, that each message is small enough to fit in a single datagram. In the future we plan to improve this communication service so as to address issues pertaining on message segmentation and reassembly.

Structure of messages

As shown in the previous section, all messages used in the service provision process are reified as standard Java objects. These messages can be sent in the network as XML-formatted documents. A message is structured in two parts: the content, and a set of headers providing information useful in message handling. Figure 4 shows a typical XML-formatted message sent by a service provider in return of a service invocation.

<message id="fb0097820f0b371" type="service-response"> <headers> <header name="origin" value="00:0F:1F:C5:2F:F5"/> <header name="destination" value="casa"/> <header name="number-of-hops" value="5"/> <header name="date" value="Nov 29 16:09:47 CET 2006"/> <header name="lifetime" value="12:00:00"/> <header name="md5sum-content" value="186c322f04579a179f1cce23b78e7a555"/> <header name="request-id" value="db0192810f0b21"/> <header name="md5sum-request-content" value="186c322f04579a179f1cce23b78e7a555"/> .... </headers> <content> ... </content> </message> The value of attribute id in a message should be unique. This condition makes it possible for a device receiving a message from the network to verify if a copy of this message is already available in its local cache. The attribute type precises the type of the message. The type of a message can be service-discovery-request, service-advertisement, service-request, service-response and cancel-message. The message also specifies that it has been sent by the node whose IP address is "00:0F:1F:C5:2F:F5" (header origin)and that is is addressed to the nodes that are members of the group "casa" (header destination). As mentioned in the previous sections, destination and origin address can be either the address of a given service provider (i.e. of a given node) of a group , or the wildcard "*". The header numberof-hops plays approximately the same role as the field TTL (Time-To-Live) in IP packets. It ensures that a message will not be propagated eternally in the network. The header date specifies the date when the message was originally sent in the network, and the header lifetime specifies that this message should be considered as being valid for only twelve hours after this date. The header md5sum-content, which is the md5 sum of the content, is expected to help node in the content-based management. In both service response and service advertisement, the md5 sum of the request associated with the response or with the advertisement is also specified. With such an information a mobile host receiving a service invocation request pertaining to a service that it not provides itself, but for which it has already played the role of forwarder, can reply itself to this message by sending the response that it has stored previously in its local cache, whether this one is still valid obviously. The headers can also include contextual properties such as the GPS position of the sender.

Related work

Existing middleware solutions, such as DEAPspace [START_REF] Hermann | DEAPspace -Transient ad hoc networking of pervasive devices[END_REF], Konark [START_REF] Helal | Konark : Service Discovery and Delivery Protocol for Ad-hoc Networks[END_REF], ReMMoC [START_REF] Grace | ReMMoC: A Reflective Middleware to Support Mobile Client Interoperability[END_REF] and INDISS [START_REF] Bromberg | INDISS: Interoperable Discovery System for Networked Services[END_REF], have investigated the service provision issues in ad hoc networks. DEAPspace provides a support for the discovery and the delivery of services in wireless single-hop ad hoc networks. The middleware Konark targets environment and goal similar to DEAPspace, but considers multi-hop wireless ad hoc networks. Like in DEAPspace, each device in Konark maintains in a directory a vision of services available in the network, and acts both as client and provider of services. Konark makes some assumptions regarding the network by considering that a transmission route can be established between a client and a service provider whenever needed. Thus it does not support the service provision in intermittently connected mobile ad hoc networks. ReMMoC and INDISS have investigated the dynamic discovery and interaction in pervasive environments, particularly focusing on configuring and using the appropriate discovery protocol to find services in the current environment. These systems have so far only considered infrastructure-based wireless networks in which standardised discovery protocols such as Jini, Service Location Protocol, and Universal Plug and Play are used.

There is now emerging a suite of discovery protocols for mobile ad-hoc networks (MANETs), which have been developed to deal with the limitations of nodes in such environments (i.e. unpredictable network topology, variable number of participating nodes, different levels of dynamicity, and nodes with restricted knowledge of their neighbours). Scalable Service Discovery (SSD) [START_REF] Sailhan | Scalable Service Discovery for MANET[END_REF] is an example of such protocols. In SSD, the discovery relies on a set of directories elected on the fly by mobiles nodes. Each directory is responsible for performing service discovery in a n-hops range. The global service discovery is achieved by a collaboration of the directories. This ap-proach aims at reducing the service discovery traffic. SSD assumes IP-level connectivity using the underlying routing protocol (e.g. OLSR, AODV, ZRP).

Conclusion and future work

In this paper, we have presented both an approach and a framework for the service provision in partially connected, intermittently connected, or disconnected mobile ad hoc networks. This approach relies on a flexible addressing scheme, on a content-based management of messages and on asynchronous communications relying on the store-andforward principle.

The middleware platform implemented using this framework will be evaluated in the future through simulation under different network conditions, varying the network size, node mobility level, the number of services and requests. Moreover, we plan to enable bridging MANETs with infrastructure-based networks since Intranet and/or Internet remains the primary source of service provisioning.

Figure 1 .

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

Figure 2 .

 2 Figure 2. The middleware architecture.

Figure 3 .

 3 Figure 3. A partial UML representation of the service management API.

Figure 4 .

 4 Figure 4. An XML-formatted message exchanged by application-level services.

Acknowledgements

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. http://www-valoria.univ-ubs.fr/SARAH


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

A Framework for Service Provision in Intermittently Connected Mobile Ad hoc Networks

Mobile ad hoc networks have been recently receiving much attention due to the important prospects they offer in service terms. Indeed, beyond the application services envisioned so far in emergency and military scenarios, civilian mobile ad hoc services usable in everyday life are considered from now. Service provision is a critical issue to the success of this new computing paradigm. In this paper, we present a novel approach for service provision in intermittently connected mobile ad hoc networks, as well as a framework implementing this approach.

Introduction

Recent technological advances in hardware computing and wireless technologies are opening up exciting possibilities for the future of mobile and pervasive computing. Indeed, beyond the application services considered so far for mobile ad hoc networks (i.e. services for emergency and/or military domains), new kinds of services relying on wireless proximate communications, and do not requiring any infrastructure-based networks, can be envisioned from now for civilians.

Most of works investigating service provision in Mobile Ad hoc NETworks (MANETs) consider that communication between two devices in a network is possible only if these devices are both simultaneously active, and if a transmission route can be established between them whenever needed. Making such an assumption is actually equivalent to assuming that communication can only be made using a point-to-point synchronous communication paradigm, and that it can only occur in a fully connected network. A large number of works thus aim to define and to implement routing algorithms for MANETs in order to reuse the service provision mechanisms designed for wired-networks (e.g. Jini, UPnP, SLP). Yet, when considering the largescale peer-to-peer mobile ad hoc networks that could appear in a near future, one can observe that the topology of these networks is very dynamic due to the mobility and the volatility of devices, and that they are frequently fragmented into small disconnected islands. Therefore, the above-mentioned assumption is somewhat contradicted by the nature of these networks.

A number of recent research papers address specifically the problem of communication in disconnected, partially connected, or intermittently connected mobile ad hoc networks. Some of these papers focus on point-to-point routing in "delay-tolerant networks" [START_REF] Li | Sending Messages to Mobile Users in Disconnected Ad-hoc Wireless Networks[END_REF][START_REF] Shah | Delivering Messages in Disconnected Mobile Ad-Hoc Networks[END_REF], while others rather consider the problems of data flooding and dissemination in such networks [START_REF] Khaled | Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding in Sparse Mobile Networks[END_REF][START_REF] Musolesi | EMMA: Epidemic Messaging Middleware for Ad hoc networks[END_REF]. Moreover, while some of the papers assume that mobility patterns can be identified -and sometimes controlled-in ad hoc networks [START_REF] Zhao | A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks[END_REF][START_REF] Li | Sending Messages to Mobile Users in Disconnected Ad-hoc Wireless Networks[END_REF], other papers make no such assumption and propose to rely on redundancy in order to improve the reliability of delay-tolerant transmission. In the latter category, it is usually proposed to rely on epidemic [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF][START_REF] Eugster | From Epidemics to Distributed Computing[END_REF][START_REF] Musolesi | EMMA: Epidemic Messaging Middleware for Ad hoc networks[END_REF] or probabilistic [START_REF] Sasson | Probabilistic Broadcast for Flooding in Mobile Ad Hoc Networks[END_REF] propagation schemes. Nevertheless, none of these works address specifically the service provision issues in such networks. Existing middleware solutions, such as DEAPspace [START_REF] Hermann | DEAPspace -Transient ad hoc networking of pervasive devices[END_REF] and Konark [START_REF] Helal | Konark : Service Discovery and Delivery Protocol for Adhoc Networks[END_REF], have already investigated the service provision issues in ad hoc networks, but not specifically in intermittently connected mobile ad hoc networks. DEAPspace provides a support for the discovery and the delivery of services in single-hop wireless ad hoc networks. Konark in contrast considers multi-hop wireless ad hoc networks, but it makes some assumptions regarding the network by considering that a transmission route can be established between a client and a service provider whenever needed. The lack of solutions for service discovery and delivery thus motivated us to propose a new service provision approach for these networks.

The remainder of this paper is organised as follows. Section 2 identifies the functionalities suited for service provision in disconnected, partially connected, or intermittently connected peer-to-peer mobile ad hoc networks. Section 3 presents the framework we have designed to support service provision in such networks. Section 4 summarises our contribution and concludes this paper.

Service provision issues in intermittently connected mobile ad hoc networks

This section presents a scenario of service provision in a peer-to-peer mobile ad hoc network, and underlines the major issues that must be addressed.

In the scenario of Figure 1, we consider provision of road traffic information services. These services -which can be delivered by devices deployed temporarily by teams carrying out road works and/or by rescue squads during accidents, and by devices installed permanently in difficult traffic areas-are expected to be used by devices embedded in vehicles (e.g. GPS) in order to notify drivers about the eventual traffic difficulties. We also consider in this scenario that the devices embedded in vehicles and those deployed in the environment are equipped with short range radio interfaces (e.g. IEEE 802.11). The topology of the network considered in this scenario thus suffers from frequent and unpredictable changes and is often partitioned into small disconnected islands.

For the sake of illustration, let us consider that a team carrying out road works in P 1 (see Figure 1) has temporarily installed an equipment offering an access to a service of type of those above-considered, and that at the time T , only one vehicle, the vehicle V 1 , is in the vicinity of this equipment. At this time only V 1 , which is going to P 2 , is able to discover and to invoke this service. Yet, it is, for instance, suitable to allow the vehicle V 2 , which is going to P 3 , to discover and to invoke this service as soon as possible even if no route can be established between it and the provider of this service. Therefore, at the time T + ∆t 1 , when the vehicles V 1 and V 2 will be both at P 4 , V 1 should spontaneously advertise V 2 of the availability of the considered service, or should reply to a discovery request sent by V 2 for such a service. If at the time T + ∆t 2 , V 2 invokes the service thus discovered with a request similar to that addressed by V 2 at the time T , and if V 1 is always in the vicinity of V 2 , V 1 should send to V 2 the response it obtained itself from the service at the time T , if this response is still valid obviously. Such a service discovery and invocation process should occur in a recurrent manner according to the mobility of the vehicles.

Besides issues inherent in communication in mobile ad hoc networks (e.g. the minimisation the traffic generated by mobile nodes), provision of such services requires

• To provide a flexible addressing scheme so as to enable a node to send a message to a particular host, to a group of remote hosts or to all reachable hosts, thus minimising the number of messages disseminated in the network.

• To support asynchronous communications relying on the store-and-forward communication principle in order to face up to the fragmentation of the network, as well as to the mobility and volatility of devices.

• To support a content-based management of messages in order to reduce the service provision latency, and to help each device to decide what messages it should accept to store.

• To take into account spatial, temporal and contextual properties in order to improve service provision and to reduce the propagation of messages in the network.

A framework for service provision in mobile ad hoc networks

Overview of the framework

The core of our framework is based on the OSGi framework [START_REF] Le Sommer | Osgi service platform, release 3[END_REF]. In this framework, services are characterised by both the Java interface they implement and their nonfunctional properties. Since, this framework only supports the registration, the discovery and the invocation of local services, we have defined a set of extensions in order to support a service provision process addressing the abovementioned issues. These extensions, whose a partial UML representation is given in Figure 3 (only most pertinent elements and methods are specified), make it possible to describe local and remote services, to characterise service providers, to define messages exchanged in the service provision process, to perform a proactive and/or reactive service discovery and an asychronous service invocation. In this framework, each mobile host is characterised by its contextual properties (e.g. hardware characteristics, position), the services it provides and it has discovered and the groups of which it is a member (see Figure 3). The concept of group aims to allow a host to send the same message to a set of remote hosts without invoking them successively. All the messages exchanged asynchronously by devices include a unique identifier, temporal properties so as to decide if a message can be still considered as being valid, the identifiers of the sender and of the recipient, both spatial and contextual information to control the propagation of messages in the network, the content of the message, as well as a set of properties describing this content in order to help in the content-based management. The spacial, the temportal, and in a less measure the contextual properties, associated with the messages are used by routing protocols in order to improve message delivery in mobile ad hoc networks. These properties are rarely accessible at application levels. Yet in mobile ad hoc networks, these properties are relevant to the elements that perform the service discovery and delivery. Indeed, such properties can help them to select the best service providers, to estimate the probability to access to a given remote service, to choose the best service invocation mode (invocation of a group of providers vs invocation of a specific host), to enable client and service providers to define the lifetime and the range of their request and response, etc. Moreover unlike routing protocols, these elements are able to correlate these properties with the content of messages. A UML representation of messages is given in Figure 3.

Service discovery

Our framework defines functionalities to support a proactive and/or reactive service discovery. The proactive service discovery can be performed using objects implementing the interfaces ServiceRegister, ServicePublisher and ServiceTracker respectively. A service register is responsible for maintaining locally a list of information about services and service providers. The service register is expected to be invoked by local services in order to discover remote services and to obtain references on service providers. When a service requested by a local service was not discovered yet, the service register should create itself a service discovery request (i.e. an object implementing the interface ServiceDiscoveryRequest) using the information specified by the local service (i.e. using the object implementing the interface ServicePattern), and should send it in the network. An object implementing the interface Servi-cePattern makes it possible to select services according to their description. When a service discovery request is received from the network by the service request handler of another node, this one is expected to check if this request is matched by a descriptor of a local service, and if it is true, it asks to the service publisher to send in the network a service advertisement for this service. Such an advertisement should be received by the local service tracker. This one is responsible for handling service advertisement from the network and to register them with the service register.

The reactive service discovery relies on the reception of unsolicited service advertisements and on their management by the service tracker. These advertisements can be send periodically or sporadically by a service publisher. As show in Figure 2, service advertisements include objects implementing the interface ServiceDescritpor. Service descriptors provide information about services (e.g. the name of the interface, the properties of the service).

When the lifetime associated with a service advertisement become obsolete, then the service register remove this descriptor and notifies the local services using the considered service that this one is not reachable from now. Thus local services can adapt dynamically their behaviour in order to take these changes into account.

Service invocation

In our framework, the asynchronous service invocation is achieved using notably the objects of type Ser-viceRequest, ServiceResponse, ServiceInvoker and Ser-viceResponseHandler. To invoke asynchronously a remote service (or a set of remote services), a local client is expected to used the methods asyncInvoke() defined by a Ser-viceInvoker object. The first method asyncInvoke() takes as parameters a ServiceResquest object and a ServiceRepon-seHandler 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 lifetime specified in the request-and a number specifying how many responses must be handled. This handler is registered with the ServiceResponseListener by the ServiceInvoker in order 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 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 a Ser-viceRequest. This method is designed to be blocked 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 specify themselves these properties in the ServiceRequest and ServiceResponse objects respectively.

Conclusion and future work

In this paper, we have presented both an approach and a framework for the service provision in partially connected, intermittently connected, or disconnected mobile ad hoc networks. This approach relies on a flexible addressing scheme, on a content-based management of messages and on asynchronous communications relying on the store-andforward principle.

Figure 1 .

 1 Figure 1. Example of an intermittently connected mobile ad hoc network.

Figure 2 .

 2 Figure 2. A partial UML representation of the framework.

The middleware platform implemented using this framework will be evaluated in the future through simulation under different network conditions, varying the network size, node mobility level, the number of services and requests. Moreover, we plan to enable bridging MANETs with infrastructure-based networks since Intranet and/or Internet remains the primary source of service provisioning.


Sreenath Ramanath

Veeraruna Kavitha

Eitan Altman

Spatial queueing analysis for mobility in pico cell networks

In this work, we characterize the performance of pico cell networks in presence of moving users. We model various traffic types between base-stations and mobiles as different types of queues. We derive explicit expressions for expected waiting times, service times and drop/block probabilities for both fixed as well as random velocity of mobiles. We obtain (approximate) closed form expressions for optimal cell sizes when the velocity variations of the mobiles is small for both non-elastic as well as elastic traffic. We conclude from the study that, if the call is long enough, the optimal cell size depends mainly on the velocity profile of the mobiles, its mean and variance. It is independent of the traffic type or duration of the calls. Further, for any fixed power of transmission, there exists a maximum velocity beyond which successful communication is not possible. This maximum possible velocity increases with the power of transmission. Also, for any given power, the optimal cell size increases when either the mean or the variance of the mobile velocity increases.

I. INTRODUCTION

Since the time 3G technology was designed and deployed, various other technologies have appeared. The ambitious objectives in terms of quality of service offered by 3G technology turned to be quite expensive, which made the 3G technology vulnerable to cheaper competing technologies such as WIFI. Pico cell technology has been recently proposed as an alternative that offers some basic connectivity and mobility support, and is yet sufficiently simple so as to be economically competitive ( [START_REF]Picocell Mesh: Bringing Low-Cost Coverage, Capacity and Symmetry to Mobile WiMAX[END_REF], [START_REF] Davi | Using picocells to build high-throughput 802[END_REF]). To prevent a large number of handovers that would result from the small size of the cells ( [START_REF] Sen | A QoS management framework for 3G wireless mobile network[END_REF]), it has been proposed to group together a number of pico cells in one virtual Macrocell and to restrict the effort of preventing losses due to the handover only to those handovers that occur between Pico cells of the same virtual cell. In between the Pico cells some fast switching mechanisms are proposed such as frequency following mechanism where the frequency used by a mobile follows it from one pico cell to the next. This requires reserving the same channel for a user in the entire Macrocell.

In this paper we consider a large macrocell divided into a number of pico cells and study the impact of mobility on such systems, especially the effect of frequent handovers. We assume that the ongoing call is never dropped at the pico cell boundary, however base station switching (BSS) at any pico cell boundary requires some fixed amount of information (in terms of bytes) to be exchanged. There is however a possibility of calls being dropped at macrocell boundaries. We further assume that the active users cross macrocell boundaries at maximum once. The handovers at the macrocell boundaries are modeled as independent Poisson process. This paper has several goals. First, to model the system so as to predict its performance measures. We are thus interested in developing tools in spatial queueing that take into account not only the instantaneous geometry but also the way it varies in time. It should thus account for the impact of the speed of the users. We model the macrocells by various types of queues and well known results from queueing theory are used to obtain performance measures like expected waiting times, service times, drop or blocking probabilities, etc [START_REF] Wolff | Stochastic Modeling and the Theory of Queues[END_REF]. We shall use these results for preliminary dimensioning purposes in planning the Pico cell network catering to pedestrian and vehicular mobility, typical of urban and sub-urban areas. We derive closed form expressions of useful performance metrics considering free space path loss, handover constraints, traffic type etc. We also obtain closed form expressions for optimal cell sizes, optimal for various performance metrics, when all the users move at the same fixed velocity. To derive these performance measures, we would require the moments of the time taken by the system to serve the customers, which in our case will equivalently be the time the macrocell spends on a call. We derive the expressions for these service times, during which the information is exchanged between the moving user and the set of appropriate base stations (which it encounters during its journey), using variable rate • Maximum possible velocity: For any fixed power of transmission P , there exists a maximum velocity V lim (P ), beyond which successful communication is not possible;

• Larger cells for larger velocities: Given P , the optimal cell size increases with an increase in the highest velocity that the system has to support.

• Insensitivity to application: The optimal cell size remains the same for non-elastic as well as elastic calls for big file sizes, as long as rest of the parameters remain the same.

II. SYSTEM MODEL

We consider a macrocell, [-D, D], divided into a number of pico cells of length L. Each pico cell has a base station (BS) located at the center and all these BS communicate to a central unit (CU), which controls the entire system. We assume that there is no interference between any two transmissions.

Traffic Types: Define the waiting time as the duration between the arrival of the call and the instance its service starts. We consider two types of traffic: elastic (ES) and Non-elastic (NES). The non-elastic traffic is very sensitive to the waiting time (multimedia streaming, voice calls etc). A call of this type will be blocked if not picked up within a very small waiting time. with respective densities f n,X , f n,V and f n,S . Let P n := (P n,X , P n,V , P n,S ),

We assume symmetry in both directions, i.e., P n ((X, V, S) ∈ A) = P n ((X, V, S) ∈ -A) for all Borel sets A. In this paper we thus calculate and analyze without loss of generality (w.l.g.) for V > 0.

Handovers: A crossover into a new macrocell results in a successful handover only if the new macrocell has free servers. We model each handover into a macrocell as a Poisson arrival, stochastically independent of the new call arrivals. We further assume that there can be at maximum one handover, i.e., the calls get finished before reaching the second macrocell boundary. This simplifies the analysis to a good extent and is quite a good assumption as the macrocells are typically large in dimension. We consider generalization of this assumption in our future work.

Radio Conditions:

The BS communicates with the mobiles using a wireless link, at a rate that depends upon the distance between the two. Since our primary focus is on mobility we implicitly consider pico cells deployed outdoors, for example urban, suburban scenarios. Hence we can assume significant line of sight signal. Further, pico cells being small in size, it will be sufficient to consider only the direct path for communication. A user located at x communicates with BS of cell m using unit transmit power (when receiver noise variance is one) at rate

R(x; m) := 1 {|x-(mL-L 2 )|≤d0} + 1 {|x-(mL-L 2 )|>d0} d 0 β x -mL - L 2 -β , (1)
where β ≥ 1 represents path loss factor and d 0 > 0 is small distance up to which there is no propagation loss 1 .

III. SYSTEM ANALYSIS

The users are moving continuously with a fixed but random velocity. The macrocell can handle at maximum K parallel calls. Transmission always occurs at fixed power P . Since Pico cells are small in size, the movement of the users results in frequent handovers. The number of handovers will be quite large that it would be complicated to design a reliable system without redundancy: We assume that every BS can also handle K parallel calls 2 . This ensures that, once a call is picked up it is not dropped at any pico cell boundary. We further assume that : (1) Every BSS (base station switching at a pico cell boundary) requires fixed B h bytes of information to be communicated (independent of the user's velocity), after which the user's service is resumed by the BS of the cell it just entered; (2) The user is served by the BS of the pico cell in which it is moving, as it is physically nearest to this BS.

A. Time required for communicating S bytes:

Define by B c (S, X, V ) the time required to communicate a packet of length S bytes to a user located at X (when the service starts) and moving with velocity V . If the user can communicate at a fixed rate r bytes/sec then the communication time would have been S/r. The maximum rate at which a user can communicate with the BS in cell m is given by ( 1). This position dependent rate varies: minimum when the user is at the cell edges and increases as the user moves towards the cell center. This poses a need to calculate the communication time considering the variable rates. The location of the user (under service) will change according to X(t) = X + V t (Figure 1). At time t, if the user is in cell m, i.e. if X(t) ∈ [(m -1)L, mL], it communicates with the BS of m th cell. Hence the user gets service at time varying rate given by

R(t; X, V ) := P R(X(t); m) if t ∈ (m -1)L -X V , mL -X V .
Without loss of generality we consider the users, whose communication started in the first pico cell, i.e., with X ∈ [0, L].

The communication time B c required by the user, i.e., the time required to communicate S bytes satisfies :

S = Bc 0 R(t; X, V )dt. (2)
Let

g(l) := l/V 0 P R(V t; 1)dt = P l 0 R(l ; 1) dl V ,
represent the number of bytes communicated while the mobile traverses interval [0, l]. For any m, the number of bytes communicated as the user traverses through m th pico cell,

mL-X V (m-1)L-X V R(t; X, V )dt = mL-X V (m-1)L-X V P R(X + V t; m)dt = P V L 0 R(l; 1)dl = g(L)
and thus is independent of m. Out of this number, B h number of bytes are dedicated for BSS. Hence, irrespective of the cell which the user traverses, g(L) -B h number of bytes are transmitted during the user's journey via one pico cell. Thus the communication time can have three components :

1) Time taken in the originated cell (L -X)/V , 2) Time taken to travel N full cells, where (with t representing the largest integer in t)

N := (S -(g(L) -g(X))) g(L) -B h
represents the number of cells traveled during the communication of S bytes and 3) Time taken in the cell in which the call terminates: time taken to communicate the leftover bytes

S l := S -(g(L) -g(X)) -N (g(L) -B h ).
From (2), the communication time B c (S, X, V ) can be calculated and is given by Theorem 1, placed at beginning of the following page. Theorem 1 requires the existence of g -1 , which is guaranteed as g is a continuous and monotonically increasing function.

Approximation : In pico cell based systems, user traverses a large number of pico cells while receiving service. Hence the communication time can be approximated by the product of number of cells S/(g(L)-B h ) and the time taken for traveling each cell L/V :

B c (S, X, V ) ≈ S g(L) -B h L V when g(L) > B h . ( 3
)
The approximation is very good, in fact for all velocity profiles (refer to [START_REF] Ramanath | Spatial queueing analysis for mobility in pico cell networks[END_REF] for details). If a call is originated at position X and moves with velocity V = 0, then in case of ES applications, Theorem 1: Time to communicate S bytes with a user initially located at X and moving with velocity V is,

B c (S, X, V ) =      g -1 (S+g(X))-X V if S < (g(L) -g(X)) ∞ if B h > g(L) (L-X)+N L+g -1 (S l +B h ) V
else, where

g -1 (s, v) =                              L 2 (1 -e -sV P d 0 ) if β = 1 sV P d0 < log L 2d0 L 2 + 2d 2 0 e -2 L e sV P d 0 if β = 1 sV P d0 > log L 2d0 + 2 L 2 + sV P -d 0 log L 2d0 -d 0 if β = 1 else L 2 -sV (β-1) P d β 0 + L 2 -β+1 β-1 if β > 1 sV (β-1) P d β 0 < d -β+1 0 -L 2 -β+1 L 2 + 2βd -β+1 0 β-1 -sV (β-1) P d β 0 -L 2 -β+1 β-1 if β > 1 sV (β-1) P d β 0 > (β+1)d -β+1 0 β-1 -L 2 -β+1 L 2 + d β 0 β-1 sV (β-1) P d β 0 + L 2 -β+1 -d -β+1 0 β if β > 1 else. ----------------------------------------------------
the call will be picked up at a position X s (= X + V W ; W the waiting time) different from X. It is difficult to estimate X s and the time taken to communicate S bytes, B c , actually depends upon X s but not on X. However with the above approximation, B c (S, X s , V ) = B c (S, V ), i.e., B c does not depend upon the location of the user when its communication started.

Maximum velocity handled by the system : Communication time is finite only if the number of bytes transfered g(L) per cell is strictly greater than the bytes required for BSS, B h .

Hence, the communication time is finite with probability one if and only if

P rob(B h > g(L)) = P n,V (V B h > η(L)) = 0.
where η(L) := V g(L) depends only upon P and L. Thus we have, Theorem 2: When β = 1, for any transmit power P , system can handle all velocity profiles. When β > 1, there exists a bound V lim (P ) < ∞ (increasing linearly with P ) on the maximum velocity that can be handled by system

V lim (P ) := η ∞ B h with η ∞ := lim L→∞ η(L) = 2P d 0 + d β 0 ∞ d0 l -β dl = 2P d 0 β β -1

B. Service time : The time of the macrocell spent for user's service

The user reaches the boundary of the macrocell starting from a point X in time (w.l.g. when V > 0)

B ∂ (X, V ) := D -X V .
The macrocell has to serve the user either until all its S bytes are transmitted (which takes time B c ) or till the user reaches the boundary. Thus, the overall service time requirement of the user in a macrocell is

B D := min D -X s V , B c (V, S) .
As noted above, B c does not depend upon X s . For NES applications X s = X the position of arrival. For ES applications, it is difficult to estimate X s , instead we approximate X s with X, i.e.,

B D (X, V, S) ≈ min{B ∂ (X, V ), B c (V, S)}.
The error in this approximation is given by:

E rr = W 1 {Bc> D-X V } + B c - D -X s V 1 { D-Xs V <Bc< D-X V }
and so for any k,

E[E k rr ] ≤ E W k 1 {Bc> D-X V -W } .
The error is small either whenever K is large (so waiting times are small) or when the macrocell is large in size.

Distribution of handover call marks (X, S): In general their densities will be different from f n,X , f n,S and f n,V . As the users move in either direction with equal probability, P h,X the position of handover arrival occurs either at -D or at D with half probability. If handover occurs at -D the corresponding velocity will be positive, which is the case we consider w.l.g. We assume f n,S is exponential, i.e., f n,S (s) = µe -µs for some µ > 0, in which case

f h,S = f n,S .
Rate of handovers: Let

ν(v, L) := η(L) -vB h L . (4)
Then

P ho := P rob(B ∂ < B c ) = E n,X,V exp -µν(V,L) (D-X) V
gives the probability that a call is not completed in one macrocell. This precisely represents that fraction of new arrivals which get converted into handover calls. So

λ ho := λP ho
is the rate at which handovers occur.

Speed of handover arrival : A handover call arrives at X = -D with velocity v > 0 only if a new call with velocity v is not completed before reaching the boundary. Here we use the assumption that handover occurs at maximum at one macrocell boundary. Let

P ho,v := P rob(B ∂ < B c |v) = E n,X exp -µν(v,L) (D-X) v
represent the conditional probability that an handover occurred given V = v. Then the handover speed distribution,

f h,V (v) = f n,V (v) P ho,v P ho .

C. Moments of Service time

The number of bytes that can be communicated in a cell increases with the increase in cell size (g is clearly monotonically increasing and a continuous function of L). For any given velocity there exists a minimum cell size (the smallest cell size at which one can transmit more than B h bytes per cell), beyond which successful communication is possible. When cell sizes are closer to this smallest one, the useful bytes transmitted per cell (g(L) -B h ) are very small and hence it take more time to transmit S bytes, i.e., the communication time B c will be large. As the cell sizes increases from this smallest size, the communication time B c starts reducing.

However after some point, due to path loss, the number of bytes per cell starts saturating and hence the gain in terms of useful bytes transmitted per cell will be small in comparison with the extra time taken to traverse each cell, resulting in increasing the communication time again. Thus there exists an optimal cell size for every fixed velocity. One can extrapolate similar things even for random velocity. In this subsection, we find the optimal cell size L * b (1) := arg min L b (1) (where b (1) , the first moment of the overall service time is defined in [START_REF] Sen | A QoS management framework for 3G wireless mobile network[END_REF] of the following page) and relate the same to the optimizer of more interesting performance measures for ES and NES calls in the subsequent sub-sections.

We assume P (V < V max ) = 1 with V max < V lim (P ). Then the k th moment of B D exists (whenever the corresponding for S and V -1 exist) and is given by eqn [START_REF] Sen | A QoS management framework for 3G wireless mobile network[END_REF] in the following page. It is easy to see that the service time B D (x, v, s) also depends upon L only via the function ν given by ( 4). Hence it is easy to see that the derivatives will have the form

db (k) dL = E n,V ∂ν(V, L) ∂L E n,X [Γ k (X, V, S, ν(V, L))]
for some functions Γ k . Thus for fixed velocities, i.e., when V ≡ v, all the moments have unique minima arg min L b (k) and the unique minimum for all k is given by

arg min L b (k) = arg min L ν(v, L).
Thus b (2) and b (1) are optimized by the same cell size for fixed velocities. Further for velocity profiles with small variances, the optimizers will be equal approximately. Hence when P n,V has small variance with mean v then L * b (1) := arg min L b (1) is close to L * ν := arg min L ν(v, L) and hence satisfies ∂ν(v, L) ∂L

L=L * b (1) ≈ 0 or 2P L * b (1) d 0 -β L * b (1) -η(L * b (1) ) + vB h ≈ 0.
Thus we have, Theorem 3: For fixed velocity profile, i.e., P n,V (V = v) = 1 the optimal cell size for expected service time is,

L * b (1) = 2 2P d β 0 β β-1 2P d 0 β β-1 -vB h β-1 when β > 1 and = 2d 0 e vB h 2P d 0 when β = 1. b (k) := E X,V,S [(B D (X, V, S)) k ]
where P X,V,S := λ(P n,X , P n,V , P n,S ) + λ ho (P h,X,V , P h,S ) λ + λ ho (5)

= 1 (1 + P ho ) ∞ 0 D -D Vmax 0 B D (x, v, s) k + B D (-D, v, s) k P ho,v f n,V (v)dv f n,X (x)dx µexp -µs ds.
- ---------------------------------------------------The above will be approximately true for the velocity distribution P n,v with mean v and small variance. From the above it is clear that L * b increases when the mean v increases.

D. ES Calls : Average Waiting time

Each macrocell can handle at maximum K parallel calls.

The CU of the macrocell keeps a record of the users entered into the system and serves them in FIFO order via the BSs of the Pico cells. When a new user initiates a call, it is immediately picked up if there are less than K active calls in the system. If not the user will have to wait. Its service will start at the time:

• when one of the active K users finish their service and exit

• if there are no other waiting users arrived before it.

The BS nearest to the user, at the time of its service start, will initiate the call. Hence after, its call is served as discussed in subsection III-A either till its service is over or till it reaches the macrocell boundary. When it reaches the boundary the call will be transfered to the next macrocell as a handover call and the handover call is treated by the new cell similar to that of a new call. Thus each macrocell can be modeled by a M/G/K queue with service times B D and Poisson arrivals at rate λ + λ ho . This queue has been analyzed to a good extent and the system is stable only if ( [START_REF] Takahashi | An approximation formula for the mean waiting time of an M/G/c queue[END_REF])

ρ := λb (1) K < 1.
For stable queues, the expected waiting time of a randomly arrived customer can be approximated by eqn (6) ( [START_REF] Takahashi | An approximation formula for the mean waiting time of an M/G/c queue[END_REF]). where b (1) , b (2) are given by ( 5). If the system is unstable the number of waiting customers grows towards infinity and thus one should consider only the cell sizes L with ρ < 1. Hence, the optimal size,

L * ES = arg min {L:ρ<1} E[W ] K .
We saw in the previous section that the optimizer of b (2) is same as that of b (1) for fixed velocities and will be close to each other for smaller velocity variances. The expected waiting time ( 6) is continuously differentiable in both b (1) , b (2) . Thus (minimizer of ( 6) is a zero of its derivative and

E[W ] K depends upon L only via b (1) , b (2) ),
Theorem 4: Optimal cell size for a system with elastic traffic and when all users move with velocity v is

L * ES = arg min {L:ρ<1} E[W ] k = L * b (1) .
In other words, L * b (1) minimizes both expected waiting and service times. Further, when the variance of the velocity profile is small, from (6) it is easy to see that the optimizer of E[W ] K will be close to that of the expected service time, b (1) . Thus for low velocity variances also,

L * ES ≈ L * b (1)
. We see that this is true even for many general velocity profiles via numerical examples in the subsequent sections.

E. NES Calls : Block and Drop Probabilities

A call is picked up immediately only if the system is serving lesser than K users at the time of its arrival. If all the servers are busy it is dropped. When an active customer reaches the boundary of a macrocell, its call is continued in the next macrocell only if the new macrocell has free servers. This system can thus be modeled by an M/G/K/K queue. And its call block probability is given by,

P B (L) = ρ(L) K K! K k=0 ρ(L) k k! with ρ(L) := λb (1) K .
It is easy to see that (P B depends upon L only via b (1) . Refer [START_REF] Ramanath | Spatial queueing analysis for mobility in pico cell networks[END_REF] for details)

Theorem 5: The minimizer, L * b (1) also minimizes the block probability, P B , for all velocity profiles. Drop Probability : Under the assumptions stated earlier, only a new call can reach the boundary and not a call which was already handed over once. Further, an active call is dropped only when it reaches the macrocell boundary and the new macrocell is busy. By independence of the two events (status of the new macrocell prior to handover is independent of the call that is handed over), the drop probability is

P D (L) = P ho P B (L). E[W ] K = b (2) 2(b (1) ) 2 b (1) K(1 -ρ) (Kρ) K K! π 0 ; π -1 0 = (Kρ) K K! + (1 -ρ) K-1 i=0 (Kρ) i i! , (6)
----------------------------------------------------One can design an optimal system which jointly minimizes the two probabilities or minimizes one of the probabilities while placing a constraint on the other. Usually systems are designed with stringent requirements on P D than on P B . We note from the above calculations that P D is directly proportional to P B and will be smaller than P B by a factor which depends on the inverse of the macrocell size: 1/2D

(details in [START_REF] Ramanath | Spatial queueing analysis for mobility in pico cell networks[END_REF]). macrocells are large in dimension and hence P D can be ensured to be within the prescribed limits (the limit is a design parameter) by directly minimizing P B itself. Thus we propose to chose cell size L to minimize P B and hence equivalently b (1) :

L * N ES := L * b (1) = arg min {L:ρ(L)<1}
b (1) .

Thus for both ES and NES applications one needs to minimize the first moment of the service time, b (1) , to obtain the optimal cell size. This optimal cell size has been discussed in the previous section for fixed velocities and for velocities with small variances. The general situation is studied in the next section via numerical examples.

IV. MOBILITY EXAMPLES

In the numerical examples of this section, we consider uniformly distributed velocity profiles. The position of arrival X is also uniformly distributed in the macrocell [-D, D].

We use monto carlo simulation to estimate b (1) , b (2) and use exhaustive search to find the optimizers. In figure 2 we plot normalized values of b (1) , b (2) and E[W ] K versus L. As discussed earlier we notice that the various performance measures decrease with cell size initially, reach an optimal value and increase again from then on. In fact, all the performance measures have unique minimum at the same L. We study more details of these minimizers in the following.

In figure 3 we plot the optimal cell size (optimal with respect to moments of service time b (1) , b (2) , block and drop probabilities P We also plot L ν , which is the minimizer of ν(E n [V ], L). For small velocity variances (curves with variance equal to 1), all the minimizers are close to L ν . For large velocity variance, we notice that all the minimizers (L

* b (1) , L * b (1) , L * PB , L * PD and L * E[W ]
) are away from L ν , but however are close to each other for most cases. That is, the minimizers of expected waiting time are the same as that of block as well as drop probabilities and all of them equal L * b (1) . This suggests that even for velocity profiles with high variances, it is sufficient to optimize the average service time b (1) for both ES as well as NES calls and hence the optimal cell size again remains independent of the application. However in this case, it is not sufficient to minimize ν(E n [V ], L) but one needs to minimize b (1) directly. In Figure 4 we plot the various optimal cell sizes as a function of velocity variance. We set mean, E[V ] = 10, d 0 = 4, λ = 0.1, B h = 3.12, P = 1, µ = 5, K = 20. We once again note that all the minimizers are close to each other for many cases. We also note that all the minimizers are close to L ν for low velocity variances. We further observe that the optimal cell size increases with increase in the variance also.

Thus larger the velocities the system has to support, the larger are the optimal cell sizes.

We notice in both the figures 3 and 4 that, only the optimizer of the second moment L * b (2) , is some times different from the rest of the minimizers. However, even when L * b (2) is different from L * b (1) , the minimizer L * EW is equal to L * b (1) and thus for both the types of traffic L * b (1) gives the optimal cell size. V. CONCLUSIONS We looked at the problem of characterizing the performance of pico cell networks in the presence of mobility. We modeled various traffic types between base-stations and mobiles as different types of queues. We derived explicit expressions for expected waiting times, service times and drop/block probabilities for the various queueing models considered for both fixed as well as random velocity of mobiles. We showed that there exists an optimal cell size for a given velocity profile, which minimizes the service times for elastic applications as well as the drop and block probabilities of non-elastic applications.

We obtained (approximate) closed form expressions for this optimal cell size when the velocity variations of the mobiles is very small. We find that if the call is long enough, the optimal cell size depends mainly on the velocity profile of the mobiles, its mean and variance.; It is independent of the traffic type or duration of the calls. We show that for any fixed power of transmission, there exists a maximum velocity beyond which successful communication between the mobile and the system is not possible. This maximum possible velocity increases with the power of transmission. Further, for any given power, the optimal cell size increases when either the mean or the variance of the mobiles velocity increases.

Fig. 1 .

 1 Fig. 1. User moving with velocity V along an infinite line . of transmission. We make the following theoretical and or simulation based observations:

  By bounded convergence theorem, all b (k) are continuously differentiable (c.d.) in L (B D is almost surely c.d. while P ho,v is c.d. everywhere in L and the derivatives are uniformly bounded).

  B , P D of NES calls and the expected waiting time E[W ] K of ES calls) versus mean velocity for two different values of variance. We set d 0 = 4, λ = 0.1, B h = 2, P = 1, µ = 5, K = 20 and consider a macrocell of size D = 1000.

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Moments of the service times and the expected waiting time versus L.

  S the file size requirement and V the user velocity, distributed respectively according to P n,X , P n,V and P n,S

	of arrival,
	The elastic traffic (data traffic) is less sensitive
	so it is never blocked. Expected waiting time is the appropriate
	performance measure for the ES calls while the probability of
	a call being blocked, P B and the drop probability, i.e., the
	probability that an ongoing call is dropped before finishing,
	P D are important performance measures for NES calls. Sys-
	tems are designed with more stringent requirements on P D
	than P B .
	Arrivals: The two (ES, NES) arrivals are modeled by two
	independent Poisson arrivals with rates λ. Every arrival is
	associated with Marks (X, V, S): X ∈ [-D, D] the location

The above model is valid for systems with low signal to noise ratios. One can also consider other rate models (see[START_REF] Ramanath | Spatial queueing analysis for mobility in pico cell networks[END_REF])

In practical systems, each BS will have M backup servers to manage handovers. This means each BS can handle M parallel calls. In general M need not be equal to K, however M has to be chosen large enough to ensure negligible call drops at pico cell boundaries, taking into consideration the large number of handover associated with pico cells. With this large enough M the system's behavior will be close to the system considered in this paper (the case with M = K).

ACKNOWLEDGMENT This work is partially supported by the ANR project ECOSCells. It was done within the INRIA-Alcatel Lucent joint research lab. It was also partially supported by CEFIPRA and the DAWN associate project between IISc and INRIA. In particular, the work of Dr. Kavitha is supported by CEFIPRA and the work of Sreenath Ramanath is part of the INRIA-Alcatel Lucent selfnet project.