張海永，方賢進(jìn)*，張恩皖，李寶玉，彭超，穆健翔

基于測(cè)量報(bào)告信號(hào)聚類的指紋定位方法

張海永1，2，方賢進(jìn)1*，張恩皖3，李寶玉2，彭超4，穆健翔2

（1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001； 2.科大國(guó)創(chuàng)云網(wǎng)科技有限公司，合肥 230088； 3.中國(guó)移動(dòng)通信集團(tuán)安徽有限公司，合肥 230088； 4.國(guó)防科技大學(xué) 電子對(duì)抗學(xué)院，合肥 230037）（?通信作者電子郵箱xjfang@aust.edu.cn）

針對(duì)基于加權(quán)最近鄰（WKNN）和機(jī)器學(xué)習(xí)算法的指紋庫定位方法存在精度和定位效率較低的問題，提出一種基于測(cè)量報(bào)告（MR）信號(hào)聚類的指紋定位方法。首先，把MR信號(hào)分為室內(nèi)、道路和室外這3種屬性；其次，利用地理信息系統(tǒng)（GIS）信息將柵格分為建筑物、道路和室外子區(qū)域，并將不同屬性的MR數(shù)據(jù)落入對(duì)應(yīng)的屬性子區(qū)域；最后，借助均值（-Means）聚類算法對(duì)柵格內(nèi)的MR信號(hào)進(jìn)行聚類分析，以創(chuàng)建子區(qū)域下的虛擬子區(qū)域，并采用WKNN算法對(duì)MR測(cè)試樣本進(jìn)行匹配。此外，利用歐氏距離計(jì)算平均定位精度，并通過生產(chǎn)環(huán)境的一些MR數(shù)據(jù)測(cè)試了所提方法的定位性能。實(shí)驗(yàn)結(jié)果表明，所提方法的50 m定位誤差占比為71.21%，相較于WKNN算法提升了2.64個(gè)百分點(diǎn)；平均定位定位誤差為44.73 m，相較于WKNN算法降低了7.60 m。所提方法具備良好的定位精度和效率，可滿足生產(chǎn)環(huán)境中MR數(shù)據(jù)的定位需求。

測(cè)量報(bào)告；定位；信號(hào)聚類；加權(quán)K最近鄰算法；歐氏距離

0 引言

位置能力是運(yùn)營(yíng)商數(shù)據(jù)核心能力之一［1］，在對(duì)內(nèi)運(yùn)維優(yōu)化、精準(zhǔn)營(yíng)銷，對(duì)外數(shù)據(jù)變現(xiàn)、行業(yè)應(yīng)用支撐等［2-3］方面起著至關(guān)重要的作用。室外定位方法中，雖然已有基站定位［4］、到達(dá)時(shí)間（Time Of Arrival， TOA）定位［5］、到達(dá)時(shí)間差（Time Difference Of Arrival， TDOA）定位［6-7］、到達(dá)角度（Angle of Arrival，AOA）定位［8-9］、無線網(wǎng)絡(luò)技術(shù)（Wireless Fidelity，Wi-Fi）定位［10-11］等定位方法，但是在實(shí)際應(yīng)用中，基站定位精度一般在200 m以上，無法滿足高精度定位的業(yè)務(wù)需求；而基于TOA、TDOA定位方法至少需要3個(gè)基站才能估算目標(biāo)位置，AOA定位方法至少需要2個(gè)基站才能估算目標(biāo)位置，且該類方法對(duì)數(shù)據(jù)質(zhì)量、時(shí)間同步要求較高，定位精度較差。Wi-Fi定位方法，需要建設(shè)大量的無線接入點(diǎn)（Access Point， AP），投入成本較大，不適合當(dāng)前室外定位的場(chǎng)景。當(dāng)前，運(yùn)營(yíng)商主流且能夠提供較為準(zhǔn)確位置能力的技術(shù)是基于測(cè)量報(bào)告（Measurement Report， MR）的指紋定位技術(shù)［12］。MR數(shù)據(jù)可通過無線管理平臺(tái)進(jìn)行周期性配置或者事件觸發(fā)式配置，使手機(jī)終端上報(bào)毫秒級(jí)MR。MR記錄了用戶手機(jī)在業(yè)務(wù)過程中的主服務(wù)小區(qū)ID、鄰服務(wù)小區(qū)ID、信號(hào)強(qiáng)度、時(shí)間提前量和方位角等一系列無線信息，具有更全面、更完整、更易取得的優(yōu)點(diǎn)。

本文的主要工作如下：

1）提出一種基于MR信號(hào)聚類的指紋定位方法，通過對(duì)柵格中的信號(hào)聚類分析，提升在復(fù)雜的地理環(huán)境下MR定位的精度。

2）在數(shù)據(jù)處理過程中，基于信號(hào)傳播特征，對(duì)MR樣本數(shù)據(jù)進(jìn)行了有效清洗和缺失值處理；并通過對(duì)柵格的劃分和聚類分析，可以將位置定位至柵格內(nèi)的任意聚類中心。

3）通過實(shí)驗(yàn)證明，將柵格劃分更小，僅空間聚類而不考慮信號(hào)間特性，并不能提升定位精度；通過柵格中基于信號(hào)聚類分析，可以有效提升定位精度，并且保證了定位的性能。

1 相關(guān)工作

在運(yùn)營(yíng)商位置應(yīng)用場(chǎng)景中，對(duì)MR定位的精度和效率有著明確的要求。為此，眾多學(xué)者在此方面進(jìn)行了探索。相較于基于加權(quán)最近鄰（Weighted-Nearest Neighbor， WKNN）算法［13］實(shí)現(xiàn)的MR指紋庫定位方式，當(dāng)前前沿的是利用機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)MR指紋庫定位精度的提升，Zhang等［14-15］提出了一種上下文感知的定位技術(shù)RLoc（context-awaRe telco Localization），該技術(shù)引入兩階段自適應(yīng)隱馬爾可夫模型，以計(jì)算MR樣本序列的置信度，找出有缺陷的MR樣本，并計(jì)算位置轉(zhuǎn)移的可能性，再通過動(dòng)態(tài)路徑規(guī)劃的方法修復(fù)路徑缺陷序列，從而提升電信定位精度；然而該技術(shù)面對(duì)運(yùn)營(yíng)商TB級(jí)別的MR數(shù)據(jù)時(shí)，計(jì)算性能存在著極大的考驗(yàn)。王寧等［16］提出一種基于機(jī)器學(xué)習(xí)算法設(shè)計(jì)高精度混合定位算法的思想，采用AdaBoost算法對(duì)同區(qū)域具備定位信息標(biāo)簽的MR數(shù)據(jù)進(jìn)行模型訓(xùn)練，該模型可對(duì)定位信息缺失的MR數(shù)據(jù)進(jìn)行較高精度的定位信息重構(gòu)，并且具有較好的性能和定位精度；但是該方法基于基站扇區(qū)維度的指紋庫構(gòu)建，而一個(gè)基站扇區(qū)覆蓋范圍較大，在運(yùn)營(yíng)商大數(shù)據(jù)下，計(jì)算復(fù)雜度將成倍增長(zhǎng)。周志超等［17］提出基于移動(dòng)蜂窩網(wǎng)的機(jī)器學(xué)習(xí)室外指紋定位方案，通過柵格化和非柵格化兩種方式，利用機(jī)器學(xué)習(xí)實(shí)現(xiàn)對(duì)MR的定位；然而其中基于柵格化的方式只能將定位位置定位于單點(diǎn)位置，存在較大的性能折損，基于非柵格化的方式雖然沒有性能折損，但是定位精度較低。

Toril等［18］研究了長(zhǎng)期演進(jìn)（Long Term Evolution， LTE）技術(shù)網(wǎng)絡(luò)道路場(chǎng)景中無線電信號(hào)強(qiáng)度波動(dòng)情況，顯示同一地理位置信號(hào)電平最高偏差23 dBm。Micheli等［19］分析了手機(jī)報(bào)告的最小化路測(cè)數(shù)據(jù)，發(fā)現(xiàn)陰雨天氣會(huì)對(duì)LTE車載電磁傳播產(chǎn)生較大影響。上述研究成果表明，真實(shí)環(huán)境會(huì)對(duì)MR定位產(chǎn)生了較大的影響。此外，指紋庫建設(shè)龐大，針對(duì)一個(gè)城市需要完成千萬數(shù)據(jù)集的訓(xùn)練，并實(shí)現(xiàn)每日百億次的數(shù)據(jù)定位能力，對(duì)硬件設(shè)備和定位性能有著嚴(yán)峻的考驗(yàn)；因此需要在保障定位精度的情況下，實(shí)現(xiàn)高效的定位能力，以滿足業(yè)務(wù)需求。

針對(duì)上述的需求與挑戰(zhàn)，受柵格化的MR指紋庫啟發(fā)，本文設(shè)計(jì)了一種基于MR信號(hào)聚類的指紋定位方法。該方法在原有柵格化的基礎(chǔ)上，創(chuàng)新性地引入了建筑物、道路的地理信息系統(tǒng)（Geographic Information System，GIS）數(shù)據(jù)，將柵格細(xì)分為建筑物、道路和室外子區(qū)域?？紤]不同區(qū)域內(nèi)信號(hào)的差異，利用均值（-Means）聚類算法對(duì)各個(gè)子區(qū)域進(jìn)行聚類計(jì)算，各個(gè)聚類中心作為定位點(diǎn)。該方法一方面豐富了定位區(qū)域，降低了性能折損，提升了定位精度；另一方面具有較高的定位性能，可以滿足定位業(yè)務(wù)性能的需求。

2 MR信號(hào)聚類總體框架

MR信號(hào)聚類的總體框架如圖1所示，主要包含5個(gè)模塊：MR樣本數(shù)據(jù)集構(gòu)建模塊、MR數(shù)據(jù)預(yù)處理模塊、柵格劃分模塊、MR指紋庫構(gòu)建模塊、MR指紋庫定位和評(píng)估模塊。

圖1　MR信號(hào)聚類的總體框架

2.1　MR樣本數(shù)據(jù)集構(gòu)建模塊

由于MR數(shù)據(jù)沒有用戶號(hào)碼和位置信息，需要與S1接口移動(dòng)管理實(shí)體（Mobility Management Entity， MME）信令數(shù)據(jù)通過三元組（MME碼，MME組標(biāo)碼，應(yīng)用程序標(biāo)識(shí)）進(jìn)行關(guān)聯(lián)，獲取用戶號(hào)碼信息，再通過與S1-U用戶上網(wǎng)話單數(shù)據(jù)中的用戶號(hào)碼進(jìn)行關(guān)聯(lián)，從而回填部分MR數(shù)據(jù)的位置信息；然而S1-U上網(wǎng)話單中的位置信息是通過解析用戶上網(wǎng)請(qǐng)求過程中上報(bào)的位置獲得，具有經(jīng)緯度的S1-U數(shù)據(jù)不足1%。因此，通過3種數(shù)據(jù)源的關(guān)聯(lián)，可以構(gòu)建一定量含有經(jīng)緯度的MR樣本集，樣本集包含主、鄰全球小區(qū)識(shí)別碼（Cell Global Identifier， CGI）、參考信號(hào)接收功率（Reference Signal Receiving Power， RSRP）、時(shí)間提前量（Time Advanced， TA）和關(guān)聯(lián)的經(jīng)度、緯度，用于MR指紋庫建庫。

本文所用符號(hào)說明如表1所示。

2.2　MR數(shù)據(jù)預(yù)處理模塊

1）MR樣本數(shù)據(jù)分類。

MR樣本點(diǎn)在不同環(huán)境下具有不同的地理屬性，可以通過位置移動(dòng)、信號(hào)變化和基站類型等進(jìn)行判斷，從而劃分MR樣本點(diǎn)的地理屬性。MR樣本點(diǎn)根據(jù)地理屬性可劃分為室內(nèi)樣本點(diǎn)、道路樣本點(diǎn)、室外樣本點(diǎn)這3種類型?；绢愋鸵话銊澐譃槭曳只竞褪彝饣?，其中室分基站一般部署在大型寫字樓內(nèi)，覆蓋范圍較小。MR室內(nèi)樣本點(diǎn)通過判斷上報(bào)的基站是否為室分基站，確定MR樣本點(diǎn)是否為室內(nèi)樣本點(diǎn)。如果沒有使用室分基站，由于室內(nèi)信號(hào)在無室分情況下存在信號(hào)大幅衰減現(xiàn)象，因此可以通過MR連續(xù)信號(hào)變化模擬用戶進(jìn)出室內(nèi)的過程，從而提取MR室內(nèi)樣本點(diǎn)。MR道路樣本點(diǎn)則通過用戶速度、基站切換、基站的場(chǎng)景和信號(hào)穩(wěn)定性進(jìn)行判斷：通過速度可以識(shí)別高速行駛用戶；通過基站切換相似度匹配可以獲取相似軌跡的用戶；通過基站工參部署的場(chǎng)景為地鐵，則可以提取地鐵線路上的MR樣本等。識(shí)別以上兩種MR室內(nèi)樣本點(diǎn)、MR道路樣本點(diǎn)后，其余數(shù)據(jù)歸為MR室外樣本點(diǎn)。最終，模型輸出為CGI、TA、RSRP、LON、LAT、MR屬性（室外樣本點(diǎn)、室內(nèi)樣本點(diǎn)、道路樣本點(diǎn)）。

2）異常值處理。

基站在城區(qū)一般覆蓋范圍為200～500 m，由于存在過覆蓋和信號(hào)漂移現(xiàn)象，導(dǎo)致定位點(diǎn)樣本經(jīng)緯度不準(zhǔn)確。對(duì)此，通過計(jì)算基站位置和終端位置計(jì)算基站和采集終端的水平位置；再根據(jù)基站參數(shù)站高，通過勾股定理計(jì)算基站到終端的歐氏距離，如圖2所示。

圖2　信號(hào)傳播距離模型

Fig.2　Signal propagation distance model

MR中TA可以表示為基站與終端的距離范圍。表2為TA值與最大和最小采樣時(shí)間的關(guān)系表［20］。

表2　TA關(guān)系

表2中，Ts是LTE中正交頻分復(fù)用（Orthogonal Frequency Division Multiplexing， OFDM）技術(shù)符號(hào)快速傅里葉變換（Fast Fourier Transform， FFT）大小為2 048點(diǎn)的采樣時(shí)間（分辨率），即OFDM時(shí)域符號(hào)持續(xù)時(shí)間為2 048 Ts=1 s/15 kHz。由于無線端口與終端的傳播速度約為光速，則1 Ts可表示距離（單位：m）為：

因此可計(jì)算出：

此處定義合理率，即

2.3　柵格劃分模塊

柵格劃分的一般方式是將地理區(qū)域劃分成50 m×50 m的柵格，然后對(duì)柵格內(nèi)所有的數(shù)據(jù)點(diǎn)根據(jù)主鄰小區(qū)進(jìn)行統(tǒng)計(jì)、分組和建模計(jì)算，并以柵格的中心點(diǎn)作為定位結(jié)果的位置；然而此種方式很容易造成特征失真，定位點(diǎn)單一，且性能折損較大。因此通過引入城市建筑物和道路的GIS信息，并對(duì)該GIS數(shù)據(jù)進(jìn)行處理和劃分，使得柵格具有建筑物、道路和室外屬性的子區(qū)域，極大豐富了定位位置［21］。

對(duì)GIS數(shù)據(jù)處理步驟如下：

步驟1 獲取GIS建筑物和道路數(shù)據(jù)進(jìn)行預(yù)處理，生成格式化道路和建筑物數(shù)據(jù)。

步驟2 原始道路數(shù)據(jù)是一條直線，根據(jù)道路的屬性進(jìn)行橫向擴(kuò)展，并形成封閉道路區(qū)域。

步驟3 計(jì)算柵格與封閉區(qū)域交叉點(diǎn)。

步驟4 對(duì)柵格邊界點(diǎn)數(shù)據(jù)進(jìn)行插值填充。

步驟5 判斷道路和建筑物與柵格之間是否生成封閉區(qū)域：如是，則生成子區(qū)域，并遍歷該子區(qū)域封閉區(qū)間點(diǎn)；否則，繼續(xù)判斷是否生成封閉區(qū)域。

步驟6 輸出所有子區(qū)域，柵格劃分完成。

最終劃分結(jié)果如圖3所示。模型輸出為GRID_ID、GRID_SUB_ID、GRID_SUB_TYPE（室內(nèi)、室外、道路）、GRID_SUB_ORDER，利用以上輸出的GIS信息可以計(jì)算MR樣本數(shù)據(jù)所屬的柵格子區(qū)域。

圖3　柵格劃分結(jié)果

2.4　MR指紋庫構(gòu)建模塊

1）填充子?xùn)鸥裉卣餍畔ⅰ?/p>

根據(jù)以上的步驟，將MR數(shù)據(jù)點(diǎn)分成建筑物、道路和室外這3種類型，并且將柵格內(nèi)的區(qū)域分成了建筑物子區(qū)域、道路子區(qū)域和室外子區(qū)域這3種類型。為了將各數(shù)據(jù)點(diǎn)匹配到相應(yīng)區(qū)域，需要將MR數(shù)據(jù)落入對(duì)應(yīng)子區(qū)域。首先，針對(duì)MR屬性和位置屬性完全匹配的MR樣本點(diǎn)，采用直接落入對(duì)應(yīng)子區(qū)域的處理方式；其次，對(duì)于MR屬性和位置屬性不匹配的情況，拓展建筑物和道路區(qū)域，計(jì)算具有屬性的MR樣本點(diǎn)距離對(duì)應(yīng)屬性子區(qū)域的最近距離，并設(shè)置對(duì)應(yīng)閾值，保留在閾值內(nèi)的數(shù)據(jù)；最后，舍棄落入建筑物和道路子區(qū)域但是屬性不匹配的MR樣本點(diǎn)，保留室外情況的MR樣本點(diǎn)，并歸為室外數(shù)據(jù)。最終模型輸出為CGI、TA、RSRP、LON、LAT和GRID_SUB_ID。

2）MR信號(hào)聚類預(yù)處理。

為了滿足聚類算法要求，保證數(shù)據(jù)準(zhǔn)確性，需要對(duì)缺失值進(jìn)行處理，應(yīng)當(dāng)考慮以下兩個(gè)準(zhǔn)則：

采集準(zhǔn)則 MR采集過程中，手機(jī)終端上報(bào)測(cè)量主鄰服務(wù)小區(qū)信號(hào)時(shí)，采集信號(hào)主要來自周邊信號(hào)較好的小區(qū)，如果該信號(hào)缺失，可能是由于該CGI信號(hào)較弱，因此可以用已有該CGI電平的均值替代缺失值。

聚類算法分類準(zhǔn)則 缺失值處理最主要的目的就是統(tǒng)一特征，利用聚類算法實(shí)現(xiàn)聚類，所以理論上添加的值與正常的值應(yīng)該存在明顯差異，所以添補(bǔ)值應(yīng)當(dāng)與真實(shí)值存在差異。

具體處理步驟如下：

步驟1 計(jì)算子?xùn)鸥駜?nèi)MR樣本點(diǎn)缺失的CGI、缺失CGI占比和平均電平值_。

表3　w與p的對(duì)應(yīng)關(guān)系

3）MR信號(hào)聚類。

通過對(duì)50 m×50 m的MR柵格中的數(shù)據(jù)觀察，當(dāng)MR柵格中存在建筑物、高架等復(fù)雜環(huán)境時(shí)，MR信號(hào)存在明顯的變化和差異。一般MR指紋庫建庫方法是通過對(duì)柵格內(nèi)的MR數(shù)據(jù)進(jìn)行數(shù)據(jù)匯總統(tǒng)計(jì)，或者對(duì)區(qū)域整體進(jìn)行機(jī)器學(xué)習(xí)算法分析，忽略了MR柵格中主、鄰小區(qū)的信號(hào)強(qiáng)度的差別，從而提取的MR柵格特征容易存在特征失真，導(dǎo)致定位精度不足或者計(jì)算難度較大。為了解決MR柵格中未考慮柵格內(nèi)復(fù)雜環(huán)境導(dǎo)致的特征失真、定位位置單一和不適用于實(shí)際應(yīng)用生產(chǎn)中的問題，本文利用-Means聚類算法對(duì)子?xùn)鸥駜?nèi)的MR信號(hào)進(jìn)行聚類分析。

MR信號(hào)聚類的算法步驟如下：

步驟1 根據(jù)確定子?xùn)鸥駜?nèi)聚類的簇?cái)?shù)。

步驟2 根據(jù)子?xùn)鸥駜?nèi)聚類的簇?cái)?shù)，任選其中個(gè)點(diǎn)作為起始點(diǎn)，分別計(jì)算每行信號(hào)的歐氏距離。令某個(gè)起始點(diǎn)為第行，則有：

步驟3 根據(jù)以上聚類結(jié)果，計(jì)算每個(gè)簇的新的聚類中心。

步驟4 重復(fù)步驟2～3，直至小于指定閾值，停止迭代。

計(jì)算整個(gè)數(shù)據(jù)集的誤差平方和（Sum of Squared Errors，SSE）評(píng)價(jià)聚類效果，則有：

當(dāng)聚類結(jié)果的SSE的變化小于事先設(shè)定閾值時(shí)，迭代停止。

-Means的聚類結(jié)果受參數(shù)的初始設(shè)置影響較大，因此有必要對(duì)-Means聚類結(jié)果進(jìn)行量化評(píng)價(jià)。雖然已有了蘭德指數(shù)、互信息、同質(zhì)化等聚類量化評(píng)價(jià)方法，但是針對(duì)本模型主要是區(qū)分MR柵格內(nèi)的不同區(qū)域的信號(hào)差異，避免特征失真，因此度量標(biāo)準(zhǔn)采用將柵格特征建庫與MR信號(hào)聚類建庫結(jié)果，通過MR測(cè)試數(shù)據(jù)定位方式，對(duì)定位誤差進(jìn)行統(tǒng)計(jì)度量，以此說明MR信號(hào)聚類的方法的建庫有效性。

最終，輸出CGI、TA、RSRP、LON、LAT、GRID_SUB_ID和GROUP_ID。

2.5　MR指紋庫定位和評(píng)估模塊

1）MR指紋庫定位。

MR樣本數(shù)據(jù)中，存在大量數(shù)據(jù)缺失經(jīng)緯度信息，利用MR指紋庫對(duì)該缺失位置的MR數(shù)據(jù)進(jìn)行位置修復(fù)。首先，通過粗匹配方法，取出能夠匹配上主基站CGI和時(shí)間提前量TA的指紋記錄；然后，統(tǒng)計(jì)匹配鄰區(qū)數(shù)量和計(jì)算各個(gè)匹配指紋的信號(hào)強(qiáng)度方差，進(jìn)行排序計(jì)算；最后，取出排名前3的指紋庫記錄所在的虛擬子區(qū)域（子區(qū)域內(nèi)的簇），通過對(duì)3個(gè)聚類中心進(jìn)行加權(quán)計(jì)算，最終輸出最終的MR定位位置。

2）MR指紋庫評(píng)估。

MR樣本數(shù)據(jù)集中，取出包含經(jīng)緯度非建庫MR數(shù)據(jù)，進(jìn)行MR定位，定位結(jié)束后，計(jì)算原坐標(biāo)位置與定位位置之間的距離，從而估算定位誤差，并計(jì)算相關(guān)分析指標(biāo)。

3 實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文實(shí)驗(yàn)數(shù)據(jù)來源于安徽移動(dòng)大數(shù)據(jù)平臺(tái)，MR數(shù)據(jù)由網(wǎng)管平臺(tái)進(jìn)行統(tǒng)一管理，通過周期上報(bào)或者事件觸發(fā)方式使用戶手機(jī)終端上報(bào)MR數(shù)據(jù)，如圖4所示。采集到的MR原始文件為壓縮文件包，通過對(duì)文件的解壓、可擴(kuò)展標(biāo)記語言（eXtensible Markup Language， XML）文件解析等操作，將格式化的MR文件上傳至安徽移動(dòng)大數(shù)據(jù)平臺(tái)，并構(gòu)建以小時(shí)為分區(qū)的Hive表，每15 min解析文件6萬余個(gè)，生成MR數(shù)據(jù)文件約180 GB。

圖4　MR原始數(shù)據(jù)

本文實(shí)驗(yàn)采用安徽移動(dòng)MR數(shù)據(jù)進(jìn)行建模分析，為保障模型的通用性，如圖5所示，在城區(qū)選取了連續(xù)片區(qū)7 km2的范圍（經(jīng)度范圍117.263°E—117.294°E，緯度范圍31.855°N—31.876°N），總柵格數(shù)量2 576。通過3個(gè)月的數(shù)據(jù)采集積累，經(jīng)過數(shù)據(jù)關(guān)聯(lián)、預(yù)處理后共采集MR記錄數(shù)62 401條。本模型按照5∶1劃分訓(xùn)練集和測(cè)試集。為保證每個(gè)柵格中驗(yàn)證集和測(cè)試集的均勻分布，通過柵格ID對(duì)柵格內(nèi)MR數(shù)據(jù)進(jìn)行序列排序，采用6次6折交叉驗(yàn)證，整體評(píng)估定位精度。雖然MR上報(bào)存在隨機(jī)性，可能會(huì)存在柵格內(nèi)樣本點(diǎn)分布不均的情況，但由于模型可根據(jù)子?xùn)鸥駜?nèi)樣本點(diǎn)數(shù)調(diào)整分群數(shù)量，因此對(duì)模型的整體水平影響可忽略。

圖5　測(cè)試區(qū)域

3.2　評(píng)價(jià)指標(biāo)

本文采用位置指紋法中主流的算法——WKNN算法［13］，選取與當(dāng)前MR信號(hào)最鄰近的個(gè)指紋的位置，利用加權(quán)平均的方法估計(jì)當(dāng)前位置，簡(jiǎn)單直觀有效。

因此：

3.3　實(shí)驗(yàn)結(jié)果與分析

由于Spark對(duì)大數(shù)據(jù)處理具有良好的性能，本文使用Hadoop大數(shù)據(jù)平臺(tái)，利用分布式計(jì)算框架Spark完成聚類、MR指紋庫建庫及定位測(cè)試實(shí)驗(yàn)，使用總內(nèi)存64 GB，CPU核心數(shù)4個(gè)，單核線程4個(gè)。

為了測(cè)試-Means分群算法和柵格劃分的大小對(duì)定位精度的影響，本文設(shè)計(jì)了4個(gè)方案構(gòu)建MR指紋庫，并統(tǒng)計(jì)了4個(gè)指紋庫的定位誤差。方案A使用WKNN方法進(jìn)行定位；方案B使用柵格子區(qū)域+WKNN方法進(jìn)行定位；方案C使用-Means分群+WKNN方法進(jìn)行定位；方案D使用柵格子區(qū)域+-Means分群+WKNN方法進(jìn)行定位。

通過6次6折交叉驗(yàn)證法，分別統(tǒng)計(jì)兩種方式下的定位精度，并對(duì)相關(guān)指標(biāo)進(jìn)行了統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如表4所示，平均定位誤差（Average Positioning Error， APE）為重要的衡量指標(biāo)。

表4平均定位誤差統(tǒng)計(jì) 單位：m

Tab.4　Statistics of APE unit：m

實(shí)驗(yàn)結(jié)果表明，方案A使用WKNN的平均定位誤差均值52.33 m，方案D的平均定位誤差均值44.73 m，方案D的平均定位誤差比方案A使用WKNN建庫方法低7.60 m。方案D定位方法定位精度明顯提升。

表5不同方案的誤差結(jié)果分析

Tab.5　Analysis of error results of different schemes

圖6　不同方案的聚類定位結(jié)果比較

表6不同方案的MR定位結(jié)果比較 單位：m

Tab.6　MR positioning results of different schemes unit：m

3.4　定位效率測(cè)試

基于以上單機(jī)總內(nèi)存64 GB，CPU核心數(shù)為4，單核線程數(shù)為4的服務(wù)器通過Spark1.6進(jìn)行定位測(cè)試，多次測(cè)試完成62 401條記錄的時(shí)間約為51 s。

為了充分檢驗(yàn)本文方法的定位效率，利用安徽移動(dòng)大數(shù)據(jù)平臺(tái)（內(nèi)存資源約5 TB，Spark任務(wù)提交執(zhí)行器數(shù)為250，執(zhí)行器內(nèi)存為20 GB，單個(gè)執(zhí)行器核數(shù)為2）連續(xù)測(cè)試7 d的合肥市（每日約15億條）MR數(shù)據(jù)定位效率，如表7所示，完成15億條MR數(shù)據(jù)的平均定位時(shí)間約47.14 min，可以滿足安徽移動(dòng)全省MR定位的業(yè)務(wù)需求。

表7　MR定位效率分析

3.5　實(shí)踐與應(yīng)用

本文方法可以實(shí)現(xiàn)對(duì)人員位置的精準(zhǔn)定位，滿足運(yùn)營(yíng)商對(duì)人員位置、交通流量、弱覆蓋、城市熱力分析等多方面的應(yīng)用要求［22］。該方法當(dāng)前已經(jīng)應(yīng)用于安徽移動(dòng)生產(chǎn)環(huán)境，完成每日百億次定位，精度較高且性能良好，在人員定位、弱覆蓋分析、精準(zhǔn)營(yíng)銷和職住分析等位置類分析應(yīng)用中發(fā)揮了重大作用。如圖7所示，該定位能力可以精準(zhǔn)刻畫用戶軌跡，挖掘用戶通勤線路，實(shí)現(xiàn)對(duì)城市道路交通熱力的評(píng)估。此外，基于MR中的信號(hào)強(qiáng)度、定位位置和GIS信息，可以實(shí)現(xiàn)對(duì)道路、建筑物信號(hào)的分場(chǎng)景評(píng)估，實(shí)現(xiàn)對(duì)城市道路弱覆蓋、樓宇弱覆蓋的分析，從而協(xié)助網(wǎng)優(yōu)部門實(shí)現(xiàn)對(duì)特定場(chǎng)景的無線覆蓋優(yōu)化。最后，基于海量的用戶位置信息，可以分析城市熱力分布，從而為城市規(guī)劃、智慧城市的建設(shè)提供數(shù)據(jù)支撐。

圖7　MR定位應(yīng)用示例

4 結(jié)語

本文提出了基于MR信號(hào)聚類的指紋定位方法。首先，創(chuàng)新性地引入了GIS數(shù)據(jù)，并將MR數(shù)據(jù)點(diǎn)賦予了室內(nèi)、道路、室外的屬性；其次，對(duì)MR數(shù)據(jù)進(jìn)行了有效清洗，將MR數(shù)據(jù)點(diǎn)落入對(duì)應(yīng)屬性的子區(qū)域，通過-Means聚類算法在復(fù)雜的地理環(huán)境下實(shí)現(xiàn)MR柵格信號(hào)特征聚類，從而擴(kuò)充了MR指紋庫定位位置；最后，構(gòu)建MR指紋庫，利用WKNN方法實(shí)現(xiàn)MR指紋定位，通過交叉驗(yàn)證法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，基于MR信號(hào)聚類的指紋定位方法能夠有效地提升MR柵格的定位精度，定位誤差50 m內(nèi)占比71.21%，中值誤差22 m，平均定位誤差44.73 m，并且具備良好的定位性能。MR高精度定位在人員追蹤、交通規(guī)劃和網(wǎng)絡(luò)優(yōu)化等方面發(fā)揮著巨大的作用，隨著5G建設(shè)，5G基站頻率高，覆蓋范圍更小［23］，且4G和5G長(zhǎng)期協(xié)同工作，實(shí)現(xiàn)4G、5G協(xié)同超高精度定位［24-25］將是下一步的研究方向。

[1] DEL PERAL-ROSADO J D， RAULEFS R， LóPEZ-SALCEDO J A， et al. Survey of cellular mobile radio localization methods： from 1G to 5G［J］. IEEE Communications Surveys and Tutorials， 2018， 20（2）：1124-1148.

[2] 武青. 基于指紋庫和無線測(cè)量報(bào)告的用戶定位系統(tǒng)［D］. 北京：北京郵電大學(xué)， 2021：1-2.（WU Q. User localization system based on fingerprint database and measurement report［D］. Beijing： Beijing University of Posts and Telecommunications， 2021：1-2.）

[3] 康軍，黃山，段宗濤，等.時(shí)空軌跡序列模式挖掘方法綜述［J］. 計(jì)算機(jī)應(yīng)用， 2021， 41（8）： 2379-2385.（KANG J， HUANG S， DUAN Z T， et al. Review of spatio-temporal trajectory sequence pattern mining methods［J］. Journal of Computer Applications， 2021， 41（8）： 2379-2385.）

[4] 元廣杰，李小東，江照意，等.路測(cè)數(shù)據(jù)驅(qū)動(dòng)的移動(dòng)終端定位方法［J］. 計(jì)算機(jī)應(yīng)用， 2016， 36（12）： 3515-3520.（YUAN G J， LI X D， JIANG Z Y， et al. Mobile terminal positioning method driven by road test data［J］. Journal of Computer Applications， 2016， 36（12）： 3515-3520.）

[5] 張齊林，李方偉，王明月.基于時(shí)間反演的到達(dá)時(shí)間定位［J］. 計(jì)算機(jī)應(yīng)用， 2021， 41（3）： 820-824.（ZHANG Q L， LI F W， WANG M Y. Time of arrival positioning based on time reversal［J］. Journal of Computer Applications， 2021， 41（3）： 820-824.）

[6] LIU Y， GUO F. Performance analysis of TDOA and FDOA estimation for pulse signals［J］. International Journal of Antennas and Propagation， 2022， 2022： No.7672417.

[7] DíEZ-GONZáLEZ J， áVAREZ R， VERDE P， et al. Analysis of reliable deployment of TDOA local positioning architectures［J］. Neurocomputing， 2022， 484： 149-160.

[8] CHANG A C， CHANG J C. Robust mobile location estimation using hybrid TOA/AOA measurements in cellular systems［J］. Wireless Personal Communications， 2012， 65（1）： 1-13.

[9] LI Y Y， QI G Q， SHENG A D. Performance metric on the best achievable accuracy for hybrid TOA/AOA target localization［J］. IEEE Communications Letters， 2018， 22（7）： 1474-1477.

[10] ZHOU M， LI Y， TAHIR M J， et al. Integrated statistical test of signal distributions and access point contributions for Wi-Fi indoor localization［J］. IEEE Transactions on Vehicular Technology， 2021， 70（5）： 5057-5070.

[11] WANG B， GAN X， LIU X， et al. A novel weighted KNN algorithm based on RSS similarity and position distance for Wi-Fi fingerprint positioning ［J］. IEEE Access， 2020，8： 30591-30602.

[12] VO Q D， DE P. A survey of fingerprint-based outdoor localization［J］. IEEE Communications Surveys and Tutorials， 2016， 18（1）： 491-506.

[13] ZHANG L， CHU X， ZHAI M. Machine learning-based integrated wireless sensing and positioning for cellular network［J］. IEEE Transactions on Instrumentation and Measurement， 2023， 72： No.5501011.

[14] ZHANG Y， RAO W， YUAN M， et al. Context-aware telco outdoor localization ［J］. IEEE Transactions on Mobile Computing， 2022， 21（4）： 1211-1225.

[15] ZHANG Y， DING A Y， OTT J， et al. Transfer learning-based outdoor position recovery with cellular data ［J］. IEEE Transactions on Mobile Computing， 2021， 20（5）： 2094-2110.

[16] 王寧，劉旭峰，賈元啟，等. 基于機(jī)器學(xué)習(xí)的LTE-MR定位算法研究與應(yīng)用范例［J］. 北京交通大學(xué)學(xué)報(bào)， 2021， 45（2）： 87-94， 110.（WANG N，LIU X F， JIA Y Q， et al. Algorithm design and application example of machine learning-based LTE-MR positioning technique ［J］. Journal of Beijing Jiaotong University， 2021， 45（2）： 87-94， 110.）

[17] 周志超，馮毅，夏小涵，等.基于移動(dòng)蜂窩網(wǎng)的機(jī)器學(xué)習(xí)室外指紋定位方案［J］. 電信科學(xué)， 2021， 37（8）： 85-95.（ZHOU Z C， FENG Y， XIA X H， et al. Outdoor location scheme with fingerprinting based on machine learning of mobile cellular network［J］. Telecommunications Science， 2021， 37（8）： 85-95.）

[18] TORIL M， WILLE V， LUNA-RAMíREZ S， et al. Characterization of radio signal strength fluctuations in road scenarios for cellular vehicular network planning in LTE ［J］. IEEE Access， 2021， 9： 33120-33131.

[19] MICHELI D， MURATORE G， VANNELLI A， et al. Rain effect on 4G LTE in-car electromagnetic propagation analyzed through MDT radio data measurement reported by mobile phones［J］. IEEE Transactions on Antennas and Propagation， 2021， 69（12）： 8641-8651.

[20] 中國(guó)通信標(biāo)準(zhǔn)化協(xié)會(huì). TD-LTE數(shù)字蜂窩移動(dòng)通信網(wǎng)無線操作維護(hù)中心（OMC-R）測(cè)量報(bào)告技術(shù)要求： YD/T 2824—2015［S］. 北京：中國(guó)標(biāo)準(zhǔn)出版社， 2015：7-8.（China Communications Standards Association. TD-LTE digital cell mobile communications network OMC-R measurement report technical specification： YD/T 2824—2015 ［S］. Beijing： Standards Press of China， 2015：7-8.）

[21] 科大國(guó)創(chuàng)軟件股份有限公司. 一種基于GIS數(shù)據(jù)進(jìn)行柵格子區(qū)域劃分的方法及裝置： 201811625700.4［P］. 2019-05-17.（GuoChuang Cloud Technology Company Limited. A method and equipment for dividing grid areas based on GIS data set： 201811625700.4 ［P］. 2019-05-17.）

[22] 劉大有，陳慧靈，齊紅，等.時(shí)空數(shù)據(jù)挖掘研究進(jìn)展［J］. 計(jì)算機(jī)研究與發(fā)展， 2013， 50（2）： 225-239.（LIU D Y， CHEN H L， QI H， et al. Advances in spatiotemporal data mining［J］. Journal of Computer Research and Development， 2013， 50（2）： 225-239.）

[23] 張平，陳昊.面向5G的定位技術(shù)研究綜述［J］. 北京郵電大學(xué)學(xué)報(bào)， 2018， 41（5）： 1-12.（ZHANG P， CHEN H. A survey of positioning technology for 5G ［J］. Journal of Beijing University of Posts and Telecommunications， 2018， 41（5）： 1-12.）

[24] DWIVEDI S， SHREEVASTAV R， MUNIER F， et al. Positioning in 5G networks［J］. IEEE Communications Magazine， 2021， 59（11）： 38-44.

[25] KANHERE O， RAPPAPORT T S. Position location for futuristic cellular communications： 5G and beyond［J］. IEEE Communications Magazine， 2021， 59（1）： 70-75.

Fingerprint positioning method based on measurement report signal clustering

ZHANG Haiyong1，2， FANG Xianjin1*， ZHANG Enwan3， LI Baoyu2， PENG Chao4， MU Jianxiang2

（1，，232001，；2，230088，；3，230088，；4，，230037，）

Aiming at the problems of low positioning precision and efficiency of fingerprint positioning methods based on Weighted-Nearest Neighbor （WKNN） and machine learning algorithms， a fingerprint positioning method based on Measurement Report （MR） signal clustering was proposed. Firstly， MR signals were divided into three attributes： indoor， road and outdoor. Then， by using the Geographic Information System （GIS） information， the grids were divided into building， road and outdoor sub-regions， and MR data with different attributes were placed in the sub-regions with corresponding attributes. Finally， with the help of-Means clustering algorithm， MR signals in the grid were clustered and analyzed to create virtual sub-regions under the sub-region， and WKNN algorithm was used to match MR test samples. Besides， the average positioning accuracy was calculated by using the Euclidean distance， and the positioning performance of the proposed method was tested by some MR data in the production environment. Experimental results show that the proportion of 50 m positioning error of the proposed method is 71.21%， which is 2.64 percentage points higher than that of WKNN algorithm， and the average positioning error of the proposed method is 44.73 m， which is 7.60 m lower than that of WKNN algorithm. It can be seen that the proposed method has good positioning precision and efficiency， and can meet the positioning requirements of MR data in the production environment.

Measurement Report (MR); positioning; signal clustering; Weighted K-Nearest Neighbor (WKNN) algorithm; Euclidean distance

This work is partially supported by Anhui University of Science and Technology Innovation Fund （2022CX2129）， Research and Development Special Fund of Institute of Environment-friendly Materials and Occupational Health （Wuhu） of Anhui University of Science and Technology （ALW2021YF08）.

ZHANG Haiyong， born in 1992， M. S. candidate. His research interests include operator big data， machine learning.

FANG Xianjin， born in 1970， Ph. D.， professor. His research interests include privacy protection， artificial intelligence security.

ZHANG Enwan， born in 1982， M. S. His research interests include artificial intelligence， operator big data.

LI Baoyu， born in 1982， M. S. His research interests include artificial intelligence， operator big data.

PENG Chao， born in 1994， M. S. His research interests include complex network， artificial intelligence.

MU Jianxiang， born in 1993. His research interests include operator big data.

TP391.9

A

1001-9081（2023）12-3947-08

10.11772/j.issn.1001-9081.2023010005

2023?01?04；

2023?04?23；

2023?04?24。

安徽理工大學(xué)創(chuàng)新基金資助項(xiàng)目（2022CX2129）；安徽理工大學(xué)環(huán)境友好材料與職業(yè)健康研究院（蕪湖）研發(fā)專項(xiàng)基金資助項(xiàng)目（ALW2021YF08）。

張海永（1992—），男，安徽合肥人，碩士研究生，主要研究方向：運(yùn)營(yíng)商大數(shù)據(jù)、機(jī)器學(xué)習(xí)；方賢進(jìn)（1970—），男，安徽六安人，教授，博士生導(dǎo)師，博士，高級(jí)CCF會(huì)員，主要研究方向：隱私保護(hù)、人工智能安全；張恩皖（1982—），男，安徽合肥人，碩士，主要研究方向：人工智能、運(yùn)營(yíng)商大數(shù)據(jù)；李寶玉（1982—），男，安徽安慶人，碩士，主要研究方向：人工智能、運(yùn)營(yíng)商大數(shù)據(jù)；彭超（1994—），男，安徽合肥人，碩士，主要研究方向：復(fù)雜網(wǎng)絡(luò)、人工智能；穆健翔（1993—），男，安徽阜陽人，主要研究方向：運(yùn)營(yíng)商大數(shù)據(jù)。