卫星网络中基于时变图的节能资源分配策略*

帅家成，刘雨,2**，望育梅,2

（1.北京邮电大学人工智能学院，北京 100876；2.鹏城实验室网络与通信研究中心，广东 深圳 518000）

0 引言

卫星网络由于其覆盖范围广、不受地理因素影响等特点，被广泛用于自然灾害的检测、灾害损失评估等多种地球观测任务。由于卫星网络的高动态性、链路的不连续性与高时延等特征，其资源的时变表示是当前研究难点之一[1-2]。此外，由于卫星节点能量主要由太阳能电池板提供，所以卫星在太阳光被遮挡时无法获得能量，这就导致能量同样成为卫星网络路由的稀缺资源[3]。文献[4] 用时变图（TEG,Time-Expanded Graph）来表示卫星网络的时变拓扑并研究了当卫星节点资源受限时网络中的资源分配问题，解决了当网络中节点资源受限时的最大流问题，但并没有考虑能量消耗。文献[5]、文献[6] 讨论了卫星网络中的资源分配策略，但没有降低网络中的能量消耗。文献[7] 提出了一种从用户行为分析的角度研究了数据中继卫星（DRS,Data Relay Satellite）系统中的资源分配问题，然而仍没有将传输能耗作为优化指标。文献[8]、文献[9] 提出了基于时变图的低能耗路由算法，但会降低网络的吞吐量性能。

为了解决观测任务中资源分配的传输能耗问题，本文提出了一种贪心迭代式算法，来对观测任务中的能耗进行优化，同时保证网络吞吐量不减少。首先，为了表示网络动态变化的拓扑，采用了时变图[10]来表示网络中的连接情况、能耗水平等，在时间与空间两个维度上的关系。由于卫星节点的资源受限，当一颗卫星的传输资源小于能与其建立连接的链路容量之和时，需要进行传输资源的分配。本文在时变图中添加了虚拟节点来表示受限的卫星传输资源，并添加了虚拟起点、虚拟终点与虚拟边来简化问题。此外，能耗水平被添加至图中构成资源能耗时变图（RCTEG,Resource-Cost Time-Expanded Graph）。基于RCTEG，将本文提出的算法与文献[4] 中的Ford-Fulkerson 算法和文献[11] 中 的Boykov-Kolmogorov 算法进行了对比，验证了本文提出算法在减少能耗的同时不损耗网络吞吐量。

1 系统模型

1.1 任务模型

假设在网络中存在R颗卫星，一个地面目标S，一个地面站D。R颗卫星中存在R1颗遥感卫星与R2颗中继卫星。遥感卫星从地面目标S获取数据后，如果存在连接，其可以选择直接将数据传至地面站D，也可以选择将数据传至中继卫星，最终将数据传至地面站，中继卫星只能从遥感卫星获取数据，无法直接从地面目标获取数据，其任务过程如图1 所示。由于卫星节点的资源受限，在卫星可同时与多个节点建立连接且无法同时以所有链路的最大容量进行传输时，需要进行传输资源的分配，以使网络能耗减小的同时不以牺牲吞吐量为代价。设需要进行资源分配的卫星节点数目为R3。

图1 地球观测任务

1.2 能耗模型

卫星网络中，星间链路的传输会受到衰减，其中最主要的是自由空间传播衰减。卫星的接收功率PR由式(1)决定[12]：

式中，PT为发射功率，GT为发射天线增益，GT为接收天线增益，LP为自由空间传播衰减，LP由式(2) 决定：

式中d为传播距离，λ为工作波长，c为光速，f为工作频率。假设星间与星地通信的工作频率相同，接收与发射增益相同，则当接收功率相同时，卫星节点的发射功率仅与两点的传输距离相关，假设传输时间t相同，则卫星节点的传输能耗e仅与传输节点之间的距离相关，如式(3) 所示，式中k可以看作一个常数。

由于卫星节点的高度移动性，两节点之间在连接窗口内的距离不断变化，将单次连接窗口内的卫星传输能耗视为由两节点之间的平均距离决定。由于无需研究卫星传输的具体能量，将能耗进行了归一化，将平均距离为6 300 km 的卫星传输能耗设为1。通过式(3)得到其他链路的传输能耗水平。

1.3 资源能耗时变图

为了表示网络中传输资源，能耗在时间与空间上的关系，本文将传输能耗的概念引入TEG[10]，得到RCTEG。在RCTEG 中，时间T被分为h个时隙T=｛t1,t2,……,th｝，每个时隙的长度为Δτ，每个时隙内的拓扑是固定不变的。RCTEG 由节点集V、链路集A、容量集C与能耗集E构成，RCTEG={(V,A,C,E)}。

节点集V包括：源点集VS={Si|1≤i≤h}表示h个时隙内的地面目标；遥感卫星节点集1≤l≤R1}表示h个时隙内的遥感卫星；中继卫星节点集表示h个时隙内的中继卫星；终点集VD={Di|1≤i≤h}表示h个时隙内的地面站；虚拟节点集表示h个时隙内需要进行资源分配的卫星节点对应的虚拟节点。此外，节点集还包括虚拟起点Sv与虚拟终点Dv，通过虚拟起点与终点可以使网络的多源多汇问题转化为单源单汇问题。

链路集A包括：传输链路集1≤i≤h,v∈V-VD,v∈V-VS-VR3}表示在同一时隙内的星间链路或星地链路；存储链路集表示同个实体节点在不同时隙间的存储能力；虚拟链路集表示需要进行资源分配的节点与其虚拟节点之间的连接；辅助链路集Aa={(Sv,Si),(Di,Dv)|1≤i≤h}表示虚拟起点、虚拟终点与起点和终点之间的连接。

由TEG（图2（a））改造后的RCTEG={(V,A,C,E)}如图2（b）所示。图中，Sv为虚拟起点，S1与S2为前两个时隙内的地面目标，A1与A2分别同时与两个节点存在连接，且这两个链路的容量之和比A1与A2的传输资源大，A1与A2无法同时满足两个链路的最大容量传输，所以需要进行传输资源的分配。而B1、B2、C1与C2的传输资源等于与其连接的链路容量，所以无需建立虚拟节点。为A1与A2的虚拟节点，用来表示两节点资源的受限。D1与D2为前两个时隙内的地面终点站，Dv则为虚拟终点。在RCTEG 中，除虚拟节点外，所有节点都与其在其他时隙的对应节点由存储链路相连。构造RCTEG 的关键为，得到需要进行资源分配的节点添加虚拟节点集VR3和通过节点之间的距离从而得到其能耗集E。

图2 两个时隙内的RCTEG

2 基于RCTEG的节能资源分配算法

2.1 问题模型

本文需要解决的问题是寻找一种使网络流量达到最大同时能耗较低的传输资源分配方案。在时间T内，问题可被描述为：

流守恒限制：流入节点与流出节点的流量相等。

在满足容量限制与流守恒限制的条件下，本文问题的优化目标为在不损耗网络流量的同时降低能量消耗。

2.2 基于RCTEG的节能资源分配算法

基于RCTEG，本文提出了一种贪心的迭代寻找网络中最小能耗资源分配方案的流扩充算法（EERA,Energy Efficient Resource Allocation），在不损耗网络吞吐量的同时，尽可能地减少网络的总能耗。此算法在搜寻路径时总是优先寻找能耗较小的路径并将节点的资源分配到此路径内，从而得到能耗较小的分配方案。

算法步骤如下。

首先，根据网络的连通情况找到需要进行资源分配的节点并构造虚拟节点集VR2，此后，根据节点之间的距离获得链路的能耗集E，构造出当前网络的RCTEG。

第二步，在图中，根据能耗集E找到网络中从虚拟起点Sv到虚拟终点Dv的一条最小能耗路径Pmin_cost，作为一条可扩充流路径。

第三步，根据容量集C沿此条路径寻找各个链路的可扩充流量，选择各个链路中可扩充流量的最小值作为该路径的可扩充流Δfp进行流的扩充，得到fp并更新容量集C。

此后，经过流扩充之后，进行能耗集E的重构，在E中为有流流过但未达到链路最大容量的边添加反向边能耗，达到链路容量的边则只存在反向边能耗。

最后，回到第二步，直到无法找到图中从虚拟起点Sv到虚拟终点Dv的一条最小能耗路径时，算法结束，并得到网络的节能最大流量资源分配方案。

以图2 中的两个时隙内网络拓扑为例，图3 为EERA算法与Ford-Fulkerson 算法的分配方案对比。图中绿色边表示有流经过，绿色数字表示经过流的大小，红色边与红色数字表示EERA 算法的不同资源分配选择。

Ford-Fulkerson 算法得到的分配方案中（图3（a）），链路中流过的流量为5，链路中流过的流量为15，而EERA 算法得到的分配方案中（图3（b）），链路中流过的流量为15，链路中流过的流量为5。Ford-Fulkerson 算法与EERA 算法得到的网络流量同为40，但EERA 算法网络的总能耗为255，而Ford-Fulkerson 算法所得到的网络能耗为300。

图3 EERA算法与Ford-Fulkerson算法的资源分配对比

3 仿真实验

利用STK（Satellite Tool Kit，卫星工具包），可以获得卫星网络的连通情况与网络各节点的距离，通过计算平均距离可得到卫星链路的归一化能耗。在仿真中，本文在两个不同的网络中对算法的性能进行了验证。

两种网络场景下的地面目标均为罗马，地面站均为北京，仿真时间两个小时。遥感卫星的数目设置为2，位于太阳同步轨道，高度为631 km，倾角为97.9°。中继卫星轨道高度为1 414 km，倾角为52°。遥感卫星从地面获取数据的速率设置均为120 Mbit/s，星间链路容量设置为20 Mbit/s，星地链路容量设置为30 Mbit/s。第一种网络下中继卫星为(12/6/4)Walker 星座，共12 颗卫星，第二种网络下中继卫星为(18/6/4)Walker 星座，共18 颗卫星。

在每种网络场景中，分别进行了两组实验，第一组实验中将存储能力设置为5 000 MB。传输资源在10～50 Mbit/s 之间变化。第二组实验中，传输资源设置为30 Mbit/s，存储能力在3 500～6 500 MB 之间变化。对比算法采用了文献[4]中采用的Ford-Fulkerson算法与Boykov-Kolmogorov算法[11]。

网络中存在12 颗中继卫星时，三种算法的能耗、吞吐量随传输资源变化而变化的对比如图4。由图4 可见，三种算法在不同传输资源下的吞吐量相同，而本文提出的EERA 算法的网络总能耗小于其他两种算法。网络中存在18 颗中继卫星时的三种算法的性能对比如图5。同样地，三种算法的吞吐量相同，而EERA 算法的能耗要明显小于其他两种算法。且在相对复杂的网络中，EERA 的节能效果较明显。

图4 12颗中继卫星时三种算法性能随传输资源变化的对比

图5 18颗中继卫星时三种算法性能随传输资源变化的对比

第一种网络下，三种算法的能耗与吞吐量随卫星节点的存储能力变化的对比如图6 所示。同样可以看出，存储能力变化的同时，三种算法的吞吐量相同，而EERA算法的能耗要小于其他两种算法。第二种网络下的三种算法随存储能力变化的性能对比如图7。同样地，EERA算法与其他两种最大流算法得到的吞吐量相同而能耗要少于另外两种算法。且在较为复杂的第二种网络中，其能量消耗的减少较为明显。

图6 12颗中继卫星时三种算法性能随存储能力变化的对比

图7 18颗中继卫星时三种算法性能随传输能力变化的对比

4 结束语

本文考虑了卫星网络中地球观测任务中，在卫星节点传输资源受限情况下的传输资源分配问题。基于时变图，提出了一种贪心的迭代寻找网络中最小能耗资源分配方案的流扩充算法EERA，此算法可以在不损耗网络吞吐量的条件下降低网络能耗。通过与当前已有研究的对比得到，此算法可有效降低能耗并不已牺牲吞吐量为代价。此外，算法在较复杂网络中的效果更优。下一步将考虑地面网络与更复杂的卫星星座融合的低能耗资源分配策略。