陳業(yè)斌,王仁偉
(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽馬鞍山 243032)
基于智能手機(jī)自適應(yīng)信號(hào)校正的室內(nèi)定位算法
陳業(yè)斌,王仁偉
(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽馬鞍山 243032)
隨著智能手機(jī)和無線通信技術(shù)的迅速發(fā)展,人們對(duì)基于室內(nèi)定位的應(yīng)用需求日益增多。由于在室內(nèi)環(huán)境下智能手機(jī)接收到的信號(hào)強(qiáng)度波動(dòng)性較大,導(dǎo)致基于信號(hào)強(qiáng)度值的三角形加權(quán)質(zhì)心定位算法定位精度低。三角形加權(quán)質(zhì)心算法是基于無線測距的定位算法,其定位誤差是無線測距不精確導(dǎo)致的。無線測距是根據(jù)無線信號(hào)傳播的衰減模型利用接收信號(hào)強(qiáng)度來估計(jì)距離。無線信號(hào)在室內(nèi)環(huán)境下的傳播過程中,由于障礙物的遮蔽效應(yīng)、信號(hào)的反射、多徑效應(yīng)等因素的影響,使得定位節(jié)點(diǎn)與參考節(jié)點(diǎn)的真實(shí)距離越大則估計(jì)距離的誤差越大。針對(duì)以上問題,本文提出一種自適應(yīng)信號(hào)校正定位算法,該算法采用節(jié)點(diǎn)間距離公式的導(dǎo)數(shù)作為權(quán)值參數(shù)對(duì)距離進(jìn)行修正,從而進(jìn)一步提高定位精度。實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的有效性,與現(xiàn)有定位算法比較,精度提高35.9%。
自適應(yīng)信號(hào)校正;RSSI;室內(nèi)定位;三角形加權(quán)質(zhì)心
近年來,全球定位系統(tǒng)(GPS)[1]技術(shù)已經(jīng)越來越廣泛應(yīng)用于人們的日常工作和生活中,如導(dǎo)航、跟蹤、定位、測繪等。由于建筑物內(nèi)金屬的屏蔽效應(yīng),GPS在室內(nèi)環(huán)境下的定位精度不高。隨著各種無線通信技術(shù)的迅速發(fā)展以及移動(dòng)智能設(shè)備的不斷普及,人們對(duì)在室內(nèi)環(huán)境下的基于位置的服務(wù)需求日益迫切,如智慧校園、智慧工廠、未來商店等。目前,Wi-Fi無線網(wǎng)絡(luò)已經(jīng)廣泛分布于校園、商場、住宅和辦公樓等大型室內(nèi)環(huán)境,與此同時(shí),智能移動(dòng)設(shè)備的功能不斷增強(qiáng),不僅包含了加速度、磁力、陀螺儀、溫度等多種高精度傳感器,而且處理數(shù)據(jù)的能力更強(qiáng)、工作頻率也更高。因此,利用智能手機(jī)與Wi-Fi網(wǎng)絡(luò)進(jìn)行室內(nèi)定位具有良好的應(yīng)用前景。
目前,基于智能手機(jī)的定位算法可分為兩類:基于測距定位算法和基于指紋數(shù)據(jù)庫定位算法?;跍y距的定位算法主要包括:基于時(shí)間到達(dá)(Time of Arrival,TOA)[2-3],基于到達(dá)時(shí)間差(Time Difference of Arrival,TDOA)[4-5],基于到達(dá)角度(Angle of Arrival,AOA)[6-7]和基于接收信號(hào)強(qiáng)度指示(Received Signal Strength Indication,RSSI)[8-10]等。其中,TOA和TDOA算法是利用精密的光學(xué)儀器測得信號(hào)的到達(dá)時(shí)間和到達(dá)時(shí)間差,由于光速是已知的,根據(jù)時(shí)間和光速得到距離,最后利用三角定位算法得到定位節(jié)點(diǎn)坐標(biāo);RSSI算法是通過信號(hào)衰減模型根據(jù)信號(hào)強(qiáng)度值得到距離,也是利用三角定位算法得到定位節(jié)點(diǎn)的坐標(biāo);AOA算法是通過某些硬件設(shè)備感知發(fā)射節(jié)點(diǎn)信號(hào)的到達(dá)方向,計(jì)算定位節(jié)點(diǎn)和參考節(jié)點(diǎn)之間的相對(duì)方向或角度,然后再利用三角測量法計(jì)算出定位節(jié)點(diǎn)的坐標(biāo)?;谥讣y數(shù)據(jù)庫的算法主要分為兩個(gè)階段:離線階段和定位階段。離線階段是采集RSS(Receive Signal Strength)指紋和位置信息并保存到數(shù)據(jù)庫中;定位階段是根據(jù)采集的RSS信息與數(shù)據(jù)庫中RSS指紋去匹配并得到位置信息。指紋數(shù)據(jù)庫算法的優(yōu)點(diǎn)是定位精度高,易實(shí)現(xiàn);但是它的缺點(diǎn)也是顯而易見的,在離線階段需要花費(fèi)大量的人力和物力去采集RSS指紋,而且只要室內(nèi)環(huán)境變化則需要重新采集RSS指紋,可適用性較低。
基于測距的定位算法可適用性較高,然而其定位精度不高,可通過改進(jìn)三角定位算法提高其定位精度?,F(xiàn)有關(guān)于三角定位的研究主要是基于RSSI的三角加權(quán)質(zhì)心算法,它修正了距離遠(yuǎn)近對(duì)質(zhì)心位置的偏差,并取得了一定的定位效果。然而導(dǎo)致三角定位的誤差的根本原因是距離大小不準(zhǔn)確;由于室內(nèi)障礙物的遮蔽效應(yīng)、多徑傳播以及信號(hào)的反射作用,在測距階段使得定位節(jié)點(diǎn)與參考節(jié)點(diǎn)的真實(shí)距離越大則估計(jì)距離的誤差越大,從而導(dǎo)致定位誤差越大,現(xiàn)有的定位算法并沒有考慮到這一關(guān)鍵問題。針對(duì)這一不足,本文提出一種自適應(yīng)信號(hào)校正定位算法。
一般常用的無線信號(hào)傳播路徑損耗模型如下:自由空間傳播模型、對(duì)數(shù)距離路徑損耗模型、Hata模型[11]、對(duì)數(shù)-常態(tài)分布模型等。在實(shí)際環(huán)境中,由于多徑、障礙物、繞射等隨機(jī)因素,目前基于RSSI的定位采用更為合理的對(duì)數(shù)-常態(tài)分布模型。對(duì)數(shù)-常態(tài)分布模型數(shù)學(xué)表達(dá)式如下:
PL(d)=PL(d1)+10nlg(d/d1)+x1.
(1)
其中,d為發(fā)射節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離,單位為m;d1為單位距離,通常取1m;PL(d)為經(jīng)過距離d后的路徑損耗;x1為均值為0的高斯隨機(jī)分布,其標(biāo)準(zhǔn)差范圍為4~10;n為信號(hào)衰減因子。
接收節(jié)點(diǎn)接收到的RSS值表達(dá)式如下:
RSS=Pt-PL(d).
(2)
其中,Pt為發(fā)射節(jié)點(diǎn)的發(fā)射功率,設(shè)在d0的信號(hào)強(qiáng)度為A,則由(2)可知:
PL(d1)=Pt-A.
(3)
將(3)代入到(1)中可得:
PL(d)=Pt-A+10nlg(d/d1)+x1.
(4)
由于d1通常取1m且x1均值期望為0,所以(4)可簡化為:
PL(d)=Pt-A+10nlgd.
(5)
將(5)代入(2)中可得:
RSS=A-10nlgd.
(6)
將(6)進(jìn)行轉(zhuǎn)化得到(7)如下:
(7)
3.1 三角加權(quán)質(zhì)心定位算法
在室內(nèi)環(huán)境下,由于障礙物的遮蔽效應(yīng)、信號(hào)的反射、多徑效應(yīng)等因素的影響,使得采用信號(hào)強(qiáng)度值估計(jì)的距離與真實(shí)距離存在誤差。如圖1所示,A、B、C是3個(gè)不共線的參考節(jié)點(diǎn),由于室內(nèi)環(huán)境是復(fù)雜多變的,這3個(gè)節(jié)點(diǎn)面對(duì)的環(huán)境也是不同的,故分別模擬出這3個(gè)節(jié)點(diǎn)的無線信號(hào)衰減模型。A、B、C向四周發(fā)射信號(hào)的過程中,在定位節(jié)點(diǎn)處會(huì)接收到A、B、C的信號(hào)強(qiáng)度,在分別根據(jù)各自的無線信號(hào)損耗模型計(jì)算出A、B、C與定位節(jié)點(diǎn)的距離依次為dA、dB、dC。分別以A、B、C為圓心,以dA、dB、dC為半徑畫圓;3個(gè)圓會(huì)相交出3個(gè)點(diǎn),分別計(jì)算出這3個(gè)點(diǎn)的坐標(biāo),以這3個(gè)點(diǎn)為頂點(diǎn)可以組成一個(gè)三角形,三角形的質(zhì)心可近似為未知節(jié)點(diǎn)的坐標(biāo)。
圖1 加權(quán)質(zhì)心算法原理圖
3.2 自適應(yīng)信號(hào)校正定位算法
前面三角加權(quán)質(zhì)心算法雖然考慮到了距離的不同對(duì)定位造成的不同影響,并提出加權(quán)因子,在定位精度方面取得了進(jìn)步,但是誤差較大現(xiàn)象依然客觀存在。無線信號(hào)在向外輻射的過程中,隨著距離的增大能量衰減越快,信號(hào)強(qiáng)度值偏差也就越來越大;從公式(7)中可以發(fā)現(xiàn),距離公式是一個(gè)指數(shù)型函數(shù),所以真實(shí)距離越大,則估計(jì)距離與真實(shí)距離的誤差越大。在實(shí)際實(shí)驗(yàn)中,我們發(fā)現(xiàn)定位節(jié)點(diǎn)與參考節(jié)點(diǎn)的距離越近,信號(hào)強(qiáng)度值的偏差越小,距離估計(jì)的偏差也越小;定位節(jié)點(diǎn)與參考節(jié)點(diǎn)相距越遠(yuǎn),信號(hào)強(qiáng)度值的偏差越大,距離估計(jì)的偏差也越大。
導(dǎo)致定位誤差的根本原因是測距的不精確,若所測得的距離值都是真實(shí)值,那么計(jì)算出來的定位節(jié)點(diǎn)坐標(biāo)就是真實(shí)的坐標(biāo)。正是由于測距誤差的存在,才會(huì)導(dǎo)致定位的誤差。測距誤差的大小直接決定了定位誤差大小,并且測距誤差越大,定位誤差也會(huì)變大。針對(duì)這一現(xiàn)象,故提出自適應(yīng)信號(hào)校正定位算法。自適應(yīng)信號(hào)校正算法通過自適應(yīng)地修正3個(gè)距離值以提高定位精度。
在實(shí)驗(yàn)的物理環(huán)境中,定位節(jié)點(diǎn)到3個(gè)參考節(jié)點(diǎn)的距離不同,偏差也就不同,修正值也不同。鑒于每一個(gè)距離值都不一樣,我們采用類似于梯度下降的方法去修正距離。可以發(fā)現(xiàn)Δd=f′(RSS)·ΔRSS。于是我們可以進(jìn)行如下變換:
(8)
其中,dA、dB、dC分別是定位節(jié)點(diǎn)到參考節(jié)點(diǎn)A、B、C的距離,f′(RSS)是f(RSS)的導(dǎo)函數(shù),這樣對(duì)于不用的距離值都可以進(jìn)行正確的修正。再根據(jù)三角加權(quán)質(zhì)心計(jì)算定位節(jié)點(diǎn)的坐標(biāo),三個(gè)圓的交點(diǎn)坐標(biāo)分為公式如下:
(9)
算法的實(shí)現(xiàn)步驟如下:
算法:自適應(yīng)信號(hào)校正定位算法 Input:RSS1,RSS2,RSS3數(shù)組;l1,l2,l3三個(gè)AP的坐標(biāo) Output:(X,Y)定位節(jié)點(diǎn)的坐標(biāo)sum1=sum2=sum3=0; for i=1,2,…,ndo sum1=sum1+RSS1[i]; sum2=sum2+RSS2[i]; sum3=sum3+RSS3[i];end[rss1,rss2,rss3]=[sum1/n,sum2/n,sum3/n];[d1,d2,d3]=[f1(rss1),f2(rss2),f3(rss3)];[c1,c2,c3]=[(l1,d1),(l2,d2),(l3,d3)];S=Area(c1,c2,c3);//計(jì)算三個(gè)圓形的公共面積while(S>)//是閾值 d1=d1-f1’(rss1)*; d2=d2-f2’(rss2)*; d3=d3-f3’(rss3)*;end[c1,c2,c3]=[(l1,d1),(l2,d2),(l3,d3)];[(XA,YA),(XB,YB),(XC,YC)]=getPublicPoints(c1,c2,c3);[X,Y]=getLocation((XA,YA),(XB,YB),(XC,YC));//根據(jù)公式(9)
4.1 實(shí)驗(yàn)環(huán)境的搭建
實(shí)驗(yàn)的物理環(huán)境是我們平時(shí)用來學(xué)習(xí)的實(shí)驗(yàn)室,長度為10m,寬度為8m。把3個(gè)TP-LINK的單天線的路由器作為802.11n信號(hào)接入點(diǎn)部署到實(shí)驗(yàn)室,整個(gè)實(shí)驗(yàn)環(huán)境如圖2和圖3所示,圖2為較復(fù)雜的實(shí)驗(yàn)環(huán)境,圖3為一般實(shí)驗(yàn)環(huán)境。
圖2 較復(fù)雜的實(shí)驗(yàn)環(huán)境甲平面效果圖
圖3 一般實(shí)驗(yàn)環(huán)境乙平面效果圖
4.2 信號(hào)衰減模型的模擬
無線信號(hào)的衰減模型其實(shí)就是距離與信號(hào)強(qiáng)度值的一個(gè)映射關(guān)系,這個(gè)映射關(guān)系即式(7),其中含有兩個(gè)參數(shù)。我們?cè)诓煌嚯x測量信號(hào)強(qiáng)度值,通過機(jī)器學(xué)習(xí)的方法監(jiān)督學(xué)習(xí)這兩個(gè)參數(shù)。
4.3 距離評(píng)估的誤差分析
無線信號(hào)在向外輻射過程中,隨著距離增大,能量衰減加快。前面我們已經(jīng)模擬出了無線信號(hào)的衰減模型,采集的信號(hào)強(qiáng)度值通過信號(hào)的衰減模型計(jì)算出評(píng)估距離,從而可以得到評(píng)估距離和真實(shí)距離的誤差。經(jīng)過反復(fù)和大量的實(shí)驗(yàn),結(jié)果如圖4所示。
圖4 真實(shí)距離與估算距離之間的誤差圖
4.4 實(shí)驗(yàn)過程
整個(gè)實(shí)驗(yàn)過程包括準(zhǔn)備階段和定位階段(圖5)。
圖5 整個(gè)定位過程的流程圖
4.4.1 準(zhǔn)備階段
Step1:采集數(shù)據(jù)。將移動(dòng)節(jié)點(diǎn)依次置于預(yù)先部署好的位置已知的參考點(diǎn),采集路由節(jié)點(diǎn)的RSS信息及其距離信息,得到訓(xùn)練樣本數(shù)據(jù)集。
Step2:數(shù)據(jù)過濾。由于室內(nèi)環(huán)境較為復(fù)雜,再加上信號(hào)擁塞等因素的影響,智能手機(jī)接收的RSS信息復(fù)雜多變,原始數(shù)據(jù)含有較高的噪音。在數(shù)據(jù)過濾階段,采用均值進(jìn)行過濾,以提高訓(xùn)練樣本的質(zhì)量。
Step3:通過最小二乘法對(duì)樣本數(shù)據(jù)模擬無線信號(hào)衰減模型,利用最小二乘法模擬過濾后的樣本數(shù)據(jù)集,可得到式(6)中的A和n兩個(gè)參數(shù)。
4.4.2 定位階段
Step1:采集RSS數(shù)據(jù)。Linux一句命令就可以掃描所有的AP并獲取AP信息,Android系統(tǒng)內(nèi)核基于Linux,在安卓手機(jī)上部署相關(guān)應(yīng)用即可采集RSS信息。
Step2:RSS預(yù)處理。由于RSS信息易受干擾,復(fù)雜多變,手機(jī)獲取RSS具有緩存機(jī)制,剛開始采集的RSS都是上一次時(shí)刻采集的RSS信息。故先刪除所采集的RSS信息的前小部分,然后再進(jìn)行均值過濾以提高RSS信息質(zhì)量。
Step3:距離變量循環(huán)更新。由于信號(hào)受障礙物的遮蔽效應(yīng),定位節(jié)點(diǎn)與參考節(jié)點(diǎn)的真實(shí)距離越大則估計(jì)距離的誤差越大。故采用循環(huán)更新方法對(duì)距離變量進(jìn)行修正。
Step4:定位坐標(biāo)。對(duì)距離變量進(jìn)行修正之后再進(jìn)行三角加權(quán)質(zhì)心定位,利用式(9)進(jìn)行坐標(biāo)計(jì)算,得到實(shí)驗(yàn)結(jié)果。
4.4.3 實(shí)驗(yàn)結(jié)果分析
實(shí)驗(yàn)結(jié)果如圖6所示,在實(shí)驗(yàn)環(huán)境甲下,經(jīng)過計(jì)算得到質(zhì)心算法的平均誤差為2.59m,加權(quán)質(zhì)心算法的平均誤差為2.45m,自適應(yīng)信號(hào)修正算法的平均誤差為1.57m。從圖7中也驗(yàn)證了本文所改進(jìn)算法對(duì)定位精度的明顯提高。
圖6 實(shí)驗(yàn)環(huán)境甲定位誤差圖
圖7 實(shí)驗(yàn)環(huán)境乙定位誤差圖
圖6中自適應(yīng)修正算法的誤差在質(zhì)心算法和加權(quán)質(zhì)心算法的下方,從而驗(yàn)證了本文所改進(jìn)算法對(duì)定位精度的明顯提高。在實(shí)驗(yàn)環(huán)境乙下,質(zhì)心算法的平均誤差為2.608m,加權(quán)質(zhì)心算法的平均誤差為2.272m,自適應(yīng)信號(hào)修正算法的平均誤差為1.552m。從圖2和圖3中可以看出實(shí)驗(yàn)環(huán)境乙比實(shí)驗(yàn)環(huán)境甲要空曠一些,故實(shí)驗(yàn)環(huán)境乙的定位誤差相對(duì)較高。
基于RSSI測距的三角形加權(quán)質(zhì)心算法在實(shí)際定位應(yīng)用中有較大的誤差,這種誤差完全是由環(huán)境因素使RSSI測距不準(zhǔn)確導(dǎo)致的。本文在三角加權(quán)質(zhì)心算法的基礎(chǔ)上,根據(jù)RSSI的衰減模型為測試距離提供修正因子以保證定位精度,提出了自適應(yīng)信號(hào)校正定位算法。根據(jù)實(shí)驗(yàn)結(jié)果對(duì)比可知,在相同條件下,自適應(yīng)信號(hào)校正定位算法的實(shí)驗(yàn)效果明顯優(yōu)于三角形加權(quán)質(zhì)心算法,定位精度可提高35.9%。在不同環(huán)境中,復(fù)雜環(huán)境比一般環(huán)境定位精度要低很多。
[1]Liu H,Darabi H,Banerjee P,et al.Survey of wireless indoor positioning techniques and systems[J].IEEE Transactions on Systems,Man and Cybernetics,Part C:Applications and Reviews,2007(6):1067-1080.
[2]Wang X,Wang Z,O Dea B.A TOA-based location algorithm reducing the errors due to non-line-of-sight(NLOS) propagation[J].IEEE Transactions on Vehicular Technology,2003(1):112-116.
[3]王沁,何杰,張前雄,等.測距誤差分級(jí)的室內(nèi) TOA 定位算法[J].儀器儀表學(xué)報(bào),2011(12):2851-2856.
[4]張毅,汪紀(jì)鋒,李柱.移動(dòng)通信信號(hào)到達(dá)時(shí)間差定位的估計(jì)[J].系統(tǒng)工程與電子技術(shù),2001(7):27-29.
[5]Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C].IEEE/RSJ International Conference on Intelligent Robots and Systems,Proceedings,2001:1312-1320.
[6]Niculescu D, Nath B. Ad hoc positioning system (APS) using AOA[C].Proceedings-IEEE INFOCOM,2003:1734-1743.
[7]王梓有,周憲英.無線傳感器網(wǎng)絡(luò)基于信號(hào)到達(dá)角度的節(jié)點(diǎn)定位算法研究[J].艦船電子工程,2012(7):40-42.
[8]王振朝,張琦,張峰.基于 RSSI 測距的改進(jìn)加權(quán)質(zhì)心定位算法[J].電測與儀表,2014(21):63-66.
[9]張蒼松,郭軍,崔嬌,等.基于 RSSI 的室內(nèi)定位算法優(yōu)化技術(shù)[J].Computer Engineering and Applications,2015(3): 235-238.
[10]陳順明,李平.基于 RSSI 權(quán)值的環(huán)境適應(yīng)型室內(nèi)定位算法研究[J].Computer Engineering and Applications,2015(22): 99-103.
[11]吳彥鴻,王聰,徐燦.無線通信系統(tǒng)中電波傳播路徑損耗模型研究[J].國外電子測量技術(shù),2009(8):35-37.
[12]陳維克,李文峰,首珩,等.基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學(xué)學(xué)報(bào),2006(12):2695-2700.
[13]陳祠,牟楠,張晨,等.基于主成分分析的室內(nèi)指紋定位模型[J].軟件學(xué)報(bào),2013(1):98-107.
[14]蔡文學(xué),邱珠成,黃曉宇,等.基于 WiFi 指紋的室內(nèi)軌跡定位模型[J].計(jì)算機(jī)工程,2015(6):76-82.
[15]Kotaru M,Joshi K,Bharadia D,et al.Spotfi:Decimeter level localization using WiFi[C].Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication,ACM,2015:269-282.
[16]He S,Hu T,Chan S H G.Contour-based Trilateration for Indoor Fingerprinting Localization[C].Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems,ACM,2015:225-238.
The Apaptive Signal Correct of Indoor Position Algorithm Based on Smart Phone
CHEN Ye-bin, WANG Ren-wei
(Anhui University of Technology School of Computer Science and Technology,Ma’anshan Anhui 243032, China)
With the rapid development of smart phones and wireless communication technology, the demand for the application of indoor positioning is increasing. Due to the large fluctuation of signal intensity in the indoor environment, the triangle weighted centroid localization algorithm based on the value of the signal intensity is low. Triangle weighted centroid algorithm is based on the wireless location algorithm, and its positioning error is caused by inaccurate wireless ranging. Wireless ranging is based on the attenuation model of the radio signal to estimate the distance by using the received signal strength. Wireless signal propagation in indoor environments, due to the obstacles of the shadowing effect, the signal reflection and multi-path effect, the real distance positioning node and the reference node is estimated the distance error is large. In view of the above problems, this paper proposes an adaptive signal correction algorithm, which uses the derivative of the distance between the nodes as the weight parameters to correct the distance, and further improve the positioning accuracy. Experimental results show that the proposed algorithm is effective, and the accuracy of the proposed algorithm is improved by 35.9% compared with the existing algorithm.
adaptive signal correction; RSSI; indoor position;triangle weighted centroid
2016-07-28
安徽高校自然科學(xué)研究重大項(xiàng)目“雙環(huán)網(wǎng)絡(luò)并行路由策略的研究”(KJ2015ZD39)。
陳業(yè)斌(1971- ),男,教授,碩士生導(dǎo)師,從事計(jì)算機(jī)網(wǎng)絡(luò)及數(shù)據(jù)庫研究。
王仁偉(1991- ),男,碩士研究生,從事無線傳感器網(wǎng)絡(luò)及稀疏編碼等研究。
TN911
A
2095-7602(2017)02-0010-07