鄧 遂,鄧瀚林,潘 強(qiáng),劉海濤

(無錫物聯(lián)網(wǎng)產(chǎn)業(yè)研究院,江蘇無錫214213)

引入RSSI指紋抖動(dòng)量的室內(nèi)定位改進(jìn)算法

鄧 遂,鄧瀚林,潘 強(qiáng),劉海濤

(無錫物聯(lián)網(wǎng)產(chǎn)業(yè)研究院,江蘇無錫214213)

為提高接收信號(hào)強(qiáng)度指示(RSSI)指紋進(jìn)行室內(nèi)定位的準(zhǔn)確性,提出一種利用RSSI指紋抖動(dòng)量的虛擬標(biāo)簽定位改進(jìn)算法。給出RSSI指紋抖動(dòng)量計(jì)算方法,將其應(yīng)用于待定位標(biāo)簽與參考標(biāo)簽的距離以及虛擬標(biāo)簽RSSI指紋的計(jì)算。在實(shí)際測(cè)試中,將RSSI指紋抖動(dòng)量用于虛擬標(biāo)簽定位算法射頻指紋(RFFP)的改進(jìn)。測(cè)試結(jié)果表明,與RFFP算法和LANDMARC算法相比,改進(jìn)算法的平均定位精度分別提高約0.35 m～0.88 m和0.38 m～0.94 m,算法耗時(shí)僅分別增加約1%和12%。

室內(nèi)定位;無線射頻識(shí)別;接收信號(hào)強(qiáng)度指示;指紋;虛擬標(biāo)簽;無線傳感器網(wǎng)絡(luò)

1 概述

近年來,隨著室內(nèi)無線設(shè)備的廣泛應(yīng)用,基于接收信號(hào)強(qiáng)度指示(Radio Frequency Identification, RSSI)的室內(nèi)定位算法一直是研究的熱點(diǎn)和難點(diǎn)。由于室內(nèi)環(huán)境存在復(fù)雜和動(dòng)態(tài)變化的特點(diǎn),采用建模方法對(duì)室內(nèi)無線信號(hào)的損耗進(jìn)行分析帶來的定位誤差較大;而其他采用如超聲波、超寬帶等技術(shù)的室內(nèi)定位方法[1]受成本、使用條件限制,難以滿足普遍情況下的室內(nèi)定位需求。RSSI指紋定位技術(shù)是利用一組位置已知的節(jié)點(diǎn)接收信號(hào)強(qiáng)度指標(biāo)對(duì)待定位節(jié)點(diǎn)進(jìn)行定位的方法;這一組位置已知的節(jié)點(diǎn)叫參考節(jié)點(diǎn),其接收到的待定位節(jié)點(diǎn)的信號(hào)強(qiáng)度指標(biāo)序列就叫做待定位節(jié)點(diǎn)的指紋。本文的節(jié)點(diǎn)泛指能進(jìn)行無線信號(hào)傳輸?shù)脑O(shè)備。RSSI指紋定位技術(shù)不需要額外增加硬件,不依賴室內(nèi)無線信號(hào)傳輸損耗模型,也不受室內(nèi)各種使用條件限制,是較理想的室內(nèi)定位解決方案。

RSSI指紋定位技術(shù)一般包括離線學(xué)習(xí)和在線定位2個(gè)階段[2]。在離線學(xué)習(xí)階段,定位主機(jī)收集參考節(jié)點(diǎn)的RSSI指紋,建立RSSI指紋的空間分布關(guān)系;在線定位階段,待定位節(jié)點(diǎn)的RSSI指紋與離線階段建立的RSSI指紋的空間分布關(guān)系進(jìn)行匹配,進(jìn)而估計(jì)出待定位節(jié)點(diǎn)的空間位置。RSSI指紋定位技術(shù)的關(guān)鍵在于如何在RSSI指紋庫中選擇與待定位節(jié)點(diǎn)RSSI指紋接近的指紋,以及如何利用選擇的RSSI指紋的空間分布關(guān)系估計(jì)待定位節(jié)點(diǎn)的位置。

微軟在1998年提出的RADAR系統(tǒng)[3]是早期RSSI指紋定位技術(shù)的典型代表。RADAR室內(nèi)定位系統(tǒng)在離線階段存儲(chǔ)70個(gè)不同位置的RSSI指紋,在線階段則利用K近鄰算法估算待定位節(jié)點(diǎn)的位置;在此基礎(chǔ)上,美國馬里蘭大學(xué)研發(fā)的Horus系統(tǒng)[4]引入了RSSI指紋的概率模型;加利福尼亞大學(xué)研發(fā)的Nibble系統(tǒng)[5]采用接收信號(hào)信噪比指紋來代替RSSI指紋,并建立指紋庫的連續(xù)分布概率模型;此外,采用神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法、貝葉斯方法、蒙特卡羅方法、跟蹤輔助定位等技術(shù)手段[6],均能在一定程度上提高RSSI指紋定位技術(shù)的定位精度。

LANDMARC是應(yīng)用無線射頻識(shí)別(Radio Frequency Identification,RFID)技術(shù)進(jìn)行室內(nèi)定位的系統(tǒng)[7],通過利用已知位置的有源參考標(biāo)簽實(shí)時(shí)RSSI指紋來動(dòng)態(tài)反映環(huán)境信息;對(duì)待定位標(biāo)簽的定位則通過比對(duì)待定位標(biāo)簽與參考標(biāo)簽的RSSI指紋差異,利用殘差加權(quán)算法進(jìn)行計(jì)算實(shí)現(xiàn)。LANDMARC系統(tǒng)具有成本較低、容易實(shí)現(xiàn)和較強(qiáng)環(huán)境適應(yīng)性特點(diǎn),定位精度和穩(wěn)定性相對(duì)較高。在LANDMARC系統(tǒng)基礎(chǔ)上,國內(nèi)外研究人員針對(duì)其不足進(jìn)行了各方面改進(jìn)。其中,通過引入虛擬參考標(biāo)簽的VIRE算法在不增加硬件設(shè)施前提下提高了定位準(zhǔn)確性[8];其他改進(jìn)方法包括構(gòu)建虛擬參考標(biāo)簽空間[9]、引入高斯擬合動(dòng)態(tài)權(quán)重[10]、虛擬標(biāo)簽RSSI插值方法優(yōu)化等[11]。文獻(xiàn)[12]提出了RFFP(Radio Frequency Fingerprints)虛擬標(biāo)簽定位算法,通過合理設(shè)計(jì)虛擬標(biāo)簽的布設(shè)位置和選擇適當(dāng)?shù)牟逯捣椒?在降低虛擬標(biāo)簽定位算法計(jì)算量的前提下提高了定位準(zhǔn)確性。

本文在RFFP算法基礎(chǔ)上,引入RSSI指紋抖動(dòng)量對(duì)鄰近節(jié)點(diǎn)的權(quán)重進(jìn)行重新分配,以提高虛擬標(biāo)簽定位算法的準(zhǔn)確性和穩(wěn)定性。

2 LANDMARC系統(tǒng)和虛擬標(biāo)簽定位算法

LANDMARC系統(tǒng)由多個(gè)位置固定且已知的有源RFID標(biāo)簽和若干個(gè)閱讀器組成。假設(shè)系統(tǒng)中有n個(gè)閱讀器和m個(gè)參考標(biāo)簽,待定位標(biāo)簽個(gè)數(shù)為u,參考標(biāo)簽j的位置坐標(biāo)為(xj,yj,zj);在時(shí)刻t閱讀器i接收到標(biāo)簽j(包括參考標(biāo)簽和待定位標(biāo)簽)的無線信號(hào)接收強(qiáng)度為si,j,t,則標(biāo)簽j在時(shí)刻t的RSSI指紋為Sj,t=(s1,j,t,s2,j,t,…,sn,j,t),時(shí)刻t待定位標(biāo)簽k與參考標(biāo)簽j的RSSI指紋距離定義為:

從m個(gè)參考標(biāo)簽中,挑選出與待定位標(biāo)簽k最近的N個(gè),即從{Ek,1,t,Ek,2,t,…,Ek,m,t}中選出最小的N個(gè),記為{Ek,g1,t,Ek,g2,t,…,Ek,gN,t},然后對(duì)標(biāo)簽{g1,g2,…,gN}的位置坐標(biāo)進(jìn)行加權(quán)求和,得到待定位標(biāo)簽k在時(shí)刻t的估計(jì)位置:

其中:

VIRE算法在LANDMARC系統(tǒng)的基礎(chǔ)上,引入了虛擬參考標(biāo)簽進(jìn)行輔助定位,但是由于采取的是全景式虛擬標(biāo)簽插入方法,計(jì)算復(fù)雜度太大,且提高的定位精度有限。RFFP算法在VIRE算法的基礎(chǔ)上,主要從虛擬標(biāo)簽的布設(shè)方式和RSSI指紋計(jì)算方法2個(gè)方面進(jìn)行了改進(jìn)。

VIRE算法是在整個(gè)定位區(qū)域內(nèi)所有真實(shí)標(biāo)簽之間布設(shè)虛擬標(biāo)簽,這樣帶來了計(jì)算量大的問題;而RFFP算法不同,先找出與待定位標(biāo)簽RSSI指紋距離最小的N個(gè)真實(shí)參考標(biāo)簽,然后在這個(gè)參考標(biāo)簽覆蓋的區(qū)域內(nèi)布設(shè)K個(gè)虛擬標(biāo)簽,如圖1所示,在與待定位標(biāo)簽RSSI指紋距離最小的3個(gè)參考標(biāo)簽連線上,等距布設(shè)6個(gè)虛擬標(biāo)簽,然后選擇2組虛擬標(biāo)簽,在其連線上等距布設(shè)4個(gè)參考標(biāo)簽,這樣原則上與待定位標(biāo)簽RSSI差值越小的參考標(biāo)簽附近虛擬標(biāo)簽的布設(shè)密度越大。

圖1 VIRE算法和RFFP算法的虛擬標(biāo)簽布設(shè)方式

對(duì)于虛擬標(biāo)簽的RSSI指紋計(jì)算方法,VIRE算法采用線性插值,RFFP算法則采用動(dòng)態(tài)線性插值方法,兩者本質(zhì)上都是基于空間位置關(guān)系的線性差值方法。

3 引入RSSI指紋抖動(dòng)量的改進(jìn)算法

本文在RFFP算法的基礎(chǔ)上,引入RSSI指紋抖動(dòng)量對(duì)選中參考標(biāo)簽的權(quán)重進(jìn)行重新分配,即對(duì)于與待定位標(biāo)簽k距離最小的N個(gè)參考節(jié)點(diǎn){g1,g2,…,gN},分析其RSSI指紋在一段時(shí)間內(nèi)的抖動(dòng)特性。對(duì)參考標(biāo)簽j,定義其RSSI指紋抖動(dòng)量為:

其中,σi,j,t表示時(shí)刻t參考標(biāo)簽j與閱讀器i之間的RSSI抖動(dòng)量,計(jì)算方法如下:

在計(jì)算待定位標(biāo)簽k與參考標(biāo)簽j的距離Ek,j,t時(shí),引入?yún)⒖紭?biāo)簽j的RSSI指紋抖動(dòng)量Δj,t,即將式(1)修改為:

其中,α是常數(shù);r是(-1,1)之間均勻分布的隨機(jī)數(shù);然后從修正后待定位標(biāo)簽與參考標(biāo)簽的距離{Ek,1,t,Ek,2,t,…,Ek,m,t}中選出最小的N個(gè),記為{Ek,g1,t,Ek,g2,t,…,Ek,gN,t};按照RFFP算法的虛擬標(biāo)簽布設(shè)方式,在選中的參考標(biāo)簽{g1,g2,…,gN}覆蓋的區(qū)域內(nèi)進(jìn)行虛擬標(biāo)簽布設(shè);虛擬標(biāo)簽的RSSI指紋則通過利用參考標(biāo)簽{g1,g2,…,gN}的RSSI指紋進(jìn)行動(dòng)態(tài)線性插值得到,需要說明的是,應(yīng)用動(dòng)態(tài)線性插值方法前需要對(duì)輸入的參考標(biāo)簽{g1,g2,…,gN}的RSSI指紋進(jìn)行隨機(jī)抖動(dòng)處理,如下式:

其中,α是與式(6)中α相同的常數(shù);r是(-1,1)之間均勻分布的隨機(jī)數(shù);j∈{g1,g2,…,gN}。然后從選中的N個(gè)真實(shí)參考標(biāo)簽{g1,g2,…,gN}和K個(gè)虛擬參考標(biāo)簽中,選擇與待定位標(biāo)簽的距離最小的M個(gè),利用式(2)和式(3)進(jìn)行權(quán)重計(jì)算和加權(quán)求和,得到待定位標(biāo)簽的位置。

為了進(jìn)一步降低由于標(biāo)簽RSSI指紋抖動(dòng)帶來的定位誤差,采用固定長度窗口對(duì)得到的待定位標(biāo)簽位置進(jìn)行平滑處理,最終得到的待定位標(biāo)簽的位置為:

從算法復(fù)雜度角度分析,LANDMARC算法的時(shí)間復(fù)雜度為O(umn),VIRE算法時(shí)間復(fù)雜度為O(umnq2)(其中q為每2個(gè)真實(shí)參考標(biāo)簽之間的虛擬標(biāo)簽個(gè)數(shù));相對(duì)于VIRE算法,RFFP算法增加的虛擬標(biāo)簽個(gè)數(shù)為常數(shù)項(xiàng),因此其時(shí)間復(fù)雜度為O(umn);本文提出的改進(jìn)算法在RFFP算法基礎(chǔ)上僅增加了RSSI指紋抖動(dòng)量的計(jì)算,時(shí)間復(fù)雜度為O((u+T)mn)。

4 仿真與測(cè)試結(jié)果分析

為了對(duì)本文提出的改進(jìn)算法進(jìn)行測(cè)試,本文在實(shí)驗(yàn)室環(huán)境下搭建了一個(gè)RSSI指紋采集系統(tǒng),其中,RFID標(biāo)簽和閱讀器分別采用自主研發(fā)的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)節(jié)點(diǎn)和中繼器代替,測(cè)試場(chǎng)景分為檢測(cè)器單層布設(shè)和雙層布設(shè)2種方式,如圖2和圖3所示。

圖2 檢測(cè)器單層布設(shè)示意圖

圖3 檢測(cè)器雙層布設(shè)示意圖

在單層布設(shè)方式中,共布設(shè)16個(gè)節(jié)點(diǎn),檢測(cè)器間距為2 m,布設(shè)高度為1.5 m;中繼器分別置于測(cè)試區(qū)域的4個(gè)頂點(diǎn)及4條邊的中點(diǎn)上,布設(shè)高度為1.5 m。

在雙層布設(shè)方式中,共布設(shè)18個(gè)檢測(cè)器,每層9個(gè);檢測(cè)器間距為2 m,布設(shè)高度為0.5 m和1.5 m;中繼器分別置于測(cè)試區(qū)域的4個(gè)頂點(diǎn)及4條邊的中點(diǎn)上,布設(shè)高度為1m。

為了保證測(cè)試的一致性,RFFP算法和改進(jìn)算法都采用了固定窗口對(duì)待定位標(biāo)簽位置進(jìn)行平滑處理,固定窗口大小為30。測(cè)試中,大約每500 ms記錄一次各參考節(jié)點(diǎn)和待定位節(jié)點(diǎn)與各中繼器之間的RSSI值,形成RSSI指紋,連續(xù)記錄了30 min;利用記錄的RSSI指紋對(duì)RFFP算法和改進(jìn)算法進(jìn)行測(cè)試,算法參數(shù)α為5;算法仿真實(shí)驗(yàn)在一臺(tái)Thinkpad R400上進(jìn)行,2.2 GHz雙核CPU,2 GB物理內(nèi)存,仿真軟件為Matlab R2012b。

圖4和圖5分別是單層和雙層布設(shè)方式的測(cè)試結(jié)果,圖6是2種布設(shè)方式、3種算法耗時(shí)結(jié)果比較。

圖4 單層布設(shè)方式的測(cè)試結(jié)果

圖5 雙層布設(shè)方式的測(cè)試結(jié)果

圖6 算法耗時(shí)結(jié)果對(duì)比

從以上測(cè)試結(jié)果可以看出,在單層布設(shè)方式的測(cè)試結(jié)果中,引入RSSI指紋抖動(dòng)量的改進(jìn)算法約94%的定位誤差在1.5 m以內(nèi),而RFFP算法僅約5%的誤差在1.5 m以內(nèi);雙層布設(shè)方式中,引入RSSI指紋抖動(dòng)量的改進(jìn)算法約70%的誤差在1m以內(nèi),而RFFP算法僅約5%的誤差在1m以內(nèi)。從圖中定位誤差也可計(jì)算出,相較于RFFP算法,改進(jìn)算法的平均定位精度提高了約0.35 m～0.88 m,而相較于LANDMARC算法,改進(jìn)算法的平均定位精度提高了約0.38 m～0.94 m。從3種算法的耗時(shí)結(jié)果比較來看,RFFP算法和本文提出的改進(jìn)算法運(yùn)算耗時(shí)相對(duì)于LANDMARC算法平均高出約12%,本文提出的改進(jìn)算法運(yùn)算耗時(shí)相對(duì)于RFFP算法平均高出僅約1%。

5 結(jié)束語

本文通過引入RSSI指紋抖動(dòng)量對(duì)虛擬標(biāo)簽定位算法進(jìn)行改進(jìn),在不增加硬件和計(jì)算量的前提下,能有效抵消由于環(huán)境等因素導(dǎo)致的RSSI指紋隨機(jī)抖動(dòng)問題,提高了定位精度。如何進(jìn)一步分析RSSI指紋抖動(dòng)量與定位誤差之間的關(guān)聯(lián),是今后的研究方向。

[1] Luo Xiaowei,O’Brien W J,Julien C L.Comparative evaluation of Received Signal-Strength Index(RSSI) Based Indoor Localization Techniques for Construction Jobsites[J].Advanced Engineering Informatics,2011, 25(2):355-363.

[2] Robles J J,Deicke M,Lehnert R.3D Fingerprint-based Localization forWirelessSensorNetworks[C]// Proceedingsofthe7thWorkshoponPositioning NavigationandCommunication.Dresden,Germany: IEEE Press,2010:77-85.

[3] Bahl P,Padmanabhan V N.RADAR:An in Building RF-based UserLocationandTrackingSystem[C]// Proceedings of the19th Annual Joint Conference of the IEEEComputerandCommunicationsSocieties. [S.1.]:IEEE Press,2000:775-784.

[4] Youssef M,Agrawala A.Handling Samples Correlation in the Horus System[C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.Hong Kong,China:IEEE Press,2004:1023-1031.

[5] Battiti B,NhatTL,VillaniA.Location-aware Computing:A Neural Network Model for Determining Location in Wireless LANs[R].Information Engineering andComputerScience,TechnicalReport:DIT-02-083,2002.

[6] 史偉光.基于射頻識(shí)別技術(shù)的室內(nèi)定位算法研究[D].天津:天津大學(xué),2011.

[7] Ni L M,Liu Yunhao,Lau Y C,et al.LANDMARC: Indoor Location Sensing Using Active RFID[J]. Wireless Networks,2004,10(6):701-710.

[8] Zhao Yiyang,Liu Yunhao,Ni L M.VIRE:Active RFID-basedLocalizationUsingVirtualReferenceElimination[C]//Proceedings of International Conference on Parallel Processing.Xi’an,China:[s.n.],2007:56.

[9] 李軍懷,張果謀,于 蕾,等.面向室內(nèi)環(huán)境的RFID定位方法分析與仿真[J].計(jì)算機(jī)工程,2012,38(14): 276-279.

[10] 詹 杰,劉宏立,劉述鋼,等.基于RSSI的動(dòng)態(tài)權(quán)重定位算法研究[J].電子學(xué)報(bào),2011,39(1):82-88.

[11] 李 鵬,馬 寧,楊擁軍,等.基于RFID的邊界虛擬參考標(biāo)簽改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(1): 158-160.

[12] Alfadhl Y,Chai K K,Chen Yue,et al.Indoor Location Sensing SystemsBasedonRadioChannelFingerprinting[J].China Communications,2011,8(8):1-12.

編輯 索書志

Improved Indoor Localization Algorithm of Introducing RSSI Fingerprints Jittering

DENG Sui,DENG Hanlin,PAN Qiang,LIU Haitao
(Wuxi SensingNet Industrialization Research Institute,Wuxi 214213,China)

In order to improve the accuracy of indoor localization using Received Signal Strength Indicator(RSSI) fingerprints,a new method of introducing the jittering of RSSI fingerprints is proposed,which defines the calculating method of the RSSI fingerprints jittering,and applies it to measure the distance between the reference tags and tags that are being tracked,and computes the RSSI fingerprints of the virtual tags.Test results show that the average localization accuracy is about 0.35 m～0.88 m higher by the improved algorithm than RFFP,and 0.38 m～0.94 m higher than LANDMARC while the time-consuming increases by only1%and12%respectively.

indoor localization;Radio Frequency Identification(RFID);Received Signal Strength Indicator(RSSI); fingerprint;virtual tag;Wireless Sensor Network(WSN)

鄧 遂,鄧瀚林,潘 強(qiáng),等.引入RSSI指紋抖動(dòng)量的室內(nèi)定位改進(jìn)算法[J].計(jì)算機(jī)工程, 2015,41(2):81-84.

英文引用格式:Deng Sui,Deng Hanlin,Pan Qiang,et al.Improved Indoor Localization Algorithm of Introducing RSSI Fingerprints Jittering[J].Computer Engineering,2015,41(2):81-84.

1000-3428(2015)02-0081-04

:A

:TP391

10.3969/j.issn.1000-3428.2015.02.016

江蘇省自然科學(xué)基金資助項(xiàng)目(BK2011035);江蘇省省級(jí)現(xiàn)代服務(wù)業(yè)(軟件產(chǎn)業(yè))發(fā)展專項(xiàng)引導(dǎo)基金資助重點(diǎn)項(xiàng)目(CYE11C1116)。

鄧 遂(1985-),男,博士,主研方向:無線傳感器網(wǎng)絡(luò),信號(hào)處理;鄧瀚林、潘 強(qiáng),博士;劉海濤,研究員、博士生導(dǎo)師。

2014-01-21

:2014-04-28E-mail:dengsui@wsn.cn