You are here

Maximizing network lifetime problem with connectivity constraint


In the maximum network lifetime problem with connectivity constraint (CMLP) a set of sensors randomly placed is used to cover a set of discrete targets. When a sensor is  active, it is able to cover all the targets that are placed within a maximum distance Rs, namely sensing range. Additionally, it is able to establish a wireless communication  link with the sensors (or the base station) that are placed at a  maximum distance Rc (communication range).  A base station is used to collect the information retrieved by the sensors. Then each active sensor must be able to send the information to the base station by using a direct link or a multihop path of active sensors. 

In order to monitor the targets for a long time, more sensors than actually needed are deployed. In this way,  the coverage of the targets can be reached by using subsets of these sensors that satisfy the coverage and connectivity requirements. Then network lifetime can be extended by activating sequentially the subsets and allocate them time intervals during which they will be used respecting the battery capacities of the sensors.

Furthermore, when the full coverage of the targets is not strictly necessary, lifetime can be extended by neglecting some of them. In this way it is possible to avoid that critical targets, those that are scarcely covered, became the bottleneck blocking the enlargement of network lifetime. Such variant of the problem where the quality of service is taken into account at a rate α is named (α-CMLP).

Moreover, from a technical point of view, battery consumption is not the same when a sensor is monitoring its environment or is simply communicating with other sensors to relay digital information. Such variant of the problem where different energy consumption rates occurs is known as multi-role (CMLP-MR)

Finally, a combination of the last two variants is combined in a more elaborated problem names α-CMLP-MR.


In order to generate the instances, it is assumed that sensors, base station and  targets are randomly deployed in a 500x500 square area.  A group of five sets of instances with |S| ={100, 200, 300, 400, 500} sensors is used. Two sets of targets |T|={15, 30} and one randomly located base station are also given for each instance. The sensors are assumed to be identical with the same initial battery lifetime normalized to one (b=1). Four instances are generated for each combination of the previous parameters. Finally, variations on the ratio between sensing and communication ranges are considered.  For all the experiments, the communication range is Rc=125, the sensing range Rs is the set {100, 125}.

  • CMLP instances can be downloaded in the file WSN_INSTANCES_CMLP.ZIP
  • Two levels of energy consumption rate for sensors used as a relay are considered Er ={0.8, 1.0}
    CMLP-MR instances can be downloaded in the file WSN_INSTANCES_CMLP_MR.ZIP
  • Three levels of coverage are considered alpha={0.7, 0.85, 1.0} with only one level of energy consumption rate Er = 0.8
    α-CMLP-MR instances can be downloaded in the file WSN_INSTANCES_a_CMLP_MR.ZIP