《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (7): 2168-2174.DOI: 10.11772/j.issn.1001-9081.2023070921

• 计算机软件技术 • 上一篇    下一篇

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

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

  1. 云南大学 软件学院,昆明 650000
  • 收稿日期:2023-07-11 修回日期:2023-09-21 接受日期:2023-09-25 发布日期:2023-10-26 出版日期:2024-07-10
  • 通讯作者: 薛岗
  • 作者简介:田润泽(2001—),男,河北邯郸人,主要研究方向:深度学习、路径规划;
    周宇龙(1995—),男,河南荥阳人,硕士研究生,主要研究方向:机器学习、联邦学习;
    朱洪(2000—),女,重庆人,硕士研究生,主要研究方向:机器学习、联邦学习;
    第一联系人:薛岗(1977—),男,云南曲靖人,副教授,博士,主要研究方向:服务计算、嵌入式系统。
  • 基金资助:
    云南省科技厅重大科技专项(202202AD080002)

Local information based path selection algorithm for service migration

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

  1. 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)

摘要:

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

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

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

中图分类号: