陳蒙 千博

摘要：針對(duì)現(xiàn)有WiFi定位技術(shù)位置指紋匹配算法存在搜索空間大、WiFi信號(hào)不穩(wěn)定分布導(dǎo)致定位誤差大的問題，文章提出一種改進(jìn)型位置指紋定位算法，該算法基于仿射傳播聚類和改進(jìn)型加權(quán)1：近鄰實(shí)現(xiàn)。實(shí)驗(yàn)分析表明，該算法降低了參考點(diǎn)匹配數(shù)目，提升了室內(nèi)定位精度。

關(guān)鍵詞：室內(nèi)定位；位置指紋：仿射傳播聚類；改進(jìn)型加權(quán)K近鄰法

隨著移動(dòng)通信技術(shù)的不斷發(fā)展，位置感知服務(wù)的需求日益增加，定位技術(shù)是實(shí)現(xiàn)位置感知的基礎(chǔ)。GPS衛(wèi)星導(dǎo)航定位系統(tǒng)無法應(yīng)用于室內(nèi)環(huán)境，因此需要借助其他技術(shù)手段實(shí)現(xiàn)室內(nèi)定位。目前典型的用于室內(nèi)定位的硬件設(shè)備有藍(lán)牙、RFID、超寬帶、ZigBee、傳感器、LED可見光等，基于這類設(shè)備的定位系統(tǒng)定位成本高，在實(shí)際應(yīng)用中難以普及[1-2]。由于WiFi信號(hào)廣泛存在于各種建筑物中，無線接入點(diǎn)（AccessPoint，AP）覆蓋范圍廣，基于WiFi的室內(nèi)定位技術(shù)成為熱點(diǎn)研究問題。

目前，在基于WiFi的室內(nèi)定位技術(shù)中常用基于接收信號(hào)強(qiáng)度（Received Signal Strength Indication。RSSDI）的方法[3]，基于RSSI的方法又可分為基于RSSI測(cè)距定位和位置指紋法。測(cè)距定位的思想是根據(jù)RSS在空間的傳播損耗模型估計(jì)智能終端與AP的距離，根據(jù)三邊測(cè)量方法可以計(jì)算智能終端的位置。但是由于WiFi信號(hào)在室內(nèi)傳播存在折射、散射、多徑衰落等問題，基于RSSI測(cè)距的方法難以滿足實(shí)際應(yīng)用中的定位精度。位置指紋法被國(guó)內(nèi)外很多學(xué)者研究，微軟在2000年最早進(jìn)行位置指紋的研究工作[4]。目前，室內(nèi)定位的主要目標(biāo)是如何在改善定位精度的同時(shí)降低計(jì)算復(fù)雜度，現(xiàn)有研究表明，聚類處理位置指紋庫可以達(dá)到降低計(jì)算復(fù)雜度的目的[5-7]。

1 定位原理

1.1算法基本流程

本文提出的基于仿射傳播聚類和改進(jìn)型WKNN位置指紋定位算法包括離線階段和在線階段。離線采樣階段，使用移動(dòng)設(shè)備采集某一區(qū)域己知參考點(diǎn)（ RespectivePoint，RP）的RSS信息，經(jīng)預(yù)處理得到原始指紋庫，應(yīng)用仿射傳播聚類優(yōu)化處理位置指紋庫。在線定位階段，移動(dòng)終端在當(dāng)前測(cè)試點(diǎn)接收到一組RSS信息，與指紋庫RSS進(jìn)行相似性匹配，匹配過程包括粗定位和精定位兩個(gè)過程，粗定位過程確定測(cè)試點(diǎn)所在類指紋庫，精定位過程估計(jì)出測(cè)試點(diǎn)最終位置。

1.2仿射傳播聚類算法

室內(nèi)環(huán)境下選擇M個(gè)參考點(diǎn)，在所有參考點(diǎn)處離線采樣并經(jīng)預(yù)處理后獲取原始指紋庫，用Ψ表示。

其中：

M表示參考點(diǎn)個(gè)數(shù)：

N表示AP個(gè)數(shù)；

Rn表示移動(dòng)終端在第i個(gè)參考點(diǎn)采樣的來自第i個(gè)AP的平均信號(hào)強(qiáng)度；

Vij表示移動(dòng)終端在第i個(gè)參考點(diǎn)采樣獲取到來自第j個(gè)AP的信號(hào)強(qiáng)度方差；

Ri=[Rn，R12，…，RiN]表示在參考點(diǎn)i處的平均信號(hào)強(qiáng)度向量；

Vi=[Vi1，Vi2，…，ViN]表示在參考點(diǎn)i處的信號(hào)方差；

向量R；和R，是任意兩個(gè)參考點(diǎn)的平均信號(hào)強(qiáng)度向量，參考點(diǎn)i和參考點(diǎn)/之間的相似度函數(shù)表示為：（2）

仿射傳播聚類（A伍nity Propagation Clustering，APC）是由Frey等[8]提出的一種聚類算法。聚類特征選擇為M個(gè)參考點(diǎn)之間的相似度，M個(gè)參考點(diǎn)之間的相似度可以組成MXM的相似度矩陣s。APC算法中在參考點(diǎn)間傳遞歸屬度r（i，j）（ Responsibility）和吸引度a（i，j） （Availability）兩種類型的消息，r（i，j）表示參考點(diǎn)j作為參考點(diǎn)i的聚類中心的可信程度，a（i，j）表示參考點(diǎn)；選擇參考點(diǎn)j作為其聚類中心的可信程度。如果r（i，j）與a（i，j）的值越大，則表明參考點(diǎn)j就越有可能作為聚類中心。

APC算法的迭代過程如下：

輸入相似度矩陣SM×M，由公式（2）算出參考點(diǎn)i和參考點(diǎn)j之間的相似度，s（i，j）=sim（i，j），i≠j； s（i，j）設(shè)置為矩陣SM×M的中值；

更新吸引度消息：r（i，j）=s（i，j）-max{a（i，j）+s（i，j）}j≠j（3） 更新歸屬度消息： a（i，j）=min{o，r（j，j）+∑i≠i，jmax{0，r（i，j）}}（4） 以上兩種消息在參考點(diǎn)之間不斷迭代完成聚類中心和歸屬點(diǎn)的劃分，最終完成聚類。仿射傳播聚類處理后的指紋庫表示如下：（5）

其中Rab和Vab分別表示聚類中心參考點(diǎn)。接收到的來自第6個(gè)AP的信號(hào)強(qiáng)度均值和信號(hào)強(qiáng)度方差，1≤a≤P，1≤6≤N，聚類個(gè)數(shù)為P。

1.3粗定位策略

粗定位過程用于確定測(cè)試點(diǎn)所在類指紋庫范圍，為后面的精確定位過程所用。粗定位策略的實(shí)施可以縮小在線定位時(shí)精定位的匹配搜索范圍，從而有效降低了計(jì)算的復(fù)雜度。本文采用基于聚類中心的類匹配機(jī)制，根據(jù)公式（2）計(jì)算待測(cè)點(diǎn)RSS向量與離線指紋庫φ中所有類中心RSS向量間相似度。定義閡值相似度β，選擇相似度大于閾值β的類中心。將β定義為某一比例下最大相似度與最小相似度的線性組合，表示為： β=α·max{s（i，j）} +（l-α）-min{s（i，j）}（6） 在本文的實(shí)驗(yàn)中，α=0.95。 根據(jù)選擇的一個(gè)或多個(gè)類中心，可以確定匹配類中心的集合，以及類中心對(duì)應(yīng)的類成員集合，即確定了待測(cè)點(diǎn)所在的類指紋庫。

1.4改進(jìn)的WKNN算法

在線匹配算法常用的有近鄰法、K近鄰法（K NearestNeighborhood，KNN）和基于K近鄰法改進(jìn)的加權(quán)K近鄰法（Weighted K Nearest Neighbo血ood，WKNN）。在匹配范圍內(nèi)計(jì)算待測(cè)點(diǎn)與所有參考點(diǎn)的距離，選取前K個(gè)與待測(cè)點(diǎn)距離最近的參考點(diǎn)。Rl=[Rj1，Rj2，…，RjN]表示在待測(cè)點(diǎn)j接收到的N個(gè)AP的信號(hào)強(qiáng)度，則待測(cè)點(diǎn)j與參考點(diǎn)i的距離一般用歐氏距離表示：（7）

由于WiFi信號(hào)容易受到外界環(huán)境的干擾，信號(hào)的分布不穩(wěn)定，不同位置檢測(cè)到的RSS信號(hào)穩(wěn)定性差異較大，導(dǎo)致在線定位階段出現(xiàn)的偶然誤差較大。簡(jiǎn)單的歐式距離無法完全表征實(shí)際的空間距離，基于此，考慮加入?yún)⒖键c(diǎn)信號(hào)采樣方差來表征距離。在參考點(diǎn)改」接收到來自某-AP的信號(hào)強(qiáng)度方差越小，表明該AP信號(hào)越穩(wěn)定，則給予當(dāng)前AP對(duì)待測(cè)點(diǎn)到參考點(diǎn)距離更大的貢獻(xiàn)度。

改進(jìn)后的距離計(jì)算公式為：（8）

式中，Vil移動(dòng)終端在參考點(diǎn)；采樣獲取的來自第J個(gè)AP的信號(hào)強(qiáng)度方差。

最后通過公式（8）計(jì)算得到前K個(gè)與待測(cè)點(diǎn)位置距離最近的參考點(diǎn)，并由這K個(gè)參考點(diǎn)估計(jì)待測(cè)點(diǎn)位置，計(jì)算公式為：

式中，xi為參考點(diǎn)的橫坐標(biāo)，Di為待測(cè)點(diǎn)到參考點(diǎn)i的距離，待測(cè)點(diǎn)的縱坐標(biāo)計(jì)算公式同公式（9）。

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

為了驗(yàn)證本文所提算法的性能，本文選取西安電子科技大學(xué)97號(hào)樓5樓走廊作為實(shí)驗(yàn)區(qū)域（面積約為42X1.5 m2），整個(gè)區(qū)域可檢測(cè)到的AP共79個(gè)，實(shí)驗(yàn)WiFi信號(hào)接收器采用VIVO X6A （Android5.0系統(tǒng)）手機(jī)。實(shí)驗(yàn)采集2 m×0.5m的網(wǎng)格數(shù)據(jù)，共采集64個(gè)位置點(diǎn)，其中44個(gè)固定參考點(diǎn)，20個(gè)位置點(diǎn)作為待測(cè)點(diǎn)。在每個(gè)位置點(diǎn)掃描所有可檢測(cè)到的AP，來自每個(gè)AP的RSS值采集30組，構(gòu)建原始數(shù)據(jù)庫。使用MATLAB軟件搭建仿真實(shí)驗(yàn)平臺(tái)。

實(shí)驗(yàn)采用累積誤差分布函數(shù)、定位誤差距離、定位搜索參考點(diǎn)數(shù)目來分析定位算法性能，分別與KNN和WKNN算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果見圖1、表1、表2。從圖3可以看出，本文提出的算法的定位誤差在2m以內(nèi)的概率約為60%，傳統(tǒng)的KNN和WKNN算法定位誤差在2m以內(nèi)的概率分別約為24%，27%。從表1可以看出，本文提出的算法的平均誤差和最大誤差小于KNN和WKNN算法，最小定位誤差距離稍大于KNN和WKNN算法。從表2可以看出，KNN和WKNN算法所需搜索的參考點(diǎn)數(shù)目平均值、最大值、最小值均為44個(gè)，本文提出的算法平均搜索數(shù)目為16個(gè)，最大搜索數(shù)目為28個(gè)，最小搜索數(shù)目為10個(gè)，說明本文提出的算法大幅度降低了參考點(diǎn)搜索數(shù)目，通過減少參考點(diǎn)的搜索數(shù)目，達(dá)到降低定位復(fù)雜度的目的。

3 結(jié)語

本文通過仿射傳播聚類對(duì)室內(nèi)定位指紋庫的位置指紋進(jìn)行聚類處理，以減少定位時(shí)搜索的參考點(diǎn)數(shù)目。針對(duì)WiFi信號(hào)的時(shí)變性導(dǎo)致的在線定位階段出現(xiàn)的偶然誤差大的現(xiàn)象，在線階段采用改進(jìn)的基于參考點(diǎn)信號(hào)強(qiáng)度采樣方差的WKNN算法。

通過實(shí)驗(yàn)得到以下結(jié)論：本文提出的基于仿射傳播聚類和改進(jìn)型WKNN算法可以有效改善定位精度，同時(shí)減少參考點(diǎn)匹配數(shù)目，降低計(jì)算復(fù)雜度。

[參考文獻(xiàn)]

[1]張明華基于WLAN的室內(nèi)定位技術(shù)研究[D].上海：上海交通大學(xué)，2009

[2]陳麗娜基于WLAN的位置指紋室內(nèi)定位技術(shù)[M]北京：科學(xué)出版社，2015

[3]張明華，張申生，曹健無線局域網(wǎng)中基于信號(hào)強(qiáng)度的室內(nèi)定位[J].計(jì)算機(jī)科學(xué)，2007 （6）：68-71

[4]BAHL P，PADMANABHAN V N.RADAR： an In-Building RF-based user location and tracking system[C].TelAviv： Nineteenth JointConference ofthe IEEE Computer and Communications Societies， 2000

[5]MOUSTAFA Y， ASHOK A.The horus， location determination system[J].Wireless Networks， 2008（3）：357-374.

[6]張儷文，汪云甲，王行風(fēng).仿射傳播聚類在室內(nèi)定位指紋庫中的應(yīng)用研究[J].測(cè)繪通報(bào)，2014 （12）：36-39.

[7]唐笑謀，唐佳杰基于仿射傳播聚類的概率分布室內(nèi)定位算法[J].電信工程技術(shù)與標(biāo)準(zhǔn)化，2013（8）：62-67.

[8]FREY， BRENDANJ， DELBERT D.Clustering by passing messages between data points[J].Science， 2007（ 5814）： 972-976