陳永樂，于 丹，王 澤（太原理工大學計算機科學與技術學院，太原030024）

?

＊基于相似指紋特征的室內(nèi)定位機制研究

陳永樂，于 丹，王 澤
（太原理工大學計算機科學與技術學院，太原030024）

摘 要：針對指紋定位結(jié)果中存在較大定位誤差問題，分析了離線相似指紋對應采集點的分布特征，發(fā)現(xiàn)存在部分相似指紋對應的采集點位置距離較遠的特征，這導致了較大定位誤差的出現(xiàn)。據(jù)此提出了一種基于閾值的Dynamic－kNN的算法來實現(xiàn)指紋的匹配，并進一步針對相似指紋的聚類特征設計了基于K－Means的聚類優(yōu)化算法，從而大大減少了定位結(jié)果中較大誤差的存在。實驗表明，該算法能夠?qū)⒆畲蠖ㄎ徽`差縮小到5m以內(nèi)，同時4m以上的較大定位誤差所占比例也明顯下降。本研究與其他算法相比，在定位性能和算法開銷上具有明顯優(yōu)勢。

關鍵詞：WiFi信號；信號強度；指紋定位

（2014124）；太原理工大學校青年基金（2013Z060）；太原理工大學?；痦椖浚?014TD054）

室內(nèi)定位是提供室內(nèi)位置服務的關鍵支撐，由于GPS在室內(nèi)的不可用性和蜂窩定位的粗粒度特征，使得室內(nèi)定位亟需尋求細粒度的高效定位方法。指紋定位是指利用室內(nèi)不同位置的無線信號特征存在的唯一性，將位置和其對應的無線信號特征進行關聯(lián)，從而將無線信號特征形象的稱為指紋，并將位置作為需要識別的目標進行匹配的過程。由于公共環(huán)境中無線基礎設施的普及，尤其是公共WiFi網(wǎng)絡的覆蓋，使得指紋定位能夠依賴于現(xiàn)有設施完成部署。指紋定位通常分為離線采集和在線匹配兩個步驟：離線采集是指通過對定位區(qū)域的所有位置進行信號強度指紋的采集，構建無線信號指紋數(shù)據(jù)庫；在線匹配是指在實時定位階段能夠?qū)F(xiàn)場采集的信號指紋與數(shù)據(jù)庫中的指紋進行匹配，選擇最優(yōu)匹配指紋對應的位置為定位結(jié)果。因此，只要無線WiFi網(wǎng)絡覆蓋的地方就很容易實現(xiàn)指紋定位算法，這使得指紋定位算法已經(jīng)成為室內(nèi)定位的理想之選。

定位精度是室內(nèi)定位算法追求的主要指標之一，已有許多研究者設計各種在線匹配算法來提高定位的精度，從確定性kNN算法［1］到概率性貝葉斯估計算法［2］和順序蒙特卡羅算法［3］，再到支持向量機［4］以及神經(jīng)網(wǎng)絡算法均先后被用于提高指紋定位算法的定位精度。目前多數(shù)指紋定位算法基本能夠在室內(nèi)達到2m左右的中位數(shù)誤差，但是總存在少量6m以上的較大定位誤差，這是定位精度提高的一個關鍵瓶頸［5］。同時，人身體使WiFi信號產(chǎn)生的多徑和陰影將導致信號強度嚴重衰減［7］。本文通過實驗分析了人員不同朝向和手持設備不同位置對WiFi指紋定位的影響，發(fā)現(xiàn)身體遮擋產(chǎn)生的多徑和陰影導致指紋出現(xiàn)了8m左右的更大定位誤差，說明多徑和陰影會進一步加劇較大定位誤差的存在，目前很少有研究考慮降低這些較大定位誤差。文獻［5］提出了一種基于手機輔助的Peer Assisted算法，利用手機上自帶的麥克風和揚聲器測量手機與手機之間的距離，根據(jù)手機用戶之間的距離關系來約束指紋定位的結(jié)果，從而防止出現(xiàn)較大的定位誤差。盡管該方法能夠避免較大定位誤差的產(chǎn)生，但是該方法需要采用額外的聲音測距算法，會大幅增加定位服務產(chǎn)生的能量消耗，更重要的是聲音測距在多數(shù)室內(nèi)環(huán)境中，尤其是嘈雜的公共環(huán)境中受到嚴重制約而不能使用。

針對存在的較大定位誤差問題，對離線相似指紋的位置分布進行了分析，發(fā)現(xiàn)離線指紋庫中的指紋之間存在“相似指紋對應位置卻相距較遠”的特征，這是導致出現(xiàn)較大定位誤差的根本原因。而多徑和陰影也會進一步加劇這一問題的產(chǎn)生，從而導致更多的較大定位誤差，為此，設計了一種基于閾值的Dynamic－kNN算法來實現(xiàn)指紋的匹配，并對匹配出的候選指紋設計了K－Means的聚類優(yōu)化算法以實現(xiàn)細粒度的精確指紋定位。

1　無線信號指紋粒度與定位性能分析

1．1 人身遮擋對指紋粒度和定位性能的影響

為了深入分析WiFi指紋定位的性能，針對人員朝向和手持手機的位置兩方面的遮擋因素設計了兩組實驗，分別與無人為遮擋干擾的實驗結(jié)果作對比。由于智能手機中基于位置應用的廣泛普及，采用了GALAXY Note3手機作為實驗測量平臺，本實驗集中考慮人為遮擋產(chǎn)生的多徑和陰影對指紋信號的影響，暫不考慮設備差異性帶來的指紋誤差。

實驗環(huán)境如圖1所示，在38m×26m的實驗室開放空間，由于辦公桌椅覆蓋的地方無人經(jīng)過，本實驗選擇在走廊等人員可移動區(qū)域中的76個位置進行WiFi指紋采集，共有8個AP被部署用于信號測量，部署位置如圖1中星號所示。分別手持被定位手機的底部和上部位置，在每個采集點，按照用戶朝向0°，90°，180°和270°這4個方向進行采集，每個朝向采集15組信號強度取平均值，這樣在離線指紋庫中生成指紋記錄共608條，其中每條指紋記錄可描述為

f＝〈rssi1，rssi2，…，rssin〉，

rssii的值為信號強度的平均值，n值為AP的數(shù)量。

圖1　實驗環(huán)境中指紋采集點分布圖

通常情況下，無線信號強度的測量隨時間變化也會有一定的誤差［6］，假設這一測量誤差符合零均值正態(tài)分布，方差為ε。指紋的匹配采用指紋向量的歐氏距離測量相似性，那么n個AP所得的指紋歐式距離的最大誤差能夠通過如下公式來計算：

只有當兩個指紋向量的距離大于emax時，才會有明顯的指紋相異性，這種指紋的相異性在本文中被稱為指紋粒度。由于誤差ε是信號測量的固有誤差，因此稱emax為最大固有指紋粒度誤差。

圖2　朝向和手持位置對指紋的影響

為分析人員朝向和手持手機位置對指紋粒度和定位精度的影響，對采集的608條指紋記錄分朝向和手持位置進行了4組實驗，如圖2所示。其中分朝向?qū)嶒灢捎檬殖值撞織l件下的兩組數(shù)據(jù)：分別是0°朝向采集的76條指紋自身之間的指紋粒度，0°朝向與90°朝向采集的76條指紋之間的指紋粒度；分手持位置采用180°朝向條件下的兩組數(shù)據(jù)：分別是手持底部采集76條指紋自身之間的指紋粒度，手持底部與上部采集76條指紋之間的指紋粒度。

圖2－a和2－b給出了分朝向和手持位置的指紋粒度累積分布。假設通常信號測量誤差的方差為5db［6］，按照式（1）計算得到最大固有指紋粒度誤差為28db。圖2－a中指紋粒度小于28dB的指紋（即相似指紋）所占比例分別為13%和19%，其中不同朝向間比同朝向間指紋的相似比例更大。圖2－b中指紋粒度小于28dB的指紋所占比例分別為18% 和23%，其中手持底部與上部之間比手持底部自身的相似比更大，并且手持位置比朝向?qū)ο嗨浦讣y比例的影響更大，這主要由于手比身體更靠近手機所致。圖2－c和2－d在室內(nèi)隨機抽選了30個采樣位置，并在30個位置分別定位5次對指紋定位的精度進行分朝向和手持位置的比較，發(fā)現(xiàn)指紋粒度比較中的相似指紋所占比例越高對應的定位精度越低，而且無論采用何種方式比較，定位結(jié)果中總是存在少量誤差，甚至超過6～8m。這些較大的誤差是造成定位精度下降的主要因素，為了分析較大誤差出現(xiàn)的原因，對指紋庫中的相似指紋做了進一步分析。

1．2 較大定位誤差的原因分析

圖3　四個采集點的相似指紋分布

為了分析出現(xiàn)較大誤差的原因，比較了分朝向影響下相似指紋的位置分布。將相似指紋按照指紋對應的采集點位置進行分組顯示，為76個采集點分朝向選擇相似指紋以及確定相似指紋對應的位置。指紋相似的判定閾值為最大固有指紋粒度誤差。如圖3所示，分別對73號采集點的0°朝向、42號采集點的90°朝向、51號采集點的270°朝向以及59號節(jié)點的180°朝向做了相似指紋的位置分布顯示。其中與42號采集點90°朝向的指紋相似的位置如圖中實心圓點所示，這些位置除了多數(shù)與42號采集點位置相近外，還有少數(shù)與42號采集點的位置距離較遠，這些少量的離群點將會導致相似指紋對應的位置較遠，這勢必造成指紋定位結(jié)果出現(xiàn)較大誤差。此外，具有相似指紋的采集點位置之間具有明顯的區(qū)域成簇特征，即多數(shù)相似指紋的采集位置相近。從其它采集點的相似指紋位置分布來看，也具有類似特征。因此，指紋庫中存在的少數(shù)具有相似指紋對應的離群采集點是造成指紋定位出現(xiàn)較大誤差的根源。針對相似指紋對應位置的簇分布特征，本文嘗試通過聚類優(yōu)化方法來解決較大定位誤差問題。

2　基于相似指紋特征的聚類優(yōu)化

目前，許多研究聚焦于設計在線匹配算法和濾波優(yōu)化算法來提高指紋定位的精度。其中對定位結(jié)果的濾波優(yōu)化，能夠根據(jù)前期的定位結(jié)果進行平滑擬合，防止出現(xiàn)較大的定位偏差，但是如果定位結(jié)果經(jīng)常存在較大定位誤差，即使對結(jié)果進行濾波擬合，也無法從根本上提高定位系統(tǒng)的精度。因此，對指紋定位結(jié)果的優(yōu)化預處理，能夠從數(shù)據(jù)質(zhì)量上提高單次定位的性能。

kNN算法是一種常用的分類算法，能夠從離線采集的指紋數(shù)據(jù)庫中選擇與實時采集到的指紋向量距離最近的k個指紋向量，將這k個指紋向量對應位置的質(zhì)心位置作為指紋定位的結(jié)果。通常，kNN算法也包括2個步驟。第一步是計算離線指紋庫中與在線指紋距離最鄰近的k條指紋對應的采集點，其中k值的選擇將直接關系到最終定位的精度。第二步需要通過k各候選的采集點位置利用質(zhì)心算法來估計待測指紋對應的位置，針對這2個步驟，分別給出了相應的解決策略。

2．1 設定最鄰近k值

kNN算法是通常采用指紋向量之間的歐式距離來衡量指紋鄰接，其中指紋向量的維數(shù)為環(huán)境中AP的個數(shù)。在kNN算法中最鄰近的選擇準確性依賴于k值的選擇，如果k值選擇太小，那么被選擇的最鄰近采集點就會很少，假如采集點的選擇存在誤差，會使得出現(xiàn)較大定位誤差。如果k值選擇過大，不僅增加算法執(zhí)行開銷，更容易引入許多距離較遠采集點，這也會導致定位誤差的增大。本文通過優(yōu)化設定閾值來保證kNN算法的性能，通過閾值的設定來保證既不會有太多物理距離相對較遠的采集點被選擇，也要保證盡可能多的采集點被選擇。因此，采用指紋誤差的臨界值（即最大固有指紋粒度誤差emax）作為kNN最鄰近的判定閾值，在固有誤差導致的指紋距離誤差以內(nèi)的指紋均被認為是與待測指紋是臨近的，k值的選擇將不再固定，會根據(jù)閾值的設定而動態(tài)變化，被稱為Dynamic－kNN算法。該方法能夠防止實際距離較遠的采集點被選擇為最鄰近所導致的定位性能下降。

2．2 估計最佳位置

Dynamic－kNN算法將所有的最鄰近采集點選擇完之后，需要利用質(zhì)心算法求得目標的位置坐標。以二維空間為例，質(zhì)心算法的估計位置坐標求解公式如下：

式中，（X1，Y1），…，（Xk，Yk）為k個被選擇采集點的位置坐標。

該算法操作方便，計算簡單，然而無法解決指紋相似而實際距離較遠的采集點帶來的定位誤差。盡管有些現(xiàn)有工作也提出基于加權的質(zhì)心算法來改進指紋算法的定位估計，然而都是從指紋歐式距離遠近的角度來考慮，根據(jù)指紋距離的大小來估計位置的匹配準確程度，這同樣無法解決較遠距離采集點存在相似指紋問題。

根據(jù)前面的實驗結(jié)論，已經(jīng)發(fā)現(xiàn)相似指紋的采集點存在實際距離較遠的可能，但是距離較近的明顯占多數(shù)，且具有顯著的簇特征。因此設計了一種簇中心選擇策略來估計最佳定位位置。首先，計算k個候選采集點間的平均距離Td，公式如下：然后，以平均距離Td作為候選采集點的分簇判定閾值，并利用K－Means聚類算法選擇簇的中心采集點位置作為定位結(jié)果。其主要步驟如下：

1）所有k個候選采集點為一個初始簇，計算其質(zhì)心作為簇的中心點；

2）計算每個采集點到簇中心點的歐式距離，將歐式距離小于簇判定閾值Td的采集點添加到簇中；

3）重新計算質(zhì)心作為最終定位結(jié)果。

該算法通過分簇判定閾值的設定，避免了KMeans聚類算法的多次迭代，大幅提高了算法的執(zhí)行效率。同時該算法能夠消除指紋近似而實際距離較遠的異常采集點，最終以所有最鄰近采集點的分布最密集的質(zhì)心位置為圓心，以簇判定閾值為半徑形成一個圓形的簇，圓心位置就是定位的結(jié)果。這樣，距離較遠的采集點變?yōu)楣铝Ⅻc也均被剔除出簇，

這將進一步提高定位的精度。

3　實驗驗證與結(jié)果

3．1 實驗設計

為了驗證算法的有效性，本文仍采用圖1中38m×26m開放辦公室場景和對應的608條指紋記錄進行實驗驗證。首先分析指紋距離閾值設定對k值的影響，其次分析了分簇閾值設定對定位結(jié)果的影響，最后，從整體上衡量本文提出的DynamickNN算法對指紋定位性能的提高程度。

3．2 性能評價

本實驗仍以信號測量誤差的方差為5db為參考標準，計算得到最大固有指紋粒度誤差為28db，如圖4所示。據(jù)此計算在20個位置進行了10次指紋測量和kNN定位后，綜合統(tǒng)計k值的變化，發(fā)現(xiàn)k均值呈現(xiàn)明顯的起伏，這說明不同位置的k鄰近指紋數(shù)量不盡相同，這是因為有些位置處于室內(nèi)邊角處，周邊沒有相鄰的指紋采集點，導致相似指紋偏少，而居于室內(nèi)中間位置的采集點周圍都可以采集指紋，其相似指紋偏多，從而出現(xiàn)各采集位置的k值明顯不同。

圖4　相似指紋閾值對k值的影響

為了本文優(yōu)化算法的整體性能，以手持手機底部0°朝向和以手持手機上部90°朝向的混合指紋為基礎原數(shù)據(jù)進行定位精度的分析，以分析不同朝向及不同手持位置下指紋定位精度的性能變化，如圖5所示。聚類優(yōu)化后（Dynamic－kNN，K－Means）的中位數(shù)誤差從原數(shù)據(jù)的大于2m降低到2m以內(nèi)，90%以內(nèi)誤差也由原數(shù)據(jù)的4m下降到3m左右。尤其是最大誤差有了明顯的降低，原數(shù)據(jù)的最大誤差達到8m左右，而Dynamic－kNN算法執(zhí)行后最大誤差接近6m，進一步執(zhí)行1－Means分簇后獲得5m以內(nèi)的最大誤差，這與文獻［7］中2個手機輔助的Peer Assisted算法所達到的4．3m最大定位誤差性能接近。同時較大誤差所占的比例也出現(xiàn)明顯

圖5　動態(tài)聚類優(yōu)化指紋定位算法性能

下降，原數(shù)據(jù)4m以上的定位誤差占到近10%，而Dynamic－kNN后比例下降到6%，K－Means算法進

一步使該比例下降到2%以內(nèi)。

4　結(jié)束語

指紋定位因其不依賴額外部署已經(jīng)得到廣泛研究，本文對離線相似指紋的位置分布進行分析，發(fā)現(xiàn)少量相似指紋對應采集點位置較遠是導致定位結(jié)果中出現(xiàn)較大定位誤差的主要原因，而多徑和陰影也會進一步加劇較大誤差的出現(xiàn)。為此，本文設計了一種基于閾值的Dynamic－kNN算法來進行匹配，對匹配的采集點進行K－Means的聚類優(yōu)化算法以實現(xiàn)細粒度指紋定位。實驗結(jié)果表明本文聚類優(yōu)化算法能夠大幅減少較大定位誤差的出現(xiàn)。

參考文獻：

［1］ Prasithsangaree P，Krishnamurthy P，Chrysanthis P K．On indoor position location with wireless LANs［C］∥Proceedings of the 2002IEEE Personal，Indoor and Mobile Radio Communications，2002，2：720－724．

［2］ King T，Kopf S，Haenselmann T，et al．COMPASS：A probabilistic indoor positioning system based on 802．11and digital compasses［C］∥Proceedings of the 2006IEEE WiNTECH，LosAngeles，CA，USA，2006：34－40．

［3］ Morelli C，Nicoli M，Rampa V，et al．Particle filters for RSS－based localization in wireless sensor networks：An experimental study［C］∥Proceedings of the 2006IEEE ICASSP，Washington DC，USA，2006：957－960．

［4］ Lee C W，Lin T N，F(xiàn)ang S H，et al．A novel clustering－based approach of indoor location fingerprinting［C］∥Proceedings of the 2013IEEE Personal Indoor and Mobile Radio Communications（PIMRC），2013：3191－3196．

［5］ Liu H，Gan Y，Yang J，et al．Push the limit of WiFi based localization for smartphones［C］∥Proceedings of the 18th annual international conference on Mobile computing and networking，2012：305－316．

［6］ 陳永樂，朱紅松，孫利民．一種抗多徑和陰影的視距指紋定位算法［J］．計算機研究與發(fā)展，2013（3）：524－531．

（編輯：劉笑達）

［7］ Bahland P，Padmanabhan V N．RADAR：An in－building RF－based user Location and tracking system［C］∥Proceedings of the 2000IEEE INFOCOM，Piscataway，NJ，USA，2000：775－784．

Indoor Positioning Mechanism Research Based on Similar Fingerprint Characteristics

CHEN Yongle，YU Dan，WANG Ze
（College of Computer Science and Technology，Taiyuan University of Technology，Taiyuan030024，China）

Abstract：For big errors of fingerprint positioning，we analyzed corresponding position distribution of off－line similar fingerprints and found the long distance of sampling positions of some similar fingerprints．Accordingly，we proposed a Dynamic kNN algorithm to achieve the fingerprint matching based on a setting threshold．Moreover，a clustering algorithm on K Means was proposed with the clustering characteristics of similar fingerprints，which greatly reduced larger errors in the positioning results．Experiment results show that the algorithm can reduce the maximum positioning errors to less than 5m．Meanwhile，the proportion of the large positioning errors greater than 4malso decreases，which has clear advantages in the positioning performance and overhead in comparison with other algorithms．

Key words：WiFi signal；signal strength；fingerprint positioning

作者簡介：陳永樂（1983－），男，山東濰坊人，博士，講師，主要從事無線傳感器網(wǎng)絡研究，（Tel）13994269473

基金項目：國家自然科學基金項目：基于移動感知的室內(nèi)指紋定位可通用性問題研究（61401300）；山西省教育廳科技創(chuàng)新基金

收稿日期：＊2015－01－19

文章編號：1007－9432（2015）03－0336－05

DOI：10．16355／j．cnki．issn1007－9432tyut．2015．03．018

文獻標識碼：A

中圖分類號：TP393