Research On Joint Routing And Scheduling Optimization Algorithm For Wireless Mesh Networks

Wireless Mesh Networks (WMN) have emerged recently as a type of wireless multi-hopnetworks developed form ad-hoc networks. WMNs have the capability of self-forming,self-healing and self-organization and are a key technology for the next generation wirelessnetworks. With the characteristics of easy deployment at low cost, flexible structure andcoverage, WMNs have more and more application scenarios in recent years. Based on thesurvey on the fundamentals of WMNs technology and recent advances in related research, thecross-layer joint optimization algorithms for WMNs are investigated and the contributionsand innovations are achieved as follows:1) To address the cross-layer optimization of routing and scheduling for TDMA-basedwireless mesh backhaul networks under the centralized control mode, based on introducing across-layer joint optimization framework whose optimal target is minimizing the systemactivation time, we propose a fast optimal algorithm by using maximal cliques searchingalgorithm to enumerate all maximal concurrent transmission scenarios in a wireless meshnetwork. Based on that, the optimization framework can be simplified to a LP (LinearProgramming) problem, so the global optimal solution could be easily found. Simulationresults verify that compared with the classical column generation algorithm usually used inthis kind of optimization problems, the average runtime has been reduced by more than99%.2) In order to maximize the throughput of relatively large scale WMNs, optimalalgorithms will take quite a long time to calculate the optimal result because the optimizationof thoughput of WMNs under the consideration of wireless interference is an NP-hardproblem by nature. According to the flow character in wireless mesh backhaul networks, wepropose a fast heuristic algorithm to get suboptimal results. Based on classification of linkweight, the heuristic algorithm can find out with high probability those maximal CTSs whichinclude high weight links and which are relatively more important. Furthermore, throughestablishing the effective connection between the searching times newly added and thevariance of the optimized results, the convergence of the algorithm can be guaranteed and thesuboptimal results can be obtained quickly. The simulation results show that the heuristicalgorithm can obtain suboptimal results within average0.5%of optimality for modest sizenetworks, and the average runtime is only about4%of that of maximal cliques algorithm.3) In the scenario of solving the throughput optimization problem of peer-to-peer WMNsin which there are traffic flows between multi source-destination pairs, without the flow convergence feature in wireless mesh backhaul networks, it is hard to classify the wirelesslinks and assign weight value to them. To solve this problem, firstly we propose an improvedDijkstra routing algorithm to search those key links probably used to transmit flow, thencombine those links and the heuristic algorithm mentioned above to slove the throughputoptimization. The innovative points lie in: firstly in order to avoid repeated calculation ofinterfered links’ occupancy ratio, we consider the concurrent transmission of different links inthe same path when we calculate link occupancy ratio; secondly we search those key linksrepeatedly and each time we change the sequence of the source-destination pairs ranodomly,that will reduce the influence to key links generation caused by routing sequence. Simulationresults show that this approach can solve the throughput optimization of peer-to-peer WMNsproperly and its advantage becomes more obvious with the enlargement of network scale.