网络纠错码的研究综述.docVIP

网络纠错码的研究综述 　　摘 要：网络编码与传统路由转发数据传输方式相比具有提升网络吞吐量等优势，所以成为当前众多领域研究热点。但由于各种原因数据传输中发生的错误会严重影响网络编码的性能。所以研究者们提出网络纠错码来有效的处理数据传输中的错误。网络纠错码的研究主要是采用经典纠错码的方法和基于秩距离码的方法。本文将从这两方面对该研究领域的主要工作进行综述。?? 　　关键词：网络纠错码；经典纠错码；子空间码 　　 　　一、引言?? 　　受噪声、人为等各种因素影响，数据传输过程中会产生各种错误，如：随机错误、擦除(丢包)和恶意节点攻击造成的错误。经典纠错码是处理这些错误的重要技术之一，它通过在时域上增加冗余来实现差错控制。但仍有一些错误，纯粹依靠经典纠错码技术无法很好解决。例如：擦除错误(包丢失)通常采用请求重发机制来处理，由于这种方式会带来很大传输时延，显然对时延敏感的应用不可取。另外，恶意节点攻击的错误，单独靠经典纠错码也不能很好解决。所以近来新兴一种新的差错控制方法网络纠错码开始受到越来越多的关注。网络纠错码研究内容包括信道模型的建模、不同错误纠错能力的刻画、网络纠错码的各种限的研究、最优码的存在性和构造研究以及实用网络纠错码的设计等。?? 　　2002年Yeung和Cai［1］最先提出网络纠错码，继而于2006年做了更深入探讨［2,3］。他们的研究视网络纠错码为经典纠错码的扩展，并将经典纠错码的一些限：Singleton限，Hamming限和Gilbert-Vashamov限延伸到网络纠错码中，还研究了最大距离可分网络纠错码。最大距离可分网络纠错码研究所主要关注的问题是存在性和构造问题，文献［4,5］对最这些问题进行了研究。Zhang［4］在线性网络纠错码中引入扩展的全局编码核，定义了线性网络纠错码的最小距离，进而证明该最小距离也可以刻画线性网络纠错码的纠检错能力。扩展的全局编码核非常适用于网络拓扑不确定的情景。由于这种随机特征使得经典纠错码的代数解码方法不再可行。于是，Zhang［4］提出统计译码算法。Koetter等［6］提出另外一种网络纠错码，子空间码，用子空间来表示源消息并将该子空间的一组基发送到网络上，还给出子空间码的距离度量方法，以及球填充，球覆盖限和Singleton限的扩展。?? 　　网络纠错码的研究有两个分支：基于经典纠错码理论和基于秩距离理论的研究。两者主要区别是：前者采用序列来表示消息，并通过在时域上增加冗余实现差错控制；后者采用子空间来表示消息，并通过在空间域上引入冗余实现差错控制。其中前者的研究主要包括线性纠错码以及随机线性纠错码的研究，后者主要是子空间码。本文将从这两方面来综述。?? 　　二、相关概念?? 　　通信网络可表示为有限无环有向图??G=(V, E)，其中顶点集V与网络中的设备对应，有向边集E与信道相对应。并假定各信道的容量是单位容量，两点之间的容量记为边的重数。e=(i,j)表示一条有向边，i为e??的尾节点，记为tail??(e)，j为e??的头节点，记为head(??e)??。采用In(??i)表示i??的入边集；Out??(i)表示i的出边集。目前的研究中主要考虑的是单源无环网络。设s表示源节点，T表示目的节点集，除开源和目的节点外称为中间节点。源节点的入边集和各个目的节点的出边集都为空。但为表述方便，通常在源s上引入虚输入信道，其数量即为该网络的最大流中的最小值n。?? 　　源发出的消息可表示为n-维行向量X=(x??1,x??2,…,x??n)，其中xi为有限域F??q上的元素，F??q的大小q足够大，并且源需要将消息多播到所有目的节点。为各个中间节点v建立对应的局部编码核矩阵K??v=［k????d,e］，其中k????d,e为F??q上的元素，d??为In(??v)中的一条边，e??为Out??(v)中的一条边。不考虑错误的情况下，任意信道e上传输的消息为y??e=??d∈ln(tail(e))K????d,ey??d，进而可表示为y??e=Xf??e，其中y??e为F??q上的n-维行向量，f??e为n-维的列向量，称为e的全局编码核。???? 　　三、线性网络纠错码?? 　　线性网络纠错码是一类重要的网络纠错码。当考虑网络传输过程中的错误时，??e上真正传输的信息为y′??e，z??e=y′??e-y??e表示信道错误。在网络G上引入一个辅助的节点v′(称为虚信源)，并增加一条直接通向e的尾节点的信道e′，此时可将该错误视为v′发送到e的尾节点上的一个消息，同时令k????e′,e=1，其他的任意异于e′的e*有k????e*,e=0，则e上真正传输的信息为y′??e可表示为：?? 　　y′??e=y??e+Z??e=??d∈In(tail