Computer Science ›› 2018, Vol. 45 ›› Issue (8): 84-87.doi: 10.11896/j.issn.1002-137X.2018.08.015

• Network & Communication • Previous Articles     Next Articles

Sandpile Model Based Load Balancing Algorithm in Wireless Mesh Networks

ZHANG Yun-chun, LI Long-bao, YAO Shao-wen, HU Jian-tao, ZHANG Chen-bin   

  1. School of Software,Yunnan University,Kunming 650095,China
  • Received:2017-06-01 Online:2018-08-29 Published:2018-08-29

Abstract: The shortest path routing based load balancing mechanisms,which are widely used in wireless networks,result in congestion problem on some overloaded nodes.This seriously degrades the network transmission performance.Meanwhile,with the wide deployment of wireless networks and the increasing demand of application requirements,the optimization and improvement for existing load balancing mechanisms are urgent needed.Consequently,on the basis of “collapse” mechanism and its improvement,a load balancing algorithm suitable for wireless Mesh networks was proposed.It focuses on designing the triggering condition under which the load balancing is started,candidate node set computation and traffic load distribution mechanism.The experimental results show that the sandpile model based load ba-lancing algorithm outperforms the other similar algorithms in both packet drop ratio and throughput by 10.4% and 7% respectively.

Key words: Load balancing, Sandpile model, Throughput, Wireless Mesh networks

CLC Number: 

  • TP393.04
[1]SU J F,WU M Q,ZHANG Q J.Quantized optimal throughput analysis model of wireless multi-hop Ad hoc networks[J].Journal of XIDIAN University,2012,39(1):128-134.(in Chinese)宿景芳,武穆清,张钦娟.多跳Ad Hoc网络最佳吞吐率量化分析模型[J].西安电子科技大学学报,2012,39(1):128-134.
[2]LIU Y B,LIU N A,LI X H,et al.Load Balancing Routing Protocol Based on Traffic Prediction for Wireless Mesh Networks[J].Computer Science,2017,44(1):109-112.(in Chinese)柳永波,刘乃安,李晓辉,等.基于流量预测的无线Mesh网络负载均衡路由协议[J].计算机科学,2017,44(1):109-112.
[3]AJAYI A O,ROEDIG U,EDWARDS C,et al.A survey of rural Wireless Mesh Network (WMN) deployments[C]∥2014 IEEE Asia Pacific Conference on Wireless and Mobile.Bali:IEEE Press,2014:119-125.
[4]SHEN X J,CHEN Z G,LIU L.Load balancing multicast routing based on network coding in wireless mesh network[J].Journal on Communications,2015,36(4):89-95.(in Chinese)沈小建,陈志刚,刘立.无线mesh网络中编码感知且负载均衡的多播路由[J].通信学报,2015,36(4):89-95.
[5]DAREHSHOORZADEH A,GRANDE R D,BOUKERCHE A.Towards a Comprehensive Model for Performance Analysis of Opportunistic Routing in Wireless Mesh Networks[J].IEEE Transactions on Vehicular Technology,2015,65(7):5424-5438.
[6]QIAO H,ZHANG D F,XIE K,et al.Distributed Fair Cooperative Routing in Multi-gates Wireless Mesh Network[J].Journal on Communications,2015,36(2):175-185.(in Chinese)乔宏,张大方,谢鲲,等.分布式多网关无线Mesh网公平协作路由算法[J].通信学报,2015,36(2):175-185.
[7]SHESHADRI R K,KOUTSONIKOLAS D.An ExperimentalStudy of Routing Metrics in 802.11n Wireless Mesh Networks[J].IEEE Transactions on Mobile Computing,2014,13(12):2719-2733.
[8]GAO J,ZHANG L.Load-Balanced Short-Path Routing in Wireless Networks[J].IEEE Transactions on Parallel & Distributed Systems,2006,17(4):377-388.
[9]GAUR N,CHAKRABORTY A,MANOJ B S.Load-aware routing for non-persistent small-world wireless mesh networks[C]∥IEEE 2014 Twentieth National Conference on Communications (NCC).Kanpur:IEEE Press,2014:1-6.
[10]BAK P,TANG C,WIESENFELD K.Self-organized Criticality-An Explanation of 1/f Noise[J].Physical Review Letters,1987,59(59):381-384.
[11]AHMED A M,PAULUS R.Congestion detection technique for multipath routing and load balancing in WSN[J].Wireless Networks,2017,23(3):881-888.
[12]DELGADO COLLAO O,LABEAU F.Delay aware load balancing over multipath wireless networks[J].IEEE Transactions on Vehicular Technology,2017,PP(99):1.
[13]LAREDO J L J,BOUVRY P,GUINAND F,et al.The sandpile scheduler:How self-organized criticality may lead to dynamic load-balancing[J].Cluster Computing,2014,17(2):191-204.
[14]LAREDO J L J,GUINAND F,OLIVIER D,et al.Load Balancing at the edge of chaos:how self-organized criticality can lead to energy-efficient computing[J].IEEE Transactions on Parallel and Distributed Systems,2017,28(2):517-529.
[15]ZHOU T J,JIANG G P,TU X,et al.Local load redistribution strategy based on maximum residual capacity of nodes in complex networks[C]∥2017 29th Chinese Control And Decision Conference (CCDC).IEEE Press,2017:3692-3696.
[16]PERKINS C E,ROYER E M,DAS E.Ad hoc On-Demand Distance Vector Routing[C]∥Proceedings of the 2rd IEEE Workshop on Mobile Computing Systems and Applications 1999.Loui-siana,IEEE Press,1999:90-100.
[1] TIAN Zhen-zhen, JIANG Wei, ZHENG Bing-xu, MENG Li-min. Load Balancing Optimization Scheduling Algorithm Based on Server Cluster [J]. Computer Science, 2022, 49(6A): 639-644.
[2] GAO Jie, LIU Sha, HUANG Ze-qiang, ZHENG Tian-yu, LIU Xin, QI Feng-bin. Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor [J]. Computer Science, 2022, 49(5): 355-362.
[3] TAN Shuang-jie, LIN Bao-jun, LIU Ying-chun, ZHAO Shuai. Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning [J]. Computer Science, 2022, 49(2): 336-341.
[4] ZHANG Fan, GONG Ao-yu, DENG Lei, LIU Fang, LIN Yan, ZHANG Yi-jin. Wireless Downlink Scheduling with Deadline Constraint for Realistic Channel Observation Environment [J]. Computer Science, 2021, 48(9): 264-270.
[5] XIA Zhong, XIANG Min, HUANG Chun-mei. Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL [J]. Computer Science, 2021, 48(9): 278-285.
[6] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
[7] WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions [J]. Computer Science, 2021, 48(6A): 420-426.
[8] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[9] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[10] YANG Zi-qi, CAI Ying, ZHANG Hao-chen, FAN Yan-fang. Computational Task Offloading Scheme Based on Load Balance for Cooperative VEC Servers [J]. Computer Science, 2021, 48(1): 81-88.
[11] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[12] GAO Zi-yan and WANG Yong. Load Balancing Strategy of Distributed Messaging System for Cloud Services [J]. Computer Science, 2020, 47(6A): 318-324.
[13] HUANG Mei-gen, WANG Tao, LIU Liang, PANG Rui-qin and DU Huan. Virtual Network Function Deployment Strategy Based on Software Defined Network Resource Optimization [J]. Computer Science, 2020, 47(6A): 404-408.
[14] ZHOU Jian-xin, ZHANG Zhi-peng, ZHOU Ning. Load Balancing Technology of Segment Routing Based on CKSP [J]. Computer Science, 2020, 47(4): 256-261.
[15] ZHU An-qing, LI Shuai, TANG Xiao-dong. Parallel FP_growth Association Rules Mining Method on Spark Platform [J]. Computer Science, 2020, 47(12): 139-143.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!