基于奇異值檢測和AP聚類的室內(nèi)指紋定位算法

蔣亞虎

（廣東松山職業(yè)技術(shù)學(xué)院 計算機系，廣東 韶關(guān)512126）

0 引 言

如何利用無線局域網(wǎng)的基礎(chǔ)設(shè)施完成室內(nèi)定位，是室內(nèi)定位技術(shù)的熱點問題。基于接收信號強度的無線局域網(wǎng)指紋定位技術(shù)是無線局域網(wǎng)定位算法中具有較好效果的定位方法［1，2］。很多研究者對無線局域網(wǎng)指紋定位算法進(jìn)行了深入研究，文獻(xiàn) ［3］提出了基于閾值分類及信號加權(quán)的室內(nèi)定位算法，文獻(xiàn) ［4］提出了基于物理鄰近點輔助的指紋定位算法，體現(xiàn)了物理地形與位置指紋之間的關(guān)聯(lián)性，能夠得到精度較高的算法。

1 接收信號強度值指紋定位算法

RSSI指紋定位算法有兩個步驟：

（2）在線定位：移動節(jié)點運動到某位置時可將該位置接收到的各無線節(jié)點強度記錄下來，并發(fā)送到上位機，上位機將該數(shù)據(jù)與離線訓(xùn)練系統(tǒng)得到的數(shù)據(jù)庫信號指紋匹配，通過對比，信號強度最匹配所對應(yīng)的位置即是移動節(jié)點的位置。其中匹配算法的優(yōu)劣直接關(guān)系到定位算法的準(zhǔn)確性［6］。

2 奇異值檢測

無線局域網(wǎng)指紋定位算法離線階段采集各節(jié)點數(shù)據(jù)時，由于存在多徑干擾等因素影響，一個參考點接收來自某無線節(jié)點的信號強度值會出現(xiàn)不同程度的抖動，嚴(yán)重的抖動會對該位置的RSSI均值和標(biāo)準(zhǔn)差引起較大變化，降低定位性能，所以有效去除信號強度抖動可以提高離線訓(xùn)練系統(tǒng)性能，本文融合了Hampel濾波器與核密度估計，提出了一種奇異值檢測方法。

2.1 Hampel濾波器

Hampel濾波器與3σ準(zhǔn)則相似，3σ準(zhǔn)則通過數(shù)據(jù)集合中的均值和標(biāo)準(zhǔn)差，確定某數(shù)據(jù)為正常數(shù)據(jù)還是可以數(shù)據(jù)，但是由于奇異值對均值和標(biāo)準(zhǔn)差的影響較大，這種效應(yīng)會影響3σ準(zhǔn)則的判斷效果［7］。Hampel濾波器與3σ準(zhǔn)則具有類似的規(guī)則，但是判斷數(shù)據(jù)集中數(shù)據(jù)是否為奇異值不再依賴均值和標(biāo)準(zhǔn)差，而是中值和偏離中值絕對值的中值 （median absolute deviate from median，MAD）。對于數(shù)據(jù)集合P ＝｛pi｝，median（P）表示中值，MAD 用R 表示，R 計算公式如下

中值和MAD 值計算簡單，適用與無線節(jié)點網(wǎng)絡(luò)。Hampel濾波器的弊端是，當(dāng)數(shù)據(jù)集中大多數(shù)數(shù)據(jù)相等時，MAD 值為0，這樣導(dǎo)致所有數(shù)據(jù)均被判斷為奇異值。

2.2 核密度估計

核密度估計可以用來評估數(shù)據(jù)集的分布，核密度估計是評估隨機變量概率密度函數(shù)的方法，其估算量f∧（p）定義如下［8］

式中：［P］——數(shù)據(jù)集合P 的個數(shù)，pi——數(shù)據(jù)集合中的一個采樣，其分布可通過核函數(shù)來評估，不同的核函數(shù)對評估性能影響不大，Epanechnikov核函數(shù)具有較優(yōu)的最小方差感知效果，其計算公式如下

2.3 一種奇異值檢測算法

KDE算法與Hampel濾波器在評估效果方面有互補作用，KDE算法可以克服Hampel濾波器的不足，Hampel濾波器也可以在奇異值造成核密度過高時正確識別奇異值。本文將KDE算法與Hampel濾波器結(jié)合起來，給出了奇異值檢測算法，算法步驟如圖1所示。

圖1 奇異值檢測算法流程

定義MAD 規(guī)模分變量，該變量由Hampel濾波器中的R 引申，MAD 規(guī)模分計算如下

MAD 規(guī)模分是數(shù)據(jù)集樣本偏離中值的程度，將Hampel濾波器與KDE概率密度估計聯(lián)合起來可得到可信度ci

prob（pi）由核密度計算得到。當(dāng)概率密度較大、MAD規(guī)模分較低，可信指標(biāo)值較高，數(shù)據(jù)可信，當(dāng)概率密度較小、MAD規(guī)模分較高，可信指標(biāo)較低，數(shù)據(jù)不可信。在指紋定位算法離線訓(xùn)練階段，設(shè)定某閾值，對上式計算得到的可信度進(jìn)行檢測，小于門限值的接收點信號強度視為奇異值剔除。

3 AP聚類算法

無線局域網(wǎng)指紋定位算法中，隨著定位區(qū)域的擴大，離線訓(xùn)練系統(tǒng)中的數(shù)據(jù)量也變得越來越大，后期在線定位系統(tǒng)需要參與運算的數(shù)據(jù)就增多，為了克服這一問題，減少不相干的數(shù)據(jù)，可以用AP 聚類算法將目標(biāo)區(qū)域劃分為多個小區(qū)域，縮小定位計算復(fù)雜度。

AP聚類根據(jù)數(shù)據(jù)之間的相似度分類，這些相似度構(gòu)成了相似度矩陣S，并且每個元素都添加負(fù)號成為負(fù)數(shù)，計算公式如下［9］

AP聚類不需要事先制定聚類數(shù)目，所有數(shù)據(jù)都是潛在的聚類中心，相似度矩陣對角線上的值s（k，k）是k作為聚類中心的判斷標(biāo)準(zhǔn)，值越大，可能性越大，該值也稱為參考度p。AP聚類算法中體現(xiàn)兩種信息，吸引度信息和歸屬度信息［10］。吸引度反映了j點是否可作為i 點的聚類中心，計算方法如下

a（i，j）是歸屬度，反映了i是否選擇j 作為聚類中心

自歸屬度a（j，j）反映的是點j作為聚類中心的證據(jù)，計算方法如下

a （j，j）越大，j作為聚類中心的可能性越大，a（i，j）＋r（i，j）值最大的j點就是i 的聚類中心，聚類算法循環(huán)迭代每個點的歸屬度和吸引度

λ是阻尼因子，0＜λ＜1，研究表明，λ＝0.65時所需計算成本最小，聚類中心連續(xù)迭代10次而未發(fā)生變化或者迭代次數(shù)為100次時，可認(rèn)為迭代完成。

4 基于AP聚類的粗定位與細(xì)定位

隨著無線局域網(wǎng)定位區(qū)域的增大，定位算法變得更為復(fù)雜，AP聚類算法可以簡化計算復(fù)雜度，消除誤差，本文利用在線測量的RSSI與AP 聚類中心點的RSSI向量之間的相似度進(jìn)行粗定位。

4.1 基于AP聚類的粗定位

在線移動端接收到的RSSI向量數(shù)據(jù)傳輸?shù)椒?wù)器，服務(wù)器計算該向量與數(shù)據(jù)庫各類中心點向量之間的相似度，據(jù)此，判斷數(shù)據(jù)屬于哪個類，在算法實際運行過程中，可能會出現(xiàn)移動終端與兩個或多個類相似度接近，這時如果將移動終端劃分到其中某個類可能會導(dǎo)致不準(zhǔn)確的判斷，因此需要選擇一組與測量向量有最大相似度的聚類中心集合S，其成員為C，歸屬關(guān)系如下

在向量相似度計算時，本文選擇計算復(fù)雜度較低的方法：s（r，j）＝－－，α是門限值，通過該門限獲得一組聚類中心點，因為該值的大小直接關(guān)系到聚類中心數(shù)目的多少，影響計算復(fù)雜度的高低，在此，本文定義其取值如下

其中，α1＋α2＝1。

4.2 細(xì)定位

細(xì)定位用于確定移動終端的最終位置，加權(quán)k近鄰算法具有較好的效果，在粗定位將數(shù)據(jù)集合減少為C 后，運用加權(quán)k近鄰算法完成細(xì)定位。具體過程如下

設(shè)RSSx＝｛RSSx1，RSSx2，…RSSxm｝表示在x 點處接收到的信號強度，n 是無線節(jié)點個數(shù)，RSS′i＝｛RSS′i1，RSS′i2，…，RSS′i3｝表示指紋庫中i點的信號強度，若定位區(qū)域有m 個位置參考點，則記為向量｛RSS′1，RSS′2，…，RSS′m｝，其與位置｛L1，L2，…，Lm｝對應(yīng)。實時信號強度與數(shù)據(jù)庫位置i處信號強度的歐式距離為

實時移動終端的位置為

加權(quán)k近鄰算法是選取歐式距離最小的k 個點，計算這些點的加權(quán)平均，將其作為位置估計點，加權(quán)k 近鄰算法的計算公式如下

式中：d——一個數(shù)值很小的正數(shù)，防止公式中分母出現(xiàn)零的情況。

5 基于奇異值檢測和AP聚類定位算法

本文提出了基于奇異值檢測和AP聚類定位的無線局域網(wǎng)指紋定位算法，算法流程如圖2所示，具體步驟如下：

（1）將定位區(qū)域劃分為網(wǎng)格，設(shè)置位置參考點，偵測不同參考點所接收的不同無線信號強度值RSSI。

（2）將本文提出的奇異值檢測算法應(yīng)用到第一步得到的RSSI值中，去除奇異值。

（3）對經(jīng)過奇異值檢測的RSSI向量值進(jìn)行AP 聚類，并生成最終的指紋數(shù)據(jù)庫。

（4）進(jìn)行基于AP 聚類的位置初定位，確定位置的聚類信息。

（5）用加權(quán)k近鄰算法評估的到移動用戶最終的位置，完成定位過程，得到定位結(jié)果。

圖2 定位算法流程

6 實驗結(jié)果分析

仿真場景是大小為22m×22m 的區(qū)域，不同參考點之間的距離為2 m，區(qū)域中放置4 個無線節(jié)點，型號是TPlink，均勻標(biāo)記121個參考點，在實際環(huán)境中，無線局域網(wǎng)信號均有不同程度抖動，所以本文在模擬RSS時加入了抖動因子。在離線采集階段，每個參考點生成200 個接收信號強度值，然后將強度值通過奇異值檢測算法，去除奇異值，再根據(jù)AP聚類法對模擬環(huán)境中的參考點聚類，經(jīng)過粗定位，用戶會歸屬到某個聚類中。假設(shè)參考點可分為M類，每類有參考點N 個，則未進(jìn)行粗定位時，定位算法的復(fù)雜度為Ο（M×N），而用本文定位計算復(fù)雜度為Ο（M ＋N）。在本文仿真環(huán)境中即可看出，采用本文算法，在線定位階段，最多需計算23次，而其它算法均需計算121 次，計算量大大降低。

在仿真區(qū)域中隨機選擇200個樣點，對每個樣點用本文算法和其它典型的定位算法分別定位100次，得到定位誤差累積分布圖，如下所示，從仿真結(jié)果來看，本文算法定位精度優(yōu)于文獻(xiàn) ［7］算法，平均誤差在3m 內(nèi)的概率為61%左右，算法計算時間縮短，具有較好的定位性能。

不同算法誤差累計概率如圖3所示。

圖3 不同算法誤差累計概率

7 結(jié)束語

本文提出了一種基于奇異值檢測和AP 聚類的無線局域網(wǎng)室內(nèi)定位算法，該方法首先對奇異值檢測算法進(jìn)行了探討，結(jié)合Hampel濾波器和核密度估計給出了一種奇異值檢測算法，然后將AP 聚類應(yīng)用到離線訓(xùn)練系統(tǒng)中，經(jīng)過粗檢測和細(xì)檢測完成室內(nèi)目標(biāo)定位。實驗結(jié)果表明本文算法能夠有效對無線環(huán)境中的目標(biāo)進(jìn)行定位，且定位誤差在3m 內(nèi)的概率為61%，平均定位誤差有降低，減小了計算復(fù)雜度，是一種有效的室內(nèi)目標(biāo)定位算法。

［1］DONG Zhe，WU Yao，SUN Dehui.Multi－source data fusion algorithm on indoor location technology ［J］.Computer Engineering and Design，2014，35 （5）：1527－1530 （in Chinese）.［董哲， 吳瑤，孫德輝.室內(nèi)定位技術(shù)的多源數(shù)據(jù)融合算法研究 ［J］.計算機工程與設(shè)計，2014，35 （5）：1527－1530.］

［2］SHI Xin，YIN Aimin，CHEN Xi.RSSI and multidimensional scaling based indoor localization algorithm ［J］.Chinese Journal of Scientific Instrument，2014，35 （2）：261－267 （in Chinese）.［石欣，印愛民，陳曦.基于RSSI的多維度室內(nèi)定位算法 ［J］.儀器儀表學(xué)報，2014，35 （2）：261－267.］

［3］YANG Xiaoliang，YE Ayong，LING Yuanjing.Indoor localization algorithm based on threshold classification and signal strength weighting ［J］.Journal of Computer Applications，2013，33 （10）：2711－2714 （in Chinese）. ［楊小亮，葉阿勇，凌遠(yuǎn)景.基于閾值分類及信號強度加權(quán)的室內(nèi)定位算法 ［J］.計算機應(yīng)用，2013，33 （10）：2711－2714.］

［4］ZHOU Mu，ZHANG Qiao，QIU Feng.Fingerprinting location method for WLAN using physical neighbor points information ［J］.Journal of Computer Applications，2014，34 （6）：1563－1566 （in Chinese）.［周牧，張巧，邱楓.基于物理鄰近點輔助的無線局域網(wǎng)指紋定位方法 ［J］.計算機應(yīng)用，2014，34 （6）：1563－1566.］

［5］WU Bin，LI Jun’e.Application of wireless sensor network in indoor localization ［J］.Computer Science，2013，40 （5）：115－117 （in Chinese）.［吳彬，李俊娥.無線傳感器網(wǎng)絡(luò)在室內(nèi)定位中的應(yīng)用研究 ［J］.計算機科學(xué)，2013，40 （5）：115－117.］

［6］XU Jin，ZHAO Dongming，WU Xiaojun.Improved difference correction algorithm of wireless localization based on RSSI［J］.Instrument Technique and Sensor，2014 （5）：77－79 （in Chinese）.［徐進(jìn)，趙東明，吳小軍.基于RSSI的無線定位差分修正改進(jìn)算法 ［J］.儀表技術(shù)與傳感器，2014 （5）：77－79.］

［7］Pearson RK.Outliers in process modeling and identification［J］.IEEE Transactions on Control Systems Technology，2002，10 （1）：55－63.

［8］Chen YC，Sun WC，Juang JC.Outlie detection technique for RSS－based localization problems in wireless sensor networks［C］／／Proceedings of SICE Annual Conference，2010：657－662.

［9］Tian Z，Tang X，Zhou M，et al.Fingerprint indoor positioning algorithm based on affinity propagation clustering ［J］.EURASIP Journal on Wireless Communications and Networking，2013 （1）：272.

［10］LIN Haijuan，CHEN Xiaoyun.Clustering of combining AP with NN based on time series［J］.Computer Engineering and Applications，2014，50 （2）：153－155 （in Chinese）. ［林海娟，陳曉云.基于時間序列的AP－NN 混合模型聚類 ［J］.計算機工程與應(yīng)用，2014，50 （2）：153－155.］