英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料
在边缘计算环境中的多组件应用的在线放置
摘要：移动边缘计算是一种新的云计算模式，它利用小尺寸边缘云为用户提供实时服务。 这些移动边缘云（MEC）位于用户附近，从而使用户能够无缝访问运行在MEC上的应用程序。 由于核心（集中式）云，用户以及一个或多个MEC层的共存，一个重要的问题是决定放置应用的不同组件的位置（在哪个计算实体上）。 这个问题被称为应用程序或工作负载安置问题，是非常困难的，因此，没有性能保证的启发式算法通常被用于常规实践中，与最优解决方案相比，这可能在不知情的情况下遭受较差的性能。 在本文中，我们解决了应用程序布置问题，并着重于开发具有可证明性能界限的算法。 我们将用户应用程序建模为应用程序图，将物理计算系统建模为物理图，并在这些图上注释资源需求/可用性。 我们首先考虑线性应用图的布局，并提出一个算法来寻找它的最优解。 利用这个结果，我们将这个公式推广并且获得具有多项式对数（poly-log）竞争率的在线近似算法用于树应用图布置。 我们共同考虑节点和链路分配，并将多种类型的计算资源包含在节点中。
索引术语：云计算，图形映射，移动边缘云（MEC），在线逼近算法，优化理论。
- 介绍
依靠云计算的移动应用程序在近几年越来越流行[2]，[3]。 与仅在移动设备上运行的传统独立应用程序不同，基于云的应用程序具有运行在云中的一个或多个组件，它们连接到在手持设备上运行的另一个组件，并共同构成移动用户可访问的应用程序。 基于云的移动应用的例子包括地图，存储和视频流服务[4]，[5]。 它们都需要高度的数据处理/存储能力，而这在单独的手持设备上是无法满足的，因此有必要在云中运行部分应用程序。
传统上，云位于集中式数据中心。 因此，基于云的应用程序的一个问题是用户设备和云之间的远程通信可能导致间歇性连接和长时间延迟，不能满足新兴的交互式应用（如实时人脸识别和在线游戏）的需求[6]。 为了解决这个问题，最近提出了移动边缘云（MEC）[7]，[8]。 这个想法是在通信网络边缘部署小型云实体（即MEC），它可以运行部分或全部应用程序组件。 这些MEC位于用户位置附近，使用户能够无缝且低延迟地访问云服务。 例如，他们可以与边缘设备（如Wi-Fi接入点或蜂窝基站（BS））共同定位，如图1所示，与集中式云和移动设备用户一起形成一个层次结构
图1.移动边缘云（MEC）的应用场景。 带有人脸识别应用程序的示例场景，其中虚线表示物理通信链接，红色箭头表示数据传输路径。
MEC的概念与cloudlet [9]，fog computing [10]，[11]，follow me cloud [12]和small cell cloud [13]类似。虽然MECs很有前途，但也有局限性。尤其是，与核心（集中式）云相比，它们的处理和存储能力要低得多，因此完全放弃核心云并在MEC上运行所有内容通常是不可行的。 因此，一个重要的问题是决定在哪里（即核心云，MEC或移动设备上）放置应用程序的不同处理和存储组件。 这被称为应用程序布置问题，这是一个不平凡的问题，如下面的例子所示。
A、举例
考虑一个应用程序，该应用程序可识别手持设备的摄像头拍摄的实时视频流中的人脸。如图1所示，我们可以将此应用程序分解为一个存储组件（数据库）和三个不同的处理组件，包括人脸检测（FD），图像处理和特征提取（IPFE）以及人脸识别（FR）。FD组件查找包含人脸的图像区域（视频流的一帧）。这部分图像被发送给IPFE进行进一步处理。IPFE的主要工作是滤除图像中的噪声并提取用于从人脸识别人的有用特征。这些特征被发送到FR以与数据库中存储的大量不同人脸的已知特征相匹配。
图1显示了FD，IPFE，FR和数据库在分层云架构上的一种可能的布局。在某些情况下，这可能是一个很好的位置，但在其他情况下可能不是一个好位置。例如，在移动设备上运行FD而不是在MEC上的好处是，它减少了需要在移动设备和MEC之间传输的数据量。但是，在移动设备的处理能力受到严格限制但移动设备与MEC之间存在合理高带宽连接的情况下，在MEC上放置FD可能会很好。将数据库放在核心云中可能是有益的，因为它可能包含大量不可用于MEC存储的数据。在这种情况下，FR也应该位于核心云中，因为它需要经常查询数据库。但是，如果数据库相对较小并且具有本地生成的内容，我们可能希望将数据库和FR放置到MEC而不是核心云，因为这可以减少回程网络负载。
我们看到，即使使用这个简单的应用程序，在概念上找到最佳位置也是非常简单的，而流媒体，多播和数据聚合等许多现实应用程序要复杂得多。我们还注意到，MEC可以连接到不同蜂窝网络层上的设备[8]，产生具有三层以上的分层云结构。同时，通常存在多个在云系统上随时间推移实例化的应用程序。所有这些方面都促使我们在严格的优化框架中考虑应用程序布置问题，在这种框架中，应用程序以在线方式到达，即它们随着时间的推移而顺序到达，并且我们不知道任何时间点的未来应用程序的特性。
我们将应用程序放置问题抽象为将表示应用程序组件和这些组件之间的通信的应用程序图表放置到物理图形上，该图形表示物理系统中的计算设备和通信链接，如图2所示例如，上面的人脸识别应用程序可以抽象为一个应用程序图，其中四个节点以链（线）连接，其中每个节点按顺序表示数据库FR，IPFE和FD。详细的问题表述将在第二部分介绍。
- 相关工作
现有的MECs应用程序布置和调度工作已经考虑了两个组件，一个运行在云上（可以是MEC或核心云），另一个运行在用户上[12]，[17] - [19 ]。 现有工作的另一部分，也称为“云卸载”，通常只涉及两个物理计算实体（即移动设备和云）[20] - [22]。 可以在一个或多个级别的MEC和核心云中部署的多组件应用尚未被考虑，而这种应用在实践中广泛存在，因为MEC服务器可以定位在多个不同层级的网络设备中[8]。
多组件应用程序布置问题主要在数据中心设置中进行了研究。 由于这个问题即使对于简单的图形也是NP难的（我们将在后面讨论），通常的做法是采用没有性能保证的启发式算法[23,24]，与最优解相比，它可能在不知情的情况下遭受了糟糕的性能。 只有非常有限的现有工作遵循近似算法[25]和竞争分析[26]的严格理论框架，并且提出了具有可证明的近似/竞争比1的近似算法（即近似最优算法）问题，尤其是涉及节点和链接展示位置时。
在文献[27]中，作者提出了一种在考虑负载均衡的情况下使总和成本最小化的算法，其近似比为O（N），其中N是物理图中节点的数量。该算法基于线性规划（LP）放松，并且只允许将每个应用图中的一个节点放置在特定的物理节点上; 从而排除了一个应用图中不同节点间的服务器资源共享。结果表明，该算法的逼近率为O（N），这是微不足道的，因为当将整个应用程序图放置到单个物理节点上时，可以达到相同的近似比，而不是将其分布在整个物理图上。
在[28]中的一项理论工作提出了一种具有NO（d）时间复杂度和近似比率为delta;O（D2log（ND））的算法，用于将具有D级节点的树应用图放置到物理图。它使用LP放松，其目标是最小化总和成本。基于这种算法，作者提出了一种在线算法，用于最小化每个节点和链路上的最大负载，即O（delta;log（N）） - 当应用寿命相等时具有竞争性。 [28]中的LP公式是复杂的，需要NO（d）个变量和约束。这意味着当D不是常数时，空间复杂性（指定算法所需的内存大小）在D中是指数的。
=
[29]报道了另一个相关的理论工作，它提出了一种基于LP的方法，用于将数据中心网络中的路径置入树中。在这里，应用程序节点只能放置在树形物理图的叶子上，目标是最小化链路拥塞。在我们的问题中，应用程序节点分布在用户，MEC和核心云中，因此它们不应该只放在树的叶子上，所以[29]中的问题表述不适用于我们的场景。此外，[29]仅关注最小化链路拥塞。节点的负载均衡不被视为目标的一部分; 只考虑节点的容量限制。
其他一些相关的工作则侧重于图分区，如[30]和[31]，其中物理图被定义为一个完整的图，其边缘成本与物理服务器之间的距离或延迟相关。 这种抽象将多个网络链接组合成一个（抽象）物理边缘，这可能隐藏沿着路径的各个链接的实际状态。
最近出现的一个相关问题是服务链嵌入问题[32] - [34]。 受网络功能虚拟化（NFV）应用程序的驱动，目标是在固定的源和目标物理节点之间放置一个线性应用程序图，以便对从源发送到目标的数据包执行一系列操作。 在这个工作体系中，只有[34]研究了在线投放的竞争比率，但是，这并没有考虑链接布局优化。
需要注意的一个重要方面是，大多数现有的工作，包括[27]，[29] - [33]，都没有具体考虑算法的在线操作。 尽管其中一些人隐含地声称可以对每个新到的应用程序重复应用该算法，但这种程序的竞争比例还不清楚。 据我们所知，
[28]是唯一研究考虑节点和链接布局的在线应用程序布局问题的竞争比率的工作。
A.我们的方法
在本文中，我们关注MEC语境，并提出用可证明的竞争比来解决在线应用程序布置问题的算法。 与[28]不同，我们的方法不是基于LP放松。 相反，我们的算法建立在基线算法的基础上，该算法为线性应用图的放置提供了最佳解决方案（即应用图是线）。 与[28]相比，这是一个重要的新颖事物，其中没有针对任何情况提出最佳解决方案。 许多预期在MEC环境中运行的应用程序可以抽象为分层图形，这种分层图形的最简单情况就是一条线，例如IA部分中的人脸识别示例。 因此，线性应用图的放置是MECs环境中的一个重要问题。
与[28]和基于LP放宽的大多数其他方法相比，我们工作中的另一个新颖之处在于，我们的解决方案可分解为多个小型构建块。 这使我们很容易将我们提出的算法扩展到未来的分布式解决方案，这对于减少包含MEC的分布式云环境中不同云实体间必要的控制信息交换量是非常有益的。 这个可分解的特征还使得这些算法更容易作为解决更大问题的子程序。
同样值得注意的是，本文使用的分析方法与现有的LP放松技术相比是新的，因此我们增强了一套工具在线优化。 本文的理论分析也提供了有关问题的特点和难点的见解，可以指导未来的实际应用。 另外，所提出的算法本身在实践中相对容易实施。
图3.使用和不使用周期的映射。 在此示例中，应用程序图中的路径位于应用程序节点1和应用程序节点5之间
- 主要结果
本文提出了基于非LP的在线应用程序的近似算法。 应用程序布局的一般问题很难近似[28]，[29]，[32]，[35]。 例如，[32]已经表明理论上，对于考虑线性应用图和一般物理图的业务链嵌入问题，不存在具有有界逼近比的多项式时间近似算法，并且具有节点和链路容量约束。 因此，类似于相关工作[27] - [34]，我们做了一些简化，以使问题易于处理。 这些简化是由逼真的MEC设置驱动的，其动机描述如下。
在整篇文章中，我们关注具有树拓扑的应用和物理图。 这是由于考虑到树应用程序图模拟了广泛的MEC应用程序，这些应用程序涉及一组分层的进程（或虚拟机），包括流，多播和数据聚合应用程序[14] - [16]，如前面介绍的示例性人脸识别应用程序。 对于物理系统，由于MEC环境的层次特性，我们考虑树形物理图（见图1）。 我们注意到，我们在本文中提出的算法也适用于几类非树图，第六部分将给出一个例子。 为了便于演示，本文主要关注树形图。
在树形应用图中，如果我们考虑从根到叶的任何路径，我们只允许这些分配2，沿着这条路径的应用程序节点按物理拓扑的子路径上的各自顺序分配（多个应用程序节点仍然可以放置在一个物理节点上），从而创建一个“无周期”的布局。 图3说明了这个位置。 设节点1到5表示应用程序图拓扑中沿着路径的应用程序节点。 将此路径无周期地放置到物理网络的子路径上可确保顺序得以保留（如图3（b）所示），而顺序未保留在图3（c）中。 无周期布局具有避免应用程序节点间循环通信的明确动机。 例如，对于图3（c）中的放置，应用节点2和4放置在物理节点B上，而应用节点3放置在物理节点C上。在这种情况下，物理链路B-C携带数据应用程序链接2-3和3-4以循环方式。 这种流量可以通过无周期映射自然避免（图3（b）），从而减轻通信链路的拥塞。 正如我们将在模拟中看到的那样第五部分，无周期约束条件仍然允许所提出的方案超越其他一些允许周期的可比较方案。 附录A给出了与无周期限制相关的近似比的进一步讨论。本文中，为了描述算法，我们将一个应用程序节点分类为树形应用图中的一个节点节点，当它具有两个或更多儿童。 这些联结节点可以代表多个数据流的数据拆分或加入过程。 在某些情况下，它们可能有预先指定的放置位置，因为它们提供可能与不同最终用户相关联的多个数据流，并且各个数据流可能以在线方式动态到达。 我们的工作首先考虑所有连接节点（如果有）的位置是预先指定的情况，然后将结果扩展到一般情况下，一些连接节点没有预先放置。 线性应用程序图（例如IA部分中的示例性人脸识别应用程序）没有连接节点，因此属于第一种
类别。
对于上述场景，我们针对以物理节点和边缘之间的负载均衡为目标的应用程序放置问题获得以下主要结果：
-
- 一种用于放置具有O（V3N2）时间复杂度和O（VN（VN））空间复杂度的线性图的单个应用图的最佳离线算法，其中应用图具有V节点物理图形有N个节点。
-
-
用于放置单个或多个树形应用图的在线近似算法，其中预先指定了所有交汇点的布局，即给出了它们的布局。 该算法具有O（V3N2）的时间复杂度和O（VN（V
全文共33163字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14940]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
-
用于放置单个或多个树形应用图的在线近似算法，其中预先指定了所有交汇点的布局，即给出了它们的布局。 该算法具有O（V3N2）的时间复杂度和O（VN（V
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
