加入收藏 | 设为首页 | 关于我们尊敬的先生/女士,您好,欢迎光临龙都论文期刊网!

 联系我们

点击这里给我发消息 张编辑 点击这里给我发消息 孙编辑 投稿邮箱:325783551@qq.com
联系电话:13939490175
论文发表咨询电话:17339408383
 计算机论文
多项式时间网络编码仿真系统的研究与开发
发布时间:2018-11-02 点击: 作者:去知网、万方查询
 摘要:网络编码是通信领域的一项新技术,自提出以来引起了广泛关注。文章简述了线性网络编码的工作原理,分析了确定性网络编码算法,优化了有限域,提出了一种仿真实现的具体方案,开发了一套网络编码仿真系统软件。系统实现了多项式时间复杂度的网络码字指派算法,同时对拓扑构造、最大流计算、编码点计算、算法选择、有限域选择、正交补计算等方面都进行了具体实现。系统由 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-),男,安徽马鞍山人,博士,研究方向为网络编码,传感器网络。

QQ在线编辑

服务热线

展开