Target Q-Coverage Problem with Bounded Service Delay in Directional Sensor Networks

Abstract

Maximizing network lifetime is an important objective for the target-coverage problem. With practicable manufacture and cost reduction, directional sensor has been widely used in wireless sensor networks to save energy. In this paper, we address the target Q-coverage (TQC) problem to prolong the network lifetime with bounded service delay constraint in directional sensor networks. We propose a protocol to find a collection of coverage sets that satisfy the coverage quality requirement and the bounded service delay constraint, where the target in each coverage set may not be served continuously but can be served with tolerant service delay. By steering some sensors' directional antennas, our protocol could deal with the changes of network topology or monitoring tasks. Simulation results show that the performance of our protocol is close to the upper bound of the optimal solution.

1. Introduction

Wireless sensor networks (WSNs) could be applied to fire detection, battle field surveillance, environmental monitoring, and so on [1]. In these applications, one of the important tasks is to monitor a set of targets and collect the relevant data in the geographical region. Since sensor nodes are often deployed randomly, target coverage, which aims at covering the specified targets by a subset of the deployed sensor nodes, is a fundamental issue for target monitoring. In practical application, the importance of each target is often different, which requires various qualities of coverage. In other words, targets should be covered with different numbers of sensors to satisfy their QoS requirements, this is called target Q-coverage problem. Usually, sensor nodes use omnidirectional antennas to sense the targets. However, directional antennas can switch to a particular direction to transmit farther distances than omnidirectional antennas. With the manufacturing technology improvement and cost reduction, sensors with directional antennas are widely employed in many network models.

There have been a number of works on target coverage problem in directional sensor network [2–7]. Most of them assume that there are sufficient sensors deployed such that all targets always can be covered within the network lifetime. However, the assumption may not hold if some working sensors happen to fail or new targets need to be served. Thus, the previous coverage scheduling protocols may be not feasible in such flexible and scalable network environment. To solve the problem, the authors of [8] steer sensors periodically to serve more targets. Since targets may not be covered continuously, a protocol was proposed to minimize the maximum service delay, which determines how fast an interested message can be detected for a target. In their protocol, the network lifetime is not an optimization objective.

In this paper, we address the target Q-coverage problem with maximizing the network lifetime in directional sensor network and design a target coverage schedule to satisfy a bounded service delay. We suppose that at any time, each sensor serves for at most one sector to sense targets. Thus, all targets may not be covered simultaneously. The service delay is defined as the time interval from an event occurring to the event being detected. In target coverage problem, the service delay can be regarded as the tolerant maximal time duration of completing target coverage.

The target Q-coverage problem addressed in this paper is to construct a collection of coverage sets and schedule them to work alternately to prolong the network lifetime, which satisfies the target coverage requirement under given service delay bound $\tilde{ε}$ . We first model the problem as a mixed-integer programming problem. Then, we present the upper bound of the problem and propose a centralized schedule protocol. Finally, we simulate our algorithm. The simulation results demonstrate that the performance of our algorithm is close to the upper bound of the optimal solution.

The rest of this paper is organized as follows. In Section 2, we briefly present the related works in the literature. Then, we introduce the TQC problem under a service delay bound and prove it is NP-hard in Section 3. In Section 4, we show the formulation of this problem, the upper bound of network lifetime and the definition of sensor weight. Moreover, we present the relationship between the service delay bound and the total sector numbers of a sensor. In Section 5, we propose a centralized protocol to solve this problem. The simulation results presented in Section 6 demonstrate the high performance of our protocols in prolonging the network lifetime. We conclude this paper in Section 7.

2. Related Works

Target coverage is a fundamental problem in wireless sensor networks for environment monitoring and surveillance purposes. To maximize the lifetime of a network, a large number of energy-efficient scheduling algorithms have been proposed for omnidirectional sensor networks [9–12]. These works study the 1-coverage, k-coverage, connected coverage, and multiattributes coverage. By organizing sensors into a number of subsets and elaborately managing the duty cycle of subsets in which some sensor nodes are scheduled to sleep or enter a power saving mode while the remaining active nodes keep working, significant energy savings can be achieved.

There are also many strategies to deal with target coverage problem for directional sensor networks [2–7]. The authors of [2] study the partial coverage with directional antenna and firstly propose the maximum coverage with minimum sensors (MCMSs) problem, in which coverage, in terms of the number of targets to be covered, is maximized whereas the number of sensors to be activated is minimized. The authors of [3] address the multiple directional cover sets (MDCSs) problem by organizing the directions of sensors into a group of nondisjoint cover sets to extend network lifetime. Wang et al. approximate network lifetime for target coverage scheduling problem by randomized approach and genetic algorithm, respectively [4, 6]. In [5], a weighted centralized greedy algorithm (WCGA) is proposed to improve the coverage rate for targets. In [7], the authors study the target-oriented scheduling in directional sensor networks, where each target has different coverage quality requirement based on the distance.

Since different targets may need different numbers of sensors to cover to satisfy the various sensing quality requirements, the target Q-coverage problem is first defined in [13], and a column generation-based approach is proposed. In [14, 15], a heuristic algorithm and an energy-efficient greedy algorithm are proposed to solve the target Q-coverage problem.

There are some existing works which study how to schedule sensors “on” and “off” in omnidirectional sensor network, such that each target may be covered within a bounded time interval and the sensors would not drain their energy too fast [16–18]. Cao et al. [16] propose a distributed protocol to schedule node sleeping which guarantees a bounded-delay sensing coverage while maximizing network lifetime. Gu et al. [17] propose a unified sensing coverage architecture (uSense) to address flexible and efficient target coverage problem by three novel ideas: asymmetric architecture, generic switching, and global scheduling. The authors in [18] present a sleep-wake sensor system based on cyclic cellular automata, which is verified to be highly effective in the case of frequent communication failures and sensor failures. Wang and Cao [8] consider the coverage problem in directional sensor network, where sensors are periodically steered to cover more targets. Since the targets may be not covered continuously, the authors propose a centralized protocol and a distributed protocol to minimize the maximum service delay, respectively. However, it does not take into account the network lifetime.

This paper is inspired by the above works and makes a tradeoff between coverage delay and network lifetime in traditional sensor networks. We focus on maximizing network lifetime for target Q-coverage problem with a bounded service delay constraint in directional sensor network.

3. Network Model and Problem Description

Given a directional sensor network with m targets ${a_{1}, a_{2}, \dots, a_{m}}$ and n directional sensor ${s_{1}, s_{2}, \dots, s_{n}}$ . Each sensor has p $(p \geq 2)$ sectors which are centered at the sensor node with a sensing radius r and the sensing angle $θ = 2 π / p$ . Let $d_{i, j}$ denote the jth sector of the ith sensor, and let $S_{i, j}$ denote the set of targets covered by sector $d_{i, j}$ . Target $a_{l}$ can be covered by sector $d_{i, j}$ , if and only if $a_{l}$ is in the sensing range of sector $d_{i, j}$ . We suppose at any time a sensor can serve for at most one sector.

The tolerant service delay is the time interval from an event occurring at a target to the event being detected by a nearby sensor. It determines how fast an interested message can be detected for a target. In the target coverage problem, the service delay can be regarded as the tolerant time duration of completing a target coverage. In directional sensor network without considering the rotation delay, the service delay depends on two parameters: the number of sectors used by each sensor and the time duration of serving a sector at one time. We give an example to show the service delay in Figure 1, where the time duration of serving a sector at one time is set as 1. There are three full target coverage schedules as follows: (1) $s_{1} \to {a_{1}, a_{2}, a_{3}}$ , $s_{2} \to {a_{4}, a_{5}}$ , $s_{3} \to {a_{6}}$ ; (2) $s_{1} \to {a_{2}, a_{3}}$ , $s_{2} \to {a_{1}, a_{5}}$ , $s_{3} \to {a_{4}, a_{6}}$ ; (3) $s_{1} \to {a_{3}}$ , $s_{2} \to {a_{1}, a_{2}, a_{5}}$ , $s_{3} \to {a_{4}, a_{6}}$ . The maximal service delay of the schedule (1) occurs at sensor $s_{1}$ which has 3 sectors for serving target. The delay is $3 \cdot 1 = 3$ . With schedule (2), the maximal service delay is 2. With schedule (3), the maximal service delay is 3, as sensor $s_{2}$ has 3 sectors to serve.

Figure 1

An example of service delay in directional sensor network.

We use $\tilde{ε}$ to denote the service delay. By the above analysis, we can approximate it as the product of the maximal number of the serving sectors of sensors ε and the time duration that a sensor serves each sector w.

Suppose that each sensor has a unified lifetime E if a sensor serves for all the sectors simultaneously. Then if at any time a sensor serves only one sector, the lifetime of the sensor is $p \cdot E$ . We use an integer vector $Q = {q_{1}, q_{2}, \dots, q_{m}}$ to represent coverage requirements of targets, where $q_{l}$ represents the minimum number of sectors that target $a_{l}$ needs to be covered by.

In the following, we show the definition of the target Q-coverage problem bounded with a service delay $\tilde{ε}$ .

Definition 1.

A subset D of sectors is called $S D Q$ -covset if it can satisfy the coverage requirement, that is, for each target $a_{l}$ ( $l = 1,2, \dots, m$ ), there are at least $q_{l}$ different sectors in D to cover $a_{l}$ , and the number of selected sectors from each sensor cannot exceed $⌊ \tilde{ε} / w ⌋$ , where w denotes the duration time that a sensor works on each sector.

Definition 2.

Bounded service delay for target Q-coverage (SDTQC) problem: given m targets and n sensors in an energy-constrained directional sensor network, where each sensor has p sectors, $(p \geq 2)$ . The SDTQC problem is to find a collection of $S D Q$ -covsets, where there are at least $q_{l}$ $(q_{l} \geq 1)$ different sectors to periodically cover $a_{l}$ target $(l = 1, \dots, m)$ , such that the network lifetime is maximized, meanwhile ensure that the time duration for each $S D Q$ -covset cannot exceed the service delay bound $\tilde{ε}$ . Here, at any time each sensor serves at most one sector.

Now, we show how to calculate the network lifetime. In Figure 1, each sensor has 6 sectors and we suppose the lifetime of each sensor is 2 if a sensor serves for the 6 sectors simultaneously. So if each sensor serves at most one sector at any time, the lifetime of each sensor is $6 \times 2 = 12$ .

Supposing the given service delay bound $\tilde{ε} = 2$ in Figure 1, the network lifetime is computed as follows. (1)

Suppose $w = 1$ , so the maximal number of sectors that each sensor served in each coverage set is $2 / 1 = 2$ . By checking the schedules $(1) (2) (3)$ , only schedule (2) satisfies the service delay bound. As each coverage is accomplished in 2 time slots and each sensor serves only one sector each time, the lifetime that each sensor consumes with schedule (2) is 2 for every coverage (each coverage task). So if each sensor can construct $12 / 2 = 6$ coverage sets, then the network lifetime is $T_{1} = 6 \times 2 = 12$ .

(2)

Suppose $w = 0.5$ , then the maximal number of sectors that each sensor can serve in each coverage set is $2 / 0.5 = 4$ . Thereby, we can use the schedules $(1) (2) (3)$ to cover the targets in turns, and suppose the schedule order is $(1) (2) (3) (1) \dots$ . Then, with schedule (1) the sensors $s_{1}$ , $s_{2}$ , and $s_{3}$ cost lifetime 1.5, 0.5, and 1, the working time and service delay of schedule (1) is 1.5; sensors $s_{1}$ , $s_{2}$ , and $s_{3}$ in schedule (2) cost 1 lifetime for each coverage, the working time and service delay of schedule (2) is 1; the sensors $s_{1}$ , $s_{2}$ and $s_{3}$ in schedule (3) cost lifetime 0.5, 1.5, and 1, so the working time and service delay of schedule (3) is 1.5. For one round of schedules as $(1) (2) (3)$ , each of the three sensors costs 3 lifetime so they can finish $12 / 3 = 4$ rounds of schedules and $4 \times 3 = 12$ schedules, that is $(1) (2) (3) (1) (2) (3) (1) (2) (3) (1) (2) (3)$ . Then, the network lifetime is $T_{2} = (1.5 + 1 + 1.5) \times 4 = 16$ .

Theorem 3.

The SDTQC problem is NP-hard.

Proof.

The multiple directional cover sets (MDCSs) problem [3] is a special case of the SDTQC problem. This is because when $q_{l} = 1$ for each target $a_{l}$ and the delay bound is 0, the SDTQC problem becomes the MDCS problem. Since the MDCS problem is NP-hard [3], the SDTQC problem is NP-hard.

4. The SDTQC Problem

In this section, we first formulate the SDTQC problem into a mixed integer programming problem. Secondly, we show the relationship of the given service delay bound and the number of the sectors used by each sensor in each coverage. Thirdly, we present the upper bound of the network lifetime for the SDTQC problem.

4.1. The Integer Programming Problem for the SDTQC Problem

Firstly, we describe the notations for the SDTQC problem as follows. (i)

m: the number of targets in the network.

(ii)

n: the number of directional sensors in the network.

(iii)

K: the number of $S D Q$ -covsets.

(iv)

r: the sensing radius of sensor.

(v)

p: the number of sectors for each sensor. The angle of sector is $α = 2 π / p$ .

(vi)

E: the initial lifetime of sensor if all its sectors are served together, so the lifetime of a sensor is $p \cdot E$ if only one sector is served at any time.

(vii)

$\tilde{ε}$ : the bounded service delay.

(viii)

$s_{i}$ : the ith directional sensor, $1 \leq i \leq n$ .

(ix)

$a_{l}$ : the lth target, $1 \leq l \leq m$ .

(x)

$d_{i, j}$ : the jth sector of the ith sensor.

(xi)

$S_{i}$ : the sector set of sensor $s_{i}$ .

(xii)

A: the set of targets. $A = {a_{1}, a_{2}, \dots, a_{m}}$ .

(xiii)

S: the set of sensors. $S = {s_{1}, s_{2}, \dots, s_{n}}$ .

(xiv)

Q: targets' coverage requirement. $Q = {q_{1}, q_{2}, \dots, q_{m}}$ , where $q_{l}$ represents the number of sectors needed to serve for the lth target simultaneously.

(xv)

$S_{i, j} = {a_{l} ∣ a_{l} is covered by sector d_{i, j}}$ , which represents the target set covered by sector $d_{i, j}$ , $1 \leq i \leq n$ , $1 \leq j \leq p$ .

(xvi)

$C_{l} = {d_{i, j} ∣ d_{i, j} covers a_{l}}$ , which represents a set of sectors that can cover target $a_{l}$ , $1 \leq l \leq m$ .

(xvii)

$D_{k}$ : the kth $S D Q$ -covset.

(xviii)

$t_{k}$ : the working time allocated to each working sector of each sensor in $S D Q$ -covset $D_{k}$ , $k = 1, \dots, K$ .

(xix)

Boolean variable $x_{i, j, k}$ , $x_{i, j, k} = 1$ if the sector $d_{i, j}$ is in the $S D Q$ -covset $D_{k}$ , otherwise $x_{i, j, k} = 0$ .

The SDTQC problem can be formulated to a mixed integer programming problem as follows:

\begin{matrix} \max \sum_{k = 1}^{K} ‍ (t_{k} \cdot \max_{i} \sum_{j = 1}^{p} ‍ x_{i, j, k}), \end{matrix}

(1)

subject to

\begin{matrix} \sum_{d_{i, j} \in C_{l}} ‍ x_{i, j, k} \geq q_{l}, \forall a_{l}, \forall D_{k}, \end{matrix}

(2)

\begin{matrix} \sum_{k = 1}^{K} ‍ \sum_{j = 1}^{p} ‍ x_{i, j, k} \cdot t_{k} \leq p \cdot E, \forall s_{i} \in S, \end{matrix}

(3)

\begin{matrix} \sum_{j = 1}^{p} ‍ x_{i, j, k} \cdot t_{k} \leq \tilde{ε}, \forall s_{i}, \forall D_{k}, \end{matrix}

(4)

where

\begin{matrix} x_{i, j, k} = 0 or 1, t_{k} \geq 0 . \end{matrix}

(5)

Remarks

Constraint (2) guarantees that each target $a_{l}$ is covered by at least $q_{l}$ sectors in each $S D Q$ -covset $D_{k}$ .

Constraint (3) guarantees that for each sensor, the sum of lifetimes costed in all $S D Q$ -covsets cannot exceed its initial lifetime $p \cdot E$ .

Constraint (4) indicates that for each $S D Q$ -covset $D_{k}$ , its working time, which is also its service delay, cannot exceed the given service delay bound $\tilde{ε}$ .

The objective function (1) is to maximize the sum of all $S D Q$ -covsets’ lifetime. For each $S D Q$ -covset $D_{k}$ , the lifetime should be $t_{k} \cdot \max_{i} \sum_{j = 1}^{p} x_{i, j, k}$ , which is the maximal serving time among all sensors.

4.2. The Upper Bound of Network Lifetime

In this subsection, we present the upper bound of the SDTQC problem.

We know that the maximum lifetime of a sensor network is the smallest lifetime among all sensors. Since the time and the number of serving sectors of each sensor is uncertain, we consider the minimal time of serving each target in the network. Thus, the upper bound of network lifetime is as follows:

\begin{matrix} u = \min_{l} [\frac{| C_{l} |}{q_{l}} \cdot \frac{p \cdot E}{w} \cdot \tilde{ε}] . \end{matrix}

(6)

The maximal number of $S D Q$ -covsets which each sensor can join is $((p \cdot E / (w)))$ . For each target, there are at most $| C_{l} |$ sectors to cover it. So, if we select $q_{l}$ sensors(sectors) to cover target $a_{l}$ each time, there could be $(| C_{l} | / q_{l})$ groups of sensors to compose covsets. If we do not consider the service delay, the upper bound of the network lifetime is

\begin{matrix} \min_{l} [\frac{| C_{l} |}{q_{l}} \cdot \frac{p \cdot E}{w} \cdot w] = \min_{l} [\frac{| C_{l} |}{q_{l}} \cdot p \cdot E] . \end{matrix}

(7)

Given a service delay bound $\tilde{ε}$ for each $S D Q$ -covset $D_{k}$ , the time that $S D Q$ -covset $D_{k}$ completes a coverage is $t_{k} \cdot \max_{i} \sum_{j = 1}^{p} ‍ x_{i, j, k}$ (the notations of $t_{k}$ and $x_{i, j, k}$ are shown in Section 4.1). Obviously, $\max_{k} (t_{k} \cdot \max_{i} \sum_{j = 1}^{p} ‍ x_{i, j, k}) \leq \tilde{ε}$ .

Then, all sensor's lifetime for covering target $a_{l}$ to complete the target Q-coverage problem with the service delay bound $\tilde{ε}$ is calculated as follows:

\begin{matrix} \frac{| C_{l} |}{q_{l}} \cdot \frac{p \cdot E}{w} \cdot \max_{k} (t_{k} \cdot \max_{i} \sum_{j = 1}^{p} ‍ x_{i, j, k}) \leq \frac{| C_{l} |}{q_{l}} \cdot \frac{p \cdot E}{w} \cdot \tilde{ε} . \end{matrix}

(8)

Therefore, the upper bound of network lifetime of the target Q-coverage problem with the service delay bound $\tilde{ε}$ is shown in (6).

5. The Scheduling Protocol

In this section, we first present the sector weight. Secondly, we propose a centralized scheduling protocol based on the sector weight for the SDTQC problem.

5.1. The Sector Weight

In this subsection, we define the weight $W_{s}$ of a sector as: $W_{s} = W_{n} + W_{t} + W_{c}$ , where $W_{n}$ represents the contribution of the sector to the network, $W_{t}$ represents the contribution of the sector to each target covered by the sector, and $W_{c}$ represents the validity of the coverage area by sector.

Let $\tilde{D}$ denote the temporary set of the sectors which have been selected as $S D Q$ -covset at the current serving time, let $\tilde{A}$ denote the temporary set of targets whose requirements have been satisfied by $\tilde{D}$ , and let $\tilde{q_{l}}$ denote the current number of sectors in $\tilde{D}$ , which serve target $a_{l}$ .

The contribution of a sector to network is defined as follows:

\begin{matrix} W_{n} (d_{i, j}) = \frac{| S_{i, j} - \tilde{A} |}{| A - \tilde{A} |}, \end{matrix}

(9)

where

| S_{i, j} - \tilde{A} |

indicates the number of targets which are covered by sector

d_{i, j}

and whose coverage requirements are not satisfied by

\tilde{D}

| A - \tilde{A} |

indicates the number of targets whose coverage requirements are not satisfied.

$W_{t}$ is defined as follows:

\begin{matrix} W_{t} (d_{i, j}) = \max_{a_{l} \in S_{i, j}} \frac{q_{l} - \tilde{q_{l}}}{| C_{l} | - \tilde{q_{l}}} . \end{matrix}

(10)

W_{c}

is defined as the maximal proportion of the unsatisfied coverage requirement targets in the coverage target set of

d_{i, j}

\begin{matrix} W_{c} (d_{i, j}) = \frac{(| S_{i, j} - \tilde{A} |)}{| S_{i, j} |} . \end{matrix}

(11)

Thereby, the sector weight is presented as follows:

\begin{matrix} W_{s} (d_{i, j}) = \frac{| S_{i, j} - \tilde{A} |}{| A - \tilde{A} |} + \max_{a_{l} \in S_{i, j}} \frac{q_{l} - \tilde{q_{l}}}{| C_{l} | - \tilde{q_{l}}} + \frac{(| S_{i, j} - \tilde{A} |)}{| S_{i, j} |} . \end{matrix}

(12)

Now, as shown in Figure 2(a), we give an example that constructs target Q-coverage based on the sector weight.

Figure 2

An example of a network with 4 sensors and 9 targets, each sensor has 4 sectors.

There are 9 targets and 4 sensors, each of which has 4 sectors which are labeled in counterclockwise order and the first one begins with the X(positive)-axis shown in Figure 2(b). We discuss 3 sectors' weights: $d_{1,2}$ , $d_{1,3}$ , and $d_{4,2}$ . The coverage requirements of targets are as follows: $q_{1} = 1$ , $q_{3} = 1$ , $q_{4} = 1$ , $q_{5} = 2$ , and $q_{8} = 1$ . Suppose the current $S D Q$ -covsets $D_{k} = \emptyset$ . (1)

We compute the sector weights of $d_{1,2}$ and $d_{1,3}$ . $W_{s} (d_{1,2}) = (1 / 9) + \max (1) + 1 = 2 (1 / 9)$ and $W_{s} (d_{1,3}) = (3 / 9) + \max (1 / 2, 1 / 2, 2 / 3) + (3 / 3) = 2$ . So, we add sector $d_{1,2}$ into $D_{k}$ . This indicates the importance of giving priority to the sector that satisfies the requirements of the targets.

(2)

We compute the sector weight of $d_{1,3}$ and $d_{4,2}$ as $D_{k} = {d_{1,2}}$ . $W_{s} (d_{1,3}) = (3 / 8) + \max (1 / 2, 1 / 2, 2 / 3) + (3 / 3) = 2 (1 / 24)$ and $W_{s} (d_{4,2}) = (2 / 8) + \max (1 / 2, 2 / 3) + (2 / 2) = 1 (22 / 24)$ . So, we add sector $d_{1,3}$ into $D_{k}$ because $W_{n} (d_{4,2}) + W_{t} (d_{4,2})$ is smaller than $W_{n} (d_{1,3}) + W_{t} (d_{1,3})$ . This indicates the importance of giving priority to the sector which covers more uncovered targets.

5.2. A Centralized Scheduling Protocol with the Sector Weight

In the following, based on the sector weight, we propose a centralized scheduling protocol for the SDTQC problem: (the CSSW-SDTQC protocol). The main idea of the CSSW-SDTQC protocol for selecting a $S D Q$ -covset is that each time we choose the sector which has the maximum available lifetime. If there are some sensors with the same available lifetime, we will select the sector with the maximum sector weight. Here, the number of selected sectors from each sensor cannot exceed ε. Then we update the correlated variables and the value of each sector weight. We repeat these steps till we find a $S D Q$ -covsets $D_{K}$ and check whether it is minimal. Then we assign a maximum realizable lifetime $t_{K}$ to the $S D Q$ -covsets. Finally, we repeat this process until the network lifetime cannot be increased.

The algorithm is formally represented as follows.

The input parameters for this algorithm is below: S is the set of sectors, A is the set of targets, E is the initial lifetime of a sensor, Q is the targets' coverage requirement, and the definitions of $S_{i, j}$ , $C_{l}$ , $\tilde{ε}$ , p, and w are described as in Section 4. $ε = ⌊ \tilde{ε} / w ⌋$ . The set $S_{temp}$ records sectors whose corresponding sensors still have residual energy such that these sectors can be used in additional $S D Q$ -covset. The set $A_{temp}$ contains the targets that still need to be covered by the current $S D Q$ -covset $D_{K}$ . In Algorithm 1, the step 16 minimizes $D_{K}$ to make sure that there is no redundant sector in it. In step 17, the MAX_Lifetime $(D_{K})$ is to compute the maximal lifetime of $S D Q$ -covset $D_{K}$ , which is the minimal available lifetime among all sensors. In step 18, we find the maximal value $d_{\max}$ by comparing each $d_{i}^{'}$ , which is the maximal number of the serving sectors among all sensors, $d_{\max}$ is used to compute the maximal service delay of the current $S D Q$ -covset $D_{K}$ to construct a target Q-coverage. Therefore, for each $D_{K}$ , $t_{K} = d_{\max} \cdot w'$ .

Algorithm 1: CSSW-SDTQC( $S, A, E, Q, C_{l}, S_{i, j}, ε, p, w$ ).

(1) Let $d_{i}^{'}$ denote the selected sector number of sensor $s_{i}$ in the current $S D Q$ -covset

$D_{k}$ , $S_{i}$ denote the total sector set of sensor $s_{i}$ and $d_{\max}$ denote the maximal sector

number from each sensor in the current $D_{k}$

(2) Set $E [i] = p \cdot E (1 \leq i \leq n)$ , $K = 0$ .

(3) while (each target $a_{j}$ is covered by at least $q_{j}$ available sectors) do

(4) $S_{temp} = S$ , $A_{temp} = A$ , $D_{K} = \emptyset$ , $Q [l] = q_{l} (1 \leq l \leq m)$ , $d_{i}^{'} = 0 (1 \leq i \leq n)$

(5) Initialize the sector weight of each sector. $K + +$

(6) while $A_{temp} \neq \emptyset$ do

(7) Sort sectors in $S_{temp}$ in descending order based on the number of available

lifetime. If some sectors have the same value, give the priority to the sector

with the maximal value of the sector weight.

(8) Choose the first sector $d_{i, j}$ from the sort set.

(9) $D_{K} = D_{K} \cup {d_{i, j}}$ , $d_{i}^{'} = d_{i}^{'} + 1$ , $S_{temp} = S_{temp} - {d_{i, j}}$

(10) if $d_{i}^{'} = = ε$ then $S_{temp} = S_{temp} - S_{i}$

(11) for all target $a_{l} \in A_{temp}$ do

(12) if $a_{l}$ is covered by $d_{i, j}$ then $Q [l] = Q [l] - 1$

(13) if $Q [l] = = 0$ then $A_{temp} = A_{temp} - {a_{l}}$

(14) Update the sector wight of each sector.

(15) end while

(16) Minimize $D_{K}$ , check each $d_{i, j} (d_{i, j} \in D_{K})$ whether it is redundant.

(17) Compute MAX_Lifetime( $D_{K}$ ).

(18) $d_{\max} = MAX (d_{i}^{'})$

(19) $w' = \min (w$ , (MAX_Lifetime( $D_{K}$ )/ε) $)$ , $t_{K} = d_{\max} \cdot w'$ , $T = T + t_{K}$

(20) for all sectors $d_{i, j} \in D_{K}$ do

(21) $E [i] = E [i] - w'$

(22) if $E [i] = = 0$ then $S = S - S_{i}$

(23) end while

(24) returnK SDQ-covsets: $D_{1}, D_{2}, \dots, D_{K}$ and the network lifetime T

The centralized scheduling protocol returns k $S D Q$ -covsets: $D_{1}, D_{2}, \dots, D_{k}$ and the network lifetime T.

6. Performance Evaluation

In this section, we will compare our algorithm (CSSW) with the upper bound (UB) of optimal solution in Section 4.2.

6.1. Simulation Setup

In our simulation, we deploy the sensor nodes and targets randomly in a region of 300 m $\times$ 300 m area. The initial lifetime of each sensor E is set as 5, and the service delay bound $\tilde{ε}$ is set as 0.5. To evaluate the performance of our protocol under the different situations, we respectively set the service time of each sector w as 0.25, 0.1, and 0.05.

We evaluate the impact of the following three parameters on the performance of our algorithm: the number of sensors N, the number of targets M, and the sensing range of sensor R. The coverage requirement $q_{l}$ of each target is randomly set from 1 to 3. By keeping the service delay bound $\tilde{ε}$ as 0.5, we test our algorithm under the following three cases: (1)

$w = 0.25$ , $ε = 2$ , and $p = 2$ ,

(2)

$w = 0.1$ , $ε = 5$ , and $p = 5$ ,

(3)

$w = 0.05$ , $ε = 10$ , and $p = 10$ .

6.2. Performance Comparison

Firstly, we test the impact of the number of sensors on our algorithm and the upper bound. We set the sensing range of each sensor (R) as 30, 30, 20, and the number of targets ( $T N$ ) as 30, 50, and 30, respectively. The number of sensors increases from 150 to 270 with an increment of 30. As Figure 3 shows, the network lifetime increases with the number of sensors increasing.

Figure 3

Network lifetime versus sensor number.

Secondly, we change the number of targets and compare the network lifetime of our algorithms with the upper bound. We set the sensing range of sensors (R) as 20, 20, and 30, and randomly deploy 200, 150, and 200 sensors ( $S N$ ) in the simulation area, respectively. The number of targets is increased from 40 to 80 with a step width of 10. As Figure 4 illustrates, the network lifetime decreases with the number of targets increasing.

Figure 4

Network lifetime versus target number.

Thirdly, we evaluated the impact of sensing range on our algorithm and upper bound. We set the number of sensors as 120, 120 and 180, and the number of targets as 50, 30, 50, respectively. The sensing range is changed from 25 to 45 with an increment of 5. As Figure 5 shows, the network lifetime increases with the sensing range increasing.

Figure 5

Network lifetime versus sensing range.

According to the results of the above simulations, we find that the smaller the working time of each sector is, the larger the network lifetime is. These results validate the correctness of our example for the network lifetime in Section 3.

Moreover, from the three figures, we can find two phenomena: (1) when fixing the service delay bound, the smaller the serving time w of each sector is, the closer the gap between our algorithm and the upper bound; (2) with the increasing of the sensor number and the sensing range or the decreasing of the number of targets, the network lifetime of our algorithm is farther away from the upper bound.

The reason for the first phenomenon is as follows: when the serving time of each sector is decreased, the maximal number of sectors that each sensor can use is increased, so that the total lifetime of each sensor is increased and is closer to the upper bound.

For the second phenomenon, when the sensors become denser, each sector can cover more targets, the upper bound gets larger while the network lifetime of our algorithm cannot increase any more, since the selected $S D Q$ -covsets in each round cannot always use the minimal number of sectors.

From the simulation results, we observe that our algorithm is very close to the upper bound, which shows that our algorithm is efficient.

7. Conclusion

In this paper, we study the bounded service delay for target Q-coverage problem in directional sensor networks. This network model can be used in various applications, especially when the network topology changes or some nodes maybe fail. We rotate some correlative sensors to make them serve the targets periodically. This will prolong the service delay which affects the quality of service. Hence, we study the target Q-coverage problem with a bounded service delay in directional sensor networks. We first formulate the problem into a mixed integer programming problem. A centralized scheduling protocol is proposed to address this problem based on assigning the sectors to weight. At last, we compare our algorithm with the upper bound to evaluate our algorithm's efficiency.

Footnotes

Acknowledgments

Dr. D. Li was supported in part by the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China under Grant 10XNJ032. Ms. X. Lu was jointly supported in part by National Natural Science Foundation of China under Grants 61070191 and 91124001, and Research Fund for the Doctoral Program of Higher Education of China under Grant 20100004110001.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 114

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

Abouzeid

A. A.

Coverage by directional sensors in randomly deployed wireless sensor networks

Journal of Combinatorial Optimization 2006 11 1 21 41

2-s2.0-32944460423

10.1007/s10878-006-5975-x

Cai

Lou

X.-Y.

Target-oriented scheduling in directional sensor networks

Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM '07)

May 2007

1550 1558

2-s2.0-34548314593

10.1109/INFCOM.2007.182

Wang

Niu

Shen

Randomized approach for target coverage schedulingin directonal sensor network

4523

Proceedings of the Conference of Engineering Student Society (ICESS '07)

379 390 Lecture Notes in Computer Science

Chen

U.-R.

Chiou

B.-S.

Chen

J.-M.

Lin

An adjustable target coverage method in directional sensor networks

Proceedings of the IEEE Asia-Pacific Services Computing Conference

2008

174 180

Wang

Niu

Shen

Priority-based target coverage in directional sensor networks using a genetic algorithm

Computers and Mathematics with Applications 2009 57 11-12 1915 1922

2-s2.0-67349237761

10.1016/j.camwa.2008.10.019

Yang

Chen

Coverage quality based target-oriented scheduling in directional sensor networks

Proceedings of the IEEE International Conference on Communications (ICC '10)

May 2010

1 5

2-s2.0-77955355518

10.1109/ICC.2010.5501996

Wang

Cao

Minimizing service delay in directional sensor networks

Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '11)

April 2011

Shanghai, China

1790 1798

2-s2.0-79960873476

10.1109/INFCOM.2011.5934978

Cardei

Thai

M. T.

Energy-efficient target coverage in wireless sensor networks

Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '05)

March 2005

1976 1984

2-s2.0-25844504705

10.

Liu

Wan

P.-J.

Jia

Maximal lifetime scheduling for sensor surveillance systems with K sensors to one target

IEEE Transactions on Parallel and Distributed Systems 2006 17 12 1526 1536

2-s2.0-33947415624

10.1109/TPDS.2006.175

11.

Erzin

A. I.

Zalyubovskiy

V. V.

Choo

Maximizing lifetime for a sensor network

Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication (ICUIMC '08)

February 2008

436 440

2-s2.0-79959350366

10.1145/1352793.1352884

12.

Wang

Maximizing lifetime for multi-attributes of target coverage problem in wireless sensor networks

Proceedings of the China Wireless Sensor Network Conference (CWSN '08)

2009

13.

Zhao

QoS-aware target coverage in wireless sensor networks

Wireless Communications and Mobile Computing 2009 9 12 1645 1659

2-s2.0-72949083734

10.1002/wcm.748

14.

Chaudhary

Pujari

Q-coverage problem in wireless sensor networks

5408

Proceedings of the International Conference on Distributed Computing and Networking (ICDCN '09)

352 330 Lecture Notes in Computer Science

15.

Liu

Chen

Energy-efficient algorithm for the target Q-coverage problem in wireless sensor networks

Proceedings of the International Conference on Wireless Algorithms, Systems, and Applications (WASA '10)

2010

21 25

16.

Cao

Abdelzaher

Stankovic

Towards optimal sleep scheduling in sensor networks for rare-event detection

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05)

April 2005

20 27

2-s2.0-33744944530

17.

Hwang

D. H.-C.

USense: a unified asymmetric sensing coverage architecture for wireless sensor networks

Proceedings of the International Conference on Distributed Computing Systems (ICDCS '07)

2007

8 18

18.

Baryshnikov

Y. M.

Coffman

E. G.

Jr. Kwak

K. J.

High performance sleep-wake sensor systems based on cyclic cellular automata

Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN '08)

April 2008

517 526

2-s2.0-51249104125

10.1109/IPSN.2008.14

Target Q-Coverage Problem with Bounded Service Delay in Directional Sensor Networks

Abstract

1. Introduction

2. Related Works

3. Network Model and Problem Description

Definition 1.

Definition 2.

Theorem 3.

Proof.

4. The SDTQC Problem

4.1. The Integer Programming Problem for the SDTQC Problem

Remarks

4.2. The Upper Bound of Network Lifetime

5. The Scheduling Protocol

5.1. The Sector Weight

5.2. A Centralized Scheduling Protocol with the Sector Weight

Algorithm 1: CSSW-SDTQC( S , A , E , Q , C l , S i , j , ε , p , w ).

6. Performance Evaluation

6.1. Simulation Setup

6.2. Performance Comparison

7. Conclusion

Footnotes

Acknowledgments

References

Algorithm 1: CSSW-SDTQC( $S, A, E, Q, C_{l}, S_{i, j}, ε, p, w$ ).