一种时延能耗感知的在轨边缘计算任务卸载调度方法

doi:10.11896/jsjkx.240100188

计算机科学 ›› 2024, Vol. 51 ›› Issue (6A): 240100188-9.doi: 10.11896/jsjkx.240100188

一种时延能耗感知的在轨边缘计算任务卸载调度方法

王众晓¹, 彭青蓝¹, 孙若骁¹, 徐锡峰², 郑万波³, 夏云霓²

1 河南大学人工智能学院郑州 475004
2 重庆大学计算机学院重庆 400044
3 昆明理工大学理学院昆明 650031

发布日期:2024-06-06
通讯作者: 彭青蓝(qinglan.peng@henu.edu.cn)
作者简介:(zhongxiaoWang@henu.edu.cn)
基金资助:
国家自然科学基金(62172062,62162036);河南省重点研发专项(231111211900);河南省自然科学基金青年项目(242300421700);河南省高等学校重点科研项目(24A520005)

Delay and Energy-aware Task Offloading Approach for Orbit Edge Computing

WANG Zhongxiao¹, PENG Qinglan¹, SUN Ruoxiao¹, XU Xifeng², ZHENG Wanbo³, XIA Yunni²

1 College of Artificial Intelligence,Henan University,Zhengzhou 475004,China
2 College of Computer Science,Chongqing University,Chongqing 400044,China
3 Data Science Research Center,Kunming University of Science and Technology,Kunming 650031,China

Published:2024-06-06
About author:WANG Zhongxiao,born in 2003,His main research interests include orbit edge computing and computation task offloading strategy.
PENG Qinglan,born in 1994,Ph.D,lecturer,master supervisor.His main research interests include edge computing,service computing,and cloud computing.
Supported by:
National Natural Science Foundation of China(62172062,62162036),Key Research and Development Project of Henan Province(231111211900),Young Scientists Fund of the Natural Science Foundation of Henan Province(242300421700) and Key Scientific Research Projects of Colleges and Universities in Henan Province(24A520005).

摘要/Abstract

摘要： 全球智能设备的迅速增长引发了对计算资源下沉至边缘的巨大需求,催生了边缘计算范式的出现。同时,计算资源稀缺的偏远地区用户对算力的需求又推动了在轨边缘计算(Orbit Edge Computing,OEC)概念的提出和发展。在OEC场景下,偏远地区用户可以通过星地和星间通信链路将计算任务卸载至部署在低轨卫星上的边缘服务器,以此突破地面计算通信基础设施的限制,为偏远地区的用户提供低时延和高可靠的服务。然而,OEC场景中卫星算力受有限载荷和太阳能转化效率约束,同时还存在低轨卫星绕地导致的高度动态的星地连接造成的可用时隙有限的限制,面临着计算资源稀缺和可用通信时间有限所带来的挑战。因此,需要高质高效的任务卸载决策算法来保证OEC系统的高效运行。然而,目前在OEC场景下任务卸载方法大多在处理任务时无法兼顾计算任务卸载时延与能耗,此外传统方法还缺少对任务多样性的考量。针对上述问题,提出了一种基于自适应大邻域搜索的在轨边缘计算任务卸载方法OEC-ALNS,该方法以任务类型加权的任务处理成本为优化目标,并针对性地提出了基于最小化时延的破坏算子和修复算子来进一步提升搜索效率和卸载调度质量。基于Walker Delta低轨卫星星座和真实计算任务数据的实验结果表明,与传统的OEC-TA(OEC Task Allocation)方法相比,提出的OEC-ALNS方法在多个任务集异构的OEC场景中最多能够减少42.22%的加权任务处理成本和降低42.46%的平均时延。

关键词: 在轨边缘计算, 低轨卫星星座, 计算任务卸载, 自适应大邻域搜索

Abstract: The rapid growth of smart devices around the world has created a huge demand for computing resources to sink to the edge,giving rise to the emergence of the edge computing paradigm.At the same time,the demand for computing power in remote areas where computing resources are scarce has driven the concept of orbit edge computing(OEC).In the OEC scenario,users in remote areas can offload computing tasks to edge servers deployed on LEO satellites for processing and execution through the communication link between ground station and satellite and the communication link between satellites in constellation,so as to provide low-latency and high-reliability services for users in remote areas by utilizing satellite computing resources.However,the satellite arithmetic in the OEC scenario is constrained by the limited load and solar energy conversion efficiency,and there is also the limitation of limited available time slots due to highly dynamic satellite-ground connection caused by LEO satellites circling around the earth,which is faced with the challenge of the scarcity of computational resources and the limited available communication latency.Therefore,excellent task offloading decision algorithms are needed to ensure the efficient operation of OEC systems.However,most of the current task offloading approaches for OEC scenario are unable to take into account the delay cost and energy cost when processing tasks,and the traditional approaches also lack the consideration of task diversity.To address the above problems,an adaptive large neighborhood search-based task offloading method for orbit edge computing,OEC-ALNS,is proposed,which takes the task processing cost weighted by task type as the optimization objective,and consists of destruction and repair operators based on the minimization of latency.Experimental results based on Walker Delta LEO satellite constellation and real computing task data show that,compared with the traditional OEC-TA(OEC task allocation)approach,the proposed OEC-ALNS approach could achieve at most 42.22% reduction on the weighted task processing cost and most 42.46% reduction of the average latency cost in OEC scenarios with heterogeneous multiple task sets.

Key words: Orbit edge computing, Low-orbit satellite constellation, Computation task offloading, Adaptive large neighborhood search

中图分类号:

TP311

王众晓, 彭青蓝, 孙若骁, 徐锡峰, 郑万波, 夏云霓. 一种时延能耗感知的在轨边缘计算任务卸载调度方法[J]. 计算机科学, 2024, 51(6A): 240100188-9. https://doi.org/10.11896/jsjkx.240100188

WANG Zhongxiao, PENG Qinglan, SUN Ruoxiao, XU Xifeng, ZHENG Wanbo, XIA Yunni. Delay and Energy-aware Task Offloading Approach for Orbit Edge Computing[J]. Computer Science, 2024, 51(6A): 240100188-9. https://doi.org/10.11896/jsjkx.240100188

参考文献

[1]CHEN W Y,CHOU P Y,WANG C Y,et al.Dual Pricing Optimization for Live Video Streaming in Mobile Edge Computing With Joint User Association and Resource Management[J].IEEE Transactions on Mobile Computing,2023,22(2):858-873.
[2]DAI X X,XIAO Z,JIANG H B,et al.Task Co-Offloading forD2D-Assisted Mobile Edge Computing in Industrial Internet of Things[J].IEEE Transactions on Industrial Informatics,2023,19(1):480-490.
[3]ZHU M Y,LI J.Blockchain based on Reliable Task Offloading Strategy for Edge Computing in Smart Home[C]//2023 8th International Conference on Intelligent Computing and Signal Processing.IEEE,2023:1364-1368.
[4]XIA X Y,CHEN F F,HE Q,et al.OL-MEDC:An Online Approach for Cost-Effective Data Caching in Mobile Edge Computing Systems[J].IEEE Transactions on Mobile Computing,2023,22(3):1646-1658.
[5]PENG Q L,WU C R,XIA Y N,et al.DoSRA:A Decentralized Approach to Online Edge Task Scheduling and Resource Allocation[J].IEEE Internet of Things Journal,2022,9(6):4677-4692.
[6]KIM J,HAM D,KIM T,et al.Survey on Satellite-Mobile Code Offloading[C]//2022 13th International Conference on Information and Communication Technology Convergence.IEEE,2022:921-923.
[7]FANG X R,FENG W,WEI T,et al.5G Embraces Satellites for 6G Ubiquitous IoT:Basic Models for Integrated Satellite Terrestrial Networks[J].IEEE Internet of Things Journal,2021,8(18):14399-14417.
[8]HAN Z Z,XU C,LIU K,et al.A Novel Mobile Core Network Architecture for Satellite-Terrestrial Integrated Network[C]//2021 IEEE Global Communications Conference.IEEE,2021:1-6.
[9]LI X T,XU S,ZHAO Z P,et al.A Survey on Computing Offloading in Satellite-Terrestrial Integrated Edge Computing Networks[C]//2023 15th International Conference on Communication Software and Networks.IEEE,2023:172-182.
[10]DENBY B,LUCIA B.Orbital Edge Computing:NanosatelliteConstellations as a New Class of Computer System[C]//Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems.Association for Computing Machinery,2020:939-954.
[11]DENBY B,LUCIA B.Orbital Edge Computing:Machine Infe-rence in Space[J].IEEE Computer Architecture Letters,2019,18(1):59-62.
[12]LI CC,ZHANG Y S,HAO X K,et al.Jointly optimized request dispatching and service placement for MEC in LEO network[J].China Communications,2020,17(8):199-208.
[13]WU J,JIA M,GUO Q,et al.Joint Optimization ComputationOffloading and Resource Allocation for LEO Satellite with Edge Computing[C]//2023 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting.IEEE,2023:1-5.
[14]CHAI F R,ZHANG Q,YAO H P,et al.Joint Multi-Task Offloading and Resource Allocation for Mobile Edge Computing Systems in Satellite IoT[J].IEEE Transactions on Vehicular Technology,2023,72(6):7783-7795.
[15]CAO X L,YANG B,SHEN Y L,et al.Edge-Assisted Multi-Layer Offloading Optimization of LEO Satellite-Terrestrial Integrated Networks[J].IEEE Journal on Selected Areas in Communications,2023,41(2):381-398.
[16]TANG Q Q,FEI Z S,LI B,et al.Computation Offloading in LEO Satellite Networks With Hybrid Cloud and Edge Computing[J].IEEE Internet of Things Journal,2021,8(11):9164-9176.
[17]CUI G F,LONG Y T,XU L X,et al.Joint Offloading and Resource Allocation for Satellite Assisted Vehicle-to-Vehicle Communication[J].IEEE Systems Journal,2021,15(3):3958-3969.
[18]MEI C L,GAO C,XING Y J,et al.An Energy Consumption Minimization Optimization Scheme for HAP-Satellites Edge Computing[C]//2022 IEEE 22nd International Conference on Communication Technology.IEEE,2022:857-862.
[19]SONG Z Y,HAO Y Y,LIU Y W,et al.Energy-Efficient Multiaccess Edge Computing for Terrestrial-Satellite Internet of Things[J].IEEE Internet of Things Journal,2021,8(18):14202-14218.
[20]PFANDZELTER T,BERMBACH D.Celestial:Virtual Software System Testbeds for the LEO Edge[C]//Proceedings of the 23rd ACM/IFIP International Middleware Conference.Association for Computing Machinery,2022:69-81.
[21]QI X X,ZHANG B,QIU Z L,et al.Using Inter-Mesh Links to Reduce End-to-End Delay in Walker Delta Constellations[J].IEEE Communications Letters,2021,25(9):3070-3074.
[23]ZHANG Y R,CHEN C,LIU L,et al.Aerial Edge Computing on Orbit:A Task Offloading and Allocation Scheme[J].IEEE Transactions on Network Science and Engineering,2023,10(1):275-285.
[24]DAI X,CHEN X,JIAO L B,et al.Priority-Aware Task Offloa-ding and Resource Allocation in Satellite and HAP Assisted Edge-Cloud Collaborative Networks[C]//2023 15th International Conference on Communication Software and Networks.IEEE,2023:166-171.
[25]DONG Q,XU X D,HAN S J,et al.DDPG-Based Task Offlo-ading in Satellite-Terrestrial Collaborative Edge Computing Networks[C]//2023 IEEE International Conference on Communications Workshops.IEEE,2023:1541-1546.
[26]EI N N,YOON J S,HONG C S.Energy-Aware Task Offloading and Resource Allocation in Space-Aerial-Integrated MEC System[C]//2022 23rd Asia-Pacific Network Operations and Management Symposium.IEEE,2022:1-6.
[27]CHEN B C,LI N,LI Y,et al.Energy Efficient Hybrid Offloa-ding in Space-Air-Ground Integrated Networks[C]//2022 IEEE Wireless Communications and Networking Conference.IEEE,2022:1319-1324.
[28]CHU W B,JIA X M,YU Z,et al.Joint Service Caching,Resource Allocation and Task Offloading for MEC-based Networks:A Multi-Layer Optimization Approach[J].IEEE Transactions on Mobile Computing,2024,23(4):2958-2975.
[29]WANG S H,LIU Y,HUANG X Y,et al.Adaptive large neighborhood search for the dynamic vehicle routing problem with electric vehicles[C]//2023 35th Chinese Control and Decision Conference.IEEE,2023:3776-3780.
[30]CHE A D,WANG W J,MU X H,et al.Tabu-Based Adaptive Large Neighborhood Search for Multi-Depot Petrol Station Replenishment With Open Inter-Depot Routes[J].IEEE Transactions on Intelligent Transportation Systems,2023,24(1):316-330.
[31]HUANG K Y,MA J B,LIU X Y.Research on Vehicle Route Planning with Capacity Limitation Based on Adaptive Large-scale Neighborhood Search Algorithm[C]//2021 6th International Symposium on Computer and Information Processing Technology.IEEE,2021:6-10.
[32]HAMDI M,HAMED A B,YUAN D,et al.Energy-EfficientJoint Task Assignment and Power Control in Energy-Harvesting D2D Offloading Communications[J].IEEE Internet of Things Journal,2022,9(8):6018-6031.
[33]LI Q Y.Research on Key Technologies for Joint Optimization of Access and Backhaul in 6G Dense Network[D].Nanjing:Nanjing University of Posts and Telecommunications,2023.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种时延能耗感知的在轨边缘计算任务卸载调度方法

Delay and Energy-aware Task Offloading Approach for Orbit Edge Computing

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0