一種基于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倍。同覆蓋扇區的快速計算為后續不均衡扇區發現、負載均衡方案實施節省了大量時間，可以節約網絡資源，提升用戶感知，達到降本增效目標。本算法可以推廣應用于共站信息核查、站址選擇等其他需要大批量經緯度距離計算的場景。