Phase Transition Analysis of Target Coverage Problem in Wireless Sensor Networks

Hardness analysis of combinatorial problems is an important AI-based study of intractable problems. As a domain parameter is made to vary, the hard instances of the problem cluster around a critical value. Thus, there is a phase-transition like situation and the probability of solvability sharply rises from 0 to 1 (or 1 to 0) at the critical value. The aim of this paper is to examine phase-transition behavior of maximum lifetime target coverage problem in wireless sensor networks domain. In this paper, we show that as we vary the uniform sensing range of sensors, the number of hard instances of the problem sharply rises around a critical value independent of other parameters. To facilitate the hardness analysis, we devise a new and efficient algorithm to solve target coverage problem; this algorithm has the distinct ability of distinguishing hard problem instances. The empirical analysis of phase transition is carried out through extensive experimentation.