Sage Journals: Discover world-class research

Abstract

The effectiveness of wireless sensor networks (WSN) depends on the regional coverage provided by node deployment, which is one of the key topics in WSN. Virtual force-based algorithms (VFA) are popular approaches for this problem. In VFA, all nodes are seen as points subject to repulsive and attractive force exerted among them and can move according to the calculated force. In this paper, a sensor deployment algorithm for mobile WSN based on van der Waals force is proposed. Friction force is introduced into the equation of force, the relationship of adjacency of nodes is defined by Delaunay triangulation, and the force calculated produce acceleration for nodes to move. An evaluation metric called pair correlation function is introduced here to evaluate the uniformity of the node distribution. Simulation results and comparisons have showed that the proposed approach has higher coverage rate, more uniformity in configuration, and moderate convergence time compared to some other virtual force algorithms.

1. Introduction

Wireless sensor networks (WSN), with its advanced abilities in sensing and communication, is an emerging technology that promises a wide range of potential application in both civilian and military areas due to its low power consumption, low cost, distributed, and selforganization property. A wireless sensor network typically consists of a large number of low-cost, low-power, and multifunctional sensor nodes that are deployed in a region of interest [1, 2]. These nodes are equipped with sensors, microprocessors, and mutual communication devices, so that they have sensing ability as well as data processing and communication. WSN can be used for target tracking, temperature and environmental monitoring, security surveillance, data collection, smart homes and offices, health care, and industrial diagnosis, and so forth, thus it is an active research area of interest recently.

In the applications of WSN, energy saving, connectivity, and configuration uniformity are some of the key respects of interest, which are also related with coverage rate of the whole network. Because of this, coverage becomes an important issue in WSN. It mainly addresses how to deploy the sensor nodes to achieve sufficient coverage of the service area, so that each position in the service area is monitored at least by one sensor node.

The coverage ratio of the WSN is calculated by [3]

\begin{matrix} CR = \frac{⋃ c_{i}}{A}, i \in S, \end{matrix}

(1)

where

c_{i}

is the coverage of sensor i, Sis the set of nodes, and A is the total size of the area of interest. The aim of the optimization technique is to maximize the coverage rate of the network.

A good coverage is indispensable for the effectiveness of wireless sensor networks. An efficient deployment of sensor nodes will reduce the configuration and communication cost of the network and improve the resource management, thus node deployment becomes a challenging work.

Node deployment algorithms can be divided into deterministic or movement-assisted ones. In movement-assisted deployment algorithms, each sensor knows its position; the mobile sensors can communicate with others and can move to new positions accordingly. In some cases such as remote and unmanned environments, mobile wireless sensor networks are initially distributed randomly, and only movement-assisted deployment can be applied.

Many approaches have been proposed for movement-assisted node deployment [4, 5], such as virtual force-based [3, 6–12], swarm intelligence [13–17], and computational geometry [18], and so forth, or some combination of the above approaches [19, 20], among which, the kind of virtual force-based strategies has emerged as one of the effective solutions. In this paper, a virtual force-based node self-deployment algorithm using a force model based on van der Waals force is proposed. The relationship of adjacency of nodes is defined by Delaunay triangulation, and the force calculated produces acceleration for the nodes to move. A new metric called pair correlation is introduced to evaluate the uniformity of the node distribution. Simulation results showed that the proposed approach is better than the original virtual force algorithm in convergence time, coverage rate, and more uniformity in configuration.

The rest of this paper is organized as follows. Section 2 gives a brief introduction of virtual force-based approach. Section 3 introduces the proposed algorithm. A few simulation results are given in Section 4 to verify the effectiveness of the proposed algorithm. Finally, with several improvements discussed for our future work, we conclude the paper in Section 5.

2. Virtual Force Based Node Deployment Algorithms

Virtual force-based algorithm is a popular approach for node deployment. In this kind of algorithm, the sensor nodes, the obstacles, and the preferential areas are modeled as points subject to attractive or repulsive force among them. By setting a threshold of the desired distances among sensors, each sensor moves in accordance with the summation of the force vectors, and eventually a uniform deployment is achieved.

Some assumptions are made in the virtual force algorithm [6]: first, an individual node should be able to acquire the relative position of other nodes within its communication range; second, all the nodes can move according to the calculation results of the algorithm effectively; third, all the nodes are homogeneous with omnidirectional sensors, which means that for each node, the sensing range is identical for all nodes and the sensing areas they sensed are circles with the node at its center, so is the communication range.

Virtual force-based node deployment approach is inspired by the artificial potential field-based techniques in the field of robotic obstacle-avoidance [21, 22]. Based on disc packing and virtual potential theory, Zou and Chakrabarty designed a VFA algorithm [6], in which each node $s_{i}$ is subjected to three kinds of forces: (1) a repulsive force $F_{i R}$ , exerted by obstacles, (2) an attractive force $F_{i A}$ , exerted by areas of preferential coverage (sensitive areas where a high degree of coverage is required), and (3) an attractive or repulsive force $F_{i j}$ , by another node $s_{j}$ depending on its distance and orientation from $s_{i}$ . A threshold distance $d_{th}$ is defined between two nodes to control how close they can get to each other. The net force on a sensor $s_{i}$ is the vector sum of all the above three forces:

\begin{matrix} F_{i} = F_{i R} + F_{i A} + \sum_{j = 1, j \neq i}^{k} F_{i j} . \end{matrix}

(2)

Two-sensor detection models can be applied on VFA algorithms: the binary detection model and the probabilistic detection model [6]. Then, Heo and Varshney add some restrictions on the function of force [3]. Kribi et al. improved original VFA and proposed Serialized VFA, Lmax_Serialized_VFA, and Dth_Lmax_Serialized_VFA [7]. Garetto et al. proposed a distributed sensor relocation scheme based on virtual force and made a restriction that there are at most only six nodes that can exert force on current node, and it has good coverage rate and can response to the event quickly [8]. Yu et al. introduced the idea of Delaunay triangulation to define the adjacent relation to propose a virtual force approach of better convergence time and coverage rate [9] and introduced van der Waals force into this problem [10]. An expression of exponential function for the relationship of virtual force is proposed to converge rapidly in [11]. Li et al. proposed a sensor deployment optimization strategy based on target-involved virtual force algorithm (TIVFA) [12]. Kukunuru et al. proposed a virtual force-directed particle swarm optimization algorithm, combining particle swarm optimization algorithm with virtual force to reach at a better coverage rate [13].

Once the vector of force is determined, there are various attempts to map the force to moving strategies. Some made the moving vector in the next time slot directly proportional to the calculated force or its modification [9, 11], others use the force to generate acceleration to guide motion just as the physical world [23]. In this paper, we use the original physical meaning of the force and use the force calculated to produce acceleration on nodes.

3. The Van Der Waals Force Based Node Deployment Model

The total virtual force received by a sensor node may be the composition of various types of force, such as the force resulting from interaction among the nodes themselves, the friction force hindering the motion of sensor nodes, and the force exerted by the event of interest. It is worth noting that friction plays a critical role in the performance of a VFA. In [21], potential energy and kinetic energy are mutually convertible. In order to achieve the steady state of node deployment, friction is essential for consuming the potential and kinetic energy, thus stopping the motion of whole system. In this paper, the effect of environmental events in the region of interest is not taken into consideration, and the $F_{i} (t)$ used can be defined as the sum of two different components as follows:

\begin{matrix} F_{i} (t) = F_{i}^{e} (t) + F_{i}^{f} (t), \end{matrix}

(3)

where

F_{i}^{e} (t)

is the exchange forces among sensor nodes and

F_{i}^{f} (t)

denotes the friction force. In this paper, we take van der Waals force as the exchange force. In physical chemistry, the van der Waals force is the sum of the attractive or repulsive forces between molecules (or between parts of the same molecule) other than those due to covalent bonds or to the electrostatic interaction of ions with one another or with neutral molecules [10]. The term consists of force between two permanent dipoles (Keesom force) and force between a permanent dipole and a corresponding induced dipole (Debye force), force between two instantaneously induced dipoles (London dispersion force) [24].

The van der Waals force can be modeled as

\begin{matrix} F (d) = \frac{A}{d^{a}} - \frac{B}{d^{b}}, \end{matrix}

(4)

where d is the distance between two neighboring nodes and

a > b

. The force is the composition of two terms: the first term represents the repulsive force, and the second term denotes the attractive force. When

d < D_{m}

F (d)

appears to be repulsive; when

d > D_{m}

, it turns out to be attractive. In (4), only one formula is used to describe both forces; the key problem here is to choose appropriate values of a and b. After simulating with various values of a and b, we found that with larger a, the repulsive force plays a dominant role, and when b is larger, the maximum value of attractive force is smaller. After repeated simulations, we tested out that

A = B = 160

a = 4

, and

b = 3

are satisfactory for computer simulation. The illustration of applied force model is shown in Figure 1, from which we know that when the mutual distance is less than the horizontal ordinate of zero point (threshold), the force is repulsive. When the mutual distance is larger than the threshold value, the force turns out to be attractive.

Figure 1

The van der Waals force model used in this paper.

Since van der Waals force is the interaction only between adjacent molecules, we use Delaunay triangulation [9] here to determine the “adjacent relationship”. A Delaunay triangulation for a set P of points in a plane is a triangulation such that no point in P is inside the circumcircle of any triangle in it. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation [25]. If two nodes form a side of triangle together in Delaunay triangulation, then they are defined as adjacent nodes to each other. If two close nodes are not directly connected by a triangle side in the triangulation diagram, there must be some other nodes between them, so the in-between nodes will obstruct the force between these two nodes. And if there are many nodes in the same side of the current node, only some nearest nodes are considered to exert force. In conclusion, only adjacent nodes within the communication range of each other can exert force mutually.

Friction force is indispensable for the construction equilibrium configuration and for preventing chaotic motion of sensor nodes. In real life, static friction and viscous friction are two basic forms of friction forces. For a static sensor node to move, it needs to overcome the static friction, while the motion of a moving node will also be impeded by viscous friction proportional to the instant velocity of it. During the simulation of network deployment, the friction force must be set large enough to stabilize the whole system.

Although van der Waals force has been introduced into node deployment in [10], the vector of force results in moving speed directly in the next time slot, which is inconsistent with laws of motion in the physical world. In this paper, time is divided into slot sequence, and, in each time slot $d t$ , the motion of sensor nodes conforms to Newton's second law of motion in (5)

\begin{matrix} m \frac{d^{2} x_{i} (t)}{d t^{2}} = F_{i} (t), \end{matrix}

(5)

where m denotes the “virtual” mass of a sensor node,

x_{i} (t)

denotes its position in the coordinate, and

F_{i} (t)

denotes the total “virtual” force exerted to a sensor node. A second-order leap-frog scheme [26] is applied here for the numerical solution of differential equation.

4. Simulation Results and Analysis

In order to verify the effectiveness of the proposed approaches, some simulations are proceeded. Binary detection model is used here and the nodes are distributed random initially. First is the simulation for a regular indoor case, which means that there is bound at each side.

To begin with, we set the length of square room as 100 and the total number of sensor nodes 213. By referring to [8], we get that

\begin{matrix} D m^{2} = \frac{1}{ρ_{m} \sin 6 0^{°}} = \frac{2}{\sqrt{3} ρ_{m}} . \end{matrix}

(6)

So that the theoretical equilibrium distance $D_{m}$ between two nodes is 7.4. However, due to the edge effect of walls constraint, the actual $D_{m}$ for simulation is 8.1, which is the distance of two adjacent nodes when equilibrium state is reached. Then, the sensing range of sensor node r is $D_{m} / \sqrt{3} = 4.67$ , and the communication range is 14.7. The virtual mass does not play an important role here, and we set it to 1 to all the nodes for convenience. Then, through repeated computer simulation tests, we finally determine the coefficient friction force as 0.3.

4.1. Indoor Case

Figure 2 shows the results of node distribution at initial, 250, 500, and 750 steps, respectively. The red dots represent the positions of the nodes, and the blue circles indicate the sensing range of each node.

Figure 2

The distribution of the node at some step: (a) random initial; (b) after 250 steps; (c) after 500 steps; (d) after 750 steps.

Figure 3 gives the comparison of the coverage rate versus the steps of the proposed approach, the original VFA, and the algorithms proposed in [8, 10]. From this figure, we can find that after the node reaches stable distribution, the proposed algorithm has better coverage rate than the other three approaches. This priority results from the feature of van der Waals force model shown in Figure 1, which can be summarized as follows. (1)

When the distance between two adjacent nodes increases over $D_{m}$ , the magnitude of attractive force grows at first and then vanishes gradually to zero; when the mutual distance between two nodes decreases from $D_{m}$ , the magnitude of repulsive force grows and converges to a certain value. The magnitude of force is bounded. In comparison, however, the force model of algorithm in [8] is not bounded. The magnitude of force will be infinitely larger, when the mutual distance between two nodes equals zero or $R_{c}$ , in which cases of unreasonable large forces will be exerted on both nodes.

(2)

An equilibrium point or threshold is indispensable in a well-performed force model. The force exerted on a sensor node at equilibrium point should be zero. Moreover, the force function should be continuous. The proposed model meets all these requirements and gives rise to the desired deployment results. However, in the original VFA, the function of force model is discontinuous at threshold point, which could explain the incompact and unstable resultant network topology.

(3)

The slope of the curve in Figure 1 is large, when mutual distance falls near $D_{m}$ , which insures convergence of the process of node deployment. Comparatively, the slope of force curve in algorithm [8] and original VFA is much smaller than that in the proposed algorithm, which serves as the reason accounting for the better performance of the proposed algorithm, especially in the later stage of computer simulation (steps $> 400$ ).

Figure 3

Comparison of the coverage rate versus steps.

4.2. Outdoor Case

For indoor case, there is a bound on each side preventing sensor nodes from moving outside. In order to test the effectiveness of the proposed algorithm in more general case, another simulation for outdoor case is analyzed. All nodes are initially random, but there is no bound at each side. Figure 4 gives the initial and final distribution of the four algorithms mentioned above. The center is at (0, 0) instead to illustrate the off-centered degree effectively.

Figure 4

The initial random distribution (a) and the distribution of the node at step 1000 for different algorithms, (b) the proposed approach, (c) the algorithm in [8], (d) the original VFA, and (e) the algorithm in [10].

In indoor case, coverage rate is used as the metric to evaluate the performance of deployment, however, it is not effective in outdoor case anymore, since there is no boundary on any side; if we compare the coverage area under different algorithms, we can find that the one with the highest value must be the one in which all the blue circles in above figures are tangent to each other, which will leave many sensing holes and is not desired. So for outdoor case, new metric is introduced here.

Standard deviation is widely used as a metric for evaluating the uniformity of VFA. A smaller standard deviation value corresponds to a better deployment configuration. The average distance between two adjacent sensors and the standard deviation of mutual distance are listed in Table 1. From this table, we can find that the proposed algorithm is closer to perfect distribution in both average distance and standard deviation than others.

Table 1

Comparison of the average and standard deviation of the distance between two adjacent nodes.

Algorithm	Average distance	Standard deviation
Perfect distribution	8.1	0
Proposed algorithm	9.0859	1.3448
Algorithm in [8]	9.1232	1.7287
Original VFA	9.4950	1.7102
Algorithm in [10]	9.1104	1.5629

The deployment of sensor nodes under a well-performed force model should give rise to a network topology with good uniformity. Through repeated simulation, we find that a better uniformity means more resemblance to a perfect hexagon topology. Figure 5 illustrates the perfect hexagon deployment.

Figure 5

Perfect hexagon topology.

An evaluation metric called pair correlation function [27], which compare the similarity of the configuration of the node distribution with the perfect hexagon topology, is also introduced here to evaluate the uniformity of the final distribution of each algorithms, which is shown in Figure 6. From this figure, we can find that the pair correlation of the proposed approach is closer to the perfect hexagon than the other algorithms, which shows that it has better uniformity than the other three methods. The “peaks” in the curve of the proposed algorithm is corresponding with the “impulses” which depict the pair correlation function of perfect hexagon. In the curves of other algorithms, the correspondences are not that obvious. The reason for the better performance of proposed algorithm is similar as what we have explained in Section 4.1.

Figure 6

Comparison of the function pair correlation among different algorithms.

We also compare the running time of all algorithms; the simulation environment is a PC with CPU 2.1 GHz, 8 GB RAM and all simulation are run in Matlab 2012a. The elapse time for both indoor and outdoor is almost the same, and the time elapse of each algorithm for 1000 steps is list in Table 2. From this table, we can find that the proposed approach has moderate computational complexity compared to others. The reason why the time elapse of the algorithm in [10] is the shortest is that the amplitude of force calculated is mapped into moving distance directly instead of through Newton's formula. There are no intermediate variables of speed and acceleration.

Table 2

Time elapse comparisons.

Algorithm	Time elapse
The proposed	237 s
Original VFA	174.26 s
Algorithm in [8]	325.39 s
Algorithm in [10]	116.74 s

5. Conclusions

In this paper, a van der Waals force-based deployment algorithm is proposed to provide an opinion on node deployment in WSN. The relationship of adjacency of nodes is defined by Delaunay triangulation, and the force considering friction is calculated to produce acceleration for nodes to move. A new metric called pair correlation is introduced to evaluate the uniformity of the node distribution. Simulation results and comparisons have verified that the proposed approach has higher coverage rate, more uniformity in configuration, and faster convergence time than traditional VFAs. Irregular terrain, obstacles, and other associated issues will be considered in our further work.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported by the Foundation for Distinguished Young Talents in Higher Education Guangdong, China (Grant no. LYM10011), the National Natural Science Foundation of China (Grant no. 61201178), the Scientific Project of Guangdong (no. 2010B010600019), and, United Foundation Project of Guiyang University Guizhou (Grant no. QianKeHeJ-LKG $[2013]$ 36).

References

Zheng

Jamalipour

Wireless Sensor Networks: A Network Perspective 2009

Piscataway, NJ, USA

IEEE Press

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

Heo

Varshney

P. K.

A distributed self-spreading algorithm for mobile wireless sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference

2003

New Orleans, La, USA

1597 1602

Chen

Shen

Sun

The deployment algorithms in wireless sensor net works: a survey

Information Technology Journal 2009 8 3 293 301

2-s2.0-62749086433

10.3923/itj.2009.293.301

Younis

Akkaya

Strategies and techniques for node placement in wireless sensor networks: a survey

Ad Hoc Networks 2008 6 4 621 655

2-s2.0-39149099807

10.1016/j.adhoc.2007.05.003

Zou

Chakrabarty

Sensor deployment and target localization based on virtual forces

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '03)

April 2003

New York, NY, USA

1293 1303

2-s2.0-0042014539

Kribi

Minet

Laouiti

Redeploying mobile wireless sensor networks with virtual forces

Proceedings of the 2nd IFIP Wireless Days (WD '09)

December 2009

1 6

2-s2.0-77952647403

10.1109/WD.2009.5449665

Garetto

Gribaudo

Chiasserini

C.-F.

Leonardi

A distributed sensor relocation scheme for environmental control

Proceedings of the IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems (MASS '07)

October 2007

1 10

2-s2.0-50249104744

10.1109/MOBHOC.2007.4428663

Huang

Lan

Qian

A novel virtual force approach for node deployment in wireless sensor network

Proceedings of IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '12)

2012

Hangzhou, China

359 363

10.

Huang

Lan

Qian

A van der Waals force-like node deployment algorithm for wireless sensor network

Proceedings of the 8th International Conference on Mobile Ad-hoc and Sensor Networks

2012

Chengdu, China

218 221

11.

Chen

Sun

Novel deployment schemes for mobile sensor networks

Sensors 2007 7 11 2907 2919

2-s2.0-36849032166

12.

Pan

Sensor deployment optimization for detecting maneuvering targets

Proceedings of the 7th International Conference on Information Fusion (FUSION '05)

July 2005

Philadelphia, Pa, USA

1629 1635

2-s2.0-33847144209

10.1109/ICIF.2005.1592051

13.

Kukunuru

Thella

Davuluri

Sensor deployment using particle swarm optimization

International Journal of Engineering Science and Technology 2010 2 10 5395 5401

14.

Lei

Sensor node deployment in wireless sensor networks based on improved particle swarm optimization

Proceedings of the International Conference on Applied Superconductivity and Electromagnetic Devices (ASEMD '09)

September 2009

Chengdu, China

215 217

2-s2.0-70450265316

10.1109/ASEMD.2009.5306655

15.

Liao

W.-H.

Kao

Y.-S.

A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks

Expert Systems with Applications 2011 38 10 12180 12188

2-s2.0-79958004553

10.1016/j.eswa.2011.03.053

16.

Ozturk

Karaboga

Gorkemli

Artificial bee colony algorithm for dynamic deployment of wireless sensor networks

Turkish Journal of Electrical Engineering & Computer Sciences 2012 20 2 255 262

17.

Ozturk

Karaboga

Gorkemli

Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm

Sensors 2011 11 6 6056 6065

2-s2.0-79959828517

10.3390/s110606056

18.

Wang

Cao

La Porta

T. F.

Movement-assisted sensor deployment

IEEE Transactions on Mobile Computing 2006 5 6 640 652

2-s2.0-33646437020

10.1109/TMC.2006.80

19.

Wang

J.-J.

An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment

Sensors 2007 7 3 354 370

2-s2.0-34047170719

20.

Han

Kim

Jeong

An energy-efficient self-deployment with the centroid-directed virtual force in mobile sensor networks

Simulation 2012 88 10 1152 1165

21.

Howard

Mataric

M. J.

Sukhatme

G. S.

Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem

Proceedings of the 6th International Conference on Distributed Autonomous Robotic Systems

2002

Fukuoka, Japan

299 308

22.

Poduri

Sukhatme

G. S.

Constrained coverage for mobile sensor networks

Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '04)

May 2004

Los Angeles, Calif, USA

165 171

2-s2.0-3042582668

23.

Zhang

B. H.

Cui

L. G.

Chai

S. C.

An extended virtual force-based approach to distributed self-deployment in mobile sensor networks

International Journal of Distributed Sensor Networks 2012 2012 14

417307

10.1155/2012/417307

24.

Israelachvili

J. N.

Intermolecular and Surface Forces 2011 3rd

Academic Press

25.

O'Rourke

Computational Geometry in C 1998 2nd

New York, NY, USA

Cambridge University Press

26.

Birdsall

C. K.

Langdon

A. B.

Plasma Physics via Computer Simulations 1985

McGraw-Hill Book Company

27.

Hua

J.-J.

Liu

Y.-H.

M.-F.

Wang

Zhang

Z.-H.

Structural and dynamical analysis of a two-dimensional dusty plasma lattice

Chinese Physics Letters 2003 20 1 155 157

2-s2.0-0037251688

10.1088/0256-307X/20/1/346

A Node Deployment Algorithm Based on Van Der Waals Force in Wireless Sensor Networks

Abstract

1. Introduction

2. Virtual Force Based Node Deployment Algorithms

3. The Van Der Waals Force Based Node Deployment Model

4. Simulation Results and Analysis

4.1. Indoor Case

4.2. Outdoor Case

5. Conclusions

Footnotes

Conflict of Interests

Acknowledgments

References