3D Surface Covering with Virtual Forces

3D Surface Covering with Virtual Forces

Nadia Boufares1, Leila Saidane1

1 National School for Computer Science, Cristal Laboratory, La Manouba, Tunisia

Ines Khoufi2, Pascale Minet2

2 Inria Rocquencourt, 78153 Le Chesnay Cedex, France

Abstract Wireless Sensor Networks (WSNs) are widely used in monitoring applications. Depending on the entity to be monitored, sensor nodes are deployed in a two dimension (2D) area or a three-dimension (3D) area. In addition, sensor nodes can be deployed either in a distributed way or centralized way: a central entity computes their positions and mobile robots place the static sensor nodes at their positions. In this paper, we are interested in a fully distributed deployment of WSN in a 3D- surface using autonomous and mobile nodes. Our goal is to ensure full 3D surface coverage and maintain network connectivity. To reach our goal we propose 3D-DVFA-SC, a distributed deployment algorithm based on virtual forces strategy to move sensor nodes. Simulation results show that 3D- DVFA-SC provides a very good coverage rate while maintaining network connectivity.

KeywordsWSN, 3D Surface covering, coverage, connectivity, deployment, virtual forces.

1. CONTEXT AND MOTIVATION

   Wireless sensor networks (WSNs) are deployed in an area of interest in order to monitor physical or environmental conditions, such as temperature, sound, pressure, etc. To perform the monitoring task, two main issues should be considered: area coverage and network connectivity. The area to be monitored is fully covered if each event occurring in this area can be detected by at least one sensor node. Network connectivity is maintained if there is at least one path between each sensor node and a central entity called sink. Then, each detected event can be reported to the sink. WSNs are used in many monitoring applications such as military battlefields, environment disaster, home automation, industrial monitoring. These applications differ by, on the one hand, the entity to be monitored that can be a 2D or a 3D area, Points of Interest (PoIs) or barrier and, on the other hand, the coverage and connectivity requirements. The coverage of the entity to be monitored can be full or partial and network connectivity can be either temporary or permanent. To meet the application requirements, a deployment algorithm is needed to determine the appropriate sensor node positions. The deployment

   meet required coverage and connectivity. Autonomous and mobile sensor nodes can be used to cover a 2D area or 3D area. In 3D, we have to distinguish volume covering from surface covering: in the first case, the entity to cover is the whole volume of a polyhedron as depicted in Figure 1a. A sensor node can be located at any position inside the polyhedron. Whereas in the second case, sensor nodes should be placed only on the surface considered, that is not flat (e.g. a mountain). This surface may have different variations as depicted in Figure 1b. So, the sensor nodes should follow the shape of this surface. In this work we are interested in ensuring full coverage of a 3D surface.

   Recent studies [1] reveal that sensor deployment on 3D surface is totally different from deployments in a 2D plane or a 3D volume. It tackles new challenges such as how to handle variations in the shape of the 3D surface. Some applications require a 3D surface covering, such as snow tracking in a mountainous area or forest fire detection. Thus, existing solutions developed for 2D planar or 3D volumetric deployment are no longer valid for applications requiring 3D surface covering. For instance, a 2D deployment applied to 3D surface may lead to coverage holes. That is why we propose to design a 3D distributed deployment algorithm whose aim is to deploy sensor nodes over the 3D surface area in order to ensure full coverage and maintain network connectivity. This paper is organized as follows: In section II, we give an overview of the state of the art. Section III describes our 3D distributed virtual forces algorithm in details. Section IV deals with the performance evaluation of our algorithm. Finally, we conclude in Section V.

   algorithm can be centralized, the central entity in charge of computing the deployment must collect the current positions of all sensor nodes. Then, a human or mobile robot will be in charge of placing a sensor node at each computed position. Otherwise, the deployment algorithm is distributed when sensor nodes are mobile and autonomous, and able to exchange information to reach their final position progressively. In our study, we focus on distributed deployment algorithms where sensor nodes are able to cooperate in order to determine their appropriate positions that

   1. Polyhedron

      Fig.1: 3D Area

   2. 3D Surface

2. RELATED WORK

   In the literature, several strategies for the deployment of wireless nodes are proposed to determine the appropriate node positions. We distinguish three main deployment strategies [2]: grid-based strategy, computational based strategy and virtual forces-based strategy. These strategies are proposed to monitor 2D area, however, they can be extended to monitor 3D area (e.g. volume or surface).

   If the grid based strategy is adopted, sensor nodes are placed either at cell centers or cell vertices. In the case of monitoring an area with irregular borders, some positions that do not belong to the grid should be added to avoid coverage holes near these borders. The authors in [3] proved that the truncated octahedron cells constitute the best tessellation to ensure the coverage of a volume using the minimum number of sensor nodes. Sensor nodes positions are the centers of truncated octahedrons. In order to maintain network connectivity, the communication range R must be at least 1.7889 times the sensing range r.

   The computation geometry strategy is generally based on Voronoi diagram or Delaunay triangulation to determine sensor nodes positions. This strategy has a high cost of computation since a global knowledge of the area is required. The authors in [4] focus on finding the optimal deployment on 3D surfaces whose goal is to achieve the highest overall sensing quality. They showed that the optimal deployment can be determined based on a special type of Voronoi diagram which is called Centroidal Voronoi tessellation. They proposed algorithms able to support different 3D surfaces. However, sensor nodes are static and their positions are computed by a central entity. Then, these algorithms are not scalable. Another study in

   [5] is also based on Voronoi diagram to ensure 2D or 3D kcoverage (i.e. an area is covered by at least k sensor nodes). The authors proposed an autonomous deployment for load balancing k-surface coverage called APOLLO. This algorithm allows sensor nodes to move and achieve k-coverage, while minimizing the maximum sensing range required by the nodes.

   The virtual forces strategy is based on attractive or repulsive forces to move sensor nodes based on a predefined target distance that should be maintained between neighbors. Then, if the distance between two sensor nodes is less than , a repulsive force is exerted. If this distance is greater than , an attractive force is exerted. Otherwise, the force is null. Then sensor nodes move according to the resultant of these forces. Virtual forces strategy allows sensor nodes to compute their positions autonomously. The 3D version of the virtual forces is used in both [6], [7] and [8], to ensure full coverage of 3D area (volume) and maintain network connectivity. The benefit of these algorithms is due to the simple pinciple of the virtual force strategy: sensor nodes are able to spread in the whole area and reach rapidly the final deployment.

   In this paper, we focus on 3D surface coverage. We assume that the 3D surface may be unknown or hostile and sensor nodes are mobile. We adopt the virtual forces strategy to spread over the whole 3D surface (e.g. mountains). The goal is to ensure full 3D surface coverage and maintain network connectivity.

3. OUR CONTRIBUTION: 3D-DVFA-SC

   To deploy sensor nodes in 3D-surface, we propose 3DDVFA- SC algorithm: 3D Distributed Virtual Forces Algorithm for Surface Covering. 3D-DVFA-SC is a distributed algorithm based on the virtual forces strategy to spread sensor nodes in the whole 3D-surface while maintaining network connectivity. The aim of the virtual forces is to maintain the same target distance between neighboring nodes. This target distance is called , Distance threshold.

   1. Models and Assumptions

      In this paper we adopt the following assumptions in order to cover the whole 3D surface:

      • Each sensor node is mobile and autonomous.

      • Each sensor node can determine its own position from global positioning system (GPS).

      • The binary sensing model is adopted as the sensing model, which means the probability of detecting the target is 1 if it is within the sensors sensing range, and 0 otherwise.

      • The sensing range and communication range of any sensor node are modeled by two spheres of radius r and R respectively (see Figure 2).

      • The entity to monitor is a 3D surface, see Figure 1b.

      • The 3D surface exerts a gravitational attraction on sensor nodes, as depicted in Figure 3. This gravitational attraction maintains each sensor node on the surface. This attraction combined with the resultant of the virtual forces gives a force tangent to the surface.

        Fig. 2: Sensing and communication ranges modeled by Spheres

   2. Principles of 3D-DVFA-SC

   The 3D-DVFA-SC algorithm proceeds in iterations. At each iteration, each node broadcasts a Hello message. In the Hello message, each node sends its position and the nodes it hears in order to perform the neighborhood discovery. Then, each sensor node is able to determine its 1-hop neighbors and 2- hop neighbors. It is then able to compute its new position according to the forces exerted on itself by its 1-hop and 2- hop neighbors.

   TABLE 1: Simulation Parameters Topology

   Sensor nodes 300

   3D surface considered Equation 1 MAC Layer

   Fig. 3: Gravitational attraction on the sensor node

   Let denote the Euclidean distance between the sensor nodes and .

   Protocol IEEE 802.11b

   Throughput 2 Mb/s

   Transmission range R 15 m

   Sensing range r 9m

   is given by

   ( )2

   + ( )2

   2

   + ( ) .

   Simulation

   The force exerted by sensor on sensor is

   • an attractive force if > and is given by:

     Simulation time 2500s

     3D-DVFA

     =

     · ( ) · ( , , )

     Ka 0.004

   • a repulsive force if < and is given by:

     · ( ) · ( , , )

     =

     Kr 0.25

     Hello period 2.4s

     Dth 10m

     Distmax 4

   • null otherwise, ( = )

   Hence, the resultant force on is computed as the sum of these forces exerted by its 1-hop and 2-hop neighbors:

   =

   Since the sensor node should follow the 3D surface considered, node will move according to the resultant force and the gravitational attraction of the 3D surface. Notice that

   and are the attractive coefficient and the repulsive coefficient of the virtual forces strategy, respectively. To favor the convergence of the algorithm, the coefficient should be much higher than the . To improve efficiency of the algorithm, the distance traveled by each sensor node at each iteration is limited by , a parameter of the 3D-DVFA- SC algorithm .

4. PERFORMANCE EVALUATION

   1. Simulation Parameters

      To evaluate performances of our 3D-DVFA-SC algorithm, we implemented it in the Network Simulator NS3 version

      3.20. Table I illustrates the simulation parameters used to evaluate the 3D-DVFA-SC algorithm. The values of and

      are tuned by series of simulations. The 3D surface considered is depicted in Figure 4. Its equation is given by:

      ( 50)2 ( 50)2

      Fig. 4: 3D surface corresponding to Equation 1

      We evaluate 3D-DVFA-SC using two initial configurations:

      • Random configuration, when sensor nodes are randomly scattered in the whole 3D-surface (mountain) by an aircraft, for instance (see Figure 5a).

      • Bottom of the mountain configuration, when sensor nodes are placed randomly at the bottom of the mountain (see Figure 5b).

      z = 80 exp ( 600 ) (1)

      a. Random configuration b. nodes are at the bottom

      of the mountain

      Fig 5: Initial Configuration

      a. Full 3D coverage b. network connectivity maintained

      Fig 6: Final Deployment

      To evaluate 3D-DVFA-SC, we performed 20 simulations for each configuration (i.e. random, bottom of the mountain).

   2. Simulation Results

      1. Coverage rate : We evaluate the coverage as a function of time for both configurations. To compute the coverage of a 3D-surface, we build a virtual grid of unit cells and we project each cell center on the 3D-surface. Each cell center projected is considered covered if it is at a distance less than or equal to the sensing range of at least one sensor node. Figure 7 shows the coverage rate obtained by both configurations. When sensor nodes are randomly deployed in the whole 3D-surface, the coverage rate reaches 100% at time 1000s. However, when sensor nodes are initially at the bottom of the mountain, the coverage rate at the end of the simulation is 90%. This is due to the shape of the mountain. Sensor nodes need much time to reach the top of the mountain when they are initially deployed at the bottom. However, the very good results obtained in short time by using the initial random configuration can be explained by the fact that when sensor nodes are scattered in the whole area, the coverage rate is initially good and it is improved by 3D-DVFA-SC algorithm. The 3D-DVFA-SC algorithm enables sensor nodes to heal coverage holes when the initial configuration is random and to maintain network connectivity. Final deployment is illustrated in Figure 6. Figure 6a shows that full 3D-surface coverage is ensured and

         Figure 6b shows that network connectivity is maintained by the 3D-DVFA-SC algorithm. Notice that, in our study, we take into account the opaque shape of the mountain. Then, neighboring sensor nodes (i.e. where sensor nodes are at a distance less than or equal to the communication range) may not be able to communicate since the line of sight between them cross the mountain. In such a case, the connectivity is maintained only between neighboring sensor nodes whose line of sight does not intersect the 3D-surface and whose distance is less than or equal to R.

         Fig. 7: Coverage as a function of time

      2. Distance Traveled: We evaluate the total distance traveled by nodes as a function of time for both configurations. Figure 8 shows the accumulative distance traveled by nodes during the simulation time. We can observe that this distance increases as a function of time. This is due to node oscillations problem, the main drawback of the virtual forces strategy. Then, sensor nodes are still oscillating even if the full coverage is ensured.

   Fig. 8: Distance traveled as a function of time

5. CONCLUSION

In this paper, we proposed 3D-DVFA-SC, a distributed deployment algorithm based on virtual fores to ensure full 3D-surface coverage and maintain network connectivity. We evaluated 3D-DVFA-SC using two different initial configurations. When 3D-DVFA-SC algorithm is executed with the initial random configuration, 100% coverage rate is reached. However, when sensor nodes are initially at the bottom of the mountain, the coverage rate is slightly smaller than with the other configuration. We also evaluated the total distance traveled by nodes. Simulation results show that sensor nodes still moving even when full 3D-surface coverage is reached. This is due to node oscillations problem. This problem will be tackled in our future work.

REFERENCES

1. M.-C. Zhao, J. Lei, M.-Y. Wu, Y. Liu, and W. Shu, Surface coverage in wireless sensor networks, in IEEE INFOCOM, 2009.

2. I. Khoufi, P. Minet, A. Laouiti, and S. Mahfoudh, Survey of deployment algorithms in wireless sensor networks: coverage and

   connectivity issues and challenges, International Journal of Autonomous and Adaptive Communications Systems (IJAACS), p. 24, 2014.

3. S. Alam and Z. J. Haas, Coverage and connectivity in three- dimensional networks, in Proceedings of the 12th annual international conference on Mobile computing and networking. ACM, pp. 346357, 2006.

4. M. Jin, G. Rong, H. Wu, L. Shuai, and X. Guo, Optimal surface deployment problem in wireless sensor networks, in IEEE INFOCOM, pp. 23452353, 2012.

5. F. Li, J. Luo, W. Wang, and Y. He, Autonomous deployment for load balancing-surface coverage in sensor networks, Wireless Communications, IEEE Transactions on, vol. 14, no. 1, pp. 279293, 2015.

6. X. Li, L. Ci, M. Yang, C. Tian, and X. Li, Deploying three- dimensional mobile sensor networks based on virtual forces algorithm, in Advances in Wireless Sensor Networks. Springer, pp. 204216, 2013.

7. C. Miao, G. Dai, X.-m. Zhao, Z. Tang, and Q. Chen, 3d self- deployment algorithm in mobile wireless sensor networks, in Advances in Wireless Sensor Networks. Springer, pp. 2741, 2014,.

8. N. Boufares, I. Khoufi, P. Minet, L. Saidane, and Y. Ben Saied, Three dimensional mobile wireless sensor networks redeployment based on virtual forces, in IEEE Wireless Communications and Mobile Computing Conference (IWCMC), pp. 563568, 2015.