仿射傳播聚類在室內定位指紋庫中的應用研究

張儷文，汪云甲，王行風

(中國礦業(yè)大學環(huán)境與測繪學院，江蘇 徐州 221116)

仿射傳播聚類在室內定位指紋庫中的應用研究

張儷文，汪云甲，王行風

(中國礦業(yè)大學環(huán)境與測繪學院，江蘇 徐州 221116)

基于位置指紋的室內定位，指紋數據結構復雜、信號時變性強等原因影響了定位的時效性。K-means聚類算法雖可以有效地減少數據遍歷的工作量，但該方法僅僅考慮了采樣點在信號域的相關性，導致定位精度下降，同樣難以滿足室內定位的實時性要求。本文基于位置指紋方法，借鑒K-means聚類算法的思路，研究了指紋的樣本點位置域和信號域特征的融合方法，并將融合后的特征引入了仿射傳播聚類算法。試驗測試表明，該方法在保證精度的前提下，可使時間消耗平均減少40%，有效地提高了系統(tǒng)的實時性，可以滿足室內定位的基本要求。

室內定位；位置指紋；仿射傳播聚類；特征融合

一、引 言

目前，室內指紋定位系統(tǒng)的研究主要集中在提高系統(tǒng)的定位精度和系統(tǒng)實時性上[1]。提高精度的途徑主要有兩種：一是改進定位算法[2-3]；二是加密定位中使用的指紋庫[4-5]。如果參與計算的點較多，無論是直接插值定位[6-7]，還是基于概率分布定位[8-9]，在時間消耗上都會增加。其中基于概率分布的算法會有更多的時間消耗[10]；而加密指紋庫可以得到較高精度的結果，但也會增加搜索時間。因此，減少匹配的數據量對于增強系統(tǒng)的時效性和提高系統(tǒng)精度十分重要。

對定位指紋庫進行聚類處理可以很好地降低系統(tǒng)搜索樣本點的數據規(guī)模[11-12]。在聚類特征選取上，有使用最強接入點(access point，AP)作為特征的[12]，也有使用樣本點(respective point，RP)信號之間的距離作為特征的[13]。使用最強AP作為特征的聚類處理并不能明顯減少定位計算量，這是由于無線信號在室內強反射環(huán)境中陰影衰落效應較為顯著[14]；利用信號之間的距離作為特征可以很好地避免這種情況[13]，但是定位算法的最終目的是確定未知點的位置，僅使用信號之間的距離并不能很好地反映位置之間的關系，因此造成定位結果的精度不高。

本文將指紋庫中樣本點的信號特征與位置特征進行融合，引入仿射傳播聚類(affinity propagation clustering，APC)方法進行聚類，從而實現(xiàn)指紋庫的分塊處理。試驗場測試表明，本文使用的聚類算法在保證精度的前提下，可使平均時間消耗減少40%。

二、原 理

指紋定位區(qū)域中的AP點組成集合B＝{b1，b2，…，bn}，在該區(qū)域中還有人為規(guī)劃的采樣點RP組成的集合L＝{l1，l2，…，lm}。每一個 L中的元素 li(1≤i≤m)都記錄兩部分數據，一部分是該點的位置向量 Gi＝(xi，yi)，另一部分是在該點接收到的AP點的信號強度向量 Vi＝(vi，1，vi，2，…，vi，n)，其中vi，j(1≤j≤n)表示在li點接收到來自bj的信號強度。S＝{s1，s2，…，sn}表示在區(qū)域中的某個未知位置接收到的信號強度集合，其中sk(1≤k≤n)表示未知位置接收到來自bk的信號強度。

1.融合距離與信號信息的特征提取

在提取聚類特征的過程中，需要使用采樣點在位置域和信號域的距離。信號域距離與位置距離類似，文獻[13]中將兩組信號之間的歐式距離定義為信號距離SigDisdd，如下

空間距離較近的樣本點，搜索的相同AP信號數目多；空間距離較遠的樣本點，搜索到的相同AP信號數目少。相同AP數目可以在一定程度上反映樣本點之間的空間距離關系。因此，在計算信號距離時，引入相同AP數目，可以擴大遠距離點之間的數值，縮小近距離點之間的數值。本文改進的信號距離SigDisnew為

式中，m為(li，lj)點之間的相同AP數目。

兩采樣點之間的位置域距離GeoDis為

信號域距離與位置域距離的量綱不同，為了融合特征，試驗中使用的距離是歸一化之后的結果。兩種距離在數值分布的趨勢上大體相似，但是由于信號的不穩(wěn)定性，信號域距離中噪聲更多。為了排除噪聲的影響，融合特征MixDis利用位置域距離對信號域距離進行限制。融合特征MixDis的定義為

式中，Nor為歸一化函數。

使用地理位置對信號距離進行修正，得到的融合特征可以更好地反映采樣點之間的地理關系。本文第3部分的試驗中顯示，使用融合特征進行聚類，得到的類分布更加均勻，更加接近空間結構劃分。

2.仿射傳播聚類

通常的聚類算法是在多次迭代中選出一個聚類中心，使該類其他成員與聚類中心的距離平方和最小。以經典的K-means算法為例，算法啟動時需要提供一系列的類中心初始值，并且算法對系統(tǒng)的初始值依賴性較大，容易陷入局部極值[15]。而 APC是將所有的點連接成網絡，每個節(jié)點都是潛在的聚類中心，通過迭代，點之間不斷發(fā)射和接收吸引度和歸屬度消息，從而不斷擴大中心點和附屬點之間的差距，最終確定中心點[16]。與K-means方法相比，APC的收斂速度更快，得到的絕對平均誤差和平均方差要比K-means的結果低[16-17]。

APC的輸入信息為n個點之間的相似度矩陣Sn×n，本文使用的就是融合后的特征MixDis。對于s(k，k)，需要設置一個合理的值來表示，通常選擇Sn×n中的中值，試驗中選擇S的第k行的中值作為s(k，k)的初始值。之后為算法的核心，計算兩兩參考點間的消息傳遞：吸引度消息r(i，j)和歸屬度消息a(i，j)。其中吸引度消息r(i，j)是從i點傳到j點，表明j作為i的聚類中心的可靠度；歸屬度消息a(i，j)是從j點傳到i點，表明i選擇j作為聚類中心的可行度。

(1)吸引度消息r(i，j)

由樣本點li傳到樣本點lj，表明了在除lj點之外的樣本點的作用下lj作為聚類中心對li的吸引度的積累，公式如下式中，s(i，j)是MixDis(i，j)；a(i，j)是下面要定義的歸屬度消息。

(2)歸屬度消息a(i，j)

由樣本點lj傳到樣本點li，表明了在除lj點之外的樣本點的作用下li認為lj為聚類中心的歸屬度的積累，公式如下

(3)自歸屬度消息通過以上兩種消息在樣本點之間的傳遞，實現(xiàn)了中心和歸屬點的劃分。具體來說，如果j′＝i，則參考點li為中心；否則lj′點為中心。

三、試驗與結果分析

1.試驗條件

選取中國礦業(yè)大學南湖校區(qū)的環(huán)測學院樓4層A區(qū)和C區(qū)的走廊作為試驗場，面積約為350 m2，定位中使用的泛在信號為日常傳輸數據的WiFi信號，共99個，并未加設新的設備。圖 1是試驗場的WiFi信號強度分布圖。

圖1 試驗場WiFi強度分布

試驗分為采樣過程、離線處理和定位3個步驟。使用三星GalaxyⅢ (Android 4.0平臺)進行采樣和定位，采樣率為100 Hz，接收信號強度為－110～15的整數，采樣過程需要對東西南北4個方向采集可接收AP點的Mac地址和平均信號強度，共采集有效點93個，平均采樣間隔3.5 m；離線處理即指紋庫的聚類處理；定位與采樣階段類似，但定位方向不一定，且定位時間較短。

2.聚類試驗

通過提取融合特征，采用APC算法對樣本庫中的樣本點進行聚類處理。APC是一種非監(jiān)督分類方法，因此不必設定分類數目。分類結果如圖2所示。

圖2 APC分類結果

同時與文獻[12]使用的K-means算法進行對比，K-means需要設定分類數目，這里將仿射傳播分類的分類數代入，以進行測試。分類結果如圖3所示。圈出的是分類不合理的位置，1為類成員過少，2為邊界模糊，3為走廊拐彎處沒有劃分。

圖3 K-means分類結果

本文使用3種指標對分類結果的均勻性進行分析和評定，分別是類成員數目方差、類平均中心距方差和類覆蓋面積方差。類成員數目是指各類中的采樣點的數目；類平均中心距是指類中各采樣點到聚類中心的距離的平均值，這里為了統(tǒng)計采樣點的空間分布，選用空間距離；類覆蓋面積是指類中成員覆蓋的空間范圍，由于采樣點是沿走廊兩側分布的，可以使用各類采樣點的最小凸包代表類的空間覆蓋空間。這3種數據的方差值用于衡量分類的均勻性，見表1。

表1 分類均勻性指標

從3項指標來看，APC的數值要小于K-means。其中類成員數目是從數量上衡量類劃分的均勻程度，數目差別較大會對鄰域計算產生影響，當類中點的數目少于鄰域計算數目時需要增加其他類的成員點參與計算，這就需要額外添加類之間的關聯(lián)關系。類平均中心距方差和類覆蓋面積方差反映了類在空間覆蓋上的均勻性，空間分布均勻有利于控制定位的精度在一定范圍內變動。

同時，從圖2和圖3中可以看出，APC方法除了類劃分較為均勻之外，走廊的拐彎處也都是類劃分的邊界。這種處理方法有利于提高定位的精度，在拐彎處定位，若不進行拐彎劃分，容易將位置定在走廊之外，形成邏輯錯誤。

3.定位試驗

試驗選用 K近鄰法(K nearest neighborhood， KNN)作為定位算法。未知位置的計算公式[13]為

式中， (xi，yi)為第i個被選取點對應的坐標；K為選取鄰近點的數目，試驗中 K＝6，采樣的平均間隔3.5 m。定位數據的搜集方法為：在試驗場標定26個待定位點，使用相同設備采樣2 s，記錄WiFi信號數據。試驗分別從時間效率和定位精度兩個方面分析對比APC和K-means的定位效果。

聚類處理作為數據的預處理，是通過減少定位時的數據檢索量，從而降低定位使用的時間。在手機平臺定位測試，單點定位時間如圖 4所示，K-means和APC聚類處理相對全局搜索在時間效率上有較大提升，全局搜索定位平均用時127 ms，K-means和APC分別是76 ms和70 ms，提速程度相當；其中K-means的最大降幅為88.2%，最小降幅僅為0.2%，而APC的最大降幅為87.2%，最小降幅也達到16.8%。APC的數據檢索平均減少75%，最多減少80%，其平均減少率與K-means相當，這就使兩種聚類處理方法的平均定位時間相近；但K-means的降幅變化較大，這是由于聚類結果不均勻，導致各個定位點搜索的采樣點數目相差較大，見表 2，K-means最大最小搜索數目之間相差20，而APC僅為10。

圖4 單點定位時間對比

表2 點搜索數目對比 個

定位精度如圖5所示，經過聚類處理的定位要比全局搜索定位的結果更加精確，全局搜索平均定位精度為2.6 m，K-means和APC的平均定位精度分別為1.6 m和1.5 m；K-means的最大定位誤差為5.6 m，最小為0.1 m，APC的最大定位誤差為2.8 m，最小為0.2 m。在平均誤差上 APC的結果要稍好于 K-means，而且誤差波動較小。這是由于K-means中存在成員數目很少的類，該類的信號均值不能反映該類區(qū)域信號特點，容易造成誤匹配，從而使得精度下降。

圖5 單點定位精度對比

四、結 論

本文通過APC對室內定位指紋庫的位置指紋數據進行聚類處理，以減少定位時遍歷數據量，提高定位精度。針對僅使用信號域的相關度衡量采樣點之間的關系造成的定位結果偏差的現(xiàn)象，本文將采樣點的位置域與信號域的相關度進行組合，得到融合特征，將融合特征作為聚類特征代入APC算法，通過試驗場測試得到以下結論：

1)本文使用的聚類算法和特征得到的聚類結果與K-means的結果相比，類劃分更接近空間結構劃分，類分布更加均勻，更有利于提高定位精度。

2)以APC結果為基礎進行KNN插值定位，定位結果精度高于K-means方法，遍歷點平均減少75%，時間較全局搜索平均減少40%。

因此使用APC對采樣點位置域和信號域進行聚類分析，可以有效地減少系統(tǒng)的遍歷數據量，并且提高室內定位的精度。

[1] KUO S P，TSENG Y C.Discriminant Minimization Search for Large-Scale RF-based Localization Systems[J].Mobile Computing，2011，10(2)：291-304.

[3] LI K.Location Estimation in Large Indoor Multi-floor Buildings Using Hybrid Networks[C]∥Wireless Communications and Networking Conference.[S.l.]：IEEE，2013：2137-2142.

[4] ZHE X，ZHANG H，HUANG J，et al.A Hidden Environment Model for Constructing Indoor Radio Maps[C]∥World of Wireless Mobile and Multimedia Networks.[S. l.]：IEEE，2005：395-400.

[5] ZDRUBA G V，HUBER M，KARNANGAR F A，et al. Monte Carlo Sampling Based In-home Location Tracking with Minimal RF Infrastructure Requirements[C]∥Global Telecommunications Conference.[S.l.]：IEEE，2004：3624-3629.

[6] CHAI X Y，YANG Q.Reducing the Calibration Effort for Probabilistic Indoor Location Estimation[J].Mobile Computing，2007，6(6)：649-662.

[7] KRISHNAN P，KRISHNAKUMAR A S.A System for LEASE：Location Estimation Assisted by Stationary Emitters for Indoor RF Wireless Networks[C]∥INFOCOM：Twentythird Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]：IEEE，2004：1001-1011.

[8] WYMEERSCH H，JAIME L.Cooperative Localization in Wireless Networks[J].Proceedings of the IEEE，2009，97(2)：427-450.

[9] YOUSSEF M，AGRAWAL A.Handling Samples Correlation in the Horus System[C]∥INFOCOM.[S.l.]：IEEE，2004：1023-1031.

[10] YOUSSEFF M，AGRAWALA A.On the Optimality of WLAN Location Determination Systems[J].UM Computer Science Department，2004，4(4)：1-6.

[11] YOUSSEFF M，AGRAWALA A.WLAN Location Determination via Clustering and Probability Distributions[C]∥Pervasive Computingand Communications.[S.l.]：IEEE，2003：143-150.

[12] KUO S P.Cluster-enhanced Techniques for Pattern-Matching Localization Systems[C]∥Mobile Adhoc and Sensor Systems.[S.l.]：IEEE，2007：1-9.

[13] BAHL P，PADMANABHAN V N.RADAR：An In-building RF-based User Location and Tracking System[C]∥INFOCOM.[S.l.]：IEEE，2000：775-784.

[14] 賈明華.地鐵隧道環(huán)境毫米波傳播特性的研究[D].上海：上海大學，2010.

[15] 王開軍，張軍英，李丹，等.自適應仿射傳播聚類[J].自動化學報，2007，33(12)：1242-1246.

[16] FREY B J，DUECK D.Clustering by Passing Messages Between Data Points[J].Science，2007，315(5814)：972-976.

[17] 馮辰.基于壓縮感知的RSS室內定位系統(tǒng)研究與實現(xiàn)[D].北京：北京交通大學，2010.

Affinity Propagation Clustering for Fingerprinting Database in Indoor Localization

ZHANG Liwen，WANG Yunjia，WANG Xingfeng

RUNGSI K.Distribution of WLAN

Signal Strength Indication for Indoor Location Determination[C]∥Wireless Pervasive Computing.[S.l.]：IEEE，2006.

P237

B

0494-0911(2014)12-0036-04

張儷文，汪云甲，王行風.仿射傳播聚類在室內定位指紋庫中的應用研究[J].測繪通報，2014(12)：36-39.

10.13474/j.cnki.11-2246.2014.0392

2013-10-24

國家863計劃(2013AA12A201)；地理空間信息工程國家測繪地理信息局重點實驗室資助項目(201321)

張儷文(1990—)，女，陜西渭南人，碩士生，研究方向為室內定位、模式識別。

汪云甲