Routing Algorithms For Wireless Mesh Networks Based On Forest Topology

Wireless network technology develops rapidly nowadays. Various IEEE 802.11 standards are constantly being updated. New wireless network architecture and technology are being proposed. Wireless mesh network,with large capacity, high speed and wide coverage integrates the advantages of wireless LAN and Ad hoc network. Meanwhile, the hierarchical topological structure of wireless mesh network,with the properties of high reliable transmission, good scalability and low upfront investment, has an expansive application propects.In the wireless mesh network, network topology, channel assignment and routing establishment interact. Many channel assignment algorithms and routing algorithms depend on network topology to a certain extent, and they in turn affect topology, making it change. Based on the deep analysis of the research about the related fields both at home and abroad, this dissertation proposes a relatively completely-designed cross-layer scheme from network topology to routing algorithms. The main contents include the following three aspects:1.Construction and maintenance of wireless mesh network forest topologyChannel assignment and load-balancing routing algorithms are based on the construction of wireless mesh network topology. To construct a wireless mesh network topology which is of high connectivity and is helpful for channel assignment and routing algorithm is a problem deserving of study. As the actual wireless mesh networks often have multiple gateway nodes through which the nodes complete external network access, a tree topology is formed with each gateway node as the root. The key issue to be discussed in this part is how to effectively select the gateway node to join. When establishing a forest topology, such factors as reliability rate, link quality, delay and interference should be considered, thus a criterion is required to ensure the acceptance and rejection of relevant links.Aiming at the above-mentioned problems and the bottleneck to network throughput performance in the gateway caused by most of the flows of wireless mesh network going to the internet just through a small amount of gateways after gathering at the backbone routers, the concept of link reuse degree is introduced to reduce routing overhead and attain efficient traffic aggregation. Based on the method of SPT, two different algorithms of BLBFSP and BMFSP are proposed to realize the algorithm through different perspectives of defining the network load.In addition to the consideration of the hops from gateway node, BLBFSP algorithm takes advantage of the role of the boundary nodes between multiple gateway nodes to achieve partial load balancing in the internet. Responding to the complex network invironment,BMFSP algorithm propsoed a way of building forest topology that takes link quality as accession criteria, taking inot account of such comprehensive factors as the number of node layers. The results of the simulation experiment and the performance comparison with the method of SPT indicate that the two algorithms can effectively deal with different network environments and then improve network performance.2.Multi-channel assignment in wireless mesh networkThe prior channel assignment algorithms are designed for single channel or single transceiver. Mult-channel and multi-radio has a clear advantage in improving network performance, but multi-channel assignment in wireless mesh network is not only a classical but a NP hard problem. There have been some similar heuristic algorithm to solve this problem. Such factors as interference, flow and throughput should be considered comprehensively when considering multi-channel assignment. How to choose an efficient channel assignment criterion to distribute channels is a matter of concern. The basic objective of channel assignment is to try to reduce interference.For multi-channel and multi-transceiver wireless mesh network, channel assignment strategies have an important effect on reducing link interference and improving transmission rate. By analyzing the interference existed in wireless mesh network and the characteristics that there is no conflict when multiple wireless links transmit data simultaneously through Orthogonal channels, this dissertation proposed the concept of isolation, an important judge criterion of channel assignment. It is found that the wireless interference between links rests not only on the physical distance between links but also on the separation of the channel assigned to two links.Existing multi-channel assignment algorithms and protocols basically don’t consider the separation of the wireless channels, which will result in a path interference. Channel separation based heuristic multi-channel assignment algorithm(CSCA) is proposed, with comparison to the performance of CCA and the Load-Ware CA algorithm through simulation experiment. The results show that CSCA algorithm effectively reduces the interference in wireless mesh networks and improve the network throughput.3. Study on flow and load balancing routing algorithm in wireless mesh networkIn the wireless mesh network, all nodes share the network resources by routing protocols. Therefore, the wireless mesh network routing protocols should meet the requirement of load balancing. Many new routing criteria and algorithms existing in traditional wired networks an the Ad Hoc network can not be directly applied to wireless mesh networks, so how to design a routing criterion which can dynamically adapt to current newtork topology and flow changes and select the most stable and least congestion link to establish a route is very important.Round trip time delay to the node (RTT) as a performance criterion met to some extent, the purpose of load balancing. However RTT is not valid for all situations because it is affected by the quality of links.A typicall load-balancing routing protocol is a routing algorithm which is for the communication between nodes within a network, the source node and destination node are within the same network. Therefore, the load balancing algorithm focused on the consideration of the flow balance between nodes within the same network without considering the flow balance btween various gateways. The major business of the wireless mesh network is the flow which comes from and goes to the internet, so the load balancing between different gateways has to be considered. Therefore, we should design appropriate load balancing routing algorithm according to the features of wireless mesh network.For these above-mentioned problems, this dissertation put forword a new dynamic adaptive channel load-aware metric to solve the link load imbalance caused by the interference within and between the flow in original multi-channel environment by comprehensively considering the effects of available bandwidth, time delay, reliabillity and interference on the link load in the multi-channel environment. Load balancing routing algorithm is designed on the basis of AODV-MR algorithm.Throough simulations and comparing with the algorithms with WCETT and Hop-count as the metric, the results show that LBRP algorithm is superior in grouping delivery rate, delay cost tand routing cost, so as to optimize the performance of wireless mesh networks.