Sage Journals: Discover world-class research

Abstract

In wireless sensor networks, coverage holes are caused by energy depletion at some nodes, and the aim of this paper is to study how to utilize the redundant nodes with remaining energy. Particularly, this paper proposes a vector algebra based algorithm by exploring redundant nodes as an extra dimension for coverage compensation. This algorithm consists of two parts. One is to find the locations of potential redundant nodes for coverage compensation; and the other is to opportunistically select the best redundant nodes by jointly considering the hole boundaries and the remaining energy of nodes. Simulation results are provided to demonstrate that the proposed algorithm minimizes the energy consumption when repairing the holes for full coverage. Furthermore, compared with other algorithms, the proposed one exhibits better performance in terms of moving distance and energy consumption.

1. Introduction

Wireless sensor networks (WSNs) are composed of numerous small-size sensors that have various features, such as low cost, light weight, high mobility, and capabilities for sensing, computing, and communications. The sensor has the same capabilities as the machine does. In fact, WSNs are one of typical application of machine to machine communications. The “smart home” is just an example. It is not only a good application based on WSN but also an instance of machine to machine communications. With these features, WSNs have been widely used in many fields, including intelligent transportation, military applications, infrastructure monitoring, antiterrorism disaster relief, environmental monitoring, wireless healthcare, and target tracking [1–3].

Coverage is an important metric of the quality of service (QoS) in WSNs [4, 5] and is a fundamental issue since each sensor is energy constrained. The reason why some areas are not covered is due to random deployment of sensors, node energy depletion, or environmental damages. Consequently, coverage holes appear in various parts of WSNs [6, 7], significantly reducing the QoS and the lifetime of the network. An important observation is that a number of inactive redundant nodes also exist in the network, which results in the simultaneous coexistence of two types of sensors, one with extra energy and the other with drained batteries. In hybrid WSNs, such a difficulty can be overcome by moving mobile redundant sensors to the locations at which coverage holes occur.

Many recent studies on patching holes by exploring mobile nodes are based on geometry. Reference [8] proposed the Coverage Hole Patching Algorithm (CHPA), which selects the patching point along the perpendicular bisector between any two adjacent hole boundary nodes. The distances between the selected point and the corresponding two boundary nodes are equal to the communication radius. This algorithm can be easily implemented due to its low complexity but suffers low resource efficiency. To overcome this shortcoming, the two-point vertical determination method was modified to a three-point approach in the Patching Algorithm Triangle by Triangle based on mobile node (PATT) [9]. Compared with CHPA, PATT can achieve better stability and higher coverage but does not consider the use of the existing redundant sensors. Reference [10] proposed the use of a vector algebra distributed method to achieve effective deployment of redundant nodes. This algorithm effectively uses the existing redundant resources while maintaining a sufficient level of coverage. However, [10] did not consider the energy consumption caused by long-distance moving.

In order to use such redundant node resources, this paper proposes a novel mobile node scheduling algorithm, namely, a Dispatching Algorithm based on vector algebra at mobile node (DAVM), for patching holes in hybrid WSNs. Localization algorithms are independently carried out at both static and mobile nodes. Particularly, the first step of the proposed algorithm is to find where patching position is. Then the mobile sensors adjacent to boundaries calculate their moving distance and direction towards the patching position. Static nodes will select their best patching redundant nodes individually. The criterion for node selection is based on the largest remaining energy which is determined by moving distance and initial energy of redundant node. At last, the selected nodes will be activated and asked to move towards the patching positions. Those nodes are not utilized before they are activated. DAVM provides an effective method to utilize redundant nodes. It is worthy pointing out that redundant nodes calculate their corresponding patching positions by using the local and one-hop positioning information. And the proposed node scheduling method can not only avoid patching conflict caused by more than one redundant node nearby the boundaries but also minimize the energy consumption caused by node moving by inviting the nodes close to the boundaries. Simulation results are provided to demonstrate the superior performance of the proposed scheduling algorithm by comparing it with some existing schemes.

2. Preliminaries

2.1. Network Model

Consider a hybrid wireless sensor network which consists of randomly deployed n sensor nodes. These sensors comprise a set C, including both static nodes and mobile redundant nodes. Static nodes do not have energy harvesting ability, whereas mobile redundant nodes cannot move and sense until they are activated. Mobile redundant nodes have the same capacities as static nodes in terms of communication, sensing, and data processing. Moreover, mobile redundant nodes can have theapriori information about their own initial energy. The binary perception model is adopted at all of the nodes [11]. According to [12–14], the communication radius ( $R_{c}$ ) is assumed to be twice the coverage radius ( $R_{s}$ ) in order to obtain a connected network. Each node $u (x_{u}, y_{u})$ can obtain the relative positions of adjacent nodes by using its directional antenna and algorithms in [15, 16]. The probability that the sensing discs of any three sensors would intersect at a single point is close to zero because of the random deployment of the nodes. No more than one sensor is located at the same point. And every sensor node should have at least two neighbors to avoid the isolated coverage or teardrop shaped coverage. In addition, the location information of the sink node is known to all other nodes.

We assume that the coverage holes are closed and inside the monitoring region. We can obtain all the information about the boundary nodes of the coverage hole by using hole detection algorithm [17]. In [17], the maximum simple complex is built according to network topology. When a node is adjacent to the edges of the maximum simple complex network, this node is a hole boundary node but not vice versa.

2.2. Relative Definitions

Definition 1 (coverage hole).

If a continuous area is not covered by any sensor node in WSNs, this area is defined as a coverage hole [19]. As shown in Figure 1, the shadow area is a coverage hole. Given a set of boundary nodes $S = {S_{i} ∣ i = 1,2, \dots, Num}$ , where $S \subset C$ , $S_{i} \in S$ is a hole boundary node.

Figure 1

Coverage holes.

Definition 2 (hole boundary neighbor).

The two nodes $S_{i}, S_{j} \in S$ are mutually hole boundary neighbors if $d (S_{i}, S_{j}) \leq R_{c}$ where $d (\cdot)$ is the 2D Euclidean distance between the two nodes.

Definition 3 (hole boundary intersection).

If two hole boundary nodes intersect at one point within a hole that is beyond the scope of the third node's sensing range, then this intersection point is called a hole boundary intersection.

3. Vector Algebra Principles

The fundamental function of DAVM is to calculate the potential patching locations. In consideration of the existing coverage hole, vector algebra can be used to move the redundant nodes. Without any constraints, more than one redundant node can patch the hole. Therefore, choosing the best node is another challenging problem considered in DAVM. To be considered effective, DAVM needs to guarantee that the patching node covers the hole without splitting the hole; that is, the patching node does not generate new holes [20, 21].

Thus, DAVM consists of two parts: $(1)$ calculating the displacement of the redundant node, including the direction and the distance; and $(2)$ identifying the hole boundary node and scheduling the best redundant node.

3.1. Displacement of Redundant Node

(i) Moving Direction. Consider a part of hole boundary that includes $S_{1}$ and its neighbors $S_{2}$ and $S_{3}$ , as illustrated in the following example. Given a redundant node $R (x_{R}, y_{R})$ , their sensing circles of $R (x_{R}, y_{R})$ intersect with $S_{1}$ and $S_{3}$ at $a (x_{a}, y_{a})$ and $b (x_{b}, y_{b})$ as shown in Figure 2. The following can be calculated:

\begin{matrix} \overset{⟶}{V_{1}} = (x_{a} - x_{R}) \vec{i} + (y_{a} - y_{R}) \vec{j}, \\ \overset{⟶}{V_{2}} = (x_{b} - x_{R}) \vec{i} + (y_{b} - y_{R}) \vec{j}, \\ \overset{⟶}{V_{R}} = \overset{⟶}{V_{1}} + \overset{⟶}{V_{2}}, \end{matrix}

(1)

where

θ (\vec{i}, \vec{j})

is defined as the mobility azimuth that is counterclockwise from

\vec{i}

\vec{j}

. If

V_{2}

is regarded as the reference vector, the mobility azimuth of R is defined as

- θ (\overset{⟶}{V_{2}}, R)

or simply as

θ (R)

. Let the auxiliary vector

\overset{⟶}{V}

satisfy

θ (R) = θ (\overset{⟶}{V})

and

∥ \overset{⟶}{V} ∥ = ∥ \overset{⟶}{V_{R}} ∥

. The following four cases are considered for the calculation of

\overset{⟶}{V}

, as shown in Figures 2(a)–2(d). Then,

θ (R)

is obtained.

Figure 2

Mobility azimuth of R.

Case 1.

When $θ (\overset{⟶}{V_{1}}, \overset{⟶}{V_{2}}) < π$ , $\forall P_{k}$ , if $d (R, P_{k}) \leq R_{s}$ , there is $\overset{⟶}{V} = \overset{⟶}{V_{R}}$ .

Case 2.

When $θ (\overset{⟶}{V_{1}}, \overset{⟶}{V_{2}}) < π$ , $\exists P_{k}$ , if $d (R, P_{k}) > R_{s}$ , there is $\overset{⟶}{V} = - \overset{⟶}{V_{R}}$ .

Case 3.

When $θ (\overset{⟶}{V_{1}}, \overset{⟶}{V_{2}}) > π$ , $\forall P_{k}$ , if $d (R, P_{k}) \leq R_{s}$ , there is $\overset{⟶}{V} = - \overset{⟶}{V_{R}}$ .

Case 4.

When $θ (\overset{⟶}{V_{1}}, \overset{⟶}{V_{2}}) > π$ , $\exists P_{k}$ , if $d (R, P_{k}) > R_{s}$ , there is $\overset{⟶}{V} = \overset{⟶}{V_{R}}$ .

(ii) Moving Distance. The moving distance of R, $L_{0}$ is dependent on both R and hole boundary intersections. As shown in Figure 3, the hole boundary node $S_{2}$ exists; its sensing range intersects the ranges of $S_{1}$ and $S_{3}$ at $P_{1} (x_{P_{1}}, y_{P_{1}})$ and $P_{2} (x_{P_{2}}, y_{P_{2}})$ , respectively. The calculation flow of $L_{0}$ is shown as follows:

\begin{array}{l} \overset{⟶}{V_{R P_{k}}} = (x_{P_{k}} - x_{R}) \vec{i} + (y_{P_{k}} - y_{R}) \vec{j}, \\ \cos θ (\overset{⟶}{V_{R P_{k}}}, \overset{⟶}{V}) = \frac{\overset{⟶}{V_{R P_{k}}} • \overset{⟶}{V}}{| \overset{⟶}{V_{R P_{k}}} | \times | \overset{⟶}{V} |}, \\ L_{0} = L_{R P_{k}} \times \cos θ (\overset{⟶}{V_{R P_{k}}}, \overset{⟶}{V}) \\ + \sqrt{{R_{s}}^{2} - {L_{R P_{k}}}^{2} + {L_{R P_{k}}}^{2} co  s^{2} θ (\overset{⟶}{V_{R P_{k}}}, \overset{⟶}{V})}, where \\ L_{R P_{k}} = \sqrt{{(x_{R} - x_{P_{k}})}^{2} + {(y_{R} - y_{P_{k}})}^{2}} . \end{array}

(2)

Figure 3

Moving distance based on the new position $R^{'}$ .

The new position $R^{'}$ can be determined by using $θ (R)$ and $L_{0}$ . Two new positions are calculated by $P_{1}$ and $P_{2}$ . An $R^{'}$ that satisfies $d (R^{'}, P_{k}) \leq R_{s} (k \in [1,2])$ is chosen as the new position. Therefore, the moving distance should be calculated by the chosen $R^{'}$ .

3.2. Best Redundant Node

More than one node may try to participate into patching because of the high mobility of redundant nodes. To avoid patching collision, the best redundant node should be selected in terms of energy and moving distance. Thus, the evaluated remaining energy $E_{r} (i)$ of the redundant node $R_{i}$ can be calculated as follows:

\begin{matrix} E_{r} (i) = α E_{0} (i) - β L_{0} (i), \end{matrix}

(3)

where

E_{0} (i)

is initial energy of node i,

α (α \geq 1)

is the energy endurance parameter; β is the consumption of energy per unit distance, that is, the energy consumption parameter, which is governed by the given work environment and the physical properties of the nodes.

Let $E_{th}$ be the threshold energy required for working. The best moving node $R_{best}$ can be selected if $E_{r} (R_{best})$ is larger than both $E_{th}$ and that of the other nodes.

4. DAVM

In DAVM, the hole boundary node $S_{j}$ broadcasts the information regarding the hole. Any redundant node $R_{i}$ that receives this message runs the displacement algorithm and replies to $S_{j}$ . Then, $S_{j}$ activates the best redundant node $R_{best}$ by using the feedback messages from the redundant nodes. And node $R_{best}$ moves to a new location. Let the queue $Q_{all}$ record the displacements and energy information of the redundant nodes. The procedures of the displacement algorithm and the best redundant node schedule are presented in detail in the following sections.

4.1. Displacement Algorithm

When a redundant node $R_{i}$ receives the information on the hole, the following steps are carried out.

Step 1.

Calculate $L_{0} (i)$ , $θ (i)$ , and $E_{r} (i)$ .

Step 2.

Reply $L_{0} (i)$ , $θ (i)$ , $E_{0} (i)$ , and $E_{r} (i)$ to $S_{j}$ .

Step 3.

Start the timer T.

Step 4.

If T is out of time, proceed to Step 6.

Step 5.

If $R_{i}$ receives the activated command from $S_{j}$ , it will be activated and move to the new position based on ( $θ (i)$ , $L_{0} (i)$ ); otherwise, proceed to Step 4.

Step 6.

Enter a dormancy state.

4.2. Best Redundant Node Schedule

The hole boundary node $S_{j}$ runs the following.

Step 1.

Calculate the value of $θ (\overset{⟶}{V_{S_{j} S_{k}}}, \overset{⟶}{V_{S_{j} S_{i}}})$ , where $S_{i}$ is the right hole boundary neighbor and $S_{k}$ is the left one. If $θ (\overset{⟶}{V_{S_{j} S_{k}}}, \overset{⟶}{V_{S_{j} S_{i}}}) < π$ , proceed to Step 2; otherwise, select the next hole boundary node counterclockwise until the selected node $S_{j}$ satisfies $θ (\overset{⟶}{V_{S_{j} S_{k}}}, \overset{⟶}{V_{S_{j} S_{i}}}) < π$ .

Step 2.

$S_{j}$ broadcasts the hole information.

Step 3.

Wait for the feedback messages from the redundant nodes and update $Q_{all}$ .

Step 4.

Based on $Q_{all}$ , $S_{j}$ selects the best redundant node $R_{best}$ .

Step 5.

Send activated command to $R_{best}$ .

Step 6.

Update the set S.

4.3. DAVM for Multiple Holes

In applications, it is a fact that there is more than one hole in WSN because of random deployment. If these holes are separated and satisfy the network model in Section 2.1, DAVM can still work effectively through patching them one by one. It is not overlooked that the patching order of holes might affect the results of DAVM. That is, the set of nodes used for holes patching may not be the same if the holes are patched in different orders. But the local optimality can be obtained when patching multiple holes in sequence, because DAVM can select the best redundant node from the remaining redundant node.

5. Simulation

5.1. Simulation Environment

The simulations are implemented by using Matlab. DAVM is evaluated and compared with the coverage optimization algorithm (COA) mentioned in [10]. Note that COA is also based on vector algebra. In consideration of the randomness in WSNs, the simulation is performed 20 times with the same topology for each algorithm in each scenario according to Monte Carlo theory. The simulation focuses on a normal N-polygon hole, and the N vertices are the N hole boundary nodes. The length of the edge is constant; thus, more N corresponds to a larger hole. For the multiple holes, DAVM can be usedpatchingthese holes one by one.

Furthermore, the initial energies and positions of the redundant nodes are random in the coverage hole. The simulation parameters and calculations are given in Table 1.

Table 1

Simulation parameters and calculations.

Parameters	Calculation description
Coverage hole region	A N-polygon about 12
	meters on a side, where $N \in [6,29]$
Area of hole S	$36 N / \tan (π / N)$ (m²)
Hole-boundary node number	N
Redundant node number M	$144 N / π {R_{s}}^{2}^{} \tan (π / N)$
Initial energy $E_{0} (i)$ of redundant node i	$E_{0} (i) \in [90,110]$ (J)
Communication radius $R_{c}$	16 m
Coverage radius $R_{s}$	8 m
Energy endurance parameter α	1 (network without endurance ability)
Energy consumption parameter β [18]	1 J/m
Energy threshold $E_{th}$	60 J

5.2. Simulation Analysis

5.2.1. Coverage Evaluation

The coverage ratio is the ratio of the covered area to the area of hole. Figure 4 shows the relationship between the coverage ratio and the number of mobile nodes Sum in different N-polygon holes, where $N \in [17,29]$ . After running DAVM, the coverage ratio approximately increases linearly with an increasing number of mobile redundant nodes. Repeated experiments reveal that the increasing trend slows down with the enlarging hole using linear fitting method. Let the line slope K be the trend, in which the coverage varies with the number of mobile nodes; obviously, $K \geq 0$ . In the experiment, the number of edges of hole N increases from 17 to 29, but K decreases from 0.0551 to 0.0178. Thus, for a larger area of the hole, the coverage gain of additional nodes is not significant, because more additional nodes are needed to compensate the larger coverage losses.

Figure 4

Number of mobile nodes versus coverage ratio.

5.2.2. Evaluation of the Total Number of Mobile Nodes

As shown in Figure 5, the number of activated redundant mobile nodes is simulated for various hole sizes. The number of redundant mobile nodes activated Sum increases with an enlarging hole in both algorithms. Compared with DAVM, COA requires smaller mobile nodes for a larger hole ( $N > 12$ ), which is due to the fact that COA can only guarantee 90% coverage. On the other hand, DAVM is to achieve approximately 100% coverage but requires the activation of more mobile nodes. Or in other words, DAVM can provide a better performance than COA in terms of hole compensation with a price of more system complexity.

Figure 5

Evaluation on number of mobile nodes.

5.2.3. Evaluation of Average Moving Distance

The moving distance of the mobile node directly affects the energy consumption. To analyze the average moving distance, several algorithms are simulated to evaluate the energy consumption in different holes. The average moving distance L is defined as follows:

\begin{matrix} L = \frac{1}{Sum} \sum_{i = 1}^{Sum} L_{0} (R_{best, i}) . \end{matrix}

(4)

As shown in Figure 6, the average moving distance L shows an obvious pulsation when the area of the hole increases (i.e., N↑) because COA does not consider the remaining energy of nodes. In DAVM, L stably ranges from 5 to 6, which is smaller than the range from 6 to 8 in COA. This finding verifies that the best redundant node schedule balances the energy.

Figure 6

Evaluation on average moving distance L.

5.2.4. Evaluation of Average Remaining Energy

Figure 7 shows the average remaining energy with the hole size N and β. The average remaining energy E is defined as follows:

\begin{matrix} E = \frac{1}{Sum} \sum_{i = 1}^{Sum} E_{r} (R_{best, i}) . \end{matrix}

(5)

Figure 7

Evaluation of average remaining energy E, where coordinates $(X, Y, Z)$ refer to β, N, and E.

DAVM takes the remaining energy of nodes into the consideration when designing the scheduler, which is important to effectively prevent larger moving distances of nodes and hence avoid consuming excess energy. As shown in Figure 7, the average remaining energies of both algorithms fluctuate minimally with various N and β. Compared with COA, DAVM has smoother and higher energy surface, and the fluctuation range is maintained within 1%. As result, the decrease of the network lifetime brought by using DAVM would be less than the use of COA. With an increase in β, E decreases, especially in COA. Therefore, DAVM is less sensitive to β.

5.2.5. Evaluation of Average Computation Time

The comparison of average computation time of nodes under several conditions is shown in Table 2, and Figure 8 presents the corresponding box plots. As shown in Figure 8, the computation time ranges from 0.304 s to 0.399 s for different N-polygon holes. Given a certain β, DAVM has consistently shorter computation time than COA. The performance of DAVM is more effective than COA.

Table 2

Average computation time of each node.

Scenario		Average computation time of each node (sec)
#	N	DAVM			COA
#	N	$β = 1$	$β = 2$	$β = 3$	$β = 1$	$β = 2$	$β = 3$
1	6	0.393	0.376	0.367	0.382	0.367	0.329
2	8	0.376	0.344	0.379	0.312	0.378	0.364
3	10	0.388	0.380	0.304	0.369	0.347	0.360
4	12	0.372	0.395	0.372	0.356	0.395	0.392
5	14	0.338	0.367	0.366	0.361	0.346	0.360
6	16	0.368	0.348	0.388	0.327	0.320	0.388
7	18	0.363	0.393	0.336	0.329	0.340	0.330
8	20	0.390	0.399	0.347	0.362	0.391	0.312

Figure 8

Box plots of simulation results for average computation time of each node.

6. Conclusions

This paper has proposed a novel algorithm to combat coverage holes by using redundant nodes in a wireless sensor network. The proposed algorithm achieves a balanced tradeoff between the initial energy and the moving energy consumption and chooses the best redundant node to patch the hole. Simulation results have been provided to show that DAVM is superior to COA for several aspects. However, DVAM may not be effective to the scenarios with sparse redundant nodes. A promising future direction is to focus on coverage holes with sparse redundant nodes.

Footnotes

Acknowledgments

All authors thank the effort from Dr. Yang Le. This research was financially supported by the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (no. JUSRP11129), the Doctoral Fund of Ministry of Education of China (no. 20100093120007), and the National Natural Science Fund of China (no. 61304214).

References

Younghwan

Agrawal

D. P.

Mobile sensor relocation to prolong the lifetime of wireless sensor networks

Proceedings of the IEEE 67th Vehicular Technology Conference (VTC '08)

May 2008

Singapore

193 197

2-s2.0-47749138261

10.1109/VETECS.2008.52

Kanno

Buchart

J. G.

Selmic

R. R.

Phoha

Detecting coverage holes in wireless sensor networks

Proceedings of the 17th Mediterranean Conference on Control and Automation (MED '09)

June 2009

Thessaloniki, Greece

452 457

Teng

Bolbrock

Cao

la Porta

Sensor relocation with mobile sensors: design, implementation, and evaluation

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

October 2007

Pisa, Italy

1 9

2-s2.0-50249136122

10.1109/MOBHOC.2007.4428666

Han

Z.-J.

Z.-B.

Wang

R.-C.

Sun

L.-J.

Xiao

Novel coverage control algorithm for wireless sensor network

Journal on Communications 2011 32 10 174 184

2-s2.0-81355133206

Sun

Guo

Xiao

An equilibrium optimization strategy on coverage energy consumption in wireless sensor networks

Chinese Journal of Sensors and Actuators 2010 23 11 1627 1632

2-s2.0-79951479824

10.3969/j.issn.1004-1699.2010.11.022

Raymond

D. R.

Marchany

R. C.

Brownfield

M. I.

Midkiff

S. F.

Effects of denial-of-sleep attacks on wireless sensor network MAC protocols

IEEE Transactions on Vehicular Technology 2009 58 1 367 380

2-s2.0-59649125973

10.1109/TVT.2008.921621

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

Yao

Zhang

Kanno

Selmic

Decentralized detection and patching of coverage holes in wireless sensor networks

Intelligent Sensing, Situation Management, Impact Assessment, and Cyber-Sensing

April 2009

Orlando, Fla, USA

Proceedings of SPIE

2-s2.0-69849109459

10.1117/12.819294

Wang

L.-M.

Qin

Resilient method for recovering coverage holes of wireless sensor networks by using mobile nodes

Journal on Communications 2011 32 4 1 8

2-s2.0-79957596915

10.

Deng

Y. P.

C. P.

A coverage optimization algorithm based on mobile nodes in wireless sensor networks

Application Research of Computers 2012 29 8 3134 3137

11.

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

12.

Wang

Xing

Zhang

Pless

Gill

Integrated coverage and connectivity configuration in wireless sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03)

November 2003

New York, NY, USA

28 39

2-s2.0-18844371448

13.

Zhang

Hou

J. C.

Maintaining sensing coverage and connectivity in large sensor networks

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

14.

Tian

Georganas

N. D.

Connectivity maintenance and coverage preservation in wireless sensor networks

Ad Hoc Networks 2005 3 6 744 761

2-s2.0-24144479511

10.1016/j.adhoc.2004.03.001

15.

Wang

O'Dea

A TOA-based location algorithm reducing the errors due to non-line-of-sight (NLOS) propagation

IEEE Transactions on Vehicular Technology 2003 52 1 112 116

2-s2.0-0037279394

10.1109/TVT.2002.807158

16.

Liu

Darabi

Banerjee

Liu

Survey of wireless indoor positioning techniques and systems

IEEE Transactions on Systems, Man and Cybernetics C 2007 37 6 1067 1080

2-s2.0-36248934122

10.1109/TSMCC.2007.905750

17.

Yan

Martins

Decreusefond

Connectivity-based distributed coverage hole detection in wireless sensor networks

Proceedings of the 54th Annual IEEE Global Telecommunications Conference (GLOBECOM '11)

December 2011

Houston, Tex, USA

1 6

2-s2.0-84857202626

10.1109/GLOCOM.2011.6134128

18.

Sekhar

Manoj

B. S.

Siva Ram Murthy

Dynamic coverage maintenance algorithms for sensor networks with limited mobility

Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom '05)

March 2005

Kauai Island, Hawaii, USA

51 60

2-s2.0-33646579417

10.1109/PERCOM.2005.15

19.

Wang

A self-healing algorithm without location information in sensor networks

Chinese Journal of Computers 2009 32 10 1957 1970

2-s2.0-70350592074

20.

Liu

Feng

H. Y.

Xue

J. S.

Qian

M. R.

Greedy approximation algorithm of patching hole in wireless sensor networks

Proceedings of the 2nd International Conference on Consumer Electronics, Communications and Networks (CECNet '12)

April 2012

Yichang, China

2604 2608

21.

Yang

Liu

Zhang

S. K.

Weng

D. L.

Hole recovery algorithm based on mobile inner nodes in wireless sensor networks

Journal on Communications 2012 9 33 116 117

A Vector Algebraic Algorithm for Coverage Compensation in Hybrid Wireless Sensor Networks

Abstract

1. Introduction

2. Preliminaries

2.1. Network Model

2.2. Relative Definitions

Definition 1 (coverage hole).

Definition 2 (hole boundary neighbor).

Definition 3 (hole boundary intersection).

3. Vector Algebra Principles

3.1. Displacement of Redundant Node

Case 1.

Case 2.

Case 3.

Case 4.

3.2. Best Redundant Node

4. DAVM

4.1. Displacement Algorithm

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

Step 6.

4.2. Best Redundant Node Schedule

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

Step 6.

4.3. DAVM for Multiple Holes

5. Simulation

5.1. Simulation Environment

5.2. Simulation Analysis

5.2.1. Coverage Evaluation

5.2.2. Evaluation of the Total Number of Mobile Nodes

5.2.3. Evaluation of Average Moving Distance

5.2.4. Evaluation of Average Remaining Energy

5.2.5. Evaluation of Average Computation Time

6. Conclusions

Footnotes

Acknowledgments

References