Algorithms For Jointing Routing And Channel Assignment In Wireless Mesh Network

Wireless mesh network(WMN) is a new broadband, distributed multi-hop wireless network. WMN is gradually growing its many advantages as an important access for wireless network and gradually becomes the important method to solve the"last mile"access for the Internet. It contains mesh routers and terminal nodes. The mesh router nodes in WMN, have to find routing paths, and allocate channels to the paths before they communicate with each other. Therefore, routing and channel allocation become two key technologies in WMN.This paper considers both routing and channel allocation in WMN. According to the routing traffics in the routing process, we simplify and transform the network topology graph, and gain the effective links with their frequency of use. In the channel allocation process, we group the efficient links and allocate channels to links. The joint of the two technologies, not only meet the routing requirements and ensure the throughput, but also simplify the channel allocation process with improving the channel utilization and avoiding channel interference.The strategy of this paper in the routing process is that firstly, this paper propose that traffic flows should be divided in the time slots and then transform the routing problem of multi-radio and multi-channel into the problem of multi-commodity flows and accomplish the routing paths for each traffic flows from source to destination, while source nodes and target nodes maybe various in different traffic flows. Finally, we simplify and transform the network topology graphic, obtaining effective links sets with their frequency of use. By the transformation, we record a new graph with the links in the original graph as the vertex in it, and if the links are adjacent in the original graph, there will be an edge between the two vertexes in the new graph.The strategy of this paper in the channel allocation process is that, according to the interference model, the algorithm is proposed to remove the interference vertexes-pairs with the effective links from the Cartesian products of the vertexes. And we will get vertexes-pairs with interference-free in K hops. Through an exhaustion method, we group the vertexes (links in the original graph) in the vertexes-pairs above. But the exhaustion method has a high time complexity and a high solution space complexity. Then we designs two approximation algorithms for grouping the vertexes. Using the algorithms, we will achieve some different groups, and the vertexes in the same group are interference-free. That is to say, the effective links with interference-free have assigned to the same group and the effective links with interference have assigned to different groups. Finally, we allocate the channels to the corresponding effective links using some simple scheduling.Experiments result show that, the algorithm of this paper jointing routing and channel allocation can obtain a better network throughput with interference-free within K-hops.