基于星地协同的低时延任务卸载算法

2023-10-11赵天祺赵洺月郑旷宇

无线电通信技术 2023年5期

赵天祺,赵洺月,师越,郑旷宇

(北京航空航天大学电子信息工程学院,北京 100191)

0 引言

近年来,OneWeb和StakLink等卫星网络快速发展,为天地协同计算带来了机遇和挑战。随着卫星技术的不断发展,卫星将配备高速星间链路进行数据通信[1]和先进的机载计算系统[2-3],使得数据传输可以实现低延迟和高吞吐量[4-6]。在偏远地区,难以连接云边缘网络的终端设备可以将任务卸载到卫星而不是云中心,显著提高通信质量,降低终端任务的处理时延。

许多常见的终端任务,如无人驾驶、图像识别等,通常内部都具有一定的并行与依赖关系[7-9]。并且随着协同计算的发展,一个完整的任务也可以被分解为许多个并行子任务分别在不同设备上进行计算,如机器学习中将训练集分解为不同小训练集后分配到不同计算设备上[10-11]。边缘服务器分配多并行依赖任务的一个重要问题就是如何将任务卸载到合适的服务器,从而在保证任务依赖关系顺序的前提下,减少由于并行子任务抢占服务器引起的服务器拥塞,降低任务整体卸载时延[12-13]。

然而,卫星的高动态性、有限的计算资源对依赖任务的卸载策略优化带来了很大的挑战。低地球轨道(Low Earth Orbit,LEO)具有机动性和灵活性,这使得卫星与地面设备之间的连接随着时间的推移而变化,从而影响了终端能否成功向卫星卸载任务[14-16]。

并且,在传统的依赖关系任务卸载策略中,主要通过对子任务进行优先度排序来确定子任务调度顺序[17-19]。这些方法在调度任务时主要考虑子任务间的依赖关系,而不直接考虑任务间的并行性,所以根据优先度调度的方法对于简单的串行依赖任务具有较好的性能表现,但对于具有并行结构的依赖性任务可能并不十分适合。然而,一个子任务往往与其他任务同时具有多个复杂的依赖与并行关系,或者说子任务间的并行结构与依赖关系往往并不独立,无法通过在原串行任务的基础上直接添加优化并行任务的算法来实现。

因此,本文提出了修剪路径(PruningPath)算法,旨在建立一个星地协同任务卸载系统,在满足依赖任务约束的前提下将设备卸载问题转为最短路径问题,并通过修建设备保证算法的低复杂度。

1 问题建模

1.1 系统模型

考虑在空地融合网络中构建一个协同计算框架,如图1所示。它由四部分组成:卫星、云、边缘和终端,设备总数为m。卫星均匀分布在近地轨道上,具有通信和计算能力。认为云具有非常强的计算能力和多核计算能力,因此可以认为云上任务的计算时间为0,且分配到云上的多个并行任务可以同时处理,不会产生等待能耗。相对而言,卫星、边缘和终端的计算能力较弱,同时只能处理一项任务,因此分配给边缘和终端的任务会产生计算延迟,且当多个并行任务分配给一个边缘或终端时,由于排队会产生等待延迟。在系统模型中,假设两个计算设备在一定距离内是可连接的,则二者可以相互传输数据。假设每个任务传输的大小有限,因此多个任务数据可以在同一信道中同时传输。

图1 系统框架图Fig.1 System frame diagram

整个系统协同计算步骤如下:当一个依赖任务到达时,系统将其视为一系列串联的子任务集;同时,在任务到达时判断卫星的可用性,并将终端设备、云和当前时刻可用的卫星构建为协同任务卸载系统;随后,系统将每个任务的卸载策略对应到一个路径节点上,计算相应的延迟并将其分配为路径权重,得到时延路径模型,从而将依赖任务卸载问题转化为最短路径问题。

1.2 依赖任务定义

定义一个具有m个原子性子任务的依赖任务为A:

A={a1,a2,…,an} 。

(1)

每个子任务都有相应的任务大小ai,size和输出ai,out:A={ai,size,ai,out},任务A的输入数据大小Ain为:

(2)

式中:a1,a2,…,ak(1≤k)表示任务A中没有前置任务的子任务。

类似地,任务A输出的数据数量Aout为:

(3)

式中:al,al+1,…,an(l≤n)表示任务A中没有后置任务的子任务。

1.3 时延模型

1.3.1 计算延迟

不同计算设备的计算资源是异构的,因此不同设备计算同一任务的成本不同。任务卸载的时延与任务本身计算量和设备计算能力有关。一个原子型子任务ai在设备o上的计算时间为:

(4)

式中:o的取值为(0,m),用于表示不同的计算设备,fo表示该设备每秒可以计算的数据量。角标o的定义在下文相同。

假设除云以外的计算设备每次只允许计算一个任务,则当设备o上已有任务时,任务ai分配到该设备上等待计算的时间为:

(5)

式中:No,size为任务ai到达时设备o上现有的任务数量大小。

1.3.2 传输模型

通过香农公式,可以得到设备o1到设备o2的传输速度为:

(6)

任务ai从设备o1～o2的传输时间为:

(7)

1.4 优化问题

1.4.1 约束条件

(8)

每个子任务只能卸载到一个设备上,表示为:

(9)

任务A中的子任务只有在前置任务完成后才能开始,表示为:

Tfai≤Tsav,∀ai∈A,av∈Cai,

(10)

式中:Tfai表示子任务ai的完成时间,Tsav表示子任务av的开始时间,Cai表示任务ai的后置任务集。

1.4.2 优化目标

优化目标是减少整个依赖任务A的卸载延迟,可表示为:

(11)

依赖任务的卸载决策已被证明是NP-hard[20],无法在多项式时间内找到最优解。

2 加权轮换最短路径算法

2.1 模型概述

本节提出了天地一体化协同计算背景下依赖任务卸载的加权轮换最短路径模型算法,该方法确定了依赖任务的调度方案,包括每个子任务的开始执行时间和卸载设备的决策。该算法的开发主要基于3个原则:

① 基于依赖任务子任务间的并行结构和依赖关系,对依赖任务的结构进行划分和处理,进行更精确的调度;

② 考虑依赖任务中并行结构的争用影响;

③ 在保证调度算法性能的前提下,尽量降低调度算法的复杂度。

2.2 任务结构划分

由于节点路径模型的局限性,该模型只能对只有串行结构的依赖任务进行优化。为了将其扩展到具有并行结构的依赖任务,对依赖任务结构进行分解和重构,形成由仅由串行结构子任务集组成的新任务结构。分离重构原理如下:

① 与节点N有并行关系的节点与节点N在同一层;

② 每层节点数量尽量少,以降低算法复杂度。

重组示意图如图2所示。

(a) 原任务结构

(b) 重组后的任务结构图2 任务结构重组示意图Fig.2 Task structure reorganization diagram

2.3 卸载策略路径模型

为了便于解释,使用图3(a)中的任务为例,并将计算设备(可以是云、边缘、卫星或终端)的数量设置为两个,命名为c0和c1。该任务的卸载策略路径模型如图3(b)所示。路径模型中的每一层表示对应的子任务集及其卸载策略。该模型分为节点和路径两个部分。

(a) 对任务结构进行重组

(b) 任务策略路径模型图3 任务重构与策略路径模型构建Fig.3 Task reconstruction and strategy path model

① 节点:路径模型中每个节点都代表一个卸载策略。例如,第二行节点“S01”表示子任务b在c0处卸载,子任务c在c1处卸载。特别地,底部节点0和顶部节点1是为方便计算而创建的虚拟节点。

② 路径:节点下方的路径权值表示该节点策略对应的时延。

利用最短路径算法计算模型中的最短路径,理论上可以得到性能最优的调度方案。但该方法有一个明显的缺点,即算法复杂度过高,因此需要对算法复杂度进行优化。

2.4 任务卸载最优设备序列

假设任务A中某个子任务ai的前置任务ap已经在设备o1上执行,则将ai卸载到设备o2的时延为(o1和o2可以相同):

(12)

可知k是一个与任务无关的常数,只与设备自身参数有关。

通过对子任务卸载时间的建模,发现任务的卸载时间模型是与任务大小成比例的一阶函数。也就是说,对于同一个任务来说,在前置任务的卸载设备确定且不考虑等待时延的情况下,不同设备卸载该任务的时延大小排序是确定的。即k值越低,对应设备的卸载时延越小。由此可以得到任务的最优卸载设备序列。

但是,在实际卸载中不能直接使用该序列将任务分配给序列中的第一个即最优的设备进行卸载,原因有以下三点:

① 多个前置任务有相同的后置任务:如果前置任务分配到不同的设备上,则从不同前置任务来看该后置任务的最优设备可能是不同的,显然卸载策略发生了冲突。如图4所示,其中子任务上的颜色代表将其卸载到对应颜色的设备上。

图4 多前置任务理论最佳设备产生冲突Fig.4 Multiple pre-task theory optimal device conflict

② 一个前置任务有多个并行的后置任务:当前置任务的卸载设备确定后,它所有后置任务的最优卸载设备是相同的。如果同时将多个后置任务分配给了同一个设备,将会产生额外的等待时延,如图5所示。

图5 并行任务分配到同一设备产生排队时延Fig.5 Parallel tasks assigned to the same device cause queuing delay

③ 将每个子任务直接分配给其最优设备只能得到每一层子任务的局部最优策略,而不能得到考虑整个依赖任务中所有子任务的全局最优策略。

为了解决上述问题,提出了加权轮换最短路径算法,通过给设备分配权重并根据卸载策略进行相应的权重增减,得到一个动态的最优设备排序列表。

2.5 设备权重计算

2.5.1 初始权重计算

当任务ai的前置任务ap卸载设备已确定时,可以得到ai在每个设备上卸载时延的大小。使用以下公式定义对任务ai来说不同设备j的初始权值wi,j:

(13)

式中:k为前文中的参数,α为归一化参数。

2.5.2 根据任务结构更新权重:

(1) 多前置任务的权重叠加

当子任务具有多个前置任务时,不同的前置任务可能会在不同设备上执行,从而导致该子任务从不同的前置任务角度分析可能会具有多个最优设备列表。根据前置任务的大小比例,对每个设备在这些列表中的权重按正比取加权平均值,得到最终对该子任务来说每个设备的权重与最优列表,如图6所示。

图6 多前置任务的权重叠加Fig.6 Weight superposition of multiple pre-tasks

(2) 多后置任务的权重削减

为解决多个并行子任务被分配到同一个设备导致计算设备拥塞的问题,将并行子任务中更大的子任务设置为更高的优先级,优先将其分配至更优的设备,避免被分配到性能较差设备上而产生延迟。用以下公式更新其他任务的对应设备权重:

(14)

式中:w为初始权重,ki为各设备对高优先级子任务的优先级,Nsize为该设备上已分配的任务大小,fo为该设备的计算能力,p、q为归一化参数。示意图如图7所示。

2.6 构建路径模型

根据各任务设备权重列表进行路径节点筛选,为方便阐述,使用图8中终端任务及4个设备[0,1,2,3]举例说明如何筛选设备。构建的路径模型如图9所示。

图8 终端任务及最优设备列表Fig.8 Terminal tasks and optimal devices list

图9 筛选设备后的最短路径模型Fig.9 Shortest path model after filtering device

利用最短路径算法获得模型中的最短路径,这就是任务卸载的最优策略。关于设备排序列表中保留的数量,如果太多则算法复杂度高,保留太少则性能不佳,在实验评估后选择保留3个。

3 仿真评估

3.1 仿真参数网络模型

生成一个空地网络,其中地面由一个云和3个边缘组成,卫星星座使用Starlink。

3.2 基准算法

本文使用的基准算法如下:

① 任务全部卸载到云(Cloud)执行:将终端生成的任务传输到云端,在云端计算后再传输回终端,调度顺序为任务释放时间和任务准备时间。

② 局部(Cloud)最优算法:将每个子任务直接调度到其最优服务器上进行计算,不考虑任务抢占和全局规划。

③ 贪婪(Greed):不筛选设备,使用所有设备建立最短路径模型,计算最优调度方案。

3.3 终端任务的仿真结果

在每次仿真中,每种算法执行10次,取其平均值作为每种算法的性能。

3.3.1 不同算法对卸载时延的影响

不同算法下的任务卸载时延如图10所示。从图10(a)可以看出,PruningPath可以明显降低卸载时延。而从图10(b)总时延的角度考虑,PruningPath算法性能最优。Cloud算法性能不佳的主要原因是终端与云之间距离过远产生的传输延迟,Local算法是由于只考虑局部最优解过于短视,从图10(a)和图10(b)联合分析可以看出Greed算法性能不佳的主要原因是算法运行时间过长。本文算法最多可以将卸载时延降低31.9%。

(a) 不考虑算法运行时间只考虑卸载时延

(b) 考虑算法运行时间与卸载时间的总时延图10 不同算法下的任务卸载时延Fig.10 Task offloading delay under different algorithms

3.3.2 不同算法对卸载能耗的影响

不同算法下的任务卸载能耗如图11所示,可以看出,本文算法相比局部最优算法具有较低的能耗,这是因为能耗大小也与任务计算时间与传输时间有关,当以时延为目标优化卸载方案时,在一定程度内也会优化任务的卸载能耗。图11中卸载到云方案的能耗较低,但卸载到云方案的时延较高,表明了云计算能力强,但偏远地区终端与云距离过长的特点。