基于节点近似圆的有向强栅栏构建算法

摘要/Abstract

摘要： 栅栏覆盖是有向传感器网络(DSN)覆盖控制的研究热点之一。为了在感知角度大于π时高效地构建栅栏,文中设计了有向节点的近似圆模型,提出了集中式栅栏构建HapC算法和分布式栅栏构建INSDBC算法。HapC算法把网络分成节点近似圆相连的子群,利用匈牙利算法选择最优节点连通这些子群,形成栅栏。为了进一步减少节点的数量,对基本栅栏的每个子群进行精简。INSDBC算法根据节点近似圆之间的几何关系,使每个节点具有最大的栅栏贡献,从左到右依次选择能耗最小的节点分布式构建栅栏。结果证明,这两种方法结合能够用较低能耗和较少节点构建有向强栅栏,对提升有向传感器网络的覆盖性能具有一定的理论与实际意义。

关键词: 近似圆, 能耗, 有向栅栏覆盖, 栅栏贡献

Abstract: Barrier coverage is one of the hot spots in directional wireless sensor network (DSN).In order to effectively form barrier when sensing angle is more than π,this paper designed the approximate circle model of directional nodes and proposed centralized heuristic barrier construction scheme based on approximate circle (HapC) and distributed improved barrier construction scheme based on next node sports (INSDBC) to construct directional strong barrier.In HapC,the whole network is divided into subgroup in which each approximate circle is connected,and the optimal mobile nodes are selected to connect these subgroups by Hungarian algorithm.To further decrease the number of barrier node,it reduces the staff node of sub-barrier.NSDBC maximizs the contribution of each nodes based on geometric relation of approximate circle.Moreover,it selects the node with minimum energy consumption to form barrier in turn from left to right.Simulation results show that this method can effectively constitute strong barrier coverage,and enhance the cove-rage performance of DSN.This research has a certain theoretical and practical significance for barrier coverage improvement in DSN.

Key words: Aapproximate circle, Barrier contribution, Directional barrier coverage, Energy consumption

中图分类号:

TP391

王方红, 李涛, 金英东, 胡朕豪. 基于节点近似圆的有向强栅栏构建算法[J]. 计算机科学, 2019, 46(11A): 393-398. https://doi.org/

WANG Fang-hong, LI Tao, JIN Ying-dong, HU Zhen-hao. Directional Strong Barrier Constructing Scheme Based on Node Approximate Circle[J]. Computer Science, 2019, 46(11A): 393-398. https://doi.org/

参考文献

[1]TAO D,T WU.A survey on barrier coverage problem in directional sensor networks[J].IEEE Sensors Journal,2015,15(2):876-885.
[2]范兴刚,刘涛,胡凤丹,等.一种延长目标覆盖网络寿命的群智能算法[J].计算机科学,2018,45(12):93-98.
[3]KUMAR S,LAI T H,ARORA A.Barrier coverage with wireless Sensors[C]∥Proc.of the 11th Annual International Conference on Mobile Computing and Networking.2005:284-298.
[4]罗卿,林亚平,王雷,等.传感器网络中基于数据融合的栅栏覆盖控制研究[J].电子与信息学报,2012,34(4):825-831.
[5]班冬松,温俊,蒋杰,等.移动无线传感器网络K-栅栏覆盖的构建算法[J].软件学报,2011,22(9):2089-2103.
[6]TIAN J,ZHANG W S,WANG G L,et al.2D k-barrier duty-cycle scheduling for intruder detection in wireless sensor networks[J].Computer Communications,2014,4(3):31-42.
[7]王超,范兴刚.一种高效强K—栅栏覆盖构建算法[J].传感技术学报,2015,28(2):227-233.
[8]MA H D,YANG M,LI D,et al.Minimum camera barrier cove-rage in wireless camera sensor networks[C]∥Proc.IEEE INFOCOM,Orlando,FL,USA,2012:217-225.
[9]TAO D,TANG S,ZHANG H,et al.Strong barrier coverage in directional sensor networks[C]∥Computer Communications,2012,35(8):895-905.
[10]ZHANG L,TANG J,ZHANG W.Strong barrier coverage with directional sensors[C]∥Proc.IEEE GlobeCom.Honolulu,HI,USA,2009:1-6.
[11]SSU K F,WANG W T,W F K,et al.K-barrier coverage with a directional sensing model[J].International Journal on Smart Sensing and Intelligent Systems,2009,2(1):75-93.
[12]CHENG C F,TSAI K T.distributed barrier coverage in wireless visual sensor networks with β-qom[J].IEEE Sensors Journal,2012,12(6):1726-1735.
[13]WANG Z B,LIAO J D,CAO Q,et al.Achieving k-barrier Co-verage in Hybrid Directional Sensor Networks[J].IEEE Tran-sactions on Mobile Computing,2014,13(7):1443-1455.
[14]CHEN J,WANG B,LIU W,et al.Rotating directional sensors to mend barrier gaps in a line-based deployed directional sensor network[J].IEEE Systems Journal,2017,11(2):1027-1038.
[15]WU Y,CARDEI M.Distributed algorithms for barrier coverage via sensor rotation in wireless sensor networks[J].Journal of Combinatorial Optimization,2018,36:230-251.
[16]任勇默,范兴刚.一种有向传感器网络栅栏覆盖增强算法[J].传感技术学报,2015,28(7):1051-1057.
[17]GUVENSAN A,YAVUZ G.Hybrid movement strategy in self-orienting directional sensor networks[J].Ad Hoc Networks,2013,11(3):1075-1090.
[18]王万良.人工智能及其应用(第三版)[M].北京:高等教育出版社,2016.

相关文章 15

[1]	王方红, 范兴刚, 杨静静, 周杰, 王德恩. 一种基于有向感知区域调整的强栅栏构建算法 Strong Barrier Construction Algorithm Based on Adjustment of Directional Sensing Area 计算机科学, 2022, 49(6A): 612-618. https://doi.org/10.11896/jsjkx.210300291
[2]	高堰泸, 徐圆, 朱群雄. 基于A-DLSTM夹层网络结构的电能消耗预测方法 Predicting Electric Energy Consumption Using Sandwich Structure of Attention in Double -LSTM 计算机科学, 2022, 49(3): 269-275. https://doi.org/10.11896/jsjkx.210100006
[3]	杜辉, 李卓, 陈昕. 基于在线双边拍卖的分层联邦学习激励机制 Incentive Mechanism for Hierarchical Federated Learning Based on Online Double Auction 计算机科学, 2022, 49(3): 23-30. https://doi.org/10.11896/jsjkx.210800051
[4]	张忆文, 林铭炜. 基于动态优先级设备低能耗调度算法 Devices Low Energy Consumption Scheduling Algorithm Based on Dynamic Priority 计算机科学, 2021, 48(11A): 471-475. https://doi.org/10.11896/jsjkx.210100080
[5]	金小敏, 滑文强. 移动云计算中面向能耗优化的资源管理 Energy Optimization Oriented Resource Management in Mobile Cloud Computing 计算机科学, 2020, 47(6): 247-251. https://doi.org/10.11896/jsjkx.190400020
[6]	胡锦天, 王高才, 徐晓桐. 移动边缘计算中具有能耗优化的任务迁移策略 Task Migration Strategy with Energy Optimization in Mobile Edge Computing 计算机科学, 2020, 47(6): 260-265. https://doi.org/10.11896/jsjkx.190400074
[7]	程煜, 刘伟, 孙童心, 魏志刚, 杜薇. 近阈值电压下可容错的一级缓存结构设计 Design of Fault-tolerant L1 Cache Architecture at Near-threshold Voltage 计算机科学, 2020, 47(4): 42-49. https://doi.org/10.11896/jsjkx.190300088
[8]	张彭奕, 宋杰. 区块链共识算法效能优化研究进展 Research Advance on Efficiency Optimization of Blockchain Consensus Algorithms 计算机科学, 2020, 47(12): 296-303. https://doi.org/10.11896/jsjkx.200700020
[9]	李正阳, 陶洋, 周远林, 杨柳. 基于能量获取的能耗均衡多跳分簇路由协议 Energy-balanced Multi-hop Cluster Routing Protocol Based on Energy Harvesting 计算机科学, 2020, 47(11A): 296-302. https://doi.org/10.11896/jsjkx.200300002
[10]	熊成彪,丁洪伟,董发志,杨志军,保利勇. 一种基于LEACH的低延迟和低功耗的WSN分簇算法 Low-delay and Low-power WSN Clustering Algorithm Based on LEACH XIONG 计算机科学, 2020, 47(1): 258-264. https://doi.org/10.11896/jsjkx.190100060
[11]	卢海峰, 顾春华, 罗飞, 丁炜超, 袁野, 任强. 强化学习下能耗优化的虚拟机放置策略 Virtual Machine Placement Strategy with Energy Consumption Optimization under Reinforcement Learning 计算机科学, 2019, 46(9): 291-297. https://doi.org/10.11896/j.issn.1002-137X.2019.09.044
[12]	方旭愿, 田红心, 孙德春, 杜文丛, 祁婷. 基于绿色能源感知的效用函数异构网络接入算法 Utility Function Heterogeneous Network Access Algorithm Based on Green Energy Perception 计算机科学, 2019, 46(8): 127-132. https://doi.org/10.11896/j.issn.1002-137X.2019.08.021
[13]	张举, 耿海军, 刘洁琦. 基于网络熵的域内节能路由方案 Intra-domain Energy Efficiency Routing Scheme Based on Network Entropy 计算机科学, 2019, 46(2): 76-80. https://doi.org/10.11896/j.issn.1002-137X.2019.02.012
[14]	庄晓照, 万继光, 张艺文, 瞿晓阳. 一种基于新能源驱动的存储系统的能耗优化方案 Energy Consumption Optimization Scheme for New Energy-driven Storage System 计算机科学, 2018, 45(7): 66-72. https://doi.org/10.11896／j.issn.1002-137X.2018.07.010
[15]	耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法 Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph 计算机科学, 2018, 45(4): 112-116. https://doi.org/10.11896/j.issn.1002-137X.2018.04.017

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed