广西师范大学学报(自然科学版) ›› 2016, Vol. 34 ›› Issue (4): 19-25.doi: 10.16088/j.issn.1001-6600.2016.04.003

• 广西高校优秀中青年骨干教师培养工程论坛 • 上一篇    下一篇

传感器中基于连通支配集的区域覆盖控制算法

黄恒杰1,龚小龙2,王高才2   

  1. 1.玉林师范学院教育技术中心,广西玉林537000;
    2.广西大学计算机与电子信息学院,广西南宁530004
  • 出版日期:2016-07-18 发布日期:2018-07-18
  • 通讯作者: 王高才(1976—),男,广西灌阳人,广西大学教授,博士,博士生导师。 E-mail:wanggcgx@163.com
  • 基金资助:
    广西高等学校优秀中青年骨干教师培养工程资助项目;国家自然科学基金资助项目(61562006,61262003);广西自然科学杰出青年基金资助项目(2013GXNSFGA019006)

An Area Coverage Control Algorithm Based on Connected Dominating Set for Sensor Networks

HUANG Hengjie1, GONG Xiaolong2, WANG Gaocai2   

  1. 1. Educational Technology Center,Yulin Normal University,Yulin Guangxi 537000,China;
    2. School of Computer, Electronics and Information, Guangxi University, Nanning Guangxi 530004, China
  • Online:2016-07-18 Published:2018-07-18

摘要: 针对现有无线传感器网络区域覆盖控制算法很难在确保网络连通率的同时对网络覆盖率和能耗进行优化的问题,本文提出一种基于连通支配集的区域覆盖控制(area coverage control based on connected dominating set,ACCBCDS)算法。当节点随机分布于监测区域后,未连通的节点移向Sink节点直至网络实现全连通,之后利用三着色算法构建网络连通支配集,Sink节点对非连通支配节点进行集中式优化调整,让非连通支配节点移至更优位置。在优化调整的过程中同时考虑了网络连通率、覆盖率和节点移动距离。仿真结果表明,与典型的基于虚拟力的区域覆盖控制(area coverage control based on virtual forces,ACCBVF)算法相比较,本文提出的ACCBCDS算法能使网络在确保全连通的前提下获得更高覆盖率,并能减少网络覆盖控制中的移动能耗。

关键词: 传感器网络, 连通支配集, 覆盖率, 能耗

Abstract: To solve the problem that existing area coverage control algorithms for the mobile WSNs are difficult to ensure the network connectivity rate of the network coverage and energy consumption optimization, an area coverage control algorithm based on connected dominating set (ACCBCDS) algorithm is proposed for the mobile WSNs. When the nodes are randomly distributed in the monitoring area, nodes disconnected to the Sink node are required to move toward the Sink node until full network connectivity is achieved. Then the three-staining method is adopted to construct the network connected dominating set, after which the Sink node performs centralized optimization adjustment on dominated nodes, requiring dominated nodes to move toward better locations. During the adjustment, network coverage rate, connectivity rate and node movement distance are synthetically considered. Simulation results show that compared with typical area coverage control algorithm based on virtual forces (ACCBVF) algorithm, the proposed ACCBCDS can achieve higher network coverage rate under the premise of ensuring full network connectivity, and decrease node movement energy consumption during network coverage control.

Key words: sensors networks, connected dominating set, coverage rate, energy consumption

中图分类号: 

  • TP393
[1] 岳才杰, 陈元琰, 朱新华. 一种有效的传感器网络区域查询算法[J].广西师范大学学报(自然科学版),2015,33(1):52-58.
[2] ABOUELKHAIR O, ELSAADNY A. Multipath adaptive periodic threshold-sensitive energy efficient protocol for wireless sensor networks[C]//Proceedings of the 6th IEEE International Conference on Computational Intelligence, Communication Systems and Networks. New York:IEEE Press, 2015: 33-37.
[3] JIANG P, LIU J, WU F, et al. Node deployment algorithm for underwater sensor networks based on connected dominating set[J]. Sensors, 2016, 16(3):388. DOI:10.3390/s16030388.
[4] CARDEI M, DU D Z. Improving wireless sensor network lifetime through power aware organization[J]. Wireless Networks, 2005, 11(3): 333-340.
[5] SEN A, DAS N, MURTHY S. Coverage and connected coverage problems for sensors embedded in a temperature-sensitive environment[J]. International Journal of Sensor Networks, 2010, 7(2): 106-123.
[6] 林祝亮, 冯远静, 俞立. 无线传感网络覆盖的粒子进化优化策略研究[J]. 传感技术学报, 2009, 22(6): 873-877.
[7] JIANG P, LIU J, WU F. Node non-uniform deployment based on clustering algorithm for underwater sensor networks[J]. 2015, 15(12): 29997-30010.
[8] MEGUERDICHIAN S, KOUSHANFAR F, POTKONJAK M, et al. Coverage problems in wireless ad-hoc sensor networks[C]// Proceedings of the IEEE Conference on INFOCOM. New York: IEEE Press, 2001:1380-1387.
[9] SANTOSH K, TEN H, ANISH A. Barrier coverage with wireless sensors[J]. Wireless Networks, 2007, 13(6): 817-834.
[10] LIU B Y, DOUSSE O, WANG J, et al. Strong barrier coverage of wireless sensor networks[C]// Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York: ACM Press, 2010: 411-419.
[11] HUANG C F, TSENG Y C, LO L C. The coverage problem in three-dimensional wireless sensor networks[J]. Journal of Interconnection Networks, 2011, 8(3): 3182-3186.
[12] ZHANG H, HOU J. On deriving the upper bound of α-lifetime for large sensor networks[J]. ACM Transactions on Sensor Networks, 2005, 1(2): 272-300.
[13] DHILLON S S, CHAKRABARTY K. Sensor placement for effective coverage and surveillance in distributed sensor networks[C]// Proceedings of the Wireless Communications and Networking. New York: IEEE Press, 2003: 1609-1614.
[14] 李海坡,马向南. 无线传感器网络中基于连通支配集的覆盖控制算法[C]// 中国通信学会第六届学术年会论文集(下).北京:北京邮电大学出版社,2009:658-661.
[15] ZOU Y, CHAKRABARTY K. Sensor deployment and target localization based on virtual forces[C]// Proceedings of the 22th Annual Joint Conference of Computer and Communications. New York: IEEE Press, 2003: 1293-1303.
[1] 滕志军, 吕金玲, 郭力文, 许媛媛. 基于改进粒子群算法的无线传感器网络覆盖策略[J]. 广西师范大学学报(自然科学版), 2018, 36(3): 9-16.
[2] 肖发远,李好威. 基于模糊理论的无线传感器网络路由优化算法[J]. 广西师范大学学报(自然科学版), 2017, 35(1): 37-43.
[3] 江绍锋, 黄金清, 于晓宇, 李云飞, 陆祖军. 产酸克雷伯氏菌基因组文库的构建及鉴定[J]. 广西师范大学学报(自然科学版), 2016, 34(2): 151-157.
[4] 刘宏, 王其涛, 夏未君. 基于量子遗传算法的WSN三维定位方法[J]. 广西师范大学学报(自然科学版), 2015, 33(4): 49-54.
[5] 岳才杰, 陈元琰, 朱新华. 一种有效的传感器网络区域查询算法[J]. 广西师范大学学报(自然科学版), 2015, 33(1): 52-58.
[6] 窦贤振, 徐晨, 左杨. 基于能量优先的WSN最优梯度路由协议[J]. 广西师范大学学报(自然科学版), 2013, 31(3): 157-163.
[7] 郑磊, 朱正礼, 侯迎坤. 基于改进的微粒群算法的WSN节点部署策略[J]. 广西师范大学学报(自然科学版), 2011, 29(4): 56-62.
[8] 吴礻韦娴, 苏诚, 陈明, 冯国富, 池涛. 基于Agent的温室无线传感网络分簇管理模型[J]. 广西师范大学学报(自然科学版), 2011, 29(2): 210-214.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报(自然科学版)编辑部
地址:广西桂林市三里店育才路15号 邮编:541004
电话:0773-5857325 E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发