认知无线ad hoc网的多尺度跨层路由协议

曹　静， 武君胜， 杨文超， 王硕晨

(1. 西北工业大学 计算机学院， 陕西 西安 710072;2. 西北工业大学 软件与微电子学院，陕西 西安 710072)

随着各种新型无线网络(无线传感网、软件定义网，普适网络等)的迅速普及，近年来，无线通信的业务量剧增，未来的无线网络将呈现出高速化、宽带化、异构化、泛在化等趋势．认知无线网络(Cognitive Radio Networks，CRNs)作为5G网络的核心技术之一，是提高频谱利用率，解决当前存在的频谱匮乏、带宽受限、适应能力不足等问题的有效途径．CRNs具有认知和自适应特性，各个网络节点都能够感知当前的网络环境，并根据感知结果进行学习和决策，自适应地调整传输参数，通过学习推理来改进网络的端到端性能．认知无线自组网络(Cognitive Radio Ad Hoc Networks，CRAHNs)是由一组具有认知决策的节点以多跳自治的方式组成的智能网络，能够为用户动态接入物联网提供基础通信平台[1-2]．

在认知环境下，路由设计问题较之传统的无线自组网更复杂，不仅包括认知用户(Secondary User，SU)的移动性造成的网络拓扑动态变化、链路不稳定等问题，还包括由主用户(Primary User，PU)行为的不确定性带来的频谱机会(Spectrum OPportunity，SOP)时变问题[3]．近年来，有很多学者针对CRAHNs的路由优化问题进行研究，并提出多种解决方案: 文献[4]提出一种跨层路由策略，该策略能够计算出从任一源节点到目的节点的链路时延和路径时延，结合Dijkstra算法可以通过求解最短路径问题来获得最佳选路方案．文献[5]从潜在博弈的角度出发，为多跳CRNs提出二维的信道-路由交换算法．该算法从频域和空间域两个角度进行资源管理，在不完全信息博弈下能够计算出贝叶斯纳什均衡点，从而获得最小资源开销的方案．文献[6]对按需距离矢量路由协议(Ad hoc On-demand Distance Vector routing，AODV)协议做了认知性的扩展，提出一种具有服务质量(Quality of Service，QoS)保障的基于认知的AODV协议(Cognitive-based AODV, CAODV); 该协议为CRAHNs中的认知用户提供了多信道的接入方案，并在一定程度上增加了端到端吞吐量，然而缺乏对信道切换是否会增加时延的分析．在目前的研究中，大部分学者关注于通过有效的资源管理机制来提高频谱利用率、缓解频谱拥塞和优化端到端性能．这些方法在一定程度上实现了资源优化配置并提高了路由效率和稳定性，然而随着移动网络的发展，多种无线异构业务将共存和相互融合，因此需要在认知路由设计时考虑业务特征和路由尺度的选择．

综上所述，笔者提出一种多尺度跨层路由协议(Multi-Metric cognitive Cross-layer AODV，MM-CAODV)．结合物理层的信道参数和功率分配，以及介质访问控制(Media Access Control，MAC) 层的频谱信息来制定路由策略，并根据业务类型和QoS需求来为认知用户选择适当的路由尺度权重．结合频谱可用性来避免对PU的业务流造成干扰，并通过频谱——路由联合分配来增加吞吐量、改善链路的稳定性和减少端到端时延．由于目前大部分业务(尤其是移动多媒体)具有较高的QoS要求，如高速率、时延敏感、高数据投递率等，针对业务流的网络性能进行分析，通过时延、吞吐量、数据投递率等QoS参数对MM-CAODV协议做仿真实验，从而获取路由策略的评价指标．

1　网络模型

文中考虑的认知Ad hoc网络由N个认知用户SU、M个可用信道组成，SU之间以多跳的方式通信，各个SU使用PU的空闲频段进行业务传输．为了避免对PU的传输造成干扰，SU必须获得当前的可用频谱列表，也就是频谱机会SOP; 由于PU的行为具有不确定性，SU的SOP会随时间变化，各个用户的SOP通过周期性的频谱感知来获取．当且仅当两个SU的SOP之间存在交集，并且它们之间的距离在有效传输范围之内时，才可以建立传输链路．

图1给出了抽象的网络拓扑模型，节点S和D分别代表路由的源节点和目的节点，{A，B，C，E，F}代表多跳路由的中间节点， {C1，C2，C3，C4}表示不同的授权频段．对于各个链路，由于信道带宽、路径时延、地理位置等差异，传输性能也不同，用一个二元组(delay， cost)来表示信道参数，其中delay表示路径时延，cost表示流量占用网络带宽的开销．受主用户行为的影响，各个信道在使用中随时会被主用户收回而不可用，这种情况下需要进行路由恢复，有两个解决方法:在中断的两个节点间进行信道切换，选择另外一个共用信道，原路由方案不变;重新进行源节点到目的节点间的路径选择．

图1　CRAHN的路由模型

在图1(a)中，从源节点S到目的节点D，有如下几条路径可以选择:

(1)S→A→B→D; total delay=7，cost=6;(2)S→C→D; total delay=6，cost=7;

(3)S→C→F→D; total delay=5，cost=10;(4)S→E→F→D; total delay=3，cost=11．

在这4条路径中，按照不同的尺度标准有多种选路方案:如果数据流是时延敏感型业务(如在线视频)，则应当选择(4)，以期望通过最小时延到达目的地;但是成本较高，会消耗较多的带宽资源．如果是时延容忍型数据业务(如浏览页面、文件传输等)，则应当选择(1)，以占用较少的网络资源来完成数据流传输．如果从节能和链路稳定性的角度考虑，则应当选择(2)，以经过最小跳数到达目的节点．在图1(b)中，当信道C2被主用户收回时，S→C的路径被中断时，当前可用路径仅剩(1)和(4)．这时如果剩余路径的处理能力有限，就要恢复S到C之间的链路，通过多径路由来处理网络负荷．这时可以选择从信道C2切换到信道C3来实现链路重建．在图1(c)中， 当S→C之间的信道切换到C3时，从(1)到(4)的路径全部可用，这时对路径(3)进行更新，total delay= 3，cost= 10，路径(3)成为比(4)总体性能更优的路由方案．

2　多尺度优化模型

2.1　路由尺度分析

2.1.1时延

认知Ad hoc网络是多跳、分布式的无线网络，由于SOP是动态变化的，SU需要根据PU的行为进行信道切换和选择，因此，网络的端到端总时延Dtotal由两部分组成: 路径时延Dpath和切换时延Dswitch，可以表示为

Dtotal=Dpath+Dswitch．

(1)

路径时延是由数据流在多跳节点间的传输引起的，当多个数据流竞争同一个信道时会带来退避时延Dbackoff[7]．因此，路径时延也分为两部分：数据流传输时延Dtransmission和退避时延Dbackoff．

(2)

其中，Ttraffic表示业务数据流的流量，Nhop表示当前路径的跳数，Rk表示链路k的数据传输速率;nc表示竞争同一信道的节点数量，pc为多个节点竞争同一信道而发生碰撞的概率，W0表示最小竞争窗口的大小．切换时延是在频谱发生移动时发生的，与切换过程所发生的频段差异成正比，因此，节点在信道Cm和Cn之间的切换时延为

Dswitch=K|B(Cm)-B(Cn)|,

(3)

其中，比例系数K是一个常数，表示单位频率切换的时间消耗．将K设置为 10 ms/ 10 MHz，也就是， 认知节点的收发机在进行频谱切换时，每调整工作频率 10 MHz 需要 10 ms 的时延．B(Cm)和B(Cn)表示信道带宽，综合式(1)～式(3)就可计算出当前路径的总时延．

2.1.2业务传输速率

在覆盖式(overlay)的认知网络中， SU通过频谱感知来获得空闲频谱列表，并通过参与竞争获取频谱的使用权．在无线Ad hoc网中，所有的SU节点以自治、多跳的方式组网，在传输过程中要通过分布式的功率控制来提高网络的容量和能效．各个用户需要根据周围环境的变化来调整发射功率，来满足业务传输需求．根据香农公式[8]，SU使用信道Cj能够获得的传输速率为

(4)

2.1.3稳 定 性

为了解决CRNs的资源动态变化问题，一般通过统计学模型来预测PU的活动规律，并通过计算链路稳定时间来控制数据分组的传输过程．通常把PU对授权信道的占用情况定义为ON-OFF随机过程，各个信道的ON和OFF状态相互独立且在时刻t服从指数分布，对于信道Cj， 对认知用户可用的概率是

(5)

(6)

2.2　多尺度优化模型

将路由问题建模为多尺度优化模型，在认知用户能够获得所需带宽的前提下，通过建立目标函数来改进用户的服务质量，为不同业务类型的用户寻找高效的路由方案．文中的路由策略中，优化目标是加权的路由尺度，并通过可调整的权值分配来满足用户对时延、稳定性、传输速率等的特定需求．

在定义域内存在最优解，表示为x*，有 (x-x*)Fx≥ 0．当满足条件时，可以通过迭代公式xk+1=xk-βFx在k次迭代之后求得x*，并通过比较x*与候选路由中各个参数的相似度来选取最优路径．

3　MM-CAODV路由协议

根据CRAHN的特点，对CAODV协议的数据包格式做了扩展，增加的内容主要有: 当前节点的SOP、路由尺度标记(有3项: Delay代表时延，Stab代表链路稳定性，Rd代表传输速率)、路由开销等．根据多尺度优化模型设计了MM-CAODV路由协议:

步骤1源节点S在可用信道上感知空闲频谱，并更新SOP．

步骤2S调用addNeighbor过程获得邻居节点信息，创建RREQ(Route Request)数据包并广播给所有的邻居节点．

步骤3当中间节点收到RREQ数据包之后，首先判断自己是否已经在已有的路由表中．如果是，则丢弃该数据包; 如果否，判断自己的SOP列表是否与上一跳节点的SOP之间存在交集．如果交集为空，则丢弃RREQ数据包．如果能够建立多个链路，则通过式(1)～式(6)计算出各个链路的时延、稳定性和最大传输速率，并将信息更新到路由表对应的标志位上，继续广播至下一跳节点．

步骤4当目的节点D开始接收RREQ请求包时，它将等待一个时间周期，在等待时间内会收到来自多个路径的报文．每个RREQ数据包中包含了一条路径信息，通过求解目标函数式(7)选择目标路由．目的节点D根据决策结果将RREP(Route Reply)数据包通过反向路径发送给源节点S．

步骤5当源节点S收到RREP应答数据包之后，开始在目标路径上发送数据流至目标节点．

在路由建立之后，需要在链路中断时能通过较小的代价来维护路由．首先考虑通过信道切换来修复原路径，如果不可行就重建路由．这需要建立一个信道切换(Channel Switch，CS)报文来实现，过程如下:

(1) 发生链路中断的节点根据路由表信息将CS请求报文发送给邻居节点．

(2) 对方接收到CS报文之后，中止当前正在传输的数据流并检测与中断节点间是否存在其他的SOP交集．如果是，转步骤(3)；如果否，转步骤(5)．

(3) 节点从SOP交集中通过频谱分配算法选择另一可用信道，并将选中的信道通过CS回复报文发送给中断节点．

(4) 中断节点收到CS回复信息之后，更新路由表信息并切换至此信道继续进行业务传输．

(5) 当节点间的SOP交集为空时，中断节点将生成RERR(Route Error)数据包并将该数据包沿着反向路径发送到源节点．源节点在收到RERR数据包之后，立刻停止当前数据传输，启动路由发现过程．

4　仿真实验

采用NS-2(Network Simulator 2)网络仿真工具对文中提出的MM-CAODV路由策略进行仿真和评价，具体的仿真参数如表1所示．

表1　仿真参数表

为源节点定义了3种类型的业务数据流(类型1是高传输速率型，类型2是普通业务，类型3为低路由开销型)，并通过控制报文的路由尺度域和累计开销域传递给接收节点．实验结果如图2～图4所示．在图2的实验结果中，各个节点按照随机路点模型运动，移动速度控制在 2～ 20 m/s 范围内;共有10个可用信道供用户使用进行业务传输．将文中提出的MM - CAODV与文献 [6] 中的QoS - CAODV协议分别进行实现，当SU数量从10个递增到50个时，测试和计算QoS关键参数(累计时延、吞吐量和数据投递率(Processing Data Rate，PDR)．从图2(a)～(c)的比较中可以看到，文中提出的MM-CAODV协议与QoS-CAODV协议相比，具有较小的累计时延、更大的吞吐量和更高的PDR，总体性能得到改进．在SU节点数量从10增加至40的过程中，随着节点的增加，有越来越多的数据流需要进行传输，吞吐量持续增长; 同时，由于平均跳数的增加，时延也有所增长．但是，在节点数量从40到50时，跳数的继续增加会降低路由的稳定性，这时一些不满足式(9)的约束的数据流将暂时退出对资源的竞争; 同时，一些高带宽的业务将难以获得满意的传输速率，因此吞吐量有一定程度的减少．在图2(a)中，文中的策略不会导致额外的时间开销，具有更低的时延; 在图2(b)中，MM-CAODV策略能够充分利用空闲频谱进行业务传输，吞吐量有了平均47%的增长．在图3的实验中，将认知用户数量固定为50，节点的运动模式采用马尔科夫模型; 比较可见，文中的MM-CAODV策略在绝大多数时间点具有更好的端到端性能．从图4中可见，在文中的路由策略中，3种不同类型的业务根据特定的资源需求，分别获得了不同的传输速率．

图2　不同节点数量的QoS参数

图3　不同时间的QoS参数

图4　3种业务的传输速率

为了评估路由的稳定性，进行了路由持续时间和开销测试．图5中，随着节点数量的增加，路由持续时间呈下降趋势;改进的协议都具有对无线环境的适应性，能够修复干扰引起的链路失效．MM-CAODV首选通过信道切换的方式对路径进行维护，避免了不必要的路由重建，改善了路由的持续时间，因此整体稳定性方面略高于QoS-CAODV．从图6中可见，QoS-CAODV和MM-CAODV协议在路由开销方面都略高于CAODV协议， 然而能够以相当小的开销代价换来明显的端到端性能改进．MM-CAODV协议结合用户的业务类型来分配资源，当节点数量较多时具有较明显的优势．

图5 平均持续时间图6 路由开销

5　结 束 语

笔者针对认知无线自组网提出一种多尺度路由协议MM-CAODV，该策略根据业务流的特征来定义路由尺度的权值;提出了信道-路由联合分配的解决方案，并实现了网络层-物理层的跨层优化．结合频谱信息为认知用户提供了适用于不同类型业务的路由方案;针对时延、路由稳定性、网络开销等参数进行分析并提出了多尺度优化模型，根据模型设计了具体的路由协议．通过实验表明，MM-CAODV协议能够一定程度上优化无线传输的QoS性能，为不同的业务类型分配合适的资源，在时延、吞吐量和数据投递率等方面，都具有一定程度的改进．

参考文献：

[1] KAMRUZZAMAN S M, FERNANDO X, JASEEMUDDIN M. Energy Aware Multipath Routing Protocol for Cognitive Radio Ad Hoc Networks[J]. International Journal of Communication Networks and Information Security, 2016, 8(3): 186-196.

[2]杨双懋, 郭伟, 唐伟. 一种最大化网络吞吐量的认知无线Ad Hoc网络跨层优化算法[J]. 计算机学报, 2012, 35(3): 491-503.

YANG Shuangmao, GUO Wei, TANG Wei. A Cross Layer Throughput Maximization Algorithm for Cognitive Wireless Ad Hoc Networks[J]. Chinese Journal of Computers, 2012, 35(3): 491-503.

[3]SINGHAL D, GARIMELLA R M. Cognitive Cross-layer Multipath Probabilistic Routing for Cognitive Networks[J]. Wireless Networks, 2015, 21(4): 1181-1192.

[4]ZAREEI M, MOHAMED E M, ANISI M H, et al. On-demand Hybrid Routing for Cognitive Radio Ad-hoc Network[J]. IEEE Access, 2016, 4: 8294-8302.

[5]LIANG Q K, WANG X B, TIAN X H, et al. Two-dimensional Route Switching in Cognitive Radio Networks: a Game-theoretical Framework[J]. IEEE/ACM Transactions on Networking, 2015, 23(4): 1053-1066.

[6]MALLAT Y, AYARI A, AYADI M, et al. Performance Evaluation of QoS-CAODV, CAODV Routing Protocol in Cognitive Radio Ad-hoc Network[C]//Proceedings of the 2015 23rd International Conference on Software, Telecommunications and Computer Networks. Piscataway: IEEE, 2015: 195-199.

[7]YANG Z K, CHENG G, LIU W, et al. Local Coordination Based Routing and Spectrum Assignment in Multi-hop Cognitive Radio Networks[J]. Mobile Networks and Applications, 2008, 13(1/2): 67-81.

[8]龙彦, 李红艳. 认知无线网络中视频传输的资源分配方案[J]. 西安电子科技大学学报, 2016, 43(2): 6-12.

LONG Yan, LI Hongyan. Resource Allocation Scheme for Video Transmissions in Cognitive Radio Networks[J]. Journal of Xidian University, 2016, 43(2): 6-12.

[9]阔永红, 贺冰涛, 陈健. 携能通信协作认知网络稳态吞吐量分析和优化[J]. 西安电子科技大学学报, 2016, 43(6): 1-7.

KUO Yonghong, HE Bintao, CHEN Jian. Stable Throughput Analysis and Optimization of Cooperative CRNs Based on Information and Energy Cooperation[J]. Journal of Xidian University, 2016, 43(6): 1-7.

[10]CAO J, WU J S, YANG W C. Spectrum Allocation Strategy for Heterogeneous Wireless Service Based on Bidding Game[J]. KSII Transactions on Internet and Information Systems, 2017, 11(3): 1336-1356.