多任务并发边缘计算环境中最优联盟结构生成策略

doi:10.11959/j.issn.1000-436x.2023012

摘要/Abstract

摘要：

针对求解最优联盟结构时搜索空间大、效用低等问题，提出了一种基于离散最近过去位置更新策略的多进制离散粒子群优化（MDPSO-DRPPUS）算法。首先，使用基于索引的编码方式编码联盟结构。其次，将多目标优化问题转化为联盟结构的特征值函数。最后，使用MDPSO-DRPPUS算法进行最优联盟结构的搜索。实验表明，与多进制离散粒子群优化（MDPSO）算法和遗传算法（GA）相比，所提算法运行时间大幅度降低，联盟结构的效益、均衡性和边缘节点的完成任务效率都有所提高。

关键词: 移动边缘计算, 资源调度, 联盟结构生成, 多进制离散粒子群优化, 基于离散最近过去更新策略

Abstract:

A discrete recent past-position updating strategy based m-ary discrete particle swarm optimization (MDPSO-DRPPUS) algorithm was proposed for the problem of large search space and low efficiency when solving the optimal coalition structure.First, the coalition structure with index-based was coded.Then, the multi-objective optimization problem was transformed into an eigenvalue function of the coalition structure.Finally, the optimal coalition structure was searched by using the MDPSO-DRPPUS algorithm.Experiments show that compared with the m-ary discrete particle swarm optimization (MDPSO) algorithm and genetic algorithm (GA), the proposed algorithm dramatically reduces the average running time, and improves the efficiency and equilibrium of the coalition structure and task completion efficiency of edge nodes.

Key words: mobile edge computing, resource scheduling, coalition structure generation, MDPSO, DRPPUS

中图分类号:

TN92

赵庶旭, 韦萍, 王小龙. 多任务并发边缘计算环境中最优联盟结构生成策略[J]. 通信学报, 2023, 44(2): 172-184.

Shuxu ZHAO, Ping WEI, Xiaolong WANG. Optimal coalition structure generation strategy in multi-task concurrent edge computing environment[J]. Journal on Communications, 2023, 44(2): 172-184.

图/表 13

图1

图2

图3

图4

图5

表1

表2

表3

图6

图7

图8

图9

图10

参考文献［26］

［1］	KEKKI S , FEATHERSTONE W , FANG Y ,et al． MEC in 5G networks［R］． 2018．
［2］	DANG V D , DASH R K , ROGERS A ,et al． Overlapping coalition formation for efficient data fusion in multi-sensor networks［C］// Proceedings of AAAI． Palo Alto:AAAI Press, 2006: 635-640．
［3］	HAN Z , POOR H V ． Coalition games with cooperative transmission:a cure for the curse of boundary nodes in selfish packet-forwarding wireless networks［J］． IEEE Transactions on Communications, 2009,57(1): 203-213．
［4］	ZHANG Z F , SONG L Y , HAN Z ,et al． Coalitional games with overlapping coalitions for interference management in small cell networks［J］． IEEE Transactions on Wireless Communications, 2014,13(5): 2659-2669．
［5］	ZHAN S C , NIYATO D ． A coalition formation game for remote radio head cooperation in cloud radio access network［J］． IEEE Transactions on Vehicular Technology, 2017,66(2): 1723-1738．
［6］	LI X M , WAN J F , DAI H N ,et al． A hybrid computing solution and resource scheduling strategy for edge computing in smart manufacturing［J］． IEEE Transactions on Industrial Informatics, 2019,15(7): 4225-4234．
［7］	胡山立, 石纯一, 李少芳．给定限界的势结构分组与联盟结构生成［J］．计算机学报, 2012,35(12): 2618-2624．
	HU S L , SHI C Y , LI S F ． Cardinality structure grouping and coalition structure generation with given required bound［J］． Chinese Journal of Computers, 2012,35(12): 2618-2624．
［8］	RAHWAN T ． Algorithms for coalition formation in multi-agent systems［D］． Southampton:University of Southampton, 2007．
［9］	张新良, 石纯一．多 Agent 联盟结构动态生成算法［J］．软件学报, 2007,18(3): 574-581．
	ZHANG X L , SHI C Y ． A dynamic formation algorithm of multi-agent coalition structure［J］． Journal of Software, 2007,18(3): 574-581．
［10］	徐广斌, 刘惊雷．带有联盟个数约束的最优联盟结构生成［J］．南京大学学报(自然科学), 2015,51(4): 749-761．
	XU G B , LIU J L ． The optimal coalition structure generation with the constrained number of coalition［J］． Journal of Nanjing University (Natural Sciences), 2015,51(4): 749-761．
［11］	SEN S , DUTTA P S ． Searching for optimal coalition structures［C］// Proceedings of Fourth International Conference on MultiAgent Systems． Piscataway:IEEE Press, 2000: 287-292．
［12］	YANG J G ． Coalition formation mechanism in multi-agent systems based on genetic algorithms［J］． Applied Soft Computing, 2007,7(2): 561-568．
［13］	CONTRERAS J P , BOSCH P , VARAS M ,et al． A new genetic algorithm encoding for coalition structure generation problems［J］． Mathematical Problems in Engineering,2020, 2020:1203248．
［14］	蒋建国, 夏娜, 齐美彬 ,等．一种基于蚁群算法的多任务联盟串行生成算法［J］．电子学报, 2005,33(12): 2178-2182．
	JIANG J G , XIA N , QI M B ,et al． An ant colony algorithm based multi-task coalition serial generation algorithm［J］． Acta Electronica Sinica, 2005,33(12): 2178-2182．
［15］	LIN C F , HU S L ． Multi-task overlapping coalition parallel formation algorithm［C］// Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems． New York:ACM Press, 2007: 1-3．
［16］	ZHANG G F , YANG R Z , SU Z P ,et al． Using binary particle swarm optimization to search for maximal successful coalition［J］． Applied Intelligence, 2015,42(2): 195-209．
［17］	许金友．基于改进 DPSO 算法的多任务并行联盟生成研究［D］．大连:大连理工大学, 2009．
	XU J Y ． Research on multi-task parallel coalition generation based on modified discrete particle swarm optimization algorithm［D］． Dalian:Dalian University of Technology, 2009．
［18］	HU Y N , LI C S , ZHANG K J ． A method of searching for optimal coalition structure for solving resource scheduling problem of overall load balancing in edge computing environments［J］． Journal of Physics:Conference Series, 2020,1550(3): 032080．
［19］	ZHANG K J , FU Y , HU Y N ,et al． Scheduling strategy for computational-intensive data flow in generalized cluster environments［J］． Applied Soft Computing, 2019,82:105571．
［20］	ZHANG K J , HU Y N , TIAN F ,et al． A coalition-structure’s generation method for solving cooperative computing problems in edge computing environments［J］． Information Sciences, 2020,536: 372-390．
［21］	WANG D S , TAN D P , LIU L ． Particle swarm optimization algorithm:an overview［J］． Soft Computing, 2018,22(2): 387-408．
［22］	王炜, 陈渺, 李尚华．一类联合最大特征值函数优化问题［J］．吉林师范大学学报(自然科学版), 2014,35(1): 28-31．
	WANG W , CHEN M , LI S H ． Solving a minimization problem for a class of joint maximum eigenvalue functions［J］． Jilin Normal University Journal (Natural Science Edition), 2014,35(1): 28-31．
［23］	HART S , KURZ M ． Endogenous formation of coalitions［J］． Econometrica, 1983,51(4): 1047．
［24］	SANDHOLM T , et al ． Coalition structure generation with worst case guarantees［J］． Artificial Intelligence, 1999,111(1/2): 209-238．
［25］	ASKARI Q ． Political optimizer:a novel socio-inspired meta-heuristic for global optimization［J］． Knowledge-Based Systems, 2020,195:105709．
［26］	WANG X L , DANG J W , ZHAO S X ,et al． Coalition structure generation in edge computing environment with multitasking concurrency［J］． IEEE Internet of Things Journal, 2022:doi．org/10．1109/JIOT．2022．3217171．

节点ID	CPU		RAM		计算能力/MIPS	开销/s
节点ID	内核/个	频率/MHz	内存/GB	频率/MHz	计算能力/MIPS	开销/s
VM₁	1	1.33	4	1 600	1.21	1.20
VM₂	1	2.66	4	1 600	2.43	2.50
VM₃	2	1.33	4	1 600	2.62	2.90
VM₄	2	2.66	4	1 600	4.65	3.60
VM₅	1	1.33	4	2 133	1.61	1.70
VM₆	1	2.66	4	2 133	3.25	3.45
VM₇	2	1.33	4	2 133	3.5	3.70
VM₈	2	2.66	4	2 133	6.21	6.30
VM₉	1	1.33	8	1 600	2.51	2.65
VM₁₀	1	2.66	8	1 600	4.92	5.10
VM₁₁	2	1.33	8	1 600	5.38	5.60
VM₁₂	2	2.66	8	1 600	9.54	9.90
VM₁₃	1	1.33	8	2 133	3.34	3.50
VM₁₄	1	2.66	8	2 133	6.31	6.60
VM₁₅	2	1.33	8	2 133	7.19	7.35
VM₁₆	2	2.66	8	2 133	12.98	14.20

任务ID	任务工作量/百万次	计划完成时间/s	任务报酬
M₁	409	110	487
M₂	562	105	610
M₃	713	100	780
M₄	860	120	950
M₅	1 075	110	1 195
M₆	1 204	125	1 395
M₇	1 365	125	1 520
M₈	1 520	130	1 705

参数	参数值
最大任务数/个	8
最大边缘节点数/个	16
所有联盟结构数	1.85×10¹⁵
实验环境总计算能力/MIPS	77.65
实验环境总开销/s	80.25
总计算任务/百万次	7 708

[1]	王莉, 费爱国, 张平, 徐连明. 智能应急指挥通信网络新框架与关键技术研究[J]. 通信学报, 2023, 44(6): 1-11.
[2]	苏新, 张桂福, 行鸿彦, Zenghui Wang. 基于平衡生成对抗网络的海洋气象传感网入侵检测研究[J]. 通信学报, 2023, 44(4): 124-136.
[3]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.
[4]	范伟, 彭诚, 朱大立, 王雨晴. 移动边缘计算网络下基于静态贝叶斯博弈的入侵响应策略研究[J]. 通信学报, 2023, 44(2): 70-81.
[5]	龙隆, 刘子辰, 陆在旺, 张玉成, 李蕾. 移动边缘网络下服务缓存与资源分配联合优化策略[J]. 通信学报, 2023, 44(1): 64-74.
[6]	李斌, 刘文帅, 谢万城, 费泽松. 智能反射面赋能无人机边缘网络计算卸载方案[J]. 通信学报, 2022, 43(10): 223-233.
[7]	黄永明, 郑冲, 张征明, 尤肖虎. 大规模无线通信网络移动边缘计算和缓存研究[J]. 通信学报, 2021, 42(4): 44-61.
[8]	何元智, 彭聪, 于季弘, 刘韵. 面向密集多波束组网的卫星通信系统资源调度算法[J]. 通信学报, 2021, 42(4): 109-118.
[9]	李方伟, 张海波, 王子心. 车联网中基于MEC的V2X协同缓存和资源分配[J]. 通信学报, 2021, 42(2): 26-36.
[10]	王娜,郑坤,付俊松,李剑. 基于分块的移动边缘计算密文检索方法[J]. 通信学报, 2020, 41(7): 95-102.
[11]	亓晋,孙海蓉,巩锟,许斌,张顺颐,孙雁飞. 移动边缘计算中基于信誉值的智能计算卸载模型研究[J]. 通信学报, 2020, 41(7): 141-151.
[12]	吴大鹏,吕吉,李职杜,王汝言. 移动性感知的边缘服务迁移策略[J]. 通信学报, 2020, 41(4): 1-13.
[13]	张海君,张资政,隆克平. 基于移动边缘计算的NOMA异构网络资源分配[J]. 通信学报, 2020, 41(4): 27-33.
[14]	赵临东,庄文芹,陈建新,周亮. 异构蜂窝网络中分层任务卸载：建模与优化[J]. 通信学报, 2020, 41(4): 34-44.
[15]	谭彬,赵嵩源,吴俊,张文茹. 基于移动边缘计算的虚拟现实压缩与传输系统[J]. 通信学报, 2020, 41(4): 45-53.