基于蚁群算法的卫星网络分布式多路径路由方法及系统

摘要

本发明公开了一种基于蚁群算法的卫星网络分布式多路径路由方法及系统，该方法的步骤包括：源卫星节点周期性的向目的节点发送前向Ant报文，所述前向Ant报文通过信息素量表计算概率，通过轮盘赌的方式选择下一条路由；直到所述前向Ant报文到达目的地址，所述前向Ant报文转换为反向Ant报文；所述反向Ant报文使用原路径返回源节点并在沿途留下信息素。该系统用来实施上述方法。本发明具有原理简单、适用能力强、能够提高路由效率和能力等优点。

说明书

技术领域

本发明主要涉及到卫星网络技术领域，特指一种基于蚁群算法的卫星网络分布式多路径路由方法及系统。

背景技术

卫星网络能够提供广泛的地理覆盖范围和一致的服务水平，在NGN(下一代网络)等方面发挥着越来越重要的作用，尤其是在未来的空天地面一体化信息网络方面。在这些未来的网络中，作为核心框架，卫星将异构网络彼此连接。许多卫星必须具有卫星间链路(ISL)。在许多星座中，ISL为卫星提供通信链路。为了可靠、准确地传输信息，需要一种可行且健壮的路由策略。由于卫星网络拓扑的移动性和周期性，卫星网络路由问题一直是一个极具挑战性的问题。

当前卫星网络场景的一些定义：低轨卫星网络模型包含复数个轨道面，每个轨道面有一定数目LEO低轨卫星，轨道内的地轨卫星首尾相连。每个卫星都有四个ISL，并使其能够与两个最近的轨道间和轨道内相邻卫星通信。建立了一个统一的空基网络，地面站可以连接到该网络，以传输多媒体网络报文。

为了在卫星网络上进行有效的路由，有从业者已经提出了许多路由算法。

一类方案是采用面向连接的网络结构，动态路由问题由离散时间网络模型静态化。在每个等长间隔内，将卫星网络拓扑划分为一系列固定切片，在这些固定切片上可以应用地面路由算法。但由于上述算法仅使用有关星座的静态和预测信息，因此由于适应性较差，它们几乎无法跟踪网络流量的变化。

一类分布式路由算法(DDR：分布式数据报路由)，用于解决I P与LEO卫星网络的组合问题。为了使分组延迟最小，在该算法中，每个卫星都由离散的地理坐标表示，并分别执行路由策略。但是，但DDR算法的缺点是鲁棒性差，如果卫星节点或I SL崩溃，其性能将急剧下降。

又有从业者发展出了IRSN(卫星网络上的互联网路由)的概念，分析了Internet与LEO卫星网络相结合的理论框架。在IRSN算法中，IP路由仅在入口和出口节点中实现，而常规的卫星路由算法在内部节点中使用。但是，CARP(星座地址解析协议)中的传输效率对网络性能的优化就无法利用了。

目前，大多数路由策略都采用单路径传输数据。虽然对单路径路由策略的研究相对比较成熟，但实际上，单路径通常采用贪婪机制，并假定链接是独立的。当网络资源有限时，贪婪机制将导致网络性能下降。与单路径路由相比，多路径路由具有较强的容错能力和负载均衡能力。对于LEO卫星网络，多路径路由可以提高ISL的生存能力并提高链路利用率。而且，多路径路由可以提供聚合带宽以容纳更多流量。随着网络技术的发展，由于时间和空间的复杂性，同时面临组合优化问题，单路径路由变得无能为力。对于多路径路由问题，体系结构是第一个要解决的问题。许多学者关注于进化算法(EA)，它为多路径路由提供了天然的体系结构。

网络路由问题实际上是一个复杂的优化问题。在过去的60年中，人们非常重视模拟生物进化的过程，从而为优化问题开发有效的解决方案。EA是一种基于上述理论的启发式算法。集群智能是一种新型的仿生进化算法，已成为新兴的研究前沿，已有二十多年的历史。社交昆虫群体可以看作是一个分布式系统。尽管每个个体都非常简单，但由许多个体组成的整个系统却代表着具有高度结构化群体的集群智能。在系统中，个体与其他个体协同工作。所有个体作为一个整体共同完成复杂的任务，这是单个个体很难完成的任务。有两个主要的研究领域：蚁群优化(ACO)和粒子群优化。目前，群体智能算法在组合优化、网络路由、数据挖掘、无线传感器网络等领域具有广阔的应用前景。

ACO受蚁群觅食行为的启发。像蚂蚁这样的社会昆虫虽然没有视野，却可以找到从巢穴到食物的最短路径。通过大量实验，科学家发现蚂蚁与其他蚂蚁合作并通过信息素完成复杂的任务。蚁群的集体行为显示出积极的反馈：越多的蚂蚁通过路径，信息素剩下的越多，并且蚂蚁倾向于选择具有更多信息素的路径。后来的蚂蚁增强了先前蚂蚁留下的信息素，最终，所有的蚂蚁都集中在最短的路径上。

ACO在网络路由中的应用是合理可行的，蚂蚁从巢穴到食物的寻找方法类似于从源到目的节点的数据搜索路径。这两个过程的同构性使得可以将蚁群的探索和决策系统用于网络路由。ACO中的移动Agent(如蚂蚁)从一个节点迁移到网络中源节点和目标节点之间的相邻节点，并搜索可行路径以及其他有用信息。存储每个信息素变量的信息素表显示了网络中所有路径的状态。从信息素表转换而来的数据路由表根据一些经过修改的选择策略来负责数据传输。尽管ACO在网络路由中的应用具有许多优点，但在卫星网络中使用ACO时仍存在一些未解决的问题。

发明内容

本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种原理简单、适用能力强、能够提高路由效率和能力的基于蚁群算法的卫星网络分布式多路径路由方法及系统。

为解决上述技术问题，本发明采用以下技术方案：

一种基于蚁群算法的卫星网络分布式多路径路由方法，其步骤包括：

源卫星节点周期性的向目的节点发送前向Ant报文，所述前向Ant报文通过信息素量表计算概率，通过轮盘赌的方式选择下一条路由；

直到所述前向Ant报文到达目的地址，所述前向Ant报文转换为反向Ant报文；

所述反向Ant报文使用原路径返回源节点并在沿途留下信息素。

作为本发明方法的进一步改进：当反向Ant报文返回其源节点，所述反向Ant报文将在网络中被销毁；每个所述反向Ant报文都有最长的生存时间，当超过最长的生存时间，所述反向Ant报文被自动销毁。

作为本发明方法的进一步改进：所有卫星节点均维护信息素量表，周期性地做衰减处理，并根据信息素量表更新路由表。

作为本发明方法的进一步改进：每个源卫星节点s以规定的时间间隔t周期性的向特定的目标节点d发送前向Ant报文；所述前向Ant报文用

作为本发明方法的进一步改进：卫星节点v根据信息素量表计算转移概率

作为本发明方法的进一步改进：在转发过程中，所述前向Ant报文中的路径信息同时充当禁忌表，在选择下一条时不会选择已经经过的卫星。

作为本发明方法的进一步改进：所述前向Ant报文模拟数据包转发，所述前向Ant报文具有与数据包相同的优先级队列，所述前向Ant报文从源节点向目的节点逐跳移动。

作为本发明方法的进一步改进：当卫星节点d作为目的节点接收到前向Ant报文

作为本发明方法的进一步改进：所述反向Ant报文返回“上一跳”的时候，检测“上一跳”之前的路径有没有邻居节点，如果有就直接到路径最前的邻居卫星节点上。

本发明进一步提供一种基于蚁群算法的卫星网络分布式多路径路由系统，其包括：

信息素处理模块，用来管理信息素量表，并依据信息素量表计算概率、更新路由表；

Ant报文生成模块，用来生成Ant报文；

Ant报文处理模块，用来处理、发送Ant报文；

源卫星节点周期性的向目的节点发送前向Ant报文，所述前向Ant报文通过信息素量表计算概率，所述前向Ant报文到达目的地址后转换为反向Ant报文；所述反向Ant报文使用原路径返回源节点并在沿途留下信息素。

作为本发明的进一步改进：

与现有技术相比，本发明的优点就在于：

本发明的基于蚁群算法的卫星网络分布式多路径路由方法及系统，原理简单、适用能力强、能够提高路由效率和能力，本发明基于ACO算法的通用框架，针对卫星网络的特点进行了改进，有效地利用了蚁群的自适应和动态寻优能力。多路径路由设计使得网络具有更强大的容错能力和负载均衡优势，分布式的算法设计能够有效加快网络收敛效率。本发明中前向Ant报文路径搜索，反向Ant报文留下信息素能够保障路径的有效性。使用基于信息素和启发因子概率计算方法能够使得算法能够更具需求适应不同的具体卫星网络场景。与传统路由算法相比，本发明不仅具有更好的端到端延迟，而且可以跟踪LEO卫星网络的快速变化拓扑。

附图说明

图1是本发明路由系统的原理示意图。

图2是本发明路由方法在具体应用实例中前向Ant报文策在卫星节点的处理流程示意图。

图3是本发明路由方法在具体应用实例中反向Ant报文策在卫星节点的处理流程示意图。

图4是本发明路由方法在具体应用实例中反向Ant报文的路径优化策略示意图。

具体实施方式

以下将结合说明书附图和具体实施例对本发明做进一步详细说明。

如图1-图4所示，本发明的基于蚁群算法的卫星网络分布式多路径路由方法，使用一种称为Ant报文的探测报文用于路径搜索，所述Ant报文有前向Ant报文和反向Ant报文两种形态；本发明的步骤包括：

源卫星节点周期性的向目的节点发送前向Ant报文，所述前向Ant报文通过信息素量表计算概率，通过轮盘赌的方式选择下一条路由；

直到所述前向Ant报文到达目的地址，所述前向Ant报文转换为反向Ant报文；

所述反向Ant报文使用原路径返回源节点并在沿途留下信息素。

在上述过程中，本发明是根据卫星上的信息素量和启发因子计算选择下一跳的概率，然后使用轮盘赌的方法选出下一跳卫星节点。这个概率是由卫星上的信息素量和启发因子共同决定，并可以通过设置信息素量和启发因子的重要程度参数来调整信息素量和启发因子对概率的影响，以此来适配不同具体卫星网络场景的个性化需求。

在上述过程中，本发明采用概率计算方法计算下一跳概率，以此生成多路由表，并在收到反向Ant报文时和信息素衰减时更新路由表。路由表选择概率最大的一个或多个邻居作为路由表的下一跳，并根据选择概率的大小比例设置多路由表的度量值。

在具体应用实例中，卫星网络拓扑的可预测性和周期性是在卫星路由中必须考虑的有利因素。如果发生可预知的卫星切换，则可以通过星历来预测。本发明可以根据星历切换规律，使用路由表更新策略来防止卫星节点中的队列增加。

作为较佳的实施例，所有卫星节点均维护信息素量表，周期性地做衰减处理，并根据信息素量表更新路由表。

作为较佳的实施例，考虑到卫星网络拓扑的可预测性，引入了附加控制策略，在发生可知切换时会更新路由表。所述路由表紧密跟踪卫星网络的动态拓扑。

通过采用本发明的上述方案，就可以最小化卫星切换产生的影响。

在具体应用实例中，本发明先初始化信息素，每个卫星节点s维护一个到目标节点d的信息素量表；开始时到每个邻居卫星i∈N

在具体应用实例中，每个源卫星节点s以规定的时间间隔t周期性的向特定的目标节点d发送前向Ant报文；所述前向Ant报文用

在具体应用实例中，所述前向Ant报文模拟数据包转发，所述前向Ant报文具有与数据包相同的优先级队列，所述前向Ant报文从源节点向目的节点逐跳移动。

在具体应用实例中，卫星节点v根据信息素量表计算转移概率

在具体应用实例中，在上述转发过程(移动过程)中，前向Ant报文中的路径信息同时充当禁忌表，在选择下一条时不会选择已经经过的卫星。

在具体应用实例中，所述概率

其中，η

在具体应用实例中，当卫星节点d作为目的节点接收到前向Ant报文

当卫星节点v接收到来自邻居卫星节点的反向Ant报文

在具体应用实例中，更新规则如下：

其中，τ

在具体应用实例中，所述反向Ant报文在返回“上一跳”的时候需要注意，前向Ant报文并不能保证其走的是一条最短路径，在报文返回“上一跳”的时候还需要检测“上一跳”之前的路径有没有邻居节点，如果有就直接到路径最前的邻居卫星节点上，如图2所示，这样可以保障Ant走的是一条相对最短路径。

在具体应用实例中，所有卫星节点v还会以规定的时间间隔t周期性的更新信息素量表，更新规则如下：

τ

其中，ρ表示信息素的蒸发率，取值范围为[0，1]，ρ值越小路径上残留的信息素就越多，导致无效的路径会被继续搜索，影响算法的收敛速率，ρ值越大可以有效排除无效路径，但不能保证有效路径不会被放弃搜索。在卫星网络中网络拓扑变化频繁，很容易产生无效路径，这要求要使用较大的ρ值。

在具体应用实例中，一旦反向Ant报文

以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。