延迟相容网络中基于分簇的混合路由算法

延迟相容网络中基于分簇的混合路由算法

1节点间的相互联系延迟宽容网络（tn）是一种缺乏连续端到端连接的新网络。由于节点间端到端路径的稳定，误码率高，节点间端到端的延迟率高，因此dtn采用以内存为导向的服务器协议（scf）。最初的DTN路由协议主要以控制副本的路由协议及基于上下文信息的路由协议为主,其中基于副本控制的路由协议包含传染病路由协议EPI(Epidemic)、PREP(PrioritizedEpidemic)、SprayandWait、直接传输(Directtransmission)等,基于上下文信息的路由协议主要包含SeekandFocus、PROPHET(ProbabilisticRoutingProtocolusingHistoryofEncountersandTransitivity)等.基于上下文的路由协议利用历史信息来预测未来的消息转发策略,以PROPHET为例,PROPHET是一种基于概率策略的路由协议,它利用节点间相遇(encounter)的历史信息和传递性(transitivity)来选择下一跳节点,以传输可预测性(predictability)P∈(0,1]作为概率度量标准,即其中,a和b表示任意两个节点,Pinit∈(0,1]表示初始常量.PROPHET协议的消息转发思想为:对于节点A和节点B,当节点A与B相遇时,若节点B与目的节点之间的传输可预测性更高,则节点A将消息转发到节点B.随着基于副本控制的路由技术的成熟,越来越多的研究者开始分析节点间的相互联系、节点的运动特性对路由协议产生的影响.近年来,利用节点间的相互联系,分簇/分层路由技术被引入到DTN中,主要的研究工作有基于分层的层次化机制、基于最大直径的分簇算法、基于节点相遇概率的分簇方法.另外,根据节点的运动特性进行消息的转发,也形成了许多不同的路由算法:相似性与中介中心性(BetweennessCentrality)相结合的路由算法(相似性是指两个节点共同邻居的数量;相对于节点s,d,节点i的中介中心性是指在s与d之间的所有最短路径中,经过节点i的最短路径所占的比例),根据节点的活跃程度、社会距离、节点的投递概率预测进行转发等.在基于节点运动特性的路由协议中,如何充分利用节点之间的相遇、节点的运动方向以及节点的活跃程度(节点在一定时间内遇到的不同节点的数量越多,活跃程度越高)成为决定路由性能的关键.本文分析了现有基于节点运动特性的路由机制的缺陷,提出了一种社会网络场景下的基于节点运动预测的高效路由CS-DTN(Clustering&SocialDelayTolerantNetwork).在社会网络场景(校园、国际会议等)中,节点往往以群组的方式出现(社群性),在每个群组中有少数节点活跃程度较高.以校园场景为例,同一个班级的同学出现在同一个场所的可能性很高,在班级中班长的活跃程度比其他同学要高.因而CS-DTN根据节点之间的相遇概率将节点分成不同的簇,簇内根据相遇概率限制消息的拷贝数量,簇间根据节点的活跃程度、节点与目的节点的相对位置及节点的运动方向预测进行消息的转发.由于充分利用了社会网络的特点,另外又结合了节点运动预测,从而在明显提高消息投递率的同时,极大地降低了消息的端到端延迟.2基于节点运动的社会ddosn高效路径本章使用到的数学符号介绍如表1所示.2.1节点活跃程度的影响在基于节点运动特性的路由协议中,如何利用节点之间的相互联系、节点的活跃程度以及节点的运动方向成为决定消息投递率的关键.文献中的层次化的转发机制,是根据节点的相遇频率对节点进行分层.节点根据其相遇频率分为多个包含两个节点的组,然后根据组相遇频率将两个相遇频率最大的组合并,组间相遇频率的计算公式为Dij表示节点i与节点j之间的相遇频率,M,N分别指两个组中节点的个数.以此类推形成一棵根包含所有节点的二叉树.此类基于分簇/分层的路由主要是利用节点之间的相互联系、紧密程度机制,使联系紧密的节点之间能够采用高效的消息传输.然而,对于联系不够紧密的节点,需要在不同的簇/层间进行传输.文献中,需要自叶节点从下而上对二叉树进行搜索,直到包含目的节点的簇/层,文献中也需要进行簇间的寻路过程.然而由于DTN网络中的拓扑复杂多变,簇间路径稍逊即逝,在寻路过程中会浪费大量的带宽,同时也会增加消息的投递延迟.另一方面,基于节点活跃程度的路由[10,11,12,13,14,15],主要考虑活跃节点在转发消息时带来的性能优化.文献中基于小世界的理论,提出了一种以相似性(Sim)与中介中心性(Bet)相结合(SimBet)的路由算法.假设节点N需要转发消息到目的节点D,当节点N遇到节点M时,SimBetN(D)为通过上述算法得到节点N与目的节点D之间的SimBetN(D),同样的方法得到SimBetM(D),如果SimBetN(D)<SimBetM(D),则N将消息转发到M,同时删除对该消息的缓存.类似的工作也在文献[11-12]中得到体现,文献中消息被不断地转发到具有高活跃性的节点;文献中试图将消息转发到最有可能到达目的节点的中继节点.此类路由利用在网络中与目的节点相遇可能较大的游走节点传输消息,减少了消息被转发的次数,可以保证消息快速的到达目的节点.然而,如果只利用节点的活跃程度也会带来不必要的资源浪费.如图1所示,假设节点1,4,6固定,节点2,3,5围绕图中所标识的环移动,旋转一圈的周期均为t.如果节点1需要将消息投递到节点2,根据路由算法,节点3,5相对节点2在单位时间内相遇更多的节点,视为活跃节点,节点1会将消息转发到节点3或者节点5.对于单幅本路由,会造成消息的丢失;而对于多副本路由,会大大增加网络的负载,造成资源的浪费.通过以上分析可知现有的基于节点运动特性的路由算法对节点的运动特性考虑不够全面,如果将节点间的联系、节点的活跃程度结合起来既可以实现联系紧密节点间的消息的有效传输,同时也可以实现联系不够紧密节点之间消息的可靠投递.另外,从图1中可以看出,当节点1需要投递消息到节点6时,根据节点的运动预测(节点间的相对位置,节点的运动方向),可以避免将消息转发到节点3带来的资源的浪费.因此,本文根据节点间的联系(相遇概率)对节点进行分簇,提出了簇间根据节点的活跃程度与运动方向进行消息的转发,簇内采用限制副本数量路由的混合路由机制(CS-DTN),下文将对分簇算法、CS-DTN路由机制进行详细的介绍.2.2节点的稳定性(1)节点的相遇概率节点相遇概率即节点间相遇的可能性大小,计算公式为节点相遇概率会在每个时隙结束的时候进行更新;显然,当节点相遇频繁时,相遇概率也会随着时间不断地增大,反之会不断减少;这能很好地体现节点之间的联系程度,通过此相遇概率可以大体估算出节点未来的相遇情况,从而为消息的转发提供依据.对于α,如果取值过小,则需要较长时间达到稳定状态,但会减少错位的发生,因而需要根据不同的应用场景进行选择.(2)分簇算法定义1.节点的稳定性.节点i的稳定性指i与Mi中其它节点的相遇概率的最小值.记为Si,计算如下:定义2.节点的同步.节点i与节点j进行同步,首先交换二者的相遇列表,根据相遇时间将二者的相遇列表分为两个集合Ψij,Ψji,节点i与节点j更新簇成员列表为Ψij∪Ψji,实现同步.Ψij,Ψji计算类似,Ψij计算如下:分簇算法的基础是节点间的相遇概率,根据节点间相遇概率的变化决定一个节点加入或者离开簇.算法基于事件触发,包含两个主要的事件:时隙超时事件及节点相遇事件.如算法1所示,每个时隙结束时根据式(6)进行节点间相遇概率的更新.节点相遇时(假设相遇的节点为节点i及节点j),包含两种情况:节点i与节点j属于同一个簇;节点i与节点j属于不同的簇.当节点i与节点j属于同一个簇时,根据二者之间的相遇概率判定:如果节点i与节点j之间的相遇概率大于设定的分簇阈值,则二者进行簇成员列表的同步;如果节点i与节点j之间的相遇概率小于等于设定的分簇阈值,则稳定性低的节点离开当前簇并形成一个新的只包含自身的簇.当节点i与节点j不属于同一个簇时,判定节点i是否满足加入Cj的条件及节点j是否满足加入Ci的条件(判定规则如算法1所示,当节点i与Mj中的任意一个成员之间的相遇概率大于给定的阈值,则节点i满足加入节点j的条件):如果二者均满足,则稳定性低的节点加入稳定性高节点所在的簇;如果只有其一满足时,假设节点i满足,则节点i加入Cj;如果二者均不满足时,不进行簇成员的更新.算法1.分簇算法.2.3节点i与节点j间的关系对节点进行分簇后,每个节点都会属于一个簇,假设节点i需要传输消息到节点j时,包含两种情况:节点i与节点j属于同一个簇内;节点i与节点j属于不同的簇.接下来文章将对簇内路由及簇间路由进行详细介绍.2.3.1节点间信息的上传根据分簇算法,簇内节点之间的相遇可能性很大,因而在簇内使用限制副本数量的DTN路由算法会获得较好的性能.CS-DTN基于SprayandWait算法,提出了簇内路由算法如下:其中φ为节点间的相遇概率阈值,当节点间相遇概率足够大时,此时仅需要小量的消息副本(L)即可保证消息的投递,当概率相对较低时,需要适当增加消息副本的数量(n×L),为了减缓节点缓存的压力,采用限制消息转发次数的方式来控制消息副本数量.本文中设定L=1,n=2,φ=0.7.消息的转发策略:当节点s有消息m(L份副本)需要发送到节点d时(节点s与节点d位于同一个簇内),遇到节点v,只有在εvd>εsd时,才进行转发;转发时,s将L/2份副本转发到v,当节点只包含一份副本时,只有遇到目的节点d时才进行转发.2.3.2节点的动态转发根据社会网络的特点,具有高中心性的节点将消息投递到目的节点的可能性更大,然而只考虑节点的活跃程度在一些场景下不能很好地将消息投递到目的节点.因而CS-DTN将节点的中心性与节点的运动相结合的结果(Centrality&Direction,CD)作为簇间转发的判定指标,下文将会给出CD的计算算法.将节点按照CD进行一个全局的排名,簇间进行消息传输时,消息只会从排名较低的节点传递到排名较高的节点,直到消息被投递到目的节点或者目的节点所在簇的成员.假定源节点S需要向目的节点D(S、D属于不同的簇)转发消息,遇到节点A,B;则计算S,A,B三者的CD值(CDS,CDA,CDB),计算CD前首先需要计算节点的中心性与各个节点之间的相对位置及运动方向.(1)节点的中心性,是节点在一段时间内遇到的不同节点的数量,会随着仿真的进行不断地更新,记作Cen;(2)节点的运动方向及节点与目的节点的相对位置.如图2所示,假设已知目的节点的坐标信息(通过北斗等双向GPS定位,可用小量的控制信息获取目的节点的位置),节点的相对位置以角度表示,计算DSA的角度为其中,其它角度计算类似,计算节点的运动方向,以节点A为例,通过连续获取A发出的Hello探测数据包,获取A在两个位置的坐标(xa,ya)及(x′a,y′a),计算通过比较dad及d′ad可以判定节点是否向目的节点d移动.以节点S为例,当节点S遇到节点A时,首先对中心性Cen及角度进行标准化:则CDS计算如下:簇间转发策略为:以节点S,A,D为例,当节点S遇到节点A时通过节点之间的交换信息,计算CDS和CDA,当CDS<CDA且时,说明A节点正向目的节点D移动且A节点比S接点CD值更高,因此S将消息转发到节点A.转发时包含两种策略:多副本:节点S将消息转发到A节点后仍然保留消息并将消息转发到下一个遇到的中心性高的节点,直到消息超时;单副本:节点S将消息转发到节点A后删除本地缓存;本文采用簇间采用单副本策略.2.3.3簇内/成团簇间与簇内消息的交互只有在两种情况下发生:节点加入或者离开簇,簇间传输的消息被转发到簇内.当节点加入或者离开簇时,根据节点所在的簇更新节点缓存的消息模式:簇内或者簇间,每次节点加入或者离开簇时都会更新.当在簇间传输的消息被转发到簇内时,需要进行两步操作:首先将该消息设置为簇内消息;其次根据簇内路由算法设定节点的消息副本数.3cs-dtn实现本章主要介绍CS-DTN路由机制在Qualnet平台下的设计与实现.首先介绍CS-DTN协议的系统架构及主要的工作流程,接下来对实现CS-DTN的主要函数进行了介绍.3.1混合路由机制图3所示是CS-DTN的一个应用场景,节点S需要发送消息到节点D,由于不存在稳定的端到端路径,CS-DTN需要解决的问题是如何选择一条能够高效到达目的节点D的路径,根据前一章的分析,CS-DTN的系统架构如下:对节点S与节点D之间的节点根据相遇概率进行分簇,簇内节点采用限制副本数量的SprayandWait算法,簇间采用基于节点活跃度与节点运动预测相结合的算法.通过簇内簇间的混合路由机制来实现消息的高效传输.CS-DTN的工作流程主要包含两部分:接收消息的处理以及消息的转发.接收消息的处理根据接收消息节点的不同而不同,可分为源节点、中间节点及目的节点.如图4所示,假设节点i接收消息:当i为源节点时,首先根据自身的簇成员列表判断消息的目的节点是否与i位于同一个簇内,如果位于同一个簇,则标记消息为簇内消息,根据i与目的节点之间的相遇概率设定消息的副本数量,否则标记消息为簇间消息,之后将消息存入缓存等待转发.当i为中间节点时,如果消息属于簇间消息且i与目的节点位于同一个簇内时,更新消息为簇内消息,根据i与目的节点之间的相遇概率设定消息的副本数量,之后将消息存入缓存.对于其它情况,则直接将消息存入缓存.当i为目的节点时,直接将消息向上层投递.消息的转发流程如图5所示,当节点i与节点j相遇时,二者交换节点信息(节点ID、簇ID、节点相遇列表),如果节点i与节点j位于同一个簇内,对于任意一条簇内消息m,如果εid<εjd,则节点i将消息转发到节点j;如果节点i与节点j不属于同一个簇,只有当节点j满足节点j的CD值较高、节点j属于目的节点所在的簇或者节点j为目的节点时,节点i将簇间消息转发到节点j.上述只讨论了节点i将消息转发到节点j的情况,反之亦然.3.2cstdn的基本概念CS-DTN的实现基于Qualnet仿真平台,根据Qualnet协议栈,主要包含5个主体函数:协议初始化函数、事件调度函数、协议包处理函数、路由函数及结束函数,下文将对这5个函数进行简单介绍.(1)协议初始化函数该函数来初始化协议,主要任务包括:创建一个协议的数据结构实例;从配置文件读取并存储用户指定的参数;初始化状态变量、缓冲区和统计信息;登记CS-DTN的路由函数CSDTN_RouterFunction;为自身设定开始协议的定时器.(2)事件调度函数协议事件调度函数根据接收消息的类型调用不同类型的消息处理函数.(3)协议包处理函数协议事件调度函数根据接收包的类型调用不同类型的包处理函数.协议包类型包括:CSDTN_DATA(携带数据)、CSDTN_HELLO(探测邻居节点,包含节点ID、簇ID、节点相遇列表)、CSDTN_REPLY(CSDTN_HELLO包的反馈,包含节点ID、簇ID、节点相遇列表).(4)路由函数voidCSDTN_RouterFunction(Node*node,Message*msg,AddressdestAddr,AddresspreviousHopAddress,BOOL*packetWasRouted).根据CS-DTN路由机制实现.(5)结束函数voidCSDTN_Finalize(Node*node,inti).函数在仿真结束时被调用,主要任务是打印统计信息到统计文件,清空变量和缓存信息.4性能分析4.1节点信息的传递为了评价CS-DTN路由协议的性能,本文采用基于移动模型的场景来进行仿真.如图6所示,包含6个场所(C,H1-H5),其中H1-H5为5个不同的群体所在的场所,C作为公共场所.该模型指定每个节点(假设为节点i)都有一个唯一的主H(假设为Hi)并且节点i会在Hi花费大部分的时间,为了更加符合社会网络场景的特性,本文设定每个H中10%的节点表现活跃,相对于其它节点,这些节点将花费更多的时间在不同的场所中移动,负责在各个场所中进行信息的传递.如图7所示,在该模型中,假定节点离开H之后首先进入C.当节点待在主H时,在下一个时隙待在主H的概率为PH,离开主H的概率为1-PH;当节点位于C时,在下一个时隙有PH的概率回到主H,有PC的概率待在C,或者1-PH-PC的概率进入其它H;最后,当一个节点位于非主H的其它H时,在下一个时隙有1-PH的概率留在原地,有PH的概率进入C.在仿真中设定H中非活跃节点(90%)的PH=0.7,PC=0.1;活跃节点(10%)的PH=0.5,PC=0.1.根据马尔科夫模型,设定节点i在H,C及Else的稳态概率为PHi,PCi,PiElse,则有以校园场景为例,不同班级之间的交流主要是依靠班级干部进行的,而非班级干部成员与其他班级的联系相对要少的多.因而,根据式(20)修改后的模型存在10%的节点PiElse=0.286,90%的节点以0.078的概率进入其它H,相对之前所有节点均以0.078的概率进入其它H更能体现社会网络的特性.另外,根据式(18),可以计算任意两个节点(节点i及节点j)同时位于主H的概率为由于位于同一个主H的节点间相遇的可能性很大,可以认为0.416接近于簇内节点的相遇概率,因此设定节点的分簇阈值为0.4.仿真实验将CS-DTN与Prophet,Clustering路由算法以及没有考虑节点移动方向的CS-DTN(CS-DTNwithoutDirectionForwarding)进行比较.仿真参数如表2所示.4.2不确定量—仿真结果为了全面验证CS-DTN算法,本文使用了投递成功率及平均端到端延迟两个性能评价指标.投递成功率是指目的节点成功收到的消息在源节点发送消息中所占有的比例;平均端到端延迟是指消息从源节点到目的节点所需时间的平均值.本文分别对缓存大小的变化、节点数量的变化及数据产生速率的变化对协议性能的影响进行了仿真.缓存大小变化(20~200)对网络性能的影响如图8所示.随着缓存大小的增加,由于节点缓存已满导致消息被丢弃的概率减少,从而消息的成功投递率会得到提高.同时,由于消息在缓存中产生更多的排队延迟,导致消息的端到端延迟会有所增加.因此,随着缓存的不断增加,在存活时间内未能到达目的节点而被丢弃的消息数量增加,导致消息成功投递率上升的趋势减缓.相对于Clustering和Prophet,CS-DTN在缓存足够大时会取得更高的投递率和更小的端到端延迟.在投递率方面,缓存较少时,CS-DTN的消息成功投递率较Clustering低,这是由于CS-DTN的簇间转发引起的,消息不断地向中心性高的节点累计,其缓存不足以存放接收到的消息而导致消息被丢弃.当缓存增加到一定程度时,该问题得到解决,消息投递率超过Clustering.Prophet主要考虑节点与目的节点之间的概率而未结合节点的运动特性,因此投递率相对于Clustering及CS-DTN低.同时本文也对未考虑节点移动方向的CS-DTN进行了分析,当缓存足够大