计算机应用 ›› 2013, Vol. 33 ›› Issue (11): 3024-3027.

• 网络与通信 • 上一篇    下一篇

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

许秀兰,李克清,黄瑜岳   

  1. 常熟理工学院 计算机科学与工程学院,江苏 常熟 215500
  • 收稿日期:2013-05-13 修回日期:2013-07-12 出版日期:2013-11-01 发布日期:2013-12-04
  • 通讯作者: 许秀兰
  • 作者简介:许秀兰(1978-),女,江苏海安人,讲师,硕士,主要研究方向:无线传感器网络、算法优化;李克清(1966-),男,湖北荆门人,教授,博士,主要研究方向:无线传感器网络、网格计算、优化设计、信息安全;黄瑜岳(1978-),男,江苏常熟人,讲师,硕士,主要研究方向:生产调度、无线传感器网络、算法优化。
  • 基金资助:
    江苏省科技计划项目;常熟市工业攻关重点项目

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

XU Xiulan,LI Keqing,HUANG Yuyue   

  1. School of Computer Science and Engineering, Changshu Institute of Technology, Changshu Jiangsu 215500, China
  • Received:2013-05-13 Revised:2013-07-12 Online:2013-12-04 Published:2013-11-01
  • Contact: XU Xiulan

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

关键词: 无线传感器网络, 节点部署, 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

中图分类号: