潘达儒， 曹 伟， 阮兆华

(华南师范大学物理与电信工程学院，广东广州 510006)

一种基于双向数据流网络编码的无线组播机会路由

潘达儒*， 曹 伟， 阮兆华

(华南师范大学物理与电信工程学院，广东广州 510006)

针对现有机会网络编码中存在的编码机会依赖于不同数据流间的连接节点个数和编码效率等问题，结合机会通信和网络编码的特点提出一种新的路由解决方案.首先在传统无线路由算法中引入“流内编码”和“流间编码”的概念，并设计合理的网络编码策略和响应机制，以提高编码的机会和网络的吞吐量等性能.仿真实验显示，新的优化算法可显著提高网络的吞吐量和编码增益.

网络编码； 机会路由； 流内编码； 流间编码； 组播

网络编码是一种融合了编码和路由的信息交换处理技术，借助网络编码技术，网络性能可以达到最大流传输的理论极限.不论是节点还是中间节点都进行编码，以更好地利用网络带宽，提高传输的可靠性，增大网络吞吐量. LI等[1-2]证明组播数据流线性编码可获得最大容量极限.KOETTER等[3]证明编、解码可在多项式时间内完成.另外，TRACY等[4]通过理论推导对上述结论进行了证明，并提出了随机编码的概念.相对于有线网络，无线网络中无线链路的不可靠性和物理层广播特性更适合使用编码的方法，目前这方面的研究尚在探索阶段. 因此，本文针对无线网络的特殊环境，以提高网络吞吐量、减小网络开销、提高网络编码效率和编码机会为目的，对网络编码在无线网络中的应用展开研究.

1 网络编码及相关工作

COPE[5]是第一个将网络编码技术应用于实际多跳无线网络中以获得更高吞吐量的单播路由算法.该算法采用了一种基于“异或”操作的编码方案，其中每个节点监听其邻节点的报告来确定是否存在编码机会.在COPE算法中，首先通过路由协议确定数据流经过的路径，即所有的数据包沿着固定的路由进行传输，此路径上的节点对监听获得的信息进行判断，以确定是否已获得本数据流的其他数据，并进行相应编码.这种机会路由方式利用了无线网络的广播特性进行信息监听和获取，但是会导致可能没有任何编码机会的情况.如图1所示，一数据流是从节点S经节点R1到节点D，同时，另一数据流从节点D经节点R2到节点S，由于2个数据流之间没有汇聚点，因此对COPE来说这2个数据流间不存在实际的编码机会.为解决上述问题，一些研究者提出了相应的方案，如BEND[6]、ExOR[7]、MORE[8]等算法.其中BEND算法结合网络编码和机会前传的方案在具有802.11无线MESH网中获得了更多的编码机会.然而，在BEND中仅在预定路由的节点或这些节点的相邻节点上进行编码，考虑了不同数据流在相对方向上传播时的编码机会，但是没有考虑无线信道空间复用的特性而使得在同一数据流方向上的数据信息不能进行再编码处理.ExOR算法和COPE一样，通过利用无线信号的广播特性来进行机会监听并进行编码以提高单播的效率.与传统路由算法在传输数据前先判断和选择下一跳作为传输对象不同，ExOR算法使用了机会路由的方式.MIT 的RoofNet网络实现了该算法并进行了有效性测试，获得了较好的效果[9].然而，ExOR算法在实用性方面仍面临着挑战，如该算法将MAC协议和路由协议混合在一起，防止节点重复发送相同的数据包，但会带来协议的复杂性，同时使得算法很难扩展到其他业务类型的应用中.为了解决该问题，Szymon Chachulski 提出了一种与MAC层相独立的机会路由算法——MORE算法，MORE不需要特殊的算法来同步不同路由器上的信息且能够直接在802.11的MAC协议上运行.在MORE中，来自同一信源的数据包被分成束，只要在同一束中的数据包才能够进行编码，这就意味着只有来自同一个信源的数据才能进行编码，从而丧失较多的编码机会.

图1 无网络编码机会的网络场景

图1中，一数据流从节点S经节点R3到节点D，同时，另一数据流从节点D经节点R3到节点S，即使2个数据流有汇聚R3，MORE算法也不能进行编码，然而在传统的网络编码技术中，这正是进行编码的关键时机.MORE-M算法对MORE算法进行了扩展，在基于802.11的无线网络中实现了组播路由算法，但仍然存在其数据流间不能进行编码的问题.

此外，文献[10]针对COPE和MORE中的节点不需要知道全局网络拓扑结构，只在局部进行编码的问题展开分析，提出了一种编码感知的路由算法，在理想情况下可显著提高吞吐量.文献[11]指出要令节点掌握一跳邻居节点的分组接收保存情况，该节点掌握其两跳邻居节点信息以及接收分组的两跳发送节点信息是必要的，因而，COPE采用的局部编码方案可行.但是这些算法仅就其中的一类编码展开，没有同时考虑“流内编码”和“流间编码”带来的编码机会.本文提出一种基于数据流双向网络编码的机会路由算法，在传统无线组播路由算法中引入“流内编码”和“流间编码”的概念，提高编码的概率和效率，以及提升网络的吞吐量和编码增益.

2 双向流网络编码组播路由算法

2.1 网络模型

2.2 基本思想

传统的无线组播路由算法，如MAODV，DSDV等借鉴了现有有线网络中的路由机制.这些算法屏蔽掉了无线信道的广播特性而将无线信道建模成有线网络的链路来处理，因而没有充分利用无线网络中空间复用的特性.本文的算法考虑了无线信号的广播特性，在数据包传送之前，源节点首先根据传统的无线组播路由算法构建一棵基于期望传输次数(expected transmission count，ETX)作为路由度量的最短路径组播树.这里

(1)

其中，EXT是成功发送一个数据包的期望传输次数.d表示源节点s到目的节点d的数据包丢失率.其大小通过相邻两节点对过往的探测包丢包率(数据丢包率df和确认消息丢包率dr)统计，由下式确定

d=1-(1-df)(1-dr).

(2)

确定了最短路径组播树后，数据包最初将沿着该路径进行传播，但由于无线信道广播的特性，假设允许所有的节点进行监听，那么在该最短路径组播树上的节点及其相邻节点都有可能监听到树上节点广播的数据包，甚至在极端的情况下，目的节点直接监听到了源节点广播的数据包信息.这样的结果必然导致数据包不必严格按照最短路径组播树进行逐跳传输，而且由于无线信道的多径、衰减、干扰等特性，数据包经过的路径各不相同.因此，如果在监听到数据包的节点进行网络编码处理，就能提高传输的效率，提高网络的吞吐量.然而这种处理，允许节点不但能从父节点上获取数据包，还可从兄弟节点的父节点监听数据，甚至所有网络中节点都可以进行转发和监听，这样的结果会导致消息的洪泛效应，导致过多的网络开销.为把数据包限定在一个有限的范围内进行传播，本文提出的算法对上述过程进行了处理，仅让最短路径组播树上的节点或其一跳以内的相邻节点进行转发数据，这样既提高了编码的机会和转发的效率，又避免了数据必须按照预定路径逐跳传输的限制.这样处理不仅可对来自同一数据源的同一数据流进行网络编码处理——流内编码，也可以对来自不同数据源的不同数据流进行网络编码——流间编码.由图2给出的一个实际数据转发的例子来解释该算法，在图中，有一单播数据流从节点S1流向节点D1, 同时有一组播数据流从节点S2流向D2和D3，首先它们的路由由传统的路由算法确定下来，在图中分别由细虚线和实线表示.假如数据包p1、p2和p3从节点S1流向节点D1，同时数据包p4、p5和p6从节点S2流向节点D2、D3.这些数据包可以走不同的路径，从而与本数据流的其他数据包进行编码，也可以与其他数据流的数据包进行结合.如图中，节点C1监听到p2，那么在节点B2就可以对数据包p1，p2进行编码处理，我们把这种编码方式称为“流内编码”，而同时如果节点A3监听到p4，那么在节点B2也可以对p4和p2进行编码处理，由于p2和p4是来自不同的数据流，因此把这种编码方式称为“流间编码”.

图2 双向网络编码

2.3 算法细节

2.3.1 数据包结构 首先，源节点把待传输的数据包分批进行传送，每一批中数据包的数目可以不同，传送完一批次的数据包后再传送下一批次.另外，数据包可以分成3类：原始数据包、流内编码数据包和流间编码数据包.我们修改了802.11中MAC协议定义的数据结构(表1、表2)，其中，表1的参数表示如下：BatchID为批次号，用来表示本数据包属于哪一批次，主要用于连接同一批次的数据包进行编码；FlowID为数据流编号，指明本数据包属于那一数据流；Code Vector为编码矢量，由源节点提供，用于目标节点解码；Next-next Hop为原有路由上两跳以外的节点的IP地址，这个信息可以通过ETX探测丢包率时获得；Forwarder[]为潜在的路由节点列表；DATA为实际传输的数据.表2的参数：PacketID[]为已编码包的ID的列表；Code Vector []为不同流的编码矢量列表；其他参数同表1.

表1 原始包和流内编码包数据头结构

表2 流间编码数据包结构Table 2 Packet Structure of Inter-flow coded packet

首先，源节点按式(1)对原始包进行线性编码

(3)

其中，αj=αj1,…,αji,…,αjk是编码数据包pj的编码矢量，pi是同一批次的原始.当目的节点收到k个相对独立的线性编码后，根据该编码矢量进行解码.源节点收到目的节点的证实消息ACK，并确认所有该批次的数据包都已经收到后才进行下一批次的数据包传送.

2.3.2 流内及流间编码 当节点监听到数据包时，它首先检查本身节点或它的邻节点是否在潜在的路由节点列表Forwarder[]中；如果是，该节点检查收到的编码包是否具有新的信息，即与节点中缓存的同批次其他数据包是否线性独立.如果不是，将丢弃该数据包，不做处理.如果是，将随机提抽取已有的同批次包和接受到的新包进行线性编码.不难证明这种线性编码结合产生的新编码包仍然是原始包的线性编码.即

(4)

证明因为

(5)

同时，节点还能结合来自不同批次的不同数据流的2个数据包p1和p2，为简单起见，本文采用了简单的异或操作进行编码，但这种结合必须满足如下条件：

若满足上述条件，节点就能够在不需要同步化的情况下知道下一跳节点是否收到数据包从而获得编码的机会.这些信息可以通过数据包中的潜在的路由节点列表Forwarder[]获得.另外，通过扩展现有的路由算法可以为每个节点维护一张表，记录每一节点的一跳邻节点和邻节点的邻节点信息.

2.3.3 目标节点解码、确认 当目的节点收到编码数据包后，如果检查出是流间编码包，则从数据包头中提取packID并与原来已收到的数据包进行异或处理，从而解码出原始包.

如果是流内编码包，首先检查是否收取了K个线性独立的同批次包，然后使用如下逆矩阵进行解码：

(6)

当解码成功后，目的节点发送ACK消息，通知原路径及其邻节点释放相关缓存的数据包.

3 仿真实验与分析

在修改原有传统路由算法模块的基础上对上述算法进行了仿真实现.并从吞吐量、数据的传输总数和编码增益等几个方面将它与非编码的传统路由、MORE-M算法进行比较.仿真测试的环境如下：使用CBR方式在源节点产生数据流，发送速率是每次4个包，包的大小是512 bytes，发送时间间隔是0.001 s，即发送的速率约为1 Mb/s.链路延时设为10 ms，丢包概率设为0.1%.

图3显示了本文算法与其他算法在不同传输跳数情况下的吞吐量的比较.随着跳数的增加，本文算法和MORE-M算法都保持在一个较高的吞吐量水平上，而基于传统路由算法的吞吐量会随着跳数的增加急剧下降，总体上本文提出的算法的吞吐量又比MORE-M要高，这是因为传统路由随着跳数增加，传输时延急剧增加，从而导致成功传输的数据包减少而引起吞吐量下降.而在MORE-M中由于网络编码的加入，减少了部分传输数，跳数增加，编码的机会也随之增加，因而吞吐量没有出现明显的下降，本文提出的算法在流内和流间都进行编码，编码机会多于MORE-M，单位时间内传输的数据包也比后者多，因此吞吐量相对较高.

图3 不同传输跳数下的平均吞吐量比较

图4 多场景下总传输次数比较

图4给出本文算法和MORE-M算法以及传统路由算法在10个不同场景中的总数据包传输次数的比较.这里的总数据包传输次数是指所有的源节点和前传节点所发送数据包的次数总和.由图中可看出，传统的路由算法需要的传输次数最多，而本文提出的路由算法又比MORE-M少，这是由于传统的路由算法没有进行编码处理也没有利用无线信道广播的特性，传输时按源路由算法确定的组播数逐跳传输的，因此需要的传播数最多.而引入网络编码可显著带来传输数的减少，本文提出的算法比MORE-M算法提供了更多的编码机会，因此减少的传输数更多.我们还可以通过编码增益来比较编码的效率，编码增益可定义为传统的非编码路由需要的总的数据包传输数与所提出的算法传输同样的数据包需要的传输数的比值.显然这个值是一个大于1的值.由图5可知，随着节点数的增加，2个算法的编码增益都增加了，这是由于传输环节增多以后，出现汇聚节点机会增多，编码次数随之增多，另外，本文提出的算法大于MORE-M算法的编码增益，这要归功于同时采用“流内编码”和“流间编码”的结果.

图5 不同传输跳数下的编码增益比较

4 结论

在传统组播路由算法的基础上引入网络编码可以减少无线传输的次数，带来吞吐量的提升，其中的关键是寻找合适的编码时机和设计合适的编码方案.本文提出了“流内编码”和“流间编码”两种类型的编码机会，并在传统组播路由算法的基础上进行了改进，仿真测试的结果表明，与传统路由算法和MORE-M路由算法相比，显著减少了传输的总次数，提高了吞吐量和编码增益，具有一定的可行性和有效性.对于其中的网络编码处理，采用了线性编码和“异或”处理的方式，下一步的工作将对编码操作算子的选择及其效率进行进一步研究.

[1] LI Z, LI B. On increasing end-to-end throughput in wireless Ad Hoc networks[C]∥Proceedings of Conference on Quality of Service in Heterogeneous Wired/Wireless Networks. Orlando, USA, 2005.

[2] LI Z, LI B. Network coding: The case for multiple unicast sessions[C]∥Proceedings of Allerton Conference on Communications. Monticello, USA, 2004.

[3] KOETTER R,MEDARD M．An algebraic approach to network coding[J]．IEEE/ACM Transactions on Networking,2003，11(5): 782-795．

[4] TRACY Ho，RALF K,MEDARD M R K，et al．The benefits of coding over routing in a randomized setting[C]∥Proceedings of ISIT2003. Yokohama, Japan, 2003．

[5] KATTI S, RAHUL H, HU W, et al. XORs in the air: Practical wireless network coding[C]∥Proceedings of ACM SIGCOMM. Pisa, Italy, 2006.

[6] ZHANG J, CHEN Y P, MARSIC I. Network coding Via opportunistic forwarding in wireless mesh network[C]∥Proceedings of WCNC2008.Las Vegas，USA, 2008.

[7] BISWAS S, MORRIS R. Opportunistic routing in multi-hop wireless networks[C]∥Proceedings of Conference on SIGCOMM. Philadelphia, USA, 2005.

[8] CHACHULSKI S, JENNINGS M, KATTI S,et al.Trading structure for randomness in wireless opportunistic routing[C]∥Proceedings of Conference on SIGCOMM. Kyoto, Japan， 2007.

[9] MIT.MIT Roofnet outdoor network [EB/OL]. (2010-12-01)[2010-12-01]. http://pdos.csail.mit.edu/roofnet/doku.php.

[10] SENGUPTA S, RAYANCHU S, BANERJEE S. Network coding-aware routing in wireless networks[J]. IEEE/ACM Transactions on Networking,2010,18(4): 1158-1170.

[11] 董超，钱睿，陈贵海，等，无线自组织网络中流间网络编码机会发现方法的研究[J].通信学报,2011，32(10):92-98.

AWirelessMulticastOpportunisticRoutingBasedonDoubleDirectionNetworkCoding

PAN Daru*, CAO Wei, RUAN Zhaohua
(School of Physics and Telecommunication, South China Normal University, Guangzhou 510006, China)

A practical multicast routing is presented, which utilizes the broadcasting nature of wireless signaling to create coding opportunities for the wireless network.The proposed algorithm increases the opportunities for coding by applying dual network coding, an Intel-flow coding and an Intra-flow coding scheme. The simulation shows that the proposed algorithm is a better multicast routing by comparing with none coding algorithm and MORE-M in terms of coding gain, transmission reduction and throughput.

2011-10-11

国家自然科学基金项目(61172087);广东省自然科学基金项目(06300923)

*通讯作者,pandr@scnu.edu.cn

1000-5463(2012)03-0040-05

TN915.4

A

10.6054/j.jscnun.2012.06.009

Keywords： Network coding； opportunistic routing； Inter-flow coding； Intra-flow coding； multicast

【责任编辑 庄晓琼】