一种移动Ad Hoc网络的冗余网络编码方法*

(广西大学 计算机与电子信息学院，南宁 530004)

1 引 言

移动Ad Hoc网络(MANET)由一组无线移动节点组成，网络中的各个节点互相协作,通过无线链路进行通信、交换信息，实现信息和服务的共享。网络编码是进入21世纪后通信领域的一项重大突破,是Ahlswede等人[1]于2000年提出的，融合了编码和路由的概念，允许节点对来自不同链路的数据分组进行编码组合，使得网络性能可以达到最大流传输的理论极限。网络编码已经被成功地引入到了移动Ad Hoc网络的应用中。Katti等[2]提出的基于机会的网络编码方案COPE，则是首次研究网络编码在无线环境中的协议面上具体实现的问题。文献[3]在COPE的基础上，提出了一种以条件链路消耗作为路由判据,支持网络编码的无线Mesh路由协议，网络中的节点对数据编码组合后，选择条件消耗值最小的路径传输编码后的分组。文献[4]中阐述了网络编码在移动Ad Hoc网络中对传输可靠性的影响。文献[5]提供了一种编码在移动Ad Hoc网络更加有效的方案，在采用文献[4]随机网络编码方案的基础上，加入了对网络中编码包的在插入时间及位置的优化选取。但是在目前的研究中，很少考虑到链路丢失的情况。网络编码能够使无线网络的吞吐量获得较大的提高，基本上是基于网络环境较好的条件下得出的。在传输链路存在较高的丢失率的情况下，网络编码相对传统路由的优势不能完全体现。

本文提出一种基于移动Ad Hoc网络的冗余编码方法，采用二元编码方式，通过增加传输冗余度，使得存在链路丢包率的条件下，能够保证网络编码传输的可靠性，最大化网络编码效率。

2 冗余传输及二元网络编码

2.1 网络编码传输冗余度举例

基于机会的网络编码方案COPE[2]，则是首次研究网络编码在无线环境中的协议面上具体实现的问题。在COPE方案中，每个节点编码组合数据后，进行基于机会的路由。在网络中，若是采用异或方式进行编码，而减轻全局协作和信息集合所带来的网络负载，相对于无编码的网络，毫无疑问COPE方案在有损无线环境中的传输效果是最佳的。如果不考虑传输的冗余度，那么传输次数也是最少的。我们称这样的传输方式为最简化网络编码方式(Minimalist Network Coding)。但是，无线链路往往是有损链路，在Ad Hoc或Mesh网络中的无线链路的丢包率在不太理想的环境下可能达到30%甚至更高[6]。

在下面的一个简单的二元码流传输例子中，我们将会看到增加传输次数的冗余度所带来的效果。

假设节点A和节点B是无线网络中的两个节点，节点A要将数据包Pa传给节点B，同样地，节点B将数据包Pb传给节点A。它们都在对方的通信范围之外，所以需要一个中继节点R来转播数据包(如图1)。

图1 二元传输模型Fig.1 Two-flow transmission model

方案一：采用COPE协议传输，即中继节点R接收到节点A和节点B传送的数据包Pa和Pb后，对两个数据包进行编码操作，得到Pc=Pa⊕Pb，然后将数据包Pc广播至A和B两个目的节点。假设链路R→A,R→B为有损链路，丢包率为p，则整个传输过程的传输成功率为(1-p)。

方案二：采用COPE-duplication方式(简称COPE-dup)。这种传输方式前面的操作与方案一相同，不同的地方在于将编码后的数据包Pc重复传送。若传输Pc两次，则传输成功率为(1-p2)。

如图2所示，在链路丢包率逐渐升高的情况下，COPE-dup的传输成功率高于COPE的传输成功率。它通过增加传输冗余度(或编码冗余度)来提升网络的传输质量，保证了更稳定的传输率。

图2 有损链路中两种传输方式丢包率的比较Fig.2 Packet loss rate of two transmission schemes in lossy-link

2.2 二元网络编码的引入

移动Ad Hoc网络的无线传输链路为有损链路，因此每个编码包或者原始数据包能被传输到达下一跳节点Ni存在一定的概率。由于接收到的数据包不同，Ni会存在一定的解码率(即成功解出所需包，也称作传输成功率)，这个概率与链路丢包率和编码方法有关。在最初的编码方法中，只考虑机会编码的思想，即通过增加编码机会来获取吞吐量的提高。但如果仅仅依靠机会编码的单个编码包的获得进行解码，就会使得解码率依赖于编码包的传输率。所以本文提出一种通过增加编码包冗余度的优化编码方法，使得目的节点能通过至少两种解码方式来提高传输成功率。

在Ad Hoc网络中，我们首先关心的是传输的吞吐量。应用适当的网络编码方法，能使网络的吞吐量得到相应提高。而传输吞吐量的计算可以表示为每单位时间成功解码数据包的平均数，也就是∑qi(S)/|S|。因此，获得最佳性能的编码方法就是求得∑qi(S)/|S|的最大值。

但是，求解上述最大值的问题是一个十分复杂的非线性方程组，现行的网络节点没有足够的计算能力来解决这样的问题。所以我们考虑一个最简单的编码方法，将最多可编码数据包的数量限定为2个(即1个编码包中只含有2个原始数据包)。我们称这种编码形式为二元编码。

假设n个数据包P={P1,P2,…,Pn}将通过中继节点σ传送至目的节点D={D1,D2,…,Dn}。建立图H(V,E)，图H的顶点集定义为V(H)=P∪D∪{σ}。图H的边集E(H)可以分为以下4种类型：

类型1——(Pi,Pj)：表示数据包Pi和Pj的双向链路,且该链路存在编码包Pi⊕Pj的传输;

类型2——(Pi,σ)：表示Pi至节点σ的有向链路,且该链路存在原始数据包Pi的传输;

类型3——(σ,Nj)：表示中继节点σ至每个接收节点Nj之间有向链路;

类型4——(Pi,Nj)：表示节点Nj能接收到数据包Pi的链路。

一个有效的编码方法可以表示为以P∪{σ}为顶点集的图H的诱导子图的边集,边(Pi,Pj)代表编码分组Pi⊕Pj的传输,边(Pi,σ)代表原始数据包的传输。

由于传输链路存在丢包率，目的节点Ni不可能接收到所有的数据包。因此,目的节点Ni通过接收到的编码包能解出所需包Pi的概率(即传输成功率)由链路丢包率和编码方法决定。

我们建立一个有关下一跳节点Ni的子图H(i)，它应该表示为：

(1)类型3和类型4的所有边集；

(2)以成功发送或接收的P∪{σ}为顶点集的边诱导子集。

那么，只要满足定理1，节点Ni就能解码出所需数据包Pi。

定理1：若编码包只含有两个原始数据包，则下一跳节点Ni当且仅当图H(i)中Pi至节点Ni之间存在一条有向链路时能解码出数据包Pi。[7]

在设计有效编码方法的时候，我们必须遵循上述定理才能获得最优的编码方案。同时，可以得出推论1。

推论1：如果每个接收节点都存在传送或者“侦听获得”一个原始数据包，那么就能够设计出一个有效的编码方案[8]。

2.3 二元网络编码问题的转化

若想要解决链路丢失的二元编码问题，即找到∑qi(S)/|S|的最大值是很难的。因此，我们把最值问题转化为另外一种表达形式，来找到最优的编码方法[8]。

假设S是理想的编码方法，它是顶点集P∪{s}的诱导子图的边子集。对于每个i，数据包Pi能被节点Ni成功解码的概率计算方式如下：给定S中每条边的ri(ri为中继节点至下一跳节点Ni的路径的传输成功率)。给S中每条边ri设定一个权重。对于边(Pi,Nj)，权重为节点Ni已经存在数据包Pj的概率(如果确定存在，该值为1)。类型4的边权重值为1,其它类型的值为0。数据包Pi在编码方法S下能被节点Ni成功解码的概率qi(S)可以表示为在图中拥有一条从节点Pi到节点Ni传输路径的概率。因此问题可以表述为minS|S|，约束条件是qi(S)≥p，∀i=1,2,…,n，其中p是预先设定的传输成功率。

选择的路径必须包括S∪{(σ,Ni)}，不过ki条不相交路径可以有共用边(σ,Nj)，那么设计冗余编码方法问题转化成为minS|S|，同时满足以下条件：

3 冗余网络编码方法

3.1 编码方法描述

通过上述问题的转化，本文提出一种冗余编码方法。假设(Pi,Ni)表示将数据包Pi传送到节点Ni的路径。我们创建图H，并根据(Pi,Ni)的每条传输路径的传输成功率ri由小到大排序。对于每条(Pi,Ni)，我们根据连续最短路径算法[9]得到图H的互不相交的最小成本路径。单条路径成本的计算方法为：若之前已存在有(Pj,Nj)的传输，则路径成本值为0；否则，成本值为1。每增加一条路径，我们就计算传输成功率qi(S)。当qi(S)达到或超过我们所设定的传输率阈值p，或者没有新的路径加入，则停止计算。冗余编码方法为在所得到的互不相交的最小成本路径中选择类型1的路径，然后根据所选路径(Pi,Pj)得出编码包Pi⊕Pj进行传输。

3.2 冗余编码方法举例

为了能更好地说明冗余编码方法对网络传输和编码的性能改善，下面通过一个简单的例子来阐述。

如图3所示，中继节点R被6个邻居节点N1,N2,…,N6所包围。每个节点都在其相邻节点的通信范围内，同时又在除相邻节点的其它节点范围之外，所以非相邻节点的数据要进行传输或交换，则必须通过中继节点。并假设各条传输链路中只有中继节点R到下一跳节点Ni的链路存在丢包率p，其余链路均为无损链路。

下面假设节点相互间数据包的传输为以下情况：P1,N5→N1;P2,N6→N2;P3,N1→N3;P4,N2→N4;P5,N3→N5;P6,N4→N6。

在图3中还描述了每个节点拥有的数据包。例如，节点N1拥有数据包{P2,P3,P4}。因为节点N1是数据包P3的源节点，另外两个数据包是节点N1在节点N2和N6分别传输数据包P4和P2时“侦听获得”得到。其它节点的情况类似。

图3 编码传输模型Fig.3 Network coding transmission model

如果通过传统路由传输，即不通过网络编码进行传输，则需要进行6次原始数据包的传送完成整个传输过程(即节点收到所需数据包)。如果通过一般网络编码方式传输，则编码方法为根据交换数据包的两个节点得出编码包，因此编码方案为(P1⊕P3,P3⊕P5,P5⊕P1,P2⊕P4,P4⊕P6,P6⊕P2)，共需要6次传输来完成。显然，节点Ni接收到数据包后能够有2种途径解码出所需包。考虑链路丢包率p，则一般的编码传输数据包的传输成功率为qi(S)=1-p·[1-(1-p)k-1]，其中k为发送的编码包数。

根据提出的冗余编码方法，我们设定所选用于计算的传输路径的最小成本路径数为2，那么，计算后得出发送编码包组为(P3⊕P4,P5⊕P3,P1⊕P4,P1⊕P5,P6⊕P1,P2⊕P6,P3⊕P2)。很明显，在冗余编码方法中，我们需要传输7组编码包，相比一般的编码算法多了一次冗余包传输。节点得到编码包后，可以通过至少2种解码方式解出所需数据包。

3.3 仿真实验分析

本文的仿真实验环境采用图3所示的编码传输模型，节点传输要求与前述例子中一致，实验结果通过Matlab进行模拟计算。

图4表明了传统路由传输、网络编码传输和冗余网络编码传输3种传输方式在仿真模型中关于传输成功率的比较。显然，无编码的传统路由方式传输成功率最低,冗余传输编码方法的传输成功率最高。这是因为我们设定了只选择所有满足条件的传输路径中的2条不相交路径作计算，但可能还存在其它的不相交路径，这就使得节点可以通过不少于2种解码方式获取到所需数据包，有效降低了链路丢包率对传输质量的影响。例如，节点N1可以通过以下3种方式解码出数据包P1：P1⊕P4；P1⊕P6,P6⊕P2；P1⊕P6,P6⊕P5,P5⊕P3。而对于一般网络编码方式，节点N1最多能通过两种方式解码出数据包P1：P1⊕P3；P3⊕P5,P5⊕P1。

图4 不同链路丢包率下3种传输方式的传输成功率比较Fig.4 Transmission success rate of three transmission schemes versus link loss rate

图5表示N个信息交换节点采用冗余编码方法的传输成功率的比较。可以看到，接收节点越少，传输成功率越高。这是由于传输节点越多，就存在越多的传输路径，也就存在更多的最小成本路径，由于传输成功率是有关多条不相交最小成本路径连乘的函数，链路丢包率的增加会使传输成功率呈指数下降。尽管如此，冗余编码方法相对一般网络编码方法而言，受制于链路丢包率的影响更小。

图5 采用冗余编码方法，N个不同接收节点的传输成功率比较Fig.5 Transmission success rate of N different receiving nodes in post-redundancy coding strategy

图6表示邻居节点侦听获取数据包的不同概率条件下，选取不同k值(即传输路径的最小成本路径数)所得到的编码包数量。根据冗余编码方法可以得出，选取的k值越大，编码传输的可靠性就越高。但同时在图中可以看出，选取的k值越大，所需的编码包，即需要传输的编码包数量也随之增加。所以，如何选择合适的k值，要根据网络负载和邻居节点侦听获取原始数据包的概率来综合考虑。

图6 编码方法采用不同k值的传输次数比较Fig.6 Transmission times for different values of k

4 结 论

本文针对现存的移动Ad Hoc网络的网络编码方法传输成功率不稳定的问题，利用图论中边-集的概念及相关理论，引出传输冗余度，提出一种基于冗余传输的网络编码方法。仿真结果表明，在网络存在较高丢包率的情况下，冗余网络编码方法的传输成功率比一般网络编码方法高出5个百分点，同时网络的吞吐量不受任何影响，仍能使网络传输成功率保持较高水平。在信息交换的节点数目增加的情况下，信息包的冗余度稍有增加，但传输成功率基本保持稳定。

参考文献：

[1] Ahlswede R,Cai N,Yeung R.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.

[2] Katti S,Hu W,Medard M.The importance of being opportunistic: Practical network coding for wireless environments[C]//Proceedings of the 43rd Annual Allerton Conference on Communication, Control, and Computing Monticello.2005:134-144.

[3] 覃团发,廖素芸,罗会平,等.支持网络编码的无线Mesh网络路由协议[J].北京邮电大学学报，2009，32(1):14-18.

QIN Tuan-fa, LIAO Su-yun,LUO Hui-ping,et al.A network coding aware routing protocol in wireless mesh network[J]. Journal of Beijing University of Posts and Telecommunications,2009,32(1):14-18.(in Chinese)

[4] Lun D S, M′edard M，Effros M.On coding for reliable communication over packet networks[C]//Proceedings of the 42nd Annual Allerton Conference on Communication,Control,and Computing.2004:3-20.

[5] Lun D S,Ratnaker N,Medard M,et al.Minimum-cost multicast over coded packet networks[J].IEEE Transactions on Information Theory,2006,52(6):2608-2623.

[6] Aguayo D,Bicket J,Biswas S,et al.Link-level measurements from an 802.11b mesh network[C]//Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications.[S.l.]:[s.n.],2004:121-132.

[7] Katti S，Hu W，Medard M.XORs in the air: Practical network coding [C]//Proceedings of ACM SIGCOMM.[S.l.]:[s.n.],2006:243-254.

[8] Shravan Rayanchu,Sen Sayandeep,Wu Jianming,et al.Loss-aware network coding for unicast wireless sessions: Design, Implementation, and Performance Evaluation [J].SIGMETRICS Perform. Eval.Rev,2008,36(1):85-96.

[9] Ahuja R K,Magnanti T L,Orlin J B.Network Flows:Theory,Algorithms,and Applications[M].Newyork:Prentice-Hall,1993.