Computer Science ›› 2018, Vol. 45 ›› Issue (11): 60-65.doi: 10.11896/j.issn.1002-137X.2018.11.007

• Network & Communication • Previous Articles     Next Articles

Virtual Grid Based Clustering and Routing Algorithm in Wireless Sensor Networks

CHEN Zhan-sheng1,2, SHEN Hong3,4   

  1. (School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China)1
    (School of Applied Science and Technology,Beijing Union University,Beijing 100101,China)2
    (School of Data and Computer Science,Sun Yat-sen University,Guangzhou 510275,China)3
    (School of Computer Science,The University of Adelaide,Adelaide 5005,Australia)4
  • Received:2017-10-08 Published:2019-02-25

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: Life cycle, Virtual grid, Clusterhead election, Routing algorithm, Delay

CLC Number: 

  • TP393
[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)
[1] LIU Tong, FANG Lu, GAO Hong-hao. Survey of Task Offloading in Edge Computing [J]. Computer Science, 2021, 48(1): 11-15.
[2] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[3] ZHANG Hong-ying, SHEN Rong-miao, LUO Qian. Study on Optimal Scheduling of Gate Based on Mixed Integer Programming [J]. Computer Science, 2020, 47(8): 278-283.
[4] DONG Chao-ying, XU Xin, LIU Ai-jun, CHANG Jing-hui. New Routing Methods of LEO Satellite Networks [J]. Computer Science, 2020, 47(12): 285-290.
[5] ZHANG Hua-wei, XIE Dong-feng, ZOU Yan-fang, HU Yong-hui. Multi-hop Dynamic Resource Allocation Protocol with Guaranteed QoS [J]. Computer Science, 2020, 47(11A): 310-315.
[6] ZHANG Cheng-wei, LUO Feng-e, DAI Yi. Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining [J]. Computer Science, 2020, 47(11A): 464-470.
[7] HE Ming-xing, ZHOU Jie, WU Peng, LIU Yang. Acoustic Signal Propagation Model and Its Performance in Cave Environment [J]. Computer Science, 2019, 46(9): 113-119.
[8] ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
[9] LIU Feng, GE Pei-xin, ZENG Lian-sun. Transmission Scheme for Asymmetric Two-way Relay X Channel Based on Delayed CSIT [J]. Computer Science, 2019, 46(8): 152-156.
[10] WANG Jun-ya,LI Jia-di,LI De-quan. Distributed Subgradient Optimization Algorithm with Communication Delays for Multi-agent Switched Networks [J]. Computer Science, 2019, 46(7): 81-85.
[11] LIANG Ping-yuan, LI Jie, PENG Jiao, WANG Hui. Research on 3D Dynamic Clustering Routing Algorithm Based on Cooperative MIMO for UWSN [J]. Computer Science, 2019, 46(6A): 336-342.
[12] WANG Hua-hua, ZHOU Yuan-wen, LIU Jiang-bing. Hybrid-based Network Congestion Control Routing Algorithm for LLN [J]. Computer Science, 2019, 46(6): 107-111.
[13] ZHAO Xin-wei, LIU Wei. MANET Routing Discovery and Establishment Strategy Based on Node State [J]. Computer Science, 2019, 46(6): 112-117.
[14] LIANG Tao, WANG Tong-xiang, LIU Jian-wei, YANG Jing. Modeling of Jamming Attack and Performance Analysis in Multi-hop Wireless Network [J]. Computer Science, 2019, 46(11A): 414-416.
[15] HUANG Yin-hao, MA Yun, LIN Bing, YU Zhi-yong, CHEN Xing. Cost-driven Workflow Data Placement Method in Hybrid Cloud Environment [J]. Computer Science, 2019, 46(11A): 354-358.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .