2015, Vol. 26
2 南京大学 计算机科学与技术系, 江苏 南京 210093
2 Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China
一直以来,网络中间节点(如路由器)以存储-转发的方式实现信息的多跳交付.网络编码(network coding,简称NC)的提出,颠覆了传统的网络传输观念,在存储-转发的基础上,中间节点还可以对信息进行编码,并在网络中传输编码后的信息[1,2],即,存储-编码-转发.大量研究表明,网络编码是改善网络吞吐量[3, 4, 5, 6, 7, 8]、可靠性[9,10]以及时延[11,12]性能的有效途径.按照编码的形式不同,网络编码可分为流内网络编码(intra-session network coding)和流间网络编码(inter-session network coding)两类:流内网络编码将单个数据流的多个分组编码在一起传输,以改善传输效率[13, 14, 15, 16, 17, 18, 19];流间网络编码则用于优化多个数据流并发时的网络吞吐量[20, 21, 22, 23, 24]等性能.
流间网络编码中一个至关重要的概念是编码机会(coding opportunity):多个数据流在交汇节点被编码转发后,如果某个数据流可以在其下游节点上被解码,则称该数据流获得了一次编码机会.如图 1所示,节点A需要发送分组P1给节点B,同时,节点B需要发送分组P2给节点A.由于传输距离的限制,节点A与节点B之间通信需要经过节点R中继.假设信道无丢失,那么完成上述分组交付总共需要4次传输,如图 1(a)所示.如果节点R将接收到的P1和P2进行异或,并发送该编码分组,节点A和B接收该编码分组后可分别解码获得所需原始分组,此时总共需要3次传输,如图 1(b)所示.此时,两条数据流均获得了一次编码机会.显然,编码机会正是流间网络编码性能增益的源泉.如果网络中没有编码机会,那么网络编码便无从开展;当网络中存在较多编码机会时,流间网络编码才有可能获得高的性能增益.然而,实际网络中自然存在的编码机会数量通常十分有限[25,26],这从根本上限制了流间网络编码可获得的性能增益.
 | Fig. 1 An example of inter-session NC图 1 流间网络编码示例 |
提高流间网络编码的性能,需要从提高编码机会的数量这一根本问题入手.编码机会形成于数据流间的相互作用,其数量取决于各个数据流流量的空间分布[25,27],因此,路由选择成为影响编码机会数量的关键因素.如图 2所示的网络中:数据流F2选择路由B®D®A时,网络中没有编码机会;而当F2选择路由B®C®A时,两个数据流在节点C获得一次编码机会.Ni指出:使用具有网络编码感知能力的路由选择策略可以主动创造编码机会,从而有效改善流间网络编码的性能[28].网络编码感知路由(network-coding-aware routing),或者简称为编码感知路由因此被提了出来,通过主动探索、创造并利用网络中潜在的编码机会,编码感知路由能够有效克服被动使用编码机会制约流间网络编码性能这一问题.
 | Fig. 2 Routing selection can affect coding opportunity图 2 路由选择影响编码机会 |
为了有效地创造编码机会,编码感知路由需要解决两个关键问题:
· 首先是如何发现网络中潜在的编码机会.编码感知路由需要解决编码机会存在的一般规律,并基于此设计现实可行的编码机会发现方法;
· 其次是如何评估路由优劣.编码感知路由不仅需要考虑传统的影响路由性能的因素,还需要考虑编码机会的影响,从而设计适用于网络编码条件下的路由评估标准,即编码感知的路由度量.
以上两个问题中,第1个问题是编码感知路由需要解决的核心问题.由于编码机会形成于数据流间的相互作用,其存在及数量取决于数据流流量的空间分布,因此,数据流流量的空间分布模式成为判断编码机会存在与否的直接依据.本文将满足编码机会存在条件的数据流流量空间分布模式称为编码结构(coding structure).对于给定编码结构,编码感知路由通过匹配对编码结构即可判断编码机会是否存在,并在此基础上作路由决策.
本文对编码感知路由协议进行综述,主要贡献在于首次系统地归纳了各类编码结构,并以此为主线介绍编码感知路由的研究现状.本文第1节阐述编码机会的创造方法,总结分析现有的编码结构.第2节介绍具有代表性的编码感知路由协议.第3节讨论编码感知路由中有待解决的问题.第4节总结全文.
1 编码结构编码感知路由的本质是对编码机会的创造,如何创造编码机会,是编码感知路由的核心问题.虽然目前已有不少编码感知路由协议的研究与实验,但仍然缺乏从编码结构的角度对编码机会创造方法的系统总结.本节将首次对编码结构进行归纳总结.
编码机会形成于数据流间的相互作用,其存在与否,取决于数据流的流量空间分布.因此,数据流之间的拓扑关系成为判断编码机会存在与否的直接依据.本文将满足编码机会存在条件的网络流量空间分布模式称为编码结构,创造编码机会的问题由此转化为构造编码结构的问题,即:调整数据流路由,使流量分布模式满足给定的编码结构.根据编码机会的不同形式(如单跳还是多跳、是否使用机会侦听),编码机会可被分为不同类别,每一类编码机会对应不同的编码结构.本节将介绍具有代表性的几个编码结构.需要注意的是,不同的编码结构不是完全独立的,它们之间存在交叠与包含关系.
为了方便余下章节的描述,定义符号见表 1.
|
Table 1 Notation definition 表 1 符号定义 |
单跳编码结构(single-hop coding structure,简称SCS)是最基本、最简单的编码结构,要求编码分组在下一跳被立即解码.单跳编码结构分为不使用机会侦听和使用机会侦听两种情况,分别记为SCS-O(single-hop coding structure without listening)和SCS-W(single-hop coding structure with listening).
1.1.1 SCS-O典型的SCS-O如图 1(a)所示,两条数据流方向相反经过3个共同节点A,R和B,由于每个数据流的关于中间节点的下一跳节点同时又是另一个流的关于中间节点的上一跳节点,根据图 1(b),中间节点将两个数据流的分组编码为一个分组发送后,每个下一跳节点都可以利用该编码分组以及缓存的本节点发送的分组解码得到自己需要的原始分组.这种网络编码方式也被形象地称为Reverse Pooling,形容两个逆向数据流为对方提供无耗费的传输服务(free ride).因为不使用机会侦听,这种编码方式只允许两个数据流参与.ROCX,IROCX,MMR,CAMP和RCR等编码感知路由协议中都使用SCS-O构造编码机会.在SCS-O情况下,中间节点根据缓存数据包的上下游节点信息即可判断编码机会是否存在,其实现相对简单.
SCS-O可以形式化地描述为:数据流f1和f2相交于节点C时:
机会侦听允许节点从无线广播信道中接收目的节点不是自己的分组.解码节点可以将侦听分组用于解码,这扩展了编码结构的形式,增加了编码机会的数量.
典型的SCS-W如图 3(a)所示,节点C和D能够分别侦听到节点A发送给节点R的分组以及节点B发送给节点R的分组,所以,节点R将两个数据流编码发送后,节点C和D都可以利用侦听分组解码得到所需原始分组.使用机会侦听的编码结构可以包含两个以上的数据流,图 3(b)中所示节点R可以将4个数据流编码在一起传输.使用SCS-W的编码感知路由协议主要有LP-code,PCAR,ANCHOR,OCR,NCAR等.
 | Fig. 3 Examples of SCS-W图 3 使用机会侦听的编码机会示例 |
SCS-W可以形式化地描述为:数据流f1,f2,…,fN相交于节点C时:
单跳编码结构要求编码分组在一跳传输后被立即解码,不能被解码的编码分组将被立即丢弃.相比之下,允许编码分组在多跳外被解码提高了编码包的利用率.考虑多跳时的情况,MCS(multi-hop coding structure)将解码节点扩展到编码节点一跳以外,JCS(joint coding structure)则进一步允许单个编码分组在多个节点上被逐步解码.此外,GCS(general coding structure)则考虑了多个编码流并存时存在伪编码机会的问题.
1.2.1 MCS多跳编码结构(MCS)被提出于DCAR[29]中,允许编码节点的任意某个下游节点充当解码节点.因为放松了对解码节点的要求,MCS可以创造较SCS更多的编码机会.如图 4所示,距离编码节点C两跳的节点H,可以利用编码分组P1ÅP2以及侦听分组P1解码得到P2.目前,DCAR和OCAR[30]中采用了MCS.
 | Fig. 4 An example of multi-hop coding opportunity图 4 多跳编码机会示例 |
MCS可以形式化地描述为:数据流f1,f2,…,fN相交于节点C时:
联合网络编码被提出于NJCAR[31]中,它不要求编码分组被一次性解码,而是允许单个编码分组在多个节点被逐步解码.与MCS相比,JCS进一步放松了对解码节点的约束,因而可以获得更多的编码机会.从信息利用的角度看,JCS利用多个节点的本地信息解码某个编码分组,因此具有更高的信息利用率.图 5(a)所示的网中有3个数据流,每个数据流的源节点分别发送一个分组后,网络中每个节点的分组缓存状态如图 5所示.在传统解码方式下,中间节点H必须分2次发送分组P1,P2和P3,否则,节点H发送编码分组P1ÅP2ÅP3后,F1的下游节点,即节点E和节点F,都无法独立解码得到P1.事实上,节点E和节点F可合作解码该编码分组.节点F将P3从编码分组P1ÅP2ÅP3中消去得到P1ÅP2后,将P1ÅP2转发给节点E,节点E再次解码即可得到P1.图 5(b)描述了以上解码过程.
 | Fig. 5 An example of joint decoding图 5 网络联合解码示例 |
对于数据流f而言,如果编码节点的全体下游节点能够共同收集编码分组中除本数据流以外的其余数据流的原始分组,这些节点就可以合作解码得到本数据流的原始分组.
JCS可以形式化地描述为:数据流f1,f2,…,fN相交于节点C时:
2011年,Guo等学者发现,已编码的数据流交汇可能导致出现图 6(a)所示的伪编码机会,并提出了解决方案,即GCS[32].根据MCS,F1和F3可在节点R1被编码,F2和F3可在节点R2被编码.然而,当节点R1和R2同时使用编码操作时,节点D2将无法解码,因此,R2上的编码机会实际为伪编码机会.不难发现,伪编码机会出现的原因是:网络中并存的多个编码结构相互之间产生了干扰,导致解码失败.针对这一问题,GCS对编码节点的上游节点以及下游节点增加了更多的限制,以避免产生伪编码机会.
 | Fig. 6 An example of fake coding opportunity and GCS图 6 伪编码结构及GCS示例 |
GCS可以形式化地描述为:数据流f1,f2,…,fN相交于节点C时,任意fi至少满足下列条件之一:
1) 存在一个节点C的上游节点,该节点解码或者侦听得到本数据流的原始分组,如图 6(b)所示;
2) 存在一个节点C的下游节点,该节点能够解码得到本数据流的原始分组,如图 6(c)所示;
3) 存在一个节点C的下游节点,该节点能够解码得到某个(编码)分组,从而该节点的下游节点可以利用该编码分组解码得到本数据流的原始分组,如图 6(d)所示.
1.3 编码结构之间的联系在上述编码结构中,SCS-O,SCS-W,MCS,JCS用于判断单一编码结构的编码机会,其中每一个都在前者的基础上扩展了网络编码的形式,能够更充分地利用编码机会,获得更大的编码增益.SCS-W允许机会侦听,松弛了解码节点的信息来源约束;MCS允许多跳解码,松弛了解码节点的位置约束;JCS允许多节点合作解码,松弛了解码形式约束.这一演化过程也体现于编码感知路由协议中,以利用更多形式的编码机会,进而改善吞吐量.需要注意的是,利用复杂的编码机会同时也会带来一些新的挑战:首先,复杂的编码机会更多地依赖于机会侦听以及更多、更远节点的参与,这都使解码更加脆弱,更容易导致解码失败;其次,判断复杂的编码机会对拓扑信息的需求更高,不仅需要编码节点的邻居信息,还有其邻居之间的邻接关系,甚至是多跳外的解码节点的邻居信息.
与前面4个编码结构不同,GCS针对网络中共存的多个编码流相互干扰而造成伪编码机会这一问题,对编码结构增加了一些新的限制条件.因此准确地讲,GCS并不能算是一个真正意义上的编码结构.最后,表 2总结了5种编码结构的时间演进关系.
|
|
Table 2 Evolution of coding structure 表 2 编码结构的时间演进关系 |
本节对编码感知路由进行分类,并围绕编码机会创造这一主线介绍具有代表性的编码感知路由协议.编码感知路由的本质是编码机会创造,因此,我们根据所采用编码结构对编码感知路由协议进行分类,如图 7所示.机会路由(opportunistic routing)/确定性路由、非编码感知路由/编码感知路由是路由的两种分类方式,非编码感知路由可以是确定性路由,也可以是机会路由.同样,编码感知路由可以是确定性路由,也可以是机会路由.与传统的确定性路由不同,机会路由不使用确定性路由,不预先指定下一跳接收节点,因此单独归为一类.
 | Fig. 7 Taxonomy of NC-aware routing protocol图 7 编码感知路由分类 |
本节按照图 7所示的分类方式介绍具有代表性的编码感知路由协议.
2.1SCS-O编码结构此类编码感知路由协议仅仅使用最基本的网络编码形式,即,利用两个数据流逆向传输时形成的编码机会.
(1) ROCX
Ni等人于2006年提出了编码感知路由的概念,并提出了第一个编码感知路由协议ROCX(routing with opportunistic coded exchange)[28].为了描述编码机会的益处,Ni等人定义了ECX(expected number of coded transmission for an exchange)路由度量,表示可编码条件下,两个节点通过一个中间节点交换一对分组所需的期望传输次数.记ri,j为节点i和节点j之间的链路的往返交付率,那么:
比不使用网络编码时减少了
.他们将编码感知路由建模为一个线性规划问题,优化目标为最
小化全网所有数据流的ECX的总和,其数值分析结果验证了编码感知路由的有效性.
(2) IROCX
ROCX仅仅给出期望传输次数的结论,并且未能考虑实际网络约束.IROCX(interference-aware routing with opportunistic coded exchange)在ROCX的基础上作了两个方面的改进[33]:首先,IROCX将链路上的流量限制在链路带宽容量以内;其次,考虑到无线干扰,IROCX将处于同一个团中的无线链路的信道接入率之和限制在100%以内.IROCX进而修改了ROCX中规划模型的约束条件,并以最小化ECX为目标选择路由.仿真结果表明,IROCX可以容纳较ROCX更多的数据流.
(3) MMR
Wu等人在2007年提出适合于描述网络编码环境下链路耗费的路由度量形式MMR(Markovian metric for routing)[34].使用网络编码时,数据流在某一跳链路上的编码机会的数量取决于前一跳链路上的反向背景流量,因此,该链路上的耗费与前一跳链路的状态相关.在这种情况下,路径的耗费不再能够简单地分解为链路耗费之和,最终导致无法使用最短路径算法.针对这一问题,MMR定义了条件耗费的概念:
其中,vk-1®vk是数据流路径上关于vk®vk+1的上一跳链路.从而,路径耗费可分解为
针对条件MMR,Wu等人还设计了点图以支持通用最短路径算法.点图在原图的每条边上增加一个点,点与点的连线构成条件边,其上的耗费即是条件耗费,如图 8所示.
 | Fig. 8 An example of dot graph图 8 点图示例 |
最后,Wu等人提出了具体的编码感知的路由度量ERC(expected resource consumption)以描述数据流对网络资源的消耗.如果一次发送包含了k个数据流的分组,那么这k个数据流均分此次传输所耗资源.
(4) CAMP
Han等人提出使用多径传输策略的编码感知路由协议CAMP(coding-aware multi-path routing),其特点是:可在数据传输阶段对局部路由进行动态调整,从而利用编码机会[35].在路由发现过程中,中间节点以及源节点缓存到目的节点的多条候选路径.在分组转发阶段,源节点选择候选路径中ETX最小的k条,并将业务流量按照ETX的正比关系分配在所选路径上同时传输.为了利用动态出现的编码机会,CAMP允许中间节点根据情况调整局部路由,即,切换使用缓存的候选路由,切换条件是切换后总的期望传输次数减少.
例如图 9中,节点A向节点D发送分组P1,节点B向节点C发送分组P2,此时,E节点没有编码机会.节点E切换使用路径E®B®D以及E®A®C以后,节点E可发送编码分组P1ÅP2,随后,节点A解码得到P2并转发至节点C,节点B解码得到P1并转发至节点D.可见:CAMP创造并利用了节点E上的编码机会,减少了总的传输次数.
 | Fig. 9 An example of routing changing in CAMP图 9 CAMP路由切换示例 |
(5) RCR
在多径路由中,将流量合理分配在多条路径上可以更加充分地利用网络中存在的编码机会.例如图 10中,节点A将流量分配在A®B®C和A®E®D®C上同时传输,可以最大化地利用编码机会.基于以上发现,Yan等人于2008年提出了具有速率控制能力的编码感知多径路由协议RCR(rata-adaptive coding-aware multiple path routing)[36].RCR是反应式协议,当发现到目的节点的多条路径后,源节点将流量分配在这些路径上同时传输.流量分配同时考虑3种度量:RTN(required transmission number)为对应路径上的期望传输次数;MCR(matched coding rate)表示对应路径上可被编码传输的最大速率;CAR(congestion avoidance rate)为对应路径上可分配给本数据流而不造成拥塞的最大速率.RCR按照RTN由低到高的顺序为路径分配流量,路径P上分配的流量大小为Min(CMRP,CARP).在路由维护阶段,当发现某条路径上的编码机会消失时,RCR重新计算路径以及流量分配.仿真结果表明,RCR可获得较COPE更高的吞吐量.
 | Fig. 10 Traffic splitting benefits utilization of coding opportunity图 10 分配流量有助于充分利用编码机会 |
(6) TC-IROCX
2012年,Youghourta等人在IROCX的基础上作了进一步改进,引入了拓扑控制(topology control),旨在提高网络中可容纳的数据流数量[37].提高发送功率有利于增大传输距离并减少转发次数,但同时会增大干扰范围,因此,合理的拓扑控制有利于提高网络容量.如图 11所示,当节点的传输能量为一个单位时,数据包需要经过5次转发才能从点a到达点g,若将节点发射功率提高1倍,从点a到点g则只需经过2次转发.根据拓扑控制,TC-IROCX重新定义了编码感知路由的线性规划模型,引入了发送功率这一新的变量.结果表明:使用拓扑控制手段可以进一步降低编码转发次数,提高网络容量.
 | Fig. 11 An example of topology control in TC-IROCX图 11 TC-IROCX拓扑控制示例 |
本类编码感知路由支持使用机会侦听的网络编码,可以较上一节中的编码感知路由发现并利用更多的编码机会.
(1) LP-Code
Sengupta通过建立线性规划模型,分析了编码感知路由的吞吐量性能[38].LP-Code模型较ROCX,IROCX等更加实际,包括以下几个关键部分:引入广播冲突图以及团约束描述信道接入容量约束;对使用机会侦听的编码结构建模;允许多路径并行传输;优化目标为最大化所有数据流效用之和.通过数值验证,LP-Code从理论上证明了编码感知路由的有效性以及机会侦听对编码感知的有益性.
(2) PNCAR
PNCAR(practical network coding-aware routing)是一个先应式编码感知路由协议,它提出了编码感知的路由度量ETX-CA(expected transmission count with coding awareness),并针对ETX-CA的非保序性,提出了可行的路由计算方法[39].ETX-CA描述了可编码条件下的期望传输次数:
其中,pl为链路l的丢失率,ri估计了编码节点vi上可编码的概率.由于网络编码环境下当前链路的耗费与上一跳链路上的背景流量相关[34],ETX-CA不具备非保序性,导致最短路径算法不可用.为了解决这一问题,PNCAR将实际网络映射为虚拟网络,如图 12所示,使ETX-CA重获保序性,通过在虚拟网络中计算最优路由,并将路由映射回实际网络,PNCAR可以得到最优路由.PNCAR的虚拟网络与MMR[34]的点图在本质上是相同的,虚拟网络中的虚拟节点对应点图中添加的点,虚拟网络中虚拟节点的出边对应点图中的条件边.
 | Fig. 12 An example of virtual network图 12 虚拟网络示例 |
(3) ANCHOR
AHCHOR(active network coding high-throughput optimizing routing)是具有编码感知能力的路由优化方法,旨在利用动态变化的编码机会[40].ANCHOR使用机会侦听,并且每个节点周期性地向邻居节点通告本节点的分组缓存状态.基于以上手段获得的信息,节点可以发现本节点上新出现的编码机会,并基于此对路由做出优化.
例如图 13(a)所示网络中,节点B接收分组P1,并可侦听分组P2,从而得知分组P1和P2的接收节点分别是节点A和节点G.节点B继而检查节点A和节点G的通告消息发现,节点A和节点G分别缓存有分组P2和P1,进而可以得知:当节点E选择自己为P2下一跳转发节点时,本节点可以将P1和P2编码发送,并减少传输次数.因此,节点B通告节点E更改路由,以利用此编码机会,如图 13(b)所示.
 | Fig. 13 Path optimizing in ANCHOR图 13 ANCHOR优化路由示例 |
需要注意的是,ANCHOR是一种路由优化方法,还需要结合其他路由协议使用.此外,ANCHOR只能在发现本地编码机会的基础上对路由进行局部优化,因而难以得到全局最优路径,这一点与CAMP类似.
(4) OCR
Fan等人于2009年提出了反应式路由协议OCR(on-demand COPE-aware routing)[41].OCR使用反应式路由发现方法,为了限制RREQ的过度洪泛,OCR使用一个消耗函数cost(P)来决定是否继续转发RREQ:
其中,P为RREQ的扩散路径,hop(P)为跳数,yield(P)为编码机会数量.目的节点接收到多个RREQ后,综合考虑cost(P)的路径长度以及对应RREQ经历的时延,选择一条最优路径,并通过RREP将其通告给源节点.仿真结果表明:OCR可以有效地发现编码机会,缓解网络拥塞并提高吞吐量.
(5) NCAR
使用机会侦听有助于更加充分地利用编码机会,然而由于侦听链路上的传输是不可靠的,编码结构中包含的侦听链路越多,成功解码的概率也就越低.针对这一问题,NCAR(network coding-aware routing)通过区分利用不同可靠性的编码结构,从而提高在不可靠无线环境中使用网络编码的效率[42].具体来讲,NCAR按照侦听链路由少到多的顺序为编码结构设置由高到低的优先级,当存在多个可用编码结构时,编码节点选用优先级最高的编码结构.对于给定候选路径以及每个转发节点所用编码结构,源节点根据ETC-NC(expected transmission count- network coding)度量选择最优路由.
(6) BEND
Zhang等人提出的BEND协议采用了一种较为特殊的编码形式,称为混合(diffuse)[43].Diffuse不强求参与编码的数据流存在交汇点,只要两条数据流上存在共同的邻居节点,BEND就可以利用此邻居节点构造编码机会.将这一个或一组邻居节点和其所监听的两边数据流上的节点合并到一起考虑,就类似于一般情况下的数据流交汇点,因而,BEND进一步拓展了可利用的单跳编码结构.
如图 14所示,节点X有数据包P1发往Y,节点U有数据包P2要发往V.在节点X和U一次发送后,节点A和V都收到数据包P1,节点C和Y则收到了P2,而B1,B2和B3则同时拥有了P1和P2.又因为Y和V在节点B1,B2,B3的一跳范围内,故可利用它们中的任意某个节点编码转发数据包P1ÅP2.可以看出,这样的编解码方式降低了对编码节点的要求.
 | Fig. 14 Coding-Available neighborhood packet repository图 14 可编码的邻居节点状态 |
MCS编码结构可以发现并利用多跳编码机会,使编码感知路由更加灵活、高效.
(1) DCAR
Le等人于2008年提出编码感知路由协议DCAR(distributed coding-aware routing),扩展了网络编码的形式,可首次利用多跳形式的编码机会[29].DCAR使用编码感知路由度量CRM(coding-aware routing metric),表示可编码条件下链路上的期望传输次数:
其中,pl为链路l的丢失率,MIQd(l)(modified interference queue length)则描述了l上的编码机会数量以及竞争程度.最后,DCAR使用反应式路由发现方法,源节点发现多条候选路径后选用CRM最小的路径.
(2) DODE
Vu等人于2012年提出的DODE协议[44]设计了邻居节点可编码的最短路径度量SPENM(shortest path with enriched neighborhood routing metric).DODE结合了BEND中的Diffuse编码形式以及DCAR利用多跳编码机会的能力,扩展了网络编码的形式.
如图 15所示,数据流1®2®3®5与数据流5®6®4无交叉节点,因而无法被DCAR等严格要求有中间节点的路由利用;BEND又没有考虑编码包在多跳以外被解码;DODE则结合了DCAR以及BEND各自的优势.
 | Fig. 15 DODE can utilize more coding opportunities than BEND and DCAR图 15 DODE结合了BEND和DCAR的优势 |
(3) OCAR
片面追求编码机会的数量,将引起数据流相互聚拢,由此增大数据流间的干扰,最终反而会导致数据流性能恶化.OCAR(on-demand coding-aware routing)同时具有编码感知和干扰感知能力,可在追求利用编码机会与避免干扰之间取得平衡[30].为了达到上述目的,OCAR设计了路由度量RCAIA,同时具有编码和干扰感知能力(coding aware and interference aware):
其中,
为可编码条件下链路l的期望传输时间,
则描述了链路l=(u,v)上的干扰程度.OCAR使用类似AODV的路由维护方法,并且在Hello消息上还携带了计算干扰需要的发送功率、接收功率等信息.
Zhou等人于2010年提出了网络联合编码的概念,并在此基础上提出了编码感知协议NJCAR(network joint coding-aware routing)[31].网络联合编码允许编码分组被多个节点逐次解码,使流间网络编码可以利用更广泛的编码机会.NJCAR使用反应式路由获得源节点到目的节点的多条候选路径以及每条路径上的编码机会,再由源节点从多条候选路径中选择编码机会最大的路由.为了计算编码机会,RREQ和RREP需要携带路径信息以及路径上节点的邻居信息.编码机会由中间节点计算,并记录在RREP中.在编码分组传输过程中,每个中间节点都尽最大努力解码,并在本节点无法完全解码时将部分解码的分组交由下游节点继续解码.编码分组被多次解码后,所需原始分组可被恢复,并被转发至目的节点,如图 6所示.
2.5GCS编码结构Guo等人于2011年提出了一般化的编码结构GCS,解决了伪编码机会的问题.此外,他们还提出了路由度量FORM(free-ride-oriented routing metric),并将二者结合设计了编码感知路由协议[32].FORM是路径度量,由两部分组成:
其中,第1部分bm(L)=b(L)-[H(L)-Hmin]与路径的长度以及可编码节点数目相关,其中,b(L)为路径L上的编码节点的数目,H(L)表示路径L的长度,Hmin为源节点与目的节点间的最短路径长度;第2部分为DegFR(L),表示路径L上节点队列中可与当前数据流编码的分组的数量.仿真结果表明,协议避免伪编码机会可获得更高的吞吐量.
2.6 编码感知的机会路由协议流间网络编码和机会路由都利用无线信道的广播特性提高网络传输效率,将两者结合,可同时获得机会传输和编码增益两点好处.编码感知的机会路由协议改进了使用流间网络编码的机会路由,使其可以更有效地利用编码机会[45, 46, 47].由于传输路径是不确定的,编码感知的机会路由协议仅使用单跳编码机会.
以CORE为例[46],CORE分为转发集的选择、编码机会计算以及优先级转发这3个部分,其中,后两个部分与网络编码相关.CORE选择转发节点时依据的条件是:该节点是发送节点的直接邻居,并且与发送节点相比,该节点距离目的节点更近(物理距离).为了在转发过程中充分利用编码机会,CORE使用编码感知的优先级转发策略,让具有更多编码机会的转发节点优先转发.优先转发通过转发定时器实现,定时器的时间长度与转发节点的编码机会数量成反比.低优先级的节点侦听到其他节点转发后不再转发.仿真结果表明:通过将机会路由与机会编码相结合,CORE获得了较COPE更高的吞吐量.
表 3总结了现有的编码感知路由协议的主要特征及其主要贡献.关于路由评估方法需要说明的是:不同路由度量反映了路由协议的设计侧重点(考虑多径、干扰、可靠性等),因此适用场景和应用目标有所不同.
|
|
Table 3 Summary of NC-aware routing 表 3 编码感知路由协议总结 |
自2006年编码感知路由诞生至今的短短七、八年时间内,编码感知路由协议得到了广泛的关注,并且获得了长足的发展.虽然如此,编码感知路由当前仍然停留在理论探索阶段,距离可实际应用还有较大差距.在实用化的道路上,编码感知路由还需要解决以下几个问题:
(1) 如何应对不可靠无线环境
在不可靠无线环境下利用编码机会,特别是复杂的编码机会,为流间网络编码提供了改善性能的空间,但同时也带来了新的问题.机会侦听以及更多、更远节点的参与,都会引入更多的不确定因素,使解码变得更加脆弱,解码成功率将由此下降.不合理地利用编码机会,反而可能降低网络性能,尤其是在应用多跳编码机会时,如果编码分组被多跳传输后却因无法被解码而被丢弃,将造成网络资源的严重浪费.可见,在不可靠无线环境中利用编码机会与避免编码负面效应之间取得平衡,是一个值得研究的问题.
(2) 时延性能分析以及优化
吞吐量和时延是衡量网络性能的两个最主要的指标,然而当前,编码感知路由只考虑追求网络吞吐量的最大化,却忽视了分组时延性能.从直观上看,原始分组等待编码以及编码分组等待解码都会引入新的时延,这会造成分组时延的上升.考虑时延敏感业务的需要,编码感知路由还应该将时延指标纳入路由决策的考虑中,防止片面追求吞吐量性能而导致的时延性能恶化.
(3) 如何适应网络动态
流间网络编码的性能依赖于路径上存在的编码机会的数量.由于编码机会由本数据流和背景数据流共同决定,编码感知路由较传统路由协议对网络动态因素更加敏感,拓扑、背景流量等变化都会改善编码机会的数量和分布.重新选路可以更充分地利用编码机会,但同时需要引入额外的路由开销,并且还会造成业务流传输暂时中断.因此,有必要分析动态因素对编码感知路由的影响,并以此为依据来应对网络环境的动态变化.
4 结束语编码感知路由通过选择有利于施展流间网络编码的路由,可以有效地改善网络编码的吞吐量.本文总结了编码感知路由的核心问题,即,编码机会的发现,并围绕这一核心问题综述了编码感知路由协议的研究现状.最后,讨论了编码感知路由中有待解决的问题.
| [1] | Ahlswede R, Cai N, Li SR, Yeung RW. Network information flow. IEEE Trans. on Information Theory, 2000,46(4):1204-1216 . |
| [2] | Li SY, Yeung RW, Cai N. Linear network coding. IEEE Trans. on Information Theory, 2003,49(2):371-381 . |
| [3] | Liu JN, Goeckel D, Towsley D. Bounds of the gain of network coding and broadcasting in wireless networks. In: Proc. of the 26th IEEE Conf. on Computer Communications (INFOCOM). Anchorage, 2007. 724-732 . |
| [4] | Ramamoorthy A, Shi J, Wesel RD. On the capacity of network coding for random networks. IEEE Trans. on Information Theory, 2005,51(8):2878-2885 . |
| [5] | Seferoglu H, Markopoulou A, Ramakrishnan KK. I2NC: Intra- and inter-session network coding for unicast flows in wireless networks. In: Proc. of the 30th IEEE Int’l Conf. on Computer Communications (INFOCOM). Shanghai, 2011. 1035-1043 . |
| [6] | Sundararajan JK, Shah D, Médard M. ARQ for network coding. In: Proc. of the IEEE Int’l Symp. on Information Theory (ISIT). Toronto, 2008. 1651-1655. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&arnumber=4594930 |
| [7] | Lucani DE, Stojanovic M, Médard M. Random linear network coding for time division duplexing: When to stop talking and start listening. In: Proc. of the 29th IEEE Conf. on Computer communications (INFOCOM). San Diego, 2010. 1800-1808 . |
| [8] | Sundararajan JK, Shah D, Médard M. Network coding meets TCP. In: Proc. of the 28th IEEE Conf. on Computer Communications (INFOCOM). Rio de Janeiro, 2009. 280-288 . |
| [9] | Ghaderi M, Towsley D, Kurose J. Reliability gain of network coding in lossy wireless networks. In: Proc. of the 27th IEEE Int’l Conf. on Computer Communications (INFOCOM). Phoenix, 2008. 2171-2179 . |
| [10] | Fragouli C, Katabi D, Markopoulou A, Médard M, Rahul H. Wireless network coding: Opportunities and challenges. In: Proc. of the Military Communications Conf. (MILCOM). Orlando, 2007. 1-8 . |
| [11] | Eryilmaz A, Ozdaglar A, Médard M. On delay performance gains from network coding. In: Proc. of the 40th Annual Conf. on Information Sciences and Systems (CISS). Princeton, 2006. 864-870 . |
| [12] | Alvandi M, Mehmet-Ali M, Hayes JF. Delay optimization of wireless networks with network coding. In: Proc. of the 24th Canadian Conf. on Electrical and Computer Engineering (CCECE). Niagara Falls, 2011. 1282-1287 . |
| [13] | Chachulski S, Jennings M, Katti S, Katabi D. Trading structure for randomness in wireless opportunistic routing. In: Proc. of the Int’l Conf. on Special Interest Group on data Communications (SIGCOMM). New York, 2007. 169-180 . |
| [14] | Koutsonikolas D, Wang CC, Hu YC. CCACK: Efficient network coding based opportunistic routing through cumulative coded acknowledgments. In: Proc. of the 29th Conf. on Computer communications (INFOCOM). San Diego, 2010. 2919-2927 . |
| [15] | Lin YF, Liang B, Li BC. SlideOR: Online opportunistic network coding in wireless mesh networks. In: Proc. of the 29th Conf. on Computer Communications (INFOCOM). San Diego, 2010. 2919-2927 . |
| [16] | Lin YJ, Huang CC, Huang JL. PipelineOR: A pipelined opportunistic routing protocol with network coding in wireless mesh networks. In: Proc. of the 7th IEEE Vehicular Technology Conf. (VCT). Taipei, 2010. 1-5 . |
| [17] | Katti S, Katabi D, Balakrishnan H, Medard M. Symbol-Level network coding for wireless mesh networks. In: Proc. of the Int’l Conf. on Special Interest Group on data Communications (SIGCOMM). New York, 2008. 401-412 . |
| [18] | Lin YF, Li BC, Liang B. CodeOR: Opportunistic routing in wireless mesh networks with segmented network coding. In: Proc. of the IEEE Int’l Conf. on Network Protocols (ICNP). Orlando, 2008.13-22. |
| [19] | Joon SP, Gerla M, Lun DS, Yi Y, Médard M. CodeCast: A network coding based ad hoc multicast protocol. IEEE Wireless Communications, 2006,13(5):76-81 . |
| [20] | Katti S, Rahul H, Hu W, Katabi D, Médard M, Crowcroft J. XORS in the air: Practical wireless network coding. In: Proc. of the Int’l Conf. on Special Interest Group on Data Communications (SIGCOMM). Pisa, 2006. 243-254 . |
| [21] | Scheuermann B, Hu WJ, Crowcroft J. Near-Optimal coordinated coding in wireless multihop networks. In: Proc. of the ACM Int’l Conf. on Emerging Networking EXperiments and Technologies (CoNEXT). New York, 2007 . |
| [22] | Chaporkar P, Proutiere A. Adaptive network coding and scheduling for maximizing throughput in wireless networks. In: Proc. of the 13th Annual ACM Int’l Conf. on Mobile Computing and Networking (Mobicom). New York, 2007. 135-146 . |
| [23] | Rozner E, Iyer AP, Mehta Y, Qiu L, Jafry M. ER: Efficient retransmission scheme for wireless LANs. In: Proc. of the ACM Int’l Conf. on Emerging Networking EXperiments and Technologies (CoNEXT). New York, 2007 . |
| [24] | Kuo FC, Tan K, Li XY, Zhang JS, Fu XM. XOR rescue: Exploiting network coding in lossy wireless networks. In: Proc. of the 6th IEEE Communications Society Conf. on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). Rome, 2009. 511-519 . |
| [25] | Le JL, Lui J, Chiu DM. How many packets can we encode?—An analysis of practical wireless network coding. In: Proc. of the 27th IEEE Int’l Conf. on Computer Communications (INFOCOM). Phoenix, 2008. 371-379 . |
| [26] | Koutsonikolas D, Hu YC, Wang CC. An empirical study of performance benefits of network coding in multihop wireless networks. In: Proc. of the 28th IEEE Conf. on Computer communications (INFOCOM). Rio de Janeiro, 2009.2981-2985 . |
| [27] | Wang H, Xue KP, Hong PL, Lu HC. Impact of traffic pattern on benefits of practical multi-hop network coding in wireless networks. In: Proc. of the IEEE Consumer Communications and Networking Conf. (CCNC). Shenzhen, 2011.1197-1201 . |
| [28] | Ni B, Santhapuri N, Zhong ZF, Nelakuditi S. Routing with opportunistically coded exchanges in wireless mesh networks. In: Proc. of the 2nd IEEE Workshop on Wireless Mesh Networks (WiMesh). Reston, 2006. 157-159 . |
| [29] | Le JL, Lui JC, Chiu DM. DCAR: Distributed coding-aware routing in wireless networks. In: Proc. of the IEEE Int’l Conf. on Distributed Computing Systems (ICDCS). Beijing, 2008. 462-469 . |
| [30] | Sun JZ, Liu YA, Hu HF, Yuan DM. On-Demand coding-aware routing in wireless mesh networks. Journal of China Universities of Posts and Telecommunications, 2010,17(5):80-86 . |
| [31] | Zhou ZH, Zhou L. Network joint coding-aware routing for wireless ad hoc networks. In: Proc. of the IEEE Int’l Conf. on Wireless Communications, Networking and Information Security (WCNIS). Beijing, 2010. 17-21 . |
| [32] | Guo B, Li HK, Zhou C. Analysis of general network coding structures and design of a free-ride-oriented routing metric. IEEE Trans. on Vehicular Technology, 2011,60(4):1714-1727 . |
| [33] | Benfattoum Y, Martin S, Al Agha K. IROCX: Interference-Aware routing with opportunistically coded exchanges in wireless mesh networks. In: Proc. of the Wireless Communications and Networking Conf. (WCNC). Quitana-Roo, 2011. 1113-1118 . |
| [34] | Wu YN, Das SM, Chandra R. Routing with a Markovian metric to promote local mixing. In: Proc. of the 26th IEEE Int’l Conf. on Computer Communications (INFOCOM). Anchorage, 2007. 1028-1036 . |
| [35] | Han S, Zhong ZF, Li HX, Chen GH, Chan E, Mok AK. Coding-Aware multi-path routing in multi-hop wireless networks. In: Proc. of the IEEE Int’l Performance, Computing and Communications Conf. (IPCCC). Austin, 2008. 93-100 . |
| [36] | Yan Y, Zhao Z, Zhang BX, Mouftah HT, Ma J. Rate-Adaptive coding-aware multiple path routing for wireless mesh networks. In: Proc. of the IEEE Global Telecommunications Conf. (Globecom). New Orleans, 2008. 1-5 . |
| [37] | Benfattoum Y, Martin S, Agha KA. TC-IROCX: Network coding with topology control and interference awareness. In: Proc. of the IEEE Wireless Communications and Networking Conf. (WCNC). 2012. 1970-1975 . |
| [38] | Sengupta S, Rayanchu S, Banerje S. An analysis of wireless network coding for unicast sessions: The case for coding-aware routing. In: Proc. of the 26th IEEE Int’l Conf. on Computer Communications (INFOCOM). Anchorage, 2007. 1028-1036 . |
| [39] | Peng YX, Yang YL, Lu XL, Ding XY. Coding-Aware routing for unicast sessions in multi-hop wireless networks. In: Proc. of the IEEE Global Telecommunications Conf. (Globecom). Miami, 2010. 1-5 . |
| [40] | Jiao XL, Wang XD, Zhou XM. Active network coding based high-throughput optimizing routing for wireless ad hoc networks. In: Proc. of the 4th Int’l Conf. on Wireless Communications, Networking and Mobile Computing (WiCOM). Dalian, 2008. 1-5 . |
| [41] | Fan K, Li LX, Long DY. Study of on-demand COPE-aware routing protocol in wireless mesh networks. Journal on Communications, 2009,30(1):128-134 (in Chinese with English abstract) . |
| [42] | Wei X, Zhao L, Xi J, Wang QY. Network coding aware routing protocol for lossy wireless networks. In: Proc. of the 5th Int’l Conf. on Wireless Communications, Networking and Mobile Computing (WiCOM). Beijing, 2009. 1-4 . |
| [43] | Zhang J, Chen YP, Marsic I. MAC-Layer proactive mixing for network coding in multi-hop wireless networks. Computer Networks, 2010,54(2):196-207 . |
| [44] | Vu TV, Nguyen TMT, Pujolle G. Distributed opportunistic and diffused coding in multi-hop wireless networks. In: Proc. of the IEEE Int’l Conf. on Communications (ICC). 2012. 5583-5587 . |
| [45] | Yan Y, Zhang BX, Zheng J, Ma J. CORE: A coding-aware opportunistic routing mechanism for wireless mesh networks. IEEE Wireless Communications, 2010,17(3):96-103 . |
| [46] | Islam J, Singh PK. CORMEN: Coding-Aware opportunistic routing in wireless mesh network. Journal of Computing, 2010,2(6): 71-77. |
| [47] | Yan Y, Zhang BX, Mouftah HT, Ma J. Practical coding-aware mechanism for opportunistic routing in wireless mesh networks. In: Proc. of the IEEE Int’l Conf. on Communications (ICC). Beijing, 2008. 2871-2876 . |
| [41] | 樊凯,李令雄,龙冬阳.无线Mesh网中网络编码感知的按需无线路由协议的研究.通信学报,2009,30(1):128-134 . |