多跳Ad Hoc网络中协作路由算法研究

方 周 吴其林 严小燕

（巢湖学院，安徽 巢湖 238000）

多跳Ad Hoc网络中协作路由算法研究

方 周 吴其林 严小燕

（巢湖学院，安徽 巢湖 238000）

协作分集是下一代无线通信的关键技术，也是近几年的一个研究热点。由于协作分集改变了传统的通信方式，需要设计新的路由机制（协作路由）以适应协作通信的特点。文章面向多跳自组织网络，依据路由设计时所考虑的源与目的节点数量的不同，从两个方面对当前协作路由算法的研究成果进行了综述，并分析当前研究中存在的问题，指出需要进一步研究的三个方面内容和挑战。

协作路由；跨层设计；协作分集；多跳自组织网络

1 引言

无线自组织（Ad Hoc）网络具有广阔的应用前景[1]。然而，Ad Hoc网络目前并没有得到大规模的应用，一个重要原因是由于Ad Hoc网络中数据接收的不可靠性。这是因为无线信号在传输过程中出现的阴影、衰落和干扰等现象以及节点的移动都会导致数据信号不被正确接收。值得庆幸的是，协作通信的出现给这些难题的解决带来了曙光，从而可以促使Ad Hoc网络得到广泛的应用。

随着无线通信技术的发展，基于空间分集思想的多输入多输出（MIMO，Multiple-Input Multiple-Output）技术可以在衰落的信道环境中大幅度提高信道容量，现已在新一代移动通信中广泛应用[2-5]。然而，Ad Hoc网络中的无线终端由于体积和功耗较小，要安装多个天线具有较大的困难。于是，人们便提出了一种新的空间分集技术，即协作通信[6-7]。在协作通信环境中，每个无线终端只需安装一个天线，即可以和其他终端协作形成一个虚拟MIMO阵列。这样，就不需要安装多个天线，但却可以获得分集增益。协作通信已是下一代无线通信的关键技术[8]，也是目前无线通信领域研究的一个热点。

在多跳的Ad Hoc网络环境中，路由选择对吞吐量、时延以及能耗等网络性能有着重要的影响。 因此，如何设计一个满足端到端服务质量（QoS，Quality of Service）要求的路由算法一直是众多学者研究的一项重要内容。协作路由算法就是将协作分集在物理层所表现出来的优势引入到网络层中以提高网络性能的一种跨层路由算法。在协作通信网络中，每个节点既可作为数据源又可作为协作节点以帮助其它节点转发数据包。为此，采用了协作路由的方式后，由于协作节点的存在，即使直接传输过程中造成了一些数据包的丢失，节点仍然可以根据协作节的传输找回这些丢失的数据包。这样，即使在信道条件比较恶劣和节点移动的情况下仍然可以保证网络中一定程度的可靠数据传输，从而保证了路由的可靠性和良好的端到端性能。然而，由于协作通信改变了传统的物理层通信方式，这也给协作路由算法的设计带来新的挑战（例如，多种类型链路共存、信号干扰加剧以及跨层设计等问题），这些问题都是需要研究的重要内容。

2 相关研究工作

协作通信的传输方式可以分为两个阶段：源节点在第一阶段以广播方式发送数据，协作节点和目的节点接收数据；第二阶段协作节点将接收到的数据转发给目的节点。最后，目的节点对从源节点和协作节点接收到的数据进行合并。因为目的节点合并了多条独立路径的数据，从而获得了空间分集增益。根据协作节点对接收到的数据进行的处理方式不同，转发方式一般可以分为放大转发 （AF，Amplify-and-Forward） 和解码转发（DF，Decode-and-Forward）两种[9]。 针对协作通信在物理层上的研究已经取得了较多的成果，因而需要研究与之相一致的媒体接入控制（MAC）层、路由层等上层协议，以充分发挥协作通信在物理层所带来的性能优势。目前，协作路由算法的设计已受到了研究者的关注，依据路由设计时所考虑的源与目的节点数量的不同，可以分别设计单源单目的与多源多目的两种环境下的协作路由算法。

2.1 单源单目的协作路由

DSDV（Destination-Sequenced Distance-Vector）[10]和 AODV （Ad-Hoc On-Demand Distance Vector）[11]是两个经典的Ad Hoc网络中的路由协议，有必要将它们引入到协作的网络环境中。于是，文献[12]提出了一种基于DSDV的协作路由算法，该算法运用分布式计算的方法在候选的协作中继集合中选择最佳的一个，并且利用跨层方法自适应调节MAC层重传次数从而达到减少时延的目的。与此同时，文献[13]也提出了一种基于AODV的跨层协作路由算法CLAODV。由于Ad Hoc网络节点的能量是受有限的，节省能量便成为了路由算法设计时需要考虑的一个重要因素。于是，Khandani等最早在文献[14-15]中提出了基于最小能量准则的两种协作路由算法CAN-L（Cooperation Along the Minimum Energy Non-cooperative path）和 PC-L（Progressive Cooperation），研究了协作路由对能量节省的影响。然而，寻找满足能量要求的最优路由属于NP难题，于是文献[16]又提出一个协作路由算法CSP（Cooperative Shortest Path）作为次优解决方案。之后，文献[17-19]也提出了能量节省的协作路由算法，其中，文献[17]分别考虑了Nakagami-m与Ricel两种不同的衰落信道环境；文献[18-19]则通过优化传输距离和协作中继数量来达到最小化能量的目的。在协作的网络环境中，某些节点可能经常被选为协作中继，从而造成这些节点的能量被过度的使用，最终将缩短网络的生命周期。为此，文献[20]提出了公平的使用节点能量的协作路由算法，以达到延长网络生命周期的目的。文献[21]则考虑多速率的网络环境，提出了SCRRM协作路由协议，以提供一条稳定的、高速率的路径。

图1 一个简单的协作路径

以上这些路由算法有一个共同的特点：算法首先需要发现一条确定的非协作的最短路径，然后在这条最短路径的基础上通过选择最佳中继或者多个中继来建立一条协作路径。显然，这些算法并没有充分利用协作分集的优点，因为最优协作路由可能完全不同于最短路径路由。如图1所示（图中S表示源节点，D表示目的节点，R表示中继节点），依据最短路径路由，则可能选择S→R1→D这条最短路径；如果运用协作分集技术，则可能选择S→R2→D这条最优路径，因为此时R3和R4可以协作S将数据传输到R2，从而使得S到R2的链路质量得以提高。为克服以上这些节能路由算法的缺陷，文献[22]提出了一种分布式最小功率协作路由算法MPCR（Minimum Power Cooperative Routing）。该算法充分利用协作通信来建立最小功率路由，并且可以在直接传输和协作传输两种模式之间进行选择。由MPCR所启发，文献[23-24]也分别提出了节省能量的协作路由算法。以上提到的协作路由大多数考虑的协作多输入单输出（MISO，Multiple-Input Single-Output，即多个传输方一个接收方）链路，为此，文献[24]提出了基于协作MIMO（即多个传输方多个接收方）链路的最小化路由算法，并给出了两种启发式算法GLC （Greedy Limited Cooperative）和 GPC（Greedy Progressive Cooperative）以简化最优化算法的复杂度。除了以节省能量为路由设计的目标之外，文献[26-28]也分别考虑以吞吐量、时延以及时延抖动作为路由设计的目标，并分别利用了源路由、位置信息以及跨层思想来设计协作路由算法。

以上这些单源单目的协作路由算法大多以节省能量或者以吞吐量和时延等性能作为设计目标，而没有将这些目标联合在一起加以考虑，即设计吞吐量、时延等受限的节能路由算法（有些需要优化的目标之间，例如最小化能量与最大化吞吐量，会存在相反作用的现象，因而联合这些目标进行路由设计具有挑战性）。与此同时，以上这些算法大多也没有考虑节点的移动性，而节点的移动往往会导致信道状态的改变以致影响中继节点的选择。为此，以上这些问题都需要进行细致和深入的研究。

2.2 多源多目的协作路由

当网络中出现多流共存时，将会引起流与流之间数据传输的冲突，这会带来网络吞吐量的降低。如图2所示，流S1→D1与流S2→D2将在协作节点B处发生冲突。文献[29]指出节点B会成为一个瓶颈，与单流环境相比较，这将会使流吞吐量下降50%，并且最早给出了该问题的解决方案。Zhang等在文献[29]中提出了MFCR-2（Multi-Flow Cooperative Routing-2）路由算法，该算法首先构造基于虚拟节点和虚拟链路的冲突图，然后再选择一条互不干扰的且能量最小的路由。文献[30]也运用了虚拟节点和虚拟链路的思想，提出了冲突感知的路由判据CSCM（Contention Sensitive Cooperative Metric），并据此提出了协作路由算法以研究系统的吞吐量和时延性能。以上两个路由算法虽然考虑了冲突对性能的影响，但并未联合物理层的干扰模型来加以分析，也没有考虑协作节点的数量选择问题。为此，文献[31]考虑了路由与中继节点选择的联合优化问题，指出该优化问题可以转换为混合整数线性规划问题，并进一步给出了解决该线性规划问题的BB-CP（Branch-and-Bound Framework Augmented with Cutting Planes）算法。然而该文献只是给出了分析结果，并没有给出路由算法的具体实现。文献[32]进一步指出在基于协作MISO链路的多流环境下，分集增益所带来的网络性能的提高与协作节点的数量以及协作路由策略重要关系，并联合链路速率与距离来优化网络性能，进而提出了自适应链路速率、距离以及簇大小变化的路由协议Proteus，以优化网络吞吐量。以上提到的路由算法（协议）没有考虑节点的移动问题，于是文献[33]考虑了移动Ad Hoc网络环境，并对ExOR协议 [34]进行了扩展，提出了协作机会路由CORMAN（Cooperative Opportunistic Routing in Mobile Ad hoc Networks），然而该路由算法只考虑了网络层的协作，忽略了物理层的协作分集。最近，文献[35-37]考虑了多流网络环境，在设计协议路由协议时考虑到了干扰和冲突的影响，但这些协议没有联合MAC层进行设计和分析。

图2 多流干扰

据此，目前对多流环境下的协作路由算法的研究还显得较少。在今后的研究中，还需要联合协作节点选择与物理层干扰模型来进行跨层设计，并且也需要对流路由进行调度，以最大化空间复用增益，以上这些问题也是本项目所要研究的内容之一。目前，已有研究者在这一方面做出了努力，在文献[38]中，作者就提出一个联合物理层、MAC和路由层的跨层协作协议MACR-CCT。

3 进一步的研究

结合前文对当前现状的分析，尽管目前在这一领域已有不少的研究并且取得了不少的成果，以下三方面的研究内容仍然值得挑战:

3.1 具有QoS约束的能量有效协作路由算法

一方面，随着无线通信技术的发展，人们要求Ad Hoc网络同时提供对数据业务和语音等实时业务的支持。因而设计一个满足用户对端到端吞吐量、时延、时延抖动以及数据包丢失率等QoS性能要求便成为协作路由算法设计的一个重要目标。另一方面，协作分集可以将一段长距离传输转变成两段短距离传输，这样在获得分集增益的同时也节省了能量，因而协作分集技术在能量受限的Ad Hoc网络中具有天然的优势，而能量最小化也自然成为协作路由算法设计的另一个重要目标。

目前研究中，大多数都是将这两个目标分别加以优化（以节能路由协议居多），而没有进行联合优化。通过分析，该研究内容需要解决以下两个关键问题：一是节能与吞吐量等QoS性能之间的折中问题。单纯考虑节能的路由算法往往会降低端到端吞吐量等QoS性能。因为以较低功率传输虽然可以节省能量，但降低了数据的成功接收概率，从而降低了端到端吞吐量。而以较高功率传输数据可以提高接收的成功率，进而提高端到端吞吐量，但随着发送功率的增大，会产生较高的干扰，反而降低了吞吐量。为此，在设计协作路由算法时，需要考虑功率和吞吐量之间的权衡。二是延长网络生命周期问题。能量有效性可以从降低数据流所消耗总能量和延长网络生命周期两个方面实现，而目前的研究大多数从第一方面来加以考虑。在协作通信中，某些节点可能经常被选为协作中继，从而造成这些节点的能量被过度的使用而消亡，最终导致通信的中断。为此，需要考虑在中继节点之间均衡地使用能量，以延长网络生命周期。

3.2 多径协作路由算法

Ad Hoc网络中的协作多径路由具有以下两个重要意义：一是能提供路径冗余，增加路由的稳定性。Ad Hoc网络中的终端节点具有移动性，这将导致链路状态不断地发生变化，从而影响系统的吞吐量与时延等QoS性能。幸运的是，多径路由正好可以降低节点移动对系统性能所产生的影响。如图3所示，从源节点S到目的节点D有三条路径S→A→D、S→B→D以及S→C→D，即使当节点D向上移动时也仍然有路径S→A→D来向目的节点传输数据。更有甚者，在协作通信中，协作多径路由还可以利用协作分集技术，这样就实现了物理层的协作与网络层的协作在网络的聚集，从而更有效地减少节点移动对链路质量的影响。二是能提供带宽聚合，以满足用户对吞吐量与时延等性能要求。如图3所示，假设每条路径的带宽均为等于1Mbps，而用户则要求网络能提供端到端的带宽为2Mbps，如果在单径路由的情况下，则没有一条路径能满足用户的要求。然而在多径路由的情况下，三条路径所带来的带宽聚合将能满足用户的要求。

图3 多径路由

图4 多流协作路由

目前，在协作多径路由方面的研究还显得较少，对该内容的研究需要解决以下关键问题：一是多径干扰问题。在多径路由中会存在传输路径的相互干扰问题，将会削弱多径路由所带来的性能增益。为此，多径路由算法需要优化选择相互独立性较高的路径，以减少干扰的影响。另外，在多径路由中，干扰会随着路径个数的增加而增加，因而需要在路径个数与系统性能之间进行折中考虑。

二是时延抖动问题。不同的路径会有不同的传输时延，因此会在目的节点处产生时延抖动。为此，多径路由算法需要优化选择路径以满足用户对时延抖动的要求。

3.3 多流协作路由算法

在现有的大多数研究中，通常认为网络中只有一条数据流，但实际上，无线网络中往往同时存在并发的多条数据流，这样就会对邻居链路造成干扰，进而影响网络的吞吐量与时延等QoS性能。对该内容的研究需要解决以下关键问题：一是干扰避免问题。干扰模型与中继节点的选择将决定信号的干扰范围，为了避免干扰，这将影响路由算法对下一跳节点的选择。如图4所示，两条数据流S1→D1与流S2→D2同时存在。如果S1选择A作为下一跳节点，此时S2如果选择C2作为协作中继，将在A出发生冲突（因为C2在A的干扰距离范围内）；如果S2选择C3作为协作中继则不会发生干扰。由此可见，S1与S2对下一跳以及协作中继的选择将会带来不同的干扰现象。因此，对于该问题，需要联合物理层与MAC以进行跨层设计。二是路由调度问题。在协作通信中，协作中继将会带来更多的暴露终端与隐藏终端，从而引起新的干扰问题，这会降低无线通信的空间复用增益 （即减少了并发传输的流数量）。为此，需要在协作分集增益与空间复用增益之间进行折中考虑，即需要对流路由进行调度，在保证协作分集增益的同时，尽可能最大化空间复用增益。

4 结论

本文从单源单目的与多源多目的两个方面，对当前的协作路由算法研究进行了较为详尽的综述。进一步地，对这些已有的研究成果进行了分析，指出其存在问题和挑战，并列出了具有QoS约束的能量有效协作路由算法、多径协作路由算法以及多流协作路由算法三个未来的研究内容，针对这些研究，我们进行了探讨并指出存在挑战。

[1]WU J，STOJMENOVIC I.Ad hoc networks[J].Computer，2004，（2）:29-31.

[2]TELATER I E.Capacity of multi-antenna Gaussian channels[J].European Transactions on Telecommu-nications，1999，（6）:585-595.

[3]FOSCHINI G，GANS M J.On the limits of wireless communications in a fading environment when using multiple antennas[J].Wireless Personal Communications，1998，（3）:311-355.

[4]CHOI J.Performance analysis for transmit antenna diversity with/without channel information[J].IEEE Transactions on Vehicular Technology，2002，（1）:101-113.

[5]PAULRAJ A J，GORE D A，NABAR R U，et al.An overview of MIMO communications-a key to gigabit wireless[J].Proceedings of the IEEE，2004，（2）:198-218.

[6]SENDONARIS A，ERKIP E，AAZHANG B.User cooperation diversity PartⅠ:system description[J].IEEE Transactions on Communications，2003，（11）:1927-1938.

[7]SENDONARIS A，ERKIP E， AAZHANG B.User cooperation diversity PartⅡ:implementation aspects and performance analysis[J].IEEE Transactions on Communications， 2003，（11）:1939-1948.

[8]LI Q， HU R Q，QIAN Y，et al.Cooperative communications for wireless networks:techniques and applications in LTE-advanced systems[J].IEEE Wireless Communications，2012，（2）:22-29.

[9]LANEMAN J N，TSE D N C，WORNELL G W.Cooperative diversity in wireless networks:Efficient protocols and outage behavior[J].IEEE Transaction on Information，2004，（12）:3062-3080.

[10]PERKINS C E，BHAGWAT P.Highly dynamic destination-sequenced distance-vector （DSDV） Routing for Mobile Computers[C].Proceedings of the Symposium on Communications Architectures，Protocols and Applications （ACMSIGCOMM’94），London，UK，1994:234-244.

[11]PERKINS C E，ROYER E M.Ad-hoc on-demand distance vector routing[C].Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications，New Orleans，LA， USA，1999:90-100.

[12]陈超，郑宝玉，赵贤敬.一种利用跨层优化策略选择中继的协作路由算法[J].电子与信息学报，2007，（12）：298l-2985.

[13]任智，郭伟，苏静，等.基于跨层协同设计的高效AODV改进路由算法[J].计算机学报，2007，（5）:838-843.

[14]KHANDANI A，ABOUNADI J，MODIANO E.Cooperative routing in wireless networks[C].In 41 st Allerton Confcrencc on Communications，Control and Computing.United States，2003:1270-1279.

[15]KHANDANI A，ABOUNADI J，MODIANO E.Cooperative routing in static wireless networks[J].IEEE Transaction on Communications，2007，（11）:2185-2192.

[16]LI F，WU K，LIPPMAN A.Energy-efficient cooperative routing in multi-hop wireless ad hoc networks[C].In IPCCC 2006，Phoenix，USA，2006:215-222.

[17]TAHERI A，ABOLHASSANI B.Energy-efficient cooperative routing for multi-hop networks over Nakagami-m and Rice channels[C].International Congress on Ultra Modern Telecommunications and Control Systems and Workshops （ICUMT），Moscow，2010:127-133.

[18]ZHANG J，FEI L，GAO Q，et al.Energy-efficient multihop cooperative MISO transmission with optimal hop distance in wireless ad hoc networks[J].IEEE Transaction on Wireless Communications，2011，（10）:3426-3435.

[19]AKSU A，ERCETIN O.Reliable multi-hop routing with cooperative transmissions in energy-constrained networks[J].IEEE Transaction on Wireless Communications，2008，（8）:2861-2865.

[20]CHEN S，HUANG M，LI Y.Energy-balanced cooperative routing in multihop wireless ad hoc networks[EB/OL].http://coitweb.uncc.edu/～ywang32/research/CC-loadbalancing-icc2012.pdf.

[21]DUNG L，AN B.SCRRM:a stability-aware cooperative routing scheme for reliable high-speed data transmission in multirate mobile ad hoc wireless networks[J].Concurrency and Computation:Practice and Experience，2015，（10）:2588-2601.

[22]IBRAHIM A，ZHU H，LIU K J R.Distributed energy-efficient cooperative routing in wireless networks[J].IEEE Transaction on Wireless Communications，2008，（10）:3930-3941.

[23]SHENG Z G，DING Z G，LEUNG K K.Distributed and power efficient routing in wireless cooperative networks[C].IEEE International Conference on Communications （ICC’09）， Dresden，2009:1-5.

[24]ABDULHADI S，JASEEMUDDIN M，ANPALAGAN A.Joint flow routing and relay node assignment in DAF multi-hop cooperative ad hoc networks[C].IEEE 6th International Conference on Wireless and Mobile Computing，Networking and Communications （WiMob）， Niagara Falls，ON，2010:638-643.

[25]DEHGHAN M，GHADERI M.Energy efficient cooperative routing in wireless networks[J].CPSC Technical Report，2009，（10）:209-234.

[26]GUAN Y，XIAO Y，SHEN C C，et al.CSR:Cooperative source routing using virtual MISO in wireless ad hoc networks[C].IEEE Wireless Communications and Networking Conference （WCNC），Cancun，Quintana Roo，2011:1119-1124.

[27]XIAO Y，GUAN Y，CHEN W，et al.Location-aware cooperative routing in multihop wireless networks[C].IEEE Wireless Communications and Networking Conference （WCNC）， Cancun，Quintana Roo，2011:761-766.

[28]HE X，LI F Y.Metric-based cooperative routing in multihop ad hoc networks[J].Journal of Computer Networks and Communications，2012，（2012）:1-12.

[29]ZHANG J，ZHANG Q.Cooperative routing in multi-source multi-destination multi-hop wireless networks[C].in Proc.IEEE Infocom，Phoenix，USA，2008:2369-2377.

[30]SHAHEN S A F M，SHARIFUL I M.CSCM:A contention sensitive routing metric for efficient cooperative communication in multi-hop wireless networks[J].International Journal on Internet and Distributed Computing Systems，2012，（2）:157-163.

[31]SHARMA S，SHI Y，HOU Y T，et al.Joint flow routing and relay node assignment in cooperative multi-hop networks[J].IEEE Journal on Selected Areas in Communications，2012， （2）:254-262.

[32]LAKSHMANAN S，SIVAKUMAR R.Proteus:multiflow diversity routing for wireless networks with cooperative transmissions[J].IEEE Transactions on Mobile Computing，2013， （6）:1146-1159.

[33]WANG Z，CHEN Y H，LI C.CORMAN:A novel cooperative opportunistic routing scheme in mobile ad hoc networks[J].IEEE Journal on Selected Areas in Communications，2012，（2）:289-296.

[34]BISWAS S，MORRIS R.ExOR:Opportunistic multi-hop routing for wireless networks[C].in Proc.ACM Conference of the Special Interest Group on Data Communication （SIGCOMM）， Philadelphia，PA，USA，2005:133-144.

[35] MANSOURKIAIE F，AHMED M H.Optimal and Near-Optimal Cooperative Routing and Power Allocation for Collision Minimization in Wireless Sensor Networks[J].IEEE Sensors Journal， 2016，（5）:1398-1411.

[36]XIE K，WANG X，LIU X.Interference-aware cooperative communication in multi-radio multi-channel wireless networks[J].IEEE Transactions on Computers， 2016， 65（5）:1528-1542.

[37]XIE K，WANG X，WEN J，et al.Cooperative Routing With Relay Assignment in Multiradio Multihop Wireless Networks[J].IEEE/ACM Transactions on Networking，2016，（2）:859-872.

[38]WU Q，ZHOU X，GE F.A cross-layer protocol for exploiting cooperative diversity in multi-hop wireless ad hoc networks[J].Wireless Networks，2016，（5）:1591-1610.

A STUDY ON COOPERATIVE ROUTING ALGORITHM IN MULTI-HOP AD HOC NETWORKS

FANG Zhou WU Qi-lin YAN Xiao-yan
（Chaohu Collge， Chaohu Anhui 238000）

Cooperative diversity has emerged as the key technology of next generation wireless communication and become research focus in recent years.Since cooperative diversity has changed the traditional communication way,it is necessary to design a new routing mechanism for accommodating the characteristic of cooperative communication.For multi-hop ad hoc networks,this paper presents the current research results of cooperative routing algorithm from two aspects because the number of the source and destination nodes is different when routing designed,analyzes the existing problem in current researches and points out the further three research contents and challenge.

Cooperative routing； Cross-layer design； Cooperative diversity； Multi-hop ad hoc networks

TP393

A

：1672-2868（2017）03-0027-08

责任编辑：陈 侃

投稿日期：2017-01-07

安徽省自然科学基金（项目编号：1308085MF101）；安徽省高等学校省级自然科学研究重点项目（项目编号：KJ2014A172）

方周（1988-），男，安徽池州人。巢湖学院信息工程学院，助教。研究方向：无线网络资源管理与调度。