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

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

Abstract

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

CLC Number:

TN92

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.

Figures/Tables 13

References ［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．

Metrics

Recommended 0

No Suggested Reading articles found!

节点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]	Xin SUN, Guifu ZHANG, Hongyan XING, Wang Zenghui. Research on intrusion detection for maritime meteorological sensor network based on balancing generative adversarial network [J]. Journal on Communications, 2023, 44(4): 124-136.
[2]	Xueyong YU, Lixiang QIU, Jianing SONG, Hongbo ZHU. Security communication and energy efficiency optimization strategy in UAV-aided edge computing [J]. Journal on Communications, 2023, 44(3): 45-54.
[3]	Wei FAN, Cheng PENG, Dali ZHU, Yuqing WANG. Research on intrusion response strategy based on static Bayesian game in mobile edge computing network [J]. Journal on Communications, 2023, 44(2): 70-81.
[4]	Long LONG, Zichen LIU, Zaiwang LU, Yucheng ZHANG, Lei LI. Joint optimization strategy of service cache and resource allocation in mobile edge network [J]. Journal on Communications, 2023, 44(1): 64-74.
[5]	Wenlong KOU, Yuyang ZHANG, Fenghua LI, Xiaogang CAO, Jiamin LI, Zhu WANG, Kui GENG. On-demand and efficient scheduling scheme for cryptographic service resource [J]. Journal on Communications, 2022, 43(6): 108-118.
[6]	Bin LI, Wenshuai LIU, Wancheng XIE, Zesong FEI. Computation offloading scheme for RIS-empowered UAV edge network [J]. Journal on Communications, 2022, 43(10): 223-233.
[7]	Yongming HUANG, Chong ZHENG, Zhengming ZHANG, Xiaohu YOU. Research on mobile edge computing and caching in massive wireless communication network [J]. Journal on Communications, 2021, 42(4): 44-61.
[8]	Yuanzhi HE, Cong PENG, Jihong YU, Yun LIU. Resource scheduling algorithm of satellite communication system for future multi-beam dense networking [J]. Journal on Communications, 2021, 42(4): 109-118.
[9]	Fangwei LI, Haibo ZHANG, Zixin WANG. V2X collaborative caching and resource allocation in MEC-based IoV [J]. Journal on Communications, 2021, 42(2): 26-36.
[10]	Na WANG,Kun ZHENG,Junsong FU,Jian LI. Method of ciphertext retrieval in mobile edge computing based on block segmentation [J]. Journal on Communications, 2020, 41(7): 95-102.
[11]	Jin QI,Hairong SUN,Kun GONG,Bin XU,Shunyi ZHANG,Yanfei SUN. Research on intelligent computing offloading model based on reputation value in mobile edge computing [J]. Journal on Communications, 2020, 41(7): 141-151.
[12]	Dapeng WU,Ji LYU,Zhidu LI,Ruyan WANG. Mobility aware edge service migration strategy [J]. Journal on Communications, 2020, 41(4): 1-13.
[13]	Lindong ZHAO,Wenqin ZHUANG,Jianxin CHEN,Liang ZHOU. Hierarchical task offloading in heterogeneous cellular network:modeling and optimization [J]. Journal on Communications, 2020, 41(4): 34-44.
[14]	Bin TAN,Songyuan ZHAO,Jun WU,Wenru ZHANG. Virtual reality compressing and transmitting system based on mobile edge computing [J]. Journal on Communications, 2020, 41(4): 45-53.
[15]	Zhuo CHEN,Gang FENG,Yijing LIU,Yang ZHOU. Virtual network function deployment strategy based on improved genetic simulated annealing algorithm in MEC [J]. Journal on Communications, 2020, 41(4): 70-80.

Optimal coalition structure generation strategy in multi-task concurrent edge computing environment

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References ［26］

Related Articles 15

Metrics

Recommended 0