基于丘陵地区的无线宽带基站选址算法研究

边 强，徐东辉，刘江亮，何婧媛2,，杨海宇

(1.火箭军工程大学，西安 710025；2.延安大学，陕西 延安 716000)

1 引言

无线宽带通信系统主要是在无基础设施支撑的通信场景下承担通信保障任务，是应急通信的主要手段之一。由于该系统具有部署形式灵活、建设成本较低、布设速度快等特点，因此具有很高的应用价值。在复杂多变的电磁环境中，如何快速、高效的完成基站选址是该系统保障可靠通信亟需解决的问题。基站选址问题的研究是随着实际通信应用需求不断变化的，一般的基站选址问题是通过调整站点数量、更换站点类型和改变站点位置布局等方式，达到增大网络覆盖范围、扩大业务容量和降低建设成本等目标。金伟正等[1]综合电力无线专网建设的目标、原则及成本要求，使用变步长的人工鱼群算法制定出满足覆盖率要求的基站选址方案。张英杰等[2]将基站选址问题建模成一个多目标优化问题，用免疫算法对其进行求解，考虑用较小的建站代价获得较高的网络覆盖率。为了提高通信基站选址的高效、合理性，大量方法被用于基站选址优化。一类解决方法是基于几何原理寻找合适的站点位置，如几何中心法[3]和外接圆法[4]。熊毅[5]基于泰森多边形原理，以现有基站位置为三角形顶点，以三角形边的垂直平分线相交得到的多边形顶点为新站的站址，确定具体地区所需基站的数量和位置。另一类解决方法是将其转化为单目标优化问题进行处理。康丽晴等[6]以网络覆盖率作为优化目标，采用改进的鲸鱼优化算法找到最佳选址布局。刘娟等[7]利用粒子群果蝇混合优化改进算法优化基站布局，从而实现更高的网络覆盖率。除了鲸鱼优化算法，混合免疫算法[8]、粒子群算法[9]以及其他优化算法也被用于解决基站优化问题。基站选址还可以被优化为多目标问题进行求解。刘尚雄等[10]将布局问题转化为多目标问题进行求解，采用NSGA-Ⅱ算法实现了系统覆盖率最佳，基站几何布局做好。杨俊逸[11]先对基站的站址进行优化，使得基站数量最少，再次进行优化，使得基站功耗最小。第三种处理方式是直接优化基站规划中的多个目标。吕秋实[12]通过多目标遗传算法，寻找覆盖区域最广、建设成本最低和系统容量最大的基站位置及配置方案，实现4G移动网络三网协同基站的智能规划。董宏成等[13]使用改进的多目标粒子群算法，同时优化覆盖率、网络效能比、网络负载和建设成本，解决LTE混合组网优化问题。Lakshminarasimman等[14]利用改进的NSGA-Ⅱ算法来确定车辆和行人处于移动情况下时基站的最佳位置，从而使得通信的覆盖最大化、成本最小化。除了以上提到的遗传算法、免疫算法、粒子群算法、NSGA-Ⅱ算法和多目标粒子群算法等优化算法，模糊推理[15]、推荐系统[16]和机器学习[17]等方法也都在基站选址问题中有所应用。

当前，基站选址的方法大都是针对宏基站进行深入研究的，其主要考虑物理因素、天面要求、机房要求和周围的环境安全性等多方面因素，从而降低建设成本，实现经济效益最大化；而无线宽带通信系统作为应急通信手段，是基于无基础设施支撑条件下进行指挥通信保障的，主要目的是尽最大可能为保障区域提供通信服务，所以宏基站选址方法无法适用于车载基站选址问题研究。本文中针对无线宽带通信系统车载基站在丘陵环境下布设规划问题进行研究，首先搭建系统模型，然后采用改进K-means算法迭代计算得到基站选址方案，最后布站人员根据选址方案进行车载基站布设工作，尽最大可能使骨干网络信号覆盖整个规划区域，从而提高地面终端随遇接入的成功率。

2 系统模型搭建

2.1 场景设置

本文主要针对丘陵环境为背景进行研究，丘陵区域地形起伏不定，无线电波在传播过程中会出现山体阻挡，所以电磁波在传播过程中，既有平坦地区的传播规律，又有山区的传播规律；由于周围地理环境以及地面覆盖物都会对无线电波的传播造成影响，从而增加无线电波传播的路径损耗。无线宽带通信系统中基站之间形成骨干网络，地面终端选择就近基站随遇接入进行通信，构成接入网。基站中负责基站选址规划任务的为主基站，其余为从基站，指挥所部署在主基站，从基站接受主基站的指挥协调，所有基站布设需要避开障碍区。因为无线宽带通信系统中配备的是车载基站，所以每个基站都具有移动性；当主基站选址规划结束后将选址方案下发至从基站，从基站按照选址方案移动至指定位置进行布设基站，所以需要对主基站进行提前布设。无线宽带通信系统中每个基站均配备全向天线和定向天线。全向天线为地面终端提供服务；定向天线形成骨干网络，保证基站之间通信。在丘陵环境下，电磁波在传播过程中既存在视距(LOS)传播，也存在非视距(NLOS)传播，所以全向天线发出的无线信号覆盖区域不会是规则形状，可以采用架高天线，增大发射功率等方式来增大信号覆盖范围。

2.2 基站覆盖半径

天线的覆盖半径影响定基站覆盖范围。由于本文主要针对的是丘陵地区环境下的站点布设规划问题进行研究，通常Egli模式是这一环境下电磁波传输损耗常用模型。在丘陵环境下，无线信号主要以视距方式传播和非视距方式传播(散射、折射、绕射)，根据地形起伏高度不同，传播路径上山体阻挡等地理环境因素所造成的的电波传输损耗不同。Egli模型传播路径损耗可表示为

Le=88.11+40lgD+20lgf-20lg(Ht*Hr)-Kh

(1)

式中：Le为传播损耗(dB)；D为收发设备之间的距离(km)；f为工作频率(MHz)；Ht为发射天线高度(m)；Hr为接收天线高度(m)；Kh为地形修正因子。

Egli模型受地形起伏变化影响较大，为了提高选址结果的准确性，针对不同地形，需要通过校正地形修正因子来提高模型的准确性。Kh修正因子可表示为

(2)

其中：Δh为地形起伏高度，m，当Δh<15了m时，Kh可以忽略不计。

本文针对测试点与基站之间存在视距传播和非视距传播，针对传播路径损耗(L)进行了缩放调整，具体如下：

LoS∶L=0.4Le

(3)

NLoS∶L=1.6Le

(4)

规划区域内任一点的接收功率为

Pri=10*log(Pt)-L

(5)

式中：Pri为任一点的接收功率;Pt为基站发射功率。

R=10^((A-B)/40)*1 000

(6)

A=(10*lgPt-gamma)/0.9

(7)

B=88.11+20*lgf-20lg(Ht*Hr)-Kh

(8)

其中:R为覆盖半径;gamma为接收灵敏度。

2.3 基于K-means算法的基站选址

K-means算法是基于划分的聚类算法，主要分为3个步骤：

步骤1：特征选择和特征提取。

步骤2：数据对象间相似度计算。

步骤3：根据相似度将数据对象分组。

该算法是一种无监督学习，一般用欧式距离作为衡量数据对象间相似度的指标，相似度与数据对象间的距离成反比，相似度越大，距离越小。该算法需要预先指定初始聚类数目k以及k个初始聚类簇心，根据数据对象与聚类簇心之间的相似度，将所有对象聚类到距离该对象相似度最高的簇心组成一个簇，并找出簇中到其他对象距离最小的数据形成新的簇心，不断降低类簇的误差平方和(sum of squared error，SSE)，当SSE不再变化或目标函数收敛时，聚类结束，得到最终结果。

空间内未覆盖的点与聚类簇心间的欧式距离计算公式为

(9)

式中：x为待计算的功率点对象；Ci为第i个聚类簇心;m为功率点的维度；xj和Cij为x和Ci的第j个属性值。

整个数据集的误差平方和SSE计算公式为

(10)

其中:SSE的大小表示K-means算法结果的好坏，k表示簇心的个数。

在一块矩形区域内(区域内有一个关键区域，2个障碍区域)，无线宽带通信系统的车载基站移动至选址规划位置布设基站，基站组成的骨干网络尽最大可能实现规划区域内信号全覆盖，从而保证地面终端随遇接入。假设无线宽带通信系统在规划区域内布设7个车载基站形成骨干网络，采用K-means算法进行选址规划。实验环境为Windows10操作系统、Intel Core i7处理器、16GB内存、Matlab 2019b软件，仿真参数如表1所示；采用K-means算法规划结果如图1所示。

表1 仿真实验参数Table 1 Simulation experiment parameters

图1 K-means算法信号覆盖率与迭代关系图Fig.1 K-means algorithm signal coverage and iteration diagram

图1表明：采用K-means算法进行基站布设规划仿真，迭代9次后其覆盖率达到91.8%，经过17次迭代后信号覆盖率为92.120 7%，算法运行耗时381 s。

3 基于改进K-means算法的基站选址

K-means算法原理比较简单，算法逻辑清晰，可解释度强，但在K-means算法中随机确定初始聚类簇心，导致容易陷入局部最优的问题，进而导致迭代次数多，计算时间长，影响信号覆盖效果等问题，针对这些问题，本文中提出了一种改进的K-Means算法。无基础设施支撑下基站选址是通过对输入的规划区域参数、基站参数、接收参数等系统参数，结合地形数据，选取无线信道模型，利用改进K-means算法在规划区域内对基站位置进行迭代计算，得到满足规划目标的基站选址结果，该结果包括基站位置、覆盖半径和规划区域信号覆盖率等。无线宽带通信系统在布设过程中，基站形成的骨干网络信号尽可能的覆盖规划区域。基站之间通信必须是双向的，即相互连接的基站之间均能接收到对方的信号，且信号强度均超过接收灵敏度，每个基站最多能与2个基站进行通信。

3.1 改进K-means算法

K-means算法具有原理简单，容易实现，可解释度高等优点；但是也存在容易陷入局部最优，算法结果对初始化簇心选择的依赖强的缺点。本文针对K-means算法的缺点，提出了优化初始簇心的选取的改进K-means算法。改进K-means算法中采用轮盘赌算法进行初始化簇心的选取，从而尽最大可能的使初始化簇心分散，降低簇心选择的随机性，避免陷入局部最优解，从而实现算法收敛速度快，且算法结果为全局最优值，即实现更好的信号覆盖率。轮盘赌算法的实现步骤为：

1) 初始化个体适应度值xi(未覆盖区域每个点均为一个个体)；

2) 根据公式计算个体被选中概率和累积概率；

个体选择概率(pi看成xi被选中的概率)：

(11)

累积概率：

(12)

3) 模拟轮盘选择操作，在区间[0,1]之间随机生成一个数B，如果q(xi-1)

在本文中，首先在规划区域随机初始化生成一个满足要求的初始基站布局(规划区域内7个车载基站组成的初始基站布局)，根据此时的基站布局计算无线信号覆盖情况并确定信号未覆盖区域，采用轮盘赌法在未覆盖区域选出7个聚类簇心Ci(1≤i≤7)。将未覆盖的点分配到聚类簇心Ci所对应的簇，并且根据聚类到该簇心的未覆盖点的个数，将这些簇心降序排序，确定其优先级(归类到的点数越多优先级越高)。然后根据优先级依次遍历每一个簇心，当遍历到某个簇心，计算所有基站到该簇心的欧式距离并确定优先级(距离越近优先级越高)，根据优先级遍历所有基站。当遍历到某个基站时，基站以一定步长向簇心移动，在满足基站布局条件下计算基站移动过程中的最大信号覆盖率，若最大信号覆盖率大于当前信号覆盖率，则更新基站位置，到此一次迭代结束。随后计算新的簇心进行下一次迭代，迭代终止的条件是在某次迭代中遍历完所有的簇心覆盖率均未提高，或者达到指定的迭代次数。最后，根据最终的基站位置计算布设区域内各空间点的信噪比和信号覆盖率。

3.2 算法设计

基于改进K-means算法的基站选址流程如图2所示。

图2 改进K-means算法的基站选址流程框图Fig.2 Base station site selection flowchart of the improved K-means algorithm

具体步骤如下：

首先，随机初始化生成一个由K个基站组成满足要求的基站布局，并且根据初始化基站布局，计算规划区域的覆盖率，确定规划区域内未覆盖位置；其次，从未覆盖区域内随机选择一个空间点作为初始化聚类簇心C1，计算未覆盖区域内中其余空间点和已知的聚类簇心之间的最近距离，然后计算每个点被选为下一个聚类簇心的概率；继而按照轮盘赌法选择出下一个聚类簇心，直到选择出K个簇心；然后，将信号未覆盖点的个数依据归类到就近簇心，按照降序排序确定簇心优先级(归类到的点数越多优先级越高)，选择优先级最高的簇心，计算各基站到簇心的距离(距离为欧氏距离)，从而确定基站移动的优先级，依据基站优先级，选择一个基站以一定步长向簇心移动，计算移动过程中的最大覆盖率；最后，判断最大覆盖率是否大于当前覆盖率，如果不满足条件，选择更低优先级的基站计算其在移动过程中的最大覆盖率，直到遍历完所有基站，否则跳出此循环，然后判断是否达到迭代次数，如果满足最大迭代次数，直接跳出循环，否则重新计算覆盖率，确定信号未覆盖区域，当不存在优先级更低的基站，选择更低优先级的簇心进行迭代计算，如果不存在更低优先级的簇心，算法直接结束，根据算法迭代计算结果确定基站布局，从而计算地图各空间点的信噪比和信号覆盖率。

4 仿真实验与结果分析

4.1 仿真参数设置

假设无线宽带通信系统部署7个车载基站，每个基站都配备相同的设备，在实验过程中设备都可以正常工作。仿真参数如表1所示，采用改进K-means算法和K-Means算法迭代计算结果如图3所示。

图3 改进K-means算法信号覆盖率与迭代关系图Fig.3 Signal coverage and iteration diagram of the improved K-means algorithm

4.2 结果分析

图3表明：改进K-Means算法在迭代6次后，覆盖率达到96.1%，经过14次迭代后达到96.863 2%，算法耗时297 s。

初始化基站布局后，基站组网形成的骨干网络覆盖情况如图4所示。红色框区域为关键区域，黄色框区域为障碍区域；白色圈为基站位置，白色虚线代表两基站可以互相直接通信；红紫色点为未覆盖区域的聚类簇心，红紫色虚线代表本次迭代由连线的基站向连线的簇心移动；蓝色区域为信号未覆盖区域；绿色区域为信号覆盖区域，信号覆盖区域黄色颜色越深，表示信号强度越强。

图4 迭代1次信号覆盖图Fig.4 Iterative signal coverage diagram for the first time

由图4可知，初始化基站布局后，覆盖率仅为73.844 6%，个别基站之间布设距离比较近，说明信号覆盖率还有提升的空间；未覆盖区域簇心都远离车载基站位置，且基站布设位置都避开了障碍区；系统中组成骨干网络的基站之间可以相互通信；地形起伏变化的大小直接影响信号覆盖效果。对比图4和图5可以发现：算法迭代计算一次，只移动一个基站位置；基站在移动至簇心的过程中，会存在一个最大覆盖率的位置，这个位置不一定是簇心位置，可能是基站与簇心连线之间的某一位置；一次迭代结束后，重新确定簇心位置及其优先级，随着簇心优先级的改变，基站的优先级也随之改变。由图6可见：随着迭代次数的增加，覆盖率由73.844 6%提高至96.863 2%，此时达到信号覆盖率最大状态，即最终基站布局结果；最终基站布局仍然存在骨干网络信号无法覆盖的区域，即存在信号覆盖盲区。

图5 迭代2次信号覆盖图Fig.5 Iterative signal coverage diagram for the second time

图6 迭代结束信号覆盖图Fig.6 End-of-iteration signal coverage diagram

4.3 对比分析

为了检验改进K-means算法的性能，将其与K-means算法进行对比实验。对比实验结果如图7和表2所示。

图7 K-means算法和改进K-means算法曲线Fig.7 Comparison chart of K-means algorithm and the improved K-means algorithm

表2 算法对比结果Table 2 Algorithm comparison results

由图7和表2可见：信号覆盖率由92.120 7%提高至96.863 2%，算法性能有所优化；迭代收敛次数由9次降低为6次，最终收敛迭代次数由17降为14，达到了快速收敛的目的；算法运行时间由381 s降低至297 s，算法效率明显提高。

5 结论

基站选址是无线宽带通信系统布设的重要环节，选址方案的合理性决定着系统信号覆盖范围和通信保障能力。本文建立了最大信号覆盖率为目标的基站选址模型，提出了基于优化初始化簇心选取的改进K-means算法，确定了信号覆盖率为96%的基站选址方案。对比分析发现改进K-means算法效率和收敛速度都有一定提高。虽然依据最佳基站选址方案，无线宽带通信系统可以基本实现规划区域信号全覆盖，但是本文中考虑的场景因素还不够全面，下一步将针对实际道路条件下进行基站选址方法研究。