Polynomial Algorithm for Node Deployment in Hybrid Wireless Sensor Networks

When detecting a target or monitoring a physical phenomenon in a region, the deployment problem is fundamental in these applications. Traditionally, stationary sensor networks are deployed to carry out the sensing operations. It is well known that the mobility of sensor nodes can improve the coverage and the probability of the detecting, so we deal with the problem of detecting a target using hybrid sensor networks which contain both stationary sensors and mobile sensors. In this paper, to begin with, we prove that the node deployment problem is NP-complete. Then, one polynomial algorithm for node deployment in hybrid wireless sensor networks is proposed, which aims at minimizing the number of all sensors to reduce the cost. The simulations verify the efficiency of our algorithm.