基于数据校验时空图的卫星网络连接计划设计

戴翠琴，贺黎明，罗 屹

重庆邮电大学通信与信息工程学院，重庆400065

近年来，低轨（low earth orbit,LEO）卫星网络凭借传输时延小、组网灵活、不易受地理环境影响的优势在灾害救援、环境监测、情报侦察中发挥着关键作用。然而，LEO 卫星网络中节点的相对运动导致的网络拓扑时变和链路连接瞬断会给LEO 卫星网络通信的可靠性和有效性带来巨大影响。在LEO 网络中，“连接”用于表示卫星网络中节点间相对运动轨迹在时间和空间上具有交集的一系列通信机会，但是网络拓扑和星间链路（inter-satellite links,ISL）的时变性、卫星节点能源和负载的有限性限制了LEO 卫星之间建立连接的机会，使得卫星通信中可用连接计划（contact plan,CP）时变且有限，进而导致卫星网络连接和系统性能受到严重影响。为解决以上问题，连接计划设计（contact plan design,CPD）得到了广泛关注[1]。

目前，LEO 卫星网络中的CPD 按优化目标可以分为两类：1）基于网络连接优化的CPD方案[2-13]，如最小化网络连接瞬断概率[2-10]和最大化连接公平性[11-13]；2）基于系统性能优化的CPD 方案，如最大化能源效率[14-16]、最小化时延[17-20]和最大化吞吐量[21-22]的CPD方案。

第1 类CPD 方案是最小化网络连接瞬断概率，即最小化ISL 连接中断概率。文献[2] 考虑队列长短和流量大小提出了一种基于流量感知的层间连接选择方法，该方法虽然提升了网络吞吐量，但是增加了系统交付时延。文献[3] 提出一种改进的基于协同进化机制的多卫星协同任务规划算法，提高了任务收益，但是并未考虑卫星间因ISL 冲突而导致的传输阻塞问题，该问题可能会导致高延迟。文献[4] 提出连接图路由的替代方案，提高了机会路由算法的数据传输效率，但是并未给出校验数据是否到达目标点的方法，同时也未验证方案在时延方面的表现。文献[5] 基于马尔可夫决策过程理论模型，确定了故障下的最佳路由策略，但并未考虑到LEO 卫星的移动性问题，这是CPD 问题需要重点考虑的内容。文献[6] 综合考虑时变拓扑、间歇性连接和不同天气条件下的自适应传输，提出了两种启发式的CPD 方案，解决了有限资源条件下的CPD 问题，但是该方案并不适用对时延有严苛要求的应用。文献[7] 提出了基于遗传算法（genetic algorithm,GA）的多任务规划方案，解决了任务重规划问题，但是对任务进行重规划会超出用户程序所能容忍的时间限制，因此会降低用户体验。文献[8] 将时空图中的流量优化问题视为与队列稳定性相关的随机优化问题，提升了网络稳定性，但是该方案优先保证卫星连接的公平性，可能出现某颗卫星空闲，但是因排队导致无法及时传输数据，造成了时延的增大。文献[9] 将节点的运动特性建模为有限状态自动机（finite state automaton,FSA），设计了一种基于模拟退火（simulated annealing,SA）算法的CPD 方案，SA 会进一步增加卫星的能耗，一般并不适用资源受限的小型卫星网络。文献[10] 考虑两层空间网络，并提出了3 种可以提高连接可靠性、降低成本和降低无效概率成本的CPD 方案，该方案问题分析较为单一，并未综合考虑可靠性和成本问题下的CPD 问题。最大化连接公平性，指的是最大化ISL 连接的公平性，保证各个节点建立ISL 的概率是相同的。文献[11] 将一个大的连接计划拆分成几个部分，提出了一种多层卫星网络的分布式连接计划设计方案。文献[12] 提出了一个优化模型形式化问题，并提出当出现大量CP 时，将其作为一个匹配问题解决。文献[13]提出基于路由感知的CPD，利用SA 优化卫星网络整体端到端传输时延。文献[11-13] 仅仅将公平性放在首位，不仅未考虑延迟和卫星能耗的问题，而且还存在因长时间等待连接分配而导致流量阻塞的问题。以上文献为优化网络连接性能做了大量贡献，但是均存在可以改进的地方：1）仅仅考虑连接是不够的，因为保证卫星网络连接的最终目的是传输数据，而数据的传输过程又需要考虑到网络吞吐量的表现；2）主要针对空间层的数据传输，均未给出如何判断流量阻塞和解决流量阻塞的方法。

对于第2 类CPD 方案，已有的研究主要围绕能耗、时延和吞吐量3 个方面进行。最大化能源效率指的是最大化卫星能源利用率。文献[14] 设计了基于电池感知的CPD 方案，以保证最大化通信资源的利用率，并且提出采用电池安全裕量的方法，从而保证卫星能源不会被耗尽，但是方案只考虑能效不考虑拓扑特性，未能给出具体的CPD 方案，缺乏一定的说服力。文献[15] 设计了一种适用于延迟容忍网络（delay tolerance network,DTN）的能源感知路由算法，使卫星始终具有充足的能力转发数据，该方案并不适用于大型卫星星座，因为目前大型星座并不需要以“存储– 携带– 转发”的方式传输数据。文献[16] 利用粒子群优化（particle swarm optimization,PSO）算法处理因拓扑时刻变化而产生的复杂的路由问题，减少了卫星网络能耗，该方案重点考虑了路由，并未考虑到卫星节点的特性，比如系统容量和转发器状态。为最小化时延，文献[17] 提出一种基于离散的PSO（discrete particle swarm optimization,DPSO）方案以解决多任务规划问题，方案虽然降低了时延，但是多任务规划问题的空间复杂度往往较高，给卫星的计算能力带来很大挑战。文献[18] 提出了一种基于CP的延迟约束路由算法，满足了具有时延限制服务的需求，但是方案仅仅适用于时延敏感型任务。文献[19] 采用遗传启发的CPD 方案，以减少传输时延，但是运行算法本身的能源消耗可能会超出卫星本身可承受范围，因此可能会对卫星能耗算法提出更高的要求。文献[20] 首次提出了适用于全球导航卫星系统的分布式CPD 方案，但是该方案并未考虑导航系统在不同天气时的性能不稳定问题，需要进一步验证所提方案的有效性，因此缺乏一定的说服力。为最大化吞吐量，文献[21-22] 提出接入卫星选择和数据下载策略。其中，为解决星地链路稳定性和流量平衡问题，文献[22] 提出一种去中心化的预测算法，用于估计卫星之间的CP，但是该方案并未对所提算法在时延方面的表现进行仿真验证，因此可能并不适用于对时延要求比较严苛的任务和应用程序。总之，以上基于系统性能优化的CPD 研究工作所考虑的问题均较为单一，仍存在以下局限性：1）未考虑到卫星网络不同于地面网络，卫星网络中各个卫星的能源本身是受限的；2）未考虑到数据传输过程中需要兼顾卫星节点负载状态和ISL 的连接状态，可能会发生链路冲突，进而造成网络阻塞。

本文针对资源受限的LEO 卫星网络连通性和数据阻塞的问题，考虑了网络拓扑的时变性、卫星资源的有限性，提出了一种基于数据校验时空图的CPD 方案。首先，为表征卫星网络资源和网络瞬时拓扑，在最大化电池能效的基础上建立了一种基于电池模型的数据校验时空图；其次，将CPD 问题建模为以ISL 和能源为约束、以最大化吞吐量为目标的约束优化问题；接着，通过该模型比较校验层的校验数据和传输层的转发数据进而判断是否发生了流量拥塞，并综合ISL 和节点负载状态，对错误CP 进行初步修复，生成可用CP；最后，利用适应度函数评价修复后可用CP 的优异程度，并利用DCGA 算法生成使得吞吐量最大化的最佳CP。仿真结果表明了该方案可以提升网络吞吐量和降低交付时延。

1 系统模型

给出了LEO 卫星网络模型，并设计了一种改进的电池模型，在最大化卫星能源效率的基础上，利用基于电池模型的数据校验时空图（data check time-space graph,DCTSG）表征LEO 卫星网络资源和瞬时拓扑结构。

1.1 网络模型

如图1 所示，LEO 网络模型主要由3 个部分构成：1）数据发送区域，从该区域通过LEO网络向地面站发送数据，并且通过地面网关向数据中心发送数据的简要信息，包括数据大小、类型和内容等；2）资源受限的LEO 卫星，主要负责从数据发送区域接收任务数据，并发送到地面站；3）地面站，主要接收LEO 卫星通过ISL 转发的任务数据，并发送到数据中心处理。

图1 LEO 卫星网络模型Figure 1 LEO satellite networks model

在图1 的网络模型中，LEO 卫星从数据发送区域收集数据，并传输到地面站，最后发送到数据中心。数据中心比较校验数据和从LEO 卫星接收的数据是否相同，进而判断是否需要进一步处理该数据。当发送区域在LEO 卫星观测范围之内时，卫星从发送区域采集数据。之后的数据传输主要包含两种情况：1）若此时该卫星在目标地面站的观测范围之内，则该卫星将收集到的数据直接发送到地面站；2）若此时该卫星不在地面站观测范围之内，则该卫星需要经过ISL 的一系列转发后，才能将任务数据送达到目标地面站。针对第2 种情况，尤其是在卫星资源受限的情况下，制定合适的CPD 方案，可以有效地防止卫星之间出现间歇性连接，从而避免数据在传输时出现连接中断，甚至丢失。

1.2 电池模型

为确保卫星节点的可用性，首先需要对传统的电池模型[15]进行改进，得到改进的电池模型（improved-battery model,IBaM），该模型能够最大化电池效率、最小化电源耗尽概率，从而能够保证卫星节点的可用性。

IBaM 如图2 所示，其存储的电荷分为两个部分：1）可用电荷k(t)，该部分电荷直接受到负载的影响，通过电压表显示可用电量；2）束缚电荷s(t)，该部分的电荷以化学能的形式存储在电池内，不直接受到负载的影响。当束缚电荷和可用电荷存在高度差时，将发生电荷的扩散作用：若束缚电荷高度高于可用电荷，则束缚电荷内稳定的化学能将通过扩散作用转化为可用电荷；反之，可用电荷将转化为束缚电荷。电荷的恢复效应和容量效应分别遵循的两个耦合的微分方程为

图2 电池模型Figure 2 Battery model

式中：f(t) 为电池上的负载，其扩散速度由非负参数p调节，并与k(t) 和s(t) 高度差成正比；c为可用电荷的比例，其范围为[0,1]。

为保证电池的可用性，引入安全阈值ymin。当ymin＞0 时认为电池能源是能够进行数据转发的；当ymin=0 时认为电池能源被耗尽。但在此模型中，即使可用电荷k(t)＜ymin，电池内部右侧以化学能形式存储的s(t) 仍能够转化为可用电荷以达到安全阈值，从而保证了卫星电池的可用性，即不存在失效的卫星节点。

1.3 数据校验时空图

电池模型能够最大化电池效率，确保在时空图中不存在失效的节点，时空图表征了网络资源和网络瞬时拓扑。如图3 所示，使用DCTSG 表征网络资源以及网络瞬时拓扑。拓扑采用的是时间间隙的模式，该模式将拓扑中的时间划分为n个时间间隙，即t ∈¯λ={Δτ,2Δτ,···,nΔτ}，每个时间间隙的长度为Δτ，在每个间隙内网络拓扑被看作是固定的。DCTSG 是由n个时间间隙构成的有向图，记为G(V,∂)，顶点V=Vg ∪Vo ∪Vs，具体公式为

式中：g为地面站，O为观测目标，S为卫星。考虑到卫星资源的有限性，链路在调度过程中可能会发生冲突，因此需要考虑从DCTSG 中选择可行的CP 方案。显然，可行的CPD 方案是DCTSG 的子图，图3 中方案1 和2 是可行的两种方案。

在图3 中，有4 种顶点和5 种链路弧线。4 种顶点分别为观测目标O，卫星S，地面站g以及数据中心D。采用时间间隙的模式，在每个间隙中拓扑可以看作是固定的，采用上下标区分每个节点的不同状态，其中表示卫星1 在第2 个间隙中的状态，以此类推，表示地面站2 在第1 个间隙中的状态，表示目标区域3 在第2 个间隙中的状态。5 种链路弧线包括机率链路弧线和存储弧线，分别为：1）橘黄色线，表示在每个时间间隙内，小卫星从观测目标区域收集任务数据的几率；2）绿线，表示卫星之间通过ISL 建立连接的概率和卫星转发任务数据到地面站的概率；3）红线，代表同一卫星在不同时刻的变化；4）蓝线，表示任务1 和2的可行数据传输路径，即可行的CP 方案；5）紫线，表示将校验数据发送给数据中心，其中校验数据包含了要传输任务的数据大小、数据类型、数据名称等简要信息。

数据校验的原因和过程：任务从数据发送地经过LEO 卫星网络的传输到数据接收地（地面站），但是在任务传输过程中可能因为ISL 冲突等原因发生流量阻塞，因此需要进行数据校验，以确定数据接收地接收到了数据发送地的所有数据。数据校验的过程为：当数据发送地发送数据到LEO 卫星网络（橘黄色线），会同时发送简短的信息（类似报文）到数据接收地（紫线），一般来说，地面网络的传输时延小于卫星网络的传输时延，因此并不会影响对于整体延迟的判断；接着数据中心接收到校验数据后会实时比较校验数据和转发数据（经过LEO 网络转发到地面站，再到数据中心）是否一致，若在时延容忍范围内两者数据不一致，则判定任务在LEO 卫星网络中发生了阻塞，因此需要进一步对其进行CPD。

2 问题描述

基于DCTSG 将ISL 和卫星能源作为约束条件，以最大化吞吐量为优化目标，将CPD 问题建模为约束优化问题。

2.1 相关约束

由于LEO 卫星网络中的资源是有限的，因此往往需要考虑在有限资源约束下进行CPD，本文主要考虑ISL 约束和卫星能源约束下的CPD 问题，以下为具体的约束条件：

1）ISL 资源约束 考虑卫星资源的有限性，假设每颗卫星有两个转发器，在同一时间最多只能建立两条链路：卫星到卫星之间的ISL 和卫星到地面的星地链路（satellite-ground link,SGL）。基于此假设，引入布尔型变量表示卫星节点的转发器是否被占用，公式为

假设一个卫星在某一时刻最多只能建立1 条ISL 和1 条SGL，于是有如下约束：

同时，1 个地面站在1 个时间间隙内，最多只能和1 个卫星建立连接，于是有如下约束：

2）能量约束 假设电池的最大放电深度为A，则卫星i在第t个时间间隙的剩余电量可表示为

式中：EBimax为卫星i的电池容量。

2.2 问题建模

式中：F为所有任务流f在时间¯λ上的集合，Ese为卫星从目标点收集数据弧线的集合。

假设卫星i从观测目标点收集数据消耗的功率和接收功率分别为Psc和Psr，则在时间间隙Δτ内卫星i收集数据和接收数据的能量大小为

式中：Ess为ISL 弧线的集合。

假设卫星i正常运行的功率为Pn，则在一个时间间隙内卫星运行消耗的能量可表示为

假设在t－1 个时间间隙结束时卫星i的剩余能量为，在第t个时间间隙内卫星i通过太阳板收集的能量为，则卫星i在第t个时间间隙的能源约束可表示为

根据以上约束条件，在DCTSG 的基础之上，将CPD 建模为基于DCTSG 的最大化吞吐量问题，最大化吞吐量问题可表示为

根据以上约束条件和优化目标可知，CPD 中的吞吐量问题需要确定大量的整数变量，而且式(13) 是一个整数线性规划问题，且该问题是NP-hard 问题，难以求解。

3 基于DCTSG 的连接计划设计

由第2 节可知，CPD 中的吞吐量问题是NP-hard 问题，求解该问题的时间复杂度较高。因此，提出了一种基于DCTSG 的CPD 方案，旨在求解出LEO 网络中吞吐量最大化的最佳CP。

3.1 DCTSG-CPD 整体方案

DCTSG-CPD 整体方案框图如图4 所示，在DCTSG 的基础上，首先通过比较校验数据和转发数据判断LEO 网络的连通性，若此时网络处于阻塞状态，则需要通过综合ISL 和卫星负载状态对当前错误CP 进行初始化、编码和修复，并通过适应度函数判断修复后CP 的优异程度，然后利用基于数据校验的遗传算法（data check genetic algorithm,DCGA）算法求解出吞吐量最大化的最佳CP，下面将展开对整体方案的具体描述。

3.2 网络连通性判断

在DCTSG 的基础上，LEO 卫星、数据发送地和数据中心被表示为网络节点，但是此时网络可能存在数据传输拥塞的问题，因此需要进一步分析网络的连通性。提出将网络模型分为两层：通过LEO 卫星网络转发数据的转发层和地面发送地发送数据的数据校验层。转发层负责将大规模流量转发到地面站，并由地面站进一步传输到数据中心处理；数据校验层主要负责将任务的简要信息（如任务的大小、类型和名称等）发送到数据中心，数据中心通过比较接收到的检验数据和转发数据的一致性，进而判断是否发生了流量阻塞（这里不考虑网络的其他传输问题，如卫星信道状况等），若数据一致，则转到3.3 节介绍的字符串更正和适应度判断；若发现校验数据和转发数据不一致，则判断空间传输层发生了流量阻塞。流量阻塞的原因可能有两种：1）因链路冲突而导致的阻塞，假设每个LEO 卫星最多只能建立一条ISL 和一条SGL，此时可能存在多个卫星同时和某个卫星建立ISL 的情况，因此会因链路冲突而发生网络阻塞；2）卫星满负载，即已无法接收其他卫星通过ISL 传输的数据，此时卫星会因为等待而导致网络阻塞。

3.3 字符串更正和适应度判断

根据以下方法对错误CP 进行修复。首先，把一对潜在连接随机表示为二进制字符，离散拓扑中所有的连接被表示为随机的二进制字符串。但是该过程并未考虑约束条件，因此接下来还需要对该二进制字符串加以更正，一个离散拓扑被编码为二进制字符串的过程如图5所示。

图5 二进制编码和修复Figure 5 Binary encoding and repair

由图5 可知，一串二进制字符串由多个单个字符组成，字符串的状态代表部分离散拓扑的瞬时连接状态，更正后的单个二进制字符代表卫星节点之间实际的连接状态：1 代表可建立ISL 传输数据，0 代表不可以建立ISL 传输数据。以为例，上标t表示第t个时间间隙，1 代表卫星S1和S3的转发器处于空闲状态，初始化生成的字符为1，表示卫星S1和S3之间正在通过ISL 进行数据传输。但是生成的字符串并没有考虑CPD 的约束，因此需要对其进行更正。更正需要考虑两个方面的因素：1）节点的链路状态，系统的传输方式为半双工传输，一个卫星节点在某一时刻只能使用一个转发器传输数据；2）链路的负载状态，若链路的负载状态为0，则不建立链路，避免造成链路资源的浪费。只有满足链路状态和节点状态同时为1 时，该链路才会建立。

经过以上步骤会更正错误的CP，生成大量的可行CP。但并不是所有可行CP 都是最优的，为了比较单个可行CP（个体）在所有可行CP（群体）中的优异程度，需要使用适应度函数进行判断。因为优化目标为最大化吞吐量，所以优化目标是非负的，故将目标函数作为个体适应度的判断函数，适应度函数如式(18) 所示，适应度函数的值越大，表明该CP 的适应性越高，越符合最大化吞吐量的要求。

3.4 DCGA 算法

DCGA 算法流程如图6 所示。在判断网络阻塞状态和二进制字符串适应度的基础上，本节进一步利用GA 中的选择、交叉和变异操作，生成满足适应度函数的更优解。

图6 DCGA 算法流程Figure 6 Process of DCGA algorithm

由于更正后的二进制字符串（即可行CP）无法保证LEO 卫星网络是连通的，因此需要进一步根据校验数据和转发数据判断网络阻塞状态，同时若LEO 网络是非阻塞状态，则进一步判断字符串的适应度，若满足字符串的适应度阈值，为进一步求得满足吞吐量最大化的最佳CP，则继续进行遗传算法中的选择、交叉和变异步骤，步骤具体过程描述如下：

步骤1选择

选择的目的是把优秀的CP 留给下一代。轮盘赌选择法是最常见、最简单的选择方法，它通过个体适应度与群体适应度之和的比率来确定每个CP 被选择的概率。CP 被选中的概率为

由式(19) 可以看出，个体被选择的概率与它在群体中的适应度比例成正比，个体的适应度越大，被选中的概率也就越大。

步骤2交叉和变异

交叉操作的目的是将优良的基因结合在一起，产生具有新的基因组合的个体。单点交叉是遗传算法中最常用的交叉方法，它是随机产生一个交叉位点，并在交叉点前后进行基因交换，可以使后代方便有效地保存亲本基因。

为了防止遗传算法在优化过程中陷入局部最优解，增强搜索全局最优解的可能性，在搜索过程中，需要对个体CP 进行变异，变异操作主要采用单点变异，也叫位变异，即只需要对基因序列中某一个位进行变异，二进制编码表示为：0 变为1，1 变为0。交叉和变异步骤与传统的遗传算法相似，此处不再赘述。

在完成一系列遗传操作后，会得到一个比亲本群体更大的新群体。根据初始群体的大小和个体的适应度，将个体从前到后进行选择，准备进入下一次迭代。由于在算法实施前无法知道优秀CP 的适应度，所以采用静态终止准则，即达到最大迭代次数时，算法终止。

4 仿真实验与结果分析

本节介绍仿真环境和具体的参数设置，然后从平均适应值、任务平均交付时间和任务数据到达率3 个方面进行了实验，并且对DCTSG 和DCGA 在这3 方面的表现进行分析。

4.1 仿真实验

为了验证DCTSG 和DCGA 的有效性，本文利用MATLAB 和卫星工具箱进行了仿真。

仿真场景由66 颗LEO 卫星构成的Iridium 二代卫星星座构成。该星座包含6 条极轨轨道，每条轨道拥有11 颗卫星，卫星轨道高度为780 km，轨道倾角为86.4°，仿真时长为24 000 s，具体仿真参数如表1 所示。假设建立ISL 的最大距离为4 000 km，卫星可以与同一轨道内相邻卫星和相邻轨道距离最近的卫星建立ISL，并且一颗卫星同一时刻最多建立一条ISL 和SGL。场景中共设置3 个观测目标区域，分别位于华盛顿、阿姆斯特丹和莫斯科，地面站分别位于重庆、北京和西安，每个数据分组的大小为1 Mbit，链路的数据传输速度为1 Mbit/s，所以链路每秒可以传输一个数据分组。3 个目标区域各发起30 个采集任务，所有任务共包含1 500 个数据分组。

表1 LEO 卫星网络相关参数Table 1 Parameters of LEO satellite networks

4.2 仿真结果分析

为了说明所提DCTSG-CPD 方案的优越性，将其在平均适应值、任务平均交付时间和任务数据到达率方面与TSG-CPD 和CPD 方案进行了对比分析。此外，为了证明所提DCGA算法的性能，将其与引入模拟生物竞争的GA 算法和基于演化计算的PSO 算法进行对比分析。

4.2.1 DCTSG-CPD 和TSG-CPD、CPD 的性能对比及分析

为体现出DCTSG-CPD 方案的性能优势，选取TSG-CPD 和CPD 方案作为对比。为保证仿真的准确性，以上3 种方案采取的算法均为DCGA 算法，除DCTSG-CPD 方案含有数据校验功能的数据中心、TSG-CPD 含有时空图和CPD 无时空图外，其他所有的参数设置均相同。仿真分别在平均适应值、任务平均交付时间和任务数据到达率3 个方面进行了大量CPD 实验。具体的仿真结果如图7～9 所示。

图7 平均适应值曲线Figure 7 Average fitness curve

图7 的平均适应值指的是可行CP 的平均适应值。由图7 可以看出，3 种方案的平均适应值都随着迭代次数的增加而增加。DCTSG-CPD 在迭代350 次后趋于稳定，TSG-CPD 在迭代200 次后趋于稳定，CPD 在迭代150 次后趋于稳定。但是，DCTSG-CPD 方案的适应值高于TSG-CPD，TSG-CPD 方案的适应值高于CPD。这是因为DCTSG-CPD 方案采用了纠正错误CP 的方法，使得每次迭代得到的可行CP 都是在满足适应度函数条件且没有ISL 冲突的最优CP，其他两种方案均未考虑利用卫星负载状态和ISL 状态对错误CP 进行纠正，因此平均适应值较低。TSG-CPD 方案相比较于DCTSG-CPD 方案，前者缺少纠正CP 的步骤，因此平均适应值低于后者。但是相比于CPD 方案，TSG-CPD 存在对卫星网络中可用资源的抽象化分析，且建立CP 的尝试次数少于无TSG 的CPD 方案，因此适应值也较高。

图8 是数据分组从数据发送地到达地面站平均消耗的时间。由图8 可以看出，随着迭代次数的增加，3 种方案的任务平均交付时间均先减少再趋于稳定。其中DCTSG-CPD 方案在迭代300 次后趋于稳定，TSG-CPD 方案在迭代200 次后趋于稳定，CPD 方案在迭代250 次后趋于稳定。由以上分析可知，相比其他两种方案，DCTSG-CPD 方案采用了纠正错误CP的方法，可以在更短的时间内选取无冲突的可用CP，TSG-CPD 方案虽然无纠正CP 的步骤，但是依然能够通过多次尝试找到可用的CP，CPD 方案不存在主动寻找可用CP 的步骤，于是在无可用ISL 的条件下，拥有负载的卫星节点会选择等待，流量被阻塞在卫星中，直到有可用的ISL 为止。因此，DCTSG-CPD 方案的交付时延小于TSG-CPD，TSG-CPD 方案的交付时延小于CPD。

图8 任务平均交付时间Figure 8 Average task delivery time

图9 是3 种方案数据分组到达率的对比。由图9 可以看出，随着迭代次数的增加，3 种方案的任务到达率均先增加再趋于稳定。图9 中，DCTSG-CPD 和TSG-CPD 方案在迭代250次后趋于稳定，CPD 方案在迭代100 次后趋于稳定，由此可见，与TSG-CPD 方案和CPD方案相比，DCTSG-CPD 方案能够在更短的时间内选取无冲突且适应度更高的CP。另外，如果采用单双工的传输模式，即同一时刻不存在多条ISL，那么更短传输时延的方案能够在相同的时间内传输更多的数据量，数据的到达率和吞吐量也就更高。因此，DCTSG-CPD 方案的吞吐量大于TSG-CPD，TSG-CPD 方案的吞吐量大于CPD。

图9 数据到达率Figure 9 Data arrival ratio

4.2.2 DCGA 算法和GA、PSO 算法的性能对比及分析

为体现出DCGA 算法性能的优越性，本文选取了PSO[18]和GA[20]算法这两种启发式算法作为对比算法。在设置参数时，GA 的参数和本文算法相同，而PSO 的最小惯性权重、最大惯性权重、局部学习因子和全局学习因子分别设置为0.6、0.8、2 和2。此外，算法中的种群大小为100，最大迭代次数为500，交叉率和变异率分别设置为0.6 和0.05。图10 为DCGA算法和GA、PSO 算法的性能对比。

图10 DCGA 算法和GA、PSO 算法的性能对比Figure 10 Performance comparison of DCGA algorithm with GA and PSO algorithm

图10(a) 中的平均适应值指的是CP 的平均适应值。由图10(a) 可以看出，3 种算法的平均适应值都随着迭代次数的增加而增加。但是GA 并未考虑到链路状态和负载状态，因此每次更新完比特序列之后，该算法需要对大部分的序列进行修复，导致该算法的迭代效率低于PSO 算法和DCGA。由于PSO 算法只受历史最优信息的影响，因此该算法的平均适应值很快收敛且落后于DCGA。又由于PSO 算法在每次迭代后会选择适应度高的CP，因此其寻优能力和整体的平均适应值也高于其他两种算法。

图10(b) 是数据分组到达地面站平均消耗的时间。由图10(b) 可以看出，3 种算法的时间变化规律基本与平均适应值的变化类似。整体的适应值越高，算法对应的数据分组到达地面站的传输时间越短。GA 算法因为没有考虑卫星负载和链路的状态，可能会发生链路阻塞，因此需要更多的迭代次数才能够收敛。DCGA 算法的传输时间小于PSO 算法，这是因为前者考虑到了节点负载状态和链路状态，能够更快地选择出适应值更高且在传输过程中无ISL 冲突的路径，能够有效地避免因数据在一条链路上长时间等待而导致链路阻塞的问题，因此交付时间更短。

图10(c) 是3 种算法数据分组到达率的对比。从图10(c) 中可以看出，所提算法的数据到达率明显高于其他两种算法。这是因为该算法考虑了链路状态和节点负载状态，在相同的时间内，本文算法中的数据分组并不会出现长时间等待的现象，当节点负载已满或者该链路处于忙碌状态被占用时，会立即寻找其他传输路径，直到有可行的ISL 为止，使得在相同时间内能够传输更多的数据，因此数据传输的达到率也较高。

5 结语

针对资源受限的LEO 卫星网络时空连通性和流量阻塞的问题，提出了一种基于数据校验时空图的CPD 方案。首先，构建了基于电池模型的DCTSG，并对CPD 问题进行建模；其次，给出了判断网络是否发生了流量拥塞的方法；接着，提出对错误CP 进行修复的方法；最后，设计了DCGA 算法求得最佳CP。仿真结果表明了该方案的有效性。