随机线性网络编码^[14]是一种分布式网络编码方式,它能适应拓扑动态变化、无中心节点的网络.随机线性网络编码的提出推动了网络编码走向实用,特别是将网络编码应用于无线网络,使网络编码不再受限于确定的网络拓扑及集中式的算法.以下将从发送端、转发节点和接收端分别描述随机线性网络编码基本原理.

源节点.如图1,信源以m为单位,将数据包分组,每组都用X₁,X₂,…,X_m表示m个数据包.从有限域F_q中随机地选择m个数g_i1, g_i2,…, g_im组成第i个数据包的编码,对X₁,X₂,…,X_m进行编码组合,编码后变成了M(>m)个数据包,用Y₁,Y₂,…,Y_M表示,即Y_i=∑^m_j=1g_ijX_j. 信源把编码数据包Y₁,Y₂,…,Y_M的组标志和相应的编码g_i1,g_i2,…,g_im添加到数据包前发送出去,编码后的数据包格式如图2.

图1 随机网络编码示意图
Fig.1 Random network coding scheme

图2 随机网络编码下的数据包结构
Fig.2 Structure of random network coding packet

中间节点.中间节点接收到一个数据包,首先判断与缓存中已有的编码数据包是否线性相关.若无关,则放入缓存; 否则,丢弃.假设中间节点R缓存中存在k个相同组标识的线性无关的数据包Y₁,Y₂,…,Y_k,从有限域F_q中随机选择k个数生成局部编码g^r_i1, g^r_i2, …, g^r_ik, 对应的编码过程为Y^r_i=∑^k_j=1g^r_ijY_j. 由此,得到原始信息对应的全局编码h^r_i,j=∑^k_j=1g^r_ijg_jz(z=1,2,…,m), 利用新编码更新数据包中的编码系数后继续向下发送.

目的节点.目的节点接收到至少m个线性无关编码数据包后,可根据式(1)解码得到原始数据包.

[X₁

X₂



X_m]=[g₁₁ … g_1m

  

g_m1 … g_mm][Y^'₁

Y^'₂



Y^'_m](1)

其中,g_ij(i=1,2,…,m; j=1,2,…,m)为目的节点得到的编码系数; [Y^'₁,Y^'₂,…,Y^'_m]^T为对应的编码数据包.Ho等^[15]指出,当所有节点的编码系数都在有限域F_q内随机产生,无差错传输时,目的节点成功解码的概率超过(1-d/q)^β. 其中, d为目的节点数; q为有限域大小; β为产生的随机编码系数数目.若选择F_q=2⁸, 即q=8, β=3, 则有98.8%的成功解编码率,相应数据包中只需增加3×8=24 bit的数据记录编码系数,不会带来过高的编码管理开销.

在传统路由机制下,无线多跳网络中源节点会依据不同的路由指标确定一条到达目的节点的传输路径,将数据包通过中继转发至目的节点.这种路由方式忽略了无线信道的广播特性,即数据包会被其发送节点通信范围内的多个邻居节点监听.多路径传输机制充分利用此特性,发送节点会选择多个邻居节点组成潜在的转发节点集合并参与数据包转发,从而提高传输可靠性.

图3 网络编码在无线网络中应用
Fig.3 Application of network coding in wireless network

本研究通过一个实例理解多路径传输思想及其与网络编码结合的优势.如图3,3个节点S、R和D组成的通信网络,S-R、R-D和S-D之间链路上数据包传输成功概率分别为1.0、0.9和0.5,网络采用时分复用的信道控制方式.假设S需发送数据包P₁和P₂到D,传统路由方式下会选择传送成功率最高的链路转发,即选择S-R-D路径发送,传输成功概率为1.0×0.9=0.9.实际上,由于无线信道具有广播特性,S向R发送数据时,D能侦听到S发送的数据.D将缓存侦听到S发送给R的数据包,假设D侦听到了数据包P₁, 由于D是目的节点,D将不再向下转发,否则D可参与转发.此时,S-D之间成功传输概率为1-(0.5×0.1)=0.95.可见,针对一个数据包的传输,选择2条传输路径的传输成功率较1条传输路径的成功率提高了5%,R只需转发P₂就能保证D收到P₁和P₂.但D需告知R自己已侦听到了P₁,才能保证R不重复转发P₁, 这需在网络中建立协作机制,必将消耗额外的通信资源.

采用随机网络编码,不需建立节点之间的协作机制就可避免重发数据包.如图3(b), S将P₁与P₂线性组合成两个编码数据包后发送给R,假设D侦听到了其中的一个编码数据包α₁P₁+β₁P₂, [α_i,β_i]为各编码数据包中的编码系数.R将接收到编码数据包再编码,如式(2),此时R只需将α₃P₁+β₃P₂和α₄P₁+β₄P₂中的一个转发给D,假设为α₃P₁+β₃P₂,在保证[α₁,β₁]和[α₃,β₃]线性无关的条件下,D能根据式(3)解编码得到P₁和P₂, 解决了重复发送问题.

[α^'₁ β^'₁

α^'₂ β^'₂][α₁P₁+β₁P₂

α₂P₁+β₂P₂]=[α₃P₁+β₃P₂

α₄P₁+β₄P₂](2)

[P₁

P₂]=[α₃ β₃

α₄ β₄]^-1[α₃P₁+β₃P₂

α₄P₁+β₄P₂](3)

表1为图3实例中全网络发送的时隙分配情况,详细列出了每个时隙中各节点缓存的数据包.从表1可见,采用随机网络编码与机会路由结合的方式,少占用一个发送时隙,从而提高了网络吞吐量.可见,随机网络编码与多路径传输结合的方式,可有效提高网络传输可靠性.

表1 采用网络编码前后的时隙分配情况
Table 1 Time slot assignment with/without network coding

对传统单径路由机制,选择链路质量最好的一跳路径进行传输,即单个数据包传输成功概率为

p_single=max(p_Si×p_Di)(4)

若采用端到端前向纠错机制,源节点在原始数据包中加入数据冗余增加传输可靠性.假设将m个原始数据包编码成M_single(>m)个数据包进行传输,目的节点D只要能成功接收到其中m个数据包就能恢复原始数据包,则成功完成一次传输的概率为

p_SD=1-∑^m-1_k=0(M_single

k)p^k_single(1-p_single)^M-k(5)

在多路径路由机制下,源节点寻找多条到目的节点的路径进行数据传输,只要有一条路径有效就能完成数据包发送,所以多路径传输下,单个数据包发送成功的概率为

p_multi=1-∏ⁿ_i=1(1-p_Sip_Di)(6)

同样采用端到端前向纠错机制,发送存在数据冗余的M个数据包,目的节点能成功完成m个原始数据包接收的传输概率为

p_SD=1-∑^m-1_k=0(M

k)p^k_multi(1-p_multi)^M-k(7)

在此分析基于网络编码的多路径传输机制的可靠性.采用随机网络编码和多径的传输方式,S先将m个原始数据包进行线性编码组合,编码成M(>m)个线性无关编码数据包,它们属于同一批(分批编号识别),发送给中继节点集合R, 再由R转发给D.R中节点i成功接收k个编码数据包的概率为

p_i,k={(M

k)p^k_Si(1-p_Si)^M-k, 0≤k<m

1-∑^m-1_k=0p_i,j, k=m(8)

其中,i=1,2,…,N.

定义q_i,r为目的节点D接收来自R中i节点的r个编码数据包的概率. 因为每个中继节点最多发送m个编码数据包,故得

q_i,r=∑^m_k=0p_i,k(k

r)p^r_Di(1-p_Di)^k-r, r≤k(9)

则目的节点共接收到R转发的k个编码数据包的概率为

p_D,k=∏^N_i=1q_i,ri,(10)

其中, r_i=0, 1, …, k, 且∑r_i=k.

D成功接收m个线性无关的编码数据包就能解编码得到原始数据包,再向上游节点发送Ack确认数据包,让上游节点停止编码数据包转发,可见S到D完成一批编码数据包传输的概率为

p_D,m=1-∑^m-1_k=0p_{D, k}(11)

本研究针对图4模型,设置3个中间节点组成转发节点集进行数值实验.假设链路上包传输成功概率初始值为{p_S1, p_S2, p_S3}={0.8, 0.6, 0.4}, {p_D1, p_D2, p_D3}={0.8, 0.6, 0.4}. 为对比3种传输方式的可靠性,初始化设置3种传输方式下原始数据包数m=3, 编码冗余数据包数M_single=M=5. 为评估3种传输方式的抗干扰特性,以S-R₁链路为例,改变该链路包丢失率e=1-p_S1, 并观察链路质量对3种传输方式下可靠性影响,如图5(a).

图5 可靠性数值分析结果
Fig.5 Reliability numerical result

由于随机产生的编码之间线性相关的可能性很小,所以对应用了网络编码的传输方式,我们只需对比不同编码冗余数目M下的传输可靠性,如图5(b).由图5(a)可见,网络编码与多路径传输相结合的传输方式可靠性最优,其次是多路径传输方式,这两种方式下的传输可靠性都远优于单路径传输方式.随着S-R₁链路包丢失率增加,3种传输方式下的传输可靠性都会下降,但用了网络编码的传输方式其可靠性下降最缓,抗干扰性更强.单路径传输方式下的传输可靠性下降较快,当S-R₁链路恶化到一定程度,源节点会选择其他路径发送数据,可靠性将不再受e变化影响.图5(b)显示,网络传输可靠性随M的增加而提高, M超过一定值后性能改善效果趋于稳定.增加M意味需发送更多数据包,这会消耗更多的网络资源,所以在确定网络编码方案时,需折衷考虑网络可靠性提升和网络资源的消耗.

图6 可靠性仿真实验结果
Fig.6 Reliability simulation result

按照3.1节设置参数,用matlab进行蒙特卡罗仿真实验,源节点1 000次发送原始数据包,统计目的节点成功解编码的次数得到传输可靠性,仿真结果如图6(a)和图6(b).仿真实验结果进一步验证了理论分析结果.应用网络编码方式下,仿真实验与理论分析结果比较如图6(c),相同参数设置下,仿真实验中传输可靠性略逊于理论分析结果.我们认为这是因为理论分析时并未考虑目的节点收到的编码数据包的编码之间的线性相关性.仿真实验中,由于有真实的有限域编码参与运算,即使目的节点接收到足够数量的编码数据包,只要对应的编码矩阵不满秩,不可逆,就法通过式(1)完成解编码得到源节点发送的原始数据包.