卫星边缘计算中任务卸载与资源分配联合优化算法

方 海,高 媛,赵 扬,杨 旭

(中国空间技术研究院 西安空间无线电技术研究所 有效载荷系统创新中心,西安 710100)

1 引 言

卫星将是未来6G网络的必要部分[1-3],通过接入卫星完成各类业务的需求不断增加,其中包含延迟敏感业务,例如环境感知、目标提取、交通管理、预警等,在这些业务中传感器产生的数据越来越多,传统卫星网络将数据回传至地面处理的中心式处理计算时延越来越大,与业务的低时延要求形成矛盾.随着技术的发展,卫星的计算和存储能力不断增加,将每颗卫星视为边缘节点,实现在轨边缘计算,通过在数据源处处理数据,可以降低卫星数据传输带来的延迟[4].因此如何通过对网络边缘分散的卫星资源合理分配和调度,实现低轨卫星、高轨卫星和地面云中心的协同,提供低时延业务的支持能力,成为卫星边缘计算的挑战之一.

文献[5-8]从架构和应用上对天基边缘计算进行了研究,提出了卫星边缘计算架构,将卫星边缘计算系统分为包括用户节点、卫星边缘节点和地面数据中心3部分,可以减少业务时延以及节省带宽.文献[9]进一步介绍了将传统卫星改造成空间边缘计算节点相应的卫星硬件结构和软件架构,通过卫星资源的虚拟化,实现灵活的计算服务.文献[10]对天地一体化边缘计算网络中的协同计算卸载、多节点任务调度和移动性管理等进行的全面详尽的分析,并指出了卫星边缘计算面临的技术挑战.文献[11]考虑卫星是具有计算和存储资源的边缘计算平台,通过解决混合整数线性规划问题来解决系统服务请求调度决策和服务放置问题.文献[12]提出了一种基于软件定义网络和网络功能虚拟化的卫星边缘云架构,提出同时考虑能源消耗、服务延迟和资源利用的计算资源调度方法.由于卫星平台的通信、功耗、计算资源均受限,文献[13-16]研究联合计算通信资源分配和卸载决策的卸载算法,分别基于深度强化学习、博弈论和启发式搜索算法实现卸载决策,以减少系统服务时延和功耗.

现有文献对于卫星网络边缘计算的卸载决策算法大多需要多次迭代,算法执行时间长,不利于实际应用.本文基于低轨、高轨、地面云中心三层网络拓扑结构构建卫星网络边缘计算场景,对卫星无线资源、计算资源分配和卸载决策进行联合优化,减少系统延迟和能耗,同时满足卫星边缘计算环境的功能和性能要求.

2 系统模型

未来天地一体化信息网络系统将包含高轨骨干和低轨接入卫星[17],因此,考虑如图1所示的卫星边缘计算场景,高轨卫星、低轨卫星和地面云计算中心为各类型资源受限的卫星终端提供计算服务,地面或者空中卫星终端通过低轨星座接入卫星网络,由于低轨卫星和地面云计算中心不能保证连续可见,低轨卫星通过高轨卫星与地面云计算中心通信,其中高轨卫星、低轨卫星都具备边缘计算服务能力.低轨卫星的计算任务可以是低轨卫星本身产生的,也可以是接入该卫星的陆海空终端产生的,低轨卫星的计算任务分为本地计算、卸载到高轨卫星计算或卸载到地面云计算中心计算3种类型,其中,高轨卫星的计算能力介于低轨卫星和地面云计算中心之间.高轨卫星和地面云计算中心总是可见的.

图1 卫星边缘计算系统结构图

2.1 卫星计算任务模型

低轨卫星u的计算任务Tu,由描述,du为任务Tu的待计算数据量,单位为bits,cu为该任务所需的计算周期数,单位为cycles,各节点计算资源单位为cycles/s,设fu,l为低轨卫星u的本地可用计算资源,fu,s为高轨卫星s分配给用户u的计算资源,fu,e为地面云计算中心分配给用户u的计算资源.一个计算周期的能耗ε=κf2,κ为能耗系数,f是处理器主频.

低轨卫星u本地执行任务Tu的能量消耗为:

Eu,l=κ(fu,l)2cu[J]

(1)

2.2 通信模型

低轨卫星到高轨卫星的可用带宽B分成W个子带,每个子带带宽为Bsub.某个低轨卫星任务可以分配使用bu,s个子带,0≤bu,s≤W.仅考虑低轨卫星到高轨卫星链路的带宽分配,馈电链路带宽认为是够用的.

低轨卫星u到高轨卫星s的链路信噪比为:

(2)

其中,N0为背景噪声功率谱密度,hu,s为低轨卫星u到卫星s上行信道增益,包括路损和天线增益,pu为低轨卫星u卸载任务时数据发送的发射功率,0

Ru,s=Bsubbu,slog2(1+γu,s)

(3)

2.3 卸载开销

定义Us={u∈U|xu,s=1}为任务要卸载到高轨卫星s的低轨卫星集合.定义Ue={u∈U|xu,e=1}为任务要卸载到地面云计算中心e的低轨卫星集合.则卸载任务的低轨卫星集合Uoff=Us∪Ue.

带宽资源分配策略B={bu,s|u∈U},高轨卫星s分给低轨卫星u的通信带宽资源bu,s,bu,s>0,u∈Uoff,bu,s∈[1,W],bu,s=0,u∉Uoff.

功率资源分配策略P={pu|u∈U},pu>0,u∈Uoff,pu=0,u∉Uoff.

任务卸载策略X={xu,l,xu,s,xu,e|u∈U},xu,l=1,表示低轨卫星u的任务Tu低轨卫星本地执行,xu,l=0时表示不在本地执行.卸载变量xu,s=1,表示低轨卫星u的任务Tu卸载到高轨s执行,xu,s=0时表示不在高轨s执行.xu,e=1,表示低轨卫星u的任务Tu通过高轨s卸载到地面云计算中心执行,xu,e=0时表示不在地面云计算中心执行.

卸载开销分为时延和低轨卫星功耗两部分,设低轨卫星u完成任务Tu时延为tu,则:

(4)

将低轨卫星u的开销定义为:

(5)

2.4 问题形式化描述

将系统开销定义为所有低轨卫星的卸载开销的加权和:

(6)

式(6)中,λu为用户权重,将联合任务卸载和资源分配问题描述为系统开销最小化问题,

(7)

xu,l∈{0,1},∀u∈U

(8)

xu,s∈{0,1},∀u∈U

(9)

xu,e∈{0,1},∀u∈U

(10)

xu,l+xu,s+xu,e=1,∀u∈U

(11)

(12)

0

(13)

(14)

fu,s>0,∀u∈Us

(15)

其中式(8)～式(11)是卸载约束,表示每个任务可以本地执行或者卸载到地面云中心或者高轨卫星;式(12)是无线资源分配分配约束,即分配的总带宽不能超过该服务器总带宽;式(13)是功率约束,确定每个低轨卫星的发射功率;式(14)～式(15)是计算资源约束,为接入高轨卫星的低轨卫星分配计算资源,即总计算资源不得超过高轨卫星的计算能力.

3 低复杂度解决算法

由于任务卸载决策的组合性质,式(7)联合优化问题是一个混合整数非线性规划问题,寻找最优解需要指数时间复杂度.随着低轨卫星数量的增加,难以在有限的时间内给出最优解.本文的目标是设计一种低复杂度的解决方案,在达到具有竞争力性能的同时具备工程可用性.

3.1 问题分解

对于给定的卸载决策,无线资源包括带宽及发射功率的分配和计算资源的分配相互独立,因此是可以解耦的,可以通过分解成独立的问题解决.因此,解决式(7)问题分为以下几步:

a)给一个初始的卸载策略.

b)计算资源分配.

c)无线资源分配.

d)联合卸载和资源调度.

给定满足约束的可行任务卸载决策X,并且使用式(6)中的Ju的表达式,可以将联合优化问题重写为:

(16)

为了表达简洁,记:

(17)

记:

(18)

式(17)用于功率及带宽资源分配,式(18)用于计算资源分配.

3.2 无线资源分配

无线资源分配包括上行功率分配和子带个数分配,以式(17)作为目标函数,无线资源分配问题可以表述为:

(19)

通过拉格朗日乘子法,可得出关于bu,s和pu的非线性方程组,每个低轨卫星分配的子带个数满足式(12)约束,用式(20)确定bu,s的值.

(20)

由于每个低轨卫星传输功率互相独立,bu,s确定后利用二分法可求出pu的值.

3.3 计算资源分配

以式(18)为目标函数,解决计算资源分配问题,可以通过求解式(21)来解决:

(21)

式(21)的约束是凸集,计算Λ(X,F)关于fu,s的二阶导,式(21)中目标函数的黑塞矩阵是正定的,因此式(21)是凸优化问题,可使用Karush-Kuhn-Tucker(KKT)条件求解.

3.4 联合任务卸载和资源调度

从式(16)、式(17)和式(18)可以得到:

J*(X)=Γ(X,P*,B*)+Λ(X,F*)

(22)

其中P*、B*、F*为式(19)、式(20)和式(21)在给定卸载决策X下的解.由于给定决策X的约束和资源分配策略P、B、F的约束不耦合,因此解决问题(7),等效于解决如下的计算卸载问题:

(23)

其中Λ(X,F*)通过3.2节方法解决,Γ(X,P*,B*)通过3.3节方法解决.由于低轨卫星快速移动,不能随时和地面云计算中心直接通信.在本文的场景中,低轨卫星任务不管是卸载到高轨卫星上还是卸载到地面云中心,都需要将任务数据先发送到高轨卫星,因此,本文算法首先考虑低轨用户是否卸载,再考虑是卸载到高轨卫星,还是通过高轨卫星卸载到地面云计算中心.设连接到高轨卫星s的低轨卫星数量为N.提出如下卸载决策算法实现计算卸载调度.

任务卸载与资源分配联合优化算法:

输入:低轨卫星数量及计算能力,低轨卫星最大发射功率,高轨卫星计算能力,地面云中心为每用户分配算力,系统带宽及子带个数,各低轨卫星任务待处理数据及所需CPU周期数,低轨卫星及功耗时延权值,搜索范围R

输出:卸载决策X和资源分配策略P、B、F

1. 初始化各低轨卫星任务请求参数及系统参数

2. 对于每一个用户仅卸载自己按式(5)计算系统代价

3. 按系统代价从小到大对用户进行升序排序,设排序后的用户序号为1到N

4.Jold=Inf

5. foru=1∶N

计算卸载当前用户u后的系统代价Jnew

记录当前资源分配策略P、B、F

ifJnew

Jold=Jnew

xu,l=0,xu,s=1

pos=u

else

进入步骤6

end

end

6. 根据步骤5所得pos,按步骤3所得用户顺序,以[pos-R,pos+R]为搜索范围

7. fori=pos-R:pos-1

forj=pos:pos+R

第i个用户不卸载,第j个用户卸载,计算系统代价Jnew,

ifJnew

Jold=Jnew

更新卸载策略X为

xi,l=1,xi,s=0

xj,l=0,xj,s=1

更新资源分配策略P、B、F为计算Jnew时的分配策略

end

end

end

8. 对每个用户比较高轨计算代价Ju,s和Ju,e地面云计算的代价

ifJu,e

更新卸载策略X为:xu,l=0,xu,s=0,xu,e=1

end

9. 输出:X、P、B、F

计算卸载决策算法中一次系统开销计算的时间复杂度和用户数有关,因为卸载用户数最多为N,因此为一次系统开销计算复杂度为Ο(N),步骤2中为计算单独卸载一个用户的系统代价,因此步骤2计算复杂度Ο(N),步骤3排序算法的时间复杂度为Ο(Nlog2N),步骤5搜索pos的时间复杂度为Ο(N2),由于R为常数,算法步骤7的时间复杂度为Ο(N),步骤8的时间复杂度为Ο(N),因此本文计算卸载决策算法的时间复杂度为Ο(N2).

4 仿真结果与分析

4.1 参数设置

系统的仿真场景中低轨星座包括24个轨道面,每个轨道面内24颗卫星,共576颗低轨卫星,高轨卫星位于地球同步轨道,通过3颗高轨卫星形成对低轨卫星的覆盖,每颗低轨卫星同时只能接入一颗高轨卫星.其他具体仿真参数如表1所示.

仿真在处理器为英特尔i5-6500,内存为32.0GB,操作系统为Windows 7的计算机上进行,仿真工具为Matlab.

4.2 仿真分析

由于低轨卫星的业务可以是自身产生的也可以是接入其的各类终端产生的,在卫星网络中都可以认为是该卫星的业务,因此可以将各低轨卫星看做用户,根据用户延迟和能耗来评估系统开销.按表1的参数设置,进行1000次蒙特卡洛仿真,仿真中的任务数据量和任务计算量均以该数据为均值随机产生.

图2为不同用户数下系统开销与任务数据量的关系,图3为不同用户数下系统开销与任务计算量的关系,高轨卫星计算能力设置为20G cycles/s.通过仿真图可见系统开销随着用户数以及任务数据量的增加而增加,同时系统开销随着任务计算量的增加逐渐下降,表明任务卸载在任务计算量大时对系统开销的降低更为显著.

图2 系统开销与任务数据量的关系

图3 系统开销与任务计算量的关系

图4和图5分别为不同高轨卫星算力条件下系统开销与任务数据量和任务计算量之间的关系,高轨卫星可用算力分别设为10G cycles/s和20G cycles/s,用户数设为30.在任务计算量一定的情况下,随着任务数据量的增加系统开销将由任务数据量决定,从图4中可以看出,随着任务数据量的增加高轨卫星计算能力的对系统开销带来的差异逐渐缩小.如图5所示,在任务数据量一定的情况下,传输带来的系统开销固定,随着任务计算量需求的增加,任务卸载使系统开销逐渐降低.

图4 不同高轨卫星算力下系统开销与任务数据量的关系(任务计算量均值为13G Cycles)

图5 不同高轨卫星算力下系统开销与任务计算量的关系(任务数据量均值为130 Mbits)

图6(a)和图6(b)分别给出了平均卸载用户数与任务数据量及任务计算量的关系.如图6(a)所示随着任务数据量的增加,由于数据传输引起的系统开销将增加,不卸载在本地进行计算的用户数增多,卸载到地面云中心的用户数逐渐减少.如图6(b)所示,随着用户任务计算量需求的增加,卸载任务的用户数逐渐增加,而且由于地面云中心计算能力强,在计算量增加到一定程度时原来卸载到高轨卫星的用户任务也将卸载到地面执行.

图6 平均卸载用户数与任务数据量和任务计算量的关系

图7和图8分别为不同高轨卫星算力条件下,所提算法性能与文献[16]启发式任务卸载调度算法性能在不同用户数下的对比结果.

图7 与现有算法系统开销的比较

图8 与现有算法运算时间的比较

如图7所示,在同样的仿真条件下,相对于随机卸载和不卸载,本文算法与文献[16]算法均能降低系统开销,本文算法稍占优势.同时,如图8所示,本文算法由于采用局部搜索方法,将卸载决策的搜索限定在一定范围,该范围不随用户数的增加而增加,因此本文算法所需运行时间显著降低,并且随着用户数的增加,本文算法的运行时间优势更加明显.文献[16]启发式算法需要对用户遍历搜索计算,执行时间随着用户增加明显增加,而本文所提算法执行时间增长不明显,在用户数为50时,本算法平均运行时间是文献[16]启发式算法的15.66%.

5 结 论

卫星功能的日益强大,6G网络的卫星将具备边缘计算能力,针对卫星网络的卸载问题,本文提出一种计算资源、无线资源、功率资源及卸载决策的联合优化算法,对典型卫星边缘计算场景进行了仿真,本文算法得出的资源配置和任务部署策略,与不进行卸载相比可以显著减少系统延迟和能耗,提高系统整体效用,与已有算法相比可以降低资源分配和卸载决策算法的运行时间,更具有应用价值.