A Lagrangean-based heuristics for the target covering problem in wireless sensor network

We study the target coverage problem in wireless sensor networks. The problem consists in maximizing the network lifetime by grouping the sensors in disjoint set covers of the targets. A binary integer programing model is formulated to maximize the network lifetime. Since the problem is NP-complete, we provide an iterative approximation based on Lagrangean relaxation and subgradient optimization.