无线多跳网络中网络编码感知的机会转发机制

袁永琼 张 军 王 赟

(北京航空航天大学 电子信息工程学院，北京100191)

网络编码是一种提高网络吞吐量和鲁棒性的新技术［1］.网路编码最早是 Ahlswede 等人［2］提出的，并证明了使用网络编码可以达到有向网络的组播容量，而该容量是传统路由方式难以达到的.文献［3］首次提出了一种协议层面上实现的网络编码传输方案COPE，来提高无线多跳网络单播通信的端到端吞吐量.COPE利用信道的广播特性进行机会侦听和编码广播，中间节点尝试将待发送的多个数据分组进行网络编码后发送，降低局部的发送次数，提高带宽利用率，进而提高网络的整体吞吐量.数据流的传输路径由路由协议确定，编码机会依赖于不同流所选路径存在线性结构、“Y-结构”、“X-结构”等.本质上，COPE 是一种基于“机会”的消极编码策略，若多个流所选路由没有任何交叉节点，则无编码机会.

为挖掘更多的编码机会，近年来学者们提出了集中式和分布式编码感知的路由协议［4－10］.

文献［4］从理论上分析了基于COPE类型的网络编码感知的路由方式在无线网络中所能带来的吞吐量增益.文献［6］定义了一个新的度量ECX(Expected Coded transmission Count)，将编码感知的路由问题转化为线性优化问题，分析了编码感知的路由对网络吞吐量带来的提升.这两种集中式算法虽能从全局进行优化，然而算法需知道全网拓扑信息和当前流量分布的全局信息，不适用于动态无线网络.

文献［7－10］提出了分布式的编码感知路由算法，每个节点据自己了解的局部网络状态信息，在路径选择过程中考虑网络编码机会，更适用于动态无线网络.不过这几种协议多采用固定路径转发，编码机会还是有限的.上述协议为了创造编码机会，在路由发现和数据传输阶段对现有路由协议改动很大，可移植性不强.BEND协议［11］在基于IEEE 802.11的Mesh网络中利用分组在转发候选节点及邻节点之间的冗余性，类似于机会路由，动态选择有编码机会的节点进行机会转发，创造更多编码机会，来提升网络吞吐量.

若考虑到无线链路的损失特性及网络中热点问题导致分组丢失或网络拥塞，则BEND可能并不能获得预期的编码收益.面临的主要挑战是节点侦到分组后，如何选择该分组与哪些分组编码可获得网络编码收益，以及如何有效避免冗余转发.为此，本文提出一种应用于无线多跳网络中网络编码感知的机会转发机制(NCAOF，Network Coding-Aware Opportunistic Forwarding).

1 NCAOF的基本思想

NCAOF的核心思想是分组转发过程中，利用信道的广播特性导致分组在预定转发节点和邻节点间的数据冗余性，结合机会转发和网络编码，不优先使用预定的节点转发，而根据节点侦听的分组情况和所了解的局部拓扑信息，动态选择有编码机会的节点编码后机会转发，可获得更多的编码机会.

以图1所示场景为例具体说明NCAOF的基本思想.假设路由协议确定节点S1和S2处待发送报文p1和p2的局部两跳路径分别为S1→R1→T1和S2→R2→T2.对于COPE，由于没有任何交叉路径，不存在任何编码机会.不过因机会侦听，S1和S2广播报文p1和p2后，中间节点Ri，i=1，…，4，收到报文情况如图1所示.若R2或R3将编码分组p1xor p2广播，T1，T2收到 p1xor p2后能够解码出p1和p2，这样可有效减少中间节点的局部转发次数，从网络整体来看，创造了更多网络编码机会.

图1 NCAOF的基本思想示意图

类似R2，R3这样的潜在机会节点越多，编码机会越多.随之也带来了新的问题:节点如何确定将哪些侦听到分组进行编码可获得局部最大的收益?其次，由于多个机会节点存在，如何避免多个节点转发相同的分组?为此，提出网络编码感知的机会转发机制，结合了机会转发和网络编码的优势.在分组转发过程中，中间节点通过定义的编码收益函数评估节点将不同流的分组编码后的机会转发效能，选择能够获取编码收益最大的分组进行组合编码.此外，在分组调度上赋以编码分组更高的转发优先级，可高效利用编码机会同时避免分组冗余转发.从该例可看出，相比COPE和BEND协议，NCAOF可获得更好的编码机会，中间节点选择编码收益最大的分组进行组合编码而非盲目进行网络编码.NCAOF详细描述见第2节.

2 NCAOF详细描述

分组的转发过程中NCAOF机制利用无线信道的广播特性，结合机会转发和网络编码，提升网络的吞吐量.当分组p被中间节点i收到，无论i是否是路由协议指定的路由节点，都将该分组发送给网络层.网络层填next-hop和TTL域，如果本节点是路径上节点还需要填next-2Nd hop域，然后传给MAC(Media Access Control)层，MAC层执行网络编码感知的机会转发.

NCAOF包含3个部分:①分组存储机制，有效地管理存储各种类型的分组;②编码收益优化的分组组合算法，评估将哪些分组编码组合会带来的最大收益;③基于优先权的分组转发机制，有效实现网络编码机会并避免分组冗余转发.

2.1 分组存储机制

NCAOF中每个节点会处理3种类型的数据分组:①待转发的编码分组;②待转发的原始分组;③侦听到或者自己发起的分组，供解码时备用.

前两种类型的分组采用队列来存储.满足编码条件(具体见2.2.1)的分组放置在队列 Q1.待转发的原始分组放置在队列Q2和Q3，其中如果路由协议指定本节点参与该分组的转发，则将该原始分组放置队列在Q2，否则放在队列Q3.仅对Q1和Q2中的分组进行调度转发.Q3中分组只参与编码后转发，不直接转发该队列中的原始分组.对于第三种类型的分组，分配一定的缓存空间临时存储.当缓存溢出时，丢弃最早缓存的分组.采用散列表存储数据分组，方便快速查询，减少处理时间.

当队列Q1，Q2和Q3中的分组被成功发送或者已经收到下游节点发送的确认分组后，从队列中删除.

2.2 编码收益优化的分组组合算法

首先分析编码可行条件，然后给出中间节点编码收益的评价函数.最后基于编码可行条件和评价函数，详细阐述编码收益优化的分组组合算法.为了表述简便，首先对文中用到的符号加以说明，见表1.

表1 符号说明

本文采用一个称为编码结构的四元结构Ci(p，u，v，sp)来表示局部网络拓扑中一个分组 p在节点i处的状态:p是经过的部分路径为u→i→v，sp表示该分组是否是编码分组，sp=n表明p是原始分组，sp=c表明p是编码分组，n，c是常数.

2.2.1 编码可行条件

与COPE相似，NCAOF采用XOR运算作为网络编码的实现方式.为保证编码分组转发后能够被下一跳节点正确接收和解码，节点i队列中的n个分组能编码为一个分组的充要条件是参与一起编码的任何一个分组的下一跳节点已获取与该分组编码的其余n－1个分组.NCAOF中考虑两个分组一起编码，具体的实现方法如下:

假设分组 p的编码结构为 Ci(p，u，v，sp)，Q2和 Q3队列中的分组编码结构为 Ci(pj，uj，vj，spj)，j=1，2，…，J，J 为 Q2和 Q3队列长度和.那么同时满足式(1)和式(2)，可将p和pj进行网络编码.

2.2.2 中间节点网络编码收益的评价

首先给出本文对中间节点网络编码收益的定义，然后推导其计算公式.

以图2为例，推导出中间节点进行编码后转发获得的网络编码收益理论值的计算方法.

图2 NCAOF编码收益示意图

假设分组p1被指定的部分路径为a→i→b，分组p2被指定的部分路径为m→j→n.通过机会侦听，节点i收到了p1和p2，则在节点i处存在编码机会，p2可以“free-ride”在p1上发送.考虑到无线信道是有损信道，那么节点i转发编码分组p1xor p2所需发送的期望次数}为

而采用传统路由的存储转发方式，p1和p2从i→b和j→n所需发送的期望次数和为E{Ttrad}:

所以，由式(3)和式(4)可得通过网络编码减少的发送次数ΔT为

所以，来自不同数据流的分组p1和p2，经过中间节点i编码后成功送达节点b和n所获得的网络编码收益计算方法如下:

如果ΔT＞0，可获得网络编码收益，中间节点i应该发送p1xor p2给节点b和n.相反，如果ΔT≤0，表明i→b和i→n中至少有一条链路的质量较差，从统计上来说将两个分组编码后传输并不会减少传输次数，这时没必要进行编码转发.

2.2.3 编码收益优化的分组组合算法

本小节给出中间节点编码收益优化的分组组合算法.考虑局部拓扑信息及自身负载情况，利用2.2.1 节的编码可行条件发现编码，然后利用2.2.2 节定义的编码收益函数评估节点的机会转发效能，中间节点动态选择能获取编码性能最好的分组进行机会编码，来优化网络带宽的利用率.具体流程见图3.

2.3 基于优先权的分组转发调度机制

结合机会转发创造了更多网络编码机会，可有效提升链路利用率.除了创造编码机会外，有效实现这些编码机会才能真正获益.NCAOF提出采用优先权的调度机制来充分利用编码机会同时有效避免分组冗余转发.具体是:编码分组赋以更高的调度优先级和更小的信道争用窗口提高发送的优先级.队列中的分组调度采用具有优先级权重的加权轮询调度，编码分组队列的权重ωC和原始分组的队列权重ωN分别为α和1－α，其中0≤α≤1，一般应取α＞0.5，根据实际应用场景调节α的权重值，保证给编码分组更多机会发送的同时不“完全剥夺”原始分组的发送机会.

其次，由于是分布式系统，原始分组可能被多个节点侦听到并转发.为避免冗余报文，高编码收益的分组有机会优先发送，采取根据编码收益动态设置IEEE 802.11MAC中分组发送时信道争用窗口的大小τCW为

其中，ΔtCW为时间常数，它的取值为没有考虑网络编码时IEEE 802.11确定的信道争用窗口大小.由式(7)可知，随着编码收益增加，争用窗口减小，最小值为没有编码机会时争用窗口的一半.这样，编码分组竞争到信道的机会更大.在信道竞争期间，如果侦听到信道上有节点发送了该数据分组，则节点立即删除发送队列中的分组副本.

3 性能仿真

本文采用NS2网络仿真平台评估NCAOF的性能，并与BEND，COPE，传统的传输方案进行比较.所有实验中，参数设置如下:MAC层采用IEEE 802.11 DCF，信道容量为2Mbit/s.使用恒定比特速率业务流业务，有效载荷为1000 Byte.

评价的性能指标包括:

1)网络吞吐量:单位时间内所有数据流的平均聚合吞吐量;

2)数据分组送达率:成功交付目的节点的数据分组数量与源节点发送的数据分组数量之比.

3)编码机会的数量:单位时间网络中进行有效分组编码传输的次数.

3.1 简单网络拓扑

拓扑结构采用如图 1 示.S1，T1，S2，T2既是源节点也是目的节点，产生4个数据流.数据分组产生的平均间隔初值为0.1 s，间隔6 min逐步递减，直至减少到0.01 s.图4给出了不同数据传输率下4种方案的性能.

图4 简单网络拓扑场景下的性能

从图4的3个子图中可看出，当网络负载较低时，4种传输方案表现相似，网络吞吐量性能曲线几乎重合.随着网络负载的增加，增加网络编码的传输方案表现更优，从数据分组产生的平均间隔为0.07s开始，积极创造编码机会的NCAOF和BEND协议的优势开始体现.图4c显示了单位时间内发送编码分组的数量NCAOF显著高于COPE，且在网络吞吐量上NCAOF相比COPE最高提高了38.3%，相比BEND最高提高了16.4%(当数据分组产生的平均间隔为0.05 s时).随着负载继续增加，由于网络拥塞严重，NCAOF，BEND和COPE吞吐量都略有下降，不过NCAOF吞吐量和送达率仍然优于其他对比方案.

3.2 随机拓扑模型

随机网络拓扑采用NS2自带的拓扑产生工具setdest生成.模拟的网络由60个静止节点随机分布在900 m×900 m的矩形区域，数据流从这些节点中随机选取k个数据流，k从10依次增加至37.每个流平均每秒产生4个数据报文.仿真运行时间为360 s.仿真结果如图5所示.

图5 随机拓扑场景下的性能

从图5可看出，随着网络负载的增加，4种传输方案下的网络都经历了从空闲到严重拥塞的过程.当网络负载较低时，网络流数量小于等于13时所有方案的性能表现相似，网络吞吐量和分组送达率曲线几乎重合.这种情况下网络比较空闲，不必采用对报文网络编码后传输，可降低操作复杂度和存储开销.随着网络流数量的增加，网络负载加重，编码机会增多(如图5c所示)，4种传输方案的吞吐量都呈上升趋势，当流数量增加至19时达到吞吐量的峰值，此后随着流继续增加导致网络拥塞，吞吐量反而有所减小，编码机会略有降低.整个过程大多数情况下NCAOF的性能优于其他对比方案.在吞吐量方面，相对 COPE和BEND，NCAOF最高能提升13.6%和8%.这是因为，由于流数量的增加，相比COPE，NCAOF结合机会转发和网络编码创造更多编码机会;相比BEND，动态选择能获取编码性能最优的分组进行机会编码，创造更好的编码机会，避免BEND的盲目编码转发，有效提升了吞吐量.但当网络拥塞严重时，所有方案的性能都逐渐下降.

4 结 束 语

网络编码是一种有效提高网络吞吐量和鲁棒性的新技术.针对COPE协议消极编码的问题，提出了一种网络编码感知的机会转发机制NCAOF，结合机会转发和网络编码发现更多编码机会，不再优先使用预定的节点转发，而是动态选择有编码机会的节点进行编码后机会转发，提高网络的吞吐量.分组转发过程，中间节点通过获知局部拓扑信息和自身的负载情况，利用定义的节点编码收益函数评估其机会编码转发效能，动态选择能获取编码性能最优的分组进行机会编码，并赋以编码分组更高的、动态的转发优先级，使得有效利用编码机会并避免分组冗余转发.实验表明，在无线多跳网络的数据传输过程中，相比COPE和BEND，大多数情况下NCAOF能获得更好的编码机会，并有效提高了网络的吞吐量.

References)

［1］Fragouli C，Boudec J L，Widmer J.Network coding:an instant primer［J］.ACM SIGCOMM Computer Communication Review，2006，36(1):63 －68

［2］Ahlswede R，Cai N，Li S R，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204 －1216

［3］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

［4］Sengupta S，Rayanchu S，Banjerjee S.Network coding-aware routing in wireless networks［J］.IEEE/ACM Transactions on Networking，2010，18(4):1158 －1170

［5］Zhang J，Zhang Q.Cooperative network coding-aware routing for multi-rate wireless networks［C］//Proceeding of IEEE INFOCOM.Rio de Janeiro，Brazil:IEEE，2009:181 －189

［6］Ni B，Santhapuri N，Zhong Z，et al.Routing with opportunistically coded exchanges in wireless mesh networks［C］//IEEE Workshop on WiMesh.Reston，Virginia，USA:IEEE，2006:157 －159

［7］Le J，Lui J C S，Chiu D.DCAR:distributed coding-aware routing in wireless networks［J］.IEEE Transactions on，Mobile Computing，2010，9(4):596 －608

［8］樊凯，李令雄，龙冬阳.无线mesh网中网络编码感知的按需无线路由协议的研究［J］.通信学报，2009，30(1):128 －134 Fan Kai，Li Lingxiong，Long Dongyang.Study of on-demand COPE-aware routing protocol in wireless mesh networks［J］.Journal on Communications，2009，30(1):128 － 134(in Chinese)

［9］杨林，郑刚.无线多跳网中具有网络编码意识的机会路由协议［J］.清华大学学报:自然科学版，2010，50(10):1713 －1717 Yang Lin，Zheng Gang.Network coding-aware opportunistic routing protocol in wireless multi-hop networks［J］.J Tsinghua Univ:Sci＆ Tech ，2010，50(10):1713 －1717(in Chinese)

［10］Guo B，Li H，Zhou C，et al.Analysis of general network coding conditions and design of a free-ride oriented routing metric［J］.IEEE Transactions on Vehicular Technology，2011，60(4):1714－1727

［11］Zhang J，Chen Y，Marsic I.Network coding via opportunistic forwarding in wireless mesh networks［C］//Wireless Communications and Networking Conference.Las Vegas，Nevada，USA:IEEE，2008:1775 －1780