基于节点运动的机会网络路由算法∗

张棋飞,桂 超,宋 莺,孙宝林,戴志锋

(湖北经济学院 信息与通信工程学院,湖北 武汉 430205)

机会网络是一种在通信链路间歇式连通状况下,利用节点移动带来的接触机会实现数据传输的自组织网络[1].作为一种新兴的网络形态,机会网络面临着许多在传统网络环境中不曾遭遇的困难和挑战[2],其分组路由问题更是引起了研究者的极大关注[3−5].机会网络路由机制基于节点间链路间歇式连通状况,利用节点移动带来的接触机会实现数据转发[6].在没有找到合适的下一跳节点前,节点携带数据并等待连接机会,如图1 所示.在t1 时刻,源节点S与目标节点D分别位于两个不连通的子区域,在它们之间无法建立起一条完整的传输路径.于是,S将数据转发给自己的邻居节点B,由B携带该数据在t2 时刻转发给下一跳节点E.最后,在t3 时刻,节点E将数据交付给最终的目标节点D.

Fig.1 Illustration of routing in opportunistic networks图1 机会网络路由示意图

机会网络采取数据捎带转发模式,即节点在自由运动过程中寻找机会转发数据,其运动轨迹一般不受所携带数据的影响.这种方式维护了节点的独立性,却给数据传输带来一定影响,导致投递率降低,传输时延增加.我们认为:针对不同的通信需求应该采取不同的传输策略,尤其对那些具有较高传输要求的应用更应如此[7].在某些情况下,应该允许节点牺牲运动独立性,调整运动轨迹,以构建快速、稳定、有效的通信连接.同时也应该看到:运动轨迹的调整必然会改变节点的运动状态,对原有的任务调度造成影响.因此需要综合考虑节点的任务调度以及数据转发需求,设计节点的运动转发机制,实现数据的有效转发.本文第1 节介绍典型的机会路由协议.第2节设计基于运动的机会路由算法.仿真实验结果在第3 节给出.最后一节总结全文.

1 相关工作

机会路由的初衷是为了满足稀疏移动环境下的自组织网络通信要求[8].经过多年的发展和完善,目前已成为实现间歇式连通环境下数据收集与内容共享的一项重要技术.根据消息的传输策略不同,可以将机会网络路由协议分成3 类[1]:基于副本的路由、基于主动运动的路由以及基于效用的路由等.

(1) 基于副本的路由

基于副本的路由策略通过在网络中产生一定数量的消息副本提高目的节点接收消息的成功率,可分为单副本传输和多副本传输.Direct Transmission[9]采用单副本传输策略,源节点缓存消息直到遇到目标节点.每个数据包只传输一次,且没有其他副本,网络开销最小,但时延大,分组投递率低.多副本传输基于洪泛策略,又可分为全网洪泛和部分洪泛.Epidemic Routing 采用全网洪泛机制,为每个节点维护一个摘要向量,存储本地的分组消息列表.节点相遇时,通过交换摘要向量获得新的消息.消息以洪泛方式在全网快速扩散,最终抵达目标节点.如果资源条件允许,可以找到一条最短路径从而获得较低时延.然而由于副本数目太多,会给网络带来巨大开销.2-Hops[9]算法采取了部分洪泛策略,通过将消息拷贝给最先遇到的n个中继节点,限制消息只在两跳范围内传输,从一定程度上避免了冗余信息过多的问题.Spray &Wait[10]同样采取部分洪泛策略,源节点定义分组在Spray阶段被转发的最大次数,每个收到该副本的节点按照一定比例将副本转发.一旦副本数目减少到1,则进入Wait阶段,节点携带副本直至遇到目标节点.

(2) 基于主动运动的路由

基于主动运动的路由机制通过引入部分能够实现主动移动的特殊节点,来为其他普通节点提供通信服务.DataMULEs[11]引入了MULE 节点,在移动过程中收集传感器数据,实现稀疏传感器网络环境下的数据采集.Message Ferrying[12]协议在区域内部署Ferry 节点,按预定义路径或普通节点的通信请求,在移动过程中实现数据的转发.Zhao 等人[13]在Message Ferrying 的基础上,提出使用多个Ferry 节点以提高系统的可靠性和传输效率.

(3) 基于效用的路由

基于效用的路由策略通过引入效用值评估选择合适的下一跳节点,避免消息的盲目转发.PQBCF[14]算法设计了一个中间中心度指标,用来描述节点在信息传输过程中的参与度和重要度.Zhao 等人[15]从延长网络存活时间的角度出发,提出了一种差分概率转发机制,以节点的剩余能量为度量设计转发策略,以最大化网络生存时间.SMART[16]协议通过在邻居节点之间交换朋友关系,将节点接触概率的计算放在发送端进行,降低节点间信息交换次数.PeopleRank[17]协议基于经典的PageRank算法分布式计算节点中心度,降低传统社会化网络分析方法的复杂性.BUBBLE[18]协议考虑节点的社会地位,对节点进行聚类后,利用节点所在的社区信息及中心度信息转发数据.SCOR[19]算法利用网络中的社会上下文信息,通过BP 神经网络模型预测节点的移动行为.针对机会网络数据转发模式带来的较为严重的流量分配不公以及投递成功率不公问题,FSMF[20]算法引入用户社会关系马尔科夫链模型对用户的社会关系进行评价;同时,为了提高公平性,根据用户的社会关系限制消息副本的数量并限制转发副本的数量.PICD[21]针对节点循环运动的场景,考虑节点与汇聚点间存在间歇多跳路径的情况,将消息容忍的延迟与传输概率的计算相结合,利用节点间的周期间歇连通性改善路由性能.PROPHET[22]协议为网络中的每一对节点计算投递概率,利用接触概率的传递性更新投递预测概率值,实现数据从低概率节点向高概率节点的转移,直至抵达目标节点.TOR[23]算法针对恶意的网络环境设计基于信任机制的路由算法,对参与转发的中间节点进行信任度评估,利用信任广播周期性地将最新信任路由表反馈给其他节点,从而简化传统信任关系评估和传播的复杂性.在消息转发过程中,采用沿着信任度递增的梯度转发,提高转发成功率.

以上路由机制中,基于副本的路由策略通过在网络中生成多个消息副本来保证数据的传输.这种消息的复制对网络资源要求很高,会在网络中产生大量冗余,导致资源浪费.基于主动运动的路由通过引入某些具有移动功能的特殊节点来辅助数据的传输.此类节点往往具有较强的运动能力、通信能力以及存储能力,与普通节点差别很大.而且算法假设目标节点的位置是固定的,并没有考虑到移动节点间的数据通信.而基于效用的路由策略主要利用相遇预测、链路状态以及上下文等信息计算效用值,并没有充分考虑数据传输的不同要求以及节点自身的运动特质对路由的影响.

机会网络的部分概念来源于早期的间歇式连通网络和延迟容忍网络,这两种网络着重强调应用的延迟容忍特性.但随着机会网络研究的不断深入,其内涵覆盖更为广泛,承载的业务类型日渐丰富,数据传输的要求也越来越多样化.在这种情况下,如果还是按照传统模式依靠节点随机运动带来的有限连接机会来传输数据,势必无法满足应用多样化的传输需求[7].既然机会网络是利用节点移动带来的接触机会传输数据,就应该充分利用节点的运动特性更好地为数据通信服务.某些情况下,为了满足应用的要求,甚至可以牺牲节点的独立性来保障传输的质量.我们知道,机会网络中的节点在运动过程中寻找转发机会,正是节点的运动为数据交换提供了可能.运动独立性从运动的角度反映了节点保障传输任务的能力.一般来说,当前传输任务的优先级越高,节点的运动独立性越强,在传输过程中越不易受到外来任务的干扰.节点的任务调度按照优先级顺序从高到低依次执行.当节点承担的新的传输任务优先级高于其原有的任务调度时,应该牺牲节点的运动独立性,将其原有任务暂时挂起,通过调整节点的运动路线来保障高优先级任务的执行.基于此,本文研究机会网络路由机制的关键技术,以机会网络的运动特性为切入点,以提高分组路由性能为基本目标,从应用的需求及网络资源的调度出发,设计了基于运动的机会路由算法MBOR(motion based opportunistic routing),通过调整节点的运动轨迹,在满足不同数据传输要求的同时提高分组投递率,降低传输时延.

2 MBOR 路由算法

2.1 数据传输机制

数据在路由到目的地的过程中,一般要经历中继转发和直接交付两个阶段.通常而言,为了获得稳定的数据传输质量以及较低的分组延迟,往往要求参与转发的节点数目越少越好,最好能够直接交付[24].尤其对于机会网络这种在源节点和目的节点之间可能都不存在一条完整传输路径的情况,采取直接交付更为可靠.然而数据的直接交付是有前提的,即数据携带节点与目的节点之间是可以构建直连通路的,而这恰恰是多数网络环境所不具备的.由于传统网络采用了存储-转发的数据交换方式,对于那些无法实现直接交付的节点,只能通过寻找合适的下一跳,将数据中继转发至目的地.而机会网络独有的存储-携带-转发方式给了我们一个新的选择,节点可以携带数据直至直接交付.也就是说,机会网络可以允许节点在无法实现直接交付的情况下继续携带数据,直至完成直接交付.

采用直接交付方式固然可以提高分组投递率,提升传输可靠性,但使用不当也会带来不利影响.尤其网络中可能存在无法实现直接交付的情况,此时若强行采用直接交付,只会恶化网络性能.因此,数据的传输必须遵循一定规则.本文从数据传输的角度出发设计数据转发优先级评价模型,同时结合节点活动区间划分方案,设计机会网络环境下的数据传输规则.

2.1.1 数据转发优先级评价模型

为了适应不同的应用需求,结合机会网络自身弱连接、间歇性通信的特点,构建数据转发优先级评价模型对待传数据进行分类,使数据的传输同网络资源的调度以及应用的需求更好地进行匹配.数据转发优先级是节点在处理数据传输时决定数据被转发的优先等级,节点根据优先级的大小对数据采取不同的转发策略.

影响数据转发优先级的因素包括数据的传输、数据的内容以及应用的要求.我们认为:数据转发优先级与数据内容的重要程度成正比,与参与传输的节点链优先级成正比,与应用的时延要求成反比.基于此,定义数据转发优先级(data forwarding priority,简称DFP)函数为:

其中,m代表数据,γ表示从源节点s到当前节点i的传输节点集合,Bm,Lm和Gγ(s,i)分别代表内容优先级、时延优先级和节点链优先级.其中:内容优先级从信息内容的角度反映数据的重要性,体现不同内容的差异价值,可分为普通信息(ordinary information)、重要信息(important information)和重大信息(major information),优先级依次递增;时延优先级体现应用对传输时延的要求,可分为尽力而为传输(best effort delivery)、加急传输(urgent delivery)以及紧急传输(critical delivery),紧迫性依次递增;节点链优先级代表参与数据传输的节点的优先程度,覆盖整个传输节点链.凡有重要节点参与的传输,节点链优先级要高,满足:

其中,Gj代表节点j的优先级.

2.1.2 节点活动范围划分

将节点的运动范围划分为4 个区域,分别为常规访问区域(routine access area,简称RAA)、随机访问区域(RanDom acess area,简称 RDA)、权限访问区域(authorized access area,简称 AAA)以及禁止访问区域(InAccessible area,简称IAA),如图2 所示.图中的黑点代表节点的访问足迹,深灰色区域代表常规访问区域,浅灰色区域是随机访问区域,阴影部分表示权限访问区域,其他部分则为禁止访问区域.

Fig.2 Illustration of range of node activities图2 节点活动范围示意图

从图中可以看出:

•常规访问区域是节点访问频率最高的区域,节点去往常规访问区域的概率最大.如果有需要发往该区域的数据,节点可以随身携带,在访问过程中捎带完成数据交付,此时,数据的转发对优先级没有要求.

•随机访问区域是节点偶尔会访问的区域,节点对该区域的访问是随机的,如果有数据要发往该区域,则节点需要调整运动路线,这对于数据的优先级有一定要求.

•权限访问区域是节点尚未访问过但是可以访问的区域,若要节点改变路线前往权限访问区域,需要较高的转发优先级.

•禁止访问区域代表节点不能访问的区域,节点无法前往禁止访问区域.

2.1.3 基于数据转发优先级与节点活动范围分布的传输规则设计

考虑到数据传输要求的多样性以及节点活动范围的分布,根据目标区域所在的位置信息,结合自身任务以及携带数据的转发优先级要求,动态调整运动路线,优先保证高优先级数据的有效转发.考虑到任务调度的复杂性以及节点的运动路线规划,基于活动范围分布情况,将节点的任务调度与活动区间进行映射以简化设计.

基于优先级评价模型,将数据的转发优先级分为3 个等级:紧急数据(emergency data)、优先数据(priority data)和普通数据(plain data),优先级依次递减.结合节点活动范围划分方案,确立数据传输规则的总体设计思路是:对紧急数据采取直接交付优先原则,对普通数据以不影响节点的原有状态为原则.

将节点的运动模式分为3 种,即固有运动(inherent move)模式、主动运动(active move)模式以及协调运动(coordinated move)模式:在固有运动模式下,节点不受携带数据的影响,保持自身原有的运动状态,最大限度保障独立性;在主动运动模式下,节点为了实现数据的有效传输而改变运动状态,主动调整自身的运动轨迹和行进路线,朝着更有利于实现数据直接交付的方向运动;在协调运动模式下,节点需要兼顾原有的任务调度和新的数据传输要求,适当调整运动轨迹.

根据目标区域的不同分布以及转发数据的不同级别,节点采取不同的数据传输策略,见表1.

Table 1 Data transmission rules表1 数据传输规则

从表中可以看出,对紧急数据而言,除非目标节点位于禁止访问区域内,否则节点会主动调整自己的行进路线,朝着目标节点方向运动,实现数据的直接交付;对优先数据来说,如果目标节点位于常规访问区域内,说明在转发节点与目标节点之间建立直接通信的可能性较大.鉴于优先数据的转发要求并非十分迫切(优先数据的优先级低于紧急数据),此时可依靠转发节点的固有运动来实现数据的直接交付.其传输时延与紧急数据相比会有所增加,但是节点的运动状态可以不受影响,保证了独立性.而针对目标节点位于随机访问区域的情况,则有必要通过节点的主动运动实现数据的直接交付.倘若目标节点位于转发节点不曾访问过的区域(包括权限访问区域和禁止访问区域),则需要通过寻找合适的下一跳节点来实现数据的有效转发.对优先级最低的普通数据来说,目标节点所处区域对采取的数据传输策略并无太大影响,节点的运动轨迹也不会因此发生改变,节点始终保持原有的运动状态,保证了独立性.

2.1.4 差异化副本传输策略

机会网络通常采用多副本传输策略来保障数据的投递,同时也会给系统带来一定开销.考虑到数据转发的优先级要求,我们认为,不同类型的数据传输其目标也不尽相同.对紧急数据而言,及时且有效的投递是第一要义;而对普通数据来说,系统开销问题则更受关注,投递失败在一定程度上也是可以容忍的.基于此,我们设计了基于数据转发优先级的差异化副本传输策略.

•针对低优先级数据采取条件转发策略,选择合适的中继节点完成数据的传输,依靠节点的固有运动转发数据,将副本数量控制在较低水平,以降低系统开销.

•针对高优先级数据,采取运动交付辅以洪泛传输的复合方式.一方面,通过节点的主动运动实现数据的直接交付;另一方面采取洪泛策略,将数据转发给遇到的节点.这种并行的传输方式能够保障数据的及时有效投递.

•为降低对其他传输任务的干扰,为优先级最高的紧急数据传输设计互斥保护机制(mutex protection),规定只有第1 个收到该紧急数据的节点采取主动运动转发方式,其他节点只需进行洪泛,仍然维持自身原有的运动状态.

•节点的主动运动传输可以与洪泛传输有效互补,弥补了部分场景下洪泛传输覆盖范围不足的问题,保

证了数据的有效投递,进一步降低传输时延.

2.1.5 同向数据捎带传输策略

主动运动转发有可能造成节点向同一目标区域聚集,如图3 所示.源节点Src将数据传递给邻居节点A和B.A,B皆处于主动运动状态,由于互斥保护机制,只能将数据分别洪泛扩散给C,D和E,F.节点D和F可以进行运动转发,携带数据向目标区域运动.节点E由于已经处于主动运动状态,只能继续洪泛给节点G,使得G也向目标区域运动,在一定程度上导致节点向同一目标区域聚集,带来局部通信流量增大,且会造成网络资源浪费.考虑到中继节点向同一目标区域运动过程中可能遭遇,我们采取同向数据捎带传输策略,通过节点间的协商实现数据的捎带传递,既释放了网络资源,又避免了流量冲突.

Fig.3 Illustration of how nodes converge together图3 节点聚集示意图

2.2 效用函数设计

在现实网络环境中,受限于某些条件,如节点分布、运动状态、节点级别、可用资源等,导致节点的运动范围受到一定限制,无法实现直接交付.此时,只能通过寻找合适的中继节点来转发数据.因此,中继节点的选择就成为一个重要问题.

一般来说,节点i为网络中所有节点维护一个效用函数Ui(⋅),τi(j)代表节点i和节点j的相遇间隔时间,Ui(⋅)是τi(⋅)的单调递减函数,有:

A节点携带有去往目标节点D的数据,当且仅当满足:

数据才会由A转发至B.效用函数的设计对路由性能的影响很大.

2.2.1 运动自由度模型

机会网络利用节点运动带来的连接机会传输数据,应该充分利用节点的运动特性,更好地为数据传输服务.尤其在进行数据转发时,需要重点考量节点的运动性.运动自由度Fi代表节点进行自由运动的能力,取决于节点的活动范围Ri、节点中心度Hi以及剩余能量Ei,满足:

其中,α和β分别代表影响因子,δi表示扰动因素.活动范围反映节点的活动区域分布情况,满足:

其中,T表示网络节点集合.可以看出,禁止访问区域范围越小,节点的活动空间越广,运动自由度越大.节点中心度反映节点在通信过程中的地位,取决于上下游节点间的通信联系.定义入度(incoming degree)代表将数据直接转发给自己的上游节点数目占节点总数的比例,出度(outgoing degree)代表接收转发数据的直接下游节点数目占节点总数的比例,有:

其中,Ii和Oi分别代表节点i的入度和出度,i−1 和i+1 分别表示节点i的直接上游节点和直接下游节点,N代表节点数目.入度越高,说明节点的通信枢纽地位越强,越容易成为流量汇聚中心;出度越高,表示节点拥有的转发选择越多,通信适应性越强.基于此,定义机会网络的节点中心度指标Hi满足:

其中,u,v分别代表中心度入权和中心度出权.节点中心度越高,对其运动限制能力越强,运动自由度越低.剩余能量代表节点当前的能量水平,对其进行归一化处理,得到:

考虑到节点能耗与数据收发的关系最为密切[25,26],建立数据收发与能耗之间的关联:

节点的剩余能量水平越高,运动能力越强,运动自由度越高.综合式(5)～式(14),得到:

2.2.2 效用函数模型

传统观点认为:节点中心地位越高,在转发中所起的作用越大,越适合成为中继节点.而实际在资源均等的情况下,节点中心度越高,流量越集中,往往会导致局部通信拥塞,反而不利于数据的传输.利用节点的运动特性转发数据,应该将运动性放在首位考虑.同时,为了体现传输的特点,将数据转发优先级同步纳入效用函数参考模型,定义效用函数满足:

综合式(1)、式(2)、式(15)、式(16),有:

效用函数能够综合反映节点的运动水平和数据优先级状况,表征传输的多重属性.剔除与数据直接相关的变量,定义效用函数指标UFI(utility function index)为

在传输高优先数据时,优先考虑数据的投递,通过节点的主动运动和洪泛传输来保障;在传输普通数据时,优先考虑系统开销以及节点原有的任务调度,通过衡量节点链优先级以及节点的运动性来决定是否转发.通常来说,节点链优先级越高,节点运动性越强,越适合成为转发节点.节点在相遇时,通过比较UFI值,使得数据从UFI值较低的一方向较高的一方传输,实现数据的转发.

2.3 算法设计与实现

随着GPS 等设备的广泛应用,节点的位置已经成为网络中的一个重要信息.系统配备节点位置服务器统一对节点的位置信息进行管理.节点采取预发布形式将自己的行程安排提前公布,供需要的节点查询.预发布行程的消息格式如图4 所示.

Fig.4 Itinerary pre-release message图4 行程预发布消息

其中,结束时间属于可选项.如果节点位置发生较大变化,即当前位置与预发布行程位置的距离偏差超过偏航阈值时,需要主动向服务器推送实时位置更新消息,格式如图5 所示.

Fig.5 Real time location update message图5 实时位置更新消息

位置服务器按照接收消息的序列号更新位置信息列表,供节点查询.当收到节点的位置查询请求时,位置服务器返回目标的当前位置信息.

节点相遇后,交换扩散向量列表DiffusionVector和转发消息队列MessageQueue,然后针对扩散向量集合DV中的每个数据包pkt∈DV,根据其消息类型进行如下处理.

3 实验仿真及性能评估

使用ONE(opportunistic networking environment)[27]工具进行仿真.在现实生活场景中,节点往往以群组形式出现,且不同群组中的节点具有不同属性.以园区场景为例,群组对象包括3 类:高管(senior executives)、中层管理人员(mid-level management)以及普通工人(workers),其中:高管的节点优先级最高,中层管理人员次之,普通工人优先级最低.园区分布如图6 所示,包含住宅区(包括员工宿舍、管理公寓、高级公寓)、生活区(包括餐厅I和餐厅II、超市、学校、幼儿园、医院、商业区)、生产区(包括生产区I～VII)以及办公区(包括管理服务区I,II以及高管办公区).根据不同对象的日常行为特点,定义各自的访问区域界定见表2.

Fig.6 Sketch map of an industrial park图6 园区示意图

Table 2 Illustration of visit area definition for park staff表2 园区人员访问区域界定

各优先级参数均统一设置为3 级,对应优先级值分别为4,2 和1.不同参数的数量占比均以百分比形式显示,见表3.依据表3 中各优先级参数值及其比例,计算数据转发优先级取值概率,结果见表4.其他实验参数见表5.

Table 3 Priority values and occupation ratios表3 优先级值与占比

Table 4 DFP values and probabilities表4 DFP 取值及其概率

Table 5 Experimental parameters表5 实验参数

选取Direct Transmission(DT)、Epidemic Routing、Spray and Wait(S&W)以及PRoPHET,与MBOR 进行比较,考察算法性能.

(1) 分组投递率:成功接收的分组数目占发送的分组数目的比例.

改变节点密度,统计得到各协议的分组投递率如图7 所示.

Fig.7 Impact of node number on packet delivery ratio图7 节点数目对分组投递率的影响

提高节点密度可以从一定程度上提升网络连接性,使投递的分组数目增多,但同时也会产生更多的冗余.由于采用了全网洪泛策略,Epidemic 的分组投递率最低.与其相比,DT 的单副本传输策略、S&W 的部分洪泛机制以及PRoPHET 的节点选择机制均能有效降低产生的分组数目,获得比Epidemic 的盲转发更高的分组投递率.MBOR 的运动转发机制能更好地保证分组的投递.尽管其差异化副本传输策略针对高优先级数据同样采取洪泛方式进行传输,但此类数据往往占比较低.对于数量最多的普通数据,MBOR 采取条件转发策略,在抑制副本数目、限制盲目洪泛的同时选择更具运动灵活性的节点参与数据转发,进一步提升投递成功率.

固定节点数目、改变网络负载大小,研究分组投递率的变化情况如图8 所示.从图中可以明显看出,随着网络负载的增加,各协议的投递率均出现了明显的下降.这是由于过大的负载造成缓存溢出,导致数据丢包,从而降低了投递率.

Fig.8 Impact of network load on packet delivery rate图8 网络负载对分组投递率的影响

(2) 传输延迟:消息从源节点发出直至抵达目标节点所经历的时间.

由于DT 协议采取了单副本传输策略,节点缓存数据直到遇到目标节点,无需中继,其传输时延取决于节点的相遇概率.对其他协议而言,随着节点数目的增加,节点的路径选择增多,更容易找到一条时延更短的路径,如图9 所示.

传输时延受网络流量变化的影响如图10 所示.从图中可以看出,随着网络负载的增加,丢包率逐步增大,增加了传输延迟.由于采用了全网洪泛策略,在负载较小的情况下,Epidemic 能够获得较低的传输时延.但是随着流量的增加,丢包率会随之上升,导致延迟增大.MBOR 协议通过节点的主动运动对洪泛传输进行适当补充,有效弥补了洪泛传播覆盖范围不足的问题.同时,MBOR 的同向数据捎带机制能够在保证高优先数据有效投递的前提下释放冗余的传输资源,优化任务调度,进一步降低传输时延.

Fig.9 Impact of node number on packet delay图9 节点数目对分组延迟的影响

Fig.10 Impact of network load on packet delay图10 网络负载对分组延迟的影响

(3) 投递开销率:节点转发的数据包数量与成功投递的数据包数量之间的比值.

投递开销率越高,说明节点完成数据传输所需的代价越大,占用资源越多.网络负载对投递开销率的影响如图11 所示.从图中可以看出,由于DT 协议只会将数据直接交付给目标节点,无需控制信令的传递,不会产生额外的开销,因此其开销最低.Epidemic 的全网洪泛导致网络中产生大量冗余分组,投递开销率较高.对MBOR 协议而言,由于需要获取节点位置信息以及进行运动转发,会在网络中产生一定的控制开销.与此同时,MBOR 采取的数据捎带传输策略可以释放冗余的网络资源,实现传输资源的二次分配,缓解局部流量拥塞.其差异化副本传输策略在保证高优先数据投递的同时,也会抑制盲目转发导致的分组冗余问题.同时,节点挑选合适的中继节点进行数据的转发,能进一步降低网络开销.

Fig.11 Impact of network load on delivery overhead ratio图11 网络负载对投递开销率的影响

(4) 缓存对算法性能的影响.

改变节点缓存大小,考察各指标的变化情况,结果如图12 所示.可以明显看出,随着缓存的增加,丢包减少,存储的分组数目增多,网络中传输的分组数目也相应增大,投递率增大.

Fig.12 Impact of buffer size on packet delivery ratio,delay and delivery overhead ratio图12 缓存大小对分组投递率、延迟和投递开销率的影响

4 结 论

本文基于节点的运动特性设计机会网络路由算法,通过对节点运动轨迹的调整,构建快速有效的通信连接.综合考虑数据的传输效率以及网络开销,设计差异化副本传输策略,针对不同优先级数据采取不同的传输机制.基于节点运动水平设计效用函数,实现中继节点的优化选择.实验表明:MBOR算法能够在限制系统开销的同时保障分组的投递,获得更低的传输时延.