DTN中一种网络状态感知的概率路由算法

发布时间：2019-09-24 19:54

【摘要】：容迟/容断网络(DTN)是一类支持在大时延、链路间歇中断等受限条件下进行通信的新型网络体系.针对DTN中由于节点移动性、缓存空间受限等而不能保证消息可靠传输的问题,提出一种网络状态感知的概率路由算法NSAPR(network situation-aware probabilistic routing algorithm).该算法依据节点之间的历史接触成功率获取网络状态信息,在转发决策时引入接触成功率的影响,并根据网络状态采取自适应的参数选取策略进行消息的转发和副本的删除,同时进行相应的队列管理和拥塞控制,从而优化中继节点的选择和减少对网络资源的浪费.仿真实验表明,与现有其他几种算法相比,该算法能够在不同网络状态下提高消息交付率并降低网络开销,具有较好的网络适应性.
【图文】：

示例,算法,消息,接触频率

状态．PROPHET仅根据历史接触频率进行转发决策，而没有考虑节点的自身性能，难以反映投递概率值的准确性．如图1所示，节点A有消息m需要发送给节点D，B和C为中间转发节点，且与A的接触频率基本相同．节点C的缓存空间比较有限，A与C之间数据传输率较低，消息传输经常失败，而节点B的性能较好，与A之间消息传输成功的可能性较大．PROPHET以历史接触频率为依据，则A对B与C的投递概率值几乎相同．然而B为较理想的转发节点，将更多的消息转发给节点B会提高消息到达目的节点D的可能性．图1PROPHET算法示例Fig．1ExampleofPROPHETalgorithm基于此，本文提出接触成功率(probabilityofsuccessfulcontact)的概念，记为Ps=N/M(N≤M)，其中M为两节点的历史接触次数，N为两节点的接触成功次数，接触成功即消息在节点之间传输成功．Ps的大小反映了两节点的历史传输消息状况，假设节点性能不会发生突变，则Ps在很大程度上决定了未来的接触成败情况．本文基于PROPHET算法提出一种网络状态感知的概率路由算法(networksituation-awareprobabilisticroutingalgorithm，NSAPR)，在计算投递概率时同时考虑历史接触频率和接触成功率，根据网络状态自适应调整路由参数，使消息在传输过程中能够选择更有可能接触成功的理想节点，从而提高消息的交付率．2．2算法合理性分析本文采用马尔可夫链对算法的合理性进行分析．假设节点A与节点B的历史接触次数为M，接触成功次数为N，建立N的有限状态空间的马尔科夫链X(n)(n=0，1，2，…)，状态空间为{0，1，2，…，i，…，M}．N的初始状态为0，接触成功时N由状态i变为状态i+1，接触失败时N保持状态i不变．设由状态i转移到状态i+1的概率为Pi，i+1，由状态i转移到状态i的概率为Pi，i．以历史接触

状态转移概率,成功率

in(1－NM)n(11－NM－1)i，0≤i≤n0，i＞{n(n≤M)(3)2)当N=0即每次接触均失败时:状态转移概率为Pi，i+1=0Pi，i{=1，Q(M+1)×(M+1)为M+1阶单位阵，P(n)i=(1，0，0，…，0)．3)当N=M即每次接触均成功时:状态转移概率为Pi，i+1=1Pi，i{=0，P(n)i=(0，0，…，1，…，0)(仅当i=n时为1，其余为0)．由此可以求出n步转移后状态为i的概率P{X(n)=i}．在式(3)中令i=n，则P{X(n)=n}=(N/M)n，n分别取5和10，，N/M在0～1之间取值，P的变化如图2所示．由图2可图2状态转移概率Fig．2Statetransitionprobability以看出，随着历史接触成功率的增加，n步转移后状态为n即每次接触均成功的概率也逐渐增加，且转移步数越少概率越大，因此基于历史接触成功率进行转发决策是比较合理的．3算法设计3．1消息转发在NSAPR算法中，概率更新公式(4)和老化公式(5)引入接触成功率，传递公式(6)与PROPHET保持一致．P(a，b)=P(a，b)·old+(1－P(a，b)old－δ)×Pinit×CNM(4)P(a，b)=P(a，b)old×γk(1－NM)(5)P(a，b)=P(a，c)old+(1－P(a，c)old)×P(a，b)×P(b，c)×β(6)其中，C为接触成功率对投递概率的影响因子(C＞1且Pinit·C＜1)，δ为P(a，b)的上限因子．该算法基于历史信息，接触成功率越高则投递概率越大，节点之间越容易进行消息转发;同时，接触成功率高则对该节点的投递概率老化变慢，可146小型微型计算机系统2013年
【作者单位】：空军工程大学信息与导航学院;
【基金】：全军军事学研究生课题(2011XXXXX-523)资助
【分类号】：TP393.02

【相似文献】