介绍一种基于滑动窗口的网络编码方法

本站提供的介绍一种基于滑动窗口的网络编码方法,是因为有小编给大家分享的

本站提供的介绍一种基于滑动窗口的网络编码方法,是因为有小编给大家分享的

一种基于滑动窗口的网络编码方法

[0001 ]本发明属于网络编码技术领域,更具体地,涉及一种基于滑动窗口的网络编码方 法。

[0002] 在提高无线网络的传输效率和延长网络寿命上,专家学者不断研究更加有效的交 换理论供路由器使用。2000年,香港中文大学的几位教授(R.Ahlswede,蔡宁,李硕彦和杨伟 豪)在其著名论文 "Network Information Flow"(R· Ahlswede,N· Cai,S · - Y· R· Li,and R.ff.Yeung.Network information flow. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216)中创造性地提出了"网络编码(Network Coding,NC)"新概念,首次 将编码与路由技术有机地融合为一体,建立了一种全新的网络体系结构,不仅解决了广播 路由这一信息论中的经典难题,而且从理论上证明了网络编码可以达到最大传输容量和效 率,其精髓来自于图论中著名的Max-flow Min-cut理论。
[0003] 2003年,李硕彦、杨伟豪和蔡宁(S.-Y.R.Li,R.W.Yeung,N.Cai .Linear network coding. IEEE Transactions on Information Theory,2003,49(2) :371 ~381)又发表了著 名论文"Linear Network Coding",指出线性网络编码可以达到多播传输的最大容量。随后 的研究成果构建了网络编码的最基本框架,从此网络编码成为了世界各知名大学和实验室 最热门的研究领域之一。在现有技术中提出了多种网络编码方法,这几种方法主要应用于 无线网络、网络路由技术、协作通信以及数据压缩等方法中,较好地提高了网络的数据传输 率和可靠性。
[0004] Ebrahimi等(J.B.Ebrahimi,C.Fragouli.Algebraic Algorithms for Vector Network Coding.IEEE Transactions on Information Theory,2011,57(2):996~1007) 提出了一个基于向量和标量的网络编码代数构造算法,从而在降低算法复杂性的同时,较 好地提高了网络编码的性能。了&11等(]\1.1311,1?.1¥6111^,3.11-1'.!1〇,1〇3;[.厶1]11丨;1^6(1 Framework for Linear Network Coding.IEEE Transactions on Information Theory, 2011,57(1):416~423)通过对全局编码核中的线性独立性基本原理进行了深入研究,证明 了线性网络编码存在的必要条件是线性网络编码满足一定的独立性的要求。宋小全等(宋 小全,胡鹏,孙旭.基于局部重传和网络编码的可靠性传输机制.北京邮电大学学报,2014, 37(4) :54-58)提出了一种面向无线Ad hoc网络应用的基于局部重传和网络编码的多路径 路由可靠性传输机制。
[0005] 任智等(任智,郑爱利等.基于滑动窗口的连续无线网络编码.计算机应用,2011, 31(9) :2321-2324)提出一种基于滑动窗口的网络编码方案,在待重传数据分组矩阵中设计 一个按时间顺序滑动的编码窗口并在其中选择参与网络编码的分组,同时保证编码分组的 可解性,从而减少数据分组的重传次数和传送时延。孙杰英在硕士学位论文中对基于滑动 窗口的随机线性网络编码进行了研究(孙杰英.基于滑动窗口的随机线性网络编码研究.中 南大学,2012)。研究表明滑动窗口大小和滑动步调大小对基于滑动窗口的随机线性网络编 码产生重要的影响。何明等(何明,裘杭萍等.基于滑动窗口技术的网络节点对可靠性评估. 解放军理工大学学报(自然科学版),2009,10(3) :269-272)使用基于滑动窗口技术的递归 算法,滑动窗口由数个连续节点构成,窗口向前滑动一个节点,此过程重复,直至窗口到达 最后的节点,此时的连通概率即可计算网络系统的节点对可靠性。
[0006] 现有的技术研究主要集中于网络编码在一些相关领域中的应用;而在基于滑动窗 口的网络编码机制中,针对不同的网络编码机制,缺少对滑动窗口大小、滑动步调大小等较 强的理论支持。当网络出现丢包时,会使后面的一系列编码分组均解码失败,从而导致目的 节点需要缓存的编码分组大大增加,因此如何确定滑动窗口大小,并仅对已确定的滑动窗 口内的数据分组进行编码,对解码系数矩阵的规模及解码的复杂度都会产生较大影响。



[0007] 针对现在技术的存在的缺陷和问题,本发明的目的在于提供一种基于滑动窗口的 网络编码方法,只对进入滑动窗口内的数据分组进行编码操作,减少了网络编/解码操作的 复杂性和计算时间,在实现快速网络编码的同时,提高了编解码效率,从而使网络数据吞吐 量最大化,延长了网络生存期。
[0008] 为实现上述目的,本发明提出了一种基于滑动窗口的网络编码方法,其特征在于, 所述方法包括:
[0009] (1)确定待发送的数据分组数量N,以及滑动窗口的大小W;
[0010] (2)源节点按照已确定的滑动窗口大小对待发送数据分组进行编码操作,具体包 括:
[0011] (2-1)源节点确定待发送数据分组1=(1〇^1,一4^1),生成一组对应的编码向量 g,g=(g〇,gi,···,gN-1),编码向量元素 gjGGF(2n),其中 j = 0,l,···,N-1,同时确定滑动窗口 大小为W;
[0012] (2-2)按照随机线性编码对第i个滑动窗口内的数据分组(Xf,Xf+1,…,x e)进行编 码,得到第i个编码后数据分组又户財时財+出#…+geXe,其中,f为滑动窗口开始值,e为滑 动窗口结束值,〇<f〈e<N-l;
[0013] (2-3)源节点将第i个编码后数据分组yi与滑动窗口对应的编码向量gkU'gf +1,"_,ge)进行组合,得到对应的第i个编码分组PKgSy!)并将其发送至下一跳中间节点;
[0014] (3)中间节点对接收的编码分组进行再编码并传输;
[0015] (4)目的节点利用交换高斯消去法对接收到的编码分组进行解码;
[0016] (5)当源节点传输数据结束后,执行步骤(6);否则,转步骤(2)继续处理下一个数 据分组;
[0017] (6)目的节点对解码后的数据分组进行恢复。
[0018] 作为进一步优选的,所述滑动窗口大小W = e-f+l,f为滑动窗口开始值,e为滑动窗 口结束值,对于数据分组X = (xq,XI,…,xN-i),滑动窗口数为Ν-W+l。
[0019] 作为进一步优选的,其特征在于,所述滑动窗口开始值f服从下列分布:
[0020] m
ο
[0021] 作为进一步优选的,所述步骤(3)具体为:中间节点接收到k个编码分组(Pt^g*3, 7〇),?1(8 1,71),"办-1(81"1,5^-1))后,生成对应的随机编码向量〇 = (〇〇,(:1,",〇{-1),,编码 向量元素cj£GF(2n),j = 0,1,…,k-Ι,且编码向量元素cj为1的概率P{cj = l} = 1/2,同样 的,按照随机线性编码,得到再编码后数据分组yricoyo+dy#…+0^71^及对应的编码向量 gkcOghdgkH+Ck-lgk-S重新组合得到新的编码分组PrWjr)并发送。
[0022] 作为进一步优选的,所述步骤(4)具体包括两个阶段:
[0023] (4-1)对接收到的编码分组的编码向量利用三角化过程变换得到上三角窗口矩 阵;
[0024] (4-2)当N个线性无关的编码分组被接收到时,则所述上三角窗口矩阵的秩等于N, 目的节点通过对角化过程对上述接收到的N个线性无关的编码分组进行解码。
[0025]作为进一步优选的,所述步骤(4-2)可通过迭代XOR操作实现。
[0026] 总体而言,通过本发明所构思的以上技术方案与现有技术相比,主要具备以下的 技术优点:
[0027] 1)本发明采用了基于滑动窗口的网络编码方法,无需对所有数据分组进行编码, 只对进入滑动窗口内的数据分组进行编码操作,从而减少了编码的复杂性;
[0028] (2)本发明基于滑动窗口的网络编码方法中,采用包括三角化和对角化两个阶段 的交换高斯消去法对接收的编码分组进行解码,使得解码系数矩阵的规模进一步减小,从 而进一步降低了解码过程的复杂性,大大提高了解码效率。

[0029] 图1是本发明基于滑动窗口的网络编码方法流程图;
[0030] 图2是本发明实施例中数据分组N=8和滑动窗口 W=3的示意图;
[0031]图3是无线网络编码传输不意图。

[0032]为了使本发明的目的、技术方案及优点更加清楚明白,以下结合附图及实施例,对 本发明进行进一步详细说明。应当理解,此处所描述的具体实施例仅仅用以解释本发明,并 不用于限定本发明。此外,下面所描述的本发明各个实施方式中所涉及到的技术特征只要 彼此之间未构成冲突就可以相互组合。
[0033] 如图1所示,本发明提供了一种基于滑动窗口的网络编码方法,包括如下步骤:
[0034] (1)确定待发送的数据分组数量,以及滑动窗口的大小;
[0035] 无线网络可以表示成一个无向图G=(V,E),其中V表示网络中的节点集,这些节点 随机地分布于一个矩形区域内,E表示两个节点之间可以通信的边集,GF(2 n)表示在G中的 有限域。
[0036] 数据分组是在无向图G中的源节点产生,编码操作是在G中的有限域GF(2n)中进 行。若源节点确定待发送数据分组X,数据分组X中包含N个元素,可表示为:X = ( XQ,XI,…, 1^1),同时,源节点生成一组随机向量,即编码向量8 4=(8(),81,"_撕-1)必^?(211)。
[0037] 根据待发送的数据分组确定滑动窗口的大小。考虑数据分组X=(XQ,X1,…, XN-〇和 编码向量g = (go,gi,…,gN-i),定义滑动窗口大小W=e-f+1,f为滑动窗口开始值,e为滑动窗 口结束值,,对于数据分组X中的N个元素,可能有Ν-W+l个滑动窗口 >则落入窗口内的编 码向量为(gf,"_,ge)。如图2所示为数据分组N=8和滑动窗口 W=3的举例。数据分组N=8,滑 动窗口值W = 3,则有N-W+l = 6个滑动窗口,即wf)。考虑两个相邻窗口妒丨1和 ? · · · 9 IV. W f2 2 f1。如果与重叠,则有f2 < e1,并且f1 < f2 < e1。因此,确定滑动窗□开始值 与结束值的条件为:〇 < f <e < N-ι。
[0038] (2)源节点按照已确定的滑动窗口大小对待发送数据分组进行编码操作,具体包 括:
[0039] (2-1)源节点确定待发送数据分组1=(1〇41,"_4〃-1),生成一组对应的编码向量 g,g=(g〇,gi,···,gN-1),编码向量元素 gjGGF(2n),其中 j = 0,l,···,N-1,同时确定滑动窗口 大小为W;
[0040]其中,滑动窗口开始值f服从下列分布:
[0041] (1)
[0042] PDN,w(f)在保证数据分组内的每个元素进行编码的同时,进一步提高了解码的 效率。用s和t表示g的第一个和最后一个非零元素的位置,有:gs = gt=l和gj = 0,对任何j〈s 和 j>t。
[0043] (2-2)按照随机线性编码对第i个滑动窗口内的数据分组(Xf,Xf+1,…,x e)进行编 码,得到第i个编码后数据分组又户財时財+出#…+geXe,其中,f为滑动窗口开始值,e为滑 动窗口结束值,〇<f〈e<N-l;
[0044] (2-3)源节点将第i个编码后数据分组yi与滑动窗口对应的编码向量 +1,"_,ge)进行组合,得到对应的第i个编码分组PKgSy!)并将其发送至下一跳中间节点;
[0045] 其中,编码分组的度可用d表示,其度分布Ω可以表示为:Ω d = P{ | | g | 11 = (1},Ω为 二项分布。其中11g111表不g的范式。
[0046] 称Pi(gi,yi)是一个滑动窗口码(Sliding Window Packet,SWP),在滑动窗口开始 值f,如果& [/>],有gi = 〇;如果i e [f,e ],编码向量为1的概率P{gi = 1} = 1/2。
[0047] 令?1(81,71)和?2(82,72)表示两个滑动窗口码31?0,1 1)和31?0,12)的分组,如果 滑动窗口 rj4和rw{2重叠,则分组P,.(备,j.Y)=Pi ? A是一个swp(n,wr)的分组,并且滑动窗口 的大小是f <炉+妒。可以得到:如果w1=w2=w和fi=f2,则F=w。
[0048] (3)中间节点对接收的编码分组进行再编码并传输;
[0049] 对于中间节点,当其接收至Ijk个编码分组(Po(gQ,y()) ,ΡιΜ,γι),…,Pk-i(gk-^yk-1)) 后,生成对应的随机编码向量C = (CQ,C1,···,ck-i),,编码向量元素 CjEGF(2n),j = 0,1,…, k-1,且编码向量元素为1的概率P{Cj = l} = l/2,同样的,按照随机线性编码,得到再编码 后数据分组 yr = coyo+ciyi+'"+ck-iyk-1 及对应的编码向量 gkcoga+cig1-···+〇<-lgk-1,重新组 合得到新的编码分组Pr (gt,yr)并发送。
[0050] (4)目的节点对接收到的编码分组进行解码操作;
[0051] 在解码过程中,假设节点接收到N个编码分组,根据GX = Y计算NXN线性组合编码 矩阵G,Gi表示G的行向量,Gi,j表示G的i行j列的元素,Y是NX 1线性组合编码向量,X是NX 1 包含符号^的向量。分组解码过程采用交换高斯消去法,包括三角化和对角化两个阶段: [0052] (4-1)对接收到的编码分组的编码向量利用三角化过程变换得到上三角窗口矩 阵;上述三角化过程增加了组合解码的概率,降低了解码复杂度。
[0053] (4-2)当N个线性无关的编码分组被接收到时,则所述上三角窗口矩阵的秩等于N, 目的节点通过对角化过程对上述接收到的N个线性无关的编码分组进行解码。矩阵的对角 化可以通过迭代X0R操作实现。
[0054]如下对三角化及对角化解码过程的复杂性进行分析。用DC表示解码的复杂性,目 的节点接收分组P(g,y),根据交换高斯消去法、X0R操作和滑动窗口的大小W可知,假设rank (G)〈k,当k+1个分组接收时,编码向量矩阵G的行冲突是k,g的度是W/2,接收k+1个分组的平 均冲突为kW/2N,则三角化解码的复杂性为:
[0055]
[0056] 编码向量矩阵G为上三角窗口矩阵,窗口大小为W,则G中包括N2-(N-1 )2/2-(N-W)2/ 2个非零元素,则对角化过程的解码复杂性为:
[0057]
-L Z: 呼
[0058]最后,可得本发明基于滑动窗口的网络编码的解码复杂性为:
[0059]
[0060] 也就是说,本发明方法的解码复杂性为0(NW),或0(N2)。
[0061] (5)当数据分组传输结束后,执行步骤(6);否则转步骤(2)继续处理下一个数据分 组;
[0062] (6)目的节点对解码后的数据分组进行恢复。
[0063] 由于是通过滑动窗口进行网络编码的,所以每个节点接收到的数据分组解码后会 有重复部分,对重复的数据进行拼接,得到原始数据分组。
[0064] 如图3所示为无线网络编码传输示意图,无线节点A及B为源节点,无线节点C及D为 目的节点,无线节点S为中间节点,即编码节点,也就是说,根据本发明提出的网络编码方 法,无线节点A对滑动窗口内的数据分组进行编码操作得到编码分组1并发送至S,同样地, 无线节点B对滑动窗口内的数据分组进行编码操作得到编码分组2并发送至S,当无线节点S 接收到编码分组1和编码分组2后,经再编码后得到分组1 ? 2,并将其发送至无线节点C和D, 那么无线节点C和D即可通过接收到的编码分组对原始数据分组进行恢复。
[0065]本领域的技术人员容易理解,以上所述仅为本发明的较佳实施例而已,并不用以 限制本发明,凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等,均应包含 在本发明的保护范围之内。

1. 一种基于滑动窗口的网络编码方法,其特征在于,所述方法包括: (1) 确定待发送的数据分组数量N,W及滑动窗口的大小W; (2) 源节点按照已确定的滑动窗口大小对待发送数据分组进行编码操作,具体包括: (2-1)源节点确定待发送数据分组X=(X0,X1,…,XN-1),生成一组对应的编码向量g,g = (g〇,gi,…,gN-i),编码向量元素 gjEGFUn),其中j = 〇,l,…,N-1,同时确定滑动窗口大小为 W; (2-2)按照随机线性编码对第i个滑动窗口内的数据分组(Xf,Xf + l,…,Xe)进行编码,得 到第i个编码后数据分组yi = gfXf+gf+lXW+…+geXe,其中,f为滑动窗口开始值,e为滑动窗口 结束值,〇<f<e<N-l; (2-3)源节点将第i个编码后数据分组yi与滑动窗口对应的编码向量gi=(gf,gf+i,…, ge)进行组合,得到对应的第i个编码分组Pi(gi,yi)并将其发送至下一跳中间节点; (3) 中间节点对接收的编码分组进行再编码并传输; (4) 目的节点利用交换高斯消去法对接收到的编码分组进行解码; (5) 当源节点传输数据结束后,执行步骤(6);否则,转步骤(2)继续处理下一个数据分 组; (6) 目的节点对解码后的数据分组进行恢复。2. 如权利要求1所述的方法,其特征在于,所述滑动窗口大小W = e-f+l,f为滑动窗口开 始值,e为滑动窗口结束值,对于数据分组X = (XO,Xi,…,XN-I),滑动窗口数为N-W+1。3. 如权利要求1或2所述的方法,其特征在于,所述滑动窗口开始值巧g从下列分布:4. 如权利要求1所述的方法,其特征在于,所述步骤(3)具体为:中间节点接收到k个编 码分组(Po(yo),Pi(gi,yi),…,Pk-I (gk-i,yk-i))后,生成对应的随机编码向量〇 = (CO, Cl,...,ck-i),,编码向量元素 CjEGFU。),j = 〇,l,k-l,且编码向量元素 Cj为1的概率Pkj =^ = 1/2,同样的,按照随机线性编码,得到再编码后数据分组7,=圳7日+(3巧1+-+〇^-巧1<-成 对应的编码向量gt = C0g%31gl+-+Ck-lgW,重新组合得到新的编码分组Pr(gT,yr)并发送。5. 如权利要求1所述的方法,其特征在于,所述步骤(4)具体包括两个阶段: (4-1)对接收到的编码分组的编码向量利用S角化过程变换得到上S角窗口矩阵; (4-2)当N个线性无关的编码分组被接收到时,则所述上S角窗口矩阵的秩等于N,目的 节点通过对角化过程对上述接收到的N个线性无关的编码分组进行解码。6. 如权利要求5所述的方法,其特征在于,所述步骤(4-2)通过迭代XOR操作实现。
本发明公开了一种基于滑动窗口的网络编码方法,所述方法包括:首先,确定待发送的数据分组数量N,以及滑动窗口的大小W;源节点按照已确定的滑动窗口大小对待发送数据分组进行编码操作,中间节点对接收的编码分组进行再编码并传输;最后,目的节点利用交换高斯消去法对接收到的编码分组进行解码,并对解码后的数据分组进行恢复。本发明通过确定滑动窗口大小,并仅对滑动窗口内的数据分组进行编码,进一步提高了网络编码的可靠性,显著降低了解码复杂性,在实现快速网络编码的同时,从而使网络的数据吞吐量最大化,大大延长了网络生存期。
H04L1/00
CN105515728
CN201510824717
孙宝林, 桂超, 宋莺, 肖琨, 李红艳, 鲁晓成
湖北经济学院
2016年4月20日
2015年11月24日

介绍一种基于滑动窗口的网络编码方法的相关内容如下:

标题:介绍一种基于滑动窗口的网络编码方法|http://www.bailuda.cn/new-252960.html

本文来自网络,不代表本站立场,转载请注明出处!