Research On Routing And Spectrum Allocation Algorithm In Cognitive Wireless Mesh Networks

Cognitive Radio (CR) is intelligent revolutionary spectrum (channel) sharing technology and the most important new wireless technology, which can relief the scarcity of spectrum resource efficiently. Wireless mesh networks (WMNs) have been an important technology for next-generation wireless networking. Cognitive wireless mesh networks (CWMNs) are a wireless mesh network which integrates CR technology. There are potentially advantages to integrate CR into WMNs for solving the scarcity of spectrum problem. At present, the researches about CWMNs are at an early stage. There are many open challenges in CWMNs.Routing algorithm is one of the hot issues in the research of CWMNs. However, research results of routing in WMNs cannot be applied to CWMNs directly. Because there are some differences about the usability of channels between WMNs and CWMNs. Firstly, the mesh nodes in WMNs work with the fixed channels, but the CR-Mesh nodes in CWMNs work with the dynamic variable channels because of the randomicity of channels used by primary users. Secondly, the CR-Mesh nodes in CWMNs using the spectrum hole must ensure that the communications of primary users are not interfered, and the problem of routing and channel allocation must be considered jointly in CWMNs. It is not needed in WMNs. The unicast routing and channel allocation which is aim at maximizing the accept ratio of wireless service and minimizing the average end-to-end delay, and multicast routing and channel allocation which is aim at minimizing the total channel conflict, balancing the load of network and minimizing the end-to-end delay are studied deeply in this thesis. The main work and contributions are presented in the following aspects:(1)Aim at the problem of no available channel for a single route constructed by routing algorithm in CWMNs, we propose the centralized unicast multi routes construction and channel allocation algorithm.A self-adaptive joint routing and spectrum allocation algorithm (SA2JR) with QoS constraints in CWMNs was proposed. Maximizing the accept ratio of wireless service is the objective of SA2JR under the QoS constraints. The SA2JR algorithm contains K-Routing and QDSA algorithm. The K-Routing algorithm produces K paths for each wireless service. QDSA algorithm takes charge of maintaining a feasible path from the K paths which produced by K-Routing algorithm. Simulation results show that SA2JR algorithm can achieve expectation goal. It can achieve a higher accept ratio.(2)Aim at the difference of available channel for each CR-Mesh nodes, we propose the distributed unicast routing and channel allocation algorithm based on node cooperation.The decrease in average end-to-end delay with node cooperation is analysed through instance. A distributed routing and spectrum allocation algorithm with cooperation (DRSAC_W) in CWMNs is proposed. In order to show the decrease of the average end-to-end delay with cooperation in DRSAC_W, a distributed routing and spectrum allocation algorithm without cooperation (DRSAC_WO) is proposed. Minimizing the average end-to-end delay is the objective of DRSAC_W and DRSAC_WO. Simulation results show that the proposed algorithm DRSAC_W with cooperation can alleviate the high delay due to the heterogeneity available channels of different nodes, and achieve low average end-to-end delay.(3) Aim at the difference of available channel for each CR-Mesh nodes, we propose the centralized multicast routing and channel allocation algorithm with QoS constraints.A framework of solving the joint problem multicast routing and channel allocation, which contains problem description, representation of solution, fitness function, spectrum allocation algorithm, is proposed. Two algorithms for joint multicast routing and spectrum allocation with end-to-end delay constraints based on intelligent computation are proposed. The first one is multicast routing and spectrum allocation algorithm based on genetic algorithm (GA-MRSA). The second one is multicast routing and spectrum allocation algorithm based on simulated annealing algorithm (SA-MRSA).The object of the two algorithms are minimizing the total channel conflict. And, under the condition of getting lower total channel conflict number, the number of used channel is also a few. Simulation results show that our two algorithms can achieve expectation goal. It can achieve a lower total channel conflict number.(4) Aim at the no load balancing for CR-Mesh nodes, we propose the centralized load balancing multicast routing and channel allocation algorithm. A load balancing wireless links weights computing function and computing algorithm (LBWC) are proposed. On this basis, a load balancing joint multicast routing and spectrum allocation algorithm with QoS constraints in cognitive wireless mesh networks (LMRS2A) is proposed. Balancing the load of network and minimizing the number of transmission of multicast tree are the objective of LMRS2A under the QoS constraints. Firstly, LMRS2A computes the weights of wireless links using LBWC for constructing the load balancing multicast tree. Secondly, LMRS2A uses the algorithm LMRS2A with QoS constraints allocating channel to links which is based on the Wireless Broadcast Advantage (WBA).Simulation results show that LMRS2A algorithm can achieve expectation goal. It cans not only avoiding the congestion of node, but also needing lower number of transmission of multicast tree.(5) Aim at the difference of available channel for each CR-Mesh nodes, we propose the distributed multicast routing and channel allocation algorithm, and the distributed multicast scheduling algorithm.Firstly, the potential heterogeneity in channel bandwidth and delay of channel and the effect among different multicast sessions is considered. The problem of multicast routing and spectrum allocation from CR-Mesh gateway to access CR-Mesh router is studied. With the objective of minimizing the end-to-end delay, a QoS constraints distributed multicast routing algorithm based on dynamic programming (D2MRA) is proposed. The CR-Mesh nodes are mapped into stages, the available channels of CR-Mesh nodes into states. Simulation results show that the proposed algorithm D2MRA can achieve low end-to-end delay time comparing with the algorithm OMRA. Secondly, the problem of multicast routing and spectrum allocation from access CR-Mesh router to CR-Mesh client is studied. We are aim to solve the problem of multicast scheduling between the CR-Mesh route and CR-Mesh client. The multicast time of wireless service is becoming longer on account of the heterogeneous of channel for CR-Mesh route and CR-Mesh client. The goal is to minimize the multicast time of wireless service. A distributed assistance multicast scheduling algorithm (DAMSA) in CWMNs is proposed. The multicast time of wireless service reduces through the assistance of nodes which belong to or do not belong to the same multicast group. Simulation results show that the proposed algorithm not only can achieve low multicast time, but also can increase the throughput of system.