You are here

Minimum Cover Breach problem with Bandwidth constraint


In the MCBB problem, we have to build and schedule groups of active sensors (covers) so as to minimize the total breach, under lifetime 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, T0], where T0 is the minimum network lifetime. The problem has a solution if and only if T0n, i.e., the maximum lifetime is achieved when each sensor is used alone for one unit of time. The breach of a target is the total time during which it is not covered by any active sensor along the network lifetime.


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 MCBB requires setting a minimum lifetime T0 for the network. This value is set as in the litterature, with the following formula: T0 = n/W rounding to the integer below. However, when there is no bandwidth constraint (W = n), T0 is set to n/10 . 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 file does not contain the T0 value since it can be computed from the formula 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 = {}