# Detecting Boundary Nodes and Coverage Holes in Wireless Sensor Networks

Authors: Li-Hui Zhao; Wenyi Liu; Haiwei Lei; Ruixia Zhang; Qiulin Tan
Journal: Mobile Information Systems
 (2016)

---

## Abstract

The emergence of coverage holes in wireless sensor networks (WSNs) means that some special events have broken out and the function of WSNs will be seriously influenced. Therefore, the issues of coverage holes have attracted considerable attention. In this paper, we focus on the identification of boundary nodes and coverage holes, which is crucially important to preventing the enlargement of coverage holes and ensuring the transmission of data. We define the problem of coverage holes and propose two novel algorithms to identify the coverage holes in WSNs. The first algorithm, Distributed Sector Cover Scanning (DSCS), can be used to identify the nodes on hole borders and the outer boundary of WSNs. The second scheme, Directional Walk (DW), can locate the coverage holes based on the boundary nodes identified with DSCS. We implement the algorithms in various scenarios and fully evaluate their performance. The simulation results show that the boundary nodes can be accurately detected by DSCS and the holes enclosed by the detected boundary nodes can be identified by DW. The comparisons confirm that the proposed algorithms outperform the existing ones.


---

## Body

## 1. Introduction

Wireless sensor networks are widely applied in many fields such as battlefield surveillance [1, 2], target tracking [2–4], environment monitoring [5], and health care [6, 7]. Most of the above applications are mission-critical and require complete coverage of the monitored area so that the events under observation can be precisely detected. However, these requirements constantly encounter the obstacles from coverage holes. On the one hand, coverage holes degrade the performance of WSNs, such as decreasing the connectivity, unbalancing the WSNs load, and aggravating the burden of hole border nodes in data forwarding. On the other hand, the appearance of coverage holes indicates the burst of special events, such as forest fire and earthquake [8]. Unfortunately, due to nonuniformity of deployment [9], failure of nodes [10], and obstacle of terrain [11], coverage holes are bound to appear and gradually increase in number and size. Thus, to alleviate the increase is stringently demanded [12]. However, no matter which idea is adopted, optimizing routing protocols [13, 14] or reducing energy consumption [15], to identify coverage holes comes first and foremost.Existing works take advantage of various characteristics of nodes in terms of geometrical morphology [4, 16–22], distribution [23, 24], and connectivity [8, 12, 25–30] to identify coverage holes. However, most of the algorithms require relatively high average node degrees [23, 24, 29], leading to a high communication overhead [25] in the process of searching the specific patterns [28, 29]. It is noted that although all the algorithms identify coverage holes by locating the nodes on the boundary of holes, none of them provides an approach for clustering the nodes except [25]. Regrettably the tremendous communication overhead in [25] badly shrinks the life cycle of WSNs.In this paper, we tackle the problem of identifying coverage holes in various scenarios by detecting the nodes located on the border of holes. Our contributions are as follows. First, we formally define the notions of boundary nodes and coverage holes. Second, we generalize our work into two questions: one is how boundary nodes are identified and the other is how coverage holes are detected. Correspondingly, we propose two algorithms, Distributed Sector Cover Scanning (DSCS) and Directional Walk (DW) algorithm. DSCS, motivated by the observation that a node can have its sensing area divided into different sectors by its neighbors, transforms the problem of identifying boundary nodes into judging whether all the sensing sectors of a node are covered by the adjacent neighbors of the node. DW, based on DSCS, is responsible for detecting coverage holes by connecting the boundary nodes that enclose the same coverage hole and clustering the nodes on the outer boundary of WSNs. Finally, we implement DSCS and DW and verify their correctness and robustness.The remainder of this paper is organized as follows. Section2 reviews related works. In Section 3, we present the net model and define coverage holes and boundary nodes. Section 4 presents the DSCS and DW algorithms in detail and states the related theoretical analysis to prove the correctness of the algorithms. Section 5 presents a part of the simulation results and compares the proposed algorithms with the existing ones. Finally, we conclude the paper.


## 2. Related Work

In this section, we recall the previous studies on the boundary node identification and coverage hole detection. The existing works can be classified into three categories: geometrical, statistical, and topological [25].In general, geometry-based methods employ the geometrical tools to recognize the boundary nodes and coverage holes with the assumption that nodes are aware of their own locations. Fang et al. [16] proposed a two-step distributed approach, in which each node autonomously checks whether it is a stuck node serving the identification of coverage holes and then an alternative route is created for data transmission along the holes. Khedr et al. applied Barycentric technique to propose a decentralized algorithm in [17], in which each node can determine whether it is a boundary node by calculating the distance of the adjacent nodes. The scheme proposed by Deogun et al. identifies a boundary node by Choosing Good Neighbors (CGN) of a node and then checking whether the Good Neighbors can form a triangle enclosing the node in [18]. Simek et al. proposed Boundary Recognition using Cset (BRC) in [19] based on the improved CGN. The implementation of both CGN and BRC is restricted by the communication range of nodes. Ma et al. [20] utilized the characters of the circumcircle of a triangle to propose a simple distributed algorithm for boundary node identification. Wang and Ssu described a scheme in [21] that if all the intersection points of the sensing area of a node with those of other nodes can be covered by the sensing region of any other node, then the node is not a boundary node. Li and Zhang [22] used the properties of empty circle based on Delaunay triangulation [31] to discover boundary nodes. All the above-mentioned algorithms can recognize whether a node is located on the border of coverage holes. However, few of them offered a clear scheme how coverage holes are identified.Statistical methods usually identify boundary nodes by assuming that the nodes in WSNs abide by the probability distribution. Fekete et al. [23] proposed an algorithm to detect boundary nodes based on the fact that mostly the node degree of boundary nodes is less than that of the nonboundary nodes of WSNs. Although good results can be achieved when the node degree in WSNs is smooth, the method is prone to being invalid when the node degree fluctuates sharply. In their subsequent work, Fekete et al. [24] derived the location of boundary nodes from the restricted stress centrality of node. However, to achieve the desirable performance, both of the above methods demand such an unrealistic node density that the average node degree should be not less than 100.Topology-based approaches, particularly applied to the location-free environment, recognize boundary nodes and coverage holes by exploiting the connectivity information of nodes. Funke et al. developed a distributed hole detection algorithm (DHD) that identifies boundary nodes by locating the broken contour in [8]. DHD firstly selects each node in the max independent set of WSNs as a seed to build its different layers of contours by connecting its neighbors that share the same hop distance, and then the algorithm identifies boundary nodes by locating the end points of a broken contour. On the basis of DHD, Chu and Ssu [26] proposed to recognize boundary nodes through creating the contour of each node based on the three-hop neighboring information of the node. Huang et al. [27] extended the idea of isocontour and proposed a scheme that uses the two-hop neighbors of any node to build the isocontour of it. The node is a boundary node if its isocontour is broken. Although the scheme does not require the location of node, it marks too many boundary nodes. Kröller et al. [28] identified coverage holes and the outer boundary of WSNs by searching a complex combinatorial structure, called flower, on the assumed prerequisite that the average node degree is more than 20. After that, Saukh et al. improved the flower pattern to recognize boundary nodes in [29], but both of them fail to detect some special patterns. Different from the above, Wang et al. [25] utilized the cut pair of the shortest path tree constructed by an arbitrary node in WSNs to identify boundary nodes, which can work well even with low average node degree. However, the high communication cost produced by repeatedly using the flooding way shrinks the lifetime of WSNs. To overcome this problem, Khan et al. proposed a hop-based approach in [12]. In this approach, each node determines whether it is a boundary node by checking whether the k-hop neighbors of a node can form an enclosed cycle of the node. Ghrist and Muhammad put forward a scheme [30] based on algebraic homology theory. However, the centralized design does not follow the trend of actual implementation in WSNs.In this paper, we propose two distributed algorithms based on computational geometry, which can effectively prevent the drawbacks of the aforementioned approaches. In the first algorithm, each node can autonomously determine whether it is a boundary node. In the second, boundary nodes can be clustered according to the coverage holes and the outer boundary of WSNs that they enclose.


## 3. Preliminary

### 3.1. Network Model and Assumption

Imagine the following scenario: a WSN is formed byn homogeneous sensor nodes v
i  (
i
=
1
,
…
,
n
) that are randomly deployed in a 2-dimensional monitored area A. The WSN is modeled as a connected graph G
=
V
,
E, where V represents the set of all nodes in the WSN and E denotes the set of edges (communication links) between the pairwise nodes. In this model, it is assumed that each node has a unique ID and knows its own location via GPS or some other localization approaches [32, 33]. Besides, we assume that all the nodes can communicate directly with the adjacent nodes within the communication range and collect their own one- and two-hop neighbors. At the same time, this work assumes that the sensing area and communication range of node v
i in WSN are regular disks with R
s and R
c as the radii, respectively, centered at v
i. Here, R
s equals R
c.


### 3.2. Definitions

Definition 1 (neighbor set).
LetN
k
(
v
i
), described in formula (1), denote the k-hop neighbor set of node v
i; node v
u is called the k-hop neighbor of node v
i if v
u
∈
N
k
(
v
i
). Let N
1,2
(
v
i
), described as formula (2), represent the union set of one- and two-hop neighbor nodes of v
i. Let N
1,2
v
i denote the node number of N
1,2
(
v
i
):(1)
N
k
v
i
=
v
u
∣
k
-
1
×
R
c
<
d
v
u
,
v
i
≤
k
×
R
c
,
u
≠
i
,
k
=
1,2
,
…
,
n
(2)
N
1,2
v
i
=
N
1
v
i
∪
N
2
v
i
,where d
v
u
,
v
i is the Euclidean distance between the nodes v
u and v
i.Definition 2 (sensing area).
The sensing area of nodev
i, denoted as S
(
v
i
), is described as formula (3). S
(
v
i
) is a circular disk with R
s as the radius and v
i as the center. As shown in Figure 1, with the location of node v
i as the origin of local Cartesian Coordinate System (CCS), the circular disk enclosed by dashed line is the sensing area of node v
i; the dashed line represents the boundary of sensing area, denoted as ∂
S
(
v
i
): (3)
S
v
i
:
x
2
+
y
2
≤
R
s
2
.Figure 1
Illustration of definitions.Definition 3 (absolute angle).
As shown in Figure1, a local CCS is created with node v
i
(
x
v
i
,
y
v
i
) as the origin, and v
m
∈
N
1,2
(
v
i
). The coordinate of v
m in local CCS is (
x
v
m
,
y
v
m
). The absolute angle of v
m refers to the forward angle from x-axis positive direction to the ray v
i
v
m
→ and it is denoted by ∠
a
b
s
(
v
i
,
v
m
)
(
∠
a
b
s
(
v
i
,
v
m
)
∈
[
0
°
,
36
0
°
]
) or ∠
a
b
s
(
v
i
,
k
); k represents the position of v
m in N
1,2
(
v
i
) where the nodes are sorted according to the ascent of absolute angles of nodes:(4)
∠
a
b
s
v
i
,
v
m
=
mod
⁡
360
+
arctan
⁡
y
v
m
-
y
v
i
x
v
m
-
x
v
i
,
360
,
x
v
m
≠
x
v
i
9
0
°
,
x
v
m
=
x
v
i
∧
y
v
m
>
0
27
0
°
,
x
v
m
=
x
v
i
∧
y
v
m
<
0
.Definition 4 (central angle).
As shown in Figure1, an angle formed by the two rays, v
i
v
m
→ and v
i
v
n
→, is called a central angle, denoted as ∠
(
v
m
,
v
i
,
v
n
)
(
∠
(
v
m
,
v
i
,
v
n
)
∈
[
0
,
π
]
).Definition 5 (sensing sector).
S
(
v
i
) can be divided into k
(
k
=
1
,
…
,
N
1,2
v
i
) sectors by N
1,2
(
v
i
); each sector is called a sensing sector and the kth sensing sector is denoted by S
(
v
i
,
k
); if the central angle corresponding to S
(
v
i
,
k
) is ∠
(
v
m
,
v
i
,
v
n
), then S
(
v
i
,
k
) can also be denoted by S
(
v
m
,
v
i
,
v
n
). The sectors satisfy the following formula: (5)
S
v
i
=
⋃
k
=
1
N
1,2
v
i
S
v
i
,
k
.Definition 6 (communication range).
As shown in Figure1, the communication range of node v
i is the circular disk enclosed by dashed line, with v
i as its center and R
c as its radius; R
c
=
R
s in this paper.Definition 7 (investigated node (ItN)).
ItN is the node that has already collected the neighbor information and is ready to perform the boundary node detection algorithm.Definition 8 (boundary node (BN)).
A node is called a BN if it lies on the border of holes or the outer boundary of WSNs. A set of boundary nodes is denoted by BNs. If a node is not a BN, then it is called a non-BN; the set of nonboundary nodes is denoted by non-BNs, as illustrated in Figure2.Figure 2
Illustration of BNs and coverage holes.Definition 9 (coverage hole).
In this paper, a coverage hole means a hole that is not covered by the sensing area of any node inA, as illustrated in Figure 2.A summary of the symbols is described in Symbol.


## 3.1. Network Model and Assumption

Imagine the following scenario: a WSN is formed byn homogeneous sensor nodes v
i  (
i
=
1
,
…
,
n
) that are randomly deployed in a 2-dimensional monitored area A. The WSN is modeled as a connected graph G
=
V
,
E, where V represents the set of all nodes in the WSN and E denotes the set of edges (communication links) between the pairwise nodes. In this model, it is assumed that each node has a unique ID and knows its own location via GPS or some other localization approaches [32, 33]. Besides, we assume that all the nodes can communicate directly with the adjacent nodes within the communication range and collect their own one- and two-hop neighbors. At the same time, this work assumes that the sensing area and communication range of node v
i in WSN are regular disks with R
s and R
c as the radii, respectively, centered at v
i. Here, R
s equals R
c.


## 3.2. Definitions

Definition 1 (neighbor set).
LetN
k
(
v
i
), described in formula (1), denote the k-hop neighbor set of node v
i; node v
u is called the k-hop neighbor of node v
i if v
u
∈
N
k
(
v
i
). Let N
1,2
(
v
i
), described as formula (2), represent the union set of one- and two-hop neighbor nodes of v
i. Let N
1,2
v
i denote the node number of N
1,2
(
v
i
):(1)
N
k
v
i
=
v
u
∣
k
-
1
×
R
c
<
d
v
u
,
v
i
≤
k
×
R
c
,
u
≠
i
,
k
=
1,2
,
…
,
n
(2)
N
1,2
v
i
=
N
1
v
i
∪
N
2
v
i
,where d
v
u
,
v
i is the Euclidean distance between the nodes v
u and v
i.Definition 2 (sensing area).
The sensing area of nodev
i, denoted as S
(
v
i
), is described as formula (3). S
(
v
i
) is a circular disk with R
s as the radius and v
i as the center. As shown in Figure 1, with the location of node v
i as the origin of local Cartesian Coordinate System (CCS), the circular disk enclosed by dashed line is the sensing area of node v
i; the dashed line represents the boundary of sensing area, denoted as ∂
S
(
v
i
): (3)
S
v
i
:
x
2
+
y
2
≤
R
s
2
.Figure 1
Illustration of definitions.Definition 3 (absolute angle).
As shown in Figure1, a local CCS is created with node v
i
(
x
v
i
,
y
v
i
) as the origin, and v
m
∈
N
1,2
(
v
i
). The coordinate of v
m in local CCS is (
x
v
m
,
y
v
m
). The absolute angle of v
m refers to the forward angle from x-axis positive direction to the ray v
i
v
m
→ and it is denoted by ∠
a
b
s
(
v
i
,
v
m
)
(
∠
a
b
s
(
v
i
,
v
m
)
∈
[
0
°
,
36
0
°
]
) or ∠
a
b
s
(
v
i
,
k
); k represents the position of v
m in N
1,2
(
v
i
) where the nodes are sorted according to the ascent of absolute angles of nodes:(4)
∠
a
b
s
v
i
,
v
m
=
mod
⁡
360
+
arctan
⁡
y
v
m
-
y
v
i
x
v
m
-
x
v
i
,
360
,
x
v
m
≠
x
v
i
9
0
°
,
x
v
m
=
x
v
i
∧
y
v
m
>
0
27
0
°
,
x
v
m
=
x
v
i
∧
y
v
m
<
0
.Definition 4 (central angle).
As shown in Figure1, an angle formed by the two rays, v
i
v
m
→ and v
i
v
n
→, is called a central angle, denoted as ∠
(
v
m
,
v
i
,
v
n
)
(
∠
(
v
m
,
v
i
,
v
n
)
∈
[
0
,
π
]
).Definition 5 (sensing sector).
S
(
v
i
) can be divided into k
(
k
=
1
,
…
,
N
1,2
v
i
) sectors by N
1,2
(
v
i
); each sector is called a sensing sector and the kth sensing sector is denoted by S
(
v
i
,
k
); if the central angle corresponding to S
(
v
i
,
k
) is ∠
(
v
m
,
v
i
,
v
n
), then S
(
v
i
,
k
) can also be denoted by S
(
v
m
,
v
i
,
v
n
). The sectors satisfy the following formula: (5)
S
v
i
=
⋃
k
=
1
N
1,2
v
i
S
v
i
,
k
.Definition 6 (communication range).
As shown in Figure1, the communication range of node v
i is the circular disk enclosed by dashed line, with v
i as its center and R
c as its radius; R
c
=
R
s in this paper.Definition 7 (investigated node (ItN)).
ItN is the node that has already collected the neighbor information and is ready to perform the boundary node detection algorithm.Definition 8 (boundary node (BN)).
A node is called a BN if it lies on the border of holes or the outer boundary of WSNs. A set of boundary nodes is denoted by BNs. If a node is not a BN, then it is called a non-BN; the set of nonboundary nodes is denoted by non-BNs, as illustrated in Figure2.Figure 2
Illustration of BNs and coverage holes.Definition 9 (coverage hole).
In this paper, a coverage hole means a hole that is not covered by the sensing area of any node inA, as illustrated in Figure 2.A summary of the symbols is described in Symbol.


## 4. Detecting Boundary Nodes and Coverage Holes

In this section, we focus on how BNs, coverage holes, and the outer boundary of WSNs are identified. To begin with, we present a mechanism for the recognition of BNs. Then, we offer the method of clustering BNs, namely, how coverage holes and the outer boundary are located. Finally, we prove the lemmas used in the schemes.


### 4.1. Detecting Boundary Nodes

DSCS, proposed for identifying boundary nodes, is described in Algorithms1 and 2.Algorithm 1:DSCS algorithm.
Input: v
i, Graph G
=
(
V
,
E
)
Output: H
v
i
(1) Set I
t
N
←
v
i // c
hoosing a node  v
i  randomly from set  V  as ItN
(2) H
v
i
←
f
a
l
s
e
(3) Collect N
1
(
v
i
) and N
2
(
v
i
) of node v
i
(4) Set N
1,2
(
v
i
)
=
N
1
(
v
i
)
∪
N
2
(
v
i
)
(5) Calculate the ∠
abs
⁡
(
v
i
,
k
)
(
k
=
1
,
…
,
|
N
1,2
(
v
i
)
|
) of nodes in N
1,2
(
v
i
)
(6) if  ∠
abs
⁡
v
i
,
m
=
∠
abs
⁡
v
i
,
l
∧
d
m
,
i
≤
d
l
,
i  then
(7)
N
1,2
(
v
i
)
=
N
1,2
(
v
i
)
-
v
l
(8) Sort the nodes of N
1,2
(
v
i
) on the basis of their absolute angles in the ascending way
(9) if  the absolute angle of the node in  N
1,2
(
v
i
)  meets any one of the following conditions:
(10)  (a) ∠
abs
⁡
(
v
i
,
|
N
1,2
(
v
i
)
|
)
≤
π, (b) ∠
abs
⁡
(
v
i
,
1
)
>
π, (c) ∀
k, ∠
abs
⁡
(
v
i
,
k
)
∈
(
π
/
2
,
3
π
/
2
],
(d) ∀
k, ∠
abs
⁡
(
v
i
,
k
)
∈
[
0
,
π
/
2
]
∣
∠
abs
⁡
v
i
,
k
∈
(
3
π
/
2
,
2
π
]. then
(11)  H
v
i
← true
(12) else
(13)
for  j
←
1  to  |
N
1,2
(
v
i
)
|  do
(14)
if  j
<
|
N
1,2
(
v
i
)
|  then
(15)
H
v
i
←
H
v
i
∪
s
e
c
t
o
r
C
o
v
e
r
(
(
N
1,2
(
v
i
)
)
j
,
(
N
1,2
(
v
i
)
)
j
+
1
)
// (
N
1,2
(
v
i
)
)
j and (
N
1,2
(
v
i
)
)
j
+
1  represent the elements of  j  and  j
+
1  of  N
1,2
(
v
i
),  respectively
(16)
else
(17)
H
v
i
←
H
v
i
∪
s
e
c
t
o
r
C
o
v
e
r
(
(
N
1,2
(
v
i
)
)
|
N
1,2
(
v
i
)
|
,
(
N
1,2
(
v
i
)
)
1
)
(18) return  H
v
iAlgorithm 2:Function sectorCover.
Input: s
t
a
r
t
,
e
n
d
,
v
i
,
N
1,2
(
v
i
)
Output: f
l
a
g
(1) f
l
a
g
←
f
a
l
s
e
(2) if  S
(
N
1,2
(
v
i
)
s
t
a
r
t
,
v
i
,
N
1,2
(
v
i
)
e
n
d
)
is covered by the sensing area of the neighbor of
v
i  then
(3)
f
l
a
g
←
f
a
l
s
e
(4) else
(5)
f
l
a
g
←
t
r
u
e
(6) return  f
l
a
gBefore executing the algorithm of DSCS, the neighboring information of all the nodes inA should be prepared. Each node needs to collect the information of its one- and two-hop neighbors, including the location and ID of the neighbor nodes. In this procedure, each node (or sender), with its unique ID and location, broadcasts a hello message to its neighbors within its communication range, and then the neighbors (or receivers) calculate the distance (
d
′
) between each of them and the sender after receiving the hello message; if d
′ meets formula (1) (
k
=
1
), then the receivers set themselves as the one-hop neighbors of the sender and unicast a response message with their IDs and locations to the sender. In the subsequent step, the sender initiates a request message for exchanging one-hop neighbor list with its one-hop neighbors. Finally, the sender carries out formula (6) to achieve the two-hop neighbors [12]:(6)
N
k
v
i
=
⋃
v
u
∈
N
k
-
1
v
i
N
1
v
u
-
N
k
-
1
v
i
-
v
i
.DSCS is carried out after the required information is collected. We exploit Figure3 and Algorithms 1 and 2 to explain the implementation of DSCS. As shown in Figure 3, v
1 is an ItN; N
1
(
v
1
)
=
{
v
2
–
5
,
v
7
,
v
17
}, N
2
(
v
1
)
=
{
v
6
,
v
8
–
16
,
v
18
}, and N
1,2
(
v
1
)
=
N
1
(
v
1
)
∪
N
2
(
v
1
). According to row (5) of Algorithm 1, the absolute angle of every node in N
1,2
(
v
1
) is calculated, with these nodes being arranged in the ascending order of their absolute angles. It is noted that nodes v
2 and v
18 have the same absolute angles; we retain node v
2 and remove v
18 (marked as red) from N
1,2
(
v
1
) based on row (6) of Algorithm 1. Then, the set N
1,2
(
v
1
) changes into {
v
12
-
13
,
v
5
,
v
14
,
v
6
,
v
15
,
v
7
,
v
16
-
17
,
v
2
,
v
8
–
10
,
v
3
,
v
11
,
v
4
}. Next, DSCS examines the absolute angles of the nodes in N
1,2
(
v
1
); if the absolute angles satisfy the condition of rows (9)–(11) of Algorithm 1, v
1 is a BN. Otherwise, DSCS starts to examine whether the border of each sector of S
(
v
1
) is completely covered by the sensing area of the corresponding neighbor nodes. According to row (13) of Algorithm 1, ∂
S
(
v
12
,
v
1
,
v
13
) is selected in the first step. Obviously, ∂
S
(
v
12
,
v
1
,
v
13
) can be fully covered by S
(
v
12
); a similar procedure will continue until the last sector. It is apparent that v
1 has no holes around it; therefore, it is a non-BN. This procedure can be distributedly executed by any node of WSNs.Figure 3
Illustration of BN detection.


### 4.2. Identifying Coverage Holes

In this section, we present DW, as described in Algorithm3, to illustrate how the BNs that enclose the same coverage hole are clustered. It serves to fulfill our work in a more meaningful way. Here are the concrete steps.Algorithm 3:DW algorithm.
Input: G
B
N
s
=
(
B
N
s
,
E
(
B
N
s
)
), G, δ
Output: BoundCycle
(1) i
←
0
(2) while BNs ≠ δ  do
(3)
Q
←
⌀
(4)
i
←
i
+
1
(5)
v
s
t
← finding the starting node from BNs according to Step 2
(6)
Q
←
Q
∪
v
s
t
(7)
while  the
v
s
u
of
v
c
is not equal to
v
s
t
or
v
s
t
∉
N
1,2
(
v
c
)  do
(8)
v
s
u
← searching for v
s
u of v
c from BNs according to Steps 2–5
(9)   Q
←
Q
∪
v
s
u
(10) examining the continuity according to Step 6
(11)
B
o
u
n
d
C
y
c
l
e
[
i
]
←
Q
(12)
B
N
s
←
B
N
s
∖
B
o
u
n
d
C
y
c
l
e
[
i
]
,
N
1
(
B
o
u
n
d
C
y
c
l
e
[
i
]
)Step 1.
Initialize an empty queueQ for storing the clustered nodes in the following steps.Step 2.
Select the node with the minimum coordinate from BNs as the start node(
v
s
t
), being marked as the current node of DW (denoted by v
c) and pushed into Q. Then v
c checks, from its N
1
(
v
c
)
⊂
B
N
s, whether there are any nodes whose absolute angles belong to [
3
π
/
2
,
2
π
]. If there exist any, v
c selects the node which has the minimum absolute angle as its inorder successor (denoted by v
s
u), and v
s
u, as the new v
c, is put into Q. Otherwise, change the scope of the absolute angle to [
0
,
π
/
2
] and repeat the above procedure. If there does not exist v
s
u in N
1
(
v
c
), then repeat the same searching process in N
2
(
v
c
).Step 3.
Repeat Step2 until v
c cannot find its v
s
u any longer; then change the scope of the absolute angle to [
π
/
2
,
π
] and execute the same procedure as in Step 1. Note that the first v
s
u found in this procedure is called the first inflection node; after that, the searching procedure will be continued within the scope [
0
,
π
].Step 4.
Ifv
s
u of v
c cannot be found in Step 3, change the scope of absolute angle to [
π
,
3
π
/
2
] and continue the searching process as in Step 3. In this procedure, the first found node is marked as the second inflection node, and then the searching process is continued within the scope [
π
/
2
,
3
π
/
2
].Step 5.
Whenv
s
u of v
c cannot be found in Step 4, change the scope of absolute angle to [
3
π
/
2
,
2
π
] and repeat the same searching procedure as in Step 4. If the first node found during the procedure is v
s
t or the one- or two-hop neighbor of v
s
t, then the searching procedure is done.
Each time the implementation from Step1 to Step 5 is over, a boundary cycle formed by selected nodes is identified. Of all the boundary cycles, the first identified is the outer boundary, while the rest are coverage holes.Step 6.
Check the queueQ; if there is any node in Q that has its two-hop neighbor as its v
s
u, insert a relay node that is the one-hop neighbor of both the node and its v
s
u. At the same time, the sum of the distance between the node and this relay node and the distance between the relay node and v
s
u should be the minimum.
Note that the relay node may be a non-BN.Step 7.
Remove all the nodes inQ and their one-hop neighbors from BNs.Step 8.
IfB
N
s
=
⌀, repeat the procedure from Steps 1 to 7 until the set of BNs is empty or the number of the remaining nodes in the set is δ (in our practice δ
=
2).We use Figure2 to describe the whole procedure of DW. We set queue Q
=
⌀. The node v
41, bearing the minimum coordinate in all BNs, is selected as v
s
t according to Steps 1 and 2, being marked as v
c and pushed into Q
(
Q
=
{
v
41
}
). Among the one-hop neighbors of v
c, v
42 is the best choice to be v
s
u of v
c according to Step 2; then v
42 takes the place of v
41 to become v
c and is pushed into Q
(
Q
=
{
v
41
,
v
42
}
). This process is executed repetitively until the first inflection point v
24 appears. Next, DW changes the searching direction according to Step 3 and continues the same procedure. When the second inflection point v
29 appears, DW changes the searching direction again according to Step 4 and repeats the same searching process until v
s
u of v
c is v
s
t or v
s
t
∈
N
1,2
(
v
c
); the searching process is over. In the following, DW finds that v
s
u of all nodes in Q are the one-hop neighbors of the nodes. Hence, the nodes enclosing the outer boundary are identified. Finally, DW removes all the nodes in Q
(
Q
=
{
v
41
–
44
,
v
21
–
40
}
) and their one-hop neighbors {
v
4
,
v
9
–
20
} from BNs. As a result, B
N
s
=
{
v
1
–
3
,
v
5
} are left.If DW findsB
N
s
≠
⌀ after the outer boundary is identified, it resets Q
=
⌀, selects v
5 as v
s
t, and then performs the following operation. v
5 is marked as v
c and pushed into Q. Then, v
c finds v
3 as its v
s
u, being marked as new v
c and pushed into Q. At the same time, DW detects that v
c is the first inflection node according to Step 3; therefore, it changes the searching scope and finds v
2 as its v
s
u as well as the second inflection node according to Step 4, with v
2 being taken as v
c and pushed into Q. Here, DW changes the searching scope again and finds v
1 as v
s
u of v
c. Hence, DW takes v
1 as new v
c and pushes it into Q. Next, v
c finds that v
5 is both its one-hop neighbor and v
s
t according to Step 5. Therefore, DW begins to check v
s
u of the nodes in Q. As a result, DW finds that v
s
u of v
3 and v
s
u of v
2 are their two-hop neighbors, respectively, so v
4 is inserted between v
5 and v
3 according to Step 6. Similarly, v
8 is inserted between v
2 and v
3. So far, all the nodes have their one-hop neighbors as their v
s
u in Q. That is to say, the nodes enclosing coverage holes are identified. In the following, DW removes all the clustered nodes in the second round of identification from BNs except v
4 and v
8 (v
4 and v
8 do not exist in BNs). At this moment, B
N
s
=
⌀, which means that the hole detection is over.


### 4.3. Theoretical Analysis

To prove the correctness of the implementation, we conduct the following theoretical analysis.Lemma 10.
Consider an ItNv
i, v
m, and v
n are any pair of adjacent neighbors (
v
m
,
v
n
∈
N
1,2
(
v
i
)
), and S
(
v
m
,
v
n
)
=
S
(
v
m
)
∩
S
(
v
n
), which is described as formula (7). If S
(
v
m
,
v
n
) is empty or S
(
v
m
,
v
n
) is not empty, the intersection of S
(
v
m
,
v
n
) with ∂
S
(
v
m
,
v
i
,
v
n
) is empty. That is, S
(
v
m
,
v
n
)
=
⌀ or (
S
(
v
m
,
v
n
)
≠
⌀
)
∧
(
S
(
v
m
,
v
n
)
∩
∂
S
(
v
m
,
v
i
,
v
n
)
=
⌀
); v
i is a BN: (7)
S
v
m
,
v
n
=
x
-
x
v
m
2
+
y
-
y
v
m
2
≤
R
s
2
x
-
x
v
n
2
+
y
-
y
v
n
2
≤
R
s
2
,where (
x
v
m
,
y
v
m
) and (
x
v
n
,
y
v
n
) are the coordinates of v
m and v
n, respectively, in the local CCS with v
i as the origin.Proof.
Given a nodev
i and any pair of adjacent neighbors v
m and v
n, we assume that v
m and v
n are located within the CCS with v
i as the origin. To prove the correctness of Lemma 10, we discuss it via the following three cases.
Case
1. If S
(
v
m
,
v
n
)
=
⌀, d
v
m
,
v
n
>
2
R
s. Hence, ∂
S
(
v
m
,
v
i
,
v
n
) cannot be fully covered by S
(
v
m
) and S
(
v
n
); thereby, v
i is a BN according to Definition 8. As shown in Figure 4, the blue shaded area represents the coverage hole.
Case
2. In another scenario, S
(
v
m
,
v
n
)
=
{
P
}, if point P lies on ∂
S
(
v
m
,
v
i
,
v
n
), ∂
S
(
v
m
,
v
i
,
v
n
) can be fully covered by S
(
v
m
) and S
(
v
n
). That is to say, there does not exist a hole in S
(
v
m
,
v
i
,
v
n
) and v
i is a non-BN, as shown in Figure 5(a). Otherwise, no matter whether P is inside or outside S
(
v
i
), there must be a hole at least around it. Hence, v
i is a BN, as shown in Figures 5(b), 5(c), and 5(d).
Case
3. In the third case, S
(
v
m
,
v
n
)
≠
⌀; whether holes exist is determined by the position of S
(
v
m
,
v
n
), if S
(
v
m
,
v
n
)
∩
∂
S
(
v
m
,
v
i
,
v
n
)
=
⌀, as shown in Figures 6(a) and 6(b); there must exist a hole and v
i is a BN. Otherwise, no holes exist and v
i is a non-BN, as shown in Figures 6(c), 6(d), 6(e), and 6(f).Figure 4
Illustration for Case1.Figure 5
Illustration for Case2.
(a)
No hole
(b)
Hole
(c)
Hole
(d)
HoleFigure 6
Illustration for Case3.
(a)
Hole
(b)
Hole
(c)
No hole
(d)
No hole
(e)
No hole
(f)
No holeLemma 11.
Considering an ItNv
i, S
(
v
i
) is divided into N
1,2
v
i by N
1,2
(
v
i
). If ∂
S
(
v
i
,
k
)
(
k
∈
{
1
,
…
,
N
1,2
v
i
}
) is not covered by the sensing areas of the neighbors of v
i, then v
i is a BN. Otherwise, it is a non-BN.Proof.
According to Definition5, S
(
v
i
) is divided into N
1,2
v
i sectors by the neighbors of v
i. If there exists a sector whose border cannot be covered by the sensing areas of the neighbors of v
i, according to Lemma 10 and Definition 8, node v
i is a BN. Otherwise, it is a non-BN.Lemma 12.
Given a sensor nodev
i, v
i is a BN if the absolute angle of a node in N
1,2
(
v
i
) meets any of the four cases: (a) ∠
a
b
s
(
v
i
,
N
1,2
v
i
)
≤
π, (b) ∠
a
b
s
(
v
i
,
1
)
>
π, (c) ∀
k
,
∠
a
b
s
(
v
i
,
k
)
∈
(
π
/
2
,
3
π
/
2
], and (d) ∀
k
,
∠
a
b
s
(
v
i
,
k
)
∈
[
0
,
π
/
2
]
∣
∠
a
b
s
(
v
i
,
k
)
∈
(
3
π
/
2
,
2
π
].Proof.
We prove Case (a) and the other cases can be proved in the same way. As shown in Figure7, nodes v
m and v
n are neighbors of node v
i. The three disk areas enclosed by the dashed lines are S
(
v
m
), S
(
v
i
), and S
(
v
n
), respectively. For v
m is the |
N
1,2
(
v
i
)
| neighbor of v
i, its absolute angle is the largest one. According to Case (a) of Lemma 12, ∠
a
b
s
(
v
i
,
v
m
)
≤
π. v
n is the adjacent node of v
m, and v
n
∈
N
1,2
(
v
i
); thus, ∠
a
b
s
(
v
i
,
v
n
)
<
∠
a
b
s
(
v
i
,
v
m
). The probable positions of v
m and v
n are shown in Figures 7(a), 7(b), and 7(c). In Figure 7(a), we assume that v
m, v
i, and v
n do not coincide with each other and they all lie on the x-axis and ∂
S
(
v
m
,
v
i
,
v
n
) can be completely covered by S
(
v
m
) and S
(
v
n
); meanwhile, S
(
v
m
)
∩
S
(
v
n
)
∩
S
(
v
i
)
=
{
P
1
,
P
2
}. In addition, the radii of S
(
v
m
), S
(
v
i
), and S
(
v
n
) are equal. Hence, if ∂
S
(
v
m
,
v
i
,
v
n
) can be fully covered, S
(
v
m
), S
(
v
i
), and S
(
v
n
) must coincide; in other words, d
v
m
,
P
2, d
v
i
,
P
2, and d
v
n
,
P
2 are equal. However, this contradicts with the assumption. Therefore, v
i is a BN when Case (a) is satisfied and all v
m, v
n, and v
i are on the x-axis. In Figures 7(b) and 7(c), we can clearly find that the blue shaded area cannot be covered by any sensors wherever v
m is located. Consequently, v
i is a BN when the position of N
1,2
(
v
i
) conforms to any case shown in Figures 7(b) and 7(c).Figure 7
Illustration for Lemma12.
(a)
∠
(
v
m
,
v
i
,
v
n
)
=
π
(b)
π
/
2
<
∠
(
v
m
,
v
i
,
v
n
)
<
π
(c)
0
<
∠
(
v
m
,
v
i
,
v
n
)
<
π
/
2Lemma 13.
The BNs clustered by DW depict the outer boundary and coverage holes of WSNs, respectively.Proof.
Because all the BNs located on the border of coverage holes and the outer boundary are identified by DSCS, we only need to cluster the BNs into different groups that map coverage holes and the outer boundary. Without loss of generality, within each group of the BNs, there must exist a BN with the minimum coordinate. Besides, the coverage holes lie within WSNs; hence, the BN with the minimum coordinate in all the BNs must lie on the border of the outer boundary. Therefore, the first identified boundary is the outer boundary. Similarly, the other boundary cycles identified in the subsequent rounds are coverage holes.


## 4.1. Detecting Boundary Nodes

DSCS, proposed for identifying boundary nodes, is described in Algorithms1 and 2.Algorithm 1:DSCS algorithm.
Input: v
i, Graph G
=
(
V
,
E
)
Output: H
v
i
(1) Set I
t
N
←
v
i // c
hoosing a node  v
i  randomly from set  V  as ItN
(2) H
v
i
←
f
a
l
s
e
(3) Collect N
1
(
v
i
) and N
2
(
v
i
) of node v
i
(4) Set N
1,2
(
v
i
)
=
N
1
(
v
i
)
∪
N
2
(
v
i
)
(5) Calculate the ∠
abs
⁡
(
v
i
,
k
)
(
k
=
1
,
…
,
|
N
1,2
(
v
i
)
|
) of nodes in N
1,2
(
v
i
)
(6) if  ∠
abs
⁡
v
i
,
m
=
∠
abs
⁡
v
i
,
l
∧
d
m
,
i
≤
d
l
,
i  then
(7)
N
1,2
(
v
i
)
=
N
1,2
(
v
i
)
-
v
l
(8) Sort the nodes of N
1,2
(
v
i
) on the basis of their absolute angles in the ascending way
(9) if  the absolute angle of the node in  N
1,2
(
v
i
)  meets any one of the following conditions:
(10)  (a) ∠
abs
⁡
(
v
i
,
|
N
1,2
(
v
i
)
|
)
≤
π, (b) ∠
abs
⁡
(
v
i
,
1
)
>
π, (c) ∀
k, ∠
abs
⁡
(
v
i
,
k
)
∈
(
π
/
2
,
3
π
/
2
],
(d) ∀
k, ∠
abs
⁡
(
v
i
,
k
)
∈
[
0
,
π
/
2
]
∣
∠
abs
⁡
v
i
,
k
∈
(
3
π
/
2
,
2
π
]. then
(11)  H
v
i
← true
(12) else
(13)
for  j
←
1  to  |
N
1,2
(
v
i
)
|  do
(14)
if  j
<
|
N
1,2
(
v
i
)
|  then
(15)
H
v
i
←
H
v
i
∪
s
e
c
t
o
r
C
o
v
e
r
(
(
N
1,2
(
v
i
)
)
j
,
(
N
1,2
(
v
i
)
)
j
+
1
)
// (
N
1,2
(
v
i
)
)
j and (
N
1,2
(
v
i
)
)
j
+
1  represent the elements of  j  and  j
+
1  of  N
1,2
(
v
i
),  respectively
(16)
else
(17)
H
v
i
←
H
v
i
∪
s
e
c
t
o
r
C
o
v
e
r
(
(
N
1,2
(
v
i
)
)
|
N
1,2
(
v
i
)
|
,
(
N
1,2
(
v
i
)
)
1
)
(18) return  H
v
iAlgorithm 2:Function sectorCover.
Input: s
t
a
r
t
,
e
n
d
,
v
i
,
N
1,2
(
v
i
)
Output: f
l
a
g
(1) f
l
a
g
←
f
a
l
s
e
(2) if  S
(
N
1,2
(
v
i
)
s
t
a
r
t
,
v
i
,
N
1,2
(
v
i
)
e
n
d
)
is covered by the sensing area of the neighbor of
v
i  then
(3)
f
l
a
g
←
f
a
l
s
e
(4) else
(5)
f
l
a
g
←
t
r
u
e
(6) return  f
l
a
gBefore executing the algorithm of DSCS, the neighboring information of all the nodes inA should be prepared. Each node needs to collect the information of its one- and two-hop neighbors, including the location and ID of the neighbor nodes. In this procedure, each node (or sender), with its unique ID and location, broadcasts a hello message to its neighbors within its communication range, and then the neighbors (or receivers) calculate the distance (
d
′
) between each of them and the sender after receiving the hello message; if d
′ meets formula (1) (
k
=
1
), then the receivers set themselves as the one-hop neighbors of the sender and unicast a response message with their IDs and locations to the sender. In the subsequent step, the sender initiates a request message for exchanging one-hop neighbor list with its one-hop neighbors. Finally, the sender carries out formula (6) to achieve the two-hop neighbors [12]:(6)
N
k
v
i
=
⋃
v
u
∈
N
k
-
1
v
i
N
1
v
u
-
N
k
-
1
v
i
-
v
i
.DSCS is carried out after the required information is collected. We exploit Figure3 and Algorithms 1 and 2 to explain the implementation of DSCS. As shown in Figure 3, v
1 is an ItN; N
1
(
v
1
)
=
{
v
2
–
5
,
v
7
,
v
17
}, N
2
(
v
1
)
=
{
v
6
,
v
8
–
16
,
v
18
}, and N
1,2
(
v
1
)
=
N
1
(
v
1
)
∪
N
2
(
v
1
). According to row (5) of Algorithm 1, the absolute angle of every node in N
1,2
(
v
1
) is calculated, with these nodes being arranged in the ascending order of their absolute angles. It is noted that nodes v
2 and v
18 have the same absolute angles; we retain node v
2 and remove v
18 (marked as red) from N
1,2
(
v
1
) based on row (6) of Algorithm 1. Then, the set N
1,2
(
v
1
) changes into {
v
12
-
13
,
v
5
,
v
14
,
v
6
,
v
15
,
v
7
,
v
16
-
17
,
v
2
,
v
8
–
10
,
v
3
,
v
11
,
v
4
}. Next, DSCS examines the absolute angles of the nodes in N
1,2
(
v
1
); if the absolute angles satisfy the condition of rows (9)–(11) of Algorithm 1, v
1 is a BN. Otherwise, DSCS starts to examine whether the border of each sector of S
(
v
1
) is completely covered by the sensing area of the corresponding neighbor nodes. According to row (13) of Algorithm 1, ∂
S
(
v
12
,
v
1
,
v
13
) is selected in the first step. Obviously, ∂
S
(
v
12
,
v
1
,
v
13
) can be fully covered by S
(
v
12
); a similar procedure will continue until the last sector. It is apparent that v
1 has no holes around it; therefore, it is a non-BN. This procedure can be distributedly executed by any node of WSNs.Figure 3
Illustration of BN detection.


## 4.2. Identifying Coverage Holes

In this section, we present DW, as described in Algorithm3, to illustrate how the BNs that enclose the same coverage hole are clustered. It serves to fulfill our work in a more meaningful way. Here are the concrete steps.Algorithm 3:DW algorithm.
Input: G
B
N
s
=
(
B
N
s
,
E
(
B
N
s
)
), G, δ
Output: BoundCycle
(1) i
←
0
(2) while BNs ≠ δ  do
(3)
Q
←
⌀
(4)
i
←
i
+
1
(5)
v
s
t
← finding the starting node from BNs according to Step 2
(6)
Q
←
Q
∪
v
s
t
(7)
while  the
v
s
u
of
v
c
is not equal to
v
s
t
or
v
s
t
∉
N
1,2
(
v
c
)  do
(8)
v
s
u
← searching for v
s
u of v
c from BNs according to Steps 2–5
(9)   Q
←
Q
∪
v
s
u
(10) examining the continuity according to Step 6
(11)
B
o
u
n
d
C
y
c
l
e
[
i
]
←
Q
(12)
B
N
s
←
B
N
s
∖
B
o
u
n
d
C
y
c
l
e
[
i
]
,
N
1
(
B
o
u
n
d
C
y
c
l
e
[
i
]
)Step 1.
Initialize an empty queueQ for storing the clustered nodes in the following steps.Step 2.
Select the node with the minimum coordinate from BNs as the start node(
v
s
t
), being marked as the current node of DW (denoted by v
c) and pushed into Q. Then v
c checks, from its N
1
(
v
c
)
⊂
B
N
s, whether there are any nodes whose absolute angles belong to [
3
π
/
2
,
2
π
]. If there exist any, v
c selects the node which has the minimum absolute angle as its inorder successor (denoted by v
s
u), and v
s
u, as the new v
c, is put into Q. Otherwise, change the scope of the absolute angle to [
0
,
π
/
2
] and repeat the above procedure. If there does not exist v
s
u in N
1
(
v
c
), then repeat the same searching process in N
2
(
v
c
).Step 3.
Repeat Step2 until v
c cannot find its v
s
u any longer; then change the scope of the absolute angle to [
π
/
2
,
π
] and execute the same procedure as in Step 1. Note that the first v
s
u found in this procedure is called the first inflection node; after that, the searching procedure will be continued within the scope [
0
,
π
].Step 4.
Ifv
s
u of v
c cannot be found in Step 3, change the scope of absolute angle to [
π
,
3
π
/
2
] and continue the searching process as in Step 3. In this procedure, the first found node is marked as the second inflection node, and then the searching process is continued within the scope [
π
/
2
,
3
π
/
2
].Step 5.
Whenv
s
u of v
c cannot be found in Step 4, change the scope of absolute angle to [
3
π
/
2
,
2
π
] and repeat the same searching procedure as in Step 4. If the first node found during the procedure is v
s
t or the one- or two-hop neighbor of v
s
t, then the searching procedure is done.
Each time the implementation from Step1 to Step 5 is over, a boundary cycle formed by selected nodes is identified. Of all the boundary cycles, the first identified is the outer boundary, while the rest are coverage holes.Step 6.
Check the queueQ; if there is any node in Q that has its two-hop neighbor as its v
s
u, insert a relay node that is the one-hop neighbor of both the node and its v
s
u. At the same time, the sum of the distance between the node and this relay node and the distance between the relay node and v
s
u should be the minimum.
Note that the relay node may be a non-BN.Step 7.
Remove all the nodes inQ and their one-hop neighbors from BNs.Step 8.
IfB
N
s
=
⌀, repeat the procedure from Steps 1 to 7 until the set of BNs is empty or the number of the remaining nodes in the set is δ (in our practice δ
=
2).We use Figure2 to describe the whole procedure of DW. We set queue Q
=
⌀. The node v
41, bearing the minimum coordinate in all BNs, is selected as v
s
t according to Steps 1 and 2, being marked as v
c and pushed into Q
(
Q
=
{
v
41
}
). Among the one-hop neighbors of v
c, v
42 is the best choice to be v
s
u of v
c according to Step 2; then v
42 takes the place of v
41 to become v
c and is pushed into Q
(
Q
=
{
v
41
,
v
42
}
). This process is executed repetitively until the first inflection point v
24 appears. Next, DW changes the searching direction according to Step 3 and continues the same procedure. When the second inflection point v
29 appears, DW changes the searching direction again according to Step 4 and repeats the same searching process until v
s
u of v
c is v
s
t or v
s
t
∈
N
1,2
(
v
c
); the searching process is over. In the following, DW finds that v
s
u of all nodes in Q are the one-hop neighbors of the nodes. Hence, the nodes enclosing the outer boundary are identified. Finally, DW removes all the nodes in Q
(
Q
=
{
v
41
–
44
,
v
21
–
40
}
) and their one-hop neighbors {
v
4
,
v
9
–
20
} from BNs. As a result, B
N
s
=
{
v
1
–
3
,
v
5
} are left.If DW findsB
N
s
≠
⌀ after the outer boundary is identified, it resets Q
=
⌀, selects v
5 as v
s
t, and then performs the following operation. v
5 is marked as v
c and pushed into Q. Then, v
c finds v
3 as its v
s
u, being marked as new v
c and pushed into Q. At the same time, DW detects that v
c is the first inflection node according to Step 3; therefore, it changes the searching scope and finds v
2 as its v
s
u as well as the second inflection node according to Step 4, with v
2 being taken as v
c and pushed into Q. Here, DW changes the searching scope again and finds v
1 as v
s
u of v
c. Hence, DW takes v
1 as new v
c and pushes it into Q. Next, v
c finds that v
5 is both its one-hop neighbor and v
s
t according to Step 5. Therefore, DW begins to check v
s
u of the nodes in Q. As a result, DW finds that v
s
u of v
3 and v
s
u of v
2 are their two-hop neighbors, respectively, so v
4 is inserted between v
5 and v
3 according to Step 6. Similarly, v
8 is inserted between v
2 and v
3. So far, all the nodes have their one-hop neighbors as their v
s
u in Q. That is to say, the nodes enclosing coverage holes are identified. In the following, DW removes all the clustered nodes in the second round of identification from BNs except v
4 and v
8 (v
4 and v
8 do not exist in BNs). At this moment, B
N
s
=
⌀, which means that the hole detection is over.


## 4.3. Theoretical Analysis

To prove the correctness of the implementation, we conduct the following theoretical analysis.Lemma 10.
Consider an ItNv
i, v
m, and v
n are any pair of adjacent neighbors (
v
m
,
v
n
∈
N
1,2
(
v
i
)
), and S
(
v
m
,
v
n
)
=
S
(
v
m
)
∩
S
(
v
n
), which is described as formula (7). If S
(
v
m
,
v
n
) is empty or S
(
v
m
,
v
n
) is not empty, the intersection of S
(
v
m
,
v
n
) with ∂
S
(
v
m
,
v
i
,
v
n
) is empty. That is, S
(
v
m
,
v
n
)
=
⌀ or (
S
(
v
m
,
v
n
)
≠
⌀
)
∧
(
S
(
v
m
,
v
n
)
∩
∂
S
(
v
m
,
v
i
,
v
n
)
=
⌀
); v
i is a BN: (7)
S
v
m
,
v
n
=
x
-
x
v
m
2
+
y
-
y
v
m
2
≤
R
s
2
x
-
x
v
n
2
+
y
-
y
v
n
2
≤
R
s
2
,where (
x
v
m
,
y
v
m
) and (
x
v
n
,
y
v
n
) are the coordinates of v
m and v
n, respectively, in the local CCS with v
i as the origin.Proof.
Given a nodev
i and any pair of adjacent neighbors v
m and v
n, we assume that v
m and v
n are located within the CCS with v
i as the origin. To prove the correctness of Lemma 10, we discuss it via the following three cases.
Case
1. If S
(
v
m
,
v
n
)
=
⌀, d
v
m
,
v
n
>
2
R
s. Hence, ∂
S
(
v
m
,
v
i
,
v
n
) cannot be fully covered by S
(
v
m
) and S
(
v
n
); thereby, v
i is a BN according to Definition 8. As shown in Figure 4, the blue shaded area represents the coverage hole.
Case
2. In another scenario, S
(
v
m
,
v
n
)
=
{
P
}, if point P lies on ∂
S
(
v
m
,
v
i
,
v
n
), ∂
S
(
v
m
,
v
i
,
v
n
) can be fully covered by S
(
v
m
) and S
(
v
n
). That is to say, there does not exist a hole in S
(
v
m
,
v
i
,
v
n
) and v
i is a non-BN, as shown in Figure 5(a). Otherwise, no matter whether P is inside or outside S
(
v
i
), there must be a hole at least around it. Hence, v
i is a BN, as shown in Figures 5(b), 5(c), and 5(d).
Case
3. In the third case, S
(
v
m
,
v
n
)
≠
⌀; whether holes exist is determined by the position of S
(
v
m
,
v
n
), if S
(
v
m
,
v
n
)
∩
∂
S
(
v
m
,
v
i
,
v
n
)
=
⌀, as shown in Figures 6(a) and 6(b); there must exist a hole and v
i is a BN. Otherwise, no holes exist and v
i is a non-BN, as shown in Figures 6(c), 6(d), 6(e), and 6(f).Figure 4
Illustration for Case1.Figure 5
Illustration for Case2.
(a)
No hole
(b)
Hole
(c)
Hole
(d)
HoleFigure 6
Illustration for Case3.
(a)
Hole
(b)
Hole
(c)
No hole
(d)
No hole
(e)
No hole
(f)
No holeLemma 11.
Considering an ItNv
i, S
(
v
i
) is divided into N
1,2
v
i by N
1,2
(
v
i
). If ∂
S
(
v
i
,
k
)
(
k
∈
{
1
,
…
,
N
1,2
v
i
}
) is not covered by the sensing areas of the neighbors of v
i, then v
i is a BN. Otherwise, it is a non-BN.Proof.
According to Definition5, S
(
v
i
) is divided into N
1,2
v
i sectors by the neighbors of v
i. If there exists a sector whose border cannot be covered by the sensing areas of the neighbors of v
i, according to Lemma 10 and Definition 8, node v
i is a BN. Otherwise, it is a non-BN.Lemma 12.
Given a sensor nodev
i, v
i is a BN if the absolute angle of a node in N
1,2
(
v
i
) meets any of the four cases: (a) ∠
a
b
s
(
v
i
,
N
1,2
v
i
)
≤
π, (b) ∠
a
b
s
(
v
i
,
1
)
>
π, (c) ∀
k
,
∠
a
b
s
(
v
i
,
k
)
∈
(
π
/
2
,
3
π
/
2
], and (d) ∀
k
,
∠
a
b
s
(
v
i
,
k
)
∈
[
0
,
π
/
2
]
∣
∠
a
b
s
(
v
i
,
k
)
∈
(
3
π
/
2
,
2
π
].Proof.
We prove Case (a) and the other cases can be proved in the same way. As shown in Figure7, nodes v
m and v
n are neighbors of node v
i. The three disk areas enclosed by the dashed lines are S
(
v
m
), S
(
v
i
), and S
(
v
n
), respectively. For v
m is the |
N
1,2
(
v
i
)
| neighbor of v
i, its absolute angle is the largest one. According to Case (a) of Lemma 12, ∠
a
b
s
(
v
i
,
v
m
)
≤
π. v
n is the adjacent node of v
m, and v
n
∈
N
1,2
(
v
i
); thus, ∠
a
b
s
(
v
i
,
v
n
)
<
∠
a
b
s
(
v
i
,
v
m
). The probable positions of v
m and v
n are shown in Figures 7(a), 7(b), and 7(c). In Figure 7(a), we assume that v
m, v
i, and v
n do not coincide with each other and they all lie on the x-axis and ∂
S
(
v
m
,
v
i
,
v
n
) can be completely covered by S
(
v
m
) and S
(
v
n
); meanwhile, S
(
v
m
)
∩
S
(
v
n
)
∩
S
(
v
i
)
=
{
P
1
,
P
2
}. In addition, the radii of S
(
v
m
), S
(
v
i
), and S
(
v
n
) are equal. Hence, if ∂
S
(
v
m
,
v
i
,
v
n
) can be fully covered, S
(
v
m
), S
(
v
i
), and S
(
v
n
) must coincide; in other words, d
v
m
,
P
2, d
v
i
,
P
2, and d
v
n
,
P
2 are equal. However, this contradicts with the assumption. Therefore, v
i is a BN when Case (a) is satisfied and all v
m, v
n, and v
i are on the x-axis. In Figures 7(b) and 7(c), we can clearly find that the blue shaded area cannot be covered by any sensors wherever v
m is located. Consequently, v
i is a BN when the position of N
1,2
(
v
i
) conforms to any case shown in Figures 7(b) and 7(c).Figure 7
Illustration for Lemma12.
(a)
∠
(
v
m
,
v
i
,
v
n
)
=
π
(b)
π
/
2
<
∠
(
v
m
,
v
i
,
v
n
)
<
π
(c)
0
<
∠
(
v
m
,
v
i
,
v
n
)
<
π
/
2Lemma 13.
The BNs clustered by DW depict the outer boundary and coverage holes of WSNs, respectively.Proof.
Because all the BNs located on the border of coverage holes and the outer boundary are identified by DSCS, we only need to cluster the BNs into different groups that map coverage holes and the outer boundary. Without loss of generality, within each group of the BNs, there must exist a BN with the minimum coordinate. Besides, the coverage holes lie within WSNs; hence, the BN with the minimum coordinate in all the BNs must lie on the border of the outer boundary. Therefore, the first identified boundary is the outer boundary. Similarly, the other boundary cycles identified in the subsequent rounds are coverage holes.


## 5. Experiments and Performance Evaluation

Both DSCS and DW are implemented in MATLAB 2013b on the platform of Windows 7. In the simulations, the sensor nodes are randomly deployed in a monitored square, the size of which is from100
m
×
100
m to 500
m
×
500
m. The number of the deployed nodes ranges from 200 to 2000 with the increment of 200. The communication radius of each node varies from 20 m to 50 m with the increment of 10
m. Besides, we compare our algorithms with the existing detection schemes, BRC and DHD, in terms of the correct detection rate, false detection rate, runtime, average energy dissipation, and algorithm complexity.Figure8 shows the simulation results in such a WSN that 2000 nodes are randomly deployed in a 500
m
×
500
m monitored area with coverage holes different in size, shape, and number. In Figure 8(c), the green points represent the BNs detected by DSCS and the purple represent the refined ones by DW from the detected BNs. Moreover, DW connects the refined BNs to form different holes and the outer boundary of the WSN. Compared with BRC and DHD, DSCS hardly has any noise points.Figure 8
The comparison of detection.
(a)
BRC
(b)
DHD
(c)
DSCS and DW
(d)
BRC
(e)
DHD
(f)
DSCS and DWLetB
N
c denote the correctly detected BNs and B
N
f  (
B
N
f
=
B
N
s
∖
B
N
c
) denote the falsely detected BNs. The correct detection rate and false detection rate can be determined by the following formula:(8)
c
o
r
r
e
c
t
R
a
t
e
=
B
N
c
B
N
s
×
100
%
,
f
a
l
s
e
R
a
t
e
=
B
N
f
B
N
s
×
100
%
.Figure9 lists all the correct detection rates and false detection rates of algorithms DSCS, BRC, and DHD. For convenience, we apply the data set offered by Simek et al. [19] in this simulation. It can be observed that the correct detection rate of DSCS always keeps at more than 92
% and the false detection rate keeps at less than 10
% in the simulations with various sizes and different average node degrees. Although the correct detection rate increases and the false detection rate decreases along with the ascent of average node degree in all algorithms, it is clearly found that the fluctuation of the correct detection rate and false detection rate of BRC and DHD is significantly higher than that of DSCS, which shows that DSCS has a better robustness in all the simulation cases.Figure 9
The comparison in terms of detection rate.
(a)
Nodes = 100
(b)
Nodes = 400
(c)
Nodes = 100
(d)
Nodes = 400As shown in Figures10(a) and 10(b), the number of BNs increases with the ascent of the size of the monitored area while it decreases with the ascent of the length of the communication radius. The reason is that when the same number of nodes is deployed in the monitored areas with different sizes, the node density decreases with the ascent of the size, which results in the reduction of the number of each node's neighbors and the enhancement of the BNs’ occurrence probability. On the contrary, the node density increases with the ascent of the length of the communication radius, which lowers the BNs’ occurrence probability. From Figure 10(c), we can clearly observe that the number of BNs detected by DSCS is neither the most nor the least, but the outer boundary and the coverage holes are identified more accurately.Figure 10
The comparison in terms of the number of detected BNs.
(a)
BNs detected in different sizes of WSNs
(b)
BNs detected under differentR
c
(c)
BNs detected by different algorithmsAs for the runtime, Figures11(a) and 11(b) show that it decreases with the enlargement of the monitored area and the reduction of the communication radius. The reason is that, given the number of nodes, the node density increases with the size reduction of the monitored area or the length increase of the communication radius. The increase of node density results in the fact that each node has to spend more time to transmit messages and compute its relation with the neighbors. As shown in Figure 11(c), although the runtime is increasing exponentially along with the ascent of the node number, the growth of runtime of DSCS and DW is slower than that of the other two algorithms.Figure 11
The comparison in terms of runtime.
(a)
Runtime in different sizes of monitored areas
(b)
Runtime under differentR
c
(c)
Runtime for different number of nodesAs a key factor to prolonging the lifetime of WSNs, the energy efficiency during the phase of identifying BNs is evaluated through figuring out the energy each node consumes. During the simulations, all the algorithms apply the energy dissipation model as depicted in [34, 35].Figure12(a) shows the average energy dissipation of DSCS and DW in the WSNs with the size ranging from 100 m × 100 m to 500 m × 500 m. It can be observed that the energy dissipation is inversely proportional to the size of the monitored area. The main reason is that each node needs to transmit more messages in the case of high node density. As mentioned in [34, 35], the dissipation of energy mainly concentrates on message transmission. Thus, the higher the node density is, the more the energy consumption is. Similarly, Figure 12(b) shows that the longer the communication radius is, the more the energy consumption is. In Figure 12(c), different algorithms show a common feature that the energy dissipation is proportional to the amount of nodes. However, the curves of DSCS and DW and BRC, especially of DSCS and DW, grow more smoothly than that of DHD. That is, DSCS is more energy-efficient than BRC and DHD. The same results are obtained from the comparison of remaining energy, as shown in Figure 12(d). The remaining energy of the nodes is the highest when DSCS and DW are employed.Figure 12
The comparison in terms of energy dissipation.
(a)
Energy dissipation in different areas
(b)
Energy dissipation under differentR
c
(c)
Energy dissipation by different algorithms
(d)
Remaining energy in different algorithmsTo fully evaluate the performance of DSCS and DW, the computation complexity is considered and illustrated in Table1. By the foregoing analysis, the implementation of DSCS and DW can be divided into five subprocedures, namely, collecting neighbor information, computing absolute angle per node, sorting nodes, identifying BNs, and connecting them to enclose holes. Correspondingly, their complexities are O
(
n
+
m
), O
(
n
), O
(
n
log
⁡
(
n
)
), O
(
k
n
), and O
(
a
(
B
N
s
)
), respectively. Here, n
=
V, m
=
E, k
=
21 (k represents the average node degree of WSN), a
=
4 (a denotes the number of coverage holes and the outer boundary of WSN), and B
N
s
=
226. Therefore, the overall complexity of DSCS and DW is O
(
34
n
+
m
+
904
), approximately equal to O
(
34
n
+
m
). The BRC is composed of choosing Good Neighbors and identifying BNs; their complexities are O
(
n
+
m
) and O
(
3
(
k
-
1
)
n
), respectively. For k
=
21, the overall computation complexity is O
(
60
n
+
m
). The DHD algorithm can be divided into two steps. Firstly, it needs to find a max independent set I; the complexity of the stage is O
(
n
+
m
). Secondly, every node of set I needs to serve as a seed to construct isocontours and the complexity of this stage is O
(
I
n
) and I
=
85. Hence, the overall computation complexity of DHD is O
(
m
+
86
n
). Obviously, the complexity of DSCS and DW is lower than that of the other two algorithms.Table 1
The comparison in terms of algorithm complexity.
Algorithm
Subprocedure
Complexity
Overall complexity
DSCS and DW
Collecting neighboring information
O
n
+
m
O
34
n
+
m
Computing absolute angle per node
O
n
Sorting nodes
O
n
log
⁡
n
Identifying BNs
O
k
n
Connecting BNs that enclose holes
O
a
|
B
N
s
|
BRC
Choosing Good Neighbors
O
n
+
m
O
60
n
+
m
Identifying BNs
O
3
k
-
1
n
DHD
Finding max independent set
O
n
+
m
O
86
n
+
m
Creating isocontours
O
|
I
|
n


## 6.  Conclusions

In this paper, DSCS and DW are proposed for identifying boundary nodes and coverage holes in a WSN where nodes are randomly distributed. Besides, we simulate various scenarios and evaluate the proposed algorithms from different aspects, including detection rate, runtime, energy efficiency, and algorithm complexity. In the performance evaluation, the effects from the size of WSN and the length of communication radius are taken into account. Simulation results show that DSCS bears the inspiring performance for detecting boundary nodes and DW works well in identifying coverage holes of different sizes and shapes. The algorithms developed in our work are effective in healing coverage holes, improving data forwarding efficiency, and prolonging the lifetime of WSN.



---

*Source: 8310296-2016-02-21.xml*