期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

非连通无线传感器网络的最少传感器节点部署 被引量：4

A Minimum Sensor Deployment Algorithm for Non-Connected Wireless Sensor Network
原文传递
导出
摘要 传感器节点的部署包括连通网络和非连通网络2种情况.为了最小化网络部署开销,对非连通网络的传感器节点部署问题进行了研究,建立了整数线性规划模型,并证明该问题为NP-complete问题.为找到该问题的近似最优解,通过理论分析确定了传感器节点的候选部署区域,提出了一种启发式的传感器节点贪婪部署算法,迭代地将传感器节点部署到覆盖目标点数最多的候选部署区域,直到覆盖所有目标点.通过仿真实验将所提出的贪婪部署算法和现有的遗传算法以及问题模型的最优解进行了比较,验证了算法的有效性. 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.
作者 闫中江 沈中 常义林 张颖 代亮
机构地区 西安电子科技大学综合业务网理论及关键技术国家重点实验室
出处 《北京邮电大学学报》 EI CAS CSCD 北大核心 2011年第5期15-18,24,共5页 Journal of Beijing University of Posts and Telecommunications
基金 高等学校学科创新引智计划项目(B08038) 国家自然科学基金项目(61172069) 陕西省自然科学基金项目(2011JM8029)
关键词 无线传感器网络 部署算法 贪婪算法 整数线性规划 wireless sensor networks deployment algorithm greedy algorithm integer linear program
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献8

  • 1Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey [ J ]. Computer Networks, 2008, 52 ( 12 ) : 2292-2330.
  • 2Xu X, Sahni S. Approximation algorithms for sensor de- ployment[ J]. IEEE Transactions on Mobile Computing, 2007, 56(12) : 1681-1695.
  • 3Lin F Y S, Chiu P L. A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks[J]. IEEE Comm Letters, 2005, 9(1) : 43-45.
  • 4刘巍,崔莉.基于蚁群算法的传感器网络节点部署设计[J].通信学报,2009,30(10):24-33. 被引量：13
  • 5Jourdan B, Weck 0 L. Layout optimization for a wireless sensor network using a multi-objective genetic algorithm [ C 1//J Proceeding of IEEE Vehicular Technology Confer-ence. Los Angeles: IEEE Press, 2004 : 2466-2470.
  • 6何欣,桂小林,安健.面向目标覆盖的无线传感器网络确定性部署方法[J].西安交通大学学报,2010,44(6):6-9. 被引量：28
  • 7Xu Y, Yao X. A GA approach to the optimal placement of sensors in wireless sensor networks with obstacles and preferences [ C ] JJ Proceedings of IEEE Conference on Consumer Communications and Networking (CCNC). Las Vegas: IEEE Press, 2006: 127-131.
  • 8Hochbaum D S. Approximation algorithms for the set cov- ering and vertex cover problems [ Jl. SIAM Journal on Computing, 1982, 11(3) : 555-556.

二级参考文献27

  • 1ZOU Y, CHAKRABARTY K. Sensor deployment and target localization based on virtual forces[A]. INFOCOM 2003[C]. NC, USA, 2003. 1293-1303.
  • 2PODURI S, SUKHATME G. Constrained coverage in mobile sensor networks[A]. IEEE International Conference on Robotics and Automation (ICRA)[C]. Los Angeles, CA, USA, 2004. 40-50.
  • 3KAR K, BANERJEE S. Node placement for connected coverage in sensor networks[A]. Proceedings of WiOpt[C]. INRIA Sophia- Antipolis, France, 2003.50-52.
  • 4ERDICHIAN M S, KOUSHANFAR F, QLJ G, et al. Exposure in wireless ad hoc sensor networks[A]. Proceeding of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom)[C]. Rome, Italy, 2001. 139-150.
  • 5VELTRI G, HUANG Q, QU G, et al. Minimal and maximal exposure path algorithm for wireless embedded sensor networks[A]. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys)[C]. Los Angeles, CA, USA, 2001.40 -50.
  • 6CHAKRABARTY K, IYENGAR S S. Grid coverage for surveillance and target location in distributed sensor networks[J]. IEEE Transactions on Computers, 2002, 51(5): 1448-1453.
  • 7KUMAR R, KUMAR V, TSIATSIS M. Computation hierarchy for in-network processing[A]. The 2nd ACM International Conference on Wireless Sensor Networks and Applications[C]. San Diego, CA, USA, 2003.68-77.
  • 8TOUMPIS S, TASSIULAS L. Optimal deployment of large wireless sensor networks[J]. IEEE Transactions on Information Theory, 2006, 52(7): 2935-2953.
  • 9YANG Y, SHUHUI Y, MINGLU L. Scan-based movement-assisted sensor deployment methods in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(8): 1108-1121.
  • 10DHILLON S S, CHAKRABARTY K, IVENGAR S S. Sensor placement for grid coverage under imprecise detections[A]. Proceedings of the Fifth International Conference on Information Fusion[C]. Durham, NC, USA, 2002. 1581-1587.

共引文献38

同被引文献28

  • 1Rodoplu V, Meng T H. Minimum energy mobile wireless networks [J]. IEEE Journal on Selected Areas in Com- munications, 1999, 17(8): 1333-1344.
  • 2Weber S, Andrews J G, Jindal N. An overview of the transmission capacity of wireless networks [ J ]. IEEE Transactions on Communications, 2010, 58 (12) : 3593- 3604.
  • 3Hu Junping, Jin Yuhui, Dou Liang. A time-based clus- ter-head selection algorithm for LEACH [ C ]// Chi-Ming Chen. Proceedings of the 13th IEEE Symposium on Com- puters and Communications. Marrakech: IEEE, 2008: 1172-1176.
  • 4张勇,滕颖蕾,宋梅,等.认知无线电与认知网络[M].北京:北京邮电大学出版社,2012.
  • 5XING G,WANG X,ZHANG Y,et al. Integrated coverage and connec- tivity configuration for energy conservation in sensor networks [ J ]. ACM Trans on Sensor Networks,2005,1 ( 1 ) :36-72.
  • 6XING Xiao-fei, WANG Guo-jun, WU Jie, et al. Square region-based coverage and connectivity probability model in wireless sensor net- works[ C]//Proc of the 5th International Conference on Cullaborative Computing. Washington DC : IEEE Computer Society ,2009.
  • 7YUN Li-qiu, BAI Xiao-le, XUAN Dung, et al. Pattern mutation in wireless sensor deployment[J]. [EEE/ACM Yrans on Networking, 2012,20(6) : 1964-1977.
  • 8YIU M L,MAMOULIS N. Aggregate nearest neighbor queries in road networks[ J]. IEEE Trans on Knowledge and Data Engineering, 2005,17(6) : 820-833.
  • 9CARDEI M, WU J. Energy-efficient coverage problems in wireless Ad hoc sensor networks [ J ]. Journal of Computer Communications on Sensor Networks, 2006,29(4) :413-420.
  • 10ANTHONY S, YE Y. On solving coverage problems in a wireless sen- sor network using voronoi diagrams[ C ]//Proc of the 1 st Work Shop on lnternet and Network Economics. 2005: 584-593.

引证文献4

二级引证文献29

北京邮电大学学报
2011年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部