【作者】 曾锋；

【导师】 陈志刚；

【作者基本信息】 中南大学 ， 计算机应用技术， 2010， 博士

【摘要】 无线Mesh网是重要的下一代无线接入技术。流量负载均衡技术能实现无线Mesh网吞吐量及QoS性能的提升,是无线Mesh网技术研究的热门课题。无线Mesh网体系结构中,无线骨干层处于核心地位,对无线Mesh网性能有重要影响。由于无线骨干层由网关和Mesh路由器节点组成,无线Mesh网流量负载均衡有赖于两个方面：其一是网关之间的负载均衡,其二是Mesh路由器之间的负载均衡。因此,本文关于无线Mesh网流量负载均衡技术的研究工作基于两个方面展开,即网关负载均衡技术和Mesh路由器负载均衡技术。针对网关负载均衡问题,本文从网络设计阶段着手,提出负载均衡的网关部署问题,同时考虑网络QoS因素和部署费用；针对Mesh路由器负载均衡问题,本文研究具有负载感知能力的路由度量及其协议,以及QoS优化的多路径路由路径流量分配策略。本文围绕网关及Mesh路由器负载均衡问题进行了深入研究,主要工作如下：(1)针对负载均衡的网关部署问题,提出负载均衡的网络分簇算法,设计遗传算法达到数量及负载均衡的双重优化本文定义网关负载均衡度量,提出负载均衡的网关部署问题。为实现网关的负载均衡部署,提出网关部署的贪婪算法Greedy_Partition,该算法通过调整簇结构贪婪地减小网关之间负载的差别。为达到网关数量与负载均衡的双重优化,利用遗传算法在多目标寻优方面的优势,设计遗传算法GA_Placement求解网关数量最少、负载均衡的部署方案。在遗产算法GA_Placement设计中,力求与Greedy_Partition算法相结合,以实现在较少迭代次数下得到网关数量和负载均衡两方面优化的网关部署方案。(2)针对网关部署费用的差别,提出基于邻接矩阵和部署性价比的网关部署算法,实现网关负载均衡部署中的费用优化本文提出费用最小且负载均衡的网关部署问题,针对网关性能存在差别这一特点,设计新的网关负载均衡度量。提出费用优化及网关负载均衡的网关部署算法CLGP,该算法基于邻接矩阵和部署性价比进行网关选择,并对网关部署费用及负载均衡进行迭代优化。仿真实验验证了算法的有效性,算法执行复杂性较低。(3)基于图论支配集理论,提出有限支配集概念,把费用最小网关部署问题归结为图的最小权有限支配集问题,并提出相应的求解算法本文基于网关部署问题与图论支配集问题的相关性,提出有限支配集的概念,并把费用最小满足QoS约束的网关部署问题转化为最小权有限支配集问题。提出求解问题的贪婪算法Greedy_LDS和粒子群优化算法PSO_LDS。Greedy_LDS具有较低的算法复杂性,PSO_LDS以执行时间增加为代价可以找到较优的解。两算法各有优势,具有重要的参考价值。(4)基于无线Mesh网流量自相似性,进行流量预测,并综合当前流量与预测流量信息到路由度量及协议中,实现路由选择的负载自适应本文利用自相似流量的可预测性,进行流量预测；提出节点可负载度的概念,并作为路由度量,该度量包含了当前流量和预期流量的信息,可以很好地反映在将来的一段时间里节点仍可接受负载的能力,由此实现路由选择的前瞻性和预见性；提出具有负载均衡的路由协议LBDSR,该协议以路由中节点可负载度均值来衡量路由的好坏,从而达到网络的负载均衡。仿真实验表明,当网络负载较重时,LBDSR协议与其它协议相比,有更好的网络吞吐量和端到端时延。(5)基于网络演算理论分析路径时延及其抖动上界,并提出时延及抖动优化的多路径流量分配算法本文基于多媒体应用的服务质量研究多路径路由协议中路径流量分配策略。首先基于网络演算理论分析了路径时延上界及路径间时延抖动上界；然后,基于路径时延及路径间时延抖动上界提出满足时延约束、抖动优化的路径流量分配算法DCJOTA,并分析了算法实现的可行性和方法；最后,把DCJOTA算法应用到AOMDV路由协议中,并在NS-2网络模拟器中验证了算法的有效性。更多还原

【Abstract】 Wireless mesh networks (WMNs) have been an important technology for next-generation wireless networking. As an important technology, load balancing can improve the throughput and QoS performance in WMNs, and becomes one of the hot issues in the research of WMNs. In the architechture of WMNs, wireless backbone is the key point in WMNs, and has much impact on the network performance. Since wireless bachbone is made up of gateways and mesh routers, the load balancing technology should be considered from two sides. One is the balancing of load on the gateways, and the other is the load balancing among the mesh routers. Consequently, in our work, there are two routes in the research process of load balancing. The first route is how to realize the load balancing among the gateways, and the second one focus on the load balancing among mesh routers. To the first one, we pay attention to the gateway placement technologies in network design, and propose the load balancing gateway placement problem, considering the QoS and the placing cost. In the second route of our research, we put emphasis on the traffic-aware routing metric and the related protocols, and the QoS optimized traffic allocation strategy for the paths in multipath routing. Through the two researching routes, the load balancing technologies on the gateways and the mesh routers are studied deeply in this thesis. The main work and contributions are presented in the following aspects:(1) We address the load balancing gateway placement problem in WMNs, and propose the related algorithms to realize the balancing of the load on the gateways.The most existing work puts emphasis on reducing the number of gateways in a WMN, while ensuring QoS requirements. But, the load balancing among the gateways is little considered. In this thesis, we define the metric for load balancing on the gateways, and address the load balancing gateway placement problem. In order to realize the load balancing among the gateways, we propose a greedy algorithm Greedy_Partition, which iteratly reduces the load difference among the gateways through the adjustment of cluster structure. In order to get the two goals of minimum gateways and load balance in gateway placement at the same time, a genetic algorithm GA_Placement is designed, which is integrated with the greedy algorithm Greedy_Partition in the genetic operators. (2) Taking the placing cost into account, we propose minimum cost and load balancing gateway placement problem and related algorithms.In reality, the facility performance and the placing cost of the gateways are different from each other, and the minimum number of gateways never means the minimum cost of gateway placement. In some case (i.e. the cost or the facility performance are limited), we should consider the cost optimization problem in the gateway placement. In this thesis, we address minimum cost and load balancing gateway placement problem. Due to the facility difference of the gateways, we design a new metric for load balancing among the gateways, and propose the gateway placement algorithm CLGP, which selects the gateway candidates based on the adjacent matrix and performance/cost ratio of the gateways, and iteratly does the optimization of load balancing. Simulation results show that the proposed algorithm has better performance and complexity than the other algorithms in placing cost and load balancing.(3) Based on the theory of dominating set in graph, we propose a new model and the algorithms for cost optimized placement of gateways in WMNs.The previous work in gateway placement modeled the problem as linear programming, which is of high complexity to be solved requiring some rigor conditions. Different from the existing work, based on the analysis of the relationship between gateway placement and dominating set in graph, we present the concept of limited dominating set (LDS), and address the cost-minimum gateway placement problem as the minimum weighted LDS problem. In order to find the minimum weighted LDS, we propose a greedy algorithm Greedy_LDS and a particle swarm optimization (PSO) algorithm PSO_LDS. Greedy_LDS has lower computing complexity, and PSO_LDS has better quality of the result. Thus, we provide a trade-off for minimum cost gateway placement in WMNs.(4) Based on the self-similarity of traffic in WMNs, we propose a traffic-aware and load-adaptive routing metric and protocol.The self-similarity of traffic in WMNs has been validated by some researchers. Based on the predictability of self-similar traffic, we introduce a statistical methodology to predict the traffic. Then, we combine the measured traffic and the predicted traffic to form a new metric named loadability degree, which can be used to evaluate the node’s ability to handle traffic and can adjust itself to the change of traffic. At last, we present a load-adaptive routing protocol LBDSR using the new metric for route selection. This protocol can effectively balance the traffic and improve throughput in WMNs. Simulation results show that when the network traffic is heavy, LBDSR outperform others on the network throughput and end-to-end delay.(5) Based on network calculus theory, we propose a delay-constrained and jitter-optimized traffic allocation algorithm for multipath routing.In WMNs, traffic allocation algorithm in multipath routing has an important impact on network performance and load balancing. In order to improve the QoS for multimedia application, we focus on the delay-constrained and jitter-optimized traffic allocation problem in multipath routing. First of all, based on the network calculus theory, we make a deep analysis on the upper bound of end-to-end delay and jitter in the transmission. Then, based on the upper bound of delay and jitter, we propose a delay-constrained and jitter-optimized traffic allocation algorithm DCJOTA, and the implement methods of DCJOTA are analyzed. Experimental results show that the DCJOTA embedded multipath routing protocol outperforms AOMDV at the term of end-to-end delay and jitter.更多还原