基于网络编码的无线网络路由协议

基金项目：国家自然科学基金课题(60702074)，国家科技重大专项03专项(2009ZX03006-007)，中科院无线传感网与通信重点实验室开放课题

    网络编码(NC)使得网络节点既实现路由功能又实现编码功能，已被证明是可以逼近网络容量理论传输极限的有效方法[1]。2000年，R.Ahlswede等人发表了文章“Network information flow”[2]证明了组播网络在网络编码传输模式下可以达到极大流容量理论上限。网络编码刚提出的几年，研究工作主要集中在网络编码的理论以及构造和应用等方面。从2005年后，许多国外学者开始研究无线网络中的网络编码，然而网络编码在无线网络(包括无线自组织网络、无线Mesh网络、无线传感器网络)的研究和应用还处于起步的阶段。
无线网络与有线网络中的网络编码的理论和应用有着显著的差别，这主要是由无线网络的结构特征决定的。同时无线网络环境也是网络编码非常适宜的一个应用领域。因为无线链路的不可靠性和物理层广播特性非常适合使用编码的方法。相对于传统网络编码机制来说，无线网络中的网络编码尤其能够增加单播流的吞吐量，这也是无线网络中的网络编码与传统网络编码主要区别之一，这同样得益于无线介质的广播特性。图1所示为一无线网络中3节点使用网络编码进行通信的例子：节点A、节点B相互传递信息p1、p2。图1中的箭头代表无线链路。图1(a)采用传统的无线通信方式，这样需要4次传输来完成报文的交换。但是如果利用无线介质的广播特性，将p1和p2作异或运算后直接转发出去，则在节点B处，根据接收到的信息可恢复出p1来；同理，在节点A处也可以恢复出信息p2来。因此采用了网络编码技术后(见图1(b))，只需要使用3次传输就可以实现传统方式的所有通信要求。

    基于上述思想，Katti等提出基于机会的网络编码方法(COPE)[3]，COPE是首次研究网络编码在无线环境中的协议层面上具体实现的问题。COPE协议使用机会监听以及接收报告来获取邻居节点所存储的报文信息。在得到所有邻居节点所存储的报文信息后，每个节点独立的利用本地信息决定哪些数据包需要进行编码以及如何进行编码，以最大化一次传输中所能够发送的报文数量。通过COPE，无线网络的吞吐量可以得到有效的提高。

1 无线网络中的编码感知路由协议
    当前的无线网络中的网络编码协议，如COPE等方案多半被动的等待编码机会的出现，这种被动的策略很大程度上限制了网络编码提高网络吞吐量的能力。为了更大限度的提高网络编码的性能，需要更有效的方案来在无线节点上创造出更多的编码机会以减少总的传输次数，以有效的提升网络的吞吐量。

    从COPE协议中可以看出，节点上的编码机会多少主要是由节点附近的流模式所决定的。路由协议的主要功能就是完成网络流的路由和寻址。因此如果将无线网络路由机制与网络编码机制进行有效的结合，设计出编码感知的无线自组织网络路由协议，为节点创造出更多的编码机会，就能有效的提高网络的吞吐量。如图2所示，有两个网络流，分别为从A到E以及从F到A。如果采用传统的最短路径路由机制，则两个流的路径分别为A→B→C→E以及F→D→B→A。网络中没有编码机会。如果从F到A的路径变为F→E→C→B→A，虽然比最短路径多了一跳。但是在节点C和B出创造出了编码机会，从而有效的提升了网络的吞吐量。

    下面将分别介绍采用不同策略进行编码感知路由的协议，着重介绍各协议的主要工作机制，并讨论它们的优缺点。

    无线自组织网络中的编码感知路由主要可以分为两大类：集中式和分布式。

1.1 集中式算法
    Sengupta等人[4]首次从理论分析的角度给出了COPE类型的网络编码机制在无线网络中所能带来的吞吐量提升。方案通过线性优化的方式给出了如何计算任意无线多跳网络拓扑以及任意多并发单播流量模式下的网络吞吐量，同时研究了无线路由选择与编码机会多少的折中，即将网络中并发的多个单播流以“靠近的路由方式”路由以获得更多编码机会，还是以“远离的路由方式”方式路由以减少无线干扰。同时考虑节点间无线广播传输的调度，以适应无线发送/传输的多样性以及链路间的干扰。模拟结果显示如果路由能够感知编码机会的存在，则网络的吞吐量能够比单纯的应用COPE类型的网络编码得到显著的提高。

    Ni等人[5]从另一个角度对编码感知的路由协议对网络的吞吐量所带来的提升做出了理论上的分析。协议定义了期望的编码传输数目(ECX)。与传统无线网络路由协议所采用的度量，如跳数、期望传输数目(ETX)[6]等不同，ECX定义了两个节点通过一个中间节点采用网络编码机制后成功交换报文所需的传输次数。在定义了ECX后，协议将编码感知的路由问题转化为一个线性优化的问题。模拟结果同样显示编码感知的路由可以有效提升网络的吞吐量。

1.2 分布式算法
    集中式算法能够从全局对算法进行优化，然而算法的复杂度较高、需要的网络信息量大，不适用动态无线网络(包括网络动态和流量动态)。在分布式的编码感知路由算法中，每个节点都独立地根据自己保存的网络状态信息作出路由决定，因而具有较低的协议开销以及复杂度，更适用于动态无线网络。

    (1)基于Markovian的路由度量
    Wu[7]提出了基于Markovian的路由度量来进行编码感知的路由。Markovian度量指出在某链路上发送报文的代价，可能会依赖于该报文的前一跳节点，因此能够有效地衡量出使用网络编码的情况下某条路径的路由代价。但是，Markovian度量的主要问题在于，它只能发现某条链路上是否存在编码机会，而不能发现该链路上编码机会的多少，因此可能无法找出编码机会最多的路径。

    (2)分布式编码感知路由协议
    分布式编码感知路由协议(DCAR)[8]能够找出源和目的节点间的潜在路径，并能找出这些路径上的所有潜在网络编码机会而不仅是两跳拓扑内的编码机会。源节点首先发送路径请求(RREQ)消息，RREQ消息所经过的所有节点都将其一跳邻居记录在RREQ消息中的“谁能监听”节点列表中。目的节点接收到RREQ消息后，向源节点返回路径回复(RREP)消息。中间节点接收到RREP消息后，根据“谁能监听”信息检查此流能否与现有经过该节点的流进行编码。当RREP消息返回到源节点后，源节点根据RREP消息中包含的潜在编码机会作出路由选择，找出所有具有潜在网络编码机会的路径。然而编码机会最多的路径不一定能够带来最好的性能，该路径可能过长，或者已经严重拥塞。某些不具备编码机会的路径可能反而具有较高的吞吐量。DCAR综合考虑了编码机会，拥塞等因素，定义了新的编码感知度量(CRM)用于衡量某条路径上期望的传输次数。将CRM与路由发现过程相结合，DCAR能够找出能够有效提升网络吞吐量的路由。

    (3)速率匹配的编码感知多路径路由协议
    当前的大多数的网络编码方案都假定参与编码不同的流之间的速率是一致的，而没有考虑速率不同的流之间的网络编码问题。文献[9]提出了速率匹配的编码感知多路径路由协议(RCR)。该协议能够将一个流分割成多个流以便于有效的实现流之间的速率匹配，从而有效地提升网络编码的效率。同时当前大多数无线网络中的路由协议都选择基于无线链路状态的度量，但是对于网络编码来说，基于链路状态的度量并不一定是最佳的选择。因此，RCR定义了多个基于节点的路由度量，分别用于衡量某路径的编码机会的多少，路径的匹配编码速率以及该路径的拥塞避免速率。

    在路由发现阶段，源节点向网络中广播RREQ消息，当RREQ经过网络中的中间节点时，节点将该节点的路由度量记录在RREQ消息中。目的节点收到多个RREQ消息后，分别计算出不同路径的所需传输数目，流量匹配速率以及拥塞避免速率。目的节点根据这些度量选择路径，并对不同的路径分配速率，并沿着选择的路径返回RREP消息。源节点接收到RREP消息后，根据不同路径分配的速率在多个路径对流进行传输。

    (4)编码感知多路径路由协议
    编码感知多路径路由协议(CAMP)[10]同样利用多路径以及分流来增大网络中的编码机会。CAMP协议提出了一种新的路径转换增益，用于衡量路由应该转换至哪条路径以带来较多的增益。在路由发现阶段，CAMP依据ETX信息，为源节点找出多个可用的路径。每个路径的中间节点都缓存多个可能的路由候选者，为将来的路径转换做好准备。在报文转发的过程中，CAMP动态的将缺省路径转换至新的能够最大化编码增益以及路径转换增益的路径上。CAMP的问题在于其所寻找的多路径需要在一定范围内互相临近，以便于中间节点能够转换路径，因此不能完全利用多路径的多样性。

    (5)编码感知机会路由协议
    虽然上述协议都不同程度地实现了编码感知的路由，但是，上述协议都基于传统的最短路径路由，每个节点的下一跳都是预先确定的，这对于信道并不可靠的无线网络来说可能会导致报文的多次重传。

    机会路由作为新的研究热点，已经被证明能够有效地提高无线网络的吞吐量。机会路由同样利用了无线传输媒介的广播特性，每个节点维护一个转发节点集合作为可能的下一跳，具有最优路由的节点的成为实际的下一跳节点。机会路由大大降低了报文丢失和重传的机率，同时利用那些离目的节点较近但是信道情况较差的无线链路，能够有效地降低传输次数。

    编码感知机会路由(CORE)[11]协议有效的结合了流间网络编码与机会路由。在某个节点发出报文之前，节点首先选择转发集作为可能的下一跳。转发集中的所有节点都独立计算本次传输的编码机会，并根据其编码机会的多少来进行衡量其发送的优先级。每个节点维护一个定时器，编码机会较多的节点定时器触发较早。当定时器触发时，节点进行传输。如果节点监听到了该报文被其他节点传输，则取消定时器。CORE可以同时得到网络编码和机会路由对无线网络所带来的增益。试验结果显示，CORE可以有效提升网络的吞吐量。

    (6)MAC无关机会路由
    MAC无关机会路由(MORE)[12]将流内随机网络编码与机会路由相结合。当源节点发送数据时，将所要发送的原始数据分成批，例如把每K个包作为一批。源节点将每一批数据包做随机线性编码后，不停地广播出去，每个分组携带其编码向量。中间转发节点只接受创新数据包(Innovative数据包)，即：收到一个包后，首先判断它与本地已经收到的属于该批的数据包是否线性独立，如果线性独立则将新数据包存入缓存，否则丢弃该包。当收到属于同一批次的K个Innovative数据包后，目的节点就可以恢复出原始K个数据包，并向源节点回送ACK包。源节点收到ACK后，进行下一批数据包的发送。试验结果显示，与ExOR相比，MORE可以大大提高分组成功投递率。

    (7)最优化多路径网络编码协议
    最优化多路径网络编码协议(OMNC)[13]将线性随机编码，速率控制与机会路由协议相结合以增大网络中的编码增益。OMNC以基于优化的方式控制编码报文在易丢失的无线环境中的传输。利用媒体访问控制(MAC)协议的广播特性，使得一次传输能够被多个下游节点所监听。利用随机网络编码的特性，OMNC能够保证单播传输的可靠性而不需要链路层的重传机制。

    与MORE协议相似，在OMNC中，端到端的传输是由编码报文在多个机会的路径上所完成的。然而与MORE不同，OMNC将每个节点的编码以及广播速率与其信道状态相匹配，以有效的避免拥塞，更好利用路径的多样性，减少冗余报文的传输。只要网络中的节点能够进行线性编解码操作，OMNC就能很好的提升易丢失无线网络的吞吐量。

    (8)区域联合编码与传输调度算法
    传统网络编码机制着眼于最大化单次传输内所包含的报文个数来最大化无线网络的吞吐量。然而，这种从单个节点的角度来最大化网络编码增益的做法，实际上却有可能损害整个网络的编码增益。如果每个节点能够考虑到邻居节点的编码增益进行编码传输的话，整个网络的编码增益有可能得到进一步提升。在区域联合编码与传输调度算法(PACE)[14]中，节点每次转发都着眼于提升节点附近区域中的整体编码增益，同时使用编码感知的传输调度来保证编码机会的实现。PACE使用区域编码增益作为节点传输的优先级，以此为优先级来对传输进行调度，保证临近节点的最佳传输顺序以最大化区域的网络编码增益，同时有效的减轻碰撞的发生，有效的提升网络性能。

2 结束语
    本文综述了已有编码感知路由协议的基本思想和主要协议。已有工作显示，网络编码感知的路由协议能够显著提高包括Ad Hoc网络、无线传感器网络和无线Mesh网络等在内的无线多跳网络的性能。但作为一个无线网络领域的新技术，无线网络内的编码感知路由领域还有很多问题需要进一步研究。

    (1)新型路由度量
    路由度量对路由协议的性能具有重要影响。已有编码感知路由协议主要以编码机会的多少、ETX、地理距离、拥塞程度等作为主要度量来设计编码感知的路由协议。引入新的路由度量有可能提出更有效的编码感知路由协议。

    (2)跨层设计
    现有的编码感知路由协议主要着重于路由层的协议设计。除此之外，MAC层的接入，高丢失无线信道所带来的重传等也是影响网络编码性能的重要因素。综合考虑上述因素以及应用的特点，进行编码感知跨层研究，对无线网络中的网络编码性能将起到较好的促进作用。结合编码感知链路调度的网络编码感知路由能够极大地提高网络性能，值得进一步深入研究。

3 参考文献
[1] ELIAS P, FEINSTEIN A, SHANNON C. A note on the maximum flow through a network[J]. IEEE Transactions on Information Theory, 1956,2(4): 117-119.
[2] AHLSWEDE R, CAI N, LI S Y 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[C]// Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06), Sep 11-15, 2006, Pisa, Italy. New York, NY,USA:ACM,2006:243-254.
[4] SENGUPTA S, RAYANCHU S, BANERJEE S. An analysis of wireless network coding for unicast sessions: The case for coding-aware routing[C]// Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOM’07), May 6-12,2007, Anchorage, AK,USA. Piscataway, NJ, USA:IEEE, 2007:1028-1036.
[5] NI B, SANTHAPURI N, ZHONG Z, et al. Routing with opportunistically coded exchanges in wireless mesh networks[C]//Proceedings of the 2nd IEEE Workshop on Wireless Mesh Networks (WiMesh'06),Sep 25,2006, Reston, VA, USA. Piscataway, NJ, USA:IEEE, 2006: 157-159.
[6] De COUTO D S J, AGUAYO D, BICKET J, et al. A high-throughput path metric for multi-hop wireless routing[C]// Proceedings of 9th Annual International Conference on Mobile Computing and Networking, Sep 14-19,2003,San Diego,CA,USA.New York, NY,USA:ACM, 2003:419-434.
[7] WU Y, DAS S M, CHANDRA R. Routing with a Markovian metric to promote local mixing[C]// Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOM’07),May 6-12,2007, Anchorage, AK,USA. Piscataway, NJ,USA:IEEE, 2007: 2381-2385.
[8] LE J, LUI J C S, CHIU D M. DCAR: Distributed coding-aware routing in wireless networks[C]// Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS’08), Jun 17-20,2008, Beijing, China. Piscataway, NJ,USA:IEEE, 2008: 462-469.
[9] YAN Y, ZHAO Z, ZHANG B, et al. Rate-adaptive coding-aware multiple path routing for wireless mesh networks[C]//Proceedings of IEEE Global Telecommunications Conference (GLOBECOM'08),Nov 30-Dec 4,2008, New Orleans, LA,USA. Piscataway, NJ,USA: IEEE,2008: 543-547.
[10] HAN S, ZHONG Z, LI H, et al. Coding-aware multi-path routing in multi-hop wireless networks[C]// Proceedings of the 27th Performance, Computing, and Communications Conference(IPCCC’08),Dec 7-9,2008, Austin,TX,USA.Los Alamitos, CA,USA:IEEE Computer Society, 2008:93-100.
[11] YAN Y, ZHANG B, MOUFLAH H T, et al. Practical coding-aware mechanism for opportunistic routing in wireless mesh networks[C]// Proceedings of IEEE International Conference on Communications(ICC’08),May 19-23,2008, Beijing, China.Piscataway, NJ,USA:IEEE,2008: 2871-2876.
[12] CHACHULSKI S, JENNINGS M, KATTI S, et al. Trading structure for randomness in wireless opportunistic routing[C]// Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ’07), Aug 27-31, 2007, Kyoto, Japan. New York, NY,USA:ACM, 2007: 169-180.
[13] ZHANG X, LI B. Optimized multipath network coding in lossy wireless networks[C]// Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS’08), Jun 17-20,2008, Beijing, China. Piscataway, NJ,USA:IEEE ,2008: 243-250.
[14] YAN Y, ZHAO Z, ZHANG B, et al. Mechanism for maximizing area-centric coding gains in wireless multihop networks[C]// Proceedings of IEEE International Conference on Communications (ICC’09),Jun 14-18,2009, Dresden, Germany. Piscataway, NJ,USA: IEEE,2009.

收稿日期：2009-07-30

[摘要] 基于机会的网络编码方法(COPE)研究网络编码在无线环境中的协议层面上具体实现的问题，但COPE被动地等待编码机会的出现。为了更大限度的提高网络编码的性能，需要将网络编码与无线路由协议相结合来在无线节点上创造出更多的编码机会以减少总的传输次数，以有效的提升网络的吞吐量。当前的编码感知路由算法主要包括基于Markovian路由度量的路由协议、编码感知机会路由协议(CORE)、分布式编码感知路由协议(DCAR)、速率匹配的编码感知多路径路由协议(RCR)、编码感知多路径路由协议(CAMP)等。无线网络内的编码感知路由领域中新型路由度量和跨层设计等问题还需要进一步研究。

[关键词] 无线网络；网络编码；单播路由；编码感知路由

[Abstract] Cope, an opportunistic network coding mechanism, investigates how to implement network coding in a wireless network. However, Cope passively waits for the appearance of network coding opportunities. To further improve the performance of network coding, integration of network coding and wireless routing protocol is required to greatly improve the throughput of wireless networks by creating more coding opportunities at wireless nodes. In this article, we introduce typical coding-aware wireless routing protocols, which mainly include Markovian metric based routing protocol, coding-aware opportunistic routing mechanism CORE, Distributed Coding-Aware Routing (DCAR), Rate-Adaptive Coding-Aware Multiple Path Routing (RCR), and Coding-Aware Multi-Path Routing (CAMP). Some problems like selection of new routing metric and cross layer design still require further investigation to enable efficient coding-aware routing.

[Keywords] wireless networks; network coding; unicast routing; coding-aware routing.