物理网络编码（精选7篇）
物理网络编码 篇1
0引言
射频识别(Radio Frequency Identification,RFID)［１］作为一种自动识别技术,不需要被识别物体在识别物体视距范围内即可工作,具有准确率高、读取距离远、存储数据量大、耐用性强等特点。作为物联网的关键技术之一,射频识别技术广泛应用于仓储物流、物品追踪、身份识别、门禁控制等领域。
一套典型的RFID系统［１］由一个阅读器和一些标签组成。标签用于记录和存储物品信息,阅读器用于读写标签内信息。当多个标签处于一个阅读器的工作范围内,且使用同一通信频率同时向阅读器返回信息时,将产生标签信号传输的干扰。当阅读器检测到信号发生干扰时,将无法正确读取标签内信息,称为RFID系统的多标签冲突问题［２］。该问题将严重制约RFID系统读写效率。因此,研究并解决RFID系统的多标签冲突问题具有重要意义。
1相关工作与动机
目前已提出一些用于解决RFID系统的多标签冲突协议,主要分为两类［３］:基于ALOHA的算法和基于二进制搜索树的算法。
基于ALOHA的算法思想简单,但无法确保标签在一定时间内被读取,一些标签可能长时间无法被读取,出现“标签饥饿”问题;基于二进制搜索树的算法,在发生标签碰撞时,不断将标签分为2组,直到阅读器能够无碰撞地读取所有标签信息为止。典型算法有基本二进制搜索树算法(Binary Search Tree,BST)［４］、动态二进制搜索树算法(Dynamic Binary Search Tree,DBST)［５］、后退二进制搜索树算法(Regressive-style Binary Search Tree, RBST)［６］。基于二进制搜索树的算法是一种确定性算法, 能够避免“标签饥饿”问题,因此越来越受到研究领域的重视。
二进制搜索算法中,阅读器在检测到发生碰撞后,简单地将冲突信息丢弃。但该冲突信息包含有多标签信息, 如能加以利用,则可以减少读写次数,进一步提高二进制树搜索算法的性能。
近年来出现的网络编码技术［７］,给RFID阅读器利用多标签冲突信号、提高读写效率带来了可能。网络编码允许网络中的中间节点对接收到的数据进行编码后转发。 物理层网络编码［８］则是在物理层进行数据编码,利用电磁波的叠加特性,将无线电磁波在空间的自然叠加看作信号的编码过程,即等效为物理层的网络编码过程。在接收端通过译码获取所需信息,可减少数据传输时间,提高传输效率。
而RFID系统中多标签冲突发生时,冲突信号是多个标签信号的叠加,正是一种物理层网络编码运算。物理层网络编码的技术特点,使其适合于处理RFID系统中多标签的应答信号叠加时产生的冲突问题。
为此,本文提出一种基于物理层网络编码的二进制算法(Physical layer Network coding based Binary Algo- rithm,PNBA)来解决射频识别中的多标签冲突问题。与现有的射频识别标签防冲突算法相比,PNBA算法的创新性在于其引入了物理层网络编码,将传统方法中丢弃不用的多标签叠加冲突信息利用起来,分析和利用其中的有用信息,提高射频识别系统对多标签的识别速度和运算开销。仿真结果表明,PNBA算法在标签数目为100时,其识别次数比BST低83%,比RBST低43%,其读取次数效率达到0.93。
2 PNBA算法
2.1 PNBA算法冲突位识别
PNBA算法采用曼彻斯特码,以识别出接收到的信号是否发生了多标签冲突,并能定位到具体哪些位发生了冲突。PNBA算法在识别冲突时,将检查叠加信号的解调信号。如果该位前半周期或后半周期为零电平,则该位未发生冲突。如果该位前半周期和后半周期都为非零电平,则该位发生冲突,用“X”表示。
2.2 PNBA算法相关约定
在给出PNBA算法详细流程前,首先给出PNBA算法用到的相关概念和符号。
请求命令———REQ(RSN):请求命令发送一个参考序列号RSN(Reference Sequence Number),序列号大于RSN的标签不应答,小于等于RSN的标签应答,以减小待识别标签数量,即减小冲突范围。
选择命令———SEL(RSN):序列号与RSN相同的标签,被阅读器选择,为进行后续的读写操作等作准备。
读取命令———RD-DATA:阅读器读取被选择命令选定的标签返回的序列号数据。
休眠命令———UNSEL(RSN):将序列号与RSN相同的标签置位休眠状态,不再响应阅读器的任何命令。
阅读器堆栈———为了保持冲突信息,阅读器在识别标签过程中维护一个堆栈结构,用于保存接收到的多个标签的叠加冲突信息。
2.3 PNBA算法流程
PNBA算法将物理层网络编码引入到射频识别标签防冲突方法中,分析和利用被传统防冲突方法丢弃的冲突信息,提高标签识别效率,具体包括以下步骤:
步骤1:初始化参考序列号RSN,将其每一位设置为1,例如电子标签的序列号为8位,则参考序列号初始化为11111111,初始化后退变量i为0。
步骤2:读写器执行读请求命令REQ(REQuset),所选标签组中标签序列号小于等于参考序列号的电子标签应答,并传回该标签序列号。
步骤3:按照曼彻斯特码编码原理,读写器对接收到的信号进行解调、译码并检测是否发生冲突:如果某个码元的前半周期和后半周期都为非零电平,则表明该码元产生冲突,将该冲突信号对应的冲突解调信号压入冲突解调信号堆栈,然后找出最高的冲突比特位,将译码信号的最高冲突比特位设置为0,低于该位的设置为1,高于该位的保持不变,然后以此作为下一次请求命令REQ的参照序列号,执行步骤2;如果每个码元的前半周期和后半周期中,其中一个为高电平,另外一个为低电平,则没有产生冲突,读写器能识别该标签信息,执行步骤4。
步骤4:对选中的标签,读写器执行读出数据命令RD -DATA(ReaD-Data)来读取标签数据并保存,接着执行去选择命令UNSEL(UNSELect),使标签进入“休眠”状态。
步骤5:判断冲突解调信号堆栈是否为空,如果为空, 表示所有标签信息都已得到,则算法结束。否则读写器将已读取到的标签数据与冲突解调信号堆栈栈顶存储的冲突解调信号作减法运算,执行i=i+1运算:如果无法得到无冲突的编码信号,即运算结果始终存在冲突,执行步骤6;如可以得到无冲突的编码信号,则得到1个未读取标签信息,将该标签信息存储,然后读写器执行去选择命令UNSEL,使该标签进入“休眠”状态,冲突解调信号堆栈的栈顶元素出栈,重复步骤5;如果得到信号为全低电平, 表明该冲突信号内所有标签信息都已解码得到,将冲突解调信号堆栈栈顶元素出栈,重复步骤5。
步骤6:将倒数第i次读写器与标签交互所用的参考序列号作为下一次请求命令REQ的参照序列号,将i重新设置为0,然后执行步骤7。
步骤7:返回步骤2,直到识别出所有标签为止。
PNBA算法流程如图1所示。
3 PNBA算法仿真分析
为了分析PNBA算法的性能,使用MATLAB对BST、DBST、RBST和PNBA算法进行了仿真。
图2给出了待识别标签数目为5~100时,4种算法分别需要的读取次数。由图2可知,BST和DBST所需的读取次数一致。RBST的读取次数与BST和DBST相比, 有了较大幅度降低,且随着标签数目增加,优势越发明显。 在标签数目在5~25范围内,PNBA算法和RBST算法较为接近;待识别标签数目大于25以后,PNBA所需的读取次数明显低于RBST,且随着标签数目增加,其与RBST相比优势越大;在标签数目为100时,PNBA算法比RBST算法低45%。
图3给出了待识别标签数目为5~100时,4种算法读取次数效率的比较。所谓读取次数效率,为标签个数除以所需的读取次数。从图3可以看到,PNBA算法的读取次数效率明显高于其它3种算法。当标签数目在5~40范围内时,BST和DBST的读写次数效率逐步降低至0.2, PNBA算法逐步增加至0.8,而RBST一直维持在0.5;标签数目大于40以后,BST、DBST、PNBA的读取次数效率变化较为缓慢,BST和DBST维持在0.16~0.19之间, PNBA维持在0.89~0.93之间,RBST一直维持在0.5。
4结语
本文提出基于物理层网络编码的二进制算法PNBA来解决射频识别中的多标签冲突问题。PNBA依托物理层网络编码技术,利用多标签冲突信号中的信息,能够减少识别次数,提高识别效率。多个标签非严格同步情况下,冲突信息的解码将是本文下一步的研究工作。
参考文献
[1]ROBERT C M.Radio frequency identification(RFID)[J].Computer and Security,2006,25(1):18-26.
[2]QIAN ZHIHONG,WANG XUE.An overview of anti-collision protocol for radio frequency identification device[J].China Communications,2014,11(11):44-59.
[3]ZHU LEI,SHING TAK,YUM PETER,et al.A critical survey and analysis of RFID anti-collision mechanisms[J].IEEE Communications Magazine,2011,49(5):214-221.
[4]WALDROP JAMES,ENGELS DANIEL W,SARMA SANJAY E.An anti-collision algorithm for the reader collision problem[C].2003IEEE International Conference on Communications,Piscataway,2003:1206-1210.
[5]LI BINGZHANG,JING ZHENGJUN,LUO YE.A RFID anti-collision searching algorithm based on regressive-style binary system[J].Computer Applications and Software,2009,26(12):96-98.
[6]LAW CHING,LEE KAYI,SIU KAI-YEUNG.Efficient memoryless protocol for tag identification[C].2000 4th International Workshop on DIALM,NewYork:ACM Press,2000:75-84.
[7]AHLSWEDE RUDOLF,CAI NING,LI SHUOYENROBERT,et al.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.
[8]ZHANG SHENGLI,LIEW SOUNG CHANG,LAM PATRICK P.Hot topic:physical-layer network coding[C].The 12th Annual International Conference on Mobile Computing and Networking,NewYork:ACM Press,2006:358-365.
网络编码 篇2
网络编码,是网络中的节点将接收到的信息进行编码后再转发出去的多点传送技术,是一种融合了路由和编码的信息交换技术,它的核心思想是在网络中的各个节点上对各条信道上收到的信息进行线性或者非线性的处理,然后转发给下游节点,中间节点扮演着编码器或信号处理器的角色。根据图论中的最大流-最小割定理,数据的发送方和接收方通信的最大速率不能超过双方之间的最大流值(或最小割值),如果采用传统多播路由的方法,一般不能达到该上界。R Ahlswede等人以蝴蝶网络的研究为例,指出通过网络编码,可以达到多播路由传输的最大流界,提高了信息的传输效率,从而奠定了网络编码在现代网络通信研究领域的重要地位。
2 网络编码方案
网络编码方案可分为线性和非线性两种,其中线性方法的编码和解码都相对简单,因此,一般都倾向于采用线性方法。Li指出在有向网络中,如果一个网络编码问题有解,则一定有线性解。从理论上保证了线性算法的有效性。线性组合要求网络节点具有更高的计算能力,然而根据摩尔定律,随着处理成本的降低,网络的“瓶颈”逐渐转向业务所需的更高的带宽支持和服务质量(QoS)保证。网络编码实际上是用节点处理能力换取更高的网络效率。
2.1 编码过程
线性网络编码是将节点传送信息线性映射到一个有限域内,利用线性关系实现编译码过程。假设每个信息数据包为L比特,当它与要组合的数据包长度不同较短的信息附加额外一串“0”,将包中的s个连续比特组成域上的一个符号,则一个包中包含L/s个符号。在线性编码下,运用乘法和加法运算,使从节点发出去的数据为该节点接受到信息的线性组合。假设一个源或多个源产生的原始数据包含信息为M1.......Mn,则在线性网络编码中传输的数据可表示为线性网络编码是将节点传送信息线性映射到一个有限域内,利用线性关系实现编译码过程。假设每个信息数据包为L比特,当它与要组合的数据包长度不同时,较短的信息附加额外一串“0”,将包中的s个连续比特组成域上的一个符号,则一个包中包含L/s个符号。在线性编码下,运用乘法和加法运算,使从节点发出去的数据为该节点接收到信息的线性组合。
2.2 解码过程
解码需要求解一组线性方程。实际中,可以应用高斯消去的方法:节点存贮编码向量以及编码之后的结果,以行向量的形式,存储在所谓解码矩阵中。最初,解码矩阵中只包含未经该节点编码的包以及与之相对应的编码向量(如果有的话),否则为空。当接收到一个已编码包后,会从中抽取它的编码向量以及编码结果,放入到解码矩阵中。解码矩阵会经过等价变换变成行阶梯型,最终变成行最简型。所收到的某一个包如果可以增加矩阵的秩,则称之为更新包,如果所收到的包是非更新的,它可以通过等价变换变为全零,从而可以忽略。当解码矩阵变换成最简型后,方程组得解。这种情况发生在当接收到n个线性独立的编码向量之后。
3 总结
网络编码(Network Coding)是进入21世纪后通信领域的一项重大突破,它融合了编码和路由的概念,通过允许对来自不同链路的信息进行编码组合,使得网络节点既实现路由功能又实现编码功能.网络编码的应用可以改善网络性能,甚至可以改变网络结构、改变网络协议设计方法,可以说网络编码正在给现有的网络带来革命性的变化。
参考文献
[1]熊志强,黄佳庆,刘威,杨宗凯.无线网络编码综述[J].计算机科学.2007(3).
[2]黄政,王新.网络编码中的优化问题研究[J].软件学报,2009(5).
物理网络编码 篇3
智能电网结合信息技术可以重塑目前的电力系统,使其行之更为有效率,结合先进的控制、信息和管理技术,实现一系列从电力输送到终端用户之间的实时信息交互,故电网中的各个部分都需要进行数据的实时监测以保证电网运行效率。目前,传统的电力系统中通常采用有线通信技术来实现系统组件的监测和诊断。随着网络规模的扩大,有线通信技术(如PLC)会使得电力系统的监测网络部署和维护成本较高,难以满足实际工程成本控制的需要。因此,智能电网亟需部署大量低成本、高效率的无线监测设备以满足电网运行的稳定性和有效性,实现优化电力系统的目的。
在配电网络中,由于覆盖区域大,电网内部用于信息采集的节点数量众多,各节点间布置在楼宇之间,或近或远,如果采用传统的蜂窝网络,其覆盖有限,且会浪费大量资源。无线传感器多跳通信系统利用其良好的扩展性可以广泛应用于智能电网配电网络监控系统中。随着无线网络进一步深入至配电网络系统中,网络可以随时按需加入各种传感器节点终端,实时或周期性采集用电情况并将其反馈至配电网络中心。然而,大量终端监控节点的加入和退出,使得监控中心对于网络的管理更为复杂,如何建立有效的下行数据网络成为摆在智能电网配电监控网络建设面前的实际问题。采用简单固定路由构建的传统网络已经无法满足新兴监控网络应用在带宽和网络服务质量方面的要求,随之而来的是网络延时增加、数据丢失等等问题[1,2]。于是,多路径路由的通信方式被提出,旨在改善现有网络中存在的一些网络资源紧张问题,提高网络的服务质量Qo S。
1 相关工作
在传统的网络通信中,网络中的节点只能存储转发所收的数据包,当不同的数据采集节点到汇聚节点之间的最大流经过的路径可能在网络拓扑的某些链路上形成交叉共享链路,进而影响共享链路之间节点的数据传输率,因此采用传统的存储转发模式一般是不可能达到最大流最小割定理规定的组播信息容量上限的[3,4,5]。应用随机线性网络编码理论被证明在单个源节点向多个目的节点发送数据的情况下,一定能够达到网络组播容量的上限。采用网络编码技术可以有效地提高数据传输速率,实现最大容量通信。
考虑到网络编码在提高网络的吞吐量方面的优点,为了进一步改善配电网络下行监控网络的传输性能,引入了网络编码技术。但是网络编码不是万能的,不是所有的网络组播拓扑都能使用。配电监控网络要结合网络编码技术,在路由选择方面必须满足两个条件:(1)网络中存在冗余的路径;(2)具有相同目的节点的路径之间不能存在共用的路径。
2 基于网络编码的应用层组播路由算法
为了使配电网络下行监控网络的整体性能尽可能逼近网络容量上限,本节提出一种基于网络编码的无线数据传输路由算法,它是面向异构化接入不同类型大量监控终端的路由算法,并且充分考虑因网络编码的构造而采用多路径方法。
由图理论可知,在建立配电网络下行监控网络数据路由路径时,可以将无线下行网络抽象为有向图G(V,E),其中V是监控终端节点集合。监控网络中心控制节点向配电网络中各监控数据采集节点下发不同信息指令时,根据终端系统节点在网络中的功能不同,可以分成中心控制源节点S、中间转发节点N和目的节点T三类。E是节点之间的链路集合,对于每条链路(i,j)都有相应的权值:传输带宽bij和时延dij,其中i,j分别表示链路两端起始和结束节点序号。这里,源节点S完成对指令数据的生成和编码功能,中间节点N实现数据的编码和转发功能,目的节点T除了接收所需的数据分组外,也能够完成中间节点的数据转发功能。
假设整个配电网络下行监控网络中,只有一个中心控制源节点S负责提供数据。希望能借助网络编码的力量,使得建立的信息分发图能尽可能接近最大流传输,建立源节点和目的节点之间的多条通信路径。这里,为每条链路(i,j)定义参数state,当state=0时认为链路(i,j)未被占用,当state=1时认为链路(i,j)被占用,在某个目的节点加入网络的时候,网络中的链路状态均为0。
在建立无线下行监控网络的开始,网络中中心控制源节点S可以向与它邻接的其他网络节点通信,其他网络节点也可以和邻接节点保持通信更新链路状态信息。当一个新的数据采集节点v(v∈T)申请加入监控网络,它首先从与其邻接的节点获取相应的链路状态信息,得到v到各个邻接节点biv和div。节点v按照自己的接入需要,选择能提供自己服务的最大接入带宽的邻接节点作为其父节点(这里可以为节点v提供数据的邻接节点包括与节点v邻接的已经加入通信的目的节点)。节点v的父节点根据自己收到的邻接链路状态信息同样选择与其邻接的可以提供最大带宽的节点作为自己的父节点。如果选定的父节点为监控网络中的源节点S,则完成了建立节点v到源节点S之间数据传输路径,节点v加入了该监控网络。此时,路径p(s,v)上的带宽应该为p(s,v)上所有经过的链路(i,j)((i,j)∈p(s,v))提供的最大带宽的最小值;节点v到源节点的传输延时Dv为路径p(s,v)上各链路延时之和。修改网络状态信息,路径p(s,v)上所有经过的链路(i,j)的状态state全部赋值为1,链路被占用;路径p(s,v)上各链路的可用带宽也要进行更新,即减去p(s,v)所占用的带宽。
如果节点v只有一个与其邻接的网络节点,即节点v的入度为1。那么认为节点v完成了加入下行监控网络的全过程,否则,将在剩余的网络中(state=0的链路中)继续建立新的路径。在建立新的路径时,考虑网络的传输延迟问题,可以在进行链路选择的时候,选择传输时延最小的邻接节点做节点v新路径的父节点。按照前面一条路径建立的方法,同样建立一条新路径p(s,v),并修改网络中各链路的状态信息。如果节点v剩下的入度仍大于0,即还有可用的邻接节点和链路的存在,将继续为节点v建立新的路径,使得节点v可以以逼近最大流的速率接收来自源节点的数据。
通过对数据采集节点的路径延迟值进行衰减(非目的地节点的路径值不作衰减),这样数据采集节点可以吸引其他未加入到路由树的节点通过数据采集节点来加入到路由树,使更多的链路能得到共享,从而优化网络。按照下式对数据采集节点的路径进行衰减
其中,k是与节点v相邻且未加入网络的节点数,λ是调节衰减的参数,λ≥0。
在整个配电网络下行监控系统中,大量存在的监测数据采集节点不停加入退出整个网络,下行控制系统需要及时可靠将中心节点的指令信息传达下去。中心指令信息对于其传达的目的节点不同,数据传输路径可能存在链路的共用,这些共用的链路被定义为“瓶颈链路”。瓶颈链路的存在会影响整个网络吞吐量的大小。将网络编码技术应用在与瓶颈链路相连接的节点上,节点把收到的来自上级节点的数据分组进行有限域内的线性组合,就可以消除瓶颈链路对整个网络的影响,使得每个数据接收的目的节点可以相互共享这个网络资源,避免了不同数据分组之间的竞争碰撞。
以图1(a)所示拓扑为例来说明在具体网络拓扑给定下如何为每一个监控终端节点独立地建立两条与数据中心通信的数据传输链路。图1(a)表示的是控制中心发送指令信息的初始化过程,拓扑图中只有源节点,其他目的节点并未加入网络。如图1(b)所示的两条路径,其中10是申请加入网络。传感器终端节点除了作为数据接收者,同样可以作为中间节点完成对数据的存贮、处理和转发功能。因此,对于新申请加入的节点,它既可以通过共用网络中的其它节点,也可以通过接入与其邻接的中间节点来加入网络。图1(b)给出了节点9和10的两条路径,虚线表示的路径是到节点9,两条粗线表示的是到节点10。对于不同的节点,存在瓶颈链路(S,1)、(6,10),只需在节点S和节点6处进行网络编码即可解决数据碰撞的问题。
3 实验仿真和结果分析
采用Salama的随机链路发生器产生随机网络进行仿真来比较本文提出的算法和其他算法的性能。该网络模型能产生平均节点度为4的随机连通网络。网络节点随机分布在一个矩形区域中,任意2个节点u和v之间是否存在链路由概率函数
提出的路由算法是希望建立多条传输路径来使得网络的传输流量逼近图论中的网络最大流。然而在建立多条传输路径后,随之而来的网络延时问题将会被扩大,下面的仿真给出了尽可能多地建立到源节点的路径情况下形成的路由路径与只建立两条路传输路径(即冗余度为2)以及单路径之间的性能比较。
考虑到每一个节点的实际接受数据的处理能力,设置网络中目的节点入度最大值为5。下面分别比较有单路径树,2-冗余路径和多路径的性能,还主要是网络端到端吞吐量和网络延时:
图2和图3主要是通过改变网络的规模来比较路径数量不同对网络性能的影响。在不同的网络规模中,中心节点向各个终端节点进行数据传输,通过图2可以发现通过建立多条路径的方法,网络的端到端的流量大大提高,而网络的延时相比之下也有一定提高(如图4所示)。在传输大量数据的时候,每一个终端节点使用多路径算法找出能逼近最大流的多条路径同时进行传输,结合网络编码技术使得每一个终端节点可以独立享用整个网络资源,从而大大提高了网络的吞吐量。与此同时,对于每一个终端节点而言,其网络延时则是全部路经延时的最大值,而通过仿真可以看到,对于多条路径带来的延时增加相对与网络流量的成倍增加是较小的。
4 结束语
本文讨论了基于网络编码使用冗余链路来提高配电网络下行监控网络端对端吞吐量的算法,并且在Salama随机网络中对该算法进行了性能评价。仿真结果说明了建立多条链路的方法能以较小的网络延迟代价,显著地增强网络的吞吐量,提高网络链路的使用。
摘要：文中讨论了利用网络编码技术和使用冗余链路来提高配电网络下行监控网络端对端吞吐量的算法,并通过仿真结果说明了建立多条链路的方法能以较小的网络延迟代价,显著地增强监控网络下行链路的吞吐量,可以提高网络链路的使用。
关键词：多路径,网络编码,瓶颈链路
参考文献
[1]Banejee S,Bhattacharjee B.A comparative study of application layer Multicastprotocols[EB/OL]∥Submited,available at http://www.cs.wisc.edu/suman/pubs/compare.ps.gz.
[2]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.MIT Press,2001.
[3]Winter P.Steiner problem in networks:a survey[J].Networks,1987,17(1):129-167.
[4]Zhu Y,Li B,Guo J.Multicast with network coding in applicationlayer overlay networks[J].IEEE J.Select.Areas Commun.,Jan.2004,22(1):1-13.
物理网络编码 篇4
近几年出现的网络编码理论[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. 基于网络编码的网络Qo S性能分析
网络的Qo S参数主要有:网络时延、吞吐量、带宽、安全性等方面,在这一部分,将通过仿真分析几种网络编码算法对Qo S参数的影响。
3.1 仿真环境
仿真环境中共布置100个节点,仿真拓扑以及节点之间的连接关系采用Waxman[8]拓扑模型,首先在仿真的节点中基于均匀分布随机产生一个源节点和多个目的节点,其次找到从源节点到多个目的节点的最小割集,最后选择网络编码算法进行编码处理,本仿真中采用的网络编码算法都是二维结构,即均采用两个编码系数,在节点交汇处进行编码,然后再转发出去,仿真主要研究和比较延迟和吞吐量两个Qo S参数,仿真在QualNet 5.0下完成。
3.2 仿真结果及分析
本次仿真分别比较了优化网络编码(Optimal)、启发式网络编码(Heuristic)、随机性网络编码(Random)和确定性网络编码(Deterministic)四种网络编码算法在网络吞吐量和延迟方面的表现。
图2是四个算法在吞吐量方面的表现,由于优化编码算法采取了优化策略,获得的网络吞吐量最大,而启发式算法侧重于速度的要求,网络吞吐量较低。
图3是四个算法在延迟方面的比较,由图中可以看出优化网络编码尽管吞吐量大,但是所付出的延迟也比较大,而其它几种算法在延迟方面的表现就比较理想,尤其是启发式算法,大部分情况下保持一个比较低的延迟。
4. 结论
本文分析了几种网络编码中的常用算法,并对几种编码算法在提高Qo S性能方面的表现进行了仿真研究,仿真表明优化算法在网络吞吐量方面有良好的表现,而启发式算法则在低延迟方面更具优势。
参考文献
[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 of15th 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 network coding[J].Information Theory,IEEE Transactions,March2006.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.
物理网络编码 篇5
关键词：网络编码,延迟,无线网络,吞吐量,编码机会
0 引言
在传统的网络中, 网络节点的作用仅仅是完成对数据包的存储和转发。直到2000年网络编码[1]概念的提出, 网络节点担任的角色才得以发生改变:网络编码允许网络节点对接收到的多个数据包编码后再发送出去。这样可以大大提高单次传输携带的信息量、减少传输次数、缓解网络拥塞以及提高网络吞吐量。
无线网络与生俱来的广播特性和侦听能力使得它非常适合网络编码的应用。Kitti等[2]在20个节点的无线网络试验床上实现了基于机会路由和异或操作网络编码的无线协议COPE。然而数据包在数量上的不公平性对编码机会的产生带来了巨大的影响。文献[3]提出了人为地延迟网络节点中暂时不能编码的数据包的发送时间, 以制造更多的编码机会。但是该方法是针对TCP流提出的, 并不适用在UDP流上。Seferoglu等人[4,5,6]提出了基于丢包策略的编码感知算法用于调节各个数据流的发送速率, 用来均衡不同流中的数据包以达到增加编码机会的目的。文献[7-8]对具有编码感知能力的路由协议展开了研究, 针对COPE较被动的编码方式, 在路由选择过程当中适当地选择编码机会较高的路由。
1 COPE原理
COPE的基本工作原理可以用图1所示的X型拓扑来说明。假设该拓扑中存在2条数据流如表1所示, 节点1要向节点3发送数据包a, 节点4要向节点5发送数据包b。在某一时刻, 中间节点2同时获得了数据包a和数据包b, 节点5侦听到数据包a, 节点3侦听到数据包b, 并且节点2可以获知到它的邻居节点所存数据包信息。此时在节点2处采取异或编码方式得到ab, 然后将该编码包广播发送出去。在节点5和节点3处利用本地的数据包信息可以分别从编码包ab中解码出自己想要的数据包。由此可见, COPE通过3次发送达到了原来发送4次的效果, 使得网络的吞吐量提高了33.3%。
2 MDCNC基本思想
从增加编码机会的角度出发, 对采用COPE编码机制的UDP流无线网络展开研究, 提出一种基于最小延迟代价的网络编码方法——— (Minimum Delay Cost Network Coding, MDCNC) 。
在图2中, 假设有3条数据流分别记做f1、f2和f3, 各条流的路径如表2所示;则对于f1和f2, 节点2是它们的可编码节点。因为节点1向节点2发送来自于f1的数据包可以被节点5侦听到, 节点4向节点5发送的来自于f2的数据包可以被节点3侦听到, 此时如果将来自于2条数据流的数据包在节点2处编码后再发送出去, 那么在节点5和节点3处分别可以解码出各自所需要的数据包。但是对于f3, 在节点2处无法找到可以同它编码的数据流。因为节点7无法侦听到节点1或者节点4发送的数据包, 因此若来自于f3的数据包在节点2处同f1或f2中任何一个编码后都不能在节点7处完成解码。我们称这种情况为节点2是f3的非可编码节点。
以上情况是针对UDP流展开讨论的, 如果是TCP流则不会有这种情况发生, 因为TCP流与UDP流的不同之处在于TCP流存在一个ACK确认机制, 文献[3]正是有效利用了ACK的确认机制, 将路径相同但是方向相反的ACK包同要传输的数据包编码, 使得网络编码有可能发生在沿途任何一个中继节点上。而对于UDP数据流来说不是在每个节点处都存在网络编码的机会。图2中如果采用文献[3]的延迟策略, 则当节点2获得发送数据的机会且刚好待发送数据包是来自于f3时, 为了等待可能到来的编码机会, 会暂时不发送该数据包。但是该编码机会是不存在的, 称这种延迟为非必要延迟。
MDCNC的基本思想就是减少不必要延迟次数、降低必要延迟时间, 用牺牲很小的端到端延迟时间来获取更多的编码机会, 相比原有的COPE协议, MDCNC可以带来更高的吞吐量。
3 MDCNC实现
3.1 可编码条件
在给出MDCNC的实现方法之前, 首先给出确定可编码节点的算法。文献[2]指出, 节点v要向n个下一跳节点r1, ..., rn分别发送n个数据包p1, ..., pn, 节点v处可以将这n个数据包异或编码的充分必要条件是每个下一跳节点ri都已经拥有n-1个数据包pj, 其中j≠i。文中仍然考虑2跳以内的网络编码情况, 给出可编码节点要满足的条件:
式中, c表示待判定节点, F表示新增加的一条数据流, 用Fi标识c处已经存在的其中一条数据流。N (c) 表示c的一跳邻居节点集合。U (c, F) 表示F上c的上一跳节点, D (c, F) 表示F上c的下一跳节点。若要判断节点c是否为新增数据流F的可编码节点, 只要满足式 (1) 和式 (2) , 就能说明节点c为新增数据流F的可编码节点。
3.2 路由发现过程
当节点Vsrc准备向节点Vdest发送数据并发现路由表中没有相应路由项时, Vsrc启动路由请求过程。
步骤1:Vsrc生成一个RREQ包并向自己的邻居节点广播出去, 在被广播之前需要初始化RREQ包中的一系列参数。每个中间节点Vi将首先丢弃路径记录中已经包含Vi的地址的RREQ包, 以防止出现路由环路。否则, RREQ包中的信息被更新后广播出去。
步骤2:RREQ到达目的节点Vdest之后, 目的节点会选择一条最优路径, 然后生成一个路由回复RREP包, 将其沿着与来时相反的方向发送至源节点Vsrc。每个中间节点Vi首先根据RREP包中的信息更新路由表以建立到目的节点的正向路由。然后, Vi根据邻居信息应用式 (1) 来判断本身是否为该路由的可编码节点, Vi将该判断结果记录下来。Vi继续转发RREP包。
步骤3:源节点Vsrc接收到RREP后, 开始根据选定的路径发送数据包。
路由发现过程是在现有的AODV路由协议上做的改进, 只需要加入步骤2中可编码节点的判断, 这样做的好处是实现了网络的平滑过度。
3.3 MDCNC实施方案
图3中的算法流程图描述了MDCNC编码的具体实现方案, 整个过程可以分为发送和接收两部分。在每个节点Vi处都维护了3个FIFO队列 (Q1、Q2、Q3) , Q1用于存放将该节点作为下一跳节点发送过来的数据包, Q2用于存放该节点侦听到的数据包, Q3用于存放等待编码机会的数据包。
当节点Vi接收到一个数据包后, 首先判断该数据包是不是编码数据包, 能不能完成解码。接下来检查该数据包下一跳节点列表中是否包含Vi节点, 如果没有则说明Vi不是该数据包的下一跳节点, 将其保存在Q2中;如果是下一跳节点, 还要判断Vi是否为目的节点。
节点Vi获得一次发送数据包的机会后, 先处理Q3中的数据包, 再处理Q1中的数据包。
对于Q1中的数据包, 根据先进先出原则, 首先对放在队首的p1进行编码能力的判断, 判断Vi是否为它的可编码节点。如果是可编码节点再接着查看编码机会, 存在编码机会则编码后发送编码包;假如是可编码节点, 但此时却没有编码机会, 则将p1移动到Q3中等待可能到来的编码机会。
对于Q3中的数据包, 如果没有超过设定的延迟等待时间, 则继续等待, 如果超过了延迟等待时间, 则检查此时是否有编码机会到来, 有编码机会则编码后发送出去, 没有编码机会则不编码直接发送。
4 仿真分析
4.1 评价指标确定
MDCNC的设计目的在于增加数据传输过程中的编码机会, 因此选取吞吐量、平均端到端延迟和编码次数作为性能好坏的评价指标。
4.2 仿真环境设置
仿真环境为NS2[9], MAC层协议采用IEEE802.11 DCF, 信道容量为2 Mbit/s, 节点的数据发送队列大小为50, 节点的传输范围为250 m, 数据源采用的是CBR流, 数据包大小为512 byte, MDCNC中数据包延迟发送时间设置为1.5 s。分别对AODV、AODV+COPE和AODV+MDCNC这3种传输方式进行比较。
4.3 仿真结果及分析
4.3.1 固定网络拓扑
为了直观地说明MDCNC的优点, 首先在图2所示的轮拓扑中比较上述3种传输方式的性能, 数据发送速率设定在0~1 400 kbit/s之间, 选取其中的19个采样点作为性能分析的参考数据, f1和f2采用不同的数据发送速率:
图4和图5展示了在不同速率下3种传输方式的网络吞吐量和平均端到端延迟的变化情况。从折线对比图中可以看出在速率非常小的情况下3种传输方式对网络吞吐量影响差异不是很大, 而MDCNC的平均端到端延迟略微高于其他两种情况。但是随着数据发送速率的逐渐增大, 大概从180 kbit/s开始, 可以编码的COPE和MDCNC的吞吐量逐渐超出了不能编码的AODV和AODV的端到端延迟时间也迅速增大, COPE和MDCNC的端到端延迟均没有什么变化。由于采用了延时机制, MDCNC的端到端延迟时间会略微高于COPE, 此时MDCNC相对于COPE的优势并没有明显表现出来。但是随着速率的继续增长, COPE的网络吞吐量上升开始变缓, MDCNC迅速超过了COPE。在400 kbit/s左右时, 由于可编码的2条流速率不匹配问题以及发送队列的容量问题, 使得COPE的编码机会出现减少的趋势, 网络吞吐量开始下降, 端到端延迟迅速上升。而MDCNC所特有的延迟机制以及更大的队列空间使得它的编码机会还在增加, 吞吐量仍然保持上升, MDCNC的端到端延迟也略低于COPE, MDCNC的吞吐量优势显现出来。当速率达到900 kbit/s时, 由于严重的网络拥塞, 3种方式的吞吐量变化都趋于平缓状态, 端到端延迟也达到最大。
图6表示的是在不同速率下COPE和MDCNC编码次数的变化情况。在数据发送速率非常小的时候, 两者的编码次数相差不大, 随着数据发送速率的增加, MDCNC的编码次数要明显高于COPE。
4.3.2 随机网络拓扑
为了使MDCNC协议的评价更具普遍性, 在一个随机拓扑网络模型下进行多次实验。主要评价指标为不同数据流数目下MDCNC与COPE编码次数的变化。实验环境为利用NS2中setdest工具创建一个长、宽各1 000 m, 拥有50个节点的移动场景。节点的移动速度最大为2 m/s, 仿真时长为150 s, 选取数据流数目为2~20之间的10个数值, 每个数值下进行100次实验, 取平均值。
由图7可以看出, MDCNC中的编码次数明显高于COPE, 这说明MNCNC能够制造更多的编码机会, 进一步提高网络吞吐量。
5 结束语
针对COPE会受数据包数量不公平性的影响, 提出了一种可以应用在无线多跳网络中的最小延迟代价网络编码方法MDCNC。该方法的主要特点是只有在可编码节点处才会采取延时策略, 这样做的目的是尽可能少地增加端到端延迟时间。从仿真结果可以看出虽然MDCNC的平均端到端延迟大部分情况下会略微高出COPE, 但是却比没有网络编码的AODV低, 所以这样的延迟时间在网络容忍范围之内, 对于网络性能并无太大影响。而该方法所制造的编码机会却是不可忽视的, 与COPE相比较, MDCNC的编码机会约为COPE的1.5倍, 能够有效地缓解网络拥塞和提高网络吞吐量。
参考文献
[1]AHLSWEDE R, CAI N, LI S, et al.Network Information Flow[J].IEEE Transactions on Information Theory, 2000, 46 (4) :1204-1216.
[2]KATTI S, RAHUL H, HU W, et al.XORs in the Air:Practical Wireless Network Coding[C]∥SIGCOMM'06Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM, 36 (4) :243-254.
[3]HUANG Y, GHADERI M, TOWSLEY D, et al.TCP Performance in Coded Wireless Mesh Networks[C]∥Proc.Of IEEE SECON, 2008:179-187.
[4]SEFEROGLU H, MARKOPOULOU A.Network Codingaware Queue Management for Unicast Flows over Coded Wireless Networks[C]∥IEEE International Symposium on Network Coding (NetCod) , Toronto, Canada, June2010:1-6.
[5]SEFEROGLU H, MARKOPOULOU A, MEDARD M.NCAPQ:Network Coding-Aware Priority Queueing for UDP Folws over COPE[C]∥International Symposium on Network Coding (NetCod) , Beijing, China, July 2011:1-8.
[6]COPPI N D, NING J X, PAPAGEORGIOU G, et al.Network Coding Aware Queue Management in Multi-Rate Wireless Networks[C]∥The 21st International Conference on Computer Communications and Networks (ICCCN) , Munich, GER, July 2012:1-7.
[7]樊凯, 李令雄, 龙冬阳.无线mesh网中网络编码感知的按需无线路由协议的研究[J].通信学报, 2009, 30 (1) :128-134.
[8]LE J L, LUI J, CHIU D M.DCAR:Distributed Codingaware Routing in Wireless Networks[J].IEEE Transactions on Mobile Computing, 2010, 9 (4) :596-608.
网络编码技术在无线网络中的运用 篇6
相对于有线网络, 无线网络的可靠性一般较低。网络编码与无线信道的广播特性充分结合起来可以提高分布式无线网络传输可靠性。在多跳的无线网络中, 使用传统的重传方式会造成很大的延时, 严重影响数据的传输效率。而使用网络编码后, 路由器可以将缓存中所有的数据包放在一起进行编码, 目的节点在可以解码时对所有的数据只进行一次确认即可。Lun等人研究对比了目前己有的5种可靠性保证机制:端到端重传、向前纠错编码、链路重传、链路网络编码、完全网络编码, 以每个数据包的平均发送次数来衡量以上各种机制的性能。通过仿真发现, 端到端重传机制的性能最差, 链路重传和向前纠错编码机制两者的平均发送次数相差不大, 但两者较端到端重传机制有了显著的提高。后两种策略采用了网络编码技术, 较前面3种机制能够进一步地提高网络可靠性。本文将随机网络编码与无线网络的空间多样性结合起来, 提高无线网络的可靠性。
1 网络编码与网络空间的多样性
1.1 网络空间的多样性
国内外许多学者已经研究得出空间多样性对提高无线网络可靠性的作用, 其核心思想就是利用无线节点的协作, 建立起多径传输的通信子网, 并以此提高网络的可靠性。图1为空间多样性图示, 源节点S不能直接与目的节点T通信, 必须使用节点A、B或者C作为中继节点才能将数据包转发给T。采用端到端重传机制时, 即源节点S在收到目的节点T对每个数据包的确认信息后才会转入下一个数据包的发送。如果从路径S-A-T、S-B-T或S-C-T中只任选一条进行传输, 无论选择哪一条路径传输, 数据包能成功从S传输到T的概率都为20%, 而S传输K个数据包的传输次数的期望为10K次, 其中包括5K次数据包的传输和5K次和10K消息的传输。这种传输的效率是比较低的。当利用无线的空间多样性后, S可以在同一个时隙内以广播的方式向节点A、B、C发送数据包。网络中从源节点到目的节点的路径越多, 可靠性也会提高得越多。
1.2 网络编码与网络空间的结合
将网络编码引入无线通信领域之后, 网络编码能充分利用空间多样性达到提高网络性能的目的。把要传输的K个数据包作为一个数据块进行随机网络编码后, 若编码有限域Fq足够大, 可以认为源节点S不同时隙发送的数据包线性无关。T只需要正确接收到K个线性无关的数据包后就可以依据数据包中携带的全局编码向量, 并利用高斯消元法解出这K个数据包, 因此, 要使T能接收到K个线性无关的数据包, 源节点S需要发送数据包数量的期望为:
目的节点T并不关心是否能正确的接收到每一个编码数据包, T只需在收到任意K个线性无关的数据包后就能解码, 目的节点能够解码后只需向源节点S发送一次信息确认收到了整个数据块即可。使用完全编码机制时, 若从S发送K个线性无关数据包到T时, S需要发送编码数据包的次数期望为2.0K+5次。显然, 如果不考虑数据包长度的限制, K越大, 利用网络编码的优势也会越大。
2 通信子网的选择与建立
2.1 通信子网选择
在利用完全编码前需要在已知拓扑的前提下利用线性规划的方式选择子网来进行通信。这种方法的计算量一般都很大, 而且在实际的分布式无线网络中, 往往并不能事先知道网络的拓扑结构。本文将定义一种可以根据需求控制子网大小的新型通信子网:超路径。
图2进一步说明超路径的定义。若P1 (N1, A1) 为超图H (N, A) 的子图, P0 (N0, A0) 是一条以源节点为起点, 目的节点为终点的简单路径。设某超图H由S, A, B, C, D, E, F, T节点组成。信源节点S向新宿节点T发送数据, 可以选取以节点S, B, D, T组成的子图作为S, T-路径P0 (N0, A0) 。组成P0的1阶超路径P1 (N1, A1) 的将节点将在P1基础上加入A, C, F 3个节点。组成P0的2阶超路径P2 (N2, A2) 的节点将在P1基础上加入节点E。常见的普通的点到点路径是超路径的一个子集, 即P0可以看成是0阶超路径。节点A、C、E的使用可以提高源节点S到D之间的可靠性。而节点D到目的节点T的可靠性因为有节点F的参与而得到了提高。可以发现, 超路径的使用在局部提高了传输的可靠性。
2.2 通信子网的建立
建立一条从信源节点到目的节点的简单路径, 首先把这条简单路径作为P0, 并将P0所有的节点状态设为“激活” (Active) , 利用已知的R-1 (R≥l) 阶超路径生成R阶超路径。
(1) PR-1上的各点向周围节点广播探测信息包REQ, 探测包中包含了发送节点的阶数和地址; (2) 收到2个以上REQ探测包的节点则将自己状态设为“激活”并保存所有相邻节点的地址, 然后向自己相邻的节点报告状态。超路径PR则由PR-1, 加上所有处于激活状态的节点共同组成; (3) 当通信完全结束时, 目的节点就会利用广播的方式通知超路径上的节点立即停止发送数据, 并将其状态设为“停止”。其中, 步骤1保证了新加入的节点都为PR-1的邻节点, 步骤2保证了在PR-1上至少有2以上的节点与新加入PR的节点相邻。
建立超路径以后, 采用完全编码方式进行随机网络编码操作。当通信开始时, 信源节点首先将欲传输的数据组织成数据块的形式, 随后只要MAC层允许, 源节点就向其邻域广播经过随机线性网络编码后的数据包。当中继节点接收到编码数据包后就会把数据包线性无关的数据包缓存起来。同样在其MAC允许层时, 中继节点也将其已缓存的属于同一数据块的数据包进行随机线性网络编码运算, 然后把编码数据包在自己的邻域内广播。当目的节点收到足够的编码数据包使其能够解码当前数据块时, 就立即使用简单路径P0向信源节点发送确认消息, 这时在P0上可使用链路重传机制以保证传输的可靠性。当信源节点接收到确认信息后就会转入下一个数据块的发送。在通信完全结束时, 目的节点就会通知子网中所有节点停止数据的发送。
由于超路径能在局部给网络提供多条传输路径, 利用无线网络的广播信道就可以提高网络传输的可靠性。超路径包含越多节点, 网络则可能提供越高的可靠性。有两种方法可以增加超路径的节点数: (1) 通过提高节点的发射功率来增大节点的通信半径, 以增加每个节点的邻域节点的数量的办法来增加超路径的节点数。这种方式非常直接但是它的使用可能会给节点带来较大的耗能; (2) 每个节点可以使用较小的发射功率, 只与距离较近的节点直接通信, 通过选取更大阶数的超路径进行传输来达到可靠性的要求。这种方式需要有一个建立高阶超路径的过程, 但是每个节点不必选取很大的发射功率也可以提高通信的可靠性。
在节点数量达到一定程度后, 由于节点数量的增加而带来的可靠性的增益会非常有限, 因此不论通过何种方法提高超路径的节点数都可能会因为节点过多造成网络资源的浪费。因此超路径的阶数和发射功率的选择都是非常重要的。
3 仿真与结果
本文将仿真在无线网络中使用超路径改善网络可靠性的方法, 采用网络为方格网络, 如图3所示, 黑点表示节点, 各节点只能与其相邻节点通信。设数据包在每条链路传输失败的概率Pe都相等。S和T都同处于行标号为O的直线上, 数据包至少需要5跳才能从S到达T。选取从S到T所在直线上的节点作为简单路径P0。由超路径的定义可知, R阶超路径的节点都处于以标号-R至R之间的各行上。在仿真中, 每个数据块的大小都包含32个数据包, 每个数据包长度均为1000字节。随机网络编码的系数选取的有限域为Fq, 其中q=28, 即每个编码符号占用1字节。仿真开始后源节点S以1Mb/s的恒定速率发送数据包。
实验结果表明:Pe=27%时, 利用简单路径P0和超路径P1、p2进行随机网络编后的吞吐率的均值分别得到为0.40Mb/s、0.58Mb/s和0.60Mb/s。可以看出网络编码与无线网络的空间多样性结合起来, 提高了无线网络的可靠性, 吞吐率也会随之提高。当Pe分别为和50%和27%时, 在源节点发送的数据包个数相同时, 链路越可靠的目的节点接收到的线性无关数据线多说明网络可靠。链路越不可靠源节点需要发送越多的数据包才能使目的节点解码。
4 结束语
本文将随机网络编码与无线网络的空间多样性结合起来, 提高无线网络的可靠性。通过仿真实验表明, 较不使用网络编码与在简单路径上编码和在超路径上使用网络编码后, 可靠性得到了较大的提高, 具有较高的吞吐率。
参考文献
[1]陶少国, 黄佳庆, 杨宗凯, 等.网络编码研究综述[J].小型微型计算机系统, 2008 (8) .
[2]熊志强, 黄佳庆.无线网络编码综述[J].计算机科学, 2007 (10) .
[3]LUN D.5, MEDARD M, KOETTER R.Network Coding for Efficient Wireless Unicast[C].International Zurich Seminar on Communica-tions.2006.
基于NECO网络编码仿真研究 篇7
Ahlswede等人[1]证明了一般多播网络的最大流最小割容量只能通过中间节点混合不同数据流而获得, 网络编码研究[2,3,4]也揭示了:在高度不稳定网络中 (比如移动ad hoc网络、传感器网络和对等网络) , 网络编码在提高吞吐量和鲁棒性方面的潜力。
网络编码的基本思想在[1]中做了详细描述。目前, 网络编码的研究是基于玩具模型和分析工具, 随着实际协议和应用的开发, 需要一种网络编码的通用仿真平台。虽然, 在NS[5,6]、Opnet[7]和其它通用网络仿真器中, 已经实现了仿真框架和一系列访问库, 但是它们没有标准的网络编码仿真框架和可用库, 而仿真框架被看作是启动研究和重建协议栈的重要特征。由于网络编码对于不可靠和大规模网络最有益, 网络编码仿真器的关键特征是能仿真复杂网络。
NECO (Network Coding Simulator) [10]是一款致力于网络编码协议仿真的简单高性能仿真框架, 它的主要特征包括: (1) 拓扑图的定义 (这可以由NECO使用标准表示法随机产生) ; (2) 网络编码协议定义容易; (3) 网络操作的可视化; (4) 无缝的统计分析。
2、NECO的安装
NECO[8]仿真器的安装有两种方法。第一种也是最直接的方法就是安装VirtualBox[9]。VirtualBox是一个虚拟机, 可用于大多数操作系统。网站中提供的虚拟镜像包括仿真网络编码要用的操作系统的Ubuntu和运行NECO所需要的全部组件。第二种方式要求安装NECO使用的包, 提供了基于Linux系统的安装脚本。
2.1 基于Windows系统的安装
安装过程如下: (1) 下载虚拟机VirtualBox-3.1.2-56127-Win.exe, 双击安装图标可使用安装向导进行安装; (2) 下载Ubuntu系统的虚拟硬盘并解压成ubuntu＿neco＿rc4.vdi; (3) 启动虚拟机, 打开"新建虚拟电脑"对话框;在名称栏输入虚拟电脑名称, 系统类型选择"Linux", Version栏选择"Ubuntu", 单击下一步; (4) 在虚拟硬盘对话框中选择"使用现有的虚拟硬盘", 单击"Empty"后面的按钮, 在弹出的对话框单击"注册"按钮, 选择"ubuntu＿neco＿rc4.vdi"所在的文件夹, 单击完成; (5) 启动Ubuntu。在虚拟机中选择Ubuntu, 单击开始, 弹出启动窗口; (6) 启动终端, 在命令提示符后输入:cd neco和neco命令启动neco仿真器。
2.2 基于Linux系统的安装
安装过程: (1) 使用tar-xvf neco＿src＿install＿rc4.tar恢复所有文件到home目录, 用命令chmod+x install＿neco.sh设置文件的可执行权限; (2) 使用命令sudo./install＿neco.sh执行脚本, 这个脚本将安装运行neco所需的所有包。在安装过程中要求两次确认, 都选择"yes"; (3) 脚本中断后, 关闭终端, 重新打开一个终端; (4) 执行命令sage, 然后关闭; (5) 在neco目录下使用命令neco进行执行。
3、用法
NECO仿真器包括三种运行的方法: (1) 图形用户界面; (2) 命令行; (3) 使用XML文件建立仿真参数。在这三种方式中, 仿真器的用法由以下几点组成: (1) 产生随机图, 或者通过Pygraphviz导入静态图; (2) 选择源节点和sink节点; (3) 确定路由算法; (4) 确定网络编码协议; (5) 将仿真结果输出到指定终端, 或实时可视化网络操作。
3.1 图形用户界面的使用
在NECO的图形用户界面分为三种主要组件:左边是控制组件, 可预先设置仿真参数, 当仿真运行时更新仿真输出;中间是网络可视化组件;右边是直方图。
控制组件上共有7个标签。根据Graph标签, 可以选择图的类型, 对于不同的类型, 选择必要的选项, 然后单击Generate graph按钮, 由参数指定的拓扑图出现在可视化组件中。
在协议标签上, 可以选择用在仿真中的协议。
在仿真标签上, 选择选项:仿真限定时间、随机数产生器的仿真种子和目的节点数。如果仿真限定时间选择为0, 只有当所有目的节点接收到源节点发送的数据时, 仿真结束。
在shell标签上, 单击Start按钮, 可以启动仿真。对用户来说, 为了能以较慢的步速跟随通信时间的演进, 在Options中提供了Slow Simulation模式。在仿真结束之前能随时被停止;当仿真正在运行时, 网络中节点接收的包数的柱状图每两秒更新一次。左边, shell给出节点已经接收到的全部数据集。
3.2 命令行的使用
使用命令行选项可进行复杂图的建立和仿真, 而且仿真速度快。命令行的启动使用"-c"标志, 选项如表1所示, 在命令行中必须指出具有相应选项的图的类型、具有相应选项的协议、仿真的限定时间、仿真种子和目的节点数, 图的类型由Id列给出。
3.3 使用XML文件建立仿真参数
为了创建XML文件, 如果使用图形用户界面, 用户能激活选项"Save simulation parameters";如果使用命令行, 使用标志--save-sim-parameters。当执行仿真时, 将仿真参数保存到XML文件中。建立XML文件如图1所示。
3.4 统计和仿真输出
统计被保存在一个python hash中, 这就是被保存在python cPickle文件中的可行的数据结构, 并根据它的结构被解释。在Statistics类中, NECO包括无缝保存统计的方法。Statistics类包含两个主要方法:writeContant和writeTimeDependent。第一个可用于保存常量信息;第二个可用于保存随时间变化的变量。
4、结束语
NECO是致力于网络编码协议仿真的简单高性能仿真框架。直到现在网络编码的研究很大程度上依赖简单模型和分析工具。然而, 随着实际协议和应用的来临, 复杂网络中越来越多地需要通用的仿真平台。NECO提供了这样的平台, 并且能容易地扩展, 增加其他网络协议模块。
摘要：理论上, 网络编码技术的应用可以使网络吞吐量达到最大, 该技术在无线网络中的应用尤为突出。本文介绍了网络编码仿真器NECO的安装过程, 对仿真器的各组件的使用方法进行研究, 给出使用NECO进行仿真的具体操作步骤。
关键词：网络编码,NECO,仿真器
参考文献
[1]R.Ahlswede, N.Cai, S.Y.R.Li, and RW Yeung.Network informationflow[M].IEEE Transactions on Information Theory, vol.46, no.4, pp.1204-1216, July 2000.
[2]Ralf Koetter and Muriel M?edard.An algebraic approach to networkcoding[J].IEEE/ACM Trans.Netw., vol.11, no.5, pp.782-795, 2003.
[3]T.Ho, M.M?edard, R.Koetter, D.R.Karger, M.Effros, J.Shi, and B.Leong.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory, vol.52, no.10, pp.4413-4430, Oc-tober 2004.
[4]DS Lun, M.M?edard, R.Koetter, and M.Effros.Further results oncoding for reliable communication over packet networks[J].IEEE Interna-tional Symposium on Information Theory (ISIT) , pp.1848-1852, 2005.
[5]"The Network Simulator-ns-2, "http://www.isi.edu/nsnam/ns/.
[6]"The Network Simulator-ns-3, "http://www.nsnam.org.
[7]"Opnet Simulator, "http://www.opnet.com/.
[8]"NECO:NEtwork COding simulator, "http://www.dcc.fc.up.pt/neco/wiki.
【物理网络编码】推荐阅读：
物理网络设计05-13
安全网络编码07-28
随机网络编码09-15
随机线性网络编码08-30
一种网络编码和信道编码的联合设计07-06
网络编码:多媒体传输07-19
初中物理与高中物理08-26
物理很难，如何学习好物理08-11
初中物理教学论文掌握物理考试策略06-08
如何学好初中物理，初中物理学习方法总结08-31