You are here

Maximum Network Lifetime problem under Bandwidth constraint


In the MNLB problem, we have to build and schedule groups of active sensors (covers) so as to maximize the total lifetime of the network, under breach and bandwidth constraints. The network is composed of n identical sensors having an identical battery lifetime. Without loss of generality, the battery lifetime is normalized to one unit of time. A sensor s is said to cover a target if the distance to the target is less than or equal to its sensing range Rs . The number of targets is denoted by m, and Ck is the set of sensors covering target k for all k in {1, . . . , m}. A valid group (or cover) Sj is then a subset of sensors with cardinality less than or equal to W for all j in {1, . . . , p} (where p is the number of groups). These groups have to be scheduled, i.e., the duration of tj during which group Sj is active must be computed. It should be recalled that no two groups can be active at the same time, so exactly one group has to be active during the time interval [0, T], where T is the network lifetime to determine. The breach of a target is the total time during which it is not covered by any active sensor along the network lifetime. The breach constraint refers to the minimum coverage of the targets by the active sensors over the whole lifetime of the network. It is also called the breach rate (BR). BR = 0 means that all the targets are covered in the time interval [0, T]; BR = 1 means that no target is covered during the network lifetime. BR = 0.1 means that 90% of the targets are covered in the time interval [0, T].


Four classes of instances are considered: they are characterized by the number of sensors n and the number of targets m to be covered. Like in the litterature, it is assumed that all the sensors and targets are randomly located in a 500 ×500 square area. Each class is further divided into three subclasses corresponding to various bandwidth constraints: a group is restricted to being composed of up to W sensors, where W is equal to 5, 10, and n, respectively. The last subclass intends to show results with no bandwidth constraint at all. Solving MNLB requires setting a breach rate BR for the network. This value is set as BR=0 or BR=0.1 or BR=0.2. The sensing range Rs is uniformly assumed to be 150. Each class is composed of 30 instances, the subclasses differing only by the value of W.

A set of instances is available for download in the file 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.


Best results published are achieved in our paper published in Networks.
You can download it from the follwing link

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

A. Rossi, A. Singh, and M. Sevaux. Column generation algorithm for sensor coverage scheduling under bandwidth constraints. Networks, 60(3):141-154, 2012.

  author = {A. Rossi and A. Singh and M. Sevaux},
  title = {Column generation algorithm for sensor coverage scheduling Under bandwidth constraints},
  journal = {Networks},
  year = {2012},
  volume = {60},
  number = {3},
  pages = {141-154},
  url = {}