基于智能手機自適應信號校正的室內定位算法

陳業斌，王仁偉

(安徽工業大學計算機科學與技術學院，安徽馬鞍山 243032)

基于智能手機自適應信號校正的室內定位算法

陳業斌，王仁偉

(安徽工業大學計算機科學與技術學院，安徽馬鞍山 243032)

隨著智能手機和無線通信技術的迅速發展，人們對基于室內定位的應用需求日益增多。由于在室內環境下智能手機接收到的信號強度波動性較大，導致基于信號強度值的三角形加權質心定位算法定位精度低。三角形加權質心算法是基于無線測距的定位算法，其定位誤差是無線測距不精確導致的。無線測距是根據無線信號傳播的衰減模型利用接收信號強度來估計距離。無線信號在室內環境下的傳播過程中，由于障礙物的遮蔽效應、信號的反射、多徑效應等因素的影響，使得定位節點與參考節點的真實距離越大則估計距離的誤差越大。針對以上問題，本文提出一種自適應信號校正定位算法，該算法采用節點間距離公式的導數作為權值參數對距離進行修正，從而進一步提高定位精度。實驗結果驗證了該算法的有效性，與現有定位算法比較,精度提高35.9%。

自適應信號校正；RSSI；室內定位；三角形加權質心

1 引言

近年來，全球定位系統(GPS)[1]技術已經越來越廣泛應用于人們的日常工作和生活中，如導航、跟蹤、定位、測繪等。由于建筑物內金屬的屏蔽效應，GPS在室內環境下的定位精度不高。隨著各種無線通信技術的迅速發展以及移動智能設備的不斷普及，人們對在室內環境下的基于位置的服務需求日益迫切，如智慧校園、智慧工廠、未來商店等。目前，Wi-Fi無線網絡已經廣泛分布于校園、商場、住宅和辦公樓等大型室內環境，與此同時，智能移動設備的功能不斷增強，不僅包含了加速度、磁力、陀螺儀、溫度等多種高精度傳感器，而且處理數據的能力更強、工作頻率也更高。因此，利用智能手機與Wi-Fi網絡進行室內定位具有良好的應用前景。

目前，基于智能手機的定位算法可分為兩類：基于測距定位算法和基于指紋數據庫定位算法。基于測距的定位算法主要包括：基于時間到達(Time of Arrival，TOA)[2-3],基于到達時間差(Time Difference of Arrival，TDOA)[4-5]，基于到達角度(Angle of Arrival，AOA)[6-7]和基于接收信號強度指示(Received Signal Strength Indication，RSSI)[8-10]等。其中，TOA和TDOA算法是利用精密的光學儀器測得信號的到達時間和到達時間差，由于光速是已知的，根據時間和光速得到距離，最后利用三角定位算法得到定位節點坐標；RSSI算法是通過信號衰減模型根據信號強度值得到距離，也是利用三角定位算法得到定位節點的坐標；AOA算法是通過某些硬件設備感知發射節點信號的到達方向，計算定位節點和參考節點之間的相對方向或角度，然后再利用三角測量法計算出定位節點的坐標。基于指紋數據庫的算法主要分為兩個階段：離線階段和定位階段。離線階段是采集RSS(Receive Signal Strength)指紋和位置信息并保存到數據庫中；定位階段是根據采集的RSS信息與數據庫中RSS指紋去匹配并得到位置信息。指紋數據庫算法的優點是定位精度高，易實現；但是它的缺點也是顯而易見的，在離線階段需要花費大量的人力和物力去采集RSS指紋，而且只要室內環境變化則需要重新采集RSS指紋，可適用性較低。

基于測距的定位算法可適用性較高，然而其定位精度不高，可通過改進三角定位算法提高其定位精度。現有關于三角定位的研究主要是基于RSSI的三角加權質心算法，它修正了距離遠近對質心位置的偏差，并取得了一定的定位效果。然而導致三角定位的誤差的根本原因是距離大小不準確；由于室內障礙物的遮蔽效應、多徑傳播以及信號的反射作用，在測距階段使得定位節點與參考節點的真實距離越大則估計距離的誤差越大，從而導致定位誤差越大，現有的定位算法并沒有考慮到這一關鍵問題。針對這一不足，本文提出一種自適應信號校正定位算法。

2 無線信號傳播模型

一般常用的無線信號傳播路徑損耗模型如下：自由空間傳播模型、對數距離路徑損耗模型、Hata模型[11]、對數-常態分布模型等。在實際環境中，由于多徑、障礙物、繞射等隨機因素，目前基于RSSI的定位采用更為合理的對數-常態分布模型。對數-常態分布模型數學表達式如下：

PL(d)=PL(d1)+10nlg(d/d1)+x1.

(1)

其中，d為發射節點與目標節點的距離，單位為m；d1為單位距離，通常取1m；PL(d)為經過距離d后的路徑損耗；x1為均值為0的高斯隨機分布，其標準差范圍為4～10；n為信號衰減因子。

接收節點接收到的RSS值表達式如下：

RSS=Pt-PL(d).

(2)

其中，Pt為發射節點的發射功率，設在d0的信號強度為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)進行轉化得到(7)如下：

(7)

3 室內定位算法

3.1 三角加權質心定位算法

在室內環境下，由于障礙物的遮蔽效應、信號的反射、多徑效應等因素的影響，使得采用信號強度值估計的距離與真實距離存在誤差。如圖1所示，A、B、C是3個不共線的參考節點，由于室內環境是復雜多變的，這3個節點面對的環境也是不同的，故分別模擬出這3個節點的無線信號衰減模型。A、B、C向四周發射信號的過程中，在定位節點處會接收到A、B、C的信號強度，在分別根據各自的無線信號損耗模型計算出A、B、C與定位節點的距離依次為dA、dB、dC。分別以A、B、C為圓心，以dA、dB、dC為半徑畫圓；3個圓會相交出3個點，分別計算出這3個點的坐標，以這3個點為頂點可以組成一個三角形，三角形的質心可近似為未知節點的坐標。

圖1 加權質心算法原理圖

3.2 自適應信號校正定位算法

前面三角加權質心算法雖然考慮到了距離的不同對定位造成的不同影響，并提出加權因子，在定位精度方面取得了進步，但是誤差較大現象依然客觀存在。無線信號在向外輻射的過程中，隨著距離的增大能量衰減越快，信號強度值偏差也就越來越大；從公式(7)中可以發現，距離公式是一個指數型函數，所以真實距離越大，則估計距離與真實距離的誤差越大。在實際實驗中，我們發現定位節點與參考節點的距離越近，信號強度值的偏差越小，距離估計的偏差也越小；定位節點與參考節點相距越遠，信號強度值的偏差越大，距離估計的偏差也越大。

導致定位誤差的根本原因是測距的不精確，若所測得的距離值都是真實值，那么計算出來的定位節點坐標就是真實的坐標。正是由于測距誤差的存在，才會導致定位的誤差。測距誤差的大小直接決定了定位誤差大小，并且測距誤差越大,定位誤差也會變大。針對這一現象，故提出自適應信號校正定位算法。自適應信號校正算法通過自適應地修正3個距離值以提高定位精度。

在實驗的物理環境中，定位節點到3個參考節點的距離不同，偏差也就不同，修正值也不同。鑒于每一個距離值都不一樣，我們采用類似于梯度下降的方法去修正距離?？梢园l現Δd=f′(RSS)·ΔRSS。于是我們可以進行如下變換：

(8)

其中,dA、dB、dC分別是定位節點到參考節點A、B、C的距離，f′(RSS)是f(RSS)的導函數，這樣對于不用的距離值都可以進行正確的修正。再根據三角加權質心計算定位節點的坐標，三個圓的交點坐標分為公式如下：

(9)

算法的實現步驟如下：

算法:自適應信號校正定位算法 Input:RSS1,RSS2,RSS3數組;l1,l2,l3三個AP的坐標 Output:(X,Y)定位節點的坐標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);//計算三個圓形的公共面積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));//根據公式(9)

4 實驗過程及結果

4.1 實驗環境的搭建

實驗的物理環境是我們平時用來學習的實驗室，長度為10m，寬度為8m。把3個TP-LINK的單天線的路由器作為802.11n信號接入點部署到實驗室，整個實驗環境如圖2和圖3所示，圖2為較復雜的實驗環境，圖3為一般實驗環境。

圖2 較復雜的實驗環境甲平面效果圖

圖3 一般實驗環境乙平面效果圖

4.2 信號衰減模型的模擬

無線信號的衰減模型其實就是距離與信號強度值的一個映射關系，這個映射關系即式(7)，其中含有兩個參數。我們在不同距離測量信號強度值，通過機器學習的方法監督學習這兩個參數。

4.3 距離評估的誤差分析

無線信號在向外輻射過程中，隨著距離增大，能量衰減加快。前面我們已經模擬出了無線信號的衰減模型，采集的信號強度值通過信號的衰減模型計算出評估距離，從而可以得到評估距離和真實距離的誤差。經過反復和大量的實驗，結果如圖4所示。

圖4 真實距離與估算距離之間的誤差圖

4.4 實驗過程

整個實驗過程包括準備階段和定位階段(圖5)。

圖5 整個定位過程的流程圖

4.4.1 準備階段

Step1：采集數據。將移動節點依次置于預先部署好的位置已知的參考點，采集路由節點的RSS信息及其距離信息，得到訓練樣本數據集。

Step2：數據過濾。由于室內環境較為復雜，再加上信號擁塞等因素的影響，智能手機接收的RSS信息復雜多變，原始數據含有較高的噪音。在數據過濾階段，采用均值進行過濾，以提高訓練樣本的質量。

Step3：通過最小二乘法對樣本數據模擬無線信號衰減模型，利用最小二乘法模擬過濾后的樣本數據集，可得到式(6)中的A和n兩個參數。

4.4.2 定位階段

Step1：采集RSS數據。Linux一句命令就可以掃描所有的AP并獲取AP信息，Android系統內核基于Linux，在安卓手機上部署相關應用即可采集RSS信息。

Step2：RSS預處理。由于RSS信息易受干擾，復雜多變，手機獲取RSS具有緩存機制，剛開始采集的RSS都是上一次時刻采集的RSS信息。故先刪除所采集的RSS信息的前小部分，然后再進行均值過濾以提高RSS信息質量。

Step3：距離變量循環更新。由于信號受障礙物的遮蔽效應，定位節點與參考節點的真實距離越大則估計距離的誤差越大。故采用循環更新方法對距離變量進行修正。

Step4：定位坐標。對距離變量進行修正之后再進行三角加權質心定位，利用式(9)進行坐標計算，得到實驗結果。

4.4.3 實驗結果分析

實驗結果如圖6所示，在實驗環境甲下，經過計算得到質心算法的平均誤差為2.59m，加權質心算法的平均誤差為2.45m，自適應信號修正算法的平均誤差為1.57m。從圖7中也驗證了本文所改進算法對定位精度的明顯提高。

圖6 實驗環境甲定位誤差圖

圖7 實驗環境乙定位誤差圖

圖6中自適應修正算法的誤差在質心算法和加權質心算法的下方，從而驗證了本文所改進算法對定位精度的明顯提高。在實驗環境乙下，質心算法的平均誤差為2.608m，加權質心算法的平均誤差為2.272m，自適應信號修正算法的平均誤差為1.552m。從圖2和圖3中可以看出實驗環境乙比實驗環境甲要空曠一些，故實驗環境乙的定位誤差相對較高。

5 結語

基于RSSI測距的三角形加權質心算法在實際定位應用中有較大的誤差，這種誤差完全是由環境因素使RSSI測距不準確導致的。本文在三角加權質心算法的基礎上，根據RSSI的衰減模型為測試距離提供修正因子以保證定位精度，提出了自適應信號校正定位算法。根據實驗結果對比可知，在相同條件下，自適應信號校正定位算法的實驗效果明顯優于三角形加權質心算法，定位精度可提高35.9%。在不同環境中，復雜環境比一般環境定位精度要低很多。

[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]王沁,何杰,張前雄,等.測距誤差分級的室內 TOA 定位算法[J].儀器儀表學報,2011(12):2851-2856.

[4]張毅,汪紀鋒,李柱.移動通信信號到達時間差定位的估計[J].系統工程與電子技術,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]王梓有,周憲英.無線傳感器網絡基于信號到達角度的節點定位算法研究[J].艦船電子工程,2012(7):40-42.

[8]王振朝,張琦,張峰.基于 RSSI 測距的改進加權質心定位算法[J].電測與儀表,2014(21):63-66.

[9]張蒼松,郭軍,崔嬌,等.基于 RSSI 的室內定位算法優化技術[J].Computer Engineering and Applications,2015(3): 235-238.

[10]陳順明,李平.基于 RSSI 權值的環境適應型室內定位算法研究[J].Computer Engineering and Applications,2015(22): 99-103.

[11]吳彥鴻,王聰,徐燦.無線通信系統中電波傳播路徑損耗模型研究[J].國外電子測量技術,2009(8):35-37.

[12]陳維克,李文峰,首珩,等.基于RSSI的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報,2006(12):2695-2700.

[13]陳祠,牟楠,張晨,等.基于主成分分析的室內指紋定位模型[J].軟件學報,2013(1):98-107.

[14]蔡文學,邱珠成,黃曉宇,等.基于 WiFi 指紋的室內軌跡定位模型[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

安徽高校自然科學研究重大項目“雙環網絡并行路由策略的研究”(KJ2015ZD39)。

陳業斌(1971- )，男，教授，碩士生導師，從事計算機網絡及數據庫研究。

王仁偉(1991- )，男，碩士研究生，從事無線傳感器網絡及稀疏編碼等研究。

TN911

A

2095-7602(2017)02-0010-07