An Extended Virtual Force-Based Approach to Distributed Self-Deployment in Mobile Sensor Networks

Abstract

Virtual physics based approach is one of the major solutions for self-deployment in mobile sensor networks with stochastic distribution of nodes. To overcome the connectivity maintenance and nodes stacking problems in the traditional virtual force algorithm (VFA), an extended virtual force-based approach is investigated to achieve the ideal deployment. In low- $R_{c}$ VFA, the orientation force is proposed to guarantee the continuous connectivity. While in high- $R_{c}$ VFA, a judgment of distance force between node and its faraway nodes is considered for preventing node stacking from nonplanar connectivity. Simulation results show that self-deployment by the proposed extended virtual force approach can effectively reach the ideal deployment in the mobile sensor networks with different ratio of communication range to sensing range. Furthermore, it gets better performance in coverage rate, distance uniformity, and connectivity uniformity than prior VFA.

1. Introduction

Wireless sensor networks can be deployed manually or spread randomly over the interested regions for practical applications [1–3]. However, in many working environments, such as remote harsh fields, disaster areas, and toxic gas regions, it is almost impossible to deploy sensors by human beings. In such case, deploying the sensor nodes randomly may not satisfy the requirement of precise placement. Sensor nodes may cluster for stacking in a small region or may distribute sparsely without connectivity guarantee.

A mobile sensor network is composed of a distributed collection of nodes, each of which has communication, sensing, computation, and locomotion capabilities. Mobility of sensor nodes allows more complex application scenarios. With locomotion capabilities, sensor nodes can adjust their positions after stochastic distribution, thus enhancing the coverage and reaching more precise placement.

Many efforts have been put on the algorithms of repositioning sensors in order to obtain a required placement and improve the coverage rate. Previous work on self-deployment issue of mobile sensor networks can be classified into two categories: virtual physics-based approach and computational geometry-based approach. In terms of virtual physics-based strategy [4–7], it models the mobile sensor nodes as the electrons or molecules, and nodes move toward or away each other by their virtual forces or potential fields. However, except the factor of oscillation moving, it does not consider any more crucial problems such as connectivity maintenance and topology control [8, 9]. According to the computational geometry-based approach [10–13], nodes adjust their positions in order to construct a uniform Voronoi diagram or Delaunay triangulation. Nevertheless, decentralized algorithm is too hard to realize because global position information of network should be provided in establishing the Voronoi diagram or Delaunay triangulation.

In this paper, the stability and formation of self-deployment by virtual physic based methods is analyzed. More precisely, the connectivity maintenance problem caused by few neighbors and nodes stacking problem by nonplanar connectivity graph in the existing VFA algorithms are discussed. This paper aims to solve the above problem by introducing an extended virtual force-based approach that can achieve the ideal deployment after self-deployment. The extended virtual force approach can be applied in the mobile sensor networks with different ratio value of communication range and sensing range. In low- $R_{c}$ VFA, the orientation force is proposed to guarantee the continuous connectivity. While in high- $R_{c}$ VFA, the judgment of distance force between node and its faraway nodes is adopted in order to prevent node stacking from nonplanar connectivity.

The rest of this paper is organized as follows. Section 2 summarizes the related work. Section 3 describes fundamental model of network, ideal deployment, and virtual force approach. In Section 4, the analysis of stability and formation of self-deployment in mobile sensor networks is given. Our proposed extended virtual force approach is introduced in Section 5. Simulation results that illustrate the performance are shown in Section 6. Finally, Section 7 concludes the paper.

2. Related Work

There exists prior works on self-deploying mobile sensor nodes in recent years. Specifically, those closely related to our filed are summarized below.

The concept of self-deployment in mobile sensor networks is derived from dealing with coordination in behavior control of many robots teams [14–16]. Gage [14] has investigated the use of robot swarms to provide blanket, barrier, or sweep coverage of area. According to this taxonomy, the deployment problem of this paper focuses on the blanket coverage. Simmons et al. [15] have calculated desired deployment locations by attempting to minimize overlap in information gain. Blach and Hybinette [16] have suggested the leverage of “attachment sites” that mimic the geometry of crystals. However, most of the behavior based control approaches are centralized and may not perform well on large-scale networks.

In self-deployment approaches, most of strategies are based on the virtual physics. Howard et al. [4] have presented a potential-field-based approach to spread sensor nodes in a target environment. Control force is defined as the negative gradient of the potential. This approach models robots as like electric charges in order to cause uniform deployment into an unknown enclosed area. VFA [5] works in a similar fashion with potential-field-based algorithm. It increases sensor coverage by considering the virtual attractive and repulsive forces exerted on each sensor node by neighbor nodes and obstacles. Heo and Varshney [6] have developed a distributed self-spreading algorithm (DSSA). The force models in DSSA are similar to internuclear repulsion and attraction between molecules. There are also some flaws in these virtual force based self-deployment algorithms. First, they have not considered the connectivity maintenance on the processing of adjusting positions. Moreover, all of these models use fully connected graphs or unit disk graph (UDG), there is a possibility that nonplanar graph may cause significant stacking of sensor nodes [8].

Improved virtual force algorithm (IVFA) and exponential virtual force algorithm (EVFA) [17] have improved traditional VFA to some extent. IVFA sets a maximum movement per iteration in order to prevent nodes from moving out of the region of interest, and incorporates an effective communications distance measure into the force equations to assist the wireless sensor network in reaching a steady state. EVFA provides an exponential force model so that achieve steady state more quickly in mobile sensor networks with a large communication range. However, discontinuous connectivity and coverage holes may appear in IVFA and EVFA because they only assume the effective communication distance is twice as long as the sensing range.

Connectivity-preserved virtual force (CPVF) scheme [18] considers the connectivity preserving by having disconnected sensors move toward the base station to establish connectivity. But CPVF does not conceal the drawback of stacking in large communication range. Self-deployment by density control (SDDC) is presented in [7]. In SDDC, virtual force is decided by density at a sensor node and obstacles. Although compact initial deployment can be spread out, and the stacking problem can be solved, it does not perform well in sparse initial distribution. Distributed robotic macrosensor (DRM) algorithm [8] by virtual spring force control eliminates stacking. The mesh is decidedly planar without intersection of edges by acute-angle test. Extend virtual spring mesh algorithms (EVSM) [19] extends the DRM algorithm with several enhancements such as exploration of unknown areas and obstacle avoidance. In fact, the topology by acute-angle test mesh is Gabriel Graph (GG). However, sensor nodes can only get information from its logical neighbor nodes through GG edges, the uniformity of GG is worse than regular hexagonal deployment structure. Lam and Liu [9] have proposed a self-deployment algorithm named ISOGRID. In ISOGRID, virtual force only exerts on each sensor node by its six closet neighbor nodes, and each node try to move to the vertex of its neighbor nodes' hexagonal placement structure. Though ISOGRID performs very well when the communication range $R_{c}$ is twice as long as the sensing range $R_{s}$ , it fails to avoid the stacking in large value of $R_{c} / R_{s}$ . Ion-6 [20] is a position unrelated self-deploying method. Ion-6 computes sensor nodes' moving directions and distances independently without a priori position information. However, each sensor has to install a precise antenna array according to this algorithm.

Another commonly used self-deployment approach relies on the use of computational geometry such as Voronoi diagram and Delaunay triangulation. Wang et al. [11] have presented three independent algorithms: the vector-based algorithm (VEC), the Voronoi-based algorithm (VOR), and MiniMax. These algorithms use Voronoi diagrams to partition the coverage field into many subareas and maximize the coverage via pushing or pulling nodes to cover the coverage gaps on virtual force. In computational geometry-based strategy, stacking can be limited. However, the Voronoi diagram is a global structure, in which all Voronoi vertices and cells can only be obtained when the global location information with all other nodes in the network is known.

3. Preliminaries

3.1. Network Model and Assumptions

This paper focuses on the self-deployment issue in 2-dimensional plane and leverages Euclidian plane $ℝ^{2}$ to model the coordinate system. Node's position is represented by its coordinate. The position of node i is described as $S_{i} (x_{i}, y_{i})$ . The distance between node i and node j is defined as Euclidean distance $d_{i j}$ . The initial deployment is a stochastic placement in unknown distribution. It assumes that each sensor node can learn its own exact position via GPS or other localization technology, and sensor node is capable of receiving its neighbors' message without losing data. At the same time, it can also calculate or measure the relative distances and orientations between them. The sensor node's communication and sensing models are modeled circular discs. All sensors have the identical communication range $R_{c}$ and sensing range $R_{s}$ , respectively. $R_{c}$ is larger than $R_{s}$ .

3.2. Ideal Deployment

The essential aim of self-deployment is to make the sensor nodes move from their original positions to new positions in order to form the ideal deployment layout. Optimal deployment patterns for k-coverage with l-connectivity maintenance have been studied [21–23]. Bai et al. [24] have improved k-coverage of mobile sensor networks using improve PSO algorithm. In this paper, we study the 1-coverage self-deployment problem. An ideal deployment grid structure for 1-coverage is show in Figure 1. Equilateral triangle grid (hexagonal placement structure) has the smallest overlapping area, hence this deployment requires the least number of sensors for area full coverage [25]. There is no coverage “hole” exists in an ideal deployment sensor network. The ideal distance $D_{th}$ between sensor node and its nearest neighbor should be $\sqrt{3} R_{s}$ , and the angle formed by one node and its two adjoined neighbors should be $π / 3$ [26]. If $R_{c} / R_{s} > 3$ , the distance between sensor node and its physical neighbors may be larger than $D_{th}$ .

Figure 1

Ideal deployment for full coverage.

3.3. Virtual Force-Based Approach

All of the virtual physics approaches for self-deployment are similar with the framework of virtual force, which combines the ideas of potential field with circle packing [4] by modeling the sensor node to be a particle in the potential field. The potential field exerts forces on the nodes nearby. For node i and j, it is useful to write the force as the negative gradient of the potential field. We can construct a potential function $V_{i j}$ . So the control input of a node is the force as

F_{i j} = - \nabla V_{i j} .

(1)

Sensor nodes move towards the required placement by these virtual forces. The force may be either attractive force or repulsive force. If two sensor nodes are placed closer than the threshold distance (ideal distance $D_{th}$ ), repulsive forces are exerted on each other. Alternatively, attractive forces are exerted if two sensor nodes are farther apart than the threshold distance. The attractive force is to keep a certain density of sensor nodes without coverage holes, and the repulsive force is to make sensors sparse enough without too much redundant coverage.

The law of updating position exploits either step method by iteration [17] or sampling time method [8, 19]. Normally, both of these methods will achieve the same results. In this paper, we choose sampling time method for analyzing. The control law for each sensor node is

{\ddot{x}}_{i} = \sum_{j \in G_{i}}^{} F_{i j} - k_{d} {\dot{x}}_{i},

(2)

where

{\ddot{x}}_{i}

is node's acceleration,

{\dot{x}}_{i}

is node's velocity,

G_{i}

is the set of node's neighbors (in original VFA,

G_{i}

is the set of all nodes except i),

k_{d}

is the positive damping coefficient.

According to the traditional VFA, the force law is given as follows:

\vec{F_{i j}} = {\begin{cases} (ω_{A} (d_{i j} - D_{th}), α_{i j}), & if d_{i j} > D_{th}, \\ 0, & if d_{i j} = D_{th}, \\ (ω_{R} d_{i j}^{- 1}, α_{i j} + π), & if d_{i j} < D_{th}, \end{cases}

(3)

where

ω_{A}

and

ω_{R}

represent the virtual force attractive and repulsive coefficients, respectively. And

d_{i j}

is the Euclidean distance between sensor nodes i and j,

α_{i j}

is the orientation of the line segment from nodes i to j.

The sensor moves to its new position under the control law in (2). The total force $F_{i}$ exerted on node i is decided by the summation of all forces contributed by its all neighbors:

F_{i} = \sum_{j \in G_{i}}^{} F_{i j} .

(4)

4. Analysis of Virtual Physics-Based Approach for Self-Deployment

4.1. Stability Analysis

Although small oscillation can be observed in the processing of self-deployment under virtual physics-based approach, all nodes will stop moving finally. In fact, there is always damping effect acting against the motion of each sensor node. It causes the reduction in kinetic energy. Potential energy is conservative because the drive force is defined as the negative gradient of it. Thus, the total energy cannot be increased, and kinetic energy must eventually approach to 0. We can proof the stability with Lyapunov stability theory.

Theorem 1.

In virtual force-based approach for self-deployment, any node will eventually converge to a steady state.

Proof.

Let $x_{i}$ be the position vector of node i. The control input of a node is the force $\vec{F_{i j}}$ exerted on node i by node j. The virtual potential field is constructed as $V_{i j}$ . From (1) and (4), we obtain the total force from each node which can be described as

F_{i} = \sum_{j \in G_{i}}^{} F_{i j} = \sum_{j \in G_{i}}^{} - \nabla V_{i j} .

(5)

Formally, we consider the following energy function (

Φ

) that combines kinetic energy with potential energy as Lyapunov function:

Φ = \sum_{i = 1}^{N} \frac{1}{2} {\dot{x}}_{i}^{T} {\dot{x}}_{i} + \frac{1}{2} \sum_{i = 1}^{N} \sum_{j \in G_{i}}^{} V_{i j} .

(6)

Because of the symmetry of

V_{i j}

and

V_{j i}

, and

{\dot{x}}_{i} = - {\dot{x}}_{j}

on the orientation from node i to j. We get the time derivative of

V_{i j}

as follows:

\begin{matrix} \frac{d}{d t} V_{i j} & = \frac{\partial V_{i j}}{\partial x_{i}} \cdot \frac{d x_{i}}{d t} + \frac{\partial V_{i j}}{\partial x_{j}} \cdot \frac{d x_{j}}{d t} \\ = \nabla V_{i j} \cdot {\dot{x}}_{i} - \nabla V_{i j} \cdot {\dot{x}}_{j} \\ = \nabla V_{i j} \cdot ({\dot{x}}_{i} - {\dot{x}}_{j}) \\ = 2 \nabla V_{i j} \cdot {\dot{x}}_{i} . \end{matrix}

(7)

So the derivative of the energy function

Φ

is transferred into:

\begin{matrix} \dot{Φ} & = \sum_{i = 1}^{N} \frac{1}{2} ({\dot{x}}_{i}^{T} {\ddot{x}}_{i} + {\ddot{x}}_{i}^{T} {\dot{x}}_{i}) + \sum_{i = 1}^{N} \sum_{j \in G_{i}}^{} \nabla V_{i j} {\dot{x}}_{i}^{T} \\ = \sum_{i = 1}^{N} {\dot{x}}_{i}^{T} ({\ddot{x}}_{i} + \sum_{j \in G_{i}}^{} \nabla V_{i j}) . \end{matrix}

(8)

According to (2), (8) can be processed as follows:

\begin{matrix} \dot{Φ} & = \sum_{i = 1}^{N} {\dot{x}}_{i}^{T} ({\ddot{x}}_{i} + \sum_{j \in G_{i}}^{} \nabla V_{i j}) \\ = \sum_{i = 1}^{N} {\dot{x}}_{i}^{T} (\sum_{j \in G_{i}}^{} F_{i j} - k_{d} {\dot{x}}_{i} + \sum_{j \in G_{i}}^{} \nabla V_{i j}) \\ = \sum_{i = 1}^{N} {\dot{x}}_{i}^{T} (\sum_{j \in G_{i}}^{} - \nabla V_{i j} - k_{d} {\dot{x}}_{i} + \sum_{j \in G_{i}}^{} \nabla V_{i j}) \\ = - k_{d} \sum_{i = 1}^{N} {\dot{x}}_{i}^{T} {\dot{x}}_{i} . \end{matrix}

(9)

For the positive damping coefficient

k_{d}

\dot{Φ}

is the seminegative definite. Therefore, according to Lyapunov stability theory, the system with virtual force input control law is asymptotically stable. Equality

\dot{Φ} = 0

only when

{\dot{x}}_{i} = 0

. So any node will eventually converge to a stationary state.

Figure 2 shows the variations of coordinate for movement from self-deployment by 3 nodes with initial positions of $S_{1}$ (50, 55), $S_{2}$ (55, 58), and $S_{3}$ (45, 60). From the graph, it can be seen that each sensor node could eventually converge to a steady state within 1 minute.

Figure 2

Convergence of VFA for 3 nodes with sensing range 10 m.

Note that the domain of the Lyapunov function $Φ$ is not the positions x, but the velocities $\dot{x}$ of mobile sensor node. Although every node may reach a stable state, it does not mean that the mobile sensor network can achieve the ideal deployment. It is possible for some potential energy to exist even in a static state. We will further discuss it in Section 4.2.

4.2. Formation Analysis

The goal of self-deployment is to make the formation of placement as the ideal equilateral triangle grid. However, Chen et al. [17] and Shucker and Bennett [8] have noticed that attractive force always exists whenever the distance between two sensors is larger than threshold $D_{th}$ by some examples. So VFA cannot always guarantee that the distance between sensors is reached at threshold $D_{th}$ . Moreover, VFA shows significant stacking of nodes in full-connectivity graph or nonplanar connectivity graph. Here, we analyze the drawbacks of VFA.

Theorem 2.

In mobile sensor networks with ideal deployment, all virtual forces exerted on any pair of nodes are equal to 0.

Proof.

From Section 3.2, we know that the distance between each pair of nodes is larger than or equal to $D_{th}$ in an ideal deployment. Therefore, every force exerted on each pair of nodes is either 0 or attractive force. An ideal deployment is a stable deployment, and the total virtual force from neighbors of each node is equal to 0.

We assume there are N sensor nodes in the network topology graph, and there are $M (M ⩾ 1)$ virtual attractive forces across M connectivity edges $E (i, j)$ , while other forces equal to 0.

For $\forall E (a, b) \in E (i, j) > D_{th}$ , the force through the edge $E (a, b)$ is toward each other for node a and node b. We consider $\vec{a b}$ as the orientation of x-axis and the position of node a as the coordinate origin. Then we build the Cartesian coordinate system, as shown in Figure 3.

We suppose there are $P_{a}$ neighbors on the left half plane of node a, while $Q_{a}$ neighbors on the right half plane. As the total forces on a static node is 0, the sum of virtual forces of node a is

\vec{F_{a}} = \vec{F_{a b}} + \sum_{i = 1}^{P_{a}} \vec{F_{a i}} + \sum_{j = 1}^{Q_{a}} \vec{F_{a j}} = 0 .

(10)

For each neighbor node of a, the force on

\vec{a b}

\begin{matrix} \vec{F_{a (\vec{a b})}} & = \vec{F_{a b}} + \sum_{i = 1}^{P_{a}} (| \vec{F_{a i}} | \cos ∠ i a b) u_{a b} \\ + \sum_{j = 1}^{Q_{a}} (| \vec{F_{a j}} | \cos ∠ j a b) u_{a b} = 0, \end{matrix}

(11)

where

u_{a b}

is the unit vector from node a to node b. If

P_{a} = 0

\cos ∠ j a b \geq 0

, so

F_{a (\vec{a b})} = | \vec{F_{a b}} | + \sum_{j = 1}^{Q_{a}} | \vec{F_{a j}} | \cos ∠ j a b > 0 .

(12)

It is unstable. So, there are $P_{a} (P_{a} ⩾ 1)$ neighbor nodes on the left half plane of node a, and these $P_{a}$ nodes satisfing their x-coordinates are negative. We define node a as the top node, and these $P_{a}$ nodes as level 1 nodes.

As shown in Figure 3, in order to achieve the stable state of these $P_{a}$ nodes, for the same analysis on node a, there are $P_{1} (P_{1} ⩾ P_{a})$ level 2 neighbor nodes on the left half plane of these $p_{1}$ nodes. For the same reason, there are $P_{N - 1} (P_{N - 1} ⩾ P_{N - 2})$ level N neighbor nodes on the left half plane of $P_{N - 2}$ level $N - 1$ nodes. So, in order to keep the equilibrium of force on orientation $\vec{a b}$ , the number of nodes we need is at least:

2 + P_{a} + P_{1} + P_{2} + \dots + P_{N - 1} + \dots \geq 2 + P_{a} N > N .

(13)

It is obvious that the network cannot reach the ideal deployment if there exists attractive force. Therefore, we conclude that all of the virtual forces across connectivity edges in the topology graph for ideal deployment are equal to 0.

Figure 3

Virtual force for each node should equal to 0.

Lemma 3.

If the connectivity graph of mobile sensor network is nonplanar, the network deployment cannot reach the ideal deployment.

Proof.

Figure 4 shows a nonplanar connectivity graph of sensor nodes ${a, b, c, d}$ with two intersections of connectivity edges $E (a, c)$ and $E (b, d)$ .

From Theorem 1, in an ideal deployment, all the connectivity graph edges should equal to ideal distance $D_{th}$ .

So $a c = b d = D_{th}$ . For quadrilateral abcd, there is at least one angle larger than or equal to $π / 2$ . In right-angled triangle or obtuse-angled triangle, the other two edges of triangle are shorter than the longest angle's diagonal whose length is $D_{th}$ . However, in Section 3.2 we know that in an ideal deployment, the distance between each pair of two nodes is larger than or equal to $D_{th}$ .

Thus, the network deployment cannot reach the ideal deployment if there is (are) intersection(s) of edges in connectivity graph.

Figure 4

Nonplanar connectivity graph.

As shown in Figure 5, the connectivity graph of four nodes is nonplanar. Self-deployment by traditional VFA cannot reach the ideal deployment. In fact, the nonplanar graph exhibits more significant stacking under self-deployment if there are more intersections of connectivity edge. So in mobile sensor networks with a large value of $R_{c} / R_{s}$ , compact deployment will be reached after self-deployment via VFA. Some algorithms assume the communication range $R_{c}$ is twice as long as the sensing range $R_{s}$ in order to decrease the intersections of connectivity edges [9, 17]. However, it may cause coverage hole suffer from discontinuous connectivity. Even if the planar connectivity graph such as MST, GG, RNG, and TDG can be used in avoiding the intersections [8, 19], they cannot guarantee the logical neighbor for each node is 6 for construct the hexagonal formation.

Figure 5

Nonplanar connectivity graph cannot reach ideal deployment.

In the following sections, we will make some improvements on virtual physics-based approach in order to solve the above-mentioned problems.

5. Extended Virtual Force Approach for Mobile Sensor Networks

The extended virtual force algorithm is a self-deployment scheme with some novel features which can overcome the drawbacks of traditional VFA. In mobile sensor networks with small value of $R_{c} / R_{s}$ , the stacking problem caused by nonplanar connectivity graph is not serious. Thus, connectivity maintenance should be more important than stacking avoidance. In this paper, the algorithm is defined as low- $R_{c}$ VFA. On the other hand, in mobile sensor networks with large value of $R_{c} / R_{s}$ , the stacking problem caused by nonplanar connectivity graph is quite obvious. The algorithm should eliminate the sensor nodes' stacking. We define the algorithm as high- $R_{c}$ VFA.

5.1. Low- $R_{c}$ VFA

As shown in Figure 1, under the ideal deployment, the nonplanar connectivity graph can be formed, when $R_{c} / R_{s}$ is larger than 3. So in this paper, we consider the mobile sensor network as a low- $R_{c}$ network, while the value of $R_{c} / R_{s}$ is equal to or smaller than 2.5. In low- $R_{c}$ VFA, distance force pushes nodes away from neighbors if their distances are less than $D_{th}$ while moves nodes towards to neighbors if their distances are larger than $D_{th}$ , and orientation force is added to improve the force model in order to keep the continuous connectivity. Chen et al. [17] have shown that exponential force model can achieve fast convergence. The distance force model is shown in (14) and Figure 6(a):

\vec{F_{i j (d)}} = {\begin{cases} α ({d_{i j}}^{- β} - {D_{th}}^{- β}) u_{i j}, & if D_{th} < d_{i j} \leq R_{c}, \\ 0, & if d_{i j} = D_{th}, \\ | α ({d_{i j}}^{- β} - {D_{th}}^{- β}) | u_{j i}, & if 0.5 D_{th} < d_{i j} < D_{th}, \\ 1 u_{j i}, & if d_{i j} \leq 0.5 D_{th}, \end{cases}

(14)

where

u_{i j}

is the unit vector from node i to node j, α and β are constants which can be adjusted according to different situations. Normally, the value of α is equal to

0.25 {D_{th}}^{2}

, while β is equal to 2. For pair of nodes which distance is less than

0.5 D_{th}

, the limit magnitude of virtual force exerted on them is set as 1 in order to avoid the high acceleration and velocity by the control input saturation.

Figure 6

Force models.

The distance force can reduce the connectivity degree to be less than or equal to 6 if the initial connectivity degree is larger than 6. The orientation forces are only exerted on the nodes whose neighbors are less than 6. The aim of orientation force is tried to keep the angle formed by one node and its two adjoined neighbors equal to $π / 3$ . Then mobile sensor networks will reach reliable connectivity and eliminate coverage holes caused by continuous connectivity. For node i with connectivity degree m ranging from 2 to 6, we calculate all angles between node i and its two adjoining neighbors as $S (θ) = {θ (i, j, p)}$ . The orientation force model is

\vec{F_{i j (o)}} = {\begin{cases} ω_{o} (θ (i, j, j_{c}) - \frac{π}{3}) u_{j j_{c}}, \\ if θ (i, j, j_{ac}) is the largest angle, \\ ω_{o} (θ (i, j, j_{ac}) - \frac{π}{3}) u_{j j_{ac}}, \\ if θ (i, j, j_{c}) is the largest angle, \\ ω_{o} {| (θ (i, j, j_{c}) - \frac{π}{3}) | u_{j j_{c}} \\ + | (θ (i, j, j_{ac}) - \frac{π}{3}) | u_{j j_{ac}}}, \\ otherwise, \end{cases}

(15)

where node

j_{c}

is the neighbor of node i on the clockwise orientation under node j, and

j_{ac}

is the neighbor on the anticlockwise orientation.

Then, in low- $R_{c}$ VFA, the force exerted on a node can be calculated by

\vec{F_{i j}} = {\begin{cases} \vec{F_{i j (d)}}, & if m > 6 or m = 1, \\ \vec{F_{i j (d)}} + \sum_{j \in G_{i}}^{} \vec{F_{j i (o)}}, & if 2 \leq m \leq 6 . \end{cases}

(16)

5.2. High- $R_{c}$ VFA

We consider the mobile sensor network as a high- $R_{c}$ networks if the $R_{c} / R_{s}$ is larger than 2.5. In high- $R_{c}$ VFA, connectivity maintenance can be guaranteed. Thus, only distance forces are exerted among the nodes and their neighbors. We obtain the virtual force model in high- $R_{c}$ VFA as follows:

\vec{F_{i j}} = {\begin{cases} α {d_{i j}}^{- β} u_{i j}, & if D_{th} > 2.5 R_{s}, \\ α ({d_{i j}}^{- β} - {D_{th}}^{- β}) u_{i j}, & if D_{th} < d_{i j} \leq 2.5 R_{s}, \\ 0, & if d_{i j} = D_{th} or d_{i j} > R_{c}, \\ | α ({d_{i j}}^{- β} - {D_{th}}^{- β}) | u_{j i}, & if 0.5 D_{th} < d_{i j} < D_{th}, \\ 1 u_{j i}, & if d_{i j} \leq 0.5 D_{th} . \end{cases}

(17)

In high- $R_{c}$ VFA, virtual force varies exponentially with distance between each pair of mobile sensor nodes. As shown in (17) and Figure 6(b), the virtual forces between node and its faraway neighbors are decreasing with the farther distance. This feature can diminish nodes stacking effectively.

There always exist virtual attractive forces between nodes and its faraway neighbors in the traditional VFA. Therefore, stacking possibly occurs in high- $R_{c}$ mobile sensor networks. In high- $R_{c}$ VFA, besides the exponential force model, we consider a judgment of distance force between node and its faraway nodes to prevent node stacking from nonplanar connectivity. The scheme of judgment is described as Algorithm 1.

Algorithm 1: The scheme of virtual force between node i and its neighbor nodes.

$G_{i}$ : the set of neighbors of node i satisfy $d_{i j} \leq R_{c}$ ;

$S_{i}$ : the set of neighbors of node i satisfy $d_{i j} < D_{th}$ ;

$N_{i}$ : the number of nodes belongs to $G_{i}$ ;

$n_{i}$ : the number of nodes belongs to $S_{i}$ ;

(1) for $1 \leq j \leq N_{i}$

(2) if $d_{i j} \leq D_{th}$

(3) $\vec{F_{i j}}$ is calculated by (17)

(4) end if

(5) if $d_{i j} > D_{th}$

(6) Find the neighbors which belong to both $S_{i}$ and $G_{j}$ . m is the number of

nodes satisfy $d_{j m} < R_{c}$ and belong to $S_{i}$ ;

(7) if $m < 2$

(8) $\vec{F_{i j}} = 0$

(9) end if

(10) if $m \geq 2$

(11) Compute the angle θ formed by node i, $j_{c}$ , and $j_{ac}$ , where $\vec{{i j}_{c}}$ is on the

clockwise side of $\vec{i j}$ , while $\vec{i j_{ac}}$ is on the anti-clockwise side. Node $j_{c}$ , and $j_{ac}$

belongs to $S_{i}$ and $G_{j}$ .

(12) if $θ \leq π / 3$ and there are not any nodes located in quadrilateral $i j$ $j_{c}$ $j_{a c}$

(13) $\vec{F_{i j}} = 0$

(14) else

(15) $\vec{F_{i j}}$ is calculated by (17)

(16) end if

(17) end if

(18) end if

(19) end for

As shown in Figure 7, $d_{14} > D_{th}$ . $∠ 213 < π / 3$ in (a), while $∠ 213 > π / 3$ in (b). Node 2 and node 3 are the neighbors of node 1, where $d_{1 j} < D_{th}$ , and also are the neighbors of node 4, where $d_{4 j} \leq R_{c}$ . According to Algorithm 1, $\vec{F_{14}} = 0$ in the deployment of (a), while $\vec{F_{14}}$ in (b) can be calculated by (17). And in Figure 7(c), node 5 is located in quadrilateral 1234, so $\vec{F_{14}} = 0$ in this deployment.

Figure 7

Virtual force between node and its faraway node.

Both in low- $R_{c}$ VFA and high- $R_{c}$ VFA, the total force exerted on node i is decided by adding all forces contributed by its neighbors as (4). Each node is driven for moving by the control law in (2).

5.3. Performance Evaluation

5.3.1. Coverage Rate

The coverage rate is a measure of the coverage quality for sensor networks. It was originally introduced by Gage [14]. In blanket coverage problem, coverage is defined by the ratio of the union of covered areas of each node to the complete area of interest. In this paper, the covered area of each node is defined as the circular area with sensing range $R_{s}$ . The value of coverage rate C is as

C = \frac{⋃_{i = 1}^{n} A_{i}}{A},

(18)

where

A_{i}

is the area covered by the node i, n is the total number of mobile sensor nodes, and A is the total area of ROI.

5.3.2. Uniformity of Distance

Under the ideal deployment of sensor nodes, the formation effectiveness of a deployment can be measured by distance uniformity and connectivity uniformity. Distance uniformity is defined as the average of the local standard deviation of the distances between neighboring nodes [6]:

\begin{matrix} U_{d} & = \frac{1}{n} \sum_{i = 1}^{n} U_{d i}, \\ U_{d i} & = {(\frac{1}{n_{i}} \sum_{j \in G_{i}}^{n} {(d_{i j} - D_{th})}^{2})}^{1 / 2}, \end{matrix}

(19)

where

U_{d i}

is the local distance uniformity,

G_{i}

is the set of node's neighbors, and

n_{i}

is the number of neighbors for node i. However, (19) is inappropriate for showing the uniformity in nonplanar connectivity graph. Here, we define

U_{i}

U_{d i} = {(\frac{1}{n_{i}} \sum_{j \in (G_{i}, d (i, j) < 2.5 R_{s})}^{n} {(d_{i j} - D_{th})}^{2})}^{1 / 2} .

(20)

5.3.3. Uniformity of Connectivity

Under the ideal deployment of sensor nodes, each node has the same number of neighbors except the boundary nodes. Uniformity of connectivity is defined as:

U_{c} = {(\frac{1}{n} \sum_{i = 1}^{n} {(C N_{i} - C N_{th})}^{2})}^{1 / 2},

(21)

where

C N_{i}

is the number of neighbors for node i, where

d_{i j} \leq 2.5 R_{s}

, and

C N_{th}

is the ideal number of neighbors. Particularly,

C N_{th}

is equal to 6 in this paper.

6. Simulation Results

In this section, we present simulation results for the extended virtual force approach including low- $R_{c}$ VFA and high- $R_{c}$ VFA.

6.1. Performance of Low- $R_{c}$ VFA

Figure 8 shows the self-deployment results from stochastic initial distribution of 20 mobile sensor nodes in a $100 m \times 100 m$ area. In this simulation, the communication range is 25 m, while the sensing range is 10 m. The sampling time is 0.1 sec, and the damping coefficient $k_{d}$ is 0.5. Figure 8(a) is the initial deployment and its unit disk graph (UDG). Figure 8(b) shows the self-deployment result by VFA. The final deployment is compressed because the nonplanar connectivity graph. In Figure 8(c), IVFA shows the better result than VFA for avoiding node stacking caused by intersection of connectivity edges. However, the continuous connectivity is not perfect because of significant coverage holes in IVFA. Self-deployment by low- $R_{c}$ VFA is shown in Figure 8(d). We can see that an ideal deployment is achieved.

Figure 8

Self-deployment results in $R_{c} / R_{s} = 2.5$ .

Figure 9 shows the performance comparison of coverage rate among VFA, IVFA, and low- $R_{c}$ VFA. IVFA can reach the highest coverage because the discontinuous connectivity. For the stacking of nodes, VFA cannot guarantee the enhancement of the coverage rate. All three of these algorithms have achieved a convergence state in about 30 sec. Moreover, the performance comparison of distance uniformity among VFA, IVFA, and low- $R_{c}$ VFA is shown in Figure 10. It is noticed that after self-deployment with 60 s, the distance uniformity of VFA, IVFA, and low- $R_{c}$ VFA are 3.01, 1.42, and 0.13 respectively. The performance of distance uniformity shows that low- $R_{c}$ VFA has reached the most regular ideal deployment.

Figure 9

Coverage rate comparison among VFA, IVFA, and low- $R_{c}$ VFA.

Figure 10

Uniformity comparison among VFA, IVFA, and low- $R_{c}$ VFA.

6.2. Performance of High- $R_{c}$ VFA

Figure 11 shows the self-deployment from stochastic initial distribution in Figure 8(a), when $R_{c} / R_{s}$ is equal to 4. In this simulation, the communication range is 40 m, while the sensing range is 10 m. The sampling time is 0.1 sec, and the damping coefficient $k_{d}$ is 0.5. Here we investigate self-deployment results under VFA, Gabriel Graph (GG, same as acute-angle test mesh in [8]) and high- $R_{c}$ VFA.

Figure 11

Self-deployment results in $R_{c} / R_{s} = 4$ .

Figure 11(a) is the initial deployment and its unit disk graph (UDG). It can be seen that more intersections of connectivity edges have been found compared to the network in Figure 8(a) due to the larger $R_{c}$ . In Figure 11(b), a fully connectivity graph and conspicuous nodes stacking are shown in self-deployment results by VFA. Self-deployment by GG mesh has obtained a result without stacking. Figure 11(c) shows the GG mesh graph after self-deployment. Although GG is a planar graph, it does not guarantee the hexagonal formation. Self-deployment by high- $R_{c}$ VFA is shown in Figure 11(d). Clearly, it shows that a regular ideal deployment has been attained in this circumstance.

In order to demonstrate self-deployment of large-scale mobile sensor networks, 100 mobile nodes are randomly placed for a concentrated deployment, as shown in Figure 12(a). The communication range is 40 m, while the sensing range is 10 m. The sampling time is 0.1 sec, and the damping coefficient $k_{d}$ is 0.5. The simulation result of self-deployment by high- $R_{c}$ VFA is shown in Figure 12(b). The number of iterations is 6000 (10 minutes). It is obvious that an asymptotically ideal deployment has been reached.

Figure 12

Self-deployment in large-scale concentrated deployment.

The impact of network size on self-deployment is shown in Figure 13. Figure 13(a) shows the change of distance uniformity with different nodes' numbers. In both IVFA and GG, distance uniformity deteriorates as the number of nodes is increased, while high- $R_{c}$ VFA provides almost constant uniformity. And we can also observe that high- $R_{c}$ VFA obtains the best performance uniformity from Figure 13(b).

Figure 13

Impact of nodes' number under IVFA, GG, and high- $R_{c}$ VFA.

6.3. Impact of Control Coefficients

The control coefficients influence the algorithm's performance. In the proposed extended virtual force-based approach, we focus on the sampling time and damping coefficient in this section. Equation (2) models the movement of self-deployment as a continuous system. Therefore, more accurate control can be obtained, when the sampling time becomes shorter. Figure 14(a) shows the distance uniformity comparison of different sampling time under high- $R_{c}$ VFA. It can be seen that uniformity oscillation is obvious, when sampling time is 1 sec, while convergence state and low uniformity are shown when the sampling time is 0.1 sec and 0.01 sec. However, a short sampling time needs lots of communication cost, and it also requires the process time should be shorter than sampling time. These requirements may be limited by the hardware of sensor nodes. So, 0.1 sec is a reasonable sampling time in this paper.

Figure 14

Impact of control coefficients and the nodes' number.

The damping coefficient also strongly influences self-deployment. Shucker and Bennett [8] has shown that convergence time increases when the damping coefficient is higher. We conduct simulations with damping coefficient of 0.3, 0.5, and 1 in this paper. As shown in Figure 14(b), the lower damping coefficient takes a faster moving at the beginning of self-deployment. However, it gets a higher value of distance uniformity with oscillation. It means that we should choose a higher damping coefficient to reach the more regular formation. Thus, we consider damping coefficient varying from 0.5 to 1 is reasonable value.

7. Conclusions

In this paper, we analyze the stability and formation of self-deployment with virtual physics-based methods. We argue the connectivity maintenance and nodes stacking problems of the existing VFA algorithms. To solve these problems, we proposed an extended virtual force-based approach which can achieve the ideal deployment under self-deployment and can be applied into networks with the different ratio of communication range to sensing range. In low- $R_{c}$ VFA, the orientation force is introduced to guarantee the continuous connectivity. While in high- $R_{c}$ VFA, we propose the judgment of distance force between node and its faraway nodes in order to prevent node stacking from nonplanar connectivity.

Simulation results confirm the efficiency of the proposed extended virtual force approach in coverage rate, distance uniformity, and connectivity uniformity, respectively. In low- $R_{c}$ mobile sensor networks, ideal deployment with continuous connectivity is achieved under low- $R_{c}$ VFA. Regular ideal deployment can be obtained in high- $R_{c}$ mobile sensor networks by high- $R_{c}$ VFA, though the connectivity graph is nonplanar. Future work involves testing the extended virtual force approach in heterogeneous mobile sensor networks with unequal communication (sensing) range and studying k-coverage requirement.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant no. 61104086), the National Defense Advanced Research Project of China (Grants nos. 104080, 40405020401), and Excellent Young Scholars Research Fund of Beijing Institute of Technology (Grant no. 2011CX04031).

References

Mainwaring

Polastre

Szewczyk

Culler

Anderson

Wireless sensor networks for habitat monitoring

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications

September 2002

88 97

2-s2.0-0036986465

Tsai

Y. R.

Tsai

Y. J.

Sub-optimal step-by-step node deployment algorithm for user localization in wireless sensor networks

2008 IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC ′08)

June 2008

114 121

2-s2.0-50949100876

10.1109/SUTC.2008.33

Meguerdichian

Koushanfar

Potkonjak

Srivastava

M. B.

Coverage problems in wireless ad-hoc sensor network

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′01)

April 2001

1380 1387

Howard

Mataric

M. J.

Sukhatme

G. S.

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

Distributed Autonomous Robotic Systems 2002

Springer

299 308

Zou

Chakrabarty

Sensor deployment and target localization based on virtual forces

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′03)

2003

1293 1303

Heo

Varshney

P. K.

Energy-efficient deployment of intelligent mobile sensor networks

IEEE Transactions on Systems, Man, and Cybernetics A 2005 35 1 78 92

2-s2.0-11844258234

10.1109/TSMCA.2004.838486

Chang

R. S.

Wang

S. H.

Self-deployment by density control in sensor networks

IEEE Transactions on Vehicular Technology 2008 57 3 1745 1755

2-s2.0-44849127666

10.1109/TVT.2007.907279

Shucker

Bennett

Virtual spring mesh algorithms for control of distributed robotic macorsensors

2005 CU-CS-996-05

Boulder, Colo, USA

University of Colorado

Lam

M. L.

Liu

Y. H.

ISOGRID: an efficient algorithm for coverage enhancement in mobile sensor networks

Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS ′06)

October 2006

1458 1463

2-s2.0-34250634381

10.1109/IROS.2006.281971

10.

Cǎrbunar

Grama

Vitek

Cǎrbunar

Redundancy and coverage detection in sensor networks

ACM Transactions on Sensor Networks 2006 2 1 94 128

2-s2.0-33745257022

10.1145/1138127.1138131

11.

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

12.

C. H.

Lee

K. C.

Chung

Y. C.

A Delaunay Triangulation based method for wireless sensor network deployment

Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS ′06)

July 2006

253 260

2-s2.0-34047208114

10.1109/ICPADS.2006.11

13.

Kamil

Y. I.

Manikas

Wireless array based sensor relocation in mobile sensor networks

Proceeding of the 5th ACM International Wireless Communications and Mobile Computing Conference (IWCMC ′09)

June 2009

832 838

2-s2.0-70450277329

10.1145/1582379.1582560

14.

Gage

D. W.

Command control for many-robot systems

Proceedings of the 19th Annual AUVS Technical Symposium

June 1992

15.

Simmons

Apfelbaum

Brugard

Fox

Moors

Thrum

Younes

Coordination for multi-robot exploration and mapping

Proceedings of the 7th National Conference on Artificial Intelligence

2000

16.

Balch

Hybinette

Behavior-based coordination of large-scale robot formations

Proceedings of the 4th International Conference on Multiagent Systems

July 2000

363 364

17.

Chen

Sun

Novel deployment schemes for mobile sensor networks

Sensors 2007 7 11 2907 2919

2-s2.0-36849032166

18.

Tan

Jarvis

S. A.

Kermarrec

A. M.

Connectivity-guaranteed and obstacle-adaptive deployment schemes for mobile sensor networks

IEEE Transactions on Mobile Computing 2009 8 6 836 848

2-s2.0-65349140735

10.1109/TMC.2009.31

4770105

19.

Derr

Manic

Extended virtual spring mesh (EVSM): the distributed self-organizing mobile ad hoc network for area exploration

IEEE Transactions on Industrial Electronics 2011 58 12 5424 5436

20.

Huang

S.-C.

Ion-6: a positionless self-deploying method for wireless sensor networks

International Journal of Distributed Sensor Networks 2012 2012 10

10.1155/2012/940920

940920

21.

Miao

Cui

Zhang

Deployment patterns for k-Coverage and l-Connectivity in wireless sensor networks

Proceedings of the IET International Conference on Wireless Sensor Network

2010

73 77

22.

Bai

Kumar

Xuan

Yun

Lai

T. H.

Deploying wireless sensors to achieve both coverage and connectivity

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′06)

May 2006

131 142

2-s2.0-33748086475

23.

Bai

Xuan

Yun

Lai

T. H.

Jia

Complete optimal deployment patterns for full-coverage and K-connectivity (

k \leq 6

) wireless sensor networks

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′08)

May 2008

401 410

2-s2.0-57349090662

10.1145/1374618.1374672

24.

Bai

Mobile sensor deployment optimization for k-Coverage in wireless sensor networks with a limited mobility model

IETE Technical Review 2010 27 2 124 137

2-s2.0-77949876878

10.4103/0256-4602.60166

25.

Zhang

Hou

Maintaining sensing coverage and connectivity in large sensor networks

Wireless Ad Hoc and Sensor Networks 2005 1 1-2 89 123

26.

Yang

Adaptive triangular deployment algorithm for unattended mobile sensor networks

IEEE Transactions on Computers 2007 56 7 946 958

2-s2.0-34547881836

10.1109/TC.2007.1054

An Extended Virtual Force-Based Approach to Distributed Self-Deployment in Mobile Sensor Networks

Abstract

1. Introduction

2. Related Work

3. Preliminaries

3.1. Network Model and Assumptions

3.2. Ideal Deployment

3.3. Virtual Force-Based Approach

4. Analysis of Virtual Physics-Based Approach for Self-Deployment

4.1. Stability Analysis

Theorem 1.

Proof.

4.2. Formation Analysis

Theorem 2.

Proof.

Lemma 3.

Proof.

5. Extended Virtual Force Approach for Mobile Sensor Networks

5.1. Low- R c VFA

5.2. High- R c VFA

Algorithm 1: The scheme of virtual force between node i and its neighbor nodes.

5.3. Performance Evaluation

5.3.1. Coverage Rate

5.3.2. Uniformity of Distance

5.3.3. Uniformity of Connectivity

6. Simulation Results

6.1. Performance of Low- R c VFA

6.2. Performance of High- R c VFA

6.3. Impact of Control Coefficients

7. Conclusions

Footnotes

Acknowledgments

References

5.1. Low- $R_{c}$ VFA

5.2. High- $R_{c}$ VFA

6.1. Performance of Low- $R_{c}$ VFA

6.2. Performance of High- $R_{c}$ VFA