A Novel Energy-Efficient k -Coverage Algorithm Based on Probability Driven Mechanism of Wireless Sensor Networks

Abstract

In the process of fulfilling k-coverage over target nodes, a large quantity of redundant data may be produced, which will cause network congestion, reduce communication efficiency, impair coverage quality, and exhaust network energy quickly. To solve this problem, the paper proposes an Energy-Efficient k-Coverage Algorithm (EEKCA), which attempts to construct a network coverage model by utilizing the relative positions of nodes. Through analyzing the model, the coverage expectations for nodes in the monitored area and the minimum number of nodes required for full coverage are computed. As for power consumption, the paper presents an energy shifting function between working nodes and neighboring nodes, by use of which the scheduling for low-energy node is completed, balancing the energy consumption over the entire network and optimizing network resources. Finally, simulation results suggest that the proposed algorithm not only can improve the coverage quality of network but also can prevent the rapid depletion of node energy, thus achieving the goal of extending network lifetime.

1. Introduction

Wireless sensor network [1] (WSN) is a new type of ad hoc network architecture consisting of thousands of sensor nodes [2, 3]. Each node can fulfill certain functions such as perceiving [4], computing [5], communicating [6], and storing [7, 8]. By gathering sensory information from physical environment and transmitting them through multihop routing [9], these nodes integrate physical world with information world [10, 11], creating a chain-like network service system which combines data collection, storage, computation, and transmission [12, 13].

Coverage quality and power consumption are two chief indexes to evaluate the performance of WSN [14]. Coverage quality depends on the way that nodes are deployed over a region of interest [15, 16]. Network lifetime, which is closely linked with the energy consumption of nodes, directly affects the quality of service (QoS) of the whole network [4, 17]. Generally, nodes are distributed randomly over a region due to complicated terrain conditions and harsh environment limitations. As precise location information cannot be acquired in advance, one monitoring area may be put under the sensing range of more than one node, causing k-coverage, as is the case in military battlefield shown in Figure 1, or it may become a blind spot where no sensing signals can be received and which calls for additional nodes for coverage. Firstly, when k-coverage exists, a large quantity of redundant data is certainly to be produced during the process of data collection, computation, and transmission, which will make the whole WSN more vulnerable to error and uncertainty. Secondly, the goal of coverage is not to have each point in an area under supervision but to merely focus on a set of targets instead, so an undifferentiated area coverage scheme ignorant of the precise location of targets will cause waste of energy and bring down the system more quickly. Thirdly, in a random distribution scheme, it is inevitable that an area may be packed with an excessive number of nodes, causing bottle-necking effect and information redundancy in communication channel and impairing network expansibility.

Figure 1

Topological graph for coverage in military battlefield.

To address the problems above, the paper proposes an Energy-Efficient k-Coverage Algorithm (EEKCA), which intends to solve the coverage rate and expectation coverage of a sensor node with a sector area formed while mobile sensors are moving across monitoring area. As for power consumption, the paper presents the solution to multipoint transmission and single-point transmission. Provided that a required coverage rate is reached, when a working mobile target node is moving across k-coverage area and its energy consumption is within or above the upper limit of the threshold values, the node will be switched to sleeping mode under self-adaptive switching scheme, while other sensor nodes are using node energy scheduling mechanism to finish the conversion process for sensor node energy in order to improve the network life cycle.

A is the base station. There are five sensor nodes in all in the monitored area. The pentagrams mark target nodes. From Figure 2, it can be seen that the sensor layer includes 5 interconnected sensor nodes, which are ordered to collect different types of data and form several clustering structures by certain rules. Node A is called Sinks layer, the primary function of which is to equip sensor nodes at the layer with more powerful computation, storage, and energy supply capability and to send data collected at the layer to base station. Each node at the sensor layer covers several target nodes, thus forming the correspondence between nodes and target nodes. Node B corresponded to the region between target node 1 and node 2; Node C corresponded to the region between target node 2, node 5, node 6, and node 8; Node D corresponded to the region between target node 7 and node 8; Node E corresponded to the region between target node 2, node 3, and node 5; Node F corresponded to the region between node 3, node 4, node 5, and node 6. Through the correspondence, we can obtain the minimum target set $S=\left\{\mathrm{B},\mathrm{D},\mathrm{F}\right\}$ and maximum target set $T=\left\{3,4,5,6\right\}$ .

Figure 2

Topological graph for k-coverage.

When more sensor nodes are added, one target node may be covered by and corresponding to several sensor nodes, a case we call k-coverage. For example, node 2 and node 5 are under k (k = 3)-coverage, and node 6 and node 8 are under k (k = 2)-coverage. When the coverage of a target node exceeds itself, a large number of redundant nodes are to be generated, which will exhaust the energy of the whole network system quickly and shorten the lifetime of the network. In order to avoid the redundancy of nodes, it is necessary to keep each node at different status and to realize shift between different states.

2. Network Model and Coverage Quality

In order to better facilitate the analysis of the coverage problem of WSN, the following hypotheses are proposed [18, 19]:

• (1)

All the sensor nodes are in isostructure; the sensing radius and transmitting radius are in circular shape.

(2)

Each sensor node can acquire its location information through GPS.

(3)

All the sensors have the same initial energy and sensing radius and are time-synchronized.

(4)

All the sensor nodes are randomly deployed over a square region with l on each side. It is ensured that the sensing radius of nodes is no longer than l, boundary effects being neglected.

2.1. Basic Definition

Definition 1 (full coverage).

Provided that all the nodes in the detected region are covered within the sensing range of at least one sensor, that is to say, the Euclidean distance between the sensor node and target node is less than the sensing radius of sensor node, $d_{(i,t)}\le R_s$ , we call it full coverage. And the set of nodes satisfying full coverage conditions is called coverage set.

Definition 2 (k-coverage).

When any target node in the monitored region is covered by at least k number of sensor nodes, we say that the targets are under k-coverage, and the monitored region is called k-coverage area.

Definition 3 (coverage quality).

The coverage quality equals the ratio of the sum of the sensing areas of all sensor nodes to the area being monitored. It, to some degree, reflects the extent of coverage over target nodes.

Definition 4 (multilevel coverage).

Consider

$$\begin{array}{cc}& p_n=\mathrm{1}-{\left(\mathrm{1}-p\right)}^n,\end{array}$$

(1)

in which $p_n$ is multilevel coverage rate, p is the coverage rate of any sensor node, and n is the number of sensor nodes [15, 16].

2.2. Network Model

To analyze the coverage of WSN, a network model with l-meter square monitoring area and a sector coverage area is being built, as shown in Figure 3.

Figure 3

Network model with k-coverage.

In Figure 3, the monitored area is a square with l meter on each side, and the coverage area for a sensor node is a sector. The angles between four sector areas are given in radian measure. Tanks and soldiers (target nodes) are being placed under k-coverage ( $k=4$ ). Let the sensing radius of sensor nodes be $R_s$ , and then the area of sector is

$$\begin{array}{cc}& S_{\mathrm{1}}=\pi R_s\left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}+{\alpha }_{\mathrm{3}}+{\alpha }_{\mathrm{4}}\right).\end{array}$$

(2)

Let $\theta ={\alpha }_1+{\alpha }_2+{\alpha }_3+{\alpha }_4$ ; that is,

$$\begin{array}{cc}& S_{\mathrm{1}}=\pi \theta R_s.\end{array}$$

(3)

When the target nodes remain within the coverage area of sensor nodes, the coverage rate of the entire network is

$$\begin{array}{cc}& P_N=\frac{\pi \theta R_s}{l^{\mathrm{2}}}.\end{array}$$

(4)

Theorem 5.

The expectation for a target node to be covered is $E(X)=\pi \theta ({\sigma }^{\mathrm{2}}+l^2)/l^2$ .

Proof.

Since sensor nodes distributed randomly over the monitored area follow uniform distribution pattern, the coverage of any sensor node is    $P_N=\pi \theta R_s^{\mathrm{2}}/l^{\mathrm{2}}$ , in which θ is the sum of sector angles and $R_s$ is the sensing range of sensor nodes. As $R_s$ follows normal distribution $\left(l,{\sigma }^{\mathrm{2}}\right)$ , in which l is the average of normal distribution and ${\sigma }^{\mathrm{2}}$ is the variance of normal distribution, the expectation that any target node within the monitored area is being covered by sensor nodes is

$$\begin{array}{cc}& E\left(X\right)={{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{2}l}{P}_N\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }\sigma }\exp \left(-\frac{{\left(R_s-l\right)}^{\mathrm{2}}}{\mathrm{2}{\sigma }^{\mathrm{2}}}\right)\mathrm{d}{R}_s.\end{array}$$

(5)

Let $x=(R_s-l)/\sigma$ ; then we have

$$\begin{array}{cc}& \mathrm{d}{R}_s=\sigma \mathrm{d}x\\ E\left(X\right)={\left(\frac{\pi }{\mathrm{2}}\right)}^{\mathrm{1}/\mathrm{2}}\frac{\mathrm{1}}{l^{\mathrm{2}}}{{\displaystyle \int }}_{-l/\sigma }^{l/\sigma }{\left(x\sigma +l\right)}^{\mathrm{2}}\exp \left(-\frac{x^{\mathrm{2}}}{\mathrm{2}}\right)\mathrm{d}x.\end{array}$$

(6)

After computation, we have

$$\begin{array}{cc}& E\left(X\right)={\left(\frac{\pi }{\mathrm{2}}\right)}^{1/2}\frac{\mathrm{1}}{l^{\mathrm{2}}}\left({{\displaystyle \int }}_{-l/\sigma }^{l/\sigma }{\sigma }^{\mathrm{2}}{x}^{\mathrm{2}}\exp \left(-\frac{x^{\mathrm{2}}}{\mathrm{2}}\right)\mathrm{d}x+{{\displaystyle \int }}_{-l/\sigma }^{l/\sigma }\mathrm{2}\sigma x\exp \left(-\frac{x^{\mathrm{2}}}{\mathrm{2}}\right)\mathrm{d}x+{{\displaystyle \int }}_{-R_{\mathrm{0}}/\sigma }^{R_{\mathrm{0}}/\sigma }{l}^{\mathrm{2}}\exp \left(-\frac{x^{\mathrm{2}}}{\mathrm{2}}\right)\mathrm{d}x\right)={\left(\frac{\pi }{\mathrm{2}}\right)}^{\mathrm{1}/\mathrm{2}}\frac{\mathrm{1}}{l^{\mathrm{2}}}\left({\left.-{\sigma }^{\mathrm{2}}x\exp \left(-\frac{x^{\mathrm{2}}}{\mathrm{2}}\right)\right|}_{-l/\sigma }^{l/\sigma }\right)+{\left(\frac{\pi }{\mathrm{2}}\right)}^{\mathrm{1}/\mathrm{2}}\left({\sigma }^{\mathrm{2}}+l^{\mathrm{2}}\right).\end{array}$$

(7)

Simplifying the above equation, we have

$$\begin{array}{cc}& E\left(X\right)=\frac{\theta \pi \left(l^{\mathrm{2}}+{\sigma }^{\mathrm{2}}\right)}{l^{\mathrm{2}}}.\end{array}$$

(8)

Corollary 6.

With a given coverage rate, when one can complete multilevel coverage over the monitored area with a minimum number of sensor nodes, the coverage expectation is $(1-\epsilon )/\mathrm{l}\mathrm{n}(1-\pi \beta ({\sigma }^2+l^2)/l^2)$ .

Proof.

All the sensor nodes randomly deployed over the monitored area are independently located. According to Definition 4 and Theorem 5, the expectation for any target node to be covered by at least one node in the coverage set is

$$\begin{array}{cc}& E\left(k_{\mathrm{1}}\right)=\frac{\pi \beta \left({\sigma }^{\mathrm{2}}+l^{\mathrm{2}}\right)}{l^{\mathrm{2}}}.\end{array}$$

(9)

If there are n working nodes in the coverage set, the expectation for any target node in the monitored area to be covered by multilevel coverage is

$$\begin{array}{cc}& E\left(k\right)=\mathrm{1}-{\left(\mathrm{1}-\frac{\pi \beta \left({\sigma }^{\mathrm{2}}+l^{\mathrm{2}}\right)}{l^{\mathrm{2}}}\right)}^n.\end{array}$$

(10)

With a given coverage quality, there must be an extremely small number ε, which guarantees that when the expectation for multilevel coverage is smaller than ε, the limit exists; that is,

$$\begin{array}{cc}& \mathrm{1}-{\left(\mathrm{1}-\frac{\pi \beta \left({\sigma }^{\mathrm{2}}+l^2\right)}{l^{\mathrm{2}}}\right)}^n\le \epsilon .\end{array}$$

(11)

Solve it:

$$\begin{array}{cc}& n\ge \frac{\ln \left(\mathrm{1}-\epsilon \right)}{\ln \left(\mathrm{1}-\pi \beta \left({\sigma }^{\mathrm{2}}+l^{\mathrm{2}}\right)/l^{\mathrm{2}}\right)}.\end{array}$$

(12)

When the monitored area is under effective coverage, the expectation for the monitored area to be covered by a minimum number of sensor nodes is $\ln (1-\epsilon )/\ln (1-\pi \beta ({\sigma }^2+l^2)/l^2)$ .

Theorem 5 and Corollary 6 demonstrate the process to compute the coverage expectation and multilevel coverage expectation. Normally, a sector will be formed when the target nodes are moving under the coverage of sensor nodes. The coverage expectation can be readily computed by probability theory and geometric theory. But how to derive the coverage expectation when mobile targets move into the monitored area for the first time is an issue that needs to be solved; hence we introduce Theorem 7.

Theorem 7.

When the mobile target enters the monitored area for the first time, the expectation for the mobile target node to be covered for the first time is $E(X)=[1-{(1-p)}^N]p^{-1}$ , in which N is maximum number of times that targets are allowed to move and p is the coverage rate of sensor nodes.

Proof.

Based on the probability theory, let X be the number of times that mobile targets change their position; $X\in [\mathrm{1,2},3,\dots ,N]$ . When $X=m$ and satisfies $1\le m\le N-1$ , which means that the target nodes are not being covered by sensor nodes during their ( $N-1$ ) times of moving, we have the distribution density function as

$$\begin{array}{cc}& P\left(X=k\right)=\left\{\begin{array}{cc}p{\left(\mathrm{1}-p\right)}^{k-\mathrm{1}},\hfill & k=\mathrm{1,2},\mathrm{3},\dots ,N-\mathrm{1}\hfill \\ {\left(\mathrm{1}-p\right)}^{N-\mathrm{1}},\hfill & k=N.\hfill \end{array}\right.\end{array}$$

(13)

From the equation on coverage expectation, we have

$$\begin{array}{cc}& E\left(X\right)={\displaystyle \sum }_{k=\mathrm{1}}^{N-\mathrm{1}}kp{\left(\mathrm{1}-p\right)}^{k-\mathrm{1}}+N{\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}.\end{array}$$

(14)

Let $q=1-p$ and $={\sum }_{k=\mathrm{1}}^{N-\mathrm{1}}k{\left(\mathrm{1}-p\right)}^{k-\mathrm{1}}$ . Multiplying both sides with q, we have $qS={\sum }_{k=\mathrm{1}}^{N-\mathrm{1}}k{q}^k$ ; then

$$\begin{array}{cc}& S=\frac{\mathrm{1}-q^{N-\mathrm{1}}}{{\left(\mathrm{1}-q\right)}^{\mathrm{2}}}-\frac{\left(N-\mathrm{1}\right)q^{N-\mathrm{1}}}{\mathrm{1}-q}=\frac{\mathrm{1}-{\left(\mathrm{1}-p\right)}^N}{p^{\mathrm{2}}}-\frac{N{\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}}{p}.\end{array}$$

(15)

Substituting (13) into (12), we have

$$\begin{array}{cc}& E\left(X\right)=p\left(\frac{\mathrm{1}-{\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}}{p^{\mathrm{2}}}-\frac{\left(N-\mathrm{1}\right){\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}}{p}\right)+N{\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}=\frac{\mathrm{1}-{\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}+p{\left(\mathrm{1}-p\right)}^{N-\mathrm{1}}}{p}=\left[\mathrm{1}-{\left(\mathrm{1}-p\right)}^N\right]p^{-\mathrm{1}}.\end{array}$$

(16)

2.3. Energy Transfer

The power of operating sensor nodes in the monitored area will inevitably deplete after working for t period of time [20–22]. The energy consumption will result in the reduction of coverage area. Therefore, in order to minimize the power consumption and maximize network lifetime, the paper utilizes a model to analyze the energy consumed by sensor nodes while fulfilling unilateral and multilateral transmission. Neglecting the energy consumed for computation, storage, and controlling, we can obtain the energy consumption model for the transmitting terminal of a node which is

$$\begin{array}{cc}& E_{\mathit{\text{Tx}}}\left(l,d\right)=l{E}_{T\text{-elec}}+E_{\text{amp}}\left(l,d\right)=\left\{\begin{array}{cc}l{E}_{T\text{-elec}}+l{\epsilon }_{\mathrm{f}\mathrm{s}}{d}^{\mathrm{2}},\hfill & d<d_{\mathrm{0}}\hfill \\ l{E}_{T\text{-elec}}+l{\epsilon }_{\text{amp}}{d}^{\mathrm{4}},\hfill & d\ge d_{\mathrm{0}}.\hfill \end{array}\right.\end{array}$$

(17)

The energy consumption model for the receiving end is

$$\begin{array}{cc}& E_{\mathit{\text{Rx}}}\left(l\right)=E_{R\text{-elec}}\left(l\right)=l{E}_{\text{elec}},\end{array}$$

(18)

in which l is the bit of transmission data, d is the Euclidean distance between sensor node and neighboring node, and $d_0$ is the threshold value for the distance between communication nodes. When the distance is shorter than $d_0$ , the energy attenuation index is 2, or else the energy attenuation is 4. $E_{\text{elec}}$ represents the energy consumed by communication nodes for receiving and sending modules.

3. Algorithm Descriptions and Analysis

3.1. State Transformation Algorithm

In order to enhance the energy efficiency of nodes, the paper adopts node state scheduling strategy, which allows nodes to work under the following three states: sleeping, waiting, or active. Under sleeping mode, sensor nodes switch off the redundant modules to minimize the waste of energy and nodes are awakened periodically to intercept radio information by cluster head nodes. Under waiting mode, nodes can perceive surrounding targets to detect the arrival of mobile targets, compute their distance, and so forth. Nodes periodically compute their participatory monitoring weight. Under active mode, all nodes are in operation to fulfill a range of tasks, such as detecting the arrival of target nodes and collecting and sending target information. Under this state, nodes are consuming the maximum amount of energy.

Node state switching mode works as follows: When the network is initialized, the cluster head nodes are under active state, while the member nodes are under sleeping state; the sleeping nodes are awakened periodically to detect whether cluster head nodes have sent state scheduling orders. If receiving such order, the sleeping nodes will be switched to waiting state, or else they will continue sleeping. The waiting nodes periodically compute their participatory monitoring weight. If the weight is larger than or equal to its threshold, the node will be switched to active mode to participate in the monitoring of mobile targets; if the waiting node receives information sent from cluster head nodes, it will be switched to sleeping mode. The nodes under active state also periodically compute their participatory monitoring weights. If the weight is smaller than its threshold, the active node will be switched to waiting state, or it will keep its original state. The process through which nodes are switching in different modes is as shown in Figure 4.

Figure 4

Node energy transition diagram.

3.2. Algorithm Design Idea

In EEKCA algorithm, we establish a set composed of neighboring nodes within the sensing range of sensor nodes and divide all the nodes into several subsets, with the fully powered nodes with comparatively strong capability of computation and communication as managing nodes and other nodes as member nodes. When the network is initialized, a node is chosen as managing node arbitrarily since the attributes of all nodes are the same. Member nodes send a “Coverage” message to managing node, which allots a memory space based on their own characteristics to store the received messages in the chain table CL. “Coverage” message mainly includes the attributes and current status of member nodes, such as energy changes, ID information, and the coverage condition over targets. One or several cycles later, with all the information collected from member nodes, the managing node can rank the member nodes according to their residual energy and expected coverage value and store them in the chain table. Assign weights to the member nodes based on their ranking to make the nodes ranking ahead with heavier weights than those ranking behind. The managing nodes will analyze the coverage condition over target nodes and seek from chain table for most eligible member nodes and mark them. Then a “Notice” message will be sent to these member nodes to schedule other nodes to collaboratively fulfill ideal coverage.

3.3. Algorithm Description

EEKCA algorithm shall be fulfilled in 7 steps.

Step 1.

Firstly calculate the coverage expectation of all member nodes in each set, noted as $E\left(X\right)=\bigcup \left\{(s_i,L)\mid s_{i}N(l,{\sigma }^2)/l^2\right\}.$

Step 2.

The manager node stores all the information collected from member nodes in CL chain table. The “Coverage” message shall include the ID information, energy information, and information about coverage expectation.

Step 3.

One or several cycles later, the managing node can rank the member nodes according to their residual energy and expected coverage and store them in the chain table. Assign weights to the member nodes based on their ranking to make the nodes ranking ahead with heavier weights than those ranking behind.

Step 4.

Check whether member nodes cover target nodes and mark eligible member nodes.

Step 5.

Find member nodes in chain table. When the residual energy of one member node is higher than threshold value $E_{\text{thr}}$ , send a “Notice” message to the member node, which, after receiving the message, will start sensing module to cover the monitored region.

Step 6.

If a target node is being covered by k members of nodes simultaneously, the managing node will browse through the chain table again to seek for eligible member nodes and shut them off.

Step 7.

After the completion of browsing, the managing node will screen the most eligible node by self-adaptive mechanism and start this node to finish coverage, or turn to Step 2.

3.4. Algorithm Code

See Algorithm 1.

Algorithm 1

( $\mathit{1}$ )    Input N, R, r

( $\mathit{2}$ )    Initialize the number of nodes, communication radius and perception radius

( $\mathit{3}$ )    for $i=\mathit{1}$ to N do

( $\mathit{4}$ )     if coverage possibility exists then

( $\mathit{5}$ )      determine coverage and computer coverage rate // determine the coverage area

( $\mathit{6}$ )      state_transition (nodes) // nodes state transition function

( $\mathit{7}$ )     else

( $\mathit{8}$ )      break

( $\mathit{9}$ )     end if

( $\mathit{10}$ ) end for

( $\mathit{11}$ ) state_transition (nodes)

( $\mathit{12}$ ) while (node energy > ε)

( $\mathit{13}$ )  state = wait

( $\mathit{14}$ )  If random ( $\mathit{0},\mathit{1}$ ) >= p then

( $\mathit{15}$ )   compete = state

( $\mathit{16}$ )   work = compete // meet the conditions of coverage, activate the work nodes

( $\mathit{17}$ )  else

( $\mathit{18}$ )   wait = compete

( $\mathit{19}$ )  end if

( $\mathit{20}$ ) start timer $T_n$  // $T_n$ is next time

( $\mathit{21}$ )  if ( $d<r_{\mathit{1}}$   &&   $d<r_{\mathit{2}}$ ) then

( $\mathit{22}$ )   state = sleep // target nods is the neighbor nodes within the overlapping range

( $\mathit{23}$ )  else if (random ( $\mathit{0,1}$ ) >= p)

( $\mathit{24}$ )    compete = state

( $\mathit{25}$ )    work = compete // meet the conditions of coverage, activate the work nodes

( $\mathit{26}$ )   else

( $\mathit{27}$ )    wait = state

( $\mathit{28}$ )   end if

( $\mathit{29}$ )  end if

( $\mathit{30}$ ) end while

3.5. Complexity Analysis

Theorem 8.

Under optimal condition, the algorithm complexity of EEKCA algorithm is $O(n)$ ; under worst condition, the algorithm complexity is $O(n^2)$ .

Proof.

EEKCA fulfills the task switch between member nodes by receiving and sending different types of information and identifies the most eligible node by browsing through chain table. If EEKCA algorithm finishes the coverage over target nodes in one or less than one cycle, then the complexity of the algorithm is $O(n)$ . If it is finished in more than one cycle or less than the maximum number of cycles, n times of cyclic coverage shall be fulfilled; that is, the worst complexity is $O(n^2)$ .

4. Architecture Assessments

In order to validate the effectiveness and stability of the proposed algorithm, the paper takes MATLAB7 as simulation platform and compares it with other four algorithms in [13] (Energy-Efficient Target Coverage Algorithm, ETCA) and [4] (linear programming maximum lifetime coverage with energy harvesting, LP_MLCEH), [14] (Event Probability Driven Mechanism, EPDM), and [17] (Optimization Strategy Coverage Control, OSCC). The experiment environment consists of WIN XP, RAM 2 G, Double-core CPU, 1.7 G. Simulation parameters are listed in Table 1.

Table 1

Simulation parameters.

Parameter	Value	Parameter	Value
Monitoring area I	$$\mathit{100}\ast \mathit{100}$$	$$R_c$$	10 m
Monitoring area II	$$\mathit{200}\ast \mathit{200}$$	$$E_{R\text{-elec}}$$	50 J/b
Monitoring area III	$$\mathit{300}\ast \mathit{300}$$	$$E_{T\text{-elec}}$$	50 J/b
$$R_s$$	5 m	$${\epsilon }_{\mathrm{f}\mathrm{s}}$$	10 (J/b)/m2
Initial energy	5 J	$${\epsilon }_{\mathrm{a}\mathrm{m}\mathrm{p}}$$	100 (J/b)/m2
Time	600 s	$$e_{\mathrm{m}\mathrm{i}\mathrm{n}}$$	0.005 J

Experiment 1.

Give the coverage rate with different k value within a $300\ast 300$ simulation area.

Figure 5 presents the change curve of sensor nodes and coverage rate under different k value within a $300\ast 300$ monitored area. It can be seen that, with a fixed monitoring area, the coverage rate increases with the number of sensor nodes. When $k=2$ , the coverage rate (coverage probability, CP) increases with the number of working sensor nodes. When CP = 99.9%, WSN realizes effective coverage with 280 sensor nodes. When $k=3$ , 231 nodes are working together to realize effective coverage. When $k=4$ , the number of nodes is 183. The coverage rate rises rapidly between 85% and 99.9%, mainly because more areas are being covered with the increase of k.

Figure 5

k-coverage change curve.

Experiment 2.

In order to verify the efficiency of the proposed algorithm in extending network lifetime, we compare EEKCA algorithm with ETCA algorithm and LP_MLCEH protocol. The experiment data is the mean value of 200 times of simulation, as shown in Figures 6, 7, and 8.

Figure 6

$100\ast 100$ , changing curve of network lifetime.

Figure 7

$200\ast 200$ , changing curve of network lifetime.

Figure 8

$300\ast 300$ , changing curve of network lifetime.

In the experiment, with different k, we change the number of nodes randomly distributed within the monitored region to change the scale of network. For a small-scale monitored area, 20 nodes are deployed initially. Then more nodes are added gradually. It can be seen from the simulation chart that the lifetime of WSN extends as the number of sensor nodes increases, which is mainly because the member nodes in node set take turns to cover the target nodes under a scheduling scheme. Under the same network environment, EEKCA algorithm extends the network lifetime by 13.71% and 16.52% as compared to ETCA algorithm and LP_MLCEH protocol, respectively. For a large-scale monitored area, 50 nodes are deployed initially and more nodes are added gradually. The lifetime of WSN also extends as the number of sensor nodes increases, though not as distinct as that in small-scale area. Under the same network environment, EEKCA algorithm extends the network lifetime by 15.13% and 17.27% as compared to ETCA algorithm and LP_MLCEH protocol, respectively.

Experiment 3.

A comparison of coverage rate between EEKCA algorithm, EPDM algorithm in [14], and OSCC algorithm in [17] is made. With a $200\ast 200$ monitored area, the experiment data is the mean value of 200 times of simulation, as shown in Figures 9–11.

Figure 9

$200\ast 200$ , changing curve of network coverage.

Figure 10

$200\ast 200$ , changing curve of network running time.

Figure 11

Comparison between number of working sensor nodes and all sensor nodes.

As shown in Figure 9, with the increase of the number of sensor nodes, the coverage rate increases in all three algorithms. With a coverage rate of 99.9%, when $k=2$ , there are 185 sensor nodes; when $k=3$ , there are 152 nodes; when $k=4$ , while the proposed algorithm realizes k-coverage with 107 nodes, the other two algorithms fail to reach 100%, which indicates that EEKCA algorithm has a higher coverage rate than EPDM algorithm and OSCC algorithm, validating the effectiveness of the proposed algorithm. As shown in Figure 10, at the initial stage of operation, the EPDM algorithm and OSCC algorithm have a similar coverage rate. But as time goes by, the coverage rate of these two algorithms decreases, mainly because these two algorithms adopt continuous coverage scheme, which means that the working nodes will cover the target nodes continuously till it runs out of power and when t = 150, the coverage rate decreases most significantly in all three algorithms. When $k=\mathrm{2,3},4$ , its coverage is, respectively, ${\text{CP}}_{\text{EEK2CA}}$ = 77.83%, ${\text{CP}}_{\text{EEK3CA}}$ = 86.83%, ${\text{CP}}_{\text{EPDM}}$ = 88.52%, ${\text{CP}}_{\text{OSCC}}$ = 94.58%, and ${\text{CP}}_{\text{EEK4CA}}$ = 97.26%. When $k=4$ , the coverage rate of the proposed algorithm is obviously higher than the mean coverage rate of the other two algorithms, which suggests that, with the same number of nodes, the coverage rate of EEKCA algorithm is obviously higher than the other two algorithms, validating the effectiveness of the proposed algorithm. Figure 11 presents a comparison in the number of working nodes of three algorithms with fixed coverage rate.

When the number of sensor nodes is kept between 140 and 180, the working nodes in all three algorithms do not change much. When $k=\mathrm{2,3},4$ , the number of working nodes required in the proposed algorithm is fluctuating around 146, 142, and 121, while the number of working nodes required by EPDM algorithm and OSCC algorithm is within 134 and 152. This difference can be explained by the reason that while the proposed algorithm relies on the node set composed of neighboring nodes within the sensing radius of local nodes to finish the coverage over the monitored region, the other two algorithms rely on a fixed number of nodes to fulfill the coverage continuously. Therefore, compared to other algorithms, the proposed number reduces the number of working nodes required by 3.49%.

5. Conclusions

Based on an analysis of the coverage characteristics of WSN, the paper proposes an Energy-Efficient k-Coverage Algorithm (EEKCA). The algorithm proposes a method to calculate the coverage expectation with a sector and gives the process to fulfill the coverage with the minimum number of sensor nodes. In the meantime, the algorithm also gives the way to calculate and deduce the expectation for the first coverage over mobile target nodes. As for power consumption, the paper demonstrates the detailed process to reduce energy and proves through calculation that multilateral transmission consumes less energy than unilateral transmission. Finally, the paper conducts simulation experiments to testify that the proposed algorithm is more effective and stable than LP_MLCEH protocol, EPDM algorithm, and OSCC algorithm in network lifetime and network coverage.