认知路由算法设计的挑战与关键指标分析

闵慧 李鹏

摘 要： 在认知无线网络中，认知用户如何在动态变化的频谱环境下实现可靠、高效的路由是目前的一个研究热点。在对最近的研究成果进行归纳总结的基础上，从节点具有的频谱机会集合（SOP）动态变化和多信道多接口两方面特性出发，指出了认知路由面临的主要挑戰；通过实例对比分析了设计路由算法所需考虑的功率控制、认知用户移动性、链路可靠性、负载均衡等多个重要指标；展望了认知路由技术的进一步研究方向，并针对认知路由新技术研究和某些热点问题，提出了可能采取的路由优化方法和思路。

关键词： 认知无线网络； 路由； 挑战； 指标； 进一步研究方向

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2018）06-18-05

Analysis of challenges and key indicators in design of cognitive routing algorithm

Min Hui1， Li Peng2

（1. Department of Computer Engineering， Hunan College of Information， Changsha， Hunan 410200， China；

2. School of Information Science and Engineering， Hunan University of Chinese Medicine）

Abstract： In the cognitive wireless network， how to find a reliable and effective routing path for CR users with the dynamic changes of spectrum is currently a hot research topic. Based on the summary of the current routing research results， this paper points out the critical challenges of the cognitive routing from the two features of nodes： the dynamic spectrum and multi-channel multi-interface； The key indicators in the design of routing algorithm such as power control， cognitive users' mobility， link reliability， and load balancing are discussed， and compared and analyzed with practical examples. The further research direction of cognitive routing technology is prospected， and the possible route optimization methods and ideas are proposed for new technology research and some hot issues.

Key words： cognitive wireless network； routing； challenges； indicators； further research direction

0 引言

随着无线通信技术的飞速发展以及通信需求的不断增加，现有的固定频谱分配方案导致频谱资源日益枯竭，如何有效地提高频谱利用率以满足不同用户的多种业务需求已经成为通信产业发展的必然趋势和面临的主要挑战。认知无线电技术[1]被认为是应对这一挑战的关键手段。认知无线电的核心思想是，通过频谱感知和系统的智能学习能力，实现动态频谱分配和频谱共享。认知无线电技术在工业控制、战场侦查、野外勘查等需要多跳链路的复杂电磁环境中，具有不可比拟的优势。

由多个认知无线电收发机以自组织的形式组建而成的无线网络称为认知无线网络（以下简称为认知网络）。其中，路由研究[2]是认知网络研究的一个重要方面，在设计认知路由算法时，目前讨论较多的是基于基础设施的认知网络（即平面型认知网络），即主要用户（PU）与认知用户（CU）共同组成的网络，节点角色在网络部署前已经确定，并且在网络生命周期内保持不变。对这种网络的路由进行研究是目前的主流。

1 认知路由算法设计的挑战

由于受到认知节点频谱机会的不确定性、多频段通信的差异性、信道切换延时影响以及授权用户的干扰等影响[3]，认知用户间的通信随时可能被中断而不得不重新寻找新的可用频段，对认知网络中路由算法的研究提出了新的严峻挑战，成为了目前的研究热点。本节将从节点的SOP集合动态变化和多信道多接口两方面特性进行展开，总结分类了平面型认知网络中路由面临的主要挑战，如图1所示。

1.1 节点SOP集合的动态变化特性

认知用户当前检测到的有效频谱资源具有时变性，这就有可能使得利用之前检测到可用的频谱资源建立的路由很快失效，从而降低已经建立路由的性能和增加路由维护及路由重寻的开销。总的来说，节点的SOP集合动态变化特性，给路由算法的建立与维护带来了以下三大主要挑战。

⑴ 网络拓扑的动态变化问题

在认知网络中，认知用户通过感知技术利用主要用户的空闲频段来实现通信，当主要用户出现时，认知用户则必须进行频谱切换来避免对主要用户的通信造成干扰。而随着时间、空间或地理位置的变化，主要用户出现的概率不可预测，这就造成了认知节点的可用频谱数目和可用时间存在动态变化特性，从而导致了网络拓扑结构的不稳定。网络拓扑的这种动态变化特性会导致间歇性链接问题，从而使得如何对路由进行快速修复成为一个研究热点。如何在当前路径失效时，快速地找到一条替代的传输路径，对于提高网络的端到端性能是十分重要的，也是目前路由研究的难点之一。

⑵ 认知路由测度的设计问题

由于受到路径可靠性、频谱可利用性以及主要用户的影响，较为理想的认知路由测度应该既能反映认知网络吞吐量和丢包率，也能反映不同连接间的可靠性和等待信道切换的时延。传统的基于带宽、延时、吞吐量和能量有效等评价指标不再适合于认知网络，比如，传统无线网络在计算延时大多只需考虑传输队列的延时和路径延时等，但对于认知网络而言，节点上信道切换带来的延时，以及节点间竞争同一信道带来的延时，对于最终路由性能的影响显得更为重要。因此，设计符合认知网络路由内在性能需求的路由测度是目前研究的热点之一。

⑶ MAC层与路由层的联合设计问题

为了获得端到端的优化性能，当前的路由算法大多采用了MAC层与路由层的跨层设计思路[4-5]，基于这种思路主要有两种设计方法：去耦合设计（decoupled design）和联合设计（collaborative design）。但是去耦合设计着重于单跳通信的优化，很难达到良好的端到端的性能；其次，因为链路在信道间频繁的切换，使得对链路质量的预测变得困难，这潜在地降低了所选路由的可靠性。而联合设计则将两者融合起来对所要选择的路由、路由中每个链路上所使用的信道，以及对信道使用的时间调度等做出决策。这种设计方法能够较为准确地预测链路间的性能，提高路由选择的精确性和可靠性。但是，这种方法增加了额外的复杂性和通信开销，并使得路由选择对于频谱的波动变得敏感，任何可用频谱的改变都可能触发新的路由和信道分配过程。另外，目前的跨层设计方法主要是针对某些特定方面性能的优化，而不是着眼于整个系统层面，因此，算法的移植性差。

1.2 节点的多信道多接口特性

相对于传统无线网络而言，认知节点可以同时感知到多个可用的以连续或非连续形式存在的频段，认知节点具有的这种多信道多接口特性，对于实现节点间的通信提出了更高要求，同时也给认知路由带来了新的挑战：

⑴ “耳聋”问题

认知网络中每个节点都具有频谱检测的能力，但由于每个节点在网络拓扑中的位置和所处的无线环境并不一定相同，例如周围主要用户系统的分布、附近建筑物的影响等，这些都会影响到认知节点最终可以用哪些无线频谱资源来进行通信。当认知节点间的通信需要进行频繁地信道切换时，则会引发“耳聋”问题[6]。该问题是指：在认知网络中，当某一源节点A通过中继节点B向目的节点C发送数据包时，AB节点间首先选择频段f2实现A→B的通信，然后B节点切换到频段f3将数据包发送到C节点，在B切换回f2 之前，如果有其他的节点（如D，E，F等）以f2向B节点发送数据，则B无法接收，从而造成数据包丢失（如图2所示）。耳聋问题可能造成邻居节点之间无法监听到对方的存在，从而产生大量的孤立点，最终影响到认知网络拓扑的建立与稳定性。

⑵ 多频段通信的差异性问题

认知网络中的节点能够工作在不同的频带上，因而具有不同的传输范围及频段特性。传输范围的差异性会影响到现有高层协议性能，为了降低上层协议设计的复杂度，需要尽量屏蔽传输范围不同带来的差异。一种可能的方法是通过一些操作来调整不同频段的通信范围使之尽量统一，比如通过功率控制或者调制策略，来调整节点在某频段的通信范围。然而，调整发射功率会影响网络的连通性，同时造成资源浪费；改变调制策略会造成信道间速率差异，使得协议设计更为复杂。

现有的多信道协议（如IEEE 802.11g[7]）虽然工作于多个信道，但是每个信道的特性均相同。因此，在同构多信道网络中，节点X在其任一信道上所见的邻居集合都相同；即使节点X的邻居Y处在于X不同的信道之上，X与Y仍可能正常通信。然而在认知网络中，节点间通信的前提是它们使用相同的信道和接口且通信双方处于通信半径之中。但由于节点在不同频段上所见的邻居不同，信道和接口的选择对于通信双方都是透明的，通信双方的协调通常需要很长时间来完成，有时甚至无法协调一致，这就对认知路由算法的自适应能力提出了很高的要求。

⑶ 控制频段的选择问题

控制频段的选择对于節点间交换控制信息、路由的建立和维护是必需的。在认知无线网络中，节点的可用频段数量很大，但其无线电收发器在一定时间内只能工作在一个频段上；此外，一个节点所带的无线电收发器数量一般有限（一个或两个）。这样，节点X只有用其邻居Y正在监听的频段发送广播报文才能被Y收到。为保证每个X的邻居都能收到广播报文A，X需要在它所有频段上广播A。因此，当节点拥有的频段数量大于其无线收发器数量时，全频段广播的开销太大。

另外，由于认知节点具有不同的频段，不同频段有不同的特性、传输范围及邻居集合，使用一个控制频段的做法也不一定行得通。如图3所示，节点X有A，B，C三个频段，Y有A、B频段，Z有A、C频段，传输范围分别有RC>RB>RA。乍看起来，A是三个节点共有的频段，可以选为控制频段，然而注意到三个频段的传输范围后，如果选A频段作为控制频段，则Z不能和X交换控制频段，因为Z，X不在A频段的传输范围之内。因此，如何选择合适的控制频段成为目前认知路由的一大难点。

2 技术指标/需考虑的因素

为了获得理想的路由性能，目前的研究在设计认知路由算法时，除了考虑传统的延时、丢包率和带宽等因素外，还需考虑一些关键技术指标。

⑴ 功率控制/能耗

功率控制影响着认知路由可靠性、抗干扰能力和能量有效性。认知节点间实现通信的前提条件之一是接收机的通信半径位于发射机的通信半径之内，且位于其他发射机的干扰半径之外。通信半径与干扰半径的范围主要与发射机的功率控制相关。一般而言，干扰半径要大于通信半径，且随着发射功率的增大，干扰半径的增长幅度也要大于通信半径的增长幅度，如果发射功率过低，则接收机不能接收到数据；如果发射功率过高，则对其他用户会造成干扰。因此，在建立认知路由时，如何对发射机的功率进行控制是一个十分重要的问题。

⑵ 认知用户移动性[8]

在现实频谱环境中，认知用户不是固定存在的，例如Wi-Fi使用者能够在不同的时间不同的地点来随机地接入无线网络。当认知用户的时间或者空间发生变化时，它所能利用的频段数目和时间通常也将发生改变，认知用户的这种移动特性，对于设计稳定可靠的路由算法提出了挑战。如图4所示，考虑由4个认知用户（CU1，CU2，CU3，CU4）和一个主要用户PU组成的认知无线网络。要实现从源节点CU1到目标节点CU4的数据传输，依据经典的DSR，AODV等路由协议，选择的路由路径为CU1→CU3→CU4。但是，考虑到认知用户CU3具有越来越靠近PU的趋势，CU2具有越来越远离PU的趋势，表明CU3对主要用户PU造成的干扰将越来越大，如果选择CU3作为中继实现路由，将可能导致路由的失败，需要重新选路的概率较大。而CU2具有越来越远离PU的趋势，表明它对主要用户PU造成的干扰将越来越小，此时选择路径CU1→CU2→CU4将更能实现路由的可靠性。因此，如何在路由算法中加入对认知用户移动性的考虑，将对最终的路由性能起到重要的作用。

⑶ 链路可靠性

在认知无线网络中，由于认知用户周边频谱环境变化而引起路由失效的情况经常发生，究其原因主要是选择的通信链路可靠性较低，容易受到其他因素的干扰。因此，一个好的认知路由算法[9]应该具有一定的容错性和鲁棒性，在路由过程中尽量选择具有高可靠性的链路以提高端到端的传输性能，如果选择的链路不可靠，则会带来巨大的开销，以及降低QoS。然而，如何在众多通信链路中找到一条可靠性相对较高的链路，以及如何在部分认知节点的占用频谱变得不可用而导致部分链路失效的情况下，快速地找到一条可靠的替代路径，以避免进行大规模的路由重构，保证局部链路的可靠性，这些都是目前认知路由算法设计考虑的主要因素和难点。

⑷ 负载均衡

任何一种路由算法设计都必须重视负载均衡问题[10]。在认知网络中，对于负载均衡问题的考虑显得尤为重要。认知链路的负载均衡与否，关系到认知路由性能的多个方面，比如，如果某些认知节点上传输的数据流过多，则会给该通信链路造成大的负载，不但会影响到链路的可靠性，还会加大传输队列的排队延时，从而导致路由性能的瓶颈。另外，为了提高频谱利用率，认知用户经常利用多个频段同时进行多条任务流的传输，而由于受到可用频段变化的影响，任务流的传输经常需要进行频谱间的切换，但由于不同信道的质量特性（如带宽、占用时间等）存在差异，这种切换会导致任务流的传输冲突。现有的资源调度算法无法在动态变化的频谱环境下实现资源的有效调度，是目前研究的一大难点，从而拖累了路由的整体性能。因此，在设计认知路由算法时，应该依据问题的具体场景，从整体上来综合考虑负载均衡对于路由性能的影响，以求达到整体性能优化的目标。

3 结论与进一步的研究

本文对认知网络中路由面临的主要挑战、设计路由算法所需考虑的主要因素进行了归纳和分析。总的来说，当前的研究虽然取得了一定的进展，但是仍然还有相当多的问题需要更加深入的分析和讨论，下面列出了未来在认知网络环境下进行路由算法设计和协议研究的一些方向和建议：

⑴ 认知路由中的难解问题研究

认知路由存在着许多难解问题，比如，联合路由与频谱分配问题的最优化着色、路由发现过程中认知用户的发射机功率优化问题等。目前的工作大多将这些问题当作经典的优化问题处理，即先证明其难解性，然后采用启发式算法、近似算法、随机算法等方法求近似解。这种传统的做法往往只注重了问题的实例大小等一般性特征，而忽略了在认知无线电环境下通信的特殊性，对约束条件的参数分布特性挖掘不够，同时也缺乏面向问题特征的精确算法设计技术，从而影响了路由算法的性能。事实上，这些难解问题大多受到多个参数影响，特别是某些参数在实际应用中受到特别限制，这些限制可以很大程度地影响到问题的难解性。如何对问题进行参数化建模，并设计有效的算法技术来解决认知路由中的难题，是下一步研究工作的重点。

⑵ 大规模认知路由的基础性问题研究

现有的研究主要集中在理想环境下的认知路由研究，很少对大规模应用场景下认知路由的特性进行分析，然而由于大规模认知路由更接近于真实应用场景，因此具有更高的研究价值。要真正实现大规模认知路由，还有一些基础性问题需要解决。第一，节点的部署问题。目前的研究都假设认知节点的初始位置已知、确定，在此前提下进行路由研究，事实上，在大规模认知环境下，节点的初始部署对于随后的路由选择有较大影响。例如，在频谱资源较为丰富的大都市，由于主要用户的数量也较多，节点的部署位置如果过于松散，有可能感知不到有效的频谱资源，但是如果增加节点的个数进行高密度部署，显然成本代价过高。第二，频谱使用的局部特性分析。在大规模认知场景下，频谱能否利用显得十分复杂，不同的区域具有不同的频谱特性，要想在这种环境下找到一条可靠的、高效的路由是一个难题。

参考文献（References）：

[1] Boulogeorgos A A A， Chatzidiamantis N D， Karagiannidis

G K. Energy Detection Spectrum Sensing Under RF Imperfections[J]. IEEE Transactions on Communications，2016.64（7）：2754-2766

[2] 谢小民，王兴伟，温占考等.一种面向认知网络的 QoS 路由协

议[J].计算机学报，2013.36（9）：1807-1815

[3] Huang L， Zhu G， Du X. Cognitive femtocell networks： an

opportunistic spectrum access for future indoor wireless coverage[J]. IEEE Wireless Communications，2013.20（2）：44-51

[4] 馬晓彤，金顺福，刘建平等.认知无线电网络中的基站节能策

略及纳什均衡研究[J].通信学报，2016.37（7）：172-181

[5] Cui C， Man H， Wang Y， et al. Optimal Cooperative

Spectrum Aware Opportunistic Routing in Cognitive Radio Ad Hoc Networks[J]. Wireless Personal Communications，2016.91（1）：101-118

[6] 谢小可，唐菁敏，李静叶等.非饱和认知无线电网络MAC协议

设计[J].电子学报，2013.41（6）：1140-1145

[7] Seung-yerl Lee， Sang-sloe Lee， Je-woo Kim， Duck-jin

Chung； Dong-sun Kim. An IEEE 802.11g WLAN digital baseband processor using hybrid channel estimation for wireless home A/V receivers[J].IEEE Transactions on Consumer Electronics，2009.55（3）：1263-1270

[8] 张龙，白春红，许海涛等.分布式认知无线电网络多路径路由

协议研究综述[J].电讯技术，2016.56（4）：463-470

[9] 张沪寅，王菁，唐星.认知无线车载自组织网络中的联合路由

调度[J].计算机研究与发展，2017.54（11）：2445-2455

[10] 杨艺清，陈志刚.认知无线Mesh网络中资源节约的最小信

道冲突值组播路由算法[J].国防科技大学学报，2016.38（4）：76-84