Sage Journals: Discover world-class research

Abstract

Directional sensor networks have a lot of practical applications, and target coverage is one of the most important issues. In this article, we study the target coverage problem in directional sensor network, where directional sensors can rotate freely around their centers and targets are attached with differentiated coverage quality requirements. Our goal is to maximize the lifetime of sensor network, satisfying the coverage quality requirements of all targets. We model it as the maximum cover sets problem and address it by organizing the directions of sensors into a group of non-disjoint cover sets, which can cover all targets, satisfying their coverage quality requirements, and then schedule them alternately to extend the network lifetime. It consists of two parts. First, since directional sensor has infinite directions by rotating continuously, we propose sensing direction partition algorithm to find all non-redundancy directions for each sensor according to the targets deployed within the sensing region of the sensor. Then, based on the result of the sensing direction partition algorithm, we propose an efficient heuristic algorithm for the maximum cover sets problem to organize the directions of sensors into a number of non-disjoint cover sets and allocate work time for each cover set. Besides, we get an upper bound of the optimal solution for the problem. Finally, simulation results are presented to demonstrate the performance of our algorithm.

Keywords

Coverage quality directional sensor network network lifetime sensor scheduling target coverage

Introduction

Wireless sensor network is a multi-hop ad-hoc network, consisting of sensor nodes with low cost and stringent power budget through wireless communication, which is capable of monitoring physical phenomenon in real time, collecting, transmitting, and processing information in the fields of sensors. Wireless sensor network has powerful function and extensive application.¹ How to assign monitoring tasks to sensor nodes to make them effectively accomplished and how to reflect how well a sensor field is monitored are the fundamental problems in wireless sensor network, which are considered as coverage problems. In general, coverage problems can be classified into four categories: area coverage,^2–9 target coverage,^10–22 barrier coverage,^23–25 and coverage problem aiming at determining the maximal breach path (MBP) and the maximal support path (MSP).²⁶ In this article, we consider the target coverage problem.

In view of the surveillance nature and the energy constraint of sensor networks, it is very important to prolong the network lifetime for solving coverage problem. Among many proposed approaches, there are three basic types. The first one is density control by utilizing the inherent redundancy of densely deployed sensors,^2–6 which uses the number of working sensors as less as possible to satisfy the coverage requirement and turns off redundant sensors. When the coverage requirement is not met due to sensor nodes’ failure, redundant sensors can be activated to replace fault nodes to ensure network normal operation, so that the network lifetime can be extended. The second one is node scheduling by organizing sensors into a number of subsets,^9–15 in which each subset can satisfy the coverage requirement, and scheduling them alternately to prolong the network lifetime. The third one is energy control by adjusting the sensing and communication ranges of sensors to reduce energy consumption as much as possible.^20–22 In this article, we consider the sensor scheduling.

Conventional sensor networks adopt omni-directional sensors. Actually, in view of low cost and energy conservation, directional sensors with limited angle of sensing range have great value of practical application, such as video sensors, ultrasonic sensors, and infrared sensors. Previous studies on coverage problem mainly focus on the fixed directional sensors that cannot turn their orientations to cover different sensing regions upon initial placement. In the researches,^13–16 the sensors are sub-tunable, that is, each sensor has finite separate and fixed work directions by turning to specific orientations and one sensor can only choose one direction to work at any time. However, a high-demanding coverage in important, and complicated places (such as bank, traffic, intelligence building, airport, and station) needs high accuracy and flexibility; it is inefficient to use fixed directional sensors or sub-tunable sensors in practice. We consider that the sensors can rotate their orientations around centers freely, which is viable in most of commercial camera sensors, and as a consequence, the sensors with infinite work directions have chance of covering more targets.

In practical application, the importance of each target may be different and the coverage quality required by each target is related to its importance. For example, in a video monitoring system, some key sites (such as nuclear reactors, entrances, and exits) need to be covered by more sensors so as to guarantee the fault tolerance of the system. In addition, if the monitoring data of targets have a certain precise requirements, the targets also need to be covered by more sensors to improve the sampling frequency. Generally, the coverage quality that sensors can provide to targets is influenced by the distance between sensors and targets, and it decreases as the distance increases. We assume that the coverage quality obtained by one target from sensors is the sum of actual coverage quality provided by all sensors covering it.

In this article, we consider the target coverage problem in directional sensor network where sensors have infinite directions by rotating continuously and targets require different coverage quality requirements. We assume that the density of sensors is sufficiently high to monitor all targets. We aim at maximizing the lifetime of directional sensor network and satisfying the coverage quality requirements of all targets. Several difficulties make our issue challenging. First, unlike wireless sensor networks, target coverage in directional sensor networks is determined by both location and direction of sensors. This feature makes target coverage scheduling more complex. Second, every sensor can rotate its orientation around the center freely, so it has infinite work directions. However, it is impossible to check all feasible choices exhaustively. Moreover, individual targets may be associated with differentiated coverage quality requirements, and the coverage quality that sensors can provide to targets is also different. So, for some targets, only one sensor may not satisfy its coverage requirement, and it needs some sensors to work cooperatively in order to achieve the coverage goal.

Our method is to study the intrinsic relationship between the work directions of sensors and the targets deployed within sensing region of sensors, and we propose sensing direction partition (SDP) algorithm to find all non-redundant directions for each sensor. Then, we design heuristic algorithm for the maximum cover sets (HMCS) problem to divide the directions of sensors into non-disjoint cover sets such that every cover set completely covers all targets satisfying their coverage quality requirements and then allocate work time for each cover set. These cover sets are activated alternately, such that at any moment, only one cover set is active. All sensors are in sleep state except sensors having a direction from the active cover set.

The rest of this article is organized as follows. First, we briefly review related research. Second, we define the directional sensor network model and the maximum cover sets (MCS) problem. We get an upper bound of the optimal solution for the problem and then formulate the MCS problem as integer programming formulation. Based on the model, we propose SDP and HMCS algorithms to solve the problem we study and simulation results are presented to show the performance of our algorithm. Finally, we conclude this article.

Related works

Coverage, as a fundamental concept in wireless sensor networks, is a reflection of the quality of service (QoS) of sensing function.²⁶ In the study of coverage problem, target coverage is an important part where the goal is to cover discrete targets satisfying the coverage requirements of all targets and extend the network lifetime. Referring to literature, one of the effective methods is node scheduling by dividing sensors into disjoint or non-disjoint subsets to alternately activate them. Slijepcevic and Potkonjak,⁹ Cardei and Du,¹⁰ and Diop et al.¹¹ design centralized protocols by organizing sensors into disjoint subsets, where sensors are restricted to participate in only disjoint subsets, that is, a sensor can be active in not more than one subset. Theoretically, the upper bound of the number of disjoint subsets is the minimum number of sensors covering each target. Cardei et al.¹² study maximum set covers (MSC) problem and maximize the lifetime of network by organizing sensors into non-disjoint set covers, where each sensor can be part of more than one set covers. The set of solutions to the disjoint subsets problem is a subclass of the non-disjoint subsets problem, so it often produces better result by dividing sensors into non-disjoint subsets. In this article, we consider the case that sensors are divided into non-disjoint subsets to cover targets.

Recently, research on directional sensors has made great progress, and many strategies about target coverage have been proposed in directional sensor networks. Maximum coverage with minimum sensors (MCMS) problem is studied by Ai and Abouzeid,¹⁶ which is designed to activate the minimal number of directional sensors to cover the maximal number of targets. Lu and Li¹⁷ use the directional sensor model with tunable directions and study maximum directional sensor coverage (MDSC) problem by assigning directions to sensors to maximize the number of targets covered by sensors. Zhang et al.¹⁸ focus on the fairness-based coverage maximization problem; they consider how to schedule the orientations of camera sensors to maximize the minimum accumulated full-view coverage time of target points. However, these studies consider the practical scenario where sensors initially deployed are not sufficient to provide full coverage (or full-view coverage¹⁸). Different from them, in this article, we consider that sensors are abundant to cover all targets satisfying their coverage quality requirements. Li et al.¹³ address target Q-coverage (TQC) problem under the constraint of bounded service delay in directional sensor networks aiming at maximizing the lifetime of network. However, this study considers the scenario where targets in each coverage set may not be served continuously but can be served with tolerant service delay. In this article, we focus on sensors monitoring all targets continuously as long as possible. Cai et al.¹⁴ address multiple directional cover sets (MDCS) problem by organizing the directions of sensors into non-disjoint cover sets. But in their works, they consider that directional sensors have a finite set of separate and fixed work directions and that targets are considered with the same importance and the coverage quality requirements of targets are not considered.

Among those existing literature, Yang et al.¹⁵ and Wang et al.¹⁹ are particularly relevant to our work. Yang et al.¹⁵ study the maximal network lifetime scheduling (MNLS) problem where the coverage quality requirements of targets are different. However, our problem differs from their problem in the following several ways. First, the directional sensors in our model could rotate freely, while the sensors in their model are sub-tunable, because in their setting, each directional sensor has finite separate and fixed work directions. As a consequence, the sensors in our model have chance to cover more targets. For instance, as shown in Figure 1, a sensor could cover three targets, not just two. Second, despite the directional sensors in our model may have infinite work directions by rotating continuously around their centers, we study the intrinsic relationship between the work directions of sensors and the targets deployed within the sensing region of the sensors, and eliminate the redundant directions (where two directions are redundant if they cover the same set of targets). So that each directional sensor can have finite non-redundant directions, which leads to significant dimension reduction. Third, in the problem of Yang et al.,¹⁵ for each sensor, the finite directions are independent, that is, the covered target sets of any two different directions are disjoint. In our problem, for one target, it is possible to be covered by two non-redundant directions, which makes our problem more difficult.

Figure 1.

(a) The sensor has four fixed directions, and this sensor can cover two targets at most; (b) the sensor is freely tunable, and this sensor can cover three targets.

Sensors equipped with continuous rotation capacity are considered by Wang et al.,¹⁹ thus each sensor has infinite directions and sensing regions of different directions may overlap. Given the assumption that targets to be covered have the prescribed priorities, they strive to find the minimum number of directional sensors to monitor all targets satisfying their prescribed priorities. Different from them, we study the target coverage problem in directional sensor network aiming at maximizing the directional sensor network lifetime and satisfying the coverage quality requirements of targets at any instant.

Sensor network model and problem description

In this section, we present the directional sensor network model and the formulation of MCS. Beyond that, we get an upper bound of the optimal solution for the MCS problem and then formulate the MCS problem as integer programming formulation.

To facilitate understanding, we first list the notations adopted throughout this article:

$M$ : number of targets

$N$ : number of sensors

$a_{m}$ : $m$ th target, $1 \leq m \leq M$

$s_{i}$ : $i$ th sensor, $1 \leq i \leq N$

$A$ : set of targets, $A = {a_{1}, a_{2}, \dots, a_{M}}$

$S$ : set of sensors, $S = {s_{1}, s_{2}, \dots, s_{N}}$

$c_{i}$ : possible number of directions of sensor $s_{i}$ , $1 \leq i \leq N, 1 \leq c_{i} < \infty$

$d_{i, j}$ : $j$ th direction of sensor $s_{i}$ , $1 \leq i \leq N$ , $1 \leq j \leq c_{i}$ . We define $d_{i, j} = {a_{m} | a_{m}$ is covered by $d_{i, j}$ , $\forall a_{m} \in A}$ . Here, if $a_{m} \in d_{i, j}$ , $a_{m}$ is covered by $d_{i, j}$ .

$D_{i}$ : set of directions of sensor $s_{i}$ , $D_{i} = {d_{i, j} | 1 \leq i \leq N, 1 \leq j \leq c_{i}}$

$D$ : collection of direction sets of all sensors, $D = {D_{1}, D_{2}, \dots, D_{N}}$

$L_{i}$ : lifetime of sensor $s_{i}$

$\vec{f_{i}}$ : orientation of sensor $s_{i}$

$R$ : sensing radius of sensors

$α$ : sensing angle of sensors

$S_{m}$ : set of sensors covering target $a_{m}$ , $1 \leq m \leq M$

$xy (node)$ : coordination function that provides the location for node

$u (s_{i}, a_{m})$ : function reflecting the coverage quality that sensor $s_{i}$ can provide to target $a_{m}$

$g (a_{m})$ : function reflecting the coverage quality required by target $a_{m}$

Considering the distance between sensors and targets influences the coverage quality, without loss of generality, and we employ the functions as defined as follows

$u (s_{i}, a_{m}) = 1 - {(\frac{dist (s_{i}, a_{m})}{R})}^{2}$ ; $g (a_{m}) = z$ , where $z$ is randomly and uniformly chosen within $(0, 1]$ .¹⁹

Model and problem

First, we describe the sensor network model and then give definitions of the problem we study.

We consider a directional sensor network with $N$ directional sensors $S = {s_{1}, s_{2}, \dots, s_{N}}$ and $M$ targets $A = {a_{1}, a_{2}, \dots, a_{M}}$ . The targets with known locations are deployed in a two-dimensional Euclidean plane, and the directional sensors are randomly scattered close to these targets. We assume that sensors are abundant to cover all targets. Note that the directional characteristic that we discuss in this article is from the point of view of the sensing, but not from the communicating activity of sensor nodes. We do not take the energy consumed for data collection and transmission into consideration, and omit the energy consumed by switching from a direction of sensor to another.

For each sensor $s_{i}$ , its sensing region can be modeled as a sector, which is characterized by three parameters: sensing range $R$ , sensing angle $α$ , and orientation $\vec{f_{i}}$ . The sensing range $R$ and sensing angle $α$ are unique for all sensors, and the orientation $\vec{f_{i}}$ (the internal bisector of $s_{i}$ ’s sensing area) of each sensor rotates around the center freely. We view every sector as a work direction and note that every time only one direction of each sensor can be activated. For each target, it is associated with a coverage quality requirement. Target $a_{m}$ can be covered by direction $d_{i, j}$ only when $a_{m}$ is in the sensing region of $d_{i, j}$ . The coverage quality required by target $a_{m}$ is $g (a_{m})$ , and the coverage quality that sensor $s_{i}$ can provide to target $a_{m}$ is $u (s_{i}, a_{m})$ . The coverage quality obtained by target $a_{m}$ from sensors is the sum of actual coverage quality provided by all sensors covering it.

According to the directional sensor network model, we attempt to solve the problem of how to schedule the work directions of sensors to maximize the lifetime of directional sensor network, satisfying the coverage quality requirements of all targets.

It is challenging to solve the problem. First, each camera sensor has infinite choices to decide their work directions by rotating continuously. It is impossible to check all feasible choices exhaustively. Furthermore, targets have different coverage quality requirements, and the coverage quality that sensors can provide to targets is also different. Sensors need to work cooperatively at the same time slot so that targets can be covered satisfying their coverage quality requirements.

In order to solve this problem, we should give reasonable and explicit definitions based on the directional sensor network model.

Definition 1. Cover set

Given a directional sensor network with sensor set $S = {s_{1}, s_{2}, \dots, s_{N}}$ and target set $A = {a_{1}, a_{2}, \dots, a_{M}}$ The direction set of sensors is $D$ , where each direction is represented as a subset of $A$ that is the set of targets in the sensing region of the direction. A cover set is a subset $C \subseteq D$ such that every target in $A$ belongs to at least one member of $C$ and its coverage quality requirement is satisfied.

Definition 2. MCS

Given a directional sensor network with sensor set $S = {s_{1}, s_{2}, \dots, s_{N}}$ , target set $A = {a_{1}, a_{2}, \dots, a_{M}}$ , and the lifetime of sensor $s_{i}$ is $L_{i}$ . Find a family of $K$ cover sets $C_{1}, C_{2}, \dots, C_{K}$ , with nonnegative weights $t_{1}, t_{2}, \dots, t_{K}$ , such that $TL = t_{1} + t_{2} + \dots + t_{K}$ is maximized, and for each $s_{i} \in S$ , the total weight that $s_{i}$ appears in cover sets $C_{1}, C_{2}, \dots, C_{K}$ is at most $L_{i}$ .

Theorem 1. MCS problem is NP-hard.

Proof. When we set $u (s_{i}, a_{m}) = 1$ and $g (a_{m}) = 1$ for $1 \leq i \leq N$ , $1 \leq m \leq M$ , the MCS problem is the same as MDCS problem in Cai et al.¹⁴ Since MDCS problem is NP-hard, the MCS problem is also NP-hard.

Upper bound of network lifetime

In this section, we present an upper bound of the optimal solution for the MCS problem.

Apparently, the maximum network lifetime is decided by the minimum lifetime of sensors. Since the work time and the number of directions of sensors are depended on the deployment of sensor network, which is random, we can consider the minimum time that each target is covered by sensors in the network.

For each target $a_{m}$ , we assume $S_{m}$ is the set of sensors covering it. Then, the target $a_{m}$ can be covered at most $l_{m} = \frac{\sum_{s_{i} \in S_{m}} L_{i} \times u (s_{i}, a_{m})}{g (a_{m})}$ time units. So, the $\min$ $l_{m}$ is the upper bound of network lifetime, that is

UBound = mi n_{m} (\frac{\sum_{s_{i} \in S_{m}} L_{i} \times u (s_{i}, a_{m})}{g (a_{m})}) .

Integer programming formulation for MCS problem

We assume that the possible number of directions of sensor $s_{i}$ is $c_{i}$ , $1 \leq c_{i} < \infty$ . Let us set a bound $K$ for the number of cover sets. We formulate the MSC problem as follows:

Given: sensor set $S = {s_{1}, s_{2}, \dots, s_{N}}$ , target set $A = {a_{1}, a_{2}, \dots, a_{M}}$ .

We define a Boolean variable $x_{i, j, k}$ as

x_{i, j, k} = {\begin{matrix} 1, & d_{i, j} \in C_{k} \\ 0, & otherwise \end{matrix}

(1)

The optimization problem can be written as follows

Maximize

TL = t_{1} + t_{2} + \dots + t_{K}

(2)

Subjected to

\sum_{k = 1}^{K} \sum_{j = 1}^{c_{i}} x_{i, j, k} \cdot t_{k} \leq L_{i}, \forall s_{i} \in S

(3)

\sum_{j = 1}^{c_{i}} x_{i, j, k} \leq 1, \forall s_{i} \in S, k = 1, 2, \dots, K

(4)

\sum_{d_{i, j} \in C_{k}} u (s_{i}, a_{m}) \cdot x_{i, j, k} \geq g (a_{m}), \forall a_{m} \in A, k = 1, 2, \dots, K

(5)

x_{i, j, k} \in {0, 1} and t_{k} \geq 0, \forall i, j, k

(6)

The objective function (2) maximizes the total network lifetime of $K$ cover sets. The constraint (3) insures that the time allocated for each sensor, across all cover sets, is not more than the initial lifetime of the sensor. Constraint (4) indicates that every directional sensor can only choose one direction to work at one time slot, so it has at most one direction in a cover set depending on whether the sensor is activated. Constraint (5) guarantees that the coverage quality requirement of each target is satisfied by each cover set. Constraint (6) shows restriction on variables.

Algorithm for MCS problem

To solve the MCS, our method is to organize the directions of sensors into a group of non-disjoint cover sets and schedule them alternately to extend the network lifetime. It consists of two parts. First, we find all non-redundant directions for each sensor according to SDP. Then, based on the result of SDP, we propose an efficient heuristic algorithm (HMCS) to divide the directions of sensors into non-disjoint cover sets and allocate work time for each cover set.

SDP

Here, we propose SDP to find all non-redundant directions for each sensor according to the targets deployed within the sensing region of the sensor, where two directions are redundant if they cover the same set of targets. The details are shown in Algorithm 1.

Algorithm 1 SDP
Require: sensor set $S = {s_{1}, s_{2}, \dots, s_{N}}$ , target set $A = {a_{1}, a_{2}, \dots, a_{M}}$ , sensing radius $R$ , sensing angle $α$ , and coordinate function $xy (node)$ Ensure: collection of target subsets $D = {D_{1}, D_{2}, \dots, D_{N}}$ 1: let $S^{'} = S$ , $D = \emptyset$ 2: while $S^{'} \neq \emptyset$ do 3: for $i = 1$ to $N$ do 4: $T = \emptyset$ 5: for $m = 1$ to $M$ do 6: if $∥ xy (s_{i}) - xy (a_{m}) ∥_{2} < R$ then 7: $T = T \cup {a_{m}}$ 8: end if 9: end for 10: if $T \neq \emptyset$ then 11: for $a_{m} \in T$ do 12: compute offset angle $Θ$ with respect to the X(positive)-axis 13: get target set $D_{i}^{m}$ where each target is within angle section $[θ, θ + α]$ 14: $D_{i} = D_{i} \cup D_{i}^{m}$ 15: end for 16: end if 17: $D = D \cup D_{i}$ 18: $S^{'} = S^{'} - {s_{i}}$ 19: end for 20: end while 21: return $D$

Algorithm 1 SDP

Require: sensor set

S = {s_{1}, s_{2}, \dots, s_{N}}

, target set

A = {a_{1}, a_{2}, \dots, a_{M}}

, sensing radius

R

, sensing angle

α

, and coordinate function

xy (node)

Ensure: collection of target subsets

D = {D_{1}, D_{2}, \dots, D_{N}}

1: let

S^{'} = S

D = \emptyset

2: while

S^{'} \neq \emptyset

do 3: for

i = 1

N

do 4:

T = \emptyset

5: for

m = 1

M

do 6: if

∥ xy (s_{i}) - xy (a_{m}) ∥_{2} < R

then 7:

T = T \cup {a_{m}}

8: end if 9: end for 10: if

T \neq \emptyset

then 11: for

a_{m} \in T

do 12: compute offset angle

Θ

with respect to the X(positive)-axis 13: get target set

D_{i}^{m}

where each target is within angle section

[θ, θ + α]

14:

D_{i} = D_{i} \cup D_{i}^{m}

15: end for 16: end if 17:

D = D \cup D_{i}

18:

S^{'} = S^{'} - {s_{i}}

19: end for 20: end while 21: return

D

Figure 2 shows an example of determining the directions of directional sensor. There are seven targets that can be covered by directional sensor $s$ . According to the algorithm SDP, sensor $s$ has seven non-redundant directions. Take the first four directions for example, when $s$ is in the first direction (or second, third, and fourth direction), it covers the set of targets ${a_{1}, a_{2}, a_{3}}$ ( ${a_{2}, a_{3}}$ , ${a_{3}, a_{4}}$ , and ${a_{4}, a_{5}}$ , respectively).

Figure 2.

An example of determining the directions of directional sensor. (a) When s is in the first direction, it covers the set of targets ${a_{1}, a_{2}, a_{3}}$ . (b) When s is in the second direction, it covers the set of targets ${a_{2}, a_{3}}$ . (c) When s is in the third direction, it covers the set of targets ${a_{3,} a_{4}}$ . (d) When s is in the fourth direction, it covers the set of targets ${a_{4}, a_{5}}$ .

HMCS

In this section, we describe the HMCS. We define $g (a_{m})_{r}$ as the remainder coverage quality that target $a_{m}$ requires and initialize it with $g (a_{m})$ . Let $U_{i, m}$ denote the coverage quality that sensor $s_{i}$ can provide to target $a_{m}$ , and $U_{i, j, m}$ denote the coverage quality that direction $d_{i, j}$ can provide to target $a_{m}$ . Let $V_{i, j, m}$ be the actual coverage quality obtained by target $a_{m}$ from direction $d_{i, j}$ , and it is initialized with $\min$ ${g (a_{m})_{r}, U_{i, j, m}}$ .

The main idea of HMCS algorithm is to organize the directions of sensors into a number of non-disjoint cover sets and allocate work time for each cover set. When constructing cover sets, we keep on choosing the direction with the maximum available lifetime. If some directions have the same available lifetime, we give priority to the direction providing the greatest total actual coverage quality to targets. Then, we put the selected direction into $C_{k}$ until $C_{k}$ is a cover set. If the direction $d_{i, j}$ is selected, we need to delete the remainder directions of sensor $s_{i}$ in $D_{c}$ because one sensor can only choose one direction in a cover set, and update $g (a_{m})_{r}$ of all targets covered by direction $d_{i, j}$ . After the reminder coverage quality of one covered target is updated, the actual coverage quality provided by the directions covering that target also needs to be updated. Note that if $V_{i, j, m}$ is greater than $g (a_{m})_{r}$ , we should set $V_{i, j, m} = g (a_{m})_{r}$ , because the part of coverage quality beyond $g (a_{m})_{r}$ is not used by target $a_{m}$ . When one cover set is obtained, we calculate the lifetime of the current cover set, which is the minimum lifetime of sensors in the cover set, and then update the lifetime of sensors in the cover set. If the sensors’ lifetime is zero after being updated, then the sensors cannot work. Then, we keep on selecting directions to construct cover sets until the rest of sensors cannot satisfy the coverage quality requirements of targets. The lifetime of sensor network is the accumulation of the lifetime of all cover sets. Algorithm 2 describes the details of HMCS.

Algorithm 2 HMCS
Require: sensor set $S = {s_{1}, s_{2}, \dots, s_{N}}$ , target set $A = {a_{1}, a_{2}, \dots, a_{M}}$ , sensing radius $R$ , sensing angle $α$ , and coordinate function $xy (node)$ Ensure: cover sets $C_{k}$ , $k = 1, 2, \dots, K$ and total lifetime $TL$ 1: get direction set $D = {D_{1}, D_{2}, \dots, D_{N}}$ by running Algorithm 1 2: for $i = 1$ to $N$ do 3: $T_{i} = L_{i}$ 4: end for 5: $k = 0$ , $TL = 0$ 6: $U_{i, m}$ is initialized to the coverage quality that sensor $s_{i}$ can provide to $a_{m}$ 7: $U_{i, j, m}$ is initialized to the coverage quality that direction $d_{i, j}$ can provide to $a_{m}$ 8: while $\sum_{s_{i} \in S_{m}} U_{i, m} \geq g (a_{m})$ for every target $a_{m}$ , $1 \leq m \leq M$ do 9: $k = k + 1$ 10: $C_{k} = \emptyset$ , $D_{c} = D$ 11: $g (a_{m})_{r}$ is initialized to the $g (a_{m})$ for every target $a_{m}$ 12: $V_{i, j, m}$ = min ${g (a_{m})_{r}, U_{i, j, m}}$ , $1 \leq i \leq N$ , $1 \leq j \leq c_{i}$ , $1 \leq m \leq M$ 13: calculate $V_{i, j}$ = $\sum_{m = 1}^{M} V_{i, j, m}$ 14: while $\sum_{m = 1}^{M} g (a_{m})_{r} \neq 0$ do 15: sort directions in $D_{c}$ in the descending order according to the number of available lifetime. if some directions have the same available lifetime, give priority to the direction with the maximal value of $V_{i, j}$ 16: choose the first direction $d_{i^{'}, j^{'}}$ from the set 17: $C_{k} = C_{k} \cup {d_{i^{'}, j^{'}}}$ 18: for all $a_{m} \in {a_{m} \| V_{i^{'}, j^{'}, m} > 0}$ do 19: $g (a_{m})_{r} = g (a_{m})_{r} - V_{i^{'}, j^{'}, m}$ 20: for all $d_{i, j} \in {d_{i, j} \| V_{i, j, m} > 0}$ do 21: $V_{i, j, m}$ = min ${g (a_{m})_{r}, V_{i, j, m}}$ 22: end for 23: end for 24: $D_{c} = D_{c} - {d_{i, j} \| i = i^{'}}$ 25: recalculate $V_{i, j}$ = $\sum_{m = 1}^{M} V_{i, j, m}$ 26: end while 27: set the lifetime $t_{k}$ of $C_{k}$ with the minimum lifetime of $d_{i, j}$ in $C_{k}$ , $TL = TL + t_{k}$ 28: for all $d_{i, j} \in C_{k}$ do 29: $T_{i} = T_{i} - t_{k}$ 30: if $T_{i}$ is equal to 0 then 31: $D = D - {d_{i, j} \| j = 1, 2, \dots, c_{i}}$ 32: end if 33: end for 34: end while 35: return $C_{1}, C_{2}, \dots, C_{K}$ and TL

Algorithm 2 HMCS

Require: sensor set

S = {s_{1}, s_{2}, \dots, s_{N}}

, target set

A = {a_{1}, a_{2}, \dots, a_{M}}

, sensing radius

R

, sensing angle

α

, and coordinate function

xy (node)

Ensure: cover sets

C_{k}

k = 1, 2, \dots, K

and total lifetime

TL

1: get direction set

D = {D_{1}, D_{2}, \dots, D_{N}}

by running Algorithm 1 2: for

i = 1

N

do 3:

T_{i} = L_{i}

4: end for 5:

k = 0

TL = 0

U_{i, m}

is initialized to the coverage quality that sensor

s_{i}

can provide to

a_{m}

U_{i, j, m}

is initialized to the coverage quality that direction

d_{i, j}

can provide to

a_{m}

8: while

\sum_{s_{i} \in S_{m}} U_{i, m} \geq g (a_{m})

for every target

a_{m}

1 \leq m \leq M

do 9:

k = k + 1

10:

C_{k} = \emptyset

D_{c} = D

11:

g (a_{m})_{r}

is initialized to the

g (a_{m})

for every target

a_{m}

12:

V_{i, j, m}

= min

{g (a_{m})_{r}, U_{i, j, m}}

1 \leq i \leq N

1 \leq j \leq c_{i}

1 \leq m \leq M

13: calculate

V_{i, j}

\sum_{m = 1}^{M} V_{i, j, m}

14: while

\sum_{m = 1}^{M} g (a_{m})_{r} \neq 0

do 15: sort directions in

D_{c}

in the descending order according to the number of available lifetime. if some directions have the same available lifetime, give priority to the direction with the maximal value of

V_{i, j}

16: choose the first direction

d_{i^{'}, j^{'}}

from the set 17:

C_{k} = C_{k} \cup {d_{i^{'}, j^{'}}}

18: for all

a_{m} \in {a_{m} | V_{i^{'}, j^{'}, m} > 0}

do 19:

g (a_{m})_{r} = g (a_{m})_{r} - V_{i^{'}, j^{'}, m}

20: for all

d_{i, j} \in {d_{i, j} | V_{i, j, m} > 0}

do 21:

V_{i, j, m}

= min

{g (a_{m})_{r}, V_{i, j, m}}

22: end for 23: end for 24:

D_{c} = D_{c} - {d_{i, j} | i = i^{'}}

25: recalculate

V_{i, j}

\sum_{m = 1}^{M} V_{i, j, m}

26: end while 27: set the lifetime

t_{k}

C_{k}

with the minimum lifetime of

d_{i, j}

C_{k}

TL = TL + t_{k}

28: for all

d_{i, j} \in C_{k}

do 29:

T_{i} = T_{i} - t_{k}

30: if

T_{i}

is equal to 0 then 31:

D = D - {d_{i, j} | j = 1, 2, \dots, c_{i}}

32: end if 33: end for 34: end while 35: return

C_{1}, C_{2}, \dots, C_{K}

and TL

Now, we show an example of constructing cover sets and calculating the network lifetime. In Figure 3(a), there are three targets ( $a_{1}, a_{2}, a_{3}$ ) covered by three directional sensors ( $s_{1}, s_{2}, s_{3}$ ). The sensing angle of sensors is $α$ = 90°, and the lifetime of the three sensors is 4, 6, and 8, respectively, that is, $T_{1} = 4$ , $T_{2}$ = 6, and $T_{3}$ = 8. The coverage relationships between sensors and targets are also illustrated in Figure 3(b). The value labeled on every target is coverage quality requirement of the target, that is, $g (a_{1})$ = 0.62, $g (a_{2})$ = 0.3, and $g (a_{3})$ = 0.32. The value labeled on each edge between the sensor and the target is the coverage quality that the sensor can provide to the target, that is, $U_{1, 1}$ = 0.78, $U_{1, 2}$ = 0.42; $U_{2, 1}$ = 0.66, $U_{2, 2}$ = 0.39, $U_{2, 3}$ = 0.5; and $U_{3, 3}$ = 0.34. The cover sets are constructed as follows.

1. According to Algorithm 1, we get the direction set $D = {D_{1}, D_{2}, D_{3}}$ , where $D_{i}$ is the direction set of sensor $s_{i}$ , $i = 1, 2, 3$ . $D_{1} = {d_{1, 1}, d_{1, 2}}$ , where $d_{1, 1} = {a_{1}, a_{2}}$ , $d_{1, 2} = {a_{2}}$ ; $D_{2} = {d_{2, 1}, d_{2, 2}, d_{2, 3}}$ , where $d_{2, 1} = {a_{3}}$ , $d_{2, 2} = {a_{2}, a_{1}}$ , $d_{2, 3} = {a_{1}}$ ; and $D_{3} = {d_{3, 1}}$ , where $d_{3, 1} = {a_{3}}$

We can obtain the coverage quality that every direction of sensors provide to every target from Figure 3(b): $U_{1, 1, 1}$ = 0.78, $U_{1, 1, 2}$ = 0.42, $U_{1, 2, 2}$ = 0.42; $U_{2, 1, 3}$ = 0.5, $U_{2, 2, 2}$ = 0.39, $U_{2, 2, 1}$ = 0.66, $U_{2, 3, 1}$ = 0.66; and $U_{3, 1, 3}$ = 0.34. Then, we initialize the remainder coverage quality of targets: $g (a_{1})_{r}$ = 0.62, $g (a_{2})_{r}$ = 0.3, and $g (a_{3})_{r}$ = 0.32.

Since $U_{1, 1}$ + $U_{2, 1}$ ≥ $g (a_{1})$ , $U_{1, 2}$ + $U_{2, 2}$ ≥ $g (a_{2})$ , and $U_{2, 3}$ + $U_{3, 3}$ ≥ $g (a_{3})$ , that is, for each target, the total coverage quality sensors can provide to every target is more than the coverage quality requirement of the target, so cover sets exist.

Based on $V_{i, j, m} = \min {g (a_{m})_{r}, U_{i, j, m}}$ , we compute the actual coverage quality that every direction of sensors provide to every target: $V_{1, 1, 1}$ = 0.62, $V_{1, 1, 2}$ = 0.3, $V_{1, 2, 2}$ = 0.3; $V_{2, 1, 3}$ = 0.32, $V_{2, 2, 2}$ = 0.3, $V_{2, 2, 1}$ = 0.62, $V_{2, 3, 1}$ = 0.62; and $V_{3, 1, 3}$ = 0.32. According to $V_{i, j}$ = $\sum_{m = 1}^{3} V_{i, j, m}$ , we obtain the actual coverage quality that every direction of sensors provide to the targets in this direction: $V_{1, 1}$ = 0.62 + 0.3 = 0.92, $V_{1, 2}$ = 0.3; $V_{2, 1}$ = 0.32, $V_{2, 2}$ = 0.3 + 0.62 = 0.92, $V_{2, 3}$ = 0.62; and $V_{3, 1}$ = 0.32.

Every time, we select the direction with the maximum available lifetime. If some directions have the same available lifetime, we select the direction with the maximal value of total actual coverage quality. So, the direction $d_{3, 1}$ is chosen into the first cover set $C_{1}$ , and sensor $s_{3}$ cannot be used in the subsequent construction of $C_{1}$ . We update $g (a_{3})_{r}$ = 0; $V_{2, 1, 3}$ = 0, $V_{2, 1}$ = 0; then, we select $d_{2, 2}$ into $C_{1}$ , and update $g (a_{2})_{r}$ = 0, $g (a_{1})_{r}$ = 0; $V_{1, 1, 1}$ = 0, $V_{1, 1, 2}$ = 0, $V_{1, 2, 2}$ = 0; and $V_{1, 1}$ = 0, $V_{1, 2}$ = 0. Since $g (a_{1})_{r}$ + $g (a_{2})_{r}$ + $g (a_{3})_{r}$ = 0, the construction of $C_{1}$ is finished, $C_{1} = {d_{3, 1}, d_{2, 2}}$ , and the lifetime of $C_{1}$ is $t_{1}$ = 6. We update the lifetime of sensors: $T_{1}$ = 4, $T_{2}$ = 0, and $T_{3}$ = 2. The lifetime of sensor $s_{2}$ is 0, so $s_{2}$ cannot work.

2. We get the direction set $D = {D_{1}, D_{3}}$ . Repeat the above process; we can finish the construction of cover set $C_{2} = {d_{1, 1}, d_{3, 1}}$ , and the lifetime of $C_{2}$ is $t_{2}$ = 2. We update the lifetime of sensors: $T_{1}$ = 2 and $T_{3}$ = 0. The lifetime of sensor $s_{3}$ is 0, so $s_{3}$ cannot work. Sensor $s_{1}$ cannot satisfy the coverage quality requirements of targets. So, no cover sets exist, and the network lifetime is $TL = t_{1} + t_{2}$ = 8.

Figure 3.

An example of constructing cover sets and calculating the network lifetime. (a) There are three targets ${a_{1}, a_{2}, a_{3}}$ covered by three directional sensors ${s_{1}, s_{2}, s_{3}}$ . (b) The coverage relationships between sensors and targets.

Simulation results

In this section, we evaluate the performance of the heuristic algorithm HMCS through simulations. We first show the effect of network parameters (the number of sensors, the number of targets, sensing range, sensing angle, and coverage quality of targets) on the network lifetime and simultaneously compare our algorithm with the upper bound of the optimal solution for the MCS problem aforementioned. Then, we evaluate the performance of our algorithm by comparing with the heuristic algorithm in Yang et al.¹⁵

All simulations are implemented via Visual Studio 2008 on Windows 7. We run 100 times through random placement of sensors and targets in each simulation and compute its average value.

Effect of network parameters

In our simulations, we deploy $N$ sensors with sensing radius $R$ and sensing angle $α$ and $M$ targets with differentiated coverage quality requirements randomly in a region of 500 m × 500 m area. Through changing one of the five parameters above, we evaluate their impact on the network lifetime, respectively, and simultaneously compare our algorithm with the upper bound of the optimal solution for the MCS problem. The lifetime of each sensor is initialized between 1 and 10.

Case 1. Number of sensors

In this section, we vary the number of sensors $N$ and compare the network lifetime of HMCS algorithm and the upper bound in the following three cases: $(1)$ $M = 120$ , $R = 100$ ; $(2)$ $M = 80$ , $R = 100$ ; and $(3)$ $M = 80$ , $R = 115$ . We fix $α$ = 90∘ as default value. The number of sensors increases from 200 to 400 with an increment of 50. The coverage quality of targets is randomly and uniformly chosen within $(0, 1]$ . Figure 4 shows the relationship between the network lifetime and the number of sensors. The network lifetime increases almost linearly when the number of sensors increases, because targets can be covered by more sensors as the number of sensors increases.

Figure 4.

Network lifetime versus the number of sensors.

Case 2. Number of targets

In this section, we evaluate the impact of the number of targets $M$ on HMCS algorithm and the upper bound in the following three cases: $(1)$ $N = 250$ , $R = 100$ ; $(2)$ $N = 300$ , $R = 100$ ; and $(3)$ $N = 300$ , $R = 115$ . We set $α$ = 90° as default value and vary the number of targets from 40 to 120 with an increment of 20. The coverage quality of targets is randomly and uniformly chosen within $(0, 1]$ . Figure 5 shows that the network lifetime drops as the number of targets increases, which is consistent with the actual situation because more targets with different coverage quality requirements are needed to be covered by sensors.

Figure 5.

Network lifetime versus the number of targets.

Case 3. Sensing radius

In this section, we change the sensing radius $R$ and compare the network lifetime of HMCS algorithm and the upper bound in the following three cases: $(1)$ $N = 300$ , $M = 120$ ; $(2)$ $N = 300$ , $M = 80$ ; and $(3)$ $N = 350$ , $M = 80$ . We set $α$ = 90° as default value and change the sensing radius of each sensor from 70 to 130 with an increment of 15. As the sensing radius increases, sensors can cover more targets. Figure 6 shows the relationship between the network lifetime and the sensing radius, which also increases almost linearly when sensing radius increases.

Figure 6.

Network lifetime versus sensing radius.

Case 4. Sensing angle

In this section, we test the impact of the sensing angle $α$ on HMCS algorithm and the upper bound in the following four cases: $(1)$ $N = 300$ , $M = 120$ , $R = 100$ ; $(2)$ $N = 300$ , $M = 80$ , $R = 100$ ; $(3)$ $N = 350$ , $M = 80$ , $R = 100$ ; and $(4)$ $N = 300$ , $M = 80$ , $R = 130$ . We increase the sensing angle from 70 to 110 with an increment of 10. The coverage quality of targets is randomly and uniformly chosen within $(0, 1]$ . Figure 7 presents the network lifetime which shows no big change as sensing angle increases in the given range. It is because the number of directions of each sensor is certain after the deployment of sensors and targets, which is decided by the number of targets in sensing circle of the sensor according to Algorithm 1.

Figure 7.

Network lifetime versus sensing angle.

Case 5. Coverage quality of targets

In this section, we change the coverage quality of targets and compare the network lifetime of HMCS algorithm and the upper bound in the following four cases: $(1)$ $N = 300$ , $M = 120$ , $R = 100$ ; $(2)$ $N = 300$ , $M = 80$ , $R = 100$ ; $(3)$ $N = 350$ , $M = 80$ , $R = 100$ ; and $(4)$ $N = 300$ , $M = 80$ , $R = 130$ . We set $α$ = 90° as default value and increase the coverage quality of targets from 0.6 to 1.0 with an increment of 0.1. Figure 8 shows that the network lifetime drops as the coverage quality of targets increases. It is because the targets with higher coverage quality need to be covered by more sensors to satisfy their coverage quality requirements.

Figure 8.

Network lifetime versus coverage quality of targets.

Comparison with MNLS-H-T

Among those existing literature, Yang et al.¹⁵ is the most relevant to our work. They employ the sub-tunable directional sensor model, that is, each sensor has finite separate and fixed work directions, to study the MNLS problem where the coverage quality requirements of targets are different. They design two heuristic algorithms named MNLS-H and MNLS-H-T, respectively, and their experimental results clearly demonstrate that the algorithm MNLS-H-T has better performance than MNLS-H. So, we evaluate our algorithm by comparing with MNLS-H-T. In the following simulations, we deploy randomly $N$ sensors and $M$ targets in a region of 500 m × 500 m area, and set $ω = 4$ ¹⁵ and $α$ = 90° to guarantee the sensing angles in the two-directional sensor models are the same.

We compare the network lifetime of our algorithm HMCS and the algorithm MNLS-H-T in the following four cases: $(1)$ $M = 80$ , $R = 100$ , and the number of sensors increases from 200 to 400 with an increment of 50. The coverage quality of targets is randomly and uniformly chosen within $(0, 1]$ ; $(2)$ $N = 300$ , $R = 100$ , and the number of targets varies from 40 to 120 with an increment of 20. The coverage quality of targets is randomly and uniformly chosen within $(0, 1]$ ; $(3)$ $N = 300$ , $M = 80$ , and the sensing radius of each sensor changes from 70 to 130 with an increment of 15. The coverage quality of targets is randomly and uniformly chosen within $(0, 1]$ ; and $(4)$ $N = 300$ , $M = 80$ , $R = 100$ , and the coverage quality of targets increases from 0.6 to 1.0 with an increment of 0.1. Figures 9 –12 present the performance of our algorithm HMCS compared with the algorithm MNLS-H-T changing with the number of sensors, the number of targets, sensing radius, and coverage quality of targets, respectively. The simulation results illustrate that the performance of our algorithm is better than MNLS-H-T. This is because the directional sensors in our model could rotate freely, so the sensors have chance to cover more targets. Beyond that, we make improvements when selecting directions from the candidate set of directions to construct cover sets in our heuristic algorithm.

Figure 9.

HMCS versus MNLS-H-T: network lifetime changing with the number of sensors.

Figure 10.

HMCS versus MNLS-H-T: network lifetime changing with the number of targets.

Figure 11.

HMCS versus MNLS-H-T: network lifetime changing with sensing radius.

Figure 12.

HMCS versus MNLS-H-T: network lifetime changing with quality coverage of targets.

Conclusion

In this article, we investigated the target coverage problem in directional sensor network with the objective to maximize the network lifetime satisfying targets’ coverage quality requirements, where directional sensors can rotate freely around their centers and targets are associated with different coverage quality requirements. We studied the intrinsic relationship between the work directions of the sensors and the targets deployed within the sensing region of the sensors, and proposed the SDP algorithm to eliminate the redundant directions and found all non-redundant directions for each sensor, which leads to significant dimension reduction. Based on that, we proposed a heuristic algorithm HMCS to solve the target coverage problem. In simulations, we compared our algorithm with the upper bound of the optimal solution and the algorithm MNLS-H-T in Yang et al.,¹⁵ and evaluated the effect of several network parameters on the lifetime of sensor network. The simulation results showed the efficiency of our algorithm.

As a future work, we plan to consider the two-directional characteristic: the sensor nodes’ sensing and the communicating, and design distributed algorithms to prolong the lifetime of directional sensor network.

Footnotes

Academic Editor: Stefano Avallone

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was partly supported by the National Natural Science Foundation of China (grant no. 11671400) and the Research Funds of Central China Normal University (2016CXZZ159).

References

Akyildiz

Sankarasubramaniam

. Wireless sensor networks: a survey. Comput Netw 2002; 38(4): 393–422.

Tian

Georganas

. A coverage-preserving node scheduling scheme for large wireless sensor network. In: Proceedings of the 1st ACM international workshop on wireless sensor networks and applications, Atlanta, GA, 28 September 2002, pp.32–41. New York: ACM.

Wang

Xing

Zhang

. Integrated coverage and connectivity configuration in wireless sensor networks. In: Proceedings of the 1st international conference on embedded networked sensor systems, Los Angeles, CA, 5–7 November 2003, pp.28–39. New York: ACM.

Jiang

Dou

. A coverage preserving density control algorithm for wireless sensor networks. In: Proceedings of the 3rd international conference on ad-hoc, mobile, and wireless networks (ADHOC-NOW), Vancouver, BC, Canada, 22–24 July 2004, pp.42–45. Berlin: Springer.

Zhang

Hou

JC.

Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sens Wirel Ne 2005; 1: 89–124.

Gallais

Carle

Simplot-Ryl

. Localized sensor area coverage with low communication overhead. IEEE T Mob Comput 2008; 7(5): 661–672.

Wang

Cao

. On full-view coverage in camera sensor networks. In: Proceedings of IEEE conference on computer communications (INFOCOM 2011), Shanghai, China, 10–15 April 2011, pp.1781–1789. New York: IEEE.

Shin

D-H

Zhang

Full-view area coverage in camera sensor networks: dimension reduction and near-optimal solutions. IEEE T Veh Technol 2016; 65(9): 7448–7461.

Slijepcevic

Potkonjak

. Power efficient organization of wireless sensor networks. In: Proceedings of IEEE international conference on communications, Helsinki, 11–14 June 2001, pp.472–476. New York: IEEE.

10.

Cardei

D-Z.

Improving wireless sensor network lifetime through power aware organization. Wirel Netw 2005; 11(3): 333–340.

11.

Diop

Diongue

Thiare

. A weight-based greedy algorithm for target coverage problem in wireless sensor networks. In: Proceedings of IEEE international conference on computer, communication and control technology (I4CT 2014), Kedah, Malaysia, 2–4 September 2014, pp.120–125. New York: IEEE.

12.

Cardei

Thai

. Energy-efficient target coverage in wireless sensor networks. In: Proceedings of the 24th annual joint conference of the IEEE computer and communications societies, Miami, FL, 13–17 March 2005, pp.1976–1984. New York: IEEE.

13.

Liu

. Target Q-coverage problem with bounded service delay in directional sensor networks. Int J Distrib Sens Netw 2012; 2012: 1–10.

14.

Cai

Lou

. Target-oriented scheduling in directional sensor networks. In: Proceedings of the 26th IEEE international conference on computer communications, Anchorage, AK, 6–12 May 2007, pp.1550–1558. New York: IEEE.

15.

Yang

Chen

. Coverage quality based target-oriented scheduling in directional sensor networks. In: Proceedings of the IEEE international conference on communications, Cape Town, South Africa, 23–27 May 2010, pp.1–5. New York: IEEE.

16.

Abouzeid

AA.

Coverage by directional sensors in randomly deployed wireless sensor networks. J Comb Optim 2006; 11(1): 21–41.

17.

. Approximation algorithms for maximum target coverage in directional sensor networks. In: Proceedings of IEEE the 11th international conference on networking, sensing and control (ICNSC 2014), Miami, FL, 7–9 April 2014, pp.155–160. New York: IEEE.

18.

Zhang

Chen

. Toward optimal orientation scheduling for full-view coverage in camera sensor networks. In: Proceedings of IEEE global communications conference (GLOBECOM 2016), Washington, DC, 4–8 December 2016.

19.

Wang

Niu

Shen

Priority-based target coverage in directional sensor networks using a genetic algorithm. Comput Math Appl 2009; 57(11–12): 1915–1922.

20.

Cardei

. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In: Proceedings of IEEE international conference on wireless and mobile computing, networking and communications (WiMob 2005), Montreal, QC, Canada, 12–14 August 2005, pp.438–445. New York: IEEE.

21.

Cerulli

De Donato

Raiconi

Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges. Eur J Oper Res 2012; 220(1): 58–66.

22.

Arivudainambi

Sreekanth

Balaji

Energy efficient sensor scheduling for target coverage in wireless sensor network. In: Zeng

(ed.) Wireless communications, networking and applications (Lecture Notes in Electrical Engineering, vol. 348). New Delhi, India: Springer, 2016, pp.693–705.

23.

Luo

Kim

. Imperfection better than perfection: beyond optimal lifetime barrier coverage in wireless sensor networks. In: Proceedings of the 10th international conference on mobile ad-hoc and sensor networks (MSN 2014), Maui, HI, 19–21 December 2014, pp.24–29. New York: IEEE.

24.

Tao

T-Y.

A survey on barrier coverage problem in directional sensor networks. IEEE Sens J 2015; 15(2): 876–885.

25.

Yang

Teng

. Local face-view barrier coverage in camera sensor networks. In: Proceedings of IEEE conference on computer communications (INFOCOM 2015), Hong Kong, China, 26 April–1 May 2015, pp.684–692. New York: IEEE.

26.

Meguerdichian

Koushanfar

Potkonjak

. Coverage problems in wireless ad-hoc sensor networks. In: Proceedings of IEEE international conference on computer communications, Anchorage, AK, 22–26 April 2001, pp.1380–1387. New York: IEEE.

Sensor scheduling for target coverage in directional sensor networks

Abstract

Keywords

Introduction

Related works

Sensor network model and problem description

Model and problem

Upper bound of network lifetime

Integer programming formulation for MCS problem

Algorithm for MCS problem

SDP

HMCS

Simulation results

Effect of network parameters

Case 1. Number of sensors

Case 2. Number of targets

Case 3. Sensing radius

Case 4. Sensing angle

Case 5. Coverage quality of targets

Comparison with MNLS-H-T

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References