You are here

Maximizing network lifetime problem of sensors with adjustable sensing ranges

Definition

The ASR problem suppose that n sensors are randomly deployed in order to cover a set of m targets {τ1,…,τk,…,τm}. Each sensor si has an initial energy bi. Sensors can either be active or inactive. An inactive sensor does not cover any target, and its power consumption is negligible. When a sensor is active, its power consumption depends on its sensing range. All the sensors have the same maximum sensing range, denoted by Rmax: a sensor can cover a target if its distance is less than or equal to Rmax. Lifetime maximization is reached by gathering sensors into non-disjoint subsets called covers (each cover being such that each target can be covered by at least one sensor in that cover), and by scheduling these covers, i.e., by determining the amount of time during which each cover is used. The sensors that are not part of the cover that is currently being used are not active. Moreover, covers are not necessarily disjoint, as this allows for reaching longer lifetimes. The schedule must be such that the total amount of energy consumed by sensor si is at most equal to its initial energy bi. The network lifetime is the sum of these durations: when it is exceeded, the coverage of all targets is no longer possible.

Our work addresses two close versions of the lifetime maximization problem:

  • Lifetime Maximization with Ad-hoc Sensing Ranges (LM-ASR): Each sensor can adjust its sensing range so as to cover targets with the minimum amount of necessary power (for all targets which distance to the sensor is less than Rmax). In this model, continuous variations of the sensing range are allowed.
  • Lifetime Maximization with Predefined Sensing Ranges (LM-PSR): Sensors have MPSR nonzero and distinct predefined sensing ranges, so all the targets that are under such a predefined range are covered at a predefined power level. In this model, MPSR predefined sensing ranges are supposed to be given.

Instances

The instances that we have used in our computational experiments have been generated as follows. n sensors and m targets are generated at random in a 500x500 area. The maximum sensing range of sensors is set to Rmax=150. The instance name format is nXXXmYYY, where XXX is in [50, 100, 150, 200, 300, 600] and is the number of sensors, and YYY is in [15, 30, 45, 60, 90, 120, 180, 360] and is the number of targets. Five instances of the same size have been generated, leading to a grand total of 60 different instances. In addition to LM-ASR, LM-PSR is addressed for three different numbers of sensing ranges. In PSR1, sensors are either sensing up to their maximum range Rmax, or not used at all; this corresponds to the problem where sensing ranges are not adjustable. In PSR3, the three sensing ranges are {50, 100, 150} and in PSR6, the six considered sensing ranges are {25, 50, 75, 100, 125, 150}.

A set of instances is available for download in the file WSN_INSTANCES_ASR.zip

References

Best results published are achieved in our paper published in Computers & Operations Research.
You can download it from the follwing link http://dx.doi.org/10.1016/j.cor.2012.04.001.

Please cite our work using the following information or the BibTeX entry below.

A. Rossi, A. Singh, and M. Sevaux. An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges. Computers and Operations Research, 39(12):3166-3176, 2012.

@article{rossi.singh.ea:2012b,
  author = {A. Rossi and A. Singh and M. Sevaux},
  title = {An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges},
  journal = {Computers and Operations Research},
  year = {2012},
  volume = {39},
  number = {12},
  pages = {3166-3176},
  url = {http://dx.doi.org/10.1016/j.cor.2012.04.001}
}