Local information based path selection algorithm for service migration

doi:10.11772/j.issn.1001-9081.2023070921

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (7): 2168-2174.DOI: 10.11772/j.issn.1001-9081.2023070921

• Computer software technology • Previous Articles Next Articles

Local information based path selection algorithm for service migration

Runze TIAN, Yulong ZHOU, Hong ZHU, Gang XUE()

School of Software，Yunnan University，Kunming Yunnan 650000，China

Received:2023-07-11 Revised:2023-09-21 Accepted:2023-09-25 Online:2023-10-26 Published:2024-07-10
Contact: Gang XUE
About author:TIAN Runze， born in 2001. His research interests include deep learning， path planning.
ZHOU Yulong， born in 1995， M. S. candidate. His research interests include machine learning， federated learning.
ZHU Hong， born in 2000， M. S. candidate. Her research interests include machine learning， federated learning.
First author contact:XUE Gang， born in 1977， Ph. D.， associate professor. His research interests include service computing， embedded system.
Supported by:
Science and Technology Plan in Key Fields of Yunnan Province(202202AD080002)

基于局部信息的服务迁移路径选择算法

田润泽, 周宇龙, 朱洪, 薛岗()

云南大学软件学院，昆明 650000

通讯作者: 薛岗
作者简介:田润泽（2001—），男，河北邯郸人，主要研究方向：深度学习、路径规划；
周宇龙（1995—），男，河南荥阳人，硕士研究生，主要研究方向：机器学习、联邦学习；
朱洪（2000—），女，重庆人，硕士研究生，主要研究方向：机器学习、联邦学习；
第一联系人：薛岗（1977—），男，云南曲靖人，副教授，博士，主要研究方向：服务计算、嵌入式系统。
基金资助:
云南省科技厅重大科技专项(202202AD080002)

Abstract

Abstract:

With rapid development of mobile edge computing， providing high-quality mobile services requires considering various factors that affect network communication diversifiedly according to the real-time changes of user mobility trajectories， and service migration paths should be dynamically planned. Addressing existing gaps in service migration path planning studies， particularly the lack of predictive models for user mobility trajectories in urban scenarios and low similarity between planned and actual user paths， an algorithm was proposed for service migration path selection based on real-time user movement trajectories. The user’s future movement trajectory was predicted through a trajectory prediction algorithm based on Long Short-Term Memory （LSTM） model and a road network matching algorithm based on Hidden Markov Model （HMM）. Then， according to predicted movement trajectory and status information of nearby local base stations， the optimal migration edge server was selected， thereby completing service migration path selection in urban scenarios. On the dataset constructed from taxi trajectory dataset and mobile base station status dataset in Shenzhen， compared to the improved Depth-First Search （DFS） algorithm， improved A^* algorithm， Matrix-based Dynamic Multi-Path Selection （MDMPS） algorithm and Grid Division-based Service Migration Path Selection （GDSMPS） algorithm， the proposed algorithm reduced the average service migration time by 34.8%， 44.5%， 24.9% and 12.7% respectively， and increased average path similarity by 26.2%， 49.7%， 14.3% and 4.7% respectively. On noise datasets and long path datasets， the proposed algorithm had the smallest fluctuation in average service migration time and the highest average trajectory similarity. Experimental results show that the proposed algorithm not only effectively reduces service migration time， enhances the similarity between migration path and user movement path， but also has good resistance to data noise and excellent long-distance path planning capability.

Key words: service migration path, Long Short-Term Memory (LSTM) neural network, trajectory prediction, road network matching, dynamic path planning

摘要：

随着移动边缘计算技术的高速发展，提供高质量的移动服务需要根据用户实时的移动轨迹变化多元地考虑网络通信中的影响因素来动态地规划服务迁移路径。针对现有服务迁移路径规划研究中对城市场景下用户移动轨迹预测缺失、规划迁移路径与用户移动路径相似度较低等问题，提出一种根据用户实时移动轨迹的服务移动路径选择算法。首先通过基于长短期记忆（LSTM）模型的轨迹预测算法和基于隐马尔可夫模型（HMM）的路网匹配算法预测用户未来移动轨迹，然后根据预测移动轨迹与邻近局部基站状态信息选择最佳迁移边缘服务器，进而完成城市场景下基于网格地图的服务迁移路径选择。在深圳市出租车轨迹数据集与手机基站状态数据集所构造的数据集上，相较于改进深度优先搜索（DFS）算法、改进A^*算法、基于矩阵的动态多路径选择（MDMPS）算法和基于矩形区域划分的服务迁移路径选择（GDSMPS）算法，所提算法的平均服务迁移时间分别减少了34.8%、44.5%、24.9%和12.7%，平衡路径相似度分别提升了26.2%、49.7%、14.3%和4.7%；在噪声数据集和长路径数据集上，所提算法的平均服务迁移时间波动幅度最小且平均轨迹相似度最高。实验结果表明，所提算法不仅可以有效减少服务迁移时间，提升迁移路径与用户移动路径的相似度，而且具有良好的抗数据噪声能力与优秀的长路径规划能力。

关键词: 服务迁移路径, 长短期记忆神经网络, 轨迹预测, 路网匹配, 动态路径规划

CLC Number:

TP311.1

Runze TIAN, Yulong ZHOU, Hong ZHU, Gang XUE. Local information based path selection algorithm for service migration[J]. Journal of Computer Applications, 2024, 44(7): 2168-2174.

田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.

Figures/Tables 6

Fig. 1 Basic process of real-time service migration path selection stage

Fig. 2 LSTM model structure

Fig. 3 Schematic diagram of extracted Shenzhen road network information

Tab. 1 Experimental results on total test set

算法	$T r u n ¯$ /s	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%
本文算法	0.32	1.72	86.2
改进DFS算法^［17］	3.42	2.64	68.3
改进A^*算法^［18］	0.27	3.10	57.6
MDMPS算法^［19］	0.35	2.29	75.4
GDSMPS算法^［20］	0.41	1.97	82.3

Tab. 1 Experimental results on total test set

算法	$T r u n ¯$ /s	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%
本文算法	0.32	1.72	86.2
改进DFS算法^［17］	3.42	2.64	68.3
改进A^*算法^［18］	0.27	3.10	57.6
MDMPS算法^［19］	0.35	2.29	75.4
GDSMPS算法^［20］	0.41	1.97	82.3

Tab. 2 Experimental results on noisy datasets

算法	ND1（偏移距离20 m）		ND2（偏移距离30 m）		ND3（偏移距离40 m）		ND4（偏移距离50 m）		ND5（偏移距离80 m）
算法	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s
本文算法	87.2	1.75	86.4	1.68	85.9	1.82	85.3	1.77	82.1	1.79
改进DFS算法^［17］	74.1	2.69	72.2	2.36	68.1	2.91	65.7	2.84	60.3	3.09
改进A^*算法^［18］	57.5	3.04	56.2	2.44	54.1	3.56	51.3	3.19	48.8	3.68
MDMPS算法^［19］	77.2	2.11	74.6	1.82	71.3	2.28	69.1	2.51	67.3	2.60
GDSMPS算法^［20］	83.7	1.92	80.4	2.09	77.2	2.16	75.6	2.31	74.1	2.47

Tab. 2 Experimental results on noisy datasets

算法	ND1（偏移距离20 m）		ND2（偏移距离30 m）		ND3（偏移距离40 m）		ND4（偏移距离50 m）		ND5（偏移距离80 m）
算法	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s
本文算法	87.2	1.75	86.4	1.68	85.9	1.82	85.3	1.77	82.1	1.79
改进DFS算法^［17］	74.1	2.69	72.2	2.36	68.1	2.91	65.7	2.84	60.3	3.09
改进A^*算法^［18］	57.5	3.04	56.2	2.44	54.1	3.56	51.3	3.19	48.8	3.68
MDMPS算法^［19］	77.2	2.11	74.6	1.82	71.3	2.28	69.1	2.51	67.3	2.60
GDSMPS算法^［20］	83.7	1.92	80.4	2.09	77.2	2.16	75.6	2.31	74.1	2.47

Tab. 3 Experimental results on long-path datasets

算法	LPD1		LPD2		LPD3
算法	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s
本文算法	86.8	2.07	84.7	2.68	82.6	3.56
改进DFS算法^［17］	74.1	2.77	71.3	3.67	66.9	5.72
改进A^*算法^［18］	57.5	3.82	53.2	5.43	44.4	7.27
MDMPS算法^［19］	77.2	2.31	73.1	2.89	69.8	4.12
GDSMPS算法^［20］	83.6	2.19	80.2	3.01	74.3	3.86

Tab. 3 Experimental results on long-path datasets

算法	LPD1		LPD2		LPD3
算法	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s	$S ¯ t r a j e c t o r y$ /%	$T ¯ m i g r a t i o n$ /s
本文算法	86.8	2.07	84.7	2.68	82.6	3.56
改进DFS算法^［17］	74.1	2.77	71.3	3.67	66.9	5.72
改进A^*算法^［18］	57.5	3.82	53.2	5.43	44.4	7.27
MDMPS算法^［19］	77.2	2.31	73.1	2.89	69.8	4.12
GDSMPS算法^［20］	83.6	2.19	80.2	3.01	74.3	3.86

References 21

1	ALI B， GREGORY M A， LI S. Multi-access edge computing architecture， data security and privacy： a review ［J］. IEEE Access， 2021， 9： 18706-18721.
2	CRUZ P， ACHIR N， VIANA A C. On the edge of the deployment： a survey on multi-access edge computing ［J］. ACM Computing Surveys， 2022， 55（5）： No.99.
3	LIANG B， GREGORY M A， LI S. Multi-access edge computing fundamentals， services， enablers and challenges： a complete survey ［J］. Journal of Network and Computer Applications， 2022， 199： 103308.
4	曹腾飞，刘延亮，王晓英.基于改进深度强化学习的边缘计算服务卸载算法［J］.计算机应用， 2023， 43（5）： 1543-1550.
	CAO T F， LIU Y L， WANG X Y. Edge computing and service offloading algorithm based on improved deep reinforcement learning ［J］. Journal of Computer Applications， 2023， 43（5）： 1543-1550.
5	LI C， ZHANG Q， LUO Y. A jointly non-cooperative game-based offloading and dynamic service migration approach in mobile edge computing ［J］. Knowledge and Information Systems， 2023， 65（5）： 2187-2223.
6	LIU J， ANAVATTI S， GARRATT M， et al. Modified continuous ant colony optimisation for multiple unmanned ground vehicle path planning ［J］. Expert Systems with Applications， 2022， 196： 116605.
7	WANG H， LI G， HOU J， et al. A path planning method for underground intelligent vehicles based on an improved RRT* algorithm ［J］. Electronics， 2022， 11（3）： 294.
8	ZHAO C， ZHU Y， DU Y， et al. A novel direct trajectory planning approach based on generative adversarial networks and rapidly-exploring random tree ［J］. IEEE Transactions on Intelligent Transportation Systems， 2022， 23（10）： 17910-17921.
9	GAO D， ZHU Y， ZHANG J， et al. A novel MP-LSTM method for ship trajectory prediction based on AIS data ［J］. Ocean Engineering， 2021， 228： 108956.
10	GUO H， MENG Q， CAO D， et al. Vehicle trajectory prediction method coupled with ego vehicle motion trend under dual attention mechanism ［J］. IEEE Transactions on Instrumentation and Measurement， 2022， 71： 2507516.
11	GAO H， QIN Y， HU C， et al. An interacting multiple model for trajectory prediction of intelligent vehicles in typical road traffic scenario ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2021， 34（9）： 6468-6479.
12	袁景凌，毛慧华，王娜娜，等.移动边缘计算中资源受限的动态服务部署策略［J］.计算机应用， 2022， 42（6）： 1662-1667.
	YUAN J L， MAO H H， WANG N N， et al. Dynamic service deployment strategy in resource constrained mobile edge computing ［J］. Journal of Computer Applications， 2022， 42（6）： 1662-1667.
13	郑赛，李天瑞，黄维.面向通信成本优化的联邦学习算法［J］.计算机应用， 2023， 43（1）： 1-7.
	ZHENG S， LI T R， HUANG W. Federated learning algorithm for communication cost optimization ［J］. Journal of Computer Applications， 2023， 43（1）： 1-7.
14	EWEES A A， AL-QANESS M A A， ABUALIGAH L， et al. HBO-LSTM： Optimized long short term memory with heap-based optimizer for wind power forecasting ［J］. Energy Conversion and Management， 2022， 268： 116022.
15	MAI G， JANOWICZ K， ZHU R， et al. Geographic question answering： challenges， uniqueness， classification， and future directions ［J］. AGILE： GIScience Series， 2021， 2： No.8.
16	LI C， CAI Q， LUO Y. Low-latency edge cooperation caching based on base station cooperation in SDN based MEC ［J］. Expert Systems with Applications， 2022， 191： 116252.
17	郭展羽，张志明，贺兰山，等.过必经点集且具有额外硬约束的最短路径算法［J］.计算机工程与应用， 2022， 58（18）： 297-303.
	GUO Z Y， ZHANG Z M， HE L S， et al. Shortest path algorithm through necessary nodes with extra hard constraints ［J］. Computer Engineering and Applications， 2022， 58（18）： 297-303.
18	王洪斌，尹鹏衡，郑维，等.基于改进的A^*算法与动态窗口法的移动机器人路径规划［J］.机器人， 2020， 42（3）： 346-353.
	WANG H B， YIN P H， ZHENG W， et al. Mobile robot path planning based on improved A^* algorithm and dynamic window method ［J］. Robot， 2020， 42（3）： 346-353.
19	ANWAR M R， WANG S， AKRAM M F， et al. 5G-enabled MEC： a distributed traffic steering for seamless service migration of Internet of vehicles ［J］. IEEE Internet of Things Journal， 2022， 9（1）： 648-661.
20	PU C， YAO S， CHEN D， et al. Grid division-based service migration path selection method in edge computing environment ［C］// Proceedings of the 2022 4th International Conference on Communications， Information System and Computer Engineering. Piscataway： IEEE， 2022： 541-548.
21	TSAI T J. Segmental DTW： a parallelizable alternative to dynamic time warping ［C］// Proceedings of the 2021 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2021： 106-110.

[1]	Hailin XIAO, Tianyi HUANG, Qiuxiang DAI, Yuejun ZHANG, Zhongshan ZHANG. Safe reinforcement learning method for decision making of autonomous lane changing based on trajectory prediction [J]. Journal of Computer Applications, 2024, 44(9): 2958-2963.
[2]	Peiqian LIU, Shuilian WANG, Zihao SHEN, Hui WANG. Location privacy protection algorithm based on trajectory perturbation and road network matching [J]. Journal of Computer Applications, 2024, 44(5): 1546-1554.
[3]	Yu WANG, Zhihui GUAN, Yuanpeng LI. Distributed UAV cluster pursuit decision-making based on trajectory prediction and MADDPG [J]. Journal of Computer Applications, 2024, 44(11): 3623-3628.
[4]	Jiagao WU, Shiwen ZHANG, Yudong JIANG, Linfeng LIU. Social-interaction GAN for pedestrian trajectory prediction based on state-refinement long short-term memory and attention mechanism [J]. Journal of Computer Applications, 2023, 43(5): 1565-1570.
[5]	Tao PENG, Yalong KANG, Feng YU, Zili ZHANG, Junping LIU, Xinrong HU, Ruhan HE, Li LI. Pedestrian trajectory prediction based on multi-head soft attention graph convolutional network [J]. Journal of Computer Applications, 2023, 43(3): 736-743.
[6]	Yijian ZHAO, Li LIN, Qianqian WANG, Peng WEN, Dong YANG. Trajectory prediction of sea targets based on geodetic distance similarity calculation [J]. Journal of Computer Applications, 2023, 43(11): 3594-3598.
[7]	Yuli CHEN, Qiang TONG, Tongtong CHEN, Shoulu HOU, Xiulei LIU. Short-term trajectory prediction model of aircraft based on attention mechanism and generative adversarial network [J]. Journal of Computer Applications, 2022, 42(10): 3292-3299.
[8]	DAI Yurou, YANG Qing, ZHANG Fengli, ZHOU Fan. Trajectory prediction model of social network users based on self-supervised learning [J]. Journal of Computer Applications, 2021, 41(9): 2545-2551.
[9]	LI Xujuan, PI Jianyong, HUANG Feixiang, JIA Haipeng. Self-generated deep neural network based 4D trajectory prediction [J]. Journal of Computer Applications, 2021, 41(5): 1492-1499.
[10]	FU Qianhui, LI Qingkui, FU Jingnan, WANG Yu. Dense crowd counting model based on spatial dimensional recurrent perception network [J]. Journal of Computer Applications, 2021, 41(2): 544-549.
[11]	ZHANG Xiaohan, FENG Aimin. Short-term traffic flow prediction based on empirical mode decomposition and long short-term memory neural network [J]. Journal of Computer Applications, 2021, 41(1): 225-230.
[12]	WANG Kun, ZHENG Yi, FANG Shuya, LIU Shouyin. Long text aspect-level sentiment analysis based on text filtering and improved BERT [J]. Journal of Computer Applications, 2020, 40(10): 2838-2844.
[13]	ZHAO Hong, WANG Le, WANG Weijie. Text sentiment analysis based on serial hybrid model of bi-directional long short-term memory and convolutional neural network [J]. Journal of Computer Applications, 2020, 40(1): 16-22.
[14]	GAO Jian, MAO Yingchi, LI Zhitao. Trajectory prediction based on Gauss mixture time series model [J]. Journal of Computer Applications, 2019, 39(8): 2261-2270.
[15]	KIM Chungsong, LI Dong. Deep learning neural network model for consumer preference prediction [J]. Journal of Computer Applications, 2019, 39(7): 1888-1893.

Local information based path selection algorithm for service migration

基于局部信息的服务迁移路径选择算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 21

Related Articles 15

Recommended Articles

Metrics