Guang Tan

Stephen A Jarvis

Anne-Marie Kermarrec

Connectivity-Guaranteed and Obstacle-Adaptive Deployment Schemes for Mobile Sensor Networks

Keywords: Sensor Networks, Mobile, Deployment, Connectivity. 3

Mobile sensors can relocate and self-deploy into a network. While focusing on the problems of coverage, existing deployment schemes largely over-simplify the conditions for network connectivity: they either assume that the communication range is large enough for sensors in geometric neighborhoods to obtain location information through local communication, or they assume a dense network that remains connected. In addition, an obstacle-free field or full knowledge of the field layout is often assumed. We present new schemes that are not governed by these assumptions, and thus adapt to a wider range of application scenarios. The schemes are designed to maximize sensing coverage and also guarantee connectivity for a network with arbitrary sensor communication/sensing ranges or node densities, at the cost of a small moving distance. The schemes do not need any knowledge of the field layout, which can be irregular and have obstacles/holes of arbitrary shape. Our first scheme is an enhanced form of the traditional virtual-force-based method, which we term the Connectivity-Preserved Virtual Force (CPVF) scheme. We show that the localized communication, which is the very reason for its simplicity, results in poor coverage in certain cases. We then describe a Floor-based scheme which overcomes the difficulties of CPVF and, as a result, significantly outperforms it and other state-of-the-art approaches. Throughout the paper our conclusions are corroborated by the results from extensive simulations.

INTRODUCTION

In a mobile sensor network the sensors are able to relocate and self-organize into a network. The mobility and self-management of sensors are desirable for many application scenarios, including remote harsh fields, disaster areas, or toxic urban regions, where manual operations are unsafe or burdensome. In this paper we consider the following self-deployment problem: Given a target sensing field with an arbitrary initial sensor distribution, how should these sensors self-organize into a connected ad hoc network that has the maximum coverage, at the cost of a minimum moving distance?

There have been a number of proposed solutions to this problem, including that based on the concept of potential fields [START_REF] Howard | Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem[END_REF] or virtual forces [START_REF] Zou | Sensor Deployment and Target Localization Based on Virtual Forces[END_REF]. This approach imitates the behavior of electro-magnetic particles: when two electro-magnetic particles are too close in proximity, a repulsive force pushes them apart. Applied to a sensor network, this method helps move sensors from high density to low density areas, thereby minimizing sensing overlap and improving the overall network coverage. Another commonly used approach relies on the use of Voronoi Diagrams (VDs) [START_REF] Cortes | Coverage control for mobile sensing networks[END_REF] [START_REF] Heo | Energy-Efficient Deployment of Intelligent Mobile Sensor Networks[END_REF] to partition the field into many sub-areas, one for each sensor, allowing sensors to move to maximize coverage in its own sub-area. A combination of these two approaches is also possible; see [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF].

While existing methods prove to be effective under certain models, they have several problems in practice. First, they assume that a sensor can easily detect all (or most) of its Voronoi neighbors through local communication. This assumption may not however be satisfied in a real network, because the communication range of a sensor may not be large enough to cover all Voronoi neighbors. An incomplete view of the Voronoi neighbors may result in very inaccurate VDs being constructed. Consequently, significant sensing overlaps or voids among sensors may be ignored, leading to poor network coverage. Figure 1 illustrates the impact of communication range on the construction of Voronoi cells. In Figure 1(a), O's communication range is such that it will detect all of its Voronoi neighbors, enabling it to construct a correct Voronoi cell; in Figure 1(b) however, the shorter communication range only covers four of the Voronoi neighbors, yielding an incorrect Voronoi cell.

A second problem with existing studies is that when concentrating on the motion planning of sensors, they tend to assume that the network remains connected throughout the process of sensor relocation. However, the implicit assumption that the network connectivity can be guaranteed by a high node density, or a large communication range, does not hold in general; network partitions can still occur in a dense network. As a critical requirement for a network to function normally, connectivity must be considered in protocol design. A third problem that we observe with existing schemes is that when planning sensor relocation to increase coverage, most existing studies assume that the sensing field is obstacle-free (e.g., [START_REF] Wang | Sensor Relocation in Mobile Sensor Networks[END_REF] [START_REF] Yang | Scan-Based Movement-Assisted Sensor Deployment Methods in Wireless Sensor Networks[END_REF]). This greatly simplifies the motion planning and optimization problem, but in so doing it is clear that many real-world environments (a metropolitan area with buildings, or a rural environment with plants and water etc.) that naturally have obstacles or holes, render such schemes ineffectual. This significantly weakens the potential applicability of such approaches.

In this paper, we present new schemes that are not governed by the above simplifying assumptions, and thus adapt to a much wider range of application scenarios. While maximizing sensing coverage, our distributed schemes also aim to achieve three additional goals: [START_REF] Bai | Deploying Wireless Sensors to Achieve Both Coverage and Connectivity[END_REF] to achieve connectivity for a network with an arbitrary initial distribution, communication/sensing range, or node density; (2) to minimize moving distance, which dominates energy consumption in the deployment process;

(3) to be able to work without any knowledge of the field layout, which can be irregular and have obstacles of arbitrary shape. This is important for deployment in an environment whose layout is not fully known in advance. The lack of topological knowledge also makes a central server-based deployment solution infeasible.

To the best of our knowledge, no published work addresses all these issues simultaneously. Optimization of the multiple objectives (coverage and moving distance) under the constraint of global network connectivity for general network topologies is known to be a challenging task; even sub-problems of this have been shown to be difficult. For instance, Wang et al. show that introducing a minimum number of sensors to completely cover a target area is strongly NP-hard [START_REF] Wang | A Bidding Protocol for Sensor Deployment[END_REF]. In view of the complexity of the problem, our design is heuristic-based and supported by comprehensive experimental evaluation.

Our first solution is called the Connectivity-Preserved Virtual Force (CPVF) scheme, which is an enhanced form of the virtual-force-based method with the additional consideration of the connectivity requirements. We show that the localized communication, which is the very reason for its simplicity, results in poor coverage in cases of small communication ranges and obstacles. We then consider a Floor-based scheme (or FLOOR for short) which divides the field into fixed-height floors and encourages sensors to maintain a particular floor-height level. The coverage expansion process of FLOOR can be regarded as being similar to the growth of a plant from the Vitis genus (e.g. a common vine). Simulations show that FLOOR overcomes all the difficulties of CPVF and several previous algorithms, and significantly outperforms them in terms of coverage, moving distance, and convergence time.

The remainder of this paper is organized as follows. Section 2 documents related work and Section 3 introduces preliminaries of the proposed schemes. Section 4 presents the CPVF scheme in detail; Section 5 describes the FLOOR scheme.In Section 6 we evaluate the performance of a number of different schemes through extensive simulations. Finally, Section 7 concludes the paper.

RELATED WORK

Sensor deployment problems have been studied in a variety of contexts. It is widely recognized that when deploying sensor networks, coverage and connectivity must be considered together. The authors in [START_REF] Xing | Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks[END_REF] provide a geometric analysis of the fundamental relationship between coverage and connectivity, and present protocols to achieve a desired degree of coverage while maintaining network connectivity. They prove that when the communication range r c is at least twice the sensing range r s , then coverage implies network connectivity.

The assumption r c ≥ 2r s greatly simplifies the design of coverage-oriented protocols (for instance, the locationfree coverage protocol [START_REF] Younis | Coverage Without Location Information[END_REF] and obtaining tradeoffs between mobility and coverage [START_REF] Wang | Trade-offs Between Mobility and Density for Coverage in Wireless Sensor Networks[END_REF]); at the same time this assumption also limits the protocol's applicability. Bai et al. [START_REF] Bai | Deploying Wireless Sensors to Achieve Both Coverage and Connectivity[END_REF] first present a full picture of optimal deployment patterns that achieve both coverage and connectivity for general values of r c /r s . In particular, they show a stripbased pattern that achieves asymptotically optimal coverage with one-connectivity, and for two-connectivity, some variants of the strip pattern are also proposed.

In [START_REF] Bai | Deploying Four-Connectivity And Full-Coverage Wireless Sensor Networks[END_REF], the authors consider the same problem with a higher degree of connectivity. While these work provides useful guidelines for real network deployment, their analysis only considers an obstacle-free plane, therefore the results do not apply to a field with holes of general shape.

In a mobile sensor network, the mobility of sensor nodes provides the possibility for the nodes to selforganize to a network with desired properties from an arbitrary initial distribution. Howard et al. [START_REF] Howard | Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem[END_REF] employ the potential field method in sensor deployment, assuming a line-of-sight connectivity; that is, a sensor is always able to determine the location of nearby nodes. This actually requires special sensing ability or alternatively, a large communication range, in a non-dense network. Zou. et al. [START_REF] Zou | Sensor Deployment and Target Localization Based on Virtual Forces[END_REF] propose a VF-based deployment scheme, which is centralized and only works for a small cluster of sensors.

In [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF], Wang et al. present a set of VD-based schemes to maximize coverage. The VDs are used by sensors to detect coverage holes in their vicinities, and sensor locations are adjusted round by round so that the coverage is gradually improved. Other schemes that have employed VDs include [START_REF] Wang | A Bidding Protocol for Sensor Deployment[END_REF] [14] [4] [START_REF] Heo | Energy-Efficient Deployment of Intelligent Mobile Sensor Networks[END_REF]. As previously described, this approach implicitly relies on a relatively large r c /r s to guarantee the construction of a correct VD. This condition concerning r c /r s is not always satisfied in practical scenarios, where r c /r s could be any value. Furthermore, their studies do not consider the problems of connectivity and obstacles.

Yang et al. [START_REF] Yang | Scan-Based Movement-Assisted Sensor Deployment Methods in Wireless Sensor Networks[END_REF] use a grid-based network structure to detect low density areas, and then maximize sensing coverage through balancing the sensor distribution. The same structure is also used in [START_REF] Wang | Sensor Relocation in Mobile Sensor Networks[END_REF] to identify redundant sensors. Unfortunately, a grid structure is feasible only for networks with relatively high densities, which, again, translate to a relatively large r c . In addition, both sets of research require an obstacle-free field.

Liu et al. [START_REF] Liu | Mobility Improves Coverage of Sensor Networks[END_REF] study the dynamic coverage of a sensor network. They show that while the mean coverage at any given time instance remains unchanged, a larger area will be covered during a time interval because of sensor movement. A similar concept called sweep coverage is studied in [START_REF] Cheng | Sweep Coverage with Mobile Sensors[END_REF]. Our work differs from theirs in that we consider only static coverage.

PRELIMINARIES

System assumptions

We assume that all sensors have the same communication range r c and sensing range r s . Both ranges are modeled as an isotropic unit disk, and sensors within r c of a sensor are called that sensor's neighbors. As is the case for many applications, a sensor can determine another sensor's location only by communication. (Relaxing this requirement only simplifies the design.) At any given time, a sensor knows its own position and can recognize the boundary of the obstacles within its sensing range. All sensors are also aware of the boundary of the sensing field. Sensors move in steps of variable size (or distance). In each step, a sensor moves in a straight line at a uniform speed for a fixed amount of time (e.g., 2 seconds), which we term a period and denote by T ; and at the end of that step, it decides the direction and size of the next step, and so on. The maximum moving speed is denoted by V .

We assume that the field is on a 2-D plane, which can contain any number of obstacles of arbitrary shape, as long as the field is connected; that is, any two points in the non-obstacle areas of the field can be connected by a continuous path. There is a reference point O known to all sensors, where O could be the location of the base station or some head sensor; all the sensors will try to connect to O either directly or via multi-hop links. Without loss of generality, we assume O is at (0, 0). The base station knows the total number of sensors in the On its way to R, the sensor encounters two obstacles and moves around them using the right-hand rule.

network while other sensors do not. Sensors do not have a map of the sensor field.

Obstacle avoidance

We use Lumelsky and Stepanov's path planning algorithm [START_REF] Lumelsky | Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shap[END_REF] called BUG2 to help a sensor move from a starting point Start to a destination point T arget in an environment with obstacles. Roughly speaking, this algorithm works as follows. The sensor initially moves along the straight line (Start, T arget), which we call the reference line, until it encounters an obstacle at some hitting point H; then, the sensor follows the boundary of the obstacle using the right-hand rule (i.e., the right hand maintains contact with the obstacle), until it gets back to the reference line at some point. Now, if the sensor finds that it is closer to the T arget than from H, and that it can make progress on the reference line, then it resumes its straight line walk toward the T arget; otherwise it continues to navigate around the obstacle. The above procedure repeats until the sensor reaches the T arget. BUG2 is shown to produce a path of length at most D + i nili 2 , where D is the distance between Start and T arget, n i is the number of times the reference line crosses the ith obstacle, and l i is the perimeter of the ith obstacle. For convex obstacles, BUG2 is essentially optimal. Figure 2 provides an example of this algorithm.

Lazy movement

With multiple hop communication, not all disconnected sensors need to move to get connected. We use a lazy movement strategy to reduce the unnecessary movement as follows. At the end of each step, a sensor checks its neighbors to see if there are any ahead of it (i.e., closer to its current destination); if so, then it chooses the nearest neighbor as its candidate path parent. A sensor with a path parent can stop moving for a period, in the hope that the path parent can become connected, thereby saving its own movement. A sensor can take a neighbor as a real path parent, only when that neighbor is not adopting the sensor itself as a path parent. When the field is irregular or has obstacles, it may be the case that two sensors are waiting for each other's move indirectly.

In our scheme, if a sensor has not moved for a certain number of periods, it will check whether a loop exists. To do this it sends a PathParentInquiry message once a period to the parent path, which forwards the message to its own path parent if available, and so on. If the sensor finally receives such a message sent by itself, then it knows that a loop has been formed, and it simply resumes its suspended walk at the beginning of the next step; the disregarded path parent will not be taken as its path parent again. A sensor stops moving only when it enters the communication range of a connected sensor, at which time it takes the connected sensor as its parent and changes its own state to connected.

THE CONNECTIVITY-PRESERVED VIRTUAL FORCE (CPVF) SCHEME

The traditional virtual force method has the advantage of local communication, coverage maximization capability, and adaptability to obstacles. Therefore our first design is based on this method. Our approach to achieving these three goals is to first guarantee network connectivity by having disconnected sensors move toward the base station to establish connectivity, during which time we try to minimize the moving distance; the virtual forces method is then applied to maximize coverage.

Achieving connectivity

Initially, all sensors are required to decide their states regarding connectivity. The sensors in the immediate vicinity of the base station know that they are connected. Those sensors then flood a message to the network, and sensors receiving such a message, becoming aware that they are also connected, further flood the message into the network (each sensor sends the message only once). After a certain period of time (for example, an estimate of the maximum possible multi-hop transmission delay between two sensors), if a sensor still has not received such a message, it can decide that it is disconnected. In this case, it will allow a small random time period to elapse after which it starts to move using the BUG2 algorithm (with the lazy movement strategy) toward the base station.

Maximizing sensing coverage

All sensors, upon becoming connected, start to move under the influence of virtual forces (VF) in order to maximize sensing coverage. Our goal is to preserve the network connectivity throughout this stage.

The use of virtual forces in our protocol is essentially the same as in previous work (e.g., [START_REF] Zou | Sensor Deployment and Target Localization Based on Virtual Forces[END_REF]): the obstacles and neighboring sensors exert repulsive forces onto a sensor, and the sum of all forces determines the subsequent direction of that sensor. In fact, the VF method is used in our scheme only for determining the direction to move in; the selection of step size needs special care in the interest of network connectivity and maximum coverage: on the one hand, aggressive step sizes may push sensors beyond the communication range and thus cause network partitions; on the other hand, moving too conservatively may result in sensors being distributed far from evenly, which usually means poor coverage. Considering this, we need a sensor to be able to determine the maximum step size it can make without disconnecting the network, or the maximum valid step size, at the end of each step.

Suppose at time t, the beginning of some period, a sensor s needs to check whether a planned move will disconnect itself from a current neighbor s , or whether that move for s is valid. Since the network is an asynchronous system, sensor s may be in the middle of its own period, which we assume ends at time t ≤ t + T . Sensor s first obtains the information of s 's current moving direction, moving speed and period end time t by communication. We assert that if the planned move satisfies the following two conditions, termed the connectivity preserving conditions, then that move will not by itself break the connection between s and s during [t, t + T ]:

1) the distance between s and s at time t is no greater than r c ; and 2) the distance between s 's position at t and s's position at t + T is no greater than r c . In fact, as is proven in Appendix A, the first condition can guarantee the connection being maintained throughout [t, t ]. We consider [t, t + T ] and emphasize the condition by itself because during [t , t + T ], s cannot (and need not) control s 's motion, for s may choose to abandon their connection in order to join a new (parent) sensor. If s does wish to keep the connection with s, then it is s 's responsibility to find an appropriate step size following the above conditions. However, s still needs to guarantee that the connection remains, in case s does not move in its next period; it is for this reason that the second condition must be satisfied.

With the validity criterion for a step size, a sensor can approximately determine the maximum valid step size by checking a set of possible values; for example, V T, 0.9 × V T, . . . , 0.1 × V T, 0, for a certain connection. Nevertheless, there remains an issue of which connections it needs to maintain. The simplest strategy for a sensor is to retain its connections to its current parent and all children all of the time. However, our experimental results show that allowing sensors to change parent provides more freedom for sensors to move around and thus provides more opportunities for the uncovered areas to be explored.

To allow a sensor to connect to a new parent, care needs to be taken not to create loops in the tree. Suppose sensor s wishes to connect to a new parent p, it first needs to "lock" the tree rooted at itself. It sends a LockTree request down the tree. If a receiving node is in the middle of a period or has just decided not to change parent in its next step, then it accepts the request and forwards the request down the tree (or up the tree in the case of a leaf node); at the same time it is "locked", meaning that it cannot change parent unless it receives further instructions. In other cases the receiving node rejects the request and sends an UnLockTree message back, which travels up the tree, unlocking all the nodes on the way, until it reaches s.

If s receives the LockTree message from all its direct children, it knows that the tree has been successfully locked and it can further pursue joining p, otherwise it gives up and waits for a period. When joining p, s first asks p if p is locked by s; if not, then it begins to join p, otherwise it again abandons the task. After joining p, s sends a UnLockTree message down the tree to unlock all the nodes.

There is a time limit for a sensor to determine its next step. If for any reason the above procedure takes longer than that time limit, s simply cancels its movement for the next period. Considering the message overheads of locking trees, we allow a sensor to change parent connection only when it cannot move under its current parent.

Coverage of CPVF

We have developed an event-based simulator using C++ to evaluate the performance of CPVF. In this section we report a set of results showing the coverage ability of the scheme in several typical settings. These results are only intended to motivate our further exploration; more detailed discussion will be given in Section 6.

In the experiments, a total of 240 sensors are initially randomly distributed in a sub-area {(x, y) : 0 ≤ x ≤ 500m, 0 ≤ y ≤ 500m} of a target field {(x, y) : 0 ≤ x ≤ 1000m, 0 ≤ y ≤ 1000m}; the base station is located at (0, 0). Sensors have r c and r s varying between 30-60m; they first move to gain connectivity, and then adjust their positions to maximize network coverage. The maximum moving speed is 2m/s, and the period length is 1 second; the simulation runs for 750 seconds, after which the sensor layout becomes quite stable. We define the metric coverage as the fraction of area that is covered by at least one sensor. In the first scenario (Figure 3(a)), sensors have r c = 60m and r s = 40m and move in an obstacle-free field. It can be seen that CPVF distributes the sensors quite evenly, producing a coverage of 78.8%. When r c reduces to 30m (Figure 3(b)), the situation is very different: the smaller r c makes the sensors cluster together, producing a much smaller coverage of 28.7%. We can see that significant overlap of sensing disks (depicted by the circles) exists in the network, yet most sensors are unaware of this due to their poor ability to contact the sensors in their vicinities. Although the connected network provides the possibility for a sensor to find those whose sensing disks overlap with its own, the geography-based search is a non-local process and requires extra support from the protocol. Even if they can manage to make contact, significant coordination among many sensors may be needed to achieve an agreement of movement that leads to a good layout. The impact of poor coordination is further demonstrated by the poor coverage (37.8%) in Figure 3(c), where r c = 60m, the same as in Figure 3(a), but two rectangular obstacles are now present in the field, leaving three exits to the large vacant area. It turns out that the sensors have considerable difficulty circumventing the obstacles: while a few can make their way out of the two top exits, no sensors can escape from the narrower exit at the bottom of the field. Increasing the run time does not help the sensors disperse: many of them only oscillate infinitely around their centers without being able to expand coverage.

Convergence of CPVF

During the experiments, we have observed another problem with CPVF: that the sensor layout does not converge easily. For many sensors, after a certain point in time, they start moving in a near cyclic way, without being able to move forward or stabilize. This problem is especially serious in a field with obstacles that form narrow or bumpy passages. The reason behind this is that every sensor makes movement decisions based only on the information of its neighbors. While the neighborhood changes, a sensor has to move; its move results in further change to the neighborhood, which forces other sensors to move -the constant change of virtual forces imposed on each sensor thus causes the sensors to move indefinitely.

A similar observation has also been made by Koren et al. [START_REF] Koren | Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation[END_REF]. In particular, they point out that oscillation happens very often in an irregular field which will significantly increase the overhead in terms of moving distance. We discuss this issue in Section 6.

In conclusion, while the VF-based approach has often been adopted in the planning of robotic movement and in mobile sensor deployment [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF] [21] [9] [START_REF] Poduri | Constrained Coverage for Mobile Sensor Networks[END_REF], our experiments suggest that under the connectivity constraint, it delivers good performance only in very restrictive scenarios; an ideal field model as in Figure 3(a) thus conceals its drawbacks. These facts suggest that it is difficult, if not impossible, to remedy the VF method's weaknesses without significantly compromising its localized communication, which is the very reason for its popularity. This motivates us to look for alternative ways to improve the performance of a deployment scheme.

THE FLOOR-BASED SCHEME

In the CPVF method, the sensors move in a greedy fashion to establish connectivity; this can result in arbitrary overlaps of the sensors' sensing ranges. When r c /r s is small, the sensors lack information that can guide them to move apart in a coverage-maximizing way. A common situation is depicted in Figure 4(a), where the large circles represent sensing ranges, and the small circles represent communication ranges; r c /r s is assumed to be 0.5. It can be seen that despite the significant overlap of sensing ranges between the two groups (green and The key idea of our floor-based method is to divide the field into floors of common height 2r s , and to encourage sensors to stay at the central floor lines of those floors, as shown in Figure 4(b). Now that sensors are separated by floors, the overlap of the sensing ranges is much reduced, and so the global network coverage can be improved.

A high-level view

In FLOOR, sensors move in two patterns that bear a resemblance to the growth of a plant from the Vitis genus (e.g., a common vine) over a framework. The framework is composed of field/obstacle boundary lines and floor lines. In the first instance, nodes may expand along the field/obstacle boundaries, following possibly irregular paths; in the second instance, nodes may expand along the straight floor lines. If the floor lines are appropriately spaced, then beginning at some root, we would expect that using these two techniques good coverage will eventually be attained. Figure 5 illustrates the two expansion patterns in a field with two irregular obstacles. The arrows show the directions in which sensors move along the boundary or floor lines. In the formal description, the first pattern is termed boundary-guided expansion, and the second pattern floor-line-guided expansion. These two patterns are performed in parallel. The first pattern is responsible for introducing sensors to the front end of every floor, while the second pattern is responsible for filling in the floors. We can expect that if enough sensor nodes are provided, then the field in Figure 5 will eventually be well covered. Moreover, the sensing overlap will be small due to the floor lines. The floor-based scheme is implemented in three phases: 1) achieving connectivity, 2) identifying movable sensors, and 3) expanding coverage.

floor-line guided expansion boundary guided expansion

In the first phase, sensors move toward the reference point to establish connectivity, following a different trajectory from that in CPVF for the sake of sensing overlap reduction. In the second phase, a class of nodes termed the fixed nodes are determined, and the remaining nodes, termed the movable nodes, are provided the freedom to relocate for coverage expansion (from high-density to low-density areas). In the third phase, movable nodes expand their coverage following the expansion patterns introduced above.

Achieving connectivity

In this phase, a sensor does not move toward the base station in a straight line, as is the case in CPVF. Instead it is required to pass through two intermediate destinations. Suppose the initial location of the sensor is (x, y), then it first moves toward point D 1 , the projection point of (x, y) on its nearest floor line, using the BUG2 motion planning algorithm. Upon reaching D 1 or hitting some obstacle, it takes D 1 as a new starting point, and starts moving toward point D 2 , the projection of D 1 on the y axis. Upon reaching D 2 (or on collision with an object), the sensor takes D 2 as a new starting point and begins moving toward (0, 0). During the algorithm, the lazy movement strategy is used, and the sensor stops once it enters the communication range of a connected node, which then becomes its parent. Note that in FLOOR, the distance between a sensor and its parent is min(r c , 2r s ), and the y axis is regarded as a wall-like obstacle. A more formal description of the above process is given in Algorithm 1. In Figure 6, sensor s 1 moves to (0, 0) after changing direction twice and without encountering any obstacles; sensor s 2 meets two obstacles, thus preventing it from reaching the locations Dest1 and Dest2. By following Algorithm 1, it finally reaches location (0, 0).

Identifying movable sensors

After a sensor becomes connected, it reports to the base station, and waits for a response from the base station. The response message will reach the sensor carrying the IDs of all the sensor's ancestors, which will be kept in the sensor's memory. The base station initiates the second phase after all sensors have reported their arrival, or after a certain time (e.g., an estimate of the maximum time for a sensor to arrive at the base station) has elapsed, whichever is earlier.

The purpose of the second phase is to identify sensors that can move without partitioning the network, and whose move is expected to increase network coverage. The former condition requires a sensor to help all of its children to find new parents. This can be done as follows. It first obtains a list of neighbors within two hops of itself, and then tries to find for each child a new parent. For a particular child, it needs to check if the child joining some candidate parent will cause a loop, which can be done by simply checking the candidate parent's ancestor list. If all the children can find parents without creating loops, then it means that the sensor can safely move away. To become movable, a sensor also needs to decide whether its move is worthwhile in terms of coverage: it estimates the area currently covered exclusively by itself using the location information of its neighbors; only when such an area is below a certain threshold does it become movable.

To ensure state consistency, the procedure of identifying movable sensors needs to be serialized. This can be coordinated by a message traversing the tree in, for example, a depth-first manner. Such a message can be initiated by the base station at the start of this phase.

Determining the coverage status of a point

A sensor often needs to determine whether a point in its vicinity is covered by others, so that it can decide whether it needs to invite some movable sensor to fill that uncovered area. As demonstrated earlier, local communication is inherently limited in its ability to detect the coverage status of a point beyond a sensor's sensing range, especially when r c /r s is small; thus some method of non-local communication is inevitable.

With the field divided into floors, we are able to implement a simple scheme that solves this problem. We define a floor header node as the node with the smallest x-coordinate in a floor. (Ties can be resolved using the nodes' IDs.) Each floor header node maintains a data structure that records the locations of the nodes in its floor. Since many fixed nodes are linked with the same (or approximately the same) inter-node intervals, and thus share the same y-coordinate (i.e., they reside on the same floor line), their locations can be summarized in a compact form: given a sequence of such nodes, only the first and the last nodes' x-coordinates need to be recorded. For instance, in the layout shown in Figure 8(a), the floor header nodes need to record only a small amount of information concerning the nodes locations on their floor lines. When a node s needs to determine whether a point p beyond its sensing range is already covered, it firsts checks whether any of its neighbors covers that point; if not, it then calculates the possible floors that may contain a node whose sensing range can reach p. s then sends a query message to the floor header nodes corresponding to those floors. Those floor header nodes can in turn determine whether p is covered by any sensor in their own floors, and send back their responses, from which s can determine p's coverage status. Note that this task need not be done with perfect accuracy, since strict performance optimality is not our goal.

Every node in the tree records the floor header nodes in the sub-tree rooted at itself, so the query messages can be easily routed on the tree. Given a field of fixed width and a fixed r c , there will be a constant number of floor header nodes, therefore the memory overhead will be bounded.

Expanding sensing coverage

With all movable sensors identified, we can now expand the network's coverage by having those sensors move to uncovered areas. In Section 5.1 we provide a high-level description for floor line guided expansion (FLG-expansion) and boundary line guided expansion (BLG-expansion). We will also describe a third type of expansion, termed inter-floor line guided expansion (IFLGexpansion).

For each type of operation, a sensor first needs to find an expansion point (EP) on its expansion circle, defined as the circle of radius min(r c , r s ) centered at its current location, after which it invites some movable sensor to relocate to the EP. When searching for expansion points, we only consider the environment consisting of fixed nodes. A formal description of this process is given in Algorithm 2.

Finding expansion points

• FLG-expansion. A sensor s tries to obtain a floor line segment covered by its sensing range (see Figure 7(a)). If such a segment exists, it picks one endpoint of that line segment that is farthest to the y-axis. Such a point is called a frontier point. Next, s determines whether that frontier point is covered by other sensors using the method introduced in Section 5.4. If s can find an uncovered frointer point, it calculates the intersection between its expansion circle and the line segment from s's current location to the frontier point; the intersection point is the desired EP. • BLG-expansion. A sensor s tries to obtain a set of boundary line segments covered by its sensing range (see Figure 7(a)). If any such line segments exist, it randomly picks a segment, say Γ, and chooses a random point on Γ and moves the point along Γ following the left-hand rule 1 , until the point reaches the sensing circle; this new location is the frontier point for Γ. After determining the frontier point, s calculates the EP following the same procedure as in the FLG-expansion. • IFLG-expansion. This type of expansion is used for filling coverage holes left by neighboring sensors in the same floor (see Figure 7(d)). A sensor and its child can jointly determine if there is a coverage hole between themselves and an inter-floor line, which is defined as that at the middle of two neighboring floor lines. If a hole is found, then the parent checks if the intersection point of their expansion circle at the side of the hole is already covered by other sensors. If it is not, then the intersection point is taken as an EP.

With an EP determined, s can start inviting movable sensors over. After a movable sensor has agreed to such a move, the above process is repeated. Figure 7 illustrates the three types of expansion. In Figure 7(a), the sensor centered at O detects three line/curve segments (the thick lines) in its sensing range: one from the floor line, and two from the two obstacles. Using the left-hand rule, it can obtain three frontier points, A, B, and C. Suppose s has just discovered that A is uncovered, it then takes A as an EP and invites a movable sensor to relocate to it, resulting in the layout shown in Figure 7(b). Afterwards, s can continue to find movable sensors to relocate to B and C. At the same time, the newly arriving sensor centered at A can determine its own EP A and invite sensors to move to that EP; see Figure 7(c). An example of IFLG-expansion is provided in Figure 7(d).

Algorithm 2: Coverage expansion.

----Pseudo-code of fixed node thread 1 (discovering EPs) FLG-expansion provides more improvement in coverage per operation, so it is assigned the highest priority in the protocol; BLGexpansion is ranked second, and IFLG-expansion has the lowest priority.

Inviting movable sensors

The sensors check the sensing coverage and obstacles in their surrounding areas once per period, and determine whether there is any chance for expansion. If a sensor finds no expansion points on its expansion circle, then it stops the checking process. Otherwise, it sends an Invitation message containing an EP to the network. This message has a TTL value and walks randomly in the network. When a movable sensor has collected a certain number of invitations, it picks the one with the highest priority (and smallest Euclidean distance when ties occur). It then sends an AcceptInvitation message to the inviter, which acknowledges the message if it has not found any other movable sensor for that EP, or rejects it otherwise. In the former case, the movable sensor can start to relocate; at the same time the inviting sensor constructs a virtual place-holding fixed node in the tree, and sends a message to the root on behalf of the invited sensor to update the location information maintained by its ancestors. If the AcceptInvitation message is rejected or no response has been received, the movable sensor simply continues to collect Invitation messages and responds to an inviter when appropriate.

Once a movable sensor moves to an EP, it becomes fixed and can start searching for expansion opportunities around itself. It is possible that two movable sensors relocate to the same (or very near) positions, thus wasting coverage. However, the chance of such an occurrence will be small as long as the communication latency is much smaller than the length of a period. The wasted coverage is thus insignificant.

Coverage of FLOOR

We conduct simulations for FLOOR using exactly the same settings as in Figure 3, and show the sensor layout in Figure 8. When the field is obstacle-free (Figure 8(a)), the coverage achieved by FLOOR is 78.8%, which is slightly higher than that of CPVF (74.5%). When r c decreases to 30m (Figure 8(b)), FLOOR produces a much higher coverage than CPVF (46.2% vs. 26.4%). This is because FLOOR can separate sensors using floor lines, thus reducing coverage overlap in the vertical direction to minimum. This example clearly demonstrates the advantage of FLOOR over CPVF in adapting to varying r c . Another advantage of FLOOR can be seen from Figure 8(c), where two obstacles are present in the field. In contrast to CPVF, FLOOR has no difficulty expanding the coverage beyond those obstacles, producing a coverage of 72.5%, nearly twice that of CPVF.

In FLOOR, once a movable sensor relocates to a certain location it stabilizes, and so the convergence time of the protocol is bounded.

COMPREHENSIVE PERFORMANCE EVALUA-TION

In this section we conduct a more comprehensive performance evaluation of the proposed schemes. Besides coverage, we also consider the moving distance of sensors, which dominates energy consumption in the deployment process. A further energy consumption factor that we investigate is the message overhead. The same settings of field, sensor movement patterns, and the ranges of r c and r s as in Section 4.3 are used. We consider a clustered initial sensor distribution, in which sensors are randomly distributed in a sub-area {(x, y) : 0 ≤ x ≤ 500, 0 ≤ y ≤ 500} of the whole field {(x, y) : 0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000}. This distribution is intended to test how sensors move apart from a clustered distribution to maximize network coverage. We have also tested an initial distribution in which sensors are placed in the field uniformly at random; the results are consistent with the clustered case, so we mainly report on the former.

Coverage in obstacle-free fields

Assuming an obstacle-free field, we compare the coverage performance of five schemes: 1) CPVF, described in Section 4; 2) FLOOR, described in Section 5;

3) The optimal scheme (OPT) described in [START_REF] Bai | Deploying Wireless Sensors to Achieve Both Coverage and Connectivity[END_REF]. This centralized scheme achieves provably optimal coverage with guaranteed connectivity (applicable only to obstacle-free regular fields); 4) VOR, an Voronoi Diagram (VD) based scheme, introduced in [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF]. In VOR, nodes move in rounds; in each round, every node moves toward its farthest Voronoi polygon vertex, under the constraint of a maximum moving distance of r c /2; 5) Minimax, also an VD-based scheme, introduced in [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF]. Like VOR, nodes move in rounds; in each round, every node moves to the point that has the smallest distance to its farthest Voronoi polygon vertex. These schemes include state-of-the-art techniques for our deployment task: CPVF represents the VF-based approach, while VOR and Minimax represent the VDbased approach. (In [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF] the authors also propose a third scheme but since it performs no better than VOR and Minimax we ignore this case.) Note that VOR and Minimax are connectivity-ignorant.

Comparison between CPVF, FLOOR and OPT

Figure 9 shows the coverage of CPVF and FLOOR for varying numbers of sensors. The results confirm previous findings from Figures 3 and8: FLOOR outperforms CPVF in all cases, especially for a moderate or small r c /r s . For instance, for 240 sensors with r c = 20m and r s = 60m, the coverage of CPVF (20%) is only 46% of FLOOR's coverage (46%). As r c /r s increases, the gap becomes smaller. For example, with r c = 60m and r s = 20m, the coverage of CPVF and FLOOR are 24% and 28%, respectively (not shown in the figure). Generally, in an obstacle-free field, when r c r s , the advantage of FLOOR is most pronounced; when r c r s , the two schemes come very close in coverage.

Figure 9 also plots the results of OPT. As can be seen, FLOOR is only surpassed by OPT by a small to moderate margin, with the largest difference occurring at r c = r s = 60 with 120 sensors, where the coverage of FLOOR is 26% lower than the optimal. As r c and the number of sensors grows, FLOOR's coverage becomes quite close to the optimal. For instance, for r c = r s = 60 with more than 200 sensors, FLOOR's coverage is only 4% lower than the optimal. Further increase of sensors (≥ 300) brings diminishing gains in coverage as the field gradually becomes saturated (expect under the case of CPVF with r c = 40m and r s = 60m).

The difference between FLOOR and OPT is mainly due to some sensors that are located at the boundary of the field. Here the coverage holes are smaller than those found at the interior of the field, and therefore the coverage gains are smaller than average. In a system where a central coordinator is absent, achieving a perfect (and strict) pattern will require more sensor relocations, which leads to increased energy consumption. It is FLOOR's choice to trade a small amount of coverage for a saving in energy consumption. This point will be further demonstrated in the next section.

Comparison between FLOOR, VOR and Minimax

In a VD-based scheme, the connectivity and coverage prove to highly depend on r c /r s . Figure 10 • Neither VOR nor Minimax achieves connectivity for r c /r s ≤ 2, which suggests they rely on a large r c /r s to generate a fully functional network; nevertheless, even if r c /r s is large, there is no guarantee of connectivity from the principle of VOR and Minimax; • VOR and Minimax start generating correct VD cells only when r c /r s ≥ 3 and r c /r s ≥ 4, respectively. The improving coverage with increasing r c /r s implies the significant impact of correct VD generation on coverage performance. In particular, the Minimax scheme is extremely sensitive to r c /r s : when the ratio is smaller than 1, the resulting network is very unreasonably deployed, producing a coverage of only 4.5%; • If r c /r s is large enough (≥ 2.5 in our case), both VOR and Minimax perform well in terms of coverage. In some cases, they are very close to the optimal and slightly outperform FLOOR. The reason is that they do not consider connectivity and thus have more freedom for coverage maximization.

Moving distance in obstacle-free fields

We compare the moving distance of sensors for six schemes, including CPVF, FLOOR, VOR, Minimax, and two other schemes. When the sensors are initially densely deployed within a sub-area of the field, as is the case for our first distribution setting, VOR and Minimax need an "explosion" procedure to disperse the sensors into an approximately random distribution, and then VD-based coverage improvement can begin. We let this stage take a minimum total moving distance, which can be calculated as follows. We assume that the resulting random distribution is already known, then choosing a destination point in this distribution for each sensor can be modelled as a classic minimum weighted bipartite matching problem (or an assignment problem), where the objective is to find the assignment that requires the minimum matching cost. This problem can be solved in polynomial time using the well-known Hungarian algorithm [START_REF]Hungarian Algorithm[END_REF]. Calculating a minimum value for VOR and Minimax gives us a baseline as to how they perform in terms of moving distance in the best case. After the initial explosion process, we let VOR and Minimax run for 10 rounds, after which the coverage stabilizes.

Using the Hungarian algorithm, we also implement two optimal schemes with respect to two final network layouts. The first network layout is the optimal pattern proposed in [START_REF] Bai | Deploying Wireless Sensors to Achieve Both Coverage and Connectivity[END_REF], and the second is the one produced by FLOOR itself. The first optimal scheme shows the minimum moving distance for achieving an optimal coverage, while the second scheme shows how much FLOOR deviates from the lower bound with its own coverage.

Figure 11 shows the average moving distance of these six scheme. Comparing FLOOR with VOR and Minimax, one can see that FLOOR performs significantly better. The main source for VOR and Minimax's long moving distance is the explosion process, despite the optimized moving arrangement. Without this process, VOR and Minimax will suffer from the same problems as VF-based scheme: a long convergence time and motion oscillation. This reflects VOR and Minimax's reliance on a good initial sensor distribution.

Comparing FLOOR with the optimal schemes, one can also see that the moving distance of FLOOR is lower than that required by the optimal pattern. This is so because when planning node movement, FLOOR takes a more comprehensive consideration of coverage and moving distance -if a sensor finds that its move brings only a small gain in coverage, then the sensor remains fixed. Although sacrificing a certain amount of coverage, this strategy can effectively reduce the moving distance. In contrast, the optimal pattern only considers total coverage, thus potentially involves more node movement. These results again demonstrate FLOOR's choice in striking a balance between maximum coverage and minimum energy consumption.

It can also be observed that FLOOR has a moving distance 15.6-38% higher than the optimal for achieving its own coverage. This is no surprise since in FLOOR, the matching between coverage holes and movable sensors is performed in a distributed and greedy manner.

Comparing FLOOR with CPVF, one can see that CPVF generally requires more than two times the average moving distance of FLOOR. The reason behind this is that frequent oscillation occurs in CPVF, that is, many sensors move back and forth under the drive of virtual forces, requiring a large number of unnecessary moves on the way to their destinations.

The disadvantage of CPVF in terms of moving distance is also found in the case where sensors are initially distributed uniformly at random. Although it is the case that when connectivity is established, FLOOR requires all the sensors to try to pass two intermediate destinations, which causes more movement compared with CPVF's straight-line movement, the oscillation of CPVF in the coverage maximization phase cancels out this advantage and leads to increased moving distance.

Oscillation avoidance for CPVF

We consider two oscillation avoidance techniques for reducing unnecessary movement in CPVF, in an attempt to remedy its drawbacks while retaining its strengths. In the first technique, called one-step oscillation avoidance, a sensor cancels its movement for the next step if it finds that the next step size is smaller than V T /δ, where V T is the maximum step size and δ is a parameter called the oscillation avoidance factor. This is intended to eliminate small perturbations and force the system to enter an equilibrium state earlier; see [START_REF] Howard | Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem[END_REF] for a similar strategy. In the second technique, called two-step oscillation avoidance, a sensor compares its future location at the end of the next step with its past location at the end of the previous step; if the distance between them is smaller than V T /δ, then it cancels its movement plan for the next step. A similar approach has been used in [START_REF] Wang | Movement-Assisted Sensor Deployment[END_REF]. Figure 12 shows the impact of varying the δ value on the moving distance (the left y-axis) and coverage (the right y-axis) of both schemes. It can be observed that δ does have the effect of reducing the moving distance; however, this comes at the cost of reduced coverage. When δ gets smaller, it is more likely that a step will be regarded as an unnecessary or repeated move, thus more steps are cancelled. On the other hand, the conservative moving of sensors prevents them from exploring the uncovered areas effectively, resulting in poor coverage. We have also tried oscillation avoidance based on a longer movement history, and have found similar trends. The difficulty of avoiding oscillation without reducing coverage is that some seemingly unnecessary steps are actually effective moves that can potentially push the frontier of coverage forward, yet it is very hard to detect which of these moves are effective, so that we can decide when to start the oscillation avoidance and when to stop it. The failure of reducing oscillations by local decisions again reflects the limitation of the VF-based approach.

Fields with random obstacles

We next consider sensor deployment in a field with obstacles. In this setting, the previously discussed optimal and VD-based schemes no longer apply, so we only consider CPVF and FLOOR. We randomly select between 1 and 4 rectangular obstacles of random size; these obstacles may overlap with one another, however we maintain the condition that the obstacles do not partition the field.

A total of 300 runs of the simulation are executed, and the coverage and moving distance of the two schemes are recorded. Figure 13 depicts the cumulative distribution function of coverage and average distance. In this general obstacle setting, it can be seen that FLOOR outperforms CPVF significantly in terms of both coverage and moving distance. For instance, while the mean coverage of FLOOR is more than 20% higher than that of CPVF, the mean moving distance is less than half that of CPVF.

Message overhead

We examine the message overheads of FLOOR by varying the TTL values used in the sensor invitation process, and recording the number of protocol messages that are transmitted during the simulation. Table 1 shows the total (and average) number (×1000) of protocol messages for varying numbers of sensor nodes N , and T T L as a fraction of N , under the non-obstacle environment, as well as the two-obstacle environment as shown in Figure 3(c).

We can see that the per-node message overhead during the 750 seconds is quite moderate. For instance, for N = 200 and T T L = 0.2 × N = 40, the overhead is 3.1 × 1000 = 3100 messages per node, which translates to approximately 4 messages per node per second. These messages are all short query messages. This is unlikely to be a high bandwidth requirement for current sensor hardware. When the network grows, more message transmissions will be incurred. In this case, the periods could be prolonged to guarantee that the bandwidth requirement does not exceed the limit of sensor nodes.

It should be noted that the energy consumption for message transmissions is usually very small compared with the energy consumption required for mechanical movement. Besides, the deployment process is often very short in comparison with the expected network lifetime (e.g., hours vs. weeks). We thus believe that the message overhead of FLOOR is acceptable for many of today's applications.

CONCLUSION AND FUTURE WORK

We have presented two sensor deployment schemes for mobile sensor networks in general 2-D fields. The major difference of our schemes from previous work is their adaptability to arbitrary network densities or communication ranges, and to obstacles. Our first scheme is an enhanced form of the traditional virtual forcebased method. We show that it performs well only in very restricted scenarios. We then consider a floor-based scheme which shows good performance in all cases. As part of our future research we plan to investigate how to extend these schemes from deployment through to the whole life cycle of a mobile sensor network -including tasks such as failure recovery and balancing movement overhead. A higher degree of coverage/connectivity in dense networks will also be considered.

Fig. 1 .

 1 Fig. 1. Impact of communication range on the construction of Voronoi diagrams.

Fig. 2 .

 2 Fig.2. An example of the BUG2 algorithm. The dashed line shows the path of a sensor moving to the point R. On its way to R, the sensor encounters two obstacles and moves around them using the right-hand rule.

Fig. 3 .

 3 Fig. 3. Sensor layouts under CPVF for varying r c and r s . The green circles represent sensors' sensing ranges. The 1000 × 1000m 2 field is obstacle-free in (a) and (b), and has two obstacles in (c), shown as grey areas. There are 240 sensors that can move at a speed of no greater than 2m/s, with a period length of one second.

Fig. 4 .

 4 Fig. 4. Examples of sensor layout under CPVF and FLOOR. The large circles represent sensing ranges, and the small circles represent communication ranges; r c /r s = 0.5.

Fig. 5 .

 5 Fig. 5. Coverage expansion in a field. The grey areas represent obstacles. r c = r s .

Algorithm 1 : 2 Execute 5 Execute 7 target ← (0, 0); 8 Execute

 12578 FLOOR's motion planning algorithm. input : Current location (x, y) and a connected field with unknow topology symbols: FloorLine(y): the y coordinate of the nearest floor line to the point (x, y) start ← (x, y); 1 target ← (x,FloorLine(y)); BUG2(start, target) until becoming connected, or 3 reaching target, or hitting an obstacle. If connected then terminate the algorithm; start ← (x,FloorLine(y)); 4 target ← (0,FloorLine(y)); BUG2(start, target) until becoming connected, or 6 reaching target, or hitting an obstacle. If connected then terminate the algorithm; start ← (0,FloorLine(y)); BUG2(start, target) until becoming connected, or 9 reaching target.

Fig. 6 .

 6 Fig. 6. Sensors' moving paths toward (0, 0) under FLOOR.

Fig. 7 .

 7 Fig. 7. Illustration of coverage expansion. (a, b, c) BLGand FLG-expansion; (d) IFLG-expansion. The grey irregular areas represent obstacles. r c = r s .

1 while 3 5 - 6 while true do 7 8 p 13 20 Wait until having collected a certain number of 21 Invitation

 135678132021 there exists at least one EP do 2 Let p be one of the EPs; Send a random-walk Invitation message carrying 4 the location and type of p, along with a TTL; end ---Pseudo-code of fixed node thread 2 (handling messages) Wait for a message m to come through; ← the EP that m corresponds to; 9 msrc ← the source node of m 10 if p is covered by a fixed or virtually fixed node then 11 Send a reject message to msrc; 12 else Send an Acknowledge message to msrc; 14 Construct a virtual fixed node for msrc; 15 Send a message to the root on behalf of the virtual 16 node to update the ancestors' location information; messages, at the same time forwarding received random-walk messages; Pick the highest-priority message m (and smallest 22 Euclidean distance when ties occur), with source m src ; Send an AcceptInvitation message back to m src ; 23 Wait for an Acknowledge message with a timeout; 24 if an Acknowledge message is accepted then 25 Move to the EP contained in m following BUG2; 26 Mark itself to be fixed;

Fig. 8 .

 8 Fig. 8. Sensor layout using FLOOR for varying r c and sensing ranges r s . The field is obstacle-free in (a) and (b), and has two obstacles in (c), shown in grey.

  compares the coverage of the three schemes for r s = 60 and r c /r s ∈ [0.8, 4]. Above the bars, labels "Disconn." and "Incorrect VD" indicate network disconnection and the failure to generate all correct VD cells, respectively. One can make several observations from this figure:

Fig. 9 .

 9 Fig. 9. Coverage of CPVF, FLOOR, and OPT.

Fig. 10 .

 10 Fig. 10. Coverage of CPVF, VOR, and Minimax, r s = 60.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Average moving distance.

  (a) CDFs of coverage (b) CDFs of moving distance

Fig. 13 .

 13 Fig. 13. Comparison of CPVF and FLOOR in coverage and moving distance under random obstacles.

  non-obstacle environment N = 120 225 (1.9) 306 (2.6) 388 (3.2) 470 (3.9) N = 160 325 (2.0) 472 (3.0) 620 (3.9) 769 (4.8) N = 200 409 (2.0) 623 (3.1) 837 (4.2) 1052 (5.3) N = 240 457 (1.9) 714 (2.9) 970 (4.0) 1228 (5.1) two-obstacle environment N = 120 198 (1.7) 286 (2.4) 372 (3.1) 460 (3.8) N = 160 296 (1.8) 453 (2.8) 609 (3.8) 767 (4.8) N = 200 387 (1.9) 617 (3.1) 846 (4.2) 1077 (5.4) N = 240 428 (1.8) 700 (2.9) 973 (4.1) 1246 (5.2)

Fig. 14 .

 14 Fig. 14. Moving paths of two sensors s and s . In (a), s's path AB and s 's path A B do not intersect; in (b), their paths intersect at some point.

TABLE 1

 1 Total(/average) number (×1000) of protocol messages required by FLOOR during a 750-second period.

The left-hand rule, as opposed to the right-hand rule used by the sensors to establish connectivity, can help sensors disperse into unexplored areas more quickly.

APPENDIX A PROOF OF CPVF GUARANTEEING CONNECTIV-

ITY

We formally prove that CPVF guarantees connectivity throughout the process of VF-driven sensor movement. We assume that all sensors follow the connectivity preserving conditions, and that the message transmission latency is negligible compared with the length of a period.

Following the argument made in Section 4.2, we need to prove that for a sensor s planning for its next move and its neighbor s , their distance will be no greater than r c at any time during [t, t ], given that their distances at time t and t are both no greater than r c . The paths of the two sensors are illustrated in Figure 14, where the line segments AB and A B represent s's planned path and s 's moving path during [t, t ], respectively, and AA ≤ r c and BB ≤ r c . Geometrically, we need to prove that for any point C on AB, and point C on A B , we satisfy AC/AB = A C /A B , CC ≤ r c . Now consider the case in Figure 14 Since A B BD is a parallelogram, we have

which is impossible. Therefore A E must be no greater than r c , as is the case for CC , as desired.

The proof for the case in which AB intersects A B , as shown in Figure 14(b), is similar to the above argument and is thus omitted.

PLACE PHOTO HERE

Guang Tan received the Bachelor's degree from the Chongqing University of Posts and Telecommunications, China, in 1999, the Master's degree from the Huazhong University of Science and Technology, China, in 2002 and the Ph.D. degree in computer science from the University of Warwick, U.K., in 2007. He is currently a postdoc researcher in the ASAP Group, French National Institute for Research in Computer Science and Control (INRIA), Rennes, France. From 2002 to 2004, he worked in industry as a software engineer. His area of interest is distributed systems and networks. He is a member of the IEEE.

PLACE PHOTO HERE

Stephen A. Jarvis is an associate professor and the head of research in the Department of Computer Science, University of Warwick, U.K. While previously at the Oxford University Computing Laboratory, he worked on the development of performance tools with Oxford Parallel, Sychron Ltd., and Microsoft Research, Cambridge. He has close research ties with the industry, including current projects with IBM, BT, Hewlett-Packard Research Laboratories, and AWE. He has authored more than 120 refereed publications (including three books) in the area of software and performance evaluation. He is also co-organizer for one of the UK's high-end scientific computing training centers, the manager of the Midlands e-Science Technical Forum on Grid Technologies and a member of the EPSRC and BBSRC Peer Review Colleges. He is member of the IEEE.

PLACE PHOTO HERE

Anne-Marie Kermarrec obtained her Ph.D. from the University of Rennes in October 1996. She spent a year (Oct.96-Oct97) in the Computer Systems group of Vrije Universiteit, Amsterdam. In 1997, she became an assistant professor at the University of Rennes. In 2000, she joined Microsoft Research in Cambridge and worked in the area of peer-to-peer computing. Since February 2004, she has been a senior researcher at INRIA, Rennes, France. Her research interests include large-scale distributed systems, peer to peer overlay networks and applications.


Quentin Lamy-Besnier

Ilias Theodorou

Maud Billaud

Hao Zhang

Harry Sokol

Marianne De Paepe

Luisa De Sordi

Marie-Agnès Petit

The blood virome in Crohn's disease

à 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.

The blood virome in Crohn's disease

Quentin LAMY-BESNIER 1,2 Viral communities (viromes) are integral components of various body microbiomes. The intestinal virome has recently been associated with multiple diseases, including Crohn's disease (CD), suggesting implications for health. However, the virome of other environments, such as the blood, despite its potential as a disease biomarker and implications for health, remains poorly studied. Indeed, most studies of the blood virome have focused on eukaryotic viruses, and broad metagenomic investigations are lacking.

With the aim of improving our limited understanding of the link between CD and the microbiota, we conducted virome sequencing on 29 blood samples obtained from healthy individuals and CD patients. We rigorously addressed the specific limitations of this supposedly sterile environment (such as the low quantity of viruses, leading to high risks of studying contaminants) to provide the first comprehensive characterisation of the human blood virome.

We show that the blood virome contains diverse phages, which mostly infect Proteobacteria.

Using fecal samples obtained conjointly from the same individuals, we also demonstrate that the contigs present in the blood virome are rarely found in the intestinal virome. We further explore other origins for the blood phages, including the oral environment. We also reveal that the blood virome is significantly different in CD patients compared to healthy individuals, contrary to the fecal virome which does not differ significantly between the two groups.

Although very few phages were shared between the blood and intestinal environments, we found that CD patients had significantly more of them, suggesting that their altered intestinal permeability could lead to the passage of viral particles to the blood.

Collectively, these results unveil the presence of phages in human blood, suggest that their origin is only partially intestinal, and underscore differences in the blood virome composition between CD and healthy individuals.

  , Ilias THEODOROU 1 , Maud BILLAUD 1 , Hao ZHANG 1 , Harry Sokol 3 , Marianne DE PAEPE 1 , Luisa DE SORDI 2 , Marie-Agnès PETIT 1 1 Université Paris-Saclay, INRAE, MICALIS Unit, 78352 Jouy en Josas, France 2 Sorbonne Université, INSERM, Centre de Recherche St Antoine, 75012 Paris, France

	3 Sorbonne Université, INSERM, Centre de Recherche Saint-Antoine, CRSA, AP-HP, Saint Antoine
	Hospital, Gastroenterology Department, F-75012 Paris, France.
	Session : Interaction Phage-hôte
	Mots-clés : blood virome; gut virome; Crohn's disease
	Summary (maximum 300 words):


Denis E Corpet

An evaluation of methods to assess the effect of antimicrobial residues on the human gut flora

An evaluation of methods to assess the effect of antimicrobial residues on the human gut flora.

Drug resistant commensal bacteria are not harmful either, but most resistant bacteria bear Rplasmid. The increased size of the plasmid reservoir enables more plasmid transfers to pathogens, and could favor the addition of new genes on a pre-existing R-plasmid [START_REF] Corpet | Ecological factors influencing the transfer of plasmids in vive and in vitro[END_REF].

Subtle changes in flora

Drug residues could induce changes in the flora that are not harmful to present knowledge. Examples are a significant change in the balance between commensal bacteria, whose role is unknown, a small shift in the drug resistance of anaerobes, or a change in some microflora associated characteristics.

These 3 effects may be summarized as a decrease in the barrier effect. This barrier effect is also called bacterial antagonism, antagonistic effect, colonization resistance or competitive exclusion (Tancrède, 1989). The barrier effect means that the strict anaerobes of the dominant indigenous flora prevent the growth of minor aerobes, of R-plasmid carriers, and of bacterial invaders. As a consequence of this barrier effect: * Some resident bacteria of the gut flora remain at relatively low population levels, when compared with dominant anaerobes, or with population numbers of a single strain in the gut of a germfree animal. For example there are about 10 7 cells of E. coli per gram of stool, while the same strain inoculated alone in a germfree mouse would establish at the level of 10 10 cells per gram of gut content (Freter et al., 1983a). * Multi-resistant strains, carrying R-plasmids, are generally not resident in the gut. In volunteers given a sterile diet, most resistant enterobacteria are cleared from the gut within a few days (Corpet, 1988a). * Bacterial invaders, including pathogens, that enter the gut are most often cleared from the gut ( [START_REF] Van Der Vaaij | Bioregulation of the digestive tract microflora[END_REF]. Enteric infections can occur only with high infecting doses, or in special people as newborn or antibiotic-treated persons (Tancrède et al., 1977;[START_REF] Holmberg | Drug-resistant salmonella from animals fed antimicrobials[END_REF][START_REF] Van Der Vaaij | The influence of antibiotics on gut colonization[END_REF]. * This indirect effect of antimicrobial drugs through the weakening of barrier effect may explain why an antibiotic active against gram-positive organisms may cause a change in the gram-negative population [START_REF] Gaines | Effeet of penicillin and virginiamycin on drug resistance in lactose-fermenting enteric flora[END_REF].

From those considerations, is clear that any relevant model for the study of gut flora should include an anaerobic dominant flora, since this is probably important in providing a barrier effect against minor bacteria.

QUANTITATIVE STUDIES OF THE FECAL FLORA

To assess the effect of antimicrobial residues on the gut flora, one could evaluate the following parameters: the dominant anaerobes, the minor aerobes, the antibioresistance characteristics; the resistance of the flora to a challenge by a pathogenic strain, and indirect biochemical markers of bacterial activity.

Anaerobes

Anaerobes are by far the dominant bacteria of the gut ecosystem, as shown on Fig. l. Several hundred species have been reported from the fecal flora, and the cultivable anaerobes constituting 80% of the bacteria in one human stool belong to 30 different species [START_REF] Moore | Human fecal flora : the normal flora of 20 Japanese Hawaüans[END_REF]). An ideal approach to assess the effect of an antimicrobial on the composition of gut flora would require the determination and enumeration of those anaerobes, and the determination of their resistance to antimicrobial drugs. However, technical problems make this approach impracticable. The flora has a complex composition, no good selective media for anaerobes are available, species and genus are not precisely defined, and most anaerobes are extremely oxygen sensitive. Therefore the exact determination of the composition of the flora in one fecal specimen is time consuming and rather imprecise. For instance, a specialized laboratory composed of 8 technicians can handle only one specimen per week, and moreover the coefficient of variation of data is at least 10% and often it is more than 100% [START_REF] Moore | Human fecal flora : the normal flora of 20 Japanese Hawaüans[END_REF][START_REF] Moore | Some current concepts in intestinal bacteriology[END_REF]. From a specific study of the Bacteroides fragilis group in 10 volunteers, [START_REF] Meijer-Severs | Variations in the anaerobic faecal flora of ten healthy human volunteers with special reference to the bacteroides fragilis-group and clostridium difficile[END_REF] concluded that at least a 3 to 4 log difference from the control sample is required to establish a significant change in anaerobes due to antibiotic treatment (i.e. a 1000 to 10 000 fold decrease ) . A simplified technique has been proposed, using the morphology of the 96 dominant anaerobic clones from a fecal sample. One may question the ability of this simplified (and still time consuming ) technique to detect a small change in the flora composition, when for example the Bacteroides spp. are represented by only one or two clones in some volunteers (Tancrède and Barakat, 1989). Finally, results obtained with anaerobes are difficult to interpret, since there are usually not enough accurate data to the test the statistical significance of the observed changes, and we lack the background knowledge to tell if the observed effect is clinically relevant.

A micromorphometric technique has been used to assess the effect of ceftriaxone on flora and appears promising. This is the direct digital image analysis of human fecal flora, followed by a principal components analysis of the data ( [START_REF] Van Der Vaaij | Bioregulation of the digestive tract microflora[END_REF][START_REF] Meijer | Image analysis of gut microflora[END_REF].

Aerobes

Aerobes (or facultative anaerobes) represent a minor fraction of the human fecal flora, usually less than 1 % of the bacteria. Major aerobes are enterobacteria (principally E. coli ), and enterococci. Species are well characterized, and good selective media are available to count aerobes in fecal flora. Since the techniques are fast and inexpensive they can be used to count aerobes repeatedly and accurately yielding enough data for statistical analysis. Although aerobes are only a small part of the fecal flora, their determination could be a sensitive assessment of the gut ecosystem modification. As can be seen in Fig. 2 an antimicrobial affecting slightly the dominant anaerobes, and decreasing the number of Bacteroides sp. from 2 5 to 24% could permit a 2000% increase in the number of E. coli. The change in the Bacteroides sp. population would be undetectable, while the change in the E. coli population would be easy to detect. Some aerobes are potential pathogens, and could harbor plasmids and transposons that are directly infectious for pathogens: changes in aerobe counts following antimicrobial residues are hence directly related to public health problems.

Antibioresistance

The antibioresistance characteristics of anaerobes and of aerobes can be determined in two ways: (1) a direct count of bacteria resistant to a given antimicrobial at a given concentration (breakpoint). ( 2) the determination of minimum inhibitory concentrations ( MIC ) of selected clones. The first method is fast, and permits the accurate determination of minor populations of resistant bacteria. However the choice of the breakpoint concentration for resistance is critical and must be based on previous data or pilot study. The second method, MIC, is time consuming, does not allow the accurate quantification of minor resistant populations (not enough selected clones), nor the detection of resistance when the ratio of total/resistant population is more than 1000. The statistical analysis of MIC shift is usually done by testing only the median MIC in control and treated flora. Only MIC determinations can detect a change far from the breakpoint (e.g., a doubling in the MIC of resistant bacteria, but with no change in their population number ) .

Resistant populations of aerobes are sensitive markers of the modifications of the flora by antimicrobial drugs. Since bacteria resistant to the drug under study are not affected by the drug, their increase in number would reflect indirectly other perturbations of the ecosystem, either in the susceptible populations of the same species ( selection ), or in other bacteria (barrier effect modifications). Finally, an increase in the resistant population size, corresponding to an increased size of the R-plasmid reservoir, is directly related to public health.

Thus, the proportion of resistant enterobacteria appears to be simple and sensitive marker of gut flora changes under drug treatment.

Pathogen challenge

The barrier effect of a flora can be directly assessed by following the elimination of a known bacterial inoculum [START_REF] Ducluzeau | Transit digestif de divers inoculums bacteriens introduits Per Os chez des souris axeniques et holoxeniques (conventionnelles): effet antagoniste de la microflore du tractus gastro-intestinal[END_REF][START_REF] Koopman | Influence of the antibiotics roxithromycin and erythromycin on the gastro-intestinal ecology of mice[END_REF]. For instance, inocula containing 10 8 living cells of E. coli, Shigella flexneri, Salmonella typhimurium, Vibrio cholerae, Pseudomonas aeruginosa, Campylobacter jejuni, Staphylococcus aureus, Clostridium difficile, C. perfringens, or Candida albicans were given to mice, and the number of organisms surviving in the gut 15 days later was compared in control and in drug treated animals [START_REF] Andremont | Effect of erythromycin on microbial antagonisms: a study in gnotobiotic mice associated with a human fecal flora[END_REF]Pecquet et ai. 1991). This kind of study appears to be directly relevant to public health, but the sensitivity to low antimicrobial doses is unknown. The technique of the oral challenge with an exogenous pathogen is easy to perform in experimental animals, particularly in isolators, but would be unethical in human.

Indirect biochemical markers

A number of biochemical markers of the activity of the flora have been proposed, including the measure of beta-glucuronidase, 7-alpha-dehydroxylation of bile acids, conversion of cholesterol to coprostanol, mucin breakdown, short chain fatty acid production and degradation of beta-aspartylglycine [START_REF] Midtvedt | Effects of antimicrobial agents upon the functional part of the intestinal flora[END_REF]. Though they can be measured accurately, biochemical measurements are at best only indirectly related to the barrier effect, observed changes cannot be interpreted in terms of public health.

EXPERIMENTAL METHODS

Methods used to assess the effects of antimicrobial residues on gut flora include: testing in vitro the effect of antimicrobial on pure strains, and administration of antimicrobial agents in vivo to conventional animals, to human volunteers or to gnotobiotic mice.

Tests in vitro * Lorian and de-Frietas (1979) measured the minimum antibiotic concentrations of antimicrobial drugs on pure strains, estimated by altered morphology or decreased growth rate. They showed that most antimicrobial drugs remain active at concentrations 10 times lower than the MIC. * Brady et al. (1988 ) made daily sequential inoculations of flasks containing antimicrobial with a pure bacterial strain. They showed that 0.1 µg tetracycline/ml "selected" a phenotype of increased resistance to most antibiotics, while 1 mg/ml of other antibiotics had no effect. The test does not seem to be relevant since the assessment of resistance is not genotypic, and the selection among a pure strain differs greatly from the selection conditions in an ecosystem. * Brady and Katz (1988 ) measured the mating between E. coli clones in a flask containing an antimicrobial for 18 h and determined the percent transfer rate. They observed almost no effect of low antimicrobial concentrations, except lµg tylosin/ml (shift of transfer rate from 57 to 80%). However, since the transfer rates in vivo are between 10 -14 and 10 -16 , one may question the relevance of their observation to the in vivo situation [START_REF] Corpet | Ecological factors influencing the transfer of plasmids in vive and in vitro[END_REF]. * [START_REF] Lebek | R-Selection of subbacteriostatic tetracycline concentrations[END_REF] studied the effect of antimicrobial drugs in an 8 h continuous flow culture of 3 E. coli strains, one of which carried an R-plasmid. In this chemostat, concentrations around one tenth of the MIC of tetracycline, chloramphenicol, and gentamicin were sufficient to favor the R-plasmid bearing E. coli. The experimental system mimics in some ways the digestive transit, and a kind of simplified barrier effect is obtained from the competition between E. coli strains. This model however lacks the ecological conditions in vivo (antimicrobial metabolism, anaerobiosis, substrate limitation, growth rate), and was later invalidated in vivo, by testing the same strains in the gut of gnotobiotic mice [START_REF] Corpet | Antibiotic residues and R-plasmid selection : are in vitro methods good models?[END_REF].

The major drawback of those in vitro systems is the absence of the gut ecosystem, hence they cannot test the effect of residues on the barrier effect. This problem could theoretieally be overcome, by culturing the fecal flora in che-mostat (Miller and Wolin,1981;Freter et al., 1983b;Corpet, 1989b). but this approach seems no simpler than the model using germfree mice contaminated with human fecal flora.

Tests in vivo in conventional animals

Antimicrobial have been tested at residue concentrations in conventional rodents, and in beagle dogs. A number of studies were also carried out in farm animals given growth promoting antimicrobials, at levels ranging from 5 to 50 ppm of the diet. * Conventional rodents are considered unacceptable because their gut flora is very different from the human one, particularly since the number of E. coli is very low in mice and rats. Attempts were made to provide E. coli cells continuously in the drinking water of rats, or to expose the rats to an environment highly contaminated with E. coli. These rodent models proved to be unsatisfactory for determining the no-effect level of an antimicrobial on the gut flora [START_REF] Rollins | Animal model for determining the no-effect level of an antimicrobial drug on drug resistance in the lactose-fermenting en-teric flora[END_REF]. * The feeding of certain antimicrobial as feed additives to chickens, pigs or calves result in a population of resistant fecal E. coli. However the baseline incidence of resistant bacteria is high in farm animals, even after a 10 years without antibiotic use [START_REF] Langlois | Antibiotic resistance in pigs following a 13 years ban[END_REF]. Therapeutic treatments or inter-group cross contaminations are difficult to avoid in farm animals studies [START_REF] Linton | The effects of feeding tetracycline, nitrovin and quindoxin on the drug-resistance of coli-aerogenes bacteria from calves and pigs[END_REF]. Moreover, natural changes in bacterial populations in the gut of chicken and pig interfere with any possible drug effect [START_REF] Linton | Monitoring for antibiotic resistance in ecterococci consequent upon feeding growth promoters active against gram-positive bacteria[END_REF] * [START_REF] Rollins | Animal model for determining the no-effect level of an antimicrobial drug on drug resistance in the lactose-fermenting en-teric flora[END_REF], and [START_REF] Gaines | Effect of low concentrations of dihydrostreptomycin on drug resistance in enteric bacteria[END_REF][START_REF] Gaines | Effeet of penicillin and virginiamycin on drug resistance in lactose-fermenting enteric flora[END_REF] fed groups of 5-7 beagle dogs for 35-57 d with residue doses of oxytetracycline, dihydrostreptomycin, penicillin or virginiamycin. Total and resistant coliforms were counted in 5 to 10 samples from each animal, and compared to levels in control untreated dogs. In these well designed experiments, the baseline level of resistance was low and contamination was avoided by housing groups in separate buildings. However the inter-animal and day-to-day variability of the flora was high (e.g., standard deviation > mean, [START_REF] Gaines | Effeet of penicillin and virginiamycin on drug resistance in lactose-fermenting enteric flora[END_REF], leading to a low ability to detect an effect. Dogs, like other animals, harbor some bacteria resembling those in humans, but when detailed analyses are done it is evident that most of the bacterial species in the different animals are not the same as those in humans [START_REF] Moore | Some current concepts in intestinal bacteriology[END_REF]. Moreover, the drug metabolism is not the same in dogs and humans. However, this model seems the best acceptable one amongst conventional animal models, to test in vivo the effect of drug residues on a complex flora. * Nord et al. (1985, and1993 elsewhere in this issue of Vet. Microbiol.) gave per os therapeutic doses of a number of antimicrobial drugs to groups of 10 patients for 7 d. According to their data the drugs that are fully absorbed from the gut, and that cannot be detected in the stools, do not change any measured parameter of the fecal flora (including anaerobe counts, and antibioresistant bacteria) . Provided the methods are sensitive enough (detection threshold and statistical power), it is reasonable to postulate that residues of the drugs that produced no detectable effect at therapeutic doses cannot affect the gut flora. * [START_REF] Goldberg | Long-term, low-level antibiotics and the emergence of antibiotic-resistant bacteria in human volonteers[END_REF], and [START_REF] Knothe | Darmfiora und Antibiotika unter besonderer Berucksichtigung der Tetracycline[END_REF] gave daily doses of oxytetracycline to 25-50 volunteers, for 2-6 months. They did observed a sporadic increase of resistant enterobacteria in volunteers given 10 mg per day (resistance increase in 30% of the subjects, P < 0.01; [START_REF] Goldberg | Long-term, low-level antibiotics and the emergence of antibiotic-resistant bacteria in human volonteers[END_REF] . The no-effect level was not determined, and sampling was not frequent enough to detect a small change in a highly fluctuant parameter. * In volunteers given residue doses of ampicillin [START_REF] Corpet | Antibiotic residues and drug resistance in human intestinal flora[END_REF], or oxytetracycline [START_REF] Tancrede | Ecological inpact of low doses of oxytetracycline on human intestinal microflora[END_REF], no firm conclusion could be drawn due to of a lack of design power. Two mg of oxytetracycline per day produced no detectable effect on the gross composition of the 96 dominant anaerobes, and no apparent shift in the MIC of 6x96 clones of anaerobes (no statistics were given). However, the percentage of resistant enterobacteria increased (P<0.01) in 2 volunteers out of 5 given ampicillin (1.5 mg/d for 21 d. 17 data pairs per subject ), and in the 6 others given oxytetracycline (2 mg/d for 7 d. 1 data pair per subject) (P=0.05, median increase 30-fold).

Human volunteer trials

Because of contamination from food, the concentration of resistant E. coli in feces varies enormously in humans [START_REF] Corpet | Antibiotic residues and drug resistance in human intestinal flora[END_REF](Corpet, , 1988a)). Thus a possible effect of antimicrobial drugs could be hidden by the natural fluctuations in resistant populations of fecal bacteria. A relevant trial in human would require a high number of volunteers and a long monitoring period. Power-based assessments of sample size are not easy to do since data are not distributed normally [START_REF] Mann | Apprapriate animal numbers in biomedical research in light of animal weifare considerations[END_REF] . However, a posteriori calculations show that 14 and 33 volunteers respectively would have been necessary to reach a P= 0.01 significance in the trials of Tancrède and[START_REF] Tancrede | Ecological inpact of low doses of oxytetracycline on human intestinal microflora[END_REF][START_REF] Corpet | Antibiotic residues and drug resistance in human intestinal flora[END_REF] (Corpet, 1988c, p.43).

Advantages of human trials are obvious, since no inter-species extrapolation has to be made. Major drawbacks are the difficulty of testing a drug not cleared for use in human, and the requirement to use high number of volunteers and to monitor each one for a long time, to overcome the variability in the fecal resistant populations.

Gnotobiotic mice

Gnotobiotic mice are living isolated models where the effect of antibiotics can be studied in the absence of contamination [START_REF] Corpet | Influence de faibles doses de chlortetracycline sur la resistanee a la chlortetracycline de Escherichia coli dans le tube digestif de souris axeniques hebergeant des flores complexes d'enfant, de veau ou de porcelet[END_REF][START_REF] Corpet | The effect of bambermycin, carbadox, chlortetracycline and olaquindox on antibiotic resistance in intestinal coliforms : a new animal model[END_REF]Corpet, 1988b). * The minimum antibiotic levels for selecting a resistance plasmid was determined in dixenic mice, i.e. germfree mice harboring two isogenic E. coli strains, one of which was carrying an R-plasmid [START_REF] Corpet | Antibiotic residues and R-plasmid selection : are in vitro methods good models?[END_REF]. A strong correlation between antimicrobial dose and selection of the resistant E. coli clone was observed in 70 groups of 3 dixenic mice. Minimum selecting doses were in the range 1-10 mg/1 of drinking water [START_REF] Corpet | Minimum antibiotic levels for selecting a resistance plasmid in a gnotobiotic animal model[END_REF]. However, this model lacks the dominant anaerobic flora that provides the barrier effect in human gut. * The gross composition of the anaerobic flora, the barrier effect and the other major functions of the flora in the human gut are present in the gut of human flora associated mice [START_REF] Raibaud | Implantation of bacteria from the digestive tract of man and various animals into gnotobiotic mice[END_REF][START_REF] Hazenberg | Effects of the human intestinal flora on germfree mice[END_REF][START_REF] Andremont | Effect of erythromycin on microbial antagonisms: a study in gnotobiotic mice associated with a human fecal flora[END_REF][START_REF] Ducluzeau | Effet de l'ingestion de son de ble sur la flore microbienne fecale de donneurs humains et de souris gnotoxeniques receveuses, et sur les effets de barriere exerces par ces flores a l'egard de divers microorganismes potentiellement pathogenes[END_REF][START_REF] Mallet | The use of rats associated with a human faecal flora as a model for studying the effects of diet on the human gut microflora[END_REF]Corpet, 1989b). The human flora associated mice have been used extensively to assess the in vivo effect of therapeutic doses of antimicrobial on the human gut flora com-position, and on the resistance to pathogen challenges [START_REF] Hazenberg | Effect of sulfasalazine on the human intestinal flora[END_REF][START_REF] Andremont | Effect of erythromycin on microbial antagonisms: a study in gnotobiotic mice associated with a human fecal flora[END_REF][START_REF] Pecquet | Selective antimicrobial modulation of the intestinal tract by norfloxacin in human volunteers and in gnotobiotic mice associated with a human fecal flora[END_REF]Pecquet et al. , 1987[START_REF] Pecquet | Effects of roxithromycin on fecal bacteria in human volunteers and resistance to colonization in gnotobiotic mice[END_REF]. * Human flora associated mice can be used to test in vivo the effect of antimicrobial residues on human flora. In a typical trial, 20 germfree mice are first inoculated with a strain of B. fragilis of human origin, to reduce the oxygen and substrate concentrations in the gut. Fecal samples from 4 human donors are diluted a hundred-fold anaerobically, pooled, introduced in the isolator and given by gavage to the 20 mice within 30 min after passing. The barrier effect was not fully transferred to the mice when the germfree mice were not preinoculated with a B. fragilis strain, or when the fecal human flora was frozen (-85 ° C in prereduced 50% glycerol) before its transfer to the mice (Corpet, 1991, unpublished data). A week after the flora transfer, mice are randomized to 4 isolators. Each group is given continuously for 30-40 d a drinking bottle containing either pure water (negative control), or a selecting dose of the antimicrobial under study (positive control), or residue concentrations. Total and resistant enterobacteria and/or enterococci are monitored daily in the pooled mice feces, in order to get 15 to 20 data points per group. Numbers and proportions of resistant bacteria in treated groups are compared with control groups by a matched-pair non-parametric rank test. Data show that the flora is the same in recipient mice and human donor, and in different individual mice as well as different untreated groups of mice. In human flora associated mice, 0.5 mg/1 of chlortetracycline or ampicillin was enough to increase 30-fold the resistant population of fecal E. coli (P<0.005) [START_REF] Corpet | Antibiotic residues and drug resistance in human intestinal flora[END_REF].

This model is easy to handle, yields clear cut data for statistical analysis, and meets the following prerequisites: (1) a low base-line of resistant bacteria, (2) no difference between the different groups before treatment, (3) no contamination during the trial, and hence a low day-to-day variability in resistance levels (4) a flora similar to the human flora, including a barrier effect and interactions in vivo. This model seems sensitive to the effect of low antimicrobial concentrations, possibly more than its human counterpart [START_REF] Corpet | Antibiotic residues and drug resistance in human intestinal flora[END_REF].

Potential drawbacks are the following: (1) the model flora is similar to human flora, but it is impossible to prove they are identical. (2) the results depend on the initial donor flora. The use of a pool from several donors helps to normalize the flora, but unless a standardized human flora is defined, the repetition of an experiment will never be certain (Corpet, 1988b). (3) the model does not include the variability of human flora (due to age, illness, drug treatment, and contaminations by new plasmids ). However, the same drawback exists in human trials. (4) the drug metabolism could be different in mice and human, and (5) the fecal drug concentrations in the mice must be assayed and related to concentration in human intestine.

EFFECTS OF DIETARY CONTAMINATION ON HUMAN FLORA

A sterile diet was given to 7 healthy volunteers for 2.5 weeks, after a control period of 3 weeks. During both periods, total and antibiotic resistant lactose-fermenting enteric organisms were counted daily in their stools. A drastic drop in the fecal concentration of ampicillin, tetracycline and streptomycin resistant bacteria was observed during the sterile diet period (see Table 1) . It is concluded that, in the normal human population, most resistant enterobacteria in feces come from contaminated food (Corpet, 1988a). The dayto-day increase in the number of resistant enterobacteria could be 1 000 000, due to the ingestion of a contaminated food (see Fig. 3).

CONCLUSION

The mean increase in resistance in volunteers given 2mg of oxytetracycline was 30-fold (Tancrède and [START_REF] Tancrede | Ecological inpact of low doses of oxytetracycline on human intestinal microflora[END_REF]. In mice with human flora given 0.5 mg chlortetracycline or ampicillin the mean increase in resistant population numbers was also 30-fold. Tentatively extrapolated to human, those concentrations are in the high range of residue levels possibly found in human food [START_REF] Corpet | Antibiotic residues and drug resistance in human intestinal flora[END_REF]. Thus antibiotic residues due to veterinary treatments might have a statistically significant effect on gut flora. However, the relative contribution of selecting residues seems low when compared with bacterial contamination.

In our opinion and according to current knowledge, antimicrobial residues are not likely to have a meaningful effect on general public health.

Fig. 1 .

 1 Fig. 1. Composition of the human fecal flora. Percentage of each genus are given within parenthesis.

Fig. 2 .

 2 Fig. 2. Speculative effect of an antimicrobial on the composition of the human fecal flora. Per-cent changes for one genus are given in boxes.

Fig. 3 .a

 3 Fig. 3. Log No. of lactose-fermenting enteric organisms in the in stools of a volunteers given a sterile diet from days 21 to 40