DTN网络环境下动态随机网络编码方法

邓广宏，曹万华，张剑，冯力，程雄

（1.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001；2.武汉数字工程研究所 系统科研部，湖北 武汉 430074）

1 引言

容迟容断网络（DTN,delay tolerant network）是为实现异构、不稳定网络互连而提出的一种覆盖型网络架构，是一种能适应资源受限网络环境的新型网络。与传统网络相比，DTN网络属动态性网络，具有如下特性：1)动态链路，由于节点移动，节点间的链路状态不稳定，甚至是间歇连通的，信道速率、网络分组丢失率等都会随环境的变化而发生改变；2)动态拓扑，由于节点间链路的变化和节点的随机移动，使得网络拓扑经常变化；3)延迟容忍，由于节点间的间歇连通性，DTN网络中数据的传输延迟往往不可预知且时延较长。

为实现在DTN网络中正确、完整、快速的数据传输，研究人员对 DTN网络的移动模型、路由算法、编码传输等方面进行了大量的研究。其中，网络编码在提高网络吞吐量、减小传输延迟、节省节点能耗、增强网络顽健性等方面均显示出其优越性[1～3]。Ahlswede等人[1]提出，通过网络中间节点的编码可以实现单源多播网络的最大流界，而传统的路由技术在一般情况下不能达到这个极限。李硕彦等人[2]也指出，对于一般的多播网络，采用线性网络编码可以达到多播容量的上限。随机网络编码的提出[3]更是将网络编码带入了更为实用的分布式网络领域中，得到了广泛的应用[4～12]。

当前的随机网络编码方案大都是在静态网络中基于多播容量已知的假定[4～9]。文献[4]提出了一种确定性网络编码方法，根据网络的全局拓扑知识先求出多播容量，再确定每一信道的编码系数，然后采用确定性网络编码方案传输数据。文献[5,6]也研究了动态网络拓扑环境下的线性网络编码问题，但也都是在假定多播容量已知且不变的情况下进行的。这对网络拓扑已知、多播率固定的环境下，进行编码构造就显得相对容易。但在DTN等动态网络中，网络拓扑、多播率等往往是动态变化的，这使得传统的随机网络编码方法在DTN网络进行数据传输变得更加困难。首先，变化的信道会以不同的多播率进行数据传输，若采用已有的确定性的随机网络编码方法，则需针对不同的多播率设计不同的编码方案，不仅增加了计算量，编码节点还需同时保存不同多播率下的编码系数，占用了大量的存储空间；其次，动态的网络拓扑使得在信源获知全局网络拓扑信息相当困难，因而也难以获取网络的多播容量，而为使网络吞吐率尽可能地大，源节点多播率应尽量与多播容量相等[5]。因此，传统采用静态多播率的随机网络编码方法已无法适应DTN网络中传输链路和网络拓扑动态变化的网络编码传输过程。

另外，采用随机网络编码方法进行数据传递时，信宿节点只有接收到足够数量的编码分组并使得解码矩阵为满秩时才能进行数据解码，因此，一组编码数据的规模与数据投递延迟和投递成功率有很大关系。在可靠网络连接中，认为一组编码数据的规模与网络多播容量相等为最佳[5]，这样所有编码分组能在一个时隙到达信宿节点实现数据解码。同样，在DTN网络中，若一组编码数据中的所有编码分组能在一个接触周期传递到信宿节点实现解码，则数据投递时延为最小，同时节点缓存的数据最少，因数据拥塞导致编码分组丢失造成的投递率下降也最小。但 DTN网络是动态网络，信道速率和网络多播容量不断变化，显然基于一个固定多播容量确定编码数据规模的静态网络编码传输方式无法时刻保证编码分组在较集中的时间到达信宿节点，因此需根据网络状态动态调整数据编码规模和编码向量，使得信宿节点在一个接触周期收到的编码分组能立即进行数据解码，以减少解码过程的编码分组等待时间。

为适应 DTN网络的动态性，充分利用信道传输能力，提高数据投递率，降低数据投递延迟，本文设计了一种动态随机网络编码方法。基于有限状态的马尔科夫信道模型，通过监测节点间的信道速率，在信源构造了带信道容量的网络流图并计算得到网络多播容量；为消除多播容量的计算延迟，再根据多播容量变化趋势预测网络实时多播容量；然后对随机网络编码方案进行动态扩展和裁剪，设计了与网络多播容量相匹配的可变多播率随机网络编码传输算法，实现 DTN网络环境下数据的动态编码传输；最后基于DTN仿真工具ONE建立了仿真场景，对 DTN环境下的传染病路由方法，传统的静态随机网络编码方法和本文提出的动态随机网络编码方法进行了比较和分析。仿真结果表明，动态随机网络编码方法在DTN网络环境下有更好的数据投递性能。

2 相关知识

2.1 网络模型

本文假设由物理空间中随机分布的若干个移动终端、移动汇聚节点和固定数据接收点等构成一个 DTN网络，并仅考虑单源多宿情况下的数据投递过程。假设该DTN网络具有如下性质。

1)所有终端节点随机分布，终端节点以固定功率向周边接收节点和其他终端发送数据；节点间的数据传输速率受干扰情况和传输距离的影响；终端节点为节省能源，会根据应用情况周期性休眠，能源耗尽时会退出网络。

2)数据接收点处于某固定位置接收、处理和转发数据。汇聚节点呈连续规律性移动，经过终端节点周边时，从周围终端节点获取数据,在汇聚节点移动到目的节点时，将数据转发到目的节点。

3)由于节点的移动性，造成节点间的传输链路呈连续动态变化特性，并且假定链路的变化在有限马尔科夫信道模型的信道状态间连续变化。

4)节点间存在反馈链路，信源节点将数据分组传递到信宿节点，各接收节点通过可靠上行链路信道将节点和链路的状态信息反馈回发送节点，再逐级反馈回源节点。

2.2 多播率与多播容量

将网络模型简化描述为网络流图 G=(V,E)，其中，V表示节点集合，E表示边的集合，对于节点i和j，i,j∈V，(i,j)∈E表示网络中的一条边，每条边(i,j)对应于一个非负数wij，表示为网络中该信道的容量。

定义1 在单源多播网络中，多播率是指信源节点s的数据传输速率，记为h

多播容量指信源与信宿间的最小割值[1]，记为C。

2.3 随机网络编码

随机网络编码允许网络节点在一个给定的有限域(也称为伽罗华域)GF(2m)独立随机地选取一组编码系数作为编码向量，并采用这组编码向量对节点输入信息进行线性运算，同时也将这组编码向量作为分组头控制信息随节点输入信息发给相应的输出边[2,3]。信宿节点在接收到足够的编码数据分组后进行高斯消元，得到原始信息。由于随机网络编码产生的编码向量是在有限域内随机产生，因此可能造成编码矩阵奇异，导致在信宿节点无法解码出原始信息，Tracey Ho等人[3]证明了接收节点可以较大的概率正确恢复出信源所发送的信息，当有限域GF足够大时，随机编码方式产生的编码矩阵满秩的概率趋近于1，即可解码概率为1。

3 网络多播容量计算

DTN网络是动态性网络，每一时刻的网络拓扑及其相应的多播容量都是变化的。为获得最佳的网络编码传输效率，信源多播率应尽可能与网络多播容量相等[5]，为此本文在马尔科夫信道模型[13]的基础上动态监测节点间的信道速率，并通过反馈链路在信源节点构造网络流图，计算得到网络的多播容量并预测实时多播容量，再根据多播容量的变化动态地调整随机网络编码方案的多播率。

3.1 有限状态马尔科夫信道(FSMC)模型

有限状态马尔科夫信道(FSMC)[13,14]是将信噪比的变化范围划分为有限个状态

Γk+1-Γk表示每个信道状态的信噪比区间，并假设信道为慢衰落，信道只在相邻的状态之间转变，如图1所示。信道状态间转移概率为

其中，St=i表示 t时刻信道的状态为i,Pi,j表示信道状态从i变化到j的概率。

图1 有限状态马尔科夫信道模型状态转移图

从文献[14]可知，在瑞利衰落信道下，节点 i接收到数据的瞬时信噪比(SNR)γ的概率密度函数为

fd为多普勒频移,若发生数据的符号速率恒定时，Tc为一恒定值[4]。对应的为

则可得到节点i的状态转移矩阵为

3.2 信道速率动态获取算法

假设节点接收数据时节点间信道状态在一个时隙内处于稳态，则在一个时隙段，节点i通过该信息接收到数据量的期望值为

其中，ω表示源节点发送一个数据帧所用时隙大小，V=(v1,v2,…,vn)表示对应于每个信道状态的数据速率，L=(l1,l2,…,ln)表示对应于每个信道速率下的分组丢失率，V LT=(v1l1,v2l2,…,vnln)，表示信道稳态概率向量的转置。

信道e的状态向量为Se=(s1,s2,…,sj…,sn),信道处于状态sk的状态元素值为

对于状态向量 Se=(s1,s2,…,sj…,sn)，计算状态概率矩阵SePi取矩阵中第k列并转置，记为

计算该列中元素的最大值，并把该值置为1，其他值置为0，记为'SP，则信道e新的状态向量为=SP'，由信道的状态向量对应到信道的数据速率向量可得到信道当前的信道速率。

采用上述信道速率的计算方法，即可得到网络中各链路的信道容量(即网络流图中的 wij，以信道速率表示)。算法如算法1所示。

算法1 信道速率动态获取算法

Input

V:信道e的数据速率向量。

L:信道e的数据分组丢失率向量。

Output

vi:信道e的信道速率。

Step

1)统计信道在一个时隙接收到的数据量D；

3)按式(2)和式(3)计算信道处于S0状态的稳态概率向量；

4)根据信道的数据速率向量V，分组丢失率向量L，按式(8)计算信道在一个时隙接收数据的期望值向量；

7)st=s0，返回 vi,st；

8)else

9)根据式(9)获取信道转移概率向量SP；

10)计算SP中元素的最大值，并把该值置为1，其他值置为0，得到信道e新的状态向量st；

11)s0=st；

12)end if

13)end for

3.3 多播容量计算

根据多播容量的定义和最大流最小割定理，多播容量的计算可转化为网络流图最大流的计算。网络最大流的计算方法已有广泛的研究和算法[15]。结合应用场景，本文采用改进的割集矩阵算法求取网络流图的最大流。

各传输节点通过3.2节的计算方法得到其连通信道的信道容量wij后，通过信道的反馈链路将链路状态反馈回源节点，即可在源节点得到某一时刻的网络流图。

wij表示节点i到节点j之间信道传输速率，若wij=0则表示节点之间不连通。

对网络流图 G=(V,E),i∈V，假设由 i出发的所有出弧构成的集合称为i的一个部分割，记为

对应的部分割的容量矩阵为

其中，Ki,j={wim,m≠j,(i,m)∈E,i,j,m∈V }表示由节点i出发，且不指向节点j所有出弧的弧容量构成的集合，即约束的部分割容量；若i与j不关联，则令Ki,j=Λ。

取矩阵 K的第一行包含K1,1的子集 Q={K1,1,K1,j,…,K1,m}，再取第(j,m)行中对应的列，构成原矩阵的m阶子阵mD，表示从源节点出发的一个子图。

当遍历整个部分割集容量矩阵K后，即得到网络的所有割集。当得到一个网络的所有割集以后，只需计算出各个割集的容量即可，进而比较大小，找出最小割，由最大流最小割定理，得到网络的最大流，算法如算法2所示。

算法2 最小割计算算法

Input

A：网络信道状态图。

Output

C:网络的最小割。

Step

1)C=+∞,T=0;

2)foreach(wij∈A)

3)计算 Ki,j={wik,k≠j,(i,k)∈E,i,j,k∈V }，构建部分割容量矩阵K；

4)end for

5)for(m=1;m

6)在K中取出所有的m阶子阵 Dm；

9)if(T

10)C=T;

11)end if

12)end for

13)return C;

根据多播容量的定义和最大流—最小割定理，可得到网络的多播容量C。

3.4 信道容量反馈过程分析

在节点的每次接触过程中，通过节点间的上行链路将节点状态和链路信道容量逐级反馈回信源节点。反馈信息格式如图2所示，反馈信息大小与节点的连通信道数有关，往往在几十个字节以内，信息量少，传输时间短；另外，反馈信息通过节点信息传输过程中的上行链路传递，对下行链路影响不大，因此，相对于下行数据信息的传递，反馈信息增加的链路开销可不计考虑。

图2 随机线性网络编码的数据分组格式

由于 DTN网络中节点间的连接链路是动态变化的，各信道状态反馈到信源需要一定的时间，因此反馈到信源节点的信道容量和状态信息具有滞后性，但链路状态的变化是连续的，并且各链路的状态变化存在互补性，节点移动过程中移出区域的信道容量变小，但移入区域的信道容量则变大，因此可假定网络多播容量的变化在网络连通状态不存在剧烈抖动的情况下也是连续变化的。通过 3.3节描述的多播容量计算方法得到当前反馈的网络多播容量，此多播容量计算值存在滞后性，但可根据当前计算的多播容量和多播容量变化趋势对网络的实际多播容量进行预测，方法如式(10)所示。首先根据前两次多播容量 Cold,Ccur计算得到多播容量的变化趋势和梯度α，再根据α和多播容量计算值预测网络的实时多播容量Cpre

4 随机网络编码方案的动态性扩展

4.1 随机网络编码的裁剪和扩展

文献[16]通过研究编码节点的局部编码向量和全局编码向量，提出了一种线性网络编码的导出和扩展方法，并在理论上证明了该方法的可行性。在该方法的基础上本文设计了面向可变多播率的随机网络编码动态裁剪和扩展算法。

本文采用伽罗华域GF(2m),假设信源多播率为h，并保持与多播容量一致，即 h=C，在单位时间播出的信息为x1,x2,…,xh，属于GF(2m)，每一字符均为m bit，信息的编码操作对应于伽罗华域上的字符运算。信道e∈E传输的编码信息记为I(e),也属于GF(2m)上的字符。为方便描述，信道e=(i,j),记i=tail(e),j=head(e)。

对于随机线性网络编码，参与编码的每个网络节点k的输出信道e，有

对应于多播率h和每个编码信道e上的编码向量ne=(ne,1,ne,2,…,ne,j)，形成了一个随机线性编码的编码方案，记为Ψ。

Ψ={(n1,1,n1,2,…,n1,j),…,(ni,1,ni,2,…,ni,j)},0＜i≤|E|,0＜ j≤h，(|·|为集合或向量的元素个数,下同)。

由于参与网络编码的网络节点往往不止一个，因此信宿节点收到的编码数据信息是多个编码传递节点进行多次编码后形成的全局编码数据。这时，在信宿节点t接收到的编码信息为

其中，gi=neMk，ne为一个1行、h列的编码向量矩阵，Mk是节点 k的输入向量组成的输入矩阵，为一个以k的输入信道数为行数、列数为h的矩阵。

根据线性方程组可解的条件可知，若所有信宿节点所接收的数据分组中以gi形成的编码矩阵的秩均为h，则原始数据在信宿节点可被还原，称此编码方案为一个可行的编码方案。

随机线性网络编码的数据分组格式如图3所示。

图3 随机线性网络编码的数据分组格式

对于一个多播率为h编码方案Ψ和一个多播率为k的编码方案ψ，k≤h，2个编码方案间存在如下关系

其含义为:当e为源点s的输出信道时,则信道e在s节点的编码方案ψ下的编码向量由在编码方案Ψ下的编码向量的前k个分量构成;对于其他信道,在ψ下的局部编码向量与Ψ下的局部编码向量相同，蒲保兴等人[16]已证明通过此方法对编码方案的裁剪和扩展是可行的。

同样，Ψ的编码方案可由ψ的编码方案添加h-k个编码量后扩展得到。如图4所示，图中的Ψ可由ψ扩展而来。

图4 随机网络编码的扩展示例

4.2 面向可变多播率的动态随机网络编码

利用3.3节和3.4节描述的网络多播容量计算方法和4.1节介绍的随机编码方案的裁剪和扩展方法，设计了面向可变多播率的动态随机网络编码算法。算法首先取一个初始多播率进行试播，将数据编码传递到信宿节点，再根据节点反馈的链路状态信息进行多播率修正和编码向量修正，进行下一组数据的编码传递，然后再修正，再编码传递，直至数据传递完毕。算法描述如算法3所示。

算法 3 面向可变多播率的动态随机网络编码算法

Input

G=(V,E)：网络流图。

Step

1)if(信源节点)

2)设置源节点i的初始多播率h；

3)信源将数据分组按多播率进行分组x1,x2,…,xh，并向中继节点转发；

4)while(信道速率改变)

5)信源节点根据3.3节描述方法计算网络多播容量C；

6)根据式(10)预测当前多播容量C'，设置信源多播率k=C'；

7)按多播率 k对数据分组进行分组x1,x2,…,xk，并向中继节点转发；

8)end while

9)end if

10)if(中继节点)

11)接收编码数据分组并获取编码向量长度k，对比上次编码向量长度h；

12)if(h=0)

13)对每个输出信道随机生成向量(ni,1,ni,2,…,ni,k)，构建编码方案Ψ={(n1,1,n1,2,…,n1,k),…,(ni,1,ni,2,…,ni,k)}；

14)else if(k

15)取原编码方案中前 k各分量生成一组编码方案Ψ={(n1,1,n1,2,…,n1,k),…,(ni,1,ni,2,…,ni,k)}；

16)else if(k>h)

17)中继节点随机生成k-h个分量，扩展生成编码向量长度为k的编码方案Ψ={(n1,1,…,n1,h,…,n1,k),…,(ni,1,…,ni,h,…,ni,k)}；

18)end if

19)按式(11)对输入数据进行编码计算，并向输出信道转发。

20)根据 3.2节方法获取信道速率并通过反馈链路向信源反馈；

21)end if

22)if(信宿节点)

23)接收编码数据分组，构建编码向量矩阵；

24)if(编码向量矩阵满秩)

25)按式(12)进行数据译码；

26)end if

27)end if

4.3 信宿节点译码

由于 DTN网络中传输链路的动态性，链路的连通状态往往不确定，为在有限的时间传输尽可能多的数据，信宿节点不立即进行解码操作，而是判断接收到的数据分组达到可解码数量时，即接收到数据分组的个数大于等于编码向量的长度时，再判断所有编码向量组成的编码矩阵是否满秩，若为满秩则利用高斯消元法进行解码得到原始数据，否则随机选择一个输入节点请求其对数据分组进行重新编码计算后发送一个新的编码分组，信宿节点再进行数据解码。

数据编码传递过程中采用了可变多播率的动态随机网络编码方案，源节点可根据多播容量的变化动态调整一组参与编码的数据量，使得编码数据量与网络多播容量的变化相适应，这样同一组的编码分组能在相对集中的时间到达信宿节点，进行数据解码，降低了数据解码的等待时延。

假定某时刻源节点到目的节点的多播容量为h，数据从信源到信宿的一次传递过程所需时间为一个接触周期，信源节点按某一多播率 k（对应的编码数据个数为k）进行编码传递。

若k=h，则信宿节点能在一个接触周期内收到h个数据分组，若解码矩阵为满秩，则数据分组能全部解码，此时，网络利用率最高，数据解码延迟最少。

若k>h，发送数据量超过了网络多播容量，根据抽屉原理，则必有k-h个数据分组在下一个接触周期到达信宿节点，同时，信宿节点必须缓存上一个时隙的编码数据分组，等待数据分组到齐后进行解码，因此，信宿节点必须有h个数据分组的缓存空间，并在下个接触周期所有编码分组到达后才能解码数据。

若 k

采用可变多播率的动态随机网络编码方法能动态调整信源多播率k，使得k=h，让数据传递过程在更多的时间里处于一种最佳传输状态，降低了数据传递延迟。而对固定多播率的情况，在传递过程中大多数时间里处于k≠h状态，也就造成了动态网络环境下网络利用率和数据投递性能的降低。

由上述分析可知，动态随机网络编码方法更适应于 DTN网络应用，在数据投递延迟、网络利用率及数据投递率等方面都更优于传统的静态网络编码方法。

5 仿真实验与分析

5.1 仿真平台

本文基于DTN仿真软件ONE1.4.1(opportunistic network environment simulator)[17]进行了DTN网络环境仿真。但 ONE缺少对物理层和链路层的仿真支持，当处于通信范围内的2个节点通信时，ONE假定它们的信道速率是不变的，而在真实世界中，由于距离或干扰等情况的变化，信道传输速率往往动态变化的。另外，DTN网络中，节点为节省能源往往不会处于持续通信状态，而是在工作和空闲状态之间不断切换。为模拟更真实的 DTN场景，本文对DTN仿真软件ONE进行了扩展，在ONE中添加了基于马尔科夫信道模型的物理层和链路层支持，并在核心模块中添加了物理层配置接口和休眠机制，可以模拟传输链路的变化情况和节点的状态转换，从而使仿真场景更趋于真实。

为模拟传输速率的动态变化，在物理层配置接口实现了 ConnectionListener接口中的 hostsConnected方法，当2个节点进入到彼此的通信范围时，节点就会根据配置文件setting中的Scenario.disturbRate=value来设置环境干扰产生的概率，通过Scenario.disturbType=value来配置干扰的类型。另外，物理层配置接口还可以根据距离的远近自动调节传输速率。定义了transmitRange=nearestTransDis，furthestTransDis用来描述通信距离。距离近于nearestTransDis传输速率保持不变，在nearest TransDis和furthestTransDis传输速率缓慢地降低，远于furthestTransDis的随着距离的不断增大，传输速率快速地降低。为实现节点间歇性休眠机制，在setting配置文件中定义Group.sleep=value1,value2参数。当节点资源开销超过了一定量时，节点就会随机选择value1至value2之间的值进行休眠，经过一段时间后，节点恢复运行状态，重新发送和接收消息数据。

为实现数据的编码传输，在ONE的核心模块、路由模块和应用模块中扩展实现了数据分组的编码解码功能，并实现了SRNC和DRNC 2个网络编码类，实现数据分组的静态随机网络编码和动态随机网络编码传输。通过配置文件中的Scenario.trans Type=value设置数据传输方式(SRNC、DRNC和ER)，其中，SRNC表示静态随机网络编码方式，DRNC表示动态随机网络编码方式，ER表示传染病路由方式。

5.2 仿真环境

通过对ONE仿真环境的扩展和配置，本文设计了一个在战场侦察和灾难搜救环境下典型的微缩型DTN网络场景：在没有通信环境的半径为2000 m的地理区域内均匀分布若干执行侦察任务的移动个体，节点运动符合RandomWaypoint移动模型，节点有效传输距离为1～5 m，节点缓存为5 MB。同时，在指定的路径上存在一些车载移动汇聚通信节点，节点有效传输距离为2～20 m，节点运动符合MapBasedMovement移动模型，节点缓存为20 MB。此外，在区域指挥中心有固定数据接收点执行数据收集和处理，数据接收点的有效通信距离为10～300 m。所有节点都有数据收发能力，都可作为信源、传递节点和信宿节点。场景仅考虑单源多宿情况，从所有节点随机选取一个信源节点，并随机选取总节点数的20%作为信宿节点，其他节点为传递节点。

为仿真以上网络环境，在ONE中设置了三类节点组。分别设置了终端节点、汇聚节点和数据接收点的节点数、节点移动模型和信道模型等参数，三类节点以8:1.5:0.5的比例生成。采用动态随机网络编码方式时部分主要的仿真参数如表 1所示。

表1 部分仿真参数配置

仿真过程中，各节点按设定的移动模型在区域内移动，节点间的信道速率随节点的移动动态变化，网络中的信源节点分别采用路由或网络编码的方式向信宿节点投递数据，信宿节点统计接收数据量和接收时间，最后根据发送数据量和发送时间计算出数据投递率和投递延迟。

5.3 结果分析

在ONE1.4.1的仿真环境中，本文对DTN网络环境下基于传染病路由的传输方法（ER,epidemic routing）、静态随机编码传输（SRNC,static random network coding）和动态随机编码传输（DRNC,dynamic random network coding）3种方法进行了仿真实验，分析了3种方法的数据投递率和投递延迟。其中数据投递率定义为信宿节点收到的数据分组数量与信源节点发出数据分组数量的比值，实验结果取所有信宿节点数据投递率的均值；数据投递延迟定义为数据分组从信源节点发出开始到信宿节点收到报文所花费的时间，实验结果取所有信宿节点收到的所有数据分组的平均投递延迟。3种方法的数据投递过程简要描述如下。

ER：当节点相遇时，2个节点交换对方没有的数据分组，但不删除原数据，直至信宿节点收到数据。

SRNC：源节点以固定的多播率向邻接节点传递数据，中间传输节点随机生成编码向量对输入数据进行编码计算后传递给周围节点，信宿节点收到足够的编码数据后进行解码计算得到数据信息。

DRNC：源节点根据网络多播容量的变化以可变多播率向邻接节点投递数据，中继节点扩展或裁剪随机编码向量对数据分组进行编码计算后投递给邻接节点，信宿节点收到足够的解码数据分组后进行解码计算得到数据信息。

图5和图6是ONE仿真环境中ER、SRNC、DRNC 3种方法随网络规模变化的平均投递延迟和数据投递率的对比分析。随着节点密度的增加，数据投递率更高，而平均时延也更长，这主要是由于节点的增加使得数据可投递路径更多，数据投递成功率因此也更大，而节点增多也使得数据转发次数增加，产生更多的传递延迟，因此平均时延也更长。3种方法中，DRNC方法的数据投递率和投递延迟都要优于ER和SRNC方法。其中ER方法采用多副本洪泛，造成网络中存在大量冗余数据分组，当节点缓存耗尽时，则会导致数据拥塞，传播延迟加大，数据投递率降低，因此在资源受限时，其投递率和延迟等性能要低于编码传输方式。SRNC采用静态多播率传输数据，不能适应网络多播容量的动态变化，容易造成网络带宽的不充分利用和信宿节点的解码时延增加，导致其数据传递时延较长，投递率降低。DRNC采用适应网络多播容量变化的可变多播率进行动态编码传输，相比于SRNC，编码分组能在相对集中的时间到达信宿节点，减少数据解码等待时间，降低了数据解码延迟，同时数据的快速投递使得网络中拥塞数据减少，也降低了数据分组丢失率，提高了数据投递率。

图5 平均投递延迟随网络规模变化的性能比较

图6 数据投递率随节点增加的性能比较

为验证 DTN环境下网络拓扑以及信道状态变化加剧的情况下3种方法的数据投递性能，通过加快终端节点运动速度使得链路状态、网络拓扑变化加剧。图7和图8对比分析了网络规模为100个节点时，ER、SRNC、DRNC 3种方法随节点移动速度变化的平均投递延迟和数据投递率。

图7 平均投递延迟随节点移动速度变化的性能比较

图8 数据投递率随节点移动速度变化的性能比较

随着节点移动速度增加，节点间链路变化更频繁，但节点间相遇并转发数据的机会增多。在ER方法中，传输链路的频繁变化同时也造成传递成功率降低，使得节点缓存拥塞，数据分组的排队延迟加大，平均投递延迟在节点移动速度到一个均衡值后反而更差，数据投递率也因分组丢失增多呈下降趋势。SRNC方法采用网络编码的方式进行数据传输，产生的冗余数据分组相对较少，数据分组排队延迟较小，因此平均延迟和投递率都略好于ER方法，但在动态网络中，SRNC以固定多播率进行编码传输使得数据解码时编码分组的等待时间不可控，造成数据投递时延增大，投递率较差。DRNC采用可变多播率编码传输方式，能随网络多播容量的变化调整信源多播率，相比于SRNC其对网络变化有更好的适应性，因此数据传递过程中节点移动速率增加反而会加快数据的转发速度，另外，信源数据发送速度与多播容量相匹配也使得数据在传递节点中产生拥塞，造成分组丢失及延迟等情况发生的概率降低，也提升了数据投递性能。

另外，通过实时多播容量预测方法对DRNC方法的投递性能也有所增益。节点移动过程中链路变化的互补性使得网络多播容量呈连续平缓变化趋势，因此通过趋势预测实时多播容量能较真实地逼近实际网络状态，使得多播率更贴近实际多播容量，编码分组能相对集中地到达信宿节点，降低了解码延迟。

综合以上仿真结果可以看出，DRNC方法更适应于 DTN网络等动态网络，在网络规模增大和节点移动速度增加的情况下，DRNC方法都有更好的数据投递性能。

6 结束语

通过分析传统的静态随机网络编码在DTN网络应用中的动态性适应能力的不足，提出了一种动态随机网络编码方法。该方法在马尔科夫信道模型的基础上动态获取节点间的信道速率并在信源节点计算并预测网络的多播容量，然后根据变化的多播容量设计了可变多播率的动态随机网络编码传输方法，实现DTN网络环境下数据的动态网络编码传输。最后，在DTN网络仿真工具ONE上进行了仿真实验，对比分析了DTN网络中基于传染病路由方法、静态随机网络编码方法和动态随机网络编码方法的数据投递率和数据投递延迟。仿真结果表明，动态随机网络编码方法更能适应DTN网络的动态性，有更好的数据投递性能。通过仿真实验，也发现了该方法存在的不足和需要进一步深入研究的地方，如网络多播容量计算方法和信道速率计算方法的性能优化；结合DTN路由算法和分组丢弃策略，提高编码分组的传递有效率等实现随机网络编码方案的优化等，这些将是课题以后深入研究的方向。

[1]AHLSWEDE R,NING C,LI S,et al. Network information flow[J].IEEE Transactions on Information Theory,2000,46(4): 1204-1216.

[2]LI S Y R,YEUNG R W,CAI N. Linear network coding[J]. IEEE Transactions on Information Theory,2003,49(2): 371-381.

[3]TRACEY H O,M´EDARD M,KOETTER R,et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[4]LI B C,NIU D. Random network coding in Peer-to-Peer networks:from theory to practice[J]. Proceedings of the IEEE,2011,99(3):513-523.

[5]HAEUPLER B,KARGER D R. Faster information dissemination in dynamic networks via network coding[A]. PODC’11[C]. California,USA,2011.381-390.

[6]FONG S L,YEUNG R W. Variable-rate linear network coding[J].IEEE Trans on Information Theory,2010,56(6):2618-2625.

[7]卢冀,吴成柯,肖嵩等. 基于机会式网络编码的高效广播传输算法[J]. 通信学报,2012,33(1):64-70.LU J,WU C K,XIAO S,et al. Efficient broadcast transmission algorithms based on opportunistic network coding[J]. Journal on Communications,2012,33(1): 64-70.

[8]ROUAYHEB A E L,SPRINTSON A,GEORGHIADES C. Robust network codes for unicast connections: a case study[J]. IEEE/ACM Transactions on Networking,2011,19(3):644-656.

[9]DEB S,MEDARD M,CHOUTE C. Algebraic gossip: a network coding approach to optimal multiple rumor mongering[J]. IEEE Transactions on Information Theory,2006,52(6): 2486-2507.

[10]蒲保兴,杨路明,王伟平. 网络拓扑未知环境下确定性网络编码数据传输[J]. 电子学报,2009,37(10):2119-2124.PU B X,YANG L M,WANG W P. A deterministic data transmission approach with network coding under unknown network topology[J].Acta Electronica Sinica,2009,37(10):2119-2124.

[11]汪玉,卢汉成,洪佩琳等. 基于随机线性网络编码的双源交替调度算法[J]. 电子与信息学报,2011,33(12):3008-3014.WANG Y,LU H C,HONG P L,et al. Random linear network coding based alternative scheduling algorithms with two sources[J]. Journal of Electronics＆Information Technology,2011,33(12): 3008-3014.

[12]GOPINATHAN A,PENG Z. Optimal layered multicast[J]. ACM Transactions on Multimedia Computing,Communications and Applications,2011,7(2): 1-20.

[13]ZHANG Q,KASSAM S. A finite-state markov model for rayleigh fading channels[J]. IEEE Transactions on Communications,1999,47(11):1688-1692.

[14]RAZAVILAR J,LIU K J R,MARCUS S I. Jointly optimized bit-rate/delay control policy for wireless packet networks with fading channels[J]. IEEE Transactions on Communications,2002,50(3):484-494.

[15]张宪超，江贺，陈国良.节点和边都有容量的有向平面网络中的最小截和最大流[J].计算机学报,2006,29(4):544-551.ZHANG X C,JIANG H,CHEN G L. Minimum cuts and maximum flows in directed planar networks with both node and edge capacities[J]. Chinese Journal of Computers,2006,29(4):544-551.

[16]蒲保兴,杨路明,王伟平. 线性网络编码的导出与扩展[J].软件学报,2011,22(3):558-571.PU B X,YANG L M,WANG W P. Generation and extension of linear network coding[J]. Journal of Software,2011,22(3): 558-571.

[17]KERÄNEN A,OTT J,KÄRKKÄINEN T. The ONE simulator for DTN protocol evaluation[A]. Proc of the 2nd International Conference on Simulation Tools and Techniques[C]. Rome,Italy,2009.