湖南人文科技学院数学与金融学院 易婷 申佳灵 聂勤 李军成

在边缘计算中，边缘服务器的部署是任务卸载的核心，因此选取合适的边缘服务器部署算法显得尤为重要。本文以K-Means算法、二分K-Means算法、K-Medoids算法及免疫优化算法等边缘服务器部署算法为对象，通过仿真实验对四种算法的性能进行了对比分析，为边缘服务器部署算法的选择提供了一定的依据。

边缘计算是指在靠近数据源头的一侧，采用网络、计算、存储、应用核心能力为一体的开放平台，就近提供最近端服务，产生更快的网络服务响应，同时满足行业在实时业务、应用智能、安全与隐私保护等方面的基本需求[1]。边缘服务器（Edge Server，ES）是边缘计算的重要组成部分，因此边缘服务器的部署问题具有重要的研究意义。

目前，已有许多文献对边缘服务器的部署问题进行了研究，例如引用[2]以时延与能耗为目标，对边缘服务器放置进行研究，提出了一种基于混沌麻雀搜索算法的边缘服务器放置方法，但其并不适用于多跳的时延模型；引用[3]以最小化访问延迟和最小化负载差异为优化目标，建立了边缘服务器放置优化模型并提出了一种基于改进启发式算法的移动边缘服务器放置方法，但其在负载平衡方面没有达到最优；引用[4]将智能城市中k个边缘服务器放置问题描述为一个多目标优化问题，提出了一种改进的带有精英策略的多目标非支配排序遗传算法对该问题进行优化解决；引用[5]为克服参数调整困难等，提出了一种基于深度Q网络和强化学习的新型边缘服务器放置算法等。

在部署边缘服务器时，往往需要选取合适的算法。本文的目的是将K-Means算法与二分K-Means算法、K-Medoids算法及免疫优化算法分别应用于边缘服务器部署中，通过仿真实验进行对比分析，为边缘服务器部署算法的选择提供了一定的参考。

1 四种边缘服务器部署算法简介

1.1 K-Means算法

在利用K-Means算法[6]部署边缘服务器时，首先基站数据集中随机取k个基站分别作为k个簇的中心基站，计算剩下的所有基站到k个中心基站的欧氏距离，如式（1）所示：

其中，ai表示第i个基站，bj表示第j个中心基站；然后将与中心基站的欧式距离和最小的基站划分为一簇，并根据聚类划分结果重新得到k个中心基站，按照新中心基站重新聚类；最后不断重复选取新中心基站并划分簇，直至目标函数SEE收敛，此时所得到的k个中心基站即为边缘服务器位置，如式（2）所示：

其中，ai表示第k个簇的中第i个基站，bk表示第k个簇的中心基站。

1.2 二分K-Means算法

将二分K-Means算法[7]应有于边缘服务器部署时，将整个基站数据集视为一个簇A1，对簇A1进行K-Means聚类(k=2)得到两个基站分簇A2、A3；分别根据式(2)计算簇A2、A3的SSE，选择较小SEE的基站簇继续进行K-Means聚类(k=2)得到基站簇A4、A5并计算各簇的SSE，重复以上步骤直至得到k个基站簇数，在进行基站簇划分过程中各簇中心基站已明确得到，即边缘服务器部署完成。

1.3 K-Medoids算法

将K-Medoids算法[8]应有于边缘服务器部署时，首先在基站数据集中随机选取k个初始中心基站，依据就近原则将所有基站划分至k个初始中心基站内，此时基站数据集分为k类；在每一类中计算任意基站与其他基站的距离和，选择该类中与该类其他基站距离和最小的基站为该类新中心基站；再依据新中心基站重新将整个基站数据集划分k类，直至k个中心基站不再发生变化，最后所得到的k个中心基站即为所部署的k个边缘服务器位置，边缘服务器部署完成。

1.4 免疫优化算法

在利用免疫算法[9]部署边缘服务器时，从有限个位置(N个)中选择一定数量的位置(K个)，以边缘服务器为抗体、基站为抗原建立一个选址模型，将边缘服务器与基站之间的最小距离和为目标函数F，如式（3）所示：

约束条件如式（4）所示：

其中，d(Aa,Bb)表示在同一类中位置Aa的边缘服务器和位置Bb的基站之间的距离，K为边缘服务器数量，N为基站数量，Sa表示边缘曲线所包含的不规则区域。

在基站数据集中随机产生n1个中心基站，即视为初始边缘服务器种群。对n1个中心基站进行亲和值评价并以此进行升序排序，如式（5）所示：

其中，aff(Ai,Cj)表示中心基站Ai与其他基站Cj的距离和，值越小代表基站Ai与Cj越亲和。

在排序后的n1个中心基站中取前n2个基站作为父代边缘服务器群体，前m1个基站放入边缘服务器记忆库；若记忆库中的m1个基站满足约束条件则结束，若不满足则将父代边缘服务器群体中n2个基站进行选择、交叉、变异等操作，与记忆库中的m1个基站构成一个新群体；重新进行基站评价并以亲和值排序，从新群体中选取前m2个基站替换记忆库中已有的部分基站；若此时记忆库中的基站满足约束条件则结束，若不满足则继续重复以上步骤直至满足；满足条件后输出记忆库中排序最高的k个基站，即为k个边缘服务器位置。

2 仿真结果与对比分析

首先将区域划分结果与部署后所得的边缘服务器具体位置作为评价指标，对K-Means算法、二分K-Means算法、K-Medoids算法、免疫优化算法的性能进行对比分析。当边缘服务器数量取9时，分别利用四种算法进行边缘服务器部署，结果如图1所示。

当边缘服务器数量取15时，分别利用四种算法进行边缘服务器部署，结果如图2所示。

由图1与图2可知，K-Means算法所得的边缘服务器部署结果只能得到具体的边缘服务器位置，并没有进行区域划分且可能摒弃孤立点；二分K-Means算法所得的边缘服务器部署结果既有明确的区域划分，同时又直接给出边缘服务器位置；K-Medoids算法、免疫优化算法所得的边缘服务器部署结果只有区域划分结果而没有直接给出边缘服务器位置，还另需对各区域计算任意基站与其他基站的距离之和，取每簇中与该簇中其他基站距离之和最小的基站作为各区域待部署的边缘服务器位置。

另外，当基站与边缘服务器之间的距离越短时，两者之间的访问延迟会越短，故这里将基站与边缘服务器之间的平均访问延迟值作为另一个衡量不同算法性能的指标。在实验中，将基站与边缘服务器之间的平均距离表示平均访问延迟，其计算式如式（6）所示[10]：

式中，其中d(Aa,Bb)表示分别在位置Aa的边缘服务器和位置Bb的基站之间的距离，K为边缘服务器数量，N为基站数量。显然，在边缘服务器数量K和基站数量N一定时，基站和边缘服务器之间的距离越小，平均访问延迟T也越小，即越满足部署目标。

当边缘服务器数量取9与15时，分别利用四种算法进行边缘服务器部署，平均访问延迟结果对比如表1所示。

表1 四种算法的平均访问延迟结果对比（单位：s）Tab.1 Comparison of average access delay results of four algorithms (unit: s)

由表1可知，四种算法的平均访问延迟由小到大分别为二分K-Means算法、K-Medoids算法、免疫优化算法、K-Means算法。

综合两个性能指标的对比分析可知，相较于K-Means算法、K-Medoids算法和免疫优化算法，二分K-Means算法在边缘服务器部署中具有更好的效果。

3 结语

本文首先介绍了K-Means算法、二分K-Means算法、K-Medoids算法及免疫优化算法分别应用于边缘服务器部署的基本原理，然后通过仿真实验对四种算法的区域部署结果、平均访问延迟两个性能指标进行了比较，为边缘服务器部署算法的选择提供了一定的依据。