基于时延与能量感知的边缘服务器放置方法

赵兴兵，赵一帆，李 波，陈 春，丁洪伟

（1.云南大学 信息学院，昆明 650500；2.云南民族大学 电气信息工程学院，昆明 650504；3.云南民族大学 应用技术学院，昆明 650504）

0 概述

随着物联网、人工智能、大数据、云计算等新一代信息技术的快速发展，各种基于移动互联网的新型业务不断出现，移动终端的数据流量呈现爆炸式增长［1］。由于移动终端具有有限的计算和存储能力，因此可将部分负载迁移到云端进行处理［2-3］。但由于云计算部署模式［4］的限制，基于远程数据中心的云计算模式需要通过广域网传输数据和应用，因此产生的网络时延和抖动会对实时交互性应用和用户体验产生不利影响。边缘计算在靠近用户端的网络边缘部署本地云资源，在很大程度上可缓解网络带宽、时延和抖动对移动应用的影响，有效改善传统通信网络结构。移动边缘计算［5］支持用户在无线接入网（Radio Access Network，RAN）范围内访问信息和云计算服务，大幅降低了传送时延，提高了用户体验［1］。边缘服务器（Edge Server，ES）是移动边缘计算的重要组成部分［6］。在城市中，移动用户分布密集，来自用户的任务量大。对于运营商而言，相比于其他地区，在城市中放置ES 将有更高的收益。因此，研究无线城域网（Wireless Metropolitan Area Network，WMAN）中的ES 放置问题（简称为WESP问题）具有重要意义。

目前，有关ES 放置问题的研究较少，但在相关研究领域微云放置已取得了一定的研究成果，可为ES 放置提供一定的参考。文献［7］以最小化系统时延为目标，对微云放置进行研究，提出负载最重优先和用户密度优先的放置策略。文献［8］研究WMAN中有限容量的微云放置问题，在问题规模较小时提出基于整数线性规划的放置方法。文献［9-11］讨论了微云放置的成本问题，其中：文献［9］通过拉格朗日启发式算法对微云进行放置；文献［10］将时延映射为成本，提出二进制差分进化布谷鸟搜索算法，解决基于软件控制网络的微云放置问题；文献［11］采用改进的贪婪算法解决ES 放置问题。文献［12］以覆盖更多的用户为目标，对微云放置问题进行讨论。文献［13］以优化时间开销和能量开销为目标，讨论了5G 环境中的ES 放置问题，并提出基于等效带宽的放置方法。文献［14］以优化用户接入时延和均衡ES 负载为目标，讨论移动边缘计算环境中的ES 放置问题，并提出基于混合整数规划（Mixed Integar Planing，MIP）的放置方法。此外，学者们还对移动边缘计算中的应用部署问题进行了大量研究［15-17］。

本文对WMAN 中ES 放置的时延和能耗问题进行研究，建立WESP 问题的时延和能耗模型，提出基于混沌麻雀搜索算法（Chaos Sparrow Search Algorithm，CSSA）的ES 放置方法，针对WESP 问题设计新的个体编码方式，使用精英反向学习（Elite Opposition-Based Learning，EOBL）策略产生初始种群加快算法搜索速度，采用逻辑混沌映射策略对麻雀个体进行改进，增强算法收敛性。

1 问题描述

假设E=｛E1，E2，…，E|E|｝为一组ES 集合，|E|为边缘服务器的总数；B=｛B1，B2，…，B|B|｝为一组基站集合，|B|为基站的总数；对于∀i，表示基站Bi为一组移动用户提供转发服务，|U|为由基站Bi提供转发服务的用户总数。

WESP 问题描述：给定一组ES 的集合、BS 的集合以及每个基站负责的用户集合，在给定的基站集合中寻找一种ES 放置方案，并为ES 分配基站，使得ES 放置的平均时延D［E］和平均能耗EC［E］最小。目标函数的数学模型表示如下：

其中：X为ES 放置方案，即问题的一组可行解。

单个边缘服务器Ev的负载W[Ev]表示如下：

其中：W[∙]表示将单个用户的负载累加到ES。

边缘服务器的平均时延是所有ES 传输时延的平均值，表示如下：

单个ES 的传输时延包含本地传送时延和远程传送时延。本地传送时延是移动用户请求到达ES的传输时间，表示如下：

其中：T[∙]为单个用户请求到达ES 的传输时延，由基站与ES 之间的距离除以光速得到，并且本文不考虑用户请求接入基站之前的无线传输时延。

假设所有ES 同构，单个ES 负载的阈值为WTH。当ES 的负载达到阈值后，ES 不再处理用户请求，随后到达的用户请求将被迁移到远程云处理，产生的远程传送时延如下：

其中：Tmax为ES 将负载迁移到远程云产生的固定时延。

由式（4）和式（5）可知，单个ES 的时延表示如下：

在ES 中，CPU、内存和硬盘等都是造成能耗的器件，但主要的能耗器件为CPU［18］，并且ES 的能耗可由功率和CPU 使用率的线性关系得出［19-20］。单个ES 的能耗表示如下：

其中：Pidle为服务器的空闲功率；Pmax为服务器完全工作时的功率；UPv为服务器的使用率。UPv的计算公式如下：

由式（7）～式（9）可得，所有ES 的平均能耗表示如下：

由以上分析可知，WESP 问题是一个多目标优化问题，优化的目标是最小化ES 的平均时延和平均能耗，传统的优化算法难以解决多目标优化问题。本文采用加权方法将平均时延和平均能耗转化为系统开销，其中权值为0.5，因为在优化过程中平均时延和平均能耗同样重要。

由于时延和能耗的量纲不同，为了消除量纲不同对加权效果的影响，因此先采用式（11）对单个ES的时延和能耗进行归一化，再使用式（3）和式（10）重新计算平均时延和平均能耗。

定义1系统开销被定义为归一化后的平均时延和平均能耗的加权和，表示系统实现所需的时间代价和能耗代价，能够反映系统性能的优劣，值越小，系统性能越好，计算公式如下：

2 基于混沌麻雀搜索的放置方法

麻雀搜索算法（Sparrow Search Algorithm，SSA）［21］是一种新型群体智能优化算法，通过模拟麻雀的捕食和反捕食行为进行迭代寻优，具有调整参数少、收敛速度快、设计简单等优点。麻雀种群可分为发现者、加入者和警戒者。发现者和加入者构成了发现者-跟随者模型，警戒者为模型加入警戒者机制。在麻雀种群中：容易发现食物的个体（在本文中为适应度函数值较小的个体）被指定为发现者，负责为所有加入者提供觅食区域和方向；剩下的个体为加入者，负责平衡种群数量，迭代过程中发现者和跟随者的比重是不变的；警戒者由种群中随机选取的个体组成，占种群数量的10%～20%，负责为种群警戒，当危险发生时提醒其他成员转移位置。

麻雀搜索算法优点众多，但不适用于解决WESP 问题，并且存在接近全局最优时搜索能力不足和容易陷入局部最优的问题。为了克服这些问题并解决WESP 问题，本文提出基于混沌麻雀搜索算法的放置方法。

2.1 个体编码

由以上分析可知，WESP 问题是一个离散优化问题，传统的二进制编码和实数编码难以有效描述WESP 问题，并且难以与迭代过程相结合。文献［22］提出一种放置问题编码方式，受此启发，本文提出一种个体编码方式，如表1 所示，其中√表示ES的标记。

表1 个体编码Table 1 Individual coding

在表1 中，个体编码为k×2m的矩阵，每一行表示一个边缘服务器，每一列表示一个基站。前m列为放置矩阵Y，后m列为分配矩阵Z。在放置矩阵中，每一行的标记位置表示第i个ES 的放置位置。在分配矩阵中，每一列的标记位置表示将此列代表的基站分配给该行代表的ES。以表1 为例：第1 行表示将第1 个ES 放置在第1 个基站上，并且为其分配第1 个和第（m-1）个基站；第k行表示将第k个ES放置在第2 个基站上，并且为其分配第2 个基站。因为WESP 问题存在约束条件，所以编码还需满足以下规则：

1）Y中任意两行对应的标记不在同一列，并且每一行有且只有一个标记，对应

2）Z中每一列中有且只有一个标记，对应

3）在Z和Y中，相同列中的标记必须位于同一行，放置ES 的基站被分配给该ES。

2.2 适应度函数

适应度函数用来控制种群迭代更新，适应度函数值反映个体能量的高低。本文将适应度函数定义为式（14），表示平均时延和平均能耗的加权和。适应度函数值越小，放置性能越好，个体能量越高且越优秀。

2.3 发现者位置更新

在搜索过程中，具有良好适应度的发现者会优先获取食物，并且发现者负责为种群寻找食物提供觅食方向，因此发现者相比加入者有更大的搜索范围，按式（15）的规则更新位置：

其中：α∈(0,1]为随机数；R2∈[0,1]为安全值；SST∈[0,1]为警戒值；Q为服从正态分布的随机数；L为1×2m的矩阵，其元素全部为1；itermax为最大迭代次数；Round(∙)为取整操作。当R2

2.4 加入者位置更新

在觅食过程中，一些加入者会时刻监视发现者，并与发现者抢夺食物（表现为式（15）），如果抢夺食物成功，则成为发现者，否则成为加入者，按式（16）的规则更新位置：

其中：XP为目前发现者占据的最佳位置；Xworst为当前种群的最差位置；A+=AT(AAT)-1，A是形状为1×2m、元素为1 或-1 的矩阵。当时，个体i没有获得食物，处于十分饥饿的状态，此时个体i将飞往其他地方觅食；否则，个体i将向食物更加丰富的区域移动。

2.5 警戒者位置更新

警戒者的位置是在种群中随机产生的，按照式（17）的规则更新位置：

2.6 逻辑混沌映射

传统SSA 与其他群体智能优化算法一样，在迭代后期，算法搜索能力下降，导致种群多样性降低，容易陷入局部最优。为了克服该问题，采用逻辑混沌映射［23］的方式在每次迭代结束后对种群的位置进行更新，以保持种群的多样性，保证算法的收敛性，如式（18）所示：

其中：μ∈(0,4]。

2.7 精英反向学习策略

反向学习（Opposition-Based Learning，OBL）策略通过构造初始种群加快算法搜索速度。精英反向学习策略［24］是反向学习策略的改进，利用优势个体反向构造初始种群，以保证种群的多样性，加快算法的搜索速度。

设Xi=(Xij1,Xij2,…,Xij(2m)),j=1,2,…,k为一个 普通个体，其对应的极值为精英个体其对应的精英反向解定义如下：

其中：maxdj、mindj分别为Xi的第j维的最大值和最小值。

2.8 CSSA 算法描述

将求解WESP 问题的CSSA 算法步骤描述如下：

步骤1初始化种群，定义相关参数，转到步骤2。

步骤2计算所有个体的适应度值，找出精英个体，并根据式（19）构造新的种群，转到步骤3。

步骤3计算所有个体的适应度函数值并进行排序；保存适应度值和个体位置；找出最佳适应度函数值fg并保存其位置Xbest，转到步骤4。

步骤4根据式（15）更新发现者的位置和适应度函数值；找出目前发现者占据的最优位置XP、当前全局最差个体的Xworst和fw，转到步骤5。

步骤5根据式（16）更新加入者的位置和适应度函数值，转到步骤6。

步骤6根据式（17）随机更新警戒者的位置和适应度函数值，转到步骤7。

步骤7得到更新后的位置和适应度函数值，转到步骤8。

步骤8将更新后的适应度函数值与步骤2 中保存的适应度函数值进行比较，若小于步骤2 中保存的适应度函数值，则更新适应度函数值和位置，否则不更新；更新fg和Xbest，转到步骤9。

步骤9根据式（18）产生新的个体，并与原个体比较，若新个体更优，则更新原个体的位置和适应度函数值，否则不更新，转到步骤10。

步骤10比较迭代次数是否满足itermax，若满足，则转到步骤11，否则转到步骤4。

步骤11输出最佳适应度值和个体位置。

3 仿真与结果分析

使用上海市电信局的真实网络数据集对算法进行仿真实验。经过处理后的数据集包含2 753 个基站信息，包括编号、用户数量、纬度、经度和连续15 天的接入时长（记为负载）。经过处理后，部分基站信息如表2 所示。

表2 部分基站信息Table 2 Information of some base stations

实验软硬件环境为Intel®CoreTMi7-9750H CPU 2.60 GHz 处理器、Windows 10 操作系统、Python 3.7版本。核心参数设置如下：最大迭代次数itermax∈[60～100]，种群数 量N∈[60～80]，Pidle=0.3w，Pmax=0.5w，WTH为3×108min，ES 将负载迁移到远程云产生的固定时延Tmax为0.5 s，最大接入时延Ad为0.7 s。选取MIP［14］、K-Means［14］、Random［22］、Top-K［22］等4 个主流放置算法作为对比算法。算法的性能测试指标为平均时延和平均能耗。

保持基站数量为2 753，不断增加ES 数量，测试平均时延的变化，如图1 所示。由图1 可以看出：当ES 为100 时，Random、K-Means、Top-K、CSSA、MIP的平均时延分别为0.028 s、0.21 s、0.036 s、0.022 s、0.028 s，CSSA 相比其他4 种算法分别约降低了21.4%、86.6%、38.8% 和21.4%；当ES 为200 时，Random、K-Means、Top-K、CSSA、MIP 的平均时延分别为0.017 s、0.14 s、0.021 s、0.015 s、0.018 s，CSSA 相比其他4 种算法分别约降低了11.7%、92.1%、28.5%和16.6%；当ES 为300 时，K-Means 的平均 时延为0.085 s，其他算法的平均时延接近相等，约为0.005 8 s；当ES 为400 时，Random、K-Means、Top-K、CSSA、MIP 的平均 时延分别为0.008 7 s、0.23 s、0.032 s、0.003 2 s、0.006 1 s，CSSA 相比其他4 种算法分别约降低了51.7%、91.3%、28.5%和47.5%。

图1 平均时延随ES 数量的变化Fig.1 Variation of average time delay with the number of ES

由图1 分析可知，随着ES 数量的增加，不同算法的平均时延均呈现下降的趋势，主要原因为当基站总数不变时，随着ES 数量的增加，基站趋向于被分配给更近的ES，所以平均时延下降。CSSA 平均时延最小，其次为MIP、Top-K、Random 和K-Means。除CSSA 之外，其他算法均在ES 数量为300 时表现最好，当ES 数量为400 时，性能反而有所下降，分析其原因为陷入了局部最优，而CSSA 未陷入局部最优，性能继续优化。因为CSSA 使用精英反向学习策略初始化种群，加快了算法的搜索速度，利用逻辑混沌映射对个体进行改进，保证了算法的收敛速度。

保持基站数量为2 753，不断增加ES 数量，测试平均能耗的变化，如图2 所示。由图2 可以看出：当ES 数量为100 时，Random、K-Means、Top-K、CSSA、MIP 的平均 能耗分别为0.264 kWh、0.193 kWh、0.032 kWh、0.02 kWh、0.291 kWh，CSSA 相比其 他4 种算法约分别降低了96.1%、94.7%、41.3%和96.5%；当ES 数量为200 时，Random、K-Means、MIP 的平均能耗分别为0.21 kWh、0.266 kWh、0.285 kWh，CSSA 和Top-K 的平均能耗约 为0.012 kWh，CSSA 相比其 他3 种算法约分别降低了93.8%、91.3%和91.2%；当ES数量为300 时，Random、K-Means、Top-K、CSSA、MIP的平均能耗分别为0.264 kWh、0.193 kWh、0.011 kWh、0.01 kWh、0.271 kWh，CSSA 相比其他4 种算法约分别降低了96.2%、94.3%、9% 和95.3%；当ES 数量为400 时，Random、K-Means、MIP 的平均能耗分别为0.173 kWh、0.232 kWh、0.269 kWh，Top-K 和CSSA为0.007 kWh，CSSA 相比Random、K-Means 和MIP平均能耗约分别降低了95.5%、93.3%、18.1% 和97.3%。

图2 平均能耗随ES 数量的变化Fig.2 Variation of average energy consumption with the number of ES

由图2 分析可知，随着ES 数量的增加，不同算法的平均能耗都有下降的趋势。CSSA 的平均能耗最少，之后是Top-K，其他算法的平均能耗均很高，分析其原因是CSSA 和Top-K 放置时考虑了负载因素，而其他算法放置的依据是距离，忽略了对能耗影响较大的负载因素，所以平均能耗表现很差。

不同算法的系统开销随ES 数量的变化如图3 所示，可以看出CSSA 的系统开销最优，其次是Top-K、Random、MIP 和K-Means。

图3 系统开销随ES 数量的变化Fig.3 Variation of system overhead with the number of ES

由图3 分析可知：CSSA 在迭代寻优时，以系统开销为适应度函数指导种群个体进化，同时兼顾平均时延和平均能耗，所以系统开销是最优的；对于Top-K，因为在真实的WMAN 中，用户总是集中在特定的区域（商场、学校等），所以将ES 放置在这些位置将有更小的用户接入时延，同时这些位置的基站负载较大，意味着放置在此地的ES 使用率较高，ES使用率越高，处于空闲状态的时间越少，系统能耗越小，系统开销越小；Random 和MIP 的平均时延较小，但平均能耗较大，系统开销也较大；K-Means 中的ES由于必须被放置在基站上，因此选取与聚类质心最近的基站作为ES 的放置位置，导致平均时延较大，此外，由于K-Means 是非均匀的聚类算法，因此ES负载差异很大，导致平均能耗较大，K-Means 系统开销也较大［18］。

图4 给出了放置100 个ES 时CSSA 的适应度曲线，可以看出CSSA 的适应度函数值呈现单调递减的趋势，在前10 次迭代内适应度函数值下降较快，迭代12 次后适应度函数值完全收敛，算法找到全局最优解。在该情况下，CSSA 系统开销最初为0.033，经过迭代后最终下降到0.027，减少了18.1%。

图4 当ES 数量为100 时CSSA 的适应度曲线Fig.4 Fitness curve of CSSA when the number of ES is 100

4 结束语

本文提出一种基于混沌麻雀搜索算法的WMAN边缘服务器放置方法。通过设计新的编码方式有效描述WESP 问题，并解决离散优化问题。采用精英反向学习策略初始化种群，提高算法搜索速度。利用逻辑混沌映射改进麻雀个体，保证迭代后期的种群多样性，避免陷入局部最优解。实验结果表明，CSSA 在优化平均时延和平均能耗方面表现突出。但由于在实际WMAN中用户请求可能通过多次转发到达边缘服务器，因此后续将分析并建立包含多跳的时延模型。此外，在新一代信息技术的支持下，边缘服务器的作用和功能趋于多元化，异构的边缘服务器放置问题也是下一步研究的重点方向。