引入RSSI指紋抖動量的室內定位改進算法

鄧 遂,鄧瀚林,潘 強,劉海濤

(無錫物聯網產業(yè)研究院,江蘇無錫214213)

引入RSSI指紋抖動量的室內定位改進算法

鄧 遂,鄧瀚林,潘 強,劉海濤

(無錫物聯網產業(yè)研究院,江蘇無錫214213)

為提高接收信號強度指示(RSSI)指紋進行室內定位的準確性,提出一種利用RSSI指紋抖動量的虛擬標簽定位改進算法。給出RSSI指紋抖動量計算方法,將其應用于待定位標簽與參考標簽的距離以及虛擬標簽RSSI指紋的計算。在實際測試中,將RSSI指紋抖動量用于虛擬標簽定位算法射頻指紋(RFFP)的改進。測試結果表明,與RFFP算法和LANDMARC算法相比,改進算法的平均定位精度分別提高約0.35 m～0.88 m和0.38 m～0.94 m,算法耗時僅分別增加約1%和12%。

室內定位;無線射頻識別;接收信號強度指示;指紋;虛擬標簽;無線傳感器網絡

1 概述

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

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

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

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

本文在RFFP算法基礎上,引入RSSI指紋抖動量對鄰近節(jié)點的權重進行重新分配,以提高虛擬標簽定位算法的準確性和穩(wěn)定性。

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

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

從m個參考標簽中,挑選出與待定位標簽k最近的N個,即從{Ek,1,t,Ek,2,t,…,Ek,m,t}中選出最小的N個,記為{Ek,g1,t,Ek,g2,t,…,Ek,gN,t},然后對標簽{g1,g2,…,gN}的位置坐標進行加權求和,得到待定位標簽k在時刻t的估計位置:

其中:

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

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

圖1 VIRE算法和RFFP算法的虛擬標簽布設方式

對于虛擬標簽的RSSI指紋計算方法,VIRE算法采用線性插值,RFFP算法則采用動態(tài)線性插值方法,兩者本質上都是基于空間位置關系的線性差值方法。

3 引入RSSI指紋抖動量的改進算法

本文在RFFP算法的基礎上,引入RSSI指紋抖動量對選中參考標簽的權重進行重新分配,即對于與待定位標簽k距離最小的N個參考節(jié)點{g1,g2,…,gN},分析其RSSI指紋在一段時間內的抖動特性。對參考標簽j,定義其RSSI指紋抖動量為:

其中,σi,j,t表示時刻t參考標簽j與閱讀器i之間的RSSI抖動量,計算方法如下:

在計算待定位標簽k與參考標簽j的距離Ek,j,t時,引入參考標簽j的RSSI指紋抖動量Δj,t,即將式(1)修改為:

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

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

為了進一步降低由于標簽RSSI指紋抖動帶來的定位誤差,采用固定長度窗口對得到的待定位標簽位置進行平滑處理,最終得到的待定位標簽的位置為:

從算法復雜度角度分析,LANDMARC算法的時間復雜度為O(umn),VIRE算法時間復雜度為O(umnq2)(其中q為每2個真實參考標簽之間的虛擬標簽個數);相對于VIRE算法,RFFP算法增加的虛擬標簽個數為常數項,因此其時間復雜度為O(umn);本文提出的改進算法在RFFP算法基礎上僅增加了RSSI指紋抖動量的計算,時間復雜度為O((u+T)mn)。

4 仿真與測試結果分析

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

圖2 檢測器單層布設示意圖

圖3 檢測器雙層布設示意圖

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

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

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

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

圖4 單層布設方式的測試結果

圖5 雙層布設方式的測試結果

圖6 算法耗時結果對比

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

5 結束語

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

[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] 史偉光.基于射頻識別技術的室內定位算法研究[D].天津:天津大學,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] 李軍懷,張果謀,于 蕾,等.面向室內環(huán)境的RFID定位方法分析與仿真[J].計算機工程,2012,38(14): 276-279.

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

[11] 李 鵬,馬 寧,楊擁軍,等.基于RFID的邊界虛擬參考標簽改進算法[J].計算機應用研究,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)

鄧 遂,鄧瀚林,潘 強,等.引入RSSI指紋抖動量的室內定位改進算法[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

江蘇省自然科學基金資助項目(BK2011035);江蘇省省級現代服務業(yè)(軟件產業(yè))發(fā)展專項引導基金資助重點項目(CYE11C1116)。

鄧 遂(1985-),男,博士,主研方向:無線傳感器網絡,信號處理;鄧瀚林、潘 強,博士;劉海濤,研究員、博士生導師。

2014-01-21

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