基于改進(jìn)聚類與WKP的Wi-Fi室內(nèi)定位算法

葉瀚云,何 軍

(四川大學(xué)計(jì)算機(jī)學(xué)院,四川 成都 610065)

1 引言

隨著無線技術(shù)的快速發(fā)展與智能設(shè)備終端的普及,現(xiàn)在使用位置定位服務(wù)的應(yīng)用也越來越多,基于位置服務(wù)的APP也漸漸滲透到日常生活與各個(gè)生產(chǎn)之中[1]。從現(xiàn)有的研究來看,較為常見的定位方法主要有基于紅外線,超聲波,藍(lán)牙,射頻識別,超寬帶與Wi-Fi的室內(nèi)定位。其中,Wi-Fi設(shè)備分布廣泛,部署成本低,大部分的移動智能設(shè)備可以很方便地連接上Wi-Fi網(wǎng)絡(luò)。這就為Wi-Fi定位提供了極大的便利。因此以,基于Wi-Fi的室內(nèi)定位是實(shí)現(xiàn)室內(nèi)定位最為簡便的方法之一。

現(xiàn)階段的基于Wi-Fi的室內(nèi)定位方法主要分為以下幾種:基于角度的定位方法(AOA),基于到達(dá)時(shí)間的方法(TOA),基于到達(dá)時(shí)間差的方法(TDOA)以及基于信號強(qiáng)度的方法(RSSI)[2],前三種方法需要部署高精度的天線和高精度的時(shí)鐘,而最后一種基于信號強(qiáng)度的方法不需要部署額外的硬件,僅需要無線AP即可完成定位。

基于信號強(qiáng)度的方法又可以分為兩種,基于傳播模型的方法和基于位置指紋的方法,前者是建立無線信號的傳播模型,分析接收信號強(qiáng)度與距離之間的關(guān)系,使用幾何方法確定待定目標(biāo)的位置。基于位置指紋的方法不需要推導(dǎo)出信號的傳播模型,而是在前期部署多個(gè)樣本點(diǎn)和無線信號發(fā)射點(diǎn)(AP),多個(gè)AP在某一個(gè)樣本點(diǎn)的信號強(qiáng)度組成一個(gè)信號強(qiáng)度矢量,這些信號強(qiáng)度矢量就被稱為位置指紋,這些指紋在整個(gè)區(qū)域內(nèi)具有唯一性[3]。通過比較測試點(diǎn)與樣本點(diǎn)位置指紋的相似度來確定最終的定位結(jié)果[4]。由于信號傳播的不穩(wěn)定性與不確定性,大部分情況下基于位置指紋的方法的定位精度優(yōu)于基于傳播模型的方法[4]。

為了提高基于位置指紋方法的定位精度,國內(nèi)外進(jìn)行了許多研究,文獻(xiàn)[6]提出了一種基于誤差修正的聲源目標(biāo)混合定位算法,來解決因多徑傳播效應(yīng)等因素導(dǎo)致的低穩(wěn)定性問題。實(shí)驗(yàn)結(jié)果表明,簡單地使用信號強(qiáng)度差值的倒數(shù)作為權(quán)值,并不符合Wi-Fi在空間中分布不均的特性。文獻(xiàn)[7]則通過位置距離,比較聚類中心與接收點(diǎn)之間的信號距離和樣本點(diǎn)的數(shù)目,使用K臨近算法進(jìn)行位置推斷。雖然聚類算法拋棄了一些不必要的樣本點(diǎn),但是有時(shí)候各個(gè)聚類的樣本點(diǎn)數(shù)量會不同,該聚類的樣本點(diǎn)數(shù)量過少的話,K值不應(yīng)該取太大,而該聚類中樣本點(diǎn)過多的話,K值取太小又會影響到定位精度。同時(shí),由于信號強(qiáng)度的波動可能會受到多重影響,聚類的區(qū)分不應(yīng)該以信號強(qiáng)度為唯一的依據(jù)。

因此,在K-means聚類加權(quán)KNN算法的基礎(chǔ)上,提出根據(jù)實(shí)際環(huán)境調(diào)整聚類,從而來動態(tài)調(diào)整加權(quán)K臨近方法的K值的算法。前期通過高斯濾波盡量減少信號波動帶來的誤差,后期則通過改進(jìn)的加權(quán)K臨近算法得到定位結(jié)果。

2 基于位置指紋定位的一般原理

2.1 離線階段

在基于位置指紋的定位方法中,分為離線階段與在線階段。離線階段是在定位區(qū)域內(nèi)測量N個(gè)樣本點(diǎn)的位置指紋,第i個(gè)參考點(diǎn)記作Ni,假設(shè)參考點(diǎn)Ni處檢測到了m個(gè)AP的信號,則Ni的位置指紋就記作

(m,RSSIi1,RSSIi2,RSSIi3…RSSIim,xi,yi)

(1)

式中,xi、yi為該參考點(diǎn)的位置坐標(biāo)。在錄入到數(shù)據(jù)庫中時(shí),會將該區(qū)域內(nèi)所有能探測到的AP信息按照順序排列。

由于Wi-Fi信號傳輸?shù)膹?fù)雜性,所以在錄入信號強(qiáng)度信息時(shí),會進(jìn)行多次測量,并使用高斯濾波,剔除不符合實(shí)際情況的偶然誤差。

2.2 在線階段

在線定位階段中,測量點(diǎn)會讀取周圍AP的信號強(qiáng)度,進(jìn)行高斯濾波后,按照一定順序排列,然后根據(jù)排列后所產(chǎn)生的位置指紋與各個(gè)樣本點(diǎn)進(jìn)行比較。加權(quán)KNN算法將計(jì)算測量點(diǎn)與樣本點(diǎn)的信號距離,信號距離的計(jì)算公式為

(2)

其中,RSSIj表示第j個(gè)AP的信號強(qiáng)度。由于信號傳播不穩(wěn)定,測試點(diǎn)可能接收不到m個(gè)AP信號,有時(shí)候會多于m,而有時(shí)候又會少于m,并且在同一條件下,取多個(gè)樣本點(diǎn)的位置指紋進(jìn)行計(jì)算的話,計(jì)算出的位置距離可能與實(shí)際的距離不符。所以,當(dāng)測試點(diǎn)掃描到n個(gè)AP的信號時(shí),使得N=min(m,n),這樣所有的測試點(diǎn),都直接使用前N個(gè)信號的平均信號強(qiáng)度,避免了這種誤差。

用這個(gè)距離作為權(quán)值,將各個(gè)樣本點(diǎn)的位置進(jìn)行加權(quán)計(jì)算。權(quán)值的計(jì)算如式(3)所示

(3)

其中,ωi為當(dāng)前第i個(gè)樣本點(diǎn)對該測試點(diǎn)的權(quán)值,K是KNN算法中需要加權(quán)平均計(jì)算的樣本點(diǎn)的數(shù)量。

在室內(nèi)環(huán)境的情況下,加權(quán)KNN算法的精度依賴該區(qū)域中樣本點(diǎn)的數(shù)量與K值的大小。一般來說,一個(gè)區(qū)域內(nèi)的樣本點(diǎn)數(shù)量越多,K值越大,運(yùn)算最后得到的結(jié)果也就越精確,但是這也會增大計(jì)算量,而且當(dāng)K取值過大時(shí),會使用與測試點(diǎn)相距甚遠(yuǎn)的樣本點(diǎn)參與計(jì)算,這無疑增大了最后定位結(jié)果的誤差[8]。為了解決這個(gè)問題,可以選擇在離線階段將各個(gè)樣本點(diǎn)進(jìn)行聚類,在線階段通過在同一個(gè)聚類進(jìn)行計(jì)算,減小誤差與計(jì)算量,其中K-means聚類算法使用比較廣泛。

最后則根據(jù)式(4)可以求得測試點(diǎn)的位置

(4)

3 改進(jìn)加權(quán)KNN算法

3.1 與實(shí)際建筑環(huán)境相結(jié)合的聚類算法

一般來說,在一個(gè)聚類里面的樣本點(diǎn)應(yīng)該不僅僅在信號上相似,并且在實(shí)際建筑環(huán)境中也應(yīng)該相鄰,這樣一個(gè)聚類里的樣本點(diǎn)的關(guān)聯(lián)性才會高,定位結(jié)果才會較為精確且符合實(shí)際情況。雖然K-means算法能夠根據(jù)信號強(qiáng)度,將有相似位置指紋的采樣點(diǎn)會分到一個(gè)聚類里面,但是由于信號強(qiáng)度的不穩(wěn)定性,K-means算法可能會將兩個(gè)不同區(qū)域的采樣點(diǎn)劃分到一個(gè)聚類里面[9]。

如圖1所示,在一個(gè)室內(nèi)環(huán)境內(nèi)有一堵半開放的墻壁,墻壁的兩側(cè)均有2個(gè)樣本點(diǎn),而測試點(diǎn)位于墻壁的左側(cè)。由于信號強(qiáng)度的波動,聚類算法將這4個(gè)樣本點(diǎn)劃在了一個(gè)聚類里面,然后定位后的結(jié)果卻在墻壁里面,這是在現(xiàn)實(shí)情況下不可能發(fā)生的事情[10]。

圖1 不考慮實(shí)際建筑環(huán)境的聚類

造成這種情況的原因是將墻壁另一側(cè)的樣本點(diǎn)進(jìn)行了加權(quán)計(jì)算。解決的方法就是將這個(gè)聚類里的樣本點(diǎn)重新按照實(shí)際的建筑環(huán)境進(jìn)行調(diào)整。

為了保證一個(gè)聚類里的采樣點(diǎn)能夠在地理空間上也相鄰,采用以下方法對樣本點(diǎn)進(jìn)行聚類:

1)樣本點(diǎn)采樣完成后,對所有樣本點(diǎn)進(jìn)行K-means聚類;

2)觀察所有的聚類,如果發(fā)現(xiàn)一個(gè)聚類里有建筑環(huán)境上不相鄰的采樣點(diǎn),就將這些不相鄰的點(diǎn)分配到旁邊的聚類中,使每一個(gè)聚類中的采樣點(diǎn)都在建筑環(huán)境上相鄰;

因此,離線階段在進(jìn)行K-means聚類的時(shí)候,應(yīng)該在信號強(qiáng)度聚類的基礎(chǔ)上,根據(jù)實(shí)際的建筑環(huán)境進(jìn)行調(diào)整。

3.2 根據(jù)聚類內(nèi)部采樣點(diǎn)的個(gè)數(shù)改變K值

加權(quán)KNN算法中的K值的大小直接影響了最后定位結(jié)果的精確程度,即使在一個(gè)聚類里,K值的取值也要合適。

同時(shí),K-means聚類算法將各個(gè)樣本點(diǎn)劃分到不同的聚類里面,但是各個(gè)聚類里樣本點(diǎn)的數(shù)量和區(qū)域大小卻不一定相同,如圖2所示,左邊的聚類樣本點(diǎn)的數(shù)量明顯比右邊兩個(gè)聚類多,面積也比左邊的都大。在這種情況下,不應(yīng)該使用一個(gè)固定的K值。需要對K值進(jìn)行調(diào)整。

圖2 同一區(qū)域內(nèi)不同的聚類

在傳統(tǒng)的KNN算法里面,K值是一開始就被確定的,K值的大小與測試點(diǎn)所在的聚類無關(guān),這是一個(gè)不合理的現(xiàn)象。固定大小的K值可能對一個(gè)大的聚類來說太小,而對于一個(gè)小的聚類來說太大。因此,根據(jù)加權(quán)的K臨近算法得到的K值也應(yīng)該根據(jù)聚類里樣本點(diǎn)數(shù)量和區(qū)域面積大小而作出動態(tài)調(diào)整。

在K值調(diào)整中,可以在樣本點(diǎn)數(shù)目較多,聚類區(qū)域面積較大的時(shí)候使用較大的K值,從而在較大的區(qū)域中提升最后定位結(jié)果的精度;而在樣本點(diǎn)數(shù)目較少,聚類區(qū)域面積較小的時(shí)候使用較小的K值,從而在較小的區(qū)域內(nèi)減少計(jì)算量。

在離線階段的聚類完成之后,可以分析這些聚類中的樣本點(diǎn)的數(shù)目以及聚類區(qū)域大小,找到其中樣本點(diǎn)和區(qū)域大小都居中的一個(gè)聚類,將這個(gè)聚類以及所有的樣本點(diǎn)數(shù)量和區(qū)域面積都大于這個(gè)聚類的聚類稱為大聚類,而所有的樣本點(diǎn)和區(qū)域面積都小于這個(gè)聚類的聚類稱為小聚類。在大聚類中會盡量選取比較大的K值,在小聚類中會盡量選取比較小的K值。

為了確定K值在不同聚類中的不同取值,使用以下方法計(jì)算K值

1)觀察該聚類屬于大聚類還是小聚類,原則上K值的理論上限不應(yīng)該設(shè)得過大,所以選取類樣本點(diǎn)數(shù)目的80%作為該聚類的K值的理論上限,并取所有聚類的K初值為1

2)假設(shè)該聚類一共有j個(gè)樣本點(diǎn),對于聚類中的某一個(gè)樣本點(diǎn),將其視為測試點(diǎn),其余樣本點(diǎn)仍然是樣本點(diǎn),計(jì)算在該測試點(diǎn)下的平均誤差。遍歷所有的樣本點(diǎn)都會成為一次測試點(diǎn),求得在該K值下總體的平均誤差為

(5)

3)判斷K值是否已經(jīng)到達(dá)理論上限,如果未到達(dá),則將K值加1,重復(fù)第2)步,否則進(jìn)行第4)步

4)在所有K值情況下得到的所有平均誤差dk中,找到最小的d,即d=min(d1,d2,…,dk),找到d所對應(yīng)的K值,即為該聚類所對應(yīng)的K值。

這樣,通過在修正后的聚類里使用可變化K值的加權(quán)K臨近算法,可以根據(jù)不同聚類的特性,提升算法的定位精度,同時(shí)也可以減少部分情況下的算法的計(jì)算量。

圖3表示了改進(jìn)的加權(quán)K臨近的算法流程。

圖3 改進(jìn)K臨近算法的流程圖

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

為了驗(yàn)證文中改進(jìn)定位方法的性能,在某一室內(nèi)環(huán)境進(jìn)行Wi-Fi室內(nèi)定位實(shí)驗(yàn)。室內(nèi)環(huán)境如圖4所示。

圖4 室內(nèi)試驗(yàn)環(huán)境

該室內(nèi)環(huán)境共有4個(gè)房間,從左到右分別標(biāo)記為房間1,房間2,房間3與房間4。其中房間1與房間2,房間3與房間4之間各有一堵較厚的墻壁,房間2與房間3之間有一堵較薄的墻壁。在每個(gè)房間的最左上角開始,上下和左后都分別每隔1m處設(shè)置參考點(diǎn),盡量將參考點(diǎn)設(shè)置為均勻分布,并隨機(jī)設(shè)置測試點(diǎn)。一共布置了8個(gè)無線AP,64個(gè)樣本點(diǎn)以及20個(gè)測試點(diǎn)。

實(shí)驗(yàn)采用手機(jī)進(jìn)行信號采集。手機(jī)型號為小米Note3,每個(gè)無線AP都設(shè)置為2.4G。每個(gè)樣本點(diǎn)會采集10次數(shù)據(jù),并根據(jù)高斯濾波后的值取平均,構(gòu)成最后的位置指紋。

使用K-means方法聚類后的效果如圖5所示。

圖5 K-means方法的結(jié)果

通過聚類結(jié)果發(fā)現(xiàn),房間2和房間3中有的樣本點(diǎn)被劃分到了同一個(gè)聚類里面,原因可能是房間2與房間3之間的墻壁不夠厚,導(dǎo)致信號強(qiáng)度之間的差異不夠引起的。

所以,根據(jù)實(shí)際的建筑環(huán)境,將聚類調(diào)整如圖6所示。

圖6 調(diào)整后的聚類

接下來,對于每個(gè)聚類,依照前面所用的算法,查找每個(gè)聚類內(nèi)部的最合適的K值。該室內(nèi)環(huán)境一共劃分了8個(gè)聚類,則分別將其命名為聚類1～聚類8。并選出其中的大聚類以及小聚類。

對于小聚類,不同K值下不同的平均誤差如圖7所示。

圖7 所有小聚類不同K值下的誤差

可以看出,對于聚類1、聚類2、聚類3和聚類4來說,最佳的K值分別是4、3、3、4,其中聚類2只有4個(gè)樣本點(diǎn),所以對于聚類2來說,K=3、K=4與K=5的誤差是一樣的。

同理,對于大聚類,不同K值下不同的平均誤差如下圖8所示:

圖8 所有大聚類不同K值下的誤差

可以看到,對于聚類5、聚類6、聚類7和聚類8來說,最佳的K值分別是5、4、5、4,其中,對于聚類6與聚類7來說,K=7、K=8與K=9的誤差是一樣的。

根據(jù)最佳K值的計(jì)算結(jié)果,在該定位區(qū)域內(nèi)最佳的K值分別有3、4、5,證明了前面所提出的可變化K值的觀點(diǎn)是正確的。

為了能更直觀展示基于實(shí)際建筑環(huán)境調(diào)整后的聚類有著更加高的精度,選取了房間3第二行的4個(gè)樣本點(diǎn)作為測試點(diǎn),兩個(gè)聚類中的最佳K值均為4,分別進(jìn)行加權(quán)K臨近運(yùn)算。表1給出了在僅使用K-means算法下和基于實(shí)際建筑環(huán)境調(diào)整下的聚類的誤差值。

表1 兩種聚類方法的誤差比較

從該表中可以看出,在相同的最佳K值下,相比于傳統(tǒng)的基于信號強(qiáng)度的K-means算法,基于實(shí)際建筑環(huán)境調(diào)整后的聚類能更加符合同一個(gè)聚類中的樣本點(diǎn)在實(shí)際建筑環(huán)境中相鄰的要求,同時(shí)也大體上保證了信號強(qiáng)度相似的特性,最后的定位結(jié)果的精度比前者要好。

5 結(jié)語

通過分析K-means算法與加權(quán)K臨近算法,針對K-means聚類算法中聚類判定條件僅僅為接收信號強(qiáng)度,提出根據(jù)實(shí)際的建筑環(huán)境來進(jìn)行調(diào)整,同時(shí)根據(jù)傳統(tǒng)的加權(quán)K臨近算法中K值與聚類本身聯(lián)系不大的問題,提出根據(jù)聚類自己本身的樣本點(diǎn)來尋找每個(gè)聚類的最佳K值。實(shí)驗(yàn)結(jié)果表明,基于改進(jìn)聚類與加權(quán)K臨近的Wi-Fi室內(nèi)定位算法比起傳統(tǒng)的聚類和加權(quán)K臨近算法,平均定位誤差更低,定位精度得到了提高,同時(shí),調(diào)整后的聚類更加符合實(shí)際建筑環(huán)境,使得算法的計(jì)算量與定位精度進(jìn)一步提高,能夠滿足室內(nèi)定位的精度需求。