Ali Makke

Yves Mahéo

Nicolas Le Sommer

Towards Opportunistic Service Provisioning in Intermittently Connected Hybrid Networks

Keywords: Opportunistic Networks, Disconnected Mobile Ad hoc Networks, Service Oriented Computing

An intermittently connected mobile ad hoc hybrid network (ICHN) is one of the challenging networks induced by the proliferation of handheld devices equipped with wireless interfaces. It is formed by a number of fixed infostations, hosting service providers, and some mobile devices, hosting service clients, organized in an ad hoc network facing frequent connectivity disruptions. This paper focuses on two novel protocols that form the basis of a service provisioning platform specifically designed for ICHN. It details a service discovery protocol and a service invocation protocol that implement in particular an opportunistic routing based on a time-aware heuristic. Performance evaluation shows that the specialization of TAO is able to guarantee good performance with limited overhead.

I. INTRODUCTION

The amount and the variety of wireless communicating devices affecting our daily life is noticeably increasing. Many of these devices can communicate directly with one another, and to support multi-hop communication between the various devices that may simultaneously appear in the environment, a Mobile Ad Hoc Network (MANET) could be simply created by relying only on the collaboration among these devices and without resorting to any pre-existing infrastructure of communication. However the underlying assumption that a MANET is dense enough to form quasi-permanently a fully connected graph often proves to be unrealistic. In practice, the free movement of people coupled with the short communication range of wireless interfaces result in unpredictable disruptions in the communication links. These disruptions entail the creation of disconnected communication islands, forming a type of network known as Intermittently Connected Mobile Ad Hoc Network (ICMANET). In these conditions, it is difficult, and most often impossible, to maintain an endto-end path between two devices thanks to traditional routing protocols designed for wired networks or thanks to dynamic routing protocols such as AODV or OLSR.

Delay-tolerant networking and-more specifically for ICMANETs-opportunistic networking, have emerged as sets of techniques to cope with these issues. Hence, a number of routing protocols have been proposed in the last few years for networks that suffer from frequent and unpredictable disruptions, by implementing the "store, carry and forward" general principle. When two devices cannot communicate directly because they are not simultaneously present in the same network island, these protocols make it possible to exploit other mobile nodes as intermediate relays that can carry a copy of a message when they move and forward it afterwards to other nodes so that it eventually reaches its destination.

In the aim of extending the concept of opportunistic networking, the different resources made available by the various devices (static or mobile) that appear in the environment can be exposed as application services. This opens the way to opportunistic computing: following a Service-Oriented Architecture approach, an application can be built on top of a middleware layer that offers means to discover the services provided in the network and invoke the desired services, regardless of the fact that they are in the radio range or remote.

In our opinion, and although it has been seldom studied per se, one of the most interesting and realistic type of network in which opportunistic computing can be applied should be what we call an Intermittently Connected Hybrid Network (ICHN), that is, an infrastructure-based network with opportunistic extensions. An ICHN includes some fixed infostations (potentially connected together with some fixed infrastructure, typically the Internet) and a set of mobile devices, viewed as an ICMANET that is exploited with opportunistic networking techniques. Furthermore, the volatility and the limited resources of the mobile devices induce that the majority of the provided services are offered by the fixed infostations.

In this paper, we present two protocols that form the basis of the Time-Aware Opportunistic middleware (TAO), devoted to service provisioning in ICHNs. Indeed, TAO implements a protocol for service discovery and a protocol for service invocation, combining several well-known heuristics and mechanisms in a coherent platform. The originality of TAO lies in the fact that it takes all the specificities of ICHNs into account, namely the frequent and unpredictable communication disruptions, the mobility of numerous devices, the stability of the service providers, and the interconnection of infostations providing services.

II. RELATED WORK

Several research studies have been conducted in the domain of delay-tolerant-networking for MANETS [START_REF] Khabbaz | Disruption-Tolerant Networking: A Comprehensive Survey on Recent Developments and Persisting Challenges[END_REF] and opportunistic networking [START_REF] Conti | Opportunities in Opportunistic Computing[END_REF], but the vast majority focus on communication between mobile nodes and do not exploit the presence of fixed points in the network. In addition, these works consider general communication: sending a message from a node A to a node B, ignoring potential optimizations for communication that follow the request-response pattern of service invocation.

Indeed, several mobility-based approaches that use short range communication and that exploit mobility to deliver data have been investigated. Some of them exploit the nonrandomness mobility behavior of special nodes [START_REF] Zhao | A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks[END_REF] to deliver messages, while others rely on flooding-based approaches [START_REF] Vahdat | Epidemic Routing for Partially-Connected Ad Hoc Networks[END_REF] to disseminate the messages over the network. On the other hand, several strategies and optimizations to control the replication of messages have been devised, for example by limiting the number of disseminated copies [START_REF] Spyropoulos | Spray and Wait: an Efficient Routing Scheme for Intermittently Connected Mobile Networks[END_REF]. Some other works have investigated solutions relying on probabilistic and prediction techniques using context properties and history contacts to choose among a set of nodes the best relay(s) for each message that must be forwarded ( [START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF], [START_REF] Boldrini | Context and Resource Awareness in Opportunistic Network Data Dissemination[END_REF]). History-based algorithms can achieve high efficiency and delivery ratio, but have the major drawback of assuming that a node is able to register a large amount of contact information in its buffers.

As far as service provisioning is concerned, the research works described in the literature essentially focus on service discovery in dense MANETs, very few of them consider ICMANETs (e.g. [START_REF] Said | Toward a Platform for Service Discovery and Invocation in Disconnected Mobile Ad Hoc Networks[END_REF], [START_REF] Wang | Service Discovery for Delay Tolerant Networks[END_REF]) and, to our knowledge, none of the latter include fixed infostations in their studies. Despite the fact that these protocols consider the dynamicity of the targeted networks, they mainly assume the availability of a fully-connected underlying network which can support an endto-end path between any two nodes in the network. Obviously, such assumptions cannot be applied over ICHN, where the volatility of the devices, the short communication range of wireless interfaces, accompanied with the radio interference and the free movement of people, result low density networks with no guarantees on the end-to-end paths or on the reliability of communications. The provision of application services with this kind of opportunistic and asynchronous communications has been addressed so far only by a few research works [START_REF] Conti | Opportunities in Opportunistic Computing[END_REF], [START_REF] Conti | From opportunistic networks to opportunistic computing[END_REF], [START_REF] Sommer | A Middleware Support for Location-Based Service Discovery and Invocation in Disconnected MANETs[END_REF], [START_REF] Mahéo | Service Invocation over Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF]. Mahéo and Said [START_REF] Mahéo | Service Invocation over Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF] and Conti and Kumar [START_REF] Conti | Opportunities in Opportunistic Computing[END_REF] focus on service provisioning in opportunistic networks composed solely of mobile nodes. In [START_REF] Mahéo | Service Invocation over Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF], the authors propose content-based service discovery and invocation solutions in order to exploit the redundancy of the services offered by the mobile devices that can move freely. Conti and Kumar [START_REF] Conti | Opportunities in Opportunistic Computing[END_REF] target networks relying on social interactions between mobile nodes that act as both clients and providers of services. Due to the volatility and the limited resources of the mobile devices, the number of relevant services that can be offered by these devices are limited in comparison to those that could be offered in hybrid networks. Unlike in [START_REF] Mahéo | Service Invocation over Content-Based Communication in Disconnected Mobile Ad Hoc Networks[END_REF] and [START_REF] Conti | Opportunities in Opportunistic Computing[END_REF], in [START_REF] Sommer | A Middleware Support for Location-Based Service Discovery and Invocation in Disconnected MANETs[END_REF] the services are provided by fixed infostations in limited geographic areas. In contrast with the environments we consider, in [START_REF] Sommer | A Middleware Support for Location-Based Service Discovery and Invocation in Disconnected MANETs[END_REF], the infostations are not connected together and nodes are aware of their own location. Finally, most of the above-presented works consider networks formed only of mobile devices. In contrast, TAO also takes into account the presence of some potential fixed devices in the network.

III. TAO PROTOCOLS

In this section, we explain how the specificities of ICHNs guide the design of the architecture of TAO, and describe the key aspects of the protocols. TAO is designed as couple of protocols which aim at supporting the discovery and invocation of software services to fulfill the specific requests of the clients roaming an ICHN network. In general, in the aim of accommodating the free mobility patterns of the nodes, both TAO protocols rely on the "store, carry and forward" principle to send and receive messages. Therefore, messages will be stored in the local caches of intermediate nodes, and the mobility of those nodes is exploited to bring messages closer to their destination.

A. Service Discovery in TAO

Before being able to invoke a service hosted by an infostation, a client must be able to discover the existence of this service as well as its details. The TAO service discovery protocol (TAO-DIS) serves this purpose by allowing a client to automatically obtain the service descriptors produced and advertised by the providers in the network. Such descriptors consist in lists of properties that covers the functional and non functional aspects of service provision.

In ICHNs, infostations may be subject to a form of administrative grouping or clustering. In this paper, we consider that infostations form clusters. The infostations that are affiliated to one cluster are connected together and aware of the services proposed by each of them. Though, these infostations are unaware of the presence of other infostations in the network or of the services they provide.

The fastest way to inform all the nodes of the offered services is to perform an epidemic dissemination of the service advertisements over the whole network. However, this is a very costly operation for it imposes an excessive load on the network. In this respect, TAO-DIS proposes an optimization of the epidemic dissemination approach by benefiting from the compulsory presence of the periodic beaconing mechanism utilized for neighbor discovery in such networks. Indeed, by piggybacking the IDs of the provided services in the beacon messages and exchanging the actual descriptors of the services only when needed, we restrict the number of exchanged messages while maintaining the same dissemination performance. For that, we represent every service by a unique identifier or a "hashkey". Ensuring unique hashkeys is obtained by applying a hash function on the concatenation of the different properties describing the service and the infostation ID providing the service. Thus, for every service descriptor s i , the hashkey generation process is defined by:

K si = H(F unctional+N onF unctional+Inf ostationID)
Furthermore, since every infostation (or cluster of infostations) might provide more than one service, we define a "service guide" (SG) as a catalog that lists the descriptors of all the provided services by a cluster of infostations. The main components of the SG are a set of entries each of which details a provided service, the time tag that represents the creation date of this exact version of the SG, the cluster ID, and the unique SG hashkey defined by:

K SG = H( i=N i=1 K si )
Where is the string concatenation operation and s i is a service descriptor entry.

In order to avoid the excessive exchange of unnecessary messages, we introduce the tuple <SG hashkey, Cluster ID, Time Tag> in the header of the beacon messages. Thus, the comparison between the SG hashkey already registered in the local cache of a node and the value received from a neighbor will result in sending the newest version of the SG only if any difference is detected between the two values. This difference requires a reaction only from the node in possession of the newer version of the SG, where this is decided by comparing the two time tags. Therefore, any change in the SG (addition, withdrawal or modification of a service descriptor) will yield a modification of the SG hashkey. As a result, the modified part of the SG is propagated as soon as it happens.

In summary, in TAO-DIS, we perform a controlled and opportunistic dissemination of service advertisements in the network, where the actual exchange of a SG only occurs when two nodes carrying two different versions of the same SG enter in the transmission range of each other.

B. Service Invocation in TAO

The second part of TAO is an invocation protocol (TAO-INV) that allows a mobile client to send a request to a service provider and to receive a response back from this provider following the "store, carry and forward" principle. The primary objective behind the design of TAO-INV is estimating the ability of intermediate nodes to deliver the messages from a client device to the infostations as they represent the main providers of services in an ICHN.

When a client (or an application on the client's device) discovers the various services present in the network, it chooses the service that best matches its needs and generates an "invocation message" to invoke this service on its provider. In order to avoid the too costly epidemic forwarding of the invocation messages in the network, TAO-INV strives to evaluate the neighbors of a node (i.e., the nodes present in its transmission range) so as to classify them as good or bad carriers, in order to determine the number of copies that should be generated and the relay nodes that should contribute in transmitting these messages toward the infostation. A neighbor is considered a good carrier if it is capable of relaying the messages from the client closer to the infostation. In practice, TAO implements a time stamping-based heuristic that classifies a node as a good carrier if its last date of contact with an infostation is more recent than the others.

Consequently, the node sets a threshold equal to its last contact time with the infostation. The neighbors having a more recent contact time with the infostation are classified as good carriers and will receive copies of the invocation messages. In addition, the value of the threshold is augmented and set equal to the value of the most recent contact time of a neighbor with the infostation, in the aim of reducing the dissemination of the invocation messages.

However, as we target highly disrupted networks, it might be sometimes risky to forward copies exclusively to good carriers, especially if the source node is located remotely from an infostation, with a huge gap separating them. Hence, in TAO-INV, each mobile node has a stock of a few number of copies dedicated to bad carriers. This number of copies is limited in order to avoid network overload and resource consumption on mobile devices.

As introduced before, the only piece of information needed by TAO-INV to perform the selection process of good and bad carriers is the last contact time of the neighbors with an infostation. It is piggy-backed in the beacon messages that are periodically exchanged among the nodes in the network. By that, we limit the load imposed by TAO-INV on the network and eliminate the exchange of unnecessary messages.

After the infostation has received the invocation message, it generates a "service response" and destines it for the client that requested the service. In order to send the response back toward this client, the infostation relies on the information included in the invocation message it has just received. In fact, the invocation message records in its header the path it has traversed (i.e., the order of the nodes that have contributed in relaying it) to move from the client toward the infostation. Hence, TAO-INV implements a reverse source routing mechanism to build the path that should be traveled back by the response message from the infostation toward the client. If the source routing fails, because an intermediate node becomes unreachable, the carrier of the service response keeps this message in its local cache until encountering any of the nodes mentioned in the header of the service response message. All of the new carriers will try to resume the source routing process.

Finally, TAO-INV makes it possible to control the propagation of messages in the network using two parameters: a lifetime and a number of hops. When the lifetime is expired or when the number of hops is zero, the message is automatically removed from the local cache and will not be forwarded anymore. Moreover, in order to reduce the dissemination of service requests in the network, we have implemented in TAO-INV a network healing mechanism that exploits the request/response paradigm. When a carrier receives a response for a request it has locally, it removes the request from its local cache and stops forwarding this request. Thus, progressively, the request will no longer be forwarded in the network.

IV. EVALUATION

In this section, we present the service discovery performance evaluation of TAO, discussing the obtained results in details. The metrics measured for TAO-INV are the satisfaction ratio (the number of service requests for which a client node receives a response over the total number of service requests sent by clients) and the service delivery delay (the delay between the emission of the service request and the actual reception of the corresponding service response). As for TAO-DIS, we measured the average dissemination delay (the delay between the emission of the SG by the infostation and its actual reception by the mobile clients). For both TAO-INV and TAO-DIS, we also evaluated the network load, i.e., the overall number of messages exchanged between nodes during the simulation. Only messages carrying data related to the protocols were counted.

A. Simulation Setup

We used the OMNeT++ network simulator [START_REF] Varga | The OMNeT++ Discrete Event Simulation System[END_REF] to conduct experiments that involved service providers, service clients and simple relay nodes as well as a number of fixed infostations. A first series of simulations exploited purely simulated movements with up to 300 nodes. In an area of 1 km 2 , a simple hybrid network was deployed, that was composed of one infostation (in the center of the area) and a set of mobile devices carried by pedestrians (moving according to a random way-point mobility model, with a speed set to 0.5 m/s). A subset of these pedestrians acted as clients that requested services from the infostation, the rest of the mobile devices serving as potential relays. The second environment was based on the exploitation of real movement data. We used a data set from the CRAWDAD repository that contains 92 GPS traces of movement of students in a campus [START_REF] Rhee | CRAW-DAD data set ncsu/mobilitymodels (v. 2009-07-23[END_REF]. Combined with the use of OMNeT++ simulator, this makes it possible to take into account low-level constraints (MAC level and physical level). plots number of messages over timeFor the sake of comparison with the artificial environment, we added 3 infostations in the 4×4 km 2 area, so that the infostations were distant from each other by more than 1 km. Again, roles of clients and relays were assigned to the mobile nodes.

In both simulation environments, the communication range of the mobile devices and of the infostation was set approximately to 30 m. In the experiments aiming at evaluating TAO-INV, the mobile clients invoked the desired services every 3 minutes, omitting some requests randomly. For the evaluation of TAO-DIS, the number of services descriptors produced by the infostation varied between 1 and 3. We did not assign a lifetime and a maximum number of hops to the messages as these values are directly related with the nature of the provided services and their relative applications. Thus, the number of messages that roam the network increases continuously during the simulation. A warm up period of 10 minutes was used in the beginning of the simulations before the infostation started to generate the SG (respectively before clients started to generate request messages). Each simulation ran then during one hour before the infostation ceased to produce service descriptors (respectively clients ceased to emit invocation requests). Finally, the simulation proceeded for 10 minutes to allow all the messages to be delivered. In these simulations we consider an infinite buffer size for both mobile devices and infostations.

B. Evaluation of TAO-DIS

For a first evaluation of TAO-DIS, we focused on the average delay of dissemination of the SG. The curves in Figure 1 show the cumulative percentage of clients that have received the SG with respect to time, for four densities of mobiles nodes. In this case study, the infostation generated one SG at time = 600 seconds. The epidemic nature of the dissemination of the SG can be observed (the performance is actually very close to the one of a plain flooding). Expectedly, TAO-DIS can benefit from the impact of the density of the network on the efficiency of the dissemination. For example, to reach 95% of the nodes, 1150 s are required with 50 nodes, whereas 275 s are sufficient with 300 nodes).

In the next experiment we focused our attention on the total volume of traffic generated by all the nodes present in the network in order to ensure a full dissemination of the SG. We considered two case studies: in the first one the infostation generated only one SG at the beginning of the experiment, while in the second one the infostation produced three different service descriptors in three successive steps, thus leading to three different versions of the SG. We introduced a 1000-second time gap between the generation of the service descriptors in order to track the dissemination of each version of the SG. Moreover, in each case study we varied the number of mobile nodes forming the network from 50 to 300 to change the density of the network and thus the rate of contact among the different nodes in the network. Figure 2 plots the evolution of the total number of exchanged SG update messages over time. It is easy to see that, as the number of mobile nodes forming the network increases (from 50 to 300 in our case), the dissemination speed of the SG significantly increases. Nevertheless, we notice that our protocol retains its scalability: the number of exchanged messages remains of the order of the number of nodes roaming the network. On the other hand, coherent with what was observed before, when the density of the network is low, the speed of dissemination of the SG is low as we notice that the exchange of messages was stretched over a larger period of time. These results are 2b. When having a large number of nodes in the network, the SG was fully disseminated over all the nodes before the creation of the new service descriptor (i.e., the new version of the SG). On the contrary, when having only 50 nodes roaming the network we can clearly see the dissemination of more than one version of the SG at the same period of time. Finally, these results show that the overall load imposed over the network is limited and the algorithm implemented in TAO-DIS ensures a fast dissemination of the SG over all the mobile nodes present in the network.

C. Evaluation of TAO-INV

The curves in Figure 3 present the variation of the satisfaction ratio for TAO-INV when the number of mobile nodes in the network increase from 20 to 92, and the number of clients from 20 to 60 while moving according to the real movement traces. The interesting point to observe is that, in all cases, the satisfaction ratio reaches a high value within the duration of the simulation (95% with 60 clients). Figures 3 also represents the distribution of the service delivery delays for TAO-INV in the real traces scenario. We notice that the majority of the round trip durations fall in the 1 to 10 seconds period when having 10, 30 and 60 clients in the network. Indeed, since TAO does not rely on an exchange of summary vectors among nodes, it is able to preserve a lower average round trip time than other more general approaches. Concerning the load imposed by TAO over the network, despite the increase in the number of mobile nodes roaming the network, the increase in the number of exchanged messages is limited. The main explanation lies in the fact that sending a request with TAO-INVO is adapted to the hybrid characteristics of the network, as it is specialized for sending requests only to the infostations. Indeed, a TAO node only embeds in the beaconing message the last date of contact with the infostation. Moreover, the time heuristic implemented in TAO permits somehow to reflect the notion of distance separating the mobile node from the infostation.

V. CONCLUSION

In this paper, we have presented TAO-INV and TAO-DIS, two protocols dedicated to service provisioning in ICHNs. The originality of these protocols lies in the fact that their design strives to exploit the pattern of communication induced by invocations as well as the fact that an ICHN includes not only intermittently connected mobile clients but also fixed infostations that host service providers. This is achieved mainly thanks to a simple heuristic that exploits the last date of contact between a mobile device and an infostation. Simulation experiments based in particular on real mobility traces data showed that TAO is able to guarantee good performance with limited overhead.

Figure 1 .

 1 Figure 1. Evaluation of TAO-DIS: Average Dissemination Delay

  One version of the service guide (b) Three versions of the service guide

Figure 2 .

 2 Figure 2. Evaluation of TAO-DIS: Network Load

Figure 3 .

 3 Figure 3. Evaluation of TAO-INV


Diogo Lima
email: dlima@lasige.di.fc.ul.pt

François Hugo Miranda
email: hmiranda@di.fc.ul.pt

François Taïani
email: francois.taiani@irisa.fr

Towards a new model for cyber foraging

Keywords: C.2.4 [Distributed Systems]: Client/server; D.4.7 [Software]: Operating System-Organization and Design Cyber Foraging, Surrogate, Remote Execution, Wireless

INTRODUCTION

Cyber foraging seeks to overcome the limitations of wireless mobile devices [START_REF] Balan | The case for cyber foraging[END_REF] by opportunistically offloading resource intensive tasks on nearby resourceful surrogate computers. Cyber foraging is particularly useful for CPUintensive computations running on devices with either limited capabilities or constrained energy resources. Such computations include mobile interactive multimedia applications, that combine rich media with on-line analysis tasks. An example is the cognitive assistance scenario presented in [START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF], where a face and object recognition application embedded in smart glasses helps assisting Alzheimer's patients in remembering people and everyday tasks.

Cyber foraging system must balance the benefits of remote executions with the additional communication costs (energy, latency) introduced by delegating parts of an application's computation to remote surrogates. One source of overhead stems from the need to exchange enough information about the state of a computation to allow its remote execution. Existing cyber foraging systems are generally oblivious or make little use of the applications' state at the client's side. In this paper, we argue that this knowledge can be used to enhance performance by reducing the number of remote invocations and the volume of data transferred, thus reducing the latency of the computation and the mobile device's energy consumption.

In this paper, we first introduce cyber foraging in more detail (Sec. 2). In Sec. 3 we present a case study of an existing face recognition application and discuss how cyber foraging with state-sharing could help improve its execution. Section 4 sketches the high-level blueprint of a cyber foraging architecture designed to enable state sharing. Finally, in Sec. 5 we discuss how this blueprint offers a path forward to materialize the benefits identified by our case study. Section 6 concludes the paper.

BACKGROUND

Existing cyber foraging systems have been exploiting three main mechanims to realize their benefits: Virtual Machine images, mobile code and Remote Procedure Calls (RPC). In the following, we discuss each of them in more detail.

Virtual Machines

In this approach, the mobile device prepares a virtual machine image of its own execution and sends it to the surrogates [START_REF] Chun | Clonecloud: Elastic execution between mobile device and cloud[END_REF][START_REF] Chun | Augmented smartphone applications through clone cloud execution[END_REF][START_REF] Goyal | A lightweight secure cyber foraging infrastructure for resource-constrained devices[END_REF][START_REF] Su | Slingshot: Deploying stateful services in wireless hotspots[END_REF][START_REF] Ha | Just-in-time provisioning for cyber foraging[END_REF][START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF]. This solution is flexible in the sense that the set of services used by the device can be uploaded to the surrogates upon demand or in anticipation.

In CloneCloud [START_REF] Chun | Clonecloud: Elastic execution between mobile device and cloud[END_REF][START_REF] Chun | Augmented smartphone applications through clone cloud execution[END_REF] the VM is created in the cloud, and is synchronized either periodically or on-demand with the mobile device. Applications can either be entirely offloaded or executed cooperatively on both entities.

In [START_REF] Goyal | A lightweight secure cyber foraging infrastructure for resource-constrained devices[END_REF], a centralised registrar helps mobile devices locate adequate surrogates, for example to ensure portability. An interesting aspect of this model is that surrogates are expected to retrieve from the Internet the application software required by the clients for remote execution.

Slingshot [START_REF] Su | Slingshot: Deploying stateful services in wireless hotspots[END_REF] assumes that both clients and surrogates have ubiquitous Internet connectivity and defines two classes of surrogates. The first-class replica is an Internet connected server controlled by the mobile user. Second-class replicas are temporary servers available on the mobile device's local network and which retrieve the virtual machine image from the first-class replica. To circumvent the relatively low speed and high latencies of Internet links when compared to local Wi-Fi, Slingshot prefers second-class replicas.

Satyanarayanan's vision [START_REF] Ha | Just-in-time provisioning for cyber foraging[END_REF][START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF] equally relies on full Virtual Machine migration.

Rather than relying on a distant "cloud", a device can obtain a fast response from a nearby resource-rich cluster, here called cloudlet. The mobile device operates as a thin client, with all significant computation occurring in the cloudlet. The use of low latency, high-bandwidth network link allows for near realtime interactions, a powerful feature of this approach.

These various approaches demonstrate the flexibility of Virtual Machines when applied to cyber foraging. However, designing a VM-based approach is not a trivial task. Their main drawback is the initialization and migration overhead they typically incur due to the time and data size required to transfer and boot up a virtual machine image elsewhere.

Mobile Code

Mobile code offers an alternative to Virtual Machines in which only part of the code is transferred to and executed on surrogate machines. This avoids the need to replicate the full state of the mobile device, as a Virtual machine would.

In Scavenger [START_REF] Kristensen | Scavenger: Transparent development of efficient cyber foraging applications[END_REF], for instance, the source code to be executed as part of the task offloading is uploaded to the surrogates by the mobile devices. Surrogates run a daemon which is responsible for providing an execution environment for the mobile code. The offloading process is automatic. The application programmer annotates each method that may be remotely executed and lets the system decide which functions are transferred to the surrogates. Additionally, the developer can also create mobile code tasks manually. This is done by asking for available surrogates, check whether the task is already installed on that surrogate, install it if necessary and finally, invoke the task at the surrogate.

Compared to the Virtual Machine approach, mobile code is more lightweight. Given that the source code should not exceed a few kilobytes in size, mobile code has a negligible initialization overhead, in contrast with virtual machine images, one order of magnitude larger. However, mobile code is bounded to a specific language, thus limiting the portability needed to ensure a seamless and transparent execution environment for all mobile devices.

Remote Procedure Calls (RPC)

As with mobile code, RPC-based cyber foraging avoids transferring a device's full state. In the RPC approach, client applications are partitioned into locally executable code and remotely executable services. In contrast to Mobile Code approaches, these services are pre-installed on surrogate computers who offer a RPC like API.

In Spectra [START_REF] Flinn | Balancing performance, energy, and quality in pervasive computing[END_REF], for example, the mobile clients run a specific Spectra client, which follows one of a set of possible execution plans for an application. An execution plan lists one or more services, which provide the actual application code that is executed on the surrogates. The execution plan concept was refined in Chroma [START_REF] Balan | The case for cyber foraging[END_REF][START_REF] Balan | Simplifying cyber foraging for mobile devices[END_REF] with the introduction of tactics. In a tactics file, the developer specifies the RPC functions that may be called during that operation execution, and the different ways that these functions may be combined to solve the operation. Nevertheless, on both of these systems it is up to the programmer to code the remotely executable services as stand-alone applications to be installed on the surrogates.

Other RPC-based systems include MAUI [START_REF] Cuervo | Maui: Making smartphones last longer with code offload[END_REF] and Odessa [START_REF] Ra | Odessa: Enabling interactive perception applications on mobile devices[END_REF] which aim at automatically partitioning application's methods. Applications rely on the MAUI framework to decide which methods should be offloaded.

This decision is based upon a call graph created off-line to assess the computing and energy costs of each method and the size and energy consumed to transfer the state remotely. Odessa, on the other hand, proposes a runtime solution that automatically and adaptively makes offloading and parallelism decisions. Instead of estimating costs based on off-line graphs, Odessa uses a greedy algorithm that periodically gathers information from a profiler to estimate the bottleneck of applications in the current configuration. This information is used to estimate whether offloading or increasing the parallelism level of the bottleneck stage would improve performance.

Like the mobile code approach, this model induces a negligible initialization overhead since services are already installed and made available on surrogates. RPCs also offer the portability needed to ensure a seamless and transparent execution environment for all mobile devices by being platform and programming language agnostic.

Limitations

We consider that a cyber foraging system should exhibit the following properties:

Flexibility so that it can address the requirements of a broad range of applications. Each mobile application has its own set of requirements and the system must provide enough services, functions or libraries to fulfill those requirements.

Lightweight in terms of initialization and transfer overhead. If the boot time or the volume of data transferred is significant, the system becomes unattractive to users since they might have left the surrogate's area by the time initialization is finished or because setting up the remote execution would consume as much energy as executing applications locally.

Portability so that mobile applications do not have to be bounded to a specific execution environment. The system must be able to operate with mobile devices with distinct characteristics and applications using several programming languages.

Table 1 summarizes the characteristics of the cyber foraging paradigms surveyed. Both mobile code and the RPC approaches are more lightweight than Virtual Machine images, which require a significant initialization overhead from the data transfer. RPC is unique in that it is not bounded to a specific platform or programming language. This is of particular importance given that a cyber foraging system must be able to deal with a broad range of mobile device manufacturers and programming languages. In this sense, we consider the RPC-based approach to be the most well suited to implement a cyber foraging system.

Interestingly, most of the systems we have presented are oblivious or have very little knowledge of the application's state at the client side. However, this knowledge can contribute to improve the offloading process performance by reducing the volume of data transferred. Exceptions [START_REF] Mazzola Paluska | Vision: A lightweight computing model for fine-grained cloud computing[END_REF]. In MAUI, each method invocation has an additional input parameter used to transfer the application state from the mobile device to the surrogate. The system only transfers incremental deltas of the application state, thus contributing to reduce the latency and traffic. In CloneCloud, when an execution of a process on the mobile device reaches a migration point, the executing thread is suspended and its state sent to the synchronized clone. This state is composed by the virtual state, program counter, registers, and stack. In the work presented in [START_REF] Mazzola Paluska | Vision: A lightweight computing model for fine-grained cloud computing[END_REF], the application state is used within a more general abstraction called tasklet which represents a thread of computation.

Model Flexible Lightweight Portable VM image ✦ Mobile code ✦ ✦ RPC ✦ ✦ ✦
Tasklets are composed of chunks, fixed-sized blocks that include data, code and the machine runtime state needed to execute the tasklet on the surrogates. We envision developing a more advanced version of state sharing by allowing surrogates to keep a local copy of an application's state between successive remote calls. Furthermore, we envisage that this approach can be extended to share the state of multiple application instances running on the same surrogate on behalf of different users, and exploit synergies between these users' different needs.

CASE STUDY

Face and speech recognition as well as language translation are some of the applications that would benefit from low-latency, high-bandwidth wireless access to computing resources.

In [START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF], the authors present the Cognitive Assistance scenario, where software for scene interpretation, face and object recognition are combined with a camera embedded into the eyeglass frame of a user and with earphones for audio feedback. The goal of the application is to whisper objects and person names to assist Alzheimer's patients in recognizing people and everyday objects.

Face Recognition with OpenCV is an open source application available on Google Play that relies on the OpenCV 1 computer vision software library. When running the application, the mobile device's camera is always on. The application has two operation modes: training and searching. The training mode allows the user to register a new person. When the application detects a face, the user saves it together with a name to be associated. The searching mode corresponds to the face recognition stage where each time a face is detected in a frame, the application compares it with the faces recorded and returns the name of the matched one (if any).

Application Experimentation

To understand the impact of face recognition on the resource consumption of mobile devices, the Face Recognition with OpenCV application was experimented in a Nexus 7 Android Virtual Device (AVD) running Android version 4.4

1 http://opencv.org Evaluation showed that when neither the face recognition nor any other application is running on the device, the only processes running belong to the Operating System and consume 10% of the CPU time. Once the face recognition application is running, the CPU usage rises to 98%. This confirms that face recognition makes an important use of the CPU, making it a good candidate to benefit from cyber foraging. Figure 1, which depicts the CPU load distribution by the processes when the Face Recognition with OpenCV application is running, shows that almost 90% of the CPU load that was previously idle is taken mainly by three different processes: facerecognition at the client and kernel level and surfaceflinger.

Surfaceflinger is an Android system service responsible for displaying all application and system surfaces on the mobile device's screen. The 37% of the CPU time it consumes can be attributed to its constant display of the frames captured by the device's camera. Therefore, the availability of a cyber foraging system could not help reducing this overhead. However, a cyber foraging system could contribute to reduce the 45% of CPU load spent by both facerecognition processes. Figure 2 depicts the top branches of the graph obtained from method profiling in run-time. Graph nodes are of the form: [ref ] callname (<inc-ms>, <exc-ms>,<numcalls>), where ref is the call reference number; inc-ms (resp. exc-ms) are the inclusive (resp. exclusive) elapsed time in milliseconds, which counts the time spent in the current method and child methods (resp. not including any child methods); and numcalls is the number of calls.

The figure shows two main branches starting from the program's entry point (the root of the tree), each consuming around 50% of the application's CPU time. The right-hand side branch executes methods from the android.view package, resposible for the screen layout and user interaction. The importance of this package is attributed to the camera's continuous usage, whose frames are displayed in real-time to the user. The left-hand size branch is concerned with OpenCV library methods. The leaf of this branch is a method called detectMultiScale, which belongs to the CascadeClassifier class from the OpenCV

Discussion

The method detectMultiScale detects objects in a video stream.

Its CPU usage suggests that it would be a good candidate to be installed and invoked on a surrogate computer to extend the battery life of the mobile device. In such case, providing the surrogate with the application's active operation mode (training or searching), the face recognition algorithm being used and the list of the user's trained faces would allow the surrogate to continue executing the application once the complex task of face detection is finished. State shared could equally include the personal notes associated to each face as well as a list of the latest faces observed to speed up face recognition.

To decide whether offloading this method would save energy and improve responsiveness, one must consider whether the cost of sending frames (compressed using an appropriate video encoding) to the surrogate would be balanced out by the CPU time saved from not executing detectMultiScale on the mobile device. This comparison remains to be performed. However, it should be noted that the application use of streaming does not change this equation considerably, when compared to a design that would only use on-demand static frames for face recognition. Streaming introduces the possibility to use standard video compression techniques to communicate with the surrogate, and renders the potential benefits of cyber foraging more important, but the above trade-off remains.

SYSTEM ARCHITECTURE

In our system model we assume that surrogates are resourceful devices, without power constraints, making available both computing power and storage to the clients. Our system is composed of surrogates connected to each other and located at one-hop WiFi distance of the clients. Clients invoke services available on surrogates to alleviate their computing power using an RPC like model. This model is supported by experiences observed in [START_REF] Barbera | To offload or not to offload? the bandwidth and energy costs of mobile cloud computing[END_REF] which claim that smartphone users are almost 50% of the time connected to a WiFi access point.

Application Partitioning

We claim that it should not be entirely up to the mobile application developer to assume the responsibility of application partitioning.

With the proliferation of various development tools for mobile applications, the number of application programmers has largely increased with very uneven knowledge basis. As a consequence, the awareness to structure an application to take advantage of cyber foraging may significantly vary, which could result in under-performing mobile applications. Moreover, even the most experienced developer cannot fully anticipate the environment conditions in which the application will run. On the other side, fully automatic solutions may risk to be inaccurate or add a significant overhead on mobile devices from building complex cost assessment models. Therefore, we opted for an adaptive programmer driven partitioning model. We propose to use annotations written by the developer to partition an application from its bytecode into remotely executable methods.

A novelty of our model comparing to previous solutions is the presence of an offloading interest for each method. In contrast with previous systems which only used a binary ("yes" or "no") offloading decision, we assign each annotated method with an offloading interest between 0 and 1. Decisions will weight the offloading interest with criteria such as the current network conditions (periodically measured), the current execution load and the list of available services provided by a surrogate, which are announced at discovery time.

State Sharing

In our approach, we envision clients invoking different services on different surrogates for a same application instance and surrogates having access and keeping application state to provide several services. MAUI, CloneCloud and the model proposed by Paluska et al. [START_REF] Mazzola Paluska | Vision: A lightweight computing model for fine-grained cloud computing[END_REF] are examples of frameworks that consider state sharing between clients and surrogates. As firstly proposed by Paluska et al., we envision that the applications' state will be expressed as chunks, a fixed-sized data block with an unique identifier. However, Paluska's et al. solution requires that the machine runtime state is always sent along with the code and the data, and CloneCloud requires sending the virtual state, program counter, registers and stack. MAUI improves this process by sending incremental deltas to its stored state.

Chunks are built by the clients and then sent to the surrogates who keep them. However, in contrast with [START_REF] Mazzola Paluska | Vision: A lightweight computing model for fine-grained cloud computing[END_REF] our approach decouples the control flow from the data flow. Moreover, with the objective of reducing even further the communication burden, our model defines different synchronization levels for chunks: Eager chunks will always have to be up to date at the surrogates. In contrast, lazy chunks can be used for execution by a surrogate even with previous versions and updated at a more favorable moment (e.g. when bandwidth or RSSI is high).

Considering the execution of the application discussed in the previous section, these chunks could be instances of the objects used by the OpenCV methods. In particular, OpenCV uses mainly two methods for face detection and face recognition. The detectMultiScale that allows the face detection and the predict method that executes face recognition. This last method relies on an object from the FaceRecognizer class. In a cyber foraging scenario, chunks could be attributes or fragments of such object. For example, FaceRecognizer can operate with different recognition algorithms such as: LBPH, Fisher or Eigen and maintain the list of trained faces. Keeping on surrogates the active face recognition algorithm along with the set of trained faces as chunks would avoid the user to send them along with every frame, as well as every time the user starts the application. In such case, since the active recognizing algorithm may be transparent for most users, this could be implemented as a lazy chunk, while images and labels would be eager chunks since missing their changes would have a direct impact on the user's experience.

Architecture overview

Figure 3 depicts a broader view of the invocation and state sharing model followed on our approach using the Face Recognition with OpenCV application as an example. After the application partitioning is done and methods such as detectMultiScale and predict are identified as offloading candidates, the decision of delegating those methods is taken by a scheduler present in the client's mobile device, called Task Distributor. For example, the detectMultiScale method can be executed either locally or remotely depending of the current bandwidth, the surrogate's current execution load and the number of cached faces. Whether offloaded or not, its execution is performed in a component called Tasklet Executor, available on both parties.

If offloaded to a surrogate, the method invocation must contain the name of the function requested and the IDs of the chunks needed to complete that execution. To illustrate our example, let us assume that we have a Chunk C1 representing the application's current operation mode (set to searching), a Chunk C2 containing the current face recognition algorithm used and a Chunk C3 containing the image recorded and the associated label of a user's relative. Upon receiving a method invocation, the surrogate starts by requesting the needed functions (detectMultiScale for example) and C1, C2 and C3 to their respective manager components Service Locator and Chunk Manager. To overcome the possibility of a missing chunk, the surrogate can ask the mobile device to build and send it. In the figure, we are assuming that C1 is missing in the surrogate. In response to the request sent by the surrogate, the Chunk Builder component at the mobile device creates and send it back to the surrogate. Once the execution is finished, results are sent back to the mobile device along with state changed eager chunks. An order for searching known faces is an interesting example of a lazy chunk, given that having it up to date at the surrogate could speed up the recognition process but it would not be critical for performance.

Clients may communicate with surrogates using distinct protocols (GSM, Bluetooth or WiFi).

The Network Dispatcher layer is responsible for abstracting these network conditions from the rest of the components.

FUTURE WORK

A cyber foraging model with the characteristics above raises a number of interesting research challenges. This section addresses some of them, arranged in different lines.

One class is related with mobile application experimentation, which is currently at an early stage. A larger scale study has to be conducted on mobile applications in order to identify the common characteristics of applications that are suitable for cyber foraging and those that are not. Metrics have to be defined for computing complexity, data transfer sizes among others that might help classify applications as good remote execution candidates. Problems rest on the identification and development of the library that the surrogates should make available to their users. Research must weight efficiency (knowing that the most complete functions require few interactions between mobile devices and surrogates) and applicability (given that the more simple the function, the bigger is the probability that the function can be used in more than one application).

Even if a mobile application is well suited for cyber foraging, the performance of the system will be strongly dependent of the latency of the communication between clients and surrogates. A second line of research consists in investigating an efficient algorithm allowing surrogates to anticipate a client's arrival, thus contributing to improve latency. This will imply the combination of route prediction algorithms with movement pattern studies and profile history to build predictions about users arriving close to a determined surrogate or the sequence of surrogates to be followed (consider for example a shopping mall, where the majority of users follow one of a few routes).

Ensuring user privacy is one of the more challenging questions. End-to-end encryption of messages is a basic security measure addressing this problem. However, security needs to be considered on a broader scale to include chunk security. Consider for example the reuse of a face recognition application by different users in proximity, trying to identify some bystander. In such a scenario, one must consider distinct privacy levels. The biometrics that are fed to the task as well as its results can be made publicly available. However, personal comments about the bystander, retrieved from a user's personal database must be kept confidential and disclosed exclusively for the user that created them. The mechanisms to associate the different privacy levels to tasks and chunks at the programming level and its enforcement in run-time will be equally subject of analysis.

Figure 1 :

 1 Figure 1: CPU load by process when running the Face Recognition application

Figure 2 :

 2 Figure 2: Method invocation graph of the facerecognition process

Table 1 :

 1 Proprieties of each paradigm are MAUI, CloneCloud and the architecture proposed by Paluska et al.

CONCLUSIONS

In this paper we have argued that state sharing can be used in cyber foraging to enhance performance by reducing the volume of data transferred. To make this point we presented a case study of an existing face recognition application and discussed how cyber foraging with state sharing would help improving its execution. We then sketched a high-level blueprint of a cyber foraging architecture designed to enable that state sharing. Finally, we have described the issues that will have to be addressed in order to materialize our proposed high-level architecture into a concrete framework.

ACKNOWLEDGMENTS