无线多跳网络中一种基于网络编码的机会路由

袁永琼

（中国电子科技集团公司第二十研究所，西安 710068）

0 引言

无线多跳网络路由协议设计面临巨大挑战，主要由以下几个因素引起：（1）网络带宽资源有限；（2）信道衰落导致无线链路不可靠[1]；（3）无线媒介是广播共享信道，当多个数据链流并发传输可能导致信道存在严重的竞争和冲突。

传统无线网络路由协议的设计，通常沿袭有线网络路由协议的设计思想，将无线链路抽象为点对点的有线链路后，寻找源和目的节点对之间以某种度量作为依据的最佳路径，比如说跳数最短路径、最小代价路径或者高吞吐量路径。这种抽象也忽略了无线传输独特的广播特性和空间多用户分集增益，在有线网络环境中能够工作的很好的路由协议，对于无线有损信道不一定是最佳选择。

近年来研究工作者提出了许多新兴的技术，如机会路由[2]-[5]，网络编码[6]-[11]，充分利用无线信道的广播特性提高网络的吞吐量。由于机会路由路径的分集特性，将流间网络编码与动态选择路径的机会路由相结合，以流间网络编码感知的方式选择机会转发路径，可有效地创造编码机会，以提高链路带宽利用率和网络的吞吐量。论文正是基于该思想，提出一种基于流间网络编码的机会路由机制（ORNC，Opportunistic Routing with inter-flow Network Coding），并通过网络仿真验证了其有效性。

1 相关研究工作

机会路由中的两个关键问题是：如何选择候选节点及其优先级顺序，以及如何协调避免重复分组的发送。机会路由ExOR协议[2]允许将所有靠近目的节点的节点作为候选转发节点，通过复杂的协调调度策略来避免重复转发。Bhorkar等人提出的d-AdaptOR[4]是一种分布式自适应机会路由协议。在缺乏信道统计特性和网络拓扑信息时，以期望的平均每个分组的报酬为度量标准，选择到目的端的最优机会路径。ORCD[5]采用类似d-AdaptOR的路由策略，只是选择最佳转发节点的依据不同。ORCD结合最短路径和背压路由，提出了一种拥塞分集的机会路由策略。为了避免复杂的协调机制，作为ExOR的增强版，MORE[9]是一种独立于MAC的机会路由协议。MORE在机会路由中应用随机线性网络编码，避免了由中间节点复杂地协调由哪一个节点继续转发分组。OMNC[10]将随机线性编码、速率控制、MAC广播约束与机会路由协议相结合以提高网络的吞吐量。针对 COPE[8]协议消极编码的问题，Yan等人提出CORE[11]协议，将流间网络编码和机会路由相结合，在无线网络中创造更多的编码机会，提高网络吞吐量。

2 基于网络编码的机会路由算法

在无线多跳网络中联合流间网络编码和机会路由，本文提出一种基于流间网络编码的机会路由(ORNC ， Opportunistic Routing with inter-flow Network Coding)算法。在分组的转发过程中，以流间网络编码感知的方式选择下一跳机会转发节点，积极创造网络编码机会，通过自定义机会转发效能函数的计算结果来选择每一跳的最佳转发节点，降低分组转发次数，提高链路利用率。转发效能函数考虑以下情况：当存在网络编码机会的时候，综合评估网络编码机会和到目的节点的距离；当没有网络编码机会时考虑背压信息和最短路径以平衡网络负载，避免网络拥塞。

图1 ORNC的运行过程

在 ORNC机会路由协议设计中面临的主要挑战是如何选择下一跳转发节点和如何有效避免转发重复分组。

ORNC的路由决策是根据分组的实时接收情况以及编码机会逐跳选择下一跳转发节点。在避免转发重复分组方面，与 d-AdaptOR[4]相似，ORNC通过控制分组的交互，选择和通知下一跳节点，可以有效避免重复分组的转发。ORNC是一种低复杂度，分布式实现的算法。ORNC的运行主要包含以下四个阶段，具体如图1所示。

在 ORNC算法中，下一跳候选转发节点集选择和最佳转发节点选择策略是两个核心部分。在分别详细介绍这两部分之前，首先将本文用到的符号进行定义，如表1所示。

表1 ORNC算法－符号说明

2.1 候选转发节点集选择策略

ORNC以ETX度量转发节点到目的节点的距离为依据选择候选转发节点。在ORNC中，节点r能够被节点i选中作为流c的下一跳候选转发节点集的成员，则节点r应该满足以下条件：节点r是i的邻居节点且比节点i到达目的节点的距离更近，即r∈N(i)且 E TX (r,d)＜ E TX(i,d)。候选转发节点集包含最短路径上的节点。

当节点准备发送一个分组的时候，报头中额外附加上候选转发节点集中的节点，这些节点在控制包头中的位置按路由度量的ETX值由小到大排列。

2.2 最佳转发节点选择策略

最佳转发节点的选择是 ORNC的一个关键问题。ORNC根据候选转发节点的分组实时接收情况及该节点的机会转发效能评估的反馈信息做出路由决策，逐跳选择下一跳的最佳转发节点。节点i为分组pi选择下一跳的最佳转发节点的过程包含两步：（a）转发效能评估。机会候选转发节点集中的节点计算机会转发效能并将信息附加在 ACK分组中发送给节点i；（b）最佳转发节点选择。节点i根据机会转发效能的计算结果选择取得最大转发效能的节点继续转发分组。

（a）转发效能评估

在 ORNC中，定义了转发效能函数来评价节点的机会转发效能。机会转发效能函数综合考虑网络编码机会和以ETX度量[1]的到目的节点的距离。下面给出编码收益和机会转发效能函数的定义。

下面详细说明当一个分组候选集中的节点收到该分组时，如何计算转发效能。

首先，简要描述一下 ORNC的编码条件。ORNC采用异或（XOR）[8]运算作为网络编码的实现方式。由于下一跳转发节点有多个候选节点，ORNC的编码条件是确保所有参与编码的分组的下一跳候选节点集中，至少有一个节点可以通过解码运算从编码分组中得到所需的原始分组。具体如下：假设节点j的输出队列里有k(k＞1)个属于不同数据流的分组，用符号p1,p2,… ,pk表示，对于任何一个分组Pt，如果其候选节点集里至少有一个节点已经获得除Pt以外的k-1个分组，则节点j将这些分组进行编码后得到分组。

按照上述编码条件，节点j可以决定新收到的分组Pt是否能与队列中的其它分组进行编码。如何选择哪些分组进行编码是一个非常复杂的问题。例如，流1可以和流2编码，流2可以和流3编码，但是流1不能与流3编码，问题是选择哪两个流的分组进行编码可以获得更好的编码收益？论文旨在最大化网络的链路利用率，找到可以获得最大收益的能够一起编码的的分组可以归纳为一个最大clique 问题[12]-[13]，是一个NP完全问题。这里，论文仅考虑当前收到的原始分组与缓存中其它分组进行编码的情况。分两种情况考虑：①分组Pt能够与输出队列中的分组进行编码，则sPt=1；②分组Pt不能与任何分组进行编码，则sPt=0。下面阐述如何计算编码收益。

3 性能仿真

论文采用NS2网络仿真平台评估ORNC的性能，并与COPE[8]，DSDV[16]传输方案进行了比较。试验中参数设置如下：900m*900m的矩形网络环境，包含60个节点，MAC层采用IEEE 802.11 DCF，信道容量为1Mb/s。数据流设定为15个连接，并采用恒定比特速率业务流业务 CBR，有效载荷为1000B。随机选取每个CBR业务流的源和目的节点对，之后在单次仿真模拟运行过程中保持不变。

数据流以平均n秒为间隔产生数据分组，在前1分钟内，数据流随机开始。实验评价的性能指标包括：

（1）网络吞吐量：单位时间内所有数据流的平均聚合吞吐量；

（2）编码率：网络传输的编码分组的数量与总的发送分组的数量的比值。

图2显示了随着分组到达平均间隔变化的性能仿真曲线。随着网络负载的增加，三种传输方案下的网络都经历了从空闲到严重拥塞的过程。当网络负载较低时，网络流时间间隔大于等于0.5时，所有方案的性能表现相似，网络吞吐量和分组送达率曲线几乎重合。这种情况下网络比较空闲，不必对分组采用网络编码即可传输，这样可降低转发的复杂度以及存储开销。随着网络流时间间隔的减小，网络负载加重，DSDV的吞吐量逐渐下降，但是由于编码机会的增多，ORNC和COPE的吞吐量却呈上升趋势，当流时间间隔减少至0.35时达到COPE的吞吐量峰值，相比之下ORNC的峰值是在0.3左右。此后随着流继续增加导致网络拥塞，吞吐量反而有所减小，编码率略有降低。整个过程在大多数情况下ORNC的性能优于其他对比方案。在吞吐量方面，相对COPE，ORNC最高能提升17.4%。这是因为，由于流数量的增加，相比 COPE，ORNC结合机会转发和网络编码能创造更多编码机会，有效提升了吞吐量。但当网络拥塞严重时，所有方案的性能都逐渐下降。

图2 仿真性能结果

4 结论

结合网络编码和机会路由的优势，本文提出一种无线多跳网络中基于网络编码的机会路由（ORNC）算法。在ORNC中，以网络编码感知的方式选择机会路径。分组转发过程中，根据分组的实时接收情况和机会转发效用函数选择下一跳最佳转发节点。机会转发效用函数综合考虑了网络编码收益和到目的节点的距离。当存在网络编码机会时，可以有效减少期望的转发次数，提高网络吞吐量。仿真结果验证了ORNC能够有效提高网络的吞吐量。

[1]D.D.Couto,D.Aguayo,J.Bicket,and R.Morris.A High-Throughput Path Metric for Multi-Hop Wireless Routing[C].in Proc.ACM MobiCom,2003:134 - 146.

[2]S.Biswas and R.Morris.ExOR:Opportunistic Multi-hop Routing for Wireless Networks[J].ACM SIGCOMM Computer Communication Review,2005,35(4):133-144.

[3]D.Koutsonikolas,C.-C.Wang,and Y.C.Hu.CCACK:efficient network coding based opportunistic routing through cumulative coded acknowledgments[C].In Proc.of IEEE INFOCOM,2010:2919 - 2927.

[4]Bhorkar,A.A.,M.Naghshvar,et al.Adaptive Opportunistic Routing for Wireless Ad Hoc Networks [J].IEEE/ACM Transactions on Networking,2011,20(1):243-256.

[5]Mohammad Naghshvar and Tara Javidi.Opportunistic Routing with Congestion Diversity in Wireless Multi-hop Networks [J].IEEE INFOCOM,2010:496 - 500.

[6]Ahlswede R,Cai N,Li S R,et al.Network information flow [J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.

[7]C.Fragouli,J-Y Le Boudec,and J.Widmer.Network coding:an instant primer[J].ACM SIGCOMM Computer Communication Review,2006,36(1):63-68.

[8]Katti S,Rahul H,Hu W,et al.Xors in the air:Practical Wireless Network Coding[J].IEEE/ACM Transactions on Networking,2008,16(3):497-510.

[9]S.Chachulski,M.Jennings,S.Katti,D.Katabi.Trading Structure for Randomness in Wireless Opportunistic Routing[C].in Proc.ACM SIGCOMM’07,2007:169-180.

[10]X.Zhang,B.Li.Optimized multipath network coding in lossy wireless networks [J].IEEE Journal on Selected Areas in Communications,2009,27(5):622-634.

[11]Yan Y,Zhang BX,Zheng J,Ma J.CORE:A coding-aware opportunistic routing mechanism for wireless mesh networks [J].IEEE Wireless Communications,2010,17(3):96-103.

[12]Le J,Lui J C S,and Chiu D.DCAR:Distributed Coding-Aware Routing in Wireless Networks [J].IEEE Transactions on,Mobile Computing,2010,9(4):596-608.

[13]R.M.Karp.Reducibility among Combinatorial Problems[J].Complexity of Computer Computations,,1972:85-103.

[14]M.Neely and R.Urgaonkar.Opportunism,backpressure,and stochastic optimization with the wireless broadcast advantage[C].IEEE SSC,Jan 2008:2152-2158

[15]S.Moeller ,A.Sridharan ,B.Krishnamachari and O.Gnawali.Routing without routes:The backpressure collection protocol[C].In proceedings of 9th ACM/IEEE international conference of Information Processing in Sensor Networks,2010:279 - 290.

[16]C.E.Perkins and P.Bhagwat.Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers [J].ACM SIGCOM Computer Communication Review,1994,24(4):234-244.