一种新的基于部分网络编码的机会路由机制

邬 晨，何加铭，曾兴斌，樊玲慧

(1.宁波大学通信技术研究所，浙江宁波315211;2.浙江省移动网应用技术重点实验室，浙江宁波315211;3.宁波新然电子信息科技发展有限公司，浙江宁波315211)

0 引言

近年来，网络编码逐渐成为研究热点。网络编码［1－4］不仅能够提高网络的吞吐量，而且还能降低协议设计的复杂性。与有线网络相比，因其具有的广播特性和不依赖性，无线网络更适合使用网络编码。

机会路由的概念首先是在文献［5］中提出的，它与传统的主动路由完全不同。主动路由在数据包达到之前建立起相应的路由表，而机会路由则是在收到数据包之后选择转发节点时建立相应的路由表。文献［6］中综合运用了网络编码和机会路由。尽管无线网络发送的冗余数据得到了降低，但相应的算法变得更为复杂，同时也只适用于网络节点数目较少且节点位置几乎不变的情况。

文献［7］中提出了一种机会路由选择的转发策略——Expected Transmission Count(ETX)。ETX 数值越小，则传输数据包所需的转发时间就越少，所消耗的能量就越少，传输成功的概率也就越高。但ETX不适用于拓扑结构不断变化的网络。此外，ETX值并没有考虑链路负担、数据传输速率和节点能量的消耗。

提出了一种机会路由协议(ORoPNC)，这一协议将部分网络编码引入到机会路由。同时，设计了一种新的ETXoEC转发策略。在该协议下，前向节点的选择基于当前链路状态以及节点的剩余能量。

1 部分网络编码

1．1 部分网络编码思想

部分网络编码(PNC)的思想是由Wang等提出的［8］。源节点仅仅广播原始数据，不对这些数据进行编码。中间节点采用任意长度的编码方式，目的是为了解决由数据等待而造成的网络延迟。目的节点对获得的数据进行高斯消元，然后判断是否能够解码。如果能够进行解码，则将解码后的数据发送至上一层;如果不能进行解码，则将数据压入等待队列。全网络编码的结构如图1所示，图1解释了部分编码的基本思想，以及全网络编码和部分网络编码对网络延迟的影响。

图1 全网络编码

源节点S有4个数据包要传输到目的节点D。S对原始数据进行编码，然后进行传输。中间节点收到数据后再进行编码，最终将数据传递到目的节点D。假设数据包达到的时间间隔是t，即数据包p'1、p'2、p'3和 p'4达到节点 D 的时间分别为 t、2t、3t和4t，原始数据p1、p2、p3和p4只有在D收到全部数据包之后才能进行解码，网络的平均延迟为(4t*4)/4=4t。

部分网络编码如图2所示。源节点S向外广播数据包，中间节点对收到的数据包进行任意长度的部分网络编码，然后将数据传输出去。假设节点2首先发送数据包3r1p1+3r2p2+3r3p3，节点D在t时刻收到数据包，但无法解码;假设节点D在2t时刻从节点4收到数据包r1p1+r2p2+r3p3+r4p4，这个数据包与上个数据包线性相关，故可以解码出数据p4;假设在3t时刻，节点D从节点3收到r5p3+r6p4，由于p4已知，所以可以解出p3;在最后时刻4t，节点D从节点1处收到r7p1+r8p2+r9p4，这样可以解出p1和p2。这时平均网络延迟为(2t+3t+2*4t)/4=3.25t。

图2 部分网络编码

1．2 节点转发

部分网络编码策略可以加快节点编码开始时间，同时降低节点编码操作的消耗。原始数据被分成几块，每个块包含k的数据包。部分采用网络编码的中间节点使用随机选择策略，即节点从缓存中随机地选择若干个属于同一个块的数据包进行编码操作，而不是选择全部或一定数量的数据包进行编码。在获得信道之后，节点随机地产生一个整数M(1≤M≤存储的数据包个数)，然后从缓存对列中随机地选取M个数据包进行编码和转发［9］。

由于中间节点采用了随机部分网络编码方式，未被选取的数据块的系数可以认为是0，而编码系数矩阵可以看作一个稀疏矩阵。稀疏矩阵的取逆相对较为简单，解码率较高。如果接收节点的稀疏编码系数矩阵是满秩矩阵，就可以完成解码过程。文献［10］给出了稀疏矩阵的详细描述。

2 基于部分网络编码的机会路由

网络编码与机会路由的结合能够有效地解决重复发送冗余数据的问题，但是这方面的研究目前主要集中在全网络编码之上。假设需要编码的数据包的数目是N，源节点对原始数据进行等长度的编码，则目的节点只有在收到全部N个线性无关的数据包之后才能解码出原始数据。全网络编码增加了数据包的等待延迟，而且有时数据包的到达是不平衡的，这不利于数据的解码。将部分网络编码引入机会路由当中，在考虑了成功转发传输数据的时间和节点的能量消耗后，提出了一种新的转发协议ETXoEC(Expected Transmission Count Based on Energy Consumption)和基于部分网络编码的机会路由(ORoPNC)。

2．1 节点前向时间的计算

为了避免广播冗余，离目的节点最近的接收节点应当用于转发传输数据包，这样总的传输时间将会最少。中间节点不需要传输其收到的所有数据包，只需要传输下游节点未收到的数据。转发时间应当足够长，以保证至少一个下游节点收到数据包。

假设i和j是网络的2个节点，i＜j意味着i比j更靠近目的节点，或者说i的ETX值小于j的ETX值。Ti是节点i所需的机会传输时间。节点j从上游节点处收到的总的数据包的数目为∑i＞jTi(1－pij)，如果j的所有下游节点没有收到这一数据包，则节点j将此数据包前向传输。其他节点未收到此数据包的概率为∏k＜jpjk，因此，节点j的总传输机会为:

传输时间为:

Ci和Ti的计算基于实时的链路损失率，因此，为了使用当前链路状态保证数据的可靠性，pij需要进行周期性更新。

2．2 ETXoEC转发候选集的选择策略

在设计转发候选集时，ETXoEC转发策略根据当前链路状态和节点剩余能量来选择转发节点。对于网络节点，转发机会值(OP)可以通过下面的公式计算得到:

3 性能分析

使用NS2软件对ORoPNC协议进行仿真和性能分析。仿真分析了ETXoEC和ETX这2种协议下的效果值K。仿真模型范围1 000 m*1 000 m，其中随机分布100个节点。每个节点的初始能量、传输能量和接收能量分别为10 J、3×10－4J和1.5×10－4J。源节点数据比特率保持不变，传输带宽250 KB/s。数据包大小为256 B，MAC层协议使用802.11。

3．1 不同k值下的延迟情况

实验分别比较了ORoPNC和基于全网络编码的机会路由(NCOR)在使用ETXoEC作为转发策略时的K值，其中α和β均为0.5。平均网络延迟的比较结果如图3所示。

图3 延迟比较

当k＜10时，ORoPNC的平均网络延迟小于NCOR。当k为5、6或者7时，平均网络延迟下降约25%。随着k的增大，网络延迟的提升效果开始变得不明显，甚至在k＞10时，ORoPNC的延迟大于NCOR。这主要是因为NCOR采用了全网络编码，所以只有当接收到k个线性独立的数据包后才能进行解码。部分网络编码在转发过程中随机选择数据包用于解码，而且编码过程可能会重复进行。因此，数据包之间的线性独立关系会被降低，从而导致加大网络延迟。

3．2 转发策略分析

ETXoEC转发策略综合考虑了链路状态和节点能量消耗。仿真分析了ETX和ETXoEC这2种采用了网络编码的转发策略，比较了2种策略节点剩余能量的均方差和损失率。

3．2．1 节点剩余能量均方差

在仿真开始阶段，ETX和ETXoEC这2种策略的节点剩余能量均方差几乎相同，如图4所示。仿真开始大约38 s以后，ExOR的节点剩余能量均方差大于ETXoEC转发策略，几秒钟后，ExOR的节点剩余能量迅速下降到0。但是对于ETXoEC，网络节点的生命周期得到增加，因为节点能量消耗被考虑在内，而且在传输可靠性得到确认后，能量较低的节点被排除在外，不用于数据转发。仿真结果表明，ETXoEC转发策略应用于ORoPNC之后，可以较好地平衡网络节点能量消耗，从而提升网络可靠性。

图4 节点剩余能量均方差

3．2．2 下降速率

由于充分考虑了链路可靠性，同时ETX值的计算式基于路径测量的累积，所以ETX和ETXoEC的下降速率都相对较低。但是，从图5中可以看出，ETXoEC的损失率要高于ETX，这主要是因为ETX-oEC中加入了能量控制机制。在链路选择的过程中考虑了能量的消耗，这也对传输的可靠性产生了一定的作用。

图5 下降速率

4 结束语

机会路由利用无线信道的广播特性，可以极大地提升网络的吞吐量。在综合运用了网络编码和机会路由之后，网络的整体性能能够得到很大改善。但是，传统的基于网络边编码的机会路由均采用了全网络编码的方式，只有在收到k个数据包之后才能进行解码操作，这无疑增加了数据包的等待延迟。因此提出了部分网络编码算法ORoPNC，来降低由于网络编码造成的延迟。

ORoPNC协议采用了部分网络编码的思想。源节点只广播数据包而不进行编码，中间节点在收到若干个数据包后，随机选择数据包进行编码，再将数据包进行转发，从而减少了等待延迟。ORoPNC协议使用的ETXoEC转发策略不仅考虑了当前链路的状态，还有节点的能量消耗。在保证传输可靠性的前提下，拥有更多剩余能量的节点被用来参与数据转发，因此网络的整体可靠性得到提升。

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

［2］ YAN Y，ZHANG B，MOUFTAH H T，et al．Practical Coding-aware Mechanism for Opportunistic Routing in Wireless Mesh Networks［C］∥Communications，2008．ICC＇08．IEEE International Conference on．IEEE，2008：2871 －2876．

［3］ BISWAS S，MORRIS R．ExOR：Opportunistic Multi-hop Routing for Wireless Networks［C］∥ACM SIGCOMM Computer Communication Review．ACM，2005，35(4)：133－144．

［4］ HO T，MEDARD M，KOETTER R，et al．A Random Linear Network Coding Approach to Multicast［J］．Information Theory，IEEE Transactions on，2006，52(10)：4413 －4430．

［5］ LI S Y R，YEUNG R W，CAI N．Linear Network Coding［J］．Information Theory，IEEE Transactions on，2003，49(2)：371 －381．

［6］ CHACHULSKI S，JENNINGS M，KATTI S，et al．Trading Structure for Randomness in Wireless Opportunistic Routing［M］．ACM，2007：200 －205．

［7］ WANG Y，GARCIA-ACEVES J J．Collision Avoidance in Mmulti-hop Ad hoc Networks［C］∥Modeling，Analysis and Simulation of Computer and Telecommunications Systems，2002．MASCOTS 2002．Proceedings．10th IEEE International Symposium on．IEEE，2002：145 －154．

［8］ WANG D，ZHANG Q，LIU J．Partial Network Coding：Theory and Application for Continuous Sensor Data Collection［C］∥Quality of Service，2006．IWQoS 2006．14th IEEE International Workshop on．IEEE，2006：93 －101．

［9］ WANG X D，HUO G C，SUN H Y，et al．An Opportunistic Routing for MANET Based on Partial Network Coding［J］．Dianzi Xuebao(Acta Electronica Sinica)，2010，38(8)：1736 －1740．

［10］ COOPER C．On the Distribution of Rank of a Random Matrix over a Finite Field［J］．Random Structures and Algorithms，2000，17(3 －4)：197 －212．