面向空间分布式计算的动态任务分解及长时保障机制

doi:10.3778/j.issn.1673-9418.2308046

摘要/Abstract

摘要： 低轨卫星具有覆盖范围广、离地面近等优势，随着在轨处理能力的不断增强，未来将成为地面网络的重要补充。然而，随着用户对网络服务实时性的需求日益增长，如何在资源有限的条件下，基于低轨卫星为用户提供计算密集型服务，已成为一个急需解决的问题。尤其是在低轨卫星高速移动、星间链路动态切换的情况下，如何保证空间计算能力能持续稳定地驻留在用户区域并提供稳定可靠的服务，无疑是一项巨大的挑战。为了解决上述问题，提出一种动态任务分解聚合的分布式计算策略，通过卫星分布式计算解决单星算力不足的问题。在进行任务分解与调度时，充分考虑卫星网络的资源占用情况以及子任务之间的关联关系，对任务进行灵活的分解聚合。此外，为将低轨卫星算力驻留在用户区域，解决低轨卫星服务周期短的问题，研究并设计了一种长时保障机制。根据实时卫星网络拓扑及任务分解调度图，结合任务间的关联关系进行迁移决策，对卫星迁移过程进行模块化设计，根据实时网络状况调整迁移过程中的数据压缩率以及服务切换方式，降低迁移过程中服务的中断时间。仿真实验结果表明，提出的策略可保障长时分布式计算，能提供服务的平均时长延长了110%，用户满意度提高了约20%，迁移开销以及任务间的传输开销均降低了约15%。

关键词: 卫星迁移, 算力驻留, 分布式计算, 任务分解

Abstract: With improving satellite computing capabilities, low earth orbit (LEO) satellites can be a supplement of ground networks. However, resource-limited LEO satellites face challenges in providing computationally intensive services as demand for computing power increases. Rapid movement of LEO satellites also poses a challenge in maintaining computation in the required area. To address these problems, this paper proposes a distributed computing strategy based on dynamic task decomposition. When making decisions of task decomposition, the strategy considers the resource utilization of the satellite network and the relationship between sub-tasks, and flexibly decomposes and aggregates tasks. Additionally, it proposes a long-term computing guarantee mechanism to keep the computation within user regions. The mechanism makes decisions based on real-time network topology and task decomposition relationship. It modularizes satellite handover process, and adjusts compression rate and service switching methods based on network conditions to minimize interruption during handover. The experimental results indicate that the strategy ensures long-term distributed computing. The average service time has increased by 110%, user satisfaction has improved about 20%, and both handover cost and inter-task communication cost have decreased by 15%.

Key words: satellite handover, computation residency, distributed computing, task decomposition

锁啸天, 杨雅婷, 嵩天. 面向空间分布式计算的动态任务分解及长时保障机制[J]. 计算机科学与探索, 2024, 18(6): 1648-1660.

SUO Xiaotian, YANG Yating, SONG Tian. Dynamic Task Decomposition and Long-Term Guarantee Mechanism for Spatial Distributed Computing[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(6): 1648-1660.

参考文献

[1] MIAO J S, WANG P J, YIN H Q, et al. A multi-attribute decision handover scheme for LEO mobile satellite networks[C]//Proceedings of the 2019 IEEE 5th International Conference on Computer and Communications, Chengdu, Dec 6-9, 2019. Piscataway: IEEE, 2019.
[2] ZHANG Z J, ZHANG W Y, TSENG F H. Satellite mobile edge computing: improving QoS of high-speed satellite-terrestrial networks using edge computing techniques[J]. IEEE Network, 2019, 33(1): 70-76.
[3] LI Z, JIANG C X, LU J H, et al. Distributed service migration in satellite mobile edge computing[C]//Proceedings of the 2021 IEEE Global Communications Conference, Madrid, Dec 7-11, 2021. Piscataway: IEEE, 2022.
[4] MAI T L, YAO H P, LI F X, et al. Computing resource allocation in LEO satellites system: a Stackelberg game approach[C]//Proceedings of the 2019 15th International Wireless Communications & Mobile Computing Conference, Tangier, Jun 24-28, 2019. Piscataway: IEEE, 2019: 6492-6506.
[5] WANG Y P, QI X X, LIN X B, et al. Computing offloading-based task scheduling for space-based cloud-fog networks[C]//Proceedings of the 2021 2nd International Seminar on Artificial Intelligence, Networking and Information Technology, Shanghai, Oct 5-17, 2021. Piscataway: IEEE, 2022.
[6] ZHANG Z K, GU S Z, LI S M, et al. Multi-hop coflow routing for LEO distributed computation satellite networks[C]//Proceedings of the 2022 IEEE 96th Vehicular Technology Conference, London, Sep 26-29, 2022. Piscataway: IEEE, 2023.
[7] HAN J R, WANG H P, WU S J, et al. Task scheduling of high dynamic edge cluster in satellite edge computing[C]//Proceedings of the 2020 IEEE World Congress on Services, Beijing, Oct 18-23, 2020. Piscataway: IEEE, 2020.
[8] WANG H P, HAN J R, CAO S Z, et al. Computation offloading strategy of multi-satellite cooperative tasks based on genetic algorithm in satellite edge computing[C]//Proceedings of the 2021 International Conference on Space-Air-Ground Computing, Huizhou, Oct 23-25, 2021. Piscataway: IEEE, 2022.
[9] LIU ZG, ZHA X L, REN X B, el at. Research on handover strategy of LEO satellite network[C]//Proceedings of the 2021 2nd International Conference on Big Data and Informatization Education, Hangzhou, Apr 2-4, 2021. Piscataway: IEEE, 2021.
[10] WU Z F, JIN F L, LUO J X, et al. A graph-based satellite handover framework for LEO satellite communication networks[J]. IEEE Communications Letters, 2016: 1547-1550.
[11] ZHANG S B, LIU A J, HAN C, et al. A network-flows-based satellite handover strategy for LEO satellite networks[J]. IEEE Wireless Communications Letters, 2021, 10(12): 2669-2673.
[12] 底晓强, 于力伟, 刘旭, 等. 一种基于演化博弈的低轨卫星切换算法研究[J]. 南京大学学报(自然科学), 2018, 54(4): 855-862.
DI X Q, YU L W, LIU X, et al. Research on LEO satellite handover algorithm based on evolutionary game[J]. Journal of Nanjing University (Natural Sciences), 2018, 54(4): 855-862.
[13] DU J, JIANG C X, BENSLIMANE A, el at. SDN-based resource allocation in edge and cloud computing systems: an evolutionary stackelberg differential game approach[J]. IEEE/ACM Transactions on Networking, 2022, 30(4): 1613-1628.
[14] LI Z W,?XIE Z C,?LIANG X W, et al. Dynamic channel reservation strategy based on DQN algorithm for multi-service LEO satellite communication system[J]. IEEE Wireless Com-munications Letters, 2020, 10(4): 770-774.
[15] 王磊磊, 邓晓衡, 桂劲松, 等. 边缘计算中基于任务分解的任务分配算法[J].?湖南科技大学学报(自然科学版), 2022, 37(1): 76-84.
WANG L L, DENG X H, GUI J S, et al. Task scheduling algorithm based on task decomposition in edge computing[J]. Journal of Hunan University of Science and Technology (Natural Science Edition), 2022, 37(1): 76-84.
[16] AGOSTINO M, TOMMASO C. Dynamic partitioned scheduling of real-time DAG tasks on ARM big. LITTLE architectures[C]//Proceedings of the 29th International Conference on Real-Time Networks and Systems, Nantes, Apr 7-9, 2021. New York:?ACM, 2021: 1-11.
[17] 熊宇飞. 自适应的高性能容器在线迁移系统[D]. 武汉: 华中科技大学, 2022.
XIONG Y F. A self-adaptive and high-performance container live migration system[D]. Wuhan: Huazhong University of Science and Technology, 2022.
[18] 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.
[19] HAO Y Y, SONG Z Y, ZHENG Z, et al. Joint communication, computing, and caching resource allocation in LEO satellite[J]. IEEE Access, 2023, 11(10): 6708-6716.
[20] 肖毅. 面向边缘计算的容器系统及其迁移方法研究[D]. 武汉: 华中科技大学, 2022.
XIAO Y. Container system and its migration method research on edge computing-oriented[D]. Wuhan: Huazhong University of Science and Technology, 2022.