丁承君 宇中強 朱志輝

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

關鍵詞： 信號幅值; 指紋定位; 概率分布; K?means; KNN分類算法; WiFi信號

中圖分類號： TN911?34; TP393 ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 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 ?引 ?言

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

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

1 ?WiFi指紋定位技術

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

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

1.1 ?指紋定位技術分析

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

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

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

進一步梳理采集到的數(shù)據(jù)，發(fā)現(xiàn)雙峰出現(xiàn)的并非小概率事件，如表1所示，呈現(xiàn)雙峰所占比例為20%～40%?？梢姡瑢τ谑覂葟碗s環(huán)境這一分布特性應引起重視。

上面這些數(shù)據(jù)都是構成指紋庫的必要準備。當然，采集更多的數(shù)據(jù)，指紋庫必然更準確，然而這也會加大系統(tǒng)的運算量。

2 ?聚類與指紋庫的構建

指紋庫是指紋定位方法的標尺，指紋庫的準確性會直接影響最終定位結果的精度。

在離線數(shù)據(jù)采集階段，采集每個采樣點的位置坐標，同時在該坐標處采集接收到的RSS信號，將每個AP的坐標和RSS值按照一定的格式存儲在指紋數(shù)據(jù)庫中。

2.1 ?指紋框架的建立

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

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

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

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

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

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

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

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

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

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

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

4 ?實驗及分析

本文以教室、實驗樓、辦公室、商場四個不同場景為實驗場景，進行室內定位研究。以實驗樓二樓為典型的例子：長23 m、寬13 m的地方，有復雜的拐角、許多實驗室的門與窗;實驗樓有11個固定常開的WiFi信號分布在約[300 m2]的空間內;因為有拐角等復雜地形，分為90個方形區(qū)域，每個區(qū)域為2 m×2 m，靠墻和樓梯口略有減小。在離線訓練階段，每個AP采取1 000個樣本訓練指紋庫，每個采樣點的采樣頻率為1。實驗結果結果如表2所示。

由表3可知，在4 m范圍精度達到89.7%，3 m精度達到76.3%，5 m精度達到93.3%。在實驗中，該方法的平均誤差為4.83 m。

5 ?結 ?語

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

參考文獻

[1] 周傲英，楊彬，金澈清，等.基于位置的服務：架構與進展[J].計算機學報，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] 席瑞，李玉軍，侯孟書.室內定位方法綜述[J].計算機科學，2016，43（4）：1?6.

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

[3] 陸音，繆輝輝.復雜室內環(huán)境下的WiFi定位技術研究[J].計算機科學，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] 江春冬，惠慧，陳云飛，等.與強度無關的位置指紋在線定位改進算法[J].電訊技術，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] 蔡朝暉，夏溪，胡波，等.室內信號強度指紋定位算法改進[J].計算機科學，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] 周瑞.應用室內結構布局提高WiFi定位精度和穩(wěn)定性[J].電子科技大學學報，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].計算機應用與軟件，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的指紋匹配算法在室內定位中的應用研究[J].計算機科學，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)營，成長生.基于聚類分析局部離群點挖掘改進算法的研究與實現(xiàn)[J].計算機應用與軟件，2010，27（11）：255?258.

（上接第42頁）

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)絡入侵檢測算法[J].計算機科學，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] 劉春燕，王堅.基于幾何聚類指紋庫的約束KNN室內定位模型[J].武漢大學學報（信息科學版），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.