2.1 Wireless sensor network coverage
The network coverage is the basic problem of the construction of wireless sensor networks. The network coverage needs to reach the maximum under the conditions that guarantee a certain quality of service (QoS) [
18‐
21], by measuring the network coverage to determine whether the presence of communication blind area and get the monitoring area of wireless sensor network coverage. The sensor node distribution can be adjusted or sensor nodes can be added according to the measurement condition. In addition, by changing the density of the network coverage, the more sensor nodes were deployed in some important areas in order to guarantee the reliability of measured data. Therefore, the network coverage is not only for communication coverage and monitoring area coverage but also for better meeting of the needs of certain applications. Generally speaking, quality of service is the measure of wireless sensor network coverage [
22].
The wireless sensor network coverage is mainly divided into certainty coverage and the random covering. For the certainty coverage, the coverage area size is determined in order to cover the area using the minimum number of sensors. The certainty coverage is adopted to deploy the sensor nodes of a known region in this paper.
At present, a kind of widely used strategy is choosing part nodes which can be enough to cover the monitoring area as working nodes, at the same time, turn off redundant nodes [
23]. A certain number of sensor nodes are deployed in the monitoring area, under the ensuring network connectivity in normal condition, letting part of the redundant nodes into low-power sleep state, while the rest of the active node is used to cover the whole region in the most likely small amount, which form the optimal coverage node set. In the wireless sensor network, the node number in the increased network not only means increased cost but also brings the limited bandwidth congestion because of the inter-node communication conflict. The optimal coverage node set is the minimum node set which does not affect the entire network coverage. This way does not only reduce potential conflicts in a wireless channel and reduce the possibility of competing for access to the media but also save energy in order to prolong the network lifetime [
11].
2.2 Wireless sensor network optimization coverage model
Supposed that the target monitoring area A is a two-dimensional plane, and it will be divided into m × n grid, and each grid area is 1. The N sensor nodes are randomly distributed in the A, the sensor node set S can be expressed as S = (s
1, s
2 , ⋯, s
i
, ⋯, s
N
). The (x
i
, y
i
) is the coordinate of sensor node s
i
in a target monitoring area A, each node coordinate is known, and effective perception radii are rand s
i
= {x
i
, y
i
, r}. Perception range of node s
i
is a circular region with the coordinates (x
i
, y
i
) of node s
i
as the center and the r as the perception radius, to express with c
i
= {p ∈ A|d(p, (x
i
, y
i
)) ≤ r, i ∈ [1, N]}, where, p is an arbitrary point of area A, and d is the Euclidean distance. The perception range of the whole sensor network is C = ∪
i ∈ [1, N]
c
i
, that all network nodes perceptual range are in union.
There is m × n target point. (a
1, a
2, ⋯, a
j
, ⋯ a
m × n
) need to be monitored or sensed in target monitoring area A; suppose a
j
is s
i
perception then d( a
j
, s
i
) ≤ r; an arbitrary point of monitoring area A is at least perceived by a sensor node. Assume the communication range of sensor node s
i
is a circle with the coordinates (x
i
, y
i
) of node s
i
as the center and the r
c
as the radius; if d(s
i
, s
j
) ≤ r
c
, then the sensor node s
i
and s
j
can communicate directly.
Definition 1: given a sensor node set S, the communication network G = (V, E) , { V = S, L(s
i
, s
j
) ∈ E} composed of S is an undirected graph, if there is a communication path between any two nodes in the communication diagram G derived from S then the communication diagram is connected, when d(s
i
, s
j
) ≤ r
c
.
Definition 2: for the sensor node set S and the target monitoring area A; if every point of A is perceived by a sensor node of S then the S is a covering set of A. If the communication diagram derived from S is connected then the S is a connected cover set of A.
Definition 3: for the connected cover set S and the target monitoring area A, the minimal connected cover set is looking for a minimal subset S′ ⊆ S, while the monitoring area A is covered by S′ completely and the communication diagram derived from S′ is connected.
On the basis of energy efficiency, this paper presents optimization goal of a connectivity covering set: ensuring that each target point in A is at least covered by a sensor node, at the same time, ensuring that a subset is a connected set.
In order to ensure connectivity, the communication radius
r
c
is at least two times perception radius
r, namely
r
c
≥ 2
r. On this condition, the researchers only need to consider the coverage problem in the sensor network, if the network is covered then it is connected [
24].
Let
P
cov(
x,
y,
s
i
) represent the probability that any point (
x,
y) of monitoring area
A is covered by sensor node
s
i
(
x
i
,
y
i
) then
$$ {P}_{\mathrm{cov}}\left(x,y,{s}_i\right)=\Big\{\begin{array}{l}1,\kern1.3em {\left(x-{x}_i\right)}^2+{\left(y-{y}_i\right)}^2\le {r}^2\\ {}\kern0.2em 0,\kern1.2em \mathrm{else}\end{array}\kern0.4em \operatorname{} $$
(1)
As long as there is a sensor node,
s
i
covers the monitoring point (
x,
y) then the monitoring point (
x,
y) is covered by the sensor node set
S. So the regional coverage area of sensor node set
k is expressed as follows:
$$ {A}_{\mathrm{area}}(S)={\displaystyle \sum_{x=1}^m{\displaystyle \sum_{y=1}^n{P}_{\mathrm{cov}}}}\left(x,y,S\right)\kern0.2em \varDelta x\kern0.2em \varDelta y $$
(2)
The area of monitoring area is
A
s
, the working sensor node set is
S′, the target function of network coverage of working node set is as follows:
$$ {f}_1\left({S}^{\prime}\right)={A}_{\mathrm{area}}\left({S}^{\prime}\right)/{A}_s $$
(3)
where
A
area(
S′) is the cover area of working sensor node set
S′.
The target function of nodes utilization rate is as follows:
$$ {f}_2\left({S}^{\prime}\right)=\kern0.3em \left|{S}^{\prime}\right|/N $$
(4)
where
N is the total number of sensor nodes, |
S′| is the number of working sensor nodes.
The aims of wireless sensor network node optimal coverage are to reduce the sensor node’s utilization and to ensure maximum network coverage at the same time, this is a multi-objective optimization problem. So the multi-objective optimization coverage model of wireless sensor network is expressed as follows:
$$ \max \kern0.2em f\left({S}^{\prime}\right)= \max \kern0.1em \left({f}_1\left({S}^{\prime}\right),\kern0.4em 1-{f}_2\kern0.1em \left({S}^{\prime}\right)\kern0.2em \right) $$
(5)