一种改进的认知无线网络路由算法

赵建立，苑津莎，韩东升

(华北电力大学，河北保定071003)

无线通信的迅速发展使得人们对无线频谱资源的需求量日益增大，无线频谱资源的匮乏问题显得越来越严重。然而，来自美国联邦通信委员会(FCC)的一份频谱占用调查报告显示，稀缺的频谱资源平均使用率只有15%，大部分授权频段经常处于空闲状态［1－3］。认知无线电(Cognitive Radio，CR)技术［4－5］的提出使非授权用户(Secondary User，SU)能够感知、识别及接入当前空闲的授权用户(Primary User，PU)频段，从而大幅提高频谱利用率。

由于传统的路由算法不能直接应用到认知无线电网络中［6］。近来，将CR技术应用在移动Ad Hoc中的研究越来越多［7］。文献［5］提出一种基于贪婪地理位置、最小延迟的SEARCH路由协议。当路径中不存在前向避免区域时，SEARCH路由选择算法可以得到端到端延迟最小的最短路径。但是，文献［8］中没有考虑路由节点在业务量较大的时候，中间节点由于超负荷会造成队列延迟和频繁的频谱切换问题。文献［9］提出一种SAMER认知路由选择协议。SAMER协议在长期路由稳定和短期接入机会之间取得平衡，从而提高网络的寿命。文献［10］给出了Ad Hoc网络中CR路由选择的度量。

本文在现有文献的基础上，提出一种基于联合地理位置和前向反馈的认知路由选择算法。在考虑最佳位置转发候选节点时，也考虑了节点的业务量;同时通过前向反馈，使全局路由为最佳，避免路由进入前向避免区域，给路径带来拓扑不稳定和增加延迟的影响［11］。仿真结果表明，本文提出的路由选择算法要优于文献［8］中的SEARCH路由方案，同时减小了端到端的延迟和能量消耗。

1 认知路由的挑战

多跳认知Ad Hoc网络中的路由选择，严重影响着网络的全局性能，认知路由选择的性能受多种因素的影响。

1.1 频谱切换导致的延迟

文献［9］指出，在CR网络中，路由从一个频段切换到另一个频段对SU数据传输带来极大的影响，造成频谱切换延迟。频谱切换延迟计算公式为

式中:k为常数，通常取10 ms/10 MHz;M为可用的频带数目。

1.2 队列延迟

文献［10］分析当最佳前向转发路由处于超负荷状态时，会对数据包的转发带来严重的队列延迟。队列延迟的计算公式为

式中:Pn为数据包的大小;Bi为Bandi的带宽;Numi为对带宽Bandi总共的竞争用户数。

1.3 信道感知与选择延迟

在中间节点进行频谱切换，路由就要执行相应的频谱感知，选择候选信道［8］。信道感知与选择延迟满足

式中:Tsens为CR信道感知时间。

2 基于位置和前向反馈的认知路由选择算法

为了提高Ad Hoc网络中路由的稳定性，同时降低对PU的干扰，以及降低端到端的延迟，本文提出一种基于位置和前向反馈的认知路由选择算法。

2.1 位置区分析

潜在区域(Potential Region，PR):由于Tx的发射功率有限，不能直接和Rx建立通信链路，那么Tx就必须选择潜在转发路由节点PR。潜在区域存在于图1的阴影区域，其定义为

图1 最佳转发区域

从图1可以看出，位于潜在区域中Tx的前向转发节点PR不处于PU接受功率范围之内。当PU突然出现，也不会对前向路由带来影响。

最佳转发区域(Best Forward Region，BF Region):根据两点之间直线最短定理，以及三角形两边之和大于第三边定理可以得到在PR中存在一个最佳转发扇形区域。该区域以Tx和Rx两点连线lTx－Rx为角平分线，夹角为2θmax的扇形区域。图1中路由节点a、b、c和d处于最佳转发区域中。

最佳转发路由(Best Forward Router，BFR):将最佳转发区域中的M个候选节点标记为candi_routei，i∈［1，M］。将Tx到candi_routei的方向矢量表示为Vi，Tx到Rx的方向矢量表示为Ui。为了减小转发路由偏离接收端的角度，最佳转发路由candi_routei应满足如下优化条件

根据式(5)，在图1中路由节点c为Tx的最佳转发路由BFR。

前向避免区域(Forward Avoidance Region，FA Region):在路由路径中，当前转发路由Forward Router(FR)的BFR位于PU频段使用范围内，或者FR的最佳转发路由处于超负荷状态，或者位于最佳转发区域中的路由节点不愿意给FR转发数据包，那么此时FR位于前向避免区域，如图2所示。根据最佳转发区域定义可以知道:路由节点e，f，g处于最佳转发区域之内，同时路由f为BFR节点。各类情况分析如下。

图2 前向避免区域

FR选择f:由于路由f处于PU频带使用范围之内，也就是说，由FR到路由f的PU频段不可以用。如果FR选择f作为前向转发节点，那么在f处就必须进行频谱切换，从而造成切换延迟。为此，在最佳转发区域中，路由f不是最佳节点。SEARCH协议没有考虑频谱切换造成的频谱切换延迟，仅仅考虑了信道选择延迟，所以其选择在f处需进行信道切换。

FR选择e:若此时路由e处于超负荷状态，选择e会造成严重的数据包队列延迟。为此，在最佳转发区域中，路由e也不是最佳转发节点。

FR选择g:若此时路由g由于自身的能耗限制或者g不愿意给FR转发数据包，所以FR也不能通过g转发数据。

则FR的最佳转发区域中没有候选路由。

在这4种情况下，认为FR处于前向避免区域。这4种类型的路由定义为FA Region路由。如图2所示，FR位于前向避免区域。

2.2 前向避免区域中SEARCH路由的缺陷

如果FR位于前向避免区域，那么在FR处就必须进行优化。SEARCH路由算法没有考虑路由业务量的大小对延迟的影响。如果前向避免区域中的BFR处于超负荷状态，由于贪婪地理位置准则可以满足最短路由路径，FR依然选择BFR作为下一跳。但其忽略了队列延迟;如果前向避免区域由PU出现引起，则不选择BFR进行转发，而是绕过前向避免区域，选择下一跳路由(Next Router，NR)。如图3所示。

图3 存在前向避免区域的SEARCH路由

同时SEARCH考虑了从信道k切换到k'的切换开销δk。其选择的最佳NR满足如下优化条件

式中:m'表示切换了信道之后，从NR到Rx的路由跳数;NRk'表示NR使用信道k';Ddisse表示数据从FP到达NR的传播时间。如图3所示，链路FR→a→b→c→d，很好地绕过了前向避免区域，但是造成极大的切换开销，同时忽略了10 ms数量级的频谱切换延迟。

从图3中可以看出，SEARCH对前向避免区域采用了绕行方法对数据包进行转发，显然，由Previous－FR(Pre－FR)到a经过了FR，即:Pre－FR→FR→a，从而导致了整体路由的非最优选择。

2.3 基于位置的前向反馈算法

分析图3可以发现，出现在FR进行信道切换的问题，不是由FR造成的，而是Pre－FR下一跳节点选择的问题。如果，Pre－FR在选择下一跳时不是贪婪地选取最佳路由，就不会造成在下一跳出现这种尴尬的局面。为此，Pre－FR在选择下一跳路由FR时，有必要确定FR有没有比较好的下一跳路由为其转发数据。为解决这一问题，本文采用前向反馈的方法，对前向避免区域进行优化。具体算法策略如下:

1)Pre－FR将所有存在于最佳转发区域中非FA Region路由，按照式(5)中的arccos(·)，由小到大进行排序，并将排序好的候选节点全部存放在Pre－FR的FR_node缓存中。

2)如果FR_node为空，则执行步骤5)，否则执行步骤3)。

3)执行循环。对FR_node中的所有节点，依次进行下一跳路由分析。假设当前分析节点为FR_nodei。如果FR_nodei的下一跳中不存在FA Region路由，则FR_nodei可以作为Pre－FR的FR，同时将可以作为转发节点的信息反馈给Pre－FR，退出FR_node循环，执行步骤5);若FR_nodei位于前向避免区域，对FR_nodei+1进行步骤3)。

4)如果FR_node中的所有节点均位于前向避免区域，即没有可以执行下一跳的路由，那么执行步骤5)。

5)在Pre－FR处进行频谱切换。考虑转发节点的队列长度，对SEARCH路由算法做进一步优化，选择下一跳节点的优化算法如下

式中:Dbackoff为退避延迟。

3 性能评估

3.1 端到端的延迟

认知无线电通信网络中对路由算法的性能分析，需考虑其从端到端的延迟、路径中总的跳数以及链路中总的能量消耗。对路径中总的跳数可以通过式(7)进行优化。下面就端到端的延迟进行理论分析。

在分析的时候考虑5种延迟:频谱切换延迟、队列延迟、退避延迟、信道检测和选择延迟以及传播延迟。其中频谱切换延迟、队列延迟及信道检测和选择延迟如上文所述。退避延迟的计算公式如下

式中:pc表示一个竞争节点经历碰撞的概率;W0表示最小竞争窗口大小［11］。所以，端到端的延迟Ddelay为

3.2 端到端能量消耗

无线设备发送和接收以及信号放大均需要消耗能量。文献［15］给出了无线设备能量消耗特性，见表1。

表1 无线设备能量消耗特性

为了方便，令ETx－elec=ERx－elec=Eelec。若一个功率覆盖半径为d(m)的无线设备要传输k(bit)的数据包，所需消耗的能量模型表示如下

类似地，要接收k(bit)的数据包，所需消耗的能量模型为假设Ad Hoc网络中无线设备发送功率相同，信号所能覆盖的半径相同，则端到端的能量消耗为

式中:hops为路径中总的路由跳数。

4 性能仿真和分析

4.1 仿真环境描述

仿真模型如图4所示，假设400个无线节点存在于1 000 m×1 000 m的区域内，CR收、发用户的传输覆盖半径为120 m，用黑色的小方框表示Tx和Rx，其中Tx位于(400 m，600 m)处，Rx位于(800 m，200 m)处。网络中小圆点表示无线路由，所有的路由节点均具有频谱检测功能;PU的覆盖范围为200 m，用小方框表示，PU位于(300 m，700 m)处;网络中浅色的小点表示该路由已经处于业务量饱和状态，不能再接受其他用户的转发请求;而深色的小点表示可以作为转发节点的路由。

图4 存在前向避免区域，两种路由协议性能

4.2 不同条件下两种算法的路由选择性能

图4给出了两种路由选择算法的性能比较。其中深色的路径为本文算法路由路径，另一条为SEARCH方案的路径。分析图4可以看出，SEARCH的第一跳路由为Tx的BFR。但BFR处于前向避免区域，BFR选择切换到其他信道的方法进行转发，绕过了前向避免区域，仿真与理论分析吻合。其中浅色路径为所绕路径。

与SEARCH相比，本文提出算法的路由路径要短很多。从图中可以看出，Tx的第一跳路由处于前向避免区域，通过反馈，将信息反馈给Tx，Tx从FR_node中选择次优路由进行判断;从而避免了SEARCH因贪婪的最佳路由选择，造成的路由不稳定。

此时SEARCH总共需要9跳才能将Tx的数据包转发给Rx，而本文提出的算法只需要6跳路由就可以成功递交数据包。当路径中不存在FA Region时，图5给出了此种场景下两种路由协议性能对比。在此种场景下，两种算法选择的路径重合在一起，且均是最短路径。

图5 不存在前向避免区域时两种路由协议性能

4.3 两种路由算法的数据传输延时性能分析

假设pc=0.1，Numi=5，Bi=1MHz，Tsens=50 μs。SEARCH在前向避免区域处由中心频道900 MHz切换到中心频率为915 MHz的信道上。图6给出了图4场景下端到端延迟随数据包的大小变化曲线图。

图6 端到端延迟比较

两种算法的端到端延迟均随着转发数据包的大小变化而变化，且包越长，端到端延迟越大。从图6中可以很清楚地看出，本文提出的算法要明显优于SEARCH方案。这表明加入反馈之后，可以很好地在前向避免区域处进行优化，减小了路由跳数，降低了传播延迟。

4.4 两种路由算法的节点能量消耗性能分析

图7给出了图4场景下，两种路由选择算法造成的端到端设备能量消耗随数据包大小的变化。从图7中可以很清楚地看出，当路径存在前向避免区域时，本文提出的路由算法可以降低端到端的能量消耗，随着数据包变大，效果越明显。从而节约了网络的全局能量消耗。

图7 端到端能量消耗比较

5 结论

本文提出了一种基于地理位置和前向反馈的认知路由选择算法，以解决认知路由算法SEARCH在前向避免区域频繁信道切换造成的端到端延迟和路由不稳定问题。通过信息反馈，协调当前路由和下一跳路由，综合评估最佳下一跳路由;同时提出了认知网络中路由算法的评估方案。仿真表明，本文提出的路由选择算法要优于SEARCH方案，同时降低了端到端的延迟和能量消耗。

［1］ FCC.Notice of proposed rule making and order(ET docketno.03－322)［EB/OL］.［2013－08－15］.http://en.wikipedia.org/wiki/Notice_of_proposed_rulemaking.

［2］ SUN H，NALLANATHAN A，WANG C，et al.Wideband spectrum sensing for cognitive radio networks:a survey［J］.IEEEWireless Communications，2013，20(2):74－81.

［3］ WANG J，CHEN J，CABRIC D.Cramer－rao bounds for joint rss/doabased primary－user localization in cognitive radio networks［J］.IEEE Trans.Wireless Communications，2013，12(3):1363－1375.

［4］ XUE D，EKICIE.Cross－layer scheduling for cooperativemulti－hop cognitive radio networks［J］.IEEE Journal on Selected Areas in Communications，2013，31(3):534－543.

［5］ ZHOU Y，ZHU H，SUN Y，et al.Routing－toward－primary－user attack and belief propagation－based defense in cognitive radio networks［J］.IEEE Trans.Mobile Computing，2013，12(9):1750－1760.

［6］ PARVIN S，FUJIIT.Radio environment aware stable routing scheme for multi－hop cognitive radio network［J］.IET Networks，2012，1(4):207－216.

［7］ JO M，HAN L，KIM D，etal.Selfish attacks and detection in cognitive radio Ad－Hoc networks［J］.IEEE Network，2013，27(3):46－50.

［8］ CHOWDHURY M.Search:a routing protocol for mobile cognitive radio ad－ hoc networks［J］.Computer Communications，2009，32(18):1983－1997.

［9］ PEFKIANAKIS I，WONG S，LU S.Samer:spectrum awaremesh routing in cognitive radio networks［C］//Proc.IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks(DySPAN'08).Chicago:IEEE Press，2008:1－5.

［10］ CALEFFIM，AKYILDIZ I，PAURA L.Opera:optimal routing metric for cognitive radio ad hoc networks［J］.IEEE Trans.Wireless Communications，2012，11(8):2884－2894.

［11］程赓，李昀照，刘威，等.认知无线电网络路由及频谱分配联合策略研究［J］.电子与信息学报，2008，30(3):695－698.

［12］ CHENG G，LIY，LIUW，et al.Joint routing and spectrum assignment in cognitive radio networks［J］.Journal of Electronics ＆ Information Technology，2008，30(3):695－698.

［13］ MA X，ZHENG L，LUO Y.Spectrum aware routing formulti－hop cognitive radio networkswith a single transceiver［C］//Proc.3rd International Conference on Cognitive Radio Oriented Wireless Networks and Communications(CrownCom'08).Singapore:IEEE Press，2008:1－6.

［14］ CHENG G，LIUW，LIY，et al.Joint on－demand routing and spectrum assignment in cognitive radio networks［C］//Proc.IEEE International Conference on Communications(ICC'07).Glasgow:IEEE Press，2007:6499－6503.

［15］ IEEE standard for wireless lan－medium access control and physical layer specification［S］.1999.

［16］ HEINZELMANW，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol forwirelessmicro－sensor networks［C］//Proc.33rd Annual Hawaii International Conference on System Sciences.［S.l.］:IEEE Press，2000:1－10.