论文研究-混合分代网络编码的解码时延分析.pdf

所需积分/C币:9 2019-07-22 20:51:45 1.46MB .PDF
收藏 收藏
举报

采用网络编码方式能够有效提高网络的吞吐量,混合分代网络编码通过引入不同代之间的相关性,进一步提高了译码成功的概率,但是混合分代网络编码的计算复杂度和解码时延也相应增加了。在混合分代网络编码中冗余编码包有不同的添加方式,第一种方式是把冗余编码包分散添加到各个分代中,在这种方式中,每个分代的冗余编码包是和各个分代的编码数据包同时生成的,对所有小于它所在分代位置序号的分代有保护作用;第二种方式是把冗余编码包和最后一个分代的编码数据包一起发送,在这种方式中,冗余编码包对所有的分代有保护作用。主要对这两种混合分代网络编码的解码时延进行分析,研究表明第一种方式的解码时延小于第二种方式。
第10期 孟祥镖,等:泥合分代网络编码的解码时延分析 3089 个分代的数据包发送完之后才发送的,所以如果发生数据包丢 P:=P(ho +h1+… k,=(S+1)k) (4) 失的分代位置编号为L,,则此分代在接收端将无法成功接收到 假设g,(0≤s≤m-2)分代在位置编号为s'(s+1≤s'≤ k个解码冋量,从而也就无法成功译码。根据混合分代网终编m-ˆ)的分代数据包接收宄后成功解码.说明在位置编号从s 码的解码机制,位置编号为L的分代如果不能成功解码,则其到丶之冋的所有分代接收到的线性尢关编码数据包数量不足 后的所有分代(囂n-代除外)都尢法成功解吗,必须等到接收而不能够解码,并且位置编号为s'的分代接收到了足够多的线 端接收完ε灬-代及冗余编码包后,利用ε-代及冗余编码包性无关编码数据包并能成功解码,则这种情况的概率为 信息来帮助混合分代中未能成功解码的数据包进行解码。这 P,+1s≤n-2=P(l+k1+…-k,=(s2+1)h)x 种编码方式中,只要有一个分代(gn-1代除外)发生数据包丢 ∏P(k+k1+…+k,+-1<(s+i)k) 失,其后所有分代(gn-1代除外)的解码时延都大幅度增加。 在分布式冗余编码包添加方式中,冗余编码包是与每个分 当g(0≤s≤m-1)分代在最后一个分代之前都没能成功 解码时,则此时g.分代无论是否能够成功解码都要等到最后 代编码数据包一同形成的,并在每个分代发送完编码数据包后 发送的。如果在位置编号为L的分代中,接收端能够在有数 一个分代数据包接收并处理完成后才能确定。这种情况发生 的概率为 据包夭失的情况下成功接收到不少于个线性无关的编码数 据包,那么此分代就可以成功解码;如果接收端在有数据包丢 P=m-1=∏P(k+k1+…+k4+t-1<(s+i)k) 失的情况下接收到的线性无关的编码数据包数量少于k个.那其中;k+k1+…+k表示到第s个分代数据包接收完成时 么此分代就无法成功解码。但是由于位置痂号大于L;的所有接收端接收到的所有分代线性无关的编码数据包数量之和。 分代都会发送冗余编码包,并且都包含有位置编号为L的分并且有 代信息,所以如果在它后面的分代能够接收到足够多的编码数 P(k0+k1+…+k,+-1<(s+i)h)= 据包弥补此代数据包的丢失,位置编号为L;的分代就能够在 1-P(bo+k1+…+k,+-1=(x+i)k) 后面分代的帮助下成功解码。 根据文献[13]中的随机线性网络编码接收端成功解码概 从上面的分析可知,在混合分代网络编码的过程中,解码率(式(12)可知: 时延的产生主要是因为混合分代中位置编号为0到m-1的 P(h0+l1+…+k,+;-1=(s+i)k)= 其中一个分代没能成功接收到足够多的编码数据包而无法解 (1+:(4+1)k ∑、C(1+(,+1(1-P) 码,必须等到后面的分代中冗余编码包成功接收后才能帮助此 1+)(3+)k-xPm(,(s+i)k 分代解码。所以假设混合分代中的每个分代从接收数据包到 其中,由文献13的式(7)可知: 成功解码所需要的单位时间为T,则可知混合分代网络编码中 if K<w 位置编号为(1≤l≤m)的分代成功解码时间应该为xT P,(K, N- ifK≥N 2.1末尾集中冗余编码包添加方式解码时延计算 假设在传输过程中数据包丢失的概率为p,则在末尾集中 由式(4)~(6)就可以推出,分布式冗余编码包添加方式 冗余编码包添加方式的混合分代网络编码中,它的第一个分代中g(0≤≤m-2)分代(不包活最后一个分代)的解码时廷的 解码失败的慨率的计算方法为在传输过程中有至少一个编码期望值为 数据包丢失的概率。公式为 E,(s)=Tx(s+1)×P、+T×∑(i+1) Po=∑C4xp×(1-p)k P,+1≤;≤n-2+T×mxP,=m-1 (9) 对于分布式冗余编码包添加方式中的最后一个分代g 由于在木尾集中冗余编码包添加方式的混合分代树络编 (s=m-1),无论最后一个分代能否成功译码都要把最后一个 码中,位置编号大的分代成功解码的前提条件是位置编号比此分代的编码数据包接收并处理完成,所以最后一个分代的解码 分代小的所有分代都已经成功解码,否则就要等到最后一个分时延为定值: 代的数据包和冗余编码包成功接收后才能解码,所以第个分 E mT (10) 代成功译码的概率为 P1=(1-P0) 2)3仿真与分析 从而可知,末尾集中冗余编码包添加方式的混合分代网络 编码中第Ⅰ个分代的解码时延的期望值为 这一部分主要是利用 MATLAB仿真软件对两种不同几余 E(1)-1×7×P1+mxT×(1-P1) 编码包添加方式的混合分代网络编码方式以及传统分代网络 编码的解码时延进行仿真分析和对比。 22分布式冗余编码包添加方式解码时延计算方法 在仿真中,混合分代网络编码和传统的分代网络编码的总 在分布式冗余编码包添加方式中,对于g,(0≤s≤m-1)分代数都为m=3,每个分代包含的数据包数量都为k=40,随 分代来说,它可能在ξ分代数据包接收完后就能成功解码;如机线性网络编妈的编码系数选取的有限域大小为q=256,冗 果未能成功解码也有一定概率可以在位置编号大于s的后面余度r=0.1,网络编码中每个分代从接收数据包到成功解码 的分代帮助下成功解码。 所需要的单位时间设为T=1。则根据解码时延的定义可知 如果g,(0≤s≤m-2)分代(除去最后一个分代以外)在它由于传统分代网络编码的各个分代之间没有相关性,所以它的 自己分代的编码数据包接收完成后就能成功解码,用k(0≤讠三个分代的解码时延大小均为T,同时利用第二部分推导得出 ≤m-1)表示接收端接收到的位置编号为讠的分代线性无关的解妈吋延公式对数据包丟失率P变化吋,两种不同冗余编码 编码数据包数量,则这种情况发生的概率为 包添加方式中混合分代网络编码的go、31、2分代的解码时延 3090· 计算机应用研究 第32卷 以及传统分代网络编码的εω、1、2分代解码时延进行对比。码相比,前者各个分代的解码时延值都明显大于后者。从文献 仿真结果如图4~6所小。 7]可知,混合分代网络编码相比传统分代网络编码方式的优 签35岳三 集中添加力式 势就是通过引人各个分代之间的相关性从而提高了成功译码 率;但是从解码时延的对比可知,前者引入各个分代的相关性 25 的同时,它的解码时延也随之增大了。从而可知,混合分代网 络编码方式成功译码率的增大是以解码时延的增大为代价的。 4结束语 0.050.10.150.2 0050.10.1 数据包丢失概率 数据包丢失概率 本文主要针对混合分代网络编码的两种不同冗余编码包 图4当m=3,k=40,g=256时 图5当m=3,k=40,g=256时, 添加方式以及传统分代网络编码的解码时延进行对比和分析。 g代的解码吋延随丟失概率Pg代的解码吋延随丢失概率p 的变化情况 的变化情况 经过本文的计算和仿真可知,混合分代网络编码与传统分代网 络编码相比,前者各个分代的解码时延都明显高于后者,从而 结套吗方式 也可知,混合分代网络编码方式成功译码率的增大是以解码时 延的増大为代价的。此外,对混合分代网终编码来说,分布式 冗余编码包添加方式相比于尾部集中式冗余编码包添加方式 虽然成功译码率小,但是它的解码时延也更小,增长曲线更加 平滑,与传统分代网络编码方式的解码时延也更接近;此外,在 0.050.10.150.20.250.3 其他条件都相同的情况下对两种冗余编码包添加方式的解码 数据包丢失慨率p 时延进行比较可知,位置编号越小的分代中两种冗余添加方式 图6当m=3k=40,g=256时g2代的解码时延随丢失概率p的变化情况 从图4和5可以发现,混合分代网路编码与传统分代网络的解码时延之差越大 编码相比,前者的解码时延明显大于后者;此外,对于混合分代参考文献 网络编码来说,分布式冗余编码包添加方式与尾部集中式冗余1] Ahlswede r, Cai ning,LiSY,al. Network information flow[J 编码包添加方式相比,前者的解码时延更小,增长由线更加平 IEEE Trans on Information Theory, 2000, 46(4): 1204-1216 滑,而且与传统分代网络编码的解码时延值更接近。同时混合[2 Yeung R W. A first cource in information theory M].[S.1.] 分代网络编码方式的两种不同冗余编码包添加方式的解码吋 Springer, 2002: 434 延之差随着数据包夭失率的增大而增大,增大到定程度后又13: Yeung w. Information theory and network coding[M]. [S.1.] Springer, 2008: 3409 开始减小,最终当数据包丢失率达到一定值以后两者的解码时 [4 Ford LR, Fulkerson DR. Maximal flow through a network J. Ca 延都达到相同的最人时延值。产生这种现象的原因是分布式 nadian Journal of mathematics 1 956.8. 399-404 冗余瘺码包添加方式中,冗余编码包是添加在各个分代中的,「5枥林,郑羽,胡晓惠冈络編码研究进展「1.计算机研究与发展, 当数据包丟失率较低时,通过本代的几余编码包或者本代后面 2008,45(3):400-407 的某一个或者几个分代的冗余编码包的帮助就可以成功解码 [6 Halloush M, Radha H. Performance evaluation: priority transmission 但是随着数据包夭失率的增加,当各个分代的冗余编码包无法 using network coding with multi-generation mixing[ C]//Proc of the 补偿丢失的数据包时,分代的解码时延就会不断增加并最后趋 43rd Annual Conference on Information Sciences and SystemsIS 向于最大的时延值;而在尾部集中式冗余编码包添加方式中 1.]: IEEE Press,2009424-429 由于冗余编码包都被添加在最后一个分代中,所以对于除去最7 alloush m, Radha i. Network coding with multi-generation mixing 后一个分代的所有分代来讲,只要有一个分代发生数据包的丢 [Cl//Proc of the 42nd Annual Conference on Information Science 失,则从此分代以后的所有分代都将无法成功译码,只能等到 and Systems [S.1. ]: IEEE Press, 2008:515-520 最后一个分代的帮忙,所以这种方式在数据包丢失率很小时开[8. Liu rui, Hc Jianjun, uo Yijun. An improved mcthod of multi-gcn 始,分代的解码时延就已经很人,随着数据包丟失率的增加,各 ration mixing network coding[ C]//Proc of World Congress on Info 个分代的解码时延迅速趋近于最大时延值。由图4与5对比 nation and Communication Technologics. [S. 1. 1: IEEE Prcss, 2012 还可以发现,数据包丢失率相同的情况下,位置编号越小的分 1086-1091 代中两种冗余添加方式的解码时廷之差越大。主要原因是在9. Burton. An introduction to eror correcting codes[. EEE Trans 两种方式中,当数据包丢失率达到定值时,各个分代的解码 on Communications, 1973, 21(1): 83-84 时延都趋近于相同的最大值,而位置编号越大的分代解码时延 [10 Li S Y, Yeung R W, Cai Ning. L inear network coding[J].IEEE Trans on Information Theory, 2003, 49(2): 371-381 就越大,所以位置编号越大的分代两种添加方式的解码时延差 [1]周伟伟线性网络编码研究_J].通信技术,2008,41(2):97-99 值也就越小。 12]Halloush M, Radha H. A casc study of: scndcr transmission rcliabili 由图6可以看出,对于混合分代网络编码最后一个分代 ty and complexity using network coding with multi-generation mixing 两种冗余编码包添加方式的解码时延是相等的一个定值,与数 [C]//Proc of the 43rd Annual Conference on Information Sciences 据包丢失率无关,只与混合分代的分代数m有关。这是因为 and Systems. [ S.I.I: IEEE Press, 2009: 430-435 对于最后一个分代来讲,无论解码成功与否它的后面已经没有[13] Tullos- Cruces o, Barcelo- Ordinas M, Fiore m. Exact decodin 其他分代,解码时延就是木代的解码时延,与其他分代无关。 robability under random linear network coding[ J]. IEEE Communi 由图4~6可以看出混合分代网络编码与传统分代网终编 cation Letters, 2011, 15(1): 67-69

...展开详情
试读 4P 论文研究-混合分代网络编码的解码时延分析.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-混合分代网络编码的解码时延分析.pdf 9积分/C币 立即下载
    1/4
    论文研究-混合分代网络编码的解码时延分析.pdf第1页
    论文研究-混合分代网络编码的解码时延分析.pdf第2页

    试读已结束,剩余2页未读...

    9积分/C币 立即下载 >