A Stochastic k -Coverage Scheduling Algorithm in Wireless Sensor Networks

Abstract

Coverage is one of the key issues to achieve energy efficiency of a wireless sensor network. Sensor scheduling is one of the most important methods to solve coverage problems. It can ensure the coverage degree of a region and prolong the network lifetime. In this paper, we focus on the k-coverage scheduling problem to guarantee k-coverage sensing and network connectivity. We consider both deterministic and stochastic sensing models of the sensors and adapt the results of deterministic sensing model to solve the sensor scheduling problem under the stochastic sensing model. We use regular pentagons to divide the sensing disks to solve the k-coverage problem. Each sensor node runs a stochastic k-coverage-preserving scheduling algorithm to determine its work modes, and redundant nodes can enter into sleep mode, while active nodes ensure the coverage of the network. Theoretical analysis and simulation results show that our algorithm can reduce the number of active nodes and extend the network lifetime significantly while maintaining a given coverage degree.

1. Introduction

Wireless sensor networks (WSNs) are composed of a large number of sensor nodes, which are densely deployed in a given region. All nodes collaborate to execute sensing and monitor tasks and to send sensed data to sinks. It has so far been employed in military activities, target acquisition, environmental activities, and civil engineering. On the one hand, each sensor is equipped with a limited power source, and it is impossible to replenish power resources in most applications. On the other hand, many applications require a durable lifetime. Thus, a major constraint for WSNs to be widely used is network lifetime.

Since wireless sensor networks are characterized by high density and limited energy. It is not necessary to have all sensor nodes operate in active mode simultaneously. Sensor scheduling, the most effective method to solve coverage problems, makes redundant nodes into sleep mode, in which energy consumption is lower, while active nodes meet specialized requirements. It can decrease the number of active nodes, thus avoiding the channel collision, reducing the network energy consumption, and prolonging the network lifetime substantially. However, most of the existing results on k-coverage are based on the deterministic sensing model, where a point in a region is guaranteed to be covered by k sensors, that is, the point is within the sensing ranges of those k sensors.

In this paper, we consider the k-coverage sensor scheduling problem. A more realistic sensing model, called stochastic sensing model, was considered. Under the stochastic sensing model, a point is covered by a sensor with some probability. Firstly, we solve the sensor scheduling problem of k-coverage under the deterministic sensing model. Then, we utilize the results to solve the problem under the stochastic sensing model. Finally, we present a stochastic k-coverage-preserving sensor scheduling algorithm to achieve lifetime extension. We use regular pentagon instead of Reuleaux Triangle to achieve k-coverage and give the minimum number of sensors to fully k-cover a region while ensuring the connectivity. Theoretical analysis and comprehensive simulation show that our approach is effective.

The rest of the paper is organized as follows. Section 2 discusses the related works of this paper. Section 3 introduces the network models and definitions. Section 4 gives a detailed description of our algorithm. Section 5 presents simulation results of our algorithm. Conclusion is given in Section 6.

2. Related Work

In [1, 2], Zorbas et al. divided sensor nodes into different cover sets, where the sensors in each set are capable of monitoring all targets in the region. By activating one cover set at a time, the sensors network lifetime can be extended. Erlebach et al. also used sensors set partition to solve events detection problem, and proposed an approximation algorithm to maximize the lifetime of WSNs [3]. In [4], Ammari used Reuleaux Triangle to solve the sensor scheduling problem for k-coverage under the deterministic sensing model, where each node runs a k-coverage candidacy algorithm and gives a distributed sleep-wakeup scheduling protocol for stochastic k-coverage (SCPk) of a region. In many applications, critical areas and common areas must be distinguished adequately, and it is more practical and useful to monitor critical areas rather than common areas, or the available budget cannot provide enough sensors to fully cover the sensor field. In [5], Ammari and Das improved the former method to decrease the bound of sensor spatial density and proved that when the ratio of the radius R of the communication range to the radius r of the sensing range of sensors be at least equal to one, the generated network is connected. In [6], Ke et al. proposed an approximation algorithm for critical-square-grid coverage. In [7], Xing et al. presented a novel protocol that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity, integrated CCP with SPAN [8] to provide both coverage and connectivity guarantees, proposed a probabilistic coverage model, and extended CCP to provide probabilistic coverage guarantees.

In [9], n nodes were placed over a unit area in an unreliable wireless sensor grid network, Shakkottai et al. proposed an algorithm that can meet coverage requirements and connectivity. Chakrabarty et al. presented a novel grid coverage strategy for effective surveillance and target location in distributed sensor networks in [10]. They gave a coding-theoretic bounds on the number of sensors and presented methods for determining their placement in the interesting region. And the result showed that grid-based sensors placement for single target provides asymptotically complete location of multiple targets in the grid. The exposure in WSNs, which is related to the quality of coverage provided by WSNs, was studied in [11] based on a general sensing model, where the sensing signal of a sensor at an arbitrary point was measured by a function that is inversely proportional to the distance between the sensor and the point. Based on the concept of connected dominating set (CDS), a distributed approach for active sensors selection in [12] was proposed to fully cover a region. This approach is based on a probabilistic sensing model, where the probability of the existence of a target is defined by an exponential function that represents the confidence level of the received sensing signal. In [13], Yang et al. selected the minimum number of sensor nodes to fulfill k-coverage and proposed a centralized solution based on integer linear programming and a distributed algorithm called PKA, which uses Pruning methods to reduce the number of active nodes.

A joint scheduling scheme based on a randomized algorithm for providing statistical sensing coverage and guaranteed network connectivity was presented in [14]. This scheme works without the availability of per-node location information, to schedule sensor nodes for energy saving and meet constraints, both sensing area coverage and network connectivity without accurate location information. Mao et al. proposed an energy efficient connected coverage protocol (EECCP) based on the analytical results and the existing algorithms, which constructs the connected dominating set in [15]. Extensive simulation studies show that the protocol can effectively maintain both high quality sensing coverage and connectivity for a long time.

Many applications do not require complete coverage all the time. For such applications, one effective method to save energy and prolong network lifetime is to partially cover the area. In [16], Zorbas et al. analyzed the problem of connected partial target coverage, where cover sets are allowed to monitor a subset of the targets at any point in time, while connectivity with the base station is retained. The simulation results show that monitoring $\mathrm{90}\%$ of the targets may yield twice the network lifetime provided by a full coverage approach. In [17], Li et al. proposed a framework that can transform almost any existing complete coverage algorithm to a partial coverage one with any coverage ratio by running a complete coverage algorithm to find full coverage sets with virtual radii and converting the coverage sets to partial coverage sets via adjusting sensing radii. The framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity.

In [18–20], coverage problems in heterogeneous WSNs were considered. In [18], Jin et al. proposed a location-independent, energy-efficient routing algorithm EECCR, which simultaneously preserves the network m-coverage ratio and the sensor n-connectivity probability. In [19], Khedr and Osamy introduced two new efficient distributed algorithms for finding the minimum number of connected perimeter sensor nodes that are sufficient to cover the perimeter of queried region, and the algorithm can preserve full perimeter coverage. In [20], the relay nodes were deployed to provide fault tolerance with higher network connectivity in heterogeneous wireless sensor networks, where sensor nodes possess different transmission radii.

In [21], El Salti and Nasser introduced a new approach for obtaining a fully covered network such that every single point in a region is fully covered by at least one sensor node. This approach is referred to as the chipset coverage model and algorithm.

In this paper, we use regular pentagon to solve the k-coverage problem under deterministic and stochastic sensing models. We propose a stochastic k-coverage sensor scheduling algorithm, theoretical analysis and simulation results show the correctness and superiority of our algorithm.

3. Network Model and Definition

3.1. Network Model

In this section, we present some reasonable assumptions and introduce both deterministic sensing model and stochastic sensing model. All sensors and the sink are static and aware of their locations via a localization technique [22].

All sensors are randomly and nonuniformly deployed in a planar region. The sensors are homogeneous and have determined sensing and communication ranges of radii r and R, respectively. The location of a sensor s in the region is denoted by ${\xi }_s$ .

Deterministic sensing model is also known as perfect sensing model, where a point ξ in a region is covered by a sensor s based on the Euclidean distance $\delta (\xi ,s)$ between ξ and s. This model considers the sensing range of a sensor as a disk, and hence sensing ability of all sensors is determined and has no uncertainty.

Stochastic sensing model considers the signal attenuation and the presence of noise. It is necessary to consider a more realistic sensing model by defining the coverage $\text{Cov}(\xi ,s_i)$ of a point ξ by $s_i$ using some probability function. Here, in our stochastic sensing model, the coverage $\text{Cov}(\xi ,s_i)$ is defined as the probability of detection $p(\xi ,s_i)$ of an event at ξ by $s_i$ as follows.

$$\begin{array}{cc}& p\left(\xi ,s_i\right)=\{\begin{array}{cc}{e}^{-\beta \delta {\left(\xi ,s_i\right)}^{\alpha }},\hfill & \delta \left(\xi ,s_i\right)\le r\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(1)

where β represents the physical characteristic of sensing units of sensors and $2\le \alpha \le 4$ is the path-loss exponent. The uncertainty sensing capability of a sonar sensor is modeled by a Gaussian probability density function $p(r\mid z,\theta )=(\mathrm{1}/\mathrm{2}\pi {\sigma }_r{\sigma }_{\theta })\exp [-(\mathrm{1}/\mathrm{2})((r-z{)}^{\mathrm{2}}/{\sigma }_r^{\mathrm{2}}+{\theta }^{\mathrm{2}}/{\sigma }_{\theta }^{\mathrm{2}})]$ [4]. Where r and θ represent sensing range and angel, respectively.

3.2. Definitions

Definition 1 (k-coverage).

Under the deterministic sensing model, a point ξ in a region is said to be k-covered if it belongs to the intersection of the sensing disks of at least k sensors. Under the stochastic sensing model, a point ξ in a region is said to be probabilistically k-covered if the detection probability of an event occurring at ξ by at least k sensors is at least equal to some threshold probability of $p_{\text{th}}$ ( $0<p_{\text{th}}<1$ ). For both sensing models, a region is said to be k-covered if every point ξ in the region is k-covered.

Definition 2 (reuleaux triangle).

Construct an equilateral triangle. On each vertex, center a compass and draw the minor arc between the other two vertices. The perimeter will be three nonconcentric; arcs, this is a Reuleaux Triangle. The minimum overlap area of two adjacent slices forms a lens.

As shown in Figure 1, the gray area is a Reuleaux Triangle and $becf$ is a lens.

Figure 1

A Reuleaux Triangle and One lens.

Definition 3 (central area).

Construct a regular pentagon, on each vertex, center a compass, and draw the arc between the other two adjacent vertices.

The five nonconcentric arcs form the central area of the regular pentagon, as shown in Figure 2.

Figure 2

Central area of a regular pentagon.

Definition 4 (width of regular pentagon).

The width of regular pentagon is the maximum of the distances between any pair of parallel lines that bound it.

Definition 5 (zero direction).

We take the position of a sensor s as the datum point when dividing the sensing disk and then give another point to determine a line segment. The direction of the line segment is zero direction. We use zero direction to determine the position of regular pentagon vertices.

As shown in Figure 3, take position o as the datum point, if the zero direction is $(o,p_{\mathrm{1}})$ , the angle of $\angle p_{\mathrm{4}}o{p}_{\mathrm{1}}={\mathrm{90}}^{°}$ . Similarly, when we take the other points $p_{\mathrm{2}}$ , $p_{\mathrm{3}}$ , or $p_{\mathrm{4}}$ , the angles between zero direction and x axis equal $\mathrm{6}{\mathrm{0}}^{°}$ , $\mathrm{3}{\mathrm{0}}^{°}$ , and ${\mathrm{0}}^{°}$ , respectively.

Figure 3

The zero direction.

4. A Stochastic k-Coverage Sensor Scheduling Algorithm

In this section, we analyze the k-coverage problem in WSNs using the deterministic sensing model and give the minimum required number of nodes to achieve k-coverage. Then, we utilize this result to the stochastic sensing model, get the stochastic sensing range $r_s$ of the sensors that is necessary to probabilistically k-cover a region, and present the stochastic k-coverage-preserving sensor scheduling algorithm

4.1. The Deterministic Sensing Model

In order to characterize k-coverage, we need to compute the maximum size of an area, which is k-covered with exactly k sensors. To this end, we introduce a fundamental result of convex set theory, known as Helly's theorem [4], which characterizes the intersection of convex sets. We exploit this theorem in a regular pentagon to characterize k-coverage of sensing disks. Then, we compute the minimum number of sensors required for a k-coverage.

Theorem 6 (see Helly [4]).

Let E be a family of convex sets in $R^n$ such that any m members ( $m\ge n+\mathrm{1}$ ) of E have a nonempty intersection. Then, the intersection of all members of E is nonempty.

The following Lemma is an instance of Helly's Theorem in two-dimensional space that characterizes the intersection of k sensing disks.

Lemma 7.

Let $D_{\mathrm{1}},D_{\mathrm{2}},\dots ,D_k$ ( $k\ge 3$ ) be disks in the plane $R^{\mathrm{2}}$ . If the intersection of any three disks of the k sensing disks is not empty, then the intersection of the k sensing disks is not empty.

By Lemma 7, the following Lemma 8 gives a sufficient condition for k-coverage of a region.

Lemma 8.

A regular pentagon is k-covered if the central area of the regular pentagon contains at least k active sensors $(k\ge 3)$ .

Proof.

According to Definition 3, the maximum distance among those k sensor nodes and the boundary of the regular pentagon is r, as shown in Figure 2. For the central area lies in the inside of the regular pentagon, its width is smaller than r. Thus, the intersection of any three of those k sensing disks is not empty. We can know that the regular pentagon is k-covered by Lemma 7.

We can get the following observation. When we use regular pentagons to cover a sensing disk, if any central area of regular pentagons contains at least k active sensors, the sensing disk is k-covered. If every sensing disk in the region is k-covered, then the whole region is k-covered.

Theorem 9.

Let r be the radius of sensing disks of sensors and $k\ge 3$ . The minimum number of sensors $n(r,k)$ to k-cover a region with area F is given by

$$\begin{array}{cc}& n\left(r,k\right)=\lceil \frac{\mathrm{4}Fk}{\sqrt{\mathrm{25}+\mathrm{10}\sqrt{\mathrm{5}}}{r}^{\mathrm{2}}}\rceil .\end{array}$$

(2)

Proof.

We use regular pentagons to cover a sensing disk, the area formula of the regular pentagon is $S=(\sqrt{\mathrm{25}+\mathrm{10}\sqrt{\mathrm{5}}}/\mathrm{4})r^{\mathrm{2}}$ , we can get that the minimum area those k nodes can cover is S. Thus, the minimum number of sensors to k-cover a region of area F is $n(r,k)=\lceil F/S\rceil =\lceil \mathrm{4}Fk/\sqrt{\mathrm{25}+\mathrm{10}\sqrt{\mathrm{5}}}{r}^{\mathrm{2}}\rceil$ .

Theorem 10.

A k-covered WSN is connected if $R\ge \sqrt{\mathrm{3}}r$ .

Proof.

As shown in Figure 4, the distance between point a and b is the maximum distance of sensor nodes in two adjacent regular pentagons. Thus, $\delta (a,b)=\mathrm{2}r\cos {\mathrm{30}}^{°}=\sqrt{\mathrm{3}}r$ . Therefore, as long as the communication radius is not less than $\sqrt{\mathrm{3}}r$ , the sensor nodes in the two regular pentagons can communicate with each other, and the network is connected.

Figure 4

Communication radius and sensing radius.

4.2. The Stochastic Sensing Model

In this section, we utilize the results of Section 4.1 to characterize probabilistic k-coverage. Theorem 11 computes the minimum k-coverage probability $p_{k,\min }$ .

Theorem 11.

Let r be the radius of the determined sensing range of the sensors and $k\ge 3$ . The minimum k-coverage probability such that each point in a region is probabilistically k-covered by at least k sensors under the stochastic sensing model is given by

$$\begin{array}{cc}& p_{k,\min }=\mathrm{1}-{\left(\mathrm{1}-e^{-\beta r^{\alpha }}\right)}^k.\end{array}$$

(3)

Proof.

We should deploy k sensors in the central area to k-cover a regular pentagon. The sensing ability of sensors attenuates with the increase of the distance. The farthest point away from the sensors is the five vertices of the regular pentagon (see Figure 2). Thus, the vertices have the smallest probability to be k-covered by the sensors in central area. When all sensors are deployed on the arc of the curved pentagon, the distance between sensors and corresponding vertex equals r. Thus, the minimum k-coverage probability for the least k-covered point ξ by k sensors under the stochastic sensing model is given by $p_{k,\min }=\mathrm{1}-{\prod }_{i=\mathrm{1}}^k‍(\mathrm{1}-p(\xi ,s_i))=\mathrm{1}-(\mathrm{1}-e^{-\beta r^{\alpha }}{)}^k$ .

The stochastic k-coverage problem is to select a minimum subset $S_{\min }\subseteq S$ of sensors such that each point in a region is k-covered by at least k sensors and the minimum k-coverage probability of each point is at least equal to some given threshold probability $p_{\text{th}}$ , where 0 $<p_{\text{th}}<$ 1. This helps us to compute the stochastic sensing range $r_s$ , which provides probabilistic k-coverage of a region with a probability no less than $p_{\text{th}}$ . The following lemma computes the value of $r_s$ .

Lemma 12.

Let $k\ge 3$ and $2\le \alpha \le 4$ . The stochastic sensing range $r_s$ of the sensors that is necessary to probabilistically k-cover a region with a minimum number of sensors and with a probability no lower than $p_{\text{th}}$ is given by

$$\begin{array}{cc}& r_s={\left(-\frac{\mathrm{1}}{\beta }\ln \left(\mathrm{1}-{\left(\mathrm{1}-p_{\text{th}}\right)}^{\mathrm{1}/k}\right)\right)}^{\mathrm{1}/\alpha },\end{array}$$

(4)

where β represents the physical characteristic of sensing units of sensors.

Proof.

The proof is simple. Let $p_{k,\min }\ge p_{\text{th}}$ , we can easily get $r_s\le (-(\mathrm{1}/\beta )\ln (\mathrm{1}-(\mathrm{1}-p_{\text{th}}{)}^{\mathrm{1}/k}){)}^{\mathrm{1}/\alpha }$ .

The following theorem states a sufficient condition for probabilistic k-coverage based on our stochastic sensing model, $p_{\text{th}}$ and k.

Theorem 13.

Let $k\ge 3$ . We use regular pentagons to divide all the sensing disks in the region. The length of sides of regular pentagon is $r_s$ . If any central area of regular pentagons contains at least k active sensors, then the region is stochastic k-covered with a probability no lower than $p_{\text{th}}$ $(0<p_{\text{th}}<1)$ .

The following Lemma states a sufficient condition for connectivity among sensors under our stochastic sensing model as follows.

Lemma 14.

Let $k\ge 3$ . The sensors that are selected to k-cover a region with a probability no less than $p_{th}$ under the stochastic sensing model are connected if the radius of their communication range is at least equal to $\sqrt{\mathrm{3}}{r}_s$ , where $r_s$ is the stochastic sensing range of the sensors.

4.3. ISCPk-An Improved Stochastic k-Coverage-Preserving Sensor Scheduling Algorithm

In this section, we present the stochastic k-coverage-preserving sensor scheduling algorithm. It is a distributed sleep-wakeup sensor scheduling algorithm. One can gain stochastic k-coverage and connectivity by executing this algorithm. Suppose N sensors are randomly and nonuniformly deployed in a planar region. The sensor network has the following properties.

• (1)

  Stochastic sensing model considers the signal attenuation and noise.

• (2)

  Sensors cannot move after they are deployed, and battery energy cannot be recharged.

• (3)

  Each node has a globally unique $\text{id}$ .

• (4)

  R and r represent communication and sensing ranges, respectively, ( $R\ge \sqrt{\mathrm{3}}{r}_s$ ).

• (5)

  In sleep mode, sensor node will turn off its sensing and communication functions.

The algorithm can be described as follows.

Step 1.

Compute stochastic sensing range $r_s$ and the list of the neighbor-sensor of each node.

According to α, β, k, and $p_{\text{th}}$ , calculate $r_s$ . Each node maintains a neighbor sensor list, a work set count flag WSC, and a redundancy flag RF. Initially, $\text{RF}=\mathrm{0}$ and $\text{WSC}=\mathrm{1}$ .

Step 2 (select redundant nodes).

(1) Provide a zero direction, each node divides its sensing disk into three $\mathrm{10}{\mathrm{8}}^{°}$ and one $\mathrm{3}{\mathrm{6}}^{°}$ sector regions. Take the two radii of each sector region with $\mathrm{10}{\mathrm{8}}^{°}$ as two sides of a regular pentagon we can get three regular pentagons. The fourth regular pentagon is as shown in Figure 5, the dashed line one. We use these four regular pentagons to cover a sensing disk.

(2) If every central area of four regular pentagons contains at least k active sensors with the same value of flag $\text{WSC}$ equalling to the central sensor's, then the sensing disk is k-covered.

(3) Decide whether the sensing disk is k-covered according to (2), then determine the node is redundant or not, select out the redundant nodes.

Figure 5

Regular pentagons division of a sensing disk.

Step 3 (sensor scheduling).

(1) Each node with $\text{RF}=\mathrm{0}$ executes Step 2 to determine itself redundant or not by ascending order according to $\text{id}$ . Redundant nodes change their RF to 1 and send an activate message to the nodes in the central areas; these activated nodes change their RF to 0, nonredundant nodes keep RF values 0.

(2) If there are still other sensor nodes in the sensing range of redundant nodes except those nodes in four central areas, then redundant nodes send a message to those nodes, change their RF to 2. Thus, they do not need to run Step 2, since they have already been k-covered by the activated nodes.

(3) If a redundant node receives activate message from other nodes, it indicates that the node activation enabling the sensing disk of one sensor is k-covered, then change RF from 1 to 0.

(4) Record the number of redundant nodes as m. Assume the area of the graph in Figure 5 equals A. The algorithm iterate execute Steps 2 and 3 until $m\ge 3\lceil F/A\rceil$ , where F is the area of the region.

Step 4 (enter into work mode).

At the beginning, every node determines their mode according to RF, nodes with RF equal to 1 and 2 sleep and increase $\text{WSC}$ by one, while the other nodes work. Those sleeping nodes will be awake after $T_{\text{sleep}}$ . And these nodes will modify their RF to 0 and execute Step 3. Here we assume that $T_{\text{sleep}}$ is smaller than the period of one sensor working. Since $T_{\text{sleep}}$ is smaller, when the active nodes run out of energy, a number of these once sleep nodes have already turned into work mode. Thus, the network will not be affected by nodes failure.

5. Theoretical Analysis

In this section, we evaluate and analyze the performance of the proposed algorithm.

Theorem 15.

The ISCPk algorithm is capable of generating at least one solution, if the solution exists.

Sketch of Proof

Note that sufficient number of nodes were deployed to ensure k-coverage of the region. During the execution of the algorithm, we take $m\ge 3\lceil F/A\rceil$ as the terminate condition, where $\lceil F/A\rceil$ indicates the optimum result of the algorithm. Three times of the optimum result can ensure full coverage of the region. For the deployed nodes are sufficient, thus, we can get a reasonable solution to k-cover the region. The algorithm is proved to be correct.

Theorem 16.

For ISCPk, the message complexity is $O(N)$ and time complexity is $O(N^{\mathrm{2}})$ , respectively. Where N is the number of sensors.

Sketch of Proof

Assume that we deployed N sensors in the region, let ∆ be the maximum node degree, that is, the maximum size of neighbor sensors list. Assuming no packet loss, every node broadcasts a message to obtain its neighbor sensors list in Step 1. If we can get l redundant nodes in Step 2, every redundant node sends an active or redundant message to the neighbor nodes in the sensing range of redundant nodes. The network sends at most $N+l∆$ messages in each iteration. Since $l∆$ is much smaller than N, thus, the message complexity of ISCPk is $O(N)$ . Provided that each operation of the algorithm takes one unit of time. The calculation of $r_s$ and redundant nodes selection takes $O(N)$ and $O(N^{\mathrm{2}})$ time, respectively. The other operations of the algorithm takes at most $O(N)$ time. Therefore, the time complexity for the proposed distributed algorithm is $O(N^{\mathrm{2}})$ .

Our algorithm and the algorithm in [4] are both to k-cover a sensing disk before k-cover a region firstly, then to k-cover the whole region. The difference between the two algorithms is the way to divide the sensing disk. In [4], a sensor randomly decomposes its sensing disk into six Reuleaux Triangles with width $r_s$ . If the lens of each of the three pairs of adjacent slices contains at least k active sensing neighbors, then the sensing disk is k-covered. According to the algorithm in [4], it needs 3k nodes to k-cover a sensing disk, while our algorithm needs 4k nodes to k-cover a sensing disk. It seems that our algorithm require more nodes to k-cover a region. However, that is not the case.

We consider the node utilization from the coverage area of every k nodes, in [4]; 3k nodes can k-cover an area of $S_{\mathrm{1}}$ = $\pi r^{\mathrm{2}}$ . 4k nodes can k-cover an area of $S_{\mathrm{2}}=(\sqrt{\mathrm{25}+\mathrm{10}\sqrt{\mathrm{5}}}-\mathrm{4}\sin {\mathrm{18}}^{°}\cos {\mathrm{54}}^{°})r^{\mathrm{2}}$ in our algorithm; it is equal to 4 times the area of a pentagon minus the area of overlap, as shown in Figure 5. We can get that $S_{\mathrm{1}}/\mathrm{3}<S_{\mathrm{2}}/\mathrm{4}$ .

By the analysis above, we can see that the number of sensors in our algorithm k-covering a single-sensing disk is greater than the method in [4], but the average cover area for each k node is larger than [4].

6. Simulation Results

In this section, we present the simulation results of our algorithm. Simulation parameters are shown in Table 1, the algorithms in this paper and [4] are represented by ISCPk and SCPk, respectively.

Table 1

Simulation parameters.

Parameter	Value
Region area 1 (deterministic model)	$\mathrm{400}\hspace{0.17em}\text{m}\times \mathrm{400}\hspace{0.17em}\text{m}$
Region area 2 (stochastic model)	$\mathrm{60}\hspace{0.17em}\text{J}$
Transmission energy consumption	$\mathrm{0.06}\hspace{0.17em}\text{J/s}$
Receive energy consumption	$\mathrm{0.012}\hspace{0.17em}\text{J/s}$
Idle energy consumption	$\mathrm{0.012}\hspace{0.17em}\text{J/s}$
Sleep energy consumption	$\mathrm{0}$

6.1. Sample Topology

900 nodes are randomly and nonuniformly deployed in a planar region of 400 m × 400 m. We consider deterministic sensing model, the sensing radius is 70 m, use the deployed nodes to fulfill 2-coverage of the region. We take the angle equals ${\mathrm{30}}^{°}$ . The initial topology is as shown in Figure 6.

Figure 6

Initial node distribution.

Figure 7 shows the distribution of redundant and active nodes after the execution of our algorithm, where red and blue nodes indicate redundant and active nodes, respectively. The green nodes in Figure 7 are the sensors in the sensing range of redundant nodes. Since the selected active nodes can fully cover the region, the green and black nodes are redundant nodes too, even though they cannot meet the redundant definition which we define. Thus, the number of redundant and active nodes is 134 and 766, respectively.

Figure 7

Redundant and active nodes.

The regular pentagon division of a redundant node is shown in Figure 8; the red small circle represents the near central area of a regular pentagon.

Figure 8

The regular pentagons cover a sensing disk.

Figure 9 shows the regular pentagon division of 17 redundant nodes in the region. The green circles represent the sensing range of the redundant nodes (red nodes), red small circles indicate the near central area of regular pentagons, and blue nodes denote the selected active nodes.

Figure 9

The regular pentagons cover the region.

Figure 10 gives the 2-coverage of the region, blue nodes are the selected active nodes, and we draw the sensing ranges of the active nodes. We can see from Figure 10 that active nodes can 2-cover the whole region.

Figure 10

Active nodes 2-cover to the region.

During the simulation process, we find that the zero direction has great influence on our experimental results. Figure 11 shows the relation between the zero direction and the selected nodes. The abscissa indicates the angle of zero direction. As shown in Figure 11, the selection of zero direction has a great influence on the simulation results. Thus, we change the zero direction in the next iteration to reduce the influence of zero direction to the experimental results.

Figure 11

The relation between the degree of angle and the selected nodes.

6.2. Simulation Results on Various Parameters

Figure 12 shows the sensor spatial density versus k, $p_{\text{th}}$ , and α. Sensor spatial density equals the ratio of $n(r,k)$ and region area F, that is, $n(r,k)/F=\lceil \mathrm{4}k/\sqrt{\mathrm{25}+\mathrm{10}\sqrt{\mathrm{5}}}{r}_s^{\mathrm{2}}\rceil$ , where $r_s=(-(\mathrm{1}/\beta )\ln (\mathrm{1}-(\mathrm{1}-p_{\text{th}}{)}^{\mathrm{1}/k}){)}^{\mathrm{1}/\alpha }$ and $\beta =0.02$ . Theoretical analysis shows that when k, $p_{\text{th}}$ , and α increase, the number of nodes which meet threshold $p_{\text{th}}$ increases too, so we need more nodes to achieve k-coverage. As shown in Figure 12, we find a good matching between the simulation and theoretical analysis.

Figure 12

Sensor spatial density versus k, $p_{\text{th}}$ and α.

The achieved degree of coverage k versus the total number of deployed sensors is shown in Figure 13.

Figure 13

Achieved degree of coverage k versus the number of sensors.

We can get the relation between k and $n(r_s,k)$ through Theorem 9. As shown in Figure 13, the number of nodes increases as k, but our algorithm needs smaller number of nodes than that of [4], when they have the same coverage degree k.

Figure 14 shows that the number of active sensors required to provide 3-coverage increases with the physical characteristic β of the sensors. The number of active sensors increases with β, but our algorithm needs smaller number of active nodes to achieve 3-cover than the algorithm in [4].

Figure 14

The number of active sensors increases with the physical characteristic β of the sensors.

Figure 15 shows the impact of $p_{\text{th}}$ on the network lifetime to fulfill 3-coverage. As mentioned earlier, higher values of $p_{\text{th}}$ require larger number of active sensors, and hence the network consume much energy. As shown in Figure 15, we deploy 30000 nodes in the region, the total initial energy is $1.8\times {\mathrm{10}}^{\mathrm{6}}$  J. As time progresses, the residual energy of the network gradually reduces, but our algorithm can save network energy consumption effectively.

Figure 15

The impact of $p_{\text{th}}$ on the network lifetime to provide 3-coverage.

7. Conclusion

In this paper, a distributed approach for sensor scheduling in stochastic k-covered WSNs is proposed. First, we characterize k-coverage in WSNs and provide a sufficient condition for k-coverage with a minimum number of sensors. Then, we present our stochastic k-coverage-preserving node scheduling algorithm. Theoretical analysis and simulation results indicate the correctness and superiority of the algorithm. The algorithm can k-cover a larger area than that of [4] while using the same number of nodes, and it can reduce network energy consumption and prolong the network lifetime effectively. We will extend our algorithm to three-dimensional and heterogeneous WSNs in the future.