Routing algorithm for heterogeneous computing force requests based on computing first network

ZHANG Gang; LI Xi

doi:10.11959/j.issn.1000-0801.2025016

您当前的位置：

首页 >

文章列表页 >

Routing algorithm for heterogeneous computing force requests based on computing first network

Research and Development | 更新时间：2025-03-11

- Routing algorithm for heterogeneous computing force requests based on computing first network
- Telecommunications Science Vol. 41, Issue 2, Pages: 95-110(2025)
- 作者机构：
  
  1.南昌工学院信息与人工智能学院，江西南昌 330108
  2.南昌工学院南昌市物联网信息可视化技术重点实验室，江西南昌 330108
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61572325);The Education Department Foundation of Jiangxi Province(GJJ212510);The Talent Introduction Project of Nanchang Institute of Technology(NGRCZX-21-07)
- DOI：10.11959/j.issn.1000-0801.2025016
  CLC： TP393
- Received：12 October 2024，
  
  Revised：2024-11-28，
  
  Published：20 February 2025
- 稿件说明：
移动端阅览
章刚,黎曦.基于算力网络的异构算力请求路由算法[J].电信科学,2025,41(02):95-110.

ZHANG Gang,LI Xi.Routing algorithm for heterogeneous computing force requests based on computing first network[J].Telecommunications Science,2025,41(02):95-110.
章刚,黎曦.基于算力网络的异构算力请求路由算法[J].电信科学,2025,41(02):95-110. DOI： 10.11959/j.issn.1000-0801.2025016.

ZHANG Gang,LI Xi.Routing algorithm for heterogeneous computing force requests based on computing first network[J].Telecommunications Science,2025,41(02):95-110. DOI： 10.11959/j.issn.1000-0801.2025016.

摘要

由于算力请求具有特殊性和独特性，如何为一组异构算力请求寻找传输链路互不相交的有效路径集，使得该组请求能够到达各自目的算力节点，从而实现为该组请求分配算力资源，是当前算力网络面临的关键问题。首先，对异构算力请求的路由问题进行剖析，并通过建模将其转化为非确定性多项式（nondeterministic polynomial，NP）完全问题。针对该问题，提出一种优化型遗传算法。该算法从局部和全局两个层面进行设计：在局部层面，为保证快速收敛到目标解，采用单参数满足随机性策略初始化种群，使得种群广泛地分散在解空间中；采用多参数解（或路径）均衡选择策略进行选择操作，使得被选种群丰富多样；采用两层交叉策略进行交叉操作，目的是拓宽全域搜索广度；采用多参数随机单点变异策略进行变异操作，目的是深挖局域搜索能力。在全局层面，为保证路径不冲突，采用路径分发策略，通过构建求解矩阵，并借助评价函数、可行解随机选择、低需求优先避让原则等方法，确保最终找到一组可行解集。实验从异构算力请求的传输成功率、算法收敛延时比、算力网络负载均衡误差率等3个方面进行验证，相较于IGAGCT算法与RBDQN算法，该算法在传输成功率、算法收敛延时比和负载均衡方面分别平均优化了8.85%、15.51%、17.03%及10.41%、16.5%、16.81%。

Abstract

Due to the particularity and uniqueness of computing force requests

how to find an effective path set with non-intersecting transmission links for a group of heterogeneous computing force requests

so that the group of requests can reach their respective destination computing force nodes

and thus allocate computing force resources for the group of requests

is a key issue facing current computing first networks. Firstly

the routing problem of heterogeneous computing force requests was analyzed and was transformed into an nondeterministic polynomial (NP)-complete problem through modeling. An optimized genetic algorithm to address this issue was proposed. This algorithm was designed from both local and global perspectives: to ensure fast convergence to the target solution locally

a single parameter satisfying the randomness strategy was used to initialize the population

making it widely dispersed in the solution space; adopting a multi-parameter solution (or path) balanced selection strategy for selection operations

making the selected population rich and diverse; adopting a two-layer crossover strategy for crossover operations

with the aim of expanding the breadth of global search; adopting a multi parameter random single point mutation strategy for mutation operations

with the aim of deepening local search capabilities. To ensure that the paths did not conflict globally

a path distribution strategy was adopted. By constructing a solution matrix and utilizing evaluation functions

random selection of feasible solutions

and the principle of low demand priority avoidance

a set of feasible solution sets was ultimately found. The experiment verifies that algorithm has been optimized by an average of 8.85%

15.51%

and 17.03% in terms of transmission success rate

convergence delay ratio

and load balancing compared to the IGAGCT algorithm and RBDQN algorithm

and 10.41%

16.5%

and 16.81%

respectively from three aspects: heterogeneous request success rate

algorithms convergence delay rate

and load error rate of computing first networks.

关键词

Keywords

references

中国移动通信集团终端有限公司 , 北京邮电大学 , 中国信息通信研究院 , 等 . 端侧算力网络白皮书(2022年) [R ] . 2022 .

China Mobile Terminal Co. , Ltd. , Beijing University of Posts and Telecommunications , China Academy of Information and Communications Technology , et al . Edge computing force network whitepaper [R ] . 2022 .

FU Y X , WANG J , LU L , et al . Reputation-based joint optimization of user satisfaction and resource utilization in a computing force network [J ] . Frontiers of Information Technology & Electronic Engineering , 2024 , 25 ( 5 ): 685 - 700 .

何涛 , 杨振东 , 曹畅 , 等 . 算力网络发展中的若干关键技术问题分析 [J ] . 电信科学 , 2022 , 38 ( 6 ): 62 - 70 .

HE T , YANG Z D , CAO C , et al . Analysis of some key technical problems in the development of computing power network [J ] . Telecommunications Science , 2022 , 38 ( 6 ): 62 - 70 .

贾庆民 , 胡玉姣 , 张华宇 , 等 . 确定性算力网络研究 [J ] . 通信学报 , 2022 , 43 ( 10 ): 55 - 64 .

JIA Q M , HU Y J , ZHANG H Y , et al . Research on deterministic computing power network [J ] . Journal on Communications , 2022 , 43 ( 10 ): 55 - 64 .

XIAO Y P , HE X , YANG C , et al . Dynamic graph computing: a method of finding companion vehicles from traffic streaming data [J ] . Information Sciences , 2022 , 591 : 128 - 141 .

LIU Z H , LENG J W , ZHANG Z H , et al . VELTAIR: towards high-performance multi-tenant deep learning services via adaptive compilation and scheduling [C ] // Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems . New York : ACM Press , 2022 : 388 – 401 .

KUO P C , CHEN Y W , HSU Y C , et al . High performance post-quantum key exchange on FPGAs [J ] . Journal of Information Science and Engineering , 2021 ( 38 ): 1211 - 1229 .

YANG M Y , QIAN Y , PU T L , et al . Edims: an event-driven internal memory synchronized readout prototype ASIC chip developed for HFRS-TPC [J ] . Nuclear Science and Techniques , 2023 , 34 ( 12 ): 196 .

WEI L , LI J Y , GAO Y F , et al . Resource matching algorithm based on multidimensional computing resource measurement in computing power network [C ] // Proceedings of the 2024 27th International Conference on Computer Supported Cooperative Work in Design (CSCWD) . Piscataway : IEEE Press , 2024 : 2295 - 2300 .

柴若楠 , 郜帅 , 兰江雨 , 等 . 算力网络中高效算力资源度量方法 [J ] . 计算机研究与发展 , 2023 , 60 ( 4 ): 763 - 771 .

CHAI R N , GAO S , LAN J Y , et al . Efficient computing resource metric method in computing-first network [J ] . Journal of Computer Research and Development , 2023 , 60 ( 4 ): 763 - 771 .

HAN X Y , XIE M X , YU K , et al . Combining graph neural network with deep reinforcement learning for resource allocation in computing force networks [J ] . Frontiers of Information Technology & Electronic Engineering , 2024 , 25 ( 5 ): 701 - 712 .

陈星延 , 张雪松 , 谢志龙 , 等 . 面向“云-边-端” 算力系统的计算和传输联合优化方法 [J ] . 计算机研究与发展 , 2023 , 60 ( 4 ): 719 - 734 .

CHEN X Y , ZHANG X S , XIE Z L , et al . A computing and transmission integrated optimization method for cloud-edge-end computing first system [J ] . Journal of Computer Research and Development , 2023 , 60 ( 4 ): 719 - 734 .

FANG W . Optimization algorithm for computing power resource scheduling based on container cluster deployment [J ] . Journal of Network Intelligence , 2024 , 9 ( 2 ): 835 - 849 .

李逸博 , 李小平 , 王爽 , 等 . 面向算力网络的智慧调度综述 [J ] . 自动化学报 , 2024 , 50 ( 6 ): 1086 - 1103 .

LI Y B , LI X P , WANG S , et al . Survey on wise scheduling in computing power network [J ] . Acta Automatica Sinica , 2024 , 50 ( 6 ): 1086 - 1103 .

XIE M X , YU K , WU X F . Adaptive routing of task in computing force network by integrating graph convolutional network and deep Q-network [C ] // Proceedings of the 2023 8th IEEE International Conference on Network Intelligence and Digital Content (IC-NIDC) . Piscataway : IEEE Press , 2023 : 242 - 247 .

LI X N , LU J G , ZHANG P M . A GNN-based routing and scheduling mechanism for multi-domain computing first network [C ] // Proceedings of the 2023 IEEE 9th International Conference on Cloud Computing and Intelligent Systems (CCIS) . Piscataway : IEEE Press , 2023 : 153 - 163 .

孙国玮 , 许方敏 , 朱瑾瑜 , 等 . 算力网络中的确定性调度与路由联合智能优化方案 [J ] . 北京邮电大学学报 , 2023 , 46 ( 2 ): 9 - 14 .

SUN G W , XU F M , ZHU J Y , et al . Deterministic scheduling and routing joint intelligent optimization scheme in computing first network [J ] . Journal of Beijing University of Posts and Telecommunications , 2023 , 46 ( 2 ): 9 - 14 .

李洪钧 , 任保全 , 巩向武 , 等 . 天地一体化网络分散式算力路由控制策略 [J ] . 指挥与控制学报 , 2022 , 8 ( 4 ): 451 - 459 .

LI H J , REN B Q , GONG X W , et al . Dispersed computing-dependent routing control strategies for space-ground integration networks [J ] . Journal of Command and Control , 2022 , 8 ( 4 ): 451 - 459 .

YAO H J , DUAN X D , FU Y X . A computing-aware routing protocol for Computing Force Network [C ] // Proceedings of the 2022 International Conference on Service Science (ICSS) . Piscataway : IEEE Press , 2022 : 137 - 141 .

颜晓莲 , 邱晓红 . 支持边缘端: 云端协同工作的群组命令传输算法 [J ] . 计算机应用研究 , 2021 , 38 ( 4 ): 1154 - 1157 .

YAN X L , QIU X H . Group command transfer algorithm for edge-cloud cooperative work [J ] . Application Research of Computers , 2021 , 38 ( 4 ): 1154 - 1157 .

颜晓莲 , 章刚 , 邱晓红 . 一种支撑协同制造的动态群组命令传输算法 [J ] . 计算机应用研究 , 2020 , 37 ( 8 ): 2362 - 2365, 2394 .

YAN X L , ZHANG G , QIU X H . Dynamic group command transfer algorithm for collaborative manufacturing [J ] . Application Research of Computers , 2020 , 37 ( 8 ): 2362 - 2365, 2394 .

XU X W , DING H , WANG J Y , et al . Compute first networking scheduling strategy based on genetic algorithm in edge computing environment [M ] // Communications in Computer and Information Science . Singapore : Springer Nature Singapore , 2024 : 197 - 205 .

LIU Y , JIANG J B , LIU Y , et al . Network resource optimization configuration in edge computing environment [J ] . International Journal of Computers and Applications , 2023 , 45 ( 1 ): 88 - 95 .

CREEVEY F M , HILL C D , HOLLENBERG L C L . GASP: a genetic algorithm for state preparation on quantum computers [J ] . Scientific Reports , 2023 , 13 ( 1 ): 11956 .

WAXMAN B M . Performance evaluation of multipoint routing algorithms [C ] // Proceedings of the IEEE INFOCOM '93 The Conference on Computer Communications , Proceedings . Piscataway : IEEE Press , 1993 : 980 - 986 .

O’SULLIVAN M , ANIELLO L , SASSONE V . A methodology to select topology generators for ad hoc mesh network simulations [J ] . Journal of Communications , 2020 ( 15 ): 741 - 746 .

Views

695

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on control strategy of bidirectional DC-DC converter based on improved genetic algorithm

Task urgency-based resource allocation algorithm in industrial Internet of things

Research on POI quality prediction based on KPCA-GA-BP neural network

A genetic algorithm based method of optimizing dispersion matrix for RDSM system

Virtual machine scheduling model based on Shapley value modified genetic algorithm in cloud computing

Related Author

ZHOU Hongxi

LIU Yang

CHEN Zhuaixia

GAO Feifan

LI Can

CHEN Can

LI Li

ZHUO Sai

Related Institution

State Grid Information & Telecommunication Co., Ltd.

Advanced Network and Intelligent Connection Technology Key Laboratory of Chongqing Education Commission of China

Chongqing Key Laboratory of Ubiquitous Sensing and Networking

School of Communications and Information Engineering, Chongqing University of Posts and Telecommunications

Chongqing Branch of China Mobile Communications Group Design Institute Co., Ltd.

⁰