Design And Simulated Implementation Of Joint Scheduling And Routing Optimal Algorithm In Multi-Radio Multi-Channel Wireless Mesh Networks

Wireless mesh network (WMN) is a promising solution for low cost last mile broadband Internet access because mesh nodes and mesh routers are connected via wireless links to form a multi-hop backbone infrastructure. Different from Ad-hoc network which mainly concerns about mobility and energy consuming, throughput is primary goal in WMN. Many technologies to construct high throughput WMN have been proposed, such as routing metrics, multi-radio and multi-channel technology, power control based on scheduling algorithms, load balancing, cross-layer design, etc.In this thesis, the joint scheduling and routing optimization algorithm is studied in multi-radio and multi-channel WMN. By considering the wireless media contend and the spatial multiplexing, two objectives in algorithm are addressed. The first one is to ensure the fairness among different links so that each node can obtain equal throughput. Thus, each links need to be activated for equal time. The second objective is to maximize throughput by exploiting spatial reuse. The idea is that different links can be activated in the same time slot when there do not exist interference among each other.Firstly, a traditional algorithm combining Time Division Multiple Access (TDMA) scheduling and Bellman-Ford routing protocol is proposed. Since the shortest path is prefered in this algorithm to deliver packets which may frequently cause the congestion and decrease throughput sharply. Furthremore, in traditional TDMA scheduling algorithm, the time slot is just distributed to each node according the node and radio number regardless of whether there are packets needing to be forwarded or not, and then network resources may be wasted. Thus, in this thesis an Expected Transmission Time (ETT) metric is proposed and a Heuristic algorithm based on Link Scheduling and ETT routing metric (HLSE) is developed. In HLSE, the route can be selected on network layer based on ETT metric and the network fairness can be enhanced by allocating higher priority to the links with smaller congestion. At last, through cross-layer joint optimization for scheduling metric in MAC layer and routing metric in network layer, a Joint Scheduling and Routing Optimization Algorithm (JSRO) is proposed to increase the throughput and ensure the fairness.To evaluate the performances of proposed algorithms, the simulation is implemented based on Qualnet5.0. Simulation results demonstrate that JSRO not only can significantly increase the throughput but also can improve the fairness for network resource assignment by52%and23%compared with traditional TSBF and HLSE respectively.