云边结合环境下基于海鸥优化算法的移动服务选择方法

摘要

本发明涉及服务选择技术领域，具体涉及一种云边结合环境下基于海鸥优化算法的移动服务选择方法，包括输入服务存储库中带QoS属性的服务；移动用户将任务请求上传至服务器；初始化海鸥种群，计算初始海鸥种群中最优海鸥的位置，对最优海鸥的位置进行迭代运算，直到达到最大迭代次数；将迭代得到的最优海鸥的位置所对应的候选服务输出；迭代运算包括：对每只海鸥的位置进行更新；根据适应度函数计算当前迭代种群中最优海鸥的位置P

说明书

技术领域

本发明涉及服务选择技术领域，具体涉及一种云边结合环境下基于海鸥优化算法的移动服务选择方法。

背景技术

近年来，移动应用设备的广泛普及导致了对云计算和边缘计算的巨大需求。移动设备中的应用，如自然语言处理、面部识别和视频处理，对延迟敏感，需要大量计算。MEC(Mobile Edge Computing,移动边缘计算)通过对靠近原始数据源的网络边缘的数据进行处理来优化云计算。预计这将缓解移动设备资源短缺的问题。拥有轻量级技术的服务可以为移动设备提供资源，这也使得用户可以在短时间内访问不同的服务，提高问题处理的效率。通过在移动用户附近部署和执行服务，MEC可以大大减少服务响应时间，减轻核心网络的通信负载，减少网络拥塞。如何为多个任务选择最优服务可以被建模为一个多目标优化问题，目前一种解决方案是使用进化算法，遗传算法、蚁群算法、粒子群优化算法、布谷鸟搜索算法以及海鸥优化算法等已经被广泛的使用，这类算法模拟了生物的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断的改变搜索方向，从而找到最优食物。而海鸥优化算法通过模拟海鸥的觅食行为，通过迁徙和攻击的方式最终捕获猎物，同时，种群中所有海鸥个体还需要避免进行碰撞。通过位置的不断更新，最终找到猎物的攻击位置，即产生最优解。

受自然界海鸥迁移和攻击行为的启发，海鸥优化算法是一个蜂群智能优化算法，并广泛应用于滚动轴承生产等方面。如何将海鸥优化算法的优势应用于云计算的多目标优化中，以解决现有各算法的缺陷，是一个值得解决的问题。

发明内容

本发明的目的就是针对现有技术的缺陷，提供一种云边结合环境下基于海鸥优化算法的移动服务选择方法，将海鸥优化算法与模拟退火算法结合，可以高效的找到全局最优解，为解决多目标优化问题提供更加可靠的保障。

本发明提供一种云边结合环境下基于海鸥优化算法的移动服务选择方法，包括：

输入服务存储库中带QoS属性的服务；

将用户发布的任务请求上传至服务器；

根据上传的任务初始化海鸥种群，并计算初始海鸥种群中最优海鸥的位置，所述海鸥的位置代表每个任务所选择的一组候选服务；

对最优海鸥的位置进行迭代运算，直到达到最大迭代次数；

将迭代得到的最优海鸥的位置所对应的一组候选服务输出；

所述迭代运算包括：

采用海鸥优化算法对每只海鸥的位置进行更新；

根据适应度函数计算当前迭代种群中最优海鸥的位置P

调用模拟退火算法在位置P

较为优选的，所述采用海鸥优化算法对每只海鸥的位置进行更新包括：

计算海鸥的迁徙位置

A＝f

B＝2×A

计算海鸥的攻击位置，包括

x＝r×cos(α)；

y＝r×sin(α)；

z＝r×α；

r＝u×e

其中，f

较为优选的，在输出候选服务时，还输出候选服务的总体响应时间，所述总体响应时间为上传时间、响应时间和下载时间之和。

较为优选的，还包括

构建云服务器和边缘服务器，将已经输入的候选服务随机的分布到云服务器和边缘服务器上；

根据移动用户当前位置计算所有信号范围覆盖用户的边缘服务器，计算用户与边缘服务器之间的距离，并判断距离最近的服务器；

若处理第一个任务的候选服务位于云服务器上，则用户发布的任务先上传到离用户最近的边缘服务器上，再由离用户最近的边缘服务器上传到云服务器；

若处理第一个任务的候选服务位于第一边缘服务器上，且所述第一边缘服务器为离用户最近的服务器，则用户发布的任务直接上传至所述第一边缘服务器；

若处理第一个任务的候选服务位于第一边缘服务器上，且离用户最近的服务器为第二边缘服务器，则计算用户发布的任务直接上传至第一边缘服务器所需的第一时长和先将用户发布的任务上传至第二边缘服务器，再由第二边缘服务器上传至第一边缘服务器所需的第二时长，将第一时长与第二时长中较小者作为上传时间，并以较小者对应的任务上传方式进行任务上传。

较为优选的，所述计算用户与边缘服务器之间的距离包括：

根据公式

其中，D为用户与边缘服务器之间的初始距离，v为用户移动的速度，T为上传/下载过程中用户移动的时间，θ为用户与服务器之间的角度。

较为优选的，所述第一时长或第二时长的计算包括：

根据服务器之间的距离计算云服务器和云服务器、云服务器和边缘服务器、边缘服务器和边缘服务器之间的数据传输速率；

根据服务器之间的传输速率和上传的任务大小计算上传时间。

较为优选的，在利用所述迭代输出的候选服务解决用户发布的任务后，还包括从服务器下载处理结果，所述下载过程包括：

计算用户与边缘服务器之间的距离，并判断距离最近的服务器；

若处理最后一个任务的候选服务位于云服务器上，则将处理结果先上传到离用户最近的边缘服务器上，再从离用户最近的边缘服务器上下载处理结果；

若处理最后一个任务的候选服务位于第一边缘服务器上，且所述第一边缘服务器为离用户最近的服务器，则直接从所述第一边缘服务器上下载处理结果；

若处理最后一个任务的候选服务位于第一边缘服务器上，且离用户最近的服务器为第二边缘服务器，则计算直接从第一边缘服务器上下载处理结果所需的第三时长和先将处理结果上传至第二边缘服务器，再从第二边缘服务器上下载处理结果所需的第四时长，将第三时长与第四时长中较小者作为下载时间，并以较小者对应的下载方式进行处理结果的下载。

较为优选的，所述第三时长或第四时长的计算包括：

根据服务器之间的距离计算云服务器和云服务器、云服务器和边缘服务器、边缘服务器和边缘服务器之间的数据传输速率；

根据服务器之间的传输速率和需要下载的处理结果大小计算下载时间。

本发明的有益效果为：

1、将海鸥优化算法与模拟退火算法结合，充分利用前者的优势，对候选服务进行选择，同时通过模拟退火算法对其再次进行优化，避免陷入局部最优解，从而可以高效的找到全局最优解，为解决多目标优化问题提供更加可靠的保障。能够在用户移动过程中实现复杂需求的服务选择，能够根据用户所处的位置进行判断，通过最小的代价完成用户需求。

2、基于边缘服务器、云服务器进行多种上传途径的上传时间计算，可在用户移动过程中，从信号覆盖用户的边缘服务器中选择上传任务时间最短的上传途径，缩短了任务总体处理时间，提高了任务处理效率。基于边缘服务器、云服务器进行多种下载途径的下载时间计算，从信号覆盖用户的边缘服务器中选择下载时间最短的服务器，进一步缩短了任务总体处理时间，提高了任务处理效率。

3、将云边结合环境下的服务选择建模为一个多目标优化问题，利用海鸥优化算法，从众多候选服务中找到问题最优的目标解，降低了从多个任务中选择最优服务的云计算难度。

附图说明

图1为本发明流程示意图；

图2为本发明中移动用户模型示意图；

图3为本发明模块构成图示意图；

图4为本发明中计算移动用户当前位置与边缘服务器之间的距离示意图；

图5为本发明实施例二中用户与两台边缘服务器e

图6为采用响应时间为衡量标准时本方法与六个常规进化算法的对比仿真示意图；

图7为采用花费为衡量标准时，本方法与六个常规进化算法的对比仿真示意图；

图8为图6的对比结果放大示意图；

图9为图7的对比结果放大示意图。

具体实施方式

为了使本申请所要解决的技术问题、技术方案及有益效果更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

需要说明的是，当元件被称为“固定于”或“设置于”另一个元件，它可以直接在另一个元件上或者间接在该另一个元件上。当一个元件被称为是“连接于”另一个元件，它可以是直接连接到另一个元件或间接连接至该另一个元件上。

需要理解的是，术语“长度”、“宽度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本申请和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本申请的限制。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本申请的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。

本发明提供一种云边结合环境下基于海鸥优化算法的移动服务选择方法，包括：

输入服务存储库中带QoS属性的服务，服务的属性信息包括响应时间；

将用户发布的任务请求上传至服务器；

根据上传的任务初始化海鸥种群，并计算初始海鸥种群中最优海鸥的位置，所述海鸥的位置代表每个任务所选择的一组候选服务；

对最优海鸥的位置进行迭代运算，直到达到最大迭代次数；

将迭代得到的最优海鸥的位置所对应的一组候选服务输出；

所述迭代运算包括：

采用海鸥优化算法对每只海鸥的位置进行更新；

根据适应度函数计算当前迭代种群中最优海鸥的位置P

调用模拟退火算法在位置P

较为优选的，所述采用海鸥优化算法对每只海鸥的位置进行更新包括：

(1)计算海鸥的迁徙位置

海鸥从一个位置移动到另一个位置，要做到避免与其他海鸥发生碰撞，新位置P

其中，

A＝f

其中，f

在避免了与其他海鸥位置重合之后，海鸥会向最佳位置所在方向移动：

其中，

B＝2×A

r

海鸥向着最佳位置方向移动后到达新位置

(2)计算海鸥的攻击位置(局部搜索)。

海鸥在迁徙过程中可以不断改变攻击角度和速度，它们用翅膀和重量保持高度。当攻击猎物时，它们就在空中进行螺旋形状运动。x，y和z平面中的运动行为描述如下：

x＝r×cos(α)

y＝r×sin(α)

z＝r×α

r＝u×e

其中r是每个螺旋的半径，α是[0,2π]范围内的随机角度，u和v是螺旋形状的相关常数，e是自然对数的底数。海鸥的攻击位置可由公式得：

较为优选的，模拟退火算法中的温度参数，按照特定的冷却速率下降，直到降低到某一个值为止。

较为优选的，还包括构建云服务器和边缘服务器，将已经输入的候选服务随机的分布到云服务器和边缘服务器上；

根据移动用户当前位置计算所有信号范围覆盖用户的边缘服务器，计算用户与边缘服务器之间的距离，并判断距离最近的服务器；

若处理第一个任务的候选服务位于云服务器上，则用户发布的任务先上传到离用户最近的边缘服务器上，再由离用户最近的边缘服务器上传到云服务器；

若处理第一个任务的候选服务位于第一边缘服务器上，且所述第一边缘服务器为离用户最近的服务器，则用户发布的任务直接上传至所述第一边缘服务器；

若处理第一个任务的候选服务位于第一边缘服务器上，且离用户最近的服务器为第二边缘服务器，则计算用户发布的任务直接上传至第一边缘服务器所需的第一时长和先将用户发布的任务上传至第二边缘服务器，再由第二边缘服务器上传至第一边缘服务器所需的第二时长，将第一时长与第二时长中较小者作为上传时间，并以较小者对应的任务上传方式进行任务上传。

较为优选的，所述计算用户与边缘服务器之间的距离包括：

根据公式

其中，D为用户与边缘服务器之间的初始距离，v为用户移动的速度，T为上传/下载过程中用户移动的时间，θ为用户与服务器之间的角度。

较为优选的，所述第一时长或第二时长的计算包括：

根据服务器之间的距离计算云服务器和云服务器、云服务器和边缘服务器、边缘服务器和边缘服务器之间的数据传输速率；

根据服务器之间的传输速率和上传的任务大小计算上传时间。

较为优选的，在利用所述迭代输出的候选服务解决用户发布的任务后，还包括从服务器下载处理结果，所述下载过程包括：

计算用户与边缘服务器之间的距离，并判断距离最近的服务器；

若处理最后一个任务的候选服务位于云服务器上，则将处理结果先上传到离用户最近的边缘服务器上，再从离用户最近的边缘服务器上下载处理结果；

若处理最后一个任务的候选服务位于第一边缘服务器上，且所述第一边缘服务器为离用户最近的服务器，则直接从所述第一边缘服务器上下载处理结果；

若处理最后一个任务的候选服务位于第一边缘服务器上，且离用户最近的服务器为第二边缘服务器，则计算直接从第一边缘服务器上下载处理结果所需的第三时长和先将处理结果上传至第二边缘服务器，再从第二边缘服务器上下载处理结果所需的第四时长，将第三时长与第四时长中较小者作为下载时间，并以较小者对应的下载方式进行处理结果的下载。

较为优选的，所述第三时长或第四时长的计算包括：

根据服务器之间的距离计算云服务器和云服务器、云服务器和边缘服务器、边缘服务器和边缘服务器之间的数据传输速率；

根据服务器之间的传输速率和需要下载的处理结果大小计算下载时间。

较为优选的，计算用户与服务器之间的距离根据以下公式进行计算：

其中，D为用户与边缘服务器之间的初始距离，v为用户移动的速度，T为上传/下载过程中用户移动的时间，

较为优选的，所述用户上传任务时间T

T

T

其中，∑T

较为优选的，数据传输速率根据以下公式进行计算：

r(B,g)＝B×log2(1+tp×g/σ)

其中，B为带宽，σ为接收器上的噪音，tp为移动设备的无线传输功率，g＝d-γ，d为移动设备和边缘服务器之间的距离，γ为路径损耗因子，其值为γ＝4。

实施例一

如图1所示提供了本方法一种较佳的实施例，如图2所示，移动用户向信号范围覆盖内的边缘服务器发送任务请求，如果用户同时处于多个边缘服务器的信号范围中，通过适应度函数计算任务上传时间最少的边缘服务器，将任务上传。服务器经过一段时间对上传的任务进行处理，处理完成后，通过适应度函数计算用户下载处理结果耗费时间最少的边缘服务器，将结果下载。图3所示为云边结合环境下基于改进海鸥优化算法的服务选择方法的整体框架，主要分为四个模块：云和边缘计算环境模块、用户移动模型模块、服务选择模块、改进海鸥优化算法模块。每个模块对应不同的功能，相互配合，解决用户请求。为了对本实施例进行说明，以下结合图2和3进行描述，其具体流程如下：

步骤1、输入服务存储库中的候选服务，服务包含响应时间等QoS值。

步骤2、云和边缘计算环境模块构建云服务器和边缘服务器，将已经输入的候选服务随机的分布到云服务器和边缘服务器上。

步骤3、根据服务器之间的距离计算云服务器和云服务器、云服务器和边缘服务器、边缘服务器和边缘服务器之间的数据传输速率。由于每个服务器上部署的服务不同，移动用户将任务上传到边缘服务器后，需要找到能够处理任务的服务所在服务器，根据两个服务器之间的传输速率和任务大小计算数据传输时间，直到任务处理完成。

步骤4、用户移动模型模块计算用户上传任务的服务器。首先根据移动用户当前位置计算所有信号范围覆盖用户的边缘服务器，然后将任务上传到边缘服务器上。在上传任务的过程中，服务选择模块判断处理第一个任务的候选服务是否位于云服务器上，若是，则用户发布的任务先上传到离用户最近的边缘服务器上，再由离用户最近的边缘服务器上传到云服务器；若处理第一个任务的候选服务位于第一边缘服务器上，且所述第一边缘服务器为离用户最近的服务器，则用户发布的任务直接上传至所述第一边缘服务器；反之，假设距离用户最近的边缘服务器为e

步骤5、改进海鸥优化算法模块对海鸥位置进行初始化。每一只海鸥的位置代表每个任务所选择的候选服务对应的一种解决方案。

步骤6、根据适应度函数计算初始海鸥种群中的最优位置。

步骤7、判断当前迭代是否达到最大迭代次数，如果是，则执行步骤12，否则执行步骤8。

步骤8、根据海鸥优化算法中的公式对每只海鸥的位置进行更新。

步骤9、通过适应度函数计算更新后每只海鸥的适应度，并选出当前这一代具有最优适应度的海鸥。

步骤10、通过模拟退火算法的思想在每只海鸥周围更新其他位置，并计算新位置的适应度，选择适应度更高的作为本次迭代更新后的海鸥位置。

步骤11、服务选择模块记录每一个任务选择对应的服务，同时不断更新算法计算出来的服务，确定解决任务的候选服务。

步骤12、用户移动模型模块计算用户卸载结果的服务器。首先根据移动用户当前位置计算所有信号范围覆盖用户的边缘服务器，然后将结果从边缘服务器下载。在下载结果的过程中，服务选择模块判断完成最后一个任务的候选服务是否位于云服务器上，如实则将处理结果先上传到离用户最近的边缘服务器上，再从离用户最近的边缘服务器上下载处理结果；若处理最后一个任务的候选服务位于第一边缘服务器上，且所述第一边缘服务器为离用户最近的服务器，则直接从所述第一边缘服务器上下载处理结果；反之，假设距离用户最近的边缘服务器为e

通过适应度函数计算响应时间或花费包括(以响应时间为例)：

1、计算用户与边缘服务器之间的距离，判断距离最近服务器；

结合图4，假设D是移动用户与边缘服务器的初始距离，图中箭头表示用户的移动方向，用户移动过程中始终与边缘服务器保持角度θ，在移动的过程中速度始终保持在v千米/小时，用户经过T时间之后的位置与边缘服务器之间的距离d为：

2、判断处理第一个任务的服务位于边缘服务器还是云服务器，计算上传时间T

如果处理第一个任务的候选服务s

如果处理第一个任务的候选服务s

任务发布到服务器的时间由任务大小和数据传输速率有关，用传输数据大小与数据传输速率的比值表示数据传输时间，见公式(3)。

T

其中∑Task

r(B，g)＝B×log

其中σ是接收器的噪声功率，tp为移动设备的无线传输功率，g＝d

3、计算任务处理时间

假设有两个服务s

服务s

其中，V

根据公式(5)-(7)来计算n个任务的组合结构和针对任务选择的候选服务得到T

4、判断完成最后一个任务的服务位于边缘服务器还是云服务器；

如果完成最后一个任务的候选服务s

如果完成最后一个任务的候选服务s

下载时间与上传时间类似，都是由公式(3)-(4)计算。

5、计算总体响应时间T

实施例二

在本实施例结合具体的任务和服务器，以计算响应时间为例，提供了一种最佳的实施方法。

如图5所示，共有两台边缘服务器e

表1

候选服务的属性如表2所示，其中包括完成任务所需要的时间和花费。

表2

表3提供了本实施例中一些参数设置。假设边缘服务器之间的数据传输延迟为0.5ms，云服务器和边缘服务器之间的数据传输延时为10ms。移动用户与边缘服务器e

表3

本实施例的部分步骤如下：

步骤1：将所有的候选服务随机分布到云服务器和边缘服务器上。候选服务随机分布情况如表4所示：

表4

步骤2：计算用户发布任务到边缘服务器的上传时间。

根据公式(3)-(4)和表3，用户发布任务到e

用户发布任务到e

因为解决任务的候选服务位于边缘服务器e

T

步骤3：初始化海鸥位置。

初始化海鸥位置即解决方案P

步骤4：更新迭代海鸥位置。

根据海鸥优化算法计算新的海鸥位置，即新的解决任务的服务。每次迭代更新后，只接受比上一次更优的方案，较差的方案直接抛弃掉。更新的位置P

将P

由于经过模拟退火算法调整后的位置所用到的时间比海鸥优化算法更新的位置更少，因此，选择接受P

再次更新海鸥位置P

将P

因为新的解决方案P

再达到最大迭代次数之后，当前保存的最优解决方案即为全局最优解决方案，在本实施例中，最优解决方案为位置

步骤5：计算用户当前位置与边缘服务器之间的距离。

通过公式(1)，116ms后，用户与边缘服务器e

步骤6：计算用户下载结果的下载时间。

根据公式(3)-(4)和表3，用户从边缘服务器e

用户从边缘服务器e

根据公式(2)，用户最终下载处理结果的时间为：

T

步骤7：输出用户处理任务所用时间及选择的服务。

最终用户选择的候选服务为

如图6和7，为验证方法的有效性，采用响应时间和花费为衡量标准，将本文提出的改进海鸥优化算法与改进的海鸥优化算法、遗传算法、蚁群算法等六个进化算法进行对比实验，由于数据量及进化算法的原因，导致改进海鸥优化算法和原始海鸥优化算法的对比显示不明显，因此，图8和9为两种算法对比结果放大图，以便于更方便验证。

测试的软件及硬件的环境如下：

(1)CPU：Intel(R)Core(TM)i7-8650U CPU@1.90GHz 2.11GHz

(2)RAM：16GB

(3)硬盘：NVMe KBG30ZMS256G NVM

(4)操作系统：Windows 10专业版

实验数据：本实验从澳大利亚通信和媒体管理局的数据集中选择基站的地理信息，并假设每个基站都配备有一个边缘服务器。服务随机分布在云服务器和边缘服务器上，在信息传输过程中设置了损失参数：边缘服务器之间大约需要2ms到8ms，云和边缘服务器之间需要10ms到50ms，云和云之间需要20ms到50ms。为了检查方法的性能，生成了四个数据集，每个数据集分别包含100,110,120和130个任务，每个任务有100个候选服务，每个候选服务包含响应时间和花费两个标准。本实验中所涉及的其他参数值的默认值见表5。

表5

实验结果如表6所示，从中可以看出，改进海鸥优化算法(ESOA)和原始海鸥优化算法(SOA)的性能优于其他算法。遗传算法(GA)、差分进化算法(DE)、粒子群优化算法(PSO)、模拟退火算法(SA)和蚁群算法(ACO)的收敛速度和返回解较差，ESOA和SOA都能找到最优解，且ESOA的收敛速度较好。

综上，将服务选择建模为一个多目标优化问题来解决更加容易方便。实验表明，改进海鸥优化算法要比其他算法在多目标优化问题上效率更优。

表6

应理解，上述实施例中各步骤的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本申请实施例的实施过程构成任何限定。

以上所述实施例仅用以说明本申请的技术方案，而非对其限制；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围，均应包含在本申请的保护范围之内。