开放科学（资源服务）标志码（OSID）：

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={E₁，E₂，…，E_|E|}为一组ES集合，|E|为边缘服务器的总数；B={B₁，B₂，…，B_|B|}为一组基站集合，|B|为基站的总数；对于$ \forall i $，B_i={U$ {}_{1}^{i} $，U$ {}_{2}^{i} $，…，$ {U}_{\left|{U}^{i}\right|}^{i} $}表示基站B_i为一组移动用户$ {U}_{n}^{i} $，$ n\in [1, |U\left|\right] $提供转发服务，|U|为由基站B_i提供转发服务的用户总数。

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

$ {\rm{Min}}\ D[E]（X） {\rm{\&\&}}\ {\rm{Min}}\ E_ {\rm{C}}[E]（X） $

(1)

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

单个边缘服务器E_v的负载$ W\left[{E}_{v}\right] $表示如下：

$ W\left[{E}_{v}\right]=\sum\limits _{i}^{\left|B\right|}\sum\limits _{n}^{\left|U\right|}W[{E}_{v}, {U}_{n}^{i}] $

(2)

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

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

$ D\left[E\right]=\frac{1}{\left|E\right|}\sum\limits _{v=1}^{\left|E\right|}T\left[{E}_{v}\right] $

(3)

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

$ {D}_{\mathrm{L}}\left[{E}_{v}\right]=\sum\limits _{i}^{\left|B\right|}\sum\limits _{n}^{\left|U\right|}T[{E}_{v}, {U}_{n}^{i}] $

(4)

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

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

$ {D}_{\mathrm{R}}\left[{E}_{v}\right]={T}_{\mathrm{m}\mathrm{a}\mathrm{x}}\times \left(\frac{W\left[{E}_{v}\right]-{W}_{\mathrm{T}\mathrm{H}}}{W\left[{E}_{v}\right]}\times 100\mathrm{\%}\right) $

(5)

其中：$ {T}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为ES将负载迁移到远程云产生的固定时延。

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

$ T\left[{E}_{v}\right]={D}_{\mathrm{L}}\left[{E}_{v}\right]+{D}_{\mathrm{R}}\left[{E}_{v}\right] $

(6)

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

$ {E}_{\mathrm{C}}\left[{E}_{v}\right]={\int }_{{t}_{1}}^{{t}_{2}}{P}_{v}\left(t\right)\mathrm{d}t $

(7)

单个E_v的功率表示如下：

$ {P}_{v}\left(t\right)={P}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}}+({P}_{\mathrm{m}\mathrm{a}\mathrm{x}}-{P}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}})\times {U}_{{P}_{v}} $

(8)

其中：$ {P}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}} $为服务器的空闲功率；$ {P}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为服务器完全工作时的功率；$ {U}_{{P}_{v}} $为服务器的使用率。$ {U}_{{P}_{v}} $的计算公式如下：

$ {U}_{{P}_{v}}=\left\{\begin{array}{l}\frac{W\left[{E}_{v}\right]}{{W}_{\mathrm{T}\mathrm{H}}}\times 100\mathrm{\%}, W\left[{E}_{v}\right]<{W}_{\mathrm{T}\mathrm{H}}\\ 1, W\left[{E}_{v}\right]\ge {W}_{\mathrm{T}\mathrm{H}}\end{array}\right. $

(9)

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

$ {E}_{\mathrm{C}}\left[E\right]=\frac{1}{\left|E\right|}\sum\limits _{v=1}^{\left|E\right|}{E}_{\mathrm{C}}\left[{E}_{v}\right] $

(10)

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

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

$ \overline{v}=\frac{{v}_{i}-{v}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{{v}_{\mathrm{m}\mathrm{a}\mathrm{x}}-{v}_{\mathrm{m}\mathrm{i}\mathrm{n}}} $

(11)

其中：$ \overline{v} $为归一化后的数据；$ {v}_{i} $为原始数据；$ {v}_{\mathrm{m}\mathrm{i}\mathrm{n}} $、$ {v}_{\mathrm{m}\mathrm{a}\mathrm{x}} $分别为数据集合中的最小值和最大值。

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

$ S=0.5\cdot D\left[E\right]\left(X\right)+0.5\cdot {E}_{\mathrm{C}}\left[E\right]\left(X\right) $

(12)

基于此，将WESP问题的数学模型定义如下：

$ \begin{array}{l}\mathrm{M}\mathrm{i}\mathrm{n}S\mathrm{ }\left(X\right)\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{ }\ \mathrm{t}\mathrm{o}\\ \sum\limits _{j=1}^{\left|B\right|}{z}_{ik}=\{0，1\}, 1\le k\le \left|E\right|\\ \sum\limits _{i=1}^{\left|E\right|}{y}_{jk}=\mathrm{1, 1}\le j\le \left|B\right|\\ T[{E}_{v}, {U}_{n}^{i}]<{A}_{\mathrm{d}}\end{array} $

(13)

其中：$ \sum\limits_{j=1}^{\left|B\right|}{z}_{ik}=\{0，1\}, 1\le k\le \left|E\right| $表示一个基站只能被分配给一个ES，二进制变量$ {z}_{ik}=\left\{\mathrm{0, 1}\right\} $表示分配关系，$ {z}_{ik}=1 $表示将$ {B}_{k} $分配给$ {E}_{i} $，$ {z}_{ik}=0 $表示$ {B}_{k} $没有被分配给$ {E}_{i} $，$ {z}_{ik}\in \boldsymbol{Z} $；$ \sum\limits _{i=1}^{\left|E\right|}{y}_{jk}=\mathrm{1, 1}\le j\le \left|B\right| $表示ES必须被放置在基站位置上，并且一个基站只能放置一个ES，$ {y}_{jk}\in \boldsymbol{Y} $；$ T[{E}_{v}, {U}_{n}^{i}]<{A}_{\mathrm{d}} $表示用户请求接入时延小于用户最大可接受接入时延$ {A}_{\mathrm{d}} $。

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

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

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

2.1 个体编码

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

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

1）Y中任意两行对应的标记不在同一列，并且每一行有且只有一个标记，对应$ \sum \limits_{i=1}^{\left|E\right|}{y}_{jk}=\{0，1\}, 1\le j\le \left|B\right| $。

2）Z中每一列中有且只有一个标记，对应$ \sum \limits_{j=1}^{\left|B\right|}{z}_{ik}=\mathrm{1, 1}\le k\le \left|E\right| $。

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

基于此，在迭代过程中，一个麻雀个体可以由$ {X}_{ijl}^{t}=g $表示，其意义为：在第$ t $次迭代中，第$ i $个个体在第$ j $维的第l个变量为$ g $。

2.2 适应度函数

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

$ F\left(X\right)=0.5\cdot D\left[E\right]\left(X\right)+0.5\cdot {E}_{\mathrm{C}}\left[E\right]\left(X\right) $

(14)

2.3 发现者位置更新

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

$ \mathrm{R}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\left({X}_{ijk}^{t+1}\right)=\left\{\begin{array}{l}{X}_{ijl}^{t}\cdot \mathrm{e}\mathrm{x}\mathrm{p}\left(\frac{-i}{\alpha \cdot \mathrm{i}\mathrm{t}\mathrm{e}{\mathrm{r}}_{\mathrm{m}\mathrm{a}\mathrm{x}}}\right), {R}_{2}<{S}_{\mathrm{S}\mathrm{T}}\\ {X}_{ijl}^{t}+Q\cdot L, {R}_{2}\ge {S}_{\mathrm{S}\mathrm{T}}\end{array}\right. $

(15)

其中：$ \alpha \in \left(\mathrm{0, 1}\right] $为随机数；$ {R}_{2}\in \left[\mathrm{0, 1}\right] $为安全值；$ {S}_{\mathrm{S}\mathrm{T}}\in \left[\mathrm{0, 1}\right] $为警戒值；Q为服从正态分布的随机数；L为$ 1\times 2m $的矩阵，其元素全部为1；$ \mathrm{i}\mathrm{t}\mathrm{e}{\mathrm{r}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为最大迭代次数；$ \mathrm{R}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}(\cdot ) $为取整操作。当$ {R}_{2}<{S}_{\mathrm{S}\mathrm{T}} $时，环境安全，发现者执行广泛的搜索操作；当$ {R}_{2}\ge {S}_{\mathrm{S}\mathrm{T}} $时，种群中一些麻雀发现了捕食者并发出警报，此时所有的麻雀都必须改变位置。

2.4 加入者位置更新

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

$ \mathrm{R}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\left({X}_{ijk}^{t+1}\right)=\left\{\begin{array}{l}Q\cdot \mathrm{e}\mathrm{x}\mathrm{p}\left(\frac{{X}_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}-{X}_{ijl}^{t}}{\alpha \cdot \mathrm{i}\mathrm{t}\mathrm{e}{\mathrm{r}}_{\mathrm{m}\mathrm{a}\mathrm{x}}}\right), i>\frac{N}{2}\\ {X}_{\mathrm{P}}^{t+1}+|{X}_{ijl}^{t}-{X}_{\mathrm{P}}^{t+1}|\cdot {\boldsymbol{A}}^{+}\cdot L, \mathrm{其}\mathrm{他}\end{array}\right. $

(16)

其中：$ {X}_{\mathrm{P}} $为目前发现者占据的最佳位置；$ {X}_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $为当前种群的最差位置；$ {\boldsymbol{A}}^{+}={\boldsymbol{A}}^{\mathrm{T}}(\boldsymbol{A}{\boldsymbol{A}}^{\mathrm{T}}{)}^{-1} $，$ \boldsymbol{A} $是形状为$ 1\times 2m $、元素为1或-1的矩阵。当$ i>\frac{N}{2} $时，个体$ i $没有获得食物，处于十分饥饿的状态，此时个体$ i $将飞往其他地方觅食；否则，个体$ i $将向食物更加丰富的区域移动。

2.5 警戒者位置更新

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

$ \mathrm{R}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\left({X}_{ijk}^{t+1}\right)=\left\{\begin{array}{l}{X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t}+\beta \times |{X}_{ijl}^{t}-{X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t}|, {f}_{i}>{f}_{\mathrm{g}}\\ {X}_{ijl}^{t}+K\times \left(\frac{|{X}_{ijl}^{t}-{X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t}|}{({f}_{i}-{f}_{\mathrm{w}})+\epsilon }\right), {f}_{i}={f}_{\mathrm{g}}\end{array}\right. $

(17)

其中：$ {X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t} $为当前的全局最优位置；$ K\in \left[\mathrm{0, 1}\right] $是一个随机数；$ \beta $为步长控制参数；$ {f}_{\mathrm{g}} $和$ {f}_{\mathrm{w}} $分别为当前的全局最优和最差适应度值；$ \epsilon $取0.5。当$ {f}_{i}>{f}_{\mathrm{g}} $时，麻雀处于种群边缘，极易受到捕食者的攻击，需要向全局最优位置（安全位置）靠近；当$ {f}_{i}={f}_{\mathrm{g}} $时，位于种群中间的麻雀意识到了危险，并且向其他个体靠近以减少被捕食的危险。

2.6 逻辑混沌映射

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

$ \mathrm{R}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\left({X}_{ijk}^{t+1}\right)=\mu {X}_{ijl}^{t}(1-{X}_{ijl}^{t}) $

(18)

其中：$ \mu \in \left(\mathrm{0, 4}\right] $。

2.7 精英反向学习策略

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

设$ {X}_{i}=({X}_{ij1}, {X}_{ij2}, \cdots , {X}_{ij\left(2m\right)}), j=\mathrm{1, 2}, \cdots , k $为一个普通个体，其对应的极值为精英个体$ {X}_{i}^{\mathrm{e}}=({X}_{ij1}^{\mathrm{e}}, {X}_{ij2}^{\mathrm{e}}, \cdots , $ $ {X}_{ij\left(2m\right)}^{\mathrm{e}})\mathrm{ }, j=\mathrm{1, 2}, \cdots , k $，其对应的精英反向解定义如下：

$ \mathrm{R}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\left({X}_{i}^{\mathrm{e}}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\ {d}_{j}+\mathrm{m}\mathrm{i}\mathrm{n}\ {d}_{j}-{X}_{ijl}^{\mathrm{e}} $

(19)

其中：$ \mathrm{m}\mathrm{a}\mathrm{x}{d}_{j} $、$ \mathrm{m}\mathrm{i}\mathrm{n}{d}_{j} $分别为$ {X}_{i} $的第$ j $维的最大值和最小值。

2.8 CSSA算法描述

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

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

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

步骤3   计算所有个体的适应度函数值并进行排序；保存适应度值和个体位置；找出最佳适应度函数值$ {f}_{\mathrm{g}} $并保存其位置$ {X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $，转到步骤4。

步骤4   根据式（15）更新发现者的位置和适应度函数值；找出目前发现者占据的最优位置$ {X}_{\mathrm{P}} $、当前全局最差个体的$ {X}_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}} $和$ {f}_{\mathrm{w}} $，转到步骤5。

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

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

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

步骤8   将更新后的适应度函数值与步骤2中保存的适应度函数值进行比较，若小于步骤2中保存的适应度函数值，则更新适应度函数值和位置，否则不更新；更新$ {f}_{\mathrm{g}} $和$ {X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}} $，转到步骤9。

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

步骤10   比较迭代次数是否满足$ \mathrm{i}\mathrm{t}\mathrm{e}{\mathrm{r}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，若满足，则转到步骤11，否则转到步骤4。

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

3 仿真与结果分析

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

实验软硬件环境为Intel^® Core^TM i7-9750H CPU 2.60 GHz处理器、Windows 10操作系统、Python 3.7版本。核心参数设置如下：最大迭代次数$ \mathrm{i}\mathrm{t}\mathrm{e}{\mathrm{r}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\in [60 \sim 100] $，种群数量$ N\in [60\sim 80] $，$ {P}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}}=0.3w $，$ {P}_{\mathrm{m}\mathrm{a}\mathrm{x}}=0.5w $，$ {W}_{\mathrm{T}\mathrm{H}} $为3×10⁸ min，ES将负载迁移到远程云产生的固定时延$ {T}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为0.5 s，最大接入时延$ {A}_{\mathrm{d}} $为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数量的增加，不同算法的平均时延均呈现下降的趋势，主要原因为当基站总数不变时，随着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数量的增加，不同算法的平均能耗都有下降的趋势。CSSA的平均能耗最少，之后是Top-K，其他算法的平均能耗均很高，分析其原因是CSSA和Top-K放置时考虑了负载因素，而其他算法放置的依据是距离，忽略了对能耗影响较大的负载因素，所以平均能耗表现很差。

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

由图 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 结束语

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