| 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.
|
PDF Full Text Request