《随机线性网络编码的一种差错控制方法.doc》由会员分享，可在线阅读，更多相关《随机线性网络编码的一种差错控制方法.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、随机线性网络编码的一种差错控制方法蒲保兴1，2，杨路明1，王伟平11(中南大学 信息科学与工程学院，湖南 长沙，)2(邵阳学院 信息工程系，湖南 邵阳，)E-mail ：pubook摘要:针对随机线性网络编码，提出了点-点检错和端-端重传相结合的差错控制方法。借助于随机线性网络编码的鲁棒性，对信道的突发性错误和随机错误，采用三维奇偶校验码进行检错，让有错的数据包不参与编码；当宿点不能解出源点播出的信息时，通过反馈重传策略让源点重传信息。理论分析和仿真测试结果表明，在伽罗华域较大且数据包较长时，提出的方法能以较大的概率消除信道的传输错误，并解决了全局编码向量出错的问题，且以较低的重传率实现宿点完
2、整地接收源点的信息。关键字：随机线性网络编码;差错控制;三维奇偶校验码；重传中图分类号：TN711 文献标识码：A 文章编号：An Error Control Approach of Random Linear Network CodingPU Bao-xing1，2,YANG Lu-ming1,WANG Wei-ping1 1( School of Information Science and Engineering, Central South University, Changsha , China)2( Department of Information Engineering, S
3、haoyang College, Shaoyang ,Hunan,China)Abstract：Aiming at random linear network coding, this paper proposes an error control method which combines point-point checking error and end-end retransmission. By virtue of the robustness of random linear network coding, this method adopts three dimensional
4、parity checking code to implement point-point checking error, and let erroneous packets not take part in coding. When a sink node can not decode the information coming from source node, it transmits feedback information to source node to request retransmission. Theoretical analysis and simulation re
5、sults show that, by using larger Galois field and larger packet, the proposed method has high probability to eliminate transmission error including global network coding vertexes error, and make sink nodes integrally receive information from source node at lower retransmission rate.Key words: random
6、 linear network coding; error control; three dimensional parity-check code; retransmission1 引言网络编码1-5是一种新型的数据传输技术，它能实现单源组播网络的最大数据传输速率(组播容量)。网络编码的差错控制研究引起了人们的关注，文献6,7基于端-端的前向纠错思想对网络编码的差错控制进行了理论研究，把传统的海明界，Singleton界和Gilbert-Varshamov界推广到了网络编码的前向纠错机制中。如Singleton界指明只能以不超过C-2K(C为组播容量，K为出错信道数)的数据传输速率实现端-端
7、的前向纠错。在实际应用中，源点很难获知网络的全局网络拓扑知识，采用随机线性网络编码5是唯一的选择，文献8-9基于端-端的前向纠错机制分别给出了随机线性网络编码的差错控制方法，但必须满足Singleton界，并只考虑传输的信息出错，而假定信道上传输的全局编码向量是无错的，除此之外，还要求宿点能获知出错模式:即那些信道有错误，宿点解码的运算量较大，从而实用性较差。事实上，由于随机线性网络编码技术在数据传输过程中要传输全局编码向量，无论是信道的突发性错误还是随机错误，不仅会造成传输的信息出错，还会造成全局编码向量出错；此外因节点产生局部编码向量的随机性，宿点不能解码的概率大于零。为了使宿点能正确、完
8、整地接收源点的信息，必须采用更有效的差错控制方法。本文为随机线性网络编码提出了一种新型差错控制方法，借助于随机网络编码的鲁棒性, 采用点-点检错和端-端重传相结合的策略。点-点的检错运用三维奇偶校验码实现，并让有错的数据包不参与编码，当宿点不能解码时，发送反馈信号至源点，要求源点重传信息。分析表明，当采用的伽罗华域较大且数据包较长时，该方法能以较大的概率消除了信道的传输错误，以较小的重传率实现宿点完整地接收源点的信息，且源点和宿点均不需要了解全局网络拓扑知识，并有效地解决了全局编码向量的出错问题；与已有方法相比，本文方法具有简单的特点，能适应出错信道较多的情况，提高了网络的吞吐率，仿真测试结果
9、验证了这一结论，表明提出的方法是有效的。2 相关知识与假设我们按文献3来介绍线性网络编码的相关概念和术语。假设一个单源组播网络用有向无环图G=(V，E)来表示，其中V为网络中的节点集，设s是源点，T为宿点集，E为有向边集，有向边e=(u,v)表示节点u至节点v之间的有向信道，节点u称为e的尾，记为u=tail(e);节点v称为e的头，记为v=head(e),e既是节点u的输出信道，又是节点v的输入信道，信道的容量为1，若存在容量大于1的链路，应把它分成多条信道。节点v的输入信道集记为In(v)=d:head(d=v)，输出信道集记为Out(v)=e:tail(e)=v。信道传输以数据包为单位，
10、数据包由若干字符构成，而编码和解码以字符为单位。选定一个有限域GF(2m)，设源点的数据传输速率(简称组播率)为h，在源点，信息流被划分成h等分，每等分恰好是GF(2m)上的一个字符，分别记为。节点输出信道传输的字符是该节点所有输入字符的线性组合，信道e传输的字符记为y(e)，则由式(1)计算： (1)md,e是GF(2m)上的一个系数，这些系数的组合构成信道e的局部编码向量，记为m(e)。信道e传输的字符还可以表示成的线性组合，记为： (2)其中称为信道e的全局编码向量，且下式成立。 (3)由式(2)，每一信道的全局编码向量和传输的字符形成了一个关于y1,y2,yh的线性方程，宿点r(rT)
11、从输入信道接收信息后，得到了一个关于的解码方程组。只有当该方程组的系数矩阵的秩为h时，才能恢复出源点播出的信息。文献5提出了随机线性网络编码：在数据传输过程中，编码节点为输出信道随机产生局部编码向量，由于其随机性，宿点不能解码的概率大于零。假设宿点存在至源点的反馈路径，可以通过反馈路径向源点传送反馈重传信息；假设在实现数据传输任务的过程中，网络拓扑不会发生变化。3 基于随机网络编码的差错控制方法3.1 网络编码对信道错误的敏感性信道错误一般包括突发性错误与随机错误，网络编码对信道错误极为敏感。由信道出错引起传输的数据包出错，成为有错包，当这个有错包流入某节点时，由式(1)和式(3)，则该节点所
12、有的输出数据包均被污染而变成有错包，这样错误信息不断地扩散一直到宿点。设信道e的数据包有错，只要存在自节点head(e)至宿点的路径，则该宿点必定收到有错包。图1 单源组播网络Fig.1 Single source multicast network如图1所示，当节点7至节点12的链路出错，则节点12的所有输出信道的数据包将会出错，以此类推，则只要自节点12至宿点存在有向路径，则这些宿点将收到有错包。其次，宿点只要收到有错包，无论是全局编码向量出错还是字符出错，则解码方程组中含有错误的方程，造成方程组要么不能求解，要么解出的信息是完全错误的。因此网络编码不同于路由传输，对信道的出错非常敏感，某
13、一信道上的数据包的出错可能会导致部分或全部宿点不能解出信息或解出的信息是完全错误的。因此，及时消除信道的传输错误，使之不会漫延至网络，是很有必要的。3.2 三维奇偶校验码为提高检错率，我们把行列奇偶校验码的推广到三维奇偶校验码，三维奇偶校验码构造如下:把数据信息构成一个三维的立方体，奇偶校验位于立方体的三个相邻表面，如图2所示。图2 三维奇偶校验码Fig.2 Three dimensional parity checking code设信息位构成一个长、宽、高分别为a，b，c的立方体，信息位记为x(i,j,k)(1ia,1jb,1kc)，则加上校验位后构成一个长、宽、高分别为a+1,b+1,c
14、+1的立方体，其中x(0,j,k),x(i,0,k),x(i,j,0)为校验位。校验方程如式(4)所示，其中：0ia+1,0jb+1,0kc+1。 (4)对于三维奇偶校验码，信息位数为U=abc，总的位数为N=(a+1)(b+1)(c+1)，则编码效率为： (5)无论生成校验位还是进行校验检验，其运算时间复杂度均为O(N)。称发生错误而不能检测出的概率为误检率。三维奇偶校验码不能检测的错误是：8个信息位同时出错，且分别位于某个立方体的各顶点上，所有不能检测的错误均具有这种形式。所有8个信息位同时出错的组合数为,而8个出错的信息位分别位于某个立方体的顶点上的组合数为：，从而8位错的误检率为： (
15、6)表1是取a=b=c时，8位错误的误检率和编码效率。表1 编码效率与8位错误的误检率Table 1 Coding efficiency and the false detecting rate of 8-bit errora(bit)编码效率（%）8位错误的误检率451.28.50E-10557.83.27E-11662.92.11E-12766.91.98E-13870.22.45E-14972.93.77E-15由表1，随着立方体的增大，编码效率提高，8位错的误检率减小。而三维奇偶校验码的整体误检率必定小于8位错的误检率，因而当数据包较大时，误检率相当地低，可以认为误检率接近于0。与行列
16、奇偶校检码相同，它不仅能检测突发性错误，还能检测随机错误。3.3 差错控制方法由文献3所述，在实际应用中，采用随机线性网络编码，数据传输是分批进行的，每一批传输一个字符块，设采用的组播率为h，在源点每批播出hL个字符，则每一信道将传输L个字符，这L个字符共用该信道的全局编码向量和局部编码向量。信道上传输的数据包格式如图3(a)所示，其中信息部分包括全局编码向量和字符块，其长度为(L+h)m比特。对数据包的信息部分(全局编码向量与字符块)加上三维奇偶校验码，形成带校验的数据包，如图3(b)所示。 图3 数据包的格式Fig.3 Data packet format选择立方体的长、宽、高分别为a，b
17、，c，并满足下述条件: (7) 优化选择是基于下述原因:当a,b,c接近时能使校验位数最小，当数据块的比特数构不成一个立方体时，则要通过添加冗余位凑成一个立方体，但应使添加的位数最小。各节点的操作如下：(a)源点s：选定组播率h，伽罗华域为GF(2m)，数据块的长度为L，把要组播的信息划分为h个字符块，每一个字符块含有L个GF(2m)上的字符。把这些信息保存在缓冲区中，以备重传时调用；对于每一输出信道eOut(s)，随机产生该信道的局部编码向量m(e)，按式(1)、式(3)分别计算输出数据包的字符块和全局编码向量。然后在数据包的尾部添加三维奇偶校验位，形成带校验位的数据包，由信道e传出。(b)
18、中间节点v：对于每一中间节点，接收所有输入信道的数据包，对每一个数据包的所有三维奇偶校验位进行检验，若检测出数据包有错，则把该数据包丢弃，只让无错的输入数据包参与编码。具体操作如下：对于dIn(v)，检验其数据包中的校验位，若有错，置mark(d)=0,否则置mark(d)=1；随机产生每一输出信道的局部编码向量，按式(8)、式(9)分别计算输出数据包的字符块和全局编码向量；在输出数据包的尾部添加三维奇偶校验位，形成带校验位的数据包，由相应的输出信道传出。 (8) (9)(c)宿点：接收所有输入信道的数据包，检测每一个包中的三维奇偶校验位，若检测出有错，则把该数据包丢弃，然后从所有无错的包中析
19、出全局编码向量和信息字符，形成解码方程组，判断系数矩阵的秩是否等于组播率h，若小于h，把接收的无错数据包保存在宿点的缓冲区中，并向源点发出重传信息的请求；若接收的全局编码矩阵的秩等于h，则解出源信息字符，并清除缓冲区。(d)重传处理：若源点收到了宿点的反馈重传请求信息，则以同一组播率重传缓冲区的信息至网络。对于发出反馈重传信息的宿点，把接收到的重传数据包(经过校验后是无错的)与缓冲区中同一批次的数据包联合，从中挑选出h个数据包构成一个线性方程组进行解码，若能解码，则解出源点播出的信息字符，并清除缓冲区，否则，再向源点发出反馈重传请求。4 所提方法的有效性分析定义1：在单源组播网络环境下，假设s
20、为源点，r为宿点，以组播率h采用随机网络编码方法组播数据，若宿点r能解出源点s所播出的信息字符，则称源点s至宿点r连接成功；若源点s至所有宿点均连接成功，则称组播连接成功。定义2：记单源组播网络G=(V,E)，在信道无错的情况下其组播容量为CE，当有K条信道出错，出错的信道集记为EK，并记=（V，E-EK）是由非出错信道构成的一个子图，这个子图仍是一个单源组播网络，其组播容量记为。文献4,5指出，单源组播网络采用随机线性网络编码进行数据传输，在信道无错的条件下且组播率不超过组播容量，当所采用的伽罗华域足够大时，则组播连接不成功的概率可以忽略不计。定理1：所提方法在全体有错包均能检测出时，相当于
21、在单源组播网络=(V，E-EK)上采用随机线性网络编码技术进行数据传输，从而当采用的伽罗华域足够大且组播率不超过子图=(V，E-EK)的组播容量时，则组播连接不成功的概率可以忽略不计。证明：因为全体出错信道的数据包均没有参与编码，且每一输出信道的局部编码向量是随机产生的，相当于在所有无错信道构成的单源组播网络上采用随机线性网络编码方法进行数据传输，这一性质也为称为随机线性网络编码的鲁棒性，再由以下提及到的文献4，5的结论，定理成立。证毕。定理2：若出错的信道数为K，子图的组播容量不低于CE-K。证明：因组播容量为分离源点与所有宿点的最小割的最小值，当有K条信道出错时，移去这些出错信道，则在子图
22、中，源点至每一宿点的最小割中至少有CE-K条无错信道，即组播容量不会低于CE-K。证毕。已有方法8，9必须满足Singleton界，其组播率不能超过CE-2K，而本文方法的组播率可以不低于CE-K，尽管采用本文方法要加上三维奇偶校验码，从表1可以看出，当数据包的长度较大时，编码效率p1较高。在数据包长度相同的条件下，采用本文方法和已有方法，设网络的吞吐率分别为D1和D2，当出错信道数K较大且数据包的长度较大时，由定理2和Singleton界，式(10)成立。 (10)从而与已有方法相比，本文方法提高了网络吞吐率；此外，当2KCE，已有方法不能适用，而本文方法仍然可以，从而本文方法适应范围更广。
23、定理3: 当源点采用随机线性网络编码的方法对同一批信息进行两次数据传输时，宿点可以把两次接收到的方程联立成方程组，以解出源点播出的信息。证明：因传输的是同一批信息，源点播出的字符对应相同，采用相同的组播率，宿点两次收到的全局编码向量均是同一个向量空间的向量，结论显然成立。证毕。当宿点不能解码时，采用这种方法可以提高重传时的解码成功的概率，例如，设组播率为10,假设宿点第一次收到了6个无错的数据包，显然不能解出源点的信息，则要求源点重传，当宿点收到重传的数据包后，经校验有5个无错的数据包，这样两次收到的无错数据包构成了一个系数矩阵为11行、10列的线性方程组，从中选10行使其系数矩阵的秩为10将
24、具有较大的概率。若不采用这种方法，则只能从重传数据包中得到5个方程的线性方程组，从而不能解出源点的信息。此外，本文方法还具有以下特点：因校验位对全局编码向量和字符块均进行了检验，从而本文方法不仅能检测出字符块传输错误，还能检测出全局编码向量的错误；具有简单性和有效性，只需在每一编码器和解码器增加生成校验位和校验位检验的操作，不需要进行复杂的运算，源点和宿点不需要了解全局网络拓扑知识，且运算量分摊到了各个节点。5 仿真测试对如图1所示的单源组播网络进行仿真，实验环境如下：Pentium D CPU 2.8GHz,448M内存。采用Ford-Fulkerson算法10求出组播容量为CE=8。每一批
25、数据传输的参数设置如下：L=100,m=10。按式(7)计算三维奇偶校验码的a,b,c，因数据包的长度较大，则三维奇偶校验码的误检率接近于0。采用本文方法在不同的组播率和出错信道数的环境下进行仿真测试，统计出组播连接成功的概率。让信道随机出错，且出错的信道数为K，在不同的（K，h）环境下分别仿真10000次，所得结果如表2所示。表2 不同环境下组播连接成功率Table 2 Successful multicast connection rate with different condition 0.995 0.999K组播率h8765431.8485.9961.99991112.7225.98
26、52.99991113.6047.9705.9977.9999114.5031.9391.9957.9999115.4213.9116.9932.9998116.3502.8841.9903.9992117.2963.8447.9856.9990118.2522.8067.9762.9972.999819.2012.7595.9664.9976.99991从表2可以看出，选取合适的组播率，可以达到较高的组播连接的成功率，若使组播连接的成功率达到0.995,只要选择“黑线”右边的组播率即可。例如在出错的信道数为4的环境下，采用的组播率不超过6，则重传率不会超过0.005(重传率=1-组播连接成功
27、率)，即在1万次数据传输过程中，只需50次重传，所有宿点就可以完整、正确地接收源点的信息。若选取的组播率不超过5，则重传率不超过0.0001。以下是与已有方法8-9的比较，设h为组播率，P为组播连接成功的概率，D为宿点一次数据传输所接收到的比特数，即一次数据传输时网络的吞吐量，取伽罗域的次m=10，数据包的包头长度为160bit。为了比较的公平性，在相同的环境下进行仿真测试：出错的信道数相同且数据包的长度相等，数据包的包长为9421bit。每种出错环境仿真10000次，对于本文方法，列出重传率不超过0.005的最大组播率，对于端-端前向纠错方法，取最大的组播率，由于随机线性网络编码选取局部编码
28、向量的随机性，对于已有方法同样存在宿点不能解码的情形。仿真测试结果如表3所示。从表中可以看出，当出错信道数较多时，与已有方法相比，本文方法的吞吐率较高，且适应的范围较广。表3 与已有方法的比较Table 3 Comparing with existing methodK本文方法已有方法hPD(bit)hPD (bit)1 70.99615551060.8485573662 60.99994764040.8485383243 60.99774764020.8485192024 60.995747640-5 50.995839750-6 50.999239750-750.999039750-6结束
29、语针对随机线性网络编码，提出了一种基于点-点检错丢包与端-端反馈重传相结合的差错控制方法，与已有方法相比，提出的方法具有简单、有效的特点，源点和宿点均不需要获知全局网络拓扑知识，并解决了全局编码向量出错的问题。分析与仿真测试结果表明，在数据包较长且采用的有限域较大时，提出的方法具有较高的检错率，且以较低的重传率实现宿点完整地接收源点信息。若出错的信道数较多时，与已有方法相比，本文方法可以提高网络的吞吐率且适应的出错范围更广。参考文献：1 Ahlswede R,Cai N,Li S R,et al.Network information flowJ.IEEE Trans on Informati
30、on Theory,2000, 46(4): 1204-1216.2 Li S-Y R,Yeung R W,Cai N.Linear network coding.IEEE Trans Info Theory,2003,49(2):371-381.3 Chou P A，Wu Y, Jain K. Practical network codingC Allerton Conference on Communication, Control and Computing, Monticello, 2003，473-482.4 TAO Shao-guo, HUANG Jia-qing, YANG Zo
31、ng-kai et al. Survey of network codingJ. Journal of Chinese Computer Systems,2008, 29(4):583-592.5 Ho T,Medard M,Koetter R,et al. A random linear network coding approach to multicastJ. IEEE Transactions on Information Theory, 2006,52(10):4413-4430.6 Yeung R W. Cai N. Network error correction, part I
32、:basic concepts and upper boundsJ. Communications in Information and systems,2006,6(1):19-36.7 Yeung R W. Cai N. Network error correction, part II: lower bounds J. Communications in Information and systems,2006,6(1):37-54.8 Zhang Zhen. Network Error Correction Coding in Packetized NetworksC. Informa
33、tion Theory Workshop, 2006.9 Koetter R,Kschischang F R.Coding for errors and erasures in random network codingC.in Procedure IEEE Int.SYmp.Information Therory,Nice France,2007.10 Hu Yun-quan,Guo Yao-huang. Operations Research Tutorial M.Beijin, Tsinghua University Press, 2007: 258- 265. 附中文参考文献：4 陶少国,黄佳庆,杨宗凯等.网络编码研究综述J.小型微型计算机系统,2008,29(4):583-592.10 胡运权，郭耀煌.运筹学教程M.北京：清华大学出版社，2007:258-265.作者通讯地址: 中南大学信息科学与工程学院计算机楼116#，电话:0739-，E-mail:pubook