路由模型

路由模型（共6篇）

路由模型 篇1

随着大量具有短距离通信功能的智能终端设备出现,研究人员开始利用这些设备移动带来的通信机会,在网络基础设施无法完全覆盖的环境中进行组网,提出了机会网络[1](Opportunistic Network)的概念。在机会网络中,通信节点之间不存在一条端到端的完整路径,消息是通过节点移动并与其他若干节点相遇进行存储、携带、转发。社区模型的机会网络,是指由具有社会属性的个体所携带的短距离通信设备组网而成的机会网络。由于携带者之间的社会关系存在一定的依赖性,相对稳定,因此,这种机会网络会出现节点聚集的现象,从而形成社区。节点在社区内移动相对缓慢,节点相遇频繁,但不同社区间的节点连接比较稀疏,个别节点相对活跃,经常往返于不同社区之间。

1 相关工作

机会网络中典型的路由算法,如Epidemic[2],Spray and Wait[3],Spray and Focus[4],Prophet[5]等,基本思想都是增加消息的拷贝份数,从而提高消息传输的成功率。然而,社区模型下,节点的运动具有一定的规律,根据其规律性来考虑消息的拷贝份数和转发时机,可以有效降低消息传输的延迟和网络资源的开销。

文献[6]提出了一种用于延迟容忍网络的、基于社区的消息传递算法,其基本思想是根据节点的活跃度对节点进行社区内的排名和整个网络的全局排名。当源节点发送消息时,在相遇的节点中寻找全局排名比自己大的节点进行社区间的转发,直到将消息传递到目标社区内的节点,由后者根据社区内排名进行传输,直到遇到目标节点为止。算法利用社会关系进行消息传输,提高了消息传输成功的概率,但是,该算法采用的是单消息拷贝策略,消息传输延迟较大。

文献[7]提出了一种基于社区模型的机会网络消息传输算法。算法根据节点接触的频繁程度,将所有节点划分到不同的社区。社区内,根据节点的平均相遇时间间隔来确定消息的拷贝份数和转发时机;社区间,依靠相对活跃节点的移动来进行消息的传输。该算法还考虑了过期拷贝的删除机制,有效降低了网络负担。但是,该算法的社区模型与真实社会的移动规律还有差距,并且,该算法节点活跃度的计算只考虑了节点的相遇历史情况,这使得消息投递成功的概率较低。

文献[8]提出了一种CSB算法,该算法和文献[7]基本类似,但在对社区间的消息进行转发时,引入了特殊节点的概念,即新加入本社区的节点,认为这些节点会与原社区的一些节点保持密切的联系,因此本社区节点可以借助这些特殊节点与原社区进行消息传递。

在对以上工作研究的基础上,改进了现有的社区模型,使之更加符合真实社会移动规律,并设计了新的社区间和社区内的路由算法,提高了消息投递的成功率,有效降低网络资源的消耗。

2 基于节点回归的社区模型

真实社会中,节点除了具备聚集现象外,往往会带有一定的回归性。基于这种规律,改进了现有的社区模型:

(1)设节点集为一个社会C,分为若干社区Di,一个节点只允许属于一个社区Di。

(2)节点在社区内的移动采用随机目标点模型。

(3)节点具有一个社会度属性(<1),表征节点本次移动离开家乡社区进入其他社区的概率。

(4)节点具有活跃度向量属性T,Tij表示节点ni和nj之间的相遇属性,Tij越大,表示ni和nj之间越容易相遇。

(5)设置社区向量V,Vi记录了节点s遇到的处于社区Di中的节点数。

(6)设归属阈值Ths,若节点s记录的Vi>Ths,则认为节点s到达社区Di一次,并且清除V。

(7)设吸引力向量Att,Atti表征了节点s对非家乡社区Di的趋向度,Atti越大,节点s越倾向于将Di作为下一个目标社区,初始化时所有节点的吸引力向量为0,节点s到达过Di后,则Atti++。

(8)当节点要离开家乡社区时,以80%的概率选择吸引力最大的社区作为移动目标社区,以20%的概率随机选择目标社区,节点到达目标社区后随机选取目标社区中的一个位置作为目的地。

(9)节点移动到目的地后,随机停留一段时间,然后以80%的概率选择回归家乡社区,以10%的概率用吸引力来选择下个目标社区,以10%的概率随机选择下个目标社区。

(10)设置节点回归规则,在规定的周期时间tback点,所有节点停止当前的活动,以90%的概率回归家乡社区,10%的概率留在当前社区。停留tsleep时间后,节点重新选择是否移动以及移动的目标社区,正常运行。

模型工作前采用文献[9]提出的G-N社区发现算法进行社区的划分。

3 消息传递算法

社区模型的消息传递分为社区内和社区间的传递,分别采用不同的路由算法实现。

3.1 社区内路由算法

适当增加消息拷贝数量,合理控制消息转发时机和转发时消息拷贝数量的分配,能够提高消息投递的成功率,降低网络资源的消耗。因此算法采用多拷贝加转发限制的规则,首先确定消息的拷贝份数,然后在节点相遇、消息传递的过程中,将消息按活跃度的比例进行消息拷贝份数的分配,直到遇到目标节点后删除消息的拷贝。

首先,当有消息产生并需要转发时,产生L份拷贝,由式(1)算出

$L=\frac{\text{E}\text{Μ}{}_{\text{o}\text{p}\text{t}}}{\text{E}\text{Μ}{}_{\text{r}\text{w}\text{p}}}(1)$

其中EMopt表示最优消息传输延迟,即消息按理论上的最优路径到达目标节点的传输延迟;EMrwp表示社区内节点的平均相遇时间。通过式(1)可以看出,拷贝份数等于最优传输延迟内社区中节点相遇的次数,这就保证了节点相遇时,即使每次都需要进行一次消息的拷贝,拷贝份数最多也只是最优消息传输延迟内所有节点相遇过的次数,即每个相遇节点都只保存了一份消息拷贝,从而减少了网络的开销。

EMopt的计算方法如式(2)所示[10]

$\text{E}\text{Μ}{}_{\text{o}\text{p}\text{t}}=\frac{C{\rm N}\log {}_2{\rm N}}{2({\rm M}-1)\overline{V}{\rm K}}(2)$

式(2)中,C为经验常数;文献[10]设定为0.34,N表示社区的面积;M表示社区内节点的数量;$\overline{V}$表示节点的平均移动速度;K表示节点的无线射频覆盖范围。

EMrwp的计算方法如式(3)所示[10]

$\text{E}\text{Μ}{}_{\text{r}\text{w}\text{p}}=\frac{1}{pm\overline{V}+2(1-pm)}\frac{{\rm N}}{2{\rm K}\overline{D}}(\overline{{\rm T}}+\overline{{\rm T}}{}_{\text{s}\text{t}\text{o}\text{p}})(3)$

$pm=\frac{\overline{{\rm T}}}{\overline{{\rm T}}+\overline{{\rm T}}{}_{\text{s}\text{t}\text{o}\text{p}}}(4)$

其中,$\overline{{\rm T}}$表示节点平均移动时间;$\overline{{\rm T}}{}_{stop}$表示节点平均停留时间;$\overline{D}$表示节点在一次移动过程中的平均移动距离;$\overline{V}$、N和K同式(2)一致。

此后,当消息携带节点ns移动并与nm相遇时,若nm非目标节点,则利用节点活跃度作为转发时机的判断条件:若ns的活跃度低于nm,认为转发时机成熟,将消息的一部分交由nm进行转发,否则,不进行消息转发。

节点活跃度的确定。首先,如果消息由与目标节点接触频率大的节点进行转发,则消息投递成功率也就大。其次,若一个节点比较活跃,经常遇到社区内其他节点,那么这个节点可以提高消息投递成功率。针对后者,以节点转发消息量作为度量。将以上两个因素作为正反馈效应体现在活跃度的计算中,节点活跃度的计算公式如下

${\rm T}{}_{ij}=\frac{C{}_{i}E{}_{ij}}{{\rm T}{}_{\text{n}\text{e}\text{t}}}+\frac{(1-C{}_i){\rm P}{}_i}{{\rm T}{}_{\text{n}\text{e}\text{t}}}(5)$

其中,Tij表示节点ni到节点nj的活跃度;Tnet表示到目前为止网络运行的时间;Eij表示在Tnet内,节点ni和节点nj相遇的次数;Pi表示在Tnet内,节点ni转发过的消息数量;Ci是经验常数,用来调节节点相遇频率和节点转发过的消息数量这两个因素的比例,这里设定为0.7。Tij越大,表明单位时间内ni与nj相遇的次数越多,并且ni转发过的消息数量越多,即节点i越活跃,其活跃度越高。

社区内消息转发算法如下:

(1)消息源节点ns产生一条到nt的消息,并根据式(1)确定消息的拷贝份数L${}_s^0$,L${}_s^k$表示ns将携带的消息转发过k次后剩余的拷贝数量。

(2)当消息携带节点ni与nj相遇时,若L${}_i^k$>1,nj没有该消息的拷贝,且Tjt>Tit,则ni将该消息复制一份给nj,令$L{}_i^{k+1}=\lfloor L{}_i^k\left(\frac{{\rm T}{}_{it}}{{\rm T}{}_{it}+{\rm T}{}_{jt}}\right)\rfloor ,L{}_j^0=L{}_i^k-L{}_i^{k+1}$。

(3)若L${}_i^k$=1,nj无该消息的拷贝,且Tjt>Tit,则将该消息复制一份给nj,令L${}_j^0$=1,删除ni上该消息的拷贝。

(4)其余情况不转发该消息,直至遇到目标节点,将消息转发给目标节点,并删除本节点上该消息的拷贝。

选取到目标节点的活跃度高的节点转发消息,可以降低消息转发的次数,从而减少网络的开销。在延迟要求相对宽松的机会网络中,可以权衡资源消耗和网络性能之间的关系,在降低网络资源消耗的同时,提高消息传输的成功率。

3.2社区间路由算法

社区间的路由分为两个阶段,首先是找寻目标社区,然后是在目标社区中,找寻目标节点,其中第二阶段由上述方法给出。社区间的消息传输,在查询社区间路由表的基础上,结合判断节点回归的因素。本社区内经常往返于其他社区的节点活动频繁,可以作为社区的桥接节点,来进行社区间消息的转发。为控制网络的开销,在社区间进行传输的消息也需设置一个最大拷贝份数,本文取当前网络中的社区个数C为消息的最大拷贝份数,在最坏的情况下,每个社区有且只有消息的一份拷贝,从而减小了社区间多余的消息拷贝。路由表的结构如表1所示。

表1中,吸引力是对该桥接节点而言的,按照上述社区模型中的规则进行计算,吸引力越大,表明该桥接节点到达目标社区的概率越高。

在基于回归的社区模型下,社区间消息传输的算法如下:

(1)消息源节点ns产生一条消息,确定消息的社区间拷贝份数C,查询路由表。

(2)找到一条社区号与目标社区相同,并且吸引力最高的路由信息,确定桥接节点nb。

(3)将消息在社区内传输,目标节点为nb,消息到达nb后,由nb负责将消息传输到目标社区。

(4)消息携带者ni在寻找nb的过程中,假设ni的社区间消息拷贝份数为L${}_i^k$,若相遇节点nj属于目标社区,则将消息复制一份给nj,并进行判断:若当前时间距离节点回归时间tback大于时间阈值tbback,设置nj该消息的拷贝份数为1,ni的拷贝份数为L${}_i^k$-1;否则设置nj的拷贝份数为L${}_i^k$,删除ni该消息的拷贝。tbback的大小人为设定。当到达时间截点tback时,所有节点将以90%的概率回归家乡社区,此时,选择由即将回归家乡社区的节点将消息带回目标社区,消息传输成功概率比由桥接节点转发消息到目标社区的成功概率大很多。

(5)消息到达目标社区后,采用社区内路由算法进行消息的传输。

3.3 缓存管理机制

对于已经到达的消息,或已经超过其生存周期TTL的消息,文中采用一种文献[11]中描述的缓存管理机制,用来管理系统中过时的消息。

4 仿真及性能评价

本文采用基于Java的DTN仿真工具ONE[12](Opportunistic Network Environment)进行算法性能的仿真,与机会网络的典型算法Epidemic以及现有的基于社区的机会网络路由算法CMTS进行比较。

4.1 仿真环境参数设置

仿真开始时,由于要收集节点相遇信息,所以系统先运行10 min,节点社会度随机生成,tback设置为60 min,tbback设置为10 min,tsleep设置为60 min,Ths设置为20,设置节点的最大缓存消息个数为10个,场景采用ONE中默认的城市地图,主要配置参数如表2所示。

4.2 仿真结果分析

从图1中可以看出,随着TTL的增加,各算法的消息传输成功率不断提升。Epidemic采用洪范的机制,当TTL足够大时,其消息传输成功率接近1。NBR消息传输成功率比CMTS高,这是因为在更加准确地定义了节点移动模型并且重新设计了相应的路由算法后,社区内和社区间的消息传输成功率有所提高,从而使整个网络的消息传输成功率得到了提升。

如图2所示,随着节点最大移动速度的增加,消息传输延迟明显降低。由于Epidemic采用的是洪范的消息传输策略,所以在相同的节点移动速率下,其消息传输延迟最低。NBR的消息传输延迟较CMTS算法低,由于节点会在固定的时刻回归家乡社区,这就使得消息在一定时间内,会以较高的概率到达目标社区,从而降低了消息传输延迟[13,14]。

如图3所示,在相同的TTL时,Epidemic算法中缓存消息的平均个数最低,NBR算法的缓存中消息的平均个数较CMTS低,这是由于系统的缓存管理机制会删除已经投递成功的消息的拷贝,随着消息投递成功率的提高,缓存中已经投递成功的消息会被大量的删除,因此,消息投递成功率越高则缓存中消息的平均个数就越少,所以,结果表明NBR算法较CMTS算法投递成功率高。但随着TTL的增大,消息的存活时间得到了延长,所以缓存中消息的平均个数随之增高[15,16]。

5 结束语

对社区模型下机会网络中节点的移动规则和路由算法进行了研究,提出了一种更加符合现实社会移动规律的节点移动模型,并在该模型下提出了一种社区间和社区内的路由算法NBR。该算法在充分考虑现实可能性的情况下,有效提高了消息传输的成功率,减小了消息传输时延,并且对网络内的冗余消息进行了处理,从而减少了网络资源的消耗,提高了网络的性能。

摘要：当前,基于社区的机会网络研究在模型上还有待完善,在社区间的路由算法没有考虑消息的传输效率,只采用简单的分发等待路由算法,使得路由效率较低。为此,对社区模型进行了改进,加入节点回归因素,并在此模型下提出了新的路由算法NBR。在社区内采用混合路由算法,并加入了正反馈思想重新计算节点活跃度。在社区间采用查询路由表和判断节点回归相结合的方法,利用节点回归的特性提高转发效率。仿真结果表明,在改进后的社区模型下,NBR算法使得社区间和社区内的消息传输成功率得到了提升,有效的降低了网络资源的消耗。

关键词：机会网络,社区模型,路由算法,网络效率

路由模型 篇2

关键词：VLAN,TRUNK,子接口,单臂路由,NAT

1 引言

企业网中随着接入网络的节点数量逐渐增多, 基于二层交换机的小型局域网络就会产生同一网段内网络冲突和冗余的广播信息。为了解决这个问题, 需要在二层交换机上划分虚拟局域网 (VLAN) 。VLAN是目前企业或校园网中应用非常广泛的用来隔离广播域的一种局域网技术, , 通过划分VLAN可以让在同一台交换机不同端口的客户机不能互相访问, 减少了广播风暴的产生。然而, 不同VLAN之间不能直接在二层交换机上实现通信, 如果另行购买三层交换机等设备将是一笔巨大的投资, 本文提出了一种基于单臂路由的VLAN通信模型。

2 网络地址转换 (NAT)

NAT, 即网络地址址转换, 是IP路由协议中的一种。专用地址不能直接在Internet位置进行通信, 必须将该专用地址转换成公用地址, 转换过程如下:

设:内网主机→10.1.10.11;外网主机→2.2.2.1

内网主机 (10.1.10.11) >ping 2.2.2.1

3 单臂路由原理

3.1 Trunk链路

当不使用三层交换机而用路由器进行VLAN间路由时, 若路由器实际与交换机连接的物理端口只有一个, 需将用于连接路由器的交换机端口设为Trunk链接, Trunk链接是在不同交换机之间或交换机与路由器之间的一条链路, 用来同时传输多个VLAN的信息, 不同VLAN的信息通过帧标识机制来标识。常见的主干连接的封装协议有802.1Q协议和ISL协议。ISL是Cisco专用协议, 而IEEE802.1Q标准是国际标准, 当用户使用不同品牌交换机时, 必须要使用IEEE802.1Q。Trunk链路在交换机和路由器之间起着VLAN管道的作用, 同时传输各个VLAN的信息。通过配置, 可以让Trunk链路传送所有或部分VLAN信息。

3.2 单臂路由

在使用路由器时, 为了节约物理端口的使用, 通常在路由器与交换机连接的一个物理端口上定义多个逻辑子端口, 可在逻辑上把它分割为多个虚拟端口, 一个子端口连接一个VLAN, 每个子端口配置相应VLAN内的IP地址, 并封装802.1Q或ISL协议;在交换机上把与路由器相连的端口定义成Trunk端口, 封装与路由器的子端口相同的协议;由于用于VLAN间路由的路由器拥有分别对应各个VLAN的虚拟端口, 从而可以实现不同VLAN间的通信。在这种网络路由技术中, 由于路由器只使用一个端口连接到交换机网络中, 所以称这种技术为单臂路由技术。

4 仿真分析

采用单臂路由技术实现企业网所有用户共享IP和互联网通信, 设计了模拟拓扑图 (如图1) , 给出了路由器、交换机的端口设置和IP地址分配及各自的详细配置命令, 并完成了仿真测试。

4.1 模拟拓扑图

图中有两个网络, 一个是企业内部网;一个是ISP提供的网络即互联网, 两网络已用虚线隔开。

4.2 网络设备端口及终端IP地址分配

如图1所示, 路由器R1 (型号为Cisco3745) 通过F0/0端口与交换机SW (型号为Cisco3640 (模拟switch) ) 的F0/10端口相连;路由器R1通过S1/1端口与路由器R2 (型号为Cisco3745) 的S1/1端口相连。

设企业网中两台PC机PC1、PC2分别处于Vlan10、Vlan20内, 交换机上划分Vlan情况的为:F0/1端口属于Vlan10, F0/2端口属于Vlan20。设Vlan10所在网络为10.1.10.0/24, 网关为10.1.10.254, Vlan20所在网络为10.1.20.0/24, 网关为10.1.20.254。

设R2是互联网中某ISP的一台路由器, 且有一台Web服务器Server其直接与路由器R2的端口F0/0相连。端口及IP配置如表1。

4.3 设备配置命令及解析

根据单臂路由技术实现原理, 进行如下配置以实现PC1、PC2及外网Web服务器Server三台主机之间的通信。为了方便测试, 这里使用的终端设备PC1、PC2和外网服务器Server都是虚拟主机, 其IP及网关配置如表1所示。路由器R1接口配置如图2所示。

为了节省IP, 企业网内部主机使用的是私网IP, 需要在内网与外网的边界上做网络地址转换即NAT, 将私网IP转换成公网IP以访问外网。NAT配置如图3所示。

在交换机SW上创建Vlan10和Vlan20, 配置如图4所示。

此时我们在PC1上Ping一下PC2, 发现Ping不通。也就是说Vlan10和Vlan20不能互访。其原因是VLAN流量没有经过路由器进行转发, 为了实现这个目标, 必须将交换机和路由器之间的链路设置为Trunk链路, 其配置如图5所示。

4.4 结果测试

经过测试, PC1、PC2和Server之间能相互ping通。现以PC1分别ping PC2、Server为例来说明, 测试结果如图6所示。

路由模型 篇3

在传统的ad hoc网络中提出的路由机制是基于节点和节点之间存在着完整的端到端的路径, 而机会网络是一种节点与节点之间没有端到端路径的网络。于是在传统ad hoc网络里提出的路由机制并不适用于机会网络。

目前已经提出了众多机会网络中的路由工作。经典的路由协议有:传染路由[1] (Epidemic routing) 、概率路由 (Probabilistic Routing) [2]及信息摆渡路由[3] (Message Ferry routing) 。信息摆渡路由 (MF) 是指利用一个按照预定路由运动的特殊节点 (称ferry) 来为其他普通节点传输数据。

文献[3]提出了两种ferry路由机制FIMF和NIMF。其中FIMF需要让ferry改变自己的运动轨迹来靠近普通节点以接收信息。NIMF中, ferry按照预定轨迹运动, 而让普通节点改变自己的运动轨迹来靠近ferry以发送数据。这使得普通节点无法正常完成网络的业务。文献[4]中作者提出了几种ferry的路由方案:SIRA, MURA, NRA及FRA。其中SIRA是多个ferry按照同一路径为全网络的普通节点传输数据。MURA则是多个ferry按照各自运动路径, 负责其路径上普通节点的信息传输。而NRA和FRA则是通过中继的方法来完成区间信息的传输。其中NRA是通过在相邻区域间放置中继节点来传输区间信息。而FRA是通过相邻区域间的ferry进行直接通信来传输区间信息的。同样文献[5]给出了利用中继节点的ferry路由设计。

网络中源节点和目的节点在同一区域内的信息为区内信息, 否则称区间信息。本文基于之前工作中提出的适用于实际生活的城乡模型, 并利用ferry和ferry之间直接通信的网络情况下, 统计网络中不同种类的ferry的传输信息总量。这在ferry缓存受限制时, 为了网络不丢包的情况下, 有重要的研究意义。

2 网络模型及假设

2.1 网络模型

在城乡模型中, 乡村围绕城市而建, 如图1所示。整个网络共有N个静止普通节点。中心区域即为城市, 均匀分布N1个普通节点;圆环区域均匀分布N2个普通节点, 且N=N1+N2。对圆环区域进行M等分, 即有M个外围小区域。每个外围小区域即是一个农村, 均匀分布了个普通节点。中心区域有一个中心ferry (称fM+1) 。外围小区域i有一个区域ferry i (称fi) 。中心区域的节点密度大于小区域的节点密度。城市和农村之间的普通节点称为临界点。

fM+1和fi的最短运动路径都是使用旅行商问题 (TSP) 得到的。其中fM+1需经过中心区域内的所有普通节点 (包括临界点) 。fi需经过外围区域i内的所有普通节点 (包括临界点) 。由于中心区域和外围区域内的普通节点都是均匀分布的, 可设中心区域和小区域内相邻普通节点之间的距离分别为1l和l2, 则fM+1和fi (1≤i≤M) 的周期分别为:其中v是fM+1和fi的运动速度。

在之前工作中, 在网络的初始阶段, fi (1≤i≤M) 在临界点i处静止不动, fM+1从某一临界点开始运动。当fM+1遇到fi, 就激活fi, 此后两者同时从临界点i处按照各自轨迹运动。直到fM+1回到最初的临界点, 初始化阶段结束。

2.2 业务模型

本文采用了传感器网络业务模型。将sink节点设在中心区域的某个普通节点处。那么整个网络中所有普通节点产生的信息的目的节点都是该sink节点。设网络中每个节点的信息产生率为λ, 信息大小归化为1。信息传输速率不受限制。

ferry的传输信息量是指在时间内所搜集到的全部信息。

3 区域ferry传输信息量分析

设R是fi在TM+1时间内的传输信息量。fi在外围区域i内按照运动轨迹每绕行一圈, 会访问个普通节点。那么fi在每圈搜集的信息为经过路由调度后, fi需要运行「A」圈后, 在临界点处和fM+1相遇并通信。那么此时fi搜集到的信息量为:此通信的过程中, fi将所携带的信息全部转发给fM+1, 而fM+1并不发送信息给fi。因为所有信息的目的节点是处于中心区域内的sink节点。

4 中心ferry传输信息量分析

设S是fM+1在TM+1时间内的传输信息量。fM+1会从两种节点上搜集到信息。一是从中心区域内的普通节点接收信息, 二是从区域ferry上接收信息。

fM+1在中心区域内按照路径每运动一圈的时间为TM+1。当fM+1到达一个普通节点时, fM+1会从该普通节点处接收到的信息为:=c TM+1⋅λ。由于fM+1每运动一圈, 需要访问N1-1个普通节点。于是在fM+1在TM+1内, 会从普通节点处搜集到信息大小为:

当fM+1到达一个临界点时, fM+1会在临界点处正好和各区域ferry相遇并通信。由于在fM+1运动的一个周期内, fM+1会访问到M个区域ferry。于是fM+1从所有区域ferry处搜集到信息大小为MR。

所以fM+1在TM+1时间内的传输信息量为:

5 数值分析

由上述分析中, 可知在TM+1时间内, fi会接收信息量为R=TM+1⋅λ⋅MN2, fM+1会接收到信息量为:S=TM+1⋅λ⋅ (N-1) 。以下利用MTLAB, 通过改变网络普通节点个数N、普通节点的信息产生率λ、外围区域个数M来研究网络参数对R、S的影响。

为了满足城乡网络中, 中心区域内节点密度大于外围区域的节点密度, 本文假设N=N1+N2, N1=N2, pl1=l2, p>1。为了方便数值分析, 设

5.1 普通节点数目N对ferry信息传输量的影响

设定普通节点的信息产生率为λ=1个/秒, 外围区域个数为M=4。表1显示了在节点的信息产生率、外围区域个数不变的情况下, 随着普通节点数目的增加, fM+1和fi传输信息量逐渐增加。这是因为随着普通节点数目的增加, 外围区域i内的普通节点数目增加, 则外围区域i内的信息总量增加, 所以fi传输信息量逐渐增加。中心网络的普通节点数目增加, 同样, 中心区域产生的信息总量增加, 所以fM+1传输信息量逐渐增加。

从表1中可以看出fM+1的传输信息量远大于fi的传输信息量。这是因为fi只负责该外围区域内的信息搜集, 而fM+1不仅要从fi上搜集信息, 还要从中心区域的普通节点上搜集信息。

5.2 信息产生速率λ对ferry信息传输量的影响

设定圆环区域和中心区域的普通节点个数为:N=1N=240, 外围区域个数为M=4。表2中显示了在普通节点数目、外围区域个数不变的情况下, 随着普通节点的信息产生率增加, fM+1和fi传输信息量逐渐增加。这是因为随着普通节点的信息产生率的增加, 外围区域和中心区域的信息量都增大了。

5.3 外围区域个数M对ferry信息传输量的影响

设定圆环区域和中心区域的普通节点个数为:N=1N=240, 普通节点的信息产生率为λ=1个/秒, 表3中显示在普通节点数目、节点信息产生率不变的情况下, 随着外围区域个数M的变化, fM+1传输信息量没变, 而fi传输的信息量逐渐减少。

这是因为网络内普通节点总数没变化, 外围区域个数增加, 即外围区域i内的普通节点数目减少, 由此外围区域i内的信息量减少, 由此fi传输的信息量逐渐减少。而由于整个网络普通节点数目不变, 到达中心区域的sink节点的信息量没有变化, 所以fM+1传输信息量没变。

6 总结

本文基于城乡模型上, 并利用ferry和ferry之间直接通信的工作方式下, 统计了区域ferry和中心ferry的传输信息量。并利用MATLAB, 通过改变过改变网络普通节点个数N、普通节点的信息产生率λ、外围区域个数M来研究网络参数对ferry传输数据量的影响。数值分析显示了网络参数的配置对区域ferry和中心ferry的影响很明显。

参考文献

[1] A.Vahdat, D.Becker.Epidemic routing for partially-connected Ad Hoc networks.Duke tech report CS-2000-06, 2000

[2] A.Lindgren, A.Doria, O.Schelen.Probabilistic routing inintermittently connected networks.2004-08-05

[3] W.Zhao, M.Ammar, and E.Zegura.A message ferryingapproach for data delivery in sparse mobile ad hocnetworks.ACM MobiHoc2004, 2004, 187-198

[4] W.Zhao, M.Ammar, and E.Zegura.Controlling the mobilityof multiple data transport ferries in a delay tolerantnetwork.IEEE INFOCOM, 2005, 1407-1418

[5] Z.Zhang, Z.Fei.Route design for multiple ferries in delaytolerant networks.WCNC, 2007, 3462-3467

路由模型 篇4

关键词：复杂网络模型,最短路径路由原则,关联系数矩阵,关联强度系数

0 引言

国内外电力系统一系列的大规模停电事故, 引发了电力网络连锁故障与脆弱性的研究。基于复杂网络理论研究电力系统的网络特性, 其首要任务是根据电力系统的特点建立合适的数学模型。然而, 电力网络中线路的长短不能完整的描述节点之间的耦合关系, 所以传统的网络结构度量参数或分析方法在电力系统基本网络模型上的直接应用会与实际情况产生一定的差异。

在模型改进方面, 采用网络中两点之间的自阻抗作为边的权重, 则分别采用电压相对于无功的灵敏度作为边的权重表征节点之间的耦合关系。以上研究考虑了电力网络的整体结构和线路阻抗对于负载传输的影响, 修改了网络模型中边的权重, 然而电网中节点类型差异、分布位置和节点权重亦将影响网络中的潮流分布。

本文从电能传输规律的角度入手, 定义了节点对的输电通道, 提出了电力网络节点的关联系数矩阵, 采用节点间的关联强度作为网络模型边的权重, 将线路阻抗、节点类型差异以及节点权重大小等影响潮流分布的因素引入到边的权重中, 改进了电力系统的网络模型, 使得改进模型更加符合最短路径路由原则的要求。

1 电力系统的基本网络模型

电力系统的基本网络模型主要描述了电力网络的连通特性, 其建模步骤为: (1) 将多回路输电线简化为无向单线边; (2) 对于同一变电站内同一电压等级的母线上节点进行合并; (3) 双绕组变压器等效为一条边, 三绕组变压器等效为变压器三端母线的星型连接。矩阵描述了电力网络的基本拓扑结构, 但是不含有电力系统特性的信息描述。

2 电力系统网络模型的改进

基本网络模型只描述了网架结构的信息, 节点间关联性的描述局限于连通特性层面。因此本文根据电能传输的规律, 为基本模型的边赋予权重, 改进电力系统的网络模型。

2.1 输电通道定义

在单电源、单负荷的情况下, 电能由电源节点产生, 输送至负荷节点, 网络中与电源-负荷节点对相关联的节点和边不仅限于节点对间的最短路径。因此, 本节定义电源-负荷节点对的输电通道用于界定网络中与电源-负荷节点对存在关联性的节点和边。输电通道的定义为:当电流从节点i注入, 由节点j流出时, 网络中会流经电流的所有节点与边的集合, 通道外的节点与边则不会参与该节点对的电能传输。

2.2 关联系数矩阵

为量化通道中节点与通道关联性的差异, 本文提出节点与输电通道的关联系数表征节点与输电通道的关联强度, 关联系数的物理意义为单位电流从节点i注入电力网络由节点j流出时, 网络中节点或边会流经的电流。在大型输电网络中各节点电压之间的差异相对于流经节点电流的差异非常小, 因此节点或边与输电通道的关联系数可以表征单电源、单负荷情况下, 电力网络中节点和边的负载分布。关联系数矩阵中两个列向量的差可以反映网络中所对映的任意类型元素 (任意类型节点或边) 与各个输电通道关联性的相似程度。

2.3 改进的电力网络模型

电能从电源节点产生经由输电通道传输至负荷节点时, 电源节点与负荷节点权重会影响输电通道实际传输电能的大小, 本文将电源节点权重和负荷节点权重中较小的值作为输电通道的权重, 并将带通道权重的欧氏范数作为邻接的节点与边之间的关联强度系数。

3 算例分析

为验证改进模型的有效性, 本文针对EPRI36、IEEE39、IEEE57及IEEE118节点系统建立了基本模型、计及阻抗权重模型以及本文提出的改进模型, 分析了模型改进前后, 网络小世界特性的变化, 并从局部和整体两个方面对比分析了网络结构度量参数对于不同网络的度量结果。

3.1 小世界特性分析

改进模型修改了边的权重, 网络的最短平均距离会发生变化, 为便于模型改进后网络的小世界特性分析, 本文将模型改进后边的权重按照均值做归一化处理, 经过归一化处理后, 改进模型的网络平均距离与基本模型中的平均距离差异不大, 相对于聚类系数间巨大的差异, 平均距离小范围的变化不会导致模型改进后网络的小世界特性发生改变, 经过归一化处理后, 改进模型依然可以用于网络的小世界特性分析。

3.2 中心性度量结果对比

本文选取带权重的介数指标作为度量网络局部中心性的度量参数。同一拓扑特征参数在三种模型中得到了不同的度量结果。基于“最短路径路由原则”类型的指标要求模型中的节点和边具备网络全局的信息。改进模型中边的权重包含了更多的网络全局信息, 因此改进模型中的带权重介数指标与节点负载表现出更强的关联性, 在以有功功率为横坐标、带权重介数指标为纵坐标的双对数坐标系中节点的负载分布为一条直线, 呈幂律分布。

3.3 全局性指标对比分析

不同模型中最短平均距离、网络直径等全局性指标的计算结果表明模型改进前后网络的最短平均距离与网络直径的比值出现了较大差异。系统的稳态潮流分布与改进模型中网络结构的拓扑特征所反映的情况保持一致, 其潮流分布的累计概率接近线性分布。改进模型中L与D比值较小的网络, 其高介数区域的网络结构相对紧密, 网络中会出现更少的高负载节点, 并且具有更高的负载。

3.4 改进模型中电力网络的脆弱性分析

本节采用基于电气介数的故障模型模拟电力网络的故障连锁过程。攻击模式为攻击初始状态下网络中带权重介数指标最高的节点 (即IB模式) 。在改进模型中网络的最大连通比率与断开节点数可以看出, 改进模型中更为紧密的网络中, 即上一节中L与D比值更低的网络, 高负载节点的丢失会导致潮流的大量转移引发大规模的连锁故障, 在遭受蓄意攻击时更加脆弱。

4 结论

本文针对电能传输的规律, 改进了电力系统的复杂网络模型。在保留网络连通特性的基础上更为完整的计入了电力系统特性描述。模型中边的权重可以更加完整的描述节点之间的耦合关系, 其网络拓扑特征反映了电力网络的基本结构和电气属性两方面的异质特性。实验结果证明, 改进模型中节点的负载与带权重介数指标表现出更强的关联性, 网络全局性指标也可以表征潮流分布的特点, 基于最短路径路由原则的网络结构度量参数和复杂网络特性分析方法可以在改进模型中得到更加准确的结果。

参考文献

[1]魏震波, 刘俊勇, 李俊, 等.基于P、Q网分解的有向加权拓扑模型下的电网脆弱性分析[J].电力系统保护与控制, 2010 (24) :19-24.

[2]倪向萍, 梅生伟, 张雪敏.基于复杂网络理论的输电线路脆弱度评估方法[J].电力系统自动化, 2008, 32 (4) :1-4.

路由模型 篇5

在无结构P2P网络中, 针对其搜索效率低下的问题提出了很多改进的算法, 如yang的APS, 这些算法的目标是使搜索的平均延时 (往往以跳数来衡量) 尽可能的小并且开销要小, 但是这些搜索算法都没有考虑到P2P系统中的负载不均衡导致网络某些链路出现拥塞或者“热点”现象。在网络搜索过程中, 查询消息在节点间的延迟是由三个方面组成的, 即节点间的传输延时、消息在节点中的排队等待时间和消息的处理时间。一旦网络负载不均衡则会在部分负荷较重的节点上出现消息滞留排队或丢包的现象, 导致查询延时增大, 搜索效率降低, 严重的还能使节点停止工作网络瘫痪。而引起负载不均衡的原因主要有以下几点:1) 节点能力的异构性。由于P2P系统中节点加入的随意性, 使得网络中的节点在接入带宽、CPU计算能力, 磁盘和内存空间等方面存在许多的异构性。节点能力的不同导致节点对消息处理的效率存在明显的差异, 能力强的节点能够处理更多的消息而能力弱的节点相对来说更容易产生滞留排队的倾向。2) 节点共享文件的差异较大。每个节点共享文件的内容和数目都不一定相同, 共享的文件越流行数目越多, 其被访问的概率也越大。3) 查询分布的不均衡。研究发现, P2P系统中的查询请求分布服从Zif分布定律, 各关键字查询的概率存在数量级差异, 承载热点文件的结点负载将远大于其他结点.节点之间的负载及不均衡。

为了改善网络性能, 充分利用网络的传输能力, 人们必须要在设计无线自组网路由协议时考虑负载均衡问题。做到在新的路由建立过程中, 避开负载较重的节点或者区域, 使得网络业务流尽量从负载较轻的区域穿过;在数据沿路由传送过程中在遇到负载较重或者部分区域拥塞时有相应的机制进行处理。避免网络的部分区域的节点会由于承受较大的网络负载而产生网络拥塞, 而部分区域的节点则会因为中继任务少而处于相对轻闲的状态, 导致网络负载失衡。负载均衡的实质, 是利用网络中可能存在的不同分组传输路径来构建分组的实际传输路由, 通过有足够剩余容量的节点转发分组, 以减轻网络的局部拥塞, 适应网络中负载的动态变化, 尽可能减少分组丢失和提高网络吞吐率, 为业务提供更好的Qo S保证。

针对大部分搜索算法均未考虑到节点负载均衡的不足, 本文提出一种负载均衡的路由模型并在此基础上实现搜索算法。本文设计的搜索算法的目标是在提高系统吞吐率的基础上最大化资源利用率、尽可能减少平均搜索延迟, 并且网络开销要小。

1 相关工作

在P2P网络中, 为了提高搜索效率提出了各类高效的搜索机制, 即盲搜索算法和基于知识的算法。盲搜索算法是针对基础的洪泛和随机漫步搜索算法的优化。由于采用洪泛搜索机制的P2P系统会产生70%的冗余消息, 文献[1]提出一种轻量级的洪泛机制在保证有相似搜索范围的同时能够将查询消息的数目降低69%。文献[2]将洪泛和随机漫步交替使用, 短路径搜索使用洪泛而长路径搜索使用随机漫步。文献[3]对网络中节点最感兴趣的共享文件和全局最不流行的共享文件建立部分索引帮助节点找到兴趣相似的节点, 加速定位不流行的文件, 显著提高了搜索成功率和命中率。文献[4]中的节点根据缓存内容来计算节点之间的语义相似度并提供一种全分散的方法来评估文件的流行性, 在真实的e Donkey上验证了方法的有效性。文献[5]基于概率理论框架构建了用户兴趣模型UIM, 在此基础上通过开采用户的通用兴趣设计搜索协议和路由表更新协议, 并进一步将P2P网络呈现小世界的特性。虽然这些算法都能够从理论和实验上证明其能够获得更好的性能, 如获得更高的搜索成功率、命中率, 更少的搜索评价延时更少的开销等等, 但是其假设的前提是网络的状况是良好的, 节点之间的负载是均衡的不会发生拥塞, 而网络拥塞是不可避免的, 因为节点的能力是有限的, 一旦发送消息的速率超过节点的处理速率就会产生拥塞, 而拥塞的后果有两种:一种是造成排队现象。一旦大量的消息在节点排队等待处理, 就会大大增加消息延迟, 那么在以前的评价标准中, 消息在每跳间传播的延时赋予固定数目的计算方法在网络发生拥塞时就不准确, 消息在拥塞节点上消耗的时间会更长。另一种是产生丢包现象。节点过度拥塞会丢弃部分消息, 导致搜索成功率和命中率的下降。而提高搜索效率和达到网络负载均衡往往是相互矛盾的。为了尽快的找到搜索目标, 查询消息在路由转发时根据经验 (如节点兴趣相似性, 命中率等) 往往选择最可能找到目标文件的节点进行转发以获得更短的搜索平均跳数, 为了达到负载均衡, 节点转而会选择负载较轻的节点进行转发消息, 但是这样的转发路径往往不是最短路径, 因此, 需要在搜索效率和负载均衡之间达到一种平衡, 希望提出的搜索算法不仅能获得好的搜索效率同时能够保持节点间的负载均衡。

2 方法

2.1 系统模型、定义和说明

定义一:P2P网络。P2P网络表示为无向图G= (V, E) , 其中V是网络中节点的集合, E是边的集合。对于网络中的任意节点u∈U, v∈V, 如果 (u, v) ∈E则必有 (v, u) ∈E。对于任意节点u∈V, 其邻居集合记为Nu={v| (u, v) ∈E}。

定义:P2P搜索模型。假定p是网络中的一个节点, p上共享文件的集合为pF, 对于pF中的任一文件有fPF。从P节点发起的一个查询记为qp, 以p, f, hq, ttl表示。其中f代表要查询的文件, qh记录一个查询消息在查询结束之前所访问过的所有节点, 显然, qh的尺寸不会超过TTL。

定义:节点的命中率hi。假定系统总共发起了N次查询, 节点i的命中次数为Hi, 则节点i的命中率为

定义:节点的能力iC。P2P网络中节点的能力是与很多因素相关的, 如CPU处理能力, 节点的存储能力、带宽等等。将节点i的能力标记为iC。

通过对Gnutella系统的观察发现, 节点的负载主要由三部分组成:

1) 节点的维护负载。每个节点需要周期性的通过ping/pong消息对连接进行维护, 处理节点的加入离开, 和缓存表的维护。

2) 节点的查询负载。每个节点都能够接收查询消息并处理它们。

3) 节点的响应负载。一旦节点命中查询, 节点会发送响应消息沿原路返回。

这三部分负载产生的消息长度是不一样, 其中, 维护消息的长度最大, 响应消息的长度其次, 最短的是查询消息。

定义:节点的负载iL。节点的负载是维护负载、查询负载和响应负载三部分的加权和, 其权值分别设为wm, wr, wq, 并且wq<wr<wm。假定单位时间T内节点维护负载的数目为Nmain, 查询负载的数目为Nquery, 响应负载的数目为Nres, 则节点的总负载Li为

2.2 负载均衡搜索算法

在P2P网络中设计负载均衡路由协议的目的是在路由过程中避开负载较重的节点, 使得查询消息的路由尽量从负载较轻的区域穿过, 从而能对网络的业务量进行调度, 充分利用网络容量, 减轻网络局部拥塞, 提高网络处理性能。在路由设计过程中应该重点关注两个关键技术:一是网络节点的负载探测技术;二是路由技术。前者告诉我们网络中节点的负载情况是什么样, 后者关注的是在网络负载情况已知的情况下如何实现负载均匀的查询消息路由。

2.2.1 负载探测技术

节点的负载状况和节点的度以及邻居节点的活跃度、负载状况有关。

节点的活跃度:如果网络中该节点正在通信, 则节点是活跃的, 其活跃度为1, 否则为0。活跃节点可以是源节点, 目的节点或者中间转发节点。

假定节点u的度为d, 则节点u在时刻K其邻居节点负载估值为

节点的总负载开销Lu (k) =Lu (k-1) ×a+Tu (k) × (1) , 其中是平滑因子, 且01。

定义:节点的剩余负载RiCiLi。

2.2.2 缓存机制

每个节点保存两个表, 一个是缓存表, 一个是邻居节点列表。

节点的缓存表内容如下:

为了节省网络开销防止缓存表无限增长, 我们为每个节点设定固定大小的缓存空间。假设其存储节点的条目上限为R。当插入到节点的条目超过此上限时, 我们可以使用LRU算法删除条目。

节点的邻居列表内容如下:

2.2.2 改进的转发机制

本文所采用的转发机制是采用随机漫步式的转发, 但不同的是节点在每跳转发时随机漫步的个数K是动态变化的, K的取值与邻居节点的命中率和负载状况相关, 分为如下几种情况。

1) 所有邻居节点的剩余负载Ri>Rmin, Rmin是门限值。

在这种情况下, 所以的节点都有能力接收新的查询。则K的值等于邻居节点命中率中大于阈值Pmin的个数。

2) 部分节点的剩余负载大于Rmin。

邻居节点已经有一部分达到饱和状态, 已经来不及处理新的消息, 这时查询消息就不再发往这些饱和的节点, 则K的值等于邻居节点中未达到饱和并且其命中率大于阈值Pmin的个数。

3) 节点的剩余负载均小于Rmin。

由于所有的节点都达到饱和状态, 则K=1, 随机选择下一跳节点进行转发。

负载均衡的查询算法如下。

当节点p接收到一个查询时, 它将做以下基本操作:

(1) 将自己添加到hq中。

(2) 在本地搜索文件f。

(3) 转发查询到它的一个邻居节点集K。

节点先在本地搜索目标文件。节点在自己的共享文件和缓存表里查看有没有文件f, 如果有, 则搜索成功。否则在邻居列表中选择节点集K进行转发。

参考文献

[1]Song, J., et al., Light Flood:Minimizing Redundant Messages and Maximizing Scope of Peer-toPeer Search.Parallel and Distributed Systems, IEEE Transactions on, 2008.19 (5) :p.601-614.

[2]Tsungnan, L., et al., Dynamic Search Algorithm in Unstructured Peer-to-Peer Networks.Parallel and Distributed Systems, IEEE Transactions on, 2009.20 (5) :p.654-666.

[3]Rongmei, Z.and Y.C.Hu, Assisted Peerto-Peer Search with Partial Indexing.Parallel and Distributed Systems, IEEE Transactions on, 2007.18 (8) :p.1146-1158.

[4]Yann, B.and K.Anne-Marie.PROXSEM:InterestBased Proximity Measure to Improve Search Efficiency in P2P Systems.in Universal Multiservice Networks, 2007.ECUMN‘07.Fourth European Conference on.2007.

路由模型 篇6

无线自组网 ( Ad Hoc Network) , 也被称为多跳无线网 ( Multi -Hop Wireless Network) , 是由一组带有无线通信收发装置的移动终端节点组成, 是一个多跳的临时性无中心网络, 可以在任何时刻、任何地点快速构建, 不需要现有信息基础网络设施的支持, 网中的每个终端兼有路由器的功能, 可以自由移动, 各节点的地位相等。

无线自组网结合了移动通信和计算机技术, 其网络结构和通信机制明显区别于其他固定网络。节点的无线通信性质决定了其具有强大的自组 ( Self Organization) 性能。无线自组网络具有几个显著的特点: 1动态变化的网络拓扑结构; 2无中心网络的自组性和分布式控制; 3多跳组网方式; 4有限的无线传输带宽。

由于移动自组网具有主机能源受限和动态拓扑的特点, 这使得一些常规路由协议都无法在该环境下正常工作, 如RIP等。由于路由协议是影响网络性能的一个重要因素, 目前对自组网的研究主要集中于对自组网中路由协议的研究。面相需求式路由是该环境中路由协议的主要发展方向, 本文通过几种协议的实验分析, 也为面向需求式路由提供了参数支持。

2 Ad hoc 无线网络路由协议

目前, 移动自组网中路由协议的最常见分类方式是基于路由发现策略的角度, 将路由协议按驱动方式分为表驱动路由和按需驱动路由两种协议类型, 如图1所示。

2. 1 表驱动路由协议 ( Table Driven)

在表驱动路协议中, 网络内任一节点都保持一个到其它节点相对稳定的最新路由表。其路由发现策略与传统路由协议类似, 节点通过周期性广播路由信息分组来实现路由信息交换, 并主动发现路由。同时, 节点必须维护到达全网所有节点的路由。这类协议的优点是当节点需要发送数据分组时, 只要到达目的节点的路由存在, 所需的延迟就很小, 满足QoS的需求。缺点是需要花费较大的开销, 网络动态变化的拓扑结构可能使这些路由更新变成过时的信息, 使路由协议始终处于不收敛状态。

DSDV ( Destination Sequenced Distance Vector) 协议使用目的端顺序号来避免因使用过时路由信息或产生无效路径 ( 路由环路) 。它是一个基于传统Bellman -Ford算法的路由选择协议, 通过对路由编号等措施来避免路由环路的产生。在该协议实现过程中, 节点周期地向邻居节点广播一个报文, 报文内容为节点路由表或表中发生改变的表项, 相关节点根据收到的报文更新路由表。这种协议的优点为利用目的端顺序号来避免出现路由环路, 同时通过使用触发性路由更新, 在网络链路状态改变时收敛较快。缺点是周期的广播报文增大了网络开销, 不适应变化速度快的移动自组网络, 且不支持单向信道。

2. 2 源发式面向需求路由协议 ( Source - Initiated On - demand)

与表驱动路由相反, 面向需求的路由认为在动态变化的移动自组网络中, 没有必要维护到达其他所有节点的路由。它仅在移动主机节点有需要时才建立路由, 且仅在通信过程中才维持路由, 通信完毕后路由将被拆除。一般说来, 面相需求路由包括三个过程: 路由发现, 路由维持和路由折除, 各协议的不同之处主要体现在这三个过程当中。

DSR ( Dynamic Source Routing) 协议是最早采用面相需求路由思想的路由协议。它使用了源路由, 且在每一个分组的分组头中包含整条路由的信息。该协议包含路由建立与路由维持两个阶段, 在路由发现阶段采用洪泛法。为减少路由发现过程的开销, 每个节点都包含一个路由缓存Cache, 存放己有路由信息。路由维持过程是源节点用来检测网络拓扑是否发生变化的机制。当拓扑结构发生变化, 源路由产生中断时, 源节点将收到一个路由错误信息, 并通过查找Cache中信息获得新的路由。如果不通, 则重新启动路由寻找过程。这种协议的优点是中间节点不必存储转发报文所需的路由信息, 而改由分组自己携带。因无周期性的广播操作, 减少了网络开销。缺点是在数据流突发性较强的情况下可能会带来较大的丢失率。

AODV ( Ad Hoc On Demand Distance Vector简称AODV) 协议是一种改进的距离向量路由协议, 它建立在DSDV协议基础上, 通过使用目的端顺序号避免产生无效路径。它并不维持一个路由表, 而是在需要的时候才启动路由选择过程, 因而大大降低了路由维持的开销。事实上它是DSDV协议和DSR协议的组合, 借用了DSR中路由发现和路由维持机制, 利用DSDV中hop - by - hop路由、顺序编号和周期更新的机制。优点是使用目的端顺序号可以避免路由环路, 而面相需求方式又减少了网络开销。缺点是该协议是基于双向链路的假设, 当出现单向链路时将产生无效路径, 同时周期性广播hello信息, 具有较大的网络开销。

3 典型 Ad Hoc 网络协议的 NS 仿真模型

NS ( Network Simulator简称NS) 起源于早在1989年的REAL. 网络模拟器。NS具有开放的结构和良好的可扩充性, 使NS从各个方面吸收了丰富的模块, 包括支持无线通信网络的代码。作为一个被教育、研究行业广泛应用的网络仿真软件, NS具有几个显著特点:

( 1) NS使一个离散事件模拟器。NS的核心部分是一个离散事件模拟引擎。NS中有一个“调度器”类, 负责记录当前时间, 调度网络事件队列中的事件, 并提供函数产生新事件, 指定事件发生的时间。

( 2) NS具有丰富的构件库。针对网络仿真, NS已经预先做了大量的模型化上作。NS对网络系统一些通用的实体已经进行了建模, 这就是NS的构件库。用户可以充分利用这些已有的对象, 进行少量的扩展, 组合出所要研究的网络系统的模型, 然后进行网络仿真。

( 3) NS采用了分裂对象模型。NS的构件库是用两种面向对象的语言编写的: C++和Otcl ( Object toolkitcommand language简称OTCL) 。NS中的构件通常都作为一个C++ 类来实现, 同时有一个Otcl类与之对应。用户通过编写Otcl脚本来对这些对象进行配置、组合, 描述模拟过程, 最后调用NS完成模拟。

( 4) 开放的源代码。NS是免费的, 开放源代码的。这使得利用NS进行网络模拟的研究者可以很方便地扩展NS的功能, 也可以很方便地共享和交流彼此的研究成果。NS吸纳了这些NS开发者贡献的各方面的模块, 从而使它的构件库不断地丰富, 这正是一个好的网络模拟器的生命力之所在。

( 5) 支持多跳的无线网络。Monarch研究小组用NS2实现了对多跳无线网络的物理层、链路层以及介质访问控制 ( MAC) 层的仿真。IEEE 802.11的分布式合作功能 ( DCF, Distributed Coordination Function) 被成功应用于MAC层协议, 载波侦听多路访问和冲突避免 ( CSMA/CA, Carrier Sense Multiple Access with CollisionAvoidance) 技术用于数据分组的传输。

3. 1 实验测试的性能参数

本文就以下两个方面的性能进行仿真实验和协议分析:

( 1) 数据分组传输效率 ( PDF, Packet Delivery Fraction) , 也称为数据分组投递率。即目的节点接收到的分组数量与发送的分组数量的比率。

( 2) 端到端的数据分组的平均延迟 ( Average end -to -end delay of data packets) 。包括路由发现过程中数据分组在缓冲区的滞留时间、在接口队列 ( Interface Queue) 等待发送时的排队等候时间、MAC的重发延迟、无线电波传输时间等所有时间的总和。

3. 2 实验仿真场景的建立

为了对DSDV、AODV以及DSR网络协议进行比较, 我们需要在同样的场景下对网络协议进行仿真。本文设定的仿真环境是在一个随机方位 ( random waypoint) 背景下的500×500m的矩形区域, 内设50个网络节点, 节点最大移动速度为20m/s, 暂停时间 ( pause times) 可选0, 10, 20, 40, 100s, 整个仿真运行的时间为100s。环境设定的源Tcl代码列举如下:

3. 3 随机文件的生成

( 1) 生成随机数据流文件。在无线移动节点之间建立TCP或CBR ( Continuous Bit Rate) 随机传输速率的数据流连接是通过一个数据流生成脚本实现的, 该脚本可以在 ~ ns/indep - utils/cmu - scen - gen目录下获得, 文件名是cbrgen. tcl, 脚本命令格式如下:

本实验设定节点数为50, 数据流类型为CBR, 网络最大的连接数目可选10, 20, 30, 40, 速率为每秒钟发送4个长度为512字节的数据分组。生成的数据流场景保存在cbr -50n -10c -4p文件中。

( 2) 生成随机场景文件。NS提供了setdest工具用来随机生成无线网所需要的节点运动场景。setdest在 ~ns/indep -utils/cmu -scen -gen/setdest目录下。使用setdest命令的格式为

本实验设定的节点数为50, 暂停时间可选0s, 10s, 20s, 40s, 100s, 节点最大移动速度为20m/s, 拓扑区域为500m×500m, 仿真时间设定为100s。场景输出文件为temp1。

3. 4 TRACE 文件和 GAWK 算法

通常要在Otcl脚本中设定trace文件以便做trace分析。语句格式如下:

编辑好的Otcl文本文件是被ns仿真器解释执行的。在执行过程中生成trace数据文件, 详细记录了仿真的全部过程。下面是一条典型的修订版 ( New Trace Format) 的无线移动网络的trace记录格式:

s - t 0. 267662078 - Hs 0 - Hd - 1 - Ni 0 - Nx 5. 00 - Ny 2. 00 - Nz 0. 00 – Ne - 1. 000000 - Nl RTR - Nw - - - Ma 0 - Md 0 - Ms 0 - Mt 0 – Ii 20 - Is 0. 255 - Id - 1. 255

该记录表达的含义是: 一个数据分组在0. 267662078这一时刻由节点0 ( 本节点) 发送到节点1 ( 下一跳) 。本节点的id是0, 发送时的位置坐标 ( 5.00, 2.00, 0.00) , 功率水平为1.000000, traced的“层”为RTR, 节点“事件原因”为“空白”。MAC层的信息包括, 持续时间为0, 目的节点和源节点的以太网地址都是0, 以太网类型标记为0。IP包的信息包括, IP包的id为20, 发送该分组的源节点的IP地址是0, 端口号为255, 接收该分组的目的节点的IP地址是1, 端口号为255。

得到trace文件后, 需要编写gawk程序在trace文件中提取有用的信息来计算分组传输效率PDF。是程序中关键的两句:

计算脚本格式中发送的分组数量 ( sent packets) :

计算脚本格式中接收到的分组数量 ( received packets) :

通过以下的公式计算分组传输效率PDF:

packet delivery fraction ( pdf % ) = ( received packets / sent packets) × 100%

3. 5 协议的性能分析与比较

为了便于比较协议在Ad Hoc的性能差异, 将得到的数据通过Excel作出图形。

图2和图3显著描述了DSDV、AODV、DSR三个协议的性能差异。一个突出的特点是, 在节点几乎不移动 ( pause time =100) 的时候, 三个协议的PDF都接近100%。对于移动节点的PDF, 面向需求路由协议有着明显的优势, 在各种运动速率之下, 其传输效率都超过了85%。

对于分组的端到端的传输延迟, AODV表现出优越的特性, 延迟时间低于DSDV和DSR。

由于节点的高速移动 ( 较小的pause times) , 导致无线链路容易断裂, 但由于各个协议的机制不同, 对链路断裂之后, 如何继续路由的处理方式不同, 从而使各个协议表现出不同的性能。在节点高速移动的时候, DSDV的分组传输效率降低到了70% , 几乎所有丢失的分组都是因为路由表没有来得急反映出链路断裂情况, 继续在断裂的链路上路由而产生的。DSDV只维护了一条到目的节点的路由, 一旦链路断裂, 没有其他的可选路由, 从而造成了数据分组的大量丢失。

对于DSR和AODV, 在节点的所有运动速率情况下, 分组传输效率都达到了85%以上。因为协议所采用的面向需求路由机制, 使它们自身有更好的适应能力, 在分组传输效率和分组延迟都表现出良好的性能。对于AODV而言, 链路断裂触发了新的路由发现机制, 因为AODV并不保存多条路由信息, 所以启动路由发现的次数与链路断裂的数目成正比。相比之下, DSR的反映要缓慢一些, DSR并不急于启动路由发现机制, 而是首先在源节点的缓存搜索备用的路由信息, 如果没有发现, 才启动路由发现机制。但对于高速移动的节点, DSR节点缓存的路由信息很快就会变得陈旧, 当DSR启动路由发现机制的时候, MAC的开销会因为大量的应答信息的到来而增大, 这两个原因最终导致DSR在面对高速移动的节点通信时, 性能大打折扣。

4 结束语

本次实验使用NS2仿真软件分析比较了DSDV、AODV和DSR三个协议在移动无线网络中的性能。DSDV采用的是表驱动方式, 而AODV和DSR都是面向需求的路由方式。在高速移动的仿真场景下, AODV和DSR表现出更为出色的路由性能。由于节点的高速移动, 导致链路频繁断裂, 为了获得新的路由信息, DSDV显然开销要大的多。

虽然DSR和AODV都是面向需求的路由, 但发现路由的机制两者是不同的。特别地, DSR采用了源路由和路由缓存, 不需要周期性地发送路由信息, DSR的缓存为每个目的节点都保存多条路由信息。AODV采用路由表, 只为每个目的节点保存一条路由信息, 同时, 为了防止环路和判断最新的路由, AODV也保存了目的序列号。从仿真的效果看, 在面向应用的一些特性上, 如数据分组传输效率和传输延迟, AODV较DSR表现更为突出。原因在于DSR过分依赖其路由缓存, 在多种路由选择的情况下, 缺乏一个有效的机制判断路由的新旧。但不可否认的是, DSR缓存为减少路由负载起到了积极作用。

参考文献

[1]C.E.Perkins and P.Bhagwat, Hionhly Dynamic Destination-Sequenced Distance-Vector Rout-ing (DSDV) for Mobile Computers[J].Computer Communications Review, 1994, (10) :234-244

[2]Johnson D B.Routine in Ad Hoc networks of mobile hosts[A].Proceedings of Work shop on Mobile Computinn Systems and Applications[C].1994.158-163

[3]朱西平, 兽荣波, 李宗寿, 李方军.基于NS2移动自组网路由协议性能评价的仿真实现[J].中南林学院学报, 2004 (2) .