【作者】 邝祝芳；

【导师】 陈志刚；

【作者基本信息】 中南大学 ， 计算机科学与技术， 2012， 博士

【摘要】 认知无线电技术(Cognitive Radio, CR)是一种能够有效缓解频谱(信道)资源缺乏的重要技术之一。无线Mesh网络作为下一代宽带接入系统,将认知无线电技术应用于无线Mesh网络中解决其频谱缺乏的问题具有潜在的优势。目前认知无线Mesh网络(Cognitive Wireless Mesh Network,CWMN)仍然处于研究的早期阶段,面临许多开放性的挑战。路由算法是直接影响CWMN吞吐量、端到端延迟的重要因素之一,而无线Mesh网络中已有的路由算法无法适用于CWMN。其一,在无线Mesh网络中,各Mesh节点工作在固定信道,而在CWMN中,由于主用户占用信道的随机性,CR-Mesh节点的可用信道是动态变化的；其二,在CWMN中,CR-Mesh节点使用信道必须保证不对主用户的正常通信产生干扰,并且路由与频谱分配问题必须联合考虑,而在无线Mesh网络中不是必须满足的。本文分别以提高无线业务接受率、降低端到端延迟为目标对CWMN中的单播路由与频谱分配问题开展研究,以及分别以降低信道冲突数、节点负载均衡和端到端延迟为目标对CWMN中的组播路由与频谱分配问题开展研究,主要工作如下：(1)针对CWMN中路由算法构造的单条路径可能没有可用信道的问题,提出了集中式的自适应单播多路径构造与频谱分配算法。本文提出了自适应的满足QoS约束的单播路由与频谱分配算法SA2JR,目标是最大化无线业务接受率。SA2JR包括两个部分,按需的K-路径路由算法K-Routing,以及QoS驱动的频谱分配算法QDSA。K-Routing负责为每一个需求产生K条潜在路由路径,QDSA算法自适应的进行频谱分配,目标是从K-Routing产生的K条潜在路由路径中找出一条满足QOS约束的可行路由路径。仿真结果表明SA2JR能达到预定目标,获得较高的无线业务接受率。(2)针对CWMN中各CR-Mesh节点可用信道的差别,提出分布式的基于节点协作的单播路由与频谱分配算法。本文通过实例分析了通过节点协作可以有效的降低平均端到端延迟,提出了基于节点协作的分布式单播路由与频谱分配算法DRSAC_W,为了说明DRSAC_W算法通过节点协作可以降低平均端到端延迟,提出了非协作的分布式路由与频谱分配算法DRSAC WO,目标是最小化无线业务的平均端到端延迟。仿真结果表明,DRSAC_W算法通过节点的协作可以有效的缓解不同节点可用信道异构带来的高延迟,能达到预期目标,获得较低的平均端到端延迟。(3)针对CWMN组播树中各无线链路的信道冲突问题,提出了集中式的满足QoS约束的组播路由与频谱分配算法。本文首先提出了针对该问题的求解框架,包括问题描述、解决方案的表示、适应度函数、以及频谱分配算法。然后,基于两个具有代表性的智能计算方法：遗传算法、模拟退火,提出了两个满足端到端延迟约束的组播路由与频谱分配算法GA-MRSA和SA-MRSA。目标是最小化组播树总的信道冲突数。仿真结果表明,GA-MRSA和SA-MRSA算法能够达到预期目标,获得较低的总的信道冲突数。(4)针对CWMN组播树中各CR-Mesh节点负载的不均衡问题,提出了集中式的负载均衡组播路由与频谱分配算法。本文提出了负载均衡的无线链路权值函数及计算算法LBWC,在此基础上,提出了满足QoS约束的负载均衡组播路由与频谱分配算法LMRS2A,目标是在满足QoS约束的情况下,不仅均衡化网络的负载,而且最小化传输次数,优化网络资源的使用。LMRS2A算法首先采用LBWC算法计算无线链路的权值,进行负载均衡的组播树构造,然后采用基于无线广播特性的QoS约束频谱分配算法WBA2S对无线链路进行信道分配。仿真结果表明,LMRS2A能达到预定目标,不仅避免了拥塞节点的产生,而且仅需要较少的传输次数。(5)针对CWMN中各CR-Mesh节点可用信道的差异,提出了分布式的组播路由算法,以及分布式的组播调度算法。本文考虑信道之间的差异,以及多个组播会话之间的影响,首先,研究从CR-Mesh网关节点到接入点CR-Mesh路由器的分布式组播路由路径构造与频谱分配问题,提出了基于动态规划(Dynamic Programming,DP)的分布式组播路由算法D2MRA,目标是最小化组播业务的端到端延迟。仿真结果表明,D2MRA算法相比OMRA能获得比较低的端到端延迟。然后,研究接入点CR-Mesh路由器到CR-Mesh终端节点的分布式组播调度问题,提出了基于节点协作的分布式组播调度算法DAMSA,通过同组成员或者其他组成员的协作达到降低组播时间的目的。仿真结果表明,DAMSA算法不仅降低了无线业务的组播时间,而且提高了系统的吞吐量。更多还原

【Abstract】 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.更多还原