摘 要

移动边缘计算是一种新的云计算模式，它利用小尺寸边缘云为用户提供实时服务。这些移动边缘云（MEC）位于用户附近，从而使用户能够无缝访问运行在MEC上的应用程序。由于核心（集中式）云，用户以及一个或多个MEC层的共存，一个重要的问题是决定放置应用的不同组件的位置（在哪个计算实体上）。 这个问题被称为应用程序或工作负载安置问题，是非常困难的，因此，没有性能保证的启发式算法通常被用于常规实践中，与最优解决方案相比，这可能在不知情的情况下遭受较差的性能。

本文着手解决了应用程序布置问题，提出了基于贪心算法的单个线性应用程序的计算模块在服务器节点上的放置问题。采用的数学模型是将用户应用程序的计算模块建模为线性应用程序任务图，将物理计算系统即服务器建模为物理图，我们考虑将时间片的任务节点部署到物理图上。另外还利用服务器物理图的连通性，提出应用程序计算模块在服务器上的分布式处理算法，对一段时间T内的发布的任务逐一处理，最终的目标函数是服务器处理任务的时间，以此来判断算法的优劣。其基础算法是贪心算法，这是一种基础的算法，原理也很简单，本文中是优先部署在服务器处理容量最大的服务器上。

本文提出的算法相对于其他算法，原理相对简单，主要的特点是体现在部署策略上。

关键字 云计算系统；移动边缘计算；在线放置算法；优化理论；分布式服务器

Abstract

Mobile edge computing is a new cloud computing mode, which provides real-time services for users with small size edge clouds. These mobile edge clouds (MEC) are located near users, enabling users to seamlessly access applications running on MEC. Due to the coexistence of the core (centralized) cloud, and the coexistence of one or more MEC layers, one important question is to determine the location of the different components of the application (on which computing entity). This problem is known as an application or work load placement problem, which is very difficult. Therefore, a heuristic algorithm without performance assurance is usually used in conventional practice, which may suffer worse performance than the optimal solution.

In this paper, we solved the problem of application layout, and proposed the placement of a computing module on a single linear application based on a greedy algorithm on a server node. We modeled the computing module of the user application into a linear application task map, modeling the physical computing system, the server, as a physical graph, and we consider deploying the task nodes of the time slice to the physical map. We also make use of the connectivity of the server physical map to propose a distributed processing algorithm for the application computing module on the server, which is processed one by one for a period of time in T, and the final target function is the time of the server processing tasks to judge the advantages and disadvantages of the algorithm. The basic algorithm is a greedy algorithm, which is a basic algorithm, and the principle is very simple. We are first deployed on the server with the largest server processing capacity.

Compared with other algorithms, the algorithm proposed in this paper is relatively simple, and the main characteristic is embodied in the deployment strategy.

Keyword cloud computing system;mobile edge computing;online placement algorithm optimization theory; Distributed server

目录

第一章 研究背景及意义 7

1.1 研究背景 7

1.2 研究意义 7

1.3 论文创新点 8

第二章 国内外研究现状分析 9

2.1 移动边缘计算 9

2.2 服务放置算法 10

第三章 一种基于贪心算法的服务部署策略 12

2.1 问题描述 12

3.2 系统模型 13

3.3 算法设计 14

3.4 仿真设计 15

第四章 总结及展望 17

4.1 论文总结 18

4.2 未来工作展望 18

4.3 致谢 18

参考文献 19

第一章 研究背景及意义

1.1 研究背景

依靠云计算环境的移动应用程序在近几年越来越流行。与仅在移动设备上运行的传统独立应用程序不同，基于云的应用程序具有运行在云中的一个或多个组件，它们连接到在手持设备上运行的另一个组件，并共同构成移动用户可访问的应用程序。基于云的移动应用的例子包括地图，存储和视频流服务。它们都需要高度的数据处理/存储能力，而这在单独的手持设备上是无法满足的，因此有必要在云中运行部分应用程序。

传统上，云位于集中式数据中心。因此，基于云的应用程序的一个问题是用户设备和云之间的远程通信可能导致间歇性连接和长时间延迟，不能满足新兴的交互式应用（如实时人脸识别和在线游戏）的需求。为了解决这个问题，最近提出了移动边缘云（MEC）。这个想法是在通信网络边缘部署小型云实体（即MEC），它可以运行部分或全部应用程序组件。这些MEC位于用户位置附近，使用户能够无缝且低延迟地访问云服务。

1.2 研究意义

随着虚拟技术的发展，云计算的优势越来越明显。云计算作为共有处理中心，它的核心是服务，它为应用程序服务，负责处理应用程序的任务并给予反馈。云计算系统又有三种类型的服务模式：软件即服务（SaaS）、平台即服务（PaaS）、基础设施即服务（IaaS）。从用户的需求方面考虑，云服务部署又分为公有云、私有云、社会云和混合云等，这些云的服务群体不同，其本质是一样的。云计算系统是通过云服务为用户提供云计算资源，不同的资源构建不同的服务套餐，这样可以为不同需求的人群提供更好的服务，因此设计合理的云计算服务部署方案于人们的生活工作息息相关，这也得到了广泛的关注。因为云计算资源有限，所以一种好的服务部署方案在在云计算的资源利用率及用户体验上就显得尤为重要。

云计算作为下一代信息技术的载体，其数据的存储、处理、分析、决策、任务的调度、资源的管理都在云中进行，而且其任务繁多、数据量巨大、用户需求不一、资源类型各异，因而对其资源部署与任务调度提出了新的更高的要求：既要满足用户对获取高质量服务的需求，又要尽可能地提高系统的资源利用率、保证服务提供商获得最大收益，从可持续发展和绿色环保的角度出发，还要保持高 效节能；^[1]所以资源部署与任务调度是云计算研究和实现中亟待解决的关键问题。针对数据中心普遍存在的资源利用率低、资源和能耗浪费严重的问题，服务部署方法的优化就尤为重要。

1.3 论文创新点

本课题的主要研究内容是关于应用程序的部署方案，以中心云、边缘云及用户端为物理节点，模拟出移动边缘计算环境的拓扑结构，应用程序节点与单一物理节点对应，接下来要做的就是求最优解了，即如何将这些应用节点部署在这些物理节点上。在云计算环境中服务是部署在虚拟机上的，因此它可以是一个多目标组合优化，这与移动边缘计算环境下的服务部署是不同的，它可以看成是一个物理图（即中心云、边缘云和用户），如下

图1：移动边缘云（MEC）的应用场景。 带有人脸识别应用程序的示例场景，其中虚线表示物理通信链接，红色箭头表示数据传输路径。

本课题是关注移动边缘计算语境，并提出用可证明的竞争比来解决在线应用程序布置问题的算法。本文中的算法建立在贪心算法的基础上，该算法为线性应用图的放置提供了很好的解决方案，优先布置在处理能力强的服务器上，这样可以让线性任务得到最好的解决办法。与云计算相比，这是一个重要的新颖事物，其中没有针对任何情况提出最佳解决方案。^[2]许多预期在移动边缘计算环境中运行的应用程序可以抽象为分层图形，这种分层图形的最简单情况就是一条线。因此，线性应用图的放置在移动边缘计算环境中的一个重要问题。与基于线性规划或其他的大多数方法相比，文章描述的工作中的另一个新颖之处在于，问题的解决方案可分解为多个小型构建块。这容易使得本文中提出的算法扩展到未来的分布式解决方案，这对于减少包含移动边缘计算的分布式云环境中不同云实体间必要的控制信息交换量是非常有益的。这个可分解的特征还使得这些算法更容易作为解决更大问题的子程序。本文使用的分析方法是基于传统的启发式的贪心算法，因此我们增强了一套工具在线优化。本文的理论分析也提供了有关问题的特点和难点的见解，可以指导未来的实际应用。另外，所提出的算法本身在实践中相对容易实施。

第二章 国内外研究现状分析

2.1 移动边缘计算

近年来，移动互联网和物联网得到了飞速发展，伴随而来的是各行各业的互联网 改革与新兴行业的不断涌现，这使得移动通信流量在过去的几年间经历了爆炸式增长，带来的就是通信服务的不断进步，移动终端（智能手机、平板电脑等）已经逐渐取代了个人计算机成为人们日常工作、学习、生活、社交、娱乐的主要工具。^[1]虽然移动终端直接访问云计算中心的方式很方便，但这也极大的增加了网络负荷，造成的网络延迟时间比较长，这对网络带宽、时延等性能提出了更高的需求。这时候，移动边缘计算就是的概念应运而生，它通过分布式边缘云系统，能很大程度上满足移动互联网和物联网的快速发展下所带来的高带宽、低时延等用户需求，有需求就有市场，因此，移动边缘计算的模式得到了学术界和产业界的广泛关注。

^[1]移动边缘计算即在距离用户移动终端最近的无线接入网内提供信息技术服务环境和云计算能力，旨在进一步减小延迟、提高网络运营效率、提高业务传送能力、优化终端用户体验。移动边缘计算可以被视为运行于移动网络边缘的云服务器，用以执行传统网络基础设施不能实现的特定任务。^[3]移动边缘计算架构包括三个部分，分别是边缘设备（例如智能手机、物联网设备、智能车等）、边缘云和远端云（或大规模云计算中心、大云）。其中边缘设备可以连接到网络；边缘云是部署在移动基站上的小规模云计算中心，负责网络流量控制（转发和过滤）和管控各种移动边缘服务和应用，也可以将其看作是在互联网上托管的云基础设施；当边缘设备的处理能力不能满足自身需求时，可以通过无线网络将计算密集型任务和海量数据迁移至边缘云处理，而当边缘云不能满足边缘设备的请求时，可以将部分任务和数据迁移至远端云处理。

移动边缘计算未来将为客户提供更多的服务，在物联网、人工智能方面将有很大的发展空间，这也需要良好的基础设施建设要求，而移动边缘计算的概念提出的时间并不长，许多理论和设备还并不是合乎要求。在移动边缘计算中，服务部署的研究就尤为重要。移动边缘计算有效的融合了无线网络和互联网这两个现代化技术，为了在其中植入应用，选择构建了开放式平台，它相比于传统的无线网络则是增加了计算、存储、处理等功能，并通过无线API开放无线网络与业务服务器之间的信息交互，对无线网络与业务进行融合，将传统的无线基站升级为智能化基站。面向业务层面（物联网、视频、医疗、零售等），移动边缘计算可向行业提供定制化、差异化服务，进而提升网络利用效率和增值价值。同时候移动边缘计算的部署策略（尤其是地理位置）可以实现低延迟、高带宽的优势。同时候移动边缘计算的部署策略（尤其是地理位置）可以实现低延迟、高带宽的优势。提出移动边缘计算是在物联网的大数据浪潮中，物联网的区域性和低延迟性的一个重要因素就是应用程序的部署。

2.2 服务放置算法

在传统的云计算系统中，应用程序的服务部署问题就是一个很重要的问题，也有好多学者提出了优秀的服务部署算法。而在移动边缘计算系统中，服务部署也显得尤为重要，毕竟在计算资源有限，服务延迟要求提高的情况下，有一个优秀的服务部署算法，能很好的提高用户体验。^[4]目前各种各样的数据密集型应用都有自己的数据部署与调度管理策略，在数据的部署阶段，主要关注对数据的建模分析，优化数据的部署，很少关注跨数据中心数据移动次数和数据移动量优化问题。而这些研究都没有关注于减少基于互联网的不同数据中心之间数据移动次数和数据移动量。现有的移动边缘计算的应用程序布置和调度工作已经考虑了两个组件，一个运行在云上（可以是边缘云或中心云），另一个运行在用户上。现有工作的另一部分，也称为“云卸载”，通常只涉及两个物理计算实体（即移动设备和云）。^[2]可以在一个或多个级别的边缘云和中心云中部署的多组件应用尚未被考虑，而这种应用在实践中广泛存在，因为边缘云服务器可以定位在多个不同层级的网络设备中。多组件应用程序布置问题主要在数据中心设置中进行研究。这个问题即使对于简单的图形也是很难，所以通常的做法是采用没有性能保证的启发式算法，与最优解相比，它可能在不知情的情况下遭受了糟糕的性能。只有非常有限的现有工作遵循近似算法和竞争分析的严格理论框架，并且提出了具有可证明的近似算法（即近似最优算法）问题，尤其是涉及节点和链接展示位置时。

^[10]传统的服务放置算法是启发式的，例如由意大利学者Dorigo、Maniezzo等人于20世纪90年代提出来的蚁群算法，它是通过模拟蚂蚁寻食来找到最优解的方案。作者在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。^[10]最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。^[10]蚁群算法搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率，其相对于其他生物进化算法，待确定的参数较少，易操作。

^[2]另外还有一些改进的算法，例如M. Chowdhury等人提出了一种在考虑负载均衡的情况下使总和成本最小化的算法，其近似比为O（N），其中N是物理图中节点的数量。该算法基于线性规划放松，并且只允许将每个应用图中的一个节点放置在特定的物理节点上，从而排除了一个应用图中不同节点间的服务器资源共享。结果表明，该算法的逼近率为O（N），这是微不足道的，因为当将整个应用程序图放置到单个物理节点上时，可以达到相同的近似比，而不是将其分布在整个物理图上。还有一些人提出了一种基于线性规划的方法，用于将数据中心网络中的路径置入树中。在这里，应用程序节点只能放置在树形物理图的叶子上，目标是最小化链路拥塞。在我们的问题中，应用程序节点分布在用户，边缘云和核心云中，因此它们不应该只放在树的叶子上，所以该文章中问题表述不适用于我们的场景。此外，这篇文章仅仅关注最小化链路拥塞。节点的负载均衡不被视为目标的一部分; 只考虑节点的容量限制。

其他一些相关的工作则侧重于图分区，其中物理图被定义为一个完整的图结构，其边缘成本与物理服务器之间的距离或延迟相关。这种抽象模型将多个网络链接组合成一个（抽象）物理边缘，这可能隐藏沿着路径的各个链接的实际状态。