基于信號(hào)幅值分布的室內(nèi)指紋定位算法

丁承君 宇中強(qiáng) 朱志輝

摘 ?要： 室內(nèi)定位算法是基于位置服務(wù)領(lǐng)域研究的難點(diǎn)之一。針對(duì)室內(nèi)定位應(yīng)用場(chǎng)合和精度問(wèn)題，提出了利用K?means和KNN融合算法對(duì)覆蓋率廣的WiFi信號(hào)進(jìn)行指紋定位。WiFi指紋定位主要問(wèn)題是前期指紋庫(kù)數(shù)據(jù)的精確以及后期數(shù)據(jù)的匹配效果。首先，對(duì)WiFi信號(hào)的概率分布進(jìn)行研究，彌補(bǔ)了一直以來(lái)由于K?means是無(wú)監(jiān)督學(xué)習(xí)帶來(lái)的k值的難以選取的缺陷，提高了指紋庫(kù)的精確性，同時(shí)確保數(shù)據(jù)實(shí)時(shí)性。后期在線數(shù)據(jù)處理利用KNN分類算法進(jìn)行后期在線定位過(guò)程的準(zhǔn)確性。經(jīng)多個(gè)實(shí)驗(yàn)場(chǎng)景測(cè)試結(jié)果表明，該算法在室內(nèi)定位精度上3 m定位精度概率保持在78.4%，4 m精度保持在93.6%，基本上保證了室內(nèi)定位精度的要求。

關(guān)鍵詞： 信號(hào)幅值; 指紋定位; 概率分布; K?means; KNN分類算法; WiFi信號(hào)

中圖分類號(hào)： TN911?34; TP393 ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2018）10?0039?04

Abstract： Indoor positioning algorithm is one of difficulties in location?based service field research. In allusion to the application scene and precision problems of indoor positioning， the view that using the K?means and KNN fusion algorithm to perform fingerprint positioning for wide?coverage WiFi signals is proposed. The main problems of WiFi fingerprint positioning lie in the data accuracy of the front?stage fingerprint database and the matching effect of late?stage data. The probability distribution of WiFi signals is studied to make up the defect that it is difficult to select the k value as K?means is an unsupervised learning for a long time， which can improve the accuracy of the fingerprint database， and meanwhile ensure the real?time performance of data. During the process of late?stage online data processing， the KNN classification algorithm is adopted to obtain the accuracy of the late?stage online positioning. The algorithm was tested in multiple experimental scenes. The results show that the 3 m positioning accuracy probability of the algorithm remains 78.4% in indoor positioning accuracy， and the 4 m positioning accuracy probability remains 93.6%， which can basically ensure the accuracy requirement of indoor positioning.

Keywords： signal amplitude; fingerprint positioning; probability distribution; K?means; KNN classification algorithm; WiFi signal

0 ?引 ?言

基于位置服務(wù)（Location Based Services，LBS）的其中一項(xiàng)內(nèi)容是室內(nèi)定位。由于室內(nèi)布局和臨時(shí)遮擋物的因素會(huì)造成信號(hào)不穩(wěn)定，所以對(duì)于定位精度，室內(nèi)定位較之于室外定位難度大[1]。現(xiàn)階段國(guó)內(nèi)外基于室內(nèi)定位采取的技術(shù)手段中WiFi為最佳選擇[2]。原因是成本低、覆蓋范圍廣、精度高，用戶的移動(dòng)接收設(shè)備可直接用于定位，已覆蓋WiFi的室內(nèi)場(chǎng)所無(wú)需鋪設(shè)其他硬件設(shè)備，可移植擴(kuò)展[3]。定位方法有兩種：一種是基于無(wú)線信號(hào)強(qiáng)度傳播模型，將信號(hào)的幅值與距離進(jìn)行公式化建模，例如經(jīng)典的對(duì)數(shù)距離模型[4]，然而在室內(nèi)遮擋物較多且容易移動(dòng)，模型會(huì)因無(wú)線信號(hào)受遮擋物影響衰減而變得不準(zhǔn)確;另一種是基于位置?指紋進(jìn)行定位。相比較來(lái)說(shuō)，指紋定位會(huì)有更好的表現(xiàn)[5]。

本文重點(diǎn)分析了WiFi信號(hào)的概率分布，并獲得了WiFi信號(hào)幅值的概率分布情況。使用K?means聯(lián)合KNN算法，在提高了指紋庫(kù)的準(zhǔn)確性的同時(shí)，減少了計(jì)算量，增加了定位精度和穩(wěn)定性[6]。通過(guò)辦公室、實(shí)驗(yàn)樓、家庭住宅等多個(gè)平面場(chǎng)所進(jìn)行的實(shí)際測(cè)試得出定位精度提高到1～2 m范圍內(nèi)。

1 ?WiFi指紋定位技術(shù)

WiFi定位指紋分為兩個(gè)階段：離線訓(xùn)練數(shù)據(jù)庫(kù)階段和在線定位階段。離線訓(xùn)練是作者采集并處理信號(hào)，構(gòu)建指紋數(shù)據(jù)庫(kù)。在線定位階段，是將檢測(cè)到的WiFi強(qiáng)度值用匹配算法與指紋庫(kù)里的數(shù)據(jù)進(jìn)行在線匹配，得到最佳定位值。圖1為指紋算法的流程圖。

離線采集階段：在坐標(biāo)點(diǎn)采集WiFi幅值后，先進(jìn)行預(yù)處理，目的是精確指紋庫(kù)并且減少計(jì)算量;而后進(jìn)行K?means聚類并入庫(kù);在線定位階段通過(guò)后期采集的數(shù)據(jù)與指紋庫(kù)數(shù)據(jù)進(jìn)行KNN算法，加權(quán)求和后，得到定位位置。指紋庫(kù)的準(zhǔn)確性和在線匹配的穩(wěn)定性是保證最終定位結(jié)果精度的關(guān)鍵，這也是本文所要重點(diǎn)研究的內(nèi)容。

1.1 ?指紋定位技術(shù)分析

指紋定位技術(shù)可以分為兩類：確定性技術(shù)和概率技術(shù)。確定性技術(shù)，例如KNN，KWNN，它們是對(duì)采樣信號(hào)相關(guān)的k個(gè)近似值求均值或權(quán)值來(lái)定位[7]。概率技術(shù)在研究信號(hào)強(qiáng)度分布特性之后，進(jìn)行最大似然估計(jì)。國(guó)外專家學(xué)者已經(jīng)證明概率方法有更高的精度。但是不同的試驗(yàn)場(chǎng)景存在復(fù)雜性，WiFi信號(hào)強(qiáng)度分布在一些測(cè)試點(diǎn)會(huì)與標(biāo)準(zhǔn)高斯分布表現(xiàn)不同，其結(jié)果的準(zhǔn)確性會(huì)影響概率方法的模型建立和參數(shù)的準(zhǔn)確性。所以，本文依舊選用KNN算法。為了彌補(bǔ)使用KNN算法帶來(lái)的精度損失，研究了WiFi信號(hào)的分布規(guī)律來(lái)增強(qiáng)前期指紋庫(kù)的準(zhǔn)確性。

1.2 ?WiFi信號(hào)的分布規(guī)律

WiFi幅值理論上服從高斯分布，具有一個(gè)波峰。但在實(shí)際探究固定位置采集單個(gè)信號(hào)分布情況，其幅值會(huì)在一定閾值內(nèi)上下波動(dòng)。筆者在一個(gè)月之內(nèi)連續(xù)對(duì)上述三個(gè)場(chǎng)景內(nèi)的多個(gè)WiFi信號(hào)進(jìn)行長(zhǎng)時(shí)間數(shù)據(jù)采集、歸總，發(fā)現(xiàn)WiFi信號(hào)幅值發(fā)生的概率呈現(xiàn)單峰值或雙峰值兩種。圖2為WiFi信號(hào)單峰值與雙峰值顯示。

進(jìn)一步梳理采集到的數(shù)據(jù)，發(fā)現(xiàn)雙峰出現(xiàn)的并非小概率事件，如表1所示，呈現(xiàn)雙峰所占比例為20%～40%?？梢?，對(duì)于室內(nèi)復(fù)雜環(huán)境這一分布特性應(yīng)引起重視。

上面這些數(shù)據(jù)都是構(gòu)成指紋庫(kù)的必要準(zhǔn)備。當(dāng)然，采集更多的數(shù)據(jù)，指紋庫(kù)必然更準(zhǔn)確，然而這也會(huì)加大系統(tǒng)的運(yùn)算量。

2 ?聚類與指紋庫(kù)的構(gòu)建

指紋庫(kù)是指紋定位方法的標(biāo)尺，指紋庫(kù)的準(zhǔn)確性會(huì)直接影響最終定位結(jié)果的精度。

在離線數(shù)據(jù)采集階段，采集每個(gè)采樣點(diǎn)的位置坐標(biāo)，同時(shí)在該坐標(biāo)處采集接收到的RSS信號(hào)，將每個(gè)AP的坐標(biāo)和RSS值按照一定的格式存儲(chǔ)在指紋數(shù)據(jù)庫(kù)中。

2.1 ?指紋框架的建立

離線數(shù)據(jù)庫(kù)階段，在采集點(diǎn)用一定的方法采集AP坐標(biāo)和RSS信號(hào)，并綁定一起存儲(chǔ)在指紋數(shù)據(jù)庫(kù)里。假設(shè)第i次采集到的數(shù)據(jù)用集合[Mi]表示，則定義[8]：

2.3 ?生成指紋數(shù)據(jù)庫(kù)的方法

預(yù)處理和K?means是兩項(xiàng)高度相關(guān)的工作。預(yù)處理試圖刪除那些顯著偏離多數(shù)的異常情況，而聚類則是發(fā)現(xiàn)集中數(shù)據(jù)并據(jù)此入庫(kù)。

經(jīng)過(guò)預(yù)處理，留下的數(shù)據(jù)具有一定的可信度。接著需要提取數(shù)據(jù)集的最佳參考值。在此采用聚類方法K?means，它是與某種規(guī)則進(jìn)行聚類，分成k組，把相似度數(shù)據(jù)分到一組，分別提取最佳值[10]。

主要過(guò)程如下：樣本有N個(gè)數(shù)據(jù)點(diǎn)，需要預(yù)知該樣本的聚類中心有K個(gè)，選取k個(gè)采樣點(diǎn)數(shù)據(jù)作為作為聚類中心，其余（N-K）個(gè)數(shù)據(jù)依照曼哈頓距離歸為最相似的簇，重新計(jì)算這k個(gè)平均值，再把其余（N-K）個(gè)數(shù)據(jù)重新歸位，計(jì)算均值。直到最后k個(gè)中心值保持在一定閾值之內(nèi)，即該簇內(nèi)的其他值距該中心點(diǎn)的曼哈頓距離收斂到最小值，如下所示：

使用K?means的難點(diǎn)是分類之前并不知需要分成幾類。之前章節(jié)實(shí)驗(yàn)數(shù)據(jù)說(shuō)明的信號(hào)幅值分布為單峰值或是雙峰值，放到這里可解決k值的選取為1或2的問(wèn)題。為了保證兩種k值的情況，將預(yù)處理后的數(shù)據(jù)，先以k=2進(jìn)行K?means聚類，若得到兩個(gè)結(jié)果幅值差大于2，則說(shuō)明該數(shù)據(jù)為雙峰值，保留這兩個(gè)數(shù)值入庫(kù);反之，若幅值差小于等于2，重新再以k=1進(jìn)行聚類。對(duì)于雙峰值來(lái)說(shuō)，把概率較高值稱為主幅值，即[RSSImain]，則另一個(gè)峰值副幅值表示為[RSSImain+Δ]。其中[Δ]=副幅值-主幅值。

對(duì)于入庫(kù)，單峰值聚類結(jié)果直接寫入即可。對(duì)于雙峰值，為了區(qū)別于單峰值，表示為主幅值加差值[Δ]：[RSSI=RSSImain+Δ]。

3 ?后期在線定位方法（KNN結(jié)合概率）

后期定位方法采用KNN。區(qū)別于K?means，它是一種已知指紋庫(kù)數(shù)據(jù)的分類方法。其是把新的樣本數(shù)據(jù)與已知庫(kù)數(shù)據(jù)進(jìn)行比對(duì)，尋找k個(gè)最相似數(shù)據(jù)，再對(duì)k個(gè)數(shù)據(jù)進(jìn)行分類處理。同樣，會(huì)遇到k值的選取問(wèn)題。對(duì)于k值的選取，可以有以下幾個(gè)備選值[11]。

由于開始將二維空間進(jìn)行矩形劃分，若定位到一點(diǎn)，周圍會(huì)有相鄰8個(gè)區(qū)域，把k設(shè)為8。還可以簡(jiǎn)化運(yùn)算，設(shè)k=4。此外k=1時(shí)，選取歐氏距離相距最近的坐標(biāo)。對(duì)于k=4，k=8這兩種情況，分別選出距離最近的4組、8組數(shù)據(jù)。然而每組數(shù)據(jù)的距離不同，距離遠(yuǎn)，數(shù)據(jù)說(shuō)明能力弱;反之則強(qiáng)。所以，采取距離倒數(shù)方法，分別作為其坐標(biāo)的權(quán)值，再進(jìn)行單位化歸一，最后把幾組值代入權(quán)值歐拉公式，得到最終定位結(jié)果。分別對(duì)k=1，k=4，k=8在選取的100個(gè)參考點(diǎn)進(jìn)行試驗(yàn)，定位結(jié)果與指紋數(shù)據(jù)庫(kù)值比對(duì)算出直線誤差，求取平均值數(shù)據(jù)如下：k=1時(shí)，平均直線誤差為5.28 m;k=4時(shí)，平均直線誤差為4.42 m;k=8時(shí)，平均直線誤差為4.63 m。

經(jīng)分析如下：k=1時(shí)，定位結(jié)果的直線誤差大于其他其余兩個(gè);k=4和k=8的定位誤差相近，但由于k=8的計(jì)算量明顯大過(guò)k=4。所以，對(duì)于本文KNN算法，選取k=4為最佳值。

4 ?實(shí)驗(yàn)及分析

本文以教室、實(shí)驗(yàn)樓、辦公室、商場(chǎng)四個(gè)不同場(chǎng)景為實(shí)驗(yàn)場(chǎng)景，進(jìn)行室內(nèi)定位研究。以實(shí)驗(yàn)樓二樓為典型的例子：長(zhǎng)23 m、寬13 m的地方，有復(fù)雜的拐角、許多實(shí)驗(yàn)室的門與窗;實(shí)驗(yàn)樓有11個(gè)固定常開的WiFi信號(hào)分布在約[300 m2]的空間內(nèi);因?yàn)橛泄战堑葟?fù)雜地形，分為90個(gè)方形區(qū)域，每個(gè)區(qū)域?yàn)? m×2 m，靠墻和樓梯口略有減小。在離線訓(xùn)練階段，每個(gè)AP采取1 000個(gè)樣本訓(xùn)練指紋庫(kù)，每個(gè)采樣點(diǎn)的采樣頻率為1。實(shí)驗(yàn)結(jié)果結(jié)果如表2所示。

由表3可知，在4 m范圍精度達(dá)到89.7%，3 m精度達(dá)到76.3%，5 m精度達(dá)到93.3%。在實(shí)驗(yàn)中，該方法的平均誤差為4.83 m。

5 ?結(jié) ?語(yǔ)

室內(nèi)定位中，在研究過(guò)WiFi分布規(guī)律后，去掉離群點(diǎn)數(shù)據(jù)，增強(qiáng)數(shù)據(jù)可靠性的同時(shí)，降低了數(shù)據(jù)量。結(jié)合K?means聚類算法構(gòu)建指紋庫(kù)、KNN后期定位算法，降低整體指紋算法的計(jì)算量，提高了系統(tǒng)實(shí)時(shí)性。在四個(gè)真實(shí)場(chǎng)景進(jìn)行大量數(shù)據(jù)測(cè)試，分析了該算法的定位效果，數(shù)據(jù)結(jié)果表明，定位精度可以提高到4～5 m。

參考文獻(xiàn)

[1] 周傲英，楊彬，金澈清，等.基于位置的服務(wù)：架構(gòu)與進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（7）：1155?1171.

ZHOU Aoying， YANG Bin， JIN Cheqing， et al. Location?based services： architecture and progress [J]. Chinese journal of computers， 2011， 34（7）： 1155?1171.

[2] 席瑞，李玉軍，侯孟書.室內(nèi)定位方法綜述[J].計(jì)算機(jī)科學(xué)，2016，43（4）：1?6.

XI Rui， LI Yujun， HOU Mengshu. Survey on indoor localization [J]. Computer science， 2016， 43（4）： 1?6.

[3] 陸音，繆輝輝.復(fù)雜室內(nèi)環(huán)境下的WiFi定位技術(shù)研究[J].計(jì)算機(jī)科學(xué)，2016，43（11）：152?154.

LU Yin， MIAO Huihui. Study on WiFi location technology under complex indoor environment [J]. Computer science， 2016， 43（11）： 152?154.

[4] 江春冬，惠慧，陳云飛，等.與強(qiáng)度無(wú)關(guān)的位置指紋在線定位改進(jìn)算法[J].電訊技術(shù)，2016，56（2）：128?134.

JIANG Chundong， HUI Hui， CHEN Yunfei， et al. An improved online position fingerprint algorithm for strength?independent interference source location [J]. Telecommunication engineering， 2016， 56（2）： 128?134.

[5] 蔡朝暉，夏溪，胡波，等.室內(nèi)信號(hào)強(qiáng)度指紋定位算法改進(jìn)[J].計(jì)算機(jī)科學(xué)，2014，41（11）：178?181.

CAI Zhaohui， XIA Xi， HU Bo， et al. Improvements of indoor signal strength fingerprint location algorithm [J]. Computer science， 2014， 41（11）： 178?181.

[6] 周瑞.應(yīng)用室內(nèi)結(jié)構(gòu)布局提高WiFi定位精度和穩(wěn)定性[J].電子科技大學(xué)學(xué)報(bào)，2013，42（2）：295?299.

ZHOU Rui. Improve the accuracy and stability of WiFi fingerprinting by applying the interior structure of buildings [J]. Journal of University of Electronic Science and Technology of China， 2013， 42（2）： 295?299.

[7] 趙宇，周文剛.基于智能手機(jī)的室內(nèi)定位[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32（6）：91?93.

ZHAO Yu， ZHOU Wengang. Indoor localisation based on smartphone [J]. Computer applications and software， 2015， 32（6）： 91?93.

[8] 唐洋，白勇，馬躍，等.基于WiFi的指紋匹配算法在室內(nèi)定位中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，2016，43（5）：73?75.

TANG Yang， BAI Yong， MA Yue， et al. Research of WiFi?based fingerprinting matching algorithm in indoor positioning [J]. Computer science， 2016， 43（5）： 73?75.

[9] 趙戰(zhàn)營(yíng)，成長(zhǎng)生.基于聚類分析局部離群點(diǎn)挖掘改進(jìn)算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（11）：255?258.

（上接第42頁(yè)）

ZHAO Zhanying， CHENG Changsheng. On improved algorithm for local outlier mining based on cluster analysis and its implementation [J]. Computer applications and software， 2010， 27（11）： 255?258.

[10] 華輝有，陳啟買，劉海，等.一種融合K?means和KNN的網(wǎng)絡(luò)入侵檢測(cè)算法[J].計(jì)算機(jī)科學(xué)，2016，43（3）：158?162.

HUA Huiyou， CHEN Qimai， LIU Hai， et al. Hybrid K?means with KNN for network intrusion detection algorithm [J]. Computer science， 2016， 43（3）： 158?162.

[11] 劉春燕，王堅(jiān).基于幾何聚類指紋庫(kù)的約束KNN室內(nèi)定位模型[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2014，39（11）：1287?1292.

LIU Chunyan， WANG Jian. A constrained KNN indoor positioning model based on a geometric clustering fingerprinting technique [J]. Geomatics and information science of Wuhan University， 2014， 39（11）： 1287?1292.