基于多Agent系统的LEO卫星网络路由算法研究

摘要

下一代互联网的发展趋势是融合空天地一体化的综合信息网络，而卫星网络则是其中非常重要的组成部分。低轨卫星网络因其空间损耗小，传输时延低等特点，逐渐成为了当前的研究热点。想要实现卫星网络信息的高效性传输，首先需要面对的就是路由问题。在具有星间链路的LEO卫星网络中，设计和实现最优的路由算法是非常重要的研究内容。
　　传统的LEO卫星网络路由算法通过离散化处理，将动态的卫星网络拓扑转化为一系列静态拓扑，将地面已有成熟路由算法进行移植达到路由的目的。这种方法考虑到了卫星网络对于已有技术的继承，但其适应性差的特点也同样在研究中暴露出来。因此国内外的学者转而将研究的重点转向自适应路由，由于LEO网络的切换影响及优化目标的多样性，很多研究成果难以体系化及相互比较。本文针对这些问题，对LEO卫星网络的路由问题进行了深入且详细的分析，结合多Agent系统从不同的角度对该问题进行了研究，并得到了一些具有积极意义和参考价值的方法和结论。总体来说，本文主要研究了如下几个问题：
　　第一，现有的LEO卫星网络自适应路由算法往往采用贪婪机制，这与网络性能最优化是相悖的，而基于智能的路由算法不具有统一的理论，难以形成体系化的结构。本文从多Agent系统的角度出发，对基于智能的LEO卫星网络最优路由算法进行了研究，设计了算法的组成元素，改进了算法的主要流程，并对算法的特征和优点进行了阐述，为后文的研究打下了坚实的基础。
　　第二，目前LEO卫星网络往往采用单路径路由算法，当卫星网络拓扑发生变化时，算法需要面对因星间链路频繁断裂和恢复而造成的重路由问题。与单路径路由算法相比，多路径路由具有更好的容错性能和提供更多的聚合带宽，更加适合全球覆盖且网络拓扑频繁变化的LEO卫星系统。本文提出的基于多Agent系统的多路径路由算法，采用前向Agent探索网络，反向Agent更新路径消息；节点Agent利用黑板实现了Agent之间的直接交流，加快了算法的收敛速度；单路径探索、多路径更新的方式使得算法能够快速跟踪LEO卫星网络的拓扑变化。
　　第三，针对LEO卫星网络负载均衡路由算法不够完善的问题，提出了一种具有流量预测的负载均衡路由算法。对于全球覆盖或卫星星下点地区业务突变的LEO卫星系统，网络的动态性不仅体现在拓扑的变化，同样也体现在业务流量的动态变化。本文提出的负载均衡路由算法通过径向基神经网络对网格化后的地表业务进行预测并获得修正因子，预测Agent利用修正因子指导星上的路由策略，通过动态的调整卫星之间的传输数据，有效的克服了因LEO卫星网络业务分布不均衡带来的路由影响。
　　第四，对于支持多业务、多需求混合业务的LEO卫星网络而言，传统的精确路由算法往往无法在有效时间内获得网络最优解。这是因为具有多个约束条件的QoS路由问题是NPC类问题，求解时间会随着网络规模的扩大而爆炸式增长。针对这个问题，本文提出了基于多Agent系统的QoS路由算法，将QoS路由问题划分为路径建立、路径维持和探索、断路恢复和卫星切换管理等几个子任务，并分配给不同的智能Agent完成。算法不仅能够获得保障业务QoS的多条路径，而且具有较低的复杂度，通过简单的扩展，就能满足对不同QoS指标的支持。

目录

基于多Agent系统的LEO卫星网络路由算法研究

ROUTING ALGORITHMS BASED ON MULTI-AGENT SYSTEM IN LEO SATELLITE NETWORK

摘 要

Abstract

目 录

Contents

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.1.1课题的来源及背景

1.1.2课题研究的目的和意义

1.2 国内外发展及研究现状

1.2.1 低轨移动卫星系统的发展

1.2.2 低轨卫星网络路由的研究现状

1.2.3 多Agent系统的研究现状

1.2.4 存在的问题及改进目标

1.3 学位论文主要研究内容

第2章 多Agent系统和网络路由

2.1 引言

2.2 路由问题

2.2.1 路由的定义和特点

2.2.2 路由的分类

2.3 最短路径路由算法

2.3.1 距离矢量路由算法

2.3.2 链路状态路由算法

2.4最优路由算法

2.4.1最优路由的数学模型

2.4.2局部最优和全局最优

2.4.3计算复杂度

2.4.4最优化问题分类

2.5人工智能路由算法

2.5.1启发式算法

2.5.2元启发式算法

2.5.3元启发式算法的优化模式

2.6多Agent系统

2.6.1多Agent系统的特征和协作策略

2.6.2多Agent系统的体系结构

2.7基于多Agent系统的路由

2.7.1前提假设

2.7.2路由特征

2.7.3路由流程

2.7.4节点保存的数据结构

2.8本章小结

第3章 LEO卫星网络分布式多路径路由算法

3.1引言

3.2单路径和多路径

3.2.1多路径的优缺点

3.2.2多路径的考虑因素

3.3蚁群优化算法

3.3.1蚂蚁的集体行为

3.3.2蚁群算法的系统学特征

3.4基于蚁群算法的路由

3.4.1算法流程

3.4.2算法复杂度

3.4.3算法收敛性

3.4.4蚁群算法优缺点

3.5基于多Agent系统的多路径路由算法

3.5.1算法描述

3.5.2 DMSR与蚁群算法的区别

3.5.3性能验证及结果分析

3.6本章小结

第4章LEO卫星网络负载均衡路由算法

4.1 引言

4.2 LEO卫星网络业务分布特性

4.2.1 空间分布不均衡性

4.2.2 时间分布不均衡性

4.3显式负载均衡技术

4.3.1拥塞门限

4.3.2负载均衡

4.4 流量预测算法

4.4.1 网络流量的基本特征

4.4.2 预测方法比较

4.5基于神经网络预测的负载均衡路由算法

4.5.1 地表业务流量的分解

4.5.2 基于神经网络的流量预测

4.5.3 路由决策

4.5.4 性能仿真及结果分析

4.6 本章小结

第5章 LEO卫星网络QoS路由算法

5.1 引言

5.2 服务质量保障技术

5.2.1通信量管理

5.2.2 QoS路由

5.2.3 调度算法

5.2.4 拥塞控制

5.2.5 队列管理

5.3 QoS路由的约束条件

5.3.1 QoS路由的指标选择

5.3.2 QoS路由复杂度分析

5.4 基于地面站的代数优化QoS路由算法

5.4.1 路由模型

5.4.2 路由策略

5.5 基于遗传算法的LEO卫星网络QoS路由算法

5.5.1 路由更新和路由表设定

5.5.2 基于遗传算法的LEO卫星路由协议

5.6 基于多Agent系统的LEO卫星网络QoS路由算法

5.6.1 LEO卫星网络拓扑模型

5.6.2 QoS模型

5.6.3 MAQR算法的组成元素

5.6.4 MAQR算法描述

5.6.5 LEO卫星切换策略

5.6.6 MAQR算法特点

5.6.7 性能验证及结果分析

5.7 本章小结

结 论

参考文献

攻读博士学位期间发表的论文及其它成果

哈尔滨工业大学学位论文原创性声明及使用授权说明

致 谢

个人简历