Resource Allocation In Wireless Mesh Networks

Wireless mesh networks are wireless multi-hop networks in which wireless mesh routers and user terminals are connected each other. Wireless mesh networks are easy to be set up at low cost, and have a flexible organizational structure and coverage, and have a strong scalability. They will become efficient alternate solutions of wired backbone networks in cities. Since the design goal of wireless mesh networks is to provide user terminals with high-speed Internet access, it is very significant to introduce resource allocation policies for meeting uses'traffic needs. Considering the overall optimization, the joint optimization of different modules such as routing and link scheduling can reduce design complexity and further improve resource utilization. In this thesis, joint optimization methods of resource allocation policies especially for routing, link scheduling and power control in wireless mesh networks is focused, and decomposition methods and appropriate resource allocation algorithms are proposed.Firstly, the joint optimization problem of routing and link scheduling in wireless mesh backbone networks with beam control is researched to minimize the total scheduling time. In this thesis, the fact that the joint optimization problem is NP-hard is pointed out. Then, a decomposition method of the joint optimization problem is designed, and the original problem is decomposed into a routing child problem and a link scheduling child problem. For the routing child problem, a linear programming solution is adopted. For the link scheduling child problem, a shifting and switching based scheduling algorithm is proposed. We prove that the final result by solving child problems in order is not more than the optimal value of 1.5 times of the original problem, even if the power allocation problem for OFDM technology is introduced. Simulation results show the asymptotical optimality of the proposed algorithm as the ratio of the number of mesh routers and that of wireless gateways increases.Secondly, we considered the joint optimization problem in wireless backbone mesh networks without beam control. It is NP-hard to jointly optimize routing and scheduling to maximize the efficiency of spectrum. Based on heuristic thought, a modified routing algorithm considering uses'traffic, average path capacities and links'interference is proposed. For convergent traffic to gateway, an algorithm considering link correlation in the bottleneck maximal clique is proposed to greedily search independent link scheduling sets. An alternate policy is designed for the routing module and the link scheduling module. In high interference networks, the designed policy is proved to be optimal. Simulation results show that for a variety of distributed nodes and interference circumstances, the proposed algorithm can greatly improve system spectrum utilization.Finally, in a peer-to-peer wireless mesh network, it is focused to jointly optimize routing, scheduling, and power control to maximize system power efficiency. A method decomposing the overall optimization problem into single-node optimization problems is designed. For low SNR circumstances, the proposed decomposition method achieves not more than twice optimal value of the original problem. For every single-node problem, it can be further decomposed into routing, power control and link scheduling child problems, and appropriate distributed algorithms with low complexity are proposed. The optimality of proposed routing algorithm and link scheduling algorithm is proved in low SNR cases. Simulation results showed that the proposed algorithms can improve system power efficiency for various network topologies.Resource allocation policies of joint optimization can make efficient use of scarce spectrum resources and system power and further improve system performance. In this thesis, the researches and contributions have reference significance to the resource allocation method and protocol design in wireless mesh networks.