一种基于低轨卫星网络的容迟/容断网络路由计算方法

摘要

本发明公开了一种基于低轨卫星网络的容迟/容断网络路由计算方法，包括以下步骤：构建卫星DTN网络系统模型；计算排队时延影响下的链路时延；计算接触剩余容量；计算路由。本发明考虑了路由计算中排队时延的影响，定义了一个队列要素并且提出了一种队列调度机制；为了避免已选择的路径无法转发消息的问题，考虑了接触容量的影响；通过设计一个消息路径更新因素，提出了一种路由更新策略，来打破传输实时更新和资源消耗之间的平衡。本发明能够减少网络中冗余的消息副本，降低消息的平均传输时延和网络负载率。本发明把剩余容量足够用来传输消息，并且时延最低的路径当作参考路径，能对通信过程中的一些突发故障等有较好的适应性。

说明书

技术领域

本发明涉及低轨卫星网络的路由策略，特别是一种基于低轨卫星网络的容迟/容断网络路由计算方法。

背景技术

卫星网络具有有限的传输能量、快速的移动性、频繁的切换、稀疏的节点密度、频繁的设备故障和时变拓扑等特点，卫星网络是间断性的接触，使其形成了一个典型的延迟/中断容忍网络(Delay/Disruption Tolerant Network，DTN)。如图1所示，DTN协议体系的核心思想是引入所谓的“包裹层”作为连接不同受限网络的覆盖层，采用此覆盖的节点依靠发送称为“包裹”的异步消息进行通信，所以DTN协议体系结构是一种面向受限网络的“容延迟的、面向消息的覆盖层体系结构”。这里所说的覆盖层是端到端的面向消息的附加层，称之为“Bundle层”，位于传输层和应用层之间。DTN具有两个显著的特点：一是DTN不假设存在发送端与接收端的端到端路径，包裹采用存储转发的方法进行传递；二是DTN引入了所谓的“包裹层”作为连接不同受限网络的覆盖层，采用此覆盖的节点依靠发送称为“包裹”的异步消息进行通信。

主流的DTN路由算法可以分为以下三类：①基于洪泛的路由算法，以Epidemic算法、Spray and Wait算法和PRoPHET算法为代表，此类路由算法通过增加消息副本，并按照一定的策略进行转发来增大消息投递率。因为这类路由方法不需要知道网络的任何信息就可以进行路由计算，所以计算复杂度很低，但是多副本增加了网络资源消耗，不适用于资源有限的卫星网络；②基于知识库的路由算法，以MED算法和ED算法为代表，此类路由算法使用根据传输延迟时间和传播延迟的计算预测边缘的链路的发生，并且所预测的接触可以识别一个源节点到该消息的目的节点的第一路径。该类算法降低了网络冗余，但由于采用了源路由选择，并且计算路径时不考虑中间节点的存储空间状态和系统中消息的情况，不能很好适应卫星网络的高动态性，带来大的消息传输时延；③基于连接图的路由算法，CGR路由算法，此类路由算法充分利用了卫星节点间接触的可预测性和周期性，消息每到达一个中间节点时，都会根据拥有全网节点的接触信息重新计算转发路径，这能很好的适应网络的动态性。但由于在路由计算时，未考虑消息的排队延时，导致消息可能错过当前可用的接触机会，一定程度上降低了平均传输时延和延时网络负载率。

发明内容

为解决现有技术存在的上述问题，本发明要设计一种能减少网络中冗余的消息副本和降低平均传输时延迟的基于低轨卫星网络的容迟/容断网络路由计算方法。

为了实现上述目的，本发明的技术方案如下：一种基于低轨卫星网络的容迟/容断网络路由计算方法，包括以下步骤：

A、构建卫星DTN网络系统模型

基于网络中所有节点间的接触关系，建立接触图模型，令G＝(V,E)代表卫星DTN网络，其中节点集合V为卫星和地面站网络节点的集合；边集E为星间链路、星地链路通信链路的集合。对每条接触e∈E都用cp_e(t)表示每条接触的接触时间段集合，即：

其中表示当前链路的第i次接触机会的开始时间，表示当前链路的第i次接触机会的结束时间。定义一个参数RC_e(t)∈R⁺∪{+∞}表示接触的当前剩余容量。此外，由于DTN网络中每个节点的资源都是有限的，所以对于每个v∈V，用buf(v,t)∈R⁺∪{+∞}表示t时刻节点v的剩余缓存大小。

B、计算排队时延影响下的链路时延

消息尽早被送达目的节点能够降低消息对整个网络的资源需求，这同时间接地提高消息的投递率。链路时延包括以下三种综合时延：

B1、传输时延：消息从开始发送到完全进入链路之间的时间间隔。消息的估计容量消费ECC定义为消息的大小和估计的总体聚合层消费总量之和。则传输时延从下式获得：

其中，Rate(e)表示链路的速率，假设它是一个恒定值。

B2、传播时延：消息在通信链路中传输所需要的时间。卫星网络中，总的通信链路长度为所有参与通信过程的星间、星地通信链路长度的和。两颗卫星之间的距离关系，通过瞬时地心角和卫星的轨道高度计算得到，而瞬时地心角的计算方法如下：

α＝arccos[sinα₁sinβ₁+cosα₂cosβ₂cos(α₁-α₂)]>

(α₁,β₁)、(α₂,β₂)为两个卫星星下点的经纬度。星间距离计算公式如下：

其中R表示地球的半径，H₁表示卫星A的高度，H₂表示卫星B的高度。把瞬时地星角代入公式(3)，求出两颗卫星之间的距离。

链路长度之和L_sum为：

L_sum＝∑L_i,i＝1,2,3…n>

其中L_i表示消息经过各条链路的长度，其中n∈N⁺。则传播时延为

t_pro＝L_sum/C>

其中，C表示光速。

B3、排队时延：从接触有效到该消息开始传输这两颗卫星之间的时间间隔。定义一个排队因子que确定刚到达的消息在节点队列中的位置，该排队因子que综合考虑消息的优先级、ECC、传播时延、传输时延和剩余生存时间。

其中，t_tra和t_pro分别表示传输时延和传播时延，T为时间常数。在仿真部分，设置ECC服从参数为K的泊松分布，即：ECC～P(K)。Prio表示消息的优先级，共有三种优先级：分别是bulk、standard和expedited，分别表示大宗、标准和加快。Sur(t)表示当前消息的剩余生存时间，DTN中每个消息发送时都定义一个消息生存时间TTL，所以Sur(t)定义为：

Sur(t)＝TTL-(t-t_create)>

其中，t为当前时刻，t_create为消息的创建时刻。式(6)中系数w_i表示优先级、ECC、传播时延、传输时延和剩余生存时间的权重系数，采用层次分析法AHP计算权重系数，i＝1、2、3、4。由决策人给出相对重要性，用α_pq表示属性p和q的相对重要性，即，把它当作属性p的权重w_p和属性q的权重w_q两者的比值，α_pq＝w_p/w_q。用n个目标进行两两比较所得到的结果组成判断矩阵A：

则有(A-nI)w＝0，其中I表示单位判断矩阵，如果估计的比较准确，那么上式就为0；如果估计的没那么准确，那么A中元素但凡有小的摄动，本征值也会随之产生小的摄动，因此得到：

Aw＝λ_maxw>

式(9)中λ_max表示的是判断矩阵A的最大本征值，根据该式计算出的本征向量，也就是代表n个参数权重的向量w＝[w₁,w₂,…,w_n]^T的值。

为了衡量判断矩阵A的准确性，引入一个一致性比率CR，一致性比率CR等于一致性指标CI除以随机指标RI，CR的值用于衡量判断矩阵A的可靠性。

如果CR＞0.1，说明对于各元素α_pq估计的一致性太低，需要重新进行估计；如果CR＜0.1，为α_pq的估计基本一致，用式(9)求得w。

当有消息到达节点时，使用式(6)计算、更新所有消息的排队因子que，把新消息插入队列的适当位置。然后就计算消息的排队时延：

其中，Q(e,t,u)表示时刻t排在此消息之前的所有消息的ECC之和。

C、计算接触剩余容量

在步骤A建立的模型中，定义Q(e,t,s)为本地节点s在时刻t获取的接触e源端的队列长度，即为时刻t在节点s队列中存储的所有消息的ECC之和；t_residual(e)为接触e的剩余时间；m为当前传输的数据大小。

假设当前网络中有一个节点u经接触e发送消息给节点v，接触e的传输速率为Rate(e)，设当数据到达节点u时，接触e还没有结束，即那么：

RC_e(t_arrival(u))＝Rate(e)*t_residual(e)-Q(e,t_arrival(u),u)>

其中，和分别表示接触e的第i次接触机会的开始时间和结束时间。

发送节点传输消息时，综合考虑当前队列中长度Q(e,t,s)、时刻t与接触机会的容量、剩余容量的关系：

C1、如果消息传输时，接触还没有开始，则需要计算下一个接触的容量，如果够用，则等待接触开始，反之则考虑再下一个接触机会；

C2、如果消息传输时，接触已经开始，则需要计算当前接触的剩余容量RC_e(t)，如果够用，则发送消息，反之则考虑下一个接触机会。

D、计算路由

利用接触的时变代价计算最优路径，具体计算方法如下：

其中w(e,t)表示消息在时刻t沿接触e发送的代价，除了和接触、时间有关外，还与当前消息大小和本地节点有关。所以代价函数又写为：

w(e,t)＝w′(e,t,m,s)

其中m为消息的大小，s为开始迪杰斯特拉dijsktra算法的节点。其计算方法为：

w′(e,t,m,s)＝t′(e,t,m,s)-t+d(e,t) (13)

其中，

上式中的t′表示将消息m沿接触e注入到网络中的最早时间，d(e,t)为传输时延函数。

E、更新优化路由

当卫星网络拓扑发生改变时，需要重新计算消息的传输路径。而当发送节点队列中的一个消息发送出去后，导致当前消息的排队时延发生改变，之前计算的传播路径此时已经不是最优，所以同样需要重新计算最优下一跳，但在卫星网络中，为消息队列中的每一个消息在任意时刻计算路由开销难以实现，并且也会影响节点资源的有效利用。设定一个消息路径更新因子β，定义为队列中当前消息的排队时延与当前接触有效时间的比值，即：

对同一次接触来说，消息路径更新因子β越高，说明消息在队列中等待时间越长，对网络高动态的适应性越差，会导致先前计算的下一跳不是最优或者发送失败。这间接地降低了消息的投递率，增大了消息的传输时延。理论上应该实时更新消息的最优下一跳，但这会增大计算的复杂度，造成极大的开销。

设定一个路由更新阈值λ，优化路由更新策略。根据消息路径更新因子β不同取值，采取不同的路由更新方案，具体方案如下：

E1、当β＞λ时，需要更新消息的排队时延并重新计算消息转发的下一跳节点；

E2、当β≤λ时，仍然按照之前计算好的下一跳节点进行转发。

进一步地，步骤E1中所述的路由更新阈值λ与消息平均传输时延直接相关，不同网络拓扑下，λ的取值为0.3～0.9。

进一步地，步骤B1中所述的Rate(e)取值为4.8-5.1Mbps。

进一步地，步骤B3中所述的bulk、standard和expedited分别设为常数0.9、0.6和0.3。

进一步地，步骤B3中所述的一致性指标CI用以下公式计算：

λ_max表示的是判断矩阵A的最大本征值，n表示的是判断矩阵A的除数。

进一步地，步骤B3中所述的随机指标RI的值如下：

n＝2，RI＝0.0；

n＝3，RI＝0.58；

n＝4，RI＝0.90；

n＝5，RI＝1.12；

n＝6，RI＝1.24；

n＝7，RI＝1.32；

n表示的是判断矩阵A的除数。

与现有技术相比，本发明具有以下有益效果：

1、为了克服DQN算法和CGR算法的不足，本发明提出了一种适用于低轨卫星DTN网络的路由算法，简称ICGR。本发明考虑了路由计算中排队时延的影响，定义了一个队列要素并且提出了一种队列调度机制；为了避免已选择的路径无法转发消息的问题，考虑了接触容量的影响；通过设计一个消息路径更新因素，提出了一种路由更新策略，来打破传输实时更新和资源消耗之间的平衡。本发明能够减少网络中冗余的消息副本，降低消息的平均传输时延和网络负载率。

2、本发明把剩余容量足够用来传输消息，并且时延最低的路径当作参考路径。源节点把该路径写入消息对应的数据域中，消息按照参考路径传递，但每每传递到一个节点的时候都会重新计算路径，这样能对通信过程中的一些突发故障等有较好的适应性。但采用这种分布式的路由计算会导致消息的震荡现象，因此算法对于不同的网络规定了消息的最大传输跳数，对于超过最大传输跳数的消息采用直接丢弃的策略。

附图说明

图1是DTN架构与传统网络架构对比示意图。

图2是接触图模型示意图。

图3是星间距离示意图。

图4是本发明的流程图。

具体实施方式

下面结合附图对本发明进行进一步地描述。如图4所示，本发明针对传统卫星网络长时延、大时空、资源受限等问题，提出将DTN协议体系用于卫星网络，即卫星DTN网络，并发明了一种适用于低轨卫星DTN网络的路由算法ICGR。为构建卫星DTN网络系统模型，首先基于网络中所有节点间的接触关系，建立接触图模型。如图2所示即为步骤A中的接触图模型示意图。在ICGR算法中，考虑到了传播时延，为更好的计算传播时延，给出了星间距离示意图，图3所示为步骤B2中的星间距离示意图。本发明考虑了路由计算中排队时延的影响，定义了一个队列要素并且提出了一种队列调度机制；为了避免已选择的路径无法转发消息的问题，本发明考虑了接触容量的影响；通过设计一个消息路径更新因素，提出了一种路由更新策略，来打破传输实时更新和资源消耗之间的平衡。理论上的分析可以证明，该缓存控制策略可以提高卫星DTN网络中消息的投递率，降低消息的平均传输时延和网络负载

本发明不局限于本实施例，任何在本发明披露的技术范围内的等同构思或者改变，均列为本发明的保护范围。