# A Novel Nonlinear Multitargetk-Degree Coverage Preservation Protocol in Wireless Sensor Networks

Authors: Zeyu Sun; Xiaofei Xing; Chuanfeng Li; Yalin Nie; Yangjie Cao
Journal: Journal of Sensors
 (2016)

---

## Abstract

Due to the existence of a large number of redundant data in the process of covering multiple targets, the effective coverage of monitored region decreases, causing the network to consume more energy. To solve this problem, this paper proposes a multitargetk-degree coverage preservation protocol. Firstly, the affiliation between the sensor nodes and target nodes is established in the network model; meanwhile the method used to calculate the coverage expectation value of the monitored region is put forward; secondly, in the aspect of the network energy conversion, use scheduling mechanisms on the sensor nodes to balance the network energy and achieve different network coverage quality with energy conversion between different nodes. Finally, simulation results show that NMCP can improve the network lifetime by effectively reducing the number of active nodes to meet certain coverage requirements.


---

## Body

## 1. Introduction

With the rapid development of technology [1], wireless sensor network technology has developed exponentially [2, 3]. Wireless sensor network is a network system comprised of a large number of cheap sensor nodes that are randomly deployed and are self-organized [4–6]. A sensor node is characterized with such abilities as computation, perception, communication, storage, and control; the behavior characteristics of sensor nodes indicate that they are part of the network service system fusing the physical world and the information world, realizing collection, computation, communication, and control of data [7, 8]. In the engineering field, wireless sensor networks are widely used in many areas like military surveillance, transportation, health care, environmental monitoring, and rescue work and in other fields [9, 10]. The multilevel (k-degree) coverage is given, as an example, in Figure 1.Figure 1
k-degree coverage diagram.Two vital performance criteria that are required are coverage quality and energy management, which are also hot issues in the field of wireless sensor networks [11, 12]. Coverage as its name implies means effectively covering the target nodes instead of the global monitored region. The coverage quality not only affects the degree of concern to the target nodes directly, but also affects the entire network lifetime and QOS (Quality of Services) directly [13–15]. The k-degree coverage mode is used in the process of covering multitarget nodes. Generally, the sensor nodes are deployed in the monitored region randomly, and, because of this, a large number of sensor nodes may be located in the monitored region [16, 17], which will generate a large number of redundant nodes, interfering with the communication channel and also reducing the communication ability between nodes, thereby speeding up the network energy consumption.


## 2. Related Works

Coverage control technology is an important basic research issue and is one of the hotspots in the field of wireless sensor network, and coverage quality affects the network lifetime directly [18]. In recent years, many experts at home and abroad have carried out research on the coverage technology in wireless sensor network elaborately and profoundly as it was developed and widely used. Reference [19] proposed the artificial bee colony algorithm and particle swarm algorithm deploying the nodes in the whole monitored network and optimized the global coverage with both the intelligent algorithms in the coverage optimization phase, ultimately finishing the complete coverage over the monitored area. In terms of energy consumption, node energy conversion was scheduled with heuristic node scheduling algorithm, thereby improving the network lifetime. Literature [20] proposed a method to construct connectivity coverage protocol. The protocol defined the ratio between network coverage quality, network connectivity, and the performance indexes of the network infrastructure parameters, as well as constructing the SCA (Scheduling Control Algorithm) to meet the need of ensuring the whole network connectivity with minimum number of nodes in the problem-solving process, ultimately achieving the goal of network energy consumption balancing. Literature [21] put forward a kind of effective coverage area hole repair algorithm based on Voronoi. On the premise of certain coverage quality, this algorithm improved the coverage rate by increasing working nodes to coverage hole; in the meantime, it found the proper location information for mending, guaranteeing the whole network connectivity; by researching the Voronoi diagram, literature [22] also completed covering the monitored region, finding the solution to disc location of sensor nodes formed by the geometric variation parameters in the Voronoi diagram with related geometric theory. Literature [23] introduced local parameter α and formed local α-coverage with the idea of partial coverage optimization and then, after a series of calculations with α, achieved global coverage optimization. The algorithms above can effectively cover the monitored region to some extent. However, the three algorithms have some problems in common: they all need large amount of calculation, the algorithms are highly complex, and they have poor scalability in a wireless sensor network. Literature [24, 25] proposed methods to calculate coverage rate in different monitored domain by effectively computing target nodes in monitored region, using different angle of sector formed by the sensor node and destination node. The above four algorithms have good feasibility and stability, as well as high network scalability; but their network models are too idealistic in the process of research: literature [22, 23] employed static target nodes as the research object; literature [25] did not consider the k-degree coverage situation of the moving related target nodes. Literature [26] put forward an energy efficient multitarget covering algorithm based on linear rule. The algorithm utilized a clustered structure system to solve the problem of multitarget covering. It presented an optimal solution to covering the target node in a linear fashion by calculating the coverage ability of the sensors and their remaining energy. Literature [27] proposed a coverage algorithm based on event driven mechanism. In this algorithm, the coverage and expectations of the nodes were calculated using the probability model, and then the calculation result was optimized to achieve optimal coverage on target nodes. Although these two algorithms can achieve the goal of optimal coverage on targets nodes and prolong the network lifetime, the requirement conditions for covering are quite strict. Furthermore, the algorithm is highly complex in itself. In order to cover the monitored region more effectively, based on the study in literature [24, 25], we present a nonlinear multiobjective coverage protocol (NMCP) which is given in this paper. This protocol can effectively calculate the coverage expectation value of the sensor nodes for the moving target nodes. In terms of energy, we compare the energy consumption under the multilateral connection and unilateral connection based on global network nodes energy analysis; namely, the energy cost in multipoint transmission is not higher than single-node energy consumption. In terms of energy conversion, it was completed between nodes with self-scheduling mechanism, thereby prolonging the lifetime of the entire network. At last, this paper gives the comparison process between NMCP algorithm and other algorithms in simulation experiments, which show that the NMCP algorithm is more effective and steadier.


## 3. Network Model and Coverage Quality

To study the wireless sensor network coverage problem better, as well as facilitate studying the NMCP algorithm, in this paper, we make the following assumptions:(1)
Each sensor node has certain perception ability, and their perception range and communication range are both circles.
(2)
The perception range of a sensor node is far shorter than side length of the monitored region.
(3)
Initially, all sensor nodes have the same energy and are clock synchronized.
(4)
The location information of sensor nodes can be obtained with GPS.
(5)
A sensor node’s perception radius is subject to normal distribution.


### 3.1. Basic Definitions

Definition 1 (target coverage).
In the two-dimensional plane, each target node is covered by at least one sensor node, which is called the target coverage.Definition 2 (k-degree coverage).
In a monitored region, if each target node is covered byk sensor nodes, it is called k-degree coverage.Definition 3 (network lifetime).
The time span from when a network begins running to when none target node is covered by the sensor nodes is called the network lifetime.Definition 4 (coverage quality).
In the two-dimensional plane, the ratio of the total perception area of all sensor nodes to the monitored region is known as coverage quality.


### 3.2. Coverage Quality

Theorem 5.
Suppose each sensor node’s coverage rate isp. Let k
=
2 in k-degree coverage, andm,n are the moving frequency of sensor nodes, the occurrence probability of which is p
2
q
n
-
2, and the conditional probability is p
q
n
-
m
-
1, where q
=
1
-
p.Proof.
LetX be the number the node moves in the first round; letY be that of the second round. According to the question, the target node is covered by sensor nodes in themth time during the first round and is covered twice in the nth time, with the remaining n
-
2 times not covered, during the second round.
Therefore, the sensor node probability is(1)
P
X
=
m
,
Y
=
n
=
p
2
q
n
-
2
.
The joint probability of both rounds is(2)
P
X
=
m
=
∑
n
=
m
+
1
∞
P
X
=
m
,
Y
=
n
=
∑
n
=
m
+
1
∞
p
2
q
n
-
2
=
p
q
m
-
1
,
P
X
=
n
=
∑
m
=
1
n
-
1
P
X
=
m
,
Y
=
n
=
∑
m
=
1
n
-
1
p
2
q
n
-
2
=
n
-
1
p
2
q
n
-
2
.
According to multiplication formula of probability, we get(3)
P
Y
=
n
∣
X
=
m
=
P
X
=
m
,
Y
=
n
P
X
=
m
=
p
2
q
n
-
2
p
q
m
-
1
=
p
q
n
-
m
-
1
.
The process to prove is complete.Theorem 6.
If the coverage rate of each sensor node isp, then the coverage rate at any point in a two-dimensional plane is P
(
n
A
)
=
1
-
1
-
p
n.Proof.
We will use mathematical induction in the proof. In the two-dimensional plane, any sensor node is not independent, so, according to the probability theory, whenk
=
2, we have(4)
P
A
+
A
=
p
A
+
p
A
-
p
A
p
A
=
1
-
1
-
p
2
.
Whenk
=
3, the joint coverage is(5)
P
A
+
A
+
A
=
p
A
+
A
+
p
A
-
p
A
+
A
p
A
.
Substitute formula (5) into formula (4); we have(6)
P
A
+
A
+
A
=
1
-
1
-
p
3
.
Whenk
=
i, by formula (6), we get(7)
P
n
A
=
1
-
1
-
p
n
.
The process to prove is complete.Corollary 7.
In the two-dimensional plane, suppose the sensor node coverage rate isp, and N is the maximum value of the continuous coverage number of a sensor node. Until the moving target node is covered, the sensor node coverage expectation is E
(
X
)
=
1
-
1
-
p
N
p
-
1.Proof.
In the two-dimensional plane, suppose the frequency a target node moves by isX. Because N is the maximum value of the continuous coverage number of a sensor node, the possible value range of X is X
∈
[
1,2
,
3
,
…
,
N
]. When X
=
m, and 1
≤
m
≤
N
-
1 is satisfied, namely, in the first N
-
1 times, the moving target node is not covered by the sensor nodes; we can get the distribution density function of X according to probability theory:(8)
P
X
=
k
=
p
1
-
p
k
-
1
k
=
1,2
,
3
,
…
,
N
-
1
1
-
p
N
-
1
k
=
N
.
Namely,(9)
E
X
=
∑
k
=
1
N
-
1
k
p
1
-
p
k
-
1
+
N
1
-
p
N
-
1
.
Supposeq
=
1
-
p, S
=
∑
k
=
1
N
-
1
k
1
-
p
k
-
1; then S
=
∑
k
=
1
N
-
1
k
q
k
-
1; multiplying both sides of the equation by q, we get(10)
q
S
=
∑
k
=
1
N
-
1
k
q
k
.
Namely,(11)
1
-
p
S
=
∑
k
=
1
N
-
2
q
k
-
N
-
1
q
N
-
1
=
1
-
q
N
-
1
1
-
q
-
N
-
1
q
N
-
1
,
S
=
1
-
q
N
-
1
1
-
q
2
-
N
-
1
q
N
-
1
1
-
q
=
1
-
1
-
p
N
-
1
p
2
-
N
-
1
1
-
p
N
-
1
p
.
SubstituteS into formula (9); we have(12)
E
X
=
p
1
-
1
-
p
N
-
1
p
2
-
N
-
1
1
-
p
N
-
1
p
+
N
1
-
p
N
-
1
=
1
-
1
-
p
N
p
-
1
.
After the sensor nodes cover the monitored region during time spant, they will inevitably have some energy consumptions, which results in the change in their coverage areas. In order to improve effective coverage on the target nodes concerned, in the process where sensor nodes consume energy, the total monitored region can be effectively covered, or all the concerned target nodes are effectively covered, as long as the sequence collection of the coverage areas of sensor nodes is not less than the total monitored area after their energy is consumed.Theorem 8.
In the two-dimensional plane, suppose the fitting function of a sensor node energy consumption isf
(
x
,
y
); the coverage area is S
n after the energy attenuation, where n
∈
[
1,2
,
3
,
…
,
N
]; then the bounded closed region formed is able to cover the entire monitored region; namely, ∬
S
f
x
,
y
d
x
d
y
=
lim
x
→
∞
⁡
∬
S
n
f
x
,
y
d
x
d
y.Proof.
Take a bounded closed region sequenceS
n
′, which covers the whole monitored region. Suppose S
1
′
⊂
S
2
′
⊂
S
3
′
⋯
S
n
′
⊂
⋯
S
n. Because the energy attenuation function is nonnegative, the integral sequence ∬
S
n
′
f
x
,
y
d
x
d
y is increasing; suppose the limit is as follows: (13)
I
=
lim
x
→
∞
⁡
∬
S
n
′
f
x
,
y
d
x
d
y
.
Therefore, we just need to prove(14)
lim
x
→
∞
⁡
∬
S
n
f
x
,
y
d
x
d
y
=
I
,where factor I is a finite set of numbers. For any ε
>
0, formula (13) shows that there is a number N; when n
≥
N, formula (15) is always satisfied:(15)
I
-
ε
<
lim
x
→
∞
⁡
∬
S
n
′
f
x
,
y
d
x
d
y
<
I
+
ε
.
Suppose there isn
0, when n
≥
n
0, S
n
⊃
S
n
′. Therefore, according to the nonnegative f
(
x
,
y
) and formula (15), we know that(16)
∬
S
f
x
,
y
d
x
d
y
≥
lim
x
→
∞
⁡
∬
S
n
′
f
x
,
y
d
x
d
y
>
I
-
ε
.
For each fixedn
≥
n
0, on the other hand, there must be a number which tends to infinity; suppose the number is k
n, and S
k
n
′
⊃
S
n; then by formula (15) we get(17)
∬
S
f
x
,
y
d
x
d
y
≤
lim
x
→
∞
⁡
∬
S
k
n
′
f
x
,
y
d
x
d
y
<
I
+
ε
.
Namely, whenn
≥
n
0, we get(18)
I
-
ε
<
lim
x
→
∞
⁡
∬
S
n
f
x
,
y
d
x
d
y
<
I
+
ε
.
Therefore, formula (14) is satisfied.
Now, letI
=
+
∞; for any M
>
0, formula (13) shows that there is N
1 and(19)
∬
S
N
1
′
f
x
,
y
d
x
d
y
>
M
.
And because there isn
1, when n
≥
n
1, S
n
⊃
S
N
1
′ is always satisfied, so we have(20)
∬
S
f
x
,
y
d
x
d
y
≥
∬
S
N
1
′
f
x
,
y
d
x
d
y
>
M
.
The process to prove is complete.


## 3.1. Basic Definitions

Definition 1 (target coverage).
In the two-dimensional plane, each target node is covered by at least one sensor node, which is called the target coverage.Definition 2 (k-degree coverage).
In a monitored region, if each target node is covered byk sensor nodes, it is called k-degree coverage.Definition 3 (network lifetime).
The time span from when a network begins running to when none target node is covered by the sensor nodes is called the network lifetime.Definition 4 (coverage quality).
In the two-dimensional plane, the ratio of the total perception area of all sensor nodes to the monitored region is known as coverage quality.


## 3.2. Coverage Quality

Theorem 5.
Suppose each sensor node’s coverage rate isp. Let k
=
2 in k-degree coverage, andm,n are the moving frequency of sensor nodes, the occurrence probability of which is p
2
q
n
-
2, and the conditional probability is p
q
n
-
m
-
1, where q
=
1
-
p.Proof.
LetX be the number the node moves in the first round; letY be that of the second round. According to the question, the target node is covered by sensor nodes in themth time during the first round and is covered twice in the nth time, with the remaining n
-
2 times not covered, during the second round.
Therefore, the sensor node probability is(1)
P
X
=
m
,
Y
=
n
=
p
2
q
n
-
2
.
The joint probability of both rounds is(2)
P
X
=
m
=
∑
n
=
m
+
1
∞
P
X
=
m
,
Y
=
n
=
∑
n
=
m
+
1
∞
p
2
q
n
-
2
=
p
q
m
-
1
,
P
X
=
n
=
∑
m
=
1
n
-
1
P
X
=
m
,
Y
=
n
=
∑
m
=
1
n
-
1
p
2
q
n
-
2
=
n
-
1
p
2
q
n
-
2
.
According to multiplication formula of probability, we get(3)
P
Y
=
n
∣
X
=
m
=
P
X
=
m
,
Y
=
n
P
X
=
m
=
p
2
q
n
-
2
p
q
m
-
1
=
p
q
n
-
m
-
1
.
The process to prove is complete.Theorem 6.
If the coverage rate of each sensor node isp, then the coverage rate at any point in a two-dimensional plane is P
(
n
A
)
=
1
-
1
-
p
n.Proof.
We will use mathematical induction in the proof. In the two-dimensional plane, any sensor node is not independent, so, according to the probability theory, whenk
=
2, we have(4)
P
A
+
A
=
p
A
+
p
A
-
p
A
p
A
=
1
-
1
-
p
2
.
Whenk
=
3, the joint coverage is(5)
P
A
+
A
+
A
=
p
A
+
A
+
p
A
-
p
A
+
A
p
A
.
Substitute formula (5) into formula (4); we have(6)
P
A
+
A
+
A
=
1
-
1
-
p
3
.
Whenk
=
i, by formula (6), we get(7)
P
n
A
=
1
-
1
-
p
n
.
The process to prove is complete.Corollary 7.
In the two-dimensional plane, suppose the sensor node coverage rate isp, and N is the maximum value of the continuous coverage number of a sensor node. Until the moving target node is covered, the sensor node coverage expectation is E
(
X
)
=
1
-
1
-
p
N
p
-
1.Proof.
In the two-dimensional plane, suppose the frequency a target node moves by isX. Because N is the maximum value of the continuous coverage number of a sensor node, the possible value range of X is X
∈
[
1,2
,
3
,
…
,
N
]. When X
=
m, and 1
≤
m
≤
N
-
1 is satisfied, namely, in the first N
-
1 times, the moving target node is not covered by the sensor nodes; we can get the distribution density function of X according to probability theory:(8)
P
X
=
k
=
p
1
-
p
k
-
1
k
=
1,2
,
3
,
…
,
N
-
1
1
-
p
N
-
1
k
=
N
.
Namely,(9)
E
X
=
∑
k
=
1
N
-
1
k
p
1
-
p
k
-
1
+
N
1
-
p
N
-
1
.
Supposeq
=
1
-
p, S
=
∑
k
=
1
N
-
1
k
1
-
p
k
-
1; then S
=
∑
k
=
1
N
-
1
k
q
k
-
1; multiplying both sides of the equation by q, we get(10)
q
S
=
∑
k
=
1
N
-
1
k
q
k
.
Namely,(11)
1
-
p
S
=
∑
k
=
1
N
-
2
q
k
-
N
-
1
q
N
-
1
=
1
-
q
N
-
1
1
-
q
-
N
-
1
q
N
-
1
,
S
=
1
-
q
N
-
1
1
-
q
2
-
N
-
1
q
N
-
1
1
-
q
=
1
-
1
-
p
N
-
1
p
2
-
N
-
1
1
-
p
N
-
1
p
.
SubstituteS into formula (9); we have(12)
E
X
=
p
1
-
1
-
p
N
-
1
p
2
-
N
-
1
1
-
p
N
-
1
p
+
N
1
-
p
N
-
1
=
1
-
1
-
p
N
p
-
1
.
After the sensor nodes cover the monitored region during time spant, they will inevitably have some energy consumptions, which results in the change in their coverage areas. In order to improve effective coverage on the target nodes concerned, in the process where sensor nodes consume energy, the total monitored region can be effectively covered, or all the concerned target nodes are effectively covered, as long as the sequence collection of the coverage areas of sensor nodes is not less than the total monitored area after their energy is consumed.Theorem 8.
In the two-dimensional plane, suppose the fitting function of a sensor node energy consumption isf
(
x
,
y
); the coverage area is S
n after the energy attenuation, where n
∈
[
1,2
,
3
,
…
,
N
]; then the bounded closed region formed is able to cover the entire monitored region; namely, ∬
S
f
x
,
y
d
x
d
y
=
lim
x
→
∞
⁡
∬
S
n
f
x
,
y
d
x
d
y.Proof.
Take a bounded closed region sequenceS
n
′, which covers the whole monitored region. Suppose S
1
′
⊂
S
2
′
⊂
S
3
′
⋯
S
n
′
⊂
⋯
S
n. Because the energy attenuation function is nonnegative, the integral sequence ∬
S
n
′
f
x
,
y
d
x
d
y is increasing; suppose the limit is as follows: (13)
I
=
lim
x
→
∞
⁡
∬
S
n
′
f
x
,
y
d
x
d
y
.
Therefore, we just need to prove(14)
lim
x
→
∞
⁡
∬
S
n
f
x
,
y
d
x
d
y
=
I
,where factor I is a finite set of numbers. For any ε
>
0, formula (13) shows that there is a number N; when n
≥
N, formula (15) is always satisfied:(15)
I
-
ε
<
lim
x
→
∞
⁡
∬
S
n
′
f
x
,
y
d
x
d
y
<
I
+
ε
.
Suppose there isn
0, when n
≥
n
0, S
n
⊃
S
n
′. Therefore, according to the nonnegative f
(
x
,
y
) and formula (15), we know that(16)
∬
S
f
x
,
y
d
x
d
y
≥
lim
x
→
∞
⁡
∬
S
n
′
f
x
,
y
d
x
d
y
>
I
-
ε
.
For each fixedn
≥
n
0, on the other hand, there must be a number which tends to infinity; suppose the number is k
n, and S
k
n
′
⊃
S
n; then by formula (15) we get(17)
∬
S
f
x
,
y
d
x
d
y
≤
lim
x
→
∞
⁡
∬
S
k
n
′
f
x
,
y
d
x
d
y
<
I
+
ε
.
Namely, whenn
≥
n
0, we get(18)
I
-
ε
<
lim
x
→
∞
⁡
∬
S
n
f
x
,
y
d
x
d
y
<
I
+
ε
.
Therefore, formula (14) is satisfied.
Now, letI
=
+
∞; for any M
>
0, formula (13) shows that there is N
1 and(19)
∬
S
N
1
′
f
x
,
y
d
x
d
y
>
M
.
And because there isn
1, when n
≥
n
1, S
n
⊃
S
N
1
′ is always satisfied, so we have(20)
∬
S
f
x
,
y
d
x
d
y
≥
∬
S
N
1
′
f
x
,
y
d
x
d
y
>
M
.
The process to prove is complete.


## 4. NMCP Protocol

### 4.1. Energy Conversion

For a sensor node, the energy consumption mainly happens in the sensing module and the communication module. When collectingl bits data, the energy consumption of sensing module E
T and the communication module E
R is as follows:(21)
E
T
l
,
d
=
l
E
T
-elec
+
l
ε
f
s
d
2
,
d
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
4
,
d
≥
d
0
.The energy consumption model for receiver module is(22)
E
R
l
=
E
R
-elec
l
=
l
E
e
l
e
c
,where l bits are the fixed length of data transmitted, d represents the communication Euclidean distance between sensor nodes, and d
0 represents the threshold or proportional quantity of the communication distance between sensor nodes. When the communication distance between sensor nodes is less than d
0, the energy attenuation index value is 2; otherwise it is 4.Definition 9 (optimum subset).
LetG be the set of wireless sensor network’s sensor nodes; G
1 is called an optimum subset where G
1 is a subset of sensor nodes, namely, G
1
⊂
G, and all the sensor nodes in G
1 cover target set T entirely.Definition 10 (energy property).
W
=
{
w
1
,
w
2
,
w
3
,
…
,
w
n
} is the initial energy collection of sensor nodes; W follows W
~
N
(
μ
,
σ
2
) normal distributions, where w
i denotes the initial energy of sensor node s
i.Definition 11 (the maximum distortion).
On the premise that certain coverage rate is met, the maximum distortion is(23)
E
s
1
x
,
y
-
s
x
,
y
2
≤
D
∀
s
i
x
,
y
∈
A
.
s
1
(
x
,
y
) is the estimated Euclidean distance between a sensor node and the target node, while s
(
x
,
y
) is the average measured distance, Euclidean distance, between the sensor node and the target node.Theorem 12.
The communication distance between nodes is less than or equal to half the difference between variance and the distortion.Proof.
Suppose the measured distance at the target nodet
(
x
,
y
) is s
(
x
,
y
), the data information used contains the measured data, and when multitarget nodes are measured, the average of measured values follows normal distribution. The energy collection set of preset-energy sensor nodes is W
=
{
w
1
,
w
2
,
w
3
,
…
,
w
n
}. Then the Euclidean distance between communication nodes is as follows:(24)
R
x
1
,
y
1
,
x
2
,
y
2
=
x
1
-
x
2
2
+
y
1
-
y
2
2
=
E
S
x
1
,
y
1
-
u
S
x
2
,
y
2
-
u
=
R
d
.
LetH be the set of sensor nodes which collects information, and let H
1 be the complementary set ofH; the sensor node nearest to the target node in H is used to calculate the measured distance which is then used to estimate a signal data in H
1. Therefore, the estimated signal value at the target node point (
x
,
y
) is s
1
(
x
0
,
y
0
); namely,(25)
s
1
x
0
,
y
0
=
s
x
1
,
y
2
.
According to formulas (23) and (24), we have(26)
E
s
x
0
,
y
0
-
μ
s
u
,
v
-
μ
=
2
σ
2
-
2
R
d
x
0
,
y
0
,
u
,
v
.
Substitute formula (23) into formula (26); we have(27)
R
d
x
0
,
y
0
,
u
,
v
≤
σ
2
-
D
2
.
The process to prove is complete.Theorem 13.
In initial state, when transmittingl-bit data, the energy consumed in multilateral transmission is more than that consumed in unilateral transmission.Proof.
Suppose the current working nodeS
i has a set of neighbour nodes namedZ, in which each node corresponds to neighbour S
z. For convenience, the calculations start with 3, which denotes the number of neighbours in the collection, when n
→
∞. We will prove that using mathematical induction, as shown in Figure 2.
LetA be the source node, letD be the convergence node, letB,C be the neighbour nodes, and letO be the disk centre; the network storesl-bit data of any sequence, which is going to be sent from sourceA to convergence nodeD. Two kinds of circumstances are discussed as follows.
The First Case:From A to D Directly. According to formula (21), the energy dissipations are as follows when source nodeA sends out data:(28)
E
T
x
_
A
D
l
,
d
A
D
=
l
E
T
-elec
+
l
ε
f
s
d
A
D
2
,
d
A
D
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
A
D
4
,
d
A
D
≥
d
0
.
The Second Case: From A to B, Then From B to D. We prove that with mathematical induction: when k
=
3, from nodeA to nodeB, the energy consumption model of the transmitting module in nodeA is (29)
E
T
x
_
A
B
l
,
d
A
B
=
l
E
T
-elec
+
l
ε
f
s
d
A
B
2
,
d
A
B
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
A
B
4
,
d
A
B
≥
d
0
,
E
R
x
_
B
l
=
l
E
e
l
e
c
.
The energy consumed by nodeB to receive the information is(30)
E
T
x
_
B
D
l
,
d
B
D
=
l
E
T
-elec
+
l
ε
f
s
d
B
D
2
,
d
B
D
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
B
D
4
,
d
B
D
≥
d
0
.
So far, the total energy consumption of nodes on the pathA-B-D is(31)
E
T
o
t
a
l
=
E
T
x
_
A
B
+
E
R
x
_
B
+
E
T
x
_
B
C
.
In their initial state, the nodes work with the same amount of energy and are independent from each other. The basic properties of triangle show that(32)
E
T
o
t
a
l
=
E
T
x
_
A
B
+
E
R
x
_
B
+
E
T
x
_
B
D
<
E
T
x
_
A
D
.
Namely, whenk
=
3, node energy consumption in multilateral data transmission is lower than that in unilateral data transmission, so when k
=
3, the inequality is satisfied.
First, take the path fromA toB, thenB toC, andC toD (A-B-C-D), as an example to prove, and then add to n
→
∞. Because ∠
α
>
∠
A
C
D
=
π
/
2, ∠
α is an obtuse angle. Conclusion can be drawn with cosine theorem as: cos
⁡
∠
α
<
0; namely, B
C
2
+
C
D
2
<
B
D
2, when n
→
∞. The adjacent neighbour nodes can be combined into an obtuse triangle, in which the square of the length of the side opposite to the acute angle is less than the sum of the squares of the lengths of the sides of the obtuse angles. After n
-
2 times of superposition calculation, we eventually get B
C
2
+
C
D
2
<
B
D
2; namely, (33)
E
T
x
_
A
B
+
E
R
x
_
B
+
⋯
+
E
R
x
_
n
-
1
+
E
T
x
_
n
-
1
,
n
<
⋯
<
E
T
x
_
A
B
+
E
R
x
_
B
+
E
T
x
_
B
D
<
E
T
x
_
A
D
.
The process to prove is complete.Figure 2
Multilateral and unilateral node connection diagram.Energy consumed in multilateral transmission is not higher than the energy dissipation in unilateral transmission in a multiple hops path in wireless sensor network [28–30]. But practically, it is always hard to implement the single hop transmission between the source node and the convergence node due to the limited communication radius of nodes, obstacles, and the variation of environment.NMCP algorithm takes the network running time round number as the basic unit, each round containing two aspects, namely, coverage control information and the stable state information of nodes. In working stage, the working nodes remain on, and all redundant nodes are off so as to save the network energy. At stable stage, each node has five kinds of running state, which are judge, compete, wait, start, and sleep states [31–33]. Judge state: at the beginning of each time round, nodes are in the state of judgment. When redundant judging condition of a node is satisfied, the node enters sleep state; otherwise, if the condition is not satisfied, it enters the compete state; compete state: a node which succeeds on the start-up of a competition may convert into the state of working, whereas the unsuccessful nodes enter the state of wait; wait state: those nodes failed in the competition to enter wait state, and when they successfully receive the on-duty message from their neighbours during initiating, they update the message of their own locally and then enter judge state. Start state: when a node wins in the competition, it enters the start state. By calculating the node coverage, whether the nodes which perception regions are in start states satisfy the requirements for coverage is determined. If not satisfied, it sends on-duty message for schedule and then enters judge state; sleep state: while the redundant judging conditions are satisfied, the node enters sleep state to reduce its energy consumption and enters judge state in the unit time round. When the density of nodes is too large in a monitored region, the vast majority of the nodes in the region will satisfy the redundant node judgment conditions. At the moment, all those nodes will enter sleep states. Although this state can reduce the node energy consumption, there are still some deficiencies; the reason for this is that once perceiving neighbour nodes enter sleep state, there will be large coverage blind area in monitored region; therefore the coverage quality is decreased [34–37]. In order to avoid such kind of situation, NMCP algorithm uses a mechanism that once a node enters sleep state, it wakes up its neighbour nodes immediately and converts them into wait states. The aim is to reduce the density of working nodes first, namely, select a node as a candidate working node directly; the other nodes not selected enter sleep states directly and then schedules in the candidate working nodes [38]. Each candidate working node elects itself with a probability of p, whereas those nodes which are not chosen directly enter sleep state and then work as candidate nodes in the redundant nodes. Each candidate node elects itself to enter the prework state, whereas those candidate nodes which are not elected enter presleep state. The state transition between the five states in the covering control phase is as shown in Figure 3.Figure 3
The state transition diagram.


### 4.2. The Basic Idea of NMCP Algorithm

Based on the idea in literature [10] by means of clustering theory, this algorithm divides the coverage region in the monitored region into several clusters, each head node of a cluster being in charge of and controlling the member nodes in its cluster. At the initial stage of the network operation, the cluster members send “k-degree Coverage” message to their cluster head node first, while the cluster header maintains a linked list CL which receives the messages which are composed of the sensor node ID and such properties as its perception range and energy attenuation. After one or more cycles, the cluster header will collect all the cluster members information, then sort the list according to the size of the residual energy of nodes, as well as assigning to weight the first few nodes in the front of the list; after that, it scans every item in the linked list and marks the sensor nodes which are capable of covering the target node. Finally, the cluster header sends “k-Notice” messages to those marked member nodes which are responsible for covering the target node. The cluster head node sends on-duty messages to the member nodes and neighbour nodes to awaken those members nodes to enter waiting state and notify the neighbour cluster head nodes of the monitored information of the target. Based on the above information, the weighting of member nodes participating in the monitoring is calculated. If its weighting is greater than the set threshold, the node would enter into active state and monitor any moving target within its sensing range. Active nodes around the target will form an initial dynamic cover group. Member nodes will send an information packet to the cluster head node. The data packet contains information as time stamp, node ID, and distance between the nodes and the target. As there may be more than one cluster head node in NMCP, for the convenience of management, one of the cluster head nodes will be selected as managing node and is responsible for the information fusion and data management. Because the target node is moving in the monitoring area, the initial NMCP may not meet the requirements of target monitoring. Therefore, dynamic reconstruction is needed according to the position of the target. Reconstruction process is completed by members updating management and head node reselecting. When the target moves to a new grid, new cluster head node and member nodes that meet the requirements of the threshold weighting joint to the original NMCP, and the newly jointed cluster head node is elected as the leader node. Nodes within the original NMCP that cannot meet the monitoring requirements will quit the NMCP. If the original managing node happens to be a quitting node, at this time, the original managing node needs to send information of target location and member’s nodes to the new managing node. When the target moves away from the original location, the cluster head node will broadcast messages to its member nodes to enter into sleep state to save power consumption.


### 4.3. NMCP Algorithm Description

Step 1.
Calculate the perception intensity of cluster members.Step 2.
The cluster member nodes send “k-Coverage” to the cluster header node. After one or more time units, the header node receives the message from cluster members.Step 3.
The cluster head node establishes a linked list and stores the information collected in it and then sorts the list according to the amount of energy in the sensor nodes; at the same time it assigns weights to those nodes which have higher energy.Step 4.
Find qualified sensor nodes, and mark them.Step 5.
If the target node is in the state ofk-coverage, the cluster header will traverse the list to turn off those sensor nodes which have weaker perception ability.Step 6.
After the traverse, the cluster header node schedules the optimal subset to finish covering the target node; otherwise, go to Step2.


### 4.4. Algorithm Code

See Algorithm1.Algorithm 1
(1) Input N
,
R
s
,
E
,
E
thr // Initialize the number of sensor nodes, perception radius, sensor nodes energy
and the energy threshold value.
(2) CL = Null
(3) i
=
0, j
=
0, t
=
0, k
=
0 // loop variables
(4) While (i
≤
N)
(5) E(X) = ∪
(
s
i
,
L
)
∣
N
(
l
,
σ
2
)
/
l
2 // calculating the coverage expectation values of node members
(6) While (t
r
=
t
∥
t
r
=
n
t) // After one or a few rounds
(7)
(8)   if (S
a
← Coverage) // the administrator node receives “Coverage” message
(9)  CL[j].date = Coverage
(10) j++
(11)
(1
2) Sort_order (CL[j
].data) // sorting the member nodes
(13) While (j
<
i) // determining the optimal coverage set
(1
4)
(1
5)   if (E
r
<
E
thr) // node residual energy is less than node threshold energy
(1
6)   S
i
← Notice // the administrators sends “Notice” to the member nodes
(1
7)   Coverage(t
i) ←
S
i // node members complete covering the target nodes
(1
8)
(1
9) k
=
j
(20) While (k
<
j)
(21)
(22)   if (CL[k].data ⊃ CL[j].data)
(23)
(24)   Close (CL[k].data)
(2
5)   j++
(2
6)
(2
7) else
(2
8) return ()
(2
9)


### 4.5. The NMCP Algorithm Complexity Analysis

In the analysis of NMCP algorithm,n represents the number of sensor nodes;m is equal to the number of edges connecting any two sensor nodes. P
m
i
n and P
m
a
x are the minimum and maximum coverage value of the monitoring area, respectively. Δ
p means the increment of coverage after each covering process. Set P
m
i
n
=
c and P
m
a
x
=
b
n; c and b are constant coefficient. Assume that, at the initial stage, the coverage rate of sensor node is p
(
0
)
=
b
/
n, and at time t, the transition probability of a sensor node is greater than c
/
2
b
n which also means the minimum probability of sensor node’s coverage is P
m
i
n
=
c
/
2
b
n. Set R
=
(
1
-
e
)
p
(
t
-
1
)
at time
t
+
1; the coverage of a sensor node is(34)
p
t
+
1
=
p
t
+
1
t
+
1
p
t
+
1
t
+
1
+
p
t
t
+
1
≤
p
t
+
1
t
+
1
c
+
p
t
t
+
1
≤
b
1
-
Δ
p
c
+
c
e
+
R
.WhenL
=
b
/
1
-
e
c
+
c
e
+
R, the time complexity of NMCP algorithm is E
(
T
), as follows:(35)
E
T
=
∑
m
=
1
n
-
1
2
b
n
c
n
-
m
·
1
-
L
n
1
-
n
=
2
b
n
c
1
-
L
n
1
-
n
∑
m
=
1
n
-
1
1
m
≤
2
b
n
c
e
-
L
H
n
-
1
.Since∑
m
=
1
n
-
1
(
1
/
m
) is the sum of harmonic series of first n
-
1 terms, let H
n
-
1
=
∑
m
=
1
n
-
1
(
1
/
m
); then ∑
x
=
1
n
-
1
(
1
/
x
)
-
1
<
∫
1
n
-
1
(
1
/
x
)
d
x
<
∑
x
=
1
n
-
1
(
1
/
x
); that is,(36)
H
n
-
1
=
∑
m
=
1
n
-
1
1
x
=
∫
1
n
-
1
1
x
d
x
=
O
ln
⁡
n
.


## 4.1. Energy Conversion

For a sensor node, the energy consumption mainly happens in the sensing module and the communication module. When collectingl bits data, the energy consumption of sensing module E
T and the communication module E
R is as follows:(21)
E
T
l
,
d
=
l
E
T
-elec
+
l
ε
f
s
d
2
,
d
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
4
,
d
≥
d
0
.The energy consumption model for receiver module is(22)
E
R
l
=
E
R
-elec
l
=
l
E
e
l
e
c
,where l bits are the fixed length of data transmitted, d represents the communication Euclidean distance between sensor nodes, and d
0 represents the threshold or proportional quantity of the communication distance between sensor nodes. When the communication distance between sensor nodes is less than d
0, the energy attenuation index value is 2; otherwise it is 4.Definition 9 (optimum subset).
LetG be the set of wireless sensor network’s sensor nodes; G
1 is called an optimum subset where G
1 is a subset of sensor nodes, namely, G
1
⊂
G, and all the sensor nodes in G
1 cover target set T entirely.Definition 10 (energy property).
W
=
{
w
1
,
w
2
,
w
3
,
…
,
w
n
} is the initial energy collection of sensor nodes; W follows W
~
N
(
μ
,
σ
2
) normal distributions, where w
i denotes the initial energy of sensor node s
i.Definition 11 (the maximum distortion).
On the premise that certain coverage rate is met, the maximum distortion is(23)
E
s
1
x
,
y
-
s
x
,
y
2
≤
D
∀
s
i
x
,
y
∈
A
.
s
1
(
x
,
y
) is the estimated Euclidean distance between a sensor node and the target node, while s
(
x
,
y
) is the average measured distance, Euclidean distance, between the sensor node and the target node.Theorem 12.
The communication distance between nodes is less than or equal to half the difference between variance and the distortion.Proof.
Suppose the measured distance at the target nodet
(
x
,
y
) is s
(
x
,
y
), the data information used contains the measured data, and when multitarget nodes are measured, the average of measured values follows normal distribution. The energy collection set of preset-energy sensor nodes is W
=
{
w
1
,
w
2
,
w
3
,
…
,
w
n
}. Then the Euclidean distance between communication nodes is as follows:(24)
R
x
1
,
y
1
,
x
2
,
y
2
=
x
1
-
x
2
2
+
y
1
-
y
2
2
=
E
S
x
1
,
y
1
-
u
S
x
2
,
y
2
-
u
=
R
d
.
LetH be the set of sensor nodes which collects information, and let H
1 be the complementary set ofH; the sensor node nearest to the target node in H is used to calculate the measured distance which is then used to estimate a signal data in H
1. Therefore, the estimated signal value at the target node point (
x
,
y
) is s
1
(
x
0
,
y
0
); namely,(25)
s
1
x
0
,
y
0
=
s
x
1
,
y
2
.
According to formulas (23) and (24), we have(26)
E
s
x
0
,
y
0
-
μ
s
u
,
v
-
μ
=
2
σ
2
-
2
R
d
x
0
,
y
0
,
u
,
v
.
Substitute formula (23) into formula (26); we have(27)
R
d
x
0
,
y
0
,
u
,
v
≤
σ
2
-
D
2
.
The process to prove is complete.Theorem 13.
In initial state, when transmittingl-bit data, the energy consumed in multilateral transmission is more than that consumed in unilateral transmission.Proof.
Suppose the current working nodeS
i has a set of neighbour nodes namedZ, in which each node corresponds to neighbour S
z. For convenience, the calculations start with 3, which denotes the number of neighbours in the collection, when n
→
∞. We will prove that using mathematical induction, as shown in Figure 2.
LetA be the source node, letD be the convergence node, letB,C be the neighbour nodes, and letO be the disk centre; the network storesl-bit data of any sequence, which is going to be sent from sourceA to convergence nodeD. Two kinds of circumstances are discussed as follows.
The First Case:From A to D Directly. According to formula (21), the energy dissipations are as follows when source nodeA sends out data:(28)
E
T
x
_
A
D
l
,
d
A
D
=
l
E
T
-elec
+
l
ε
f
s
d
A
D
2
,
d
A
D
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
A
D
4
,
d
A
D
≥
d
0
.
The Second Case: From A to B, Then From B to D. We prove that with mathematical induction: when k
=
3, from nodeA to nodeB, the energy consumption model of the transmitting module in nodeA is (29)
E
T
x
_
A
B
l
,
d
A
B
=
l
E
T
-elec
+
l
ε
f
s
d
A
B
2
,
d
A
B
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
A
B
4
,
d
A
B
≥
d
0
,
E
R
x
_
B
l
=
l
E
e
l
e
c
.
The energy consumed by nodeB to receive the information is(30)
E
T
x
_
B
D
l
,
d
B
D
=
l
E
T
-elec
+
l
ε
f
s
d
B
D
2
,
d
B
D
<
d
0
l
E
T
-elec
+
l
ε
a
m
p
d
B
D
4
,
d
B
D
≥
d
0
.
So far, the total energy consumption of nodes on the pathA-B-D is(31)
E
T
o
t
a
l
=
E
T
x
_
A
B
+
E
R
x
_
B
+
E
T
x
_
B
C
.
In their initial state, the nodes work with the same amount of energy and are independent from each other. The basic properties of triangle show that(32)
E
T
o
t
a
l
=
E
T
x
_
A
B
+
E
R
x
_
B
+
E
T
x
_
B
D
<
E
T
x
_
A
D
.
Namely, whenk
=
3, node energy consumption in multilateral data transmission is lower than that in unilateral data transmission, so when k
=
3, the inequality is satisfied.
First, take the path fromA toB, thenB toC, andC toD (A-B-C-D), as an example to prove, and then add to n
→
∞. Because ∠
α
>
∠
A
C
D
=
π
/
2, ∠
α is an obtuse angle. Conclusion can be drawn with cosine theorem as: cos
⁡
∠
α
<
0; namely, B
C
2
+
C
D
2
<
B
D
2, when n
→
∞. The adjacent neighbour nodes can be combined into an obtuse triangle, in which the square of the length of the side opposite to the acute angle is less than the sum of the squares of the lengths of the sides of the obtuse angles. After n
-
2 times of superposition calculation, we eventually get B
C
2
+
C
D
2
<
B
D
2; namely, (33)
E
T
x
_
A
B
+
E
R
x
_
B
+
⋯
+
E
R
x
_
n
-
1
+
E
T
x
_
n
-
1
,
n
<
⋯
<
E
T
x
_
A
B
+
E
R
x
_
B
+
E
T
x
_
B
D
<
E
T
x
_
A
D
.
The process to prove is complete.Figure 2
Multilateral and unilateral node connection diagram.Energy consumed in multilateral transmission is not higher than the energy dissipation in unilateral transmission in a multiple hops path in wireless sensor network [28–30]. But practically, it is always hard to implement the single hop transmission between the source node and the convergence node due to the limited communication radius of nodes, obstacles, and the variation of environment.NMCP algorithm takes the network running time round number as the basic unit, each round containing two aspects, namely, coverage control information and the stable state information of nodes. In working stage, the working nodes remain on, and all redundant nodes are off so as to save the network energy. At stable stage, each node has five kinds of running state, which are judge, compete, wait, start, and sleep states [31–33]. Judge state: at the beginning of each time round, nodes are in the state of judgment. When redundant judging condition of a node is satisfied, the node enters sleep state; otherwise, if the condition is not satisfied, it enters the compete state; compete state: a node which succeeds on the start-up of a competition may convert into the state of working, whereas the unsuccessful nodes enter the state of wait; wait state: those nodes failed in the competition to enter wait state, and when they successfully receive the on-duty message from their neighbours during initiating, they update the message of their own locally and then enter judge state. Start state: when a node wins in the competition, it enters the start state. By calculating the node coverage, whether the nodes which perception regions are in start states satisfy the requirements for coverage is determined. If not satisfied, it sends on-duty message for schedule and then enters judge state; sleep state: while the redundant judging conditions are satisfied, the node enters sleep state to reduce its energy consumption and enters judge state in the unit time round. When the density of nodes is too large in a monitored region, the vast majority of the nodes in the region will satisfy the redundant node judgment conditions. At the moment, all those nodes will enter sleep states. Although this state can reduce the node energy consumption, there are still some deficiencies; the reason for this is that once perceiving neighbour nodes enter sleep state, there will be large coverage blind area in monitored region; therefore the coverage quality is decreased [34–37]. In order to avoid such kind of situation, NMCP algorithm uses a mechanism that once a node enters sleep state, it wakes up its neighbour nodes immediately and converts them into wait states. The aim is to reduce the density of working nodes first, namely, select a node as a candidate working node directly; the other nodes not selected enter sleep states directly and then schedules in the candidate working nodes [38]. Each candidate working node elects itself with a probability of p, whereas those nodes which are not chosen directly enter sleep state and then work as candidate nodes in the redundant nodes. Each candidate node elects itself to enter the prework state, whereas those candidate nodes which are not elected enter presleep state. The state transition between the five states in the covering control phase is as shown in Figure 3.Figure 3
The state transition diagram.


## 4.2. The Basic Idea of NMCP Algorithm

Based on the idea in literature [10] by means of clustering theory, this algorithm divides the coverage region in the monitored region into several clusters, each head node of a cluster being in charge of and controlling the member nodes in its cluster. At the initial stage of the network operation, the cluster members send “k-degree Coverage” message to their cluster head node first, while the cluster header maintains a linked list CL which receives the messages which are composed of the sensor node ID and such properties as its perception range and energy attenuation. After one or more cycles, the cluster header will collect all the cluster members information, then sort the list according to the size of the residual energy of nodes, as well as assigning to weight the first few nodes in the front of the list; after that, it scans every item in the linked list and marks the sensor nodes which are capable of covering the target node. Finally, the cluster header sends “k-Notice” messages to those marked member nodes which are responsible for covering the target node. The cluster head node sends on-duty messages to the member nodes and neighbour nodes to awaken those members nodes to enter waiting state and notify the neighbour cluster head nodes of the monitored information of the target. Based on the above information, the weighting of member nodes participating in the monitoring is calculated. If its weighting is greater than the set threshold, the node would enter into active state and monitor any moving target within its sensing range. Active nodes around the target will form an initial dynamic cover group. Member nodes will send an information packet to the cluster head node. The data packet contains information as time stamp, node ID, and distance between the nodes and the target. As there may be more than one cluster head node in NMCP, for the convenience of management, one of the cluster head nodes will be selected as managing node and is responsible for the information fusion and data management. Because the target node is moving in the monitoring area, the initial NMCP may not meet the requirements of target monitoring. Therefore, dynamic reconstruction is needed according to the position of the target. Reconstruction process is completed by members updating management and head node reselecting. When the target moves to a new grid, new cluster head node and member nodes that meet the requirements of the threshold weighting joint to the original NMCP, and the newly jointed cluster head node is elected as the leader node. Nodes within the original NMCP that cannot meet the monitoring requirements will quit the NMCP. If the original managing node happens to be a quitting node, at this time, the original managing node needs to send information of target location and member’s nodes to the new managing node. When the target moves away from the original location, the cluster head node will broadcast messages to its member nodes to enter into sleep state to save power consumption.


## 4.3. NMCP Algorithm Description

Step 1.
Calculate the perception intensity of cluster members.Step 2.
The cluster member nodes send “k-Coverage” to the cluster header node. After one or more time units, the header node receives the message from cluster members.Step 3.
The cluster head node establishes a linked list and stores the information collected in it and then sorts the list according to the amount of energy in the sensor nodes; at the same time it assigns weights to those nodes which have higher energy.Step 4.
Find qualified sensor nodes, and mark them.Step 5.
If the target node is in the state ofk-coverage, the cluster header will traverse the list to turn off those sensor nodes which have weaker perception ability.Step 6.
After the traverse, the cluster header node schedules the optimal subset to finish covering the target node; otherwise, go to Step2.


## 4.4. Algorithm Code

See Algorithm1.Algorithm 1
(1) Input N
,
R
s
,
E
,
E
thr // Initialize the number of sensor nodes, perception radius, sensor nodes energy
and the energy threshold value.
(2) CL = Null
(3) i
=
0, j
=
0, t
=
0, k
=
0 // loop variables
(4) While (i
≤
N)
(5) E(X) = ∪
(
s
i
,
L
)
∣
N
(
l
,
σ
2
)
/
l
2 // calculating the coverage expectation values of node members
(6) While (t
r
=
t
∥
t
r
=
n
t) // After one or a few rounds
(7)
(8)   if (S
a
← Coverage) // the administrator node receives “Coverage” message
(9)  CL[j].date = Coverage
(10) j++
(11)
(1
2) Sort_order (CL[j
].data) // sorting the member nodes
(13) While (j
<
i) // determining the optimal coverage set
(1
4)
(1
5)   if (E
r
<
E
thr) // node residual energy is less than node threshold energy
(1
6)   S
i
← Notice // the administrators sends “Notice” to the member nodes
(1
7)   Coverage(t
i) ←
S
i // node members complete covering the target nodes
(1
8)
(1
9) k
=
j
(20) While (k
<
j)
(21)
(22)   if (CL[k].data ⊃ CL[j].data)
(23)
(24)   Close (CL[k].data)
(2
5)   j++
(2
6)
(2
7) else
(2
8) return ()
(2
9)


## 4.5. The NMCP Algorithm Complexity Analysis

In the analysis of NMCP algorithm,n represents the number of sensor nodes;m is equal to the number of edges connecting any two sensor nodes. P
m
i
n and P
m
a
x are the minimum and maximum coverage value of the monitoring area, respectively. Δ
p means the increment of coverage after each covering process. Set P
m
i
n
=
c and P
m
a
x
=
b
n; c and b are constant coefficient. Assume that, at the initial stage, the coverage rate of sensor node is p
(
0
)
=
b
/
n, and at time t, the transition probability of a sensor node is greater than c
/
2
b
n which also means the minimum probability of sensor node’s coverage is P
m
i
n
=
c
/
2
b
n. Set R
=
(
1
-
e
)
p
(
t
-
1
)
at time
t
+
1; the coverage of a sensor node is(34)
p
t
+
1
=
p
t
+
1
t
+
1
p
t
+
1
t
+
1
+
p
t
t
+
1
≤
p
t
+
1
t
+
1
c
+
p
t
t
+
1
≤
b
1
-
Δ
p
c
+
c
e
+
R
.WhenL
=
b
/
1
-
e
c
+
c
e
+
R, the time complexity of NMCP algorithm is E
(
T
), as follows:(35)
E
T
=
∑
m
=
1
n
-
1
2
b
n
c
n
-
m
·
1
-
L
n
1
-
n
=
2
b
n
c
1
-
L
n
1
-
n
∑
m
=
1
n
-
1
1
m
≤
2
b
n
c
e
-
L
H
n
-
1
.Since∑
m
=
1
n
-
1
(
1
/
m
) is the sum of harmonic series of first n
-
1 terms, let H
n
-
1
=
∑
m
=
1
n
-
1
(
1
/
m
); then ∑
x
=
1
n
-
1
(
1
/
x
)
-
1
<
∫
1
n
-
1
(
1
/
x
)
d
x
<
∑
x
=
1
n
-
1
(
1
/
x
); that is,(36)
H
n
-
1
=
∑
m
=
1
n
-
1
1
x
=
∫
1
n
-
1
1
x
d
x
=
O
ln
⁡
n
.


## 5. System Evaluation

In order to verify the effectiveness and the stability of algorithm NMCP, we use MATLAB7.0 as the simulation platform for experiment and analysis. With the comparison experiment between NMCP and [26, 27, 34], we give the performance comparison in different evaluation systems. The simulation parameters are as shown in Table 1.Table 1
Performance parameters list.
Parameter
Value
Monitoring area
400∗ 400
R
s
10 m
Initial energy
10 J
Time
600 s
e
m
i
n
0.005 J
R
c
20 m
E
R
-
e
l
e
c
50 J/b
E
T
-
e
l
e
c
50 J/b
ε
f
s
10 (J/b)/m2
ε
a
m
p
100 (J/b)/m2The comparison simulation experiments between algorithms NMCP in this paper and ETCA in [26], ECAPM in [34], and EPDM in [27] are carried out under the same network scale, with different network lifetime, target node scale, number of sensor nodes, network run time, and coverage rate, as shown in Figures 4–7.Figure 4
Comparison of network lifetime.Figure 5
The network lifetime and number of target nodes.Figure 6
The run time comparison of the three algorithms.Figure 7
Comparison of coverage rate.Figure4 shows the comparison simulation diagram of algorithms NMCP, ETCA, and ECAPM in the aspect of network lifetime. In this figure, the three algorithms have similar lifetime at the initial phase, while as time passes by, the ETCA algorithm and ECAPM algorithm rise relatively slower which mainly lies in the fact that ETCA algorithm and ECAPM algorithm monitor the whole network in centralized manner, thus converting the scheduling mechanism between sensor nodes in a linear fashion, which consumes more energy, whereas the NMCP algorithm in this paper mainly finishes the covering process over the monitored region in a fashion of seeking in the linked list and finding the optimal node set. With the same number of sensor nodes, the NMCP algorithm requires longer network run time. Take an example of iterating 200 times, the network lifetime is prolonged by 16.33% and 19.75% averagely compared with the algorithm ETCA.Figure5 reflects the different number of target nodes and the corresponding network lifetime variation curve. When the network begins running, the number of sensor nodes is 348, and the number of target nodes is 10. With the increase of network running time and target nodes number, the network lifetime using the three algorithms is all in equilibrium state. When k
=
4, both the ETCA algorithm and the ECAPM algorithm show slight fluctuations relative to the NMCP algorithm. With the same number of target nodes, the average running time of the network using NMCP algorithm is 7.12%, 9.06% higher than that using the ETCA algorithm.Figure6 shows the run time comparison curves of the three algorithms. As can be seen from Figure 4, the run time of NMCP algorithm is less than that of the EPDM or ECAPM algorithm. The main reason is that, using clustered structure, the NMCP algorithm has higher speed than EPCM or ECAPM algorithm when seeking nodes which meet the requirements for covering the sensor node, which reduces the difficulty in the coverage problem. Although the EPDM algorithm also uses clustering technique, it uses centralized covering strategy in the process of switching energy between nodes by traversing all the sensor nodes in the node set before the optimal covering subset is determined.To simulate the coverage rate, we carried out the comparison experiments between the algorithm in this paper and EPDM and ECAPM, with the monitored region id set to200
∗
200 m2. As shown in Figure 5, the coverage rate of the three algorithms increases along with the increase in the number of sensor nodes. When the coverage rate reaches 99.9%, the complete coverage over the target node is taken on as finished. When the active nodes number is 50 and k
=
4, the coverage rate of NMCP algorithm is 71%, while the active nodes numbers of the EPDM algorithm and ECAPM algorithm are 64% and 65%, respectively. When the coverage rate is 99.9%, the active nodes number of NMCP algorithm is 296, whereas the other two algorithms’ coverage rates are 91% and 88%, respectively, when the active nodes number is 296. Therefore, on average, the NMCP algorithm in this paper can increase the coverage rate by 10.31% and 12.47% comparing to EPDM and ECAPM algorithm, respectively.Experiment 1.
Comparison experiments between the NMCP algorithm, ETCA algorithm, and LP_MLCEH protocol [36] are carried out about prolonging the network lifetime; the experimental data are the average of 200 times simulation data, as shown from Figures 8–10.Figure 8
100
∗
100, the network lifetime curve.Figure 9
200
∗
200, the network lifetime curve.Figure 10
300
∗
300, the network lifetime curve.The second group of comparison experiments are carried out between NMCP algorithm, ETCA algorithm, and LP_MLCEH protocol in relation to the network lifetime in different monitored region. In the experiments, we giveK different values and change network scale by changing the number of nodes randomly deployed in monitored region. For smaller monitored region, the number of the randomly deployed nodes is initiated at 20, which is also used as the unit to increase gradually. The simulation diagram shows that the lifetime of wireless sensor network rises in a linear upward trend with the increase of the number of sensor nodes. The main reason is that the members in the node set cover the target node in turn with nodes scheduling mechanisms; therefore the network life cycle is prolonged. In the same network environment, NMCP algorithm prolongs the network lifetime by 13.71% and 16.52% than ETCA algorithm and LP_MLCEH protocol on average; for a larger monitored network, the number of the randomly deployed nodes is initiated to 50, which is also used as the unit to increase gradually. The simulation diagram also shows that the lifetime of wireless sensor network rises with the increase of the number of sensor nodes. Furthermore, its rising trend exceeds that of smaller monitored region. Compared to ETCA algorithm and LP_MLCEH protocol, the network lifetime is increased by 15.13% and 17.27% on average.Experiment 2.
The comparison experiments about prolonging the network lifetime are carried out between the NMCP algorithm, EPDM algorithm [28], and OSCC protocol [11]. Taking the 200
∗
200 as an example, the experimental data are the average of simulation data of 100 times, as shown from Figures 11–13.Figure 11
200
∗
200, network coverage curve.Figure 12
200
∗
200, the network running time curve.Figure 13
The comparison between working sensor nodes and sensor nodes.In Figure11, with the increase in the number of sensor nodes, the three algorithms demonstrate incremental change in coverage rate. When the coverage rate is 99.9%, and k
=
2, the number of sensor nodes is 180; when k
=
3, the number of sensor nodes is 147; when k
=
4, and the number of the sensor nodes is 107, this algorithm reaches 99.9%, which means that the k-degree coverage is completed, whereas EPDM algorithm and OSCC algorithm cannot reach 100%, which suggests that the NMCP algorithm in this paper has higher coverage rate than the EPDM algorithm and the OSCC algorithm, verifying the effectiveness of the algorithm presented in this paper. In Figure 12, at the beginning of the program execution, the two algorithms have almost the same coverage rate, but as time passes by, both the two contrasted algorithms’ coverage rates decline. The main reason of that is the fact that in EPDM and OSCC algorithm the sensor nodes use uninterrupted covering method during network operation; namely, they cover the target nodes continuously in the monitored region until the node energy is exhausted. When t
=
150, the three algorithms’ coverage rates drop quite obviously; its coverage is when k
=
2,3
,
4, respectively, CPNMCP2 = 76.55%, CPNMCP3 = 85.91%, CPEPDM = 87.92%, CPOSCC = 94.24%, and CPNMCP4 = 98.01%. When k
=
4, the coverage rate is higher than the average coverage rate of EPDM and OSCC algorithm, which shows that, with the same number of nodes, the coverage rate of NMCP algorithm is significantly higher than the other two algorithms, verifying the effectiveness of the algorithm proposed in this paper. Figure 13 shows the comparison curves of the working nodes number of the algorithm in this paper, the EPDM, and the OSCC algorithm on the premise of the same coverage rate. When the number of sensor nodes keeps between 140 and 180, the three algorithms have almost steady number of sensor nodes; when k
=
2,3
,
4, nodes number required in the algorithm in this paper generally keeps in 144, 141, and 122, while the EPDM and OSCC algorithm generally keep the number of working nodes between 132 and 150. The reason mainly lies in the fact that the algorithm in this paper finishes covering the monitored region by calculating the coverage expectation values of nodes to obtain the set of neighbour nodes in the perception radiuses of local nodes, whereas the other two algorithms finish covering the monitored region in a continuous covering manner, depending on the number of nodes. Therefore, on average, the algorithm in the paper needs less working sensor nodes than the other two algorithms by 3.49%.


## 6. Conclusions

First, the coverage problems and the deficiencies in the wireless sensor network were analysed and, on basis of that, this paper put forward a nonlinear multiobjectivek-degree coverage preservation protocol. Second, the network model is established based on the above analysis, and the dependency relationship between the sensor node and the destination node is given; then the coverage rate and expectation value of the sensor node in monitored region are then calculated and verified; in the meanwhile the process of resolving the coverage rate for any node that is covered by multisensor nodes in the two-dimensional plane is dealt with. In terms of node energy, we have proved the relationship between the communication distance and the maximum distortion, as well as the implementation process of the NMCP protocol.Finally, the effectiveness and feasibility of the NMCP protocol are verified by simulation experiments. Future work mainly focuses on how to achieve effective coverage on the boundary of monitored region and nonlinear coverage of irregular monitored region.



---

*Source: 3434961-2016-08-25.xml*