无线网络中最小延迟代价网络编码的研究

代 思，何加铭，郑紫微，冯 波

(1.宁波大学通信技术研究所，浙江宁波 315211;2.浙江省移动网应用技术重点实验室，浙江宁波 315211;3.中国移动通信集团浙江有限公司，浙江宁波 315042)

0 引言

在传统的网络中，网络节点的作用仅仅是完成对数据包的存储和转发。直到2000年网络编码［1］概念的提出，网络节点担任的角色才得以发生改变:网络编码允许网络节点对接收到的多个数据包编码后再发送出去。这样可以大大提高单次传输携带的信息量、减少传输次数、缓解网络拥塞以及提高网络吞吐量。

无线网络与生俱来的广播特性和侦听能力使得它非常适合网络编码的应用。Kitti等［2］在20个节点的无线网络试验床上实现了基于机会路由和异或操作网络编码的无线协议COPE。然而数据包在数量上的不公平性对编码机会的产生带来了巨大的影响。文献［3］提出了人为地延迟网络节点中暂时不能编码的数据包的发送时间，以制造更多的编码机会。但是该方法是针对TCP流提出的，并不适用在UDP 流上。Seferoglu等人［4－6］提出了基于丢包策略的编码感知算法用于调节各个数据流的发送速率，用来均衡不同流中的数据包以达到增加编码机会的目的。文献［7－8］对具有编码感知能力的路由协议展开了研究，针对COPE较被动的编码方式，在路由选择过程当中适当地选择编码机会较高的路由。

1 COPE原理

COPE的基本工作原理可以用图1所示的X型拓扑来说明。假设该拓扑中存在2条数据流如表1所示，节点1要向节点3发送数据包a，节点4要向节点5发送数据包b。在某一时刻，中间节点2同时获得了数据包a和数据包b，节点5侦听到数据包a，节点3侦听到数据包b，并且节点2可以获知到它的邻居节点所存数据包信息。此时在节点2处采取异或编码方式得到a⊕b，然后将该编码包广播发送出去。在节点5和节点3处利用本地的数据包信息可以分别从编码包a⊕b中解码出自己想要的数据包。由此可见，COPE通过3次发送达到了原来发送4次的效果，使得网络的吞吐量提高了33.3%。

图1 COPE应用的X型拓扑

表1 图1的路由表

2 MDCNC基本思想

从增加编码机会的角度出发，对采用COPE编码机制的UDP流无线网络展开研究，提出一种基于最小延迟代价的网络编码方法——(Minimum Delay Cost Network Coding ，MDCNC)。

在图2中，假设有3条数据流分别记做f1、f2和f3，各条流的路径如表2所示;则对于f1和f2，节点2是它们的可编码节点。因为节点1向节点2发送来自于f1的数据包可以被节点5侦听到，节点4向节点5发送的来自于f2的数据包可以被节点3侦听到，此时如果将来自于2条数据流的数据包在节点2处编码后再发送出去，那么在节点5和节点3处分别可以解码出各自所需要的数据包。但是对于f3，在节点2处无法找到可以同它编码的数据流。因为节点7无法侦听到节点1或者节点4发送的数据包，因此若来自于f3的数据包在节点2处同f1或f2中任何一个编码后都不能在节点7处完成解码。我们称这种情况为节点2是f3的非可编码节点。

以上情况是针对UDP流展开讨论的，如果是TCP流则不会有这种情况发生，因为TCP流与UDP流的不同之处在于TCP流存在一个ACK确认机制，文献［3］正是有效利用了ACK的确认机制，将路径相同但是方向相反的ACK包同要传输的数据包编码，使得网络编码有可能发生在沿途任何一个中继节点上。而对于UDP数据流来说不是在每个节点处都存在网络编码的机会。图2中如果采用文献［3］的延迟策略，则当节点2获得发送数据的机会且刚好待发送数据包是来自于f3时，为了等待可能到来的编码机会，会暂时不发送该数据包。但是该编码机会是不存在的，称这种延迟为非必要延迟。

图2 MDCNC应用的轮拓扑

表2 图2的路由表

MDCNC的基本思想就是减少不必要延迟次数、降低必要延迟时间，用牺牲很小的端到端延迟时间来获取更多的编码机会，相比原有的COPE协议，MDCNC可以带来更高的吞吐量。

3 MDCNC实现

3.1 可编码条件

在给出MDCNC的实现方法之前，首先给出确定可编码节点的算法。文献［2］指出，节点v要向n个下一跳节点 r1，...，rn分别发送 n 个数据包p1，...，pn，节点 v处可以将这 n个数据包异或编码的充分必要条件是每个下一跳节点ri都已经拥有n－1个数据包pj，其中 j≠i。文中仍然考虑2跳以内的网络编码情况，给出可编码节点要满足的条件:

式中，c表示待判定节点，F表示新增加的一条数据流，用Fi标识 c处已经存在的其中一条数据流。N(c)表示c的一跳邻居节点集合。U(c，F)表示F上c的上一跳节点，D(c，F)表示F上c的下一跳节点。若要判断节点c是否为新增数据流F的可编码节点，只要满足式(1)和式(2)，就能说明节点c为新增数据流F的可编码节点。

3.2 路由发现过程

当节点Vsrc准备向节点Vdest发送数据并发现路由表中没有相应路由项时，Vsrc启动路由请求过程。

步骤1:Vsrc生成一个RREQ包并向自己的邻居节点广播出去，在被广播之前需要初始化RREQ包中的一系列参数。每个中间节点Vi将首先丢弃路径记录中已经包含Vi的地址的RREQ包，以防止出现路由环路。否则，RREQ包中的信息被更新后广播出去。

步骤2:RREQ到达目的节点Vdest之后，目的节点会选择一条最优路径，然后生成一个路由回复RREP包，将其沿着与来时相反的方向发送至源节点Vsrc。每个中间节点Vi首先根据RREP包中的信息更新路由表以建立到目的节点的正向路由。然后，Vi根据邻居信息应用式(1)来判断本身是否为该路由的可编码节点，Vi将该判断结果记录下来。Vi继续转发RREP包。

步骤3:源节点Vsrc接收到RREP后，开始根据选定的路径发送数据包。

路由发现过程是在现有的AODV路由协议上做的改进，只需要加入步骤2中可编码节点的判断，这样做的好处是实现了网络的平滑过度。

3.3 MDCNC实施方案

图3中的算法流程图描述了MDCNC编码的具体实现方案，整个过程可以分为发送和接收两部分。在每个节点Vi处都维护了3个FIFO队列(Q1、Q2、Q3)，Q1用于存放将该节点作为下一跳节点发送过来的数据包，Q2用于存放该节点侦听到的数据包，Q3用于存放等待编码机会的数据包。

图3 MDCNC编码实施方案

当节点Vi接收到一个数据包后，首先判断该数据包是不是编码数据包，能不能完成解码。接下来检查该数据包下一跳节点列表中是否包含Vi节点，如果没有则说明Vi不是该数据包的下一跳节点，将其保存在Q2中;如果是下一跳节点，还要判断Vi是否为目的节点。

节点Vi获得一次发送数据包的机会后，先处理Q3中的数据包，再处理Q1中的数据包。

对于Q1中的数据包，根据先进先出原则，首先对放在队首的p1进行编码能力的判断，判断Vi是否为它的可编码节点。如果是可编码节点再接着查看编码机会，存在编码机会则编码后发送编码包;假如是可编码节点，但此时却没有编码机会，则将p1移动到Q3中等待可能到来的编码机会。

对于Q3中的数据包，如果没有超过设定的延迟等待时间，则继续等待，如果超过了延迟等待时间，则检查此时是否有编码机会到来，有编码机会则编码后发送出去，没有编码机会则不编码直接发送。

4 仿真分析

4.1 评价指标确定

MDCNC的设计目的在于增加数据传输过程中的编码机会，因此选取吞吐量、平均端到端延迟和编码次数作为性能好坏的评价指标。

4.2 仿真环境设置

仿真环境为 NS2［9］，MAC层协议采用 IEEE 802.11 DCF，信道容量为2 Mbit/s，节点的数据发送队列大小为50，节点的传输范围为250 m，数据源采用的是CBR流，数据包大小为512 byte，MDCNC中数据包延迟发送时间设置为1.5 s。分别对AODV、AODV+COPE和AODV+MDCNC这3种传输方式进行比较。

4.3 仿真结果及分析

4.3.1 固定网络拓扑

为了直观地说明MDCNC的优点，首先在图2所示的轮拓扑中比较上述3种传输方式的性能，数据发送速率设定在0～1400 kbit/s之间，选取其中的19个采样点作为性能分析的参考数据，f1和f2采用不同的数据发送速率:

图4和图5展示了在不同速率下3种传输方式的网络吞吐量和平均端到端延迟的变化情况。从折线对比图中可以看出在速率非常小的情况下3种传输方式对网络吞吐量影响差异不是很大，而MDCNC的平均端到端延迟略微高于其他两种情况。但是随着数据发送速率的逐渐增大，大概从180 kbit/s开始，可以编码的COPE和MDCNC的吞吐量逐渐超出了不能编码的AODV和AODV的端到端延迟时间也迅速增大，COPE和MDCNC的端到端延迟均没有什么变化。由于采用了延时机制，MDCNC的端到端延迟时间会略微高于COPE，此时MDCNC相对于COPE的优势并没有明显表现出来。但是随着速率的继续增长，COPE的网络吞吐量上升开始变缓，MDCNC迅速超过了COPE。在400 kbit/s左右时，由于可编码的2条流速率不匹配问题以及发送队列的容量问题，使得COPE的编码机会出现减少的趋势，网络吞吐量开始下降，端到端延迟迅速上升。而MDCNC所特有的延迟机制以及更大的队列空间使得它的编码机会还在增加，吞吐量仍然保持上升，MDCNC的端到端延迟也略低于COPE，MDCNC的吞吐量优势显现出来。当速率达到900 kbit/s时，由于严重的网络拥塞，3种方式的吞吐量变化都趋于平缓状态，端到端延迟也达到最大。

图4 3种传输方式的网络吞吐量变化

图5 3种传输方式平均端到端延迟变化

图6表示的是在不同速率下COPE和MDCNC编码次数的变化情况。在数据发送速率非常小的时候，两者的编码次数相差不大，随着数据发送速率的增加，MDCNC的编码次数要明显高于COPE。

图6 MDCNC与COPE编码次数对比

4.3.2 随机网络拓扑

为了使MDCNC协议的评价更具普遍性，在一个随机拓扑网络模型下进行多次实验。主要评价指标为不同数据流数目下MDCNC与COPE编码次数的变化。实验环境为利用NS2中setdest工具创建一个长、宽各1000 m，拥有50个节点的移动场景。节点的移动速度最大为2 m/s，仿真时长为150 s，选取数据流数目为2～20之间的10个数值，每个数值下进行100次实验，取平均值。

由图7可以看出，MDCNC中的编码次数明显高于COPE，这说明MNCNC能够制造更多的编码机会，进一步提高网络吞吐量。

图7 随机拓扑中MDCNC与COPE编码次数对比图

5 结束语

针对COPE会受数据包数量不公平性的影响，提出了一种可以应用在无线多跳网络中的最小延迟代价网络编码方法MDCNC。该方法的主要特点是只有在可编码节点处才会采取延时策略，这样做的目的是尽可能少地增加端到端延迟时间。从仿真结果可以看出虽然MDCNC的平均端到端延迟大部分情况下会略微高出COPE，但是却比没有网络编码的AODV低，所以这样的延迟时间在网络容忍范围之内，对于网络性能并无太大影响。而该方法所制造的编码机会却是不可忽视的，与COPE相比较，MDCNC的编码机会约为COPE的1.5倍，能够有效地缓解网络拥塞和提高网络吞吐量。

［1］AHLSWEDE R，CAI N，LI S，et al.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204 －1216.

［2］KATTI S，RAHUL H，HU W，et al.XORs in the Air:Practical Wireless Network Coding［C］∥SIGCOMM ＇06 Proceedings of the 2006 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications，ACM，36(4):243 －254.

［3］HUANG Y，GHADERI M，TOWSLEY D，et al.TCP Performance in Coded Wireless Mesh Networks［C］∥Proc.Of IEEE SECON，2008:179 －187.

［4］SEFEROGLU H，MARKOPOULOU A.Network Codingaware Queue Management for Unicast Flows over Coded Wireless Networks［C］∥IEEE International Symposium on Network Coding(NetCod)，Toronto，Canada，June 2010:1－6.

［5］SEFEROGLU H，MARKOPOULOUA，MEDARDM.NCAPQ:Network Coding-Aware Priority Queueing for UDP Folws over COPE［C］∥International Symposium on Network Coding(NetCod)，Beijing，China，July 2011:1 －8.

［6］COPPI N D，NING J X，PAPAGEORGIOU G，et al.Network Coding Aware Queue Management in Multi-Rate Wireless Networks［C］∥ The 21stInternational Conference on Computer Communications and Networks(ICCCN)，Munich，GER，July 2012:1 －7.

［7］樊凯，李令雄，龙冬阳.无线mesh网中网络编码感知的按需无线路由协议的研究［J］.通信学报，2009，30(1):128－134.

［8］LE J L，LUI J，CHIU D M.DCAR:Distributed Codingaware Routing in Wireless Networks［J］.IEEE Transactions on Mobile Computing，2010，9(4):596－608.

［9］徐雷鸣，庞博，赵耀.NS与网络模拟［M］.北京:人民邮电出版社，2003:10－174.