Research On Channel Assignment And Routing Algorithms In Wireless Networks

Wireless mesh networks are comprised of a number of wireless routers and wireless access points which are connected to each other in a multi-hop manner. It has emerged as one of the promising solutions for next generation wireless networks because it could provide high-speed data rate, enlarge wireless service coverage area and reduce the network installation cost. The transfer rate of wireless links could be decreased by interference, so using non-overlapped channels for data transfer is an efficient way to lessen link interference. Different numbers of non-overlapped channels are defined in IEEE 802.11a/b/g standards and the network throughput could be increased effectively by utilizing those channels. Research on how to increase the throughput of wireless mesh network is of great significance.Based on IEEE 802.11 MAC protocol, the research work presented in this dissertation is mainly focused on how to improve the throughputs of wireless mesh networks.Firstly, considering the problem that current central channel algorithms have the scalability problem in large scale wireless mesh networks, a new link-load based distributed channel assignment algorithm (LLDCA) was proposed to assign channels to links. This algorithm constructed link conflict graph firstly in distributed way by exchanging the local link load information within its k-hop neighbors in the wireless network and then assigned channels to links according to the link load priorities in link conflict graph. Links that did not interference with each other could select channels concurrently, so the running rounds of LLDCA had been significantly reduced. Theoretical analysis shows that for any given positive integer t, LLDCA could finish in O(log n) + t + 1 rounds with probability higher than 1-(D/D + 1)^t-1 where n is the number of links whose loads are positive number in the network and D is the maximum node degree in the link conflict graph, and the message complexity of every link in this algorithm is O(D). Simulation results show that this distributed algorithm has nearly the same performance as the central channel assignment algorithm proposed by Ashish Raniwala et al and it could improve the network throughput by a factor of three when comparing with Group CA algorithm.Secondly, a new performance evaluation model for channel assignment algorithms was proposed based on "conflict link bandwidth occupation rate". The impact of channel assignment result on each link was quantified by computing the channel bandwidth occupation rate of each link in its conflict area. This model could evaluate the performance of different channel assignment algorithms. Based on this evaluation model, a new algorithm was proposed to improve the static channel assignment algorithms by using topology control strategy. A decision was made by using this model before assigning a channel to a link. Simulation results show that this algorithm could improve the network throughput by a factor of 10% than LLDCA when the network consists of heavy-load and light-load links at the same time.Thirdly, considering the problem that the transfer rates of some nodes may be decreased due to their channel switching sequences being plenty of collisions with that of their neighbors, a distributed algorithm was proposed to generate channel switching sequences in hybrid mesh networks. A new sequence was generated in each round using random permutation method according to the node's current switching sequence and it distributed the sending collisions among different node-pairs, so the useful bandwidth of every node was effectively balanced. Every node generates new sequences independently without any negotiation with its neighbors. This algorithm is insensitive to topology change, so it is convenient for nodes to join or leave the network dynamically. The algorithm's running time is linear to the number of orthogonal channels in the network, so a real-time new sequence generation is guaranteed. Experimental results show that this algorithm could effectively improve the node's minimum useful bandwidth by a factor of more than 30% and improve the network total throughput by a factor of 5%～15% when the network load increases to 75% of its capacity.Fourthly, by utilizing the load information of mesh nodes in hybrid channel assignment strategy, a load-balanced distributed channel assignment algorithm (LBCA) was proposed in this paper. A local node conflict graph was constructed in a distributed way and those heavy loaded nodes were assigned to light loaded channels by LBCA algorithm. In this way, the loads of every channel were balanced. Simulation results show that the network throughput could be improved by a factor of above 10% than that of state-of-art algorithms in mesh networks with no more than 6 channels when the network load increases to 80% of its capacity.Fifthly, a new joint routing and channel assignment algorithm using "cross-layer" method was proposed to optimize the network performance when the number of flows in the network was not large. The shortest path was discovered firstly using the current available routing metrics and then new different channels were assigned to those links. In this way, the interference on that path was minimized and the transfer rate was increased. Simulation results show that this algorithm could improve the network throughput by a factor of 10%～20% comparing with other state-of-art algorithms when the percentage of the summation of source and destination nodes is no more than 50%.Finally, a new network topology for organizing wireless mesh network was proposed to improve the network throughput when the network contains massive intra-mesh and inter-mesh flows simultaneously. The network was divided into two parts: the static mesh zone in which channels were assigned to mesh nodes statically and the dynamic mesh zone in which the channel assignment strategy was hybrid assignment method. A new routing algorithm was also proposed for the new network topology organization by combining proactive and reactive protocols. Simulation results show that the network throughput could be improved by a factor of 15% above comparing with tree topology and hybrid topology when the channel number of the network is 12 and the amount of inter-flow is of 60%～80% of the total network flow load.