唐笑謀，唐佳杰

（1 重慶郵電大學(xué)重慶市移動通信技術(shù)重點實驗室，重慶 400065；2. 重慶工商大學(xué)計算機科學(xué)與信息工程學(xué)院，重慶 400067）

基于仿射傳播聚類的概率分布室內(nèi)定位算法

唐笑謀1，唐佳杰2

（1 重慶郵電大學(xué)重慶市移動通信技術(shù)重點實驗室，重慶 400065；2. 重慶工商大學(xué)計算機科學(xué)與信息工程學(xué)院，重慶 400067）

隨著定位技術(shù)的快速發(fā)展，基于無線局域網(wǎng)的室內(nèi)定位成為新的研究熱點。本文提出了一種基于近鄰傳播聚類的概率分布無線局域網(wǎng)（WLAN）室內(nèi)定位算法。與傳統(tǒng)室內(nèi)定位算法相比，該算法首先引入近鄰傳播聚類縮小參考點搜索空間，然后利用概率分布定位算法進(jìn)行精確定位。仿射傳播聚類可以有效減少概率分布定位算法的計算量，應(yīng)用于系統(tǒng)后將有效降低系統(tǒng)復(fù)雜度。實驗結(jié)果表明，本文所提算法具有更好的定位精度，可實現(xiàn)對WLAN室內(nèi)定位目標(biāo)的快速、可靠定位。

WLAN室內(nèi)定位；指紋法；仿射傳播聚類；信號強度；概率分布

近年來，隨著數(shù)據(jù)業(yè)務(wù)的快速增加，人們對定位與導(dǎo)航的需求日益增大，尤其對于復(fù)雜、動態(tài)室內(nèi)環(huán)境下的用戶位置判斷。IEEE 802.11無線局域網(wǎng)(WLAN)標(biāo)準(zhǔn)的問世，讓無線通信市場需求迅猛增長[1]。WLAN接入點(AP)定時發(fā)送信標(biāo)信息中所含的接收信號強度(RSS)為基于位置指紋的室內(nèi)定位技術(shù)提供了可能。目前，國內(nèi)外最具代表性的室內(nèi)定位系統(tǒng)有美國微軟研究院的RADAR系統(tǒng)[2]、馬里蘭大學(xué)的Horus系統(tǒng)[3]、加利福尼亞大學(xué)洛杉磯分校的Nibble系統(tǒng)[4]、北京航天航空大學(xué)的Weyes系統(tǒng)[5]等。RADAR系統(tǒng)定位過程簡單，但精度不高；Horus系統(tǒng)采用信號強度的概率分布函數(shù)，作為位置指紋的基本信息，精度較高，但復(fù)雜度也較高；Nibble采用信噪比作為信號空間樣本，而非RSS，精度不高，但其定義的目標(biāo)位置點粒度較大，一般被定義為整個房間或者重要的位置附近區(qū)域；Weyes系統(tǒng)不直接采用RSS，而采用差值模型，誤差值在不同設(shè)備之間差別較大，精度不高。

在室內(nèi)環(huán)境中利用無線信號強度進(jìn)行定位時，應(yīng)盡量保持室內(nèi)環(huán)境的相對穩(wěn)定，但隨著室內(nèi)人數(shù)增多且存在相對運動時，無線指紋信號的不確定性就會增大，從而嚴(yán)重影響指紋法的定位精度[6]。為了獲得較高的定位精度，基于信號強度的匹配定位技術(shù)一般需要在訓(xùn)練階段采集大量且具有位置標(biāo)記的信號樣本，以構(gòu)建位置坐標(biāo)與信號強度的有效、可靠映射關(guān)系(Radio Map)，訓(xùn)練工作量較大。于是，為了減小訓(xùn)練難度，Ocana[7]使用K-means聚類算法證明，減少位置數(shù)以及在每個位置點的采樣時間對定位準(zhǔn)確度影響不大，證實了在一定程度上降低訓(xùn)練難度的可行性。在定位計算階段，為了降低匹配計算量，文獻(xiàn)[8]采用Median和K-means聚類算法，根據(jù)訓(xùn)練數(shù)據(jù)集的信號強度向量對實際物理位置進(jìn)行聚類，然后在在線定位階段，首先計算待定位節(jié)點的所屬聚類，然后在該聚類內(nèi)進(jìn)行細(xì)粒度的位置匹配計算。

為降低計算復(fù)雜度、提高定位精確度，本文利用仿射傳播聚類方法，從指紋定位基本原理出發(fā)，研究粗定位階段的聚類產(chǎn)生過程與匹配過程，并通過精定位階段的概率分布定位算法，對定位目標(biāo)進(jìn)行精確位置估計，以實現(xiàn)對目標(biāo)的快速、可靠定位。

本文組織結(jié)構(gòu)如下：第一節(jié)介紹了基于仿射傳播聚類的概率分布定位算法的基本流程；第二節(jié)對仿射傳播聚類用于數(shù)據(jù)庫預(yù)處理的算法步驟進(jìn)行了詳細(xì)討論；第三節(jié)利用在線階段的概率分布定位算法，實現(xiàn)對目標(biāo)的精定位過程；第四節(jié)是算法的實驗結(jié)果，比較和驗證了本文所提定位算法的精度有效性；第五節(jié)對全文進(jìn)行總結(jié)。

1 算法基本流程

指紋定位法分為兩個階段，離線建立階段和在線定位階段[9]。離線階段，在WLAN定位網(wǎng)絡(luò)的覆蓋區(qū)域內(nèi)采集信號樣本，建立覆蓋區(qū)域?qū)?yīng)的WLAN位置指紋圖。定位階段，又主要包括粗定位和精定位兩個步驟。

由于室內(nèi)電波傳播復(fù)雜的時變特性，在線階段的實時接收信號強度測量值與離線階段指紋庫存在差異。為了降低信號時變特性所帶來的影響，去除潛在異常值，本文首先利用仿射傳播聚類，對數(shù)據(jù)庫中參考點的RSS向量進(jìn)行分類，保證同類中樣本具有鄰近物理位置關(guān)系，且RSS向量間具有最大相似度[10]。在在線階段的粗定位過程中，聚類結(jié)果可將目標(biāo)位置估計區(qū)域縮小至一個聚類中。從而，在每個較小聚類中實現(xiàn)精定位，既降低了RSS時變特性所帶來的影響，又提高定位算法的計算效率。

近鄰傳播聚類的基本思想是通過消息傳遞，讓數(shù)據(jù)點相互選擇聚類質(zhì)心和聚類歸屬集合。近鄰傳播過程可看作相似度消息在雙向圖上按照一定概率進(jìn)行傳播，這個雙向圖模型描述任意兩個數(shù)據(jù)點之間相似度。通過消息迭代傳播，可最終從被聚類數(shù)據(jù)中挑選出聚類質(zhì)心和將每個數(shù)據(jù)點歸屬到某個最可能聚類集中。經(jīng)典的K均值聚類方法需要通過隨機方式選取初始類首，聚類結(jié)果很大程度上依賴于初始類首的選擇[11]，且容易陷入局部極值。相反，仿射傳播聚類則將數(shù)據(jù)集的所有N個樣本點作為候選類首，每個樣本點分別對應(yīng)一個實數(shù)，稱為偏向值(Preference)，偏向值越大，對應(yīng)樣本點被選為類首的可能性越大。由于仿射傳播聚類算法無需隨機選取類首，算法收斂速度較快且有效，其結(jié)果更符合數(shù)據(jù)拓?fù)浞植迹蚨蓪⑵鋺?yīng)用于指紋定位系統(tǒng)離線階段的數(shù)據(jù)處理。

確定性方法和概率分布方法是指紋定位法中兩種較為主要的定位方法。其中確定性方法在離線階段測量并保存一定采樣時間內(nèi)接收信號的強度平均值，并在在線階段利用信號間歐氏距離來計算不同信號強度間的匹配性，RADAR和Weyes系統(tǒng)均采用這類方法。而概率分布方法則測量并保存信號的概率分布，利用貝葉斯法則估計位置坐標(biāo)，其中，以Nibble和Horus系統(tǒng)最為典型。

不同于傳統(tǒng)位置指紋定位算法，本文提出的基于仿射傳播聚類的概率分布室內(nèi)定位算法，包括離線指紋預(yù)處理與在線粗精雙步定位兩個步驟。首先，在離線階段，對數(shù)據(jù)庫進(jìn)行仿射傳播聚類處理。然后，在在線階段，利用RSS測量值與指紋庫的匹配，經(jīng)過粗定位和精定位兩個過程，完成仿射聚類傳播算法與概率分布定位算法的結(jié)合，以實現(xiàn)對目標(biāo)的快速、可靠定位。算法的基本流程如圖1所示。

圖1 仿射傳播聚類概率定位算法的基本流程

2 仿射傳播聚類算法

為了降低室內(nèi)電波傳播特性所帶來的影響，去除潛在異常值，本文首先應(yīng)用仿射傳播聚類算法對數(shù)據(jù)庫中參考點所對應(yīng)的RSS向量進(jìn)行聚類，類信息將為在線階段的粗定位機制所用。

在近鄰傳播聚類中，參考點間相互傳遞兩類信息，即r(i， j)(Responsibility)和a(i， j)(Availability)，其中r(i， j)表示參考點RPj作為RPi的聚類中心的可信度，a(i， j)表示參考點RPi選擇參考點RPj作為其聚類中心的可信度。基于近鄰傳播聚類的參考點聚類算法的偽代碼流程如下所示：

輸入：任意兩個參考點RPi和RPj間的相似度s(i， j)

輸出：參考點聚類結(jié)果和相應(yīng)聚類中心

算法過程：

初始化：

a(i， j)=0

更新參考點之間的r值：

更新參考點之間的a值：

更新同一參考點自身之間的a值：

計算：

從而，利用仿射傳播聚類所形成的類首和對應(yīng)信號強度向量，本文首先利用基于類匹配的粗定位過程，將定位區(qū)域縮小至目標(biāo)的某個鄰近物理區(qū)域，即具有最大相似度的聚類中，并進(jìn)而在該類中實現(xiàn)精定位。

計算：

精定位只需在聚類Cj中實現(xiàn)即可。

3 概率分布定位算法

概率分布定位算法通過計算采集到的無線信號強度與位置指紋圖中各點的匹配概率，選取概率最大的參考點作為目標(biāo)的估計位置。在統(tǒng)計信號強度分布時，通過引入高斯信號概率函數(shù)，利用統(tǒng)計數(shù)學(xué)期望和方差來刻畫室內(nèi)定位環(huán)境中任意位置處的信號強度分布特征。對于實際采集的無線信號強度集合，通常認(rèn)為服從正態(tài)總體分布N(μ，σ2)，統(tǒng)計參量為μ和σ2。

似然函數(shù)為：

對數(shù)方程為：

似然方程組為：

于是，可以得到：

似然方程組有唯一解(μ*，σ*2)，而且它一定是最大值點，這是因為當(dāng)|μ|→∞或σ2→0或∞時，非負(fù)函數(shù)L(μ，σ2)→0。于是μ和σ2的最大似然估計為：

用X表示所有涉及的樣本，因為最大似然估計μ*和σ*2都是統(tǒng)計量，在抽取一定的樣本空間后，認(rèn)為計算的結(jié)果μ*和σ*2為真實值，并將μ*作為該點的信號強度。

在離線訓(xùn)練階段，位置指紋圖的構(gòu)建，首先在定位區(qū)域內(nèi)選取參考點，然后測量每個參考點處不同AP(Access Point)信號強度平均值ei和di方差，其中，i為不同AP標(biāo)識，與參考點對應(yīng)位置坐標(biāo)一起構(gòu)建位置指紋數(shù)據(jù)庫。

在在線定位階段，主要根據(jù)實時采集到的信號強度，與室內(nèi)定位區(qū)域內(nèi)位置指紋圖進(jìn)行匹配，以實現(xiàn)精定位。對于采集到的所有L個AP無線信號強度值{rssi，i=1，2，…，L}，利用公式(10)所示正態(tài)分布概率公式（取μ=ei、σ=di），計算Pi=(x，y)，即得到第i個AP在位置指紋圖中的點(x，y)的概率。

獲得所有AP的無線信號強度在地圖中的分布概率后，將采集到的無線信號強度值代入概率公式，并計算出各個參考點的概率P=(x，y)，如公式(11)所示。求得最大概率積，并把其對應(yīng)的坐標(biāo)(x，y)作為當(dāng)前位置估計坐標(biāo)。

4 實驗結(jié)果及分析

4.1 實驗設(shè)置

本文利用圖2所示物理環(huán)境，對包含9個AP的WLAN信號強度數(shù)據(jù)進(jìn)行采集，并通過與基于K均值聚類的K近鄰定位算法和概率分布定位算法，以及基于近鄰傳播聚類的K近鄰定位算法的定位性能比較，驗證本文所提基于近鄰傳播聚類的概率分布定位算法的有效性及可靠性。該實驗區(qū)域尺寸為66×22 m2，9個AP型號為Cisco WRT54G。

圖2 實驗場景布置

圖3 基于仿射傳播聚類的參考點聚類結(jié)果

圖4 測試軌跡

4.2 定位結(jié)果

圖3為利用仿射傳播聚類算法進(jìn)行數(shù)據(jù)庫預(yù)處理得到的結(jié)果。圓圈代表采集到的所有參考點，圓圈上的顏色代表不同聚類。圖中182個參考點被劃分為7個聚類，同一聚類參考點具有物理臨近性。

在實驗場景中隨機選擇一條定位曲線作為測試軌跡，如圖4所示。

在該定位測試軌跡上隨機選取81個物理位置點作為定位測試點。4種典型定位算法（K均值+K近鄰，K均值+概率分布，近鄰傳播+K近鄰，以及近鄰傳播+概率分布）的誤差結(jié)果如表1所示。此外，4種定位算法的累計誤差函數(shù)如圖5所示。

4.3 誤差分析

由上述實驗結(jié)果可知：基于近鄰傳播聚類的概率分布定位算法相對于基于K均值聚類的K近鄰定位算法和概率分布定位算法，以及基于近鄰傳播聚類的K近鄰定位算法，平均誤差分別降低了34.02%、28.3%和16.17%；本文所提算法誤差在3 m內(nèi)的置信概率為80.49%，顯著優(yōu)于其它3種典型定位算法的置信概率43.9%、62.2%和65.85%。

5 結(jié)束語

本文提出的基于近鄰傳播聚類的概率分布定位算法，與傳統(tǒng)室內(nèi)指紋定位算法相比，縮小了定位搜索空間，降低了算法計算開銷。實驗結(jié)果顯示本算法具有更高的定位精度。同時，本文所提定位算法不僅適用于WLAN室內(nèi)定位網(wǎng)絡(luò)，也同樣可應(yīng)用于其它基于信號強度的無線定位網(wǎng)絡(luò)，如WSN、RFID、移動蜂窩網(wǎng)絡(luò)等。然而，該算法的不足之處是在離線階段聚類完成后，各聚類集中的樣本點不完全具有物理臨近性。在下一步工作中，將繼續(xù)開展對網(wǎng)絡(luò)AP優(yōu)化布置的研究，并優(yōu)化聚類結(jié)果，進(jìn)而提高定位精度。

表1 4種典型定位算法的誤差比較

圖5 累計誤差函數(shù)

[1] XU Y Q， Lau S L， Kusber R， David K. An experimental investigation of indoor localization by unsupervised Wi-Fi signal clustering[A]. FutureNetw[C]. 2012， pp 1-10.

[2] Bahl P， Venkata N. Padmanabhan V N1 RADAR： an in-building RF-based user location and tracking system[J] Info Com 2000.

[3] Youssef M， Agrawala A. The horus WLAN location determination system[A]. Third International Conference on Mobile Systems，Applications， and Services (MobiSys2005)[C]. June 2005.

[4] Castro P， Chiu P， Kremenek T， et al. A probabilistic room location service for wireless networked environments[A]. UbiComp 2001[C]，2001. 18～34.

[5] Lang V， Xu K. A difference model for open WLAN enviroment based location service submitted[A]. IEEE Infocom[C]. 2006.

[6] 任福君， 倪鵬， 王殿君， 姜永成， 段云濤. 基于概率法的移動機器人無線網(wǎng)絡(luò)定位系統(tǒng)[J]. 科技導(dǎo)報. 2010，28(10).

[7] Ocana M. Bergasa L M， Sotelo M A， et al. Indoor robot location system using Wi-Fi signal measure and minimizing calibration effort[A]. Proc of IEEE International Symposium on Industrial Electronics[C]. Dubrovnik， Croatia， 2005.1545-1550.

[8] Nattapong S， Prashant V K. On clustering rss fingerprints for improving scalability of performance prediction of indoor positioning systems[A]. Proc of the 1st ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environment[C]. San Francisco， California， USA， 2008.61-66.

[9] Alsindi N， Chaloupka Z， Aweya J. Entropy-based location fingerprinting for WLAN systems[A]. Indoor Positioning and Indoor Navigation[C]. 2012， 1-7.

[10] Feng C， Au W S A ， Valaee S， Tan Z. Compressive sensing based positioning using RSS of WLAN access points[A]. INFOCOM 2010 Proceedings IEEE[C]. March 2010， pp. 1-9.

[11] 顧諍， 肖若貴. 基于AP聚類和頻繁模式挖掘的視頻摘要生成方法[J]. 計算機應(yīng)用與軟件. 2010，27(6).

Probability distribution-aided indoor positioning algorithm based on affinity propagation clustering

TANG Xiao-mou1; Tang Jia-jie2
(1 Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China; 2 School of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China)

With the rapid development of localization technology, the WLAN-based indoor localization becomes a new signif i cant research concern. This paper proposes a probability distribution-aided indoor positioning algorithm based on affinity propagation clustering. Compared to the conventional indoor positioning algorithms, this paper fi rst introduces the aff i nity propagation clustering to minimize the search space of reference points. Second, we use the probability distribution-aided algorithm to realize the accurate localization purpose. Aff i nity propagation clustering can effectively reduce the calculation cost of the probability distribution-aided localization algorithm, and thereby the systematic complexity can be effectively decreased. Experimental results show that the algorithm introduced in this paper not only performs better in accuracy, but realizes the fast and reliable localization.

WLAN indoor positioning; fi ngerprinting; aff i nity propagation clustering; RSS; probability distribution

TP391

A

1008-5599（2013）08-0062-06

2013-07-04