基于网络编码的网络Q oS性能分析

刘永广

（广东轻工职业技术学院，广东广州510300）

1.网络编码的基本概念

近几年出现的网络编码理论[1]可以显著地增加网络容量和可靠性，网络编码彻底改变了通信网络中信息处理和传输的方式，是信息理论研究领域的重大突破，已经引起学术界广泛关注和重视。网络编码的本质是利用节点的计算能力提高链路带宽的利用率，图1的蝴蝶网络阐述了网络编码的基本原理。

图1 网络编码的原理

图中s是信源，x、y是信宿，各边的带宽均为1bit/单位时间，现要将2bit数据a和b同时从s传到x和y。可以看出s与x和y之间均分别存在两条独立路径，若采用传统路由方法，由于两组路径存在共有链路wz，a和b不能同时在链路wz上传输，则s到x和y的最大信息流速率为1.5bit/单位时间。若采用网络编码方法，在节点w上对a、b执行异或操作并转发，则节点x可以通过a⊕b⊕a的计算解出b，同理y也可以解出a，从而使s到x、y的信息流速率达到2bit/单位时间，带宽利用率提高33%。

可见，网络编码的核心思想是：具备编码条件的网络节点对接收到的信息进行一定方式的编码处理，然后传送下一级的网络节点，最后，在信宿节点通过逆过程的操作，即可译出信源发送的原始信息。

2.常用的网络编码算法

2.1 确定性网络编码

文献[2]首次针对组播网络提出了确定性分布式网络编码算法，其核心思想是将网络拓扑分解成多个子树，并保证每个子树的编码矢量属于其父树编码矢量的扩张空间，且任意两个子树的共有信宿的编码矢量均线性无关，该方法具有良好的可扩展性。

2.2 随机性网络编码

Ho等人给出了一种随机系数的分布式网络编码算法[3]，其随机系数从有限域中均匀随机选取，该方法对线性相关的信源具有信息压缩作用，适用于链路动态变化的场景，当给定的字母表足够大时能渐进达到最大组播速率，具有很强的实用性。

2.3 启发式网络编码

P.Sander等人提出了一种能够在多项式时间实现的集中式算法[4]，该算法是线性网络编码的快速实现，其目标是在尽可能小的有限域上快速地寻找编码向量，该算法首次将计算复杂性局限在多项式范围内，极大提高了网络编码的实用性。该算法主要包括三个步骤：（1）构造信源S至各个信宿节点t的路径簇；（2）将路径簇上的链路按照拓扑排序；（3）依次寻找各个链路的全局编码向量，使得各个路径簇上最新链路的编码向量能够形成一个基，以此确保最终形成的转移矩阵满秩。

2.4 优化网络编码

由于网络编码涉及信息缓存和矩阵运算，其额外开销比传统路由传输要大，因此降低网络编码的复杂性，对网络编码算法进行优化，具有重要的意义。目前的主要解决方案有基于简单网络的解决方案[5]，基于信息流分解的解决方案[6]，基于最小代价函数的解决方案[7]等。这些算法分别从编码构造、编码操作数以及有限域大小等方面去进行优化。

3.基于网络编码的网络Q oS性能分析

网络的QoS参数主要有：网络时延、吞吐量、带宽、安全性等方面，在这一部分，将通过仿真分析几种网络编码算法对QoS参数的影响。

3.1 仿真环境

仿真环境中共布置100个节点，仿真拓扑以及节点之间的连接关系采用Waxman[8]拓扑模型，首先在仿真的节点中基于均匀分布随机产生一个源节点和多个目的节点，其次找到从源节点到多个目的节点的最小割集，最后选择网络编码算法进行编码处理，本仿真中采用的网络编码算法都是二维结构，即均采用两个编码系数，在节点交汇处进行编码，然后再转发出去，仿真主要研究和比较延迟和吞吐量两个QoS参数，仿真在QualNet 5.0下完成。

3.2 仿真结果及分析

本次仿真分别比较了优化网络编码（Optimal）、启发式网络编码（Heuristic）、随机性网络编码（Random）和确定性网络编码（Deterministic）四种网络编码算法在网络吞吐量和延迟方面的表现。

图2是四个算法在吞吐量方面的表现，由于优化编码算法采取了优化策略，获得的网络吞吐量最大，而启发式算法侧重于速度的要求，网络吞吐量较低。

图2 网络吞吐量比较

图3是四个算法在延迟方面的比较，由图中可以看出优化网络编码尽管吞吐量大，但是所付出的延迟也比较大，而其它几种算法在延迟方面的表现就比较理想，尤其是启发式算法，大部分情况下保持一个比较低的延迟。

4.结论

本文分析了几种网络编码中的常用算法，并对几种编码算法在提高QoS性能方面的表现进行了仿真研究，仿真表明优化算法在网络吞吐量方面有良好的表现，而启发式算法则在低延迟方面更具优势。

图3 网络延迟的比较

[1]Li S-Y R，Yeung R W.Linear networking[J].IEEE Trans.Inform.Theory，2000.

[2]Fragouli C，Soljanin E.Decentralized network coding[C].IEEE Information Theory Workshop，San Antonio，Texas，2004.

[3]Ho T，Karger D R，Edard M M，et al.The benefits of coding over routing in a randomized setting[C].IEEE Int’l Symp on Information Theory(ISIT)，Pacifica Yokohama，2003.

[4]Sanders P，Egner S，Tolhuizen L.Polynomial time algorithm for network information flow[C].Proceedings of 15th ACM Symposium on Parallel Algorithms and Architectures，2003.

[5]Jaggi s，Chou P A，Jain K.Low compIexity algebraic network codes[C].Proceedings of.ISIT，2003.

[6]Fragouli C，Soljanin E.Information flow decomposition for networkcoding[J].Information Theory，IEEE Transactions，March 2006.52(3)：829-848.

[7]Lun D，Medard M.Ho T，et la.Network coding with a cost criterion[C].International symposium on Information Theory and its Applications(ISITA)，Oct，2004.

[8]Waxman B M.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications，1988，6(9)：1617-1622.