英语原文共 14 页

移动边缘云网络的设计与优化

摘要

目前的研究主要关注的是将虚拟化服务器集群（也称为“云计算”或“边缘云”）集成到接入网络中，以允许在访问移动边缘计算服务时具有更高的性能和可靠性。我们解决了在移动接入网络中的边缘云网络设计问题。该模型使得虚拟机（VM）与移动用户相关联并被分配给边缘云。设计边缘云网络意味着首先确定在可用站点的合适位置安装边缘云，然后设置接入点（例如基站分配给边缘云），同时支持虚拟机编排并且考虑部分用户移动性信息，以及服务满意度级别协议。我们提出了由启发式支持的链路路径算法，以便在合理的时间内计算解决方案。我们的优势在于考虑用户和虚拟机的移动性，因为在服务等级协议中不满意的用户减少了20％，而设备只是略有增加。我们将两种虚拟机移动模式（批量和实时迁移）作为移动云服务要求的函数进行比较，确定应优先考虑实时迁移，而批量迁移似乎是延迟敏感的微型磁盘服务的可行替代方案，例如增强现实条件的支持，进一步放宽网络约束。

索引条目 - 移动边缘计算，云网络

第一章 介绍

移动设备在人们的日常生活中无处不在，近年来移动数据流量显著增长[2]。随着移动应用程序的发展，通信资源变得越来越匮乏。为弥合这一差距，可用边缘云计算扩展移动设备资源。为了应对远程云中心的高延迟，在[3]中引入了边缘云的概念，其中它被定义为可信赖的，资源丰富的计算机或与互联网连接良好的计算机集群，可供附近的移动设备使用。 边缘云代表虚拟机的容器：连接用户并与支持低延迟应用程序的虚拟机相关联。

边缘云概念受到[4]和[5]中提出的3层分层网络配置的支持。在此层次结构中，边缘云是用于增强移动设备功能的原始资源，而远程云用作最后的可用资源，或用于延迟容忍、资源密集型的应用程序。电信供应商和提供商对此类部署越来越感兴趣，在工业论坛和标准化机构中也被称为“移动边缘计算”解决方案（例如[6]，[7]）。

在本文框架中，我们关注移动接入网络中边缘云网络的潜在中等规划。据我们所知，这是文献中未经处理的问题。这包括安排从接入点到边缘云的所有虚拟化基础架构资源，以及将用户分配到边缘云。我们研究了两个设计案例：（i）网络处于静态状态;（ii）网络状态由用户移动性引起负载和服务水平的变化。在后一种情况下，我们设计了虚拟资源的编排，特别是跨边缘云的虚拟机编排，以便重新平衡系统。我们的贡献如下：

我们提供了一种链路路径混合整数线性规划算法，包含了用于表示位置的多项式规模变量和决策，以及指数规模的编码路由选择。

由于来自文献的启发式调整不能产生准确的结果，我们利用数学编程技术，结合列生成[8]，迭代舍入，局部搜索，超大规模邻域和问题分治，在合理的时间内实现了高质量的解决方案。

我们为移动接入网络的边缘云规划带来了新颖和独到的见解。通过对来自法兰西岛橙色网络的真实4G蜂窝网络数据集进行广泛的模拟，我们展示了考虑用户移动性对云网络的影响，并且通过两个设计案例来实现的决策：因为可以为180,000个用户规划尽可能少的13到26个边缘云，同时满足严格的延迟保证。我们通过在网络规划中考虑用户和虚拟机的移动性，表明服务等级协议中满意的用户数量显着增加，高达20％。我们还确定了两种不同虚拟机移动策略，即虚拟机批量和实时迁移。分别适用于两种移动云服务模型，这些服务在所需的延迟和内存特征水平上有所不同，比如增强现实和远程桌面。

为了能够复现我们的结果，我们公布了数据集特征的数值分布。

在[1]中，我们提供了移动边缘云网络设计问题的初步建模。在本文中，我们重新定义了模型，并提供了一种新的启发式算法，包括动态分解逻辑。此外，我们提供了更详细的结果，对策略和实现进行了更深入的分析。本文的结构如下：第二章介绍了背景；第三章介绍了云网络模型和相关的数学公式；第四章展示数据集；第五章报告实验结果；第六章包含简短的结论。

第二章 背景

使用边缘云对用户体验的好处在[9]-[11]中给出，其中作者比较了不同类型的应用程序在3层层次结构的不同层上的性能。Clinch等人表明[9]，应用程序放置可以显着影响性能和用户体验，使应用程序更接近用户。Ha等人表明[10]，通过分析实验结果得出，在严格的延迟限制条件下，边缘云比从大型数据中心整合计算资源更有优势。考虑到多跳Wi-Fi网络， Fesehaye等人表明[11]，当使用不超过两个无线跳数来传输数据时，基于边缘云的方法总是优于基于云的方法，而基于边缘云的方法最多可达到四跳，对于大多数情况来说，基于边缘云的方法是最好的方法。同时对无线链路的性质没有任何约束依赖：即使开创性的想法是通过Wi-Fi使用边缘云，虚拟化架构也是独立的。有关基于云计算的移动计算研究的更多内容可以在[12]中找到。

“微数据中心”或“模块化数据中心”的结构[13]-[15]，已经可以用于实施边缘云的硬件技术。欧洲电信标准化协会（ETSI）持续进行标准化工作，在[6]和[7]中提供了部署移动边缘云网络的技术要求，以及增强现实，互联网等用例的示例，比如物联网和数据缓存以及其他技术。在这项工作中，我们主要解决应用程序虚拟化而不是虚拟网络功能。

A、虚拟移动技术

在第三章D节中，我们处理网络的动态状态，以及其变化导致的不平衡和用户服务等级协议变化。为了重新平衡系统，我们在模型中考虑了从云端到云端的虚拟机移动性，考虑了现有技术中的三种虚拟机移动技术：

虚拟机批量迁移[16]：迁移整个虚拟机堆栈（包括磁盘和内存），长时间停止虚拟机以进行传输。

虚拟机实时迁移[17]-[19]：仅在传输最近使用的内存所需的少量时间内停止VM，不需要整个一次性磁盘传输，但源和目标之间的永久磁盘存储同步。

虚拟机复制[20]：包括源和目标位置之间的磁盘存储和内存的永久同步，不需要磁盘和最近使用的内存进行点传输。

我们假设虚拟机阵列以集中方式在Cloud Stack平台中执行。鉴于我们模型的主要目的是移动边缘云网络的中期决策，并且虚拟机业务流程的目的是提供正确的网络规模。因此，这种系统的实际实现超出了这项工作的范围，但是已经存在相关工作（例如，在OpenStack平台[21]，[22]中）。

B、移动边缘云网络拓扑

根据ETSI[6]，[7]中所说，我们应仔细设计计算资源在移动接入网络的分配，进一步考虑基础设施属性。移动接入网络可以是任何形式的无线接入网络，处理回程可以是有线基础设施，通过该基础设施可以互连边缘云。按照[23]-[26]中的指导原则，宽带接入和回程网络（如蜂窝网络）可以建模为两级分层网络：现场的接入点连接到聚合节点，然后是聚合节点连接到核心节点，如图1所示（为简单起见，我们在下文中将接入点称为AP）。 AP可以仅是Wi-Fi，仅是蜂窝网络，或者是这些常见移动接入技术的混合。边缘云可以合理地放置在现场、聚合点或核心级别，AP与其边缘云之间的连接可能跨越每个级别两次。通常采用AP，聚合节点和核心节点之间的各种物理互连网络拓扑：树形，环形或网状拓扑，以及中间混合拓扑。此外，随着4G的出现，存在进一步网状回传节点的趋势。从电路交换网络到运营商级分组交换网络，通常采用各种网络协议架构。这种体系结构的共同点是能够创建链路的虚拟拓扑，该链路直接互连同一级别的节点对，并保证隧道容量。如今，随着以传统电路交换方法为代价向分组交换运营商级解决方案的融合，伪电缆链路的比特率被设置为千兆以太网级别（通常为1或10 G bps）。

在此框架中，我们认为将移动边缘云网络建模为虚拟链路星形的叠加，以便将聚合节点互连到AP以及将核心节点互连到聚合节点，即使节点没有具体的物理设备也是合适的。如图1所示，在相同的虚拟链路配置趋势下，核心节点可以被视为通过虚拟链路的全网状拓扑相互连接的中心。据我们所知，将流量从一个AP划分为多个汇聚节点，从一个汇聚节点到多个核心节点，并不是回程网络中当前的主流做法；尽管如此，这些特征并不会显著改变我们在接下来的两节中描述的建模和启发式的本质。值得注意的是，将AP与聚合节点相关联并放置聚合节点的决策可以与动态重新编程蜂窝回程网络的当前趋势完全兼容[27]。同样，另一个自定义策略可以对放置给定边缘云的路由重新优化。此外，这些决策还可以在基于云的演进分组核心架构中实际嵌入关联和放置功能[28]。

第三章 移动边缘云网络模型

在下文中，我们给出了边缘云设计问题的正式定义，并提出了两种变体：

静态规划：网络状态被认为是静态的，在规划云端放置以及AP与边缘云的关联时，不考虑用户移动性和虚拟机移动性。

动态规划：规定时间范围内的网络负载变化与用户移动性一起考虑在内。自适应的虚拟机移动性以通用方式包含在内，考虑三种不同的技术：虚拟机批量迁移，虚拟机实时迁移和虚拟机复制。

A、问题描述

我们的模型同时关注两方面：（i）最佳网络设计，包括云端放置和将AP分配给边缘云，以及（ii）从用户到达边缘云的最佳路由。其主要目的是提供最佳设计政策的一些见解，而不是运营规划。从实际角度来看，将云计算放置在某个位置可能意味着打开已安装的服务器，而不是安装新计算机。类似地，将AP改变为云分配实际上将对应于通过传输网络基础设施重新规划路由虚拟链路，而不是物理地改变互连结构。如果重视用户的服务水平协议，我们认为解决方案是可行的。最佳可行解决方案可最大限度地降低总体开销。

从理论和计算的角度来看，我们的问题都很难解决。从理论上讲，它是服从NP-Hard问题的，概括了传统的无容量设施定位问题及其容量和单源变体问题。在计算方面，它正处于文献中当前未调查的最前沿[29]：当考虑多达两个设施级别时，最先进的方法是可行的，但在我们的模型中，路由优化，延迟界限和第三个位置级别必须包括在内。

在下文中，我们介绍了网络设计的基本模型（在第三章B节中）；然后我们在添加路由方面先由SP的近似方法完成它们。最后，我们讨论了这种建模如何扩展到DP的近似方法。

B、网络设计

输入（问题数据）：我们假设已经为网络设施确定了一组合适的设置。正式地，让B作为AP位置的集合。I，J和K分别表示聚合节点，核心节点和边缘云节点的集合。Esube;（Btimes;I）cup;（Itimes;J）cup;（Jtimes;J）表示一组节点之间的可行链接。设li，mj，ck分别是iisin;I聚合节点，jisin;J核心节点和kisin;K边缘云节点中的固定成本。

输出（决策变量）：我们引入两组变量。第一组对应于位置二元变量：如果存储在聚合节点，则xi取值1；如果存储在核心节点，则yj取值1；如果存储在边缘云节点，则zk取值1。第二组对应于网络拓扑二进制变量：如果在AP和聚合节点之间建立链路，则st取值1；如果在聚合节点和核心节点之间建立聚合链路，则wi，j和wj同时取值1；如果在两个核心节点m和n之间建立核心链路，则om取值为n。为了模拟已经存在或禁止的链接，相应的变量可以分别为固定为值1和0。

目标功能：我们的主要目的是MEC网络设计，模型目标（1）是最小化所有网络设施的安装成本。 我们不包括链路安装成本，因为我们没有考虑蜂窝基础设施的大小。

约束：在链路排列方面，完整的MEC网络拓扑是我们模型的副产品。正如第第二章B节中所规定的那样，我们将这个网络建模为星型的叠加：这必须作为拓扑规则，这限制了由此产生的链路排列。每个AP连接到单个聚合节点，每个聚合节点连接到单个核心节点（如图1所示），而在核心之间构建全网状。以下约束集合使建模强制执行我们的拓扑规则：每个链接（i，j）只能用于一个目的（即AP，聚合或核心）-（2）；聚合链接必须是对称的-（3）；核心节点和云节点也是聚合节点-（4）和（5）；if（i，j）是AP链路，则j是聚合节点-（9），而if（i，j）是聚合链路，则i是聚合节点-（10）；如果（i，j）是聚合链路，则i或j是核心节点-（11），并且类似地如果（i，j）是核心链路，则i和j都是核心节点-（12），相反如果i和j都是核心节点，（i，j）是核心链路-（13），而且在核心链路上没有考虑循环-（8）;当选择作为聚合时，每个AP连接到其自身，否则连接到不同的节点-（6）和（14）；每个聚合节点具有相邻的聚合链路，从而连接到核心节点-（15），其可以是节点本身-（7），最多一个聚合链路可以连接到非核心节点（yi = 0），而任意数字可以连接到核心数字（yi = 1）-（16）。

第四章 总结

我们首次在现有技术中为移动接入城域网提供了全面的移动边缘云网络设计框架。 我们正式定义了这个问题，包括两个规划模型：（i）考虑网络的静态状态，不知道规划期间的变化，以及（ii）考虑动态网络，包括负载变化和用户和虚拟机的移动性，结合三种不同的虚拟机移动技术。

我们对构建的蜂窝网络数据集进行了广泛的不同规划选项的比较，区分了参考移动云服务的不同流量工程和性能目标，分析：（i）网络设施资源的使用，即启用的边缘云数量，边缘云资源的使用情况 ，迁移量和（ii）符合用户的用户服务等级协议。作为结论，我们可以说：

考虑到用户的移动性和网络的动态变化，我们保证完全符合用户的用户等级协议，但是从建模中排除了高达20％反用户服务等级协议情况；

考虑到用户移动性，所给出的网络资源最多使用5个用于服务600个AP，用于巴黎城域网例子（在实际交通日志上）；

同时考虑网络设计，AP和边缘云之间的关联，以及路由需要遵守的有限资源和用户的用户服务等级协议：使用启发式方法将这些设计决策分离导致用户体验提高27％；

比较虚拟机实时迁移和虚拟机批量迁移技术，已经证明前者有资格作为延迟关键和延迟敏感的移动云服务，而后者需要占用大量的网络资源，只有在要同步的虚拟机文件很小时满足要求。

我们相信所提供的方案可以激发对移动云网络和移动边缘计算这一新兴研究领域的进一步研究，特别是在线路由和云迁移策略领域，如[27]和[41]所述。未来的工作大概如下，使用多个（可能是预安装的）云端设施解决多个虚拟

资料编号：[3582]