认知无线网络中基于主用户行为的联合路由和信道分配算法

刘婧，任品毅，薛少丽，张超

（西安交通大学 电子与信息学院，陕西 西安 710049）

1 引言

随着无线通信的迅猛发展，无线频谱资源日益稀缺。然而，实际测量数据显示在大部分时间和某些地区里无线频谱未被充分利用[1]。为了提高现有频谱的利用率，Mitola博士1999年提出了认知无线电(CR, cognitive radio)技术[2],它使得非授权用户能够感知并接入当前空闲频段。

近年来，世界各国的频谱管制部门、标准化组织以及研究机构纷纷展开了对认知无线电技术的研究。影响最大的是2003年美国国防部高等研究计划署的下一代通信计划(XG)，他致力于开发认知无线电的实际标准和动态频谱管理标准[1]。XG网络也叫认知无线网络(CRN)，能够使多个用户接入空闲信道传输数据[3]。目前，认知无线网络的研究大都集中在物理层[4～6]和MAC层[7,8]的功能上，如频谱感知技术、频谱管理技术和频谱共享技术。但对于更高层如路由层仍未有完善的研究，因为认知无线网络中频谱在时间和空间上存在间断性，使得认知无线网络中的路由设计面临很大的挑战[9,10]。

文献[11,12]提出了一种在无线Mesh网络中的路由协议和多信道分配算法并设计了一种适用于多跳通信的跨层协议架构。文献[13]针对多跳认知无线网络设计了一种在基于单个收发机的频谱感知按需路由协议。文献[14] 针对多信道认知无线网络提出了一种利用Dijkstra算法的最小传输时延的路由算法。文献[15]设计了类似于DSR协议的路由发现机制的OSDRP协议，它解决了动态认知无线网络中满足服务要求的端到端路由。文献[16]针对Ad Hoc网络设计了Gymkhana路由方案，该方案利用网络图的Laplacian矩阵估计认知无线网络中不同路径的连通性。

在多信道认知无线网络中，由于频谱资源的动态性，相邻节点可能因为工作在不同信道上而无法通信，正在通信的节点可能因为主用户的出现而中断链接[1,3]。因此，针对主用户行为引起各节点之间的可用信道集动态变化的特点，本文提出了一种在具有多信道的认知无线网络中基于主用户行为的联合路由和信道分配算法（PUB-JRCA algorithm）。该算法用呼叫模型[17,18]对主用户行为进行建模，并用模型中主用户占用授权频带的活动概率定义次级用户使用该授权频带的稳定性，寻找受主用户行为影响最小的路由并在路由回复过程中完成信道分配。理论分析证明了主用户的活动概率能反映路径中链路平均持续时间，且PUB-JRCA算法的路由选择阶段计算复杂度与网络中节点数成正比。仿真结果表明，PUB-JRCA算法在主用户行为多变和多节点认知无线网络中提高了分组投递率，降低了平均分组时延。

2 系统模型

假设在一个具有多信道的认知无线网络[19]中，有N个次级用户和M个主用户。这M个主用户有M个授权信道(c1, c2,…,cm,…,cM)。每个次级用户配备有一个传统半双工收发机（工作在公共控制信道，如802.11无线网卡）和2个用于数据传输的可调收发机。2个可调收发机可以实现同时使用不同信道进行数据转发而忽略频谱切换时延并提高网络吞吐量。为了避免共道干扰，同一条路径上的相邻链路使用不同的信道。同时在本文中假设每个次级用户能精确检测到频谱机会[4]。

文献[17, 18]的研究结果表明，呼叫模型能很好地反应主用户行为规律。在这个模型中，主用户m的传输过程服从Poisson分布（独立同分布的），它的活动持续时间均为指数分布。假设状态“1”表示主用户p工作在它的授权信道上，称为主用户忙状态。相反，状态“0”表示主用户空闲，称为主用户闲状态。设α(m)是主用户m在状态“1”的平均持续时间，β(m)是主用户m在状态“0”的平均持续时间。α(m)和β(m)都服从指数分布[13,14]。从该主用户行为模型中，可以估计出主用户m出现的后验概率为[6]

图1 具有多信道的认知无线网络

在这个网络中，节点ni与节点nj在彼此的传输范围R内并且至少存在一条可用公共信道c，那么存在一条链路e=(ni, nj)∈Ε。令Cni表示次级用户ni的频谱机会(SOP, spectrum opportunity)，Cnj表示次级用户nj的频谱机会。其信道交集Ce=Cni∩Cnj随着主用户行为发生变化。所以节点ni或者节点nj接入信道cp的稳定因子为或者，那么信道cm对于链路e基于主用户行为的稳定因子为

那么，链路e基于主用户行为的稳定因子SIni,nj为

定义 设图G=(V,E)，对G的每一条边(vi,vj)，相应地有一个数l(vi,vj)称为边(vi,vj)的权。G连同它边上的权称为赋权图[20]。

通常情况下，具有多信道的认知无线网络建模为有向连通图G(N,E)，其中N表示顶点集，E表示边缘集[19]。G(N,E)中的顶点n∈N对应于网络中的次级用户，E对应于网络中相邻两点间的链路。若网络中的两节点之间能够传输数据，那么在图G(N,E)中该两点是连通的。由上述定义，令SIni,nj为图G的顶点ni与nj的边的权，那么G连同在它边上的权称为赋权图。该赋权图G中给定一个顶点s（称为始点）及顶点d（称为终点），所谓路由问题就是在(s, d)道路集合K中寻找合适的道路k。结合网络中要求避免受主用户行为影响大的节点和对路由跳数的要求，本文提出的算法要寻找值最大的道路。

3 PUB-JRCA算法

链路质量、相邻链路的共道干扰以及主用户行为等是保证路径稳定性的重要因素。假设链路质量理想化，通过每个次级用户的多接口收发机消除共道干扰，那么链路稳定性很大程度上受主用户行为的影响，因此主用户行为对认知无线网络的路由算法设计有重要的影响。本算法针对主用户行为特点设计了一种基于主用户行为的路由和信道联合分配算法，增加认知路由的平均持续时间期望，提高分组投递率和平均分组时延。

3.1 基于主用户行为的路由算法

在多跳认知无线网络中，一条多跳路径中间的各条链路同时连通才能保证该路径的正常通信。那么，利用类似于DSR的路由发现机制[21]，从一定时间内收集到的路由请求中选择不易受主用户影响的路由。基于主用户行为的路由策略过程如下：源节点S如果有数据传输请求，它首先在网络中的公共控制信道(CCC)上广播路由请求分组(RREQ)，寻找到目的节点D的K个可能路径（令 K表示在给定时间内寻找的可达路径的数量）。目的节点D收到K个RREQ后，选择受主用户行为影响最小的路径。RREQ的结构包括如下（如图2所示）。

1) 分组类型(Type)，源节点ID(Sid)，目的节点ID(Did)，包存活跳数(TTL)；

2) 路由表(RTable)：包含路径k中的所有节点的ID，即。

3) 公共频谱机会集合(C-SOP）：前跳节点与本节点的可用信道集合。如果SOP为空集，那么本节点将丢弃该RREQ。

4) 信道记录(CRecord)：记录本节点的可用信道集。

图2 RREQ结构图

中间节点收到RREQ后，检查该节点的ID是否RREQ中目的节点ID相同，如果相同，则开启该节点的定时器，等待一段时间，收集RREQ；如果不相同，那么检查RREQ中的相关信息并判别：TTL大于零；RTable不包含该中间节点的ID；C-SOP与CRecord存在交集，3个条件均满足时将该节点的相关信息写入RREQ中。例如：将本中间节点的ID写入RTable中；更新公共频谱机会集合C-SOP以及前向路径的稳定因子SI。处理RREQ后，中间节点将 RREQ广播至下一跳节点。直到第一个RREQ到达目的节点后，开启目的节点处的定时器，等待一段时间，收集K个RREQ。

PUB-JRCA算法从收集到的K个可达路径中选择稳定因子最大的路径，选择条件为

依据上述处理流程，PUB-JRCA算法可找到源节点到目的节点之间具有最大稳定因子的路由。

3.2 基于主用户行为的信道分配

找到源节点到目的节点之间具有最大稳定因子的路由后，目的节点知道路径上所有节点的可用信道信息，然后为每条链路分配能减少共道干扰和保证信道质量的信道。

目的节点首先分析本节点与所选定路径中的前一跳节点的可用信道集合交集，依据交集中可用信道的数量分为2种情况。

情况 1 可用信道集合交集中仅存在一条可用信道，那么分配该信道作为基本信道Cbasic。

情况 2 可用信道集合交集中存在多于一条的信道，那么依照以下方法选择基本信道Cbasic。

假定数据传输信道是瑞利平坦衰落信道，接收节点的功率为

其中，N0是高斯噪声的功率（在实际网络中，目的节点采用发射导频估计信道的信干噪比）。于是前向节点与目的节点间通过不同信道连通的链路权值为

假定每个节点的传输功率相等，那么将式(9)简化为

随后，目的节点在公开控制信道上沿着所选路径的反向路径发送包含路径信息以及基本信道的路由回复分组(RREP)。中间节点收到RREP分组后，选择中间节点与源节点端节点的信道记录中与基本信道Cbasic不同的信道集合，记为CR′，这样可以减少相邻链路之间的共道干扰。因为每个次级用户有2个可调收发机，可以给相邻链路分配2个不同信道，而不产生信道切换时延。在新的信道集合CR′中，中间节点选择具有最高 W 的信道作为通信信道，然后将该信道写入RREP中，继续转发RREP，直到RREP到达源节点。

3.3 路由维护

在多信道认知无线网络中，链路失败分为以下2种情况。

1) 由于主用户的出现导致2个次级用户之间的可用信道发生改变或者消失，从而导致链路失败。

2) 由于节点移动，离开原相邻节点的传输范围，导致链路失败。

当仅由于第1种情况导致2个次级用户的分配的通信信道Cbasic失效时，次级用户检查它们之间的公共可用信道集合 C-SOP，按照 3.2节的信道分配算法分配一条通信信道，而不是立即重启一个新的路由发现过程。这个处理步骤使得次级用户很快地适应主用户行为的动态变化，增加分组投递率。假如公共可用信道集合C-SOP为空集，则认为两点之间的链路已经失败，中间节点将产生路由错误分组(RRER)并沿着路由表源节点端路由传送 RRER。当数据传输的过程中出现第 2种情况时，中间节点无法与邻居节点通信，那么它认为该链路失败，然后产生路由错误数据分组(RRER)并沿着路由表的源节点端路径传送RRER。源节点收到RRER之后，删除到目的节点D的路由并重新启动路由发现程序。该过程类似于DSR协议中的路由维护。

3.4 PUB-JRCA算法总结

PUB-JRCA算法中，源节点在公共控制信道上发送路由请求，目的节点收到第一个RREQ后，继续收集一段时间内到达目的节点的 RREQ，利用每个RREQ中携带的各链路的稳定因子信息，根据 3.1节的基于主用户行为的路由策略选择受主用户行为影响最小的路由。然后目的节点产生RREP，在公共控制信道上沿着所选路由的方向发送RREP并且执行信道分配策略。为了减少相邻链路之间的共道干扰，中间节点选择与其后向链路信道不同的信道作为其前向链路的信道。因为每个认知节点有2个可调收发机，这种方案能避免信道切换时延。信道分配中考虑了信道质量和主用户对信道的影响。W值越大，越能保证信道的稳定性。直到源节点收到 RREP，该源节点已经找到与目的节点之间的受主用户行为影响最小的路由及相应信道。

总之，按照图3的处理流程，PUB-JRCA算法综合考虑了受主用户行为影响、共道干扰以及次级用户间干扰等因素，首先进行路由发现，然后在路由回复过程中完成信道分配，最后当出现链路失败时进行路由维护，这减少了由于主用户出现引起的分组行丢失，这样，PUB-JRCA算法完成了多信道认知无线网络中的路由和信道联合分配以及路由维护。

图3 PUB-JRCA算法

4 性能分析

4.1 链路平均持续时间分析

基于呼叫的模型中有2个重要的随机变量，主用户两次呼叫达到时间间隙和主用户每次呼叫持续时间均服从独立指数分布。将主用户活动简化为两状态生灭过程，生概率为a1，灭概率为a0。当主用户状态为灭时，次级用户能够使用该授权信道。这样，次级用户初始时刻选择的可用信道的所属主用户必须处于“灭”状态。在一个单位时隙Δt过后，主用户转换为“生”状态的概率为a1。如果主用户状态由“灭”转为“生”，那么位于该主用户覆盖区域内的次级用户将不能使用该授权信道。因此，公共可用信道中cm的平均持续时间期望为

其中，n表示单位时隙个数，根据

那么平均持续时间期望E(cm)(T)可写为

显然，平均持续时间期望 E(cm)(T)与主用户活动概率成反比。在认知无线网络中，信道的平均持续时间期望直接反映了次级用户能够使用该信道的稳定性。如果2个相邻节点之间存在一条甚至更多的公共可用信道，那么只要有一条信道能持续可用则能保证两点间链路的稳定性。因此，信道稳定性与成反比，利用式(5)估计链路稳定性是合理的。同理，路径的稳定和主用户活动概率也成反比，所有用式(6)能寻找到受主用户影响最小的路由。

4.2 复杂度分析

为了估计PUB-JRCA算法的复杂度，假设在多信道认知无线网络中，有N个节点，最多有M个可用信道。在路由算法的过程中，源节点广播RREQ，中间节点转发收到的 RREQ，直到目的节点收到多个RREQ。这个过程的路由开销为O(N2)。然后，目的节点选择最稳定的路径和信道。这个过程的复杂度最大为 O(NM)。因此，整个过程的复杂度为O(N2+NM)，这和 Gymkhana路由方案[17]相类似。PUB-JRCA算法在不同条件下的复杂度如表1所示。

表1 PUB-JRCA算法在不同条件下的复杂度

PUB-JRCA算法中的路由选择阶段计算式为式(6)，那么该阶段的计算复杂度为 O(N)。然而，在Gymkhana路由方案中，目的节点计算源节点到目的节点的所有候选路径的 Laplacian矩阵的第二小特征值。其Laplacian矩阵为(Hk+1)M(Hk+1)M矩阵（Hk为第k条路径的总跳数，M为网络中可用信道数）。所以Gymkhana路由方案中目的节点的路由选择阶段的复杂度为O(N3)。这使得路由选择阶段的计算量随着网络节点数的增加而指数增加。因为在PUB-JRCA算法网络中，每个认知节点装有2个可调收发机，虽然增加了设备成本，但是它能在降低路由选择阶段复杂度的情况下保证路由的稳定性。

5 仿真结果

采用 NS2[23]环境进行认知无线网络的性能仿真。仿真场景中，网络拓扑是随机生成的。N个认知节点随机分布在1 000m×1 000m的区域内，M条授权信道，认知节点（类似于802.11）的最大传输范围为 300m。源节点和目的节点随机选择，假设传输信道为瑞利平坦衰落信道，其瑞利分布的均值服从参数为1的指数分布，其他次级用户对参照节点的干扰服从均值为0dB、方差为8dB的对数正态分布，高斯噪声功率为-90dBm[24]。建模主用户行为为呼叫模型，其每个不同主用户的活动概率处于0～0.9之间。仿真初始化时，每个认知节点的可用频谱为所有授权频谱的一部分。在一个单位时间里，一个节点可以传输100个数据分组，其可用频谱确定。在下一个单位时间里，主用户m状态变为“1”的概率为，使得该主用户覆盖范围内的认知节点的可用频谱发生改变。

5.1 分组投递率

在具有多信道的认知无线网络中，分组投递率是发送分组数量与接收分组数量的比值，能反映由于路由失败引起的分组丢失率。在多信道认知无线网络中，主用户的出现是导致路由失败的主要因素。因此，主用户(PU, primary user)的活动概率会影响网络的分组丢失率。仿真网络拓扑中随机分布25个认知用户，3个主用户，PU1、PU2、PU3， PU1和PU3的活动概率为= 0 .4和= 0 .1并保持不变而PU2的活动概率从0.1到0.9变化。每个认知用户的初始化可用信道为{c1,c2,c3}。如图4所示，不同协议之间的分组投递率的差异非常明显。特别当大于0.4时，PUB-JRCA算法的分组投递率较DSR提高了7%。因为DSR协议中没有考虑主用户的活动性。图4显示3种协议的分组投递率随着PU2的活动概率的增加而减少。但是，Gymkhana路由方案和 PUB-JRCA算法的分组投递率均胜过 DSR协议。因为PU2活动概率的增加导致PU2处于状态“1”的平均持续时间增加，那么处于PU2传输范围内的次级用户使用该授权信道的概率减小。

图4 主用户2的不同活动概率下的分组投递率

在PUB-JRCA算法中，中间节点的源节点端链路和目的节点端链路选择不同信道，能减小相邻链路之间的干扰，即共道干扰。在信道分配中考虑不同信道的信干噪比与活动概率，保证信道的质量。因此，PUB-JRCA算法总是选择受主用户影响较小的节点和质量好的信道保证路由稳定。

5.2 平均分组时延

在针对平均分组时延(average packet delay)的仿真中，仅考虑路由建立延时而忽略信道传输延时。假设网络中有5个主用户，所有主用户有相同的活动概率，次级用户数从 25个逐渐增加到200个。其平均分组时延结果如图5所示，DSR协议的平均分组时延比Gymkhana路由方案和PUB-JRCA算法的平均分组时延小，因为DSR协议中源节点发送路由请求RREQ后，目的节点不需要开启定时器等待一段特定时间，因为目的节点只回复收到的第一个RREQ，从而减少了平均分组时延。但是 PUB-JRCA算法中的平均分组时延比 Gymkhana路由方案的平均分组时延小。随着网络中次级用户数的增加， PUB-JRCA算法和Gymkhana路由方案的平均分组时延均逐渐增加，但是前者平均分组时延的增加幅度比后者平均分组时延的增加幅度小，当次级用户节点数为100时，PUB-JRCA算法的平均分组时延比Gymkhana路由方案低将近1.8个单位时间。因为 PUB-JRCA算法中目的节点处的路由选择阶段的计算复杂度比Gymkhana路由方案的计算复杂度低，网络中次级用户数增加直接影响路由选择阶段时延，从而影响网络中的平均分组时延。

因此，在具有多信道的认知无线网络中，PUBJRCA算法在平均分组时延方面优于Gymkhana路由方案，尤其当次级用户数越大时，网络中平均分组时延性能越优越。而PUB-JRCA算法为获得比DSR协议更高的分组投递率，牺牲了网络平均分组时延。由此可知，PUB-JRCA算法更适合多节点认知无线网络。

图5 不同次级用户数下的平均分组时延

6 结束语

本文提出了一种适应于多信道认知无线网络的基于主用户行为的联合路由和信道分配算法。针对主用户行为导致频谱的动态特性，基于 DSR的基本思想，对其进行了扩展，提出一种新的基于主用户行为的路径权值算法，并将信道分配过程添加到路由回复阶段完成。理论分析表明，基于主用户行为的路径权值与链路的平均持续时间期望成反比，可以权衡链路平均持续时间，另外分析了算法的路径选择阶段的计算复杂度。仿真结果表明，该算法在主用户行为多变和多节点的认知无线网络中能提升分组投递率，降低平均分组时延。

[1] 周贤伟, 王建萍, 王春江. 认知无线电[M]. 北京: 国防工业出版社,2008. 1-2.ZHOU X W, WANG J P, WANG C J. Cognitive Radio Networks[M].Beijing: National Defence Industry Press, 2008. 1-2.

[2] MITOLA J, MAGUIRE G Q. Cognitive radio: Making software radios more personal [J]. IEEE Personal Communications, 1999, 6(4): 13-18.

[3] AKYILDIZ I F, LEE W Y, VURAN M C. Next generation/dynamic spectrum access/cognitive radio wireless networks: a survey [J].Computer Networks, 2007, 50(13): 2127–2159.

[4] YÜCEK T, ARSLAN H. A survey of spectrum sensing algorithms for cognitive radio applications [J]. IEEE Communication Surveys and Tutorials, 2009, 11(1): 116-130.

[5] YIN W S, REN P Y, SU Z. A multiple antenna spectrum sensing scheme based on space and time diversity in cognitive radios[J].IEICE Transactions, 2011, 94-B(5): 1254-1264.

[6] LEE W, AKYILDIZ I F. Optimal spectrum sensing framework for cognitive radio networks [J]. IEEE Transactions on Wireless Communication, 2008, 7(10): 1536-1276.

[7] ZHAO Q, TONG L, SWAMI A. Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks: a POMDP framework[J]. IEEE Journal on Selected Areas in Communications, 2007,25(3): 589-600.

[8] WANG Y C, REN P Y, SU Z. A POMDP based distributed adaptive opportunistic spectrum access strategy for cognitive ad hoc networks[J]. IEICE Transactions, 2011, 94-B(6): 1621-1624.

[9] KHALIFE H, MALOUCH N, FDIDA S. Multihop cognitive radio networks: to route or not to route[J]. IEEE Network, 2009, 23(4):20-25.

[10] CESANA M, CUOMO F, EKICI E. Routing in cognitive radio networks: challenges and solutions [J]. Ad Hoc Networks, 2011, 9(3):228-248.

[11] DRAVES R, PADHYE J, ZILL B. Routing in multi-radio, multi-hop wireless mesh networks[A]. MOBICOM2004[C]. New York, USA,2004. 114-128.

[12] LIU T, LIAO W. Multicast routing in multi-radio multi-channel wireless mesh networks[J]. IEEE Transactions on Wireless Communication,2010, 9(10): 3031-3039.

[13] MA H, ZHENG L, MA X. Spectrum aware routing for multi-hop cognitive radio networks with a single transceiver[A]. Proceedings of IEEE CrownCom[C]. Cannes, France, 2008.1-6.

[14] LI Y, QIN F, LIU Z. Cognitive radio routing algorithm based on the smallest transmission delay [A]. The 2nd International Conference on Future Computer and Communication[C]. Shanghai, China, 2010.306-310.

[15] HOWA K C, MA M, QIN Y. Routing and QoS provisioning in cognitive radio networks [J]. Computer Networks, 2011, 55(1): 330-342.

[16] ABBAGNALE A, CUOMO F. Gymkhana a stability based routing scheme for cognitive radio ad hoc networks[A]. IEEE INFOCOM2010,Work-in –Progress Session[C]. San Diego,CA, 2010. 1-5.

[17] SRIRAM K, WHITT W. Characterizing superposition arrival processes in packet multiplexers for voice and data [J]. IEEE Journal on Selected Areas in Communications, 1986, 4(6): 833-846.

[18] WILLKOMM D, MACHIRAJU S, BOLOT J. Primary users in cellular networks: a large-scale measurement study[A]. IEEE Symposium in DySPAN[C]. Chicago,IL, USA, 2008. 1-11.

[19] DING L, MELODIA T, BATALAMA S N. Cross-layer routing and dynamic spectrum allocation in cognitive radio ad hoc networks [J].IEEE Transactions on Vehicular Technology, 2010, 59(4): 1969-1979.

[20] 王朝瑞. 图论[M]. 北京: 北京理工大学出版社, 2001.206-207.WANG C R. Graph Theory[M]. Beijing: Beijing Institute of Technology Press, 2001.206-207.

[21] JOHNSON D B, MALTZ D A, HU Y C. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)[M]. Addison-Wesley Longman Publishing Co, Inc Boston, MA, USA. 2001.

[22] SALAMEH H, KRUNZ M, YOUNIS O. Throughput-Oriented Mac Protocol for Opportunistic Cognitive Radio Networks with Statistical Performance Guarantees[R]. University of Arizona UAECE- 2007-2,2007.

[23] 方路平,刘世华. NS-2网络模拟基础与应用[M]. 北京: 国防工业出版社, 2008.FANG L P, LIU S H. Fundamentals and Applications of Network Simulation: NS-2[M]. Beijing: National Defence Industry Press, 2008.

[24] WANG W W, CAI J, ALFA A S. Distributed routing schemes with accessibility consideration in multi-hop wireless networks[J]. IEEE Transactions on Wireless Communications, 2010, 9(10): 3178-3188.