Polyhedral Approach for Lifetime Maximization of Target Coverage Problem

MLTCP (Maximum Lifetime Target Coverage Problem) aims at providing required coverage to a set of targets maximizing the lifetime of wireless sensor network. The problem is known to be computationally hard and it is shown recently that MLTCP exhibits phase-transition phenomenon. The region of occurrences of hard instances is identified in terms of an interval of values of sensing-range. Most of the earlier heuristics report their empirical analyses on instances that are outside this region. There has not been any algorithm proposed so far to handle particularly hard instances. In the present work, we provide a new insight to MLTCP by studying the structure of polyhedral feasible set and propose a heuristic that distinguishes hard instances from solvable cases. The proposed method yields best-ever near-optimal solution and indicates situations when the given problem instance is hard. Considering the linear programming formulation of MLTCP, the algorithm can be viewed as traversal from one BFS (Basic Feasible Solution) to another nonadjacent BFS with non-decreasing value of the objective function. It is shown that high degree of degeneracy of BFS and cycling make the problem hard. When the algorithm encounters a non-trivial cycle, our method uses a novel way of generating an improved feasible solution (not a BFS) by moving away from BFS search. Experimental results confirm that the proposed method achieves the optimal solution for easy instances and gives best-ever near-optimal solution for hard instances.