Traffic balancing routing algorithm for wireless mesh networks based on Grover search
LIU Yongguang1,2
1. Department of Management, Guangdong Industry Technical College, Guangzhou Guangdong 510300, China;
2. NO.7 Research Institute, China Electronics Technology Group Corporation, Guangzhou Guangdong 510310,China
In applications of Wireless Mesh Networks (WMN), users can access Internet through mesh gateways. This architecture is prone to cause traffic unbalance between mesh routers located at different places, make some mesh routers become bottleneck and hence affect network performance and user's Quality of Service (QoS). To solve this problem, a traffic balancing routing algorithm based on Grover quantum search algorithm was presented. In this algorithm, the parallel character of quantum computation was utilized. The operation matrix was constructed according to model of traffic balancing function. The traffic balancing paths were gotten by Grover iteration. Simulations show that the paths selected by the algorithm can balance traffic of WMN effectively and make the minimum bandwidth every user got maximized. The executive efficiency of the algorithm is also better than the similar ones.
IAN F, WANG X D, WANG W L. Wireless mesh networks: a survey［J］. Computer Networks, 2005, 47(4):445-487.
［2］
LIU Y, YE W, FENG S, et al. Ant colony algorithm-based fair routing algorithm for wireless mesh networks［J］. Journal of South China University of Technology: Natural Science, 2009, 37(1):119-123.(刘永广,叶梧,冯穗力,等.基于蚁群算法的无线Mesh网公平路由算法［J］. 华南理工大学学报: 自然科学版,2009,37(1): 119-123.)
［3］
WU X, LIU J, CHEN G. Analysis of bottleneck delay and throughput in wireless mesh networks［C］// MASS 2006: Proceedings of the 2006 International Conference on Mobile Ad Hoc and Sensor Systems. Piscataway: IEEE, 2006:765-770.
［4］
YANG P, CHEN G. Research paradigm of capacity analysis and optimizing theory on wireless mesh networks［J］. Journal of Software, 2008, 19(1):111-125.(杨盘隆, 陈贵海.无线网状网容量分析与优化理论研究［J］.软件学报,2008,19(1):111-125.)
［5］
LI F, WANG Y, LI X Y. Gateway placement for throughput optimization in wireless mesh networks［C］// ICC 2007: Proceedings of the 2007 IEEE International Conference on Communications. Piscataway: IEEE, 2007:4955-4960.
［6］
IBRARS C, COSO A D, GRUNENBERGER Y, et al. Increasing the throughput of wireless mesh networks with cooperative techniques［C］// Proceedings of the 16th Mobile and Wireless Communications Summit. Piscataway: IEEE, 2007:1-5.
［7］
ZHANG H, TSANG D H K. Traffic oriented topology formation and load-balancing routing in wireless mesh networks［C］// ICCCN 2007: Proceedings of the 2007 International Conference on Computer Communications and Networks. Piscataway: IEEE, 2007: 1046-1052.
［8］
NANDIRAJU D, SANTHANNAM L, NANDIRAJU N, et al. Achieving load balancing in wireless mesh networks through multiple gateways［C］// MASS 2006: Proceedings of the 2006 International Conference on Mobile Ad Hoc and Sensor Systems. Piscataway: IEEE, 2006:807-812.
［9］
BEJERANO Y, HAN S J, KUMAR A. Efficient load-balancing routing for wireless mesh networks［J］. Computer Networks, 2007, 51(10):2450-2466.
［10］
HSIAO P H, HWANG A, KUNG H T, et al. Load balancing routing for wireless access networks［C］// INFOCOM 2001: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway: IEEE, 2001: 986-995.
［11］
HE J Y, CHEN J C, CHAN S H G. Extending WLAN coverage using infrastructureless access points［C］// HPSR 2005: Proceedings of Workshop on High Performance Switching and Routing. Piscataway: IEEE, 2005:162-166.
［12］
GROVER L K. A fast quantum mechanical algorithm for database search［C］// Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. New York: ACM Press, 1996: 212-219.
［13］
ZHONG P, BAO W, FAN D, et al. Quantum mechanical algorithm to solve knapsack problem［J］. Computer Engineering and Applications, 2009, 45(20): 63-64.(钟普查, 鲍皖苏, 范得军, 等. 背包问题的量子计算算法［J］.计算机工程与应用, 2009, 45(20): 63-64.)
［14］
MENG L M, SONG W B. Routing protocol based on Grover's searching algorithm for mobile Ad Hoc networks［J］. China Communications, 2013, 10(3):145-156.
［15］
LU J, WU X, ZHOU K. Research on Grover routing model for MANET based on node degree algorithm［J］. Chinese Journal of Sensors and Actuators, 2011, 24(9):1331-1335.(卢军,邬学军,周凯. 基于节点度的移动自组网络Grover路由算法研究［J］. 传感技术学报, 2011,24(9): 1331-1335.)
2014, Vol. 34 
