王 越，劉 佳，康志文，張清偉，高宗寶

（中國移動通信集團設(shè)計院有限公司山東分公司，濟南 250101）

0 引言

隨著移動通信技術(shù)的發(fā)展，網(wǎng)絡(luò)高負(fù)荷問題日益凸顯，相繼出現(xiàn)高業(yè)務(wù)量區(qū)域、高校熱點場景區(qū)域和景區(qū)突發(fā)高用戶數(shù)區(qū)域容量不足的情況。為改善現(xiàn)網(wǎng)負(fù)荷，一方面不斷開展小區(qū)擴容、站點新建等舉措，另一方面通過現(xiàn)網(wǎng)KPI指標(biāo)監(jiān)控，同覆蓋扇區(qū)間的容量差異愈發(fā)明顯，一個因高業(yè)務(wù)量耗盡資源導(dǎo)致無法使用業(yè)務(wù)，另一個卻處于空閑，造成資源浪費，需要實施負(fù)荷均衡方案。因此，同覆蓋扇區(qū)的判定是首要解決的問題，同覆蓋判定的有效性、準(zhǔn)確性、時效性決定均衡方案的實施效果。

根據(jù)《中國移動高流量小區(qū)優(yōu)化指導(dǎo)意見4.0》［1］，其中對同覆蓋扇區(qū)定義為：異頻宏站站間距小于50 m，小區(qū)方位角偏差小于15°（從方位角0°開始順時針選擇第一個小區(qū)，以該小區(qū)為基準(zhǔn)小區(qū)，其余小區(qū)若方位角與該小區(qū)差距在15°以內(nèi)，則均納入第一個同覆蓋扇區(qū)；隨后順時針選擇第二個小區(qū)，若該小區(qū)之前已有同覆蓋扇區(qū)，則不再考慮，否則作為第二個基準(zhǔn)小區(qū)，再判斷其他小區(qū)是否與該基準(zhǔn)小區(qū)同覆蓋。

同覆蓋規(guī)則涉及小區(qū)間的經(jīng)緯度和方位角計算和判斷，傳統(tǒng)方法［2-3］計算某一小區(qū)的同覆蓋小區(qū)時會與其他所有小區(qū)都進(jìn)行距離計算及方位角比對，計算效率較低且容易耗費內(nèi)存資源。GeoHash 是一種地址編碼方法［4-7］，它把二維的空間經(jīng)緯度數(shù)據(jù)編碼成一個字符串，位置相近的點具有公共前綴。本文根據(jù)GeoHash 編碼此特性，設(shè)計了一種快速同覆蓋扇區(qū)判別算法，首先對小區(qū)及周邊九宮格進(jìn)行GeoHash編碼預(yù)處理，之后對小區(qū)進(jìn)行GeoHash碼聚類，最終通過同聚類中的小區(qū)互相比對得到判定結(jié)果。

1 算法模型

1.1 GeoHash算法

GeoHash是一種地址編碼方法，它可以將二維的空間經(jīng)緯度數(shù)據(jù)編碼成一個字符串，在附近點搜索等領(lǐng)域有廣泛的應(yīng)用。它將整個地球作為一個平面，不斷使用二分法將區(qū)域劃分成一個個正方形的柵格，這樣每一個柵格都會有唯一的二進(jìn)制編碼，編碼越長，代表柵格的精度越高。之后GeoHash 算法將二分的二進(jìn)制編碼使用Base32 編碼轉(zhuǎn)換為字符串形式，同樣，當(dāng)字符串長度更長時，柵格的寬度更小，所代表的的范圍更精確。

GeoHash算法的流程如下：

（1）將經(jīng)緯度二分變?yōu)槎M(jìn)制，二分的次數(shù)越多，GeoHash編碼越長，對應(yīng)的精度越高；

（2）二進(jìn)制經(jīng)緯度合并，偶數(shù)位放經(jīng)度，奇數(shù)位放緯度，組成新的編碼串；

（3）對合并后的編碼進(jìn)行Base32編碼，生成最終的GeoHash編碼。

以 點（30.280245oN,120.027162OE）為例，GeoHash編碼經(jīng)緯度二分過程如圖1所示。

圖1 GeoHash編碼經(jīng)緯度二分劃分過程

GeoHash算法將二維的經(jīng)緯度編碼后轉(zhuǎn)換成一維字符串表示，字符串越長，表示的范圍越精確。當(dāng)編碼長度為7 位時，誤差在76 m 左右；而編碼長度為8 位時，誤差為19 m 左右。具體GeoHash編碼長度與精度對應(yīng)關(guān)系見圖2。

圖2 GeoHash 編碼長度與精度對應(yīng)圖

1.2 基于GeoHash的同覆蓋扇區(qū)高效判定算法

GeoHash編碼的性質(zhì)為，兩點之間的距離越近，GeoHash編碼的公共前綴越長?？梢酝ㄟ^比較GeoHash匹配的位數(shù)來判斷兩個點之間的大概距離。假設(shè)GeoHash 編碼誤差為d，如果兩點位于同一GeoHash編碼劃分矩形內(nèi)，兩點間歐式距離范圍為［0,］（兩點重合到對角線距離）。

如果只憑借GeoHash 碼相同判斷兩點距離在一定范圍之內(nèi)，可能會出現(xiàn)漏算情況。如圖3所示，綠點與紅點GeoHash 編碼不同，但都處于本身GeoHash 劃分矩形的邊緣，兩點之間距離較近。為解決此問題，引入九宮格的概念，以黃點為例，計算出其周圍八個相鄰GeoHash劃分矩形引入。

圖3 GeoHash編碼示例切分矩形

根據(jù)同覆蓋扇區(qū)計算規(guī)則（距離在50 m 之內(nèi)），選擇使用7 位GeoHash 編碼預(yù)處理（誤差79 m），保證了如果A、B 兩個小區(qū)距離滿足同覆蓋扇區(qū)條件，那么A 小區(qū)一定位于B 小區(qū)GeoHash 編碼九宮格范圍內(nèi)。如果A 小區(qū)處于B小區(qū)九宮格內(nèi)，需要計算兩小區(qū)距離判定是否滿足條件。這樣就將每個小區(qū)的計算列表從全部小區(qū)縮減到了近距離小區(qū)集，減少了不必要的計算量。本文采取的算法流程如圖4所示。

圖4 GeoHash算法判定同覆蓋扇區(qū)算法流程

（1）工參數(shù)據(jù)預(yù)處理，去除經(jīng)緯度、方位角無效的數(shù)據(jù)；

（2）根據(jù)小區(qū)經(jīng)緯度進(jìn)行GeoHash 編碼，同時計算出小區(qū)九宮格位置的GeoHash編碼；

（3）根據(jù)GeoHash 碼聚類小區(qū)，最終生成GeoHash 碼——在GeoHash 碼網(wǎng)格中的小區(qū)列表HashMap；

（4）遍歷每個小區(qū)，根據(jù)當(dāng)前小區(qū)九宮格的GeoHash 碼組，從步驟（3）中可取出在當(dāng)前小區(qū)九宮格內(nèi)的小區(qū)列表；

（5）以當(dāng)前小區(qū)為基準(zhǔn)，一一計算與步驟（4）中的九宮格小區(qū)的距離、方位角、站型差異，判定是否滿足共覆蓋標(biāo)準(zhǔn)，并將結(jié)果持久化至數(shù)據(jù)庫中。

傳統(tǒng)方法計算某一小區(qū)的同覆蓋小區(qū)時會與其他所有小區(qū)都進(jìn)行距離計算及方位角比對，時間復(fù)雜度高達(dá)O（n2）。本算法使用了GeoHash算法對小區(qū)進(jìn)行了預(yù)處理聚合，每個小區(qū)只需與在自己九宮格GeoHash 碼網(wǎng)格之內(nèi)的小區(qū)比對，對海量小區(qū)而言，總體時間復(fù)雜度降為O（n），大大減少了不必要計算。

1.3 對比實驗驗證

本文選擇實驗環(huán)境：CentOS 7，16core，內(nèi)存64 GB，硬盤2 T。

選取70 w、90 w 小區(qū)，分別使用傳統(tǒng)算法及本文算法進(jìn)行測試，運行十次，測試結(jié)果見表1。

表1 同覆蓋扇區(qū)計算對比驗證表

經(jīng)驗證，兩種算法輸出結(jié)果相同，傳統(tǒng)算法計算70 w級別小區(qū)的同覆蓋扇區(qū)平均需要220分鐘，使用本文算法只需要1分鐘；傳統(tǒng)算法計算90 w級別小區(qū)的同覆蓋扇區(qū)平均需要280分鐘，使用本文算法只需要3分鐘。本文算法在保證了計算正確率的情況下大幅提升了計算效率，提升效率程度達(dá)到了93倍（1/3-1/280）/（1/280）。

圖5 同覆蓋扇區(qū)計算對比驗證圖

目前，已將本算法使用Java 代碼實現(xiàn)，并集成于生產(chǎn)平臺中，為后續(xù)負(fù)載均衡模塊進(jìn)行垂直面-同覆蓋多層網(wǎng)優(yōu)化、派發(fā)工單等提供數(shù)據(jù)支撐。以山東省為例（70 w 級別4G 小區(qū)），傳統(tǒng)算法計算需要四個小時，使用本算法只需1分鐘，且結(jié)果準(zhǔn)確無誤，效率提升非常明顯。

2 結(jié)語

在無線網(wǎng)優(yōu)化中，為了滿足容量需求普遍存在單扇區(qū)多頻點覆蓋場景，需進(jìn)行多層網(wǎng)小區(qū)同覆蓋判定，以開啟負(fù)載均衡功能，優(yōu)化切換重選門限，結(jié)合各小區(qū)忙時用戶數(shù)情況，靈活設(shè)置均衡啟動門限、均衡周期、均衡用戶數(shù)等參數(shù)，達(dá)到網(wǎng)絡(luò)接續(xù)順暢、負(fù)載均衡效果。傳統(tǒng)方法計算某一小區(qū)的同覆蓋小區(qū)時會與其他所有小區(qū)都進(jìn)行距離計算及方位角比對，時間復(fù)雜度高達(dá)O（n2）。

本文算法使用GeoHash 算法對小區(qū)進(jìn)行了預(yù)處理聚合，每個小區(qū)只需與在自己九宮格GeoHash 碼網(wǎng)格之內(nèi)的小區(qū)比對，對海量小區(qū)而言，總體時間復(fù)雜度降為O（n）。經(jīng)對比實驗驗證，本算法計算90 w 級別小區(qū)同覆蓋扇區(qū)僅需要3 分鐘，在保證了計算正確率的情況下大幅提升了計算效率，提升效率程度達(dá)到了93倍。同覆蓋扇區(qū)的快速計算為后續(xù)不均衡扇區(qū)發(fā)現(xiàn)、負(fù)載均衡方案實施節(jié)省了大量時間，可以節(jié)約網(wǎng)絡(luò)資源，提升用戶感知，達(dá)到降本增效目標(biāo)。本算法可以推廣應(yīng)用于共站信息核查、站址選擇等其他需要大批量經(jīng)緯度距離計算的場景。