基于负载均衡的导航时分网络建链优化技术研究

贾卫松 王琦 李露铭 岳佳

(1 北京空间飞行器总体设计部，北京 100094)(2 北京跟踪与通信技术研究所，北京 100094) (3 太原卫星发射中心技术部，太原 030027)

全球卫星导航系统具备利用地面站完成全球导航卫星管理的能力，利用星间链路通过境内卫星快速完成境外卫星的测控管理及运控信息注入。同时，全球卫星导航系统的战略作用要求其在没有地面站支持情况下实现长时间自主运行，在自主运行期间实现60天自主定轨与时间同步。因此导航星座中的卫星之间的链路数量应大于4条，从而为自主导航提供充足的高精度星间测量信息。根据短响应时间、高建链精度、长链路寿命、建链灵活的需求，全球卫星导航系统可基于相控阵天线周期轮询构建星间链路，形成卫星连接拓扑随时间变化的延迟容忍网络。

由于卫星网络的时分建链特性，导致卫星网络路由规划策略有别于地面网络，需要考虑星间拓扑随时间的演化，在路径权值计算时增加建链时间因素。针对延迟容忍网络(Delay Tolerant Network，DTN)网络的路由问题，文献[1]基于轮询建链模式构建星间链路分配方案，提出星座内信息传输路径选择方法，文献[2]等将接触计划建模为公平系数和平均时延的多目标优化问题，提出利用模拟退火算法求解建链规划，均未考虑网络流量的负载均衡。针对负载均衡，文献[3]等提出了基于本地队列的最早投递和基于全网队列的最早投递路由算法，文献[4]提出一种基于局部队列的的最早投递路由算法，但网络节点间进行队列信息的交互对于延迟容忍网络而言时延较大，队列信息容易过时。而且基于队列状态的负载均衡，需要在固定的建链拓扑规划的基础上动态计算路由，无法保证建链计划相对于随机的路由策略的最优化。

全球卫星导航系统星座网络中卫星与卫星、卫星与地面站之间的可见性关系是周期性可预测的，因此导航卫星网络的最优链路拓扑也是可预先规划的。一旦拓扑确定，则基于特定约束的图路由算法计算出的端到端最短路径也是确定的[5-7]，进而提前获得基于路径集合的每个卫星节点的负载。本文在建链及路由规划之初即考虑节点负载情况及业务非对称特性，利用模拟退火全局最优搜索算法实现平均时延、最大时延和负载均衡多优化目标约束下的建链规划求解，以接入能力、网络时延、网络容量为指标验证时分网络建链规划方法对负载进行均衡的性能。

1 网络模型及优化目标

由于卫星平台和星间链路的约束，导航卫星装配天线数量有限，而自主定轨与时间同步要求每颗卫星与尽量多的卫星建立星间链路，以获得较好的几何精度因子(Geometic Dilution of Precision, GDOP)值。当导航卫星只携带一台相控阵收发信机时，在规划的时隙内，每颗卫星至多建立一条半双工星间链路。为保证卫星之间建链的公平性，即本星与其它每颗卫星建立星间链路的机会较为均等，将导航星座运行周期划分为若干建链周期T，在每个建链周期T中，导航卫星重复的依次与不同的卫星建立链路，直至卫星可见性发生变化，形成典型的延迟容忍网络，如图1所示。

图1 导航网络轮询建链Fig.1 Polling chain building of navigation network

在建链周期T内的星座链路状态可视为有限状态机，其中每个状态代表卫星在某时隙内的链路配对关系。划分建链周期T为n个时隙，对应状态机中的n个状态。令k∈(1,n)表示第k个时隙，基于时间代价和建链规划构建导航卫星网络的图模型。

(1)pk,is,id表征第k个时隙卫星is和卫星id的建链关系，其中卫星is的下标s代表源卫星，卫星id的下标d代表目的卫星。

(2)ek,is,id表征第k个时隙卫星is和卫星id间的边代价，若卫星is与卫星id在时隙k直接建链，则边代价仅包含通信带来的时间代价；若卫星is与卫星id在t个时隙后建立链接，则边代价包含通信时间代价和延迟时间代价Δk；若卫星is与卫星id始终不建链，则边代价为无穷大。

(3)ck,is,id表征第k个时隙卫星is和卫星id的最小代价。

为便于形象的描述图模型，如图2所示利用4个卫星节点建立导航卫星网络的时变图结构。

图2 导航卫星网络简化模型Fig.2 Simplified model of navigation satellite network

定义lk,i1,id={(k+Δk1,i1,i2),(k+Δk2,i2,i3)…(k+Δkd-1,id-1,id)}表征在第k个时隙信息从源卫星节点i1出发到达目的卫星节点id的最短路径，最短路径依次经过卫星i1、i2、i3…id，则lk+Δk1,i2,id={(k+Δk2,i2,i3)…(k+Δkd-1,id-1,id)}且lk+Δk1,i2,id∈lk,i1,id。即若第k时隙从卫星i1到卫星id的最短路径中包含卫星i2，则在第k+Δk1时隙从卫星i2出发到达id的最短路径必然与时隙k从卫星i1到卫星id的最短路径重合。因此，在一个建链周期内的任意时隙计算出的端到端最短路径与其他时隙的端到端最短路径彼此重合，端到端的信息传递最短路径是唯一的。当在确定建链规划下利用改进的Dijkstra算法[8]计算出唯一的最短路径时，卫星节点对中转信息的路由选择策略也随之确定，以确保网络中的信息均能够沿着最优路径传递。所以在不考虑突发非对称流量的前提下，对导航卫星网络的路由负载均衡的过程就是对建链规划的优化过程。

导航卫星网络中承载着遥测业务、遥控业务、自主导航业务，其中遥测业务从非接入卫星通过网络转发至接入卫星下行至地面站，而遥控业务通过地面站上传至接入卫星并转发至非接入卫星，使导航卫星网络呈现流量长期非对称的特点。接入卫星在导航卫星网络中作为星地的连接枢纽负载压力较大，如图3所示。

图3 导航业务非对称流量示意图Fig.3 Asymmetric flow diagram of navigation service

设定M为接入卫星集合，在建链规划时，应优先保证接入卫星作为起点或终点的端到端路径时延最小，实现基于非对称业务的负载均衡。此外，在端到端最短路径集合L={l1,i1,id,l1,i2,id…ln,id-2,id,ln,id-1,id}中出现卫星节点i的次数越多，代表在信息流经卫星节点i的概率越大，可以提前通过建链重规划调整最短路径集，实现基于卫星节点的负载均衡。

2 基于负载均衡的建链规划方法

基于时变图的导航卫星网络建链规划问题，实质上是基于多优化目标的全局最优解搜索问题。首先设定目标函数并计算最优值，通过持续调整建链规划，利用模拟退火算法求解近似全局最优解，寻优过程的关键步骤在以下章节中进行详细说明。

2.1 模拟退火优化

若采用遗传算法求解，则影响网络链路路径的基因仅包含时间和节点流量相关的因素，相较而言利用模拟退火算法对最优路径的求解更为有效。优化步骤如下。

(1)设置初始温度τ=1，形成初始建链规划及评价函数值f(xold)；

(2)通过调整产生新的建链规划；

(3)计算得到新的评价函数值f(xnew)；

(4)计算增量Δf=f(xnew)-f(xold)；

(6)若连续λ次调整未被接受，则结束优化，若调整次数小于λ则跳转至步骤2；

(7)τ=τ×μ，当τ>τmin时，转至步骤2。

模拟退火中温度下降的速度μ和调整次数λ取决于建链优化过程中评价函数值变化速度，若评价函数值能够快速收敛，则μ和λ可以设置为较小值。

2.2 确定评价函数

为达到负载均衡的目的，首先需要考虑卫星节点的存储负载，减小各个卫星节点的存储区利用率的差异；此外，为适应导航卫星网络流量长期非对称的特点，在评价函数中引入接入卫星上行与下行端到端时延，使额外承载着星地流量的接入卫星获得更高的建链优先权；同时，以平均端到端时延和最大端到端时延保证网络整体性能，满足自主导航信息的实时交互要求。综合以上因素，定义求解最优建链规划的目标函数为f(x)=αDAverage+βDMax+γDAeverageUp+δDAverageDown+εEMeanSquare。其中DAverage为平均端到端时延，DMax表示最大端到端时延，DAeverageUp表示接入卫星上行平均端到端时延，DAverageDown表示接入卫星下行平均端到端时延，EMeanSquare表示在最优路径集合中卫星节点负载均方差，其中卫星节点负载利用最优路径集合中节点出现次数表征。以α、β、γ、δ、ε为各指标的调节因子，当非对称业务流量较大时，提高γ和δ的值，当非对称业务流量较小时，则降低γ和δ的值。建链规划问题从而转化为寻找f(x)全局最小值的问题。

2.3 最短路径计算

本文通过改进Dijkstra算法完成时变网络图中时隙k源节点is到任意目的节点id的端到端最短路径的计算，算法步骤如下：

(1)设定V为星座网络节点集合，Q为最短路径节点集合，Q集合中的元素代表某卫星是否已经被纳入至最短路径集合L中，P=V-Q为尚未纳入至最短路径集合L的节点集合。

(2)初始化最短路径节点集合Q和最短路径集合L，使其包含源节点is，初始化ck,is,id为∞。

(3)在P中找到与is距离值最短的卫星节点iu，并将iu加入至Q和L。

(4)对L中目的卫星节点id∈P的路径进行松弛，若ck,is,id>(ck,is,iu+ek+Δk,iu,id)，则将节点iu加入至最短路径集合中的最短路径lk,is,id，并修改最短路径距离值ck,is,id。

(5)重复步骤(3)和(4)，所有卫星节点均被纳入最短路径节点集合Q，即Q=V。

与卫星节点始终可见的持续链路网络拓扑Dijkstra算法不同，由于时变图的时间演化特性，在对非最优路径进行松弛的时候，中间节点iu到目的卫星id的边代价应为ek+Δk,iu,id而非ek,iu,id，其中Δk=ck,is,iu代表在Δk个时隙后信息地带卫星iu，并准备从卫星iu出发。

2.4 调整建链规划

当目标函数解未达到最优值时，需要对建链规划进行微量调整，本文采用随机链路交换方法，步骤如下：

(1)随机产生时隙k，卫星1、卫星2；

(2)根据原建链规划获取卫星1指向的卫星3，卫星2指向的卫星4；

(3)若卫星3与卫星4为不同卫星，则对卫星1、卫星2、卫星3和卫星4进行可见性匹配，若不能产生与原建链规划存在差异的链路，则转至步骤(1)继续产生随机值。

3 性能仿真

3.1 仿真场景参数设置

导航卫星网络采用24MEO+3GEO+3IGSO的星座，其中MEO构型选择walker24/3/1，每颗卫星携带一条星间链路。基于网络参数构建STK仿真场景，获得星间可见性，形成建链规划方案。基于负载均衡的建链规划方法形成建链配置方案A，以最小平均端到端时延作为优化目标形成建链配置方案B。利用Matlab搭建导航卫星网络节点传输仿真平台，通过仿真结果比较不同方案的网络时延、容量和接入能力。表1列出了导航卫星星座网络模型参数。

表1 导航卫星星座网络参数

3.2 优化结果分析

对建链规划的负载均衡可以从两方面进行评价：①在确定的网络负载下，评估网络的最大时延、卫星节点缓存占用及平均时延；②在网络节点参数不变的情况下，不断提高接入流量，评估网络的最大接入能力。

1)基于确定网络负载的评估

设置导航卫星仿真模型参数如表2所示。设置基于负载均衡的建链规划方法中的评价函数指标权重调节因子如表3所示。

在流量非对称的导航卫星网络的管理控制场景中，利用基于负载均衡的建链规划方法形成的建链配置方案A，仅以平均端到端时延作为优化目标形成建链规划方案B，如图4所示。

表2 导航卫星网络传输仿真参数

表3 评价函数指标权重调节因子

图4 基于确定网络负载的评估结果Fig.4 Evaluation results based on determining network load

分析仿真结果发现，方案A中各卫星节点的端到端最大时延、节点缓存占用率优于方案B，端到端最大时延出现在方案B中的第24号卫星，卫星节点最大负载出现在方案B的第22号卫星。方案A与方案B的平均端到端时延差值小于1，性能基本一致。这是因为方案B是以平均端到端时延作为优化目标的，而方案A兼顾了其他指标。

2)基于接入能力的评估

按表2设置导航卫星仿真模型参数，并调整其中遥控业务注入速率。比较基于表2调节因子的负载均衡方案A以及基于平均时延优化的最大遥控业务注入速率，见图5。

图5 基于最大接入能力的评估结果Fig.5 Evaluation results based on maximum access capability

图5中可以看出，基于负载均衡的建链规划网络中遥控业务的接入能力为25帧每时隙，若对基于平均时延优化的建链规划网络注入同样的负荷，则会在4号、5号、10号、14号、17号、23号卫星节点发生丢帧现象。基于平均时延优化的建链规划网络的最大接入能力为16帧每时隙，远低于基于负载均衡的方案。

综上所述，基于负载均衡的DTN网络建链规划方案在不影响平均端到端时延的基础上有效实现导航卫星网络卫星节点间的负载的均衡。

4 结束语

本文建立导航星座时分复用网络模型，根据固定建链拓扑下最优路由路径的唯一性，以及导航卫星网络业务信息路径非对称特点，提出在拓扑建链规划时提高网络路由负载均衡性能的方法。仿真结果表明，基于负载均衡的拓扑建链优化方法优于以平均端到端时延为优化目标的建链方法，能够实现业务信息在各卫星节点间高效均衡的传输，为全球导航系统星间链路的链路规划提供支持。下一步研究将在建链规划过程中考虑更多的影响因素。例如，卫星可见性变化会导致建链规划切换，信息传输过程中会发生最优路径的变化，需要保证切换过程中网络时延性能不会下降。此外，自主导航需要导航卫星之间建立更多的测距链路，且具有较好的几何精度因子；在选择地面接入节点时，需要考虑卫星仰角、星地建链时长以及地面接入卫星数量对建链规划带来的影响。