基于虚拟网格的无线传感器网络分簇路由算法

doi:10.11896／j.issn.1002-137X.2018.11.007

计算机科学 ›› 2018, Vol. 45 ›› Issue (11): 60-65.doi: 10.11896／j.issn.1002-137X.2018.11.007

所属专题：网络通信

基于虚拟网格的无线传感器网络分簇路由算法

陈战胜^1,2, 沈鸿^3,4

(北京交通大学计算机与信息技术学院北京100044)¹
(北京联合大学应用科技学院北京100101)²
(中山大学数据科学与计算机学院广州510275)³
(澳大利亚阿德莱德大学计算机科学学院阿德莱德 5005)⁴

收稿日期:2017-10-08 发布日期:2019-02-25
作者简介:陈战胜(1979-),男,博士生,讲师,主要研究方向为无线传感器网络、大数据分析,E-mail:11112085@bjtu.edu.cn;沈鸿(1958－),男,博士,教授,主要研究方向为并行与分布式处理、组合优化算法、网络路由、资源调度、大数据分析与处理等,E-mail:shenh3@mail.sysu.edu.cn(通信作者)。
基金资助:
本文受国家自然科学基金(61170232,61672088,61300175),澳大利亚研究理事科研项目(DP150104871),北京联合大学应用科技学院科研经费资助。

Virtual Grid Based Clustering and Routing Algorithm in Wireless Sensor Networks

CHEN Zhan-sheng^1,2, SHEN Hong^3,4

(School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China)¹
(School of Applied Science and Technology,Beijing Union University,Beijing 100101,China)²
(School of Data and Computer Science,Sun Yat-sen University,Guangzhou 510275,China)³
(School of Computer Science,The University of Adelaide,Adelaide 5005,Australia)⁴

Received:2017-10-08 Published:2019-02-25

摘要/Abstract

摘要： 针对WSNs路由协议中链路通信负载不均引发的能量空洞问题,提出一种基于虚拟网格的动态聚簇策略IDCS和考虑数据转发延迟的最大化网络生命周期的动态负载均衡路由算法DCDLB。IDCS依据节点的通信半径将网络划分成若干虚拟网格,采用考虑节点能量和位置因素的分布式簇首选举策略,并引入基于簇首能量水平的动态簇首轮换机制。DCDLB综合考虑簇首间能耗均衡和数据多跳转发延迟来构建路由,实现网络生命周期的最大化。实验结果表明,DCDLB路由算法在延长网络生命周期和降低数据转发延迟方面优于LEACH,HEED和CRVB路由算法。

关键词: 簇首选举, 路由算法, 生命周期, 虚拟网格, 延迟

Abstract: In order to solve the energy hole problem caused by the unevenness of the link communication load in WSNs routing protocol,a dynamic clustering algorithm based on virtual grid (IDCS) and a dynamic load balancing routing algorithm (DCDLB) for maximizing network life cycle considering data forwarding delay were presented.In IDCS algorithm,the area is divided into several virtual grids according to node communication radius,and the nodes in the same grid form a cluster.The cluster head is chosen by distributed cluster head selection strategy considering node’s energy and location factors,and a dynamic cluster head rotation mechanism based on cluster head’s energy level is introduced for balancing consumption.In DCDLB routing algorithm,the network lifetime is maximized by considering energy consumption balance among cluster heads and multihop data forwarding delay.The simulation results show that DCDLB routing algorithm is superior to LEACH,HEED and CRVB routing algorithms in terms of extending network lifetime and decreasing data forwarding delay.

Key words: Clusterhead election, Delay, Life cycle, Routing algorithm, Virtual grid

中图分类号:

TP393

陈战胜, 沈鸿. 基于虚拟网格的无线传感器网络分簇路由算法[J]. 计算机科学, 2018, 45(11): 60-65. https://doi.org/10.11896／j.issn.1002-137X.2018.11.007

CHEN Zhan-sheng, SHEN Hong. Virtual Grid Based Clustering and Routing Algorithm in Wireless Sensor Networks[J]. Computer Science, 2018, 45(11): 60-65. https://doi.org/10.11896／j.issn.1002-137X.2018.11.007

参考文献

[1]HUYNH T T,DINH-DUC A V,TRAN C H.Delay-constrained energy-efficient cluster-based multi-hop routing in wireless sensor networks.Journal of Communications and Networks,2016,18(4):580-588.
[2]CURRY R M,SMITH J C.A survey of optimization algorithms for wireless sensor network lifetime maximization.Compu-ters & Industrial Engineering,2016,101:145-166.
[3]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISH- NAN H.Energy-efficient communication protocol for wireless microsensor networks∥Proceedings of the 33rd Annual Hawaii InternationalConference on System Sciences.USA:IEEE Press,2000:1-10. CHEN Z S,SHEN H.Energy efficient wireless sensor network routing protocol .Computer Science,2015,42(8):90-94,117.(in Chinese)
陈战胜,沈鸿.能量高效的无线传感器网络路由协议.计算机科学,2015,42(8):90-94,117. YOUNIS O,FAHMY S.HEED:a hybrid,energy-efficient,dis- tributed clustering approach for ad hoc sensor networks.IEEE Transactions on Mobile Computing,2004,3(4):366-379.
[6]XU Y,HEIDEMANN J,ESTRIN D.Geography-informed energy conservation for ad hoc routing∥Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.Rome:ACM Press,2001:70-84. JANNU S,JANA P K.A grid based clustering and routing algorithm for solving hot spot problem in wireless sensor networks.Wireless Networks,2016,22(6):1901-1916. HALEEM FARMAN H J,AHMAD J,JAN B,et al.Grid-Based Hybrid Network Deployment Approach for Energy Efficient Wireless Sensor Networks.Journal of Sensors,Research Gate,2016,2016(3):1-16. MENG X,SHI X,WANG Z,et al.A grid-based reliable routing protocol for wireless sensor networks with randomly distributed clusters.Ad Hoc Networks,2016,51(C):47-61.
[10]ZHU M,XIAO Z,LIU H L,et al.A Clustering Routing Algorithm Based on Virtual Grid in WSN.Journal of Sichuan University (Engineering Science Edition),2012,44(5):143-148.(in Chinese)
朱敏,肖震,刘昊霖,等.WSN中基于虚拟网格的分簇路由算法.四川大学学报(工程科学版),2012,44(5):143-148. ZHANG H B,SHEN H.Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks[J].IEEE Transactions on Parallel & Distributed Systems,2008,20(10):1526-1539.
[12]AKBAR M, JAVAID N, IMRAN M,et al.A multi-hop angular routing protocol for wireless sensor networks.International Journal of Distributed Sensor Networks,2016,12(9):1-13.
[13]FENG R,LI T,WU Y,et al.Reliable routing in wireless sensor networks based on coalitional game theory.IET Communications,2016,10(9):1027-1034.
[14]HAN K H H,KO Y B,KIM J H.A novel gradient approach for efficient data dissemination in wireless sensor networks∥IEEE 60th Vehicular Technology Conference.Los Angeles:IEEE Press,2004:2979-2983.
[15] ZHENG M C,ZHANG D F,ZHAO X C.The study on the behavioral characteristics of the wireless sensor network of minimum hop routing .Computer Application,2007,27(10):2552-2555.(in Chinese)
郑明才,张大方,赵小超.最小跳数路由无线传感器网络行为特征研究.计算机应用,2007,27(10):2552-2555.

相关文章 15

[1]	张皓晨, 蔡英, 夏红科. 车载社交网中基于传递概率的路由算法 Delivery Probability Based Routing Algorithm for Vehicular Social Network 计算机科学, 2021, 48(3): 289-294. https://doi.org/10.11896/jsjkx.200200097
[2]	张元鸣, 虞家睿, 蒋建波, 陆佳炜, 肖刚. 面向MapReduce的中间数据传输流水线优化机制 Intermediate Data Transmission Pipeline Optimization Mechanism for MapReduce Framework 计算机科学, 2021, 48(2): 41-46. https://doi.org/10.11896/jsjkx.191000103
[3]	陈靖邦, 潘俊哲, 沈皓朗, 谷培, 扈明涛. 一种多趋势指标结合与择时引入峰值的投资组合优化系统 Portfolio Optimization System Based on Multiple Trend Indices with Time Picking of Inducing Peak Prices 计算机科学, 2021, 48(11A): 693-698. https://doi.org/10.11896/jsjkx.210300215
[4]	刘通, 方璐, 高洪皓. 边缘计算中任务卸载研究综述 Survey of Task Offloading in Edge Computing 计算机科学, 2021, 48(1): 11-15. https://doi.org/10.11896/jsjkx.200900217
[5]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[6]	董超颖, 续欣, 刘爱军, 苌敬辉. 低轨卫星星座网络路由新方法 New Routing Methods of LEO Satellite Networks 计算机科学, 2020, 47(12): 285-290. https://doi.org/10.11896/jsjkx.191000067
[7]	郭子亭, 张文力, 陈明宇. 基于M/M/1排队模型的网络服务尾延迟分析 Network Service Tail Latency Analysis Based on M/M/1 Queuing Model 计算机科学, 2020, 47(11): 286-293. https://doi.org/10.11896/jsjkx.191200072
[8]	何明星, 周杰, 吴鹏, 刘杨. 山洞环境中声信号的传播模型及其性能研究 Acoustic Signal Propagation Model and Its Performance in Cave Environment 计算机科学, 2019, 46(9): 113-119. https://doi.org/10.11896/j.issn.1002-137X.2019.09.015
[9]	赵磊, 周金和. 基于复杂网络内容场的ICN能效优化策略 ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks 计算机科学, 2019, 46(9): 137-142. https://doi.org/10.11896/j.issn.1002-137X.2019.09.019
[10]	刘锋, 葛培新, 曾连荪. 基于延迟CSIT的非对称双向中继X信道传输方案 Transmission Scheme for Asymmetric Two-way Relay X Channel Based on Delayed CSIT 计算机科学, 2019, 46(8): 152-156. https://doi.org/10.11896/j.issn.1002-137X.2019.08.025
[11]	梁平元, 李杰, 彭娇, 王会. 基于协作MIMO的UWSN三维动态分簇路由算法研究 Research on 3D Dynamic Clustering Routing Algorithm Based on Cooperative MIMO for UWSN 计算机科学, 2019, 46(6A): 336-342.
[12]	王华华, 周远文, 刘江兵. LLN中基于混合式的网络拥塞控制路由算法 Hybrid-based Network Congestion Control Routing Algorithm for LLN 计算机科学, 2019, 46(6): 107-111. https://doi.org/10.11896/j.issn.1002-137X.2019.06.015
[13]	赵新伟, 刘伟. 一种基于节点状态的MANET路由发现和建立策略 MANET Routing Discovery and Establishment Strategy Based on Node State 计算机科学, 2019, 46(6): 112-117. https://doi.org/10.11896/j.issn.1002-137X.2019.06.016
[14]	孙海峰,宋丽丽. 路口中继辅助车载自组织网络路由算法 Intersection-relay-assisted Routing Scheme in VANETs 计算机科学, 2018, 45(5): 75-78. https://doi.org/10.11896/j.issn.1002-137X.2018.05.013
[15]	李璐璐,裘雪红,周端,张剑贤. 片上网络容错技术研究 Research on Fault Tolerant Technology for Networks-on-Chip 计算机科学, 2018, 45(3): 305-310. https://doi.org/10.11896/j.issn.1002-137X.2018.03.050

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于虚拟网格的无线传感器网络分簇路由算法

Virtual Grid Based Clustering and Routing Algorithm in Wireless Sensor Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0