You are here

Maximizing network lifetime problem with Q-coverage constraint

Definition

This article deals with a generalization of the coverage problem mentioned above where different targets have different coverage requirements. This situation is more realistic when targets need to be covered by a larger number of sensors due to the high level of accuracy and fault tolerance required for monitoring such targets. Given m targets with known locations, a collection of strictly positive integers {q1 , q2 , . . . , qm } and n sensors randomly deployed in the vicinity of targets such that the sensor i has battery life bi , the Q-coverage problem consists in scheduling the activity of sensors in such a way that the network lifetime is maximized under the restriction that, during the entire lifetime, each target k is covered by at least qk sensors. Three different versions of the Q-coverage problem are considered here.

  • Basic Q-coverage problem. In the first version, it is assumed that a base station is located within the communication range of each sensor. The base station’s role is to control the sensors as well as to collect the sensing information gathered by the sensors before sending it to the network manager.
  • Q-coverage problem with variable energy consumption. In the second version, it is assumed that the energy consumption of a sensor depends on the number of targets it covers. This version caters for sensor networks comprising this latter type of sensors and in all other respects is similar to the first version.
  • Q-coverage problem with base station connectivity constraints. In the third version of the problem, a communication range Rc is associated with each sensor so that it can directly communicate (i.e. send sensing data and receive control instructions from the base station) with any other sensor (or with the base station) located within its communication range. Moreover, indirect communication is also possible with the base station through a multi-hop path of active sensors. Consequently, a valid cover has to meet this additional constraints, which can be formulated as a connectivity requirement in an undirected graph of the sensors and the base station.

Instances

For the instances of the basic Q-coverage problem, it is assumed that all targets and sensors are randomly located in a 500 × 500 square area, coverage requirements of all targets are between 1 and 5, battery lifetimes of all sensors are between 5 and 10, and all sensors have a uniform sensing range of Rs = 150. The number of sensors n ∈ {50, 100, 150, 200, 500, 1000} and the number of targets m is either 60 or 30% of n. For each value of n, five random instances are generated with m = 0.6n. Instances with m = 0.3n are the same as instances with m = 0.6n, except for the fact that the last 0.3n targets are ignored. This leads to a total of 60 instances.

 For the Q-coverage problem with variable energy consumption, the same instances are used here with one additional condition that the lifetime of each sensor depends on the number of targets it covers.

For the Q-coverage problem with base station connectivity constraints, a 500 × 500 square area is also considered here in which all targets and sensors are located. As with the two previous versions, the coverage requirements of all targets are between 1 and 5 and the battery lifetimes of all sensors are between 5 and 10. The number of sensors n ∈ {250, 500, 1000, 750, 1500, 2000} and the number of targets m is set to 10% of n. Three different combinations of Rs and Rc have been considered here, viz. Rs = 50, Rc = 100; Rs = 50, Rc = 50; and Rs = 25, Rc = 25. For each of these three combinations of Rs and Rc , five instances are generated for each value of n. This leads to a total of 90 instances. Each of these instances is generated in the following manner: first, targets are placed randomly in the 500 × 500 area, and then enough sensors are placed randomly in the vicinity of each target to satisfy its Q-coverage requirement. If the resulting instance is not connected then its different components are connected in a random order by placing some new sensors in between. If not enough sensors are left to ensure connectivity then the instance generation is abandoned and the whole process starts afresh. If, after ensuring connectivity, some sensors are still left, then they are placed randomly in the 500 × 500 area. Base station is also placed randomly in the 500 × 500 area.

A set of instances is available for download in the file WSN_INSTANCES_QC.zip. Please note that the instance files do not contain the BR value since it can be set as indicated above. Instance names reflect the parameters as much as possible.

References

Best results published are achieved in our paper published in Engineering Optimization.
You can download it from the following link http://dx.doi.org/10.1080/0305215X.2012.687732

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

A. Singh, A. Rossi, and M. Sevaux. Matheuristic approaches for Q-coverage problem versions in wireless sensor networks. Engineering Optimization, 2013, available on-line. <http://dx.doi.org/10.1080/0305215X.2012.687732>

@article{singh.rossi.ea:2013,
  author = {A. Singh and A. Rossi and M. Sevaux},
  title = {Matheuristic approaches for {Q}-coverage problem versions in wireless sensor networks},
  journal = {Engineering Optimization},
  year = {2013},
  note = {Available on-line},
  url = {http://dx.doi.org/10.1080/0305215X.2012.687732}
}