一种基于GeoHash的同覆盖扇区高效判定算法

王 越，刘 佳，康志文，张清伟，高宗宝

（中国移动通信集团设计院有限公司山东分公司，济南 250101）

0 引言

随着移动通信技术的发展，网络高负荷问题日益凸显，相继出现高业务量区域、高校热点场景区域和景区突发高用户数区域容量不足的情况。为改善现网负荷，一方面不断开展小区扩容、站点新建等举措，另一方面通过现网KPI指标监控，同覆盖扇区间的容量差异愈发明显，一个因高业务量耗尽资源导致无法使用业务，另一个却处于空闲，造成资源浪费，需要实施负荷均衡方案。因此，同覆盖扇区的判定是首要解决的问题，同覆盖判定的有效性、准确性、时效性决定均衡方案的实施效果。

根据《中国移动高流量小区优化指导意见4.0》［1］，其中对同覆盖扇区定义为：异频宏站站间距小于50 m，小区方位角偏差小于15°（从方位角0°开始顺时针选择第一个小区，以该小区为基准小区，其余小区若方位角与该小区差距在15°以内，则均纳入第一个同覆盖扇区；随后顺时针选择第二个小区，若该小区之前已有同覆盖扇区，则不再考虑，否则作为第二个基准小区，再判断其他小区是否与该基准小区同覆盖。

同覆盖规则涉及小区间的经纬度和方位角计算和判断，传统方法［2-3］计算某一小区的同覆盖小区时会与其他所有小区都进行距离计算及方位角比对，计算效率较低且容易耗费内存资源。GeoHash 是一种地址编码方法［4-7］，它把二维的空间经纬度数据编码成一个字符串，位置相近的点具有公共前缀。本文根据GeoHash 编码此特性，设计了一种快速同覆盖扇区判别算法，首先对小区及周边九宫格进行GeoHash编码预处理，之后对小区进行GeoHash码聚类，最终通过同聚类中的小区互相比对得到判定结果。

1 算法模型

1.1 GeoHash算法

GeoHash是一种地址编码方法，它可以将二维的空间经纬度数据编码成一个字符串，在附近点搜索等领域有广泛的应用。它将整个地球作为一个平面，不断使用二分法将区域划分成一个个正方形的栅格，这样每一个栅格都会有唯一的二进制编码，编码越长，代表栅格的精度越高。之后GeoHash 算法将二分的二进制编码使用Base32 编码转换为字符串形式，同样，当字符串长度更长时，栅格的宽度更小，所代表的的范围更精确。

GeoHash算法的流程如下：

（1）将经纬度二分变为二进制，二分的次数越多，GeoHash编码越长，对应的精度越高；

（2）二进制经纬度合并，偶数位放经度，奇数位放纬度，组成新的编码串；

（3）对合并后的编码进行Base32编码，生成最终的GeoHash编码。

以 点（30.280245oN,120.027162OE）为例，GeoHash编码经纬度二分过程如图1所示。

图1 GeoHash编码经纬度二分划分过程

GeoHash算法将二维的经纬度编码后转换成一维字符串表示，字符串越长，表示的范围越精确。当编码长度为7 位时，误差在76 m 左右；而编码长度为8 位时，误差为19 m 左右。具体GeoHash编码长度与精度对应关系见图2。

图2 GeoHash 编码长度与精度对应图

1.2 基于GeoHash的同覆盖扇区高效判定算法

GeoHash编码的性质为，两点之间的距离越近，GeoHash编码的公共前缀越长。可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。假设GeoHash 编码误差为d，如果两点位于同一GeoHash编码划分矩形内，两点间欧式距离范围为［0,］（两点重合到对角线距离）。

如果只凭借GeoHash 码相同判断两点距离在一定范围之内，可能会出现漏算情况。如图3所示，绿点与红点GeoHash 编码不同，但都处于本身GeoHash 划分矩形的边缘，两点之间距离较近。为解决此问题，引入九宫格的概念，以黄点为例，计算出其周围八个相邻GeoHash划分矩形引入。

图3 GeoHash编码示例切分矩形

根据同覆盖扇区计算规则（距离在50 m 之内），选择使用7 位GeoHash 编码预处理（误差79 m），保证了如果A、B 两个小区距离满足同覆盖扇区条件，那么A 小区一定位于B 小区GeoHash 编码九宫格范围内。如果A 小区处于B小区九宫格内，需要计算两小区距离判定是否满足条件。这样就将每个小区的计算列表从全部小区缩减到了近距离小区集，减少了不必要的计算量。本文采取的算法流程如图4所示。

图4 GeoHash算法判定同覆盖扇区算法流程

（1）工参数据预处理，去除经纬度、方位角无效的数据；

（2）根据小区经纬度进行GeoHash 编码，同时计算出小区九宫格位置的GeoHash编码；

（3）根据GeoHash 码聚类小区，最终生成GeoHash 码——在GeoHash 码网格中的小区列表HashMap；

（4）遍历每个小区，根据当前小区九宫格的GeoHash 码组，从步骤（3）中可取出在当前小区九宫格内的小区列表；

（5）以当前小区为基准，一一计算与步骤（4）中的九宫格小区的距离、方位角、站型差异，判定是否满足共覆盖标准，并将结果持久化至数据库中。

传统方法计算某一小区的同覆盖小区时会与其他所有小区都进行距离计算及方位角比对，时间复杂度高达O（n2）。本算法使用了GeoHash算法对小区进行了预处理聚合，每个小区只需与在自己九宫格GeoHash 码网格之内的小区比对，对海量小区而言，总体时间复杂度降为O（n），大大减少了不必要计算。

1.3 对比实验验证

本文选择实验环境：CentOS 7，16core，内存64 GB，硬盘2 T。

选取70 w、90 w 小区，分别使用传统算法及本文算法进行测试，运行十次，测试结果见表1。

表1 同覆盖扇区计算对比验证表

经验证，两种算法输出结果相同，传统算法计算70 w级别小区的同覆盖扇区平均需要220分钟，使用本文算法只需要1分钟；传统算法计算90 w级别小区的同覆盖扇区平均需要280分钟，使用本文算法只需要3分钟。本文算法在保证了计算正确率的情况下大幅提升了计算效率，提升效率程度达到了93倍（1/3-1/280）/（1/280）。

图5 同覆盖扇区计算对比验证图

目前，已将本算法使用Java 代码实现，并集成于生产平台中，为后续负载均衡模块进行垂直面-同覆盖多层网优化、派发工单等提供数据支撑。以山东省为例（70 w 级别4G 小区），传统算法计算需要四个小时，使用本算法只需1分钟，且结果准确无误，效率提升非常明显。

2 结语

在无线网优化中，为了满足容量需求普遍存在单扇区多频点覆盖场景，需进行多层网小区同覆盖判定，以开启负载均衡功能，优化切换重选门限，结合各小区忙时用户数情况，灵活设置均衡启动门限、均衡周期、均衡用户数等参数，达到网络接续顺畅、负载均衡效果。传统方法计算某一小区的同覆盖小区时会与其他所有小区都进行距离计算及方位角比对，时间复杂度高达O（n2）。

本文算法使用GeoHash 算法对小区进行了预处理聚合，每个小区只需与在自己九宫格GeoHash 码网格之内的小区比对，对海量小区而言，总体时间复杂度降为O（n）。经对比实验验证，本算法计算90 w 级别小区同覆盖扇区仅需要3 分钟，在保证了计算正确率的情况下大幅提升了计算效率，提升效率程度达到了93倍。同覆盖扇区的快速计算为后续不均衡扇区发现、负载均衡方案实施节省了大量时间，可以节约网络资源，提升用户感知，达到降本增效目标。本算法可以推广应用于共站信息核查、站址选择等其他需要大批量经纬度距离计算的场景。