一种基于介数中心性的卫星网络备份路由计算方法及系统

摘要

本发明涉及一种基于介数中心性的卫星网络备份路由计算方法及系统，方法包括：构建无权图；所述无权图的节点为卫星网络中的卫星节点，所述无权图的边为所述卫星节点之间的通信链路；利用介数中心性计算各所述卫星节点的重要程度，获得重要节点；利用蚁群算法计算所述卫星节点中的源卫星节点和目的卫星节点之间的最短延时路径；判断所述最短延时路径中是否包含所述重要节点；若所述最短延时路径中包含所述重要节点，则为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。本发明根据介数中心性计算卫星节点的重要程度，只针对含有重要节点的最短延时路径计算备份路由，在有效提高卫星网络抗毁性能的同时，降低了路由计算的时间开销。

说明书

技术领域

本发明涉及卫星通信技术领域，特别是涉及一种基于介数中心性的卫星网络备份路由方法及系统。

背景技术

卫星通信是指利用人造地球卫星作为中继站来转发无线电波，在两个或多个地球站之间进行的通信。具有通信距离远，不受地理环境限制等优点，可以为人类日益增长的信息需求提供可靠的网络数据服务。而卫星节点位于太空之中，一旦失效，不易立即修复，特别是在未来的空间攻防中，卫星节点被动失效的概率大大增加。

网络的弹性能力为：网络在面对各种故障和正常运行挑战时提供和维持可接受服务水平的能力。目前已有一系列传统方案来解决网络的弹性抗毁问题，例如基于冗余思想的多径备份策略、动态重路由策略，可有效提高卫星网络的弹性抗毁能力。但是多径备份和重路由都会引起额外的时间开销，而卫星通信本就因为通信距离远而导致通信时延较大，因此单纯地使用以上策略很可能导致通信时延过大而难以被用户接受。

考虑到上述方法的劣势，需要设计一种卫星网络备份路由方法或系统，在有效提高卫星网络抗毁性能的同时，尽量降低路由计算的时间开销。

发明内容

本发明的目的是提供一种基于介数中心性的卫星网络备份路由方法及系统，使得在有效提高卫星网络抗毁性能的同时，降低路由计算的时间开销。

为实现上述目的，本发明提供了如下方案：

一种基于介数中心性的卫星网络备份路由计算方法，包括：

构建无权图；所述无权图的节点为卫星网络中的卫星节点，所述无权图的边为所述卫星节点之间的通信链路；

利用介数中心性计算各所述卫星节点的重要程度，获得重要节点；

利用蚁群算法计算所述卫星节点中的源卫星节点和目的卫星节点之间的最短延时路径；

判断所述最短延时路径中是否包含所述重要节点；

若所述最短延时路径中包含所述重要节点，则为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。

可选地，若所述最短延时路径中不包含所述重要节点，则不为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。

可选地，所述利用介数中心性计算所述卫星节点的重要程度，获得重要节点，具体包括：

根据所述无权图中经过各所述卫星节点的最短路径数目和所述无权图的最短路径数目计算各所述卫星节点的节点介数；

根据所述无权图中经过各所述边的最短路径数目和所述无权图的最短路径数目计算各所述边的边介数；

根据所述节点介数和所述边介数计算所述卫星节点的重要程度；

根据所述卫星节点的重要程度获得重要节点。

可选地，所述利用蚁群算法计算所述卫星节点之间的最短路径，具体包括：

对每一所述卫星节点初始化信息素；

计算所述卫星节点的启发函数；

根据所述启发函数为蚁群算法中的蚂蚁构造路径；

根据初始化后的信息素局部更新所述路径上的信息素；

对局部更新后的路径上的信息素进行全局更新；

获取全局更新后的最短路径，记为最短延时路径。

可选地，所述备份路由计算过程如下：

获取全局更新后的次短路径，作为备份路由。

一种基于介数中心性的卫星网络备份路由计算系统，包括：

构建模块，用于构建无权图；所述无权图的节点为卫星网络中的卫星节点，所述无权图的边为所述卫星节点之间的通信链路；

获取模块，用于利用介数中心性计算各所述卫星节点的重要程度，获得重要节点；

第一计算模块，用于利用蚁群算法计算所述卫星节点中的源卫星节点和目的卫星节点之间的最短延时路径；

判断模块，用于判断所述最短延时路径中是否包含所述重要节点；

第二计算模块，用于当所述最短延时路径中包含所述重要节点时，为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。

可选地，所述获取模块具体包括：

第一计算单元，用于根据所述无权图中经过各所述卫星节点的最短路径数目和所述无权图的最短路径数目计算各所述卫星节点的节点介数；

第二计算单元，用于根据所述无权图中经过各所述边的最短路径数目和所述无权图的最短路径数目计算各所述边的边介数；

第三计算单元，用于根据所述节点介数和所述边介数计算所述卫星节点的重要程度；

第一获取单元，用于根据所述卫星节点的重要程度获得重要节点。

可选地，所述第一计算模块具体包括：

初始化单元，用于对每一所述卫星节点初始化信息素；

第四计算单元，用于计算所述卫星节点的启发函数；

路径构造单元，用于根据所述启发函数为蚁群算法中的蚂蚁构造路径；

局部更新单元，用于根据初始化后的信息素局部更新所述路径上的信息素；

全局更新单元，用于对局部更新后的路径上的信息素进行全局更新；

第二获取单元，用于获取全局更新后的最短路径，记为最短延时路径。

可选地，所述第二计算模块包括：

第三获取单元，用于获取全局更新后的次短路径，作为备份路由。

根据本发明提供的具体实施例，本发明公开了以下技术效果：

本发明公开了一种基于介数中心性的卫星网络备份路由计算方法及系统，方法包括：构建无权图；所述无权图的节点为卫星网络中的卫星节点，所述无权图的边为所述卫星节点之间的通信链路；利用介数中心性计算各所述卫星节点的重要程度，获得重要节点；利用蚁群算法计算所述卫星节点中的源卫星节点和目的卫星节点之间的最短延时路径；判断所述最短延时路径中是否包含所述重要节点；若所述最短延时路径中包含所述重要节点，则为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。本发明根据介数中心性计算卫星节点的重要程度，只针对含有重要节点的最短延时路径计算备份路由，在有效提高卫星网络抗毁性能的同时，降低了路由计算的时间开销。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的基于介数中心性的卫星网络备份路由计算方法流程图；

图2为本发明实施例提供的基于介数中心性的卫星网络备份路由计算方法原理图；

图3为本发明实施例提供的基于介数中心性的卫星网络备份路由计算方法过程图；

图4为本发明实施例提供的重要节点获取流程图；

图5为本发明实施例提供的备份路径作用机制示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明的目的是提供一种基于介数中心性的卫星网络备份路由方法及系统，使得在有效提高卫星网络抗毁性能的同时，降低路由计算的时间开销。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

如图1所示，基于介数中心性的卫星网络备份路由计算方法，方法包括：

步骤101：构建无权图；所述无权图的节点为卫星网络中的卫星节点，所述无权图的边为所述卫星节点之间的通信链路。

步骤102：利用介数中心性计算各所述卫星节点的重要程度，获得重要节点。其中，步骤102具体包括：

步骤1021：根据所述无权图中经过各所述卫星节点的最短路径数目和所述无权图的最短路径数目计算各所述卫星节点的节点介数。

步骤1022：根据所述无权图中经过各所述边的最短路径数目和所述无权图的最短路径数目计算各所述边的边介数。

步骤1023：根据所述节点介数和所述边介数计算所述卫星节点的重要程度。

步骤1024：根据所述卫星节点的重要程度获得重要节点。

步骤103：利用蚁群算法计算所述卫星节点中的源卫星节点和目的卫星节点之间的最短延时路径。其中，步骤103具体包括：

步骤1031：对每一所述卫星节点初始化信息素。

步骤1032：计算所述卫星节点的启发函数。

步骤1033：根据所述启发函数为蚁群算法中的蚂蚁构造路径。

步骤1034：根据初始化后的信息素局部更新所述路径上的信息素。

步骤1035：对局部更新后的路径上的信息素进行全局更新。

步骤1036：获取全局更新后的最短路径，记为最短延时路径。

步骤104：判断所述最短延时路径中是否包含所述重要节点。

步骤105：若所述最短延时路径中包含所述重要节点，则为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。

在本实施例中，所述备份路由计算过程如下：

获取全局更新后的次短路径，作为备份路由。次短路径为全局更新后的所有路径中长度仅长于最短路径的路径。

在本实施例中，方法还包括：

若所述最短延时路径中不包含所述重要节点，则不为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。

本实施例还提供了一种基于介数中心性的卫星网络备份路由计算系统，系统包括：

构建模块，用于构建无权图；所述无权图的节点为卫星网络中的卫星节点，所述无权图的边为所述卫星节点之间的通信链路。

获取模块，用于利用介数中心性计算各所述卫星节点的重要程度，获得重要节点。

第一计算模块，用于利用蚁群算法计算所述卫星节点中的源卫星节点和目的卫星节点之间的最短延时路径。

判断模块，用于判断所述最短延时路径中是否包含所述重要节点。

第二计算模块，用于当所述最短延时路径中包含所述重要节点时，为所述最短延时路径对应的源卫星节点和目的卫星节点计算备份路由。

在本实施例中，所述获取模块具体包括：

第一计算单元，用于根据所述无权图中经过各所述卫星节点的最短路径数目和所述无权图的最短路径数目计算各所述卫星节点的节点介数。

第二计算单元，用于根据所述无权图中经过各所述边的最短路径数目和所述无权图的最短路径数目计算各所述边的边介数。

第三计算单元，用于根据所述节点介数和所述边介数计算所述卫星节点的重要程度。

第一获取单元，用于根据所述卫星节点的重要程度获得重要节点。

在本实施例中，所述第一计算模块具体包括：

初始化单元，用于对每一所述卫星节点初始化信息素；

第四计算单元，用于计算所述卫星节点的启发函数；

路径构造单元，用于根据所述启发函数为蚁群算法中的蚂蚁构造路径；

局部更新单元，用于根据初始化后的信息素局部更新所述路径上的信息素；

全局更新单元，用于对局部更新后的路径上的信息素进行全局更新；

第二获取单元，用于获取全局更新后的最短路径，记为最短延时路径。

在本实施例中，所述第二计算模块包括：

第三获取单元，用于获取全局更新后的次短路径，作为备份路由。

以下对本发明原理进行具体说明：

(1)根据图论中边介数以及点介数的指标对卫星网络中节点以及边进行计算，并根据计算结果进行排序，筛选出网络中的的“重要节点”。仅为重要节点计算备份路由，从而达到减小时间开销的目的。

(2)在进行蚁群算法迭代时，基于以上思想，在反向蚂蚁进行路径记录时，将检测路径中是否含有重要节点，当且仅当路径中含有重要节点时，才会针对此次路由计算备份路由，以避免重要节点一旦遭到自主智能攻击或自然损毁，对卫星网络的正常通信产生影响。若路径中不含重要节点，则无须进行备份路由计算。

(3)当卫星节点自然损坏或受到自主智能攻击时，将检测当前路径是否有可选的备份路径，若存在备份路径则选择此路径进行通信转发，提高其通信成功率。

根据图论的思想，拓扑网络可用图G＝(V，E)来描述，其中V＝{V

根据图论中介数中心性的公式，针对铱星模型计算其节点介数和边介数，并根据计算结果进行统计分析，从介数值最高的节点依次进行筛选，最终选出卫星网络的“全局重要节点”，仅为重要节点计算备份路径，从而减小时间开销。

IMB-ACR算法(基于介数中心性的卫星网络备份路由计算方法)可简略分为三部分，如图2所示。

S1：根据介数中心性计算节点在全局卫星网络的重要程度，并以此进行排序筛选，将排序前20％的节点列为“重要节点”。

S2：根据源节点和目的节点，通过蚁群路由算法迭代计算出最短路径，之后对路径中包含的节点进行检测，若含有重要节点，则执行步骤S3，否则结束本次路由计算，仅为源节点和目的节点计算一条最短路由。

S3：将重要节点从节点候选集删除，并为其计算备份路由。此时，为源节点和目的节点计算了两条路由，一条作为首选路由，在节点无异常情况时启用。一条作为备份路由，在节点失效时方才启用。

如图3所示，步骤S1-S3具体过程如下：

S11：令C

S12：令C

S13：将所得节点介数和边介数经过统计分析，按照介数值由高到低依次进行筛选(若两个节点的介数值都较高，则两点之间的边介数值也会较高，因此最终以节点介数为标准进行筛选)，最终根据卫星网络规模的大小，选择一定数量的节点作为网络中的“全局重要节点”。图4为本发明实施例提供的重要节点获取流程图。

步骤S2具体过程如下：

S21：对于每个卫星s，初始化信息素。对于每个目的卫星d，在t时刻建立从卫星s到卫星d的邻居节点候选集，用

其中，|d

S22：网络中所有由源节点发往目的节点的蚂蚁在选择下一跳节点时，均需要计算节点j被选为下一跳节点的概率。计算规则如下：

其中，p

S23：当前向蚂蚁发现当前节点在使用最优路径传输数据过程中，如果当前节点符合时延约束，则需要进行局部信息素更新，信息素更新规则如下：

其中，Δl为蚂蚁实际走过的路径长度与最短路径长度的差值，ω为衰减常数，a

S24：当探寻路径的前向蚂蚁被阻塞或到达目的卫星后，需要产生后向蚂蚁，沿着前向蚂蚁探索到的路径返回源卫星，并执行信息素全局更新，更新规则如下：

τ

其中，ρ为信息素衰减参数，ρ∈(0,1)，flag等于1或-1，flag为1代表成功到达目的卫星且符合时延约束，此时信息素浓度增加；flag为-1代表通信堵塞或转发时延不符合约束条件，信息素将减弱。

S25：当反向蚂蚁到达源节点，记录此次搜寻的路径，若路径没有经过重要节点，则从候选路径中选出最小时延路径，作为节点对之间的消息传输路径。如果路径中含有重要节点，则进行下一次迭代时，将重要节点从节点候选集N

S26：迭代结束之后，将从所有的候选路径中，选出前两条最小时延路径，并将时延最小的路径作为首选传输路径，而时延稍大的路径则作为备份路径。

步骤S3具体过程如下：

S31：检测到路径中含有重要节点，则针对该源节点和目的节点重新计算一条避开重要节点的备份路径。当重要节点未失效时，备份路径并不启用。

S32：当路径中的重要节点失效时(主动失效或被动失效)，则启用备份路径，以提高消息转发的成功率。

如图5所示，当卫星网络中的节点发生随机故障或受到自主智能攻击时，若该失效节点存在备份路径，则启用备份路径进行消息转发，提高卫星网络的通信成功率。

本发明以传统的卫星网络多径路由算法为研究背景，对卫星节点的多路径选择与计算进行了优化改进，区别于传统多径路由算法的特点是：当且仅当原始路径中含有重要节点时，才为其计算备份(多径)路由。此外，本发明是基于图论中介数中心性这一参数，来对卫星网络中节点的重要程度进行评估筛选，并根据卫星网络规模筛选出具体数目的“重要节点”，只针对含有重要节点的情况为其计算备份路由。因此，本发明可以在提高卫星网络的弹性抗毁能力的同时，尽可能地减小其路由计算的时间开销。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。