Research On Resource Scheduling Algorithm And QoS Guaranteeing Mechanism Of Wireless Mesh Networks

Wireless Mesh Network, WMN, is an extension to the mobile Ad Hoc network, both in network architecture and communication mechanism. The current achievements in the research of Ad Hoc Network and IP Network can not be used in WMN. There are some open issues in network architecture, capacity, physical layer, MAC layer, resource scheduling, routing protocol and QoS guaranteeing mechanism. And these issues are critical to the deployment of WMN at large scale.There are some problem in the field of resource scheduling and QoS guaranteeing for the mainstream of WMN, WiMAX Mesh Network. The IEEE 802.16 mesh mode has defined three different scheduling schemes to manage the minislots in the data subframe, i.e., centralized scheduling, uncoordinated distributed scheduling, and coordinated distributed scheduling, but the IEEE 802.16 neither explain them in detail, nor give any guideline for the stability and robustness of network. And it does not cover the problem of deploying new network technology, for example OFDMA, in WiMAX Mesh Mode. As to QoS guaranteeing, though the IEEE 802.16 defines some QoS Class and guaranteeing schemes for WiMAX Point to Multipoint Mode, there is no counterpart for WiMAX Mesh Mode. Since its character of multi-hop, it is difficult to support end-to-end QoS in WiMAX Mesh Network, and it has turned out to be an obstacle for the deployment.In this dissertation, we firstly analyze the current achievements in resource scheduling and QoS guaranteeing for WMN, then advance a series of algorithm and guaranteeing mechanism to improve the wireless resource utilization and end-to-end QoS guaranteeing, based on the character of WiMAX Mesh Network. The main research work and achievement of this dissertation includes:(1) The technical principle of mainstream of WMN, including WiFi Mesh and WiMAX Mesh, was studied systematically. We made thorough investigations in the field of network architecture, capacity, physical layer, MAC layer, resource scheduling, routing protocol and QoS guaranteeing mechanism. And this is the theoretical basis of our research.(2) The character of traffic in WiMAX MESH Network is analyzed, and a predicting method based on wavelet transformation and AAR model, WARPA, is proposed. To allocate bandwidth in WiMAX Mesh Network dynamically and efficiently, we need to predict the real-time traffic volume correctly, which will be sent to the Mesh scheduler. The Mesh scheduler will grant bandwidth to each Mesh node according to the value. In our study, the current predicting method, including ARMA, is found to be not so proper for using in WiMAX Mesh Network. With our predicting method, the noise of traffic volume with wavelet transformation is decreased, and the result is fed into the AAR model, which will adjust the model argument automatically, to do the predicting job. To verify the algorithm, we used the traffic volume data captured in Auckland college into the model. It is found that the algorithm is about 2 percent more accurate than the AARMA model. The simulation result showed that our method has more precise prediction and less computation time, and is more suitable for WiMAX Mesh Network.(3) Based on achievement (1), we consider the scheduling efficiency, throughput and robustness for WiMAX Mesh Network. We analyze the scheduling mechanism of WiMAX Mesh Network and point out problem of current backhaul network structure. We proposed a new WiMAX Mesh network topology with multiple BS as egress, and propose an efficient optimal scheduling algorithm, MEMSA, for this new network topology. The detailed procedure for deploying this algorithm is described as well. We developed a simulation platform to verify this algorithm in WiMAX Mesh network with 20 and 50 MESH SS nodes respectively. The simulation result shows that our algorithm improves the efficiency more than 53 percent. We also illustrate that the bottleneck problem of the backhaul network can be solved by our scheduling algorithm.(4) Although OFDMA is a candidate physical layer protocol for 802.16, there are few solutions for the wireless resource-allocating problem in OFDMA mesh network. We study the current resource allocation methods in OFDM and OFDMA network, and introduce the architecture of OFDMA mesh network. We build a mathematic system model for the OFDMA mesh network, and propose a sophisticated ACO-based algorithm for wireless resource allocation, AWRAA. With our algorithm, we get acceptable solution, while fulfilling power and QoS constraints. Since our algorithm is easy to adapt to more realistic problems, it turns out to be a feasible method. The simulation result showed our algorithm is able to find a sub-optimal answer for resource allocation in OFDMA mesh network.(5) Since the IEEE 802.16 Specification has not defined how to guarantee QoS in WiMAX Mesh Network, it became a critical problem for deployment. We analyzed several existing WMN QoS guaranteeing mechanisms, and found they have some limitation and could not guarantee QoS in WMN very well. We advanced an effective and dynamic QoS-Guaranteeing algorithm, WMNQGA, for WMN, which described the traffic handling method of each node in view of integrity. It calculated the global optimized traffic-handling pattern for each node, and gave some constraints for the WiMAX Mesh nodes. Our algorithm can improve the network throughput, and ensure fairness. To verify our algorithm, we developed a WiMAX Mesh simulating platform and ran our simulation on it. The simulation result showed that our algorithm is effective and feasible.(6) Though it is important for the application of WiMAX Mesh Network, the IEEE 802.16 Specification has not defined how to guarantee QoS in WiMAX Mesh Network. And most of the current related research on WMN QoS only focuses on routing Algorithm or Hop-by-Hop QoS guaranteeing. By analyzing the current status of QoS guaranteeing mechanism, we advanced a new technology named"Intelligent Tag". Based on it, we proposed a QoS-Guaranteeing algorithm for WiMAX Mesh Network, ITBQoS, which defined the ITtag handling method of each node in view of the whole network, and then we give the detailed procedure of handling the ITtag in each node. We also give some constraint on the WiMAX Mesh nodes in processing the packets. To verify our algorithm, we developed a WiMAX Mesh simulating platform and run our simulation on it. The simulation result showed that our algorithm is effective and feasible.