基于生成树的无线Mesh网络数据流负载均衡研究.pdfVIP

基于生成树的无线Mesh 网络数据流负载均衡研究 1 2 黄书强 ，周继鹏 1 （暨南大学网络与教育技术中心 广州 510632 ） 2 （ 暨南大学信息科学技术学院 广州 510632 ） 摘要：针对统一链路容量的无线 Mesh 网络的数据流负载均衡问题，本文提出了基于最大剩余流 生成树算法。该算法首先利用近似最大流算法求解每条链路上的碎片流量，然后利用最大剩余流 生成树将多径路由转化为单径路由，最后将原始流量在每条单独路径上进行缩放。本文所提算法 可以保持用户公平性前提下尽可能提高网络吞吐量。该算法最初思想来源于ROUND 算法，但是 算法速度和效率优于ROUND 算法。 关键词：生成树；最大流； 不可分割流；负载均衡 中图分类号：TP391 文献标识码：A The Research on Data Flow Load Balancing of Wireless Mesh Network based on Spanning Tree Huang Shuqiang 1, Zhou Jipeng 2 (1 Network and Education Technology Center of Jinan University, Guangzhou 510632, China) 2 （College of Information Science and Technology of Jinan University, Guangzhou 510632, China) Abstract: data flow Load balancing of wireless mesh networks of uniform link capacity has been studied in this paper and a data flow load-balancing algorithm was proposed based on maximum surplus flow spanning tree. For each network unit, flow of each link was calculated by maximum flow algorithm, and then a maximum surplus flow spanning tree was built by cutting based on flow information. The multi-path routing was transformed into a single-path routing by the spanning tree, and the original flow was scaled on each path. The proposed algorithm can maintain the balance between the fairness of user and maximizing network throughput. The algorithm idea was from ROUND algorithm, but the algorithm is better than ROUND algorithm on speed and efficiency Keywords：spanning tree; maximum flow; unsplitable flow; load balancing 在无线Mesh