无线传感器网络中基于动态规划的节点高效部署算法

Efficient node deployment algorithm based on dynamic programming in wireless sensor networks

针对传感器提供的信息不可靠导致的节点部署问题,研究了4种不同的静态无线传感器网络(WSN)部署形式,并将这4个组合优化问题归纳为NP完全问题,提出了一种基于动态规划的不确定性感知节点部署算法进行求解。算法首先为感兴趣区域内的传感器节点找到其最佳的K个部署位置,然后从K个部署位置中选择最优部署方案。该算法能够在保证覆盖范围和连接性的前提下确定最小数量的传感器及其位置。仿真实验结果表明,相对于当前最新的其他传感器部署策略,所提算法在均匀覆盖、优先覆盖要求以及网络连接性下的性能都更优。

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.