随着无线通信需求的持续增长和网络基础设施建设的快速推进，5G网络在当今经济社会发展和日常生活中扮演着重要的角色，为医疗、保健、娱乐、车联网、物联网和工业物联网等各行各业提供支持，这些应用往往需要在超低延迟下才能获得最佳性能^[1]. 基站的合理部署，是移动网络良好覆盖和最佳性能运行的保证 ^[2]. 基站选址是5G网络系统运维的关键决策环节，5G基站的合理选址确保了移动网络的良好覆盖和最佳性能运行，是确保高质量5G网络建设和信息服务的重要基础. 该问题的核心是在满足基站容量的前提下从待选址区域中选择候选站址，实现最大化基站覆盖率，并尽可能减少基站数量，满足上述条件的基站站址称为最优站址.

由于5G技术所使用的毫米波具有频率高和传播损耗大的特点，相较4G基站而言，相同面积区域内5G基站分布会更加密集^[3]. 不合理的5G基站选址，会导致基站间的覆盖范围存在大量重合，导致许多用户需求点（即一段时间内用户的终端位置）被重复覆盖，从而降低整体覆盖率. 然而，从候选基站站址中选出最优站址是NP难问题^[4]，5G基站选址方法的研究极具挑战. 近年来，大多数选址方案是以覆盖率最大化为优化目标，利用遗传算法、免疫算法等进化算法对基站选址方案进行优化求解^[5-9]. 这些算法的复杂度较高，当5G基站数量大幅增加时，算法的收敛时间会呈指数级增长，难以在短时间内选出最优站址.

随着移动通信网络的快速发展和广泛应用，大量包含地理位置等信息的用户终端通信历史数据反映了用户在相应地理位置的通信需求（其中的终端位置称为用户需求点），是合理选择基站站址的重要依据和基础. 因此，如何基于用户终端通信历史数据，在满足基站容量的前提下选出重合覆盖范围最小的基站，成为提高基站覆盖率的重要保证，也是基站高效选址和5G通信基础设施精准建设及高效运维的关键所在. 对此，本文讨论2个问题：1）在考虑基站容量的前提下，如何利用用户需求点度量基站的重合覆盖范围；2）如何高效地选出重合覆盖范围最小的基站集合.

本文基于用户终端通信历史数据，研究用户需求驱动的5G基站选址方法. 为了在满足基站容量的前提下选出具有最小重合覆盖范围的基站站址，本文首先提出规划区域网格化技术，将所有用户需求点映射到规划区域的对应网格中，从而将基站所覆盖需求点数的计算转换为基站覆盖网格集合及位于网格内的需求点数的计算，从而降低基站重合覆盖程度计算的时间复杂度. 为了在用户需求点上反映基站的覆盖情况，提出基站之间重合覆盖程度的度量方法，利用用户需求点来计算2个基站之间重合覆盖范围占其总覆盖范围的比值，称为基站间的贴近度. 在此基础上，进一步设计分离度计算方法，从而计算基站与其他所有基站之间的覆盖不重合部分与总覆盖范围的比值，然后在其基础上构建目标函数.

将用户需求点类比为社交网络中的用户节点，基站节点对用户需求点的覆盖程度类比为社交网络影响力指标，此时，可借鉴社交网络中影响力最大化的思想^[10]来优化基站覆盖率. 当向集合中增加1个元素时，该集合对应函数所增加的值称为集合增益，子模性定义为随着集合元素的增加其函数值增益逐渐减小^[11-12]. 基于子模性和贪心思想的方法能有效获得影响力最大化问题的最优解，该类方法在社交网络中选择影响力最大的种子节点时取得了良好效果^[13-16]，为基站选址提供了参考.

基于上述思想求解5G基站选址的优化问题，本文在分离度概念与计算方法基础上，考虑基站重合覆盖范围的重复计算过程，以分离度最大化为目标，构建反映所有基站分离度的目标函数. 由于5G基站数量越多，覆盖范围的重合部分越多，基站的分离度增益就越小. 将5G基站看作集合元素，分离度看作其函数值，给出分离度最大化的目标函数满足子模性的证明，进而针对5G基站选址问题，提出用于最优5G基站选址的贪心算法.

综上所述，本文主要贡献有4个方面：

1）提出规划区域网格化方法，将用户需求点分配到相应网格中，以提高各基站间贴近度的计算效率；

2）提出基站间贴近度的概念及其计算方法，基于需求点和基站容量量化基站间的重合程度，为后续目标函数设计提供了具体的量化指标和计算依据；

3）给出5G基站选址问题的目标函数并证明其子模性，基于贪心算法思想给出了最优5G基站选址方法；

4）在8个不同数据集上的实验结果表明，本文方法可实现较高的需求点覆盖率和面积覆盖率，同时具有较高的效率.

1.   相关工作

下面阐述基于进化算法和基于机器学习算法的站址选择方法，并分析国内外研究现状.

1）基于进化算法的站址选择. 在基站选址方面，文献[5]以覆盖率、成本和干扰作为基站选址的优化目标，使用遗传算法优化站点坐标、发射功率、高度和倾斜度等设计参数，进而使基站覆盖率最大，成本和干扰最小. 文献[6]以成本和覆盖率为优化目标，设计基于反学习的种群初始化方案和精英交叉策略，利用改进的免疫算法对3G基站进行选址优化，以达到最小成本和最大覆盖率. 文献[7]给出通过免疫计算的选址优化方案，联合优化IEEE802.16j网络中基站和中继站的位置，以较低代价获得较高容量，降低网络建设总体代价. 文献[8]以分布式MIMO系统的信道容量为优化目标，使用粒子群算法对基站小区的天线位置进行优化，找出最优的天线放置位置. 文献[9]提出基于改进NSGA-2算法和Atoll仿真的基站选址优化方案，充分考虑建设成本、光纤接入位置和有效覆盖范围等因素，有效指导电力无线私有网络建设.

进化算法也被用于其他领域站址的选择，例如，文献[17]以建设成本、运维成本和出行成本为优化目标，将汽车电池交换站建模为数学优化问题，提出一种基于免疫优化的算法，对电池交换站进行合理选址，使总成本最小. 文献[18]以市民服务最大化和成本为目标，基于城市的真实信息提出多目标遗传算法，通过优化车辆的平均等待时间、充电站的闲置时间等参数，以确定汽车充电站最优的位置. 文献[19]针对树状供应链系统，考虑需求不确定性和设施中断风险，提出供应链选址-库存决策模型，以系统期望总成本最小化为目标，并通过混合遗传算法进行优化.

2）基于机器学习算法的站址选择. 文献[20]通过使用基于密度的聚类算法筛选极弱覆盖点，并在聚类中心位置建设宏基站，以解决移动数据业务量增加导致的基站设备覆盖需求，并根据弱覆盖点到聚类中心的距离，利用数学期望规划基站的主方向角度，达到提高覆盖率和解决弱覆盖点的目的，同时降低建设成本. 文献[21]旨在使用地理信息系统和多标准分析方法，结合随机森林算法，找到在省会城市建立医院的理想地点，帮助决策者加快对COVID-19大流行的控制. 文献[22]提出一种基于图卷积网络的店铺选址模型，通过考虑地理空间的相互作用和交通网络对店铺选址的影响，有效预测不同地区店铺的吸引力，为店铺选址问题提供了新的思路. 机器学习算法通常基于大量的标记数据进行模型训练并进行预测，对于基站选址问题，可使用无监督学习算法对用户需求点进行聚类，以簇中心点坐标确定基站站址. 然而，当需求点分布不均或密度较低时，仍存在基站覆盖不完整或未能满足所有用户需求的问题.

2.   基站间重合覆盖范围度量

本节首先给出相关定义，然后给出规划区域网格化方法以及基站间的贴近度和分离度的度量方法.

2.1   相关定义

表1给出相关符号及其描述. 候选基站为候选基站站址上待建的基站，需求点$D$为用户历史终端位置数据，候选基站和需求点的坐标均在规划区域内. ${v}_{i}({v}_{i}\in V)$为在规划区域$A$内的第$i$个候选基站，其横坐标和纵坐标分别表示为${v}_{ix}\in \left[{{a}_{x},b}_{x}\right]$和${v}_{iy}\in [{{a}_{y},b}_{y}]$. 需求点${d}_{i}($${d}_{i}\in D)$表示在规划区域$A$内第$i$个需求点，其横坐标和纵坐标分别表示为${d}_{ix}\in \left[{{a}_{x},b}_{x}\right]\mathrm{和}{d}_{iy}\in [{{a}_{y},b}_{y}]$.

表  1  符号描述

Table  1.  Description of Symbols

符号	描述
$A$	规划区域
$({a}_{x},{a}_{y})，({b}_{x},{b}_{y})$	$A$的西南角坐标、东北角坐标
$V=\left\{{v}_{1},{v}_{2},… ,{v}_{n}\right\}$	候选基站集合
$({v}_{ix},{v}_{iy})$	基站${v}_{i}$的坐标
$r$	基站覆盖半径
$\varepsilon$	基站容量
$D=\left\{{d}_{1},{d}_{2},… ,{d}_{m}\right\}$	需求点集合
$({d}_{ix},{d}_{iy})$	需求点${d}_{i}$的坐标
$G=\left\{{g}_{1},{g}_{2},… ,{g}_{t}\right\}$	方形网格集合
$({g}_{ix},{g}_{iy})$	网格${g}_{i}$的中心点坐标
$l$	$G$中网格的边长
$S=\left\{{v}_{1},{v}_{2},… ,{v}_{k}\right\}$	候选基站子集（$S\subseteq V$）
$N({v}_{i})$	基站${v}_{i}$覆盖的需求点数
$N({v}_{i},{v}_{j})$	基站${v}_{i}$和${v}_{j}$共同覆盖的需求点数
${\alpha }_{{v}_{i}}$	容量系数
$pd({v}_{i},{v}_{j})$	基站${v}_{i}$和${v}_{j}$的贴近度
$npd(S,j)$	基站$j$和$S$的分离度
$C(S)$	覆盖率（S中基站覆盖的需求点数与总需求点数之比）

下载: 导出CSV 

| 显示表格

针对规划区域$A$，本文从$A$中的候选基站集合$V$中选出一个子集$S$，使得覆盖率$C(S)=\dfrac{p(S)}{\left|D\right|}$最大化，$\left|D\right|$表示规划区域内需求点总数，$p(S)$表示$S$中所有基站覆盖的需求点数，$S=\left\{{v}_{1},{v}_{2},… ,{v}_{k}\right\}$.

2.2   规划区域网格化

基于需求点数据优化5G基站站址，由于在基站之间重合覆盖程度即基站之间共同覆盖需求点数的计算中，总计算次数为$C_{n}^{2}\times m$，其中，$m$和$n$分别表示需求点数和基站数，$C_{n}^{2}$表示从$n$个不同基站中任意选取2个基站的组合数量，而$m$和$n$通常较大、计算复杂度高.

因此，将规划区域A沿水平和垂直方向划分为$t$个大小相等的方形网格，边长均为$l$，每个网格代表一定范围内的地理区域. 其中，网格数量$t = \dfrac{1}{{l}^{2}}{({b}_{x}-{a}_{x})({b}_{y}-{a}_{y})}$，其大小取决于网格边长$l$，第$i$个网格表示为${g}_{i}(1\le i\le t)$. 将所有需求点映射到相应网格中，基站所覆盖需求点数的计算可转换为基站覆盖的网格集合和位于网格内的需求点数的（$C_{n}^{2}\times t+m\times n$）次计算. 网格化后与网格化前的计算次数差为${(C}_{n}^{2}\times t+ m\times n)-(C_{n}^{2}\times m)$，即$\dfrac{1}{2}\times ({n}^{2}-n)\times (t-m)$，而$t << m$，因此该差值小于0，即计算时间大幅降低的同时保持了原有的需求点分布. 基站${v}_{i}$所覆盖的网格集合表示为

其中$G$为网格集合，${v}_{ix}$和${v}_{iy}$分别为${v}_{i}$的横坐标和纵坐标，${g}_{ix}$和${g}_{iy}$分别为${g}_{i}$的横坐标和纵坐标.

将所有需求点映射到相应的网格中，用式（2）中的标志${b}_{ij}$判断需求点${d}_{j}$是否在网格${g}_{i}({g}_{i}\in G$)中，需求点${d}_{j}$在${g}_{i}$中时${b}_{ij}=1$，否则${b}_{ij}=0$.

其中$l$表示网格边长，${d}_{jx}$和${d}_{jy}$分别为需求点${d}_{j}(1\le j\le m)$的横坐标和纵坐标.

统计网格${g}_{i}$内所有满足${b}_{ij}=1$的需求点数，可得到位于网格${g}_{i}$内的需求点数，表示为

其中${b}_{ij}$为判断需求点${d}_{j}$是否在网格${g}_{i}$中，$i\in \left[1,n\right]$表示第$i$个候选基站.

2.3   基站间的贴近度和分离度

为了度量基站间共同覆盖范围的大小，首先给出任意2个基站间贴近度的计算方法，并在此基础上进一步给出度量所有基站之间重合覆盖程度的分离度指标，作为5G基站选址问题的核心约束.

由2.2节可知，式（1）~（3）可将基站所覆盖需求点数的计算任务近似转换为基站覆盖网格的计算，此时，基站${v}_{i}$覆盖的需求点数表示为

其中${g}_{i}$表示第$i$个网格，${q}_{i}$表示第$i$个网格${g}_{i}$内的需求点数，${I}_{{v}_{i}}$表示基站${v}_{i}$所覆盖的网格集合.

基站${v}_{i}$和${v}_{j}$共同覆盖的需求点数表示为

其中${I}_{{v}_{i}}\cap {I}_{{v}_{j}}$表示${v}_{i}$和${v}_{j}$覆盖的网格集合交集.

为避免5G网络拥塞，需求点数多的区域应被更多基站覆盖，因此，引入式（6）中的容量系数${\alpha }_{{v}_{i}}(0 < {\alpha }_{{v}_{i}}\le 1)$，从而衡量$\varepsilon$和$N({v}_{i})$对基站间重合程度的影响程度. ${\alpha }_{{v}_{i}}$通过减小需求点数多的区域基站之间的重合程度，以允许基站在需求点数多的区域发生重合，实现更好的覆盖和容量分配，提高通信网络质量. 当$N({v}_{i}) \le \varepsilon$时，令${\alpha }_{{v}_{i}}=1$，而当$N({v}_{i}) > \varepsilon$时，$N({v}_{i})$的值与${\alpha }_{{v}_{i}}$呈反比关系，${\alpha }_{{v}_{i}}$越小，使${v}_{i}$越靠近其他基站，即越靠近需求点数多的位置.

基站${v}_{i}$和${v}_{j}$共同覆盖的需求点数与其覆盖的总需求点比值越大，且${\alpha }_{{v}_{i}}$或${\alpha }_{{v}_{j}}$越小，则基站之间贴近度越小. 为度量上述关系，定义基站${v}_{i}$和${v}_{j}$间的贴近度为

为了度量所有基站整体覆盖范围的大小，在贴进度的基础上定义一个基站与其他所有基站的分离度. 令$S(S\subseteq V,\left|S\right|=k)$为基站集合，基于式（7）表示的基站间贴近度，可利用式（8）计算$S$中基站$j$与其他基站间的分离度

其中$npd(S,j)$的值越大，基站$j$与$S$中的基站覆盖范围不重合部分与总覆盖范围的比值也越大，反之亦然.

例如，针对图1中的基站${v}_{1}$和${v}_{2}$，基于需求点来计算它们的贴近度. 根据${v}_{1}$和${v}_{2}$覆盖的网格和网格内的需求点数得到${v}_{1}$和${v}_{2}$覆盖的需求点数，根据式（4）（5），可得到$N({v}_{1})=9$，$N({v}_{2})=9$，$N({v}_{1},{v}_{2})=3$. 接着，根据式（7）计算${v}_{1}$和${v}_{2}$的贴近度，若$\varepsilon =10$，则$pd({v}_{1},{v}_{2})= 0.2$；若$\varepsilon =8$，则$pd({v}_{1},{v}_{2})=0.16$；若$\varepsilon =6$，则$pd({v}_{1},{v}_{2})= 0.09$. 若$\varepsilon =10$，$S=\left\{{v}_{1},{v}_{2},{v}_{3}\right\}$，则$pd({v}_{1},{v}_{2})=0.2$，$pd({v}_{1}, {v}_{3})= 0.1$，$npd(S,{v}_{1})=0.9$. 可以看出，基站覆盖的需求点数超出基站容量部分越多，基站间的贴近度将会越小.

图  1  5G基站覆盖范围重合示例

Figure  1.  An example of overlapping coverage areas of 5G base stations

下载: 全尺寸图片 幻灯片

3.   目标函数和最优选址算法

为了基于分离度求解基站覆盖率的最大化问题，本节构造满足子模性和分离度最大化约束的目标函数.

3.1   目标函数

令${S'}({S'}\subseteq V,|{S'}|=k,{S'}\ne S)$为基站集合，对于基站集合$S\subseteq V$，若不存在${S'}\subseteq V$满足

则称$S$为具有最大分离度的基站集合. 其中$\displaystyle \sum_{j \in S} {npd(S,j)}$表示$S$中各基站间的分离度.

由于分离度反映了基站的覆盖范围，基站数量一定时，分离度越大、覆盖范围越大. 因此，以分离度最大化为目标，构建如下目标函数

定义1. $F$是定义域为集合$V$的函数，对于$V$的任意2个子集$A$和$B$，若$F(A\cup \{v\})-F(A)\ge F(B\cup \{v\})- F(B)$（$A\subseteq B\subseteq V$，$v\in V\backslash B$），则$F$具有子模性.

文献[23-24]指出，若优化问题的目标函数满足子模性，那么使用贪心策略求解该问题所获得的结果能够保证近似最优解.

定理1. 式（10）中目标函数满足子模性.

证明. 设候选基站集合为$V$，$S(S\subseteq V)$为具有最大分离度的基站集合，设$A$和$B$分别为$S$的子集，且$A\subseteq B\subseteq S$，$v\in V\backslash S$，函数$F(S) = \displaystyle \sum_{j \in S} {npd(S,j)}$.

同理可得

由于$A\subseteq B$，有

则有$F(A\cup \{v\})-F(A)\ge F(B\cup \{v\})-F(B)$，因此，F(S)满足子模性. 证毕.

结合目标函数$F(S)$满足子模性的特点，利用贪心算法求出使目标函数$F(S)$最大的基站集合$S$，可求得近似最优解，从而得到最优5G基站站址.

3.2   最优选址算法

基于用户需求点数据，构建满足子模性的目标函数，使用贪心策略选出使目标函数增益（即$F(S\cup \{v\})- F(S)$）最大的$v$，该过程中的每一步贪心选择可能有多个$v\in V\backslash S$使$F(S\cup \{v\})-F(S)$最大，构成集合${V}^{*}$. 为使基站能覆盖更多的需求点，在${V}^{*}$中选出使覆盖率$C(S)$最大的$v$加入到$S$，直到$S$中有$k$个基站. 最终，选择$S$作为站址优化方案. 上述思想见算法1.

算法1的时间复杂度取决于贴近度、分离度和目标函数的计算开销，具体而言，算法1根据式（7）计算$n^2t+mn$次基站间的贴近度，根据式（8）计算$k$次基站间的分离度，根据式（10）计算k次目标函数. 行④~⑦总计算次数为${k}^{2}n+{k}^{3}$，行③~⑨总计算次数为${k}^{3}n+{k}^{4}$，则算法1的总计算次数为${k}^{3}n+{k}^{4}+{n}^{2}t+mn$. 然而，实际中$k$的值通常远小于$n$，且$t$的值远小于需求点数$m$，因此，算法1的时间复杂度为$O(mn)$.

算法1. 基于用户需求点的5G基站选址方法.

输入：候选基站节点坐标集合$V$，用户需求点集合$D$，基站选择数量$k$；

输出：具有最大分离度的子集$S$.

① 初始$S\leftarrow \mathrm{\varnothing }$，$j\in S$；

② $F(S) \leftarrow \displaystyle \sum_{j \in S} {npd(S,j)}$；

③ for $i=1$ to $k$ do

④ 　for each $v\in V-S$ do

⑤ 　　${V}^{\mathrm{*}}\leftarrow \underset{v\in V-S}{\mathrm{arg\;max}}\left\{F\right(S\cup \{v\})-F(S)\}$；/*使目 标函数增益最大的基站集合*/

⑥ 　　${v}^{\mathrm{*}}\leftarrow \underset{v\in {V}^{\mathrm{*}}}{\mathrm{arg\;max}}\left\{C\right(S\cup \{v\}\left)\right\}$；/*从${V}^{*}$中选出 使覆盖率最大的基站${v}^{*}$*/

⑦ 　end for

⑧ 　$S\leftarrow S\cup \left\{{v}^{\mathrm{*}}\right\}$； /*将${v}^{\mathrm{*}}$加入到$S$中*/

⑨ end for

⑩ return $S$.

例如，使用算法1选取图2中的最优基站，候选基站$V=\{{v}_{1},{v}_{2},{v}_{3},{v}_{4},{v}_{5},{v}_{6}\}$，需求点总数$\left|D\right|=30$，若需从$V$中选出$k=2$的最优基站，根据式（4）可得$N({v}_{1})= 8$，$N({v}_{2})=11$，以此类推$N({v}_{6})=6$，当$\left|S\right|=0$时，根据式（10）和覆盖率的定义得到$F(S\cup \{v\})-F(S)$和$C(S\cup \{v\})$值如表2所示. 由表2可得${V}^{*}=\left\{{v}_{1},{v}_{2},{v}_{3},{v}_{4},{v}_{5},{v}_{6}\right\}$，由于$C(S\cup \left\{{v}_{2}\right\})$最大，将${v}_{2}$加入$S$，即$S=\left\{{v}_{2}\right\}$，$\left|S\right|=1$.

图  2  候选5G基站示例

Figure  2.  An example of candidate 5G base stations

下载: 全尺寸图片 幻灯片

表  2  $\left|\mathit{S}\right|=0$时$\mathit{F}(\mathit{S}\cup \left\{\mathit{v}\right\})-\mathit{F}(\mathit{S})$和$\mathit{C}(\mathit{S}\cup \left\{\mathit{v}\right\})$的值

Table  2.  Values of $\mathit{F}(\mathit{S}\cup \left\{\mathit{v}\right\})-\mathit{F}(\mathit{S})$ and $\mathit{C}(\mathit{S}\cup \left\{\mathit{v}\right\})$ when $\left|\mathit{S}\right|=0$

候选基站	$F(S\cup \{v\})-F(S)$	$C(S\cup \{v\})$
${v}_{1}$	1	0.27
${v}_{2}$	1	0.37
${v}_{3}$	1	0.30
${v}_{4}$	1	0.16
${v}_{5}$	1	0.12
${v}_{6}$	1	0.32

下载: 导出CSV 

| 显示表格

根据式（7）可得到$pd({v}_{1},{v}_{2})=0.21$，$pd({v}_{2},{v}_{3})=0.2$，$…$，$pd({v}_{2},{v}_{6})=0.06$，由于$\left|S\right|=1$，根据式（10）可得到$F(S\cup \{v\})-F(S)$和$C(S\cup \{v\})$值，如表3所示，进而可得到${V}^{*}=\left\{{v}_{4}\right\}$，将${v}_{4}$加入$S$，有$\left|S\right|=2$. 因此，$k=2$时的最优基站选择结果为$S=\{{v}_{2},{v}_{4}\}$.

表  3  $\left|\mathit{S}\right|=1$时$\mathit{F}(\mathit{S}\cup \left\{\mathit{v}\right\})-\mathit{F}(\mathit{S})$和$\mathit{C}(\mathit{S}\cup \left\{\mathit{v}\right\})$的值

Table  3.  Values of $\mathit{F}(\mathit{S}\cup \left\{\mathit{v}\right\})-\mathit{F}(\mathit{S})$ and $\mathit{C}(\mathit{S}\cup \left\{\mathit{v}\right\})$ when $\left|\mathit{S}\right|=1$

候选基站	$F(S\cup \{v\})-F(S)$	$C(S\cup \{v\})$
${v}_{1}$	0.79	0.50
${v}_{3}$	0.80	0.53
${v}_{4}$	1.00	0.57
${v}_{5}$	0.80	0.53
${v}_{6}$	0.94	0.53

下载: 导出CSV 

| 显示表格

4.   实　　验

4.1   实验设置

1）数据集

使用8个不同规模用户需求点数和候选基站数的真实数据集和模拟数据集，对本文提出的基于用户需求点的5G基站选址UDPB（user demand points based selection）方法进行测试，统计信息如表4所示. 来自斯坦福大学SNAP项目的公开数据集Brightkite和Gowalla包含了用户在一时间段内在不同地点的签到记录^[25]，其中包含时间和经纬度坐标信息. 本文按2 km×2 km，3 km×3 km，5 km×5 km区域大小随机选取出6个不同的区域作为6个数据集，分别记为Brightkite(2×2)，Brightkite(3×3)，Brightkite(5×5)，Gowalla(2×2)，Gowalla(3×3)，Gowalla(5×5)；按2 km×2 km区域大小和高密度与低密度随机生成2个不同数据集，分别为DenseArea(2×2)，SparseArea(2×2). 其中需求点为用户终端位置，候选基站的坐标为区域网格化后边长为100 m的网格中心点坐标.

表  4  数据集统计信息

Table  4.  Statistics of Datasets

数据集	用户需求点数量	候选基站数量
Brightkite(2×2)	5993	400
Brightkite(3×3)	12938	900
Brightkite(5×5)	20984	2500
Gowalla(2×2)	1277	400
Gowalla(3×3)	4546	900
Gowalla(5×5)	16570	2500
DenseArea(2×2)	6041	400
SparseArea(2×2)	1274	400

下载: 导出CSV 

| 显示表格

2）评价指标

选择需求点覆盖率、面积覆盖率、总体贴近度3个指标评价，测试本文方法的有效性.

① 需求点覆盖率. 表示算法所选出的基站覆盖的需求点数占总需求点数的比例，即$C(S)=p(S)/\left|D\right|$，其中，$S$表示算法所选出的基站集合，$\left|D\right|$表示需求点总数，$p(S)$表示被覆盖的需求点数，$C(S)$值越大越好.

② 面积覆盖率. 表示算法所选出的基站覆盖的网格数占总网格数的比例，反映了基站覆盖的区域面积，定义为$AC(S)={n}_{\mathrm{c}}/n$，其中，$n$表示网格总数，${n}_{\mathrm{c}}$表示被覆盖的网格数，$AC(S)$值越大越好.

③ 总体贴近度. 表示算法所选出的基站间的贴近度之和，反映所有基站间的重合程度，其值越小，选址效果就越好，定义为$wpd(S) = \displaystyle \sum_{i \in S} {\displaystyle \sum_{j \in S\backslash \{i\}} {pd(i,j)} }$，$pd(i,j)$表示基站$i$和$j$的贴近度.

3）对比算法

选择经典的进化算法，如遗传算法（genetic algorithm，GA）^[5]、粒子群优化算法（particle swarm optimization，PSO）^[26]、社交网络中种子节点选取算法，包括寻找观察项集贪心算法（greedy algorithm to find the observed itemset，FOI）^[13]、影响传播树算法（influence propagation trees based algorithm，IPTB）^[14]、空间社交网络上的影响力最大化算法（influence maximization algorithms in spatial social network，SSN）^[15]、改进的时序图上影响力最大化算法（improved method for influence maximization algorithm on temporal，IMIT）^[16]作为对比算法.

① GA. 将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程，以覆盖率为目标函数，通过模拟自然进化过程搜索最优解.

② PSO. 初始化为随机解，通过模拟鸟群觅食行为，以覆盖率为优化目标，在迭代过程中，粒子通过跟踪历史最优解来更新自身状态.

③ FOI. 通过计算基站间的贴近度，构建满足子模性目标函数，再使用贪心算法选择基站.

④ IPTB. 在每次选择目标函数F(S)最大的基站后，去除与候选基站中间贴近度较大的基站.

⑤ SSN. 通过计算候选基站与S中每个基站间的贴近度，随机选择1个贴近度不小于$\tau (0 < \tau < 1)$的候选基站加入S.

⑥ IMIT. 计算每个节点的目标函数F(S)，按其取值排序并将最大值加入集合，依次比较后续节点并加入符合条件的节点，否则重新排序.

4）参数设置和实验环境

根据5G基站本身的特点和实际情况，5G基站覆盖半径$r$=300 m，基站容量$\varepsilon$=1400，规划区域中的网格边长$l$=100 m，$k$取5G基站接近全覆盖规划区域时的值. 程序采用Python3编写，实验环境为Windows10系统、32 GB内存和inter^®Core™ i7-10700K处理器.

4.2   实验结果

4.2.1   5G基站选址算法的有效性

以需求点覆盖率、面积覆盖率和总体贴近度指标测试选址结果的有效性，如表5~7所示. 可以看出，由于UDPB可以有效减小基站的重合覆盖范围且优先选择覆盖率大的基站，在不同数据集上，UDPB在需求点覆盖率和面积覆盖率2个指标上均优于对比算法；在Brightkite(2×2)数据集上，k=16时UDPB在面积覆盖率上比其他最优结果高出0.133. 由于IPTB会去除贴近度较大的基站，在Brightkite(2×2)，Brightkite(3×3)，Gowalla(3×3)数据集上，UDPB在总体贴近度指标上仅次于IPTB，在其他数据集上均优于其他算法. 在5 km×5 km区域的数据集上，UDPB优先选择重合覆盖范围小、覆盖率高的基站，其优势更加明显，在各个指标上均优于其他对比方法. 综上，UDPB算法对于基站选址而言是一种有效的选址方法，且能有效减小基站之间的重合覆盖范围、提高基站覆盖率.

表  5  在2 km×2 km的数据集上5G基站选址算法有效性比较

Table  5.  Effectiveness Comparison of 5G Base Station Location Selection Algorithms on a 2 km×2 km Dataset

数据集	算法	需求点覆盖率				面积覆盖率				总体贴近度
		k=16	k=18	k=20		k=16	k=18	k=20		k=16	k=18	k=20
Brightkite (2×2)	UDPB (本文)	0.983	0.988	0.992		0.840	0.895	0.910		0.04	0.21	0.50
	GA	0.975	0.982	0.989		0.652	0.762	0.822		6.46	6.25	6.53
	PSO	0.978	0.980	0.984		0.622	0.727	0.702		5.41	5.48	13.88
	FOI	0.961	0.962	0.963		0.627	0.750	0.797		9.13	12.31	3.78
	IPTB	0.862	0.870	0.952		0.707	0.812	0.847		0.03	0.20	0.32
	SSN	0.744	0.840	0.835		0.595	0.655	0.772		3.82	3.57	5.30
	IMIT	0.838	0.878	0.907		0.697	0.817	0.902		1.13	1.90	2.35
Gowalla (2×2)	UDPB (本文)	0.953	0.953	0.953		0.855	0.880	0.895		0.00	0.03	0.22
	GA	0.918	0.944	0.944		0.632	0.722	0.735		8.01	5.46	10.54
	PSO	0.916	0.918	0.946		0.610	0.760	0.822		3.22	5.17	6.00
	FOI	0.559	0.752	0.735		0.647	0.682	0.722		19.74	37.40	27.69
	IPTB	0.729	0.810	0.930		0.757	0.797	0.840		0.03	0.07	0.23
	SSN	0.564	0.729	0.861		0.627	0.652	0.720		0.72	4.06	7.38
	IMIT	0.464	0.508	0.551		0.525	0.607	0.682		0.03	0.10	0.72
SparseArea (2×2)	UDPB (本文)	0.940	0.962	0.973		0.872	0.932	0.955		0.22	0.44	0.86
	GA	0.864	0.901	0.908		0.775	0.742	0.772		3.89	5.90	5.95
	PSO	0.871	0.885	0.908		0.757	0.785	0.840		3.17	3.42	5.79
	FOI	0.936	0.961	0.967		0.825	0.875	0.890		3.01	3.83	5.36
	IPTB	0.705	0.790	0.839		0.835	0.847	0.885		0.35	0.71	1.28
	SSN	0.585	0.677	0.716		0.632	0.630	0.742		5.21	5.27	4.80
	IMIT	0.674	0.707	0.781		0.652	0.707	0.822		3.57	3.86	3.86
DenseArea (2×2)	UDPB (本文)	0.939	0.969	0.983		0.890	0.950	0.970		0.27	0.53	1.00
	GA	0.891	0.911	0.931		0.705	0.812	0.860		3.93	4.67	5.76
	PSO	0.837	0.900	0.944		0.707	0.797	0.800		3.77	4.88	5.87
	FOI	0.938	0.965	0.976		0.802	0.857	0.922		2.67	3.25	4.20
	IPTB	0.675	0.834	0.835		0.785	0.847	0.872		0.36	0.58	1.29
	SSN	0.534	0.640	0.791		0.655	0.657	0.672		5.48	3.52	7.31
	IMIT	0.812	0.824	0.828		0.830	0.857	0.877		0.95	7.70	7.68
注：黑体数值表示最优性能值.

下载: 导出CSV 

| 显示表格

表  6  在3 km×3 km的数据集上5G基站选址算法有效性比较

Table  6.  Effectiveness Comparison of 5G Base Station Location Selection Algorithms on a 3 km×3 km Dataset

数据集	算法	需求点覆盖率				面积覆盖率				总体贴近度
		k=38	k=40	k=42		k=38	k=40	k=42		k=38	k=40	k=42
Brightkite (3×3)	UDPB (本文)	0.983	0.994	0.995		0.839	0.850	0.857		0.59	0.83	1.17
	GA	0.969	0.977	0.990		0.655	0.657	0.758		17.21	14.26	26.32
	PSO	0.956	0.954	0.969		0.673	0.592	0.695		20.97	19.02	25.19
	FOI	0.827	0.824	0.687		0.664	0.688	0.718		117.72	226.85	214.15
	IPTB	0.834	0.843	0.913		0.797	0.848	0.849		0.24	0.83	0.73
	SSN	0.676	0.714	0.700		0.685	0.654	0.693		13.43	14.32	11.87
	IMIT	0.607	0.695	0.701		0.775	0.809	0.841		1.35	1.46	1.46
Gowalla (3×3)	UDPB (本文)	0.947	0.954	0.960		0.859	0.871	0.882		0.73	1.03	1.40
	GA	0.919	0.928	0.957		0.674	0.723	0.679		8.50	13.66	16.58
	PSO	0.904	0.921	0.924		0.618	0.710	0.691		15.64	17.17	21.85
	FOI	0.723	0.667	0.761		0.639	0.711	0.743		49.79	52.14	92.22
	IPTB	0.825	0.882	0.913		0.832	0.839	0.832		0.31	0.56	0.73
	SSN	0.574	0.576	0.727		0.633	0.709	0.679		15.57	18.82	23.29
	IMIT	0.477	0.565	0.757		0.731	0.78	0.838		1.38	1.38	1.38
注：黑体数值表示最优性能值.

下载: 导出CSV 

| 显示表格

表  7  在5 km×5 km的数据集上5G基站选址算法有效性比较

Table  7.  Effectiveness Comparison of 5G Base Station Location Selection Algorithm on a 5 km×5 km Dataset

数据集	算法	需求点覆盖率				面积覆盖率				总体贴近度
		k=38	k=40	k=42		k=38	k=40	k=42		k=38	k=40	k=42
Brightkite (5×5)	UDPB (本文)	0.845	0.846	0.846		0.430	0.449	0.462		0	0	0
	GA	0.695	0.674	0.688		0.277	0.216	0.262		137.96	191.78	138.26
	PSO	0.751	0.694	0.736		0.340	0.321	0.370		37.83	25.31	34.83
	IPTB	0.466	0.514	0.480		0.394	0.410	0.419		0	0	0
	SSN	0.470	0.420	0.423		0.336	0.345	0.348		18.74	56.94	69.59
	IMIT	0.333	0.333	0.334		0.282	0.291	0.302		2.11	2.11	2.11
Gowalla (5×5)	UDPB (本文)	0.813	0.814	0.814		0.431	0.454	0.475		0	0	0
	GA	0.601	0.595	0.619		0.246	0.277	0.310		95.97	121.16	81.16
	PSO	0.664	0.671	0.637		0.307	0.306	0.264		69.71	73.38	103.29
	IPTB	0.449	0.450	0.460		0.418	0.423	0.426		0	0	0
	SSN	0.339	0.335	0.405		0.340	0.350	0.358		33.05	58.03	42.53
	IMIT	0.269	0.269	0.292		0.257	0.272	0.290		2.50	2.50	2.50
注：黑体数值表示最优性能值.

下载: 导出CSV 

| 显示表格

4.2.2   5G基站选址算法执行效率

为了测试5G基站选址算法的执行效率，测试了不同数据集上各基站选址算法随$k$增大的执行时间，如图3所示. 可以看出，在不同区域大小和密度的数据集上，UDPB表现出比对比算法更低的运行时间，并且其运行时间随着$k$的增加呈现出更加平缓的趋势. 尤其是在2 km×2 km区域的数据集上，$k$和$n$的值较小，UDPB随$k$增大的运行时间增长缓慢，其运行时间比IPTB，IMIT低，且远低于GA，PSO，FOI，因此UDPB的算法更加稳定，相比对比算法表现得更为优异. 在3 km×3 km区域的数据集上，尽管随着候选基站数量和$k$值的增加，UDPB的运行时间呈现出上升趋势，但仍低于对比算法，其运行时间比IPTB，IMIT低，比GA和PSO几乎低50%，远低于FOI，且算法性能表现仍相对稳定. UDPB的运行时间主要与$k(k < n)$有关，在不同数据集上算法效率高于对比算法. 以上实验结果表明，UDPB在不同数据集上的效率明显优于其他对比算法，且UDPB的运行时间变化较为平稳，验证了UDPB的高效性和稳定性.

图  3  在6个数据集下运行时间随k增加的变化趋势

Figure  3.  Variation trend of the running time with the increase of k on 6 datasets

下载: 全尺寸图片 幻灯片

5.   总结与展望

本文以5G网络终端用户的历史通信数据为基础，通过引入基站容量系数和度量基站间分离度构建满足子模性的目标函数，利用贪心算法选出最优基站站址，从而有效提高基站覆盖率，为5G网络系统实现信息智能化运维提供决策支持. 实验结果表明，本文算法能够高效地求解出使5G基站覆盖率高的站址，也可为汽车充电桩、餐厅、学校和超市等选址提供参考.

相距较远的基站和需求点间可以认为并不存在关联，将考虑这一特点提高计算效率. 未来还需考虑5G信号传播模型、地形地貌、建筑物高度和密度、人口密度和流动性等更多的因素，以提高选址的精度和实用性.

作者贡献声明：黄文辉提出了算法思路和实验方案，并完成实验；王笳辉完成实验并撰写论文；周丽萍和岳昆修改论文.