一种基于深空延迟容忍网络的改进概率路由方法

摘要

本发明提供一种基于深空延迟容忍网络的改进概率路由方法，能够解决网络开销大，易造成网络拥塞的问题。所述方法包括：当两节点接触时，根据节点相遇概率、节点连接时间比率及节点消息投递率所占的比重，计算当前节点所接触的节点到目的节点的可行性概率和当前节点到目的节点的可行性概率；判断当前节点所接触的节点到目的节点的可行性概率是否大于等于当前节点到目的节点的可行性概率；若大于等于当前节点到目的节点的可行性概率，则判断当前节点所接触的节点的剩余缓存空间是否能容纳新到达的消息副本；若不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理。本发明适用于深空延迟容忍网络技术领域。

说明书

技术领域

本发明涉及深空延迟容忍网络技术领域，特别是指一种基于深空延迟容忍网络的改进概率路由方法。

背景技术

延迟容忍网络(Delay Tolerant Network，简称DTN)是一种端到端之间缺乏持续可靠连接的网路。DTN往往具有高延迟，低传输率，间歇型连接、节点频繁移动，延迟容忍、错误容忍、有限的存储及通信环境恶劣等特点，使得传统的基于TCP/IP的端到端通信的互联网技术无法很好地为其提供服务。鉴于DTN的独特性。DTN路由作为延迟容忍网络中的重中之中，成为广大研究人员的首要研究对象。根据路由策略的不同，现有DTN路由策略主要可分为消息复制/洪泛策略、转发策略、历史/预测策略、概率策略和编码策略等。消息复制/洪泛策略路由为增加消息传输成功概率，由中继节点将消息进行复制，并以泛洪机制转发到下一跳节点，直至目的节点为止；转发策略路由根据网络拓扑信息选择最佳路径，消息由此路径以逐跳方式转发至目的节点；历史/预测策略路由采用估计的方式，将历史消息传输到目的节点的情况作为先验知识，中继节点通过决策，决定消息的转发；概率策略路由根据节点移动类型或网络拓扑信息的某种概率分布来进行消息转发；编码策略路由转变了传统路由策略的思路，将网络编码或纠删码引入消息转发中，解决消息传输过程中面临的丢弃问题，提高网络吞吐量，均衡网络负载。

基于概率策略的路由算法是Prophet路由协议中的一种方法，该路由协议是一种典型的概率路由协议，利用相遇概率来描述某一节点与其他节点接触的可能性大小。每个节点都保存着其到达其他节点的概率信息，当两节点接触时，先更新各自维护的相遇概率表，然后通过比较节点与消息目的节点的相遇概率的大小来决定是否转发该消息。

电子科技大学的杨炎在其学位论文的研究中提出一种基于历史相遇和传输信息的概率路由算法的改进方案，路由算法设计时将路由中继节点的选择转化为考虑节点运动活跃性、节点剩余能量等多个路由影响因子的多目标优化问题。使用线性优化的方式计算节点的效用值，并根据该效用值大小按比例地转发消息副本，以实现最优的路由决策，但该方法并没有考虑到网络开销变大，易造成网络拥塞的问题。

发明内容

本发明要解决的技术问题是提供一种基于深空延迟容忍网络的改进概率路由方法，以解决现有技术所存在的网络开销大，易造成网络拥塞的问题。

为解决上述技术问题，本发明实施例提供一种基于深空延迟容忍网络的改进概率路由方法，包括：

当两节点接触时，根据节点相遇概率、节点连接时间比率及节点消息投递率所占的比重，计算当前节点所接触的节点到目的节点的可行性概率和当前节点到目的节点的可行性概率；

判断当前节点所接触的节点到目的节点的可行性概率是否大于等于当前节点到目的节点的可行性概率；

若大于等于当前节点到目的节点的可行性概率，则判断当前节点所接触的节点的剩余缓存空间是否能容纳新到达的消息副本；

若不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理。

进一步地，所述方法还包括：

根据公式：F_(a,b)＝argmax[α*P_(a,b)+β*R_(a,b)+γ*I_(a,b)]计算节点可行性概率；

其中，F_(a,b)表示节点可行性概率，P_(a,b)、R_(a,b)、I_(a,b)分别表示节点相遇概率、节点连接时间比率、节点消息投递率，α、β、γ分别表示节点相遇概率、节点连接时间比率、节点消息投递率的权重。

进一步地，所述方法还包括：

在一次传输过程中，若节点A和节点B不会相遇，则根据公式：

P_(a,b)＝P_(a,b)old×σ^k

对节点相遇概率进行概率衰减；

其中，节点A为储存消息的当前节点，节点B为与节点A相遇过但本次不相遇的节点，P_(a,b)表示节点A和节点B的相遇概率，σ为衰减因子，P_(a,b)old表示节点A和节点B上一次相遇时的相遇概率，k表示节点A和节点B从上次相遇到现在为止所经过的时间间隔。

进一步地，所述方法还包括：

在一次传输过程中，若节点A和节点B相遇并建立连接，则根据公式：

P_(a,b)＝P_(a,b)old+(1-P_(a,b)old)×P_init

更新节点相遇概率；

其中，节点A为储存消息的当前节点，节点B为与节点A相遇的节点，P_(a,b)表示节点A和节点B的相遇概率，P_(a,b)old表示节点A和节点B上一次相遇时的相遇概率，P_init表示最初节点A和节点B的相遇概率。

进一步地，所述方法还包括：

若节点A和节点C接触，且节点C和节点B接触，则将节点A的消息传递给节点B时，根据公式：

P_(a,b)＝P_(a,b)old+(1-P_(a,b)old)×P_(a,c)×P_(c,b)×δ

更新节点相遇概率；

其中，节点A为储存消息的当前节点，P_(a,b)表示节点A和节点B的相遇概率，δ表示传递影响因子,P_(a,b)old表示节点A和节点B上一次相遇时的相遇概率，P_(a,c)表示节点A和节点C的相遇概率，P_(c,b)表示节点C和节点B的相遇概率。

进一步地，所述若不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理包括：

判断当前节点所接触的节点的报文生存时间是否小于等于零；

若当前节点所接触的节点的报文生存时间等于或者小于零，则当前节点所接触的节点自动丢弃报文。

进一步地，所述方法还包括：

若当前节点所接触的节点的报文生存时间大于零且出现网络拥塞，则将报文按转发次数由大到小进行排序，并按照排序顺序丢弃报文直至当前节点所接触的节点能容纳新到达的消息副本。

进一步地，所述将报文按转发次数由大到小进行排序，并按照排序顺序丢弃报文直至当前节点所接触的节点能容纳新到达的消息副本包括：

将报文按转发次数由大到小进行排序，将转发次数较多的报文放在队尾，转发次数较少的报文放在队头；

按照优先丢弃队尾的顺序开始丢弃报文直至当前节点所接触的节点能容纳新到达的消息副本。

进一步地，所述方法还包括：

若当前节点所接触的节点的剩余缓存空间能容纳新到达的消息副本，则当前节点向其接触的节点传递消息。

进一步地，所述方法还包括：

若当前节点所接触的节点到目的节点的可行性概率小于当前节点到目的节点的可行性概率，则当前节点不向其接触的节点传递消息。

本发明的上述技术方案的有益效果如下：

上述方案中，当两节点接触时，根据节点相遇概率、节点连接时间比率及节点消息投递率所占的比重，计算当前节点所接触的节点到目的节点的可行性概率和当前节点到目的节点的可行性概率；判断当前节点所接触的节点到目的节点的可行性概率是否大于等于当前节点到目的节点的可行性概率；若大于等于当前节点到目的节点的可行性概率，则判断当前节点所接触的节点的剩余缓存空间是否能容纳新到达的消息副本；若不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理，从而解决网络开销大，易造成网络拥塞的问题，且能够节省网络资源、减小了延时、提高消息传输的效率。

附图说明

图1为本发明实施例提供的基于深空延迟容忍网络的改进概率路由方法的流程示意图；

图2为本发明实施例提供的节点路由信息表示意图；

图3为本发明实施例提供的基于深空延迟容忍网络的改进概率路由方法的详细流程示意图

图4为本发明实施例提供的节点消息队列示意图。

具体实施方式

为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附图及具体实施例进行详细描述。

本发明针对现有的网络开销大，易造成网络拥塞的问题，提供一种基于深空延迟容忍网络的改进概率路由方法。

参看图1所示，本发明实施例提供的基于深空延迟容忍网络的改进概率路由方法，包括：

S101，当两节点接触时，根据节点相遇概率、节点连接时间比率及节点消息投递率所占的比重，计算当前节点所接触的节点到目的节点的可行性概率和当前节点到目的节点的可行性概率；

S102，判断当前节点所接触的节点到目的节点的可行性概率是否大于等于当前节点到目的节点的可行性概率；

S103，若大于等于当前节点到目的节点的可行性概率，则判断当前节点所接触的节点的剩余缓存空间是否能容纳新到达的消息副本；

S104，若不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理。

本发明实施例所述的基于深空延迟容忍网络的改进概率路由方法，当两节点接触时，根据节点相遇概率、节点连接时间比率及节点消息投递率所占的比重，计算当前节点所接触的节点到目的节点的可行性概率和当前节点到目的节点的可行性概率；判断当前节点所接触的节点到目的节点的可行性概率是否大于等于当前节点到目的节点的可行性概率；若大于等于当前节点到目的节点的可行性概率，则判断当前节点所接触的节点的剩余缓存空间是否能容纳新到达的消息副本；若不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理，从而解决网络开销大，易造成网络拥塞的问题，且能够节省网络资源、减小了延时、提高消息传输的效率。

本实施例中，针对延迟容忍网络中存在的节点移动和链路频繁变化等特点，在原有的prophet路由算法的基础上，引入新的度量标准：节点可行性概率，所述节点可行性概率综合考虑了节点相遇概率、节点连接时间比率及节点消息投递率等因素。

本实施例中，基于新引入的度量标准：节点可行性概率，提出了一种改进概率路由的方法，当两节点接触(也可以称为：相遇)后交换路由信息，通过节点相遇概率、节点连接时间比率及节点消息投递率所占的比重计算出节点可行性概率并更新节点可行性概率，能够减小延时，提高消息传输的效率，并给出了网络拥塞的处理方法，节省了网络资源。

本实施例所述的基于深空延迟容忍网络的改进概率路由方法的具体步骤可以包括：

建立新的节点路由信息表，如图2所示，所述节点路由信息表包括：当前节点，下一节点，(节点)相遇概率，(节点)相遇时间，(节点)断开时间，(节点)相遇次数，(节点相遇)周期以及(节点)消息投递率。建立的节点路由信息表用于在一段周期内，记录当前节点与下一跳节点相遇概率等参数；节点路由信息表在两个节点相遇后会更新如图2所示，在一个周期内节点A和节点B相遇两次，那么节点连接时间为：

H_(a,b)＝(t_e1-t_s1)+(t_e2-t_s2)

其中，H_(a,b)表示节点连接时间，H_(a,b)表示节点A和节点B从这次连接开始到结束的这段时间间隔，t_e1、t_e2表示节点A和节点B两次断开的时间，

t_s1、t_s2表示节点A和节点B两次相遇的时间。

本实施例中，节点相遇概率用P_(a,b)表示，P_(a,b)表示节点A和节点B的相遇概率；节点相遇周期用T_(a,b)表示，T_(a,b)表示节点A和节点B从这次相遇连接开始到下一次相遇的这段时间间隔；用R_(a,b)＝H_(a,b)÷T_(a,b)表示节点连接时间比率；并用I_(a,b)表示节点消息投递率。

本实施例中，进一步地，根据公式：

F_(a,b)＝argmax[α*P_(a,b)+β*R_(a,b)+γ*I_(a,b)]

计算节点可行性概率；

其中，F_(a,b)表示节点可行性概率，P_(a,b)、R_(a,b)、I_(a,b)分别表示节点相遇概率、节点连接时间比率、节点消息投递率，α、β、γ分别表示节点相遇概率、节点连接时间比率、节点消息投递率的权重，α、β、γ∈[0,1]，且α+β+γ＝1，α、β、γ的值是设定的。

如图3所示为本实施例提供的基于深空延迟容忍网络的改进概率路由方法的具体流程图，在一次传输过程中，若节点A和节点B不会相遇，则根据公式：

P_(a,b)＝P_(a,b)old×σ^k

对节点相遇概率进行概率衰减；

其中，节点A为储存消息的当前节点，节点B为与节点A相遇过但本次不相遇的节点，P_(a,b)表示节点A和节点B的相遇概率，σ为衰减因子，σ∈[0,1]，此时的σ可以取0.6，P_(a,b)old表示节点A和节点B上一次相遇时的相遇概率，k表示节点A和节点B从上次相遇到现在为止所经过的时间间隔，可以从节点路由信息表中读取结果。

在一次传输过程中，若节点A和节点B相遇并建立连接，则根据公式：

P_(a,b)＝P_(a,b)old+(1-P_(a,b)old)×P_init

更新节点相遇概率；

其中，节点A为储存消息的当前节点，节点B为与节点A相遇的节点，P_(a,b)表示节点A和节点B的相遇概率，P_(a,b)old表示节点A和节点B上一次相遇时的相遇概率，P_init表示最初节点A和节点B的相遇概率/节点路由信息表中存储的原始相遇概率，P_init∈[0,1]，可以令P_init取0.8。

若节点A和节点C接触，且节点C和节点B接触，那么节点C作为中继节点，则将节点A的消息传递给节点B时，根据公式：

P_(a,b)＝P_(a,b)old+(1-P_(a,b)old)×P_(a,c)×P_(c,b)×δ

更新节点相遇概率；

其中，节点A为储存消息的当前节点，P_(a,b)表示节点A和节点B的相遇概率，δ表示传递影响因子,可令δ＝0.8,P_(a,b)old表示节点A和节点B上一次相遇时的相遇概率，P_(a,c)表示节点A和节点C的相遇概率，P_(c,b)表示节点C和节点B的相遇概率,由此公式可以看出节点相遇概率具有传递性，可以通过传递性计算出任一节点到目的节点的相遇概率，再由相遇概率计算出可行性概率。

本实施例中，根据公式:F_(a,b)＝argmax[α*P_(a,b)+β*R_(a,b)+γ*I_(a,b)]将节点相遇概率，节点连接时间比率，节点消息投递率整合计算出当前节点所接触的节点到目的节点的可行性概率、当前节点到目的节点的可行性概率，并判断当前节点所接触的节点到目的节点的可行性概率是否大于当前节点到目的节点的可行性概率，如果当前节点所接触的节点到目的节点的可行性概率小于当前节点到目的节点的可行性概率，则当前节点不向其接触的节点传递消息，直接结束；

如果当前节点所接触的节点到目的节点的可行性概率是大于等于当前节点到目的节点的可行性概率，再判断当前节点所接触的节点的剩余缓存空间是否能容纳新到达的消息副本，若当前节点所接触的节点的剩余缓存空间能容纳新到达的消息副本，则当前节点向其接触的节点传递消息；

若当前节点所接触的节点的剩余缓存空间不能容纳新到达的消息副本，则利用当前节点所接触的节点的报文生存时间丢弃策略对缓存进行管理，具体方法为：每个报文在生产的时候都有一个初始生存时间(Time To Live，TTL)值，但随着转发次数的增加，TTL值会依次减小，当当前节点缓存的报文TTL值等于或者小于零时，则当前节点所接触的节点自动丢弃报文，避免占用节点缓存网络资源、增加网络开销；

若当前节点缓存的报文TTL值均大于零时，但又出现网络拥塞的问题时，将报文按转发次数由大到小进行排序，如图4所示，节点消息队列中按照报文被转发的次数排序，即转发次数较多的报文放在队尾，转发次数较少的报文放在队头，并按照优先丢弃队尾的顺序开始丢弃报文直至当前节点所接触的节点能容纳新到达的消息副本，通过此方法可以缓解网络拥塞的问题；图4中，Message_n表示报文，下标n来区分不同的报文，Q_n表示对应的报文转发的次数。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。