Saoucene Mahfoudh
email: saoucene.mahfoudh@inria.fr

Ines Khoufi
email: ines.khoufi@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Anis Laouiti
email: anis.laouiti@it-sudparis.eu

GDVFA: A Distributed Algorithm Based on Grid and Virtual Forces for the Redeployment of WSNs

The distributed virtual forces deployment algorithm provides a very good area coverage and guarantees network connectivity for a sufficient number of sensor nodes. It relies on local information between neighboring sensor nodes. However, its main drawback is node oscillations and hence a high amount of sensor node energy wasted. The grid based strategy divides the monitored area into virtual cells. Each cell center determines the position of a sensor node. In this paper we propose GDVFA that combines the advantages of both strategies: on the one hand coverage and connectivity for virtual forces strategy and on the other hand avoidance of node oscillations for grid strategy. Simulation results reported in this paper show that GDVFA considerably reduces the energy consumed by sensor nodes. This comes from: 1) the detection of redundant nodes that are put in sleep mode, and 2) the avoidance of node oscillations by stopping nodes.

I. INTRODUCTION

The large majority of applications in Wireless Sensor Networks (WSNs) aim at monitoring a given area in order to collect information generated by sensor nodes. To achieve this goal, two major issues should be met. The first is area coverage: any event occurring in the monitored area should be detected. The second is network connectivity: each detected event should be reported to a central entity, the sink. Then if the deployment algorithm does not ensure the required area coverage and network connectivity, the monitoring task will fail. Because of the importance of the coverage and connectivity in WSN, we focus on redeployment algorithms that cope with coverage and connectivity problems. Many deployment algorithms are proposed in the literature. These algorithms are based on different strategies [START_REF] Ab | Coverage Strategies for Wireless Sensor Networks[END_REF]: Forces based strategy that uses virtual forces to move sensor nodes [START_REF] Zou | Sensor Deployment and Target Localization Based on Virtual Forces[END_REF], [START_REF] Mougou | Redeployment of Randomly Deployed Wireless Mobile Sensor Nodes[END_REF], [START_REF] Mahfoudh | Relocation of Mobile Wireless Sensors in the Presence of Obstacles[END_REF], Grid based strategy that defines a grid pattern to determine sensor node positions [START_REF] Han | Hexagonal grid-based sensor deployment algorithm[END_REF], [START_REF] Park | A Grid-based Self-deployment Schemes in Mobile Sensor Networks[END_REF], [START_REF] Xu | Back Tracking based Sensor Deployment by a Robot Team[END_REF] and Computational geometry based strategy that relies on Voronoi polygon and Delaunay triangulation to find the appropriate sensor node positions [START_REF] Wang | Movement Assisted Sensor Deployment[END_REF], [START_REF] Babaie | Hole Detection Fore Increasing Coverage in Wireless Sensor Network Using Triangular Structure[END_REF], [START_REF] Tan | Arbitrary obstacles constrained full coverage in wireless sensor networks[END_REF]. Among these strategies, we are interested in the forces based strategy and in the grid based strategy. In the forces based deployment algorithms, sensor nodes move according to virtual forces that can be attractive, repulsive or null. An attractive force is exerted, if the distance separating two sensor nodes is higher than a certain threshold, denoted D th . If the distance is lower than D th , a repulsive force is exerted. Otherwise, the force is null. The resultant of the virtual forces exerted by all neighboring nodes determines the new position of this node. In the new position, the resultant of the virtual forces is computed again and the next position of nodes is determined accordingly. This mechanism is very helpful to spread sensor nodes in the whole area while avoiding coverage holes and keeping the network connectivity. Deployment algorithms based on grid pattern also provide a good result in terms of coverage, connectivity and energy consumption. In grid based strategy, the considered area is divided into similar virtual cells according to a predefined pattern that can be triangular lattice, square or hexagon. Cell size is computed with regard to the value of both sensing range, r, and radio range, R, in order to ensure the area coverage and guarantee the network connectivity. It has been proved that the triangular lattice provides the optimal number of sensor nodes to achieve coverage when R ≥ √ 3r [START_REF] Bai | Deploying Wireless Sensors to Achieve Both Coverage and Connectivity[END_REF]. This strategy can be used to reduce the energy consumption as the node positions are predetermined. To take advantage of these two strategies, we propose a redeployment algorithm called GDVFA, Grid Distributed Virtual Forces Algorithm, combining the virtual forces strategy to move sensor nodes and the grid based strategy to save energy. This paper is organized as follows: Firstly, in Section II, we cite some studies related to virtual forces and grid strategies and present our motivation. Secondly, we propose a new algorithm called GDVFA which is an hybridization of virtual forces and grid based strategies in Section III. Simulation results of GDVFA are given in Section IV, evaluating the coverage rate and the total distance traveled by nodes and comparing GDVFA to DVFA. In Section V, we show how to compute the value of the spreading factor that depends on the initial deployment. Finally, we conclude in Section VI.

II. MOTIVATIONS AND RELATED WORK

The force based strategy is well studied in WSNs. The basic Virtual Forces Algorithm, VFA, is proposed in its centralized version in [START_REF] Zou | Sensor Deployment and Target Localization Based on Virtual Forces[END_REF]. VFA moves sensor nodes from dense to poorly covered area while maintaining connectivity due to the attractive and repulsive forces exerted between sensor nodes. This algorithm provides a uniform deployment since the target distance, D th , between sensor nodes is the same for all neighbor nodes. However, this algorithm suffers from some drawbacks, such as the existence of a bottleneck and a single point of failure, node stacking, non full coverage and instability. That is why, many enhancements of the basic VFA, namely distributed algorithms, are proposed to cope with these problems. To avoid the node stacking problem, the coefficient of the attractive force is reduced in [START_REF] Mougou | Redeployment of Randomly Deployed Wireless Mobile Sensor Nodes[END_REF] and [START_REF] Li | An Extended Virtual Force-Based Approach to Distributed Self-Deployment in Mobile Sensor Networks[END_REF]. Hence, a uniform deployment is obtained. Furthermore, the authors of [START_REF] Mougou | Redeployment of Randomly Deployed Wireless Mobile Sensor Nodes[END_REF] and [START_REF] Li | An Extended Virtual Force-Based Approach to Distributed Self-Deployment in Mobile Sensor Networks[END_REF] propose to reduce the amplitude of oscillations by limiting the maximum distance traveled in each iteration. With these enhancements, a high coverage rate is quickly achieved. Despite these improvements, node oscillations problem remains unsolved in the distributed algorithms. These oscillations are the source of the instability of the deployment. Hence, this instability may cause a high energy consumption. Moreover, the end of the virtual forces algorithm cannot be detected even when the maximum coverage rate is reached: a sensor node is unable to distinguish between a local maximum and a global maximum of the coverage rate. Furthermore, the principle of virtual forces does not include a mechanism to detect redundant nodes and make them sleep to save energy. In this paper, we are interested in the distributed version which is based only on local information and avoids the single point of failure. On the other hand, grid based strategy provides many advantages, such as a uniform deployment according to a predefined pattern, a full coverage and an easy identification of redundant nodes. To cope with the problems related to virtual forces, we propose to combine virtual forces with grid. The idea is to keep the simplicity of virtual forces and to take the advantage of predefined positions assigned to sensor nodes in grid. Indeed, node oscillations that are small moves caused by repulsive or attractive forces exerted between neighbors when the distance between them is not equal to the target distance D th , can be avoided using predefined node positions in grid. A first approach would be to design a grid based VFA algorithm. With this algorithm, any node computes the resultant of the virtual forces and moves to the cell center the closest to its new position, if this cell center is empty. Otherwise, it moves according to the virtual forces. To show the different behaviors of DVFA, a distributed virtual forces based algorithm and the grid based VFA algorithm, we evaluate the coverage and the total distance travelled by nodes as a function of time for a random topology of 200 nodes for a network area of 500 * 500. Figure 1 shows that the grid based algorithm achieves a coverage rate significantly smaller than DVFA. However, Figure 2 depicts a total distance traveled that always increases with DVFA due to node oscillations, whereas it remains constant with the grid based algorithm. We want to combine the very good coverage of DVFA with the small distance traveled obtained with the grid. The new algorithm we propose is called GDVFA: Grid Distributed Virtual Forces Algorithm that uses the grid to cope with node oscillations caused by virtual forces. The main contribution of this paper is the elimination of node oscillations by stopping them once they satisfy certain conditions fixed by GDVFA. Hence, we are able to detect redundant nodes and make them sleep. Consequently, energy consumption is considerably reduced.

III. PRESENTATION OF GDVFA A. Assumptions

In this paper we adopt the following assumptions in order to ensure full area coverage and network connectivity while coping with virtual forces oscillations problem:

• Each sensor has a sensing range r and a radio range R. Furthermore, we assume that R ≥ √ 3r. In such a case, it is sufficient to ensure full area coverage to get connectivity.

• Each sensor knows its own position (via GPS or other localization technology).

• The considered area is assumed to be a 2-dimension area and is divided into cells.

• Each sensor is able to determine the cell center in its surrounding.

• The network field is a rectangle of length L and width W . Each sensor knows the values of L and W .

B. Description of GDVFA

The GDVFA algorithm is an hybridization of the virtual forces and the grid. GDVFA, like DVFA [START_REF] Mougou | Redeployment of Randomly Deployed Wireless Mobile Sensor Nodes[END_REF], is based on virtual forces to move sensor nodes and maintain the target distance D th between neighboring nodes. The new position of a sensor node is computed according to the sum of the forces exerted on it by its 1-hop and 2-hop neighbors. As we shown in a previous work [START_REF] Mougou | Redeployment of Randomly Deployed Wireless Mobile Sensor Nodes[END_REF], the node moving distance is limited to a fixed threshold called Lmax in order to reduce the distance traveled by nodes in each iteration. The originality of GDVFA lies in the use of grid based strategy: we propose to divide the area into similar cells. Our target is to incite nodes to occupy the centers of cells. Hence, redundant nodes are nodes that do not occupy the center of a cell. They can easily be detected and switched to sleep state to save energy. Furthermore, any node whose neighboring cell centers do not change can stop moving.

So the energy consumed is reduced. These two enhancements are detailed in Subsection III-D. GDVFA proceeds in two phases. Each phase consists of iterations. In each iteration, each node proceeds as follows:

• Step 1: each node broadcasts a Hello-message each Hello-period to discover its 1-hop and 2-hop neighbors.

• Step 2: each node computes the virtual forces exerted on it by its 1-hop and 2-hop neighbors.

• Step 3: each node determines its new position by computing the resultant force.

• Step 4: The node moves. (We will see later how.)

Each iteration has a duration of a Hello-period.

Phase 1 executes the simple DVFA [START_REF] Mougou | Redeployment of Randomly Deployed Wireless Mobile Sensor Nodes[END_REF] to spread sensor nodes in the whole area while ensuring a uniform density. During this phase, each node moves in step 4 to the new position computed by the virtual forces. At the end of phase 1, the nodes are deployed in the whole area while offering a good coverage and uniform density. Nevertheless, DVFA suffers from high energy consumption due to node oscillations that may never stop.

The aim of Phase 2 is essentially to cope with this drawback by adopting the grid strategy. In this phase, step 4 is replaced by the following step:

• Step 4': each node determines the cell containing its new position. If the center of this cell is empty and this node has the smallest identifier among all nodes in this same cell, then it moves to the cell center. Otherwise, this sensor node moves to the new position determined by the resultant force. Notice that a node that occupies the center of a cell can leave it only if its neighbors exert on it an attractive or repulsive force.

The benefit of the first phase is to spread rapidly the nodes in the whole area which lasts a predefined amount of time (the spreading factor described in V), before switching to the second phase offering stability and convergence. For example, in the performance evaluation in section IV, this spreading factor is equal to 100s for topology where nodes are randomly scattered all over the network area. Any sensor node is assumed to know the value of the spreading factor, a parameter of GDVFA.

C. Cell definition

In this section, we explain how to define the virtual grid in GDVFA by giving the equations used to determine the cell center relative to a sensor node of coordinates (x, y) in the grid. The size of cells is computed with regard to the sensing range in order to ensure the full area coverage. The authors in [START_REF] Wang | Integred Coverage and Connectivity Configuration in Wireless Sensor Networks[END_REF] proved that when R ≥ √ 3r and the full area coverage is ensured, network connectivity is consequently ensured. Then, in our work, network connectivity is guaranteed since we assume R ≥ √ 3r.

In GDVFA, we choose to use rectangular cells to simplify the computation of the cell to which any node belongs to, knowing the coordinates (x, y) of the sensor node, the values of L and W of the network area considered and the value of the sensing range, r. Sensor nodes should occupy the center of these cells. Figure 3 depicts the grid cells with a rectangular shape. Each non-border cell has a length equal to D th and a width of 3r 2 . Furthermore, each non-border cell has 6 neighboring cells. However, sensor nodes are deployed in triangular lattice. These triangles of edge D th are computed as follows. As the GDVFA algorithm deploys sensor nodes in a triangular lattice, then each three neighboring nodes, vertices of the same triangle, should fully cover this equilateral triangle while minimizing their overlapping. This overlapping can be a single point which corresponds to the barycenter of the triangle. Since the distance between the barycenter of this triangle and each vertex of this triangle is r, the distance between two neighboring nodes, an edge of the triangle, is D th = √ 3r. This also corresponds to the length of the cell. The width of the cell is equal to the height of the equilateral triangle 3r

2 . The cell centers of the same floor constitute a single line. We distinguish between odd and even lines. In any odd line, the first sensor node should be located at a distance D th 2 from the left border line. Whereas, in any even line the first sensor node is located on the left border line. Border cells are a particular case. They are built to ensure full area coverage while minimizing the number of sensor nodes. That is why the first line is at a distance r 2 from the top border line. Let (x, y) be the coordinates of any sensor node s i in the grid. We want to determine to which cell s i belongs to. This cell is defined by a line number, denoted line(x, y), and a column number, denoted col(x, y).

line(x, y)

= y -r 2 3r 2 + 1 + δ l ( 1
)
with δ l = 1 if y -5r 4 - y-r 2 3r 2 3r 2 > 0 0 otherwise
For the computation of the column, we distinguish two cases:

• Case (line(x, y)modulo2) = 0:

Then, the node of coordinates (x, y) occupies the col e (x, y) th cell in an even line computed as follows: Then the node of coordinates (x, y) occupies the col o (x, y) th cell in an odd line computed as follows:

col e (x, y) = x √ 3r + 1 + δ e ( 2
)
with δ e = 1 if x -D th 2 -x D th D th >
col o (x, y) = x -D th 2 D th + 1 + δ o ( 3
)
with δ o = 1 if x -D th - x-

D. Stopping condition and detection of redundant nodes

By definition a node is said to be in stop state in an iteration if and only if it does not move in this iteration due to the stopping condition. However to keep the required property of reactivity to topology changes (e.g. node departure, empty cells detected), the stopping condition is always verified at each iteration.

Stopping condition: the nodes occupying the center of its 6 neighboring cells and its cell have not changed during three consecutive iterations. At each iteration, any node computes the resultant of the virtual forces exerted on the node, and checks the stopping condition. If the node is not stopped and the stopping condition is true, the node stops. Furthermore, a previously stopped node moves in an iteration if and only if: either the resultant of the virtual forces differs from the previous one (e.g. arrival of a new neighbor), or the stopping condition is no more true. A node that has stopped without occupying a cell center is said to be redundant. Redundant nodes are used to replace failed or depleted nodes. For the initial deployment depicted in Figure 4a, GDVFA, provides the final deployment shown in Figure 4b for 250 nodes. Nodes in red are active nodes, whereas blue nodes with small points are redundant nodes which sleep to save energy and prolong network lifetime.

IV. PERFORMANCE EVALUATION

In this section, we present the parameters we adopted to evaluate the performances of GDVFA in various random topologies.

A. Simulation parameters

The parameters used in the simulations are defined in Table I. Notice that the optimal number of sensor needed to provide full coverage of the network area is 178.

B. Comparative evaluation between DVFA and GDVFA

From Figure 5, we observe that GDVFA reaches a 100% coverage rate, while considerably reducing the total distance traveled by nodes as depicted in Figures 6, 7 and8, for different numbers of nodes 200, 250 and 300. The total distance traveled by nodes increases with time and with the number of nodes in DVFA (see Figures 6, 7 and8). Notice that the slope of the total distance curve is much steeper when the number of nodes exceeds the optimal number needed to fully cover the network area. This can be explained by the fact that DVFA tries to enforce equilateral pattern deployment, where the edge of the triangular is D th , computed for the optimal number of sensors. Hence, the node oscillations increase, when the number of sensors increase beyond this optimal number. Notice that nodes continue to move even when the 100% coverage rate is reached. Unlike DVFA, GDVFA provides very good performances with regard to the distance traveled: this distance remains constant a short time after the end of the Phase 1, because GDVFA eliminates node oscillations by stopping nodes. Hence, with GDVFA energy consumption is reduced. Simulation results show that the stopping condition is very efficient. In fact, with GDVFA all nodes stop whatever the number of nodes (see Figure 9). We can distinguish two types of stopped nodes:

• the ones occupying the center of cells. These nodes are needed to ensure full coverage;

• the other ones are redundant nodes (see Figure 10). GDVFA enables the distributed detection of redundant nodes (see Figure 10). Such nodes can be turned off to save energy and increase network lifetime. The detection of redundant nodes can also be used to repair coverage holes or replace energy depleted nodes. Figure 11 depicts the cumulative stopping time that allows nodes to save energy by reducing useless moves and hence prolong network lifetime.

V. IMPACT OF THE SPREADING FACTOR

Up to now, we have assumed that the initial deployment was random and sensor nodes were scattered in the whole network area. Simulation results reported in Section IV, show that f = 100s is sufficient to obtain a final coverage rate of nearly 100% at the end of the simulation. For many applications, this initial deployment is not representative; initially all sensor nodes are grouped together in a single entry point of the area. In this case, f = 100s may be insufficient to obtain the full coverage, even if the number of sensors is sufficient to obtain this full coverage. We can establish a lower bound for this factor in such initial topology as follows. Let W * L be the length and the width of the rectangular area. In DVFA and GDVFA, any sensor node cannot move more than Lmax at each Hello-period. The lower bound on the spreading factor is computed, taking into account the time needed by a sensor to reach the farthest position from the initial one in the topology considered. For instance, in a topology with a single entry point at the corner of the rectangular area, which can be considered as one of the worst cases, we get:

√ L 2 +W 2
Lmax * Hello period With the simulation parameters given in Table I, we get f ≥ 194s. We now study the impact of the spread factor on the performances achieved by GDVFA. Figure 12 shows that a spreading factor of 100s is not sufficient to ensure the spreading of nodes in the whole area. Consequently, the area coverage remains limited to 63%. A spreading factor larger than 200s allows to reach a 100% coverage rate. As illustrated in Figure 13, the total distance traveled by nodes increases with the spreading factor. This is due to the oscillations caused by DVFA, that occur even when the full area coverage is obtained. As a conclusion, the choice of the spreading factor is very important for the performances of GDVFA, expressed in terms of coverage rate and distance traveled. To save energy, we recommend to choose the smallest value ensuring the full coverage, (e.g. 250s in our example). Spreading Factor=100 Spreading Factor=200 Spreading Factor=300 Spreading Factor=400

Fig. 12: Impact of the spreading factor on the coverage rate with GDVFA. VI. CONCLUSION In this paper, we propose a new distributed redeployment algorithm that is an hybridization of the virtual forces and the grid based strategies. GDVFA achieves a very good coverage rate of DVFA that favors the uniform spreading of nodes in the whole network area. GDVFA eliminates the node oscillations problem by stopping nodes thanks to its grid based component. Moreover, GDVFA can detect redundant nodes in a distributed Spreading Factor=100 Spreading Factor=200 Spreading Factor=300 Spreading Factor=400

Fig. 13: Impact of the spreading factor on the total distance traveled by nodes with GDVFA.

way. These redundant nodes can be used to replace battery depleted nodes, otherwise they can switch to sleep state to save energy. We have conducted an extensive performance evaluation with two different initial topologies: a random one where nodes are scattered all over the network area and a topology where all nodes are grouped at a single entry point. These simulations show the merit of the two phases of GDVFA. We have also determined how to choose the spreading factor depending on the initial topology considered, the dimensions of the area to cover and the speed of nodes.

Fig. 1 :

 1 Fig. 1: Coverage rate with DVFA and a grid based algorithm.

Fig. 2 :

 2 Fig. 2: distance traveled by nodes with DVFA and a grid based algorithm

Fig. 3 :

 3 Fig. 3: Grid in GDVFA.

+ r 2 •

 2 0 0 otherwise Hence, the coordinates of the cell center are (x c , y c ) with    x c = (col e (x, y) -1)D th y c = (line(x, y) -1) 3r 2 Case (line(x, y)modulo2) = 0:

  coordinates of the cell center are (x c , y c ) with    x c = (col o (x, y) -1)D th + D th 2 y c = (line(x, y) -1) 3r 2 + r 2

a

  Initial random deployment b Final deployment.

Fig. 4 :

 4 Fig. 4: GDVFA with 250 nodes.

Fig. 5 :Fig. 6 :

 56 Fig. 5: Coverage with GDVFA and DVFA.

Fig. 7 :

 7 Fig. 7: Total distance traveled by nodes with GDVFA and DVFA -250 nodes.

Fig. 8 :Fig. 9 :Fig. 10 :

 8910 Fig. 8: Total distance traveled by nodes with GDVFA and DVFA -300 nodes.

Fig. 11 :

 11 Fig. 11: Cumulative stopping time.

TABLE I :

 I Simulation parameters

	Topology
	Sensor nodes	200, 250, 300 randomly spread in the whole area
	Area size	500m x 500m
	Speed	5m/s
	Simulation
	Result	average of 30 simulation runs
	Simulation time	5000s
	MAC
	Protocol	IEEE 802.11b
	Throughput	2 Mb/s
	Radio range R	50 m
	Sensing range r	25 m
	DVFA & GDVFA
	Ka	0.001
	Kr	0.56
	Hello period	2s
	Lmax	D th /6
	Spreading factor	100s for nodes

ACKNOWLEDGMENT

This work has been partially funded by the Cluster Connexion project.


Ines Khoufi
email: ines.khoufi@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Erwan Livolant
email: erwan.livolant@inria.fr

A Simple Method for the Deployment of Wireless Sensors to Ensure Full Coverage of an Irregular Area with Obstacles *

Keywords: C.2.1 [Computer-Communication Networks]: Network Architecture and Design-Wireless communication Algorithms, Design, Performance Wireless Sensor Network, Deployment algorithm, Full coverage, Area with irregular shape, Opaque obstacle, Hidden zone

In this paper, we focus on the deployment of wireless sensor nodes in an arbitrary realistic area with an irregular shape, and with the presence of obstacles that may be opaque. Moreover, we propose a simple projection-based method that tends to minimize the number of sensor nodes needed to fully cover such an area. This method starts with the optimal uniform deployment based on the triangular tessellation encompassing the whole area. Then, it projects some external sensor nodes on the border to ensure full coverage and connectivity. We show that this method outperforms the contour-based one using various types of irregular areas.

MOTIVATION

We are witnessing the deployment of many wireless sensor networks in various application domains such as pollution detection in the environment, intruder detection at home, preventive maintenance in industrial process, monitoring of a temporary industrial worksite, damage assessment after a disaster, etc. Many of these applications require the full coverage of the area considered. With the full coverage of the area, any event occurring in this area is detected by at least one sensor node. In addition, the connectivity ensures that this event is reported to the sink in charge of analyzing the data gathered from the sensors and acting according to these data.

Depending on the application targeted, and for optimality reasons, we may require a uniform deployment to fully cover such an area with a minimum number of wireless sensors. Although optimal uniform wireless sensor network deployment is a key factor for minimizing the overall cost of a wireless sensor network, it may not be accomplished in many cases. In fact the shape of the area to cover, the possible presence of obstacles within this area as well as their properties (shape, opaque or transparent to sensing range, etc) may prevent the deployment of a uniform wireless sensor network. These constraints must be considered when designing a deployment algorithm in order to reach an acceptable deployment.

Examples of applications where wireless sensor networks have proved their efficiency include monitoring of a temporary industrial worksite, damage assessment after a disaster, precision farming, intruder detection in a warehouse, health monitoring of a building. In all these cases, 2D coverage is sufficient to meet the applications requirements. Furthermore, the area to cover has an irregular shape with many edges and is not necessarily convex and may include several obstacles.

In the literature, many studies assume that this area is rectangular and adopt the classical deployment which is based on the triangular lattice that has been proved optimal [START_REF] Kershner | The number of circles covering a set[END_REF]. In real life, things are more complex. Moreover, few papers take obstacles into account. Those that do as-sume that obstacles are constituted by a juxtaposition of rectangles that seems an unrealistic assumption. In real deployments, the shape of obstacles may be irregular. Like in [START_REF] Shyam | Obstacle constrained total area coverage in wireless sensor networks[END_REF], we distinguish two types of obstacles: the transparent ones like ponds in outdoor environment, or tables in an indoor site that only prevent the location of sensor nodes inside them; whereas the opaque obstacles like walls or trees prevent the sensing by causing the existence of hidden zones behind them: such zones may remain uncovered, as illustrated in Figure 1. Authors in [START_REF] Tan | Lv An Approximate Approach for Area Coverage in Wireless Sensor Networks[END_REF] propose a solution to provide an (1 -) coverage of an area of arbitrary shape with obstacles. This solution selects some landmarks in the area and covers them. However, the boundary and the obstacles are assumed to be transparent. Opaque obstacles are much more complex to handle than transparent ones and require the deployment of additional sensors to eliminate coverage holes. That is why in this paper, we focus on the deployment of wireless sensor nodes in an irregular area with obstacles that may be opaque and propose a projection-based method that tends to minimize the number of sensor nodes needed to fully cover this area. This number is smaller than the one given by the contourbased methods [START_REF] Chang | Obstacle-resistant deplyment algorithms for wireless sensor networks[END_REF] and [START_REF] Wang | Efficient placement and dispatch of sensors in a wireless sensor network deployment[END_REF]. Our method is characterized by its simplicity. In contrast to Delaunay triangulation [START_REF] Tan | Arbitrary obstacles constrained full coverage in wireless sensor networks[END_REF], coverage holes are intrinsically known by our method.

The method presented here computes the deployment that is given as an input to a mobile robot. This robot is in charge of placing the sensor nodes (unable to move) at the right location in the area to fully cover. The goal is to provide a deployment of a wireless sensor network assisted by a mobile robot. An additional step can be done after the deployment to collect measures on site. These measures are used as a feedback to adapt the real deployment on the given area. Notice however that in our solution all sensor nodes are needed to provide full coverage, unlike [START_REF] Fotouhi | Razzazi Redundancy and coverage detection in wireless sensor networks in the presence of obstacles[END_REF] where some redundant sensor nodes can be switched off.

The remaining of this paper is organized as follows. We define the problem in Section 2. In Section 3, we give a brief state of the art, recalling known results about full coverage complexity and optimal deployment. We distinguish two approaches to deal with irregular borders and obstacles: contour-based and Delaunay-Triangulation-based. We establish general bounds on the number of sensor nodes independently from the method used. We then propose our method to fully cover an area with irregular transparent borders but no obstacles in Section 5. In Section 6, we show how to take obstacles into account. In Section 7, we generalize to borders and obstacles that can be opaque. In Sections 5 to 7, we present the main principles with an illustrative example, provide a bound dependent of our method and compare the performances of our contribution with those of a contourbased method. Finally, we conclude in Section 8.

PROBLEM STATEMENT

In this paper, we consider wireless sensors that must be deployed to fully cover a given 2D-area of irregular shape with the presence of several obstacles.

Goal

Our goal is to minimize the number of sensors needed to achieve the full coverage of the area given, denoted A, while meeting the assumptions listed in Subsection 2.2. The full coverage of A means that any event occuring in A is detected by at least one sensor node. The deployment of wireless sensor nodes is computed by a single entity that takes as inputs the vertices of the polygon defining A the area to cover as well as for each obstacle, the vertices of its polygon.

Models

For that purpose, we adopt the following models:

• The wireless sensors are assumed to have the same sensing range denoted r and the same radio range R. The sensing model adopted is the simplest one: the disk of radius r. Similarly, the radio transmission model is also disk-based: any wireless node located in the disk of radius R centered at the sensor considered has a symmetric radio link with it. For the sake of simplicity, we also assume that the condition R ≥ √ 3r is met. This condition guarantees that any deployment of wireless sensor nodes ensuring full coverage also ensures full connectivity.

• A, the area to fully cover, is considered as a polygon which may be not convex. This polygon is defined by its edges. These edges constitute the borders of the area. We distinguish two types of borders:

• Transparent border: a transparent border does not prevent the sensing of sensor nodes. The only constraint added by transparent borders is that no sensor must be outside the area to cover.

• Opaque border: an opaque border prevents the sensing of nodes located behind the border: a sensor node s can cover a point u within its sensing disk if and only if u is in the line of sight of s (see Figure 1). Hence, such a border modifies the is covered relation, which is of prime importance in the problem we want to solve.

• The area considered usually has obstacles. No sensor node must be located within an obstacle. Like for borders, we distinguish two types of obstacles: transparent and opaque. An obstacle is defined by the edges of its polygon that may be of irregular shape and not convex. Let O denote the set of obstacles.

STATE OF THE ART

Coverage is a basic issue in wireless sensor networks. The reader can refer to [START_REF] Wang | Coverage problems in sensor networks: a survey[END_REF] for a survey on the various problems related to coverage. The pioneering work on the full coverage of an infinite 2D area was published by Kershner [START_REF] Kershner | The number of circles covering a set[END_REF]. He proved that the triangular tessellation achieves a full coverage with an asymptotic minimum number of sensors. In this tessellation, each sensor node at the center of an hexagon has six neighors at a distance of r √ 3 that occupy the vertices of this hexagon as depicted in Figure 2 and Figure 4. The rectangular area is covered by several lines of sensor nodes. We notice that the first sensor of an odd line is located at a distance r √ 3/2 from the left border, whereas the first sensor of an even line is located at the left border. Furthermore, the first line starts at a distance r/2 from the top border, and the interline is equal to 3r/2. This result has been applied in many network deployments: radio cellular networks as well as wireless sensor networks. It has been extended in [START_REF] Bai | Deploying wireless sensors to achieve both coverage and connectivity[END_REF] to find the optimal tessellation (e.g. rhombus, square, hexagon, triangle) for different conditions binding the radio range R and the sensing range r. Authors of [START_REF] Shyam | Obstacle constrained total area coverage in wireless sensor networks[END_REF] show how to take obstacles into account. They also show that the problem of full coverage of a 2D-area with opaque obstacles is NP-hard. To cope with this problem, the large majority of approaches encountered in the literature adopt the optimal deployment based on the triangular tessellation as a starting point. Then, sensors nodes located within an obstacle or outside the border of the area to fully cover are eliminated. This elimination usually causes coverage holes. The existing approaches differ in the way they heal the coverage holes. We distinguish the following two approaches: • The contour-based approaches like [START_REF] Chang | Obstacle-resistant deplyment algorithms for wireless sensor networks[END_REF][START_REF] Wang | Efficient placement and dispatch of sensors in a wireless sensor network deployment[END_REF]: they deploy sensor nodes at a constant distance along the border of the area and along the border of each obstacle in order to heal coverage hole occurring on these contours. The distance between two successive sensor nodes deployed successively on a given contour is computed from the sensing range. Such approaches are simple but may require a high number of sensors in case of many irregular borders as shown in [START_REF] Tan | Arbitrary obstacles constrained full coverage in wireless sensor networks[END_REF]. In contrast to our projection-based method, the coverage holes that are not adjacent to the area border or the obstacle border are not detected as shown in Figure 3.

• The Delaunay-triangulation-based approaches like [START_REF] Tan | Arbitrary obstacles constrained full coverage in wireless sensor networks[END_REF]: they use the Delaunay triangulation to detect coverage holes and then place sensor nodes at some vertices of the triangles defined using a vertex coloring technique. However the complexity may be high, due to the presence of two modules: (a) the determination of coverage holes followed by (b) the computation of sensor locations that may be greedy in computation resources. In contrast to this approach, our method determines the sensor location without searching coverage holes. To reduce the number of sensors, our method eliminates redundant sensor nodes.

That is why we propose a simple solution requiring less computational complexity. We present in Sections 5, 6 and 7 three problems of increasing complexity. We solve these problems using our simple and efficient approach. Before, we establish general bounds on the number of sensors required to fully cover the area.

GENERAL BOUNDS ON THE NUMBER OF SENSOR NODES

In this section, we establish upper and lower bounds on the number of sensor nodes required, independently from the method used to fully cover the given area. These bounds are derived from the optimal deployment based on a triangular tessellation. We will see in the next sections whether these bounds can be improved taking into account the method used to provide the full coverage of A.

Lower bound

We first establish a lower bound on the number of sensor nodes required to fully cover the area considered. This bound is deduced from the fraction between the surface to cover and the surface covered by a sensor node. For that purpose, we focus on Figure 4 depicting the optimal deployment based on a triangular tessellation. We notice that in this optimal deployment, we can make the following approximation: any sensor node s that is not adjacent to a border can be considered as the only sensor node covering the hexagon ABCDEF of edge r centered at itself and depicted in red in this figure. We can compute the surface of the triangle ABS. It is equal to r 2 √ 3/4. The surface of the hexagon, denoted SH, is equal to the surface of the six triangles composing it. We have SH = 3 √ 3r 2 /2. With this result, we can give a lower bound on the number of sensor nodes needed to fully cover the area A without obstacles. Let M inN be this bound. Let SO be the cumulative surface of the obstacles. The surface to cover is then equal to SA -SO. We get M inN = S A -S O S H

. Finally, we have:

M inN = 2(SA -SO) 3 √ 3r 2 . ( 1
)
Figure 4: Hexagon covered by the sensor node s.

Upper bound

We can now establish an upper bound M axN on the number of sensor nodes needed to fully cover A in the presence of transparent obstacles. This bound is based on:

• NIn the number of sensor nodes within A but outside the obstacles O. This number can be obtained by counting the number of sensor nodes meeting this condition in the optimal deployment based on a triangular tessellation.

• N Add the number of additional sensor nodes to fully cover A added after the elimination of sensor nodes that are either outside A or within an obstacle. To compute this number, we consider the contour of the area and the obstacles, segment by segment.

To fully cover a segment of length L, we use the principle of the optimal deployment in a rectangular area given in Section 3 and adapted to a segment as shown in Figure 5.

Hence, we need N b sensor nodes, with:

N b = L -r √ 3 2 r √ 3 + 1 + δ b ( 2
)
with δ b = 1 if L -r √ 3 - L-r √ 3 2 r √ 3 r √ 3 > 0 0 otherwise δ b is equal to 1 if the distance
between the projection of the last sensor on the border and the extremity of the border is higher than r √ 3

2 . We now apply this method to all edges of A and the obstacles O. We then get N Add ≤ b∈edge(A∪O) N b . Since M axN = NIn + N Add , we get:

M axN = NIn + b∈edge(A∪O) N b .
(

) 3
We now show that in case of transparent borders and obstacles, this number M axN is sufficient to eliminate all coverage holes resulting from the elimination of sensor nodes outside A or within an obstacle. Let us consider any edge of A such that a sensor node s outside the area (or inside an obstacle) at a distance ε > 0 from this edge has been eliminated. This elimination can create a coverage hole in the stripe of width r parallel to this edge. If now we consider the first line of the optimal deployment that starts at a distance r/2 from the border, we notice that this line fully covers the stripe of width r parallel to this border, as illustrated in Figure 5. Hence, we propose to deploy additional sensor nodes on a line parallel to the border, at a distance r/2 from the border. Notice that if such a sensor is outside A, it is put at the first location inside A according to a projection along the border. We can apply the same principle to the obstacles, considering the sensor nodes within the obstacles that have been eliminated.

OPTIMIZED DEPLOYMENT IN AN IR-REGULAR AREA

In this section, we propose a deployment algorithm to cope with the irregular shape of an area.

Problem definition

In this first coverage problem, we consider any irregular 2-D area and assume that there is no obstacle and the border of the area is transparent.

Principle

Our method proceeds as follows:

1. We start with the optimal deployment in the rectangle circumscribing the given area A: see Figure 7(a).

2. Sensor nodes that are outside A are eliminated, which may cause coverage holes: see Figure 7(b).

3. For each sensor node s located outside the area at a distance strictly less than r from a border, we check whether the border segment initially covered by s is still covered by other sensor nodes within A, even if s is eliminated. Otherwise s is orthogonally projected on the border: see Figure 7(c). Due to this projection technique, illustrated in Figure 6, we can guarantee that the zone initially covered by the eliminated sensor node s, stills covered after the projection of s.

4. Finally, to optimize the number of sensor nodes needed, we check if some of them are providing redundant coverage, which can be eliminated in that case. They can be eliminated if and only if the intersection of A and the zone they covered is fully covered by other sensor nodes that are kept (see Figure 7(d)).

Notice that the projection of a senor node is not always on the border considered as shown in Figure 6(b). In this case, the position of the projected node is shifted in the middle of the border segment covered by this node in order to heal coverage holes.

Upper bound on the number of sensors required

We now establish OurM axN , an upper bound on the number of sensors needed by our method to fully cover an area with irregular shape but with transparent borders. This bound does not take into account the elimination of redundant sensor nodes done in step 4. Let Outr denote the set of sensor nodes outside A at a distance less than r from a border and NOutr denote the cardinality of Outr. We recall that NIn denotes the number of sensor nodes within A. Since the sensor nodes that are added come from the projections of nodes in Outr and these projections are done only on edges whose distance is less than r, we then have our upper bound:

OurM axN = NIn + P ∈Outr e∈edge(A)

1 distance(P,e)<r [START_REF] Chang | Obstacle-resistant deplyment algorithms for wireless sensor networks[END_REF] with 1 distance(P,e)<r = 1 if distance(P, e) < r and 0 otherwise.

Comparative evaluation

In this subsection, we compare the performances of our method (projection-based) with the contour-based method on the boot configuration depicted in Figure 7(d). This boot configuration has a circumscribing rectangle of size 20r x 18r. In Sections 5 and 7 we study more complex configurations. The contour-based method chosen applies the method explained in Subsection 4.2 to each edge of A. Hence, it needs N b sensor nodes to fully cover an edge of length L (see Equation 2).

We make vary the sensing range (i.e. r, r/2, r/4), whereas the dimensions of the area are kept constant. We study the impact on the number of sensor nodes required to fully cover the area. As expected, when the sensing range decreases from r to r/2, the number of sensor nodes increases from 57 to 184. The lower bound M inN suggests that this number should be multiplied by 4. We observe a multiplication by 3.23. Respectively, when the sensing range decreases from r to r/4, the number of sensor nodes increases from 57 to 652. Similarly, the lower bound M inN suggests that this number should be multiplied by 16. We observe a multiplication by 11.46. This can be explained by the irregularity of the border. The contour-based method adds 35 nodes on the border whereas our method adds only 14 nodes. Hence, the contour-based method leads to a total number of sensor nodes of 78 which is higher than this of our method (i.e. 57 nodes).

We observe that the upper bound OurM axN is very close to the number of sensor nodes needed by our method: we obtain an upper bound of 60, 188 and 656 whereas the exact number is 57, 184 and 652. Meanwhile, we notice that the gap between the real number of sensor nodes and the number given by the contour-based method drastically increases when the sensing range decreases. It reaches 21, 39 and 73 sensor nodes when the sensing range is equal to r, r/2 and r/4. This would increase the deployment cost by a factor of 36% for a sensing range r for instance.

OPTIMIZED DEPLOYMENT IN AN IR-REGULAR AREA WITH OBSTACLES

Because of the presence of obstacles, sensor nodes of the optimal deployment that are located within an obstacle must be eliminated. They can cause coverage holes that must be healed.

Problem definition

In this second coverage problem, we consider any irregular 2-D area that includes obstacles and assume that both the obstacles and the border of the area are transparent.

Principle

We proceed as previously except that:

1. We start with the optimal deployment in the rectangle circumscribing the given area A: see Figure 13(a).

2. Sensor nodes that are outside A or inside the obstacles O are eliminated, which may cause coverage holes: see Figure 13(b).

3. For each sensor node s outside the area at a distance strictly less than r from a border of the area, we check that the border segment initially covered by s is still covered by sensor nodes within A, even if s is eliminated. Otherwise s is orthogonally projected on the border. We proceed similarly with any sensor node s inside an obstacle at a distance strictly less than r from a border of the obstacle: see Figure 13(c).

4. As a last step, redundant sensor nodes are eliminated.

Upper bound on the number of sensors required

We now extend our previous bound on the maximum number of sensor nodes needed by our method in the presence of obstacles. To deal with obstacles, our method projects nodes within an obstacle at a distance less than r from an edge of the obstacle. That is why, we add a third term to account for obstacles as follows:

OurM axN = NIn + P ∈Outr e∈edge(A)
1 distance(P,e)<r + P ∈InObstr e∈edge(O) 1 distance(P,e)<r [START_REF] Wang | Efficient placement and dispatch of sensors in a wireless sensor network deployment[END_REF] where InObstr denotes the set of sensor nodes within an obstacle at a distance strictly less than r from a border of an obstacle and 1 distance(P,e)<r = 1 if distance(P, e) < r and 0 otherwise.

Comparative evaluation

We consider different configurations to compare our method with the contour-based method described in Section 4. The configurations are various:

• The boot configuration with obstacles, (see Figure 9(a))

with the circumscribing rectangle of size 20r x 18r. This configuration is the simplest one we study.

• The star configuration. This configuration is representative of a complex shape of area with many salient angles. Its circumscribing rectangle is of size 24r x 28r. See Figure 9(b).

• The warehouse configuration, see Figure 9(c), with the circumscribing rectangle of size 28r x 18r. This configuration is representative of an indoor area with several rooms and many obstacles. In the boot configuration, our method needs only 59 sensor nodes, 2 among them are used to cope with obstacles (see Figure 10). The contour-based method needs to deploy 93 sensor nodes. Among these sensor nodes, 17 are due to the presence of obstacles. The overestimation of the contourbased method contributes to increase the deployment cost by a factor of 58%. Furthermore, we notice that this overestimation increases with the number of vertices of the area to cover and the obstacles to avoid. When we vary the sensing range from r to r/2 and r/4, the number of sensor nodes increases drastically as without obstacles. Our method outperforms the contour-based method. For instance, with r/4 the contour-based method requires 737 sensor nodes instead of 645 for our method. This would require the deployment of 92 sensor nodes that could be spared. In addition, the upper bound OurM axN is still very accurate, even in the presence of obstacles. It indicates 62, 197 and 652 instead of the real values 59, 191 and 645 provided by our method.

We obtain similar results with the star configuration: the benefit of our method reaches 40% as depicted in Figure 11. With the more complex configuration of the warehouse, the benefit increases up to 76% as depicted in Figure 12. This can be explained by the fact that this configuration includes several walls inside the area and many obstacles.

HIDDEN ZONE

In this section, we propose a deployment algorithm to cope with the hidden zone due to opaque obstacles.

Problem definition

In this third coverage problem, we consider any irregular 2-D area that includes obstacles and assume that some obstacles and/or some borders of the area are opaque. This may result in hidden zones (see Figure 1). Sensor nodes must be added to cope with them.

Principle

In the presence of opaque borders or opaque obstacles, our method checks whether a hidden zone (see step 4 hereafter) exists. If so, sensor nodes are added. More precisley, the method proceeds according to the following steps:

1. We start with the optimal deployment in the rectangle circumscribing the given area A: see Figure 13(a).

2. Sensor nodes that are outside A or inside the obstacles O are eliminated, which may cause coverage holes: see Figure 13(b).

3. For each sensor node s outside the area at a distance strictly less than r from a border of the area, we check that the border segment initially covered by s is still covered by sensor nodes within A, even if s is eliminated. Otherwise s is orthogonally projected on the border. We proceed similarly with any sensor node s inside an obstacle at a distance strictly less than r from a border of the obstacle: see Figure 13(c).

4. For each sensor node s remaining after step 2, we check whether it is the only sensor node covering a zone in A \ O that becomes hidden because of the opacity of a border or an obstacle. If so, a new sensor node is added as the projection of s in the zone it should cover (see Figure 13(d)).

5. Finally, redundant sensor nodes are eliminated.

Upper bound on the number of sensors required

We now extend our previous bound on the maximum number of sensor nodes needed by our method in the presence of

where In denotes the set of sensor nodes that remain after the elimination of step 2 and 1 distance(P,e)<r = 1 if distance(P, e) < r and 0 otherwise.

Comparative evaluation

We consider again the configurations defined in the previous section, but now the obstacles are opaque.

The contour-based method needs to deploy 93 sensor nodes in the boot configuration, 140 sensor nodes in the star configuration and 197 in the warehouse configuration. Notice that the contour-based method does not distinguish between opaque and transparent obstacles.

In the boot configuration, our method needs only 64 sensor nodes, 5 among them are used just to avoid hidden zones. These sensor nodes are depicted in blue in Figure 13(d). Our method out performs the contour-based method by 48%.

In the star configuration, our method needs only 105 sensor nodes, 4 among them are used to avoid hidden zones. Our method saves 33% of the deployment cost compared to the contour-based method.

In the warehouse configuration, our method needs 134 sensor nodes, 22 among them are added to avoid hidden zones. Our method saves 47% of the deployment cost compared to the contour-based method.

When we vary the sensing range from r to r/2 and r/4, we still observe that our method outperforms the contour-based method as depicted in Figures 14, 15 and 16. The bound OurM axN always provides a very good approximation of the number of sensors required by our method. The comparative evaluation reported in Sections 5, 6 and 7 has the merit to quantitatively evaluate the impact of the complexity of the area (i.e. with/without obstacles, opaque/transparent borders, opaque/transparent obstacles) on the number of sensor nodes needed for a full coverage. The bound we computed OurM axN is very accurate, whatever the configuration. Our method is always better than the contour-based method. Furthermore, we noticed the strong impact of border edges and obstacle edges whose length is smaller than r √ 3/2 on the number of edges required by a contour-based method.

CONCLUSION

With the tremendous progress in technology miniaturization and the high reduction of costs, many monitoring applications are supported by wireless sensor networks. The quality of this monitoring strongly depends on data gathering which assumes the full coverage of the area to monitor. For cost reason, minimizing the number of sensor nodes deployed is sought. In addition, there are many constraints related to the area to monitor: an irregular shape that may be not convex, existence of transparent obstacles, existence of opaque borders and obstacles. To ensure the coverage of such an area constitutes a challenging task that we tackle in this paper. We evaluate the impact of these three factors and propose a method whose complexity gradually increases with the complexity of the coverage problem. The performances of this method are compared with the contour-based method: using our projection-based method, simulation results show that at least 30% of the deployment cost are saved. Our method is simpler than other method based on computational geometry like Delaunay triangulation. Furthermore, we establish bounds on the number of sensors required. The deployment computed by our method can be provided to a mobile robot in charge of placing the static wireless sensor nodes at their optimized location.

Figure 1 :

 1 Figure 1: Hidden zone caused by an opaque obstacle.

Figure 2 :

 2 Figure 2: Optimal deployment based on a triangular tessellation.

Figure 3 :

 3 Figure 3: Coverage hole that is undetected by a contour-based method.

Figure 5 :

 5 Figure 5: Optimal deployment along a border.

Figure 6 :

 6 Figure 6: Projection technique.

Figure 7 :

 7 Figure 7: Principles of our method.

Figure 8 :

 8 Figure 8: Impact of the sensing range on the number of sensor nodes (Boot configuration without obstacles).

Figure 9 :

 9 Figure 9: Configurations studied (Boot, Star, Warehouse).

Figure 10 :

 10 Figure 10: Impact of the sensing range on the number of sensor nodes (Boot configuration).

Figure 11 :

 11 Figure 11: Impact of the sensing range on the number of sensor nodes (Star configuration).

Figure 12 :

 12 Figure 12: Impact of the sensing range on the number of sensor nodes (Warehouse Configuration).

Figure 13 :

 13 Figure 13: Principles of our method.

Figure 14 :

 14 Figure 14: Impact of the sensing range on the number of sensor nodes (Boot configuration).

Figure 15 :

 15 Figure 15: Impact of the sensing range on the number of sensor nodes (Star configuration).

Figure 16 :

 16 Figure 16: Impact of the sensing range on the number of sensor nodes (WarehouseConfiguration).

* This work has been partly funded by the Cluster Connexion.


Ines Khoufi
email: ines.khoufi@inria.fr

Erwan Livolant
email: erwan.livolant@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Mohamed Hadded
email: mohamed.hadded@telecom-sudparis.eu

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Optimized Trajectory of a Robot Deploying Wireless Sensor Nodes

Mobile robots can be used to deploy static wireless sensor nodes to achieve the coverage and connectivity requirements of the applications considered. Many solutions have been provided in the literature to compute the set of locations where the sensor nodes should be placed. In this paper, we show how this set of locations can be used by a mobile robot to optimize its tour to deploy the sensor nodes to their right locations. In order to reduce both the energy consumed by the robot, its exposure time to a hostile environment, as well as the time at which the wireless network becomes operational, the optimal tour of the robot is this minimizing the delay. This delay must take into account not only the time needed by the robot to travel the tour distance but also the time spent in the rotations performed by the robot each time it changes its direction. This problem is called the Robot Deploying Sensor nodes problem, in short RDS. We first show how this problem differs from the well-known traveling salesman problem. We then propose an integer linear program formulation of the RDS problem. We propose various algorithms relevant to iterative improvement by exchanging tour edges, genetic approach and hybridization. The solutions provided by these algorithms are compared and their closeness to the optimal is evaluated in various configurations.

I. CONTEXT AND MOTIVATIONS

More and more applications are supported by wireless sensor networks. They cover areas as diverse as structural health monitoring, smart metering, industrial process monitoring, precision farming, smart cities, control of traffic lights, smart home, etc. The main reason for this tremendous development lies in the ease of deployment of wireless sensor networks. However, to meet the application requirements in terms of coverage and connectivity while minimizing the number of wireless sensors deployed, some rules must be followed. In short, full coverage of an area means that any event occurring in this area will be detected by at least one sensor node. Connectivity means that the information related to any event detected by a sensor node can be delivered to a special wireless node, called the sink, in charge of processing the data gathered from the sensor nodes. Many papers in the literature deal with these two big issues that are coverage and connectivity, leading to various problems mainly depending on the item to cover (area, points of interest, barrier) and on the type of coverage requested (full/partial, permanent/intermittent). The interested reader can refer to [START_REF] Khoufi | Survey of deployment algorithms in wireless sensor networks: coverage and connectivity issues and challenges[END_REF] for a survey of these problems and their solutions.

Concerning the deployment achieved to meet these application requirements, they differ in their goal, their constraints and their implementation (e.g., centralized versus distributed). Most deployments aim at minimizing the number of sensor nodes deployed for cost reasons to achieve the application requirements. Another goal that is frequently encountered in crisis situation (e.g., after a disaster) where a wireless sensor network must be fastly deployed in order to on the one hand help rescuers to save victimes and on the other hand assist in damage assessment. In such cases, the goal is to minimize the time needed to deploy an operational wireless network. This goal is also targeted in hostile environment, where the exposure duration must be reduced. For cost reasons, static sensor nodes are more frequent than mobile ones. That is why in this paper, we focus on the computation of the minimumdelay tour of a mobile robot that has to deploy static wireless sensor nodes at positions that have been previously computed to meet the application requirements in terms of coverage and connectivity. During the moves of the robot, the main energy consumption is due to robot moves. Minimizing the duration of these moves contributes to significantly reduce the energy consumed by the robot. Notice however, that the time and energy needed by the robot depend not only on the distance traveled by the robot but also on the rotations of the robot to change its directions to visit successively all sensor node positions (see Figure 2). Such rotations cannot be neglected because they consume additional time and energy. This problem is called the Robot Deploying Sensors problem, in short RDS. It can be seen as a generalized version of the traveling salesman problem, denoted TSP in the following.

This paper is organized as follows. In Section II, we give a brief state of the art related to wireless sensor network deployment assisted by a robot and TSP. For TSP, we distinguish between algorithms providing either the exact solution or approximated solutions. In Section III we formulate our RDS problem as an Integer Linear Program. In Section IV we present different approximated solutions (e.g., 2-Opt, Genetic and Hybrid) that are evaluated and compared to the exact solution provided by the CPLEX solver [START_REF] Ibm | IBM ILOG CPLEX Optimization Studio -CPLEX Users Manual[END_REF] for various configurations in Section V. We discuss further issues in Section VI and conclude in Section VII.

II. RELATED WORK

Robots are now commercially available. However, the robots vacuum and the robots lawn mowers that we can buy have random trajectories and consequently need a large amount of time to visit a whole area or only some points of interest (e.g., a dirty place or a grassy area). In the literature the problem of exploring a whole zone by a mobile robot has received a lot of attention. Different solutions have been proposed such as [START_REF] Shyam | Obstacle constrained total area coverage in wireless sensor networks[END_REF] and [START_REF] Chang | Obstacle-resistant deployment algorithms for wireless sensor networks[END_REF] that take into account the obstacles that may exist in the area considered, [START_REF] Chang | A dead-end free deployment algorithm for wireless sensor networks with obstacles[END_REF] that adapts itself to the area it discovers. The robot may move in three directions: left, straight and right that are ordered by decreasing priority order. The robot state depends on the number of directions it may take at this time: at least two directions for the normal state, one direction for narrow-lane and zero direction for dead-end. The algorithm used depends on this state. If the robot is initially located at the left-top corner of the rectangular area, it leads to a spiral trajectory. The spiral trajectory is usually preferred to the serpentine trajectory because it is shorter in the absence of obstacles. However, these solutions address the full exploration of a zone that may be combined with a deployment of sensor nodes.

Our problem has many analogies with the well-known Traveling Salesman Problem, called TSP, whose goal is to find the smallest tour visiting all sensor nodes positions (representing the cities) only once and going back to its initial position. This problem has been proved NP-hard. For problems of limited size, the optimal solution can be found with various branch and bound algorithms, integer linear programming solvers like for instance, the CPLEX solver [START_REF] Ibm | IBM ILOG CPLEX Optimization Studio -CPLEX Users Manual[END_REF]. For problems of large size, heuristic and approximation algorithms that give faster results close to optimal are used. These algorithms are either constructive or proceed by iterative improvement. For instance, the 2-Opt [START_REF] Croes | A method for solving traveling salesman problems[END_REF] algorithm improves the current solution by replacing two edges with two new ones to reduce the tour length. Other examples are given by Tabu [START_REF] Semchedine | Routing protocol based on Tabu search for wireless sensor networks[END_REF], [START_REF] Rhazi | A Tabu search algorithm for cluster building in wireless sensor networks[END_REF] and Genetic [START_REF] Norouzi | Genetic algorithm application in optimization of wireless sensor networks[END_REF], [START_REF] Zhu | iMASKO: A Genetic algorithm based optimization framework for wireless sensor networks[END_REF] algorithms. In this paper, we will compare the solutions provided by the 2-Opt algorithm, a Genetic algorithm and an Hybridation of these last two algorithms, with the optimal one for various configurations.

However, our problem differs from the classical traveling salesman problem because the objective is not to minimize the distance traveled but the duration of the tour, taking into account the angular speed of the robot. Consequently, the cost associated with a tour is equal to the time needed by the robot to perform its tour. It is significantly more complex to evaluate that the simple distance between two cities B and C visited successively as illustrated in Figure 2. It should take into account the angle made by the direction the robot had when arriving from A to B and the direction given by BC. Let us consider an example of deployment assisted by a mobile robot. Figure 3 shows the optimal tour of the robot obtained when only the distance is taken into account: this is the optimal tour of TSP. We observe many direction changes in this tour. Figure 4 depicts the optimal tour when both distance and angle are accounted for: this is the optimal tour for RDS. This tour is smoother than the TSP optimal tour. This example clearly points out the difference between the TSP optimal tour and the RDS optimal one. The optimal tour has a duration of 271.55 seconds and a distance of 2035 meters in the RDS problem, whereas it has a longer duration of 385.66 seconds but a shorter distance of 1924 meters in the TSP problem. Our contribution lies in the integer linear programming formalisation of the RDS problem, the proposal of algorithms providing exact or approximated solutions to the RDS problem and the identification of their respective application domains that can be deduced from our comparative evaluation results.

III. FORMALIZATION OF THE RDS PROBLEM The Robot Deploying Sensor nodes problem can be formulated as an Integer Linear Program (ILP).

The robot tour is modeled as a graph G = (V, E) where V is the set of vertices representing the node positions to be visited during the robot tour and E is the set of edges representing the path between node positions. The cardinal of V is n.

Let d i,j denote the distance between the node positions i ∈ V and j ∈ V. Let a i,j,k denote the angle between the edges (i, j) ∈ E and (j, k) ∈ E. Let ls and as be the robot linear speed and the robot angular speed, respectively.

We define x i,j , where i ∈ V and j ∈ V \ {i}, the utility of a path p ∈ E, i.e. x i,j = 1 if and only if p belongs to the robot tour and x i,j = 0 otherwise. Furthermore, let y i,j,k , where i ∈ V, j ∈ V \ {i} and k ∈ V \ {i, j}, be the robot rotation required at a node position. In other words y i,j,k = 1 if and only if the rotation at node j position is effective and y i,j,k = 0 otherwise. Finally we denote z i,j , where i ∈ V and j ∈ V \ {i}, the robot stock of sensor nodes available on the edge (i, j).

The objective is to minimize the time used by the robot to visit all sensor node positions. This time takes into account the time due to both the distance and the rotation angle towards the next sensor node position:

min   i∈V j∈V\{i} d i,j /ls * x i,j + i∈V j∈V\{i} k∈V\{i,j} a i,j,k /as * y i,j,k  
This objective is subject to the following constraints:

∀i ∈ V, j∈V\{i} x i,j = 1 (1)
Contraint 1 allows only one departure for the robot from a node position.

∀j ∈ V, i∈V\{j} x i,j = 1 (2)
Contraint 2 authorizes only one arrival for the robot in a node position.

i∈V j∈V\{i} k∈V\{i,j}

y i,j,k = n -1 (3)
Contraint 3 means that the robot tour includes n-1 rotation costs to make a complete tour.

∀i ∈ V,∀j ∈ V \ {i}, ∀k ∈ V \ {i, j}, y i,j,k ≤ (x i,j + x j,k )/2 (4)
Contraint 4 ensures that any rotation cost corresponds to a pair of consecutive edges followed by the robot.

∀i ∈ V \ {1}, ∀k ∈ V \ {i, 1}, y i,1,k = 0 (5)
Contraint 5 guarantees that the rotation cost of the robot in its start position is not accounted for. In fact, when the robot comes back to its start position, it does not need to rotate toward any next node position, since the tour is complete.

∀i ∈ V, ∀j ∈ V \ {i}, z i,j ≤ (n -1) * x i,j (6)
Contraint 6 denotes the maximum capacity of the robot in terms of sensor nodes.

∀i ∈ V, h∈V\{i} z h,i + n if i = 1 0 otherwise = j∈V\{i} z i,j + 1 (7)
Contraint 7 expresses that the robot carries a certain number of sensor nodes. This number decreases with the number of node positions already visited by the robot.

The ILP formulation of the RDS problem differs from this of the TSP problem on the following points:

• The second term in the objective function has been added to account for the time lost in rotations. • Constraints 3, 4, 5 have been introduced to deal with the robot rotation constraints. This model of RDS adopts the following assumptions: A1: The robot knows its location and is able to move autonomously to any location specified in the area considered. A2: The set of sensor nodes positions are given as well as the initial location of the robot. A3: The connectivity graph of sensor nodes positions is assumed to be complete. In other words, it is always possible for the robot to go from any sensor node position to any other sensor node position. For each pair of sensor node positions, the distance is given. For each triple of sensor node positions, the rotation angle is given. The next three assumptions are adopted for the sake of simplicity. They will be relaxed in Section VI. A4: There is no obstacle in the paths between any two sensor node positions. A5: The robot has enough capacity to carry all sensor nodes it has to deploy. A6: The robot has enough energy to visit all sensor nodes locations in a single tour.

IV. PROPOSED ALGORITHMS

We now describe the algorithms solving the RDS problem that we will compare in the next section. We consider an algorithm providing the exact solution and three algorithms providing approximated solutions.

A. The exact solution

The exact solution of the RDS problem is provided by the solver CPLEX [START_REF] Ibm | IBM ILOG CPLEX Optimization Studio -CPLEX Users Manual[END_REF] using the problem formulation given in Section III. This exact solution will be used as a reference to evaluate the closeness to the optimal of approximated solutions. Various approximated solutions are used. The first one, called 2-Opt, is based on iterative improvement, the second one uses genetics and the third one is an hybridation between them.

B. 2-Opt algorithm

We adapt the well-known 2-Opt algorithm [START_REF] Croes | A method for solving traveling salesman problems[END_REF] to the RDS problem. 2-Opt starts with an initial solution and tries to iteratively improve it by replacing two edges with two new ones that reduce the tour duration. This algorithm provides a local optimum based on the initial solution.

C. Genetic algorithm

A genetic algorithm is inspired from the biological evolution process. To define a genetic algorithm, we have to define the selection of the initial population, the operators we use for the selection of parents, the crossover and the mutation and finally the constitution of the population used in the next iteration as well as the fitness function. In the traveling salesman problem, an individual is defined by an ordered sequence of the cities visited by the robot. The initial population is given by K individuals, K is a non-null natural integer, each individual being a random permutation of the C cities to visit. The first city is the initial location of the robot. Hence, it is given as an input.

Let P i denote the population at the beginning of any iteration i > 0. The Genetic algorithm randomly selects K/2 pairs of parents among the current population P i , apply the crossover operator on each pair to generate two children. Each gene (i.e. a city visited) of a child is subject to a mutation with a gene mutation probability of P mut . A new population P new is then generated. All individuals of P i ∪ P new are evaluated by the fitness function. The fitness of an individual is equal to one over the time needed by the robot to perform this tour. The K/2 best individuals (i.e., maximizing the fitness function) among the P i ∪ P new are selected, they are completed by K -K/2 individuals randomly selected among the unselected ones to constitute P i+1 the population considered in the next iteration. This principle enables the algorithm to always keep the K/2 best individuals it has found during the Imax iterations performed by the algorithm.

In [START_REF] Kumar | A comparative analysis of PMX, CX and OX crossover operators for solving traveling salesman problem[END_REF], a genetic algorithm is built to solve TSP. The mutation operator exchanges two genes, selected at two random positions, of an individual. The three crossover operators considered, PMX (for Partially Matched Crossover), CX (for Cyclic Crossover) and OX (for Ordered Crossover), ensure that the crossover of any two individuals is still an individual (i.e. a permutation of the C cities to visit). Furthermore, it is shown that PMX outperforms the two other crossover operators CX and OX. Hence, we select PMX as our crossover operator, using two cross points randomly selected.

D. Hybrid algorithm

The Hybrid algorithm combines the 2-Opt algorithm with a genetic one. More precisely, instead of starting with an initial random population, the Hybrid algorithm applies the 2-Opt algorithm to optimize each individual of the initial population. In addition, at each iteration, the children obtained with the crossover operator are mutated with the gene mutation probability and then optimized by applying again the 2-Opt algorithm.

V. COMPARATIVE EVALUATION

We evaluate the different algorithms presented in Section IV on different configurations ranging from 10 sensor nodes to 154 sensor nodes. These configurations may meet various application requirements. For instance, small configurations with less than 30 nodes are representative of temporary industrial worksites, where coverage of some interest points and connectivity with a sink must be achieved. Medium to large configurations, from 50 to 150 nodes, can represent industrial warehouses where full coverage and connectivity with a sink must be met. Small and medium configurations with less than 70 nodes can also be encountered to improve data gathering about an industrial process to detect leakages for example.

For this performance evaluation, we take the following parameters values: ls = 10 meters per second, as = 10 degrees per second for the robot linear and angular speeds, respectively; P mut = 0.15, Imax = 1000 iterations for Genetic and Imax = 100 for Hybrid, K ≥ 2 * C individuals, where C is the number of sensor nodes to deploy. Sensor nodes are deployed in the area depicted in Figure 1. The dimensions of the circumscribing rectangle are 530m x 300m, the sensing range varies from 140m to 20m to match a number of sensor nodes from 10 to 154.

First, we compute the solutions to the TSP and RDS problems for a number of sensor node positions ranging from 10 to 154, using 2-Opt. Figure 5 clearly shows that if for very small configurations (i.e., configurations with at most 10 sensor nodes), the tours found by TSP and RDS may be the same. This is no longer the case when the number of sensor nodes increases, the difference between the TSP solution and the RDS one increases considerably. Secondly, we compare the accuracy (i.e., closeness to the optimal) of the solutions provided by each algorithm tested in small configurations (≥ 31 sensor nodes). Figure 6 depicts the solutions given by 2-Opt, Genetic and Hybrid versus the optimal one in small configurations. When the number of nodes is higher than 13 sensor nodes, Genetic fails to find the optimal tour in 1000 iterations. This is due to the fact that it generates many tours that are not interesting. On the contrary, 2-Opt provides a solution that is close to the optimal for the configurations tested. Hybrid provides the best results as an approximation algorithm. For large configurations, Hybrid improves the solution found by 2-Opt as shown in Figure 7. For instance, for 103 and 154 nodes, Hybrid decreases the tour duration from 629.1s to 628.15s and from 752.95s to 749.41s, respectively. This can be explained by the fact that 2-Opt can be blocked in a local optimal, whereas Hybrid uses mutations and crossovers to explore other tours. However, 2-Opt is better to exploit a given solution. We observe also that Genetic is very sensitive to the choice of the initial population: if it is far from the optimal, the final solution remains far from the optimal. In the configurations tested, 2-Opt improves the initial solution by at least 50%. Another interesting result is given by the time needed by each algorithm to compute its final solution. CPLEX is run on a Quad-core Intel Xeon W3565 3.2GHz platform, whereas the other algorithms are run on a 8-core Intel i7-2760QM 2.4GHz platform. Tables I and II depict the computation time for each algorithm tested. As expected, Optimal needs the largest computation time in all configurations tested except for 10 nodes. For example, it takes about 3 hours to solve the RDS problem with 22 sensor nodes. Hybrid needs the second largest time. This is due to the calls to the 2-Opt algorithm applied first on each individual of the initial population and then on each child generated by the crossover operator. For example, it takes 636 seconds (about 6,5mn) to generate the final solution of the RDS problem with 22 sensor nodes. The fastest algorithms are 2-Opt and Genetic to a lesser extent. In all configurations tested, 2-Opt is at least 10 times faster than Genetic, this ratio reaches 100 times in small configurations. Since Genetic may provide a solution far from the optimal one, 2-Opt is preferred. For larger configurations, (more than 31 nodes), we did not succeed to obtain the optimal solution with CPLEX after 24 hours computation. Since in configurations with more than 30 nodes, CPLEX needs a time higher than 24 hours, we take as final solution, the best solution found by CPLEX in 24 hours. This solution may be a non-optimal one, as depicted in Figure 7 by a star symbol. In all these configurations, Hybrid provides the best results. We recommend the Hybrid algorithm for large configurations because it provides the best trade-off between the optimal closeness and an acceptable computation time.

VI. DISCUSSION

In this section, we show how to relax the assumptions A4 (no obstacle), A5 (enough capacity) and A6 (enough energy).

A. Obstacles

Up to now we have considered a sensor deployment in an area without obstacles. However in the real life, obstacles may be present. In this section, we show how to relax the assumption A4 and extend the solutions given previously to cope with obstacles. In a previous paper [START_REF] Khoufi | A Simple Method for the Deployment of Wireless Sensors to Ensure Full Coverage of an Irregular Area with Obstacles[END_REF], we proposed a deployment algorithm that copes with transparent and opaque obstacles and ensures full coverage; This algorithm computes the sensor node positions that are given as input to the RDS algorithm. It is hard to compute an optimized robot trajectory taking into account obstacles. If there exists an obstacle between the sensor node positions A and B, the direct path from A to B is made impossible. Thus the connectivity graph of the cities is no longer a complete graph. We propose to define intermediate positions I i that allow the robot to reach B avoiding the obstacles. We replace the impossible direct path between A and B by a possible one that can be seen as a juxtaposition of segments I i I i+1 with I 1 = A and I n = B. The cost of this path is computed as the sum of the cost of any segment composing the path. Figure 8 shows the two intermediate points that are introduced in the path taken by the robot to reach B from A. The path AI 1 I 2 B replaces the direct path AB.

B. Capacity constraint

Up to now we have assumed that the robot has the capacity to carry all sensor nodes at the same time. If this is not the case, assumption A5 is no longer true. In such a case, the robot has to perform subtours starting at its initial position. How can we solve this new problem?

In order to handle the new carrying capacity constraint, we enhance the integer linear program of Section III as follows:

Let cap be the robot carrying capacity in terms of number of sensor nodes. The objective is the same as before and only three constraints are modified. Constraints 1 and 2 specifying that there is only one arrival and departure in each city are relaxed to enable multiple arrivals and departures in the initial robot position. In fact, the robot must come back to its initial position to refill its sensor node stock.

∀i ∈ V \ {1}, j∈V\{i} x i,j = 1 (8) ∀j ∈ V \ {1}, i∈V\{j} x i,j = 1 (9)
Furthermore, the capacity constraint 6 must be updated according to the capacity parameter cap.

∀i ∈ V, ∀j ∈ V \ {i}, z i,j ≤ cap * x i,j (10)
Figure 9 depicts an optimal RDS tour when the robot has to deploy 13 sensor nodes and its capacity is limited to 6 sensor nodes. This optimal tour comprises 3 subtours depicted in blue, each of them starting at the initial position of the robot. Table III gives the number of subtours done by the mobile robot when its capacity is 6, 5, or 4 sensor nodes respectively. When the robot capacity decreases, the number of subtour increases as expected, leading to a longer tour duration.

C. Energy constraint

What happens if the maximum energy level of the robot does not allow it to visit all sensor nodes locations in a single tour. Assumption A6 is no longer true. Here again, the robot proceeds by subtours, refilling its battery at its initial position that is also the starting point of each subtour. An idea could be to group sensor nodes into clusters, such that the robot deploys all the sensor nodes of the same cluster in a single subtour. Notice that the number of cluster members may differ from one cluster to another, since the robot consumes more energy to visit a far cluster than a close one.

VII. CONCLUSION

In this paper we have shown how to optimize the delay needed by a mobile robot to deploy sensor nodes, taking into account the rotations performed by the robot to change its direction. The delay-optimized tour of a mobile robot may result in a reduction of at least 50% in the time needed to deploy wireless sensor nodes. This smaller deployment time may be crucial not only in emergency applications but also in industrial process control because the latency before the first data gathering is reduced. This benefit is obtained by using the optimal solution that can be provided by an integer linear program solver like CPLEX for instance in small and medium configurations. For larger configurations, the time needed to obtain the optimal solution can become prohibitive. That is why we use the Hybrid algorithm that successfully combines the exploration of the Genetic algorithm with the exploitation of 2-Opt algorithm.

Fig. 1 .

 1 Fig. 1. A WSN deployment assisted by a robot.

Fig. 2 .

 2 Fig. 2. Rotation angle between cities A, B and C.

Figure 1

 1 Figure1illustrates an example of deployment in an area with irregular shape where a circle denotes the sensing range of the sensor node located in its center. The red point represents the initial position of the robot. This robot must visit each sensor node position to place each sensor node. The goal is to minimize the time needed by the robot to perform its mission. During the moves of the robot, the main energy consumption is due to robot moves. Minimizing the duration of these moves contributes to significantly reduce the energy consumed by the robot. Notice however, that the time and energy needed by the robot depend not only on the distance traveled by the robot but also on the rotations of the robot to change its directions to visit successively all sensor node positions (see Figure2). Such

Fig. 3 .

 3 Fig. 3. Optimal tour with TSP. Fig. 4. Optimal tour with RDS.

Fig. 5 .

 5 Fig. 5. Solutions found by 2-Opt for the RDS and TSP problems.

Fig. 6 .

 6 Fig. 6. Final solutions of Optimal, 2-Opt, Genetic and Hybrid for small configurations.

Fig. 7 .

 7 Fig. 7. Final solutions of Optimal, 2-Opt, Genetic and Hybrid for large configurations.

Fig. 8 .

 8 Fig. 8. Intermediate points between sensor node positions A and B

Fig. 9 .

 9 Fig. 9. Optimal RDS tour with a limited capacity of 6.

TABLE I COMPUTATION

 I TIME FOR OPTIMAL, 2-OPT, GENETIC AND HYBRID FOR SMALL CONFIGURATIONS.

	Number of nodes	10	13	22	31
	Optimal (s)	11.18	217.35	10866.24 87387.77 *
	2-Opt (s)	0.005	0.003	0.014	0.029
	Genetic (s)	0.396	0.505	0.845	1.161
	Hybrid (s)	2.808	6.788	44.319	276.9

TABLE II COMPUTATION

 II TIME FOR OPTIMAL, 2-OPT, GENETIC AND HYBRID FOR LARGE CONFIGURATIONS.

	Number of nodes	44	68	105	154
	Optimal (s)	174828.61 *	103910.62 *	-	-
	2-Opt (s)	0.114	0.339	2.051	3.689
	Genetic (s)	2.857	7.065	18.969	39.8
	Hybrid (s)	870.45	3743.66	27111.4	41267.3

TABLE III OPTIMAL

 III TOUR WITH DIFFERENT ROBOT CAPACITIES.

	Robot capacity	13	8	6	4
	Subtours (number)	1	2	3	4
	Length (m)	1712	2169	2562	3048
	Time cost (s)	237.64	262.98	319.11	385.70