唐笑謀，唐佳杰

（1 重慶郵電大學(xué)重慶市移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2. 重慶工商大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，重慶 400067）

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

唐笑謀1，唐佳杰2

（1 重慶郵電大學(xué)重慶市移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2. 重慶工商大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，重慶 400067）

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

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

近年來，隨著數(shù)據(jù)業(yè)務(wù)的快速增加，人們對(duì)定位與導(dǎo)航的需求日益增大，尤其對(duì)于復(fù)雜、動(dòng)態(tài)室內(nèi)環(huán)境下的用戶位置判斷。IEEE 802.11無線局域網(wǎng)(WLAN)標(biāo)準(zhǔn)的問世，讓無線通信市場(chǎng)需求迅猛增長(zhǎng)[1]。WLAN接入點(diǎn)(AP)定時(shí)發(fā)送信標(biāo)信息中所含的接收信號(hào)強(qiáng)度(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)定位過程簡(jiǎn)單，但精度不高；Horus系統(tǒng)采用信號(hào)強(qiáng)度的概率分布函數(shù)，作為位置指紋的基本信息，精度較高，但復(fù)雜度也較高；Nibble采用信噪比作為信號(hào)空間樣本，而非RSS，精度不高，但其定義的目標(biāo)位置點(diǎn)粒度較大，一般被定義為整個(gè)房間或者重要的位置附近區(qū)域；Weyes系統(tǒng)不直接采用RSS，而采用差值模型，誤差值在不同設(shè)備之間差別較大，精度不高。

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

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

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

1 算法基本流程

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

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

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

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

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

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

2 仿射傳播聚類算法

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

在近鄰傳播聚類中，參考點(diǎn)間相互傳遞兩類信息，即r(i， j)(Responsibility)和a(i， j)(Availability)，其中r(i， j)表示參考點(diǎn)RPj作為RPi的聚類中心的可信度，a(i， j)表示參考點(diǎn)RPi選擇參考點(diǎn)RPj作為其聚類中心的可信度?；诮弬鞑ゾ垲惖膮⒖键c(diǎn)聚類算法的偽代碼流程如下所示：

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

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

算法過程：

初始化：

a(i， j)=0

更新參考點(diǎn)之間的r值：

更新參考點(diǎn)之間的a值：

更新同一參考點(diǎn)自身之間的a值：

計(jì)算：

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

計(jì)算：

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

3 概率分布定位算法

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

似然函數(shù)為：

對(duì)數(shù)方程為：

似然方程組為：

于是，可以得到：

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

用X表示所有涉及的樣本，因?yàn)樽畲笏迫还烙?jì)μ*和σ*2都是統(tǒng)計(jì)量，在抽取一定的樣本空間后，認(rèn)為計(jì)算的結(jié)果μ*和σ*2為真實(shí)值，并將μ*作為該點(diǎn)的信號(hào)強(qiáng)度。

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置

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

圖2 實(shí)驗(yàn)場(chǎng)景布置

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

圖4 測(cè)試軌跡

4.2 定位結(jié)果

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

在實(shí)驗(yàn)場(chǎng)景中隨機(jī)選擇一條定位曲線作為測(cè)試軌跡，如圖4所示。

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

4.3 誤差分析

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

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

圖5 累計(jì)誤差函數(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] 任福君， 倪鵬， 王殿君， 姜永成， 段云濤. 基于概率法的移動(dòng)機(jī)器人無線網(wǎng)絡(luò)定位系統(tǒng)[J]. 科技導(dǎo)報(bà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]. 計(jì)算機(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