边缘计算 课件 第二章 边缘服务器部署

边缘服务器部署倡和正学出新明德1.概念理解：边缘服务器部署定义、重要性、应用场景

2.算法掌握：优化算法原理、改进策略、实现方法

3.模型构建：网络模型、覆盖模型、时延模型、成本模型

4.实践应用：动态部署策略、实验结果分析、优化建议

这节课的学习目标是什么？2.1边缘服务器部署基础2.2边缘服务器部署系统模型2.3边缘服务器的动态部署2.4边缘服务器部署实验结果及分析2.1边缘服务器部署基础

目录2.1.1微云放置012.1.2服务放置022.1.3服务器部署03042.1.4蛇优化算法

微云放置

边缘计算的相关研究中，确定边缘服务器部署方案是移动边缘计算研究的第一步。

微云是与本地网络中的无线接入点共址的服务器集群，移动用户可以将他们的任务卸载到资源丰富的微云进行处理。

与远程云处理方式相比，移动用户和微云之间更短的物理距离意味着微云的任务访问与卸载的延迟大大降低，从而显著改善了用户体验。代表性微云放置研究：目标：主要集中在最小化用户访问延迟、降低部署成本、节约系统能耗、提高资源利用效率和保证系统容错性。方法：包括启发式算法、元启发式算法（如差分进化布谷鸟搜索）、整数规划模型和近似算法等。2.1.1微云放置研究背景和代表微云放置与边缘服务器部署的根本区别：部署位置约束边缘服务器必须部署在基站上，这是其成本最小化的基本条件；而微云只需靠近用户，位置选择更灵活，不一定在基站。边缘服务器部署研究趋势：重要性凸显：随着边缘计算研究的深入，边缘服务器的合理放置愈发重要。研究焦点：当前研究主要围绕降低延迟、节约能耗和负载均衡等目标展开。问题分类：研究者将边缘服务器部署问题分为硬件部署和软件部署两部分。2.1.1微云放置研究趋势

服务放置

定义：即软件部署，是指在已存在的边缘服务器上，决定将哪些应用服务部署在哪些服务器上的过程。最终目标：是进一步降低用户访问延迟，提升服务器可用性。与“边缘服务缓存”的关键区别：服务缓存：缓存的是短期的、热门的静态内容（如视频、网页）。服务部署：部署的是具有长时间可用性的完整应用服务（如AI推理、游戏渲染服务）。因此，部署方案需要更全面地考虑应用种类和资源需求。2.1.2服务放置核心概念与界定2.1.2服务放置现有研究综述现有研究普遍采用联合优化的视角，将服务放置与其他网络决策结合起来，以解决资源约束下的复杂调度问题。研究核心方法与贡献接入网络选择与服务放置联合优化设计在线框架，平衡多种延迟（接入、通信、切换），提出基于迭代的高效算法，并有严格的理论分析。服务放置与请求调度联合优化提出双时间尺度框架，在多重资源约束下，开发了在特定条件下最优的多项式时间算法。服务放置与请求路由联合优化针对海量服务请求与带宽不匹配问题，提出基于随机舍入的近似算法，处理多维资源约束。协作服务放置将问题转化为基站与用户的关联问题，利用匹配理论设计去中心化算法，最小化服务转发带来的流量负载。资源受限网络的服务部署综合考虑服务器资源、应用业务逻辑和响应时间约束，目标是以最小成本生成最佳部署方案。

服务器部署

定义：即硬件部署，根据地理位置、网络状况和现有网络拓扑，决策边缘服务器物理设备的放置位置、数量和规模。目标：

提供高可用性服务，满足系统最高承载能力，处理大量数据，并保证服务质量。2.1.3服务器部署核心问题与目标2.1.3服务器部署现有研究综述优化目标方法与模型未明确单一目标结合K-Means和混合整数二次规划，但计算复杂度高。最大化服务器负载和整合的通信量混合整数线性规划，并设计基于图的算法。提供低延迟、高可靠的车载服务使用非支配排序遗传算法，侧重服务器放置本身。负载均衡与降低延迟表述为多目标约束优化问题，使用混合整数规划。最小化系统能耗多目标优化，提出基于粒子群优化的能耗感知算法。最小化部署成本（服务器数量）提出两种启发式算法和一种贪心算法。距离最小化、容量限制下的负载均衡提出PACK算法，支持服务器间工作负载共享。重要性：硬件部署是实施边缘系统的基本问题，对成本、服务质量和系统性能有重大影响。核心局限：上述研究普遍未考虑用户的移动性。在静态假设下优化的部署方案，在用户移动时可能无法保证：网络连接的稳定性服务的连续性稳定的低延迟体验未来方向：必须研究考虑用户移动性的边缘服务器部署方法，是提升现实世界服务体验的关键。2.1.3服务器部署研究的共同局限与未来方向

2.1.3服务器部署实验数据说明

上海基站的分布图为进行相关研究，本章采用了上海电信基站数据集，包含百万级用户上网日志和位置信息。通过预处理，选取了一天中6个关键时间点（4点、8点、12点、16点、20点、24点）的用户数据和位置进行实验，这是为了捕捉不同时段用户空间分布的动态变化，为研究移动性-aware的部署方法提供数据基础。

蛇优化算法

2.1.4蛇优化算法2.1.4蛇优化算法2.1.4蛇优化算法2.1.4蛇优化算法2.1.4蛇优化算法2.1.4蛇优化算法蛇优化（SnakeOptimization,SO）算法是一种新型的元启发式优化算法，模拟了蛇在不同温度、不同食物条件下的不同行为模式，进行最优值的查找。2.2边缘服务器部署系统模型

目录2.2.1网络模型012.2.2覆盖模型022.2.3时延模型032.2.4成本模型042.2.5问题描述05

网络模型

2.2.1网络模型本章考虑的场景如图所示。m个静态边缘服务器

，其中

，放置在小区等用户相对集中的地方。n个动态边缘服务器

，其中

，放置在公园等用户流动性较大的地方。

表示第k个用户，其中

。服务器放置场景图

覆盖模型

2.2.2覆盖模型边缘服务器的覆盖模型旨在实现高效的任务处理和分配，提高系统性能和用户体验。该模型考虑了每个用户随机产生大小不同的任务数据，以及边缘服务器和云服务器的不同计算能力和覆盖范围。注意：当一个边缘服务器接收的任务数据已经达到其计算能力上限时，即使用户在其覆盖范围内，任务也无法被卸载至该边缘服务器。此时，用户可以将任务卸载至最近的其他未达到计算能力上限且能够覆盖该用户的边缘服务器或云服务器上。用户位于边缘服务器覆盖范围内位于边缘服务器覆盖范围外任务被卸载至最近的边缘服务器进行处理任务将被卸载至云服务器进行处理2.2.2覆盖模型距离计算公式假设边缘服务器的覆盖半径为r，当用户与边缘服务器之间的距离d小于r时，用户被边缘服务器覆盖，用户与边缘服务器之间的距离d由Haversine公式来计算。假设用户的经纬度坐标为（lat1，lon1），边缘服务器的经纬度坐标为（lat2，lon2），则用户与边缘服务器之间的距离d可以通过下列公式表示如下：其中

，

，

。

时延模型

2.2.3时延模型2.2.3时延模型2.2.3时延模型

成本模型

2.2.4成本模型边缘服务器静态边缘服务器：一旦放置后不会轻易移动动态边缘服务器：随着用户流动而进行移动放置边缘服务器的成本有三个主要组成部分：固定成本指用于购买和部署边缘服务器的成本。补偿成本指空闲的边缘服务器被用于其他用途，以补偿部署成本。动态成本指边缘服务器在动态放置过程中发生的位置变化而产生的成本。2.2.4成本模型2.2.4成本模型

问题描述

2.2.5问题描述

本章的目标是根据环境的变化，通过网络模型、边缘覆盖和用户时延，找出在满足一定范围内的延迟的不同环境下，边缘服务器的数量和放置位置。可将问题建模为：

其中，公式（2-34）表示本章优化的目标即放置边缘服务器的总成本，公式（2-35）表示在边缘服务器上处理的任务数据要小于所有用户的数据总和，公式（2-36）表示边缘服务器接收的用户数据要小于边缘服务器的计算能力，公式（2-37）表示计算出的平均用户时延要满足一定的范围。

2.3边缘服务器的动态部署目录2.3.1蛇优化算法的改进012.3.2边缘服务器动态放置算法022.3.3基于线性规划问题的成本算法03

蛇优化算法的改进

2.3.1蛇优化算法的改进边缘服务器动态放置方法是一个循环执行的闭环系统，核心流程为以下四个步骤：初始位置寻优：在初始时刻或当前时刻，使用改进的蛇优化算法，通过独特的映射策略（将高维变量映射为二维坐标），在二维空间中搜索满足延迟要求的最佳边缘服务器放置位置。动态调整：环境发生变化后，通过边缘服务器动态放置算法，基于ISO算法的结果，调整服务器的数量和位置，以适应新环境并满足延迟要求。移动成本优化：在确定了当前和下一时刻的服务器位置后，使用最小放置成本算法，计算如何以最小的移动成本（如迁移、部署成本）将服务器从当前位置调整到下一时刻的目标位置。总成本计算：综合移动成本及其他可能因素，计算出下一时刻部署和运行边缘服务器的总成本。此结果将作为系统决策的依据，并开启下一轮的动态调整循环。蛇优化算法的改进：结合粒子群优化算法的思想，提高算法的全局搜索能力引用双向搜索策略，增强算法的寻优能力借鉴精英引领思想，使优秀个体更易传播其信息2.3.1改进一：结合PSO算法SO算法在早期迭代时是使用随机搜索来探索区域，具有高度的不确定性。PSO算法相较于SO算法在迭代前期具有较快的收敛速度。因此，在算法迭代前期可结合PSO算法对SO算法进行改进。具体改进措施如下：在PSO算法中，雄性个体与雌性个体的位置更新公式为当前位置加下一时刻的速度，即：

其中

与

表示第

代时雄性个体与雌性个体的位置。

与

表示第

代雄性个体与雌性个体的速度，其更新公式为：其中

为惯性权重，

与

表示第代时雄性个体与雌性个体的速度，

与

表示第

次迭代后，第

个雄性蛇与雌性蛇的最优解，

与

表示第

次迭代后，整个雄性与雌性群体中的最优解。2.3.1改进二：双向搜索策略当temperature>Threshold2时，蛇会进入小范围搜索模式去寻找食物。原算法在此过程中的寻优能力较弱，此时可以通过双向搜索策略增加找到局部最优解的能力。双向搜索是一种利用最好和最差的个体在搜索区域内进行探索的策略。目的：让算法远离最坏的个体，同时保持接近最好的个体。具体的位置更新公式表示为：其中，

和

分别表示最好和最差的雄性。

和

分别表示最好和最坏的雌性。双向搜索使算法在充分利用搜索区域的情况下接近最优值，加快了算法的收敛速度。2.3.1改进二：双向搜索策略图2-5双向搜索策略位置更新前图2-6双向搜索策略位置更新后以二维空间为例，该策略的可视化图如图2-5、图2-6所示，有六个个体在某一时刻的位置分布图。规定越靠近坐标轴零点代表适应度值越好当使用双向搜索策略时，其中某个蛇的位置变化如图所示，图2-5中橙色线表示该个体向最好个体靠拢，蓝色线表示该个体远离最差个体。黑色线表示该个体在最好最坏个体影响下的最终移动方向及距离。图2-6表示该个体移动后的位置分布图。移动个体变为适应度最好个体，原本最好个体变为其余个体。蓝色蛇：最好个体

棕色蛇：最差个体

绿色蛇：其余个体2.3.1改进三：精英引领策略在SO算法中，蛇交配后存在一定概率产生蛋，即通过随机生成的解替换掉最差的解。然而，随机解的盲目性会降低算法快速寻找最优解的能力。因此，在此处采用精英引领策略，用来替换算法中后10%适应度较低的个体，以增加找到最优解的概率。具体的公式如下所示：

其中

表示全部雄性个体中最优的个体，

表示全部雄性个体中最优的个体，此处改进可避免随机解的盲目性，提高算法的收敛速度和解的质量，并增加找到最优解的概率。2.3.1改进三：精英引领策略该策略的可视化图如图2-7、图2-8所示，图中共有8个个体在某一时刻的位置分布图。当使用精英引领策略时，棕色蛇的位置变化如图所示，图2-7中蓝色线表示该个体向最好个体靠拢，橙色线表示该个体具体移动的方向和距离。图2-8表示适应度后10%个体移动后的位置分布图。原本最好个体变为其余个体，原本其余个体有的变为后10%适应度个体。蓝色蛇：适应度最好的个体棕色蛇：适应度位于后10%的个体绿色蛇：其余个体图2-7精英引领策略位置更新前图2-8精英引领策略位置更新后边缘服务器动态放置算法

2.3.2边缘服务器动态放置算法该策略是一个基于延迟反馈的闭环动态调整系统，具体来说，该策略包含以下三个关键机制：1.初始状态：在人群密集区域预先部署静态边缘服务器，作为基础设施的基础。2.延迟过高时的扩容策略：首要措施：优化现有资源，优先调整动态边缘服务器的位置以更有效地服务用户。终极措施：当优化位置无效时，增加动态边缘服务器的数量，直接提升服务能力，确保延迟达标。3.延迟过低时的缩容策略：当系统性能过剩时，主动减少动态边缘服务器的数量。这样做既维持了延迟要求，又将多余的服务器资源释放出来用于别处，从而补偿部署成本，提升资源利用率和经济性。这种方法的核心优势在于其灵活性和成本效益。它通过一个持续的“监控-判断-调整”循环，实时响应环境变化，既保证了服务质量（低延迟），又避免了资源闲置，实现了服务性能与部署成本之间的高效平衡。基于线性规划问题的成本算法

2.3.3基于线性规划问题的成本算法核心问题：旨在解决当多个动态边缘服务器需要重新部署时，如何找到一种分配方案，使得所有服务器从“原位置”移动到“新位置”的总移动距离最小。问题本质：这是一个典型的指派问题或二分图最小权匹配问题。即如何将一组“原位置”点与一组“新位置”点进行一一配对，使得所有配对点之间的总距离最短。挑战：当服务器数量增多时，可能的分配方案数量会呈阶乘级增长，暴力枚举法不可行。解决方法：该问题被建模为一个线性规划问题，并采用内点法进行高效求解。1.内点法的核心思想：与传统方法沿着可行域的边界搜索不同，内点法是从可行域的内部直接穿越，逐步逼近最优解。这种方法避免了在边界上的复杂遍历，因此迭代次数更少，求解效率更高。2.内点法在每次迭代中，算法会：计算梯度与Hessian矩阵：确定当前点的优化方向和曲率。解牛顿步长和减量：确定下一步移动的方向和步长。线搜索与更新解：确保在向最优解靠近的同时，始终保持在可行域内部。

2.4边缘服务器部署实验结果及分析目录2.4.1参数设置01

2.4.2实验结果022.4.1参数设置本章实验的参数取值见表参数取值信道带宽10MHz用户传输功率0.2W路径损耗因子2用户与边缘服务器间的信道增益0.1噪声功率1.6×10用户与云服务器间信的道增益0.98用户到云服务器的距离1×106m2.4.2实验结果如图表示当改变边缘服务器的计算能力时，不同时间点所对应的成本值。从图中可以看出：随着边缘服务器计算能力的增加，不同时间点所对应的成本值呈下降趋势。这是因为随着计算能力的提升，需要边缘服务器的数量减少，从而导致成本的降低。随着边缘服务器计算能力的增强，成本值也越来越接近。这是因为在边缘服务器覆盖范围内，有些用户由于边缘服务器计算能力不足而无法将任务卸载至服务器，因此需要额外的服务器来满足需求。然而，随着计算能力的提高，由于计算能力不足而增加服务器数量的情况逐渐减少。因此，随着边缘服务器计算能力的增强，成本值逐渐趋近于一个稳定值。2.4.2实验结果如图表示当改变边缘服务器的计算能力时，不同时间点对应的用户平均延迟。从图中可以看出：随着边缘服务器计算能力的增大，用户的平均延迟逐渐降低。这是因为当边缘服务器的计算能力增大时，更多的用户可将任务卸载至边缘服务器处理，不必卸载到云端，从而减少延迟。2.4.2实验结果如图表示当改变边缘服务器的覆盖范围时，不同时间点对应的成本值。从图中可以看出：随着边缘服务器覆盖范围的增加，不同时间点所对应的成本值呈下降趋势。这是由于覆盖范围的扩大能够减少对动态服务器的需求，从而降低成本。通过增加边缘服务器的覆盖范围，可以覆盖到更多的用户，无需额外的动态服务器。因此，随着边缘服务器覆盖范围的增加，成本值逐渐减少。2.4.2实验结果如图表示当改变边缘服务器的覆盖范围时，不同时间点对应的用户平均延迟。从图中可以看出：随着边缘服务器覆盖范围的增大，用户的平均延迟逐渐降低。这是因为边缘服务器覆盖范围的扩大使得更多的用户可以被覆盖到，用户可将任务卸载到边缘服务器进行处理，而无需依赖云端，从而降低延迟。2.4.2实验结果如图表示当改变用户随机生成任务数量的最大值时，不同时间点对应的成本值。从图中可以看出：随着用户随机生成的任务数量变大，不同时间点所对对应的成本值呈上升趋势。