多项式时间网络编码仿真系统的研究与开发
摘要：网络编码是通信领域的一项新技术，自提出以来引起了广泛关注。文章简述了线性网络编码的工作原理，分析了确定性网络编码算法，优化了有限域，提出了一种仿真实现的具体方案，开发了一套网络编码仿真系统软件。系统实现了多项式时间复杂度的网络码字指派算法，同时对拓扑构造、最大流计算、编码点计算、算法选择、有限域选择、正交补计算等方面都进行了具体实现。系统由 C 语言编写，具有友好的操作界面，对关键数据进行了计算统计，为网络编码的教学和研究提供了有力的工具。
关键词：线性网络编码；多项式时间算法；仿真实现中图分类号：TP393 文献标识码：A 文章编号：1673-1131（2015）10-0021-03.
0 引言
网络编码 [1-2] 是一项将路由与编码技术相结合的新技术，利用在网络的中间节点进行再编码操作，极大地提高了数据的传输效率。在传统的通信领域中，网络中的中间节点（即除了负责数据发送和接收的节点之外的节点）只负责转发数据，并不会对数据进行额外操作。长期以来，人们普遍认为除了数据的复制和传输，网络的中间节点不需要其他的数据处理功能，即使对中间节点上的数据进行处理也不会产生任何收益。然而 R.Ahlswede[3]等人于 2000 年发表的论文《Network information flow》彻底推翻了这种观点。Li、Yeung 和 Cai[4]提出了有关单个源节点多个目的节点的线性网络编码的实现。P.
Sanders[5-6]等人提出了多项式时间复杂度的网络编码算法。
在网络编码相关的教学与研究中，通常需要进行试验或者仿真。有些学者自己编写程序进行模拟仿真 [7]，但这种方法需要编写大量代码，同时也无法直观地对仿真的结果进行分析。
目前，网络编码的研究比较依赖模型和分析工具，因此需要一种通用的仿真平台。沈明等人[8]提出了一种基于 Window 套接字编程的网络编码仿真的实现方法，但该方法只能在最简单的有限域上进行异或运算，也只能实现最简单的“蝴蝶网络”；还有一些学者选择NS2和OPNET等仿真软件来实现[9]，但这些软件的优势在于对高层协议的支持，且使用起来较为复杂，有一定的难度。此外，还有一些学者使用特殊的硬件来搭建实验平台[10]。
本文对网络编码仿真进行了软件系统实现。本系统实现了多项式时间的网络码字指派算法，对拓扑构造、最大流计算、编码点计算、算法选择、有限域选择、正交补计算等方面都进 行了具体实现，适用于单源组播网络的网络编码仿真。本系统为网络编码的实验与仿真提供了良好的平台。
1 网络编码基本原理
网络编码方案一般可以分为线性网络编码和非线性网络编码两种。线性网络编码是指在网络中，对数据编码采用线性函数的编码方案。线性网络编码提高了网络的吞吐量[11]，改善了网络的负载均衡，提高了传输效率[12]，因此得到了广泛的应用与研究。
在网络中，从源节点向目的节点发送数据时，为了使得所有目的节点的速率达到组播容量的速率[13]，则需要在源节点进行编码。
假设需要发送n个数据包（p1，p2，…，pn），对其进行编码之前需要一个 N×n 的矩阵 M。N 是源节点输入链路的数目，矩阵中的所有元素属于有限域 GF(2m)。
编码后的数据包：
在源节点进行编码，编码完成之后发送数据包。数据到达中间节点之后，如果需要进行编码操作，那么在中间节点进行编码。当 n 个数据包均到达目的节点后，则根据相应的全局编码向量进行计算，从而得到原始数据。
2 有限域的运算
本文采用的网络编码方案为线性网络编码方案，即采用线性编码方式对源节点和中间节点进行编码。而编码操作都 是在有限域上进行的，因此需要为网络编码方案选择合适的有限域。目前，在网络编码方案中使用最多的有限域为GF(2m)。
当确定了一个不可约的本原多项式之后，就可以得到一个有限域 GF(2m)。例如：GF(28)的不可约本原多项式为 x8+x4+x3+x+1。在有限域上，对节点进行编码操作时，涉及到字符间的加法和乘法运算。根据有限域的运算规则，采用异或运算实现加法运算；而乘法运算的实现则复杂一些，将相应的多项式相乘，再将得到的乘积模上本原多项式即可。
有限域的选择对网络编码方案非常重要，因此本文为有限域建立了一个运算库。在该运算库中，系统采用了二维查表的方法，且对所有运算都使用宏代替法。因此，在该库中，运算速率得到了极大的提高。同时，该运算库的代码量仅为现有运算库的 20%到 30%。
3 网络编码算法
根据时间复杂度，确定性网络编码算法一般可以分为指数时间算法[14]与多项式时间算法[6]。Koeter.R 等人提出了指数时间的网络编码算法。但随着网络规模的增加，该算法的复杂度呈指数增加，具有一定的局限性。P. Sanders 等人提出了一种多项式时间的网络编码算法。
该算法的核心是利用向量空间正交补，确定局部编码向量，从而确保数据经过编码后，在目的节点能够成功解码。
该算法的具体步骤如下：
（1）构造一个单位容量的单源组播有向无环网络，设S为源节点， 为目的节点集，|T|为目的节点个数，h 为组播率。
（2）通过Ford-Fulkerson算法[15]计算源节点到每一个目的节点t 最大流 ht。将最小的最大流作为网络的组播容量 h，即 。
（3）确定源节点 s 到目的节点 t 有 h 条不相交的路径，集合 R 为这些路径的集合。
（4）构造一个虚拟的源节点 S’，连接 S’到 S 的 h 条不相交的单位容量链路。
（5）选定有限域，使得 ，将 S’到 S 的 h 条链路的全局编码向量设为单位向量 。
（6）确定每个目的节点 t 的路径集合 R；确定链路对应的全局编码向量集合，记为集合 B。
（7）按照拓扑顺序，从源节点开始对网络各节点进行排序，计算各节点输出向量的全局编码向量。①若链路只有一个输入时，不需要编码，该链路的全局编码向量就是其前一链路的全局编码向量；②若链路有多个输入时，需要在该链路的源节点对其进行编码。
对于所有的目的节点，若链路 e 被占用，将集合 R 中链路e 的前一链路替换为链路 e，同时，在集合 B 中做相应的替换，确保相关目的节点的集合 B 中的 h 个向量是线性无关的。
下面，本文将采用确定性算法来确定编码方案。
S. Jaggi 等人提出了一种确定性网络编码方法，该方法是线性网络编码的一种快速实现的方法。该算法确保了当有限域的尺寸大于接收节点数目时，一定存在确定性的网络编码方案对中间节点进行编码。
确定性算法的网络编码方案所需的有限域十分小，因此该算法的计算效率极高，这些特点使得网络编码的效率得到了极大的提升。同时，当节点接收到特定数据后，该方案能够确保目的节点能够以 100%的概率成功解码。但该算法同样存在缺点，该算法需要预先得到全局网络拓扑信息，因此该算法适用于小规模网络和大规模骨干网等固定网络。当网络的全局拓扑结构固定时，该算法首先获得全局网络拓扑信息，然 后就能得到网络编码方案，最后将该方案用于整个网络。
确定性算法的实现：
（1）根据拓扑结构的顺序，为每一条链路指派网络码字。
（2）若链路被 n 个节点共用，分别为这 n 个节点计算出一个替代向量 u 和一个该替代向量的正交补 v（例子 1 将说明如何为被替代向量 u 计算其正交补 v）。
（3）链路得到 n 个 u 向量和 n 个 v 向量。
（4）令集合 U 为所有向量 u 的集合，集合 V 为所有向量 v的集合。
（5）计算 r，r 为集合 U 中的向量的线性组合，且 r 与集合V 中所有向量的内积均不为 0（算法 1 为获得向量 r 的算法）。
（6）得到链路的全局编码向量，即为 r；得到链路的局部编码系数，即为计算 r 的过程中得到的系数序列。
（7）为所有链路分配全局编码向量和局部编码向量。
（8）完成算法。
（9）检查所有节点是否能够成功解码。
例子 1：下列矩阵 M 中，第 3 行向量为被替换向量 u=[412 9 10 9]。
首先对矩阵 M 求逆，得到 M’。 M’的第 3 列向量[11 1310 14 1]与 u 的内积为 1，与 M 中任意非 u 的行向量的内积为 0，且 MM’为单位矩阵，因此 M’的第 4 列向量[3 14 4 147]就是正交补向量 v。
算法 1：本文通过如下表 1 算法获得向量 r： 4 系统设计通过对网络编码相关知识的研究，编写了网络编码仿真实现的程序。程序首先构造网络的拓扑结构，网络中有一个源节点和多个目的节点。当网络的拓扑结构被设计好之后，还可以通过系统生成邻接矩阵。采用 Ford-Fulkerson 算法，计算最大流。然后求出并得到组播容量。之后可以采用两种方法，即确定性算法与随机性算法，通过其中一种算法来确定编码方法，分配网络码字。最后对所有节点进行验证，检验是否均能解码。
5 仿真实现过程与结果
先通过系统构造网络拓扑结构，拓扑图中有 1 个源节点，4 个目的节点。将生成的网络拓扑结构进行保存。如图 1 所示。 选择确定性算法，计算最大流，分配网络码字，并检查所有节点是否都能解码。如图 2、图 3 所示。 6 结语本文简述了线性网络编码的工作原理，分析归纳了确定 性网络编码构造算法以及其实际应用的优缺点。结合实际应用中的需求，在VC平台上对多项式时间的网络码字指派算法进行了软件实现，并且针对一个仿真实例，给出了仿真实现的过程，得到的仿真结果表明了设计的有效性。本软件操作方面、易于实现，为网络编码的实验与仿真提供了有效的工具，具有一定的实用价值。
由于时间精力与专业知识有限，对网络编码的研究还不够深入，所使用只是经典算法，功能也较为简单，目前只能满足常规化的应用，在这方面还有待进一步研究与完善。
参考文献：
[1] Fragouli C, Le Boudec J Y, Widmer J. Network coding: aninstant primer[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(1): 63-68.
[2] 陶少国, 黄佳庆, 杨宗凯, 等. 网络编码研究综述[J]. 小型微型计算机系统, 2008, 29(4): 583-592.
[3] Ahlswede R, Cai N, Li S Y R, et al. Network informationflow[J]. Information Theory, IEEE Transactions on, 2000,46(4): 1204-1216.
[4] Li S Y R, Yeung R W, Cai N. Linear network coding[J]. Information Theory, IEEE Transactions on, 2003, 49(2): 371-381.
[5] Sanders P, Egner S, Tolhuizen L. Polynomial time algorithms for network information flow[C]//Proceedings of thefifteenth annual ACM symposium on Parallel algorithmsand architectures. ACM, 2003: 286-294.
[6] Jaggi S, Sanders P, Chou P A, et al. Polynomial time algorithms for multicast network code construction[JInformation Theory, IEEE Transactions on, 2005, 51(6): 1973-1982.
[7] 蒲保兴, 王伟平. 线性网络编码运算代价的估算与分析[J]通信学报, 2011, 32(5): 47-55.
[8] 沈明, 蒲保兴, 唐彬. 基于 Windows 套接字编程的网络编码仿真实现[J]. 软件, 2012, 33(2): 11-14[9] 李令雄, 洪江守, 龙冬阳. NS 仿真器的一个网络编码扩展[J]. 计算机科学, 2009, 36(7): 71-73.
[10] 张明龙, 李挥, 李亦宁, 等. 基于网络编码的多信源组播通信系统[J]. 电子产品世界, 2011, 18(3): 23-25.
[11] 司菁菁, 程银波, 孙明明. 基于微分进化算法的层间等级网络编码优化[J]. 燕山大学学报, 2014, 38(4): 340-347.
[12] 钱辰, 田小平. 基于压缩感知的网络编码算法[J]. 微电子学与计算机, 2014(3): 013.
[13] Chi K, Yang C, Wang X. Performance of network codingbased multicast [J]. IEE ProceedingsCommunications,2006, 153(3): 399-404.
[14] Koetter R, Médard M. An algebraic approach to networkcoding[J]. IEEE/ACM Transactions on Networking (TON),2003, 11(5): 782-795.
[15] 谢金星, 刑文训. 网络优化[M]. 淸华大学出版社,2009基金项目：“基于网络编码的 XXX 技术研究”，总装预研基金（编号：9140A05010113xxx）。
作者简介：华可（1989-），男，江苏无锡人，硕士，研究方向为网络编码；杨余旺（1966-），男，安徽人，教授，博士生导师，博士，研究方向为网络编码，传感器网络；王磊（1986-），男，安徽马鞍山人，博士，研究方向为网络编码，传感器网络。
