2. 清华大学 宇航技术研究中心, 北京 100084;
3. 北京空间信息中继传输技术研究中心, 北京 100094
2. Tsinghua Space Center, Tsinghua University, Beijing 100084, China;
3. Beijing Space Information Relay and Transmission Technology Center, Beijing 100094, China
中继卫星系统(TDRSS)一般部署于地球静止轨道,它是空间信息高速传输的骨干基础设施,也是空间信息网络的重要组成节点。传统的卫星地面站对近地圆轨道卫星的轨道覆盖率(用户通信链路建立的轨道弧段占总弧段的百分比)不到3%,而1颗中继卫星对其轨道覆盖率超过40%,若3颗中继卫星组网运行,可提供近100%的轨道覆盖率,显著提升业务的时效性[1-4]。
中继卫星安装机械伺服天线(称为单址天线)和多址相控阵天线为用户提供星间链路,随着用户目标数量和使用频度的迅速增长,高效调度中继卫星天线资源为更多用户提供服务已成为系统应用的现实需求。
中继卫星系统调度问题包括用户中继业务建模和系统服务建模两部分。其中,用户中继业务建模面向用户需求和相关约束,通过一组特征参数表征多用户业务,为系统服务模型输入完整、准确的业务特征信息,是本文研究的主要内容。系统服务建模则根据业务模型的输出结果和系统资源情况,设计服务模型和求解算法,将业务安排到指定的天线资源和指定时间段执行。限于中继卫星系统业务的复杂性和多样性,以往关于系统调度问题研究主要集中在优化服务模型和求解算法方面,对业务模型的研究涉及较少[5-10]。另外,对业务特征的描述不够完整,缺少空间维度信息[11],会影响系统服务模型的设计和算法的应用效果,调度结果往往与用户实际需要存在偏差。
本文针对中继卫星单址天线资源的使用开展研究。由于单址天线增益高,是中继卫星提供测控、数传等业务的主要手段。然而,由于天线在转动过程即业务准备过程中无法服务其他业务,转动时间即业务准备时间会显著影响中继卫星系统应用效能。另一方面,用户在空间分布的不均匀以及相对空间位置的动态变化使得单址天线服务相邻用户业务所需的转动时间也随之变化。现有的系统调度通常将业务默认为在空间中均匀分布,模型求解时为所有用户预留最大并且相同的天线转动时间,由此导致的系统可调度资源的损失可达20%以上。
文[5]、[6]及[8]采用带有时间窗的并行机服务模型研究了美国航空航天局 (NASA)中继卫星系统调度问题,对业务时间窗引入了松紧度的定义,该定义限于中继卫星对用户的可视窗口,不能充分体现用户业务的时效性以及相同用户业务时间间隔这两个要素。文[7]针对中继卫星系统设计了一种CSP模型,该模型考虑了可见时间窗口、任务优先级、调度目标、调度准则等因素,调度模型的输入是一组预先假设的具有确定时长的业务,限制了调度算法的灵活性。文[11]面向NASA空间信息网络架构问题给出了业务时长、传输速率和容忍延迟等几个特征参数,由于缺少业务的空间维度信息,还不能用于描述时空敏感类的中继业务。
本文首先从中继卫星系统调度问题的原理出发,将问题转化为中继卫星星间链路天线的跟踪指向路径问题,进而在传统服务模型[5-6]基础上引入中继天线指向角度作为空间维度变量,改进了传统的业务时序约束关系,为调度优化提供了条件。通过对中继卫星系统实际业务数据的特征分析,构建了一个能够统一表征多样化业务特征的参数化模型。该模型可从时间、空间2个维度描述中继业务特征,为系统调度提供更为精确的业务分布信息。最后,采用该模型对TDRSS的多种业务进行描述,并基于典型的中继卫星系统双星服务场景进行数值仿真,调度结果表明: 该模型可有效提升中继卫星系统的应用效能。
1 系统调度原理在构建业务模型前有必要对中继卫星系统调度问题的原理进行分析,并在传统混合整数规划服务模型[5-6]中引入中继天线指向角度,改进业务时序约束关系。
1.1 问题分析中继业务具有如下特点: 同时存在多类型天线执行中继业务[4],并且业务必须在用户目标可视窗口范围内进行; 用户目标通常具有高动态性和一定的轨道特征,业务时空跨度大; 中继卫星提供服务的具体方式是通过单址天线转动或多址天线数字波束合成跟踪指向用户,因此较适宜采用天线角度信息表征业务的空间位置。正是由于上述业务特殊性使得中继卫星系统调度不同于一般的机器调度问题,本文将原问题转化为中继卫星星间链路天线的跟踪指向路径问题。但是,传统路径问题[12-13]通常面向地面的静止或低速移动目标,目标间的空间关系采用大地坐标系下的距离进行分析,业务时空跨度较小,以往关于地面多车辆路径问题的建模方法[12-13]并不完全适用于本文研究的问题。
为了便于分析和建立模型,本文首先将大地坐标系中的用户目标轨道位置转换为中继卫星星间链路天线坐标系中的方位角和俯仰角,建立中继天线跟踪指向路径,再将跟踪指向路径投影到时间轴形成业务调度序列。原理如图 1所示。
在图 1中,节点0对应中继卫星天线指向路径的起点和终点,节点1至5分别按序号对应用户中继业务。业务执行和业务准备过程中的天线指向路径分别由实线和虚线表示。调度过程主要考虑如下因素: 每个业务最多由一副天线执行一次,且不可间断; 业务执行窗口必须在用户可视窗口内,而且为确保业务时效性,业务开始时刻也应在一定的延迟范围内; 同一用户相邻业务的时间间隔满足一定约束; 下一业务开始时刻必须大于前一业务结束时刻与相邻业务准备时间之和。可见,为了优化业务准备时长,需要在中继天线的跟踪指向路径问题中引入空间维度变量,建立新的业务时序约束关系。
1.2 业务时序约束关系在传统服务模型[5-6]中,天线k上相邻业务i、j的业务时序受式(1)约束:
$~x_{i,j}^{k}(t_{i}^{s}+d_{i}^{k}+s_{i,j}^{k}-t_{j}^{s})\le 0,k\in K,i,j\in J.$ | (1) |
其中: K表示天线序号集合,J表示业务序号集合,xi,jk是业务序列化变量。如果在天线k上,业务j在i之后调度,则xi,jk=1; 否则xi,jk=0。 tis和tis分别为业务i和j在天线k上的调度开始时间变量,dik为业务i在天线k上的持续时间变量。 si,jk为天线k从业务i结束到业务j开始所需准备时间变量。为改进约束式(1),需针对si,jk定义如下变量和参数。在天线k本体坐标系下,αi,tk和βi,tk分别为业务i在t时刻所处空间位置相对于天线k的方位角和俯仰角变量,tie为业务i结束时刻变量,vk为天线k转动角速度。
这样,通过将业务的空间位置转换为中继卫星天线指向角度,改进了传统业务时序约束式(1)中的分量si,jk:
$~s_{i,j}^{k}=\frac{max(|\alpha _{j,t_{j}^{s}}^{k}-\alpha _{i,t_{i}^{e}}^{k}\left| , \right|\beta _{j,t_{j}^{s}}^{k}-\beta _{i,t_{i}^{e}}^{k}|)}{{{v}_{k}}}.$ | (2) |
从式(2)可以看出: 业务j、i所处空间位置对应的中继卫星天线方位角(或俯仰角)差异越大,si,jk就越长,浪费的天线资源越多,反之越少。这样,将中继卫星天线的指向角度引入传统的业务时序约束关系,为进一步优化调度结果提供了条件。与此对应,就要求在后续业务建模过程中将中继天线指向角度要素纳入业务的时空特征描述中。
2 业务建模 2.1 业务特征分析中继卫星系统用户主要有下列6种类型业务: 用户遥测、跟踪测量、用户遥控、科学遥感数据回传、语音、图像。前3种可以统一为TTC(telemetry,tracking and command)业务。这些业务包括用户原始需求集合α和主要约束集合β两部分特征信息。
集合α包括如下参数:
1) Vd表示用户数据量传输需求。
2) Co表示对用户跟踪测量的轨道覆盖需求。
3) Dt,s表示业务发生在特定时空范围内的需求。
集合β包括如下参数:
1) Ltmax表示业务开始时刻可延迟的时长约束,即业务实际开始时刻距理论开始时刻可推迟最大时间。
2) Rbmax(或Rng={r1,r2,…,rng})表示对频段和数据中继传输速率的约束,即用户载荷能够支持的最高速率(或包含ng个速率档位的集合)。
3) Tmax和Tmin表示用户中继终端载荷工作时长约束,即用户中继终端可持续工作的最大时长和最小时长。
4) Tgmax和Tgmin表示同一用户所属相邻业务最大和最小时间间隔。
5) Tp表示用户自身任务规划周期的时长跨度约束。
对上述信息进行抽象和处理,可以得到表征用户中继业务的特征参数集合γ,具体包括:
1) Td表示中继业务时长。实测数据表明: 同一用户中继业务时长在较小范围内均匀分布,不同用户由于轨道位置以及具体业务特点,其中继业务时长有明显差异。本文面向常态化中继业务的时长特征,从最小时长开始沿时间轴均匀划分为10个时间段,每个时间段为280 s,最小时长设置为50 s,以业务时长落入相应时间段的概率来描述时长分布情况。采用这种方法,对两个用户中继业务时长分析如表 1所示。
时间段/s | 用户1 | 用户2 |
50~330 | 0 | 0.4 |
330~610 | 0.03 | 0.6 |
610~890 | 0.3 | 0 |
890~1 170 | 0.3 | 0 |
1 170~1 450 | 0.35 | 0 |
1 450~1 730 | 0.02 | 0 |
1 730~2 010 | 0 | 0 |
2 010~2 290 | 0 | 0 |
2 290~2 570 | 0 | 0 |
2 570~2 850 | 0 | 0 |
从表 1可见,用户1中继业务时长主要分布在610~1 450 s范围内,而用户2分布在50~610 s范围内。这种差异主要与其具体业务特点有关,用户1执行科学遥感数据回传业务,数据量传输需求大,用户2执行TTC业务,数据量较小。
2) Np表示用户任务规划周期范围内的中继业务次数。各用户的任务规划工作具有一定周期性如一周、一天或几个小时。对于带有周期性约束的用户需求,中继卫星系统为用户服务也要满足这种周期性约束。
3) Rb表示中继传输速率。在实际工程中,首先尽量选择较高速率完成用户需求,如果业务调度前估算通信链路质量不能满足要求,就可能提前调低中继传输速率。
4) Ptn,z描述中继业务在时间和空间两个维度的分布情况。由于用户对中继业务的需求可能发生在特定的时间区间,也可能集中分布在一定空间范围,而且这两类需求还可能同时存在。
5) Lt表示中继业务开始时刻的容忍延迟,指业务实际开始时刻距理论开始时刻可推迟的时间长度,该参数反映业务在时间域的急迫程度。例如,航天器在轨常态运行情况下,其遥测接收业务的容忍延时比较大,但火箭发射阶段中的遥测接收业务实时性要求很高,容忍延时接近0。
6) Tg表示同一用户所属相邻中继业务的时间间隔。它反映了用户载荷能源、软硬件设备状态切换以及业务之间的逻辑关系。
2.2 业务模型在上述分析基础上,构建中继卫星系统业务特征参数模型,模型的输入信息为α和β,模型输出信息为γ。这组业务特征参数从多个维度表征用户对于中继卫星系统的服务需求和工作约束,将为后一阶段系统服务调度模型提供必要的输入信息和优化空间。
为进一步说明α、β和γ之间的数学关系,在γ定义基础上,具体针对该用户第n个中继业务定义如下具体变量: 中继业务时长Tn,d、中继业务传输速率Rn,b、业务开始时刻的容忍延迟Ln,t、第(n+1)个业务开始时刻距第n个业务结束时刻时间间隔Tn,g。
这样,系统业务模型中的各参数满足如下约束关系:
$\sum\limits_{n = 1}^{{N_p}} {} ({R_{n,{\rm{b}}}} \times {T_{n,{\rm{d}}}}) = {V_{\rm{d}}};$ | (3) |
${T_{{\rm{min}}}} \le {T_{n,{\rm{d}}}} \le {T_{{\rm{max}}}},\forall n \in \{ 1,2, \ldots ,{N_{\rm{p}}}\} ;$ | (4) |
${R_{n,{\rm{b}}}} \le {R_{{\rm{bmax}}}},{R_{n,{\rm{b}}}} \in {R_{{\rm{ng}}}},\forall \in \{ 1,2, \ldots ,{N_{\rm{p}}}\} ;$ | (5) |
$0\le {{L}_{n,\text{t}}}\le {{L}_{\text{tmax}}},\forall n\in \{1,2,\ldots ,{{N}_{\text{p}}}\};~$ | (6) |
$\sum\limits_{n=1}^{{{N}_{\text{p}}}}{{}}{{T}_{n,\text{d}}}+\sum\limits_{n=1}^{{{N}_{\text{p}}}-1}{{}}{{T}_{n,\text{g}}}\le {{T}_{\text{p}}};~$ | (7) |
${{T}_{\text{gmin}}}\le {{T}_{n,\text{g}}}\le {{T}_{\text{gmax}}},\forall n\in \{1,2,\ldots ,{{N}_{\text{p}}}\};$ | (8) |
$\frac{\sum\limits_{n=1}^{{{N}_{\text{p}}}}{{}}{{T}_{n,\text{d}}}}{{{T}_{\text{p}}}}\ge {{C}_{\text{o}}}.$ | (9) |
其中: 式(3)表示中继传输的数据量需求; 式(4)表示中继业务时长要满足用户中继终端载荷工作时长约束; 式(5)表示中继传输速率要满足用户中继终端速率设计约束; 式(6)表示中继业务开始时刻的延迟不大于用户约束的最大延迟; 式(7)表示某用户所有中继业务要安排在其任务规划周期范围内; 式(8)表示同一用户相邻业务时间间隔要满足用户约束; 式(9)表示中继卫星系统对用户跟踪测量的轨道覆盖率要满足用户需求。
2.3 业务时空特征描述本文在节1.2引入空间维度变量,与此对应就需要在业务模型中对中继业务的时空特征分别进行定量描述。
中继业务在时间维度的分布情况由业务开始时刻落入任务规划周期范围内各时间子区间的概率分布表征。从便于调度计算方面考虑,采用中继卫星天线坐标系下的业务开始点和结束点坐标(由中继天线方位角和俯仰角组成)表示业务的空间位置信息,故中继业务在空间的分布情况由这2个特殊点对应的天线方位角、俯仰角分别落入各角度子区间的概率分布描述。要针对不同类型业务的历史实际数据开展分析,合理划分时间子区间和角度子区间。
将一个任务周期均匀划分为TN个时段,用tn代表每个时段的编号,从1开始顺序编号。将中继天线方位角、俯仰角分别划分Zα和Zβ个角度区间,用zα和zβ分别代表方位角和俯仰角区间的编号,都从1开始顺序编号。假设用户X共有N个中继业务,其中第i个业务的开始和结束时刻分别为tis和tie,该业务开始和结束点在中继天线k坐标系下对应的空间位置坐标由天线方位角和俯仰角组成,分别表示为(αi,tisk,βi,tisk)和(αi,tiek,βi,tiek)。
第i个业务开始时刻落入时段tn的概率为pi,tn,且
设计两个验证试验: 1) 用本文业务模型对TDRSS的多种业务进行统一描述,检验该模型是否具有一定的适用性; 2) 将业务模型用于典型的中继卫星系统双星调度场景进行数值仿真,分析业务模型对于调度效率的影响。
3.1 TDRSS业务特征描述2014年美国TDRSS为NASA、美国地质调查局(USUG)和美国国家海洋和大气管理局(NOAA)三大机构所属6大类共41个用户提供中继服务[11],具体信息如表 2所示。
用户类型 | 标识 | 用户数 |
低轨、低速、科学类 | LEO-Sci-Low | 21 |
低轨、中速、科学类 | LEO-Sci-Mod | 1 |
低轨、高速、科学类 | LEO-Sci-Mod | 3 |
大椭圆轨道、中速、科学类 | LEO-Sci-Low | 12 |
地轨气象类 | LEO-Weather | 3 |
低轨载人飞船 | LEO-HSF | 1 |
将TDRSS用户主要需求和工作约束作为本文系统业务模型的输入信息,模型输出结果见表 3,与文[11]描述吻合,说明该模型适用于描述多种类型中继业务。其中U(x,y)表示在[x,y]之间均匀分布。
用户 | 业务 | Td/s | Np/d-1 | Rb/(Mb·s-1) | Lt/s | Tg/s |
LEO-Sci-Low | TTC | U(330,890) | 15 | 1 | (0,7 200] | (3 600,5 500] |
LEO-Sci-Low | 科学遥感 | U(330,890) | 15 | 30 | (0,7 200] | (3 600,5 500] |
LEO-Sci-Mod | TTC | U(330,890) | 15 | 1 | (0,7 200] | (3 600,5 500] |
LEO-Sci-Mod | 科学遥感 | U(330,890) | 15 | 60 | (0,7 200] | (3 600,5 500] |
LEO-Sci-High | TTC | U(610,1 170) | 15 | 1 | (0,7 200] | (3 600,5 200] |
LEO-Sci-High | 科学遥感 | U(610,1 170) | 15 | 400 | (0,7 200] | (3 600,5 200] |
HEO-Sci-Mod | TTC | U(330,890) | 15 | 1 | (0,7 200] | (3 600,5 500] |
HEO-Sci-Mod | 科学遥感 | U(330,890) | 15 | 60 | (0,7 200] | (3 600,5 500] |
LEO-Weather | TTC | U(610,1 170) | 15 | 1 | (0,2 100] | (1 800,5 200] |
LEO-Weather | 科学遥感 | U(610,1 170) | 15 | 160 | (0,2 100] | (1 800,5 200] |
LEO-HSF | TTC | 5 760 | 15 | 0.072 | 0 | 0 |
LEO-HSF | 科学遥感 | 5 760 | 15 | 150 | 0 | 0 |
LEO-HSF | 视频 | 5 760 | 15 | 150 | 0 | 0 |
3.2 数值仿真
采用NASA经典的双星调度服务场景[5],分别对基于现有业务特征描述和本文业务特征描述的用户需求进行调度仿真。双星服务场景如图 2所示。
单颗中继卫星安装2面单址天线支持S和Ka两个频段,1面多址天线支持S频段多址业务。 2颗中继卫星共计6面天线提供调度服务,用户申请调度服务的业务总数为400个,任务规划周期为 86 400 s。 采用文[5]方法设计5种业务数据,每种数据随机生成5组实例,共计25组业务实例,再在每组实例中引入业务时空分布信息。
采用贪婪算法分3种情况对每组实例进行调度求解: 1) 理想情况,即单址天线相邻业务间转动时长为0,相邻业务间不需要准备时间,单址天线完成上一业务后直接开始下一业务; 2) 采用现有业务模型,单址天线相邻业务间转动时长设定为最大可能值; 3) 采用本文业务模型,考虑单址天线实际转动速度,引入业务时空分布信息。
为了比对3种情况对应的调度结果,定义了调度业务完成率和单址天线无效资源占比这2个指标。调度业务完成率表示可以调度完成的业务数与业务需求总数的比值,仿真结果如图 3所示。
单址天线无效资源占比定义为天线在相邻业务间转动的累积时长与单址天线总的任务规划周期比值:
${{R}_{SA}}=\frac{\sum\limits_{k=1}^{{{N}_{\text{SA}}}}{{}}\sum\limits_{i=1}^{{{N}_{k}}}{{}}s_{i-1,i}^{k}}{{{T}_{\text{p}}}{{N}_{\text{SA}}}}.$ | (10) |
其中: Tp和NSA分别表示任务规划周期和单址天线个数,Nk为第k个单址天线上安排调度的业务数,si-1,ik表示单址天线k从第(i-1)个业务结束点到第i个业务开始点的转动时长,仿真结果如图 4所示。理想情况下单址天线无效资源占比为0。仿真结果表明: 1) 相比理想情况,采用现有业务模型,中继业务调度完成率平均下降18.94%,单址天线无效资源占比平均增加24.27%,业务准备期间的单址天线转动时长对系统效益影响显著。 2) 在现有业务模型中引入业务时空分布信息后,中继业务调度完成率平均增加10.65%,天线无效资源占比平均减少12.85%,有效提升了中继卫星系统效益。
4 结 论
考虑到中继卫星系统业务具有的多类型、大时空跨度、不均匀分布特点,本文进行了中继卫星业务时空特征研究,构建了统一表征用户中继业务特征的参数化模型。通过引入空间维度的变量改进传统的业务时序约束关系,解决了现有业务模型对时间和空间特征描述不准确的问题。数值仿真结果表明: 采用新的业务模型后,调度业务完成率平均增加 10.65%,单址天线无效资源占比平均减少12.85%,有效提升了中继卫星系统完成任务的能力。下一步将从调度模型和算法方面优化系统调度方法,压缩无效资源占比,进一步提升系统应用效能。
[1] | Gramling J J, Chrissotimos N G. Three generations of NASA's tracking and data relay satellite system[C]//2008 AIAA SpaceOps Conference. Heidelberg, Germany:AIAA press, 2008:1-11. |
[2] | 王家胜, 齐鑫. 为载人航天服务的中国数据中继卫星系统[J]. 中国科学(技术科学版), 2014, 44(3): 235–242. WANG Jiasheng, QI Xin. China's data relay satellite system served for manned spaceflight[J]. Sci Sin Tech, 2014, 44(3): 235–242. (in Chinese) |
[3] | 黄惠明. 我国第一代中继卫星地面应用系统发展建设的思考[J]. 飞行器测控学报, 2012, 31(5): 1–5. HUANG Huiming. Reflections on development of the ground system of the first generation CTDRSS[J]. Journal of Spacecraft TT&C Technology, 2012, 31(5): 1–5. (in Chinese) |
[4] | Goddard Space Flight Center/Exploration and Space Communications Projects Division. Space Network Handbook[M]. Greenbelt, Maryland: Goddard Space Flight Center, 2007. |
[5] | Rojanasoonthon S, Bard J, Reddy S. Algorithms for parallel machine scheduling:A case study of the tracking and data relay satellite system[J]. Journal of the Operational Research Society, 2003, 54: 806–821. DOI:10.1057/palgrave.jors.2601575 |
[6] | Rojanasoonthon S, Bard J. A grasp for parallel machine scheduling with time windows[J]. INFORMS Journal on Computing, 2005, 17(1): 32–51. DOI:10.1287/ijoc.1030.0048 |
[7] | FANG Yanshen, CHEN Yingwu. Constraint programming model of TDRSS single access link scheduling problem[C]//Proceedings of the Fifth International Conference on Machine Learning and Cybernetics. Dalian, China:IEEE Press, 2006:948-951. |
[8] | LIN Peng, KUANG Linling, CHEN Xiang, et al. Adaptive subsequence adjustment with evolutionary asymmetric path relinking for TDRSS scheduling[J]. Journal of Systems Engineering and Electronics, 2014, 25(5): 800–810. DOI:10.1109/JSEE.2014.00093 |
[9] | 林鹏, 晏坚, 费立刚, 等. 中继卫星系统的多星多天线动态调度方法[J]. 清华大学学报(自然科学版), 2015, 55(5): 491–496. LIN Peng, YAN Jian, FEI Ligang, et al. Multi-satellite and multi-antenna TDRSS dynamic scheduling method[J]. J Tsinghua Univ(Sci and Tech), 2015, 55(5): 491–496. (in Chinese) |
[10] | ZHAO Weihu, ZHAO Jing, LI Yongjun, et al. Resources scheduling for data relay satellite with microwave andoptical hybrid links based on improved niche genetic algorithm[J]. International Journal for Light and Electron Optics, 2014, 125(13): 3370–3375. DOI:10.1016/j.ijleo.2013.12.042 |
[11] | Inigo DEL Portillo. Contributions to ITACA:A Tool to Architect Space Communication Networks[D]. Cambridge, MA, USA:Massachusetts Institute of Technology, 2014. |
[12] | Laporte G. The vehicle routing problem:An overview of exact and approximate algorithms[J]. European Journal of Operational Research, 1992, 59(3): 345–358. DOI:10.1016/0377-2217(92)90192-C |
[13] | Toth P, Vigo D. Vehicle Routing Problems, Methods and Applications[M]. 2nd ED. Philadelphia, PE, USA: Society for Industrial and Applied Mathematics, 2014. |