基于網(wǎng)優(yōu)大數(shù)據(jù)平臺的LTE站間距算法研究

劉佳

基于網(wǎng)優(yōu)大數(shù)據(jù)平臺的LTE站間距算法研究

劉佳

（中國移動通信集團設(shè)計院有限公司，北京 100080）

LTE站間距相關(guān)指標是中國移動網(wǎng)優(yōu)大數(shù)據(jù)平臺六維度報表中的重要指標，但已知的站間距基本算法在大數(shù)據(jù)環(huán)境下耗時過長，因此基于網(wǎng)優(yōu)大數(shù)據(jù)平臺中工參數(shù)據(jù)的存儲方式，采用GeoHash技術(shù)，設(shè)計并實現(xiàn)了一種小區(qū)級站間距并行計算方法。采用該方法后，計算站間距時可以采用Spark等大數(shù)據(jù)技術(shù)來顯著提升計算速度。

站間距 LTE 大數(shù)據(jù) 六維度報表 GeoHash

1 引言

中國移動網(wǎng)優(yōu)大數(shù)據(jù)平臺從各省采集LTE網(wǎng)絡(luò)數(shù)據(jù)（包括工參、性能數(shù)據(jù)、資源數(shù)據(jù)、MR數(shù)據(jù)等），將采集到的數(shù)據(jù)進行解析，并對原始數(shù)據(jù)進行抽取及處理，將處理后的數(shù)據(jù)存入數(shù)據(jù)庫，以供上層應(yīng)用和分析使用[1]。其中工參數(shù)據(jù)每日更新存儲在Redis數(shù)據(jù)庫中；性能數(shù)據(jù)、資源數(shù)據(jù)、MR數(shù)據(jù)均存儲在Hbase數(shù)據(jù)庫中[2]。

六維度報表是基于底層數(shù)據(jù)采集的上層應(yīng)用之一，六緯度報表總體框架分為數(shù)據(jù)存儲、數(shù)據(jù)處理和數(shù)據(jù)呈現(xiàn)三部分。通過大數(shù)據(jù)服務(wù)引擎將數(shù)據(jù)源提供的數(shù)據(jù)進行計算、匯總后，存入MPP數(shù)據(jù)庫表中，等待前臺頁面查詢。六維度報表數(shù)據(jù)源包括工參數(shù)據(jù)、性能數(shù)據(jù)及MR數(shù)據(jù)等，整體實現(xiàn)架構(gòu)如圖1所示。

圖1 六維度報表實現(xiàn)架構(gòu)圖

站間距相關(guān)指標（包括平均站間距、超遠站占比、超近站占比）采用工參數(shù)據(jù)進行計算，是六維度報表中網(wǎng)絡(luò)結(jié)構(gòu)與覆蓋分析的重要指標[3]。要計算平均站間距、超遠小區(qū)占比必須先計算小區(qū)級站間距，目前小區(qū)級站間距計算是六維度報表實現(xiàn)中算法最復(fù)雜的[4]。小區(qū)級站間距計算復(fù)雜度大，且在網(wǎng)優(yōu)大數(shù)據(jù)平臺中需要計算全國約300萬小區(qū)的站間距，若采用傳統(tǒng)計算方式，計算時間太長，因此必須采用并行計算的方法提升計算效率。

本文對站間距計算方法進行研究，采用GeoHash技術(shù)，設(shè)計并實現(xiàn)了一種小區(qū)級站間距的并行計算方法，該并行計算方法已在網(wǎng)優(yōu)大數(shù)據(jù)平臺六維度報表中實際應(yīng)用。

2 站間距基本算法與傳統(tǒng)實現(xiàn)方法分析

2.1 站間距基本算法介紹

室分站點不參與站間距分析計算，小區(qū)級站間距按照泰森多邊形法及方向角法分別計算后，取較小值[5]。

（1）泰森多邊形法

1）根據(jù)全網(wǎng)所有基站生成泰森多邊形[6]；

2）根據(jù)每個基站泰森多邊形，找到本網(wǎng)絡(luò)內(nèi)它的所有泰森多邊形相鄰基站（泰森多邊形共邊）；

3）計算所有相鄰基站到本小區(qū)的距離，平均值為本小區(qū)站間距，單位使用“m”，使用地球橢球體模型計算距離；

4）小區(qū)無相鄰基站，定義為“孤小區(qū)”，站間距結(jié)果為空。

（2）方位角法

1）根據(jù)小區(qū)A方位角與搜索角寬度確認方向，搜索角寬度范圍為20°～360°，默認為120°。初期按照120°實現(xiàn)，后期考慮共站其他小區(qū)的角度；

2）以小區(qū)經(jīng)緯度為圓心，以搜索半徑a（默認2 km）為半徑，在搜索方向上畫??；

3）如果所得扇區(qū)內(nèi)存在基站X（1個或N個），則將該基站X到A的平均距離計做站間距，如果N＞3，那么取最近的3個值納入計算；

4）如果未找到基站X，那么將搜索半徑由a升級到b（默認10 km），按照2）、3）步驟進行依次計算；

5）如果在b搜索半徑內(nèi)仍未找到基站X，將搜索半徑由b升級為c（默認20 km），按照2）、3）步驟進行依次計算；

6）在c搜索半徑內(nèi)仍未發(fā)現(xiàn)基站，則站間距計為空。

2.2 站間距傳統(tǒng)實現(xiàn)方法分析

站間距基本算法中方位角法較為簡單，每個小區(qū)可以分別計算，計算速度主要受搜索范圍影響，本文不進行主要探討。

泰森多邊形法實現(xiàn)的關(guān)鍵步驟為Delaunay三角網(wǎng)剖分。圖2中每一個點都代表一個獨立的站點，以這個點為端點的所有線段的另外一側(cè)端點就為當前站點的第一圈緊鄰站點。第一圈緊鄰站點與當前站點距離平均值即為該站點小區(qū)的站間距。在傳統(tǒng)實現(xiàn)方法中，必須先對目標區(qū)域進行Delaunay三角網(wǎng)剖分，再對各個站點進行站間距計算。當目標區(qū)域較大，例如對全國范圍進行計算時，Delaunay三角網(wǎng)剖分算法將非常耗時。

泰森多邊形法傳統(tǒng)實現(xiàn)方式的問題在于無法像方位角法一樣分別對各個站點進行計算。如果能將泰森多邊形法的實現(xiàn)方式改進成各個站點可以獨立計算，就可以通過增加計算節(jié)點的方式來提高計算效率。本文研究的站間距并行計算實現(xiàn)方法，即是對泰森多邊形法的實現(xiàn)方式進行改進，讓每個站點獨立按照Delaunay三角網(wǎng)剖分的原則選取第一圈緊鄰站點，并計算站間距。

圖2 Delaunay三角網(wǎng)剖分示意圖

3 小區(qū)級站間距并行計算實現(xiàn)方法

本文基于GeoHash技術(shù)設(shè)計了一種小區(qū)級站間距并行計算方法[7]，方法總體描述如下：首先獲取某基站一定范圍內(nèi)的鄰近基站列表，在這個范圍內(nèi)計算該基站的泰森多邊形法站間距和該基站小區(qū)的方位角法站間距，最后將泰森多邊形法站間距和方位角法站間距中的較小值取為該基站每個小區(qū)的站間距。

在計算泰森多邊形法站間距時，對Delaunay三角網(wǎng)剖分算法進行改進[8]，改進示意圖如圖3所示：

圖3 Delaunay三角網(wǎng)剖分算法改進示意圖

原有Delaunay三角網(wǎng)剖分算法需要將所有點納入計算，本文將該算法改進為可以對一個點按Delaunay三角網(wǎng)剖分法則計算所有相連的邊[9]。經(jīng)過改進后，泰森多邊形站間距計算可以針對每個基站點獨立計算，從而使得整個小區(qū)級站間距算法可以并行計算。

3.1 采用GeoHash技術(shù)獲取鄰近基站列表

從Redis數(shù)據(jù)庫中讀取所有工參數(shù)據(jù)并采用GeoHash進行編碼。

GeoHash將區(qū)域劃分為一個個規(guī)則矩形，并對每個矩形進行編碼。編碼的前綴可以表示更大的區(qū)域，例如wx4g0ec1，它的前綴wx4g0e表示包含編碼wx4g0ec1在內(nèi)的更大范圍。這個特性可以用于搜索附近的點，但是從GeoHash的編碼算法中可以看出它的一個缺點：位于格子邊界兩側(cè)的兩點，雖然十分接近，但編碼會完全不同。為此，我們同時搜索當前格子周圍的8個格子，即可解決這個問題。

GeoHash編碼長度為5時，柵格大小為2.5 km左右。

獲取某基站的鄰近基站列表時，首先計算該基站的GeoHash編碼，編碼長度可指定為5，然后計算該基站所在柵格的周圍8個格子的GeoHash編碼，最后找出前5位GeoHash編碼與上述9個GeoHash編碼之一相同的基站點，即為該基站的鄰近基站列表[10]。

3.2 泰森多邊形法站間距計算

遍歷鄰近基站列表找出距離最短的基站作為第一邊，記錄下第一邊，并將該基站添加到結(jié)果列表resultList中。

遍歷其他鄰近基站，計算目標基站到鄰近基站連線邊與第一邊的順時針夾角，將所有鄰近基站的夾角按從小到大順序排序。

排序后鄰近基站列表記為list 1，將與目標基站距離最短基站添加到list 1的末尾。

遍歷list 1，選擇第一個基站與第一邊構(gòu)成三角形，并檢測該三角形外接圓內(nèi)是否有基站點，如果有，則選擇下一個鄰近基站重復(fù)上述空圓檢測；如果沒有，將該鄰近基站添加到結(jié)果列表resultList，并將算法中的第一邊替換為目標基站與該鄰近基站的連線，重復(fù)上述操作，繼續(xù)對后續(xù)的鄰近基站進行空圓檢測，直到遍歷完list 1。

計算目標基站與結(jié)果列表resultList中所有基站距離的平均值，即為該基站下所有小區(qū)的泰森多邊形法站間距。

3.3 方位角法站間距計算

遍歷鄰近基站列表，計算某一基站與小區(qū)基站的方位角，如果方位角與小區(qū)方位角差距絕對值小于60，則繼續(xù)計算，否則跳過。

計算基站與小區(qū)基站的距離，如果距離小于等于2 km，則將該基站加入list 1；如果距離大于2 km且小于等于10 km，則將該基站加入list 2；如果距離大于10 km且小于等于20 km，則將該基站加入list 3。

鄰近基站列表遍歷完成后，檢查list 1、list 2、list 3，如果list 1不為0且長度大于3，取其中最小的3個距離值求平均值即為站間距；如果list 1長度小于3，則所有值求平均值即為站間距。

如果list 1的長度為0，則計算list 2；如果list 2的長度也為0，則計算list 3；如果list 3的長度也為0，返回空值。

4 算法驗證及應(yīng)用

4.1 算法準確性驗證

采用Java語言編寫程序?qū)崿F(xiàn)小區(qū)級站間距并行計算方法。為了測試算法準確性，采用測試數(shù)據(jù)對算法進行了測試，測試數(shù)據(jù)準備方法如下：

在百度地圖上取6×6個點，相鄰兩點間距離為500 m，利用百度地圖工具得到各個點的經(jīng)緯度。原圖比例尺以及所取點如圖4所示。對中間16個點進行站間距計算，計算結(jié)果均為500 m左右，準確度較好。

4.2 算法效率分析及與傳統(tǒng)實現(xiàn)方法的比較

采用Java語言編寫多線程程序?qū)崿F(xiàn)小區(qū)級站間距并行計算方法。測試數(shù)據(jù)采用北京市工參數(shù)據(jù)，程序執(zhí)行時間與線程數(shù)量之間的關(guān)系如圖5所示。根據(jù)測試結(jié)果，增加線程數(shù)量可以提升計算效率。

圖4 百度地圖上展示的算法測試數(shù)據(jù)

圖5 程序運行時間與線程數(shù)關(guān)系圖

傳統(tǒng)實現(xiàn)方法是先對所有小區(qū)完成Delaunay三角網(wǎng)剖分以后，再進行站間距計算，計算速度與上述采用一個線程進行計算的效率相當，無法通過增加計算資源來提升計算效率。

改進后的算法可以通過多線程或多個計算節(jié)點的方式來提升計算效率。目前在大數(shù)據(jù)領(lǐng)域已有一些優(yōu)秀的分布式計算框架，例如Spark等。Spark基于內(nèi)存計算，將磁盤數(shù)據(jù)讀入內(nèi)存，將計算結(jié)果保存在內(nèi)存，這樣可以很好地進行迭代運算，提高了在大數(shù)據(jù)環(huán)境下數(shù)據(jù)處理的實時性。改進后的算法可以充分利用這些優(yōu)秀的大數(shù)據(jù)處理技術(shù)來進一步提升效率。

4.3 算法實際應(yīng)用情況

在網(wǎng)優(yōu)大數(shù)據(jù)平臺中，利用Spark采用上述算法進行計算，結(jié)果與原網(wǎng)優(yōu)平臺計算結(jié)果大致相同，且計算效率得到極大提升。以北京市為例，北京市所有小區(qū)的站間距僅用幾分鐘就計算完成。

5 結(jié)束語

六維度報表中站間距算法較為復(fù)雜，且在大數(shù)據(jù)環(huán)境下，對于計算效率提出了更高要求。為了能夠使用Spark等大數(shù)據(jù)技術(shù)提升計算速度，本文采用Geohash技術(shù)，設(shè)計并實現(xiàn)了一種小區(qū)級站間距的并行計算方法。在網(wǎng)優(yōu)大數(shù)據(jù)平臺中，該算法已經(jīng)被使用。以北京市為例，北京市所有小區(qū)的站間距僅用幾分鐘就計算完成。在站間距計算速度得到極大提升的前提下，站間距可以作為小區(qū)工參中的一個屬性被回填到數(shù)據(jù)庫中，這樣可以滿足更精細化的應(yīng)用需求的開發(fā)，例如分場景的站間距評估等。

[1] 胡舜耕,魏進武. 大數(shù)據(jù)及其在電信運營中的應(yīng)用研究[J]. 電信技術(shù), 2015(1): 14-17.

[2] 余海波. 大數(shù)據(jù)在電信移動通信網(wǎng)絡(luò)優(yōu)化中的應(yīng)用[J].廣西通信技術(shù), 2014(4): 8-11.

[3] 李泉. TD-LTE網(wǎng)絡(luò)優(yōu)化分析和研究[J]. 移動通信, 2016,40(10): 3-6.

[4] 李寶磊,周俊,任曉華. TD-LTE網(wǎng)絡(luò)優(yōu)化關(guān)鍵問題的研究[J]. 電信工程技術(shù)與標準化, 2015(1): 57-61.

[5] 陳大業(yè),李丙輝,薛云山,等. 根據(jù)經(jīng)緯度計算站間距模塊的設(shè)計與實現(xiàn)[J]. 電信技術(shù), 2014(2): 37-39.

[6] 申永源,曹布陽. 泰森多邊形并行生成算法研究與實現(xiàn)[J]. 福建電腦, 2010(7): 1-4.

[7] 金安,程承旗,宋樹華,等. 基于Geohash的面數(shù)據(jù)區(qū)域查詢[J]. 地理與地理信息科學(xué), 2013,29(5): 31-35.

[8] 劉少華,程鵬根,趙寶貴. 約束數(shù)據(jù)域的Delaunay三角剖分算法研究及應(yīng)用[J]. 計算機應(yīng)用研究, 2004,21(3): 26-28.

[9] 李小麗,陳花竹. 基于網(wǎng)格劃分的Delaunay三角剖分算法研究[J]. 計算機與數(shù)字工程, 2011,39(7): 57-59.

[10] 趙雨琪,牟乃夏,祝帥兵,等. 基于GeoHash算法的周邊查詢應(yīng)用研究[J]. 軟件導(dǎo)刊, 2016,15(6): 16-18. ★

Research on LTE Site Spacing Calculation Method Based on Network Optimization Big Data Platform

LIU Jia
(China Mobile Group Design Institute Co., Ltd., Beijing 100080, China)

LTE site spacing related KPIs are important in the six-dimensional report of the network optimization big data platform for China Mobile. However, the existing algorithms of site spacing are time-consuming in the environment of big data. Therefore, a cell-level parallel calculation method of site spacing was designed and realized using GeoHash based on the engineering parameters stored in the network optimization big data platform. According to the method, the calculation speed of the site spacing calculation can be highly enhanced based on big data technology such as Spark.

site spacing LTE big data six-dimensional report GeoHash

10.3969/j.issn.1006-1010.2017.15.005

TN929.5

A

1006-1010(2017)15-0024-05

劉佳. 基于網(wǎng)優(yōu)大數(shù)據(jù)平臺的LTE站間距算法研究[J]. 移動通信, 2017,41(15): 24-28.

2017-05-17

責任編輯：黃耿東 huanggengdong@mbcom.cn

劉佳：工程師，碩士畢業(yè)于北京郵電大學(xué)，現(xiàn)任中國移動通信集團設(shè)計院有限公司咨詢設(shè)計師，主要從事移動網(wǎng)絡(luò)設(shè)計、優(yōu)化相關(guān)工具平臺研發(fā)工作。