LEO星际网络中的路由算法研究

论文摘要

LEO卫星网络具有轨道高度低、传输时延小以及用户终端实现简单等优点,近几年来得到了广泛的重视和研究.在具有星际链路的卫星网络中,信息可以通过多种路径传输.由于网络拓扑结构变化迅速,传输路径中断频繁,因此路由算法设计成为LEO星际网络的关键问题之一.本文的主要工作成果有以下几个方面:1.将铱星系统抽象为无回路有向网络,并在此基础上给出了解决两节点间最短路问题和所有节点间最短路问题的新算法.与经典算法相比,复杂度分别由O ( n 2)和O ( n 3)下降到了O ( m )和O ( m ( n ? m1/2)).2.以传输时延受限为基础,将切换率、阻塞率等作为参数转化到费用函数中,建立了一种新的QoS路由模型.该模型较为全面地考虑了各种QoS指标,更符合星际网络的实际应用.3.针对时延受限费用最小问题的QoS模型提出了优化算法.该算法通过构造限制子网络与费用优化子网络,极大地简化了解的搜索空间,并针对两种不同的费用优化子网络提出了不同的解决策略,有效地提高了搜索性能.4.针对单路径传输协议在通信系统中的不足,分别设计了链路独立多路径算法和节点独立多路径算法.这两个算法实现简单,复杂度低,并且独立路径的数目k可以根据实际需要任意选取.5.将卫星网络通信中的一类特殊问题转化为带固定费用的运输问题,并借鉴智能优化算法思想,提出了自适应禁忌搜索算法.与同类算法相比,本算法自适应性强,能够全局收敛.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 LEO卫星通信系统发展现状
• 1.3 文章内容安排
• 第二章 无回路网络中最短路问题的改进算法
• 2.1 图与网络的基本概念
• 2.1.1 图的基本概念
• 2.1.2 有向图的基本概念
• 2.1.3 DAG图与无回路网络
• 2.2 卫星网络模型
• 2.3 无回路网络中最短路问题研究
• 2.3.1 新算法的提出
• 2.3.2 本算法的正确性证明
• 2.3.3 本算法的复杂度分析
• 2.4 无回路网络中所有节点之间最短路问题研究
• 2.4.1 所有节点之间最短路算法
• 2.4.2 复杂度分析
• 2.5 应用举例
• 2.5.1 最短路问题
• 2.5.2 所有节点之间最短路问题
• 2.6 本章小结与展望
• 第三章 LEO星际网络中QoS路由算法研究
• 3.1 QoS路由算法概述
• 3.1.1 QoS性能参数简介
• 3.1.2 QoS路由算法研究现状
• 3.2 卫星时空网络模型的建立
• 3.2.1 时延限制条件
• 3.2.2 将阻塞率考虑进费用中
• 3.2.3 将切换率考虑进费用中
• 3.3 问题求解与算法设计
• 3.3.1 符号说明
• 3.3.2 构建限制子网络与费用优化子网络
• 3.3.3 两种情况的不同解决办法
• 3.3.4 算法复杂度分析
• 3.4 算法实例与分析
• 3.5 本章小结与展望
• 第四章 LEO星际网络中多径路由算法研究
• 4.1 多径路由概述
• 4.1.1 多径路由的优点
• 4.1.2 多径路由协议
• 4.1.3 多路径算法简介
• 4.1.4 多路径算法研究现状
• 4.1.5 多条路径上的流量分配
• 4.2 多路径算法设计的符号与概念说明
• 4.3 链路独立多路径算法
• 4.3.1 数学模型建立
• 4.3.2 问题求解与算法设计
• 4.3.3 算法复杂度分析
• 4.4 节点独立多路径算法
• 4.4.1 数学模型建立
• 4.4.2 问题求解与算法设计
• 4.4.3 算法复杂度分析
• 4.5 应用举例
• 4.5.1 链路独立多路径算法实例
• 4.5.2 节点独立多路径算法实例
• 4.6 推广到求任意k条独立路径的情况
• 4.7 本章小结与展望
• 第五章 星际网络路由设计中的智能优化算法
• 5.1 禁忌搜索算法概述
• 5.1.1 智能优化算法简介
• 5.1.2 禁忌搜索算法简介
• 5.2 应用智能优化算法解决路由问题
• 5.3 算法设计和描述
• 5.3.1 解的构成及初始解的选取
• 5.3.2 邻域和候选解
• 5.3.3 禁忌表的设置和管理
• 5.3.4 特赦准则的设置
• 5.3.5 终止条件的设置
• 5.4 仿真实验
• 5.5 本章小结与展望
• 第六章 结束语
• 6.1 主要研究结论
• 6.2 研究展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果