基于快速K-medoids聚類的WLAN室內(nèi)定位算法

陶 崢，宋 強(qiáng)，金許燁

（1.解放軍92124部隊(duì) 遼寧 大連116023；2.解放軍91550部隊(duì) 遼寧 大連116023；3.解放軍第210醫(yī)院 遼寧 大連116021）

基于快速K-medoids聚類的WLAN室內(nèi)定位算法

陶 崢1，宋 強(qiáng)2，金許燁3

（1.解放軍92124部隊(duì) 遼寧 大連116023；2.解放軍91550部隊(duì) 遼寧 大連116023；3.解放軍第210醫(yī)院 遼寧 大連116021）

在WLAN位置指紋定位技術(shù)中，K-means聚類算法一直被用于離線訓(xùn)練階段的參考點(diǎn)聚類，文中針對該法對噪聲數(shù)據(jù)和孤立點(diǎn)數(shù)據(jù)非常敏感等缺點(diǎn)，采用快速K-medoids聚類算法來對定位區(qū)域內(nèi)的參考點(diǎn)進(jìn)行聚類?？焖貹-medoids參考點(diǎn)聚類算法先選取初始類中心參考點(diǎn)，再通過迭代方式在每一類中選取與其他位置指紋信息距離之和最小的那條位置指紋信息對應(yīng)的參考點(diǎn)作為類中心參考點(diǎn)。最后通過實(shí)驗(yàn)數(shù)據(jù)分析表明，相比K-means參考點(diǎn)聚類算法，從平均誤差、標(biāo)準(zhǔn)差和累積誤差曲線圖3個方面可以看出快速K-medoids參考點(diǎn)聚類算法在去除噪聲數(shù)據(jù)和孤立點(diǎn)數(shù)據(jù)上具有更好的魯棒性，可有效地提升定位精度。

室內(nèi)定位；無線局域網(wǎng)；位置指紋；聚類算法；快速K中心點(diǎn)

隨著電腦網(wǎng)絡(luò)的興起，用戶共享諸如打印機(jī)、磁盤存儲器等設(shè)備的需求隨之增多。過去，這些共享需求基于有線連接，以以太網(wǎng)為最流行的手段，然而，自從無線連接問世以來，從方便性、可購性、移動性及生產(chǎn)力優(yōu)勢的角度分析，無線局域網(wǎng)（Wireless Local Area Networks，WLAN）被推到了網(wǎng)絡(luò)應(yīng)用的前列[1]。本論文聚焦WLAN其中的一項(xiàng)服務(wù)，就是如何在復(fù)雜多變的室內(nèi)環(huán)境下對人和物進(jìn)行高效定位。

位置信息在情景感知服務(wù)上有很多潛在的應(yīng)用[2]?；谖恢眯畔⒌那榫案兄?wù)利用客戶的位置信息提供很多有用的服務(wù)，比如，當(dāng)客戶行走在大型公用設(shè)施或購物商場內(nèi)的時候，他們的移動設(shè)備終端就可以在電子地圖上顯示客戶的實(shí)際位置。

文中研究的對象就是基于WLAN提供一種低成本、高精度的定位系統(tǒng)，讓設(shè)施的管理者可以向進(jìn)入設(shè)施內(nèi)的用戶提供基于位置信息的服務(wù)。本文將研究的焦點(diǎn)放在位置指紋定位 （Position Fingerprint Localization）技術(shù)上。

1 位置指紋定位技術(shù)

一般來說，基本的位置指紋定位系統(tǒng)劃分為兩個階段，離線訓(xùn)練階段和在線定位階段。在離線訓(xùn)練階段，將各參考點(diǎn)獲得來自各AP的的RSS向量作為位置指紋信息存入數(shù)據(jù)庫；在在線定位階段，利用模式匹配算法估算用戶的實(shí)際物理位置信息[3-4]。該技術(shù)的具體操作步驟如下所示：

1.1 位置指紋定位離線訓(xùn)練階段

1）從定位區(qū)域內(nèi)的各AP上采集RSS值

首先，用戶移動終端在每一個參考點(diǎn)從定位區(qū)域內(nèi)的R個AP獲取一組RSS值，將第j個參考點(diǎn)采集到RSS值，j=1，2，…，M，以及時間τ表示為dj（τ）=[d1，j（τ），…，dR，j（τ）]T，τ=1，…，t，t＞1，其中，di，j（τ）為j個參考點(diǎn)在時間點(diǎn)上接收到第i個AP的RSS值，t為采樣時段。

2）將位置指紋信息發(fā)送至數(shù)據(jù)庫

3）訓(xùn) 練

在離線訓(xùn)練階段的最后一步，服務(wù)器根據(jù)模式匹配算法的要求將在各參考點(diǎn)上采集的RSS信息訓(xùn)練成指定的指紋格式。最終，將位置指紋信息的訓(xùn)練結(jié)果存入數(shù)據(jù)庫。

1.2 位置指紋定位在線定位階段

1）實(shí)時采集RSS值

當(dāng)用戶請求獲取物理位置信息時，用戶移動終端先在未知位置點(diǎn)[x，y]上從定位區(qū)域內(nèi)的各AP采集實(shí)時RSS值。

2）將實(shí)時采樣發(fā)送至服務(wù)器

服務(wù)器接收到來自用戶移動終端的實(shí)時RSS信息，并將實(shí)時RSS信息訓(xùn)練成指定的指紋格式。

3）執(zhí)行模式匹配算法

在這一步，服務(wù)器通過模式匹配算法比較用戶實(shí)時的位置指紋信息和數(shù)據(jù)庫中的位置指紋信息估算用戶的實(shí)際物理坐標(biāo)。

4）發(fā)送物理坐標(biāo)信息給用戶移動終端

一旦服務(wù)器完成了用戶物理坐標(biāo)的估算，服務(wù)器便將估算結(jié)果[x，y]T發(fā)送至用戶移動終端，物理位置信息將在用戶移動終端上通過可視界面顯示。

2 基于快速K-medoids聚類的位置指紋定位算法

在WLAN位置指紋定位工程應(yīng)用中，利用加權(quán)K近鄰[5]、概率分布[6]、人工神經(jīng)網(wǎng)絡(luò)[7]等經(jīng)典的模式匹配算法都可以取得良好的定位性能。但是這些算法也有明顯的缺點(diǎn)：

加權(quán)K近鄰法等模式匹配算法在在線定位階段都需要計(jì)算待定位點(diǎn)位置指紋信息和所有參考點(diǎn)位置指紋信息之間的相似度，訓(xùn)練時間長短和參考點(diǎn)的數(shù)量成正比。因此在參考點(diǎn)數(shù)量眾多的情況下，這些算法的運(yùn)行效率就會大幅度下降，幾乎失去實(shí)用性[8]。

針對這一問題，可以應(yīng)用聚類算法對加權(quán)K近鄰算法等模式匹配算法進(jìn)行改進(jìn)。以達(dá)到減小計(jì)算開銷的目的。

2.1 聚類算法在指紋定位中的應(yīng)用

假設(shè)定位區(qū)域內(nèi)有M條位置指紋信息，定義M為不用聚類算法時的搜尋成本，K為定位區(qū)域內(nèi)的位置指紋信息被劃分為簇的數(shù)量，那么在在線定位階段用戶設(shè)備的平均搜尋成本如式（1）所示：

考慮到以上所述原因，很多學(xué)者提出用聚類算法來優(yōu)化在線定位階段的模式匹配算法。其中，研究最多的是K-means聚類算法。

K-means聚類算法是最簡單的聚類算法之一，該聚類算法通常應(yīng)用在類中心元素和其它元素都具有相同特征的情況下，這樣我們就可以輕易獲得兩個元素之間的距離[9]。文獻(xiàn)[10]、[11]和[12]均在離線訓(xùn)練階段利用K-means聚類算法對定位區(qū)域內(nèi)的位置指紋信息進(jìn)行聚類。

但是K-means聚類算法在位置指紋定位領(lǐng)域也有自身的弊端，主要體現(xiàn)為利用參考點(diǎn)位置指紋信息均值的方法來更新類中心可能會導(dǎo)致定位系統(tǒng)對噪聲數(shù)據(jù)和孤立點(diǎn)數(shù)據(jù)非常敏感[13-14]。

2.2 引入快速K-medoids聚類算法

為了提高定位系統(tǒng)的運(yùn)算效率和對環(huán)境噪聲的處理能力，文中創(chuàng)新性的將快速K-medoids聚類算法[15]引入室內(nèi)定位系統(tǒng)中來改進(jìn)K-means聚類算法的不足，定位系統(tǒng)分為離線訓(xùn)練和在線定位兩個階段。

2.2.1 離線訓(xùn)練階段

在離線訓(xùn)練階段，我們應(yīng)用快速K-medoids聚類算法依照定位區(qū)域內(nèi)各參考點(diǎn)的位置指紋信息對參考點(diǎn)進(jìn)行聚類，方法如下所示：

假設(shè)在定位環(huán)境中有M個參考點(diǎn)，每個參考點(diǎn)對應(yīng)其接收來自R個AP的RSS值，我們可以將M個參考點(diǎn)分成Koffline個簇（在聚類算法里，我們?yōu)榱藚^(qū)分離線訓(xùn)練階段的的簇?cái)?shù)和在線定位階段的預(yù)定位參考點(diǎn)數(shù)，將離線訓(xùn)練階段的簇?cái)?shù)定義為Koffline，將在線定位階段的預(yù)定位參考點(diǎn)數(shù)定義為Konline。），其中Koffline的確定方法如式（2）所示：

我們利用的精確值向下取整作為簇?cái)?shù)就能夠利用聚類算法最大程度的降低在線定位階段用戶移動終端的計(jì)算負(fù)擔(dān)[12]。

我們定義第j個參考點(diǎn)接收來自第i個AP的RSS值為dij（i=1，…，R；j=1，…，M）。歐式距離通常被用作相異度的測量，在定位環(huán)境中，參考點(diǎn)h和參考點(diǎn)j分別對應(yīng)RSS向量之間的歐式距離如式（3）所示：

對定位環(huán)境中的參考點(diǎn)進(jìn)行快速K-medoids聚類，聚類過程包含以下3個步驟：

第一步：在參考點(diǎn)中選擇初始類中心參考點(diǎn)

1）在定位環(huán)境中計(jì)算每兩個參考點(diǎn)RSS向量之間的歐式距離。

2）計(jì)算vj（參考點(diǎn)j），方法如式（4）所示

3）將vj按升序排列，挑選Koffline個vj值最小的參考點(diǎn)作為初始類中心參考點(diǎn)。

4）將定位環(huán)境中每一個參考點(diǎn)都分到與它最近的初始類中心參考點(diǎn)所屬的類中。

5）計(jì)算每一個類中所有參考點(diǎn)位置指紋信息與他們類中心參考點(diǎn)位置指紋信息的歐式距離之和。

第二步：更新類中心參考點(diǎn)

在每一個類中尋找新的類中心參考點(diǎn)，方法是計(jì)算類中每一個參考點(diǎn)位置指紋信息和所有其它參考點(diǎn)位置指紋信息的歐式距離之和，挑選類中與其它參考點(diǎn)位置指紋信息之和為最小的那個參考點(diǎn)作為類中心參考點(diǎn)，并用新的類中心參考點(diǎn)取代原來的類中心參考點(diǎn)。

第三步：分配參考點(diǎn)至它們的類中心參考點(diǎn)

1）分配每一個參考點(diǎn)至離它們位置指紋信息最近的那個類中心參考點(diǎn)。

2）計(jì)算所有參考點(diǎn)位置指紋信息和它們類中心參考點(diǎn)位置指紋信息之和，如果其和不變，那么算法將會停止。否則重回第二步繼續(xù)更新類中心參考點(diǎn)。

2.2.2 在線定位階段

在這里我們以加權(quán)K近鄰法這個最經(jīng)典的模式匹配算法為例說明在線定位階段的具體步驟，因此，整個算法可以命名為：Fast K-medoids clustered WKNN位置指紋定位算法。

第一步：劃定待定位點(diǎn)所屬的類。

定義待定位點(diǎn)位置指紋信息和各類中心參考點(diǎn)位置指紋信息的歐式距離，計(jì)算方式如式（5）所示：

其中si為待定位點(diǎn)用戶移動終端測到第i個AP的信號強(qiáng)度，dij（medoids）為位置指紋庫中第 j個類中心參考點(diǎn)接收到第i個AP的信號強(qiáng)度。

第二步：在待定位點(diǎn)所屬的類中確定其物理坐標(biāo)。

定義待定位點(diǎn)位置指紋信息和其所屬類中各參考點(diǎn)位置指紋信息的歐式距離，計(jì)算方式如式（6）所示：

其中si為待定位點(diǎn)用戶移動終端測到第i個AP的信號強(qiáng)度，dij（cluster）為待定位點(diǎn)所屬類中第 j個參考點(diǎn)接收到第i個AP的信號強(qiáng)度。

利用Lj（cluster）搜索待定位點(diǎn)所屬類中的每一個參考點(diǎn)的位置指紋信息并找到距離待定位點(diǎn)位置指紋信息最近的 Konline（Konline≥2）個參考點(diǎn)作為預(yù)定位參考點(diǎn)，最終結(jié)果計(jì)算方式如式（7）所示：

其中wj為預(yù)定位參考點(diǎn)j的權(quán)重因子，計(jì)算方式如式（8）所示：

3 實(shí)驗(yàn)驗(yàn)證

定位實(shí)驗(yàn)在大連創(chuàng)新園大廈C區(qū)2樓走廊處進(jìn)行，實(shí)驗(yàn)區(qū)域包括1個長走廊，2個短走廊，一些辦公室和實(shí)驗(yàn)室。該區(qū)域電器設(shè)備較多，工作日課間人員流動量較大。整個定位區(qū)域的環(huán)境示意圖如圖1所示。

圖1 定位實(shí)驗(yàn)環(huán)境示意圖

本次實(shí)驗(yàn)的目是用實(shí)驗(yàn)結(jié)果驗(yàn)證快速 K-medoids聚類算法在位置指紋定位中的應(yīng)用效果。

為了實(shí)現(xiàn)上述目的，我們在圖1中網(wǎng)格區(qū)域內(nèi)按圖2所示布置參考點(diǎn)，其中左下角為坐標(biāo)原點(diǎn)，箭頭所指方向即為X軸和Y軸方向，空心圓點(diǎn)即為定位區(qū)域內(nèi)的參考點(diǎn)，坐標(biāo)內(nèi)每一個正方形方格的邊長為0.6m。在定位區(qū)域內(nèi)一共布置24個參考點(diǎn)。在離線訓(xùn)練階段采樣頻率設(shè)置為1次/秒，在每一個參考點(diǎn)處采集 RSS信息，在在線定位階段分別在（1.2，1.2）、 （2.4，1.2）、 （3.6，1.2）、 （4.8，1.2）、（6.0，1.2）、 （7.2，1.2）、 （8.4，1.2）、 （9.6，1.2）、（10.8，1.2）、（12.0，1.2）、（13.2，1.2）這11個待定位點(diǎn)逐一采集RSS信息。

圖2 參考點(diǎn)布置方法示意圖

按照 2.2.1和 2.2.2的方法將 Fast K-medoids clustered WKNN定位算法的得出的定位結(jié)果和K-means clustered WKNN定位算法得出的定位結(jié)果從定位精度方面比較。

定位精度方面，主要比較平均定位誤差、標(biāo)準(zhǔn)差和累積分布函數(shù)，比較的結(jié)果如表1和圖3所示。

表1 平均誤差及標(biāo)準(zhǔn)差對比

圖3 累積誤差曲線對比

從表 1和圖 3可以看出，相比 K-means clustered WKNN 算法，F(xiàn)ast K-medoids clustered WKNN算法擁有更高的定位精度。

4 結(jié) 論

快速K-medoids聚類算法和WKNN算法結(jié)合的位置指紋定位算法相比 K-means聚類算法和WKNN算法相結(jié)合的位置指紋定位算法擁有更高的定位精度，在WLAN指紋定位的中可以用快速K-medoids聚類替代K-means聚類來對參考點(diǎn)進(jìn)行聚類，快速K-medoids聚類可以降低在線階段算法復(fù)雜度，并擁有超越K-means聚類算法的定位精度。

[1]Crow B P，Widjaja I，Kim J G，et al.IEEE 802.11 wireless local area networks[J].Communications Magazine，IEEE，1997，35（9）:116-126.

[2]KolodziejK W， Hjelm J.Localpositioning systems:LBS applications and services[M].CRC press，2006.

[3]Wang L，Wong W C.A RSS based statistical localization algorithm in WLAN[C].Signal Processing and Communication Systems（ICSPCS），2012 6th International Conference on.IEEE，2012:1-5.

[4]Bshara M，Orguner U，Gustafsson F，et al.Fingerprinting localization in wireless networks based on received-signal-strength measurements:A case study on WiMAX networks[J].Vehicular Technology，IEEE Transactions on，2010，59（1）:283-294.

[5]Yang L，Chen H，Cui Q，et al.Probabilistic-KNN:A Novel Algorithm for Passive Indoorlocalization Scenario [C]//Vehicular Technology Conference （VTC Spring）， 2015 IEEE 81st. IEEE，2015:1-5.

[6]Kasebzadeh P，Granados G S，Lohan E S.Indoor localization via WLAN path-lossmodelsand Dempster-Shafer combining[C]//Localization and GNSS（ICL-GNSS），2014 International Conference on.IEEE，2014:1-6.

[7]Borenovi M N，Ne kovi A M.Positioning in WLAN environment by use of artificial neural networks and space partitioning [J].annals of telecommunications-annales des télécommunications，2009，64（9-10）:665-676.

[8]Ding G，Zhang J，Zhang L，et al.Overview of received signal strength based fingerprinting localization in indoor wireless LAN environments[C]// Microwave，Antenna，Propagation and EMC Technologies for Wireless Communications（MAPE），2013 IEEE 5th InternationalSymposium on. IEEE，2013:160-164.

[9]Wishart D.K-means Analysis[J]//Encyclopedia of Statistics in Behavioral Science，2005.

[10]Laoudias C，Kemppi P，Panayiotou C G.Localization using radial basis function networks and signal strength fingerprints in WLAN [C]//Global telecommunications conference，2009.GLOBECOM 2009.IEEE.IEEE，2009:1-6.

[11]Altintas B，Serif T.Improving rss-based indoor positioning algorithm via k-means clustering[C]// WirelessConference2011-SustainableWireless Technologies（European Wireless），11th European. VDE，2011:1-5.

[12]Bai S，Wu T.Analysis of K-Means algorithm on fingerprint based indoor localization system[C]// Microwave，Antenna，Propagation and EMC Technologies for Wireless Communications（MAPE），2013 IEEE 5th InternationalSymposium on. IEEE，2013:44-48.

[13]Singh S S，Chauhan N C.K-means v/s K-medoids: A Comparative Study[C]//National Conference on RecentTrendsin Engineering& Technology. 2011，13.

[14]Gullo F，Ponti G，Tagarelli A.Clustering uncertain data via k-medoids[M].Scalable Uncertainty Management.Springer Berlin Heidelberg，2008: 229-242.

[15]Park H S，Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications，2009，36（2）:3336-3341.

WLAN indoor localization algorithm based on fast K-medoids clustering

TAO Zheng1，SONG Qiang2，JIN Xu-ye3
（1.PLA 92124 Unit，Dalian 116023，China；2.PLA 91550 Unit，Dalian 116023，China；3.No.210 Hospital of PLA，Dalian 116021，China）

In WLAN position fingerprint localization algorithms，K-means clustering algorithm is always used to cluster the RPs in the offline training phase.Aiming at the fact that it is very sensitive to noise and outliers，this thesis uses Fast K-medoids algorithm to cluster the RP.In the offline phase，the Fast K-medoids RP clustering algorithm selects initial medoids among the RP fingerprints first，then finds the medoid of each cluster，which is the fingerprint minimizing the total distance to other fingerprints in its cluster by using iterative method.Finally，the experiment indicates that Fast K-medoids based position fingerprint localization algorithm has greater robustness and localization accuracy than K-means based position fingerprint localization algorithm in the view of average error，STD and CDF.

indoor localization；WLAN；fingerprint；clustering；fast K-medoids

TN92

：A

：1674－6236（2017）06-0109-05

2016-03-10稿件編號：201603125

陶 崢（1984—），男，遼寧大連人，碩士，助理工程師。研究方向：通信技術(shù)。