Abstract:

Two cases are included in the minimum sensor deployment problems, according to whether the deployed network is desired connected or not. The nonconnected case is studied, to minimize the deployment cost. The proposed problem is formulated as an integer linear program problem, which is proved to be an NPcomplete problem. To approximately derive the optimal solution, the candidate deployment regions are theoretically derived and computed. A greedy algorithm is proposed, where one sensor is iteratively deployed into the maximal coverage number candidate region until all targets are covered. Compared with existing genetic algorithm and the optimal solution, simulation results confirm the effectiveness of the proposed algorithm.

Key words: wireless sensor networks, deployment algorithm, greedy algorithm, integer linear program