# Distributed Multitarget Probabilistic Coverage Control Algorithm for Wireless Sensor Networks

Authors: Ying Tian; Yang Ou; Hamid Reza Karimi; Yan Tao Liu; Jian Qun Han
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper is concerned with the problem of multitarget coverage based on probabilistic detection model. Coverage configuration is an effective method to alleviate the energy-limitation problem of sensors. Firstly, considering the attenuation of node’s sensing ability, the target probabilistic coverage problem is defined and formalized, which is based on Neyman-Peason probabilistic detection model. Secondly, in order to turn off redundant sensors, a simplified judging rule is derived, which makes the probabilistic coverage judgment execute on each node locally. Thirdly, a distributed node schedule scheme is proposed for implementing the distributed algorithm. Simulation results show that this algorithm is robust to the change of network size, and when compared with the physical coverage algorithm, it can effectively minimize the number of active sensors, which guarantees all the targetsγ-covered.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have attracted a great deal of attention. They are widely used in the fields of military affairs, intelligent family, environment surveillance and commercial management, and so on [1, 2]. However, many applications put on them lots of constraints that make issues in WSNs particularly challenging [3, 4]. Among them, the power constraint of sensor devices imposes many fundamental design limitations in WSNs. According to this problem, coverage control is one of the most effective ways on energy saving for energy-constrained WSNs [5–7], which can make the fewest sensors cover the sensing area or targets in the network.Recently, many literatures focus on the coverage problems in WSNs. They are generally classified into three types [8]: the first one is the area coverage, where the objective is to cover an area [9–14]; the second one, which our paper also focuses on, is the target coverage, where the objective is to cover a set of targets [15–18]; the last is coverage problems that have the objective to determine the maximal support/breach path that traverses a sensor field [19]. In the first type, literatures [9–14] introduce different eligibility rules for the WSN based on the problem requirements, such as energy efficiency, area monitoring, and network connectivity. The network activity is organized in rounds, with sensors in the active set performing the area coverage, while all other sensors are in the sleep mode. Different techniques have been proposed to select which sensors will be active in the next round. According to the second type, literatures [15–18] present and develop the target problem. In literature [15], disjoint sensor sets are modeled as disjoint set covers, such that every cover completely monitors all the target points. The disjoint set cover problem [15] is reduced to a maximum flow problem, which is modeled as mixed integer programming. The problem is further extended in literature [16], where sensors are not restricted to participation in only disjoint sets; that is, a sensor can be active in more than one set. Furthermore, literature [17] develops the target coverage problem in [16]. In order to reduce both energy consumption and interference at the MAC layer, the sensing range of the active sensors in [17] can be reduced, while the coverage requirements are maintained. Literature [18] formalizes the k-(connected) coverage set (k-CCS/k-CS) problems, develops a linear programming algorithm, and designs two nonglobal solutions for them. In the last type, a different coverage formulation is given in [19]. A path has the worst (best) coverage, if it has the property that. for any point on the path, the distance to the closest sensor is maximized (minimized). Among these papers mentioned above, the sensing range is a critical parameter, which determines the sensing ability of the sensor. In fact, with the increasing of sensing distance between the sensor and the target, the sensing ability of a sensor decays dramatically. We called this kind of sensing model probabilistic detection model. Literatures [13, 14] discuss the area coverage problem based on probabilistic detection model, but the objective of them focuses on area coverage problem. Most of literatures, such as [9–11, 15, 16, 18, 19], make the sensing range fixed. In these papers, a simplified circular sensing model is supposed which follows the yes/no binary detection model, called physical detection model. Obviously, the physical detection model does not obey the signal attenuation characteristic. The adjusted sensing range is adopted by literatures [12, 17], but the sensing ability is still fixed after the sensing range is adjusted.In this paper we address the multitarget coverage problem based on probabilistic detection model; our contributions are as follows: based on Neyman-Peason probabilistic detection model,(1) the multitarget probabilistic coverage problem is defined and formalized, (2) the simplified probabilistic coverage judging rule is derived for the distributed coverage control of the network, and (3) using the simplified judging rule, a distributed node schedule scheme is proposed, which not only minimizes the number of active sensors, but also guarantees all the targets monitored at the requirement of coverage probability.The rest of this paper is organized into the following sections. In Section2, the problem formulation and preliminaries are given. Section 3 presents the probabilistic coverage judging rule and the distributed coverage control algorithm. Section 4 simulates our algorithm and analyzes the simulation results. In Section 5, conclusions and further research directions are given.


## 2. Problem Formulation and Preliminaries

In this paper, we deal with the multitarget coverage problem based on Neyman-Peason probabilistic detection model. The goal is to minimize the number of active sensors while guaranteeing that each target can be covered with the required coverage probability.We consider a WSN consisting of large number of sensors and a set of targets deployed in the WSN region randomly. To reduce the energy consumption of network, we want to find the minimum number of active sensors with the property that each target is monitored by sensors around it with the required network coverage probability.


### 2.1. Probabilistic Detection Model

We assume thatN sensors, s1,s2,…,sN, and M targets, t1,t2,…,tM, are distributed randomly in the monitoring region, with location of the sensor, si, i=1,2,…,N(xsi,ysi), and location of the target tj, j=1,2,…,M, (xtj,ytj). Then si can make a measurement from the target tj by the following equation:
(1)aij=θdijα+nii=1,2,…,N,j=1,2,…,M,
where θ is the signal strength emitted by the target tj; α is the signal decay exponent, α>0; dij is the distance from the target tj to the sensor si; that is, dij=(xsi-xtj)2+(ysi-ytj)2. Assuming ni is the noise at sensor, si,   and follows a Gaussian distribution with zero mean, that is, ni~(0,σ).For sensorsi, the binary hypothesis testing problem is presented as follows:
(2)H1:p(zij∣H1)=(12πσ)exp⁡(-(zij-aij)22σ2)H0:p(zij∣H0)=(12πσ)exp⁡(-zij22σ2).Assume that all the sensors use the same detection thresholdτ to make a decision; based on Neyman-Peason detection rule, the relationship between threshold τ and the false alarm rate Pfij is given as follows:
(3)Pfij=∫τ∞p(zij∣H0)dzij=Q(τσ)τ=σ×Q-1(Pfij),
where Q(x) is the complementary distribution function of the standard Gaussian; that is
(4)Q(x)=∫x∞12πexp⁡(-t22)dt.The detection probability totj by si is
(5)PDij=∫τ∞p(zij∣H1)dzij=Q(τ-aijσ)=1-Φ(τ-aijσ),
where Φ(x) is the normal distribution function of the standard Gaussian; that is,
(6)Φ(x)=∫-∞x12πexp⁡(-t22)dt.In WSN, many sensors are deployed in the monitoring region to detect the targets. Usually, a target in the monitoring region can be sensed by more than one sensor. The detection probability oftj by sensors, si, i=1,2,…,k, motivated by [20] is
(7)PDj=1-∏i=1k(1-PDij)=1-∏i=1kΦ(τ-(θ/dijα)σ).The relationship of total detection probabilityPDj and single detection probability PDij with different number of active sensors k is given in Figure 1.Figure 1
Relationship of single detection probabilities and total detection probability with different number of sensing nodes.From Figure1, a target can be detected by three sensors in the same distance with the detection probability of 90% while it can be detected by two sensors with the probability of 84%. At the same condition, the target can be detected by single sensor at the probability of 60%.


### 2.2. Problem Definitions

Definition 1.
γ
-Probabilistic Covered. Given M targets and N sensors randomly deployed in the target’s vicinity, if one target tj is detected by k sensors together and the total detection probability is more than γ, that is, PDj≥γ, then the target is γ-probabilistic covered or (γ,k)-probabilistic covered in more detail. For simplicity, we use the notations as γ-covered or (γ,k)-covered.Definition 2.
k-Probabilistic Cover Radius. Assuming the required total detection probability is γ, there are  k sensors around one target, the distances between each sensor and the target are the same, denoted as rk. When these sensors working together, the target can be (γ,k)-covered. Then, the distance rk is the k-Probabilistic Cover Radius.Remark 3.
From Definition2, when d1j=d2j=⋯=rk and (7) is PDj=1-Φk(τ-(θ/rkα)/σ)=γ, then we can get
(8)rk=[θτ-σΦ-1(1-γk)]1/α.Definition 4.
Probabilistic Cover Set. If a targettj can be γ-covered by working together with a set of sensors, denoted by S, we can say S is a probabilistic cover set of the target tj.Definition 5.
Basic Cover Set. IfS is a probabilistic cover set of the target, tj, and S will not become the probabilistic cover set when any sensor in S is not in active, then S is the basic cover set of target tj.


## 2.1. Probabilistic Detection Model

We assume thatN sensors, s1,s2,…,sN, and M targets, t1,t2,…,tM, are distributed randomly in the monitoring region, with location of the sensor, si, i=1,2,…,N(xsi,ysi), and location of the target tj, j=1,2,…,M, (xtj,ytj). Then si can make a measurement from the target tj by the following equation:
(1)aij=θdijα+nii=1,2,…,N,j=1,2,…,M,
where θ is the signal strength emitted by the target tj; α is the signal decay exponent, α>0; dij is the distance from the target tj to the sensor si; that is, dij=(xsi-xtj)2+(ysi-ytj)2. Assuming ni is the noise at sensor, si,   and follows a Gaussian distribution with zero mean, that is, ni~(0,σ).For sensorsi, the binary hypothesis testing problem is presented as follows:
(2)H1:p(zij∣H1)=(12πσ)exp⁡(-(zij-aij)22σ2)H0:p(zij∣H0)=(12πσ)exp⁡(-zij22σ2).Assume that all the sensors use the same detection thresholdτ to make a decision; based on Neyman-Peason detection rule, the relationship between threshold τ and the false alarm rate Pfij is given as follows:
(3)Pfij=∫τ∞p(zij∣H0)dzij=Q(τσ)τ=σ×Q-1(Pfij),
where Q(x) is the complementary distribution function of the standard Gaussian; that is
(4)Q(x)=∫x∞12πexp⁡(-t22)dt.The detection probability totj by si is
(5)PDij=∫τ∞p(zij∣H1)dzij=Q(τ-aijσ)=1-Φ(τ-aijσ),
where Φ(x) is the normal distribution function of the standard Gaussian; that is,
(6)Φ(x)=∫-∞x12πexp⁡(-t22)dt.In WSN, many sensors are deployed in the monitoring region to detect the targets. Usually, a target in the monitoring region can be sensed by more than one sensor. The detection probability oftj by sensors, si, i=1,2,…,k, motivated by [20] is
(7)PDj=1-∏i=1k(1-PDij)=1-∏i=1kΦ(τ-(θ/dijα)σ).The relationship of total detection probabilityPDj and single detection probability PDij with different number of active sensors k is given in Figure 1.Figure 1
Relationship of single detection probabilities and total detection probability with different number of sensing nodes.From Figure1, a target can be detected by three sensors in the same distance with the detection probability of 90% while it can be detected by two sensors with the probability of 84%. At the same condition, the target can be detected by single sensor at the probability of 60%.


## 2.2. Problem Definitions

Definition 1.
γ
-Probabilistic Covered. Given M targets and N sensors randomly deployed in the target’s vicinity, if one target tj is detected by k sensors together and the total detection probability is more than γ, that is, PDj≥γ, then the target is γ-probabilistic covered or (γ,k)-probabilistic covered in more detail. For simplicity, we use the notations as γ-covered or (γ,k)-covered.Definition 2.
k-Probabilistic Cover Radius. Assuming the required total detection probability is γ, there are  k sensors around one target, the distances between each sensor and the target are the same, denoted as rk. When these sensors working together, the target can be (γ,k)-covered. Then, the distance rk is the k-Probabilistic Cover Radius.Remark 3.
From Definition2, when d1j=d2j=⋯=rk and (7) is PDj=1-Φk(τ-(θ/rkα)/σ)=γ, then we can get
(8)rk=[θτ-σΦ-1(1-γk)]1/α.Definition 4.
Probabilistic Cover Set. If a targettj can be γ-covered by working together with a set of sensors, denoted by S, we can say S is a probabilistic cover set of the target tj.Definition 5.
Basic Cover Set. IfS is a probabilistic cover set of the target, tj, and S will not become the probabilistic cover set when any sensor in S is not in active, then S is the basic cover set of target tj.


## 3. Multitarget Probabilistic Coverage Control Algorithm

In this section, we first propose a simplified judging rule which can make the sensor judge whether the target can beγ-covered easily; then we present a distributed node schedule scheme which can make the sensor decide whether it needs to be active locally or not, in order to minimize the number of active sensors, while guaranteeing that all the targets can be γ-covered.


### 3.1. Probabilistic Coverage Judging Rule (PCJ-Rule)

The PCJ-Rule is proposed based on Neyman-Peason probabilistic detection model. In this paper, we assume that each sensor can obtain the distances between itself and the targets in its sensing range.Theorem 6.
Suppose a targettj is around k active sensors, si, i=1,2,…,k, and the distance between tj and si is dij. If  ∑i=1kdij≤k·rk, then target tj must be (γ,k)-covered.Proof.
Given the requested total detection probability isγ, then from Definition 2, we can obtain
(9)γ=1-Φk(τ-(θ/rkα)σ).
Let
(10)F(dij)=Φ(τ-(θ/dijα)σ);
then F(dij) is a monotonic increasing function about dij. From (7), (9), and (10), we get
(11)γ=1-Fk(rk)(12)PDj=1-∏i=1kF(dij).
Due to the mean value theorem, then(13)∏i=1kF(dij)≤(∑i=1kF(dij)k)k;
when F(d1j)=F(d2j)=⋯=F(dkj), (13) is found.Considering the fact thatF(dij) is a monotonic increasing function about dij, when F(d1j)=F(d2j)=⋯=F(dkj), there must be d1j=d2j=⋯=dkj; therefore, we can obtain
(14)∏i=1kF(dij)≤Fk(r),
where r is the average value of dij.It is assumed in Theorem6 that ∑i=1kdij≤k·rk; there must be r≤rk, and we obtain that
(15)∏i=1kF(dij)≤Fk(r)≤Fk(rk).
From (12), (14), and (15), we have
(16)PDj=1-∏i=1kF(dij)≥1-Fk(rk)=γ,
where PDj=γ when dij=rk, i=1,2,…,k.Form Theorem6, a target can be judged whether it satisfied γ-covered or not. However, in order to reduce the amount of data transmission in the network and simplified calculation executed on each sensor, we proposed the PCJ-Rule which simplifies Theorem 6 further and makes the coverage judgment easily. The sensing distance dij between the sensor si and the target tj can be quantified.The method of quantification is presented as follows.Assuming thatN sensors s1,s2,…,sN and M targets t1,t2,…,tM are distributed randomly in the monitoring region, the distance between the sensor si and the target tj is dij. We set the maximum number of nodes sensing together is kmax⁡; then from Definition 2 and (8), we can calculate the values of r1,r2,…,rkmax⁡. Because of the constraint of the actual sensing abilities of sensors, we can quantify the dij is smaller than rkmax⁡; that is, dij∈[0,rkmax⁡], as the quantification distance, notated as dij′. In this paper, we consider the maximum sensing range as rkmax⁡. Then we divided the range of dij, that is, [0,rkmax⁡], into kmax⁡ quantification ranges as [0,r1], (r1,r2],…,and(rkmax⁡-1,rkmax⁡], and the corresponding quantification values are r1,r2,…,rkmax⁡; then we have dij′=rk, where k=1,2,…,kmax⁡.Definition 7.
Quantification Coefficient. If a sensing distancedij can be quantified as dij′, where dij′=rk, the quantification coefficient corresponding to dij is denoted by cij as follows:
(17)cij={1kif0≤dij≤rkmax⁡0otherwise.Figure2 shows an example with one target and four sensors with kmax⁡=3. The distances between t1 and S={s1,s2,s3,s4} are di1={d11,d21,d31,d41}; after the quantification, we can get the quantification coefficients as follows:
(18)ci1={c11,c21,c31,c41}={1,12,13,0}.Figure 2
Example of quantification with a targett1 and four sensors; S={s1,s2,s3,s4}, when kmax⁡=3.Definition 8.
Quantification Cover Set. If a sensor setS is a cover set of target tj, the distances dij between S and tj can be quantified as dij′. If the distances between S′ and tj are dij′, we can say that the sensor set S′ is the quantification cover set of S.Remark 9.
From Definition8, there must be dij′≥dij, where dij′∈{r1,r2,…,rkmax⁡}.Theorem 10.
SupposeS′ is the quantification cover set of sensor set S; if a target tj can be (γ,k)-covered by S′, the target tj must be (γ,k)-covered by S.Proof.
GivenS′ is the quantification cover set of S, where S={s1,s2,…,sk}, the distances between S and the target tj are dij, where dij={d1j,d2j,…,dkj}, and the distances between S′ and the target tj are dij′. From the quantification method, the quantified distance dij′ can be obtained, where dij≤dij′ and dij′∈{r1,r2,…,rk}.As the assumption in Theorem10 that a target tj can be (γ,k)-covered by S′, there must be ∑j=1kdij′≤k×rk; then ∑j=1kdij≤∑j=1kdij′≤k×rk. Therefore, the target tj must be (γ,k)-covered by S.Corollary 11 (PCJ-Rule).
Suppose there is a targettj detected by k active sensors S together, and kmax⁡ is the maximum allowable number of sensing nodes working on tj; that is, k≤kmax⁡; the corresponding quantification coefficients are cij, where cij≥1/kmax⁡, and the number of nonzero cij is Nc. If Nc≥kmax⁡, then ∑i=1kmax⁡cij≥1, and the target tj must be (γ,kmax⁡)-covered.Proof.
Given the distance between sensor,si, where si∈S and target, tj, is dij, where i=1,2,…,kmax⁡, dij′ is the quantified value of dij, then dij≤dij′,dij′∈{r1,r2,…,rkmax⁡}. Form the Corollary 11, when Nc≥kmax⁡, there must be more than kmax⁡ quantification coefficients with cij>0, so we have the minimum ∑i=1kmax⁡cij with (∑j=1kmax⁡cij)min⁡=kmax⁡×(1/kmax⁡)=1; therefore, ∑i=1kmax⁡cij≥1.When∑i=1kmax⁡cij=1, the corresponding quantified distance of the cij has dij′=rkmax⁡, where i=1,2,…,kmax⁡. And when ∑j=1kmax⁡cij>1, the corresponding quantified distance of the cij has dij′≤rkmax⁡, i=1,2,…,kmax⁡. Because of dij≤dij′, we have dij≤dij′≤rkmax⁡; then ∑i=1kmax⁡dij≤∑i=1kmax⁡dij′≤kmax⁡rkmax⁡. From Theorem 6, when ∑i=1kmax⁡dij≤kmax⁡rkmax⁡, the target tj must be (γ,kmax⁡)-covered by S.Remark 12.
From the proof of Corollary11, the condition ∑j=1kmax⁡cij≥1  is the sufficient condition for judging the target tj whether it satisfied (γ,kmax⁡)-covered or not.In our paper, through the information interaction between nodes, a sensor can receive quantification coefficients of the targets in its sensing range. Using Corollary11, named PCJ-Rule, the sensor will calculate whether the target has been covered by other active sensors and then decide the state of itself in active or others.


### 3.2. Distributed Node Schedule Scheme

In this section, we design a distributed node schedule scheme, which make the sensor decide the self-working state by local judgment.The flow chart of the node schedule scheme executed by a sensor locally is shown in Figure3. When the sensor runs the schedule scheme, there are three working states switched dynamically on each sensor, as shown in Figure 4. They are IDLE state, ACTIVE state, and SLEEP state.Figure 3
Flow chart of the node schedule scheme executed by sensor locally.Figure 4
Working state transfer diagram on each sensor.From Figure3, firstly, a sensor si initializes the local information, including the number of targets M in its sensing range and the distances dij between the node and the targets, where j=1,2,…,M. And then, the node quantifies the sensing distances and calculates the quantification coefficients cij, where j=1,2,…,M. Finally, the sensor sets the backoff time Tbackoff based on cij:
(19)Tbackoff=1w1Ncij=1+(1/2)w2Ncij=1/2+⋯+(1/k)wkNcij=1/k,
where Ncij=1/k is the number of cij=1/k about the sensor si; wk, called backoff weighted coefficient, is weight of Ncijwhen cij=1/k, where w1+w2+⋯+wk=1. Therefore, the backoff time of si is mainly decided by the quantification coefficients cij. For example, when w1=1, it means that the more a sensor si can (γ,1)-cover the targets, the shorter the backoff time of si.After the initialization, if the sensor does not receive any message from the others during the backoff time, it will switch to the ACTIVE state and broadcast the ACTIVE-Msg messages to its neighbor sensors.The data format of ACTIVE-Msg contains three fields: the local ID, targets’ ID in the sensing range of the sensor, and the coverage coefficientscij about the sensor and targets in its sensing range.Before the step of “execute the PCJ-Rule” in Figure3, the sensor should collect the ACTIVE-Msg messages from other active sensors to refresh the local coverage data. Then, based on the PCJ-Rule, the sensor will calculate the value of ∑j=1Mcij for each target tj to judge whether the target has been covered by other active sensors, where M is the number of targets in the sensing range of si. There are three cases of the judgment results described as follows.Case 1.
None of the targets can beγ-covered, and then the sensor will continue the backoff timer; the sensor is still in IDLE state.Case 2.
Some but not all of the targets can beγ-covered; then the sensor will set the cij=0, where i is the local ID of sensor and j is the ID of target which is γ-covered. The backoff time Tbackoff will be reset and restarted; the sensor is still in IDLE state.Case 3.
All of the targets areγ-covered; the sensor will be required to switch in SLEEP state, and then the sensor works with low energy consumption, which is still listening to the network for the reconfiguration.At last of the node schedule scheme, the sensor will work in ACTIVE state or SLEEP state. However, the node schedule scheme can be executed when the topology of network changes. The sensor will return to the IDLE state when the network coverage needs to be reconfigured.


## 3.1. Probabilistic Coverage Judging Rule (PCJ-Rule)

The PCJ-Rule is proposed based on Neyman-Peason probabilistic detection model. In this paper, we assume that each sensor can obtain the distances between itself and the targets in its sensing range.Theorem 6.
Suppose a targettj is around k active sensors, si, i=1,2,…,k, and the distance between tj and si is dij. If  ∑i=1kdij≤k·rk, then target tj must be (γ,k)-covered.Proof.
Given the requested total detection probability isγ, then from Definition 2, we can obtain
(9)γ=1-Φk(τ-(θ/rkα)σ).
Let
(10)F(dij)=Φ(τ-(θ/dijα)σ);
then F(dij) is a monotonic increasing function about dij. From (7), (9), and (10), we get
(11)γ=1-Fk(rk)(12)PDj=1-∏i=1kF(dij).
Due to the mean value theorem, then(13)∏i=1kF(dij)≤(∑i=1kF(dij)k)k;
when F(d1j)=F(d2j)=⋯=F(dkj), (13) is found.Considering the fact thatF(dij) is a monotonic increasing function about dij, when F(d1j)=F(d2j)=⋯=F(dkj), there must be d1j=d2j=⋯=dkj; therefore, we can obtain
(14)∏i=1kF(dij)≤Fk(r),
where r is the average value of dij.It is assumed in Theorem6 that ∑i=1kdij≤k·rk; there must be r≤rk, and we obtain that
(15)∏i=1kF(dij)≤Fk(r)≤Fk(rk).
From (12), (14), and (15), we have
(16)PDj=1-∏i=1kF(dij)≥1-Fk(rk)=γ,
where PDj=γ when dij=rk, i=1,2,…,k.Form Theorem6, a target can be judged whether it satisfied γ-covered or not. However, in order to reduce the amount of data transmission in the network and simplified calculation executed on each sensor, we proposed the PCJ-Rule which simplifies Theorem 6 further and makes the coverage judgment easily. The sensing distance dij between the sensor si and the target tj can be quantified.The method of quantification is presented as follows.Assuming thatN sensors s1,s2,…,sN and M targets t1,t2,…,tM are distributed randomly in the monitoring region, the distance between the sensor si and the target tj is dij. We set the maximum number of nodes sensing together is kmax⁡; then from Definition 2 and (8), we can calculate the values of r1,r2,…,rkmax⁡. Because of the constraint of the actual sensing abilities of sensors, we can quantify the dij is smaller than rkmax⁡; that is, dij∈[0,rkmax⁡], as the quantification distance, notated as dij′. In this paper, we consider the maximum sensing range as rkmax⁡. Then we divided the range of dij, that is, [0,rkmax⁡], into kmax⁡ quantification ranges as [0,r1], (r1,r2],…,and(rkmax⁡-1,rkmax⁡], and the corresponding quantification values are r1,r2,…,rkmax⁡; then we have dij′=rk, where k=1,2,…,kmax⁡.Definition 7.
Quantification Coefficient. If a sensing distancedij can be quantified as dij′, where dij′=rk, the quantification coefficient corresponding to dij is denoted by cij as follows:
(17)cij={1kif0≤dij≤rkmax⁡0otherwise.Figure2 shows an example with one target and four sensors with kmax⁡=3. The distances between t1 and S={s1,s2,s3,s4} are di1={d11,d21,d31,d41}; after the quantification, we can get the quantification coefficients as follows:
(18)ci1={c11,c21,c31,c41}={1,12,13,0}.Figure 2
Example of quantification with a targett1 and four sensors; S={s1,s2,s3,s4}, when kmax⁡=3.Definition 8.
Quantification Cover Set. If a sensor setS is a cover set of target tj, the distances dij between S and tj can be quantified as dij′. If the distances between S′ and tj are dij′, we can say that the sensor set S′ is the quantification cover set of S.Remark 9.
From Definition8, there must be dij′≥dij, where dij′∈{r1,r2,…,rkmax⁡}.Theorem 10.
SupposeS′ is the quantification cover set of sensor set S; if a target tj can be (γ,k)-covered by S′, the target tj must be (γ,k)-covered by S.Proof.
GivenS′ is the quantification cover set of S, where S={s1,s2,…,sk}, the distances between S and the target tj are dij, where dij={d1j,d2j,…,dkj}, and the distances between S′ and the target tj are dij′. From the quantification method, the quantified distance dij′ can be obtained, where dij≤dij′ and dij′∈{r1,r2,…,rk}.As the assumption in Theorem10 that a target tj can be (γ,k)-covered by S′, there must be ∑j=1kdij′≤k×rk; then ∑j=1kdij≤∑j=1kdij′≤k×rk. Therefore, the target tj must be (γ,k)-covered by S.Corollary 11 (PCJ-Rule).
Suppose there is a targettj detected by k active sensors S together, and kmax⁡ is the maximum allowable number of sensing nodes working on tj; that is, k≤kmax⁡; the corresponding quantification coefficients are cij, where cij≥1/kmax⁡, and the number of nonzero cij is Nc. If Nc≥kmax⁡, then ∑i=1kmax⁡cij≥1, and the target tj must be (γ,kmax⁡)-covered.Proof.
Given the distance between sensor,si, where si∈S and target, tj, is dij, where i=1,2,…,kmax⁡, dij′ is the quantified value of dij, then dij≤dij′,dij′∈{r1,r2,…,rkmax⁡}. Form the Corollary 11, when Nc≥kmax⁡, there must be more than kmax⁡ quantification coefficients with cij>0, so we have the minimum ∑i=1kmax⁡cij with (∑j=1kmax⁡cij)min⁡=kmax⁡×(1/kmax⁡)=1; therefore, ∑i=1kmax⁡cij≥1.When∑i=1kmax⁡cij=1, the corresponding quantified distance of the cij has dij′=rkmax⁡, where i=1,2,…,kmax⁡. And when ∑j=1kmax⁡cij>1, the corresponding quantified distance of the cij has dij′≤rkmax⁡, i=1,2,…,kmax⁡. Because of dij≤dij′, we have dij≤dij′≤rkmax⁡; then ∑i=1kmax⁡dij≤∑i=1kmax⁡dij′≤kmax⁡rkmax⁡. From Theorem 6, when ∑i=1kmax⁡dij≤kmax⁡rkmax⁡, the target tj must be (γ,kmax⁡)-covered by S.Remark 12.
From the proof of Corollary11, the condition ∑j=1kmax⁡cij≥1  is the sufficient condition for judging the target tj whether it satisfied (γ,kmax⁡)-covered or not.In our paper, through the information interaction between nodes, a sensor can receive quantification coefficients of the targets in its sensing range. Using Corollary11, named PCJ-Rule, the sensor will calculate whether the target has been covered by other active sensors and then decide the state of itself in active or others.


## 3.2. Distributed Node Schedule Scheme

In this section, we design a distributed node schedule scheme, which make the sensor decide the self-working state by local judgment.The flow chart of the node schedule scheme executed by a sensor locally is shown in Figure3. When the sensor runs the schedule scheme, there are three working states switched dynamically on each sensor, as shown in Figure 4. They are IDLE state, ACTIVE state, and SLEEP state.Figure 3
Flow chart of the node schedule scheme executed by sensor locally.Figure 4
Working state transfer diagram on each sensor.From Figure3, firstly, a sensor si initializes the local information, including the number of targets M in its sensing range and the distances dij between the node and the targets, where j=1,2,…,M. And then, the node quantifies the sensing distances and calculates the quantification coefficients cij, where j=1,2,…,M. Finally, the sensor sets the backoff time Tbackoff based on cij:
(19)Tbackoff=1w1Ncij=1+(1/2)w2Ncij=1/2+⋯+(1/k)wkNcij=1/k,
where Ncij=1/k is the number of cij=1/k about the sensor si; wk, called backoff weighted coefficient, is weight of Ncijwhen cij=1/k, where w1+w2+⋯+wk=1. Therefore, the backoff time of si is mainly decided by the quantification coefficients cij. For example, when w1=1, it means that the more a sensor si can (γ,1)-cover the targets, the shorter the backoff time of si.After the initialization, if the sensor does not receive any message from the others during the backoff time, it will switch to the ACTIVE state and broadcast the ACTIVE-Msg messages to its neighbor sensors.The data format of ACTIVE-Msg contains three fields: the local ID, targets’ ID in the sensing range of the sensor, and the coverage coefficientscij about the sensor and targets in its sensing range.Before the step of “execute the PCJ-Rule” in Figure3, the sensor should collect the ACTIVE-Msg messages from other active sensors to refresh the local coverage data. Then, based on the PCJ-Rule, the sensor will calculate the value of ∑j=1Mcij for each target tj to judge whether the target has been covered by other active sensors, where M is the number of targets in the sensing range of si. There are three cases of the judgment results described as follows.Case 1.
None of the targets can beγ-covered, and then the sensor will continue the backoff timer; the sensor is still in IDLE state.Case 2.
Some but not all of the targets can beγ-covered; then the sensor will set the cij=0, where i is the local ID of sensor and j is the ID of target which is γ-covered. The backoff time Tbackoff will be reset and restarted; the sensor is still in IDLE state.Case 3.
All of the targets areγ-covered; the sensor will be required to switch in SLEEP state, and then the sensor works with low energy consumption, which is still listening to the network for the reconfiguration.At last of the node schedule scheme, the sensor will work in ACTIVE state or SLEEP state. However, the node schedule scheme can be executed when the topology of network changes. The sensor will return to the IDLE state when the network coverage needs to be reconfigured.


## 4. Simulation Results and Analysis

In this section, we evaluate the performance of our distributed node schedule scheme. We simulate a stationary network with sensors and targets randomly deployed in a100m×100m area. Confidently, all results in this section are from average of 20 runs. In the simulation, some parameters are listed as follows:(i)
signal strength from the targetθ=30,(ii)
standard deviation of noise in the channelσ=1,(iii)
signal decay exponentα=1.2,(iv)
false alarm rate of Neyman-Peason detection rulePfi=5%,(v)
number of sensorsN varied between 200 and 800,(vi)
number of targetsM varied between 100 and 400,(vii)
maximum node number of sensing togetherk which varies between 1 and 5,(viii)
requirement probabilistic coverage probabilityγ which varies between 70% and 90%,(ix)
backoff weighted coefficientw1=1.In Figure5, the numbers of active nodes based on physical detection model and ours based on probabilistic model are compared. The same physical detection model is adopted by literatures [15, 16]; therefore, we call methods in [15, 16] as the physical coverage configuration. In physical detection model, when the target is in the sensing range, it will consider the target is 100% covered, the same as [15, 16]. While, in our simulation, the sensing range of physical coverage is set as the 1-probabilistic cover radius, which means that we consider the physical coverage configuration as the special one of our probability coverage configuration which satisfies (90%,1)-covered. It is obvious that we relax the requirement of the physical coverage configuration. We set M=100 and γ=80%. Figure 5 shows the following. (1) Our algorithm saves about 12% active nodes comparing with the physical coverage configuration. (2) The number of active sensors that make the network satisfy the coverage requirement becomes smaller with the increasing k, where k is from 2 to 5. However, the number of active sensors decreases slowly when k varies from 2 to 5. Meanwhile, if the bigger k is chosen, there will be a need for more data transfer in network [3, 8]. Therefore, the suitable value of k can make our algorithm the most efficient. Therefore, we choose k=3 in the next simulations. (3) When the maximum number of sensors detects that one target together, that is, the parameter k, is kept, the number of active sensors decreases slightly when the number of sensors deployed increases from 200 to 400, and then the number becomes stable in spite of the increasing of deployed number of sensors. It is because of the fact that when the density of sensors increases, the probability of the sensor deployed on the suitable location increases, where the sensor can make more contribution on sensing multitargets. Figure 5 shows that, in our algorithm, there are less than 40 active nodes required for monitoring all the targets in the WSN under our simulation environment, which is an effective method to save sensors’ energy and prolong the network lifetime.Figure 5
Comparison between the physical coverage configuration and the probabilistic coverage configuration with differentk.In Figure6, we compare the number of active sensors which make the network satisfy the (80%,3)-covered, when the number of targets M is 200, 300, and 400. Obviously, the number of active sensors is stable when the target number is unchanged. In our simulation, there are about 38, 48, 52, and 55 active sensors needed when we deployed 100, 200, 300, and 400 targets in the network. When the number of targets increased from 100 to 200, there are about 10 active sensors added. And when the number becomes from 200 to 300, only 5 new active sensors increased. It means that the more targets in the network, the more efficiency of our algorithm. In fact, when the number of active sensors increases to the degree that any point in the network can be probabilistic covered, there will no longer need any new active sensor even though the number of targets is increasing in the network.Figure 6
Number of active sensors required with different number of targets, which make the network satisfy the(80%,3) covered.In Figure7, our algorithms executed with the requirement detection probability γ as 70%, 80%, and 90% are compared. We set the number of targets M=100 and k=3. It is shown that more sensors are in active state when the requirement detection probability increases from 70%  to 90%. From Figure 7, the number of active sensors is steady at 33 and 38 when the network is (70%,3)-covered and (80%,3)-covered; while γ=90%, with the increasing of the deployed nodes’ number from 200 to 400, the number of active nodes decreases slightly and becomes stable at 42 active nodes at last. It is because of the fact that when γ=90%, the network with less than 400 nodes cannot make all the targets γ-covered. At the same time, our algorithm turns off many sensors, which have no contribution to the uncovered targets even though they are in active state. This simulation also indicates that our algorithm can switch a large number of redundant sensors in SLEEP state on the premise of keeping the network coverage degree even though the coverage-hole exists in the network.Figure 7
Number of active sensors needed which make the network satisfy different requirement detection probabilities.The simulation result can be summarized as follows.(1) Our algorithm is robust with the increasing of network size; it needs only a few number of active sensors to guarantee all the targets monitored at the requirement coverage probability. (2) Considering the amount of data transmission in the network, the efficiency of our algorithm can be improved by choosing the proper value of k, where we set k=3. (3) Our algorithm will no longer need the new active sensors with the number of targets increasing, when the density of active sensors increases to the degree that any points in the network can be probabilistic covered. (4) Our algorithm can turn off the redundant sensors on the premise of keeping the network coverage degree, even though the coverage-hole exists in the monitor region.


## 5. Conclusion

In this paper, based on probabilistic detection model, we propose a distributed probabilistic coverage algorithm for the WSN with multiple static targets. The goal of our work is to find a simplified judging method, which can turn off the redundant sensors and guarantee all the targets covered by active sensors. In this paper, we define and formalize the target probabilistic coverage problems based on Neyman-Peason probabilistic detection model and propose a distributed node schedule scheme using the simplified judging rule. Simulation results show that our algorithm is robust to the change of network size. When compared with the physical coverage algorithm, the number of active sensors based on probabilistic detection model is smaller than that based on a physical one; at the same time, all the targets can be monitored at the requirement of network coverage probability.In our future work, we will try to design a distributed and localized protocol that organizes the sensor nodes in disjoint set covers. By this way, the disjoint covers will work in turns, which can avoid sensors judging the local state frequently. Furthermore, we will integrate the sensor network connectivity requirement. The network connectivity is another important requirement of the network quantity of service (Qos), which makes the exchange of information between sensors easy.



---

*Source: 421753-2014-03-04.xml*