Research On Routing And Partially Overlapped Channel Assignment For Multi-radio Multi-channel Wireless Mesh Networks

Wireless mesh networks(WMNs), which can extend the coverage of current wireless networks, draw close attention from academic community and industry in recent years. They are key networking technology to construct broadband wireless access networks.Capacity is a major concern in WMNs, and its decay with increased interference is very fast. Efficient routing and channel assignment strategies are effective solutions to solve this problem, and they can dramatically improve the whole network performance. Efficient channel assignment scheme can guarantee that adjacent nodes who want to communicate with each other operate on the same channel. Efficient routing selection strategy can select the best routing path which satisfies the end-to-end quality of service requirement from many available paths between the source and destination. Channel assignment decides the interference faced by nodes in communication and the set of available routing paths; Routing metric is the basis for route calculation and selection. The designing functionality of proper routing metric directly decides the routing paths, and it has great influence on the performance of the whole network. There are unicast and multicast two types of communication manners between nodes in WMNs, therefore the characteristics of unicast and multicast should be taken into full consideration during the design of routing and channel assignment strategy, so as to take full advantage of WMNs.Current research on routing and channel assignment for WMNs has made certain progress, but there still exists imperfections, including: as orthogonal channels are assigned to adjacent transmitting nodes, the resulting co-channel interference prevents them from parallel transmissions and network throughput decreases; Field measurement is exploited to estimate the interference ranges of partially overlapped channels(POCs), which leads to weak transportability of the measurement results; Channels are only assigned to backbone links, and access links are left out of consideration, therefore the channel assignment results obtained cannot be applied to end-to-end flow data transmissions; In routing metric design, single traffic type is considered only and gateway selection is neglected, besides, adjustable parameters are introduced due to independent description of various kinds of interference; Multicast routing and channel assignment schemes are designed for WMNs with only one multicast session. In this case, network resource is optimally used for single session and network load balance is omitted.Aiming at solving the problems stated above and improving network performance, in this dissertation, channels which are partially overlapped with each other are exploited to perform routing and channel assignment in WMNs. The route and channel selection for data flows is solved from unicast routing metric design and POCs channel assignment, multicast routing and POCs channel assignment perspectives according to the characteristics of POCs WMNs. The routing and channel assignment strategies proposed in this dissertation can choose proper routing paths and assign reasonable channels for unicast and multicast data flows, and help to achieve high-throughput data transmissions. The main innovations of this dissertation can be summarized as the five points listed below:(1) Theoretical derivation is utilized to calculate POCs interference ranges, and it can conquer the inaccuracy and weak transportability problem of field measurement. Two-ray ground propagation model is used to simulate the path loss of signal in open space environment, and normalized convolution of the power spectrum density of the sender and receiver is used to quantify the reduction of POCs interference ranges. POCs interference ranges for ideal transmit spectrum mask and raised cosine FIR filter with different rolling-off factors are obtained. From the derivation results, we can see that POCs interference ranges get smaller with the increase of channel separations, which is the basis for the application of POCs.(2) End-to-end partially overlapped channel assignment schemes are proposed, and they can achieve efficient end-to-end data transmissions. Links are sorted by Rank which comprehensively considers about link position, link load and the number of neighboring interferers, and links with higher probability of congestion are given priority to be assigned with channels. Backbone links and access links may use channels in the same frequency band or distinct frequency bands. Neighbor-to-interface binding is done according to node degree or link load, and it determines which interface is used to communicate with neighbors; Interface-to-channel binding is done with the goal of minimizing total network interference, and it determines which channel is used to communicate with neighbors. If there are enough orthogonal channels to eliminate interference among backbone links, POCs should be avoided. Otherwise, POCs can be fully utilized to promote parallel transmissions.(3) Uniform description of interference based routing metric for multi-gateway WMNs is proposed, and it can solve the route selection for data flows in POCs WMNs. Equivalent bandwidth is defined to capture the effect of logical inter-flow interference, logical intra-flow interference and physical interference on data transmissions accurately, and it can simplify the metric formula. According to the traffic types, different metric formulas are used to guide data packets to route through the best gateway and the best routing path. The effect of gateway on route selection is taken into account to avoid the creation of capacity bottleneck around the gateway and the decline of network serving capability.(4) Multicast weighted conflict graph is proposed to model POCs interference in hybrid traffic scenario. It regards the links originating from the same node as one transmission and gives full consideration of wireless broadcast advantage; It uses link weight to measure the interference degree between links and gives full consideration of interference characteristics of POCs.(5) Binary integer programming construction and heuristic scheme for joint multicast routing and partially overlapped channel assignment in hybrid traffic scenario are proposed, and they can balance network load and optimize the utilization of network resource from traffic management perspective. Node load balance and channel load balance are introduced during the programming construction, and they can help to avoid the case in which some links are heavily congested and other links are underutilized. The optimal solution from the programming is benchmark to evaluate other centralized or decentralized schemes. Heuristic scheme continuously searches for the minimum-cost path to construct multicast tree from all available routing paths between uncovered multicast receivers and the multicast source, and it also assigns channels for links on the selected path. Until all multicast receivers are connected with the multicast source, the heuristic scheme stops. It can find near-optimal routing and channel assignment results within poly-nominal time, and it can be applied in practice.In this dissertation, we deeply research on routing and POCs channel assignment problem for WMNs, and propose routing and channel assignment schemes which utilize POCs to improve network performance for unicast and multicast communications. These schemes can conquer the limitations of current research results and realize effective end-to-end communications. The research results in this dissertation can help improve overall network performance and promote the application of POCs in WMNs.