###
Definition

In this work we address two versions of a lifetime maximization problem for target coverage with wireless directional sensor networks. The sensors used in these networks have a maximum sensing range and a limited sensing angle. In the first problem version, predefined sensing directions are assumed to be given, whereas sensing directions can be freely devised in the second problem version.

The main novelty is that directions are not defined a priori, but only once the network is deployed. This allows for building contextual directions: the directions of a sensor are built depending on the location of the targets that are within range. The problem of Lifetime Maximization with Predefined Sensing Directions is referred to as LM-PSD. The problem of both building the sets of Contextual Sensing Directions and maximizing network lifetime is referred to as LM-CSD.

All angles are expressed in radians and are in the interval [0, 2π). Let n and m be the number of sensors and targets, respectively. For all i ∈ {1, . . . , n}, sensor si can be used for bi units of time (in small bursts or continuously) before its battery is discharged. All sensors have the same sensing angle φ and sensing range Rs , which means that any target τk whose distance from si is less than or equal to Rs is covered by this sensor provided it is active, and that its sensing direction is such that τk can be seen from si . More precisely, let Di be the set of targets whose distance to sensor si is less than or equal to Rs . θk is the angle under which target τk is seen from si , for all k ∈ Di . When sensor si is used with sensing direction θ, it covers all the targets in Di whose angle is the interval [θ, θ + φ) if θ + φ < 2π. If θ + φ ≥ 2π, then sensor si covers all the targets in Di whose angle is larger than or equal to θ, as well as the targets whose angle is in the interval [0, θ + φ − 2π). More formally, Di,θ is the set of all the targets that are covered by sensor si under the sensing direction θ. A sensing direction θ of si is said to be normalized if there exists k ∈ Di such that θ = θk . Thus, the number of normalized sensing directions is at most |Di|. It can be less if two or more targets are seen under the same angle from si.

In the literature, the notion of groups (sometimes referred to as covers) has long been shown to be the most efficient way to address a wide variety of optimization problems in wireless sensor networks [17, 19]. In the case of directional sensors, a valid group is defined as a subset of sensors with a sensing direction for each of them, such that each target is covered by at least one sensor of that group. A group is not valid if the coverage requirement is not satisfied. LM-PDS and LM-CDS are to design valid groups and to compute the amount of time during which they are used so as to maximize the network lifetime, while enforcing that sensor si is used at most bi units of time, for all i in {1, . . . , n}. Thus, exactly one group is active at a time, the sensors that are not part of the active group are turned off (so that they do not consume energy) whereas all the sensors of the active group are active as they sense in the direction specified by the group for each of them. Consequently, a solution to LM-PDS or LM-CDS is a collection of groups with a duration. A feasible solution is composed of valid groups only, with durations that satisfy battery limitations for all sensors.

###
Solution

A partial solution of LM-CDS can be represented as below

In that figure, active sensors and their sensing ranges are clearly visible and cover the targets in red.

###
Instances

We have considered four different number of sensors in the network: n ∈ {50, 100, 200, 400}. The corresponding number of targets is m ∈ {30, 60, 120, 240}: thus we maintain the same ratio between n and m, which allows to measure the effect of the problem size. Indeed the relative variations of n and m are less relevant in this work: if the number of targets increases for a fixed n, the network lifetime can only decrease (the problem may also become unfeasible, especially for small sensing angles). If the number of targets gets sparse for a fixed n, then many sensors become useless as they do not cover any target, which leads to a smaller (and hence easier) problem instance with an even lower n/m ratio. The current ratio is 60%, which is reasonably large, given that in practice, the number of sensors is always larger than the number of targets [19]. Sensors and targets coordinates are generated randomly in a 500 × 500 area, and the sensing range is Rs = 150. In addition, we have considered three different sensing angles φ ∈ { 2π/3 , π/2 , π/3 }. They are given in decreasing order because the smaller the directional angle, the more difficult the problem is. A grand total of sixty instances have been addressed by generating five instances for all (n, φ) pair.

The set of instances is available for download in the file WSN_INSTANCES_DS.zip