选择目标微云以最大程度地减少服务延迟

任子斌

(东华大学 计算机科学与技术学院， 上海 201620)

0 引 言

近年来，移动设备在人们的日常生活中无处不在[1]。这些移动设备受资源限制，并且通常使用云资源来满足其计算要求。许多移动应用程序对延迟敏感，就像增强现实和交互式游戏[2]一样，需要低服务延迟。然而，这些应用程序的延迟要求无法通过传统云的架构[3]来得到满足。这个问题引起了研究者和用户更多的关注与重视。

在文献[4-5]中提出了移动边缘计算，以满足移动用户这些需要超低延迟的应用程序。为了便于托管延迟敏感应用程序，边缘计算节点被认为实现了快速资源响应的优先级[6-7]。边缘计算旨在将云功能推送到网络边缘，此外还提供低延迟[8]。

在智能城市中，具有任意移动性的用户设备给选择边缘计算的目标微云带来了新的挑战[9-11]。为了提供低延迟服务，在考虑用户位置时尽可能选择为用户提供最低延迟的微云是一个颇具挑战性的难题[12]。为了解决这个问题，本文根据用户的位置提出了一种目标微云选择方案、即最低局部延迟算法。该算法考虑了传输时间、计算时间、选择时间和用户在目标微云选择过程中的位置。对不同网络状况进行仿真，以评估本文提出的算法的性能。将本文提出的算法与现有算法进行了比较。仿真结果表明，该算法为移动用户提供了更低的服务延迟。

1 资源分配技术研究现状

随着用户的移动，现有的一些算法诸如：设备与AP接入点之间的最短距离算法、设备与微云之间的最短距离算法、最低延迟算法，虽然能够在一定程度上满足用户延迟需求，但总体用户的满意度仍不理想，因此，本文提出了局部最低延迟算法。

2 面向移动用户的最优微云选择机制与算法设计

在本节中，微云和AP接入点在网络中均匀分布。每个AP接入点都覆盖一个半径为R的区域。位于AP接入点的覆盖区域圆圈中的用户可以直接与AP接入点通信。AP接入点通过相邻的AP接入点与不在其覆盖区域的微云进行通信。网络中有一个微云控制中心，记录着网络的一些重要信息，例如网络中的微云数量、每个微云的可用资源、每个用户的位置以及每个AP接入点和微云的位置。所有微云和用户都可以通过AP接入点与微云控制中心通信，以更新或接收信息。每个微云可以实时监控其剩余可用的资源，并将这些信息发送到微云控制中心。每个用户都通过GPS确定其位置，并将位置信息发送到微云控制中心。

当移动用户生成需要微云服务的任务时，移动用户将连接到AP接入点并通过AP接入点将任务传输到微云。由于网络中的用户是移动的，微云控制中心应根据用户的位置为用户选择合适的AP接入点和服务微云，如此即可为用户提供低延迟的服务。根据用户位置为用户分配合适的AP接入点和服务微云从而最小化总服务延迟是本节的主要研究目标。

针对于目前三种算法，本文提出了局部最低延迟算法，局部最低延迟算法具体实现伪代码详见如下。

算法1 局部最低延迟算法

mark destination cloudlet for taskjas null;

get the nearestAPto the user, and denote the nearestAPasAPm;

letAPmbe the newAPfor the user;

letsAPmdenote the set of cloudlets in the coverage area ofAPm;

for each cloudlet insAPmdo

update service latencyτsi,u,si∈sAPm,i=1,2,...,|sAPm|;

end for

get the smallestτsi,ufrom {τs1,u,τs2,u,...,τs|APm|,u}, and denote the cloudlet which has the smallestτsi,uassm;

let the cloudletsmas the destination cloudlet;

对上述算法进行剖析后详述如下：如果微云控制中心收到用户的资源分配请求，微云控制中心将运行迁移策略4，将给用户分配连接的AP和服务微云。研究时将用户表示为u，每个AP接入点的覆盖半径为R的圆形区域。首先，获取最接近用户的AP接入点，并将此AP接入点表示为APm(请参阅第2行)。让APm成为用户的新接入的AP(见第3行)。让sAPm表示APm覆盖区域中的微云的集合(见第4行)。sAPm中的所有微云都可以与APm直接通信。然后，算法更新每个微云si(si∈sAPm,i=1,2,...,|sAPm|)和用户u之间的服务延迟τsi,u(请参阅第6～9行)，其中|sAPm|表示sAPm中的微云的数量。然后，从{τs1,u,τs2,u,...,τs|APm|,u}集合中选择的最小的τsi,u并表示成sm(请参见第10～12行)。最后，该算法将sm作为任务j的目标微云(见第13行)。

3 仿真实现

在本节中，将提出的最低局部延迟算法与现有算法进行比较，即设备与AP接入点之间的最短距离算法、设备与微云之间的最短距离算法以及最低延迟算法。所有仿真均使用iFogSim[13]在英特尔酷睿i5处理器(2.7 GHz)上执行。iFogSim是一个模拟框架，用于建模和模拟云计算基础设施和服务。

在本文的模拟中，使用了200×200公里区域。此区域中有一个移动用户。研究中为用户设置了8个移动方向。用户在实验开始时随机选择一个方向。用户在实验过程中不会更改其移动方向。用户的移动速度为19 m/s。每个微云服务器的处理器速度是每秒2 800万条指令(MIPS)，即vcloudlet=2 800 MIPS。网络中有400个微云和930个AP接入点。微云均匀分布，且相互间隔为10 Km, 即dcloudlets=10 Km，AP接入点均匀分布，且相互间隔为6.5 Km, 即dAPs=6.5 Km。每个AP接入点的覆盖范围为5 Km，即R=5 Km。模拟时间是1 h。用户每隔20 s生成一个任务。任务的上传数据大小为1 KB，任务的下载数据大小为1 KB。用户和AP接入点之间的上行带宽为每秒100 Mbps，用户和AP接入点之间的下行带宽为2 Mbps。

研究中比较了3个不同网络环境中的4种算法，即：微云和AP接入点之间的带宽均匀分布在10～20 Mbps之间；微云和AP接入点之间的带宽均匀分布于90～100 Mbps之间；微云和AP接入点之间的带宽均匀地分布在990～1 000 Mbps之间。

4 实验结果与分析

本节以服务延迟为性能指标对不同的迁移策略进行仿真实验，不同微云和AP接入点之间带宽不同的仿真结果分别如图1～图3所示。从图1中可以看到，迁移策略4的服务延迟(即最低的本地延迟算法)是最低的。尽管迁移策略1选择最接近用户的AP接入点并选择距离所选AP接入点最近的微云以向用户提供服务，但微云和用户可能不是距离最短的。因此，传输时间可能不是最短的。此外，迁移策略1在目标微云选择过程中不考虑微云的处理时间。因此，迁移策略1的服务延迟是最大的。为了最大程度地缩短微云和用户之间的传输时间，迁移策略2选择最接近用户的微云作为目标微云。因此，传输时间缩短。从图1也可以看出，迁移策略2的服务延迟小于迁移策略1的服务延迟。尽管迁移策略2选择的目标微云是最接近用户的微云，但考虑到网络拥塞，传输时间可能不是最短的时间。此外，迁移策略1和迁移策略2 在微云选择过程中不考虑微云选择时间，这可能会增加服务延迟。为了提供低服务延迟，迁移策略3选择服务延迟最短的微云作为目标微云。因此，可以减少迁移策略3的服务延迟。由图1可知，迁移策略3的服务延迟小于迁移策略1和迁移策略2的服务延迟。但是，要获得每个微云提供的服务延迟，迁移策略3应计算网络中所有微云的服务延迟，对于具有大量微云的网络，这尤其会增加选择时间。为了最小化选择时间，迁移策略4仅计算用户附近微云提供的服务延迟。综合前文分析后，并参见图1可知，迁移策略4的服务延迟最低。这是因为迁移策略4在目标微云选择过程中同时考虑传输时间、计算时间和选择时间。

图1 当带宽较小时各种迁移策略的服务延迟

Fig. 1 Service delay for various migration strategies when bandwidth is small

从图2和图3中，还可以看到迁移策略4的服务延迟最低。与其他三种算法相比，迁移策略是目标微云选择的最佳算法，该算法在考虑用户的移动的同时，提供了最低的服务延迟。

图2 当带宽较中等时各种迁移策略的服务延迟

Fig. 2 Service delay for various migration strategies when bandwidth is moderate

图3 当带宽较大时各种迁移策略的服务延迟

Fig. 3 Service delay for various migration strategies when bandwidth is large

5 结束语

本文研究了目标微云的选择问题。提出了最低局部延迟算法，为移动用户提供低服务延迟。在此算法中，在目标微云选择过程中考虑了传输时间、计算时间、微云选择时间和用户位置。研究中还进行了广泛的模拟，以证明最低局部延迟算法的有效性。对于未来的工作，将重点讨论移动用户的一组云子选择和 VM 选择问题。