本文是一篇计算机论文，本文对卫星通信网络的路由算法进行了研究，主要完成了高低轨卫星通信网络的SDN架构设计、基于SDN的QoS 路由算法设计和低轨卫星通信网络的路由算法设计三方面工作。
第一章 绪论
1.1 研究背景与意义
在过去的几十年间，通信技术的迅速发展深刻地改变了人们的生活。由于研究人员的不懈努力，移动通信系统以十年一代的速度更新迭代，且每一次换代都伴随着速率和容量的巨大提升，从而带来了更加多样化的通信服务。与国际上相比，我国的移动通信建设起步稍晚，但在国家的大力支持下，我国迅速赶上了国际先进水平，尤其是在第五代移动通信技术（Fifth generation of mobile technologies，5G）的研究和相关基础设施建设中遥遥领先。截至目前，我国已经建成规模庞大的移动通信系统，5G基站达337.7万个[1]。然而，由于人口分布呈现出东密西疏的特征，我国领土上仍有大片区域未被移动网络覆盖。在戈壁沙滩、偏远山地和海洋区域，由于基站架设成本高昂，现有的移动通信技术无法提供足够的服务能力。
卫星通信是以人造卫星为中继节点的通信方式，与地面移动通信相比具有许多独特的优势，因此被视为后者的有力补充，有望在6G通信系统中发挥关键作用[2]。首先，由于单颗卫星即可提供数十倍于地面基站的覆盖范围，卫星通信系统大大减少了架设基站的成本，弥补了地面网络服务能力的不足，为实现全球无缝的“泛在连接”提供了可能[3]。其次，卫星通信系统具有不受地理环境影响的特点：一方面，卫星的星间信道特性比地面信道更加稳定，电磁波传播时不会被地面障碍物遮挡，因此受反射、折射的影响较轻微；另一方面，地面基站在自然灾害发生时可能损坏，而卫星通信系统仍可正常工作，从而能够为灾害救援等应急通信需求提供保障。
1.2 国内外研究现状
1.2.1 LEO卫星网络路由技术
近年来，国际上以Starlink为代表的大星座计划推动了新一轮的LEO星座建设热潮[6]，也使LEO卫星网络的路由技术成为学者们的研究热点。与地面网络相比，LEO星座的节点距离不断变化、星间链路切换频繁，因此经典的OSPF协议难以适用。自上个世纪以来，针对如何处理LEO卫星网络的时变拓扑结构，学者们进行了许多研究，主要思路是对连续变化的拓扑结构进行离散化。在离散化的方式上，现有策略有时间离散化和空间离散化两种。
时间离散化策略将网络的运行周期T划分为若干时间片：[t0,t1]，[t1,t2]，…，[tn-1,T]。在这些时间片内，卫星网络的链路连接情况不发生改变，因此具有稳定的拓扑结构。如果划分的时间段足够小，每条星间链路的长度也可以视为固定的，从而可以利用最短路径算法计算路由表。该策略最早由文献[7]提出，在该文献中每个时间段内的路由表由地面站预先计算，并上注至卫星，而卫星只需在时间段切换时改变路由表，无需额外计算。因此，它充分利用了卫星网络的周期性以及由此带来的拓扑可预测性。
空间离散化策略可以细分为覆盖域离散化和虚拟节点策略，这种方法旨在将卫星变化的连续空间离散化为固定网格，从而使动态的网络拓扑转化为由固定节点组成的静态拓扑。覆盖域离散化由文献[8]提出，该文献将地球表面划分为若干互不相交的区域，并为这些区域赋予逻辑地址。在任何时刻，卫星节点根据最小距离原则一一映射到这些区域，并以它们的逻辑地址作为自身的地址。与时间离散化策略相比，这种方式考虑了地理空间信息，使卫星在转发数据包时能直接根据源/目的节点的地理位置进行转发，不需要事先存储大量路由表。
第二章 卫星网络路由关键技术研究
2.2 网络架构
2.2.1 SDN架构
在今天的计算机网络中，路由选择任务是由工作在网络层的路由器完成的。经过长期的发展演进，路由器的体系结构逐渐明晰，大致由三个部分组成：控制平面、转发平面和管理平面，如图2.1所示：
在图2.1中，转发平面由路由表和一些简单的控制逻辑组成，负责根据IP首部为路由器接收到的数据包查找下一跳，同时还可以进行一些简单的首部修改，以及对异常分组采取丢弃、缓存等不同操作；控制平面负责运行路由协议，从而对转发平面的路由表进行更新。同时通过众多的Internet协议为路由节点提供一定的自治性，使其能够完成拓扑管理、地址解析等复杂任务。控制平面还向管理平面提供合适的API，以便管理者对网络进行配置；管理平面是网络运营商和路由节点进行通信的桥梁，可提供比控制平面更加复杂的策略。
上述体系结构将网络的控制功能分散于各个路由节点中，因此控制平面的协议大多是分布式的。分布式协议假设节点在接入网络时并不具有对网络状态的了解，需要与周边节点进行信令交互才能获取和拓扑有关的信息。这一假设和Internet中节点连接方式没有明显规律的特点是相适应的，因此OSPF、RIP等广泛应用的协议都采取了这种策略；然而在一些网络中，拓扑结构变化具有明显的可预测性，采用分布式协议将带来不必要的信令开销。数据中心是这种网络的典型代表。
2.3 最短路径算法
在本节中讨论与最短路径计算密切相关的两种算法：Dijkstra算法和A*算法。
2.3.1 Dijkstra算法
Dijkstra算法[41]是目前的卫星通信网络路由协议中应用最为广泛的算法，其流程图如图2.8所示。算法维护一组队列和标记，其中V表示具有临时标记的节点队列，W表示有永久标记的节点队列。在初始阶段，除了源点之外的所有节点被视为不可到达的，因而具有标记∞。
在迭代过程中，每当一个节点被加入W，就表示找到了源点到该节点的最短路径，而该节点的标记等于最短路径长度。算法考察与集合W直接相连的节点，依次计算从W到达这些节点的路径长度，以确认是否为这些节点找到了更短的路径。随着迭代的进行，集合W不断扩大，直到目的节点加入W时停止。
从Dijkstra算法的计算过程不难看出，算法在搜索最短路径的过程中缺乏方向性，仅仅是以长度递增的顺序搜索图中的路径。因此不论目的节点与源点的相对位置如何，Dijkstra算法都需要遍历许多相同的节点，导致搜索效率较低。
第三章 基于 SDN 的双层星座 QoS 路由算法 ................................. 25
3.1 引言 ................................ 25
3.2 网络架构设计 ................................ 25
第四章 基于实时链路状态的LEO卫星网络路由算法 ...................... 43
4.1 引言 ................................. 43
4.2 LEO卫星网络的链路状态路由 ...................... 43
第五章 总结与展望 .............................. 60
5.1 全文总结 ............................. 60
5.2 未来展望 .......................... 61
第四章 基于实时链路状态的LEO卫星网络路由算法
4.1 引言
LEO卫星网络轨道高度较低，在弥补地面网络覆盖能力不足的同时还能提供与后者相当的端到端延迟，因此被视为天地一体化信息网络的重要组成部分。目前，全球在轨卫星有70%为LEO卫星[52]。2016年，我国正式将天地一体化信息网络建设列为科技创新重大项目，开启了我国LEO卫星网络的建设历程。在此之后，我国提出了多个LEO星座建设计划，如“鸿雁”、“银河”、“千帆星座”等。为了实现大规模LEO星座的全球组网，保障卫星网络中数据高速、可靠的端到端传输，亟需开展高效的LEO卫星网络路由技术研究。一方面，LEO卫星网络具有去中心化特征，比GEO/LEO双层卫星网络的健壮性更好。在基于SDN的GEO/LEO双层卫星网络中，由于SDN固有的集中控制特性，一旦控制平面与转发平面之间的通信链路中断，网络将无法进行接入控制，交换机只能依赖之前存储的流表继续转发。另一方面，随着卫星网络中用户数量迅速增长，为每个用户单独规划完整的转发路径、保障QoS需求并不现实，路由算法只能保障部分用户的QoS需求。基于上述考虑，本文设计低开销、低延迟的LEO卫星网络路由算法，在SDN控制器发生故障或提供“尽力而为”服务等情况下使网络回退到分布式更新，避免路由转发中断。
本章首先对LEO卫星网络的链路状态路由算法进行分析，说明了现有方法的不足之处。通过引入修改的A*算法，使卫星在为数据包计算下一跳时考虑实时链路状态，并显著减少了泛洪开销；之后从扩大链路状态收集范围和提高启发式策略准确性角度分别对算法进行改进，进一步降低了网络的端到端时延和丢包率。此外，本章在NS-3上搭建仿真场景并实现了所提算法，从多方面评估了算法的性能。
第五章 总结与展望
5.1 全文总结
本文对卫星通信网络的路由算法进行了研究，主要完成了高低轨卫星通信网络的SDN架构设计、基于SDN的QoS 路由算法设计和低轨卫星通信网络的路由算法设计三方面工作。针对传统卫星网络架构配置方式不灵活、转发细粒度较低等问题，设计了基于SDN的高低轨卫星通信网络架构，提出了可行的拓扑管理策略；在架构设计的基础上进一步研究了QoS路由问题，为解决卫星网络路由算法不能保证实时QoS的问题，本文提出了异轨融合软件定义的路由算法，通过高低轨卫星的协同工作，有效提高了网络的QoS保障能力；最后，考虑到为非QoS流提供“尽力而为”服务的需求，本文提出了基于动态A*算法的LEO卫星网络路由策略，在减少端到端时延的同时降低了路由开销。
本文的主要工作总结如下：
（1）对SDN架构及其在卫星网络中的应用进行了研究。通过分析SDN架构的组成和路由更新方式，说明了SDN架构在减少信令开销和提高转发细粒度等方面的优势，由此得出将SDN架构引入卫星网络路由算法的必要性。之后设计了高低轨卫星通信网络的SDN架构，利用GEO卫星组成控制平面，LEO卫星组成转发平面，因此GEO卫星可直接管理LEO卫星，无需借助位于地面的网络运营中心，降低了控制平面和转发平面的通信时延。为解决高低轨卫星网络中层间链路动态性较强导致网络管理困难的问题，设计了分域与覆盖域离散化结合的拓扑管理策略。
（2）在SDN架构的基础上设计了GEO/LEO双层卫星网络的QoS 路由算法。传统算法难以保障数据流的端到端QoS，而且新接入网络的流可能影响已经在网络中传输的流，导致后者的QoS约束无法被满足。为解决这些问题，本文在路由算法中引入端到端测量机制，并采用在线优化对流的路径进行更新，从而能够保证流的实时QoS。仿真结果表明，本文算法提高了网络的QoS满足率，同时降低了端到端延迟。
参考文献（略）