DTN中基于连接分离时间的概率路由算法

崔建群,邬 尧,常亚楠,孙佳悦,余东海

(华中师范大学 计算机学院,武汉 430079)

1 引 言

延迟容忍网络(Delay Tolerant Network,DTN)[1],又称为容迟网络,是一种新型的端到端存储转发体系结构.DTN中的节点移动会导致网络拓扑时刻发生变化,再加上节点不稳定、资源受限以及环境干扰等因素,发送端和接收端之间难以实时维护一条可靠的端对端通路.为了克服DTN的间歇连通问题,完成消息的成功投递,DTN采用“存储-携带-转发”[2]的路由模式使得DTN适用于具有挑战性的环境,如野生动物追踪,移动车载网[3]与星际互联网络[4]等现实场景中,这种“无处不在的网络”被认为是发展潜力巨大的通信方式.DTN中消息的投递成功率受网络拓扑、链路状态、网络资源以及节点能量受限等诸多因素的影响[5],而高效合理的路由算法能够使得消息以较小的代价与较短的时间从源节点成功投递到目的节点,因此路由算法设计是DTN研究方向最为关键的问题.

基于上述分析,本文在Prophet算法基础上提出了一种基于节点连接分离时间的概率路由算法(Probabilistic routing algorithm based on connection separation time in DTN).本文主要贡献如下:

1)节点的连接分离时间,衡量节点的交互度.如果节点与其他节点分离时间越长就说明该节点与其他节点的交互度越低,表明该节点不愿意进行大范围移动或则在其运动范围内邻居节点较少.因此在选择中继节点时就不应该把消息投递给这类节点,而选择交互度高的节点,这样才能使得消息在短时间内扩散至较多的节点,从而提高投递率,降低传输时延.

2)在连接分离时间的基础上衍生出平均波动的概念,其是在节点运动轨迹和连接分离时间的基础上来综合反映节点之间连接波动大小.节点vi与其他节点在相遇时,会计算上一个时间窗口T中的平均波动值.当两个节点之间的连接波动较大,消息在传输的过程中随时可能会发生中断,将消息传给这样的节点会降低消息的投递率以及浪费网络资源.从前面的描述可以得出,平均波动应该作为投递预测值影响因子的一部分,使得平均波动较大的节点保持较低的投递预测值,反之,平均波动较小的节点保持较高投递预测值.

3)以平均波动为基础衍生出了节点连接紧密性、节点连接可靠性.衡量节点连接能力不能仅凭某方面的优势而下定论,因此本文考虑到节点连接紧密性与节点连接可靠性这两个影响因素,来综合定义节点连接能力.若节点连接能力较大,当该节点与其他节点相遇更新投递预测值时,应使得这对节点间的投递预测值较大,这样才能使得优质的节点能够获得更多的消息副本,使消息在DTN网络中扩散的范围更大,进而提高消息到达目的节点的可能性.

4)ACK机制,删除成功投递到目的节点的消息会释放节点缓存和节约网络中的资源,提高消息投递率,以及能明显降低网络开销.

2 相关工作

根据网络中转发消息副本的数量,DTN中的路由算法通常可以分为基于转发的路由算法和基于洪泛的路由算法两大类.其中基于转发策略的路由算法是利用网络拓扑选择一个到达目的节点的最优路径,然而在网络拓扑频繁发生变化的DTN中,单个节点想获得这样一条最优路径是几乎不可能的,因为其无法及时获取全部网络节点的状态信息[6].而洪泛式路由于无需获取全局的网络信息,只需将消息复制到足够多的节点,通过多节点携带消息副本的方式确保目的节点能成功地接受到这些消息.为了能够更好的利用节点之间关系的信息,并且能够从源头上控制消息副本数目,研究学者提出Prophet路由算法[7].该算法利用历史相遇信息与传递性来定义投递预测值(Deliver Probability).当节点vi遇到vj节点,并不会盲目地将消息复制转发给vj,只有当vj的投递预测值比vi高时,vi才将消息转发给vj.该算法通过挑选合适中继节点与有选择的复制消息副本,提高消息传输率,降低了网络开销.假设用P(i,j)来表示节点vi和vj之间的投递预测值,P(i,j)的计算分为3个步骤:更新、衰减以及传递性.

更新:当节点vi与节点vj相遇,根据式(1)来更新投递预测值.

P(i,j)=P(i,j)old+(1-P(i,j)old)×Pinit

(1)

其中,Pinit∈[0,1]是初始化常数.

衰减:当节点vi与节点vj一段时间内没有相遇,投递预测值根据式(2)进行衰减.

P(i,j)=P(i,j)×γk

(2)

其中,γ是一个时间衰减常数,在[0,1)间取值;指数k为从上一次计算相遇概率开始所经的时间单元个数.

传递性:投递预测值具有传递性,若节点vi与vj经常相遇,vj与vk也经常相遇,则可以认为vj是vi和vk较为合适的中继节点,节点vi和vk间的投递预测值传递如式(3)所示.

P(i,k)=P(i,k)old+(1-P(i,k)old)×P(i,j)×P(j,k)×β

(3)

其中β∈[0,1]是个常数,它决定了节点传递性对节点的投递预测值将产生影响的比重.

传统的Prophet没有考虑节点特殊性以及不同DTN场景间巨大的差异性,Prophet只从节点间相遇频率来定义不够准确.另外,由于消息大小是随机产生的而节点缓存大小一般是固定的[8],当节点剩余缓存较小时会为接收消息腾出缓存空间丢弃其他消息,为了尽可能避免丢弃有效消息,在挑选中继节点时应选择剩余缓存空间较大的节点.并且Prophet算法在衰减阶段仅从时间这一维度出发也没有考虑节点自身属性或DTN环境等其他因素,具有一定的局限性和缺失[9].针对Prophet算法的主要弊端,目前国内外研究学习者已经在Prophet的改进上取得了一些成果.

文献[10]考虑到节点的剩余能量与空闲缓冲区,当两节点相遇时先交换与其他节点相遇次数,再比较相遇次数与剩余能量,携带消息的节点会将消息投递给较多的相遇次数和能量的节点.文献[11]提出基于节点持续连接时间与节点缓存空闲率的理由算法BAProphet.该算法在挑选中继节点时,考虑到节点的连接持续时间以及节点缓存,将消息复制给当前性能更优的节点.文献[12]基于节点相似性提出S-Prophet算法,其在计算消息转发概率时考虑了节点的历史相遇情况,并采用ACK删除机制来保证及时清除已成功投递消息的副本.文献[13]基于距离的概率路由协议提出了DiProphet算法,该算法在投递预测值中添加近距离度量,提高了消息的投递率,降低了投递延迟.文献[14]将Prophet算法与Spray-and-Wait算法的消息控制策略相结合,并运用到车载网络中有效地控制了消息副本复制的次数.文献[15],结合节点接触时间与相遇频率提出HPR算法,同时为提高算法的消息传递率,该算法还通过消息复制的方式实现了多路径并行消息传输.与BSW算法[16]类似,指定源节点的所携带的最大副本数M(M >1),然后基于二叉树生成M个消息副本,目的是为了减少有效的网络开销.因此,消息总能朝着投递预测值递增的方向转发,这将有利于增大消息的投递成功率以及降低网络资源开销.

BAProphet算法在消息传递的过程中考虑到节点移动模型的特性和节点缓存空间对传输概率的影响,选用节点间持续连接时间以及消息传递过程中的缓存空闲率改进,但在消息的传输过程中只是简单的选取了两节点间总的连接持续时间和当前仿真运行总时间的关系,仿真实验表明消息投递率没有明显的提升,故不能充分说明时间这一参数对算法性能的影响力.S-Prophet算法在消息传递的过程中,虽然考虑节点历史相遇节点集合的相似性,但在计算投递率时只是简单的把Pinit替换成节点相似率,而且并未考虑节点移动这一特性对投递预测值的影响,因此在消息投递率表现上并不够理想.

基于上述分析,本文综合考虑不同DTN场景中节点特殊性,以节点连接分离时间作为基础,引入了节点平均波动、节点连接可靠性、节点连接紧密性以及节点连接能力的定义,并重新设计了传统Prophet算法中的更新与衰减公式,提出了一种基于连接分离时间的概率路由算法P-AVF(Prophet routing based on Average fluctuation).该算法中,当两节点相遇时,若当前时间t大于时间窗口T,则选择P-AVF算法;否则,利用Prophet算法计算投递预测值.在P-AVF算法中,两个相遇节点将利用的上一个时间窗口T内的历史信息分别各自计算的投递预测值,挑选出合适的中继节点使优质的节点能够携带更多消息并且扩散的更远.将P-AVF的仿真与Prophet,BAProphet,S-Prophet这3种路由算法的仿真数据进行分析和比较,P-AVF路由算法能够有效提高消息投递率,并且会有效地降低网络开销.

3 问题模型

3.1 网络模型

假设网络中包含n个节点,G=(V,E)为网络拓扑图,其中V={vi|1≤i≤n}表示网络中的节点集合,E为定义在G上边的集合.每个节点vi维护了一个历史相遇节点集合Si={{vj,{ts,td}}|i≠j},其中该集合记录与节点vj起始相遇时刻ts和分离时刻td.由于集合Si是由{vj,{ts,td}}三元组构成,当vi在不同相遇时刻遇到同一节点vj也会当成一个新的三元组并加入到集合中.另外,每个节点vi还维护了一个与其他相遇节点的投递预测值的集合Si={vj|P(i,j)},其中P(i,j)表示节点vi和vj的投递预测值.若vi与节点vj在仿真过程中相遇多次,会根据上次的投递预测值更新此次投递预测值.

3.2 节点连接分离时间

在DTN中为了尽快将源节点的消息投递到目的节点,在选取中继节点时要挑选交互度更高的节点,交互度更高反映该节点愿以进行大范围的移动可以更频繁的遇到其他节点或该节点的邻居节点就较多,这样就可以将消息在短时间扩散至更多的节点.由于DTN网络拓扑结构频繁变化,为保证从DTN场景中抽象出来的数据有效性,本文取一个时间窗口T来衡量该节点在最近时间窗口T内的交互度.

假设2个节点发生相遇时,若当前时间t<时间窗口T则采用Prophet算法.若当前时间t≥时间窗口T,两个节点分别同时计算上一个时间窗口T内的节点分离时间,用来衡量节点最新交互度.

定义1.节点连接分离时间.在每个时间T窗口内节点vi都会记录1组矢量Si=[{start(i,1),end(i,1)},{start(i,2),end(i,2)},…,{start(i,n),end(i,n)}].其中,start(i,1)表示在当前时间窗口T内节点vi第1次连接分离的时刻,end(i,1)表示节点在时间窗口T内节点vi第2次建立连接的时刻.在一个时间窗口T内,连接分离时间总时间为:Ts=(end(i,1)-start(i,1))+(end(i,2)-start(i,2))+…+(end(i,n)-start(i,n)).若Ts的值越小,则表明该节点与其他节点的交互性越强;反之,越弱.

3.3 节点平均波动

DTN中有的节点移动性很强,当两个节点相遇频率较高,但节点间连接时间较短,消息在连接时间内没有被传输成功,这种情形将导致消息投递失败.因此,节点连接波动情况将与消息的成功投递密切相关,本文定义节点平均波动来衡量节点连接情况.

定义2.节点平均波动.节点平均波动是衡量节点vi与其他节点vj连接波动程度,记为AVF(Di),公式如下.

(4)

其中,Di表示节点vi与其他节点vj的分离时间,t表示当前时间,T表示时间窗口,Ni表示节点与其他节点的分离次数.当前时间t大于时间窗口T时,节点vi遇到其他节点时,其会以当前时间t为起点计算上一个时间窗口T中的AVF(Di),以此作为依据来影响节点vi与其他节点之间的投递预测值.由式(4)可以看出当连接分离时间越长,并与其他节点分离次数越少时,AVF(Di)越大,表明该节点的连接时波动性更大.

由于DTN中每个节点的缓存容量有限,在利用多副本策略下选择中继节点时应合理利用节点缓存,选择将消息复制给轨迹差异性更大的节点,减少轨迹相似节点携带过多相同的消息,使得消息能够短时间在DTN中扩散更远[17].故式(4)中f(t)取值公式如下:

(5)

其中,E(t)i表示节点vi从仿真开始到时刻t历史相遇节点的个数,E(t)j表示节点vj从仿真开始到时刻t历史相遇节点的个数E(t)i∩E(t)j表示从仿真时间开始到时刻t节点vi

与最近分离节点vj的历史相遇节点集合中相同节点的个数,如图1所示,E(t)i∩E(t)j={V1,V13}.E(t)i∪E(t)j表示节点vi与最近分离节点vj从仿真开始到时刻t的历史相遇节点集合中总节点数,如图1所示,E(t)i∪E(t)j={V1,V2,V3,V5,V7,V8,V10,V11,V13,V14,V17,V19,V20}.

图1 节点vi和节点vj的历史相遇节点集合间的关系

3.4 节点连接紧密性

DTN的网络拓扑处于动态变化中,单个节点要想实时获取全局或部分的拓扑信息几乎是不可能的,因此通过挑选合适的中继节点限制单个消息的副本数量是一种优秀的路由策略.本文中节点的平均波动反映了节点在投递消息时成功概率,为了更好的说明分离时间与节点本身的关系,本文提出节点连接紧密性的概念,该概念与平均波动负相关.当平均波动越大时,节点连接的紧密性越小;反之,越大.

定义3.节点连接紧密性.为了更好的说明节点vi自身的连接能力,采用指数函数来标准化AVF(Di)来定义节点连接紧密性.记为CT(Di),公式如下:

(6)

由式(6)可以看出当节点的平均波动越小,节点的连接紧密性越强,它直接反映了节点vi自身的连接能力.

3.5 节点连接可靠性

DTN特殊的网络环境使得节点的移动性、自身缓存、能量和带宽等限制都可能使得消息不能够成功投递给目的节点,传统的Prophet中只是通过计算历史投递预测值,将消息投递给历史预测值高的节点,忽略了节点连接质量问题,当节点开启消息传输时,由于通信节点建立通信时间过短、节点间接性休眠或外界信号干扰等因素使得不能将消息完整的投递给对端节点,这造成了不必要的网络和能量开销.本文提出节点连接可靠性来解决上述问题,节点可靠性是节点连接平均波动性的衍生概念,因为节点平均波动性只是从单个节点获取的信息进行简单积分运算,并不能充分表明节点间的连接是否可靠.

定义4.节点连接可靠性.利用平均连接分离时间的标准差来定义该节点连接的可靠性.记为CR(Di),公式如下:

(7)

其中,Li表示节点vi与其他节点的连接分离时长.

为了更好的在含义上区别节点连接紧密性与可靠性,图2给出紧密性与可靠性的简单区别.

图2 节点连接紧密性与可靠性的区别

3.6 节点连接能力

在DTN网络中,衡量节点连接能力不能仅凭某一方面的优势而下定论,每种算法都有其优劣,因此本文考虑到节点连接紧密性与节点连接可靠性这两个影响因素,综合来衡量节点的连接能力.

定义5.节点连接能力.节点连接能力是节点连接紧密性与节点连接可靠性加权平均值,记为NC(Di),公式如下:

NC(Di)=α×CT(Di)+(1-α)×CR(Di)

(8)

其中CT(Di)为节点连接紧密性见式(6),CR(Di)为节点连接的可靠性见式(7).在式(8)中α为节点连接能力的平滑因子,其取值范围在[0,1].在本文设置实验参数的仿真环境下,经大量仿真实验证明,当参数α= 0.35 时,节点连接能力NC(Di)对网络性能提升最大.连接能力综合考虑了节点连接可靠性和连接紧密性,在挑选中继节点时会更严苛,使得消息在投递的过程中能沿着更可靠的中继节点直至目的节点.

4 DTN中基于连接分离时间的概率路由算法

现实的DTN场景中,由于环境因素及场景的需要,节点的属性各不相同,节点的属性从一方面来说也往往影响消息投递率.设想下面情景:

当节点vi在较长一段时间没有遇到中继节点,说明节点vi遇到目的节点的几率较低,故它与其他相遇过节点的投递预测值应该随之动态的变化,这样才能更好的反映DTN网络中节点的特殊性.

本文就是在上述假设的基础上,把节点的连接分离时间作为改进Prophet路由算法的基础,在节点连接分离时间的基础上还衍生出节点连接紧密性以及节点连接可靠性,并将节点自身缓存占用率引入到概率路由中,得到了基于Prophet改进算法,即P-AVF(Prophet routing based on Average fluctuation).

4.1 衰减公式的常数设计

传统的Prophet算法中没有考虑节点自身的属性与其运动的特点,只是简单选取vi和vj从上一次相遇到本次相遇所经历的时间单位个数k,很难反映不同DTN场景以及不同节点间的差异性.由于缓存占用率小的节点,它有更大的缓存来接收更多消息,随着节点接收更多消息又使得该节点投递率变小,这种惩罚机制也使得DTN中每个节点能动态确定节点本身的状态,故可以更公平的挑选出合适的中继节点进行转发.因此本文为了使得缓存占用比小的节点承担更多中继节点的任务,结合接收消息节点缓存大小和参数k,来表示消息接收节点缓存占用比.

(9)

其中,Ctotal是节点vj缓存大小,Mi表示单个消息大小.k是放大参数,它的大小决定了缓存占用比在较小的情况下并且在仿真的初期时衰减公式能够起到作用.本文进行了大量的仿真实验,实验结果表明,当k=120时,Cr对网络性能的提升效果最好.

节点vi分离时间总和越大表明该节点与其他节点交互度越低,遇到目的节点的概率也就越低,因此消息投递率也会受到影响.故本文利用消息接收节点缓存占用率和分离时间与运行时间的关系来修改式(2)中的参数k,使得投递预测值的衰减不仅仅只依赖于分离时间.在本文中,节点投递预测值衰减公式如式(10)所示:

(10)

4.2 更新相遇概率常数的设计

传统的Prophet算法用P(i,j)表示节点vi与节点vj之间的预测投递值,其中Pinit∈[0,1]是一个初始化的常量,经常相遇的两个节点之间能有更高的投递预测值.当两个节点相遇频率足够高,但是建立连接的质量较差,每次都不能完整的投递整个消息,将会降低消息的投递率,并且不完整的消息也会占用节点的缓存,以及不完整消息传输过程中会损耗两个节点能量.为了避免上述情况的发生,本文在挑选中继节点时采取了更为严苛的条件.

本文利用节点连接能力对传统Prophet算法中投递预测值的更新,对式(1)中的Pinit进行重新设计,在本文中节点投递的更新公式如式(11)所示.

P(i,j)=P(i,j)old+(1-P(i,j)old)×e(NC(Ci)-1)

(11)

其中,NC(Di)为节点连接能力见式(8).连接能力越大的节点在更新投递预测值的时候也会越大.可以看出P-AVF算法在挑选中继节点时,也将节点连接能力考虑其中,从而能更好的挑选出合适的中继节点,从而控制消息副本数,降低网络开销.

从式(11)可以看出AVF的定义是本文整个算法的核心,为了更准确的描述P-AVF算法,本文下面给出平均波动AVF实现的伪代码.

算法1.P-AVF算法中平均波动AVF

输入：时间窗口T;

时间窗口T内节点vi与其他节点相遇的节点集合为list;s为节点vi与其他节点分离起始时间;

输出：AVF

1.AVF← 0

2. IF 当前时间t≥时间窗口T THEN

3. 将list中的节点按s大小降序排列

4. FORnode∈list

5. IFnode正在与vi传送消息 THEN

6. 式(4) 中的f(t)← 0

7. ELSE

8. 计算节点vi与node之间的并集

9. 计算节点vi与node之间的交集

10. 按式(5)计算f(t)

11. END IF

12. END FOR

13. END IF

14.N←list中的节点数

15. 按式(4)计算AVF

16. RETURNAVF

假设节点历史相遇节点总数为M,由于将list中的节点按起始分离时间s进行排序,所以算法1的平均时间复杂度为O(MlogM).因此,计算AVF的平均时间复杂度为O(MlogM).假设网络中节点总数为N,则P-AVF算法的平均时间复杂度为O(NMlogM).

4.3 ACK确认机制

DTN中节点资源受限,为了能够充分利用节点的缓存和减少无效转发产生的网络开销,P-AVF算法采用了ACK确认机制[18]以减少消息冗余的副本数量.具体地说,当DTN中某个消息被成功投递到目的节点后,一些中继节点缓存空间中还存在该消息的副本,这些冗余的消息副本占用节点有限的缓存空间,使节点缓存利用率较低.此外,由于冗余副本存在于中继节点缓存中,若这些中继节点继续对冗余消息继续进行复制转发将会浪费有限的网络带宽,导致算法的网络开销暴增,造成网络拥塞,从而使得待投递的消息资源被占用,最终会降低算法整体的投递率,并加剧网络负载率.

P-AVF算法在设计时,给每个节点设置了一个ACK消息列表,当消息被成功投递到目的节点时,该消息就会被加入到节点的ACK列表中.当两个节点相遇时,需要相互交换ACK列表,用以及时补充完整的ACK信息,交换完成后节点会遍历自身的消息列表,查看消息列表中是否含有ACK列表中存在的消息,若有则直接从本地消息缓存中删除,以减少无效的重复转发复制的操作,从而为其他待投递的消息腾出更多的缓存空间.

ACK消息列表实现使用的是一个哈希表,查找某个消息的平均时间复杂度为O(1),本身消息队列中的消息共有N个,则本文的ACK确认机制时间复杂度为O(N).

由于ACK确认机制引入了额外的数据结构,会占用节点的一部分缓存,而且在消息投递过程中会对每个消息都进行哈希表的查找,这样额外的操作也存在能量的开销.但与继续复制已成功投递的消息占用的缓存和能量,这部分开销是可以容忍的.

4.4 消息转发策略

本文接下来将介绍P-AVF路由算法的消息转发步骤以及消息转发的伪代码实现.

基于连接分离时间的概率路由过程与传统Prophet路由过程大致相同,只不过在传统Prophet的投递预测值更新、投递预测值衰减做了参数上的重新设计,使得P-AVF更加能够适应现实的DTN环境,也能更好提升消息的投递率.

路由转发机制如下:

Step1.节点vi携带消息mi在延迟容忍网络中移动,遇到节点vj,先判断vj是否是目的节点,若是直接投递给vj,并执行ACK策略,删除DTN中其他节点缓存中mi消息,完成本次消息的投递.若不是,再判断当前时间t是否大于设定的时间窗口T,若小于时间窗口T,则按传统Prophet的方式计算投递预测值.若大于等于时间窗口T,则执行P-AVF算法.继续执行Step 2.

Step2.判断节点vj到目的节点vd的投递预测值是否大于节点vi到vd的投递预测值,若大于则vi将消息mi复制转发给节点vj.vj和vi执行相同的功能,在DTN中寻找目的节点与合适的中继节点.否则执行Step 3.

Step3.节点vi将继续携带消息直到遇到比节点vi到目的节点投递预测值更高的节点,则将消息转发给该节点,继续执行Step 1.

上述路由转发机制的算法如下:

算法2.P-AVF路由转发机制

输入：时间窗口T

输出：AVF

1. WHILE(TRUE)

2. 节点vi携带消息mi寻找目的节点vd

3. 遇到节点vj

4. IFvj==vdTHEN

5. 将mi投递给vj

6. BREAK;

7. ELSE

8. IF 当前时间t<时间窗口T THEN

9. 执行传统Prophet算法

10. ELSE

11. 按式(11)计算P(i,j)

12. 按式(10)进行衰减

13. END IF

14. END IF

15. IFP(i,d)>P(j,d) THEN

16. 不转发消息mi

17. ELSE

18. 将消息mi转发给节点vj

19.vj携带消息寻找中继节点

20. END IF

21. END WHILE

22. 执行ACK机制

23. RETURN

5 仿真实验与结果分析

5.1 仿真环境配置

本实验采用ONE[19]仿真平台分别对P-AVF、Prophet、BAProphet以及S-Prophet算法进行仿真,本次仿真采用ONE自带的赫尔辛基市地图作为移动场景,区域大小为4500m×3400m.具体的仿真参数设置如表1所示,其他参数均采用ONE仿真平台自带的默认设置[20].

表1 仿真参数

5.2 仿真设置

由式(4)可知给定时间窗口T的大小会直接影响节点的平均波动,从而影响到连接紧密性与可靠性的大小,进而会影响到消息投递率.为挑选出效果最佳的时间窗口T值,本文在如上实验的参数的基础上做了大量的对比仿真实验,本文在此次实验中选择节点缓存大小为15MB,绘制出如下时间窗口T与投递率的关系图,其他参数若无特殊说明均为ONE自带初始化设置,实验结果如图3所示.

图3 不同时间窗口T下P-AVF算法的投递率

从图3中可以观察到,当T取值为1800时,P-AVF算法的投递率最高,并且趋近1800时,如图3所示波动的平均值趋近一个固定值.这是因为如果T值取的较小,节点没有足够多的历史分离次数以及足够长的分离时间来使得实验数据趋于稳定,可能会有部分的节点在此段时间内相遇其他节点的次数足够少,分离时间过长,导致该算法的投递率较低;如果T值较大,则P-AVF算法的投递预测值会被上一个时间窗口影响过大,不能及时的反映当前节点状态,致使该算法的投递率下降.因此本文中的时间窗口T取值1800.

5.3 仿真实验评价指标

本文采用以下指标来评估本次仿真实验所运行的四种路由算法的性能[21].

1)投递率(Delivery Ratio):仿真时间内由消息的源节点生成并成功投递到目的节点消息总数与网络中生成所有的消息数量之比,计算公式如式(12)所示:

(12)

2)网络负载率(Overhead ratio):仿真时间内网络中冗余中继转发次数与成功投递消息数目之比,计算公式如式(13)所示:

(13)

3)平均时延(Average Latency):仿真环境中所有由源节点创建的消息到被成功投递目的节点的时长之和,与成功投递的消息数目之比,计算公式如式(14)所示:

(14)

5.4 仿真结果及分析

为了验证P-AVF算法的高效性,本文通过改变消息的缓存大小、消息的生存周期、仿真时间以及消息产生间隔,进行了4组仿真实验,将P-AVF和BAProphet、Prophet以及S-Prophet 4种路由算法在投递率、网络负载率和平均传输时延的3个方面性能上进行对比,实验结果表明,P-AVF路由算法对网络性能的提升最为明显.

5.4.1 不同的节点缓存大小

在如上的环境配置下,通过改变节点缓存容量的大小,对比四种算法在不同缓存大小下的投递率、网络负载率和平均时延的变化情况结果如图4所示.

图4 不同的节点缓存大小对算法路由性能的影响

图4展示了4种算法的路由性能随着单个节点缓存空间的变化情况,从图4可以看出,在P-AVF、 BAProphet、Prophet以及S-Prophet算法中,P-AVF算法的投递率最高,网络负载率最低,平均时延较大.

如图4(a)所示,随着缓存空间的增大,4种算法的投递率都明显增大.这是因为节点缓存空间越大,单个节点就可携带更多的消息并会降低因缓存大小不够造成的消息丢弃的概率,携带待投递消息节点遇到目的节点的概率也就随之增大,从而提高算法整体的投递率.P-AVF算法的平均投递率相比Prophet算法提高78.73%,相比于BAProphet算法的平均投递率提高61.27%,相比于S-Prophet算法的平均投递率提高10.18%,这是因为P-AVF对中继节点的筛选比其他算法更加严格,并使得性能较优的节点上保持较高的投递预测值,从而提高了消息的投递率.并且由于ACK确认机制,使得P-AVF路由算法与S-Prophet路由算法中的节点都有更多的缓存空间接收待投递的消息,因此这两种算法的节点可以携带更多有效消息,提升整体算法的投递率.

如图4(b)所示P-AVF算法的平均网络负载率相比Prophet算法降低58.27%,相比于BAProphet算法的平均网络负载率降低44.66%,相比于S-Prophet算法的平均网络负载率降低16.98%,这是因为P-AVF相比较于其他3种来说,对中继节点的筛选更严格,在一定程度上减少了不必要的转发次数,而且P-AVF与S-Prophet都增加了ACK确认机制,能够及时删除已经成功投递的消息,为需要继续投递的消息腾出缓存空间,使得有效消息被丢弃的概率下降.

如图4(c)所示随着缓存容量增大,BAProphet、Prophet以及S-Prophet算法的时延都呈现上升,这是因为随着节点的缓存增大,消息能成功投递的概率变大,使原本不可能投递到目的节点的消息变为可能,整体平均时延呈现上升的趋势.P-AVF在缓存12.5M-20.0M的范围内,网络平均延迟表现出下降趋势因为12.5M后的P-AVF算法的投递率趋于稳定,而随着节点缓存的增大,节点同一时刻能携带更多的消息,消息被丢弃的次数也会降低,则消息能够被成功投递到目的节点的时延也会降低.P-AVF算法的平均网络时延相比Prophet算法提高2.67%,相比于BAProphet算法的平均网络时延降低1.33%,相比于S-Prophet算法平均网络时延提高6.18%.这是因为P-AVF算法选择中继节点时考虑的因素较多,从而能够有效避免将消息副本拷贝传输给综合性能较低的节点这样减少网络开销,但也降低了消息副本在当前网络中的扩散范围,所以在网络时延表现上不够优秀,另一方面也验证了P-AVF算法对中继节点选择的严苛,从而证实P-AVF算法的可行性.

5.4.2 不同的消息生存周期

图5展示了4种路由算法在不同的消息生存周期下的性能表现.从图5(a)可以看出,随着消息生存周期的增加,Prophet算法与BAProphet算法的投递率在降低,这是因为在节点缓存空间较小的条件下,如果消息生存周期过大,消息以较长时间存在于DTN中,这对缺少ACK确认机制的Prophet

图5 消息生存周期对算法路由性能的影响

与BAProphet算法在剩余缓存不足的条件下,被迫丢弃部分其他消息用于接收新消息.另外从生存周期200min后S-Prophet算法的投递率没有明显增加,这是因为S-Prophet算法对中继节点的筛选过于简单,只是考虑投递预测值和节点相似性,并没有有效地挑选出优秀的中继节点.从整体上来说P-AVF算法的平均投递率相比于Prophet算法提高69.20%,相比于BAProphet算法的平均投递率提高51.51%,相比于S-Prophet算法的平均投递率提高12.88%.

从图5(c)可以看出S-Prophet算法能够快速的将副本数分散到整个延迟容忍网络中,相比于P-AVF算法复杂的筛选中继节点的机制,S-Prophet算法在选择中继节点机制上更为简单所需要的计算资源也更少,因此S-Prophet算法的平均时延是最低的.

5.4.3 不同的消息产生间隔

在不同的消息产生间隔下,比较和分析各个算法在消息投递率(如图6(a))、网络负载率(如图 6(b))、平均时延(如图 6(c)),这3个方面变化情况.

图6 消息产生间隔对算法路由性能的影响

图6展示了4种路由算法在不同的消息产生间隔下的性能表现.从图6(a)中可以得知,P-AVF算法的投递率稳定上升且上升的趋势较快,其他3种算法投递率都随着消息产生间隔增大而增大,但趋势都没P-AVF明显.从图6(b)可得知,P-AVF和S-Prophet的网络开销最小,且随着消息产生间隔增大网络开销增大不明显,而Prophet算法与BAProphet算法较为随着消息产生间隔增大网络开销增大较为明显.这是因为在消息产生间隔较小时,相同时间内整个网络会产生较多的消息,由于受限的节点缓存空间与缺乏消息冗余副本的去除机制,Prophet算法与BAProphet算法都会在消息产生间隔较小时,丢弃大量的消息,由于S-Prophet算法有ACK确认机制可以在一定程度上减少消息的丢弃,但P-AVF算法利用节点的缓存占用率以及节点连接能力等因素可以选择更合适的中继节点,在一定程度上比由于S-Prophet算法性能更优.从图6(c)可得知,P-AVF算法平均时延最大,这也再次验证了P-AVF算法的可行性,此处不再赘述原因.

5.4.4 不同的仿真时间

在不同的仿真时间下,比较和分析各个算法在消息投递率(如图7(a))、网络负载率(如图7(b))、平均时延(如图现.如图7(a)所示,在仿真进行到13小时所有算法的投递率基本维持一个定值,这是因为算法运行已达到了一个稳定状态.另外,P-AVF算法的平均投递率相比Prophet算法的平均投递率提高71.56%,相比BAProphet算法的平均投递率提高60.82%,相比S-Prophet算法的平均投递率提高14.63%.这主要是因为P-AVF算法利用时间窗口T内的分离时间等信7(c)),这3个方面变化情况.

图7 仿真时间对算法路由性能的影响

图7展示了4种路由算法在不同的仿真时间下的性能表息与消息缓存占用率来评估节点的是否可靠,使得性能高效的节点总能保持较高的投递预测值,而Prophet算法与BAProphet算法的投递率较低,这是因为首先对中继节点的挑选过于简单,没有考虑节点自身能力与投递预测值的关系,并且没能及时的去除网络中成功投递的消息副本,导致网络资源被成功投递的消息消耗,引起网络拥塞并造成节点丢包.如图7(b)所示,P-AVF算法的网络负载率最低,相比于Prophet算法的平均网络负载率降低42.41%,相比于BAProphet算法的平均网络负载率降低25.61%,相比于S-Prophet算法的平均网络负载率降低16.81%,此现象原因不再赘述.如图7(c)所示,P-AVF算法的网络时延和其他参数环境下结果类似,原因不再赘述.

6 结束语

本文基于Prophet路由算法提出一种基于节点连接分离时间的概率路由算法P-AVF.该算法根据节点连接分离时间衍生出了平均波动、节点连接紧密性与可靠性以及节点能力等概念.该算法在挑选中继节点时,依据时间窗口T内的节点属性来选择性能优越的节点作为中继节点,由于对Prophet衰减公式参数进行重新设计,使得性能优异的节点能够长时间保持较高的投递预测值,同时还结合ACK确认机制降低网络负载,进一步提升了网络的整体性能.仿真实验结果表明,P-AVF算法在投递率、网络负载等方面均优于其他3种算法,但是对中继节点选择过于严苛,P-AVF算法在平均时延上也大于其他3种算法,接下来的研究应该从降低平均时延方向出发,在保持较高投递率与较低的网络负载率同时,使得算法的网络时延不要过高,从而整体上提升P-AVF的性能.