Julien Haillot

Frédéric Guidec

A Protocol for Content-Based Communication in Disconnected Mobile Ad Hoc Networks

In content-based communication, information flows towards interested hosts rather than towards specifically set destinations. This new style of communication perfectly fits the needs of applications dedicated to information sharing, news distribution, service advertisement and discovery, etc. In this paper we address the problem of supporting content-based communication in partially or intermittently connected mobile ad hoc networks (MANETs). The protocol we designed leverages on the concepts of opportunistic networking and delay-tolerant networking in order to account for the absence of end-to-end connectivity in disconnected MANETs. The paper provides an overview of the protocol, as well as simulation results that show how this protocol can perform in realistic conditions.

Introduction

Applications dedicated to information sharing, news distribution, or service advertisement and discovery, all share a common characteristic: they require a communication model where information can flow towards any interested receiver rather than towards set destinations.

Content-based communication is a style of communication that fits perfectly the needs of such applications. In content-based communication, the flow of information is interest-driven rather than destination-driven [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF]. Receivers specify the kind of information they are interested in, without regard to any specific source. Senders simply send information in the network without addressing it to any specific destination.

In this paper we address the problem of supporting content-based communication in a disconnected mobile ad hoc network (MANET). A MANET can become disconnected when, for example, the mobile hosts that compose the network are very sparsely or irregularly distributed. The whole network then appears as a collection of distinct "islands". Communication between hosts that belong to the same island is possible, but no temporaneous communication is possible between hosts that reside on distinct islands.

Figure 1. Example of a disconnected MANET

Figure 1 shows a disconnected MANET, which is typical of the kind of network we consider in our work. This MANET is composed of a number of laptops carried by users, which can move in and between buildings (for example, the buildings of a campus). In this example, some laptops are temporarily isolated (either because there is no other laptop within their transmission range, or more simply because they have been put in suspend mode for a while), while other laptops have a number of neighbours, with which they can try to communicate using either single-hop or multi-hop transmissions.

In fully connected wired networks, content-based communication can be achieved by constructing an underlying communication system, whose role is to forward each piece of information from its sender to all interested hosts [START_REF] Carzaniga | Content-based Networking: a New Communication Infrastructure[END_REF]. This system is usually organised as a logical, content-driven routing infrastructure, which itself can be implemented as an overlay network that covers the whole physical point-topoint network. This approach can hardly be applied in a disconnected MANET, since in such a network the absence of end-to-end connectivity between distinct islands precludes building any network-wide overlay.

In such conditions, a method must be devised in order to bridge the gap between non-connected parts of the network. Delay-tolerant networking is an approach that can help with that respect [START_REF] Fall | A Delay-Tolerant Network Architecture for Challenged Internets[END_REF]. In a delay-tolerant network, a message can be stored temporarily on a host, in order to be forwarded later by this host when circumstances permit. If the network includes mobile hosts-or if all hosts are mobile-, then mobility becomes an advantage, as it makes it possible for messages to propagate network-wide, using mobile hosts as carriers that can move between remote-and possibly nonconnected-fragments of the network. In the disconnected MANET shown in Fig. 1, people moving between buildings (or between different parts of a building) can thus contribute to disseminate information between non-connected fragments of the MANET.

In the remainder of this paper we present a protocol for content-based communication we designed along these lines. Since a network-wide content-driven routing structure cannot be constructed and maintained in a disconnected MANET, our protocol does not attempt to build such a structure to support routing decisions. Instead it leverages on the principles of opportunistic networking and of delaytolerant networking. Each host is associated an "interest profile", that describes the kind of information it is interested in. Transient contacts between hosts that happen to reside on the same connected fragment of the network are exploited for exchanging information between these hosts, according to their respective interest profiles. Moreover, a host that behaves as a receiver of a particular kind of information is also expected to serve as a mobile carrier for this information.

The remainder of the paper is organised as follows. The basics of the protocol are described in Section 2. Section 3 presents some of the results we obtained by running simulations. Related work is discussed in Section 4, and Section 5 concludes the paper.

Communication protocol

Our protocol is actually defined as a two-layer stack. The upper layer supports the content-driven, delay-tolerant dissemination of structured pieces of information (or "documents") in the network. It provides support for storing documents in a host's local cache, so this host can serve as a mobile carrier for these documents while moving in the network. It also defines how neighbouring hosts can interact in order to exchange documents according to their respective interest profiles. Neighbouring hosts are hosts that temporarily reside on the same connected fragment of the network. Interaction between such hosts requires that they be able to communicate using either single-hop or multihop transmissions. The lower layer of the protocol provides mechanisms for temporaneous, multi-hop forwarding, which is required in the latter case.

Support for content-driven, delaytolerant document dissemination (upper layer)

The main entities we consider in this layer of the protocol are briefly described below.

Documents, descriptors and identifiers -A document is a structured piece of information a host can send in the network, so it can disseminate and ultimately be received by any host that shows interest for this particular kind of information. A document is actually composed of two parts: its descriptor, and its content. The descriptor can be perceived as a collection of attributes, which can provide any kind of information about the corresponding document, such as its origin, its topic, a list of keywords, the type of its content, etc. As a general rule, we assume that the size of a document is far greater than that of a descriptor, which is itself significantly greater than that of a document identifier (typical orders of magnitude are O(10 kB) for a document, O(100 B) for its descriptor, and O(10 B) for its identifier).

Cache -Each host maintains a cache where documents can be stored. Although the protocol makes no assumption about the storage capacity on each mobile host, it is assumed that this capacity is generally bounded, and that it can be different on different hosts. Note that in this paper we do not attempt to evaluate the merits of different strategies for cache management, as such strategies have already been compared in the literature (e.g. in [START_REF] Harras | Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding in Sparse Mobile Networks[END_REF]). We simply assume that each host implements a caching policy, and that distinct hosts in the network can actually enforce different policies.

Interest profile -The interest profile of a host determines the kinds of documents it is interested in, and thusimplicitly-the kinds of documents for which it is willing to serve as a mobile carrier. For practical reasons, we define this profile as a predicate applicable to document descriptors. By applying this predicate to a document's descriptor, a host can decide if it must store this document in its cache or not.

Interaction between mobile hosts relies on a simple model, whereby each host periodically informs other hosts located in its neighbourhood about its own interest profile and about the documents that are currently available in its local cache. When a host discovers that one of its neighbours can provide a document it is interested in (that is, a document that matches its own interest profile and that is not already available in its own cache), it can request a copy of this document from this neighbour. Transient contacts between mobile hosts are thus exploited opportunistically for exchanging documents between these hosts, based on their respective interest profiles, and based on the documents they can provide each other on demand.

Announcing one's catalog and personal interest profile.

Each host n i periodically broadcasts an announce that combines:

a description of its own interest profile prof (n i ) a catalog cat(n i ), which contains the descriptors of locally cached documents that can be of interest to its neighbours This announce is broadcast as a single control message, whose propagation scope can be set explicitly by the sender (this is explained further in Section 2.2).

By broadcasting its own interest profile, a host lets its current neighbours know what kind of documents it is interested in. Conversely, by receiving similar information from its neighbours, each host can maintain an accurate vision of the kinds of documents they are interested in. Thus whenever a host needs to broadcast an announce, the catalog it contains can be adjusted in order to fit specifically the interest profiles of its neighbours. With this approach, the cost of broadcasting an announce periodically is kept at a minimum: a host that maintains a large number of documents in its local cache can avoid broadcasting systematically a large catalog in the network. Instead the size of this catalog is continuously adjusted in order to fit exactly the needs of its current neighbours.

Receiving a neighbour's catalog. Upon receiving a catalog from one of its neighbours, the receiver examines the descriptors it contains in order to identify documents whose characteristics match its own interest profile, and that are not already in its local cache. If there exist such documents, then the receiver of the announce builds a request that simply contains the identifiers of the documents it would like to obtain from the announcer. This request is then sent to the announcer in a unicast control message.

Processing requests. After broadcasting its catalog, a host may receive requests from several of its neighbours. These requests are processed sequentially: for each requested document, host n i retrieves this document from the local cache, and broadcasts it in the network as the payload of a data message. Notice that this document is broadcast rather than being sent only to the requester in unicast mode. This is because, after broadcasting its catalog, a host may receive a series of requests for the same document (because several neighbours are interested by this single document). In such a case, all the neighbours requesting a single document from the same host can be satisfied with a single broadcast of this document. In order to avoid that consecutive requests for the same document yield a succession of re-transmissions of this document, each host maintains a history of the documents it has broadcast recently. This history is reset every time the host broadcasts a new announce containing its profile and catalog. With this approach, when several neighbours ask for the same document, this document is broadcast only once in the network.

Receiving documents. When a document is broadcast, it can be received by any neighbour of the sender. Any host that receives a document verifies if it is interested by this document. If so, then the receiver puts the document in its cache. Thereafter, this host will serve as a mobile carrier for the newly acquired document, thus contributing to help disseminate this document further in the network.

Support for temporaneous message forwarding among neighbouring hosts (lower layer)

As explained in the former section, the upper layer of the protocol requires that a host be able to send messages (containing either its profile and catalog, a request, or a document) to its current neighbours. Temporaneous message forwarding (as opposed to delay-tolerant forwarding) is thus required in order to exploit transient connectivity between hosts that happen to reside in the same connected fragment of the network for a while. The lower layer of the protocol supports such temporaneous forwarding for unicast and broadcast messages.

Broadcast message forwarding -Multi-hop broadcasting in a MANET is known to be a bandwidth-consuming activity, which can occasionally lead to the so-called "broadcast storm" problem. In order to limit the overhead due to message broadcasting, the lower layer of our protocol implements a mechanism that is inspired from that used in the Optimized Link State Routing (OLSR) protocol for diffusing link-level information in the network [START_REF] Clausen | Optimized Link-State Routing Protocol (OLSR)[END_REF][START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF]. Basically, each node regularly selects a subset of its direct neighbours as multi-point relays (MPR), and it then relies exclusively on these MPRs for forwarding broadcast messages beyond its own radio coverage. The scope of a broadcast can be controlled by specifying how many hops a message is allowed to perform while being relayed by MPRs. Figure 2a shows an example, where host A broadcasts a message, which could be for example an announce containing its profile and catalog. In this example the message is allowed to propagate up to its 3-hop neighbours, but not further.

The algorithm used by each host to construct its MPR set is not detailed in this paper for the sake of brevity. Indeed we use the same algorithm as that described in [START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF]. Basically, each host must periodically broadcast a control message in order to inform its direct (one-hop) neighbours about its presence in the network, while informing these neighbours about its own current vision of its neighbourhood. By receiving such control messages, each host can identify its one-hop and two-hop neighbours, and use this information to calculate its MPR set. With the approach described in [START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF], specific control messages are broadcast periodically, that contain the information needed for calculating MPR sets. In our implementation, this information is piggy-backed in the announces the upper layer of the protocol must also broadcast periodically. Thus the calculation of MPR sets does not imply sending any additional message in the network: both kinds of control information (required by both layers of the protocol) are broadcast together in the network.

Unicast message forwarding -The upper layer of the protocol requires that mobile hosts be able to send requests as replies to an announce they have just received. Unicast messages must thus be forwarded towards the sender of a broadcast message. Source-routing is used as a means to perform this forwarding. Each broadcast message that propagates in the network encapsulates a history of the hosts by which it has been forwarded so far. Thus, whenever the receiver of a broadcast message decides to reply to this message, the path for sending this reply to its source is simply deduced from the path the former broadcast message has followed before reaching the receiver. Note that, in order to be effective, this approach requires that when a host decides to reply to a broadcast message, this reply is sent immediately after the broadcast message has been received. In such conditions, the path the broadcast message has followed downwards to reach the receiver is still valid in the network, so it can be followed upwards to the sender of the broadcast message.

Consider again the example shown in Fig. 2-a, and assume that hosts B, Q, and O decide to reply to the message broadcast by A. Figure 2-b shows how their replies can propagate upwards along the path the broadcast message has just followed downwards, each reply containing a specification of the path it must follow before reaching host A.

Evaluation

Our protocol for content-driven, delay-tolerant communication has been fully implemented in Java, and interfaced with the MADHOC simulator [START_REF] Hogie | The MADHOC simulator[END_REF]. Based on this combination we run a number of simulations in order to observe how the protocol can perform in different conditions. In this section we present some of the results we obtained by performing series of 14.000 second simulation runs, with the following parameters and communication scenario.

Simulation parameters. We consider a simulation scenario in which a population of 120 users move in and between a set of five buildings, which are located within a 1 km × 1 km area. Each building has a rectangular shape, with edges between 100 and 150 meters long. Each user is assumed to carry a laptop equipped with an IEEE 802.11 (Wi-Fi) interface.

The mobility of users-and therefore that of the mobile hosts they are carrying-is simulated using a variant of the random waypoint model: a user can remain motionless for a while, afterwards he/she begins to walk towards a set destination, which is selected randomly in any one of the buildings in the simulation area.

In the simulation runs whose results are discussed below, we used the following mobility parameters: users are assumed to walk at speeds varying between 0.5 m/s and 2 m/s; a stay between two consecutive moves can last between 30 seconds and 3 minutes; and the amount of intrabuilding mobility is set to 40 % (against 60 % for interbuilding mobility). Wi-Fi interfaces are assumed to have an omni-directional transmission range of 40 meters when used indoor, and 100 meters when used outdoor.

Communication scenario. We consider a communication scenario whereby all mobile hosts continuously produce new documents and send these documents in the network. Each document weighs 50 kB, and documents are introduced in the network at an average global rate of one new document every 2.5 seconds. Topic-labelling is used as a simple means to differentiate these documents: there are 16 different topics, but each document pertains to only one of these topics.

Each mobile host is interested in only two distinct topics (hence 1/8 of the global traffic). No two different hosts in the network have exactly the same interest profile.

Protocol parameters. Our protocol can be adjusted by setting two parameters. The first parameter is the period with which a host broadcasts an announce (containing its own profile and a catalog of the documents it proposes to its neighbours). We set this period at 15 seconds, for experience proves that this value is generally adequate in a MANET where hosts move at pedestrian speeds.

Another parameter is the maximum number of hops used in temporaneous message forwarding, and most notably when a host broadcasts an announce. By adjusting this parameter, we can somehow extend the "sphere of communication" of each host, controlling the scope of the announces it broadcasts periodically, and therefore the number of neighbours with which it is liable to exchange documents before moving to another part of the network.

Speed of document propagation. Our primary objective is to show how the scope of temporaneous message forwarding can influence the performance of our protocol. The expected result is that, when a mobile host is allowed to use multi-hop forwarding in order to interact with a large number of neighbouring hosts, documents can disseminate faster than when each host can only exchange documents with direct (one-hop) neighbours.

In order to verify that this expectation is met, we first consider a-somewhat unrealistic-scenario where documents can propagate eternally in the network. We notably assume that the cache capacity on each host is unlimited, and that no document is given a lifetime.

The mobility model used during the simulation ensures that each host eventually gets close to any other host in the network. In such conditions, a document that can propagate forever in the network is guaranteed to eventually reach any interested receiver. Yet the time before this document is delivered to a receiver can be influenced by the protocol parameters, and notably by the scope of temporaneous message forwarding.

In Figure 3 we consider how long it takes for documents to reach their receivers. More precisely, Fig. 3-a shows the normalized distribution of the age of these documents at delivery time, and Fig. 3-b shows the corresponding cumulative distribution.

Let us first consider the case where the hosts can only use 1-hop transmissions. In such circumstances it can be observed that about 40 % of the documents are delivered in less than 30 minutes. After an hour, about 75 % of the documents have reached their receivers, and after two hours about 90 % have been delivered.

Let us now observe how multi-hop forwarding can influence the performance of document dissemination. Fig 3-a shows that, when temporaneous 2-hop forwarding is used (that is, when each host can interact directly with its 1-hop and 2-hop neighbours), most documents are received after about 20 minutes (against 30 minutes when only 1-hop forwarding is used). In such conditions about 98 % of the documents are actually received in less than two hours, about 90 % in less than an hour, and about 60 % in less than 30 minutes.

A similar-though comparatively minor-improvement can be observed when multi-hop forwarding is pushed further, so that each host is allowed to extend its sphere of communication up to its 3-hop, 4-hop, and 5-hop neighbours respectively. Indeed, with the simulation parameters

Figure 3. Distribution and cumulative distribution of the age of documents at delivery time

used during this experiment, the islands (or connected fragments of the network) that can form in the buildings have a limited extension. Their elongation varies between 0 (isolated hosts) and 7 hops, with an average value of 4.2 hops. This explains why extending the sphere of communication of each host beyond a couple of hops does not bring much improvement. Another reason is that the propagation of documents between different buildings (or between nonconnected parts of a building) depends primarily on how fast document carriers-that is, pedestrians in the scenario considered-actually move in the simulation area.

In any case, this first experiment confirms that by extending the sphere of communication of each mobile host our protocol allows documents to disseminate better and faster in each island, thus increasing the number of hosts that can then serve as carriers between non-connected parts of the network.

Figure 4. Satisfaction ratio (of document delivery) vs. cache capacity

Cache capacity. In the simulation runs whose results were discussed above, we assumed that documents could propagate forever in the network. As mentioned above this is not very realistic, since most resources in a MANET are usually severely constrained. For example the cache where mobile hosts can store documents is of limited capacity. An adequate policy must thus be devised-and then enforced on each host-in order to deal with saturation conditions. Figure 4 shows how the capacity of each host's cache can influence the performance of document dissemination. To obtain these results we run a series of simulations, considering cache capacities ranging between 50 and 200 documents. During each simulation the cache policy enforced was such that, when a cache reached saturation, the oldest document in this cache was discarded in order to make room for a new document. In the figure we plot the satisfaction ratio (that is, the percentage of documents that are eventually delivered to interested receivers) against the capacity of the cache. First, Figure 4 confirms the natural expectation that a host with a larger cache is liable to carry documents further and longer in the network.

More interesting is the influence of temporaneous multihop forwarding on the performance of document dissemination. In Fig. 4 it can be observed that the satisfaction ratio of document delivery increases significantly when the scope of message forwarding is extended to a couple of hops around each host. Consider for example the case where each host can only maintain 100 documents in its cache. In such conditions, the documents sent in the network are received (on average) by only 78 % of the interested receivers if each host is only allowed to interact with direct neighbours. Yet this figure is increased by 10 % when the scope of temporaneous forwarding is extended to 2-hop neighbours, and again by 2 % when it is extended to 3-hop neighbours. each document a set lifetime, so that whenever a document gets obsolete it is automatically removed from any cache it might have been stored in. This method can be used either as a substitute or as a complement to the method that limits the capacity of each cache.

Document lifetime. Another way to prevent documents from remaining eternally in the hosts' caches is to give

Figure 5 shows how different values of document lifetime influence the performance of document dissemination. These results were obtained with unbounded cache capacity, so that the two types of constraints do not interfere during the simulation. In the figure we plot the satisfaction ratio (percentage of documents that are delivered to interested receivers) against the set lifetime of documents. Not surprisingly, the satisfaction ratio increases as documents are given a longer lifetime. Yet it can again be observed that temporaneous multi-hop forwarding gives significant improvement in document dissemination. For example, when documents are given a 30-minute lifetime, they are eventually received (on average) by only 40 % of the interested receivers if each host is only allowed to interact with direct neighbours. Yet this figure is increased by 20 % when the scope of temporaneous forwarding is extended to 2-hop neighbours, and again by 7 % when it is extended to 3-hop neighbours.

Communication overhead. The above results confirm that by resorting to temporaneous multi-hop forwarding, the dissemination of documents in the network can be made faster, and thus more efficient. They also show that even a slight extension of the sphere of communication of each host (by only two or three hops in the scenario considered) can bring a significant improvement over a situation where a host can only interact with direct neighbours.

The drawback of multi-hop forwarding is that it yields an important overhead in terms of the resources it mobilises on each host. Indeed, whenever a host forwards a message, this transmission drains the battery of this host, while occupying the shared wireless medium around this host.

While designing our protocol we decided to rely on MPR-based forwarding for broadcasting messages around each host. Obviously it would have been a lot easier for us to use plain flooding for broadcasting these messages. Since above-mentioned results show that messages need only be forwarded on a limited scope (typically, two or three hops) it is worth wondering whether MPR-based forwarding brings any benefit over plain flooding in such conditions.

In order to evaluate the difference between our approach relying on multi-point relays and an alternate one relying on plain flooding, we implemented a variant of our protocol that uses plain flooding as a means to broadcast messages around each sender. The results are presented in Figure 6. They were obtained when running our communication scenario during four hours (in simulation time), with unlimited cache capacity and 1-hour document lifetime.

It can be observed (Fig. 6-a) that the MPR-based and flooding-based versions of the protocol do not give exactly the same satisfaction ratio. This is because the MPR-based version is slightly slower at disseminating documents in the network. Indeed, with this version a host whose neighbourhood changes needs to wait a while (precisely, two consecutive announce cycles) because it can effectively interact with its new neighbours. In contrast, with the floodingbased version of the protocol a host whose neighbourhood changes can immediately reach its new neighbours.

The satisfaction ratio observed with the MPR-based version of the protocol is therefore slightly lower than with the flooding-based protocol. Yet this difference remains under 3 %, while the cost of using one or the other way of broadcasting messages is very different. Figure 6-b shows how the cost of transmissions compares with both versions of the protocol. Obviously our decision to rely on multi-hop relays for forwarding broadcast messages is fully justified, as the global number of messages sent when using multi-hop relays is far below that observed when flooding messages in the network.

Related work

A number of protocols have been designed in the last few years in order to support destination-driven routing in disconnected MANETs [START_REF] Zhang | Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges[END_REF][START_REF] Pelusi | Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks[END_REF]. In contrast content-based communication in such networks has not justified much research so far. Many papers about content-based communication have already been published, but these papers consider either stable, wired networks, or fully connected MANETs [START_REF] Costa | Semi-Probabilistic Content-Based Publish-Subscribe[END_REF][START_REF] Meier | STEAM: Event-Based Middleware for Wireless Ad Hoc Network[END_REF][START_REF] Petrovic | Content-Based Routing in Mobile Ad Hoc Networks[END_REF]. They usually propose to construct and maintain content-based routing structures in order to forward messages efficiently between publishers and subscribers. A notable exception with that respect is the protocol defined in [START_REF] Baldoni | Content-Based Routing in Highly Dynamic Mobile Ad Hoc Networks[END_REF]. Like ours this protocol does not attempt to build any structure to support routing decisions. Instead it too relies on broadcast transmissions, while deferring to hosts that receive a message the decision to forward this message to potential subscribers, based on an estimation of their distance to these subscribers. Yet this protocol requires that temporaneous end-to-end paths exist between senders and receivers. It could not run satisfactorily in a disconnected MANET.

Content-based dissemination in disconnected MANETs is addressed specifically in [START_REF] Costa | Adaptive Content-based Routing for Delay-tolerant Mobile Ad Hoc Networks[END_REF], which describes an approach whereby a content-driven multi-hop routing structure (limited to a given horizon) is built around each host. A utility-based function is used in order to select the best forwarders for each kind of message, and mobile carriers help disseminate messages between non-connected parts of the network. Our protocol relies on a slightly different approach. Instead of attempting to construct and maintain a routing structure, it relies on periodic broadcast transmissions (also limited to a given "horizon" from the sender), whereby each host periodically informs its neighbours about the documents it is carrying and that match their interest profiles. Upon receiving such a catalog a host can request the transmission of a document it is actually missing. Thus no document is sent in the network unless it has been requested explicitly by a client host.

Our protocol also compares with the-somehow more abstract-Autonomous Gossipping (A/G) algorithm [START_REF] Datta | Autonomous Gossiping: a Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Mobile Ad-Hoc Networks[END_REF]. Indeed, both protocols fit in the general category of gossipbased protocols. They rely on the principle of letting neighbouring hosts opportunistically exchange documents they are missing, based on their respective advertised profiles. In the A/G algorithm, information dissemination is perceived as an epidemic process: each host is considered as being more or less vulnerable to being "infected" by one or another kind of data item. One difference between our protocol and the A/G algorithm is that the latter only relies on direct interactions between one-hop neighbours, whereas ours supports interaction through multi-hop transmissions. The A/G algorithm is also potentially more flexible than our protocol, as it defines a variety of data processing policies (such as migration, replication, and reconciliation), while our protocol only relies on document replication to disseminate infformation in the network. Finally a major difference is that, to the best of our knowledge, the A/G algorithm was never actually implemented (except as a simulator), whereas our protocol has been fully implemented, so it can now run either in real conditions, or coupled to a simulator.

Conclusion

In this paper we have presented a new protocol for content-based communication in disconnected MANETs. Unlike other protocols that rely on costly methods for constructing and maintaining content-driven routing structures, ours does not attempt to build any such structure. Instead it exploits transient contacts between mobile hosts that get close enough to one another, allowing these hosts to exchange documents according to their respective interest profiles. Communication between non-connected fragments of the network is performed thanks to mobile hosts, each host serving as a carrier the kind of information it is interested in. Simulation shows that our protocol is effective at propagating documents between senders and interested receivers. It also confirms that temporaneous multi-hop forwarding helps disseminate documents in connected fragments of the network, which in turn has a positive influence on this dissemination in the whole, disconnected network. By adjusting the extension of multi-hop forwarding around each host, the resulting transmission overhead can be balanced against the benefit observed in document dissemination. With the current version of the protocol the number of hops used when broadcasting messages is set as a constant parameter. In the future we plan to investigate methods allowing each host to adjust this value dynamically, accounting for its current situation in the network (e.g. number and density of neighbours, interest profiles of these neighbours, history of recent document exchanges in the neighbourhood, etc.).

Figure 2 .

 2 Figure 2. Illustration of the two kinds of temporaneous message forwarding supported by the lower layer of our protocol

  Distribution of the age of documents at delivery-time Smoothed cumulative distribution of the age of documents at delivery-time

Figure 5 .

 5 Figure 5. Satisfaction ratio (of document delivery) vs. document lifetime

Figure 6 .

 6 Figure 6. Comparison of the MPR-based and flooding-based versions of the protocol

Acknowledgements. This work is supported by the French Agence Nationale de la Recherche under contract ANR-05-SSIA-0002-01.


Fabienne Battaglia-Brunet

Catherine Joulian

H Tris

Jérôme Jacob

Corinne Casiot

Marina Hery

Remediation of arsenic rich acid mine water in sulfate reducing bioreactors

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Past and present mining activities constitute one of the major sources of arsenic (As) pollution in the environment. Low-cost remediation options for mine water treatment generally combine aerobic and anaerobic steps. Each step must be designed to optimize process efficiency and decrease the cost of the global remediation facility. Sulfate-reduction in acidic conditions was proposed as a bioprocess to precipitate selectively metals from AMD [START_REF] Ňancucheo | New (micro-)biological strategies that enable the selective recovery and recycling ofmetals from acid mine drainage and mine process waters[END_REF]. The objective of the present study is to determine the optimal process to remove metals and As from the Carnoulès acid mine water, containing about 1 g/L iron (Fe), 100 mg/L As and 20 mg/L zinc (Zn) as the most concentrated metals and metalloïds. In this case, it would be beneficial to precipitate selectively As and Zn as sulfides through the activity of endogenous sulfate-reducing bacteria (SRB), and keep Fe in solution in order to remove it in a downstream oxidation/precipitation step. Thus, the need of organic substrate for SRB would be limited, as Fe is far more concentrated than As and Zn. With this aim, laboratory experiments were performed in two continuously fed columns in series. Then, the SRB bioreactor must be up-scaled from 0.3 L to 100 L to study the bio-treatment on site. Up-scaling implies amplification of the active biomass and modifications of the bioreactor characteristics (design and filler material).

METHODS

The small bioreactors consisted of 320 mm high glass columns with an internal diameter of 35 mm. Two columns were disposed in series, with succes-sive glycerol (electron donor) supplies. The exact amount of glycerol necessary for As precipitation was directly added to the main feed entering the first column. Between the two columns, a secondary glycerol supply corresponding to the exact quantity necessary to precipitate Zn was provided as a concentrated solution. The filler material was conceived with two aims: (1) to distribute passively nutrients to the bacteria, and (2) to establish different levels of activities in the two columns. For this last reason, the yeast extract concentration in the filler material was lower in the first column than in the second one. The filler material was prepared with pozzolana pieces impregnated with nutrient agar containing 0.78 g/L H2PO4 and 0.2 (column 1) and 2 (column 2) g/L of yeast extract. The columns were first fed (residence time 40 to 80 h in each column) with a synthetic mine water until day 55, then with the real Carnoulès mine water adjusted at pH 3.6 (until day 75), and finally with the real AMD without pH adjustment. The two bioreactors were inoculated simultaneously with a microbial consortium sampled from a previous column experiment [START_REF] Battaglia-Brunet | Development of a passive bioremediation process based on sulfate-reduction to treat arsenic-containing acidic mine water[END_REF]. For upscaling, a 0.3 L column was used to inoculate a 5 L column. The filler material of this 5 L column was composed of a mixture of 10% pozzolana embedded in nutrient agar (2 g/L yeast extract) and 90% of clean pozzolana. During up-scaling, the 0.3 L and 5 L columns were fed with the real Carnoules mine water, with no pH modification and enriched with 0.5 g/L glycerol and 1 g/L yeast extract. Fe, As and Zn were quantified by Atomic Absorption Spectrophotometry (AAS), and bacterial communities were identified by cloning-sequencing of 16S genes. (AMD) can be obtained in anaerobic bioreactors thanks to sulfate-reducing bacteria (SRB) through the precipitation of arsenic sulfide. The present study aimed to develop the sulfate-reducing anaerobic step of a bioremediation scheme to treat AMD rich in As, zinc (Zn) and iron (Fe). Column bioreactors worked in series, with differential supply of organic substrates, i.e. yeast extract and glycerol. This strategy allowed to modulate pH and to efficiently precipitate As and Zn in the columns, although it was not possible to selectively recover Zn alone. Most part of the Fe remained in solution, and was treated downstream by oxidation, allowing the co-precipitation of residual As. The SRB biotreatment is currently up-scaled and will be tested on site.

RESULTS AND DISCUSSION

Small columns experiment

The sequential supply of electron donors efficiently induced a pH gradient between the feed water, the columns 1 outlet and the column 2 outlet (Fig. 1). The pH of the column 1 outlet remained stable close to pH 4.4 whereas the pH of the column 2 outlet was more variable (from 4.8 to 6.5). Only a small percentage of As and no Zn was removed in column 1 (Fig. 2 and3). As removal in column 2 was variable, but reached nearly 100% at some periods of the experiment. Zn removal in column 2 also reached 100% during some phases, in particular with the real AMD at pH 3.6 (days 60 to 75). No Fe was precipitated in column 1, however Fe removal reached 20-30% in column 2. At the end of experiment, the most abundant 16S rRNA sequences found in the liquid phase of the bioreactors were affiliated to the genera Cellulomonas, Bacillus, Clostridium, Burkholderia, and Desulfosporosinus as the only detected sulfate reducer.

Up-scaling

In the 5 L column, pH was rapidly raised from 3.6 (pH of the real AMD with 1g/L yeast extract and 0.5 g/L glycerol added) to pH 7 in the outlet. The objective here was not to treat the water but to develop a volume of inoculum sufficient to start the SRB treatment in a 100 L bioreactor that will work on the site. The total residence time was very high (40 days), however sampling at different levels along the column showed that, in less than 250 h, the SRB removed nearly entirely As, Zn and Fe from the real mine water: the remaining concentration in the mine water sampled at 1/4 of the column total height, the closest sampling port from the feed, was less than 1 mg/L of As, less than 0.5 mg/L Zn and between 0.2 and 36 mg/L of Fe.

CONCLUSIONS

Results showed that adjusting the availability of organic substrates (yeast extract and glycerol) allows the modulation of pH increase and consequently the type of elements that precipitate as sulfides in the bioreactor. This principle will be applied through up-scaling of SRB bioreactor on site, to remove Zn and partly As (but not Fe) in an anaerobic treatment step. Up-scaling from 0.3 to 5 L, with a 90% decrease of nutrient agar in the filling material, was successfully achieved. The next steps will be performed on site in 25 L then in 100 L bioreactors, accompanied by a decrease of nutrient supply and residence time.

Figure 1 .

 1 Figure 1. Evolution of pH during experiment with columns in series.

Figure 2 .

 2 Figure 2. Evolution of As concentration during experiment with 2 columns in series.

Figure 3 .

 3 Figure 3. Evolution of Zn concentration during experiment with 2 columns in series.

  Remediation of arsenic-rich acid mine water in sulfate-reducing bioreactors F. Battaglia-Brunet, C. Joulian, H. Tris, J. Jacob BRGM, Water, Environment, Process and Analyses Division, 3, avenue Claude Guillemin, 45060 Orléans, France C. Casiot, M. Hery Arsenic (As) is a toxic element commonly found in mining sites. Removal of As from Acid Mine Drainages

	HydroSciences Montpellier, Univ. Montpellier-CNRS-IRD, Montpellier, France -CC57, 163 rue Auguste
	Broussonet, 34090 Montpellier, France
	SUMMARY:

ACKNOWLEDGEMENTS

This work was supported by the French National Research Agency in IngECOST-DMA project (ANR 2013-ECOT-0009) and by ADEME in CompAs project (contract 1872C0004).