Radio Resource Management And Broadcasting Protocols For Multi-radio Multi-channel Multi-hop Wireless Networks

Multi-hop wireless networks such as mobile ad-hoc networks and mesh networks, have gained increasing attention over the last few years. However, a fundamental obstacle to building large scale multi-hop networks is the insufficient network capacity when route lengths and network density increase due to the limited spectrum shared in the neighborhood. The use of multiple radios which tuned to orthogonal channels can significantly improve the capacity of the wireless network by employing concurrent transmissions under different channels, and that motivates the development of new protocols designed for multi-radio multi-channel networks. In this dissertation, we will investigate the issues of radio resource management and broadcasting schemes for IEEE802.11-based multi-radio multi-channel and multi-hop wireless networks.Radio frequency spectrum is a finite and scarce resource. How to efficiently use the spectrum resource is one of the fundamental issues in all wireless communication systems. Almost all past research work assume channels of fixed, pre-determined width. Recently some preliminary work identified the inefficiency of the static spectrum partition style and began to explore the dynamic channel width adaptation. In this dissertation, we propose to use channel width adaptation in multi-radio multi-channel networks to further improve the spectrum efficiency and network performance. First, we propose a multi-radio network architecture with the function of channel width adaptation. Then we identify several benefits of dynamically changing channel width in multi-radio multi-channel networks: providing a good balance between spectrum diversity and network connectivity, mitigating the phenomenon of conflict, contention and interference, improving channel load balance and providing QoS (Quality of Service) support. Then we propose three solutions to exploit above benefits:We mathematically formulate the optimal channel width adaptation, logical topology design and routing as a joint mixed 0-1 integer linear optimization problem and we propose heuristic algorithms based on LP relaxation. Our method can not only make a good tradeoff between spectrum diversity and network connectivity, but also can achieve spectrum load balance in a fine granularity while incurring the least interference.By reducing the optimal channel width adaptation into the―packing and compression‖problem, we devise distributed channel width assignment algorithms based on graph multi-interval coloring and max-coloring. Approximation ratios are obtained for the schemes based on graph multi-interval coloring, which aims at avoiding over-fragmentation of the spectrum, while the bound of the maximal execution time is set for the max-coloring-based algorithm, which is able to quickly adapt to traffic variation. We integrate our algorithms into the typical multi-radio multi-channel wireless mesh architecture—Hyacinth. Simulation results show that our schemes can improve network performance significantly.We propose a resource-reservation-based channel width assignment and routing protocol to provide QoS support for multi-radio multi-channel ad-hoc networks. We develop distributed on-demand resource assignment schemes that utilize the AODV (Ad-hoc On-Demand Distance Vector) routing to perform admission control and resource reservation. Simulation results show that the on-demand channel width assignment scheme can efficiently utilize the spectrum resources to provide QoS support when nodes are equipped with more than 4 interfaces.We also devise broadcasting schemes for multi-radio multi-channel and multi-hop wireless networks. Broadcasting is not only used for route discovery in reactive unicast/multicast routing protocols, but also used for data dissemination in broadband broadcast applications. So we propose multi-channel broadcast schemes for route discovery protocols and broadband applications respectively:In route discovery protocols, low redundancy is the major concern for broadcasting. So we propose low-redundant multi-channel broadcast scheme based on self-pruning strategy, by reducing the efficient broadcast problem into the minimal strong connected dominating set problem of the interface-extend graph which extends the network topology across interfaces.In broadband broadcast applications, more attention should be paid to the high-throughput schemes. So we propose an interference-aware broadcast routing and channel assignment scheme by formulating the problem as a mixed integer linear programming. Our schemes enable nodes to operate with minimum interference while the channel diversity can be fully exploited.In conclusion, we mainly investigate two issues for IEEE802.11-based multi-radio multi-channel and multi-hop networks: radio resource management with channel width adaptation and broadcasting schemes. The proposed channel width adaptation schemes can improve the network performance in many aspects while the broadcasting schemes can achieve low redundancy or high capacity.