Maximizing Network Lifetime of Directional Sensor Networks Considering Coverage Reliability

Abstract

Directional sensor networks composed of a large number of directional sensors equipped with a limited battery and with a limited angle of sensing have recently attracted attention. Maximizing network lifetime is a challenge in developing energy-efficient directional sensor networks, while covering all of the targets in a given area. However, the existing schemes have considered target coverage problem as only the maximization of network lifetime. In real sensor networks, the quality of target coverage will be varied according to the detection probability of the sensors covering targets. In this paper, we address the directional cover-sets with coverage reliability (DCCR) problem of organizing directional sensors into a group of nondisjoint subsets to extend network lifetime maximally while maintaining networks' satisfied coverage reliability. For the DCCR problem, we first present a coverage reliability model that mainly takes into account the detection probability of each sensor in cover-sets and eventually supports coverage reliability for target coverage. We also develop a heuristic algorithm called directional coverage and reliability (DCR) greedy algorithm to solve the DCCR problem. To verify and evaluate the algorithm, we conduct simulations and show that it extends network lifetime to a reasonable degree while guaranteeing the minimum coverage reliability.

1. Introduction

Recently, sensor networks have attracted considerable research interest due to their vast and significant applications, such as physical phenomenon or target detection, classification, and tracking [1–4]. Directional sensor networks (such as radar or image/video sensor networks [5, 6]) have different features than conventional sensor networks in which omnidirectional sensors are used. A directional sensor has directional coverage that can sense only in the direction of its orientation. These sensors have a limited sensing angle due to constraint related to manufacturing, size, and cost [7, 8]. Each directional sensor can sense only a sector of the disk, centered on itself, with the radius being equal to the sensing range.

The target coverage in directional sensor networks is determined by both the location and orientation of the sensors. This makes the network more complex. In addition, a power saving becomes a more critical issue because each sensor has only a limited amount of power and in most cases it is difficult or impossible to replace or recharge the batteries [9]. This issue is commonly resolved by using a sensor wake-up scheduling scheme by which some sensors remain active state to provide sensing services, while the others sleep state to conserve energy. Intuitively, if certain sensors share common sensing regions, some sensors can be switched into sleep state to conserve energy.

However, the most existing scheduling schemes have considered target coverage problem as only the maximization of network lifetime. In real sensor networks, the quality of target coverage will be varied according to the detection probability of the sensors covering targets. This is because each sensor has the different sensing capability by the signal attenuation rate of targets; that is, as the distance between a sensor and its interesting target increases, the signal attenuation increases. Therefore, coverage reliability is another important factor in target coverage problem, which can improve the quality of services of directional sensor networks. In this paper, we consider a sensor scheduling problem to maximize network lifetime while maintaining the target coverage satisfying a specific requirement of coverage reliability.

We propose a new problem, called the directional cover-sets with coverage reliability (DCCR) problem, the objective of which is to maximize the lifetime of a directional sensor network while continuously monitoring all targets in a specific level of coverage reliability. Our strategy to solve this problem is to group all of the deployed directional sensors into a number of subsets, each of which should cover all of the targets. Only one subset is active at any given time; all others go into a sleep state. We call this type of network organization directional cover-sets with coverage reliability. The cover-sets need not be disjoint and each of them can be activated successively one by one. Due to the NP-completeness of the DCCR problem we designed a heuristic algorithm to solve the problem, called directional coverage and reliability (DCR) greedy algorithm, which uses a greedy method to generate the maximum number of cover-sets satisfying coverage reliability. (In this paper, we omit the complete proof of the fact that the DCCR problem is NP-complete.) To verify and evaluate the proposed algorithm, we conducted simulations, which showed that the proposed algorithm extends network lifetime to a reasonable degree while guaranteeing a minimum reliability.

The remainder of this paper is organized as follows. Section 2 presents a brief review of related work. In Section 3, we introduce our directional sensor and network model. In Section 4, we present coverage reliability model based on detection probability and describe the DCCR problem. Section 5 describes the proposed greedy algorithm to solve the DCCR problem. In Section 6, we discuss the performance evaluation of the proposed algorithm with simulations. Finally, Section 7 concludes the paper.

2. Related Work

For omnidirectional sensor networks, many scheduling algorithms for prolonging network lifetime while guaranteeing target coverage have been studied [10–12]. The goal of target coverage is to make each target in the physical space of interest locate within the sensing range of at least one sensor. Cardei and Du [13] introduced the target coverage problem, where disjoint sensor sets are modeled as disjoint cover sets, such that every cover set completely monitors all of the targets. This was called the maximum set covers (MSC) problem and was shown to be NP-complete. Requirements related to this problem were alleviated in [14], where sensors were not restricted to participation only in disjoint sets; that is, a sensor could be active in more than one set.

The scheduling problems in directional sensor networks have recently attracted a great deal of interest. Compared to omnidirectional sensors, directional sensors are obviously different in that their coverage region is determined by both location and orientation. Therefore, the target coverage problem aiming at directional sensors will be more complicated than that focusing on omnidirectional sensors [15]. Previous studies regarding the coverage of directional sensor networks also aimed to maximize network lifetime by finding cover sets to cover all targets [7, 8, 16]. The initial work relevant to the coverage issue in directional sensor networks was presented in [7]. The authors formulated the maximum coverage with minimum sensors (MCMS) problem, in which coverage in terms of the number of targets to be covered is maximized, while the number of sensors to be activated is minimized. The genetic algorithms, based on evolutionary search techniques, were applied in [8, 15] to solve target coverage problem in directional sensor networks.

From different points of view, He et al. [17] aimed to deploying sensors to cover-sets including network reliability in target coverage problem. To achieve this aim, authors introduced the failure probability associated with each omnidirectional sensor into sensor networks and tried to improve the network reliability by using the similar solution used to solve MSC problem. In contrast to that work, our work focuses on the maximization of network lifetime and the improvement of network reliability in directional sensor networks. Moreover, based on the detection probability of each directional sensor, the coverage reliability that means how reliable directional sensors in cover-sets can monitor all targets with a specific level is significantly considered.

3. Directional Sensor and Network Model

3.1. Directional Sensor Model

Here, we describe directional sensor model used in this paper. A sensor has W orientations and operates in only one orientation at any time; the active sensing region is determined by the chosen orientation. We do not make any assumptions regarding the shape of sensing regions, except that each sensing region is constrained by an angle of view and it is also closed, connected, and without holes.

A directional sensor $s_i$ is represented by the six-tuple $〈P_i,R_s,o_{i,j},E_0(s_i),\omega 〉$ , where $P_i$ is the location of the sensor $s_i$ , $R_s$ is the sensing range, $o_{i,j}$ is jth orientation of sensor $s_i$ ( $j=\mathrm{1,2},\dots ,W$ , i.e., the number of orientations operated by a directional sensor is W), $E_0(s_i)$ is the initial energy of the sensor $s_i$ , and ω is the angle of view. In this paper, we assume that all deployed sensors are homogeneous in terms of sensing range, angle of view, and number of orientations. We also assume that each sensor is aware of its location by using an arbitrary localization method [18–20] and a directional sensor network is connected due to the large communication range of sensors without considering the connectivity issue of sensors.

3.2. Network Model

Let us consider a directional sensor network composed of N sensors. All sensors are randomly scattered to cover M targets with fixed locations in a two-dimensional plane. We define $S=\{s_1,s_2,\dots ,s_N\}$ as the set of N sensors and $T=\{t_1,t_2,\dots ,t_M\}$ as the set of M targets. Let O be the set of all $o_{i,j}$ for $i=\mathrm{1,2},\dots ,N$ and $j=\mathrm{1,2},\dots ,W$ and $O(t_m)$ be the set of orientations that cover a target $t_m\hspace{0.17em}\hspace{0.17em}(m=\mathrm{1,2},\dots ,M)$ . A sensor is active if it is selected to cover at least one target. A sensor that is not active goes into the sleep state. In this paper, directional sensor activity scheduling refers to determining the state of the deployed directional sensors (active or sleep).

4. Directional Cover-Set with Coverage Reliability Problem

In this section, we present the directional cover-sets with coverage reliability (DCCT) problem based on the directional sensor and network model described in the previous section.

4.1. Detection Probability Model

In real environment, each directional sensor has the detection probability of targets [21]. To take coverage reliability into consideration, we first describe the detection probability of targets in directional sensor networks.

To model the detection probability of targets, we modify the detection probability defined in [21] to accommodate directional sensors. We assume that the sensing range of each directional sensor $s_i$ is a form of disk, centered at $s_i$ , with radius $R_s$ and $s_i$ makes its orientation detection of whether a target $t_m$ is covered. The orientation detection function $f(\varphi (s_i,t_m))$ is given by $$\begin{array}{cc}& f\left(\varphi \left(s_i,t_m\right)\right)=\{\begin{array}{cc}\mathrm{1},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\varphi }_{s_i}\le \varphi \left(s_i,t_m\right)\le {\varphi }_{s_i}+\omega ,\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\end{array}$$ (1) where $\varphi (s_i,t_m)$ is an angle between $s_i$ and $t_m$ , ${\varphi }_{s_i}$ is an orientation angle of $s_i$ , and ω is the angle of view.

We also assume that each sensor $s_i$ has a detection probability of a target $t_m$ satisfying its orientation detection. The detection probability ${\widehat{p}}_{i,m}$ can be calculated by $$\begin{array}{cc}& {\widehat{p}}_{i,m}=p_{i,m}·f\left(\varphi \left(s_i,t_m\right)\right),\end{array}$$ (2) where $p_{i,m}$ is a detection probability that depends on the signal propagation of the target $t_m$ without any consideration of satisfying the orientation detection of the sensor $s_i$ . Using a general signal propagation model where the signal parameter θ attenuates along with the signal propagation, we can calculate $p_{i,m}$ as follows: $$\begin{array}{cc}& p_{i,m}=\text{Pr}\left[\frac{\theta }{d_i}+n_i\ge A\right]=Q\left(\frac{A-\theta /d_i}{{\sigma }_i}\right),\end{array}$$ (3) where $d_i$ is the Euclidean distance between $s_i$ and $t_m$ , and A is a threshold determining the minimum signal strength that can be correctly decoded at $s_i$ . $n_i$ is the measurement noise and is assumed that it follows a Gaussian distribution with zero mean and variance ${\sigma }_i^{\mathrm{2}}$ . $Q(·)$ is the Q-function defined by $$\begin{array}{cc}& Q\left(x\right)={\int }_x^{\infty }\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }}\mathrm{\hspace{0.17em}\hspace{0.17em}}{e}^{-t^{\mathrm{2}}/\mathrm{2}}dt.\end{array}$$ (4) If all directional sensors are homogenous physically, the noise variance ${\sigma }_i^{\mathrm{2}}$ of each sensor $s_i$ can be assumed to be identical. Then, we can rewrite (2) as follows: $$\begin{array}{cc}& {\widehat{p}}_{i,m}=Q\left(\frac{A-\theta /d_i}{\sigma }\right)·f\left(\varphi \left(s_i,t_m\right)\right).\end{array}$$ (5) From (5), we can say that the directional sensor $s_i$ covers the target $t_m$ if the received signal of $s_i$ is larger than the threshold A and an angle between $s_i$ and $t_m$ is within a sector.

4.2. Coverage Reliability

As we described in the previous section, each sensor $s_i$ has a detection probability when it covers a target $t_m$ . The detection probability means how well $s_i$ can detect the data emitted by $t_m$ and is associated with the signal propagation of $t_m$ . Using the detection probability ${\widehat{p}}_{i,m}$ defined by (5), we can obtain the coverage reliability of a target $t_m$ covered by more than at least one directional sensor (i.e., by $O(t_m)$ ). There are many fusion techniques that can be used to derive the coverage reliability from the detection probability of each directional sensor. In this paper, the coverage reliability of a target $t_m$ , ${\widehat{P}}_m$ , is given by $$\begin{array}{cc}& {\widehat{P}}_m=\mathrm{1}-\prod _{o_{i,j}\in O\left(t_m\right)}\left(\mathrm{1}-{\widehat{p}}_{i,m}\right),\end{array}$$ (6) where ${\widehat{p}}_{i,m}$ is a detection probability that a sensor $s_i$ having an orientation $o_{i,j}$ covers $t_m$ .

Now, we introduce the coverage reliability of a given cover-set that all targets can be reliably monitored. Using the coverage reliability of a target defined by (6), we can obtain the coverage reliability of a cover-set ${\rm Y}({\tau }_k)$ , where ${\tau }_k$ is a given lifetime for the cover-set. The coverage reliability of the cover set ${\rm Y}({\tau }_k)$ , $R({\tau }_k)$ , is given by $$\begin{array}{cc}& R\left({\tau }_k\right)=\arg \min \left\{{\widehat{P}}_{\mathrm{1}},{\widehat{P}}_{\mathrm{2}},\dots ,{\widehat{P}}_M\right\},\end{array}$$ (7) where M represents the number of targets.

Using the coverage reliability $R({\tau }_k)$ obtained by (7), we can guarantee that all targets are reliably monitored with the coverage reliability of more than $R({\tau }_k)$ by orientations in ${\rm Y}({\tau }_k)$ .

4.3. DCCR Problem Formulation

In this section, we present the directional cover-sets with coverage reliability (DCCR) problem, which is a classical optimization problem.

As an orientation $o_{i,j}$ can belong to multiple cover-sets until the lifetime of the sensor $s_i$ completely expires, we can define a Boolean variable $b_{i,j,k}$ as follows: $$\begin{array}{cc}& b_{i,j,k}=\{\begin{array}{cc}\mathrm{1},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{o}_{i,j}\in {\rm Y}\left({\tau }_k\right),\hfill \\ \mathrm{0},\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$ (8)

By using (8), we define the DCCR problem as follows: for given a set of targets T with fixed locations and the initial energy $E_0(s)$ of each sensor in a set of directional sensors S, find a set of cover-sets ${\rm Y}({\tau }_1),{\rm Y}({\tau }_2),\dots ,{\rm Y}({\tau }_X)$ with coverage reliabilities $R({\tau }_1),R({\tau }_2),\dots ,R({\tau }_X)$ such that (1) the network lifetime, denoted as $L(S,T,\kappa )$ , is maximized and (2) each coverage reliability is not smaller than a minimum coverage reliability κ. Mathematically, the DCCR problem is defined as

Maximize $$\begin{array}{cc}& L(S,T,\kappa )\equiv \sum _{k=\mathrm{1}}^X{\tau }_k\end{array}$$ (9)

subject to $$\begin{array}{cc}& \sum _{k=\mathrm{1}}^{X}E\left(s_i,{\rm Y}\left({\tau }_k\right)\right)\le E_{\mathrm{0}}\left(s_i\right),\hspace{1em}\mathrm{\hspace{0.17em}\hspace{0.17em}}\forall s_i\in S,\end{array}$$ (10) $$\begin{array}{cc}& \sum _{j=\mathrm{1}}^W{b}_{i,j,k}\le \mathrm{1},\hspace{1em}\forall s_i\in S,\hspace{0.17em}\hspace{0.17em}k=\mathrm{1},\dots ,X,\end{array}$$ (11) $$\begin{array}{cc}& \sum _{o_{i,j}\in O\left(t_m\right)}{b}_{i,j,k}\ge \mathrm{1},\hspace{1em}\forall t_m\in T,\hspace{0.17em}\hspace{0.17em}k=\mathrm{1},\dots ,X,\end{array}$$ (12) $$\begin{array}{cc}& R\left({\tau }_k\right)\ge \kappa ,\hspace{1em}k=\mathrm{1},\dots ,X,\end{array}$$ (13) where $$\begin{array}{cc}& b_{i,j,k}=\left\{\mathrm{0,1}\right\},\hspace{1em}\hspace{1em}{\tau }_k\ge \mathrm{0}.\end{array}$$ (14)

Equation (10) guarantees that the total energy consumed by each directional sensor $s_i$ across all cover-sets is not larger than its initial energy. Equation (11) guarantees that one directional sensor in a cover-set operates in at most one orientation. Equation (12) guarantees that each target is covered by at least one orientation in a cover-set. Finally, Equation (13) guarantees that all targets are reliably monitored by successive cover-sets in more than a certain level. Given a directional sensor network deployed in an area, the number of cover-sets, denoted by X, is finite but unknown. It should be noted that a sensor can appear in different cover-sets; that is, the sets of directional sensors in different cover-sets need not be disjoint. In the following section, we present a greedy algorithm to find such the cover-sets maximally.

5. The Proposed Greedy Algorithm to Solve the DCCR Problem

In this section, we propose a new heuristic algorithm, DCR greedy, to solve the DCCR problem. DCR greedy algorithm uses a greedy method to produce cover-sets and their coverage reliabilities by finding the cover-sets with coverage reliability in a given deployment of sensors and targets, based on the DCCR problem presented in Section 4.3.

The proposed algorithm is similar to those proposed previously [14, 17] but modified to capture the characteristics of directional sensor networks. Our algorithm takes as the input parameters S, T, $E_0(s_i)$ of each sensor $s_i$ , the minimum coverage reliability κ, and the angle of view ω. Each cover-set operates for a fixed amount of time τ, unless some sensors in the cover-set die due to a lack of power. The output of the proposed algorithm is a sequence of cover-sets ${\rm Y}({\tau }_1),{\rm Y}({\tau }_2),\dots ,{\rm Y}({\tau }_X)$ and their coverage reliabilities $R({\tau }_1),R({\tau }_2),\dots ,R({\tau }_X)$ . It is noted that X should be maximized. By using the output, we can obtain the network lifetime of a given network of directional sensors, each of which faces an arbitrary orientation at the initial time of deployment as follows: ${\tau }_1+{\tau }_2+···+{\tau }_X$ . When an identical value for all ${\tau }_k\hspace{0.17em}\hspace{0.17em}(k=1,\dots ,X)$ is used as τ, the output of the proposed algorithm becomes $X·\tau$ . Moreover, the output of the proposed algorithm guarantees that a given network of directional sensors can reliably operate for $X·\tau$ while keeping a minimum coverage reliability.

The pseudocode of the algorithm is shown in Algorithm 1. The following notations are used:

• (i)

$S_l$ : set of live sensors;

(ii)

$O_l$ : orientations of live sensors;

(iii)

$T(o_{i,j})$ : set of targets covered by an orientation $o_{i,j}$ ;

(iv)

x: index of cover-sets;

(v)

$E_r(s)$ : residual energy of a sensor s;

(vi)

$T_c$ : coverage reliability of a critical target $t_c$ ;

Algorithm 1: DCR-greedy algorithm.

Input parameters: $S,T,E_0\left(s_i\right),\kappa ,\omega ,\tau$

(1) $S_l=S,O_l=\varnothing ,x=0$

(2) for each $s_i\in S_l$  do

(3)  $E_r\left(s_i\right)=E_0\left(s_i\right)$

(4) for each orientation $o_{i,j}$ operated by $s_i$  do

(5)   $O_l=O_l\cup \left\{o_{i,j}\right\}$

(6) end for

(7) end for

(8) while  $O_l\ne \varnothing$  and ${\bigcup }_{o_{i,j}\in O_l}T\left(o_{i,j}\right)=T$  do

(9)  $x=x+1,TARGETS=T,{\tau }_x=\tau ,\mathrm{{\rm Y}}\left({\tau }_x\right)=\varnothing$

(10) while  $TARGETS\ne \varnothing$  do

(11)   Find a critical target $t_c\in TARGETS$ and calculate $T_c$ .

(12)    $O_c=\varnothing$

(13)   Find all orientations $\in O_l$ that cover $t_c$ and insert them into $O_c$

(14)   while  $T_c<\kappa$  do

(15)   Select ${o^{*}}_{s,t}\in O_c$ with the maximum profit $W\left({o^{*}}_{s,t}\right)$

(16)    $\mathrm{{\rm Y}}\left({\tau }_x\right)=\mathrm{{\rm Y}}({\tau }_x)\cup \left\{{o^{*}}_{s,t}\right\}$

(17)   for each orientation $o_{i,j}\in O_l$  do

(18)    if   $i=s$  then

(19)      $O_l=O_l-\left\{o_{i,j}\right\}$

(20)    end if

(21)   end for

(22)   Recalculate ${\mathrm{T}}_{\mathrm{c}}$

(23)  end while

(24)  for each ${\mathrm{t}}_{\mathrm{m}}\in \mathrm{T}\mathrm{A}\mathrm{R}\mathrm{G}\mathrm{E}\mathrm{T}\mathrm{S}$  do

(25)    if  $t_m$ is covered by $o_{i,j}\in \mathrm{{\rm Y}}\left({\tau }_x\right)$  and  $T_m\ge \kappa$  then

(26)     $TARGETS=TARGETS-\left\{t_m\right\}$

(27)    end if

(28)  end for

(29) end while

(30) for each $s\in \mathrm{{\rm Y}}\left({\tau }_x\right)$  do

(31)    $E_r\left(s\right)=E_r\left(s\right)-E\left(s,\mathrm{{\rm Y}}\left({\tau }_x\right)\right)$

(32)   if  $E_r\left(s\right)\le 0$  then

(33)    $S_l=S_l-\{s\}$

(34)   end if

(35) end for

(36)  $O_l={\bigcup }_{j=\mathrm{1}}^W\left\{o_{i,j}\right\}$  for each sensor $s_i$ in $S_l$

(37) end while

(38) return   $\mathrm{{\rm Y}}\left({\tau }_1\right),\mathrm{{\rm Y}}\left({\tau }_2\right),\dots ,\mathrm{{\rm Y}}\left({\tau }_X\right)\hspace{0.17em}\text{and}\hspace{0.17em}R\left({\tau }_1\right),R\left({\tau }_2\right),\dots ,R\left({\tau }_X\right)$

The algorithm repeatedly builds cover-sets and their coverage reliability until a cover-set is not found any more due to energy exhaustion of sensors. The process to find one cover-set and its coverage reliability stops once the entirety of each target is covered by at least one orientation of live sensors. The algorithm consists of the following steps.

Step 1.

Initialize the variables $S_l$ , $O_l$ , and x used in the algorithm and the residual energy of each sensor (lines 1–7).

Step 2.

To construct a cover-set, increase x by 1 and initialize the relevant variables such as TARGETS, ${\tau }_x$ , and ${\rm Y}({\tau }_x)$ (line 9).

Step 3.

A critical target $t_c$ is selected and defined as the most sparsely covered target, both in terms of number of sensors as well as the residual energy of those sensors [14]. After the critical target is selected, (6) is used to calculate the $T_c$ that denotes a coverage reliability of the critical target (line 11). The critical target is a bottleneck in the viewpoint of network lifetime; that is, when the energy of the sensors covering the critical target is completely exhausted, the target cannot be covered and hence the network lifetime will be terminated.

Step 4.

Initialize the variable $O_c$ and insert all orientations covering the critical target $t_c$ into $O_c$ (lines 12-13).

Step 5.

Determine whether the critical target $t_c$ is reliable or not (line 14). If $T_c$ is less than a minimum coverage reliability κ (i.e., the critical target is not as reliable as κ), proceed the next step to find another orientation covering the critical target except already selected orientations; otherwise go to Step 8.

Step 6.

Select the orientation $o_{s,t}$ with the maximum profit value $W(o_{i,j})$ among the orientations covering the critical target $t_c$ (line 15). Various profit functions can be defined and we consider two kinds of criteria; one is a reliability profit and the other is an energy profit. In this paper, we use the following function: $$\begin{array}{cc}& f\left(o_{i,j},t_c\right)=\alpha ·f_{\mathrm{1}}\left(o_{i,j},t_c\right)+\left(\mathrm{1}-\alpha \right)·f_{\mathrm{2}}\left(o_{i,j},t_c\right),\end{array}$$ (15) $$\begin{array}{cc}& f_{\mathrm{1}}\left(o_{i,j},t_c\right)=\prod _k\left(\mathrm{1}-p_{i,k}\right)·p_{i,c},\end{array}$$ (16) $$\begin{array}{cc}& f_{\mathrm{2}}\left(o_{i,j},t_c\right)=E_r\left(s_i\right),\end{array}$$ (17) $$\begin{array}{cc}& W\left(o_{i,j}\right)\equiv \arg \underset{o_{i,j}}{\max }f\left(o_{i,j},t_c\right),\end{array}$$ (18) where $0<\alpha <1$ . In (15), $f_1(o_{i,j},t_c)$ denotes a reliability profit function to get the coverage reliability of the critical target $t_c$ that is calculated by the detection probability of the orientation $o_{i,j}$ covering the critical target, and $f_2(o_{i,j},t_c)$ denotes an energy profit function to get the residual energy of the orientation $o_{i,j}$ covering the critical target. In (16), $p_{i,k}$ represents the detection probability of the sensor $s_i$ whose the orientation $o_{i,j}$ covers another target $t_k$ while covering the critical target $t_c$ and $p_{i,c}$ represents the detection probability of the sensor $s_i$ whose orientation $o_{i,j}$ covers the critical target $t_c$ . In terms of the reliability profit, the orientation $o_{i,j}$ is selected such that it has a maximum detection probability for the critical target and at the same time minimizes detection probability for other targets except the critical target. By choosing a proper value of α, the orientation will be selected such that it has higher contribution than any other orientations for detecting the critical target and the sensor $s_i$ with the selected orientation has more residual energy available.

Step 7.

Once the orientation $o_{s,t}$ is selected, it is added to the current cover-set ${\rm Y}({\tau }_x)$ (line 16) and all orientations of the sensor $s_s$ operating the selected orientation $o_{s,t}$ are removed from the live orientation set $O_l$ (lines 17–21).

Step 8.

Recalculate the coverage reliability $T_c$ (line 22) and go to Step 5.

Step 9.

All of the targets that are covered by $o_{s,t}$ and at the same time are not less than κ, are removed from the current target set, TARGETS (lines 24–28).

Step 10.

After the cover-set ${\rm Y}({\tau }_x)$ is built, the residual energy of each sensor in ${\rm Y}({\tau }_x)$ is updated (line 31).

Step 11.

Dead sensors are removed from the set of live sensors (lines 32–34). If a sensor has no residual energy, it becomes a dead sensor.

Step 12.

Before going to line 8 and repeating the above steps from Step 2, the set of available orientations $O_l$ is updated based on live sensors (line 36).

6. Performance Evaluation

In this section, we evaluate and analyze the performance of the proposed DCR greedy algorithm through simulations.

6.1. Simulation Environment

We simulated a stationary network with sensors and targets randomly deployed in an area of 500 m × 500 m. Our simulation environment assumes that the different numbers of targets ( $M=5$ and 15) are uniformly deployed in the area and the different numbers of sensors ( $N=20$ , 50, 80, and 110) are randomly scattered to cover the targets. The initial energy of each directional sensor $(E_0(s_i))$ was set to 1.0 and the active time of all cover-sets (τ) is set to 0.1. The values of three parameters for detection probability were chosen as follows: $A=2.0$ , $\theta =250$ , and $\sigma =1.65$ . We assume that all directional sensors can sense one of three orientations ( $W=3$ ) with a sensing range of 250 m and there is no overlap with the other two orientations; that is, the angle of view (ω) is fixed to $2\pi /3$ . The minimum coverage reliability (κ) ranged from 0.3 to 0.9 is used to study the effects on network lifetime.

The proposed DCR greedy algorithm is evaluated with the following two effects.

• (i)

Minimum coverage reliability: this is used to investigate whether our DCRgreedy algorithm can solve the DCCR problem defined in this paper. We then analyze the performance of our algorithm for the different values of minimum coverage reliability in terms of network lifetime.

(ii)

Orientation with maximum profit: as the value of α in the maximum profit function f defined in Section 5, we use one of the following three ones, each of which represents the different strategy to select an orientation with maximum profit.

• (a)

$\alpha =0.0$ : consider only the coverage reliability of targets.

(b)

$\alpha =0.5$ : consider both the coverage reliability of targets and the residual energy of directional sensors at the same time.

(c)

$\alpha =1.0$ : consider only the residual energy of directional sensors.

In the next subsections, we present the simulation results to analyze the effect of these factors on the network lifetime. The results presented here have been averaged over 30 simulation runs based on randomly generated networks.

6.2. Effect of Minimum Coverage Reliability

We investigated the impact of minimum coverage reliability on network lifetime. For this investigation, we fixed the value of α to 0.5, and network lifetime was evaluated for four values of minimum coverage reliability (i.e., $\kappa =0.3,0.5,0.7$ , and 0.9).

Figure 1 shows the comparison of network lifetime with varying minimum coverage reliability. The number of directional sensors (N) varied between 20 and 110 and the number of targets (M) was fixed as 5 (Figure 1(a)) and 15 (Figure 1(b)). The network lifetime almost linearly increased with the number of directional sensors regardless of the number of targets, because a larger number of directional sensors can be scheduled to cover the given targets. It should be noted that an increase in the number of directional sensors leads to more cover-sets, as more directional sensors are available for target coverage.

Figure 1

Comparison of network lifetime with varying minimum coverage reliability.

On comparing network lifetime for four values of minimum coverage reliability (κ), we can see that when high minimum coverage reliability is used, the resulting network lifetime tends to be low. This is natural because the cover-sets with high minimum coverage reliability are organized with more orientations than those with low one. Therefore, our DCR greedy algorithm can find the cover-sets satisfying a minimum coverage reliability when greedily selecting an energy-efficient orientation of a directional sensor to organize a cover-set.

6.3. Effect of Orientation with Maximum Profit

We investigated the effect of the orientation with maximum profit on network lifetime. The network lifetime is compared in accordance with the number of directional sensors for different orientation selection strategies. The number of directional sensors ranged from 20 to 110 was used to cover 5 and 15 targets, respectively. For simplicity, we set the minimum coverage reliability to 0.7. Three kinds of α to select the orientation with maximum profit were used in this evaluation.

Figure 2 shows the effect of the orientation with maximum profit on network lifetime. It is shown that the network lifetime is longest when α is 0.5, regardless of the number of directional sensors and targets. This indicates that our DCR greedy algorithm can maximally extended the network lifetime when it considers both the coverage reliability of targets and the residual energy of directional sensors at the same time.

Figure 2

Comparison of network lifetime according to different orientation selection strategies.

7. Conclusions

We have proposed a new scheduling problem called the DCCR problem and developed a heuristic algorithm called DCR greedy algorithm to schedule active directional sensors to maximize network lifetime. The active sensors in cover-sets scheduled by the algorithm can cover all of the targets while maintaining networks' satisfied coverage reliability. The algorithm can extend the lifetime of a directional sensor network maximally while continuously and reliably monitoring all targets with a specific level of coverage reliability. Throughout simulation studies, two effects regarding minimum coverage reliability and orientation with maximum profit were used to investigate the performance of our algorithm. The simulation results showed that the DCR greedy algorithm is suitable for solving the DCCR problem regardless of the minimum coverage reliability used. The DCR greedy algorithm achieves high performance in terms of network lifetime when it considers both the coverage reliability of cover-sets and the residual energy of directional sensors.