A coverage algorithm based on D-S theory for directional sensor networks

Abstract

In view of the random deployment of directional sensor nodes, this article establishes the directional probability sensing model and proposes a distributed deployment strategy based on D-S theory, which makes the perceived probability of the target points in the monitoring area is equal to or greater than the threshold through the collaborative sensing among multiple nodes. The proposed algorithm uses fewer nodes to achieve the target coverage and meet the required overall coverage level. The simulation results indicate that the proposed algorithm reduces the number of nodes effectively and guarantees the better coverage.

Keywords

Directional sensor networks probability sensing model D-S theory

Introduction

Wireless sensor networks (WSNs) are capable of real-time monitoring, sensing, and collecting information from various types of environmental and monitored objects through various types of integrated micro sensors and also apply in military battlefield surveillance, public facilities maintenance and management, inspection and maintenance of industrial equipment, scientific observations of the gathering place of plants and animals, and so on.¹ Most of the current coverage control studies are based on omnidirectional sensing model.^2,3 However, for some sensor nodes, such as video sensors,⁴ infrared sensors, and ultrasonic sensors, the way in which they sense targets and acquire the target information is obviously directional. In practical applications, the sensing probability of directional sensor networks (DSNs) varies with the change of time and location, namely, that the nodes detect targets according to a certain probability. The directional sensors are affected by various factors, so that the target detection probability is not guaranteed. And they even make false alert. The deployment of sensor nodes reflects the cost and performance of the WSN, and the reasonable deployment scheme can greatly enhance the sensing effect and reduce the cost.^5,6

Boolean perception model is mostly used in the current research on directional sensors. According to Voronoi diagram and the direction-adjustable characteristic of directional sensors, a distributed greedy algorithm is designed by Sung and Yang,⁷ which divides sensor nodes into Voronoi polygon, and finally makes the sensor nodes work in the best direction to expand the coverage effect. This algorithm can get better coverage effect without saving global information of the network, reduce the computation, and prolong the lifetime of the network. Lu et al.⁸ aiming at the problem of enhancing network coverage proposed a greedy iterative algorithm based on the directional sensor deployment. The local optimal sequence of the network nodes is solved by the iteration of the deployment model. The convergence speed of the algorithm is improved, and eventually the sensor nodes work in an optimal state and the coverage is enhanced. The region coverage problem is studied by Cheng et al.⁹ The paper defines the region coverage problem according to the virtual node and the virtual domain, translates the problem into linear programming problem, and calculates node weights and virtual domains with the different priorities of nodes. A probability-enhanced greedy algorithm is proposed, which saves the calculation time and reduces the energy consumption. However, this algorithm has a certain gap with the practical applications due to the deterministic sensing model adopted. The greedy algorithm is improved in literature¹⁰ aiming at the multiple directional cover set. This algorithm just meets the local optimum for the network coverage. Due to the lack of consideration for isolated targets, the nodes need to adjust the sensing direction through multiple iterations, which is not conducive to prolong the lifetime of the network. Two heuristic coverage algorithms of rotatable directional sensors are introduced in the literature:¹¹ maximum coverage deployment (MCD) heuristic algorithm and disk-overlapping deployment (DOD) heuristic algorithm. DOD algorithm is better than MCD algorithm when the observed objects are gathered together. The common defect of the two algorithms is that some relay nodes are deployed to guarantee the network connectivity. The literature¹² presents two greedy algorithms based on priorities to optimize the coverage area. The two algorithms, aiming at the different priorities of the nodes, further improved the quality of coverage. However, in the two algorithms, the node needs to convey messages multiple times to identify its own working state and priority, so that the energy consumption is increased. J Zhao and JC Zeng¹³ presented an algorithm to optimize the coverage of DSN based on the virtual force. The algorithm closes the redundant nodes by analyzing the overlapped coverage of the nodes and the force situation of the centroid. The literature¹⁴ defines the attractive force and proposes a distributed virtual force algorithm, which makes the node mobile, reduces the overlapped coverage, minimizes the overlapped area, makes the observing direction of sensors toward the direction of interest and can quickly converge within 5–6 iterations to achieve the expected coverage effect. Hekmat and Van Mieghem¹⁵ indicate that the target detection probabilities of the sensor nodes are usually uncertain, and the target sensing probabilities of the node within its sensing range varies with the distance. Huang et al.¹⁶ proposed a three-dimensional (3D) directional sensor coverage-control algorithm, called IPA3D, based on the probability model. The energy cost of nodes is restrained and the performance of the algorithm is improved. However, IPA3D is neither suitable for nodes with different type of sensors nor for the situation in which the edge of the deployment area is not taken into account. Liang et al.¹⁷ proposed a coverage enhancement algorithm for DSNs which is based on the virtual potential field to enhance the coverage of the sensor network. Four kinds of virtual forces are defined among the centroid of sensor nodes, the center of voronoi diagram, and the vertex of sensor nodes. These interaction forces can be used to adjust the position of the nodes to improve the network coverage, but the algorithm is more complex, and there is no limit to the movement distance of nodes which will cause the waste of energy. K-barrier coverage of DSN was studied in Wang et al.,¹⁸ and the barrier coverage problem was transformed into a graph-theoretic model. An optimal algorithm and a greedy algorithm are proposed. The strong barrier coverage is formed by graph-theoretic model which requires the minimal mobile nodes number. The greedy algorithm has better performance than optimal algorithm, but the two algorithms belong to the centralized algorithm that is not suitable for large-scale sensor networks. For sensor network coverage enhancing algorithm, the problem of redundant nodes exists; Chen and Cao¹⁹ proposed an algorithm which combines the virtual potential field with learning automata, first use virtual potential field algorithm to adjust the network node sensing direction, followed by the use of learning automata to hibernate redundant nodes without affecting the network coverage rate.

The probabilistic sensing model can be approximated as a deterministic sensing model when the nodes work in the ideal situation. Therefore, researches on the uncertain probability sensing model of DSN are more universal, but the related researches are relatively rare.

In this article, we first introduce the probability sensing model of the directional sensor in sector shape, then establish the directional probabilistic sensing model, adopt the distributed algorithm to realize cooperative sensing through D-S theory, and finally propose a coverage algorithm of DSN based on D-S theory (CABDS).

Directional sensing model and coverage model

Directional sensor model

Figure 1 shows the probabilistic sensing model of the directional sensor in sector.²⁰ In order to denote the probabilistic sensing range, a new probabilistic range parameter d is added into the information of the sensor nodes. Therefore, the node information can be represented by $< S, R_{s}, \vec{V} (t), θ_{f}, d >$ , where S is the position coordinate of the node, represented by $(x_{s}, y_{s})$ ; $R_{S}$ is the effective sensing radius; $\vec{V} (t) = (V_{x} (t), V_{y} (t))$ is the sensing direction at the time instant t; $θ_{d}$ $(0 \circ \leq θ_{d} \leq 360 \circ)$ in Figure 1 is the angle value between the node sensing direction and the horizontal direction at the time instant t; $2 θ_{f}$ is the effective sensing angle, called the field of view of directional sensors, represented by fov; d is the probabilistic sensing range and its value is related to the power and hardware design of nodes.

Figure 1.

The model of probabilistic sensing of the directional sensor in sector.

For any target point p in the monitoring area, its coordinate in the two-dimensional plane is $(x_{P}, y_{P})$ . The sensing probability of node s to target point p can be expressed as follows

P (s, p) = {\begin{matrix} \frac{α}{d {(s, p)}^{β}} & d (s, p) < R_{s} + d and θ_{d} - θ_{f} \leq θ_{p s x} \leq θ_{d} + θ_{f} \\ 0 & other \end{matrix}

(1)

where $θ_{pxs}$ represents the angle between horizontal X-axis and the straight line which contains target point p and node s; $d (s, p)$ is the Euclidean distance between p and s, $d (s, p) = \sqrt{{(x_{p} - x_{s})}^{2} + {(y_{p} - y_{s})}^{2}}$ ; $α$ and $β$ are the sensing parameters of the sensor nodes.

Literature²¹ mentions a simple linear directional sensing model. Considering the critical points and the farthest sensing distance of the directional sensor, a simple probabilistic sensing model is put forward. When $d (s, p) \leq R_{s}$ , the sensing probability is $P (s, p) = 1$ ; when $d (s, p) = R_{s} + d$ , $P (s, p) = 0$ ; and when $R_{s} \leq d (s, p) \leq R_{s} + d$ , through the least square method, the probability is expressed as follows

P (s, p) = \frac{R_{f a r} - d (s, p)}{d}

(2)

where d represents the probabilistic sensing range of the sensor node; $R_{far} = R_{s} + d$ represents the farthest sensing distance of the node.

Through equations (1) and (2), we obtain

P (s, p) = {\begin{cases} 1 d (s, p) < R_{s} and θ_{d} - θ_{f} \leq θ_{p s x} \leq θ_{d} + θ_{f} \\ \frac{R_{f a r} - d (s, p)}{d} d (s, p) < R_{f a r} and θ_{d} - θ_{f} \leq θ_{p s x} \leq θ_{d} + θ_{f} \\ 0 other \end{cases}

(3)

where $θ_{psx}$ represents the angle between horizontal X-axis and the straight line which contains point p and node s; $R_{far} = R_{s} + d$ represents the farthest sensing distance of the node.

D-S theory fusion coverage model

Evidence theory²² was proposed by Dempster in 1967 and then expanded and developed by Shafer, so the evidence theory is also called D-S theory. Evidence theory can deal with the uncertainty caused by the unknown. It uses a belief function rather than a probability as a measurement and establishes the belief function under the constraint on the probability of some events rather than illustrating the accurate probability which is difficult to obtain. When the constraint is restricted to the strict probability, it becomes the probability theory.

U represents the recognition framework. All the elements in U are taken the possible values of evidence theory, not compatible with each other. M(A) represents the basic probability assignment of proposition A. Assume that m₁, m₂, and m₃ are the basic probability assignment functions in the same recognition framework U, respectively. The focal elements are $A_{i} (i = 1, 2, \dots, k)$ , $B_{j} (j = 1, 2, \dots, l)$ , and $C_{k} (k = 1, 2, \dots, m)$ , respectively. So the synthesis formula can be expressed as follows

m (A) = {\begin{matrix} \frac{\sum_{A_{i} \cap B_{j} \cap \dots = A} m_{1} (A_{i}) m_{2} (B_{j}) \dots}{1 - K_{1}} & \forall A \subset U, A \neq \emptyset \\ 0 & C = \emptyset \end{matrix}

(4)

where $K_{1} = \sum_{A_{i} \cap B_{j} \cap \dots = \emptyset} m_{1} (A_{i}) m_{2} (B_{j}) \dots < 1$ is the degree of evidence conflict.

Define a set $S = {s_{1}, s_{2}, \dots, s_{i}, \dots, s_{n}}$ to denote n nodes in DSN, where $1 \leq i \leq n$ . In order to facilitate the calculation, the monitoring area is divided into small grids. Each grid is so small that it can be approximately equivalent to a point. The probability that the ith node $s_{i}$ senses the jth grid $p_{j}$ is defined as $P (s_{i}, p_{j})$

P (s_{i}, p_{j}) = {\begin{cases} 1 if d (s_{i}, p_{j}) < R_{s} and θ_{d} - θ_{f} \leq θ_{p_{j} s_{i} x} \leq θ_{d} + θ_{f} \\ \frac{R_{f a r} - d (s_{i}, p_{j})}{d} if R_{s} \leq d (s, p) < R_{f a r} and θ_{d} - θ_{f} \leq θ_{p s x} \leq θ_{d} + θ_{f} \\ 0 other \end{cases}

(5)

where $d (s_{i}, p_{j})$ represents the Euclidean distance between the jth grid and the node $s_{i}$ ; $θ_{p_{j} s_{i} x}$ represents the angle between horizontal X-axis and the straight line which contains the grid point $p_{j}$ and the node $s_{i}$ .

$P_{st} (p_{j})$ denotes the probability that each grid point $p_{j}$ within the monitoring area is perceived by all the sensor nodes $S = {s_{1}, s_{2}, \dots, s_{i}, \dots, s_{n}}$ $(i = 1, 2, 3, \dots, n)$ in the network. By equation (5), the probability can be obtained as follows

P_{st} (p_{j}) = \frac{Π_{i = 1}^{n} P (s_{i}, p_{j})}{1 - \sum_{k = 1}^{n} [1 - P (s_{k}, p_{j})] Π_{i \neq k}^{n} P (s_{i}, p_{j})}

(6)

In DSN, let the threshold of sensing probability be $P_{th}$ . If $P_{st} (t_{j}) \geq P_{th}$ , the grid point is judged to be sensed, namely, that the grid is covered by the network; otherwise, the grid point is judged not to be covered. $P_{c} (p_{j})$ is used to denote the probability that the network senses the grid $p_{j}$ , expressed as follows

P_{c} (p_{j}) = {\begin{matrix} \begin{matrix} \begin{matrix} 0 \end{matrix} & \begin{matrix} if \end{matrix} & \begin{matrix} P_{st} (p_{j}) < P_{th} \end{matrix} \end{matrix} \\ \begin{matrix} 1 & if & P_{st} (p_{j}) \geq P_{th} \end{matrix} \end{matrix}

(7)

$η_{cov}$ represents the coverage rate, and its value is the ratio of the area of all the covered grids and the overall area, expressed in equation (8)

η_{cov} = \frac{P_{area}}{S_{area}} = \frac{\sum_{j = 1}^{A \times B} P_{c} (p_{j}) \times Δ x \times Δ y}{A \times B \times Δ x \times Δ y} = \frac{\sum_{j = 1}^{A \times B} P_{c} (p_{j})}{A \times B}

(8)

where $S_{area}$ is the area of the monitoring region; $P_{area}$ is the sum of the area of all the covered grids, $P_{area} = \sum_{j = 1}^{A \times B} P_{c} (p_{j}) \times Δ x \times Δ y$ .

The CABDS

Algorithm assumption

To simplify the simulation, some assumptions are given as follows:

All the nodes have the same sensing radius $R_{S}$ and the same communication radius $R_{c}$ $(R_{c} = 2 R_{far})$ .

There are enough sensor nodes. A large number of nodes are randomly deployed in the target area and the nodes can sleep.

After random deployment, the sensor node can identify its own coordinate and sensing direction, and the location information of all the neighbor nodes.

The position of the sensor node cannot be moved, but its sensing direction can rotate circularly around the node.

The communications of sensor nodes are omnidirectional. As shown in Figure 2, set any two points in the network as $s_{i}$ and $s_{j}$ . And $s_{j}$ is not in the current sensing direction of $s_{i}$ . The distance between the two nodes is $d (s_{i}, s_{j})$ and $0 \leq d (s_{i}, s_{j}) \leq 2 R_{far}$ . The two nodes can communicate with each other.

Figure 2.

The model of node communication.

Standard working direction

The sensor nodes work in pairs. Their working directions have been preset according to the deployment algorithm. Define the preset working directions as the standard working directions. After the initial deployment of nodes, in order to reduce the cost, according to the relation between the standard working direction and the current sensing direction of the node, the sensing direction of the node is adjusted to the same with the standard working direction. The standard working directions $φ_{1}$ and $φ_{2}$ are set in the initial deployment and appear in pairs, and $φ_{1} + φ_{2} = 2 π$ . In this article, we set $φ_{1} = π / 2$ and $φ_{2} = 3 π / 2$ , respectively. Figure 3(a) and (b) shows the relation between the standard working direction of the sensor node and the coordinate system. Figure 4 indicates the collaborative working modes of nodes $s_{i}$ and $s_{j}$ . When the algorithm is run, the DSN will calculate the rotation of nodes. Because of the selection of standard working directions, the number of calculations can be reduced and the energy of nodes can be saved.

Figure 3.

Standard working direction: (a) working direction π/2 and (b) working direction 3π/2.

Figure 4.

Collaborative working mode: (a) Situation 1, (b) Situation 2, (c) Situation 3, and (d) Situation 4.

A large-scale deployment of nodes is used in the proposed algorithm, so the dormancy awakening strategy is adopted. There are two working states of nodes: sleeping and listening. The flags of sleeping state and listening state are 0 and 1, respectively. $n_{work}$ represents the number of working nodes after the network deployment. The network wakes up any sensor node as the first one and identifies its position (the node $s_{i}$ shown in Figure 5). In the ideal situation, assume the following awakened node is in the horizontal or vertical direction of the current node. In order to cover all the monitoring area with the least number of nodes, it should be guaranteed that the nodes work in pairs in the standard working directions, and the distance between the two nodes cannot be too far or too close. If too far, the grids in the monitoring area are not perceived, as shown in Figure 4(a); if too close, the covered area by sensor nodes is seriously overlapping, which results in wasting resources of nodes, as shown in Figure 4(d).

Figure 5.

Position relations between nodes.

We need to calculate the distance $l_{1}$ between the upper working node and lower one, the distance $l_{2}$ between the left node and right one, and the distance $l_{3}$ that can identify the positions of $S_{a}$ and $S_{b}$ , as shown in Figure 5. Set the locations of grid points $p_{1}$ , $p_{2}$ , $p_{3}$ , and $p_{4}$ . $p_{3}$ and $p_{4}$ are at the same level, as shown in Figure 5.

$d (s_{a}, p_{1})$ is the distance between $p_{1}$ and $s_{a}$ , and $d (s_{b}, p_{2})$ is the distance between $p_{2}$ and $s_{b}$ . Both $d (s_{a}, p_{1})$ and $d (s_{b}, p_{2})$ are less than the node sensing radius $R_{s}$ . By equation (5), we know the perceived probabilities of $p_{1}$ and $p_{2}$ are both 1, greater than the minimum threshold $P_{th}$ , so the events at $p_{1}$ and $p_{2}$ can be perceived by the network. The distance between $p_{3}$ and $s_{a}$ and the distance between $p_{3}$ and $s_{b}$ are both close, but $p_{3}$ is neither in the sensing direction of $s_{a}$ nor in the sensing direction of $s_{b}$ . So $P (s_{a}, p_{3})$ and $P (s_{b}, p_{3})$ are both 0.

The probability that the nodes $s_{i}$ , $s_{j}$ , $s_{k}$ , and $s_{l}$ sense $p_{3}$ can be calculated by equation (6)

P_{st} (p_{3}) = \frac{Π_{i = 1}^{n = 4} P (s_{i}, p_{j})}{1 - \sum_{k = 1}^{n = 4} [1 - P (s_{k}, p_{j})] Π_{i \neq k}^{n = 4} P (s_{i}, p_{j})}

(9)

With the distance between the node and the grid point increasing, the node sensing probability decreases linearly in the probabilistic sensing model. Figure 6 indicates the probabilities that the different grid points are perceived by the single node. The line L is perpendicular to the sensing direction of node $s_{i}$ and they intersect at point p. Meanwhile, the line L intersects the sector radii $S_{i} A$ and $S_{i} B$ at points C and F, respectively. By equation (3), we obtain the probability of the points on the curve $\hat{ED}$ is the same as point p, which is greater than the perceived probability of points C and F.

Figure 6.

The probabilities of different grid points perceived by a single node.

Therefore, when the directional sensor works in pairs, if the node at point F can be perceived collaboratively, the point p is also perceived definitely. That is to say, if the grid point $p_{3}$ is perceived in Figure 5, $p_{4}$ is also perceived definitely. Set $P_{st} (p_{3}) \geq P_{th}$ , by equation (4), we get

P_{st} (p_{3}) = \frac{Π_{i = 1}^{n = 4} P (s_{i}, p_{j})}{1 - \sum_{k = 1}^{n = 4} [1 - P (s_{k}, p_{j})] Π_{i \neq k}^{n = 4} P (s_{i}, p_{j})} \geq P_{th}

(10)

Then, $R_{far}$ , $θ_{f}$ , d, $d (s_{i}, p_{3})$ , $d (s_{j}, p_{3})$ , $d (s_{k}, p_{3})$ , $d (s_{l}, p_{3})$ , $l_{1}$ , and $l_{2}$ can be calculated.

By cosine theorem

l_{2}^{2} = l_{1}^{2} + l_{3}^{2} - 2 l_{1} \times l_{3} \times \cos (2 θ_{f})

(11)

Get

l_{3} = \frac{l_{2}}{\sqrt{2 - 2 \cos (2 θ_{f})}}

(12)

If $l_{2}$ is identified, $l_{3}$ can be calculated. Then, the locations of $s_{a}$ and $s_{b}$ can be obtained.

In the dormancy awakening strategy, we can calculate the relative theoretical position of nodes $s_{j}$ , $s_{k}$ , $s_{a}$ , and $s_{b}$ associated with node $s_{i}$ after calculating $l_{1}$ , $l_{2}$ , and $l_{3}$ . Assume that there is a virtual node at the relative theoretical position in the monitoring area. By comparing the position of the virtual node and the position of the real node, wake up the node which is the closest to the virtual node and also has the same sensing direction with the virtual node. Repeat the awakening strategy until the network deployment is completed. In order to reduce the complexity of the algorithm, the node is waked up according to the regional block. In the proposed model, four nodes can be wakened up at a time. In Figure 5, when node $s_{i}$ is identified in the working state, the nodes $s_{j}$ , $s_{k}$ , $s_{a}$ , and $s_{b}$ can be waked up. Then, wake up the nodes in the next regional block through the nodes $s_{j}$ and $s_{k}$ , respectively. In order to guarantee the connectivity of the network, $l_{1}$ , $l_{2}$ , and $l_{3}$ are all less than $2 R_{far}$ .

Estimate the number of working nodes

$S_{area}$ represents the area of the monitoring region. The directional sensor nodes are deployed randomly and evenly distributed. The sensing direction $θ_{d}$ is distributed evenly in $[0, 2 π]$ . With the calculating method of the node number in the omnidirectional sensor network, the sensing area of the single directional sensor node s is

S_{s} = θ_{f} R_{s}^{2}

(13)

In the ideal case, it achieves the full coverage of the monitoring area, namely, $η_{c o v} = 100 %$ . $n_{per}$ represents the number of nodes required for the full coverage, which is expressed as

n_{per} = \frac{S_{area}}{θ_{f} R_{s}^{2}}

(14)

Adopting the deterministic sensing model, the probability that each sensor node can monitor the entire target area is $θ_{f} R^{2} / S_{area}$ . $η_{0}$ is the coverage requirement for the monitoring area. Assume there is no overlapping coverage after the deployment of all the directional sensor nodes. Without considering the case of boundary coverage, $n *_{per}$ represents the required number of nodes at this situation,²³ expressed as

η_{0} = 1 - {(1 - \frac{θ_{f} R_{s}^{2}}{S_{area}})}^{n *_{per}}

(15)

By equation (15), when the coverage rate of the target area achieves $P_{0}$ at least, the number of nodes deployed is

n *_{per} \geq \frac{\ln (1 - η_{0})}{\ln (S_{area} - θ_{f} R_{s}^{2}) - \ln S_{area}}

(16)

The number of nodes can be estimated from expressions (14) and (16). With the values of $n_{per}$ and $n *_{per}$ , the number of deployed nodes can be determined finally.

Algorithm description

Figure 7 shows the process given below:

Step 1. Estimate the number of nodes required by expression (16) and initialize the parameters of sensor nodes. The nodes exchange information after deployment to confirm its own location and the location of the neighbor nodes. Mark the working states of all the nodes to 1 and let $n_{work} = n$ . Go to Step 2.

Step 2. According to the preset working directions $φ_{1}$ and $φ_{2}$ ( $φ_{1} = π / 2$ and $φ_{2} = 3 π / 2$ in this article), compare the difference between the sensing direction $θ_{di}$ of sensor node $s_{i}$ and the standard working direction $φ_{1}$ (or $φ_{2}$ ). Go to Step 3.

Step 3. If $0 \leq | θ_{di} - φ_{1} | \leq π / 2$ (or $0 \leq | θ_{di} - φ_{2} | \leq π / 2$ ), the sensor node adjusts its sensing direction $θ_{di}$ to $φ_{1}$ (or $φ_{2}$ ) by rotating motion; otherwise, the sensor node adjusts the sensing direction $θ_{di}$ to $φ_{2}$ (or $φ_{1}$ ) by rotating motion. That is to say, make sure the rotating radian of the sensor node is minimal. Go to Step 4.

Step 4. Execute Step 2 and Step 3 cyclically until the sensing directions of all the deployed nodes are adjusted to the preset standard working direction $φ_{1}$ or $φ_{2}$ , mark the working states of all the nodes to 0, and let $n_{work} = 0$ . Go to Step 5.

Step 5. Starting from the lower left corner of the deployment area, randomly wake up a node and mark its working state to 1. Let the number of the working nodes be $n_{work} = 1$ . By equations (9) and (12), calculate the distance between the wakened node and its neighbor nodes $l_{1}$ , $l_{2}$ , and $l_{3}$ , respectively, and then calculate the position of the virtual node and the sensing direction. Go to Step 6.

Step 6. Comparing the position of the virtual node and the position of the actual node, if the actual node does not exist at the position of the virtual node, wake up the node which is the nearest to the virtual node and has the same sensing direction with the virtual node. If the actual node does exist, wake up it. Mark the working state of the wakened node to 1 and let $n_{work} = n_{work} + 1$ . Go to Step 7.

Step 7. Execute Step 5 on the newly wakened node. If the calculated position of the virtual node is in the monitoring area, execute Step 6; otherwise, end the step and record the number of the current working nodes as $n_{work}$ . Go to Step 8.

Step 8. Calculate the coverage rate $η_{cov}$ through D-S evidence theory inference formula (7) and (8).

Figure 7.

Flowchart.

Figure 8 is the ideal result after running from Step 1 to Step 8. Pseudo code of the algorithm is as follows:

All sensor nodes acquire the location information, time synchronization;

Make sure the working sensor nodes and other sensor nodes are turned off;

The number of the nodes in the area: n; working directions: $φ_{1}$ and $φ_{2}$ ; the threshold of the coverage: $P_{th}$ ; the threshold of the energy: $E_{th}$ ; the final coverage rate: $η_{cov}$ ; the working state of the node $s_{i} : X_{i}$ .

% make all the sensor nodes turn off

for (i = 1: n);

$X_{i} = 0$ ;

end;

% compare sensing directions with the work directions, and turn the sensing direction $θ_{di}$ of $s_{i}$

if $(0 \leq | θ_{di} - φ_{1} | \leq π / 2)$

$θ_{di} = φ_{1}$

else

$θ_{di} = φ_{2}$

end

% confirm the working nodes, choose a node, make the working state $X_{i} = 1$ ; according to the model, calculate the next working node $s_{j}$ ; the node $s_{i}$ died suddenly, run out of energy or $E_{i}_{now} \leq E_{th}$ , then

If ( $E_{i}_{now} \leq E_{th}$ && $X_{i} = 0$ && the minimum $d (s_{i}, s_{j})$ && (the $θ_{di}$ of $s_{i}$ and $s_{j}$ are the same)

$X_{j} = 1$

end

% calculating the number of the working nodes $n_{work}$

$n_{work} = 0$

for $(i = 1 : n)$

if $(X_{i} = 1)$

$n_{work} = n_{work} + 1$

end

calculating the final coverage rate $η_{cov}$

end

Figure 8.

Deployment figure of sensors after running the algorithm.

Algorithm description

After the network works for a period of time, the node is unable to work because of malfunction or its current energy $E_{now} \leq E_{th}$ ( $E_{th}$ represents the minimum energy threshold required for a node to work). Another node, which is the nearest to it and has the same sensing direction with it, has the priority to go to the working state (because of a large number of nodes deployed, assume the node with the same working direction can always be found). Execute the same operation until the energy of all the nodes is exhausted or the network cannot be connected.

In this article, the preset standard working directions are $φ_{1} = π / 2$ and $φ_{2} = 3 π / 2$ in favor of network calculation. The standard working directions can also be other directions, but it must be guaranteed that they appear in pairs and $φ_{1} + φ_{2} = 2 π$ .

It cannot be guaranteed that there is always an actual node at the position of each virtual node. Therefore, in the node-wakening process, after the ith node is wakened, there are more grids whose perceived probabilities are greater than $p_{th}$ , namely, increasing the coverage rate of the sensor network.

Assume the deployment area is rectangular and the first wakened node is on its boundary. If the nodes start to work with the standard working directions $φ_{1} = π / 2$ and $φ_{2} = 3 π / 2$ , as shown in Figure 9, at the edge of the deployment area, half or more field of view has not been utilized for each working node. It is a serious waste of resources and there exists some uncovered area. That is to say, the selected working directions of the nodes have a great impact on the utilization efficiency of the edge node. Ideally, if the viewing angle of the node is $π / 2$ and its working direction is $π / 4$ (or $3 π / 4$ ), the coverage and the utilization of the nodes on the edge can be increased significantly.

Figure 9.

The situation at the edge of the deployment area.

Simulation analysis

In the CABDS, we first assume the nodes are deployed on a large scale to ensure there are always sensor nodes at each divided grid in the monitoring area. Then adopt dormancy awakening strategy to optimize the coverage of the network. Assume the monitoring area $S_{area}$ is $500 m \times 500 m$ , the sensing radius $R_{s}$ of the sensor node is 30 m, the sensing angle of view fov is $2 θ_{f} = 60 \circ$ , the farthest sensing distance of the node $R_{far} = R_{s} + d$ , the parameter of probability sensing range $d = 10 m$ , and the threshold of sensing probability $P_{th} = 0.80$ . MATLAB is used to simulate the algorithm, and the results obtained are compared with those in the literature²⁴ adopting the IPEPCA algorithm. adopting the IPEPCA algorithm.

In the ideal situation, deploying all the sensor nodes and the coverage of the nodes has no overlap. Based on the deterministic sensing model and the probabilistic sensing model, respectively, calculating the required number of nodes $n_{per}$ by equation (14), and also calculating the required number of nodes $n *_{per}$ by equation (16) with the coverage of the monitoring area $η_{0} \geq 85 %$ . Figure 10 indicates the relation between the number of working nodes and the adopted models in two different cases. According to the probabilistic sensing model of sensor nodes, there are many probability sensing regions in the network, and the probabilistic sensing area is ignored to determine perception model. In this article, D-S evidence theory was used in the probabilistic perception sensor data fusion for improving the sensing accuracy of probabilistic sensing area, so as to improve the network coverage. It shows that adopting probabilistic sensing model, the number of nodes can be reduced significantly.

Figure 10.

The relation between the number of working nodes and the models adopted.

Figure 11 indicates the relation between the number of nodes and the coverage rate in the same monitoring area, adopting IPEPCA algorithm and the CABDS algorithm, respectively. As shown in the diagram, with the number of working nodes increasing, the coverage rates of the two algorithms are both raising, and the raising speed in the proposed algorithm is faster. When $n \geq 500$ , the raising speed becomes slow. Adopting the proposed algorithm, the coverage reaches the requirement $η_{0}$ more quickly and tends to be stable.

Figure 11.

The relation between the number of nodes and the coverage rate.

Figure 12 shows the relation among the number of nodes, the sensing angle of view, and the coverage. The sensing angle of view fov is taken as $45 \circ$ , $60 \circ$ , and $70 \circ$ , respectively. With the same number of nodes, the bigger the sensing angle of view, the higher the coverage $η_{cov}$ . When fov is $70 \circ$ , with the number of nodes increasing, the coverage $η_{cov}$ tends to be saturated soon and the growth rate becomes slow. Further increasing the number of nodes has little contribution to the overall coverage $η_{cov}$ .

Figure 12.

The relation among the number of nodes, the sensing angle of view, and the coverage rate.

Figure 13 shows the number of remaining nodes varies with time adopting two different algorithms. There are 1000 nodes deployed initially in this experiment. The initial energy of each node is 350 J, the working node consumes 2 J/h, rotating 1°consumes 0.5 J, and the node consumes 0.01 J/h during the sleep period. At the initial working of the network, the number of nodes in the two algorithms is almost the same due to the sufficient energy of nodes. After running for a period of time, in IPEPCA algorithm, the number of nodes reduces sharply because the energy of the current nodes runs out, but the network is still kept connected. Because the dormancy awakening strategy is used in this article, when a node fails, the nearest node is waked up to go to the working state fast so that the connectivity and coverage of the network are guaranteed. At the initial phase, the number of nodes decreases because of the failure of the node deployment. When the network begins to work, the working nodes are always in the state of energy consumption. With some nodes switching, the remaining nodes reduce gradually. The number of nodes in the time unit (150–200) is reduced sharply because the energy-exhausted working nodes die a lot. Then, a new round of awakening starts. Therefore, the proposed algorithm is conducive to prolong the working time of network.

Figure 13.

Remaining nodes vary with time.

Conclusion

In view of the sensor nodes randomly deployed, we establish a directional probabilistic sensing model and use the information fusion method to realize collaborative sensing through information exchange among multiple sensor nodes. If the sensing probability is greater than the preset threshold, the event is detected. Node energy is limited and it is difficult to add in WSNs, so we need to use the network energy resources reasonably. This article uses the waking-up strategy to schedule the network nodes to prolong the network lifetime. Other previous algorithms have not considered the node’s data fusion, and the node’s work direction is adjusted randomly. The algorithm CABDS uses D-S evidence theory which reduces the nondeterminacy of the information, improves the confidence level of the information, uses the standard work direction structure to make full use of the network node resources, and achieves the target coverage and meets the requirements of the overall coverage level using the least amount of nodes. The simulation results show that the proposed algorithm reduces the number of nodes effectively and guarantees the better coverage. If the large-scale deployment is used in a larger area, the required fund is very high. And it is easy to cause a waste of resources if the usage of the nodes is unreasonable. The main research in the future is to further decrease the number of nodes and add a small amount of mobile nodes to enhance the coverage to the expectation efficiently and rapidly through the sensor movement or the sensing direction adjustment.

Footnotes

Academic Editor: Haiping Huang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was partially supported by the National Natural Science Foundation of China (Grant Nos 61040010 and 61304144), Key Technologies R&D Program of Henan Province (Grant No. 152102210284), the Foundation of Educational Commission of Henan Province under the Grant No. 14B120008, and the Youth Foundation of Henan Science and Technology University under the Grant No. 2015QN022.

References

X-W

Y-J.

Wireless sensor network technology. Beijing, China: Beijing Institute Technology Press, 2007.

Mini

Udgata

Sabat

SL.

Sensor deployment and scheduling for target coverage problem in wireless sensor networks. IEEE Sens J 2014; 14(3): 636–644.

Zhao

C-J

H-R

Liu

. Optimization strategy on coverage control in wireless sensor network based on Voronoi. J Commun 2013; 34(9): 115–121.

Tao

Multimedia sensor network and its research progresses. J Softw 2006; 17(9): 2013−2028.

Jiang

. A coverage-enhance scheduling algorithm for 3D directional sensor networks. In: Proceedings of the control and decision conference, Guiyang, China, 25–27 May 2013, pp.2888–2892. New York: IEEE.

Jiang

Y-B

Wang

W-L

Chen

W-J

. Coverage optimization of occlusion-free surveillance for video sensor networks. J Softw 2012; 23(2): 310–322.

Sung

T-W

Yang

C-S.

Voronoi-based coverage improvement approach for wireless directional sensor networks. J Netw Comput Appl 2014; 39: 202–213.

K-Z

Feng

Y-H

Mao

. A greedy iterative algorithm of coverage enhancing problem in directional sensor networks. Chinese J Electron 2012; 40(4): 683–694.

Cheng

W-F

Liao

X-K

Shen

C-X.

Maximal coverage scheduling in wireless directional sensor networks. J Softw 2009; 20(4): 975–984.

10.

Wen

Jiang

Dou

W-H.

Equitable direction optimizing and node scheduling for coverage in directional sensor networks. J Softw 2009; 20(3): 644–659.

11.

Wang

Y-C

Chen

Y-F

Tseng

Y-C.

Using rotatable and directional (R&D) sensors to achieve temporal coverage of objects and its surveillance application. IEEE T Mobile Comput 2012; 8(11): 1358–1371.

12.

Liang

Tsai

Chu

TH.

Coverage enhancing algorithms in directional sensor networks with rotatable sensors. In: Proceedings of the IEEE Asia-Pacific services computing conference, Jeju Island, South Korea, 12–15 December 2011, pp.377–383. New York: IEEE.

13.

Zhao

Zeng

JC.

A virtual centripetal force-based coverage enhancing algorithm for wireless multimedia sensor networks. Sensor J 2010; 10(8): 1328–1334.

14.

Guvensan

Yavuz

AG.

A new coverage improvement algorithm based on motility capability of directional sensor nodes. Ad-hoc Mob Wirel Netw 2011; 6811: 206–219.

15.

Hekmat

Van Mieghem

Connectivity in wireless ad-hoc networks with a log-normal radio model. Mobile Network Appl 2006; 11(3): 351–360.

16.

Huang

Sun

Wang

. Improved virtual potential field algorithm based on probability model in three-dimensional directional sensor networks. Int J Distrib Sens N 2012; 2012; 942080.

17.

Liang

Chung

. A virtual force based movement scheme for area coverage in directional sensor networks. In: Proceedings of the intelligent information hiding and multimedia signal processing (IIH-MSP), Kitakyushu, Japan, 27–29 August 2014, pp.718–722. New York: IEEE.

18.

Wang

Liao

Cao

. Achieving k-barrier coverage in hybrid directional sensor networks. IEEE T Mobile Comput 2014; 13(7): 1443–1455.

19.

Chen

Cao

L-Z.

Virtual potential field and learning automata based coverage control algorithm for directional sensor networks. J Syst Eng Electron 2015; 37(5): 1177–1184.

20.

Tao

H-D.

Coverage control algorithms for directional sensor networks. J Softw 2011; 22(10): 2317–2334.

21.

Wang

M-H

Long

New target coverage algorithm in dynamic vision sensor networks. Appl Res Comp 2012; 5(27): 1708–1711.

22.

Pan

Cheng

Y-M

Yan

. Multi-source information fusion theory and application. Beijing, China: Tsinghua University Press, 2013.

23.

Liu

. On coverage problems of directional sensor networks. In: Proceedings of the first international conference on mobile ad-hoc and sensor networks, vol. 3794, Wuhan, China, 13–15 December 2005, pp.721–731. Berlin, Heidelberg: Springer.

24.

Wang

A path coverage-enhancing algorithm for directional sensor network based on improved potential field. J Comp Res Dev 2009; 46(12): 2126–2133.