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

2023年第49卷第5期无线电通信技术883 doi:10.3969/j.issn.1003-3114.2023.05.013引用格式:赵天祺,赵洺月,师越,等.基于星地协同的低时延任务卸载算法J.无线电通信技术,2023,49(5):883-890.ZHAO Tianqi,ZHAO Mingyue,SHI Yue,et al.A Satellite-Ground Based Low-latency Task Offloading AlgorithmJ.Radio Communi-cations Technology,2023,49(5):883-890.基于星地协同的低时延任务卸载算法赵天祺,赵洺月,师 越,郑旷宇(北京航空航天大学 电子信息工程学院,北京 100191)摘 要:卫星在星地网络中计算能力和数量的快速提高,使天地协同任务卸载成为可能。天地协同卸载需要一个有效的任务调度算法,将任务分配到适合的服务器以提升任务卸载性能。然而,卫星高动态性带来的网络拓扑变化,以及终端任务子任务间的并行性导致服务器资源挤兑与依赖性引起的调度顺序要求,对任务协同卸载提出了新的挑战。修剪路径(PruningPath)算法实现了星地设备间任务的联合计算,并在满足子任务间依赖关系的前提下,将最小任务能耗问题转化为最短路径问题。实验结果表明,PruningPath 在降低任务响应延迟方面具有显著优势,可降低卸载时延达 31.9%。关键词:时延优化;卫星协同卸载;最短路径算法中图分类号:TN927 文献标志码:A 开放科学(资源服务)标识码(OSID):文章编号:1003-3114(2023)05-0883-08A Satellite-Ground Based Low-latency Task Offloading AlgorithmZHAO Tianqi,ZHAO Mingyue,SHI Yue,ZHENG Kuangyu(School of Electronic and Information Engineering,Beihang University,Beijing 100191,China)Abstract:The rapid improvement of the computing power and the number of satellites in the network makes satellite-ground collab-orative task offloading possible.It is necessary to have an effective task scheduling algorithm to allocate tasks to appropriate servers to improve task offloading performance.However,changes in network topology brought by high dynamics of satellite and the scheduling se-quence requirement caused by server resource crowding,and dependency caused by the parallelism between terminal task subtasks,pose new challenges to collaborative task offloading.PruningPath implements joint calculation of tasks between satellite and ground devices,and on the premise that the dependency between subtasks is satisfied,transforms the problem of minimum task energy consumption into the problem of the shortest path.Experimental results show that the algorithm has significant advantages in reducing task response latency,and can reduce the offloading latency by up to 31.9%.Keywords:latency optimization;satellite-ground collaborative;shortest path algorithm收稿日期:2023-05-230 引言近年来,OneWeb 和 StakLink 等卫星网络快速发展,为天地协同计算带来了机遇和挑战。随着卫星技术的不断发展,卫星将配备高速星间链路进行数据通信1和先进的机载计算系统2-3,使得数据传输可以实现低延迟和高吞吐量4-6。在偏远地区,难以连接云边缘网络的终端设备可以将任务卸载到卫星而不是云中心,显著提高通信质量,降低终端任务的处理时延。许多常见的终端任务,如无人驾驶、图像识别等,通常内部都具有一定的并行与依赖关系7-9。并且随着协同计算的发展,一个完整的任务也可以被分解为许多个并行子任务分别在不同设备上进行计算,如机器学习中将训练集分解为不同小训练集后分配到不同计算设备上10-11。边缘服务器分配多并行依赖任务的一个重要问题就是如何将任务卸载到合适的服务器,从而在保证任务依赖关系顺序的前提下,减少由于并行子任务抢占服务器引起的服务器拥塞,降低任务整体卸载时延12-13。然而,卫星的高动态性、有限的计算资源对依赖884 Radio Communications TechnologyVol.49 No.5 2023任务的卸载策略优化带来了很大的挑战。低地球轨道(Low Earth Orbit,LEO)具有机动性和灵活性,这使得卫星与地面设备之间的连接随着时间的推移而变化,从 而 影 响 了 终 端 能 否 成 功 向 卫 星 卸 载任务14-16。并且,在传统的依赖关系任务卸载策略中,主要通过对子任务进行优先度排序来确定子任务调度顺序17-19。这些方法在调度任务时主要考虑子任务间的依赖关系,而不直接考虑任务间的并行性,所以根据优先度调度的方法对于简单的串行依赖任务具有较好的性能表现,但对于具有并行结构的依赖性任务可能并不十分适合。然而,一个子任务往往与其他任务同时具有多个复杂的依赖与并行关系,或者说子任务间的并行结构与依赖关系往往并不独立,无法通过在原串行任务的基础上直接添加优化并行任务的算法来实现。因此,本文提出了修剪路径(PruningPath)算法,旨在建立一个星地协同任务卸载系统,在满足依赖任务约束的前提下将设备卸载问题转为最短路径问题,并通过修建设备保证算法的低复杂度。1 问题建模1.1 系统模型考虑在空地融合网络中构建一个协同计算框架,如图 1 所示。它由四部分组成:卫星、云、边缘和终端,设备总数为 m。卫星均匀分布在近地轨道上,具有通信和计算能力。认为云具有非常强的计算能力和多核计算能力,因此可以认为云上任务的计算时间为 0,且分配到云上的多个并行任务可以同时处理,不会产生等待能耗。相对而言,卫星、边缘和终端的计算能力较弱,同时只能处理一项任务,因此分配给边缘和终端的任务会产生计算延迟,且当多个并行任务分配给一个边缘或终端时,由于排队会产生等待延迟。在系统模型中,假设两个计算设备在一定距离内是可连接的,则二者可以相互传输数据。假设每个任务传输的大小有限,因此多个任务数据可以在同一信道中同时传输。整个系统协同计算步骤如下:当一个依赖任务到达时,系统将其视为一系列串联的子任务集;同时,在任务到达时判断卫星的可用性,并将终端设备、云和当前时刻可用的卫星构建为协同任务卸载系统;随后,系统将每个任务的卸载策略对应到一个路径节点上,计算相应的延迟并将其分配为路径权重,得到时延路径模型,从而将依赖任务卸载问题转化为最短路径问题。图 1 系统框架图Fig.1 System frame diagram1.2 依赖任务定义定义一个具有 m 个原子性子任务的依赖任务为 A:A=a1,a2,an。(1)每个子任务都有相应的任务大小 ai,size和输出ai,out:A=ai,size,ai,out,任务 A 的输入数据大小Ain为:Ain=ki=0ai,size,(2)式中:a1,a2,ak(1k)表示任务 A 中没有前置任务的子任务。类似地,任务 A 输出的数据数量 Aout为:Aout=ni=lai,out,(3)式中:al,al+1,an(ln)表示任务 A 中没有后置任务的子任务。1.3 时延模型1.3.1 计算延迟不同计算设备的计算资源是异构的,因此不同设备计算同一任务的成本不同。任务卸载的时延与任务本身计算量和设备计算能力有关。一个原子型子任务 ai在设备 o 上的计算时间为:tcomai,o=ai,sizefo,(4)式中:o 的取值为(0,m),用于表示不同的计算设备,fo表示该设备每秒可以计算的数据量。角标 o的定义在下文相同。2023年第49卷第5期无线电通信技术885 假设除云以外的计算设备每次只允许计算一个任务,则当设备 o 上已有任务时,任务 ai分配到该设备上等待计算的时间为:twaitai,o=No,sizefo,(5)式中:No,size为任务 ai到达时设备 o 上现有的任务数量大小。1.3.2 传输模型通过香农公式,可以得到设备 o1到设备 o2的传输速度为:r=Bo1,o2lb 1+Ptrano1,o22(),(6)式中:Ptrano1,o2表示从设备 o1 o2的传输功率。同理,2为设备 o1o2之间的噪声。任务 ai从设备 o1o2的传输时间为:ttranai,o1,o2=ai,sizer。(7)1.4 优化问题1.4.1 约束条件用 Xaij,k表示在时刻 k 时将任务 ai卸载到设备 j的决策。二进制决策变量 Xaij,k的范围约束表示为:Xaij,k=0,1,aiA,(8)如果 Xaij,k=1,则执行该调度。每个子任务只能卸载到一个设备上,表示为:mj=1Xaij,k=1,aiA,kT。(9)任务 A 中的子任务只有在前置任务完成后才能开始,表示为:TfaiTsav,aiA,avCai,(10)式中:Tfai表示子任务 ai的完成时间,Tsav表示子任务av的开始时间,Cai表示任务 ai的后置任务集。1.4.2 优化目标优化目标是减少整个依赖任务 A 的卸载延迟,可表示为:min(T)=min ni=1(tcomai+twaitai+ttranai)()。(11)依赖任务的卸载决策已被证明是 NP-hard20,无法在多项式时间内找到最优解。2 加权轮换最短路径算法2.1 模型概述本节提出了天地一体化协同计算背景下依赖任务卸载的加权轮换最短路径模型算法,该方法确定了依赖任务的调度方案,包括每个子任务的开始执行时间和卸载设备的决策。该算法的开发主要基于3 个原则:基于依赖任务子任务间的并行结构和依赖关系,对依赖任务的结构进行划分和处理,进行更精确的调度;考虑依赖任务中并行结构的争用影响;在保证调度算法性能的前提下,尽量降低调度算法的复杂度。2.2 任务结构划分由于节点路径模型的局限性,该模型只能对只有串行结构的依赖任务进行优化。为了将其扩展到具有并行结构的依赖任务,对依赖任务结构进行分解和重构,形成由仅由串行结构子任务集组成的新任务结构。分离重构原理如下:与节点 N 有并行关系的节点与节点 N 在同一层;每层节点数量尽量少,以降低算法复杂度。重组示意图如图 2 所示。(a)原任务结构(b)重组后的任务结构图 2 任务结构重组示意图Fig.2 Task structure reorganization diagram886 Radio Communications TechnologyVol.49 No.5 20232.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可以相同):t=tcomai,o2=ttranai,o1,o2=tcomai,o=ai,sizesfo2+ai,sizer=ai,sizefo2+ai,szieBo1,o2lb 1+Ptrano1,o22()=ai,size1fo2+1Bo1,o2lb 1+Ptrano1,o22()()=ai,sizek。(12)可知 k 是一个与任务无关的常数,只与设备自身参数有关。通过对子任务卸载时间的建模,发现任务的卸载时间模型是与任务大小成比例的一阶函数。也就是说,对于同一个任务来说,在前置任务的卸载设备确定且不考虑等待时延的情况下,不同设备卸载该任务的时延大小排序是确定的。即 k 值越低,对应设备的卸载时延越小。由此可以得到任务的最优卸载设备序列。但是,在实际卸载中不能直接使用该序列将任务分配给序列中的第一个即最优的设备进行卸载,原因有以下三点:多个前置任务有相同的后置任务:如果前置任务分配到不同的设备上,则从不同前置任务来看该后置任务的最优设备可能是不同的,显然卸载策略发生了冲突。如图 4 所示,其中子任务上的颜色代表将其卸载到对应颜色的设备上。图 4 多前置任务理论最佳设备产生冲突Fig.4 Multiple pre-task theory optimal device conflict 一个前置任务有多个并行的后置任务:当前置任务的卸载设备确定后,它所有后置任务的最优卸载设备是相同的。如果同时将多个后置任务分配给了同一个设备,将会产生额外的等待时延,如图 5所示。2023年第49卷第5期无线电通信技术887 图 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:wi,j=1k,(13)式中:k 为前文中的参数,为归一化参数。2.5.2 根据任务结构更新权重:(1)多前置任务的权重叠加当子任务具有多个前置任务时,不同的前置任务可能会在不同设备上执行,从而导致该子任务从不同的前置任务角度分析可能会具有多个最优设备列表。根据前置任务的大小比例,对每个设备在这些列表中的权重按正比取加权平均值,得到最终对该子任务来说每个设备的权重与最优列表,如图 6所示。(2)多后置任务的权重削减为解决多个并行子任务被分配到同一个设备导致计算设备拥塞的问题,将并行子任务中更大的子任务设置为更高的优先级,优先将其分配至更优的设备,避免被分配到性能较差设备上而产生延迟。用以下公式更新其他任务的对应设备权重:w=w-kipNsize+q1fo(),(14)式中:w 为初始权重,ki为各设备对高优先级子任务的优先级,Nsize为该设备上已分配的任务大小,fo为该设备的计算能力,p、q 为归一化参数。示意图如图 7 所示。图 6 多前置任务的权重叠加Fig.6 Weight superposition of multiple pre-tasks图 7 多后置任务的权重削减Fig.7 Weight reduction for multiple post tasks2.6 构建路径模型根据各任务设备权重列表进行路径节点筛选,888 Radio Communications TechnologyVol.49 No.5 2023为方便阐述,使用图 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)总时延的角度考虑,Pruning-Path 算法性能最优。Cloud 算法性能不佳的主要原因是终端与云之间距离过远产生的传输延迟,Local算法是由于只考虑局部最优解过于短视,从图 10(a)和图 10(b)联合分析可以看出 Greed 算法性能不佳的主要原因是算法运行时间过长。本文算法最多可以将卸载时延降低 31.9%。(a)不考虑算法运行时间只考虑卸载时延(b)考虑算法运行时间与卸载时间的总时延图 10 不同算法下的任务卸载时延Fig.10 Task offloading delay under different algorithms3.3.2 不同算法对卸载能耗的影响不同算法下的任务卸载能耗如图 11 所示,可以看出,本文算法相比局部最优算法具有较低的能耗,这是因为能耗大小也与任务计算时间与传输时间有关,当以时延为目标优化卸载方案时,在一定程度内也会优化任务的卸载能耗。图 11 中卸载到云方案的能耗较低,但卸载到云方案的时延较高,表明了云计算能力强,但偏远地区终端与云距离过长的特点。2023年第49卷第5期无线电通信技术889 图 11 不同算法下的任务卸载能耗Fig.11 Energy consumption of task offloading3.3.3 贪婪算法的局限性本节在路径模型中保留不同数量的最优设备来测量算法的性能。将保留设备数量设置为 1 时,该算法实际上就是 Local 算法。保留不同设备数量的任务卸载时延如图 12 所示。从图 12(a)可以看出,随着设备数量的增加,任务卸载本身的时延来越小。但如图 12(b)所示,当设备超过一定数量时,总时延反而呈上升趋势,这是由于路径算法的时间复杂度过高导致的。(a)不考虑算法运行时间只考虑卸载时延(b)考虑算法运行时间与卸载时间的总时延图 12 保留不同设备数量的任务卸载时延Fig.12 Different numbers of servers on latency influence 测量了不同保留设备数量下算法的运行时间,结果如表 1 所示,可以看出,当设备数量超过 3 时,算法运行时间已经与任务卸载时延的数量级相同,即算法本身将产生不可忽视的时延。所以在算法中使用更多数量的设备不一定能得到更好的性能,这进一步说明了在路径模型中删减设备的必要性。表 1 保留设备数量对算法运行时间的影响Tab.1 Different number of servers on latency influence单位:sNumber1234Time0.010.030.060.984 结论本文提出了一种用于天地协同计算中基于最短路径模型的卸载方法 PruningPath,利用任务结构重组与建模将依赖任务调度问题转化为最短路径问题,并采用权值轮换修剪设备降低算法复杂度。实验结果表明,该算法在将卸载时延最多降低 31.9%的同时,保持了较低的复杂度和运行时间。参 考 文 献1 LAI Z Q,LIU W S,WU Q,et al.SpaceRTC:Unleashing the Low-latency Potential of Mega-constellations for Real-time Communications C IEEE INFOCOM 2022.London:IEEE,2022:1339-1348.2 GRETOK E W,KAIN E T,GEORGE A D.Comparative Benchmarking Analysis of Next Generation Space Proces-sors C IEEE Aerospace Conference.Montana:IEEE,2019:1-16.3 PINGREEP J.Advancing NASA s On-board Processing Capabilities with Reconfigurable FPGA TechnologiesJ.Aerospace Technologies Advancements,2010,69:1-6.4 HANDLEY M.Delay is Not an Option:Low Latency Rou-ting in SpaceC17th ACM Workshop on Hot Topics in Networks.Redmond:ACM,2018:85-91.5 HANDLEY M.Using Ground Relays for Low-latency Wide-area Routing in Mega-constellationsCProceed-ings of the 18th ACM Workshop on Hot Topics in Net-works.New York:ACM,2019:125-132.6 LAI Z Q,LI H W,LI J H.StarPerf:Characterizing Net-work Performance for Emerging Mega-constellationsC International Conference on Network Protocols(ICNP).Madrid:IEEE,2020:1-11.7 MALEWICZ G,ROSENBERG A L,YURKEWYCH M.Toward a Theory for Scheduling Dags in Internet-based ComputingJ.IEEE Transactions on Computers,2006,55(6):757-768.890 Radio Communications TechnologyVol.49 No.5 20238 BOREGOWDA U,CHAKRAVARTHY V R.A Hybrid Task Scheduler for DAG Applications on a Cluster of Pro-cessors C International Conference on Advances in Computing and Communications.Kochi:IEEE,2014:143-146.9 SUI Z,LI J.An Auditable and Efficient Prepaid Scheme with Privacy Preservation in Smart GridsC Interna-tional Conference on Big Data and Smart Computing(Big-Comp).Jeju:IEEE,2023:318-319.10 KUCHIBHOTLA V,KUCHIBHOTLA S.A Parallel Imple-mentation of Q-learningCInternational Conference on Intelligent Sustainable Systems(ICISS).Thoothukudi:ACM,2020:455-458.11 LONG X,WU J G,WU Y L,et al.Task Merging and Scheduling for Parallel Deep Learning Applications in Mobile Edge ComputingCInternational Conference on Parallel and Distributed Computing,Applications,and Technologies.Shenzhen:PDCAT,2020:58-62.12 ZHANG W W,WEN Y G,WU D P.Energy-efficient Scheduling Policy for Collaborative Execution in Mobile Cloud ComputingCProceeding IEEE INFOCOM.Turin:IEEE,2013:190-194.13 YUAN Y C,LI X P.Scheduling Algorithm Based on the Cost Constraints on the Cloud J.Journal of Computer Research and Development,2009(2):194-201.14 BOEDHIHARTONO P,MARAL G.Evaluation of the Guaranteed Handover Algorithm in Satellite Constellations Requiring Mutual Visibility J.International Journal of Satellite Communications and Networking,2003,21(2):163-182.15 PAPAPETROU E,PAVLIDOU F N.QoS Handover Man-agement in LEO/MEO Satellite Systems J.Wireless Personal Communications,2003,24(2):189-204.16 WU Z F,HU G Y,SEYEDI Y,et al.A Simple Real-time Handover Management in the Mobile Satellite Communi-cation Networks C Asia-Pacific Network Operations and Management Symposium.Busan:IEEE,2015:175-179.17 SAHNI Y,CAO J,YANG L,et al.Multihop Offloading of Multiple DAG Tasks in Collaborative Edge ComputingJ.IEEE Internet of Things Journal,2021,8(6):4893-4905.18 SUNDAR S,LIANG B.Offloading Dependent Tasks with Communication Delay and Deadline Constraint C Proceeding IEEE INFOCOM 2018.Honolulu:IEEE,2018:37-45.19 FAN Y,ZHAI L,WANG H.Cost-efficient Dependent Task Offloading for MultiusersJ.IEEE Access,2019,7:115843-115856.20 GAREY M R,JOHNSON D S.Computers and Intracta-bility:A Guide to the Theory of NP-Completeness M.New York:W.H.Freeman&Co.,1979.作者简介:赵天祺女,(2000),硕士研究生。主要研究方向:云-边缘-移动端资源协同、空地一体化的高能效协同计算方法等。赵洺月女,(1998),硕士研究生。主要研究方向:高能效网络、边缘计算、无人机路径规划等。师 越女,(1999),硕士研究生。主要研究方向:云-边缘-移动端资源协同、星载边缘计算等。(通信作者)郑旷宇男,(1986),博士,副教授。主要研究方向:高能效通信计算机系统及网络。中国计算机协会(CCF)网络与数据通信专委会、体系结构专委会委员。