关键词: 无线传感器网络, 节点部署, NP完全问题, 动态规划, 节点数目

Abstract: To solve the node deployment problem caused by unreliable information provided by the sensors, four different forms of static Wireless Sensor Network (WSN) deployment were addressed. The four problems were formalized as combinatorial optimization problems, which were Non-deterministic Polynomial (NP)-complete. Furthermore, an uncertainty-aware deployment algorithm based on dynamic programming was proposed. Firstly, the K-best placements of sensor nodes within the region of interest were found, and then the best deployment scheme was selected over the K-best placements. The proposed algorithm was able to determine the minimum number of sensors and their locations to achieve both coverage and connectivity. The simulation results show that, compared with the state-of-the-art deployment strategies, the performance of the proposed algorithm is better than the existing methods in terms of the uniform coverage requirement, the preferential coverage requirement and the network connectivity.

Key words: Wireless Sensor Network (WSN), node deployment, Non-deterministic Polynomial (NP) complete problem, dynamic programming, number of nodes