基于自适应算子与非支配排序的星地网络多目标优化方法

李浩辉,周 雨,2,田金今,赵晓辉,雷 磊,3*

(1.西安交通大学 信息与通信工程学院,陕西 西安 710049;2.香港理工大学 电子计算学系,香港 999077;3.东南大学 移动通信国家重点实验室,江苏 南京 210096)

0 引言

随着低轨 (Low Earth Orbit,LEO) 卫星通信技术的不断发展,低轨卫星可在大尺度覆盖空间中为用户提供高速、稳定、低延迟的通信服务,从而满足用户对于星地高速通信的需求。基于此,低轨卫星通信在5G和6G网络的应用场景不断拓展[1]。在大规模星地网络优化运营中,待服务用户数量的激增以及差异化的用户数据服务请求可能导致星地网络出现负载不均、超载和拥挤等问题[2]。为了提高网络性能和用户体验,对低轨卫星和地面系统多维资源进行联合优化调度被认为是具有成本效益的解决方案之一[3]。传统的低轨卫星网络资源管理方法通常采用单目标优化策略,即只考虑单一指标(如网络吞吐量、延迟等)的优化;而实际中,多个指标优化过程中的资源分配策略和资源竞争程度,可影响系统整体性能[4]。因此,研究基于多目标优化的6G低轨卫星网络资源调度管理方法对提升星地网络整体性能指标有着积极的意义。

近年来,大量研究聚焦在星地网络资源调度优化问题上。文献[5]针对非理想动态环境,设计了基于Meta-Critic Learning的算法,提升星地系统资源调度决策的泛化性能。文献[6]采用启发式优化算法对多波束低轨卫星的带宽和功率进行联合分配。文献[7]介绍了动态多目标优化的研究现状以及性能评估的指标,包括进化算法、遗传算法、粒子群算法、模拟退火算法等。这些算法通过改进适应度函数、引入自适应参数、增加多样性保持机制等方法来适应动态环境,提高算法的性能。文献[8]阐述了多种多目标优化评估指标。文献[9]研究了基于自然梯度的Actor-Critic强化学习方法在低轨卫星网络服务功能链部署问题中的应用。

星地融合网络的资源调度优化问题本质上是一类多约束和多维度的大规模复杂优化决策问题。在实际运营中,通常需要同时优化多个性能指标如吞吐量、接入终端数量等,而多个目标在优化过程中,往往相互冲突。如何在多个指标间达到较好的折中,对星地网络资源高效、高质量的调度优化有着重要意义。本文针对星地网络如何同时提高终端接入数量与提高多用户吞吐的优化问题,进行基于单目标和多目标优化的建模。首先,产生不同权重并对单目标优化问题进行最优求解,产生多组优化结果作为性能比较的基准方案之一;随后,提出基于快速非支配排序与自适应算子调整的高效多目标优化(Non-Dominated Sorting and Adaptive Operator Adjustment Based Multi-Objective Optimization,NSA-MOO)算法,同时对多个目标函数进行优化。仿真结果表明,所提算法与加权单目标优化和传统多目标优化算法如非支配排序遗传(Non-dominated Sorting Genetic Algorithm-II,NSGA-II)算法相比,可有效提升整体优化性能。

1 星地网络系统模型

1.1 系统模型

本文考虑星地网络下行链路场景,如图1所示。该系统模型由多颗低轨卫星和一组地面终端构成。由于地面终端请求激增和系统通信资源有限,该系统模型的主要优化目标是利用有限的资源尽可能服务更多的地面终端和满足差异化的终端数据请求[10]。地面终端的集合表示为K={1,…,k,…,K},低轨卫星发射端的集合表示为N={1,…,n,…,N}。由于低轨卫星超高移动性带来的有限服务时间的影响,场景中假设星地间的传输任务应在T个时隙内完成,即T={1,…,t,…,T}。在数据传输中,每个发射端n以单播模式服务地面终端k,即一个发射端-地面终端链路(n,k)。在一个时隙内,可存在多个发射端-地面终端链路同时传输数据,形成一个链路组。

图1 星地网络系统模型示意图Fig.1 Illustrative scenario for a satellite-terrestrial system

定义G={1,…,g,…,G}表示所有可能的发射端-地面终端链路组的集合,并引入二进制参数αk,n,g来表示一个链路组中被激活的链路,其中αk,n,g=1表示发射端-终端链路(n,k)在链路组g中被激活,αk,n,g=0则表示未被激活。本文通过枚举所有可能的链路组,并根据单播约束定义二进制参数αk,n,g:

(1)

(2)

式(1)表示在星地网络系统的一个时隙内,发射端-终端链路组g中的每个终端k最多接收来自一个低轨卫星的数据,而式(2)表示,一个时隙内,发射端-终端链路组g中的每个LEOn服务不超过一个地面终端。受式(1)和式(2)的限制,星地网络发射端-终端链路g组在t时隙的地面终端k的SINR和每时隙传输的数据分别表示为:

(3)

Rk,g,t=φBlb(1+γk,g,t),

(4)

式中:pn为LEOn的发射功率,hk,n,t为在t时隙发射端n与地面终端k之间的信道状态信息,φ为每个时隙的持续时间,B为低轨卫星的固定带宽。

1.2 信道模型

在星地网络下行链路系统模型中,假设由低轨卫星高速运动引起的多普勒频移可以在已知地面终端位置、卫星轨道和卫星速度的情况下得到有效的预(后)补偿[11-12]。在时隙t中,地面终端k和发射端n之间的信道状态可以建模为:

hk,n,t=GT·GC·GR,

(5)

式中:GT和GR分别为发射天线和接收天线的增益,GC表示信道损耗,假设单天线地面终端具有相同的接收天线增益GR。对于低轨卫星到地面终端的信道,GC建模为莱斯衰落信道,包括自由空间路径损耗、俯仰角衰落、大气衰落、莱斯小尺度衰落[13],可表示为:

(6)

式中:c为光速,d为低轨卫星与地面终端之间的传播距离,fc为低轨卫星的载波频率,GH为俯仰角衰落,φ为莱斯衰落因子,A(d)为大气损失,表示为:

(7)

式中:χ单位为dB/km,表示信号通过云雨的衰减,h为低轨卫星距离海平面的高度。

2 优化问题建模

本文研究了一个星地网络下行链路中的过载场景,即资源有限,T时隙内无法成功服务全部终端以及满足全部数据传输请求。本节针对链路组-时隙调度的优化问题,进行建模求解,用以服务尽可能多的地面终端并传输尽可能多的数据。二进制变量x=[x1,1,…,xg,t,…,xG,T]T表示链路组-时隙的调度,其中:

(8)

在实际场景中,考虑到终端数据请求过于密集导致星地网络系统过载,系统可能无法满足每个终端的数据需求Dk,本文设计了一个复合效用函数式(9),并定义当满足阈值时D′k(D′k≤Dk),系统被认为已服务一个终端k,即fk(x)=1。例如,终端k请求高分辨率数据(如1080P)传输,系统无法完全满足该请求,转而在T时隙暂时以中低分辨率数据(如360P)服务终端k,达到定义的传输阈值。

(9)

式中:I(ο)是一个指示函数,表示为:

(10)

通过引入辅助变量y=[y1,…,yk,…,yK]T和线性约束式(15),将非线性函数fk(x)转换为线性函数,其中yk=fk(x)。

多目标优化问题P1可以表示为:

(11)

(12)

minf1(x,y),f2(x,y)

∀k∈K,g∈G,t∈T,

(13)

(14)

(15)

xg,t∈{0,1},∀g∈G,t∈T,

(16)

yk∈{0,1},∀k∈K。

(17)

通过加权求和的方式可将多目标优化问题转换为单目标优化问题作为比较基准,因此该单目标优化问题P2表示为:

(18)

式中:w0,w1,…,wk是各优化目标的权重。

式(14)表示在满足式(1)和式(2)的基础上,一个时隙最多调度一个链路组g。

式(15)中,如果地面终端k被成功服务,即yk=1,终端k接收到的数据量应该大于成功服务的最小要求D′k,与式(8)的效果一致。

式(16)～(17)为变量xg,t,yk的二进制约束。

3 求解方法

3.1 单目标优化问题P2的最优求解

(19)

(20)

(21)

式中:E为全1矩阵,并且

(22)

P2属于0-1型二次整数规划(Quadratic Integer Programming,QIP)问题。因P2的对称矩阵半正定,所以其松弛问题为凸。

基于上述结论,单目标优化问题P2的全局最优解可以通过分支定界法(Branch and Bound)进行求解[15],因其松弛问题为凸,固每一轮可求解一个凸优化问题。如图2所示,通过尽可能遍历权值w0,w1,…,wk,可获得不同的优化结果即图中的圆形点与叉形点,最终,连续的圆形点形成一条近似的边界可作为基于加权单目标优化的一组最优解,作为性能基准之一,可与多目标优化的结果进行后续比较。

图2 基于权值遍历的单目标优化结果示意图Fig.2 Illustrative results for single-objective optimization P2

3.2 多目标优化问题P1的求解方法NSA-MOO

对于P1的求解,实验中发现传统的多目标优化算法如遗传算法易陷入局部最优和偏离Pareto前沿[16]。针对上述问题,采用NSA-MOO算法对多目标优化问题进行求解。相较于遗传算法,NSA-MOO针对问题特性,设计了快速非支配排序(Fast Non-dominated Sorting,FNS)以及自适应算子调整(Adaptive Operator Adjustment,AOA)的策略,以保证所得到的Pareto前沿解的多样性和有效性[17]。

3.2.1 快速非支配排序

FNS是多目标优化中应用广泛的一种策略,用于将解的集合划分为不同的Pareto等级。FNS策略的基本思想是通过快速排序和二分查找的方式,对解集合进行递归划分,将解集合划分为不同的Pareto等级,算法的流程如下:

① 初始化:将所有解的支配计数设为0,并创建一个空的前沿列表。

② 对于每个解zA={f1(x,y),f2(x,y)},遍历整个解集,比较zA与zB的支配关系:如果zA支配zB,则将zB的支配计数加1;如果zB支配zA,则将zA添加到zB的支配列表中。

③ 对于每个zA,如果其支配计数为0,则将其标记为第一级前沿,并将其添加到前沿列表中。

④ 对于同一级Pareto前沿解,利用拥挤度大小进行排序,拥挤度为当前解与其相邻解之间的距离。

⑤ 对于每个前沿,重复上述步骤,通过精英保留策略获得M个精英个体。每次迭代时,前一级前沿中的解被标记为下一级前沿。

3.2.2 自适应算子调整策略

(23)

(24)

(25)

(26)

(27)

式中:γ1>γ2>γ3≥0表示根据不同情况所设置的奖励,HV(·)为超体积指标(Hypervolume,HV)的计算公式[9],该指标用于衡量解的质量,HV越大,解的质量越好。基于上述奖励,策略权重可以被自适应更新为:

(28)

式中:ξ∈(0,1)是一个更新系数。

(29)

3.2.3 NSA-MOO算法流程

NSA-MOO算法的流程图如图3所示,随机产生大小为M的初始种群。如果当前迭代次数d小于最大迭代次数,则依次执行FNS与AOA策略,并进入下一轮迭代。如果当前算法已达最大迭代次数则终止。

图3 NSA-MOO算法流程图Fig.3 Flowchart of NSA-MOO algorithm

4 仿真验证

本节通过单目标优化和多目标优化方法对过载场景下的星地网络系统资源优化问题进行求解,并分析对比其性能。仿真中,覆盖区域的卫星数量为2,区域内的终端数量为25,时隙个数为8,时隙持续时间为0.1 s,低轨卫星发射功率为100 W,Ka波段的频率为30 GHz,信道带宽为400 MHz,低轨卫星高度为500 km。

图4为单目标优化结果与多目标优化结果的对比图。可以看出,成功服务的地面终端数量与星地系统总体传输数据量这两个优化目标相互冲突。如果单目标优化中权重分配不当,可能导致各项指标恶化,如图4横坐标区间5～7时传输数据量下降,以及横坐标区间9～12时,系统无法成功服务多于9个用户。相较之下NSA-MOO在Pareto前沿解的多样性上明显优于单目标优化。同时NSA-MOO优化的结果相较于单目标优化来说在成功服务地面终端数量为5～9时,系统的整体传输数据量更多。表明了NSA-MOO算法在处理本模型问题时,所得到的优化结果无论是在多样性还是收敛性上都优于单目标优化处理的结果。

图4 单目标优化结果与NSA-MOO结果对比Fig.4 Result of single-objective optimization and NSA-MOO

图5为NSA-MOO算法与NSGA-Ⅱ多目标优化算法在世代距离(Generational Distance,GD)指标的比较图。NSA-MOO算法相较于NSGA-Ⅱ算法引进了AOA机制以获得更快的收敛速率以及更加宽广的多样性。在评估达到7 000多次时NSA-MOO算法的GD指标基本达到收敛,而NSGA-Ⅱ算法在评估次数达到10 000时,GD指标才接近于收敛。图5表明NSA-MOO算法在此模型上的性能在整体上收敛速率优于NSGA-Ⅱ。

图5 NSA-MOO与NSGA-Ⅱ算法GD指标对比Fig.5 Comparison of GD between NSA-MOO and NSGA-II algorithm

由上述分析可知,本文提出的NSA-MOO算法在处理星地网络系统资源调度优化问题时相较于单目标优化具有更优的性能,在所得到Pareto前沿解的多样性和收敛性上都优于单目标优化。而对比NSGA-Ⅱ算法,NSA-MOO算法具有更快的收敛速率。

5 结论

本文研究了6G低轨卫星星地网络通信系统中的一类资源调度优化问题,用于同时提高终端接入数量和多用户吞吐量的性能指标。首先,基于加权求和的单目标优化方法对资源调度优化问题进行求解,通过分配不同权重,产生一组解作为性能比较的基准方案之一;随后,提出基于非支配排序与自适应算子调整的多目标优化算法NSA-MOO得到一组非支配帕累托解并与NSGA-Ⅱ算法进行对比。仿真结果表明,NSA-MOO算法在本文研究的星地网络场景下相较于单目标优化与NSGA-Ⅱ算法具有一定的优越性。