Task Scheduling Algorithm Based on Dynamic Potential Game for Edge Compute First Networking

ZHANG Jing; GUAN Jian-feng; LIU Ke-xian; SHEN Ao

doi:10.12263/DZXB.20240401

您当前的位置：

首页 >

文章列表页 >

Task Scheduling Algorithm Based on Dynamic Potential Game for Edge Compute First Networking

PAPERS | 更新时间：2025-12-11

- Task Scheduling Algorithm Based on Dynamic Potential Game for Edge Compute First Networking
- ACTA ELECTRONICA SINICA Vol. 53, Issue 1, Pages: 221-237(2025)
- 作者机构：
  
  北京邮电大学网络与交换技术全国重点实验室，北京 100876
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62394323)
- DOI：10.12263/DZXB.20240401
  CLC： TP393.1;
- Received：06 May 2024，
  
  Revised：2024-09-26，
  
  Published：25 January 2025
- 稿件说明：
移动端阅览
张晶, 关建峰, 刘科显, 等. 基于动态势博弈的边缘算力网络任务调度算法[J]. 电子学报, 2025, 53(01): 221-237.

ZHANG Jing, GUAN Jian-feng, LIU Ke-xian, et al. Task Scheduling Algorithm Based on Dynamic Potential Game for Edge Compute First Networking[J]. Acta Electronica Sinica, 2025, 53(01): 221-237.
张晶, 关建峰, 刘科显, 等. 基于动态势博弈的边缘算力网络任务调度算法[J]. 电子学报, 2025, 53(01): 221-237. DOI：10.12263/DZXB.20240401

ZHANG Jing, GUAN Jian-feng, LIU Ke-xian, et al. Task Scheduling Algorithm Based on Dynamic Potential Game for Edge Compute First Networking[J]. Acta Electronica Sinica, 2025, 53(01): 221-237. DOI：10.12263/DZXB.20240401

摘要

随着个性化、多样化的新型网络应用和业务的不断发展和成熟，数据量和计算需求呈指数型增长趋势，而云计算、边缘计算、智能终端设备等也得到了快速发展，计算资源呈现出泛在、分散部署的趋势，如何高效协同地利用这些泛在计算资源以满足日益增长的计算需求，成为当前网络领域研究的一项重要新课题.边缘算力网络集中在网络边缘，在靠近数据源的位置，将异构的计算资源和网络资源结合起来，通过资源感知、服务定位、任务调度等来提高资源利用率和任务执行效率，在保持低延迟和低成本的同时，实现对分布式计算资源的最优配置.边缘算力网络通常采用分布式的任务调度方式，各节点基于局部范围内的信息进行本地决策，具有决策时间短、能有效缓解中心控制器计算和通信压力等优势.然而，信息的局部、不对称特征限制了分布式任务调度的全局优化性能，导致计算任务的覆盖率无法得到保障.本文以边缘算力网络分布式任务调度为核心，依托博弈理论及多目标优化方法，设计基于最佳动态响应的分布式任务调度算法，引入两跳范围内的通信和共识消除机制，在最小化交互开销和决策延迟的情况下，最大限度地提升了分布式任务调度的任务覆盖率，实现向纳什均衡点的收敛；将两跳范围内的共识消除作为优化目标之一，建立基于分布式决策优化性和一致性双目标的动态势博弈模型，通过理论推导证明了局部决策和全局决策的渐进等价性，为纳什均衡的存在性及分布式任务调度的收敛性提供了有效的理论依据；最后，通过仿真与经典分布式决策算法和全局最优解进行了对比，验证了所提出算法的有效性和优化收益.

Abstract

With the continuous development and maturity of personalized and diversified new network applications and services

the amount of data and computing demands are experiencing an exponential growth trend. Cloud computing

edge computing and intelligent terminal devices have been developed rapidly

and computing resources have shown a trend of ubiquitous and decentralized deployment. How to use these ubiquitous computing resources efficiently and collaboratively to meet the increasing computational demands has become an important new topic in the current network field. Edge compute first network focus on the edge of the network

near the location of the data source

combining heterogeneous computing resources and network resources to improve resource utilization and task execution efficiency through resource awareness

service positioning

task scheduling

maintaining low latency and low cost and realizing the optimal configuration of distributed computing resources at the same time. Edge compute first network usually adopts the distributed task scheduling mode. In distributed task scheduling

each node makes local decision based on local information

which has the advantages of short decision time and effective relief of calculation and communication pressure of central controller. However

the local and asymmetric nature of information limits the global optimization performance of distributed scheduling

resulting in an inadequate task coverage. This paper focuses on distributed task scheduling in edge compute first network. With the support of game theory and multi-objective optimization methods

a distributed task scheduling algorithm based on optimal dynamic response is designed

which introduces communication and consensus elimination mechanisms within a two-hop range. Under the conditions of minimizing interaction costs and scheduling delays

it maximizes the task coverage of distributed scheduling and achieves convergence to the Nash equilibrium point. A dynamic game model based on the optimization and consistency of distributed decision-making

with consensus elimination within a two-hop range as one of the optimization objectives

is established. The theoretical derivation demonstrates the asymptotic equivalence between local decisions and global decisions

providing an effective theoretical basis for the existence of Nash equilibria and the convergence of distributed scheduling. Finally

the effectiveness and optimization benefits of the proposed algorithm are validated through simulations and comparisons with a classical distributed decision-making algorithm and global optimal solutions.

关键词

Keywords

references

中国联通算力网络产业技术联盟 . 异构算力统一标识与服务白皮书 [R ] . 北京 , 2021 .

China Unicom Arithmetic Network Industry and Technology Alliance . White Paper on Unified Identification and Service of Heterogeneous Computing Power [R ] . Beijing , 2021 . (in Chinese)

张宏科 , 于成晓 , 权伟 , 等 . 融算网络体系基础研究 [J ] . 电子学报 , 2022 , 50 ( 12 ): 2928 - 2934 .

ZHANG H K , YU C X , QUAN W , et al . Fundamental research on computing integration networking [J ] . Acta Electronica Sinica , 2022 , 50 ( 12 ): 2928 - 2934 . (in Chinese)

贾庆民 , 丁瑞 , 刘辉 , 等 . 算力网络研究进展综述 [J ] . 网络与信息安全学报 , 2021 , 7 ( 5 ): 1 - 12 .

JIA Q M , DING R , LIU H , et al . Survey on research progress for compute first networking [J ] . Chinese Journal of Network and Information Security , 2021 , 7 ( 5 ): 1 - 12 . (in Chinese)

CAO Y C , YU W W , REN W , et al . An overview of recent progress in the study of distributed multi-agent coordination [J ] . IEEE Transactions on Industrial Informatics , 2013 , 9 ( 1 ): 427 - 438 .

CHOPRA S , NOTARSTEFANO G , RICE M , et al . A distributed version of the hungarian method for multirobot assignment [J ] . IEEE Transactions on Robotics , 2017 , 33 ( 4 ): 932 - 947 .

BALINSKI M L . Signature methods for the assignment problem [J ] . Operations Research , 1985 , 33 ( 3 ): 527 - 536 .

BERTSEKAS D P . A new algorithm for the assignment problem [J ] . Mathematical Programming , 1981 , 21 ( 1 ): 152 - 171 .

DEB K , PRATAP A , AGARWAL S , et al . A fast and elitist multiobjective genetic algorithm: NSGA-II [J ] . IEEE Transactions on Evolutionary Computation , 2002 , 6 ( 2 ): 182 - 197 .

CHOI H L , BRUNET L , HOW J P . Consensus-based decentralized auctions for robust task allocation [J ] . IEEE Transactions on Robotics , 2009 , 25 ( 4 ): 912 - 926 .

SMOLKA S , WIßENBERG L , MANN Z Á . EdgeDecAp: An auction-based decentralized algorithm for optimizing application placement in edge computing [J ] . Journal of Parallel and Distributed Computing , 2023 , 175 : 22 - 36 .

MOHAMMADI AMIRI M , GÜNDÜZ D . Computation scheduling for distributed machine learning with straggling workers [J ] . IEEE Transactions on Signal Processing , 2019 , 67 ( 24 ): 6270 - 6284 .

YANG C S , HUANG-FU C C , FU I K . Carbon-neutralized task scheduling for green computing networks [C ] // GLOBECOM 2022 - 2022 IEEE Global Communications Conference . Piscataway : IEEE , 2022 : 4824 - 4829 .

YANG C S , AVESTIMEHR A S , PEDARSANI R . Communication-aware scheduling of serial tasks for dispersed computing [C ] // 2018 IEEE International Symposium on Information Theory (ISIT) . Piscataway : IEEE , 2018 : 1226 - 1230 .

JIN A L , SONG W , WANG P , et al . Auction mechanisms toward efficient resource sharing for cloudlets in mobile cloud computing [J ] . IEEE Transactions on Services Computing , 2016 , 9 ( 6 ): 895 - 909 .

MA L B , WANG X Y , WANG X W , et al . TCDA: Truthful combinatorial double auctions for mobile edge computing in industrial Internet of Things [J ] . IEEE Transactions on Mobile Computing , 2022 , 21 ( 11 ): 4125 - 4138 .

DIAMANTI M , PAPAVASSILIOU S . Trading in collaborative mobile edge computing networks: A contract theory-based auction model [C ] // 2022 18th International Conference on Distributed Computing in Sensor Systems (DCOSS) . Piscataway : IEEE , 2022 : 387 - 393 .

DIONNE D , RABBATH C A . Multi-UAV decentralized task allocation with intermittent communications: The DTC algorithm [C ] // 2007 American Control Conference . Piscataway : IEEE , 2007 : 5406 - 5411 .

CHAKRAA H , GUÉRIN F , LECLERCQ E , et al . Optimization techniques for multi-robot task allocation problems: review on the state-of-the-art [J ] . Robotics and Autonomous Systems , 2023 , 168 : 104492 .

QUINTON F , GRAND C , LESIRE C . Market approaches to the multi-robot task allocation problem: A survey [J ] . Journal of Intelligent & Robotic Systems , 2023 , 107 : 29 .

LUO L Z , CHAKRABORTY N , SYCARA K . Distributed algorithms for multirobot task assignment with task deadline constraints [J ] . IEEE Transactions on Automation Science and Engineering , 2015 , 12 ( 3 ): 876 - 888 .

ZHAO W Q , MENG Q G , CHUNG P W H . A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario [J ] . IEEE Transactions on Cybernetics , 2016 , 46 ( 4 ): 902 - 915 .

WHITBROOK A , MENG Q G , CHUNG P W H . Reliable, distributed scheduling and rescheduling for time-critical, multiagent systems [J ] . IEEE Transactions on Automation Science and Engineering , 2018 , 15 ( 2 ): 732 - 747 .

QU G N , BROWN D , LI N . Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions [J ] . Automatica , 2019 , 105 : 206 - 215 .

LI T , SHIN H S , TSOURDOS A . Threshold greedy based task allocation for multiple robot operations [EB/OL ] . ( 2019-09-03 )[ 2024-01-26 ] . https://arxiv.org/abs/1909.01239v1 https://arxiv.org/abs/1909.01239v1 .

WANG J S , WANG J , CHE H J . Task assignment for multivehicle systems based on collaborative neurodynamic optimization [J ] . IEEE Transactions on Neural Networks and Learning Systems , 2020 , 31 ( 4 ): 1145 - 1154 .

FU X W , FENG P , GAO X G . Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism [J ] . IEEE Access , 2019 , 7 : 41090 - 41100 .

WANG X M , SUI Y , WANG J P , et al . A distributed truthful auction mechanism for task allocation in mobile cloud computing [J ] . IEEE Transactions on Services Computing , 2021 , 14 ( 3 ): 628 - 638 .

TANG Q Q , XIE R C , YU F R , et al . Distributed task scheduling in serverless edge computing networks for the internet of things: A learning approach [J ] . IEEE Internet of Things Journal , 2022 , 9 ( 20 ): 19634 - 19648 .

BERALDI R , ALNUWEIRI H . Distributed fair randomized (DFR): A resource sharing protocol for fog providers [C ] // 2019 Fourth International Conference on Fog and Mobile Edge Computing (FMEC) . Piscataway : IEEE , 2019 : 29 - 36 .

CHEN L X , SHEN C , ZHOU P , et al . Collaborative service placement for edge computing in dense small cell networks [J ] . IEEE Transactions on Mobile Computing , 2021 , 20 ( 2 ): 377 - 390 .

KARATALAY O , PSAROMILIGKOS I , CHAMPAGNE B . Energy-efficient resource allocation for D2D-assisted fog computing [J ] . IEEE Transactions on Green Communications and Networking , 2022 , 6 ( 4 ): 1990 - 2002 .

DAI X X , XIAO Z , JIANG H B , et al . Task co-offloading for D2D-assisted mobile edge computing in industrial internet of things [J ] . IEEE Transactions on Industrial Informatics , 2023 , 19 ( 1 ): 480 - 490 .

CHU W B , JIA X M , YU Z W , et al . On incentivizing resource allocation and task offloading for cooperative edge computing [J ] . Computer Networks , 2024 , 246 : 110428 .

LI H , YU J Y , CAO L L , et al . Multi-agent reinforcement learning based computation offloading and resource allocation for LEO Satellite edge computing networks [J ] . Computer Communications , 2024 , 222 : 268 - 276 .

ZHANG G P , YANG K , LIU P , et al . Achieving user cooperation diversity in TDMA-based wireless networks using cooperative game theory [J ] . IEEE Communications Letters , 2011 , 15 ( 2 ): 154 - 156 .

MONDERER D , SHAPLEY L S . Potential games [J ] . Games and Economic Behavior , 1996 , 14 ( 1 ): 124 - 143 .

康海燕 , 冀珊珊 . 面向无线边缘网络的分层Stackelberg博弈群体激励方法 [J ] . 电子学报 , 2024 , 52 ( 7 ): 2382 - 2392 .

KANG H Y , JI S S . Hierarchical stackelberg game swarm learning incentive method for wireless edge network [J ] . Acta Electronica Sinica , 2024 , 52 ( 7 ): 2382 - 2392 . (in Chinese)

CUI R X , GUO J , GAO B . Game theory-based negotiation for multiple robots task allocation [J ] . Robotica , 2013 , 31 ( 6 ): 923 - 934 .

ARSLAN G , MARDEN J R , SHAMMA J S . Autonomous vehicle-target assignment: A game-theoretical formulation [J ] . Journal of Dynamic Systems, Measurement, and Control , 2007 , 129 ( 5 ): 584 - 596 .

MARDEN J R , WIERMAN A . Distributed welfare games [J ] . Operations Research , 2013 , 61 ( 1 ): 155 - 168 .

MARDEN J R . The role of information in distributed resource allocation [J ] . IEEE Transactions on Control of Network Systems , 2017 , 4 ( 3 ): 654 - 664 .

HEIKKINEN T . A potential game approach to distributed power control and scheduling [J ] . Computer Networks , 2006 , 50 ( 13 ): 2295 - 2311 .

MARDEN J R , ARSLAN G , SHAMMA J S . Cooperative control and potential games [J ] . IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) , 2009 , 39 ( 6 ): 1393 - 1407 .

CHOI H L , KIM K S , JOHNSON L B , et al . Potential game-theoretic analysis of a market-based decentralized task allocation algorithm [M ] // Springer Tracts in Advanced Robotics . Tokyo : Springer Japan , 2016 : 207 - 220 .

PRASAD A , MOHAPATRA P S , REDDY P V . On the structure of feedback potential difference games [J ] . IEEE Transactions on Automatic Control , 2024 , 69 ( 1 ): 637 - 644 .

LIU J X , WANG Y T , PAN D T , et al . QoS-aware task offloading and resource allocation optimization in vehicular edge computing networks via MADDPG [J ] . Computer Networks , 2024 , 242 : 110282 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Task Segmentation and Path Optimization in Heterogeneous Cloud-Edge-End Computing Power Network

A Dynamic Task Scheduling for Wireless Sensor and Actuator Networks

Nash Equilibrium Based Task Scheduling Algorithm of Multi-schedulers in Grid Computing

Related Author

LI Chuan-huang

MA Bo

YU Ying-jie

WU Sha-chen

NI Chang

LU Qin

CHEN Chao

SHI Wei

Related Institution

School of Information and Electronic Engineering, Zhejiang Gongshang University

State Key Laboratory for Novel Software Technology at Nanjing UniversityNanjingJiangsu 210093China

College of ComputerNanjing University of Posts and TelecommunicationsNanjingJiangsu 210003China

State Key Laboratory for Novel Software Technology at Nanjing University

College of Computer, Nanjing University of Posts and Telecommunications

⁰