![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于星地协同的低时延任务卸载算法.pdf
《基于星地协同的低时延任务卸载算法.pdf》由会员分享,可在线阅读,更多相关《基于星地协同的低时延任务卸载算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、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.基于星地协同的低时延任务卸载算法赵天祺
2、,赵洺月,师 越,郑旷宇(北京航空航天大学 电子信息工程学院,北京 100191)摘 要:卫星在星地网络中计算能力和数量的快速提高,使天地协同任务卸载成为可能。天地协同卸载需要一个有效的任务调度算法,将任务分配到适合的服务器以提升任务卸载性能。然而,卫星高动态性带来的网络拓扑变化,以及终端任务子任务间的并行性导致服务器资源挤兑与依赖性引起的调度顺序要求,对任务协同卸载提出了新的挑战。修剪路径(PruningPath)算法实现了星地设备间任务的联合计算,并在满足子任务间依赖关系的前提下,将最小任务能耗问题转化为最短路径问题。实验结果表明,PruningPath 在降低任务响应延迟方面具有显著优势
3、,可降低卸载时延达 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,
4、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 pe
5、rformance.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 imp
6、lements 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 ad
7、vantages 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,使得数据传输可以实
8、现低延迟和高吞吐量4-6。在偏远地区,难以连接云边缘网络的终端设备可以将任务卸载到卫星而不是云中心,显著提高通信质量,降低终端任务的处理时延。许多常见的终端任务,如无人驾驶、图像识别等,通常内部都具有一定的并行与依赖关系7-9。并且随着协同计算的发展,一个完整的任务也可以被分解为许多个并行子任务分别在不同设备上进行计算,如机器学习中将训练集分解为不同小训练集后分配到不同计算设备上10-11。边缘服务器分配多并行依赖任务的一个重要问题就是如何将任务卸载到合适的服务器,从而在保证任务依赖关系顺序的前提下,减少由于并行子任务抢占服务器引起的服务器拥塞,降低任务整体卸载时延12-13。然而,卫星的高动
9、态性、有限的计算资源对依赖884 Radio Communications TechnologyVol.49 No.5 2023任务的卸载策略优化带来了很大的挑战。低地球轨道(Low Earth Orbit,LEO)具有机动性和灵活性,这使得卫星与地面设备之间的连接随着时间的推移而变化,从 而 影 响 了 终 端 能 否 成 功 向 卫 星 卸 载任务14-16。并且,在传统的依赖关系任务卸载策略中,主要通过对子任务进行优先度排序来确定子任务调度顺序17-19。这些方法在调度任务时主要考虑子任务间的依赖关系,而不直接考虑任务间的并行性,所以根据优先度调度的方法对于简单的串行依赖任务具有较好的性
10、能表现,但对于具有并行结构的依赖性任务可能并不十分适合。然而,一个子任务往往与其他任务同时具有多个复杂的依赖与并行关系,或者说子任务间的并行结构与依赖关系往往并不独立,无法通过在原串行任务的基础上直接添加优化并行任务的算法来实现。因此,本文提出了修剪路径(PruningPath)算法,旨在建立一个星地协同任务卸载系统,在满足依赖任务约束的前提下将设备卸载问题转为最短路径问题,并通过修建设备保证算法的低复杂度。1 问题建模1.1 系统模型考虑在空地融合网络中构建一个协同计算框架,如图 1 所示。它由四部分组成:卫星、云、边缘和终端,设备总数为 m。卫星均匀分布在近地轨道上,具有通信和计算能力。认
11、为云具有非常强的计算能力和多核计算能力,因此可以认为云上任务的计算时间为 0,且分配到云上的多个并行任务可以同时处理,不会产生等待能耗。相对而言,卫星、边缘和终端的计算能力较弱,同时只能处理一项任务,因此分配给边缘和终端的任务会产生计算延迟,且当多个并行任务分配给一个边缘或终端时,由于排队会产生等待延迟。在系统模型中,假设两个计算设备在一定距离内是可连接的,则二者可以相互传输数据。假设每个任务传输的大小有限,因此多个任务数据可以在同一信道中同时传输。整个系统协同计算步骤如下:当一个依赖任务到达时,系统将其视为一系列串联的子任务集;同时,在任务到达时判断卫星的可用性,并将终端设备、云和当前时刻可
12、用的卫星构建为协同任务卸载系统;随后,系统将每个任务的卸载策略对应到一个路径节点上,计算相应的延迟并将其分配为路径权重,得到时延路径模型,从而将依赖任务卸载问题转化为最短路径问题。图 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 中没有前置任务的子任务。类似地,任务
13、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 假设除云以外的计算设备每次只允许计算一个任务,则
14、当设备 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卸载到设
15、备 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)
16、依赖任务的卸载决策已被证明是 NP-hard20,无法在多项式时间内找到最优解。2 加权轮换最短路径算法2.1 模型概述本节提出了天地一体化协同计算背景下依赖任务卸载的加权轮换最短路径模型算法,该方法确定了依赖任务的调度方案,包括每个子任务的开始执行时间和卸载设备的决策。该算法的开发主要基于3 个原则:基于依赖任务子任务间的并行结构和依赖关系,对依赖任务的结构进行划分和处理,进行更精确的调度;考虑依赖任务中并行结构的争用影响;在保证调度算法性能的前提下,尽量降低调度算法的复杂度。2.2 任务结构划分由于节点路径模型的局限性,该模型只能对只有串行结构的依赖任务进行优化。为了将其扩展到具有并行结构
17、的依赖任务,对依赖任务结构进行分解和重构,形成由仅由串行结构子任务集组成的新任务结构。分离重构原理如下:与节点 N 有并行关系的节点与节点 N 在同一层;每层节点数量尽量少,以降低算法复杂度。重组示意图如图 2 所示。(a)原任务结构(b)重组后的任务结构图 2 任务结构重组示意图Fig.2 Task structure reorganization diagram886 Radio Communications TechnologyVol.49 No.5 20232.3 卸载策略路径模型为了便于解释,使用图 3(a)中的任务为例,并将计算设备(可以是云、边缘、卫星或终端)的数量设置为两个,命
18、名为 c0和 c1。该任务的卸载策略路径模型如图 3(b)所示。路径模型中的每一层表示对应的子任务集及其卸载策略。该模型分为节点和路径两个部分。(a)对任务结构进行重组(b)任务策略路径模型图 3 任务重构与策略路径模型构建Fig.3 Task reconstruction and strategy path model 节点:路径模型中每个节点都代表一个卸载策略。例如,第二行节点“S01”表示子任务 b 在 c0处卸载,子任务 c 在 c1处卸载。特别地,底部节点 0和顶部节点 1 是为方便计算而创建的虚拟节点。路径:节点下方的路径权值表示该节点策略对应的时延。利用最短路径算法计算模型中的最
19、短路径,理论上可以得到性能最优的调度方案。但该方法有一个明显的缺点,即算法复杂度过高,因此需要对算法复杂度进行优化。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 是一个与任
20、务无关的常数,只与设备自身参数有关。通过对子任务卸载时间的建模,发现任务的卸载时间模型是与任务大小成比例的一阶函数。也就是说,对于同一个任务来说,在前置任务的卸载设备确定且不考虑等待时延的情况下,不同设备卸载该任务的时延大小排序是确定的。即 k 值越低,对应设备的卸载时延越小。由此可以得到任务的最优卸载设备序列。但是,在实际卸载中不能直接使用该序列将任务分配给序列中的第一个即最优的设备进行卸载,原因有以下三点:多个前置任务有相同的后置任务:如果前置任务分配到不同的设备上,则从不同前置任务来看该后置任务的最优设备可能是不同的,显然卸载策略发生了冲突。如图 4 所示,其中子任务上的颜色代表将其卸载
21、到对应颜色的设备上。图 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 将每个子任务直接分配给其最
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 协同 低时延 任务 卸载 算法
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。