俞敏杰,易 平,關漢男

(上海交通大學信息安全工程學院,上海200240)

基于快速部署的室內多樓層定位算法研究

俞敏杰,易 平,關漢男

(上海交通大學信息安全工程學院,上海200240)

傳統(tǒng)的GPS系統(tǒng)在室內由于墻和障礙物的阻隔無法很好地生效,因此需要完善的室內定位系統(tǒng),彌補定位領域最后100 m的不足。然而當前國內外的主流算法大多是基于水平方向的室內定位,有關垂直方向定位方法的研究較少。為此,提出一種基于快速部署的室內多樓層定位算法,實現(xiàn)在大樓內精確的縱向多樓層定位和設備的實時、按需部署。該算法的核心是多樓層差分算法,通過接收來自不同樓層信號,加以差分計算差值的分布來區(qū)分樓層。仿真實驗結果表明,該算法能夠精確地定位樓層。

基于定位服務;室內定位系統(tǒng);多樓層定位;多樓層路徑衰減模型;多樓層差分算法;快速部署

1 概述

智慧生活的變革無處不在,在樓宇、公共設施、企業(yè)、家居、交通等領域已經(jīng)得到了廣泛的應用。這其中最重要的技術之一,也是研究的焦點之一,就是定位服務。定位服務有著廣泛的前景,能夠極大地提升人們的生活質量,使人們的工作、娛樂、休閑、餐飲、購物等生活方式更便捷。

近些年,以安卓為代表的開源智能手機系統(tǒng)蓬勃發(fā)展,同時,硬件的成本也不斷降低,智能手機已成為大眾手機的主流。在生活中,可以看到安卓手機無處不在,通過使用智能手機也能方便地獲得親朋好友的地理位置,而這些都依賴于像GPS這樣的定位服務。GPS是戶外定位的最主流的解決方案,在戶外,GPS的定位精度能夠維持在10 m左右,對于日常使用而言已經(jīng)足夠了。

然而,如果嘗試著在室內環(huán)境下使用GPS來進行定位,比如在辦公室或者在家里使用手機定位,基本收不到GPS的衛(wèi)星信號,那么得到的定位誤差會很大。導致這一問題的主要原因在于室內復雜的環(huán)境干擾了衛(wèi)星信號的傳播,衛(wèi)星信號沒法穿越這么多的墻和障礙物。因此,需要專門的室內定位系統(tǒng)來為最后100 m的定位掃清障礙,彌補GPS系統(tǒng)的不足之處。

過去十年間,室內定位技術和算法發(fā)展迅速,大部分的室內定位系統(tǒng)都基于無線傳感網(wǎng)絡的信號處理分析?？傮w而言,室內定位系統(tǒng)可以分為兩大類:距離相關(range-based[1])或是距離無關(range-free[2])的。第1類距離相關的定位方法是早期室內定位的主流,例如像 TOA[3]、TDOA[4]、AOA[5]、RSSI[6]等方法。距離相關的方法通常需要昂貴的硬件和精確的數(shù)據(jù)支持,也給了距離無關方法巨大的成長空間。近些年,RSD[7]、EZ[8]、BT[9]、UnLoc[10]等距離無關算法相繼提出。然而,現(xiàn)有的距離無關算法也有各種各樣的缺陷,比如需要花費大量時間和精力來做指紋采集等,因而很難被應用于大規(guī)模的通用室內定位系統(tǒng)中。

然而,主流的定位算法研究都是基于水平方向的,在縱向定位上,室內定位的研究較少。現(xiàn)有的支持多樓層定位的算法大多基于在每層樓部署設備,從而可以通過最近的信號源的樓層來判別為當前定位樓層。

基于以上幾點,本文提出了基于快速部署的室內多樓層定位算法,與距離無關,且無需指紋采集,可快速地部署相應設備,應用于立體的大樓環(huán)境中,多樓層差分算法通過計算來自不同樓層信號差值的分布來區(qū)分樓層。

2 多樓層差分算法

與水平定位不同,豎直定位(樓層定位)的研究模型完全不同。樓層間的鋼筋混凝土墻的信號衰減量約為20 dB～40 dB[11],這比普通的磚墻(10 dB～15 dB)[9]要大得多。由于每隔一層樓都會有這樣的混凝土墻間隔,因此使用傳統(tǒng)的三角定位方式很難進行精確定位。本文提出了多樓層差分(Multistorey Differential,MSD)算法來解決樓層定位的問題。

2.1 多樓層定位原理

圖1是本文樓層定位的基本模型:假設大樓的高度為H,單位為m,層高為h,單位為m。在底樓(S1)和頂樓(S2)的同一豎直位置各放置一個信號源。因為只考慮豎直方向的定位,所以將三維坐標抽象為二維,分別是X方向(坐標點位置到原點位置的水平距離)以及Z方向(坐標點位置到XOY平面的豎直距離)。假設測試點的坐標P1為(x,z)。

圖1 MSD基本模型

定義 多樓層路徑衰減(Multi-storey Path Loss, MSPL)是自由空間路徑衰減(Free Space Path Loss, FSPL)的擴展,加入了樓層間鋼筋混凝土的衰減模型:

其中,PR是信號接收功率,單位為dBm;PT是信號發(fā)射功率,單位為dBm;GR是接收端天線增益,單位為dB;GT是發(fā)射端天線增益,單位為dB;N是信號穿過的樓層數(shù)量;LI是每一層穿墻的信號衰減(約20 dB～40 dB)[11]。

對于自由空間的衰減模型,接收功率可以表示為[12]:

結合式(2),代入λ=c/f,可以得到:

對于一般的信號傳播,信號頻率f的單位為MHz,距離d的單位為m。假設使用無線路由器作為發(fā)射源(f=2 400 MHz):

kMSPL是一個常數(shù),在當前假設下,kMSPL=40.05。

對于測試點(x,z),可以看到N等于z/h的下確界。對于信號源S1和S2,可以計算MSPL:

可以得到MSPLS1和MSPLS2的差值:

本文的目標是進行樓層定位,因而可以將數(shù)學推導和實際的模型相結合,即本文的研究重點是樓層而不是精確的高度值。

要區(qū)分樓層,假設每層樓的測試點,相對于本樓層水平面的高度是一致的,而絕對高度則是(Ni-1)·h,其中,Ni是當前樓層數(shù)。要區(qū)分樓層,需要證明在相鄰2個樓層的任意位置上,都能通過ΔMSPL來區(qū)分。

為了證明算法的可行性,在2個不同的樓層上選擇測試點,分別為P1(x1,z1),P2(x2,z2)。不妨設z1＜z2,即z2=z1+h。定義ΔDMSPL為2個測試點上ΔMSPL的差值:

需要減少x對于式(9)的影響?？紤]不同x的2種情況:

(1)x1=x2,那么:

將ΔDMSPL對x求導,可以得到:

當x→∞時,式(10)變?yōu)?

(2)x1≠x2,那么不妨假設x1＜x2。要區(qū)分不同樓層的測試點,需要分析極端情況:x1→0,x2→∞。式(10)變?yōu)?

式(12)～式(14)考慮了不同情況下ΔDMSPL的可能取值,而這些公式的第1項對于公式的貢獻較小(0～10 dB),而第 2項 2·LI的貢獻較大(40 dB～60 dB)。

通過以上推導,證明了在不同樓層下,可以通過ΔMSPL來區(qū)分不同樓層的測試點。

2.2 多對信號源下的復雜MSD模型

理論上可以用ΔMSPL的值來進行樓層定位,但是在實際情況下,由于復雜的室內環(huán)境和無線信號的波動性,需要設計一個穩(wěn)定的、可利用多對信號源的模型來提高樓層定位的準確性。

考慮實際的部署情況。需要在整棟樓中部署無線信號源。假設在第i層上,部署了mi個信號源。

本文算法的特性之一是快速部署,要盡量減少信號源的部署,同時盡量減少對精度的影響。因而,可以按照如下方式來部署信號源,即每隔n層布置m個節(jié)點。

當x＞0時,dΔDMSPL/dx＜0,因而ΔDMSPL隨著x的增大單調遞減。當x→0時,式(10)變?yōu)?

其中,m的取值決定于水平定位算法需要部署的信號源數(shù)量;n的取值決定于信號源可以穿透的樓層數(shù)。

當大樓超過n+1層時,將高樓分解為多個n+1層的子模型,從而應用本文的MSD算法。

因此,權重模型為:

3 實驗結果與分析

3.1 仿真實驗

為了驗證MSD算法的可靠性,做了一些仿真實驗。

3.1.1 一對信號源的MSD仿真

首先,設計仿真的大樓環(huán)境:在大樓的第一層和第(n+1)層的同一位置防止了2個信號源,并計算大樓內不同位置下的ΔMSPL。測試點的水平距離范圍為0～20 m,層高為3.5 m,鋼筋混凝土的信號衰減值為25 dB。圖2為不同n值情況下ΔMSPL的分布圖。

圖2 n=3,4,5,10時ΔMSPL的分布

3.1.2 多對信號源的MSD仿真

本節(jié)仿真了多對信號源情況下的MSD算法。仿真環(huán)境和3.1.1節(jié)實驗相同,并做出了相應的擴展:定義di為第i對信號源到原點的水平距離;n的取值為4。圖3展示了本文的仿真結果。

圖3 5對信號源時ΔMSPL的分布

3.1.3 仿真結果分析

通過以上的仿真實驗可以看出在同一樓層上,不同水平位置的點獲得的ΔMSPL值在一個很小的區(qū)間內波動,每一條ΔMSPL的樓層曲線基本與X軸垂直。當信號源增加時,曲線的波動更平滑,能夠更好地區(qū)分樓層。因此,理想環(huán)境下可以通過MSD算法來進行樓層定位。

3.2 平臺搭建與實驗結果

為了驗證實際環(huán)境中MSD算法的準確性,搭建了室內定位系統(tǒng)的平臺來進行實際的測試。

3.2.1 室內定位系統(tǒng)平臺

圖4展示了本文的室內定位系統(tǒng),該系統(tǒng)是一個普適的系統(tǒng),可以使用任何頻段或種類的信號源。為了方便部署與實驗,使用了無線路由器作為信號源,并使用了安卓智能手機作為信號的接收端。并在后臺搭建了服務器用于接收手機數(shù)據(jù)并進行數(shù)據(jù)處理與計算。

圖4 室內定位系統(tǒng)平臺

3.2.2 寢室樓內的實際實驗

圖5是本文進行實驗的具體環(huán)境。在1樓和3樓分別放置了2對路由器(間隔為10 m)?？梢钥吹铰酚善鞯男盘栯S著時間變化在波動。

圖5 實驗環(huán)境

分別在1,2,3層樓進行數(shù)據(jù)的采集工作。每隔2 m選擇一個測試點,在每個測試點記錄20個信號值,每次間隔5 s。圖6顯示了實驗的具體數(shù)據(jù),X軸為采樣時間,單位為s,Y軸為水平距離,單位為m,Z軸為信號強度,單位為dB。虛線和實線分別表示了1樓與3樓在同一水平位置2個路由器的信號強度分布。

圖6 樓層實驗的信號強度數(shù)據(jù)

然后使用本文的加權MSD模型來計算具體的加權信號值,并最終得到本文的ΔMSPL值。圖7及表1是本文的一些關鍵數(shù)據(jù),包括了ΔMSPL的均值、方差,以及ΔDMSPL。圖7(a)、圖7(b)、圖7(c)中的實線表示了1樓路由器的加權信號強度,虛線表示了3樓路由器的加權信號強度;圖7(d)顯示了3個樓層的ΔMSPL的分布情況。

圖7 加權信號強度及ΔMSPL分布

表1 實驗數(shù)據(jù)分析

4 結束語

本文介紹了一種基于快速部署的室內多樓層定位算法,結合水平方向的定位算法(如三角定位、區(qū)塊劃分算法)能為多層的大樓提供高精度、穩(wěn)定、便捷的室內定位解決方案。多樓層差分算法的提出彌補了室內定位領域縱向定位上的不足之處,能夠極大地減少信號源的部署,同時提高節(jié)點的利用率,達到本文快速部署且高精度與可靠性的目標。最后做了一系列仿真實驗,并搭建實際的定位系統(tǒng)來驗證算法的可靠性。更重要的是,低成本的基礎設施與快速部署的特性使本文系統(tǒng)在未來能夠有廣闊的應用前景。

[1] 李桔鴻.基于Range-based的無線傳感器網(wǎng)絡定位算法研究與改進[D].成都:西南交通大學,2012.

[2] 史 龍,王福豹,段渭軍,等.無線傳感器網(wǎng)絡Rangefree自身定位機制與算法[J].計算機工程與應用, 2004,40(23):127-130,151.

[3] 田孝華,廖桂生.一種有效減小非視距傳播影響的TOA定位方法[J].電子學報,2003,31(9):1429-1432.

[4] 劉 影.基于TDOA的無線傳感器網(wǎng)絡節(jié)點定位技術研究[D].長春:吉林大學,2008.

[5] Niculescu D,Nath B.Ad Hoc Positioning System(APS) Using AOA[C]//Proc.of the 23nd Annual Joint Conference of the IEEE Computer and Communications. [S.l.]:IEEE Press,2003:1734-1743.

[6] 方 震,趙 湛,郭 鵬,等.基于RSSI測距分析[J].傳感技術學報,2007,20(11):2526-2530.

[7] Zhong Ziguo,He Tian.Achieving Range-free Localization Beyond Connectivity[C]//Proc.of the 7th ACM Conference on Embedded Networked Sensor Systems. [S.l.]:ACM Press,2009:281-294.

[8] Chintalapudi K,Iyer A P,Padmanabhan V N.Indoor Localization Without the Pain[C]//Proc.of the 16th Annual International Conference on Mobile Computing and Networking.[S.l.]:ACM Press,2010:173-184.

[9] Chen Pengpeng,Zhong Ziguo,He Tian.Bubble Trace: Mobile Target Tracking Under Insufficient Anchor Coverage[C]//Proc.of the 31st International Conference on Distributed Computing Systems.[S.l.]:IEEE Press, 2011:770-779.

[10] Wang He,Sen S,Elogohary A,et al.Unsupervised Indoor Localization[D].Durham,UK:Duke University,2012.

[11] Gibson T B,Jenn D C.Prediction and Measurement of Wall Insertion Loss[J].IEEE Transactions on Antennas and Propagation,1999,47(1):55-57.

[12] Walfisch J,Bertoni H L.A Theoretical Model of UHF Propagation in Urban Environments[J].IEEE Transactions on Antenna and Propagation,1988,36(12):1788-1796.

編輯 任吉慧

Research of Indoor Multi-storey Localization Alogorithm Based on Quick Deployment

YU Min-jie,YI Ping,GUAN Han-nan
(School of Information Security Engineering,Shanghai Jiaotong University,Shanghai 200240,China)

The traditional GPS is hard to do localization in indoor environment due to the complicated walls and obstacles.The mainstream of localization alogorithm is conducted on horizontal direction,and method on vertical direction is still a new topic.This paper presents an on-demand indoor multi-storey localization alogorithm,which can be fingerprint-free and deployed rapidly and on-demand in a multi-storey building.On vertical direction,it proposes Multistorey Differential(MSD)alogorithm,the main idea of which is to differentiate the RSSI from different floors to distinguish the exact floor of test point.It conducts both simulation and practical experiments to prove the accuracy of this alogorithm.

Location Based Service(LBS);indoor localization system;multi-storey localization;Multi-storey Path Loss(MSPL)model;Multi-storey Differential(MSD)alogorithm;quick deployment

1000-3428(2014)09-0023-04

A

TP393.02

10.3969/j.issn.1000-3428.2014.09.005

國家“973”計劃基金資助項目(2013CB329603);國家自然科學基金資助項目(61271220,61170164,60932003)。

俞敏杰(1989-),男,碩士研究生,主研方向:無線Mesh網(wǎng)絡,實時操作系統(tǒng),室內定位;易 平,副教授、博士;關漢男,碩士研究生。

2013-10-08

2013-11-10E-mail:ymj1037@sjtu.edu.cn