俞敏杰,易 平,關(guān)漢男

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

基于快速部署的室內(nèi)多樓層定位算法研究

俞敏杰,易 平,關(guān)漢男

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

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

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

1 概述

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

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

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

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

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

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

2 多樓層差分算法

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

2.1 多樓層定位原理

圖1是本文樓層定位的基本模型:假設(shè)大樓的高度為H,單位為m,層高為h,單位為m。在底樓(S1)和頂樓(S2)的同一豎直位置各放置一個(gè)信號(hào)源。因?yàn)橹豢紤]豎直方向的定位,所以將三維坐標(biāo)抽象為二維,分別是X方向(坐標(biāo)點(diǎn)位置到原點(diǎn)位置的水平距離)以及Z方向(坐標(biāo)點(diǎn)位置到XOY平面的豎直距離)。假設(shè)測(cè)試點(diǎn)的坐標(biāo)P1為(x,z)。

圖1 MSD基本模型

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

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

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

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

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

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

對(duì)于測(cè)試點(diǎn)(x,z),可以看到N等于z/h的下確界。對(duì)于信號(hào)源S1和S2,可以計(jì)算MSPL:

可以得到MSPLS1和MSPLS2的差值:

本文的目標(biāo)是進(jìn)行樓層定位,因而可以將數(shù)學(xué)推導(dǎo)和實(shí)際的模型相結(jié)合,即本文的研究重點(diǎn)是樓層而不是精確的高度值。

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

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

需要減少x對(duì)于式(9)的影響。考慮不同x的2種情況:

(1)x1=x2,那么:

將ΔDMSPL對(duì)x求導(dǎo),可以得到:

當(dāng)x→∞時(shí),式(10)變?yōu)?

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

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

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

2.2 多對(duì)信號(hào)源下的復(fù)雜MSD模型

理論上可以用ΔMSPL的值來進(jìn)行樓層定位,但是在實(shí)際情況下,由于復(fù)雜的室內(nèi)環(huán)境和無線信號(hào)的波動(dòng)性,需要設(shè)計(jì)一個(gè)穩(wěn)定的、可利用多對(duì)信號(hào)源的模型來提高樓層定位的準(zhǔn)確性。

考慮實(shí)際的部署情況。需要在整棟樓中部署無線信號(hào)源。假設(shè)在第i層上,部署了mi個(gè)信號(hào)源。

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

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

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

當(dāng)大樓超過n+1層時(shí),將高樓分解為多個(gè)n+1層的子模型,從而應(yīng)用本文的MSD算法。

因此,權(quán)重模型為:

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

3.1 仿真實(shí)驗(yàn)

為了驗(yàn)證MSD算法的可靠性,做了一些仿真實(shí)驗(yàn)。

3.1.1 一對(duì)信號(hào)源的MSD仿真

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

圖2 n=3,4,5,10時(shí)ΔMSPL的分布

3.1.2 多對(duì)信號(hào)源的MSD仿真

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

圖3 5對(duì)信號(hào)源時(shí)ΔMSPL的分布

3.1.3 仿真結(jié)果分析

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

3.2 平臺(tái)搭建與實(shí)驗(yàn)結(jié)果

為了驗(yàn)證實(shí)際環(huán)境中MSD算法的準(zhǔn)確性,搭建了室內(nèi)定位系統(tǒng)的平臺(tái)來進(jìn)行實(shí)際的測(cè)試。

3.2.1 室內(nèi)定位系統(tǒng)平臺(tái)

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

圖4 室內(nèi)定位系統(tǒng)平臺(tái)

3.2.2 寢室樓內(nèi)的實(shí)際實(shí)驗(yàn)

圖5是本文進(jìn)行實(shí)驗(yàn)的具體環(huán)境。在1樓和3樓分別放置了2對(duì)路由器(間隔為10 m)。可以看到路由器的信號(hào)隨著時(shí)間變化在波動(dòng)。

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

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

圖6 樓層實(shí)驗(yàn)的信號(hào)強(qiáng)度數(shù)據(jù)

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

圖7 加權(quán)信號(hào)強(qiáng)度及ΔMSPL分布

表1 實(shí)驗(yàn)數(shù)據(jù)分析

4 結(jié)束語

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

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

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

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

[4] 劉 影.基于TDOA的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D].長春:吉林大學(xué),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測(cè)距分析[J].傳感技術(shù)學(xué)報(bào),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”計(jì)劃基金資助項(xiàng)目(2013CB329603);國家自然科學(xué)基金資助項(xiàng)目(61271220,61170164,60932003)。

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

2013-10-08

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