摘 要

随着移动互联网的发展，完全依靠远端云的计算会给网络传输带来较高的拥塞和延迟，由此提出了移动边缘计算（Mobile Edge Computing, MEC）的概念。移动边缘计算将移动设备请求的服务从远端的互联网数据中心迁移到了距离终端更近的边缘云上，可以使用户获取服务的延迟更低。因此，根据负载把不同服务按照一定的策略放置在不同的边缘云上尤为重要，这就是服务提供方法。在现有的对MEC环境中的服务提供方法的研究中，较少考虑用户移动性，无法满足用户的实际需求。

针对上述问题，本文提出了一种基于多用户概率移动模型的服务提供方法。首先，基于一种个人移动模型（Individual Mobility Model，IMM）构建多用户概率移动模型；然后，依据上述模型提出一种基于多用户概率移动模型的负载预测方法，预测未来的用户位置和区域负载；最后，设计了一种在线服务提供算法，在用户获取服务的平均延迟和服务提供商服务提供成本之间进行折中，同时将用户在不同的边缘云之间进行切换导致的服务迁移带来的成本也考虑在内。

采用真实数据集测试提出方法的性能，仿真实验结果表明基于多用户概率移动模型的预测准确率比基于Markov模型的预测算法高16.87%，基于多用户概率移动模型的服务提供算法的延迟较对比算法缩短了20.30%，可见基于多用户概率移动模型的服务提供算法的性能更好。

关键词：移动边缘计算 服务提供 多用户概率移动模型 边缘云切换

Abstract

With the development of the Mobile Internet, relying on the calculation of the remote cloud will bring higher congestion and delay to the network transmission. Thus the concept of mobile edge computing (MEC) is proposed. MEC migrates the services requested by the mobile devices from the remote Internet data center to the edge cloud which is closer to the terminal, which can make the delay for the user to obtain the service lower. Therefore, it is particularly important to place different services on different edge clouds according to certain policies based on the load. This is the service placement method. In the existing research on service placement methods in the MEC environment, user mobility is rarely considered, so that the actual needs of the user cannot be met.

To solve the above problems, a service placement algorithm based on multi-user mobility model is proposed in this paper. First, a multi-user probability mobility model is constructed based on the Individual Mobility Model (IMM); then, a multi-user probability mobile load prediction algorithm is proposed according to the above model to predict the location of users and the load of regions in the future; in the end, we design an online service placement algorithm. There is a trade-off between the average latency of the user's access to the service and the service provider's cost, and the cost of service migration with users hand over among different edge clouds is also taken into account.

The performance of the method was tested using real data sets. The simulation results show that the prediction accuracy rate based on the multi-user probabilistic mobility model is 16.87% higher than that based on the Markov model, and the delay of the service placement algorithm based on the multi-user mobility model is 20.30% shorter than the comparison algorithm. It can be seen that the service placement algorithm based on the multi-user mobility model has better performance.

Key Words：mobile edge computing, service placement, multi-user mobility model, edge cloud hand over

目 录

1 绪论 1

1.1 研究背景 1

1.2 研究意义 1

1.3 论文创新点 2

1.4 论文结构 2

2 国内外研究现状分析 3

2.1 用户移动模型 3

2.2 服务提供算法 3

3 一种基于多用户概率移动模型的负载预测方法 6

3.1 问题描述 6

3.2 一种基于IMM的多用户概率移动模型 6

3.2.1 IMM模型简介 6

3.2.2 一种多用户概率移动模型 8

3.3 一种基于多用户概率移动模型的负载预测方法 8

3.4 仿真实验 10

3.4.1 仿真环境 10

3.4.2 评价指标 10

3.4.3 性能评估 11

4 一种基于多用户概率移动模型的服务提供方法 16

4.1 问题描述 16

4.2 系统模型 16

4.3 算法设计 19

4.4 仿真实验 22

4.4.1 仿真环境 22

4.4.2 评价指标 22

4.4.3 性能评估 23

5 总结及展望 25

5.1 论文总结 25

5.2 未来工作展望 25

参考文献 27

致 谢 29

1 绪论

1.1 研究背景

随着计算机互联网技术的迅速发展，移动网络广泛部署和应用于移动用户周边。移动用户的数量随之不断的增加，数以亿计的用户使用移动设备工作、学习、社交、娱乐；日常生活的诸多方面都离不开移动互联网的参与^[1]。然而，移动设备在处理能力、存储容量等方面受到设备硬件条件的限制，因此移动用户通常无法获得与使用个人计算机时相当的满意度。同时，移动云计算的发展带动了各个行业的物联网终端数量的爆炸式增长，直接导致了云计算中心的访问量剧增，物联网终端与云计算中心之间的大批量数据的发送和接收对网络负载和网络带宽也提出了更高的要求。

在现有的架构下，业务流量需要流经整个接入网和核心网，通过基站、转发设备等多重关键设备^[2]。为了满足移动用户高性能、高带宽、低时延等的客观需求，移动边缘计算（Mobile Edge Computing, MEC）的概念应运而生。2014年，欧洲电信标准化协会（European Telecommunications Standards Institute，ETSI）首次提出了移动边缘计算的概念，并进行了相关的标准化工作，迅速引起了学术界和产业界的广泛关注。

根据ETSI的定义，移动边缘计算是指在靠近移动用户的无线接入网络（Radio Access Network, RAN）内提供信息技术和云计算功能^[3]。它将云计算中心从远程的互联网数据中心迁移到与移动用户更靠近的和无线接入网络相连的基础设施中。它常常位于基站或无线电网络控制器，提供对实时无线电和网络信息（如用户位置或小区负载）的访问，这些信息可被应用程序和服务提供者用来提供上下文相关的服务。对于应用开发人员和内容提供商来说，MEC模式在无线接入网络边缘提供了一个以邻近性，低延迟，高带宽为特征的服务环境，能支持实时访问无线网络信息和位置感知的服务。

考虑到移动服务的迅速发展，研究边缘计算环境中的服务提供方法旨在利用边缘云为移动用户提供服务的存储和计算，使得用户感知到的访问延迟最小化，同时也能最小化服务提供商的成本并实现高吞吐量，使其利润最大化。由于用户高度的移动性，移动边缘计算的服务提供方法要求能够动态的在多个边缘云上提供服务，以满足用户对服务的需求并最小化用户获取服务的延迟尽，并在此基础上可以降低服务提供商放置服务的成本。

1.2 研究意义

移动边缘计算作为5G网络体系架构演进的关键技术，可以应用于时延敏感、高实时性等场景，如增强现实、智能家居等^[4]。边缘计算通过在边缘网络中为用户端提供云服务来解决用户对于资源的需求问题，以此代替在核心网络进行计算，因此可以减少延迟，提升用户的体验。

移动边缘计算技术可以满足系统吞吐量、时延、网络可伸缩性等方面的要求，在5G时代，它将会推动云计算平台同移动网络的融合，可能在技术及社会各方面带来新一轮的变革。在这样的背景下，研究移动边缘计算环境中的服务提供方法具有重要应用价值和较高理论意义。

1.3 论文创新点

1. 提出了一种多用户概率移动模型，在个人移动模型（Individual Mobility Model，IMM）的基础上对多用户的移动行为建立模型，以概率的形式描述多用户的移动性。
2. 基于多用户概率移动模型，提出了一种负载预测方法，通过预测用户的位置获得各区域的预测负载。
3. 基于多用户概率移动模型，提出了一种服务提供算法，把基于多用户概率移动模型的负载预测方法的结果作为服务提供算法的基础。在确定服务提供算法的优化目标时，考虑因用户移动，从不同边缘云中获取服务的切换成本。

1.4 论文结构

本文正文部分共分为五章，第一章介绍了移动边缘计算环境中的服务提供方法的研究背景和意义以及论文的创新点和结构。第二章综述用户移动模型和服务提供算法的国内外研究现状，分析了当前已有的成果和尚存的不足之处。第三章建立了基于IMM的多用户概率移动模型，提出了一种基于多用户概率移动模型的负载预测方法，设计并实现了该算法，并模拟真实环境分析算法性能。第四章在第三章的基础上，提出了一种基于多用户概率移动模型的服务提供算法，设计并实现了该算法，模拟真实环境评估算法性能。第五章总结本文工作，展望未来研究方向，对本文已取得的成果和有待继续深入研究的问题进行了总结。

2 国内外研究现状分析

2.1 用户移动模型

服务提供算法的输入是预测的区域负载，这与用户移动模型相关。由于用户移动受到诸多因素的影响，准确的描述用户的移动行为是不可能的，通常使用的用户移动模型有随机游走模型(Random Walk Model，RWM)、马尔科夫模型（Markov Model, MM）、隐马尔科夫模型（Hidden Markov Model, HMM）、向量机模型（Vector Mobility Model, VMM）

Chiang等人^[5]提出了一种新颖的二维（2-D）随机游走移动性模型，用于研究和分析移动用户在无线网络中的定位区域穿越率和停留时间，从而确定移动用户的位置。Lv等人^[6]研究了生活习惯对时空预测和下一步预测模型的影响，结合隐马尔可夫模型从这两个模型中选择一个实现了用户兴趣点的有效动态预测。Chung等人^[7]提出了一个随机合成随机向量机移动模型来模拟车辆自组织网络中的车辆交通移动，车辆移动性的一个基本特征是它具有方向性，并且瞄准目的地，同时在速度和角度上的变化随着其移动目的地显示出一定程度的随机性，因此向量机模型十分有效。

用户的移动受到移动方式、移动速度、用户当前的行为目的等因素的影响，随机游走模型具有较强的随机性，常常被用于物理化学学科中来描述原子运动。向量机模型更适合车辆的移动模型。马尔科夫模型基于的假设是“无后效性”，假设未来的状态只与当前的状态有关，与过去的状态无关，但实际上用户的移动位置会显示出与过去行为相似的特性。用户移动会展现出一定的倾向性和聚类性，这是上述模型中没有涉及到的。

针对上述问题，Ge等人^[25]提出了IMM模型，IMM模型考虑了人类移动的倾向性和聚类性。在IMM模型中，为用户的每一次移动建立模型，用户移动和停留满足一定的概率分布，从而模拟用户的可能的行为状态。IMM模型可以更好的描述用户移动性。

2.2 服务提供算法

国内外对移动边缘计算环境中的服务提供方法的研究相关的工作大致如下：一是直接根据需要动态的放置边缘云，随着移动用户和请求服务的变化将边缘云迁移到合适的位置；二是在固定的边缘云上动态的放置服务；三是在放置边缘云或是放置服务时研究其中的优化工作。

移动边缘计算的实现首先需要搭建相关环境，配置软硬件设施，Yin等人^[8]使用一个为在线服务提供商提供边缘服务器的决策支持框架Tentacle，开发了一种新的方法来利用延迟进行排序实现了更有效的边缘配置，Wang等人^[9]解决了应用程序布置问题，在移动边缘计算环境中将一个线性应用图放置在树形物理图上，最大限度地减少物理节点和链路上的最大资源利用率。Xu等人^[10]使用整数线性规划解决了大规模无线城域网中的有容量限制的边缘云的放置问题。邓等人^[11]考虑边缘计算中的隐私信任与安全保障问题，针对用户应用需求特征，充分考虑用户体验质量(QoE)来优化边缘计算系统，实现了对应用场景的动态匹配。

根据移动用户的移动性迁移边缘云是一个平衡负载的解决方案，Xiang等人^[12]根据移动设备的地理位置研究了基于GPS大数据的自适应的边缘云放置方法，同时生成边缘云的迁移轨迹。Jia等人^[13]研究了无线城域网中放置边缘云并把边缘云分配给用户的问题，达到最小化边缘云的迁移时间的目的。

边缘计算环境中服务的放置的策略的研究的方面也有多个，Aral等人^[14]提出了一种分布式的副本放置方法——基于FLP的D-ReP，通过本地拓扑信息动态的创建/替换/删除副本。Khodashenas等人^[15]提出了一种放置算法，将构成网络服务的虚拟网络功能放置在可用的硬件基础架构中。

关于服务提供方法的优化的主要研究方面围绕以下几点：负载的预测，降低延迟和成本。芬兰的一个研究项目^[16]表明在边际网络中移动用户的信息需求模式在一定程度上可利用社交关系和设备间的通讯历史来预测；Wang等人^[17]研究了如何放置服务实例以应对移动用户的动态性，提出了一个离线的动态规划算法来在特定的预测窗口内解决由所有可能的配置形成的虚拟图中的最短路径问题。Yang等人^[18]从用户感知延迟和服务提供商的成本角度进行了服务的放置和负载的分配；杨仕豪^[19]讨论了将云中心的资源分布式存储在边缘节点上的最优的存储方案，使得用户获取的资源的路径最短和花费最少；Zeng等人^[20]设计了一个有效的任务调度和资源管理策略，最大限度地减少所有请求的总体计算和传输延迟来提升用户体验，它们被表述为混合整数非线性规划问题；Li等人^[21]研究了一种适用于动态自适应视频流的QoE驱动的移动边缘缓存布局优化问题，将它转换为一个具有一组背包约束的等价子模块最大化问题。

其他的相关研究还包括考虑到网络功能来部署服务，Taneja等人^[22]提出的资源感知的数据分析平台布局主要权衡的是网络成本，直接自适应的以最小化网络成本和用户响应时间为目的将分析平台部署在云上。Reason等人^[23]致力于解决提供移动边缘计算服务的小型小区多租户集群的虚拟网络功能布局问题，放置算法将鲁棒优化技术应用于系统的全局功耗最小化，这取决于网络服务的比特率和延迟限制。郭等人^[24]针对移动社交平台忽略网络状态、频繁刷新内容(文字、图片、视频等)造成的高能耗以及运算能力问题，提出一种边缘计算模式下基于Markov决策过程(Markov decision process, MDP)的能耗优化模型。

在上述的研究中，迁移边缘云虽然可以提高云上的资源利用率，但是这同时也意味着迁移服务器，对软硬件配置的要求过高，从服务提供商的成本角度来看成本也过高。现实情况下，在边缘云中放置和迁移服务更具有可以部署的实际意义。放置服务的策略主要取决于算法要达到的目标，在移动用户请求服务的延迟方面，现有的研究只是根据移动设备与服务之间的路径来计算传输延迟，而没有考虑到用户在移动的过程中，会在不同的边缘云中进行切换，而在这个过程中也会造成延迟；而负载的预测方法在现有的研究中建立的模型也较为简单，如动态规划、线性回归等，而负载的分布受多维变量的影响，因此可以使用深度学习的方法来更为准确的进行预测。

3 一种基于多用户概率移动模型的负载预测方法

3.1 问题描述

服务提供算法的基础是要获得各个区域内使用各个服务的负载。因此，本章建立了基于IMM的多用户概率移动模型，据此提出了一种基于多用户概率移动模型的负载预测方法。多用户概率移动模型的具体的变量定义如表3.1。

用户数量为M。将用户移动的位置划分为N个区域。本文拟在已知的M个用户的过去T时刻的位置的基础上，预测未来的T 1时刻，用户m处于区域i的概率，其中m∈M,i∈N。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：