基于可靠多播网络下的上下文相关性网络编码方案

周艳玲，马林山

（合肥学院，安徽 合肥 230601）

基于可靠多播网络下的上下文相关性网络编码方案

周艳玲，马林山

（合肥学院，安徽 合肥 230601）

网络编码可以提高多播网络吞吐量,但传统的网络编码算法中节点的编译码很明显地增加了时间和空间的复杂度。文章给出的方案中，信源节点增加了编码功能，具有编码能力的节点对所接受到的信息进行简单的线性编码，不需要复杂的局部编码矩阵和全局编码向量的计算过程，中间节点和链路对所接受的信息块只提供存储和转发的功能，目的节点不需要考虑网络的拓扑结构和接受到数据块的次序问题，只要能够接收到足够的信息块，就可以在极短的时间内成功译码，恢复原信息。实验证明，基于上下文相关性的网络编码在多播网络中不仅使得多播传输达到理论的传输容量，并且降低了时间和空间复杂度，提高了网络可靠性。

上下文相关性；线性网络编码；可靠多播；时间复杂度；空间复杂度

0 引言

网络编码引自Ahlswede等人编著的关于网络编码的开创性论文[1]。网络编码理论使得在单源多播的网络环境下，数据的传输可以达到最大流最小割定理所决定的网络流量理论上的最大值[2，3]。在多播中应用网络编码技术，除了有提升网络吞吐量的显著优势，还有实现多播网络的流量均衡、提高带宽利用率、提升网络的可靠性、降低最优吞吐量问题的计算复杂度[4]等优点。

在有向无环网络中，研究最早也较为成熟的网络编码是线性网络编码，在线性网络编码中网络节点对传输的信息进行线性操作。在多播网络中，只要在足够大的有限域Fq中通过合适的线性网络编码，总能使多播传输达到其理论的最大容量。线性网络编码的核心是确定两个重要的参量，即局部编码矩阵和全局编码向量。局部编码矩阵针对节点而言，要求该节点需要存在输出链路，即出度不允许为0的节点。全局编码向量针对链路而言，一般为列向量，它们是通过局部编码矩阵计算得到的。

网络编码多播技术与传统的多播路由机制相比，网络编码操作需要消耗额外的计算资源，增加了网络成本和代价。文献[5]统计了多播节点执行网络编码的运算时间。实验数据显示，在极坏的情况下，节点的编码运算的时间可能达到1000s。文献[6]从不同的角度对如何降低网络编码的代价问题进行了探讨。由于多播网络中节点的编码和译码时间的限制，使得网络编码算法的研究至关重要。

本文主要从网络编码多播应用出发，针对有向无环的多播网络提出一种多播网络中基于上下文相关性的网络编码方案，通过在信源节点处对数据包进行划分、线性编码、存储、转发四个过程，使得信息在传输的过程中不需要了解网络的拓扑结构。中间具有编码能力的节点对信息的编码采用最简单的向量运算，然后对编码后的信息进行存储和转发，不具有编码能力的节点只对信息进行转发，克服了传统的局部编码矩阵和全局编码向量复杂的求解过程。此方案利用信源节点、中间节点和信宿节点之间所具有的上下文相关性的关系，使得具有编码和解码能力的节点在整个信息传输的过程中，缩短时间提高效率。

1 相关工作

文献[7，8]中提出在有限域上进行线性运算可实现组播，进而提出了多播网络中的线性网络编码（Linear Network Coding，LNC），线性网络编码的编码译码简单，因此，被作为主流的编码方法。文献[9，10]把网络编码问题转换为代数问题，把信息的输入和输出用转移矩阵联系起来，实现了应用状态变量方程或矩阵解决编译码问题。文献[11，12]针对多播应用，提出一种多项式时间复杂度的线性网络编码方法，使得线性网络编码的算法复杂度有了一定程度的提高。文献[13]提出了网络中建立子树分解的概念，并基于子树分解提出了射影几何编码的分布式方法，把子树的全局编码矢量设计成射影线上的射影点坐标，从而保证了不同路径上子树的编码矢量的线性无关性。在分解子树方法的启发下，文献[14]也使用了子树分解的方法，通过建立静态子树集和动态子树集，为各个子树分配全部编码矢量，但算法是一种拓扑依赖的确定性方法，在拓扑信息未知的情况下，本算法的可行性不强。文献[15]运用线性规划理论对网络编码的代价进行了分析和建模，提出了最小代价网络编码的理论模型，但该模型难以在实际网络中应用。鉴于此，文献[16]提出了一种改进的最小代价的网络编码算法，该算法遵循了最少关键链路优先的原则，实现了两点操作，一方面尽可能减少关键链路，另一方面使已经使用的链路次优先。该算法能够在一定程度上保证在实现多播的理论容量的前提下形成包含较少的关键路径，但是，当关键链路成为瓶颈时，会使网络延迟加大，甚至会使网络的效率明显下降。

网络编码的出现，在一定程度上使得多播的传输容量得以提高，但是网络编码操作需要消耗额外的计算资源，增加了成本和代价，因此，有必要探讨一种编码和译码简单、容错能力强、安全性好的可靠的多播传输模式。

2 上下文相关性网络编码方案

本文仅考虑单源即仅有一个源节点，如果是多源的情况下，只需要引入一个超源节点即可。设向量x=(x1，x2，x3，…，xn)表示源节点初次划分的消息向量。在本文中源节点根据下行链路的数量来决定消息的发送速率，当源节点的出度为h时，其发送的速率为h。节点和链路上所传输的消息y为x消息向量的线性向量。在本文中不管是行向量还是列向量，都是定义在某个有限域Fq上的，这样可以保证运算有意义。

2.1 上下文相关性网络编码引入

在网络编码下的多播中，源节点对数据包的处理功能由传统的分块、存储、转发三个基本功能，变成分块、编码、存储、转发。保证了网络中的数据包在传输的过程中，不会因为哪个数据包的丢失而引起数据包无法正常接收。源节点发送的数据包始终是数据分块的编码后的数据包，因此，网络传输过程中的安全性和可靠性也显著提高。在目的节点处，根据收到的数据包中的一部分信息组成可逆矩阵，另一部分组成编码包向量，通过这两部分的运算可以得到原数据包按顺序分块的数据包，从而得到原信息流。这种多播中的源节点、中间节点以及目的节点三者之间的编码、解码的过程完全具有上下文的相互联系、互相影响的关系，因此，具有上下文相关性的特点。

2.2 上下文相关性网络编码下的源节点多播流

源节点将原始的数据划分成n个数据块，并且源节点具有编码能力，将分块后的网络流在每一条链路上进行编码，并且将编码矩阵连同编码后的网络流一起传输。图1为原数据流被划分成三个数据块m1、m2、m3，经过线性网络编码后，三个数据块又形成了三个不同的线性编码数据块M1、M2、M3，三个编码后的数据块连同它们的编码系数矩阵一起分别形成了三个数据包M1、M2、M3，这三个数据包分别由三条链路转发到对应的下游节点路由器。源节点在对分块包编码的过程中，编码系数向量能够形成的系数矩阵A，且A是可逆的，即A-1有解，如图2所示。

图1 源节点数据流的划分、编码、转发图

图2 源节点编码后的信息系数形成的矩阵图

2.3 上下文相关性网络编码下的多播中间节点

在多播网络拓扑图中，除了源节点和目的节点，其他节点称为中间节点，在传统的网络中，中间节点都具有存储和路由转发能力。在网络编码多播网络中，当中间节点的入度大于1时，这个节点具有编码能力，当中间节点的入度等于1时，这个中间节点不需要具有编码能力。图3为具有网络编码能力的节点和不具有网络编码能力的节点比较。具有编码能力的网络节点采用最简单的线性网络编码。在编解码的过程中需要的时间最短，编码算法简单。

图3 编码节点和非编码节点信息转发图

2.4 上下文相关性网络编码下的多播目的节点

在多播网络中，目的节点所接受到的数据由两部分组成，一部分为线性网络编码后的信息流，另一部分为线性编码系数向量。在目的节点所接受的信息流，不需要关心信息流的次序问题，只需要关心是否收到与目的节点入度数相同的信息流数量，然后将信息流分离，按照接收的次序，将线性编码系数向量组成线性系数矩阵，将线性编码后的信息流组成一个目的信息流向量，经过运算得到原信息流的向量组合，最终形成原始数据。这个方法较传统方法的优点是，算法简单，不需要复杂的局部编码矩阵和全局编码向量的运算，减少了中间编码节点的开销，节省了时间，方便了计算。另外，在源节点就对信息流进行了信息分割和信息编码，使得信息在传输过程中安全系数更高，并且节点和相邻链路、链路与相邻节点之间的信息传递的计算时间降低，传输速度提高，不需要太多的缓冲存储。

2.5 上下文相关性网络编码下的多播网络传输

基于网络编码下的多播网络云图如图4所示。中间的网络节点云中的拓扑结构可以已知也可以未知，在网络传输的过程中，只要能够保证源节点发送信息成功和目的节点接收信息成功，就可以成功地解码形成原始信息。如果中间的网络节点云中有某个节点或者某个链路出现问题，这时候会由其他的链路再次发送网络编码数据信息，因为信息都是编码后形成的，因此，不需要分析哪个数据包丢失，只要在源节点再通过另外一条备份链路发送再次编码后的信息，目的节点能够接受到一定数量的数据包，就可以成功地还原出原始数据。

图4 基于网络编码下的多播网络云图

3 基于上下文相关性网络编码下的多播网络模型

多播网络用有向图G(V,E)表示，其中V表示网络节点的集合，E表示传输链路（边）的集合，源节点用S表示，目的节点的集合用T表示。本文中假设有向图G为单位容量网络，在图5中，多播的最大理论传输容量为3个单位，源节点中的原始的数据包为m，在源节点处经过分块和线性网络编码两个过程，其中数据包m被原始分块成三个数据块m1、m2、m3，再次经过线性网络编码，最终形成了M1、M2和M3三个数据包。并且，原始编码数据包块M1、M2、M3系数向量形成的矩阵可逆。图6为网络拓扑图和经过上下文网络编码后的网络流传输图。

图5 网络拓扑图

图6 网络编码后网络流传输图

3.1 每个节点编码后的数据包

数据由上游的源点经过中间节点编码、存储、转发后形成的网络编码数据流，以及到达最终的目的节点所形成的数据包流的集合而成。

3.2 在目的节点t1和t2可以收到的信息流

目的节点t1收到的信息流的6种可能组合，分别 为 （M1 M12 M23）、（M1 M23 M12）、（M12 M1 M23）、（M12 M23 M1）、（M23 M1 M12）、（M23 M12 M1）。

目的节点t2收到的信息流的6种可能组合，分别 为 （M12 M23 M3）、（M12 M3 M23）、（M3 M12 M23）、（M3 M23 M12）、（M23 M12 M3）、（M23 M3 M12）。

在目的节点所收到的编码信息流块的组合可能为上面六种情况的任意一种。不管是哪种情况的组合，都可以还原出原始信息流。

3.3 目的节点解码过程

假设t1收到的编码信息流块的组合为（M1 M12 M23），那么解码的过程为：

将信息块组合按照一定的顺序分解和再组合，将线性组合系数向量形成的编码矩阵为设为A，将编码信息流形成信息流向量设为C，通过矩阵A和向量C的运算可以求出原信息流块，然后将原信息流块按照顺序组合形成原信息流。公式如式（1）、（2）、（3）、（4）所示。

4 上下文相关性网络编码多播复杂性分析

基于上下文相关性的网络编码多播与传统的多播相比，其复杂性明显降低。本文所提出的方案中仍然采用最简单的线性网络编码算法，它与传统的线性网络编码有明显的不同，传统的线性网络编码过程包括中间节点的局部网络编码矩阵和网络链路的全局网络编码向量，不管是哪种编码方式，其转换的过程都需要大量的运算时间，如果网络节点的数量为n，链路数量为e，目的节点的数量是t，传统多项式复杂度的线性网络编码算法的复杂度为O(eth(h+e))。基于上下文相关性网络编码多播中，参与编码的节点有源节点和入度不小于2的中间节点，参与解码的节点只为目的节点。在整个数据传输的过程中，不存在每一个节点的局部编码矩阵和每一条链路的全局编码向量的计算过程，中间的不具有编码能力的节点和网络中的所有链路都只是起到了接收信息和转发信息的功能。并且在整个传输的过程中，传输的信息始终为线性编码系数向量，不需要编码矩阵的复杂运算，因此，节省了大量的时间。目的节点接收到的信息是向量集合，目的节点只需要通过简单的组合，就可以形成编码矩阵和编码系数向量，从而求得原始的数据。相比之下，复杂度远远小于传统的线性网络编码，其复杂度为O(n)。

本文中的方案与传统多项式复杂度的网络编码复杂度的比较图如图7所示。算法1线为本文中的基于上下文的网络编码方案中所体现的时间复杂度，算法2线为传统的多项式复杂度网络编码算法所体现的时间复杂度。通过图7可以看出，本文的方案随着网络节点的增多，其复杂度呈现缓慢增长的趋势，而传统的多项式复杂度网络编码算法其复杂度随着网络节点的增加呈现快速增长的趋势。实验证明，随着网络节点数的增加，该方案的优势更加突出。

图7 算法1和算法2时间复杂度比较图

5 结语

基于上下文多播网络中的网络编码方案可用于解决在网络拓扑结构未知的情况下的无圈有向网络的可靠多播问题。该方案的实现是通过在源节点处增加了编码的功能，使得源节点由传统的分块、存储、转发三功能变为分块、编码、存储、转发四个功能。在中间的网络节点和链路处，避免了传统线性编码由于计算节点的局部编码矩阵和链路编码向量所带来的计算和存储代价的增加。只要源节点能够保证原信息分块编码后的向量所组成的系数矩阵是可逆矩阵，目的节点在接收到足够多的信息块后，就可以成功译码，还原原始的信息，并且不需要考虑信息的次序问题。这在一定程度上节省了时间和存储资源，同时，由于信息都是编码后的数据块，所以也不会因为传输过程中消息的丢失而产生牵连效应，以至于目的节点不能及时成功译码，从而增大译码时延的问题。

基于上下文多播网络中的编码方案是一种简单的线性编码算法，其实现的条件必须是源节点具有编码的功能，并且在源节点处，信息编码也需要一定的计算时间，这就要求源节点的能量必须充足，功能必须强大。另外，本方案在安全性方面也有了一定的提高。当然网络中也避免不了可能存在重点节点加入垃圾消息或病毒，若不能正确和及时识别，经编码后将造成垃圾消息或病毒的扩散，最终使得目的节点无法译码。因此，在后期工作中，需要在多播的安全性方面对本文的方案进一步改进。

［1］Ahlswede R，Cai Ning，Y S，et al.Network information flow［J］.IEEE Trans.on Inform Theory，2000，46（4）:1204-1216.

［2］Yeung R W，Li S Y R，Cai N，et al.Network coding theory［M］.Hanover:Now Publishers Inc，2006.

［3］黄佳庆，程文青.信息论基础［M］.北京：电子工业出版社，2010.

［4］黄佳庆，李宗鹏.网络编码原理［M］.北京：国防工业出版社，2012.

［5］Ho T，Medard M，Koetter R，et al.A Random Linear Network Coding Approach to Multicast［J］.IEEE Transactions on Information Theroy，2006，52（10）:4413-4430.

［6］Ebrahimi J B，Fragouli C.Algebraic Algorithm for Vector Network coding［J］.IEEE Transactions on Information Theory，2011，57（2）:996-1007.

［7］Li S Y，Sun Q，Shao Z，et al.Linear Network Coding:Theory and Algorithms［J］.Proceedings of the IEEE，2011，99（3）:372-387.

［8］Ma S Y，Zhuo X J，Guo Q，et al.A Unified Result for Variable-rate Linear Network Coding［J］.Journal of Harbin Institute of Technology,2010，17（5）:657-660.

［9］Dougherty R，Freiling C，Zeger K.Insufficiency of Linear Coding in Network Information flow［J］.IEEE Transaction on Information Theory，2005，51（8）:2745-2759.

［10］Fong S L，Yeung R W.Variable-rate Linear Network Coding［J］.IEEETransactiononInformationTheory，2010，56（6）:2618-2625.

［11］Jaggi S，Sanders P，Chou P A，et al.Polynomial Time Algorithms for Multicast Network Code Construction ［J］.IEEE TransactionsofInformationTheory，2005，51（6）:1973-1982.

［12］Li S Y R，Cai N,Yeung R W.On Theory of Linear Network Coding［A］.IEEE ISIT［C］.2005.

［13］Fragouli C，Soljanin E.Information Flow Decomposition for Network Coding［J］.IEEETransactiononInformationTheory，2004，52（3）:829-848.

［14］刘宴涛，夏桂阳，等.一种基于子树分解的组播线性网络编码算法［J］.计算机工程，2015，41（11）：153-159.

［15］Bhattad K，Ratnakar N，Koetter R,et al.Minimal network coding for multicast［A］.IEEE International Symposium on Information Theory［C］.Melbourne:IEEE Communication Society，2005:1730-1734.

［16］陶少国，黄佳庆，等.一种改进的最小代价网络编码算法［J］.华中科技大学学报（自然科学版），2008，36（5）:1-4.

Context Correlation Network Coding Scheme under the Reliable Multicast Network

ZHOU Yan-ling，MA Lin-shan
（Hefei University，Hefei 230601，China)

Network coding can improve the multicast network throughput，but the encoding nodes and decoding nodes of traditional network codingalgorithmobviouslyincreased the complexityoftime and space.In this scheme，the source code can encode the blocked packets.The encoding nodes encoded the packets simply and didn’t need to intricately compute the local encoding matrix and the global coding vector.The middle nodes and links that have no encoding ability only store and forward the data packet.The destination nodes do not need to consider the network topology and the data-block order.As long as they can receive enough packets，they can decode successfully in a very short time and restore the original information.The experiments prove that the scheme can not only make the multicast reach the transmission capacity in theory，but also reduce the time and space complexityand enhance the reliabilityofmulticast network.

context correlation；linear network coding；reliable multicast；time complexity；space complexity

TP393.01

A

1674-3229（2017）03-0026-06

2017-05-25

安徽省教育厅自然科学资助项目（KJ2016A609）;安徽高校人文社会科学研究重点项目（SK2017A0606）

周艳玲（1979-）,女，博士，合肥学院计算机科学与技术系讲师，研究方向：多播技术、网络编码等。