Malika Boulkenafed
email: malika.boulkenafed@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

A Middleware Service for Mobile Ad Hoc Data Sharing, Enhancing Data Availability

Keywords: Middleware services, data availability, collaborative work, ad hoc networks, mobile computing, wireless networks

It is now commonplace for a person to use lightweight wireless computing devices, and to make his/her data available to other people's devices using todays various networking capabilities (infrastructurebased WLAN, ad hoc WLAN, GSM, etc.). Middleware platforms initially developed for stationary distributed systems cannot be directly applied in such a mobile environment. They must adapt their functionalities so as to best cope with possible resource constraints (energy, storage) of mobile terminals as well as with the various types of wireless networks that are now available. In this paper, we present a middleware service that allows collaborative data sharing among ad hoc groups that are dynamically formed according to the connectivity achieved by the ad hoc WLAN. Our service enhances, in particular, data availability within mobile ad hoc collaborative groups, and integrates a new adaptive data replication protocol for mobile terminals, combining both optimistic and conservative schemes. Our service has been designed so as to minimize energy consumption and optimize data availability and storage consumption.

Introduction

Given the current advances in the field of mobile computing concerning both lightweight devices and wireless networking capabilities, middleware infrastructures have to adapt their services to better support this mobile wireless environment and the new classes of applications that result from it. Lightweight computing devices (e.g., PDA 1 , third generation mobile phones, hand-held computers, etc.) are becoming increasingly available for a large range of users. In addition, low-power and short-range wireless connectivity among these devices (e.g., Bluetooth, IEEE 802.11, MANET 2 , HiperLAN, OWS 3 , and HomeRF in the context of PAN 4 ) are increasingly flexible, especially with the advent of protocols supporting ad hoc communication (e.g., Bluetooth, IEEE 802.11, MANET) and enabling a collection of mobile hosts with wireless network interfaces to form a temporary network without the need for any established infrastructure or centralized administration [START_REF] Gibson | The Mobile Communication Handbook[END_REF], [START_REF] Imielinski | Mobile Computing[END_REF]. Middleware infrastructures initially developed for stationary distributed systems cannot be directly applied in such a mobile environment. Therefore, widely accepted middleware platforms have specified their wireless or mobile variants (e.g., wireless CORBA). Indeed, mobile devices are resource-scarce (low amount of persistent storage, limited battery power, etc.). It is therefore necessary to adapt all system functionalities and in particular functionalities related to data management (adequate coherency and replication management protocols), which is the focus of our paper. In this context, a number of services and/or protocols have been proposed regarding specific problems raised by mobility, such as disconnected operations (e.g., [START_REF] Ekenstam | The bengal database replication system[END_REF], [START_REF] Guy | Rumor: Mobile data access through optimistic peer-to-peer replication[END_REF], [START_REF] Kubiatowicz | Oceanstore: An architecture for global-scale persistent storage[END_REF], [START_REF] Kumar | Supporting application-specific resolution in an optimistically replicated file system[END_REF], [START_REF] Mascolo | Xmiddle: an xml based approach for incremental code mobility and update[END_REF], [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF], [START_REF] Reiher | Peer-to-peer reconciliation based replication for mobile computers[END_REF], [START_REF] Satyanarayanan | Coda: A highly available file system for a distributed workstation environment[END_REF], [START_REF] Yu | Design and evaluation of a continuous consistency model for replicated services[END_REF] and discovery of services [START_REF] Bettstetter | A comparison of service discovery protocols and implementation of the service location protocol[END_REF].

Since it became commonplace to find users equipped with lightweight devices and short-range wireless interfaces, new needs for adapted functionalities that account with the various connectivities enabled by today's networking capabilities have emerged. There are scenarios in which no wired or wireless networking infrastructure is available, either because it may be economically impractical or physically impossible to provide the necessary infrastructure. Therefore, ad hoc networks are particularly suitable. Ad hoc networks represent the latest trend in distributed computing; work in this area has mainly dealt with routing protocols [START_REF] Adler | Efficient communication strategies for adhoc wireless networks[END_REF], [START_REF] Marti | Mitigating routing misbehavior in mobile ad hoc networks[END_REF], [START_REF] Qayyum | Analysis and evaluation of channel access schemes and routing protocols for wireless networks[END_REF], [START_REF] Luo | A self-coordinating approach to distributed fair queueing in ad hoc wireless networks[END_REF] without taking into account data management within these networks. However, ad hoc networks are particularly well suited to form small groups of devices that are in the communication range of each other, in order to share and manipulate common data when the fixed networking infrastructure is not available. This requires devising adequate data management that allows the user to work in a collaborative manner and to benefit from the flexibility of ad hoc networks, thus supporting the notion of mobile collaborative ad hoc groups.

An example of mobile collaborative ad hoc group is a working meeting regarding some international cooperation (e.g., a European research project), which takes place in a hotel conference room, somewhere in a convenient destination easily reachable by all partners. An other example is a network gaming session, which may happen at any place (e.g., a cafeteria, train, lounge, etc.). Consider the first example. Representatives from each project partner meet periodically to work in a collaborative manner on the project. In order to facilitate travel arrangement, project partners choose a European meeting location that is easily reachable by all of them. Usually, they book a hotel, which unfortunately does not always provide any facility to support this kind of meetings, except may be a projector and an insufficient number of sockets. Attendees bring their project data on their wireless devices, which range from laptops to PDAs. It means that these devices have heterogeneous capacities in terms of persistent storage, and 4 Personal Area Network.

battery. Furthermore, attendees do not bring all project data. Thus, data are already distributed between the attendees' devices according to both the attendees' contribution and the capacity of their devices. Every attendee must be able to easily access any project data brought by others, even if not locally cached on his device. This can be done either using floppy disk, or memory card, but it does not allow any coherency management of such replicated data. Fortunately, attendees' devices are equipped with wireless interface cards. Thus, they would like to be able to share their data using the wireless network even if there is no existing networking infrastructure in the meeting hotel, provided that some security guarantees are given regarding the wireless communication. The solution to this requirement is to use ad hoc networking (e.g. IEEE 802.11b WLAN in ad hoc mode) with adequate data management functionalities, which support secure mobile ad hoc collaborative groups. These functionalities subdivide into two core categories:

1. Secure group management that ensures: (i) transparent group creation using a discovery service to detect trusted partners (their devices) that belongs to the group; (ii) adaptation to the group dynamics, so that members can leave or join the group at any time; (iii) secure group communication through an encryption protocol that must account with devices' resources and network connectivity. 2. Data management that ensures: (i) that members access the most recent data version available within the ad hoc group, (ii) data coherency within the group through a conservative coherency protocol to effectively support collaborative work, since members must have the same version of shared data; (iii) adaptive data replication to avoid data loss if the devices storing them suddenly disconnect.

There is the need for a middleware service guaranteeing collaborative data sharing within mobile ad hoc groups and enhancing data availability while meeting the above constraints, by making adequate tradeoffs among data replication, data coherency, and resource consumption on mobile devices. Most of the replication mechanisms that have been proposed for mobile environments do not manage replication with respect to the mobile devices' resources or more generally with respect to the execution context. They all assume that mobile devices have enough cache to contain a user's entire working set of data. This is not a reasonable assumption when the system runs on an environment containing hand held devices with reduced storage capacities. In addition, these systems rely on infrastructure-based networks (e.g., reachability of a base station), and do not offer the possibility of forming ad hoc collaborative groups. These systems, further, maintain coherency of replicas optimistically, which means that they allow updates to be performed independently on any replicas. Although this is convenient for stand-alone mobile devices, it does not match the requirement of accessing a uniform version of the shared data within collaborative ad hoc groups. This paper presents a middleware service for data sharing within a mobile ad hoc collaborative environment that addresses the aforementioned require-ments. It supports secure group management and provides an adequate solution to enhance data availability with respect to mobility constraints (connectivity, device resources) through an adaptive availability scheme that deals with data coherency and replication, in a way that minimizes energy and storage consumption. Our adaptive replication protocol ensures data availability despite the dynamics of the collaborative groups according to the users' specific situation (e.g., profile of the device in use, network connectivity, etc.).

This paper is organized as follows: Sections 2 and 3 are the core of this paper. Section 2 presents functionalities of the middleware service necessary to support secure mobile ad hoc collaborative groups. Section 3 presents our contribution concerning data availability management within ad hoc collaborative groups. Our contribution lies in the integration of both conservative and optimistic coherency management within an adaptive data replication protocol for enhanced availability according to group dynamics and devices' specific situations. Section 4 assesses the proposed service in terms of local storage and communication overhead, response time, and energy consumption. It is shown that using our protocol, generated meta-data overhead is negligible, response time grows linearly with data update size, while group size affects it slightly. Finally, Section 5 concludes, summarizing our contribution and discussing our current and future work.

Middleware Service for Data Sharing within Collaborative Mobile Ad Hoc Groups

Ad hoc networks enable users equipped with lightweight computing devices and wireless interfaces to form a temporary network without the need for any established infrastructure. It is quite interesting to exploit such flexibility to allow them to share and manipulate some data in a collaborative manner (e.g., working meeting, network gaming, etc.) provided that some guarantees regarding security are given. Therefore, a mobile middleware platform should include a service that provides a number of functionalities so as to best cope with mobile collaborative ad hoc groups.

The secure group management functionalities (see §2.1) include discovery of peer mobile terminals that are in the communication range of each other. Then, to form a collaborative group, all the peer terminals should authenticate themselves. Authentication requires a trusted third party (e.g., the home server of the European project) to issue a digital certificate, which is stored on any device that previously authenticated with the given third party. Then, peers that can trust each other build a secure ad hoc group in order to share data and collaborate. Groups are restricted to one hop ad hoc networks, because we consider that the collaborating peers are usually located in the local communication range of each other. However, every peer is free to leave the group, as well as, new trusted peers can join it at any time.

Data sharing within the group is then carried out by making sure that each peer within the ad hoc group has complete knowledge of all the data cached/stored within the group. Access to such data from any of the mobile terminals, belonging to the group, leads to copying it locally, if not already cached. Data coherency is maintained by enforcing a conservative coherency protocol that takes into account mobile devices and wireless network constraints, and provides an effective support for collaborative work, since collaborating users must have the same version of the shared data (see §2.2). Finally, in order to enhance data availability and prevent data miss, useful data for collaborative work have to be rationally replicated on peer devices, with respect to the devices' resources (storage space , energy, etc.) as further detailed in Section 3.

Secure Group Management

Security is of crucial importance in our context, it is therefore mandatory to ensure end-to-end privacy and integrity of the user's data. However, as our platform aims to run on resource constrained terminals, it is necessary to balance strong security enforcement with resource consumption, and in particular energy. For authentication purposes, a trusted third party (e.g., home server) issues Digital Certificates (DC) [START_REF] Menezes | Handbook of Applied Cryptography[END_REF] to users' devices after proper verification of their IDs. The use of DC avoids the need for a trusted, online, third party. A DC includes the user's public key, validity period, the domain name (defined by the home server, e.g., the name of the European project) to which the user belongs, etc. The DC is signed by the trusted third party's private key. Thus, when two nodes wish to authenticate each other upon joining/creating a group, they announce each other with their Digital Certificates. Each of them then verifies the genuineness of the certificate by using the signature on the certificate (every peer must know the third party's public key). Then, the authenticated peers participate in a Group Key Agreement (GKA) protocol to come up with a common secret. A GKA protocol is essentially a contributory protocol designed to provide all the participants with a shared secret key over an open network. This secret is a symmetric key and can be used for securing all further communication. It has to be renewed upon group composition change or at the end of some prefixed security interval. Many such protocols have been proposed in the literature [START_REF] Ateniese | New multiparty authentication services and key agreement protocols[END_REF], [START_REF] Burmester | A secure and efficient conference key distribution system[END_REF], [START_REF] Diffie | A secure audio teleconference system[END_REF], [START_REF] Just | Authenticated multy-party key agreement[END_REF].We are currently examining their adaptation for mobile ah hoc environment with respect to devices' resource constraints. In particular, note that the authentication protocol can be integrated with the Group Key Agreement (GKA) protocol thus saving on communication costs.

Group management builds upon a discovery protocol that aims to dynamically detect new peers that are in the communication range of a given group 5 , and those that have left it. This task is addressed by service discovery protocols, like SLP (Service Location Protocol), Jini6 , UPnP7 (Universal Plug and Play), SDP (Bluetooth Service Discovery Protocol) and Salutation8 [START_REF] Bettstetter | A comparison of service discovery protocols and implementation of the service location protocol[END_REF]. SLP offers a decentralized mode that does not require any Directory Agent to collect service announcements in a centralized database. Therefore, it is particularly suitable for ad hoc networks. Each mobile terminal then periodically advertises for the domains9 it belongs to (e.g., the European project) using its Digital Certificate. When it meets other mobile terminals in its communication range (remember that we consider one hop ad hoc networks) that are advertising for the same domain (i.e., peers that it can trust), the group creation takes place after proper devices authentication.

For a given period of time, a peer is chosen to lead the group. The leader then checks the value of the group variable, which gives the group composition, with the list of nodes' IDs returned by the discovery service. If these two values differ, the group must integrate the (potential) newcomers, and/or discard the (potential) nodes that have left. In addition, the group leader makes sure that peers belonging to the group have a global view of data cached within the group and other peers situation (available resources for collaboration). The leader election ensures that the same peer will never be a leader for two successive periods, in order to distribute the charge of group management over all the peers involved (see [START_REF] Boulkenafed | Valérie Issarny: Ad-HocFS: Sharing files in wlans[END_REF] for more details).

Data Management

Data management ensures that the user accesses the most recent data version available within the ad hoc group, and guarantees data coherency within the group. It enforces, within the ad hoc group, a conservative coherency protocol that accounts with mobility constraints (devices' resources, network connectivity) (see [START_REF] Boulkenafed | Coherency management in ad-hoc group communication[END_REF] for more details). This stems from our concern for effectively supporting collaborative work within ad hoc groups. Therefore, peers belonging to an ad hoc group must access the same version of shared information.

The coherency protocol is based on two elements: an exclusive writer protocol adapted to mobile environments, and a log, named Coherency Control List (CCL). The exclusive writer protocol, used within ad hoc groups, builds upon a distributed token management protocol: a unique token, is associated with each shared data and created upon first access to the data within an ad hoc group. Each peer must request the token ownership to be able to modify the corresponding data. Therefore, only the peer that owns the token is allowed to modify the data. However, local data can be manipulated (read/write) independently within disjoint groups, provided that the data are synchronized when a group is joined. Update propagation for a given shared data occurs only when any member of the group tries to access the data, because if a group member updates its local copy of particular data, propagation of this update is not necessary if none of the other group members wants to read or update the same data (either cached locally or not). Furthermore, updates are propagated only to the peer which is to access the data. This follows from our aim to save energy by reducing communication among peers.

The Coherency Control List is used for incremental lazy update propagation, and serves two purposes: (i) achieving coherency among replicas within an ad hoc group by the lazy update propagation from the current token owner to the peer which is to access its copy; (ii) handling divergences due to non-synchronized concurrent updates in different ad hoc groups which may ultimately require user intervention since fully automated conflict resolution can not be achieved [START_REF] Edwards | Designing and implementing asynchronous applications with bayou[END_REF], [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF].

Adaptive Data Replication for Enhanced Availability

To enhance data availability, an adaptive data replication protocol with respect to mobile devices constraints is used. In the context of collaborative work within mobile ad hoc groups, data may become unreachable if the peers storing them suddenly disconnect. On the other hand, excessive or systematic data replication in order to address unforeseen disconnection leads to unnecessarily overloading the group's peers and in particular to greatly increasing their energy consumption and storage space. Thus, useful data for collaborative work within a group have to be rationally replicated on peer devices, with respect to the devices' resources. Following our assumptions, mobile users are able to form ad hoc groups and to share their data in a collaborative manner. As previously stated, existing mobile distributed systems do not manage replication with respect to devices' resources, nor support transparent collaborative data sharing within ad hoc groups, although some of them support collaborative database applications within infrastructure-based WLAN [START_REF] Edwards | Designing and implementing asynchronous applications with bayou[END_REF]. We aim to achieve data availability within mobile collaborative ad hoc groups through an adaptive peer-to-peer data replication protocol with respect to devices' specific profiles in order to minimize resource consumption (in particular energy).

Each peer caches the set of data necessary for its local autonomy and/or collaborative work. When a peer meets other trusted peers in its local communication range, they form a collaborative ad hoc group. Then, any peer within the group knows about the other peers' situations. Peers profiles serve to identify whether peers can be involved in increasing data availability according to their specific situation. A profile thus indicates: (i) available local storage space for sharing, (ii) whether the peer is able to store replica files other than those that are accessed on the peer depending on available energy, and (iii) expected time within the group, following user's indications (e.g., a diary). Notice further that by construction of ad hoc group management each peer knows both the data that are stored on the various peers of the group, and the situation of each of these peers. Our replication scheme then distinguishes two replica types for a data: (i) Work Replicas are stored on the peer according to data access, either before joining or when part of the group, and (ii) Preventive Replicas are generated by replicating/updating data among the Work Replicas, in order to maintain an up-to-date copy of the data within the collaborative group depending on the peers' profiles. The choice of which peers should store Preventive Replicas is determined by combining the peers' profile with semantic relationships between already stored data on the considered peer and the generated Preventive Replica (see §3.2).

Peers Profile

Within a collaborative ad hoc group, data are distributed among peers belonging to the group. The main reason for data miss is peer disconnection. We can distinguish two types of disconnections: (i) voluntary disconnection, e.g., when the user does not want to stay within the group any longer; and (ii) involuntary disconnection, essentially due to a low battery for power-unplugged devices. Therefore, we define the peer's profile, in order to anticipate decreasing availability generated by these disconnections. The peer's profile provides the following information:

-Available energy: this can be approximated using the monotonously decreasing linear function 10 :

Energy(t) = init - init battery × t ( 1
)
where init is the initial battery value at the time the peer joined the group, and battery is the estimated battery life defined as a function of the peer's charge and is periodically recomputed. Energy(t) serves to determine whether the peer is able to replica files other than those that are accessed locally. Indeed, receiving a new replica involves wireless communication and thus energy consumption [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF]. -Expected time within the group: this can be estimated using,e.g., user's indications or his/her diary. It can be approximated by the following linear function of time:

T ime(t) = cst -t ( 2
)
where cst is the expected time spent within the group. -Available local storage space for sharing: this is given by the function Space(t), whose value depends on the peer's replication rate and has to be recomputed periodically. The profile of any peer is always locally available. The ad-hoc group profile is then periodically updated by gathering fresh profiles from the peers belonging to the group. This period is dynamically adapted according to the group's evolution, considering that peers' mobility has a greater impact than changes in individual profiles. Indeed, peers' motion leads to modifying the number of replicas within the group. So, by adapting the update of the group profile to the group's dynamics, we control the replication rate while minimizing communication. The period is initially set to a given value T . Using statistical modal class the duration of the period T is adapted every n periods as follows. Let t be the current time and γ = Cprev C last , with C last being the number of changes11 over the last n periods (i.e. over [t -(n × T ), t]) and C prev being the number of changes over [t -(2 × n × T ), t -(n × T )] (see Figure 1). Then, if γ is smaller than one, T should be decreased for the next n periods because the group has been changing less frequently over the last n periods than it changed over the n previous periods. The new value of T then becomes equal to:

T × (1 + C prev -C last n ) ( 3
)
with T being the previous value of T . On the other hand, T should be increased if γ is larger than one. We get the following new value for T :

T × (1 - 1 n × C last × maxc i=1 (i × n ci )) (4)
where max c denotes the maximum number of changes over a period for the last n periods of duration T and n ci gives the number of periods during which there were i changes over the last n periods. Over a given period T , we can associate one of the following attributes with each peer's profile functions Energy(t), T ime(t), and Space(t). Considering Energy(t), we have:

-Optimal, the function is maximal over T and superior to the given threshold e th . This thresholds is tuned by the user or the application. Let G be a group of n peers, Energy i (t) is the function for available energy estimation for peer i 's profile. Energy i (t) is optimal if and only if The definition of attributes is applied similarly to functions T ime(t), and Space(t), using their respective thresholds t th , and s th . Then, combining the functions' attributes, we associate the previous attributes to the peer's profile as indicated in Table 1. An optimal profile designates a peer able to actively collaborate and share its resources within the ad hoc group. In contrast, a weak profile designates a peer with few resources, and hence, unable to share them within the group.

∀t ∈ [0, T ], ∀j = 1, ..., n ∧ j = i/peer j ∈ G Energy i (t) ≥ e th ∧ Energy i (t) ≥ Energy j (t) (5)
The attributes of Energy(t), T ime(t), and Space(t) do not have the same weight for determining the profile attributes. Indeed, Energy(t), and T ime(t) indicate, respectively, the available energy and the expected time within the group. Moreover, they represent the evaluation of parameters that can generate a peer's disconnection. Thus, if one of them has a weak attribute, the peer's profile is considered weak. On the other hand, Space(t) does not have the same influence on a peer's profile. Therefore, even if Space(t)'s attribute is weak, a peer's profile is still acceptable because replacement policies can be used to release some storage space. A peer's profile attributes serve to adapt replication to the peer's available resources.

Work and Preventive Replicas

When a peer joins a group, its locally cached data are considered as Work Replicas (WR). Furthermore, Work Replicas are generated upon access demands to non locally cached files. Those replicas are stored locally on the requesting peer regardless of its available resources. A replacement policy (LRU) is used in order to release storage space and hence delete old or seldom accessed Work Replicas provided that at least an other Work Replica is cached within the group.

Within an ad hoc group, updates among Work Replicas are lazily propagated. Therefore, coherency checks, based on CCLs, are performed upon actual access to Work Replicas. Their coherency is managed following the log-based exclusive writer as described in Section 2.2.

When the profile of a peer p caching the latest version of a Work Replica (p is the last writer on this replica) becomes weak, p propagates an update (if not already done) to another Work Replica stored on a peer with an optimal profile 2. The choice of which peer should store the new Preventive Replica is determined by combining its profile with semantic relationships between data as further described below.

Preventive Replicas serve to maintain an up-to-date copy within the group. This is actually our minimal replication rate. Some peers can already cache Preventive Replicas created within other ad hoc groups. These replicas are considered to be Work Replicas when these peers join a new group and become part of the peers' regular local cache. Furthermore, a Preventive Replica within an ad hoc group becomes a Work Replica when: (i) an access demand is made on it; (ii) a new Work Replica is created within the group on a peer with at least acceptable profile (see Table 1). This can happen either when a new peer joins the group, or a peer belonging to the group requires an access to the given replica.

The choice of which peer of an ad hoc group, should store a Preventive Replica is first guided by its profile. Therefore, peers with weak profiles are never going to be selected to store a Preventive Replica. Then, peers already caching a corresponding Work Replica are chosen. In this case, the chosen Work Replica is updated regardless of lazy update propagation. Hence, it also becomes a Preventive Replica. If none of the peers with an optimal or an acceptable profile are caching a corresponding Work Replica, then we rely on semantic relationships between data cached on peers and the Preventive Replica to be created.

Let p 1 be a peer caching the latest version of a Work Replica f 1 W . The profile of p 1 becomes weak so p 1 has to create a Preventive Replica. Assuming, that none of the peers caching f 1 W has a convenient profile, then p 1 has to chose a peer caching the most semantically related set of data to f 1 W in order to create its Preventive Replica. The choice of semantically related data is specific to data type. For instance, when considering files, the peer p 1 chooses semantically related set of files to f 1 W as follows:

as a general rule, files cached on p 1 or in the same directory as f 1 W are the most closely related. File naming also provides important clues to semantic relationships, e.g., files with the same name but different extensions are closely related. p 1 computes semantic distances between f 1 W and locally cached files, as described in [START_REF] Kuenning | Seer: Predictive File Hoarding for Disconnected Mobile Operation[END_REF], in order to create clusters of semantically related files.

Notice that f 1 W can belong to different clusters. Peers locally caching n files belonging to f 1 W 's clusters are considered to be semantically related to f 1 W . The parameter n is tuned by the user or the application. -After the clustering operation, p 1 orders the peers according to their eligibility to store the Preventive Replica. Table 3 gives all the cases involved in a peer's selection for storing a Preventive Replica. Optimal selection peers are the best candidates to store the Preventive Replica. Otherwise, a peer among acceptable selection peers is chosen. If there are no optimal or acceptable selection peers within the group, then a weak selection peer is chosen.

A weak selection peer does not cache Work Replicas or semantically related data, but its profile allows it to become involved in increasing data availability. However, if the group contains only not selected peers, data availability cannot be maintained without compromising these peers' resources, which are already weak.

Assessment

In order to evaluate our collaborative ad hoc group and data availability management protocol in terms of performance and data overhead, we have implemented our middleware service within a file system. The resulting distributed file system for mobile ad hoc data sharing [START_REF] Mentre | AdHocFS: A serverless file system for mobile users[END_REF], [START_REF] Boulkenafed | Valérie Issarny: Ad-HocFS: Sharing files in wlans[END_REF] CCLs, profiles, etc.) by the group leader so as to allow peers belonging to the group to have a global view of shared data and other peers' profiles. Table 4 shows that the cost, in terms of response time and energy consumption, of getting the token (without the updates) to modify a data, is constant within a particular group. Note that the cost of an additional peer in terms of response time is only about 0.005 sec. However, the cost of one additional peer in terms of energy depends on the group size. Indeed, being in ad hoc mode means that even non destination peers consume energy when messages are being sent. That is why, adding one peer to a group of three peers does not have the same energy impact as adding one peer to a group of ten peers. However, the cost in terms of energy consumption still very low. Note that being idle in an ad hoc configuration costs 843 mW.sec.

The cost, in terms of response time, of getting updates is proportional to the update size, as depicted in Figure 3. Using our coherency protocol, getting access to coherent data locally depends on the update size, while group size affects only slightly the performance of our protocol. However, the energy consumption depends on both the group size and the update size. It is given (based on equations from [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF]) by: where n is the ad hoc group size and size the update size. Figure 4 and 5 show the benefits of our coherency management protocol (lazy update propagation) in terms of response time. Indeed, the response time, when lazily propagating updates (in the case of write operations) ranges from 0.0269 sec to 3.219 sec according to the group size and the update size, as depicted by Figure 4. However, when the updates are propagated whenever they occur, which corresponds to an optimistic coherency management (note that peers belonging to group are in the communication range of each other), the response time (in the case of write operations) ranges from 0.0361 sec to 24.8 sec according to the group size and the update size, as depicted by Figure 5. Let compare these two coherency management protocols for a given scenario. Initially, we have an ad hoc group of four peers, all caching the data. We have made four successive write operations by different peers, and we suppose that update size is 640 Kbytes for each write operation. Following our protocol, the time taken to first write access a coherent data file is equal to 0.019 sec, for the second successive write operation it is equal to 1.20 sec, for the third it is equal to 1.22 sec, and for the last write operation to 1.27 sec (this results from our lazy update propagation). However, if the updates are propagated whenever they occurs, in the same scenario, the time taken to write access a coherent data file is equal to 3.639 sec per write operation. Thus, by lazily propagating updates, we save time and communication for the four write operations, which is equivalent to 7218 mW of energy consumption.

ε msg = (0.
Concerning the data overhead introduced by our availability management protocol, we can distinguish two types of overhead: the local storage overhead, it includes the data necessary for coherency and replication management (group composition, CCLs, profiles, etc.) and that are locally stored; the message overhead, which includes the data sent within messages in addition to the actual updates. The local storage overhead is given by (in Bytes):

Local overhead = 3 × int + 2 × bool + (5 × real + 16 × char) × p + G j=1 (16 × char × p j + int × M odif j ) + W +R i=1 (16 × char + size ccl i ) (9) size ccl i = int + G j=1 (16 × char × p j + int × M odif j )) ( 10
)
Where p is the number of peers caching locally the data, M odif is the number of write operations, G is the number of different group configurations where updates occur, W is the number peers waiting for write, R is the number peers waiting for read, and int, real, char, and bool the sizes of respectively integer, real, character, and boolean variables. The message overhead 13 is given by (in Bytes):

M essage overhead = 2 × int + file name × char + G j=1 (16 × char × p j + int × M odif j ) + sum W +R i=1 (16 × char + size ccl i ) (11)
Where file name is the length of the file name. In these equations we considered that peer's ID is a string of 16 characters.

Using our availability management protocol, the local storage overhead as well as the meta-data sent in addition to the updates are negligible regarding the average size of data files, e.g., the message overhead represents 0.41 percent of the whole message to be sent. Further evaluations using simulation should be done, in order to measure the performances of our protocol within different scenarios and profiles including high peers mobility, this is part of our future work.

Conclusion

Mobile ad hoc networks are particularly suitable to form small collaborative groups in order to share and manipulate common data. Until now, work concerning ad hoc networks mainly deals with routing protocols without taking into account data management within these networks. Data management over wireless networks relies essentially on adequate replication management for enhanced availability. Manipulating data within mobile ad hoc collaborative groups requires two core functionalities:

1. Secure group management that ensures: (i) transparent group creation using a discovery service to detect trusted partners (their devices) that belongs to the group; (ii) adaptation to the group dynamics, so that members can leave or join the group at any time; (iii) secure group communication through an encryption protocol that must account with devices' resources and network connectivity. 2. Data management that ensures: (i) that members access the most recent data version available within the ad hoc group, (ii) data coherency within the group through a conservative coherency protocol to effectively support collaborative work, since members must have the same version of shared data; (iii) adaptive data replication to avoid data loss if the devices storing them suddenly disconnect.

Existing distributed systems that deal with mobility do not manage replication with respect to wireless devices resources, nor support transparent collaborative data sharing within ad hoc WLAN groups. Therefore, we have designed and presented a middleware service that allows collaborative data sharing among ad hoc groups that are dynamically formed according to the connectivity achieved by the ad hoc WLAN. Our service enhances, in particular, data availability within mobile ad hoc collaborative groups, and integrates a new adaptive data replication protocol for mobile terminals.

We believe that data availability is a crucial requirement in such environment, and it is one of the prominent QoS criteria for collaborative work. Our replication protocol is based on a combined coherency management (using both optimistic and conservative schemes) in order to account for various connectivity as enabled by today's wireless networking capabilities. It is further based on two replica types: Work Replica, and Preventive Replica. The former is generated according to access demands to non locally cached files, and benefits from the lazy update propagation following our log-based exclusive writer coherency protocol. The latter serve to maintain an up-to-date copy within the group, and is generated according to the profile of the peer holding the latest version of the corresponding Work Replica. The choice of which peer should store a Preventive Replica is determined by combining the peers' profile with semantic relationships between locally stored files and the generated Preventive Replica.

It is shown that using our middleware service, the meta-data overhead generated is negligible, the response time grows linearly with update size, while group size affects it slightly, and, the lazy update propagation saves time and energy consumption. We are further working on evaluating performances of our protocol, by simulating various scenarios and peers' profiles.

1

  Personal Digital Assistants. 2 Mobile Ad hoc NETwork 3 Optical Wireless Solution M. Endler and D. Schmidt (Eds.): Middleware 2003, LNCS 2672, pp. 493-511, 2003. c IFIP International Federation for Information Processing 2003

Fig. 3 .Fig. 4 .

 34 Fig. 3. Cost of Getting Updates

Fig. 5 .

 5 Fig. 5. Optimistic Update Propagation

-

  Acceptable, the function is acceptable over T if it is not optimal, but still greater that the threshold. Energy i (t) is acceptable if and only if

	∀t ∈ [0, T ], Energy i (t) ≥ e th	(6)

-Weak, the function is considered to be weak over T if it goes below the given threshold. Energy i (t) is weak if and only if ∃t ∈ [0, T ], Energy i (t) ≤ e th

[START_REF] Diffie | A secure audio teleconference system[END_REF]

Table 1 .

 1 Peer's profile classification

	Energy(t) T ime(t)	Space(t) Peer's Profile
	Optimal	Optimal	Optimal	Optimal
	Optimal	Optimal Acceptable	Optimal
	Optimal	Optimal	Weak	Acceptable
	Optimal Acceptable	∀	Acceptable
	Optimal	Weak	∀	Weak
	Acceptable Optimal	∀	Acceptable
	Acceptable Acceptable	∀	Acceptable
	Acceptable	Weak	∀	Weak
	Weak	∀	∀	Weak

Table 2 .

 2 Replicas Management within an Ad Hoc Group , or with an acceptable profile otherwise. This updated Work Replica also becomes a Preventive Replica (PR). Notice that the lazy update propagation is no longer respected in this case, updates are systematically propagated to the Preventive Replica. If peer p is the only peer caching this Work Replica (determined using the group variable), then a new replica (Preventive Replica) has to be created, as summarized in Table

	Within an Ad Hoc Group	Events	Actions
		only one replica the peer caching the up-to-update a WR, that
	Their are	is up-to-date date replica becomes weak becomes also a PR
	many WRs	many WRs are up-to-date	a peer caching a WR becomes weak	Do nothing
	Their is one WR	-	the peer caching the WR becomes weak	create a PR on an appropriate peer
	if one exists

Table 3 .

 3 Selecting a Peer for Caching a Preventive Replica

	Is Caching Profile a Work Replica Semantically Related Data Is Caching	Peer's Selection
	Optimal	true	∀	Optimal Selection
	Optimal	false	true	Acceptable Selection
	Optimal	false	false	Weak Selection
	Acceptable	true	∀	Acceptable Selection
	Acceptable	false	true	Acceptable Selection
	Acceptable	false	false	Weak Selection
	Weak	∀	∀	Not Selected

Table 4 .

 4 Figure 2 gives the time taken for creating a group, leaving and joining a group, which are linear with the group size. The main cost of group creation lies in detecting trusted peers and sending the meta-data (group composition, Cost of Getting the Token

	is implemented in Objective Caml

Notice that a singleton peer is consider as a group.

http://www.sun.com/jini

http://www.upnp.org

http://www.salutation.org

As defined by its home server, e.g., the European project.

By changes we mean peers' motion that leads to joining or leaving the group

Acknowledgments

The authors would like to acknowledge the work carried out by Raghav Bhaskar and Daniel Augot regarding security management in mobile ad hoc networks and their proposition to adapt group key agreement protocol to such environment. We would like also to acknowledge the contribution of David Mentré, Anis Ben-Arbia, and Animesh Pathak to the design and the implementation of the ad hoc group management protocol and the coherency management protocol. This work has been partially funded by the ITEA VIVIAN Project (ITEA 99040).


Françoise Sailhan
email: francoise.sailhan@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

Cooperative Caching in Ad Hoc Networks

come   L'archive ouverte pluridisciplinaire

Introduction

The last decade has seen the rapid convergence of two pervasive technologies: wireless communication and the Internet. The resulting mobile Internet a priori enables users to easily access information anytime, anywhere. However, we have not yet reached the point where anywhere, anytime Internet access is actually offered. This paper addresses the above issue, concentrating more specifically on Web caching in a mobile environment to allow for Web access, without requiring availability of an infrastructure in the nearby environment.

There exist two different ways of configuring a mobile network: infrastructurebased and ad-hoc-based. The former type of network structure is the most prominent, as it is in particular used in both Wireless Lans (e.g., IEEE 802.11) and global wireless networks (e.g., Gsm, Gprs, Umts). An infrastructure-based wireless network uses fixed network access points (known as base stations) with which mobile terminals interact for communicating, i.e., a base station forwards messages that are sent/received by mobile terminals. One limitation of the infrastructure-based configuration is that base stations constitute bottlenecks. In addition, it requires that any mobile terminal be in the communication range of a base station. These shortcomings may be solved through the deployment of a sufficient number of base stations. However, this comes at a high cost for network providers. The ad-hoc-based network structure alleviates this problem by enabling mobile terminals to cooperatively form a dynamic network without any pre-existing infrastructure. In general, ad hoc and infrastructure-based networking should be seen as complementary rather than as competitive. Ad hoc networking is much convenient for accessing information available in the local area, and possibly reaching a Wlan base station, which comes at no cost for users. Ultimately, the user may decide to pay for communication using wireless global networking facility. This paper concentrates on improving the Web latency using a Wlan, exploiting both the ad hoc and infrastructure-based capabilities of the network.

The issue that we are addressing is on setting an ad hoc network of mobile terminals that cooperate to exchange Web pages. One application of our work is, e.g, multimedia guided tour from PDAs. Indeed, several cities and museums have proposed such services over the last few years but the limited number of base stations due to a prohibitive financial cost and the limited communication range of mobile terminals prevent tourists from accessing data anywhere. In addition, the limited memory capacity of PDAs requires constant interaction with the base station to gain access to the rich set of available information. Our proposal allows users to access information when a base station is not reachable in one hop and then offers better scalability at lower financial cost.

In the above context, it is crucial to account for the specifics of mobile terminals. Mobile terminals that will soon be available will embed powerful hardware (e.g., LCD screens, accelerated 3D graphics, high performance processor), and an increasing number of devices (e.g., DVD, CD) [START_REF][END_REF]. However, the capacity of batteries goes up slowly and all these powerful components reduce battery life. Thus, it is mandatory to devise adequate solutions to energy saving on the mobile terminals, for all the constituents of the mobile environment, i.e., application software, network operating system, and hardware. In particular, communication is one of the major sources of energy consumption, and hence a number of wireless communication protocols have been designed to reduce energy consumption [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF][START_REF] Chang | Energy conserving routing in wireless ad-hoc networks[END_REF][START_REF] Nakano | Energy-efficient randomized routing in radio networks[END_REF]. However, most of the communication protocols that have been proposed for ad hoc networks are addressed in terms of bandwidth usage and not energy consumption [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in ad hoc networking environment[END_REF]. In addition, it is mandatory for these protocols to be coupled with distributed application software that are designed so as to minimize energy consumption.

This paper introduces such a distributed application software, which implements ad hoc cooperative Web caching among mobile terminals 1 . The proposed solution aims at improving the Web latency on mobile terminals while optimizing associated energy consumption. The solution accounts for both the capacities of mobile terminals and the network features; it comprises: (i) a cooperative caching protocol among mobile terminals that builds upon an existing ad hoc routing protocol, and (ii) a local caching strategy for the mobile terminal. The next section discusses related work, addressing background in the area of cooperative Web caching and Web access from mobile terminals. Section 3 then introduces the proposed ad hoc cooperative Web caching protocol, and is followed in Section 4 by the presentation of the caching strategy implemented on terminals. Section 5 provides an evaluation of our proposal, giving the energy consumption associated with cooperative caching. Finally, Section 6 concludes with a summary of our contribution, and our current and future work.

Related Work

The ever growing popularity of the Web and the resulting poor latency for users have given rise to huge effort on improving the Web latency, which mainly lies in the introduction of Web caching protocols. Due to the network topology, the idea of making network caches (also referred to as proxy caches or simply proxies) cooperate has emerged. The Harvest project [START_REF] Bowman | The Harvest information discovery and access system[END_REF] introduced the notion of hierarchical caching, which is pioneering and lies in introducing a cache on every network node, the system's hierarchical structure coming from the national networks' hierarchical organization. A cache then locates a missing requested object by issuing a request to the cache at the hierarchy's upper level. The process is iterated until either the object is found or the root cache is reached, which may ultimately involve contacting the object's server. The object is then copied in all the caches contacted as it is returned to the client.

A transversal system enriches the hierarchy by integrating a set of sibling caches that are close in terms of latency time, at each hierarchical level. On a cache miss, a cache not only contacts its ancestral cache but also its siblings. A number of transversal cooperative caching protocols have been proposed in order to minimize the number of messages that are exchanged among sibling caches to retrieve cached objects. Proposed solutions all amount to maintain a partial knowledge of the objects that are cached on siblings. With Summary Cache [START_REF] Fan | Summary cache: a scalable widearea Web cache sharing protocol[END_REF], each proxy keeps a compact summary of the cache content of other sibling proxies. The Scoop protocol [START_REF] Menaud | A scalable and efficient cooperative system for Web caches[END_REF] proposes to distribute this knowledge among the cache composing the transversal system and the Cache Array Routing Protocol (CARP) [START_REF] Valloppillil | Cache array routing protocol[END_REF] partitions the URL space among sibling proxies.

In the context of mobility, proxy caches are used not only to cache and retrieve documents but also to manage user mobility. These proxies are access points to the Internet for mobile terminals. Proxies implement functionalities dedicated to the transfer of data to mobile terminals, such as compression, filtering, format conversion [START_REF] Markatos | A top-10 approach to prefetching on the Web[END_REF] [START_REF] Bennett | Practical Wap, Developing applications for the Wireless Web[END_REF]. It is further mandatory to account for the disconnection of mobile terminals, as their connectivity is highly dynamic in nature. Typically, a mobile terminal can be in either of the three following connection modes, shifting from one to another depending on the user's location: strongly connected (i.e., use of a fixed LAN), less strongly connected (i.e., use of a wireless network), or disconnected (i.e., due to the absence of connectivity or to save energy). Solutions to the above issue include the one offered by the ARTour Web Express software [START_REF] Chang | Web browsing in a wireless environment: disconnected and asynchronous operation in ARTour Web express[END_REF], which queues user requests that are made during an unexpected disconnection. These requests are later processed as a background task when the connection is restored. In addition, the user may act upon local cache management by requesting to keep in the cache the pages that he/she marks using the cache browsing tool. However, not all the disconnections are unexpected, and some may be anticipated by the user. In this case, the user may indicate the kind of Web pages she will be willing to access (e.g., subject of interest, Urls). The information is then exploited, possibly in combination with the user's profile, to prefetch a number of pages. Similar to our solution, the one of [START_REF] Chakraborty | A reactive service composition architecture for pervasive computing environments[END_REF] in the area of service discovery and composition or [START_REF] Perich | Profile driven data management for pervasive environments[END_REF] in the area of databases use a decentralized model in an ad hoc environment. Complementing proxy solutions with ad-hoc-based ones will allow for both enhanced connectivity and Web access at low cost. In that context, the caches of the mobile terminals cooperate in a way similar to proxy caches in transversal cooperative cache systems. However, the cooperative scheme must be devised so as to account for: the continuously changing set of cooperating terminals, the heterogeneity of terminals in terms of resource availability, and energy saving.

Cooperative Caching in Ad Hoc Networks

A number of ad hoc routing protocols are implemented over a base Wlan. Basically, these protocols maintain a routing table and differ in the way they manage it ( § 3.1). Using the ad hoc network protocol that offers the best trade-offs in terms of energy consumption and response time, we propose a specialization of the protocol that is specifically aimed at handling remote access to Web pages ( § 3.2). We then introduce our ad hoc cooperative caching protocol, which has primarily been designed to minimize energy consumption ( § 3.3).

Ad Hoc Networking

The main issue to be addressed in the design of an ad-hoc (network) routing protocol is to compute an optimal communication path between any two mobile terminals. This computation must minimize the number of control messages exchanged in order to minimize network congestion and energy consumption [START_REF] Das | Performance comparison of two ondemand routing protocols for ad hoc networks[END_REF].

There exist two base types of ad hoc protocols: proactive and reactive. Proactive protocols (e.g., Olsr [START_REF] Clausen | Optimized link state routing protocol[END_REF]) update their routing table periodically. Compared to proactive protocols, reactive protocols (e.g., Aodv [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF], Dsr [START_REF] Johnson | Dynamic source routing in ad hoc wireless networks[END_REF]) check the validity of, and possibly compute, the communication path between any two mobile terminals only when a communication is requested between the two. Zrp [START_REF] Haas | A new routing protocol for the reconfigurable wireless networks[END_REF] is a hybrid protocol that combines the reactive and proactive modes. The design rationale of Zrp is that it is considered advantageous to accurately know the neighbours of any mobile terminal (i.e., mobile terminals that are accessible in a fixed number of hops), since they are close. Hence, communicating with neighbours is less expensive and neighbours are most likely to take part in the routing of the messages sent from the terminal. As a result, Zrp implements: (i) a proactive protocol for communication with mobile terminals in the neighbourhood, and (ii) a reactive protocol for communication with the other terminals. With respect to a given mobile terminal, its neighbourhood is referred to as its zone. Notice that it would be interesting to dynamically set the number of hops used to define a zone, according to the number of mobile terminals that are present in the perimeter. Zrp is currently among the most efficient ad hoc routing protocols in terms of network load due to control messages and hence of associated energy consumption on mobile terminals. We thus use Zrp over Ieee 802.11, as the base ad hoc protocol for realizing ad hoc cooperative caching among mobile terminals. Mobile terminals belonging to the zone of a given terminal then form a cooperative cache system for this terminal since the cost for communicating with them is low both in terms of energy consumption and message exchanges [START_REF] Haas | The performance of query control schemes for the zone routing protocol[END_REF]. However, cooperative caching must not be restricted to the mobile terminals belonging to the zone: low-cost reachability of a base station must be accounted for as well as knowledge of a terminal that does not belong to the zone but that is likely to store a requested Web document given commonalities in performed Web accesses.

Ad Hoc Communication for Web Caching

A mobile terminal may get Web data that are not cached locally through two communication paths: (i) using the infrastructure-based mode, the terminal may interact with the nearby base station, which forwards the request to the Web, (ii) using the ad-hoc-based mode, the terminal may request for the data to the mobile terminals in its communication range (i.e., accessible in one hop in a base Wlan or in a number of hops using some ad hoc network routing protocol). The former is the most efficient in terms of energy consumption; the mobile terminal sends a single message to a base station that has an infinite energy budget. However, the ad-hoc-based mode must be enabled for the case where a base station is not reachable in one hop. In this case, a base station can still be reachable in a number of hops, thanks to mobile terminals forwarding the requests. For instance, Umts supports such a mechanism to extend the range of the infrastructure2 . The number of hops that are necessary to access a base station depends on the terminal's location. Let N be this number, then any mobile terminal that is at a distance greater or equal to N is not contacted to get a document. Figure 1 depicts the case where the mobile terminal A reaches the base station D in 3 hops, using the mobile terminals B and C for routing the request. Then, if either a mobile terminal in the zone of A (e.g., B belonging to the path leading to the base station or any other terminal in the zone) or a known mobile terminal located outside the zone but at a lower distance than the base station D (e.g., C that is in the path leading to D or E that does not belong to the path) holds the requested document in its cache, it returns it to A. Otherwise, the request reaches D, and D forwards it to the Web. We get the following ad hoc communication protocol over Zrp, to retrieve a remote Web object W , with respect to a given mobile terminal A:

• In-zone communication:
If a base station is in the zone of A, then A requests for W through the base station only. Otherwise, A broadcasts the request message for W to the mobile terminals in the zone of A, incurring a low energy cost since the routing table contains the necessary information.

• Peer-to-peer communication:

If W is not cached by any of the mobile terminals in the zone of A and if there is no base station in the zone of A, then a peer-to-peer communication (or point to point messaging) scheme is realized with mobile terminals that are known to share interests with A (see § 3.3) and that are at a distance that is less than the one between A and the nearest base station. Mobile terminals outside the zone of A are basically known through two ways: (i) they belong to the path used to reach the nearest base station, (ii) they were previously either in the zone or in the path used to reach the base station.

The request for W is ultimately forwarded to the nearest base station.

Based on the above, the communication cost and hence the energy cost associated with getting a Web object is kept to a minimum: (i) broadcast is within a zone and is thus unexpensive by construction of Zrp, (ii) peer-to-peer communication occurs only with mobile terminals that are both the most likely to store a requested object and closer than a base station.

Ad Hoc Cooperative Caching

Without a proxy-type architecture that centralizes requests, local statistics are relied on for a mobile terminal A to identify mobile terminals that are likely to store a Web object requested on A. Such statistics are maintained on A through a terminal profile for every mobile terminal with which A interacts. The terminal profile is characterized by a value that counts the number of times the corresponding mobile terminal either is known to cache an object requested by A or requested for an object to A that A had in its cache. The value of the terminal profile is used to identify the mobile terminals with which peer-topeer communication is undertaken. The list of known mobile terminals outside the zone and that are at a distance less than a base station are then weighed according to the value of F = terminal prof ile ÷ hops where the number of hops, hops, is obtained from the routing table. Mobile terminals for which the value of F is the greatest are first contacted and the process is iterated until a hit message is received or there are no more mobile terminals eligible for the request. In addition to the management of terminal profiles to identify mobile terminals that share common interests, we must account for the heterogeneity of the terminals' capacity (i.e., battery, processing, storage, communication). In particular, for two mobile terminals that are equally likely to store a requested object, it is better to contact the one that has the greatest capacity.

Ignoring the case where a base station is accessible in the zone and given the ad hoc communication protocol aimed at Web caching that was discussed in the previous subsection, the request for a Web object W that is not cached locally, from a mobile terminal A is handled as follows: (i) A first broadcasts the requests for W within the zone; (ii) if W is not retrieved then the retrieval protocol iterates on sending the request for W to known mobile terminals outside the zone and at a distance less than the base station according to the maximization of F ; (iii) the base station is ultimately contacted. The processing of requests is further handled as follows. A mobile terminal that receives the request for W and caches it increments its local value of A's terminal profile. If the terminal is further willing to cooperate (e.g., absence of energy safeguarding or of security policy enforcement), it returns a hit message, which embeds:

• (i) T T L that gives the Time To Live field of the document.

• (ii) Capacity that characterizes the capacity of the terminal to handle requests, whose value is in the range [0..1], 1 denoting the highest capacity. Currently, we use a simple scheme to set the value of Capacity; it is equal to the percentage of the energy budget that is left. It is part of our future work to investigate a more accurate way of computing Capacity.

For every hit message that it receives, A increments the terminal profile of the sender. Among the mobile terminals that replied by a hit message, A selects the terminal from which W should be obtained, that is the one that maximizes the following function3 : R = Capacity × (λ × T T L + µ × hops) where λ and µ are set so as to favour communication with the closest nodes. More precisely, the value of R is computed as follows. The metrics used for consistency (duration given by ttl) and for communication cost (number of hops) are distinct and should be made comparable. As a dispersion measure of TTL and hops, we use the standard deviation. Thus, considering that A received N hits messages for W, A computes the mean m T T L (resp. m hop ) of the TTL (resp. hops) and the standard deviation σ T T L (resp. σ hop ):

m T T L = 1 N N i=1 T T L mobilei , σ T T L = 1 N n i=1 [T T L mobilei -m T T L ] 2 m hop = 1 N N i=1 hop mobilei , σ hop = 1 N n i=1 [hop mobilei -m hop ] 2
For illustration, Figures 2 gives a set of ttl and hop values considering reception of hit messages from terminals [B,..,G]. We distinguish four intervals for the value of ttl: level .4], and is the one used in the computation of R. For illustration, Table 1 gives the initial ttl and hops values, and values under the unified metric, considering the distribution given in Figure 2. Then the values of λ and µ are set so that λ+µ = 1 and will be chosen according to the respective weighing factors for the consistency and communication cost. Figure 3 gives the value of R capacity for the mobile terminals B,..,G considered in Figure 2, according to the value of λ, ranging from 1 (i.e, µ=0 and the communication cost is ignored) to 0 (i.e, µ=1 and the communication cost is the only selective factor). We do not use miss messages for mobile terminals to notify that they do not cache a requested object. This is to minimize both network load and energy consumption. Hence, we use timeouts to detect the absence of a requested object. The value of the timeout is set according to the greatest number of hops that are involved to interact with the mobile terminals to which the object is requested, together with the current network load. Upon expiration of the timeout, if hit messages have been received, the Web object will be requested to the mobile terminal that maximizes R. Otherwise, the next iteration of the cooperative caching protocol is processed (i.e., from the broadcast step to the peer-to-peer iterative step). For the case where a hit message is received after timeout expiration, while the object is still not retrieved, the message is accounted for in the current step of the protocol.

I 1T T L = ]-∞, m T T L -σ], level I 2T T L = [m T T L -σ, m T T L ], level I 3T T L =[m T T L , m T T L +σ], level I 4T T L = [m T T L +σ, +∞].
(m -σ) -1 2 σ 1 -1 2 = 1 2 4 1 + 1 √ 5 c 4 7 m -3 7 σ 2 -3 7 = 11

Local Caching

The ad hoc cooperative caching protocol introduced in the previous section is complemented by a local caching strategy, which is adaptive according to the current capacity of the terminal. Local cache management mainly amounts to the implementation of a replacement algorithm that is run when the cache gets full. We weigh every cached document according to both its probability of being accessed in the future and the energy cost associated with getting remotely the document. Documents with the lowest weighs are those that are removed from the cache. The document weigh is computed according to the following criteria:

• Popularity. The P opularity value serves approximating the probability of future access, both on the terminal and from remote terminals, as enabled by the cooperative caching protocol. The probability is approximated according to the number of times the document has been requested since it has been cached. • AccessCost. The AccessCost value gives an estimate of the energy cost associated with getting the document remotely if it is to be removed from the cache. This cost varies depending on whether: a base station is accessible in the zone of the terminal, the document is cached on a mobile in the zone of the terminal, communication out of the zone is required to retrieve the document. In the first two cases, the cost is quite low, while it may be quite high in the third case. The value of the access cost is computed according to the energy consumption associated with intra-zone and interzone communication (see § 5). Intra-zone communication holds if a base station is known to be in the zone. It is further assumed if the document was obtained from a terminal that is still in the zone, as identified using the routing table. • Coherency. A document is valid for a limited lifetime, which is known using the T T L field. However, when the energy remaining on the terminal is low, it is better to favour energy saving over the accuracy of the document. Hence, the value of Coherency is equal to ν ×T T L where ν increases as the available energy decreases.

We get the following function to compute the document weigh:

W = α × P opularity + β × AccessCost+ γ × Coherency + δ × size
The values of α, β, γ and δ are set so as make the values of AccessCost, P opularity, Size, and Coherency, decreasingly prominent factors for deciding whether a document should be kept in the cache. The metric used to compare the differents parameters is computed in a way similar to the one described in Section 3 for the function R. Notice that our W function offers similarities with the one used by hybrid replacement algorithms that were proposed in the literature for Web caching on stationary hosts (e.g., [START_REF] Jinag | Web prefetching in a mobile environment[END_REF]). In the same way, we use a function that accounts for a combination of criteria in the replacement decision. However, our function differs in that energy saving is a prominent criterion.

Evaluation

Control messages generated by Zrp and messages associated with ad-hoc cooperative caching affect the network traffic and energy consumption on mobile terminals. In this section, we examinate the energy consumption induced by:

• Maintening the routing table on each mobile terminal with ZRP.

• Using the ad-hoc cooperative strategy to identify terminals that are likely to store the requested Web data. • Retrieving the Web data.

The above includes the energy cost due to both communication and computation. However, we do not consider the latter cost since it is induced by any local cache management, and it is negligible compared to the energy cost of communication: the energy cost of transmitting 1Kb is approximately the same as the energy consumed to execute 3 million intructions [START_REF] Pottie | Wireless integrated network sensors[END_REF]. We further use the following wireless interface for our evaluation: 2.4Ghz DSSS lucent IEEE 802.11 WaveLan PC "Bronze" 2Mbps on the terminal.

Energy Consumption of ZRP Control Messages

Performance of Zrp has been evaluated in [START_REF] Haas | The performance of query control schemes for the zone routing protocol[END_REF][START_REF] Haas | A new routing protocol for the reconfigurable wireless networks[END_REF] using event-driven simulation; this evaluation is gauged by considering the control traffic generated by Zrp. Figure 4 gives the energy consumption generated by the reception of ZRP traffic. Messages are used to maintain the zone routing tables with a beacon broadcast period of 0.2/s. To obtain the path to a mobile terminal out of the zone, additional control messages are exchanged only on-demand. Given the energy consumption generated by ZRP, we evaluate energy consumption associated with ad-hoc cooperative caching, as the sum of the energy consumption induced for the various mobile terminals that are involved (both in and outside the zone) in the cooperation, which adds to the energy cost induced by ZRP.

Energy Consumption of Ad-Hoc Networking

Focusing on the energy cost associated with communication, the cost associated with the emission of one message is the sum of:

• The cost of emission for the sender node.

• The cost of reception for the destination node.

• The cost of reception and emission for mobile nodes forwarding the message.

• The cost of reception for non-destination nodes (i.e., terminals that receive control messages due to their location with respect to the aforementioned nodes, although they are not involved in the routing of the message).

To minimize collisions in point-to-point traffic, the IEEE 802.11 protocol provides the following collision avoidance mechanism. Prior to any point-to-point transmission, the sender broadcasts a Rts (Request To Send) control message, which specifies the destination node and the data size (for duration). The sender then waits for a Cts (Clear To Send) message from the destination node. Once it receives the Cts, the sender sends the data message. Finally, the destination node sends an Ack message upon the reception of the data message. Therefore, the energy consumed by any mobile terminal for sending, receiving or discarding a message is given by the linear equation [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in ad hoc networking environment[END_REF]: ε = m * size + p; where size is the message size, and m (resp. p) denotes the incremental (resp. fixed) energy cost associated with the message. The value of ε is detailed hereafter, for the various mobile terminals affected by the message transmission. Table 2 gives the energy cost, relative to the size of the message, for the sender and destination nodes (i.e., the actual sender and destination nodes and the forwarding nodes that act as both sender and destination nodes). For the sender X, the high value of the Consider now a network of 500 mobile terminals whose communication range is of about 250m, that is such that the mobile terminals are uniformly distributed in the network surface S with S = 4000[m] × 4000[m] 4 . In a zone (see Figure 5), all the mobile terminals consume the same energy. Thus, the overall energy = πR 2θr 2 sin 2 θ + βR 2 sin 2 β nAεA consumption within a zone is the sum of the energy consumed by every mobile terminal in this zone (see Table 3). Then, the energy consumption of the overall network is the sum of the energy consumed per zone that is traversed. Figure 6 gives the energy consumption associated with the delivery of a message of 1 Kb to the destination node according to the number of hops, which is the sum of the energy consumed on all the nodes involved in the communication.

The figure clearly demonstrates that the energy consumption increases with the number of hops. This directly follows from the resulting increase of both mobile terminals forwarding the message and non-destination nodes receiving control messages. Table 4 further evaluates the impact of the network density on energy consumption. For a constant number of hops (=3), we see that increased density of mobile terminals results in additional energy consumption for nondestination nodes. But, the ratio ε send +ε dest +ε f orwarding mobile terminals ε overall non-destination mobile terminals highlights the weak impact of message reception on non-destination nodes, on the overall energy consumption. Indeed, for 600 mobile terminals and a destination node at 4 hops of the sender, the energy consumed by non-destination nodes is about 6 times less than the energy consumed by the sender, the receiver and the 3 forwarding mobile terminals. Fig. 6. Energy consumption in the network for the retrieval of Web data.

Energy Consumption of Ad-Hoc Copperative Caching

Having examined the energy consumption associated with data delivery, we now focus on the energy consumption induced by our ad-hoc cooperative caching protocol, which retrieves a requested Web page among mobile terminals. A request message for a Web page includes broadcasting (with mobile terminals in the requester's zone) and peer-to-peer communication (with mobile terminals sharing the same interests). Before broadcasting a message, the sender listens to the channel; if no traffic is detected, the message is broadcasted. Table 5 gives the energy consumption induced by a broadcast while the one associated with peer-to-peer communication is given in Table 2. The difference between the energy consumption associated with broadcasting and the energy consumption associated with peer-to-peer communication is due to the emission of control messages (RTS, CTS and ACK messages) in the case of peer-to-peer communication. Figure 7 gives the energy consumed by cooperative caching according to the number of hops that defines the zone. Precisely, Figure 7 gives the cost associated with broadcasting and peer to peer communication at a distance that adds one hop to the number of hops that defines the zone. As expected, the overall energy consumption of both broadcast and peer-to-peer communication increases with the number of hops that defines the zone (because more mobiles are in the zone). Comparing energy consumption of broadcasting with the one of peer-to-peer communication, we find that the cost added by broadcasting is weak compared to the number of mobile terminals contacted, and hence supports our approach.

Conclusion

Mobile technology has reached a stage that enables foreseeing easy access to information technology anywhere, anytime. However, it is necessary to devise adequate software and hardware solutions to mask unstable connectivity and limited energy. This paper has addressed one such solution, which focuses on enabling Web accesses from mobile terminals. Currently, Web access is easy to realize if the mobile terminal is in the communication range of a base station of either a Wlan or a global wireless network. However, this cannot always be assumed due to the financial cost associated with the deployment of the underlying infrastructure. In addition, the systematic use of a global wireless network is quite costly for users. Instead of relying on a base station for accessing the Web, an alternative solution is to exploit ad hoc networking, which allows for remote communication at no financial cost and also reaching a base station of a Wlan in a number of hops. In that context, we have proposed a cooperative Web caching system for ad hoc networks, which enables mobile terminals to share Web pages, while minimizing the resulting energy cost. Our system lies in implementing on each mobile terminal: (i) an ad hoc cooperative caching protocol that selects the mobile terminals from which a requested page should be retrieved, in a way that minimizes both energy consumption and network load, (ii) a caching strategy that maintains the local cache in a way that minimizes resource consumption. Such a system is well suited for location-dependent data such as multimedia guided tours. It is further a cheap solution compared to existing ones since it is not based on the infrastructure mode. Preliminary assessment of our proposal has been addressed by providing the energy cost that our system incurs for mobile terminals. We are currently working on further assessment of our proposal, which lies in the implementation of a simulator to thoroughly examine the behaviour of our system. Experiment using the simulator will in particular serves tuning the various weighing functions that we use for cooperative caching. We are also implementing our proposition for multimedia guided tours on the Web.

  M.-S. Chen et al. (Eds.): MDM 2003, LNCS 2574, pp. 13-28, 2003. c Springer-Verlag Berlin Heidelberg 2003

Fig. 1 .

 1 Fig. 1. Getting Web data

Fig. 2 .

 2 Fig. 2. Energy consumption.

Fig. 3 .

 3 Fig. 3. R/capacity function.

Fig. 4 .

 4 Fig. 4. Energy consumption generated by the reception of ZRP traffic in a zone per /s

Non-destination nodes in range of

  sender X εAX =mAX * size + pAX mAX = -0.22 pAX = 210 in range of sender X εX =mX * size + pX mX = -0.04 pX = 90 in range of destination A εA=mA * size + pA mA = 0 pA = 119 incremental cost m send is due to the emission of the data message. The fixed cost p send results from the reception of two control messages (Cts and Ack) and from the emission of the Rts message. For the destination node A, the fixed cost p dest is due to the emission of two control messages (Cts and Ack) and to the reception of the Rts message. The value of m dest for A follows from the reception of the data message. Table 2 also gives the energy cost, relative to the size of the message, for non-destination nodes. Non-destination nodes in the range of the sender receive Rts messages and thus enter a reduced energy consumption mode during data emission; this leads to have a negative value for m AX and m X since the energy consumption is less than the one in the idle mode. The fixed cost p AX for non-destination nodes in the range of both the sender and the receiver is greater than the fixed cost p X for non-destination nodes in the range of the sender only, because the latter do not receive the Cts and Ack messages. Finally, non-destination nodes in the range of the destination node but not the sender receive the Cts and Ack messages. On the other hand, they do not receive the Rts message, and thus cannot enter in the reduced energy consumption mode; this leads to have the incremental cost m A equal to 0.

Fig. 5 .

 5 Fig. 5. Mobile terminals in the range of the sender and of the destination node.

Fig. 7 .

 7 Fig. 7. Energy consumption in the network for the broadcast and the peer-topeer communication.

Table 1 .

 1 TTL and hop metric

	mobile TTL	TTL	TTL metric hop hop metric
	b	1 2

Table 2 .

 2 Energy consumption on nodes for point to point communication send = m send * size + p send m send = 1.9 p send = 454 Destination A ε dest = m dest * size + p dest m dest = 0.5 p dest = 356

	Mobile	Energy consumption (µW.sec)	m (µW.sec) p (µW.sec)
	Sender X

ε

Table 3 .

 3 Energy consumption in a zone. = πr 2θr 2 sin 2 θ + βR 2 sin 2 β nX εX the receiver A SA = πR 2 -SAX nA =

	Mobile terminal	Surface	Number of mobile	Total energy
	in range of		terminals	for a zone
	the sender X & SAX = θ(r 2 -a 2 1 ) the receiver A +β(R 2 -a 2 2 )	nAX =	N S AX S	nAX εAX
	the sender X SX = πr 2 -SAX nX =	N S X S
			N S A
			S

Table 4 .

 4 Energy consumption according to the network density.

	Number of Mobile terminals in	500 600 700
	the network surface
	Energy consumption of non-	1389 18959 2136
	destination mobile terminals (µ W.sec)
	ratio	9	7 6.11

Table 5 .

 5 Energy consumption on the sender and destination nodes for broadcast. Destination ε brdest = m brdest m brdest = p brdest =

	Mobile	Energy consumption	m	p
		(µW.sec)	(µW.sec/byte) (µW.sec/byte)
	Sender	ε brsend = m brsend m brsend =	p brsend =
	X	*size+p brsend	1.9	266
	A	*size+p brdest	0.5	56

In the following we do not address the issue of Web Data conversion for these devices for which a number of base solutions exists.

http://www.3gpp.org

For the case where the selected terminal is no longer accessible, e.g., due to energy safeguarding, the request will be sent to the next eligible terminal and will be so until the page is received.

This network is taken as an example, as it is used in[START_REF] Haas | The performance of query control schemes for the zone routing protocol[END_REF] for the evaluation of ZRP.

http://www.extra.research.philips.com/euprojects/ozone/

Acknowledgments:

This work has been partially funded by the OZONE European IST project 5 .