You are here

Trade-Off between Lifetime and cover Breach under bandwidth constraint


The TOLB problem is a bi-objective optimization problem in which we have to build and schedule groups of active sensors (covers) so as to maximize the total lifetime of the network and to minimize the total breach, under 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 type of resuts that we can obtain are presented in our paper cited below. But a figure is more explicit than many word. Below trade-offs between lifetime and coverage for an instance with n = 200, m = 120, and W = 5.

TOLB example


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. 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 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 = {}