# Energy Balanced Redeployment Algorithm for Heterogeneous Wireless Sensor Networks

Authors: Guang Ye; Baihai Zhang; Senchun Chai; Lingguo Cui
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Wireless sensor networks (WSNs) have gained worldwide attention in recent years. Since WSNs can be conveniently deployed to monitor a given field of interest, they have been considered as a great long-term economic potential for military, environmental, and scientific applications and so forth. One of the most active areas of research in WSNs is the coverage which is one of the most essential functions to guarantee quality of service (QoS) in WSNs. However, less attention is paid on the heterogeneity of the node and the energy balance of the whole network during the redeployment process. In this work, the energy balanced problems in mobile heterogeneous WSNs redeployment have been analyzed. The virtual force algorithm with extended virtual force model is used to improve the QoS of the deployment. Furthermore energy model is added to enhance or limit the movement of the nodes so that the energy of nodes in the whole WSNs can be balanced and the lifetime of the networks can be prolonged. The simulation results verify the effectiveness of this proposed algorithm.


---

## Body

## 1. Introduction

WSNs consist of small-sized low cost sensor nodes which have several restrictions in energy supply, computing power, and bandwidth of the wireless communication [1]. The QoS of the network is highly related to the deployment performance of the nodes. However, in many working environments such as disaster areas, battlefields, and toxic gas regions, all sensor nodes are mainly deployed randomly by aircraft instead of human beings. In such case, the deployment result may not satisfy the requirement of the system. All the nodes may cluster in a small region or may even distribute sparsely without connectivity guarantee which would influence the QoS and reliability of the WSNs significantly.Many researchers are currently engaged in coverage problem [2–4] and numerous algorithms are related to mobile WSNs.Mobile WSNs are composed of a distributed collection of nodes, each of which has communication, sensing, computation, and locomotion capabilities. The mobility of sensor nodes allows more complex application scenarios. With locomotion capabilities, sensor nodes can adjust their positions after stochastic distribution; thus the whole networks could enhance the coverage performance and reach more precise placement. However, the movement of the node would expend the energy of the node. Some node may run out of power because of the long distance movement during redeployment.Another actual problem in WSNs coverage is that the nodes in networks cannot be always the same in practice due to various reasons. The coverage analysis of heterogeneous WSNs is very useful for both academic and industrial fields. The concept of heterogeneous sensor network is proposed in [5]. The existence of heterogeneous WSNs is mainly due to the following aspects. (1) Nodes are different as physical devices, and the physical properties of the sensor node are very difficult to be completely homogenized. (2) The same type of sensor nodes may work differently due to work environment, regional terrain characteristics, and imbalanced workload or other reasons. All those could affect the behaviour of nodes in WSN.In the literature, abundant work has been done in the redeployment of the mobile WSNs, and many effective algorithms have been put forward to obtain a required placement and improve the coverage rate. Pervious work on mobile WSNs redeployment algorithms can be classified into two main kinds: virtual force algorithms (VFA) and computational geometry-based approach. In VFA based algorithms [6], those models the mobile sensor nodes as electrons or molecules, and nodes move toward or away from each other by the virtual force (often related to the distance between nodes) or potential fields. However algorithms above do not consider some actuality problems such as connectivity maintenance and the energy cost [7]. References [8–10] are algorithms according to the computational geometry in which nodes update their positions to from a uniform Voronoi diagram or Delaunay triangulation. It can provide well performance but is hard to be used for the need of the global position information of the whole network which usually cannot be realized.In this paper, the redeployment problem in mobile heterogeneous WSNs considering energy balanced is addressed. Delaunay triangulation is used in VFA to find the logic neighbors nodes in order to avoid nodes cluster in a small region. Furthermore according to the research fixed ideal distance is proposed to solve the serious coverage holes and redundant problem in traditional VFA. And the energy model of the nodes is proposed. In order to balance the energy of the whole networks, in this paper energy control function is added to the virtual force model.Throughout the paper, it is assumed that the communication range is two times the sensing range. The rest of this paper is organized as follows. Section2 gets over the past work that closely related to our work. Section 3 analyzes energy unbalanced problem in mobile WSNs redeployment and provides a solution. Section 4 gives the simulation results that illustrate the performance. Section 5 is the conclusion of the paper.


## 2. Related Works

The prior work on redeployment of mobile WSNs in recent years which closely related to this subject is summarized below.The concept of redeployment of mobile WSNs is derived from dealing with coordination in behavior control of many robots teams [11, 12]. Gage [11] has classified the use of robot swarms to provide blanket, barrier, or sweep coverage of area. According to this classification, the redeployment problem studied in this paper focuses on the blanket coverage. Reference [12] considers multirobot exploration and mapping for larger teams and gives an evaluation of different strategies for coordinating the efforts of a robot team during an exploration mission in an unknown environment. In [13], a potential-field-based approach (PFBA) is presented to deploy sensor nodes in a target environment. In order to obtain a uniform deployment in an unknown enclosed area, control force defined as negative gradient of potential (NGOP) is employed. However, some crucial problems had not been considered such as connectivity maintenance and topology control. In [14], the author introduced the concept of virtual force algorithm (VFA) to the WSNs deployment. The VFA adopts the similar strategy as PFBA, by considering the virtual attractive and repulsive forces exerted on each node by neighbor nodes and obstacles. The VFA can significantly increase sensor coverage. These works only consider homogeneous sensing models. Based on works in [14], a distributed self-spreading algorithm is developed in [15]. The virtual force in (distributed self-spreading algorithm) DSSA is modeled as internuclear repulsion and attraction between molecules. Computational geometry such as Voronoi diagram and Delaunay triangulation is commonly used in redeployment of WSNs, and the vector-based algorithm (VEC), the Voronoi-based algorithm (VOR), and MiniMax are presented in [8]. The algorithms above use Voronoi diagrams to divide the coverage field into many small areas and enhance the covered area by pushing or pulling nodes according to virtual force. Computational geometry-based algorithms can solve the stacking problem. However the Voronoi diagram is a global structure; it means that the diagram can be obtained only if the global location information of all nodes in the WSNs is known.


## 3. Preliminaries

### 3.1. Network Model and Assumptions

In this paper we focus on the redeployment problem of heterogeneous WSNs in 2-dimensional plane. The position of nodei is described as (xi,yi). The distance between node i and node j is defined as Euclidean distance dij. The initial deployment is a random deployment in unknown distribution. We assume that every node can learn its own position by GPS or other localization technologies. Rc is the communication range; if dij≤Rc, node i and node j are neighbor nodes. Nodes can receive and send message to their neighbors without losing data. Meanwhile, nodes can also get relative distances and orientations between them. Nodes are aware of their remaining energy and can share this information with their neighbors. Rs is the sensing range. The perceptual model Cpi is defined as follows (p is an arbitrary position in target area):(1)Cpi1,dip<Rs0,dip≥Rs.In general,Rc is larger than Rs.All of the virtual physics algorithms for redeployment problem in WSNs are similar to the structure of virtual force, which include the ideas of potential field with circle packing that models the sensor node to be a particle in the potential field. And the potential field exerts forces on the nodes in its field. For a couple of neighbor nodesi and j, the potential function Vij could be built. And the virtual force is shown as follows:(2)Fij=-∇Vij.Nodes move toward the target area by the virtual forces. The force can be attractive force or repulsive force. Generally, there is an ideal distanceDth. If the distance between nodes i and j is less than Dth, repulsive force will act on nodes. Similarly, attractive force will act on nodes if the distance is larger than the ideal distance. The repulsive force is to insure the sensors are sparse enough without too much redundant area and the attractive force is to guarantee the coverage without coverage holes.The control law for nodes is described in(3)x¨i=∑j∈GiFij-kdx˙i,where x¨i is the acceleration of the node, x˙i is the velocity of the node, kd is damping coefficient, and Gi is the neighbors of node i.In traditional VFA, the virtual force is defined as follows:(4)Fij=ωAdij-Dthi,juij,ifdij>Dthi,jωRdij-1uji,ifdij<Dthi,j0,ifdij=Dthi,j,where ωA is the virtual force attractive coefficient, ωR is the virtual force repulsive coefficient, dij is the Euclidean distance between node i and node j, and uij is the unit vector from node i to node j.Nodes move to new positions according to (3). The total force Fi exerted on node i can be described as follows:(5)Fi=∑j∈GiFij.


## 3.1. Network Model and Assumptions

In this paper we focus on the redeployment problem of heterogeneous WSNs in 2-dimensional plane. The position of nodei is described as (xi,yi). The distance between node i and node j is defined as Euclidean distance dij. The initial deployment is a random deployment in unknown distribution. We assume that every node can learn its own position by GPS or other localization technologies. Rc is the communication range; if dij≤Rc, node i and node j are neighbor nodes. Nodes can receive and send message to their neighbors without losing data. Meanwhile, nodes can also get relative distances and orientations between them. Nodes are aware of their remaining energy and can share this information with their neighbors. Rs is the sensing range. The perceptual model Cpi is defined as follows (p is an arbitrary position in target area):(1)Cpi1,dip<Rs0,dip≥Rs.In general,Rc is larger than Rs.All of the virtual physics algorithms for redeployment problem in WSNs are similar to the structure of virtual force, which include the ideas of potential field with circle packing that models the sensor node to be a particle in the potential field. And the potential field exerts forces on the nodes in its field. For a couple of neighbor nodesi and j, the potential function Vij could be built. And the virtual force is shown as follows:(2)Fij=-∇Vij.Nodes move toward the target area by the virtual forces. The force can be attractive force or repulsive force. Generally, there is an ideal distanceDth. If the distance between nodes i and j is less than Dth, repulsive force will act on nodes. Similarly, attractive force will act on nodes if the distance is larger than the ideal distance. The repulsive force is to insure the sensors are sparse enough without too much redundant area and the attractive force is to guarantee the coverage without coverage holes.The control law for nodes is described in(3)x¨i=∑j∈GiFij-kdx˙i,where x¨i is the acceleration of the node, x˙i is the velocity of the node, kd is damping coefficient, and Gi is the neighbors of node i.In traditional VFA, the virtual force is defined as follows:(4)Fij=ωAdij-Dthi,juij,ifdij>Dthi,jωRdij-1uji,ifdij<Dthi,j0,ifdij=Dthi,j,where ωA is the virtual force attractive coefficient, ωR is the virtual force repulsive coefficient, dij is the Euclidean distance between node i and node j, and uij is the unit vector from node i to node j.Nodes move to new positions according to (3). The total force Fi exerted on node i can be described as follows:(5)Fi=∑j∈GiFij.


## 4. Energy Balanced Redeployment Algorithm for Heterogeneous WSNs

The extended virtual force algorithm is a redeployment algorithm with some novel features which can overcome the limitations of traditional VFA. In practical networks the sensing rangeRs of nodes cannot be always the same due to various reasons; in that case coverage holes may appear which may influence the QoS of the WSNs seriously. Prior algorithm assumed that Rc is two times larger than Rs; however as a matter of fact Rc is much larger than Rs. High Rc may induce stacking problem in redeployment.In order to solve the problem above, Energy Balanced Redeployment Algorithm (EBRA) is proposed.Firstly we prove the stability of the algorithm.


### 4.1. Stability Analysis

The stability of the algorithm can be proved with Lyapunov stability theory.Proof.
Assumexi is the position vector of node i. The control input of node i is the virtual force Fij exerted on node i by its neighbor j. Then the virtual potential field can be known according to (2) and (5). The total force of the node i can be summarized as follows:(6)Fi=∑j∈GiFij=∑j∈Gi-∇Vij.
Then energy functionΦ which combines kinetic energy with potential energy is built as Lyapunov function:(7)Φ=∑i=1N12x˙iTx˙i+12∑i=1N∑j∈GiVij.
For the symmetry ofVij and Vji, x˙i=-x˙j on the orientation from node i to node j. The time derivative Vij is described as follows:(8)ddtVij=∂Vij∂xi·dxidt+∂Vij∂xj·dxjdt=∇Vij·x˙i-∇Vij·x˙i=∇Vij·x˙i-x˙j=2∇Vij·x˙i.
The energy functionΦ can be simplified as follows:(9)Φ˙=∑i=1N12(x˙iTx˙i+x˙iTx˙i)+∑i=1N∑j∈Gi∇Vijx˙iT=∑i=1Nx˙iTx¨i+∑j∈Gi∇Vij.
Combining (9) and (3), we get(10)Φ˙=∑i=1Nx˙iTx¨i+∑j∈Gi∇Vij=∑i=1Nx˙iT∑j∈GiFij-kdx˙i+∑j∈Gi∇Vij=∑i=1Nx˙iT∑j∈Gi-∇Vij-kdx˙i+∑j∈Gi∇Vij=-kd∑i=1Nx˙iTx˙i,where kd is the damping coefficient and Φ˙ is seminegative definite. According to Lyapunov stability theory, the redeployment algorithm is asymptotically stable.


### 4.2. Redeployment Algorithm for Heterogeneous WSNs

As exponential force model can achieve fast convergence, the force model is shown in (11) and Figure 1:(11)Fijd=αdij-β-Dth-βuij,ifDth<dij<Rc0,ifdij=Dthαdij-β-Dth-βuij,if0.5Dth<dij<Dth1uijifdij≤0.5Dth,where uij is the unit vector from node i to node j, α and β are constants that may be changed in different situations, and Dth is the ideal distance.Figure 1
Virtual force model.In heterogeneous WSNs there is no ideal deployment to achieve, which is different from homogeneous WSNs, so a new balance pointDth(i,j) and the new force field truncation coefficient which keeps the nodes from stacking should be found. Dth(i,j) in homogeneous WSNs is 3Rs. However, in heterogeneous WSNs every node has different Rs, so a new ideal distance for heterogeneous WSNs should be found.Theorem 1.
As shown in Figure2, there are three nodes i, j, and k with different sensing range.
If∑ϕijk=ϕij+ϕik+ϕjk>2π, there is a hole in coverage area; if ∑ϕijk=ϕij+ϕik+ϕjk<2π, redundant coverage exists in area; if ∑ϕijk=ϕij+ϕik+ϕjk=2π, neither coverage hole nor redundant coverage exists.
Assume the distance between nodei and node j is dij=λ(Rsi+Rsj), where λ is the distance coefficient. Then, if λ=3/2, nodes cover the area without any hole.Figure 2
Localization effect in convex and concave holes.
(a)
∑
ϕ
i
j
k
>
2
π
(b)
∑
ϕ
i
j
k
=
2
π
(c)
∑
ϕ
i
j
k
<
2
πProof.
Consider(12)ϕij=arccosRsi2+Rsj2-dij22RsiRsj=arccosRsi2+Rsj2-0.75Rsi+Rsj22RsiRsj=arccos0.25Rsi2+0.25Rsj2-1.5RsiRsj2RsiRsj=arccos⁡0.25Rsi-Rsj22RsiRsj-0.5≤arccos-0.5=23π.
Similarlyϕik≤(2/3)π and ϕjk≤(2/3)π, and sum them up.
Consider∑ϕijk=ϕij+ϕik+ϕjk≤2π; that is, in heterogeneous sensor network, if we set λ=3/2, we can get coverage results without holes.
From the above,Dth(i,j)=(3/2)(Rsi+Rsj).
In VFA for homogeneous WSNs, there is a force field truncation coefficientλ2; generally λ2=1 which equivalent reduce the value of  Rc in order to avoid nodes stacking when the nodes have high Rc. However the connectivity of the networks cannot be ensured in the case of scatter initial deployment.
In this paper we employ Delaunay triangulation to solve the node gathering problem and on the other hand avoid affecting the connectivity of the networks.
Delaunay triangulation graph is composed of several disjoint triangles. The vertices of the triangle are sensor nodes. Delaunay figure is used as the logical topology of the network in the coverage control because it has no intersecting edge topology.
This paper uses Delaunay graph as the network topology where the balance pointDth(i,j)=3/2(Rsi+Rsj).
To make the algorithm as a distributed algorithm, every node uses its own local Delaunay triangulation graph.Definition 2.
Every node and its neighbor nodes in its communication radius make up the Delaunay graph. This graph is the node’s local Delaunay triangulation graph (Local DTG or LDTG). The LDTGs of all the nodes form Unit Delaunay Triangulation Graph (Unit DTG or UDTG). Obviously, UDTG is a subgraph of DTG.
To achieve better performance, another round of movement is employed; the proof is shown below.Theorem 3.
IfDth(i,j)=3/2(Rsi+Rsj) in a Delaunay triangle, the increment of ∠jkijk+1 causes monotone decrement of Rsi.Proof.
Consider(13)cos∠jkijk+1=32Rsi+Rsj2h+32Rsi+Rsj+12i-32Rsj+Rsj+12×232Rsi+Rsj32Rsi+Rsj+1-1=Rsi+Rsj2+Rsi+Rsj+12-Rsj+Rsj+122Rsi+RsjRsi+Rsj+1.
Assuming three circles are tangent to each other,cos∠jkijk+1=3/2 as shown in Figure 3.
It is clear that(14)∠jkijk+1=2arctanRVLRsi.
The area of the triangle can be described as follows:(15)Sjkijk+1=2×12RVLRsi+2×12RVLRsjk+2×12RVLRsjk+1=RVLRsi+Rsjk+Rsjk+1.
Also the area of the triangle can be calculated by Heron’s formula:(16)Sjkijk+1=Rsi+Rsjk+Rsjk+1RsiRsjkRsjk+1.
Clearly from (14), (15), and (16),(17)∠jkijk+1=2arctanRsjkRsjk+1RsiRsi+Rsjk+Rsjk+1.
∂
∠
j
k
i
j
k
+
1
/
∂
R
s
i is shown in(18)∂∠jkijk+1∂Rsi=11+RsjkRsjk+1/RsiRsi+Rsjk+Rsjk+1×1RsjkRsjk+1/RsiRsi+Rsjk+Rsjk+1×RsjkRsjk+1RsiRsi+Rsjk+Rsjk+12-RsjkRsjk+1Rsi2Rsi+Rsjk+Rsjk+1hhh-RsjkRsjk+1RsiRsi+Rsjk+Rsjk+12<0.
Theorem3 proves that the increment of ∠jkijk+1 leads to the monotone decrement of Rsi in Delaunay triangle. Therefore a node in each Delaunay triangle that meets the distance coefficient must be a determined value. But it is almost impossible to have all nodes meet the value at one time. So another step is used to improve the performance.Figure 3
Delaunay triangle.As shown in Figure2, if ∑ϕijk=ϕij+ϕik+ϕjk=2π, neither coverage holes nor coverage redundant exist. Then the main aim of the algorithm is to adjust the distance between the nodes according to the ∑ϕijk in Delaunay triangle to approach 2π.For nodei shown in Figure 2(a),(19)ϕthi,jk=ϕijk+2π-∑ϕijkjk+1ϕijk∑ϕijkjk+1.The ideal distance between nodes can be described as follows:(20)Dthi,jk=Rsi2+Rsjk2-2RsiRsjkcosϕthi,jk.Virtual force between nodesi and j is listed as follows:(21)Fijd=αdij-β-Dth-βuij,ifDthi,j<dij<Rc0,ifdij=Dthi,jorEi,jistheoutsideedgeαdij-β-Dth-βuij,if0.5Dthi,j<dij<Dthi,j1uijifdij≤0.5Dthi,j.IfE(i,j) is the outside edge of the LDTG, the virtual force between nodes i and j is zero.Then each node calculates its own resultant virtual force of its logic neighbors. Then it moves to the new position according to the motion dynamic model.Furthermore, the algorithm above can be described in Algorithm1.Algorithm 1
//m: the number of the logic neighbors  of node i
//Δt: the sampling time
Step  1. Find out logic neighbors node i in LDTG(i) of node i;
Step  2. For 1≤j≤m
Step  2.1. Set distance coefficient λ=3/2
Step  2.2.
Calculate Fij the virtual force between node i and its neighbor node j;
Step  3. Calculate the resultant virtual force;
Step  4. Calculate the accelerated speed ai and speed vi of node I and then move node i to new position;
Step  5. Update t+Δt;
Step  6. Go back to Step  1.
Step  7. Find out logic neighbors node i in LDTG(i) of node i;
Step  8. For 1≤j≤m
Step  8.1. Calculate the virtual force Fij between node i and its logic neighbor j;
Step  9. Calculate the resultant virtual force;
Step  10. Calculate the accelerated speed ai of node i and speed vi, node i move to new position;
Step  11. Update to t+Δt
Step  12. Go back to Step  1.


### 4.3. Energy Balanced Revision

Actually the imbalanced energy cost of the network may cause some node to run out of energy in a short time. In this case the whole structure of the WSNs may change, the QoS of the network cannot be guaranteed, and the lifetime of the network may be greatly shortened. As analyzed above, in mobile WSNs we can prolong the lifetime of the whole network by balancing the energy cost of the nodes during the redeployment process. Minimum energy of nodeE¯min is to describe the minimum remaining energy of the nodes in the network.Definition 4.
L
x
¯
,
L
-
x
¯
,
L
y
¯, and L-y¯ are the energy cost of the node when moving standard distance in each direction. Energy cost of node i is shown as follows:(22)Li¯=∑∀dir|Li¯×diri¯|,where diri¯ is the distance that node i moves in each direction. EIi¯ is the initial energy of node i. Ei¯ is the energy of the node i. Thus the lowest energy of the node E¯min is described as follows:(23)E¯min=MinEIi¯-Li¯.
In order to prolong the lifetime of the network, the algorithm should keepE¯min as large as possible.Definition 5.
Energy differential coefficientφ (see (24)) is used to describe the energy difference between two nodes:(24)φi,j=Ei¯-Ej¯MaxEi¯,Ej¯.
Obviously,φ∈[0,1], and if φ approaches zero, more effort should be made to protect the nodes which have low energy to save their energy.Definition 6.
Node levelγ shows the importance of the node. In practical application some key nodes are more important than other nodes. Those key nodes can influence the QoS of the whole network. Therefore the algorithm should give priority to economize the energy of those key nodes.
To balance the energy cost of the node energy control function (see (25)) is added to (21):(25)eφi,j=εrand0,1<φi,j1rand0,1≥φi,j.
ε is the attenuation coefficient. Every time node i calculates the virtual force of its logic neighbor j, node i compares its energy with j and gets the energy differential coefficient φi,j, and then node i generates a random number k∈[0,1]. If k<φi,j, the virtual force would be limited so that the movement of the node i would be reduced and in that case node i may save its energy in this round.
Then the new virtual force between nodei and node j is listed as follows:(26)Febi=∑j∈LNeφi,j·Fijd,where LN is the set of logic neighbors of node i.
There are some key nodes in the networks, those nodes should always save energy no matter their neighbor’s energy is low or not.
Node level control function is addressed in(27)δγ=γ-μ-σ,where μ and σ are constants which can be adjusted according to different situations. And the final resultant virtual force Fi is described in(28)Fi=δγ∑j∈LNeφi,j·Fijd.
Then each node calculates its own resultant virtual force of its logic neighbors according to the distance and energy and node level. Then it moves to the new position according to the motion dynamic model.
EBRA can be described in Algorithm2.Algorithm 2:EBRA.
//m: the number of the logic neighbors  of node i
//Δt: the sampling time
Step  1. Find out logic neighbors node i in LDTG(i) of node i;
Step  2. For 1≤j≤m
Step  2.1. Set distance coefficient λ=3/2
Step  2.2.
Calculate Fij the virtual force between node i and its neighbor node j;
Step  2.3.
Compare the energy of node i and node j,
Step  2.4.
Calculate the energy differential coefficient φ to fix the  Virtual force,
Step  3. Calculate the resultant virtual force;
Step  4. Calculate the accelerated speed ai and speed vi of node I and then move node i to new position;
Step  5. Update t+Δt;
Step  6. Go back to Step  1.
Step  7. Find out logic neighbors node i in LDTG(i) of node i;
Step  8. For 1≤j≤m
Step  8.1. Calculate the virtual force Fij between node i and its logic neighbor j;
Step  9. Calculate the resultant virtual force considering node level γ;
Step  10. Calculate the accelerated speed ai of node i and speed vi, node i move to new position;
Step  11. Update to t+Δt
Step  12. Go back to Step  1.


### 4.4. Performance Evaluation

Coverage Rate. The coverage rate is a measure of the coverage quality for WSNs. It was originally introduced by Gage [11]. In the 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 Rs. The value of coverage rate C is as follows:(29)C=⋃i=1nAiA,where Ai is the area covered by the node i, n is the total number of mobile sensor nodes, and A is the total area.Uniformity of Energy. In heterogeneous WSNs, the uniformity of energy can be measured by the average of the local standard deviation of the node energy(30)σE=1n∑i=1nEi-1n∑j=1nEi21/2.Minimum Energy. E¯min stands for the minimum energy of all the nodes and is described in (23).


## 4.1. Stability Analysis

The stability of the algorithm can be proved with Lyapunov stability theory.Proof.
Assumexi is the position vector of node i. The control input of node i is the virtual force Fij exerted on node i by its neighbor j. Then the virtual potential field can be known according to (2) and (5). The total force of the node i can be summarized as follows:(6)Fi=∑j∈GiFij=∑j∈Gi-∇Vij.
Then energy functionΦ which combines kinetic energy with potential energy is built as Lyapunov function:(7)Φ=∑i=1N12x˙iTx˙i+12∑i=1N∑j∈GiVij.
For the symmetry ofVij and Vji, x˙i=-x˙j on the orientation from node i to node j. The time derivative Vij is described as follows:(8)ddtVij=∂Vij∂xi·dxidt+∂Vij∂xj·dxjdt=∇Vij·x˙i-∇Vij·x˙i=∇Vij·x˙i-x˙j=2∇Vij·x˙i.
The energy functionΦ can be simplified as follows:(9)Φ˙=∑i=1N12(x˙iTx˙i+x˙iTx˙i)+∑i=1N∑j∈Gi∇Vijx˙iT=∑i=1Nx˙iTx¨i+∑j∈Gi∇Vij.
Combining (9) and (3), we get(10)Φ˙=∑i=1Nx˙iTx¨i+∑j∈Gi∇Vij=∑i=1Nx˙iT∑j∈GiFij-kdx˙i+∑j∈Gi∇Vij=∑i=1Nx˙iT∑j∈Gi-∇Vij-kdx˙i+∑j∈Gi∇Vij=-kd∑i=1Nx˙iTx˙i,where kd is the damping coefficient and Φ˙ is seminegative definite. According to Lyapunov stability theory, the redeployment algorithm is asymptotically stable.


## 4.2. Redeployment Algorithm for Heterogeneous WSNs

As exponential force model can achieve fast convergence, the force model is shown in (11) and Figure 1:(11)Fijd=αdij-β-Dth-βuij,ifDth<dij<Rc0,ifdij=Dthαdij-β-Dth-βuij,if0.5Dth<dij<Dth1uijifdij≤0.5Dth,where uij is the unit vector from node i to node j, α and β are constants that may be changed in different situations, and Dth is the ideal distance.Figure 1
Virtual force model.In heterogeneous WSNs there is no ideal deployment to achieve, which is different from homogeneous WSNs, so a new balance pointDth(i,j) and the new force field truncation coefficient which keeps the nodes from stacking should be found. Dth(i,j) in homogeneous WSNs is 3Rs. However, in heterogeneous WSNs every node has different Rs, so a new ideal distance for heterogeneous WSNs should be found.Theorem 1.
As shown in Figure2, there are three nodes i, j, and k with different sensing range.
If∑ϕijk=ϕij+ϕik+ϕjk>2π, there is a hole in coverage area; if ∑ϕijk=ϕij+ϕik+ϕjk<2π, redundant coverage exists in area; if ∑ϕijk=ϕij+ϕik+ϕjk=2π, neither coverage hole nor redundant coverage exists.
Assume the distance between nodei and node j is dij=λ(Rsi+Rsj), where λ is the distance coefficient. Then, if λ=3/2, nodes cover the area without any hole.Figure 2
Localization effect in convex and concave holes.
(a)
∑
ϕ
i
j
k
>
2
π
(b)
∑
ϕ
i
j
k
=
2
π
(c)
∑
ϕ
i
j
k
<
2
πProof.
Consider(12)ϕij=arccosRsi2+Rsj2-dij22RsiRsj=arccosRsi2+Rsj2-0.75Rsi+Rsj22RsiRsj=arccos0.25Rsi2+0.25Rsj2-1.5RsiRsj2RsiRsj=arccos⁡0.25Rsi-Rsj22RsiRsj-0.5≤arccos-0.5=23π.
Similarlyϕik≤(2/3)π and ϕjk≤(2/3)π, and sum them up.
Consider∑ϕijk=ϕij+ϕik+ϕjk≤2π; that is, in heterogeneous sensor network, if we set λ=3/2, we can get coverage results without holes.
From the above,Dth(i,j)=(3/2)(Rsi+Rsj).
In VFA for homogeneous WSNs, there is a force field truncation coefficientλ2; generally λ2=1 which equivalent reduce the value of  Rc in order to avoid nodes stacking when the nodes have high Rc. However the connectivity of the networks cannot be ensured in the case of scatter initial deployment.
In this paper we employ Delaunay triangulation to solve the node gathering problem and on the other hand avoid affecting the connectivity of the networks.
Delaunay triangulation graph is composed of several disjoint triangles. The vertices of the triangle are sensor nodes. Delaunay figure is used as the logical topology of the network in the coverage control because it has no intersecting edge topology.
This paper uses Delaunay graph as the network topology where the balance pointDth(i,j)=3/2(Rsi+Rsj).
To make the algorithm as a distributed algorithm, every node uses its own local Delaunay triangulation graph.Definition 2.
Every node and its neighbor nodes in its communication radius make up the Delaunay graph. This graph is the node’s local Delaunay triangulation graph (Local DTG or LDTG). The LDTGs of all the nodes form Unit Delaunay Triangulation Graph (Unit DTG or UDTG). Obviously, UDTG is a subgraph of DTG.
To achieve better performance, another round of movement is employed; the proof is shown below.Theorem 3.
IfDth(i,j)=3/2(Rsi+Rsj) in a Delaunay triangle, the increment of ∠jkijk+1 causes monotone decrement of Rsi.Proof.
Consider(13)cos∠jkijk+1=32Rsi+Rsj2h+32Rsi+Rsj+12i-32Rsj+Rsj+12×232Rsi+Rsj32Rsi+Rsj+1-1=Rsi+Rsj2+Rsi+Rsj+12-Rsj+Rsj+122Rsi+RsjRsi+Rsj+1.
Assuming three circles are tangent to each other,cos∠jkijk+1=3/2 as shown in Figure 3.
It is clear that(14)∠jkijk+1=2arctanRVLRsi.
The area of the triangle can be described as follows:(15)Sjkijk+1=2×12RVLRsi+2×12RVLRsjk+2×12RVLRsjk+1=RVLRsi+Rsjk+Rsjk+1.
Also the area of the triangle can be calculated by Heron’s formula:(16)Sjkijk+1=Rsi+Rsjk+Rsjk+1RsiRsjkRsjk+1.
Clearly from (14), (15), and (16),(17)∠jkijk+1=2arctanRsjkRsjk+1RsiRsi+Rsjk+Rsjk+1.
∂
∠
j
k
i
j
k
+
1
/
∂
R
s
i is shown in(18)∂∠jkijk+1∂Rsi=11+RsjkRsjk+1/RsiRsi+Rsjk+Rsjk+1×1RsjkRsjk+1/RsiRsi+Rsjk+Rsjk+1×RsjkRsjk+1RsiRsi+Rsjk+Rsjk+12-RsjkRsjk+1Rsi2Rsi+Rsjk+Rsjk+1hhh-RsjkRsjk+1RsiRsi+Rsjk+Rsjk+12<0.
Theorem3 proves that the increment of ∠jkijk+1 leads to the monotone decrement of Rsi in Delaunay triangle. Therefore a node in each Delaunay triangle that meets the distance coefficient must be a determined value. But it is almost impossible to have all nodes meet the value at one time. So another step is used to improve the performance.Figure 3
Delaunay triangle.As shown in Figure2, if ∑ϕijk=ϕij+ϕik+ϕjk=2π, neither coverage holes nor coverage redundant exist. Then the main aim of the algorithm is to adjust the distance between the nodes according to the ∑ϕijk in Delaunay triangle to approach 2π.For nodei shown in Figure 2(a),(19)ϕthi,jk=ϕijk+2π-∑ϕijkjk+1ϕijk∑ϕijkjk+1.The ideal distance between nodes can be described as follows:(20)Dthi,jk=Rsi2+Rsjk2-2RsiRsjkcosϕthi,jk.Virtual force between nodesi and j is listed as follows:(21)Fijd=αdij-β-Dth-βuij,ifDthi,j<dij<Rc0,ifdij=Dthi,jorEi,jistheoutsideedgeαdij-β-Dth-βuij,if0.5Dthi,j<dij<Dthi,j1uijifdij≤0.5Dthi,j.IfE(i,j) is the outside edge of the LDTG, the virtual force between nodes i and j is zero.Then each node calculates its own resultant virtual force of its logic neighbors. Then it moves to the new position according to the motion dynamic model.Furthermore, the algorithm above can be described in Algorithm1.Algorithm 1
//m: the number of the logic neighbors  of node i
//Δt: the sampling time
Step  1. Find out logic neighbors node i in LDTG(i) of node i;
Step  2. For 1≤j≤m
Step  2.1. Set distance coefficient λ=3/2
Step  2.2.
Calculate Fij the virtual force between node i and its neighbor node j;
Step  3. Calculate the resultant virtual force;
Step  4. Calculate the accelerated speed ai and speed vi of node I and then move node i to new position;
Step  5. Update t+Δt;
Step  6. Go back to Step  1.
Step  7. Find out logic neighbors node i in LDTG(i) of node i;
Step  8. For 1≤j≤m
Step  8.1. Calculate the virtual force Fij between node i and its logic neighbor j;
Step  9. Calculate the resultant virtual force;
Step  10. Calculate the accelerated speed ai of node i and speed vi, node i move to new position;
Step  11. Update to t+Δt
Step  12. Go back to Step  1.


## 4.3. Energy Balanced Revision

Actually the imbalanced energy cost of the network may cause some node to run out of energy in a short time. In this case the whole structure of the WSNs may change, the QoS of the network cannot be guaranteed, and the lifetime of the network may be greatly shortened. As analyzed above, in mobile WSNs we can prolong the lifetime of the whole network by balancing the energy cost of the nodes during the redeployment process. Minimum energy of nodeE¯min is to describe the minimum remaining energy of the nodes in the network.Definition 4.
L
x
¯
,
L
-
x
¯
,
L
y
¯, and L-y¯ are the energy cost of the node when moving standard distance in each direction. Energy cost of node i is shown as follows:(22)Li¯=∑∀dir|Li¯×diri¯|,where diri¯ is the distance that node i moves in each direction. EIi¯ is the initial energy of node i. Ei¯ is the energy of the node i. Thus the lowest energy of the node E¯min is described as follows:(23)E¯min=MinEIi¯-Li¯.
In order to prolong the lifetime of the network, the algorithm should keepE¯min as large as possible.Definition 5.
Energy differential coefficientφ (see (24)) is used to describe the energy difference between two nodes:(24)φi,j=Ei¯-Ej¯MaxEi¯,Ej¯.
Obviously,φ∈[0,1], and if φ approaches zero, more effort should be made to protect the nodes which have low energy to save their energy.Definition 6.
Node levelγ shows the importance of the node. In practical application some key nodes are more important than other nodes. Those key nodes can influence the QoS of the whole network. Therefore the algorithm should give priority to economize the energy of those key nodes.
To balance the energy cost of the node energy control function (see (25)) is added to (21):(25)eφi,j=εrand0,1<φi,j1rand0,1≥φi,j.
ε is the attenuation coefficient. Every time node i calculates the virtual force of its logic neighbor j, node i compares its energy with j and gets the energy differential coefficient φi,j, and then node i generates a random number k∈[0,1]. If k<φi,j, the virtual force would be limited so that the movement of the node i would be reduced and in that case node i may save its energy in this round.
Then the new virtual force between nodei and node j is listed as follows:(26)Febi=∑j∈LNeφi,j·Fijd,where LN is the set of logic neighbors of node i.
There are some key nodes in the networks, those nodes should always save energy no matter their neighbor’s energy is low or not.
Node level control function is addressed in(27)δγ=γ-μ-σ,where μ and σ are constants which can be adjusted according to different situations. And the final resultant virtual force Fi is described in(28)Fi=δγ∑j∈LNeφi,j·Fijd.
Then each node calculates its own resultant virtual force of its logic neighbors according to the distance and energy and node level. Then it moves to the new position according to the motion dynamic model.
EBRA can be described in Algorithm2.Algorithm 2:EBRA.
//m: the number of the logic neighbors  of node i
//Δt: the sampling time
Step  1. Find out logic neighbors node i in LDTG(i) of node i;
Step  2. For 1≤j≤m
Step  2.1. Set distance coefficient λ=3/2
Step  2.2.
Calculate Fij the virtual force between node i and its neighbor node j;
Step  2.3.
Compare the energy of node i and node j,
Step  2.4.
Calculate the energy differential coefficient φ to fix the  Virtual force,
Step  3. Calculate the resultant virtual force;
Step  4. Calculate the accelerated speed ai and speed vi of node I and then move node i to new position;
Step  5. Update t+Δt;
Step  6. Go back to Step  1.
Step  7. Find out logic neighbors node i in LDTG(i) of node i;
Step  8. For 1≤j≤m
Step  8.1. Calculate the virtual force Fij between node i and its logic neighbor j;
Step  9. Calculate the resultant virtual force considering node level γ;
Step  10. Calculate the accelerated speed ai of node i and speed vi, node i move to new position;
Step  11. Update to t+Δt
Step  12. Go back to Step  1.


## 4.4. Performance Evaluation

Coverage Rate. The coverage rate is a measure of the coverage quality for WSNs. It was originally introduced by Gage [11]. In the 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 Rs. The value of coverage rate C is as follows:(29)C=⋃i=1nAiA,where Ai is the area covered by the node i, n is the total number of mobile sensor nodes, and A is the total area.Uniformity of Energy. In heterogeneous WSNs, the uniformity of energy can be measured by the average of the local standard deviation of the node energy(30)σE=1n∑i=1nEi-1n∑j=1nEi21/2.Minimum Energy. E¯min stands for the minimum energy of all the nodes and is described in (23).


## 5. Numerical Simulation

In this section, we present the simulation results of EBRA.In the simulation environment, 40 nodes are deployed randomly in a100m∗100m square field. Communication range of all nodes is 30 m. The sensing range of 14 nodes is 10 m, and other nodes’ sensing range is 8 m.


### 5.1. Performance of Energy Balanced Redeployment Algorithm

Firstly, simulation is done in scatter initial deployment. The scatter initial deployment is shown in Figure4.Figure 4
Scatter initial deployment.The redeployment results of VFA and EBRA in scatter initial deployment are shown in Figures5(a) and 5(b).Figure 5
Simulation result in scatter initial deployment.
(a)
Redeployment by VFA
(b)
Redeployment by EBRAIt can be seen clearly from Figure5 that EBRA shows the better result than VFA for guaranteeing the connectivity of the whole network. VFA employed force field truncation to avoid nodes stacking. λ2=1 makes long-distance virtual force disappear. In EBRA use Delaunay triangulation to seek logic neighbor of nodes instead of real neighbor to settle the defects of VFA.Then simulation is done in concentrated initial deployment. The concentrated initial deployment is shown in Figure6.Figure 6
Concentrated initial deployment.The redeployment results of VFA and EBRA in concentrated initial deployment are shown in Figures7(a) and 7(b).Figure 7
Simulation result in concentrated initial deployment.
(a)
Redeployment by VFA
(b)
Redeployment by EBRAIt can be seen clearly from Figure7(a). Compared with Figure 7(b), less holes and redundant coverage exist in the deployment result. In VFA, ideal distance coefficient is settled, and neighbor nodes cannot reach the ideal distance coefficient at same time. To improve the performance of the algorithm, another round of movement begins with modified ideal distance coefficient. Due to the modified ideal distance coefficient, the virtual forces between nodes change causing two scenarios. In area with redundant coverage virtual force makes the nodes move away from each other and in area with holes virtual force makes nodes get closer to each other.The above experiments have been carried out for 100 times, and the simulation results are illustrated below.Figure8 shows the k-coverage rates of VFA and EBRA with the initial deployment as shown in Figure 6.Figure 8
k-coverage rates of the final deployment.It can be seen clearly that EBRA can achieve better deployment than VFA, because it has less redundant coverage, and holes.Figure9 shows the minimum energy of all the nodes in mobile WSNs. Compared with traditional VFA, the minimum energy value of nodes reduces more slowly, and at step 100, both algorithms meet the ending condition, and EBRA saves more energy for the mobile WSNs which means the mobile WSNs employed EBRA can provide longer service time and better QoS.Figure 9
Minimum energy of node.Figure10 shows the uniformity of energy of the whole networks. The uniformity of energy of EBRA is lower than traditional VFA which means the energy in EBRA is more uniform distribution which provides better robustness for the whole system.Figure 10
Uniformity of energy.Figure11 shows the energy cost of the key nodes with and without energy protecting. Simulations are done in same initial deployment. Firstly a random node is selected as a key node whose energy cost will be recoded. Secondly, the node which has been selected changes its node level and then recodes the energy cost. It can be seen clearly from Figure 11 that EBRA saves the energy for the key nodes.Figure 11
Energy cost of the key nodes with and without energy protecting.


## 5.1. Performance of Energy Balanced Redeployment Algorithm

Firstly, simulation is done in scatter initial deployment. The scatter initial deployment is shown in Figure4.Figure 4
Scatter initial deployment.The redeployment results of VFA and EBRA in scatter initial deployment are shown in Figures5(a) and 5(b).Figure 5
Simulation result in scatter initial deployment.
(a)
Redeployment by VFA
(b)
Redeployment by EBRAIt can be seen clearly from Figure5 that EBRA shows the better result than VFA for guaranteeing the connectivity of the whole network. VFA employed force field truncation to avoid nodes stacking. λ2=1 makes long-distance virtual force disappear. In EBRA use Delaunay triangulation to seek logic neighbor of nodes instead of real neighbor to settle the defects of VFA.Then simulation is done in concentrated initial deployment. The concentrated initial deployment is shown in Figure6.Figure 6
Concentrated initial deployment.The redeployment results of VFA and EBRA in concentrated initial deployment are shown in Figures7(a) and 7(b).Figure 7
Simulation result in concentrated initial deployment.
(a)
Redeployment by VFA
(b)
Redeployment by EBRAIt can be seen clearly from Figure7(a). Compared with Figure 7(b), less holes and redundant coverage exist in the deployment result. In VFA, ideal distance coefficient is settled, and neighbor nodes cannot reach the ideal distance coefficient at same time. To improve the performance of the algorithm, another round of movement begins with modified ideal distance coefficient. Due to the modified ideal distance coefficient, the virtual forces between nodes change causing two scenarios. In area with redundant coverage virtual force makes the nodes move away from each other and in area with holes virtual force makes nodes get closer to each other.The above experiments have been carried out for 100 times, and the simulation results are illustrated below.Figure8 shows the k-coverage rates of VFA and EBRA with the initial deployment as shown in Figure 6.Figure 8
k-coverage rates of the final deployment.It can be seen clearly that EBRA can achieve better deployment than VFA, because it has less redundant coverage, and holes.Figure9 shows the minimum energy of all the nodes in mobile WSNs. Compared with traditional VFA, the minimum energy value of nodes reduces more slowly, and at step 100, both algorithms meet the ending condition, and EBRA saves more energy for the mobile WSNs which means the mobile WSNs employed EBRA can provide longer service time and better QoS.Figure 9
Minimum energy of node.Figure10 shows the uniformity of energy of the whole networks. The uniformity of energy of EBRA is lower than traditional VFA which means the energy in EBRA is more uniform distribution which provides better robustness for the whole system.Figure 10
Uniformity of energy.Figure11 shows the energy cost of the key nodes with and without energy protecting. Simulations are done in same initial deployment. Firstly a random node is selected as a key node whose energy cost will be recoded. Secondly, the node which has been selected changes its node level and then recodes the energy cost. It can be seen clearly from Figure 11 that EBRA saves the energy for the key nodes.Figure 11
Energy cost of the key nodes with and without energy protecting.


## 6. Conclusion

In this paper, we analyze the coverage problem in heterogeneous WSNs. We argue the energy unbalanced, coverage holes, and redundant coverage problems that appear when traditional VFA algorithms are used in heterogeneous WSNs. In order to solve these problems, EBRA which can be applied for heterogeneous WSNs in any initial deployment is proposed. Furthermore, it provides better performance than VFA. Moreover the energy cost of the nodes in the network has been balanced to prolong the lifetime and enhance the QoS of the WSNs (heterogeneous WSNs).Compared with VFA, EBRA saves almost about 20% energy for key nodes and reduces the energy waste of network. Moreover EBRA provides better coverage performance (larger coverage area, less redundant, and holes). All the above insure that EBRA is more suitable in redeployment heterogeneous WSNs for its longer lifetime, better coverage performance, and higher QoS. Future work involves studyingk-coverage requirement of heterogeneous WSNs.



---

*Source: 608121-2015-06-28.xml*