网络编码构造算法研究

摘 要：网络编码是通信网络中信息传输技术的一个重大突破，其核心思想就是利用路由器的智能化功能，允许网络中间节点对传输信息进行编码，从而提高网络传输效率。该文通过“蝶形网络”来分析网络编码的基本原理，并归纳现有网络编码的基本构造算法及其优缺点，最后讨论网络编码构造算法的进一步发展方向。

关键词：网络编码； 构造算法； 多项式时间算法； 随机网络编码

中图分类号：TN915-34文献标识码：A文章编号：1004-373X(2011)19-0011-04

Research on Construction Algorithm of Network Coding

CHEN Hai-yong1, ZHU Shi-bing2, LI Chang-qing3

(1.Department of Postgraduate, Institute of Command & Technology of Equipment, Beijing 101416, China;

2. Department of Training, Institute of Command & Technology of Equipment, Beijing 101416, China;

3.Department of The Informational Equipment, Institute of Command & Technology of Equipment, Beijing 101416, China)

Abstract： Network coding is an important breakthrough of the information transmission technology in communication network, whose main idea is using the intelligentized function of router and encoding the transmit information by the intermediate node of network to improve the efficiency of network transmission. An example about "papilionaceous net" is proposed to analyze the basic theory of network coding, the basic construction algorithm, advantages and shortages of network coding are summarized, and the further development direction of this algorithm is discussed.

Keywords： network coding; construction algorithm; multinomial time algorithm; random network coding

收稿日期：2011-04-11

0 引 言

在传统的通信网络及信息传输过程中，中间节点都只是完成简单的存储转发功能。2000年，R Ahlswede等人在IEEE Transactions on Information Theory上发表了论文《Network Information Flow》，第一次提出了“网络编码”这一概念，论文证明了在单信源组播网络中，使用网络编码可以达到信息传输的最大流界，并通过蝴蝶网络的例子说明传统路由无法实现最高的传输效率［1］。这篇文章是网络编码理论发展的开端。

网络编码是一种基于网络层的编码技术，核心思想就是尽量利用路由器的智能化功能，将传统的路由器中对数据包先接收再转发的处理模式提升到允许对接收到的数据包进行组合、编码等一系列的智能化处理，然后再转发出去［2］。

1 网络编码的基本原理

在研究网络编码的过程中，为了能够给大家一个直观的印象，能够更深入地了解网络编码的概念，下面将通过著名的“蝶形网络”进行分析。假定有一个(如图1所示)通信网络，它拥有单个信源和2个接收节点，假设每条链路都无时延和无差错，且信道容量为1，即单位时间内可以传输一个单位信息量(例如1 b)。图中，S是信源节点；Y和Z是信宿节点；T,U,W,X是中间节点。源节点S要同时向两个信宿节点Y和Z发送组播信息。根据图论的“最大流最小割”定理，该多播的最大理论传输容量为2，即理论上信宿Y和Z能够同时收到信源S发出的2个单位的信息，也就是说能同时收到b1和b2。

图1 “单信源二信宿”蝴蝶网络如果是传统的信息传输方式，如图1(a)所示，链路STTY和STTWWXXZ传送b1，链路SUUZ，和SUUWWXXY传送b2，信道容量为1的要求约束了链路WX，使得链路WX无法同时传输b1和b2。b1和b2传输到节点W时，若WX传输b1，则b2需要等待b1传输完毕才能传输，所以在单位时间内，信宿Y获得两个b1，信宿Z获得b1和b2，该方式不能够实现最大传输容量。如果应用网络编码的思想，则如图1(b)所示，令节点W为编码节点，b1和b2传输到节点W时，W对接收到的b1和b2进行编码，压缩传输信息流，从而，使得链路STTY和SUUZ分别给信宿Y和Z传输b1和b2，链路WXXY和WXXZ给信宿Y和Z传输b1b2，Y收到b1和b1b2后，通过译码操作b1(b1b2)就能解出b2，因此，信宿Y同时收到了b1和b2。同理，信宿Z也同时收到b1(通过译码操作b2(b1b2))和b2，由此，基于网络编码思想的传输方式能够实现理论上的最大传输容量。

在无环有向网络中，只要存在链路瓶颈，就可以利用网络编码来提高其信息传输吞吐量。因此，在利用网络编码思想时，应该寻找链路瓶颈，选择适宜的网络编码节点，应用相关的网络编码构造算法，从而实现理论上网络组播的最大传输容量。

2 网络编码构造算法

为了便于理解，在介绍网络编码构造算法之前，先给出以下两个定义：

定义1：全局编码向量

如图2所示，设X=［x1,x2…,xn］为信源S输出的n维信息流向量;Zj为第j条链路上传输的信息流向量;Zj为第j条链路上传输信息流中关于信源输出信息流向量的系数，则Zj=ξjXT，则ξTj称为第j条链路的全局编码向量。

定义2：系统转移矩阵

如图2所示，设X为发送的信息流向量;Y为接收的信息流向量;ξj为第j条链路上传输信息流中关于信源输出信息流向量的系数，Mi为第i个节点对应的系统转移矩阵，即Y=X×Mi，其中Mi=［ξ1,ξ2,…,ξj］T。

网络编码构造算法解决的主要问题是如何有效求得每条链路对应的全局编码向量，并运用该全局编码向量进行线性操作，计算出链路上传输的信息向量。编码算法的复杂性是衡量网络编码能否有效实现的重要依据。网络编码构造算法应根据实际的网络拓扑结构来具体分析。在前期的研究中，人们提出了线性网络编码、代数网络编码以及随机网络编码等方法。典型的算法包括指数时间算法［3］、多项式时间算法［4］、随机网络编码算法［5］和贪婪算法［6］等。