劉佳

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

劉佳

（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司，北京 100080）

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

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

1 引言

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

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

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

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

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

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

2.1 站間距基本算法介紹

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

（1）泰森多邊形法

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

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

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

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

（2）方位角法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GeoHash編碼長(zhǎng)度為5時(shí)，柵格大小為2.5 km左右。

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

3.2 泰森多邊形法站間距計(jì)算

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

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

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

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

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

3.3 方位角法站間距計(jì)算

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

計(jì)算基站與小區(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且長(zhǎng)度大于3，取其中最小的3個(gè)距離值求平均值即為站間距；如果list 1長(zhǎng)度小于3，則所有值求平均值即為站間距。

如果list 1的長(zhǎng)度為0，則計(jì)算list 2；如果list 2的長(zhǎng)度也為0，則計(jì)算list 3；如果list 3的長(zhǎng)度也為0，返回空值。

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

4.1 算法準(zhǔn)確性驗(yàn)證

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

[6] 申永源,曹布陽. 泰森多邊形并行生成算法研究與實(shí)現(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]. 計(jì)算機(jī)應(yīng)用研究, 2004,21(3): 26-28.

[9] 李小麗,陳花竹. 基于網(wǎng)格劃分的Delaunay三角剖分算法研究[J]. 計(jì)算機(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ù)平臺(tái)的LTE站間距算法研究[J]. 移動(dòng)通信, 2017,41(15): 24-28.

2017-05-17

責(zé)任編輯：黃耿東 huanggengdong@mbcom.cn

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