一種自適應(yīng)的指紋更新定位方法

葉阿真，張楨萍，孫明輝

(1.福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，福建 福州 350117；2.福建信息職業(yè)技術(shù)學(xué)院商貿(mào)管理學(xué)院，福建 福州 350003)

近幾年，基于位置服務(wù)的需求不斷增加，越來越多的人關(guān)注到了室內(nèi)定位[1-2].室內(nèi)定位服務(wù)包括智能營銷、精確廣告、室內(nèi)導(dǎo)航、物品監(jiān)控等.現(xiàn)有全球定位系統(tǒng)的信號無法穿透建筑物[3]，所以在室內(nèi)環(huán)境中無法有效地發(fā)揮作用.因此，室內(nèi)定位成了當(dāng)前的一個熱點(diǎn)研究問題[4-5].出于成本和復(fù)雜性的考慮，大多數(shù)現(xiàn)有的室內(nèi)定位都是基于接收信號強(qiáng)度(RSS)[6].信號的多徑傳播對環(huán)境具有很強(qiáng)的依賴性，對于每個具體位置而言，該位置上信號的多徑結(jié)構(gòu)是唯一的，發(fā)射的信號經(jīng)過反射和折射，會產(chǎn)生和周圍環(huán)境相關(guān)的信號強(qiáng)度值，這樣的信號強(qiáng)度值反映了環(huán)境的特征，可以認(rèn)為是該位置上的信號指紋.基于位置指紋的定位方法[7-10]的核心思想，是通過提讀取標(biāo)簽的信號強(qiáng)度值，然后再將信號強(qiáng)度值與事先存儲在數(shù)據(jù)庫中的信號指紋進(jìn)行匹配，找出最相似的結(jié)果進(jìn)行定位.

基于指紋定位系統(tǒng)的工作過程大致可分為兩個階段：離線指紋采集階段和在線定位階段.在離線采集階段，首先在各參考點(diǎn)測量各信標(biāo)節(jié)點(diǎn)的信號特征(如RSSI值)，并將這些RSSI存儲為樣本，建立一個無線指紋定位地圖(指紋數(shù)據(jù)庫)；在在線定位階段，移動終端實(shí)時測量各信標(biāo)節(jié)點(diǎn)的信號特征后，采用相關(guān)的匹配算法來確定實(shí)時信號特征與哪些參考點(diǎn)的離線信號特征相匹配，再采用定位算法計(jì)算出終端的大致位置.然而，由于環(huán)境變化，同一地點(diǎn)在不同時間測量出的RSSI值很可能差異很大.這里所謂的環(huán)境變化包括人的隨機(jī)運(yùn)動、門窗的開關(guān)以及溫濕度的變化等等.因此，離線階段建立的信號指紋庫可能會過時，從而導(dǎo)致定位精度降低.然而，依靠人工重新標(biāo)定更新信號指紋庫的方式，會消耗大量的時間和人力成本，難以接受.因此需要采用自動更新信號指紋庫的方法，本文提出了一種基于模糊聚類的自適應(yīng)信號指紋庫更新方法：

(1)針對環(huán)境實(shí)時變化導(dǎo)致離線指紋不能充分匹配實(shí)時信號特征的問題，提出一種指紋動態(tài)更新的定位方案；通過部署校正節(jié)點(diǎn)，實(shí)現(xiàn)定位指紋的動態(tài)更新，從而有效提高基于指紋的定位系統(tǒng)的自適應(yīng)性和準(zhǔn)確性；

(2)提出一種基于模糊聚類的分區(qū)機(jī)制；以定位指紋數(shù)據(jù)庫中各參考點(diǎn)的傳播路徑損耗參數(shù)為判別依據(jù)，引入模糊聚類方法對目標(biāo)區(qū)域進(jìn)行分區(qū)，確保各分區(qū)的物理環(huán)境具有相近的信號傳播特性，為矯正節(jié)點(diǎn)的部署以及指紋的動態(tài)更新提供依據(jù).

1 相關(guān)工作

RADAR是一種典型的指紋定位系統(tǒng)[8].它的工作原理是用多個基站覆蓋目標(biāo)區(qū)域，然后記錄目標(biāo)區(qū)域的信號強(qiáng)度信息.它結(jié)合了經(jīng)驗(yàn)測量和信號傳播模型來確定用戶位置.LANDMARC以RFID標(biāo)簽作為定位參考[11]，該方法可實(shí)時提供參考位置信息.但需要更多的參考標(biāo)簽來進(jìn)一步提高定位精度.使用這種方式，一方面會增加定位成本，另一方面也會造成信號之間的相互干擾.Sergios等[12]提出了一種LEASE系統(tǒng)，該系統(tǒng)以靜態(tài)發(fā)射器和嗅探器作為輔助，來訓(xùn)練脫機(jī)指紋.文獻(xiàn)[13]提出了一種基于位置不確定性約束的室內(nèi)無線定位方法，利用貪婪算法來求解位置匹配的優(yōu)化問題.但該算法依賴于當(dāng)前已有的定位決策，無法保證獲得最優(yōu)解.此外，針對由于無線信號強(qiáng)度不穩(wěn)定導(dǎo)致定位誤差大的問題，研究者也提出了一種基于離散系數(shù)改進(jìn)的WKNN(加權(quán)K近鄰)算法[14-15].離散系數(shù)可以反映單位均值上的離散程度，因此信號源的離散系數(shù)可以很好地指示每個基站的信號穩(wěn)定程度.

2 本文方法

2.1 系統(tǒng)模型

本文方案的系統(tǒng)模型如圖1所示.該系統(tǒng)主要由定位服務(wù)器、信標(biāo)節(jié)點(diǎn)(BNs)和校正節(jié)點(diǎn)(CNs)3部分組成.定位服務(wù)器用于存儲指紋地圖，它可以部署在網(wǎng)絡(luò)中的任何位置.如果是基于基礎(chǔ)設(shè)施的定位系統(tǒng)，則定位服務(wù)器還將負(fù)責(zé)計(jì)算位置.信標(biāo)節(jié)點(diǎn)負(fù)責(zé)為所有參考點(diǎn)提供信標(biāo)信號.因此，需要確保每個參考位置點(diǎn)都有多個信標(biāo)節(jié)點(diǎn)的信號覆蓋.對于基于WLAN的定位系統(tǒng)，無線路由器(AP)可以充當(dāng)信標(biāo)節(jié)點(diǎn).校正節(jié)點(diǎn)負(fù)責(zé)對信標(biāo)信號進(jìn)行實(shí)時觀測.因此，校正節(jié)點(diǎn)應(yīng)具備接收信標(biāo)信號的能力，可以測量RSSI值，并與位置服務(wù)器建立網(wǎng)絡(luò)連接.本方案將定位區(qū)域劃分為多個更新分區(qū)，每個分區(qū)中的校正節(jié)點(diǎn)負(fù)責(zé)更新本區(qū)域內(nèi)RPs的指紋.因此，每個子區(qū)域至少部署一個校正節(jié)點(diǎn).

圖1 系統(tǒng)模型

本文提出的信號指紋庫動態(tài)更新機(jī)制如圖2所示.首先，采集和建立全局的靜態(tài)指紋地圖；然后引入模糊聚類，根據(jù)路徑損耗參數(shù)將地圖劃分為若干個子區(qū)域，并在每個子區(qū)域部署一個校正節(jié)點(diǎn)；最后，根據(jù)校正節(jié)點(diǎn)的測量信號強(qiáng)度，周期性更新射頻指紋地圖，用于實(shí)時定位.

圖2 信號指紋庫更新模型

2.2 模糊聚類

在硬聚類中，指紋被劃分為不同的聚類，每個指紋恰好屬于一個聚類.在模糊聚類中，一個指紋可以屬于多個聚類，并且指紋與聚類是相互關(guān)聯(lián)的.

對于室內(nèi)無線信道，由于無線信號會受到室內(nèi)障礙物的影響，產(chǎn)生反射、衍射和折射，所以接收到的信號由不同振幅、不同相位的入射信號構(gòu)成.根據(jù)對數(shù)距離路徑損耗模型，信號的能量會隨著傳播距離的增加而減小.一般來說，滿足Shannon對數(shù)模型：

PL(d)=PL(d0)+10ηlog10(d/d0)+Xσ，

(1)

其中，d為發(fā)射端與接收端之間的距離.d0為參考距離，一般在室內(nèi)環(huán)境為1 m.PL(d)是距離發(fā)射終端d米的接收強(qiáng)度.PL(d0)為參考強(qiáng)度.Xσ為標(biāo)準(zhǔn)差.η為路徑損耗參數(shù)，表示接收強(qiáng)度隨距離增大而減小的速率，其值與周圍環(huán)境和建筑物類型有關(guān).通常，η值主要由發(fā)射機(jī)和接收機(jī)之間的特定信道環(huán)境決定.在實(shí)際應(yīng)用中，不同地區(qū)室內(nèi)環(huán)境的η值是不同的.

圖3為不同區(qū)域內(nèi)RSSI與對數(shù)距離的關(guān)系.如果在某一區(qū)域η值相同或相近，則說明該區(qū)域內(nèi)無線電信號傳播特性相似，同樣也說明該區(qū)域參考點(diǎn)的指紋受到了類似的環(huán)境影響.因此，可以根據(jù)η的近似程度對離線指紋進(jìn)行聚類，從而實(shí)現(xiàn)對定位區(qū)域的分區(qū).

圖3 不同區(qū)域內(nèi)RSSI與對數(shù)距離的關(guān)系

假設(shè)有P個信標(biāo)節(jié)點(diǎn)，在室內(nèi)定位區(qū)域有M個參考點(diǎn).測量第j個信標(biāo)對應(yīng)的參考點(diǎn)i的RSSI時，路徑損耗參數(shù)可表示為：

(2)

因此，位置i處的RSSI指紋可以表示為其路徑損耗參數(shù)向量.信號指紋庫由參考點(diǎn)的坐標(biāo)及其RSSI指紋組成.

ηi={ηi1,ηi2,…,ηij, …,ηiP}， 1≤i≤M，

(3)

其中，ηij為第j個信標(biāo)節(jié)點(diǎn)對應(yīng)的第i個參考點(diǎn)的路徑損耗參數(shù).因此，所有參考點(diǎn)的路徑損耗參數(shù)向量可以表示為：

η={η1,η2, …,ηM}.

(4)

聚類函數(shù)定義為：

(5)

其中，φ(ηi)為ηi到高維特征空間的映射；φ(pj)表示聚類j的原型向量在特征空間中的映射；U=[uij]為相關(guān)隸屬度矩陣；uij表示指紋ηi在第j個聚類中的隸屬度；C是聚類數(shù)；M是平滑參數(shù)；dij為φ(ηi)與φ(pj)的相似性.通常，dij定義為與兩個向量之間的歐氏距離有關(guān)的函數(shù)：

20世紀(jì)末，中國文學(xué)藝術(shù)出現(xiàn)了一種反道德的現(xiàn)象，受拜金主義的不良影響，一些文學(xué)藝術(shù)作品不以宣揚(yáng)真善美為己任，而是以低級趣味的東西來迎合一些人的口味。這不僅背離了文學(xué)藝術(shù)的本質(zhì)所在，而且造成了自身道德信念的失落。新時代，堅(jiān)定文化自信，推動社會主義文化繁榮興盛，提升或者重建文學(xué)藝術(shù)工作者的道德人格首當(dāng)其沖。文學(xué)藝術(shù)工作者只有恪守真理與理想，保持強(qiáng)烈的社會責(zé)任感和歷史使命感，才能不放棄對假丑惡的批判與抗?fàn)?，通過作品傳播先進(jìn)的思想和正確的人生觀、價值觀，真正充分發(fā)揮文學(xué)藝術(shù)的道德價值。

dij=‖φ(ηi)-φ(pj)‖.

(6)

聚類的原則是最小化Jm.由于矩陣U中的列元素相互獨(dú)立，故Jm的最小值為：

(7)

式(7)的約束條件為：

(8)

隸屬度表達(dá)式可通過拉格朗日乘數(shù)法求解：

(9)

根據(jù)uij和樣本，可以得到聚類中心：

(10)

最后，歸屬參考指紋最接近pj的位置為聚類j的檢查點(diǎn).

2.3 信號指紋庫更新

經(jīng)過模糊聚類后，可以將信號指紋聚類為C類.同一聚類內(nèi)的信號具有相近的信號傳播參數(shù)(η).在每個聚類中部署一個校驗(yàn)節(jié)點(diǎn)，觀察環(huán)境變化引起的信號傳播參數(shù)的相應(yīng)變化，從而更新相應(yīng)的聚類信號指紋庫.

2.4 定位計(jì)算

通常，使用KNN算法作為指紋方法中的定位算法.該算法以距離度量，如曼哈頓距離或歐氏距離，作為實(shí)時指紋與參考指紋匹配值.然后通過比較匹配值來估計(jì)目標(biāo)位置.廣義距離公式定義如下：

(11)

其中s為實(shí)時指紋，s′為參考指紋.當(dāng)q= 1和2時，d分別為曼哈頓距離和歐幾里得距離.

KNN算法通過匹配值進(jìn)行升序排列，選擇k個最接近的參考點(diǎn).然后取這些候選位置的質(zhì)心作為估計(jì)位置：

(12)

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

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

本文實(shí)驗(yàn)基于Zigbee平臺上實(shí)現(xiàn)，硬件平臺采用TI公司的CC2431芯片，軟件部分基于VC++平臺編碼，并選用XML文件存儲數(shù)據(jù)信息.實(shí)驗(yàn)物理環(huán)境為所在實(shí)驗(yàn)室的6樓，以1.5 m的間隔設(shè)置85個參考點(diǎn)(用綠色標(biāo)記)，并在房間的角落和走廊共設(shè)置5個信標(biāo)節(jié)點(diǎn)，分別記為B1、B2、B3、B4、B5，如圖4所示.信標(biāo)節(jié)點(diǎn)的部署如圖5所示.在每個參考點(diǎn)分別采集100次不同信標(biāo)節(jié)點(diǎn)的信號指紋，然后取平均值后存入指紋數(shù)據(jù)庫.

圖4 實(shí)驗(yàn)環(huán)境

圖5 信標(biāo)節(jié)點(diǎn)的部署

定位誤差采用真實(shí)位置和估計(jì)位置的歐式距離計(jì)算：

e=(x-x0)2+(y-y0)2,

(13)

其中(x,y)為目標(biāo)節(jié)點(diǎn)的定位坐標(biāo)，(x0,y0)為目標(biāo)節(jié)點(diǎn)的真實(shí)位置坐標(biāo).

3.2 結(jié)果以及分析

首先通過移動節(jié)點(diǎn)采集所有參考點(diǎn)的信號指紋，并建立指紋地圖.然后采用2.2節(jié)提出的模糊聚類方法對定位地圖進(jìn)行分區(qū)處理，結(jié)果如圖6所示，實(shí)驗(yàn)環(huán)境大致可以劃分為7個子區(qū)域.由此，在每個區(qū)域部署一個校驗(yàn)節(jié)點(diǎn)，用于實(shí)時更新指紋.一方面，該指紋庫對環(huán)境具有較強(qiáng)的自適應(yīng)能力；另一方面，自適應(yīng)更新機(jī)制可以節(jié)省人力物力，降低系統(tǒng)部署成本.

圖6 分簇結(jié)果與校驗(yàn)點(diǎn)部署

圖7對比了動態(tài)更新信號指紋庫的方法與靜態(tài)信號指紋庫方法(naive KNN)定位累積誤差的概率分布.從圖7中可以看出，動態(tài)更新信號指紋庫的方法表現(xiàn)較好，2 m以內(nèi)的誤差為92%，1 m以內(nèi)的誤差為67%.與naive KNN相比，整體定位性能更好.這是因?yàn)樵摲椒ú皇腔陟o態(tài)信號指紋庫，而是基于動態(tài)更新的信號指紋庫.因此，該方法能夠有效地適應(yīng)環(huán)境和干擾的變化，從而提高定位精度.

圖7 累積誤差概率分布

4 結(jié)論

對于室內(nèi)指紋定位，本文提出了一種新的自適應(yīng)信號指紋庫更新方法.不同于典型的指紋定位方法，該方法將靜態(tài)信號指紋庫轉(zhuǎn)換為動態(tài)更新的自適應(yīng)指紋庫.利用模糊聚類將指紋分為幾個聚類，然后為每個聚類選擇代表.在定位階段，信號指紋庫會通過觀察檢查站信號特征的變化來進(jìn)行自我更新.該方法既能適應(yīng)環(huán)境變化，又能降低信號指紋庫更新的人工成本.實(shí)驗(yàn)表明，該方法在定位精度方面有較好的表現(xiàn).