面向边缘计算的高效基站部署：一种最外层用户优先的启发式方法

《Future Generation Computer Systems》：Efficient base station deployment for edge computing: An outermost-users-first heuristic approach

　　

摘要

基站（BS）的高效部署是建立可靠且具有成本效益的边缘计算网络的基础。主要挑战在于在几何覆盖模型下，以最少的基站数量实现对预定用户位置的完全覆盖。这一难题在现实场景中因用户的地理分布不均匀而加剧，其中稀疏分布的边缘用户往往被忽视。为了解决这一问题，本文将基站部署建模为一个组合优化问题，并提出了一种新颖的启发式策略：在覆盖内部区域之前，优先利用凸包算法识别并覆盖最外层的边缘用户。这种"由外向内"的方法系统地最小化覆盖缺口和冗余部署，在给定模型假设下保证对用户分布的完全覆盖。本文将提出的方法与一系列基线算法进行了对比评估，包括基于聚类的方法、经典启发式方法和元启发式算法，使用了两个真实世界数据集和一个合成数据集。实验结果表明，在所有数据集和不同规模下，本文方法在保持输入用户分布覆盖的前提下始终需要的基站数量最少。其性能稳健稳定，并随问题规模的增长呈现可预测的扩展性，显著优于所有其他方法。值得注意的是，与通用元启发式算法性能波动不同，这种领域特定的设计在空间受限的规划问题中证明更加可靠和高效。这些发现证实，设计良好的、结合领域信息的启发式算法在复杂基础设施部署任务中可以优于通用优化算法。本工作为边缘计算规划提供了一种实用且优越的解决方案，并突显了在未来研究中将此类启发式规则整合到混合优化框架中的潜力。

引言

深度学习已被广泛应用于移动和无线网络中，推动了日益复杂的移动应用的发展，这些应用能够从多样化设备生成的用户数据中提取高价值信息 [1]、[2]。然而，移动设备通常面临电池寿命有限和计算能力不足的问题，而云计算和集群计算等集中式计算范式则引入了高网络延迟，且往往难以保证数据隐私和安全。为应对这些挑战，边缘计算作为一种有前景的范式，近年来受到了学术界和产业界的广泛关注 [3]、[4]。通过在靠近数据源的位置部署计算资源，边缘计算增强了移动设备的能力，并减少了数据源与处理单元之间的数据传输延迟。

典型的边缘计算系统由多个地理分布的边缘计算中心（称为"边缘节点"）组成。每个边缘节点配备一个网络接入点，使移动设备能够访问本地边缘资源或将请求转发至其他边缘节点或云端，从而实现边缘-云协同 [5]、[6]。多种无线技术，如微型和空中基站（BS）[7]、[8]、WiFi [9]、ZigBee [10]以及低功耗蓝牙（BLE）[11]，均可作为接入点。本文聚焦于基站作为代表性接入单元，鉴于其在5G电信网络中的基础性作用 [12]。由于物理空间限制和资源成本，每个边缘节点的处理能力有限，因此需要进行精细的资源管理以避免效率低下和性能下降。

部署边缘计算服务涉及两个相互关联的阶段：基站部署和资源配置（如边缘服务器放置）。第一阶段从一组候选站点中确定基站的物理位置，旨在最小化部署成本同时最大化网络覆盖。第二阶段为每个已部署基站分配计算资源，平衡服务质量与基础设施支出。本文主要关注基站部署优化问题，因为系统的部署策略是基础性的，直接影响后续资源分配的有效性。本文讨论的解决方案适用于以下场景：(1) 建立新的边缘计算平台，(2) 扩展现有基础设施，或 (3) 动态缩减运营规模（如让基站进入睡眠模式）以在低需求时段节省能源。我们指出，资源配置以及部署与资源分配的联合优化是未来工作的重要方向，待建立高效部署框架后将进一步探索。

尽管已有几项研究涉及边缘部署优化，但大多数假设基站已经部署，转而关注资源配置。仅有少数工作直接解决基站部署问题 [13]、[14]、[15]。值得注意的是，通过将边缘节点建模为用户、边缘服务器建模为基站，资源配置方法可以借鉴用于解决基站部署问题，这突显了两者之间的结构相似性。

现有的边缘/基站部署方法可分为三类：启发式方法 [13]、[15]、[16]、基于聚类的方法 [14]、[17]、[18]以及全局优化搜索方法 [19]、[20]、[21]、[22]、[23]。为最大化用户覆盖，启发式方法通常迭代选择覆盖用户最多的候选站点。基于聚类的方法首先按位置对用户分组，然后在聚类中心附近部署基站。然而，贪心方法和基于聚类的方法都存在一个共同局限性：它们往往忽视人口稀疏区域（如郊区或偏远地区）的用户。由于贪心启发式方法在早期迭代中优先考虑高密度区域，稀疏分布的边缘用户被推迟到后期阶段处理，此时每个额外基站可能仅覆盖一两个用户，导致基站总数膨胀。另一方面，基于聚类的方法可能在聚类边界处留下未覆盖用户，当最近的候选站点位于所需覆盖半径之外时。这一根本性弱点将在下一节进一步阐述。全局优化方法通常受自然或社会现象启发，可能比启发式方法产生更优解，但由于搜索空间呈指数增长，难以应对大规模问题。在拥有数万个候选站点的现实场景中，搜索空间变得极其庞大，难以保证获得最优解。

为克服现有启发式方法和基于聚类方法的局限性，本文提出了一种新颖的启发式基站部署策略，优先覆盖位于区域边界的用户。该设计源于以下观察：边界用户通常位于人口密度较低的郊区，容易被基于聚类的方法忽视，可能需要专门的基站部署 [24]。我们的方法迭代执行两个步骤，直到所有用户被覆盖：(1) 使用凸包算法识别最外层用户，(2) 选择覆盖这些边界用户数量最多的候选站点并在该处部署基站。在公开真实世界数据集上的评估表明，我们的方法能以最少的基站数量实现完全用户覆盖，优于多种现有启发式方法和全局优化策略。

本文其余部分组织结构如下。第2节介绍我们启发式基站部署方法的动机。第3节对基站部署问题进行建模，设定最大化用户覆盖和最小化已部署基站数量的双重目标。第4节详细介绍提出的启发式方法，第5节使用真实世界数据集评估其性能。第6节讨论相关工作。最后，第7节总结全文。

章节片段

动机

为清楚阐明现有贪心方法和基于聚类方法的局限性，并说明我们"最外层用户优先"策略的动机，我们在图1中展示了一个简单示例。图1a所示环境包含三个候选基站部署站点（A、B和C）以及十个地理分布的用户。最优解决方案在A和C处部署基站，仅用两个基站即可实现100%用户覆盖。

贪心启发式方法。现有贪心方法迭代选择覆盖

问题描述

本节首先对本文处理的基站部署问题进行建模，然后展示所提出模型如何扩展以适应更广泛的应用场景。

先覆盖最外层用户的启发式基站部署

在现实边缘计算环境中，区域中心的用户密度通常远高于边缘区域，这一模式可由图2数据支持。尽管现有基站部署策略通常优先覆盖人口密集区域，但这种做法可能导致需要部署过多基站才能覆盖沿区域边缘稀疏分布的用户。为解决这一效率问题，本节提出一种启发式基站部署

性能评估

我们首先在两个真实世界数据集和一个合成数据集上评估所有算法，以验证所提方法的性能。随后通过测试从三个数据集中随机抽取的不同大小子集（以用户数和候选站点数计）来检验其稳定性。由于基站部署属于离线规划任务，执行时间并非主要关注点。尽管如此，所有算法均能在台式机上于数分钟至数十分钟内完成

相关工作

边缘计算因其低延迟和安全的服务交付而被广泛应用于农业 [46]、医疗 [47]和交通 [48]等领域。大量研究聚焦于通过边缘服务器放置、边缘缓存和任务卸载等策略改进边缘计算服务。在此背景下，基站（BS）部署是实现边缘计算服务的基础性初始决策。

已有若干工作解决了BS

结论

本文研究了边缘计算基站（BS）部署这一NP困难问题，目标是在非均匀空间分布下保证完全用户覆盖的同时最小化基站数量。我们提出了COUF，一种新颖的启发式算法，利用凸包算法迭代识别并覆盖最外层用户，在解决内部区域之前系统地消除外围覆盖缺口。我们证明了该算法的收敛性和完全覆盖保证，

CRediT作者贡献声明

Bo Wang：撰写——原稿，监督，软件，方法论，概念设计。Xiaoyun Qin：撰写——审阅与编辑，撰写——原稿，可视化，资金获取。Zhifeng Zhang：资源，项目管理，调查，形式化分析。Ying Song：撰写——原稿，验证，形式化分析。

利益冲突声明

作者声明他们不存在已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

Bo Wang目前任职于河南理工大学计算机科学与技术学院副教授。他于2017年获西安交通大学计算机科学博士学位，于2010年获东北林业大学计算机科学学士学位。2012年至2016年期间，他在中国科学院计算技术研究所担任访问学生研究员。他的研究方向包括

Bo Wang|Xiaoyun Qin|Zhifeng Zhang|Ying Song

河南理工大学，河南省新乡市平原大道东699号，453003，中国