一種自適應智能三邊定位算法的設計與實現*

藍威濤,張衛強,羅健宇

(寧波大學信息科學與工程學院,浙江 寧波 315211)

?

一種自適應智能三邊定位算法的設計與實現*

藍威濤,張衛強*,羅健宇

(寧波大學信息科學與工程學院,浙江 寧波 315211)

為了有效抑制室內復雜環境對無線傳感器網絡節點定位精度的影響,以及降低室內定位系統對環境的依賴性,提出了一種自適應智能三邊定位算法。該算法通過測量移動節點與各信標節點的距離值的波動情況,生成相應的自適應因子。該變化因子控制三邊定位算法中距離半徑的微調量,使3個定位圓的重疊部分的面積小于一定的數量級,然后在重疊區域中作最大內接圓,將圓心作為移動節點的位置。仿真結果表明該算法比加權三邊定位算法具有更高的定位精度,魯棒性好,能適應不同規模和類型的定位系統。

無線傳感器網絡;三邊定位算法;自適應因子;最大內接圓

近年來,基于位置服務的應用在物聯網、救援、監控、倉管等領域得到了快速的發展,人們對室內定位與導航的需求日益增大[1]。隨著無線傳感器網絡WSN(Wireless Sensor Network)技術的不斷發展,室內定位的方法也變得也來越多,系統的精度、識別范圍、魯棒性等均有提升[2]。

現有的室內定位技術可以分為兩大類:基于測距的定位技術和非測距的定位技術。基于測距的定位系統對硬件設施要求較高,主要有基于信號到達時間TOA(Time of Arrival)定位、基于信號到達時間差TDOA(Time Difference of Arrival)定位、三角測量AOA(Angle of Arrival)定位、基于接收信號強度RSSI(Received Signal Strength Indication)定位、TDOA/AOA混合定位技術等[3-5]。基于非測距的定位系統成本、功耗、精度均較低,它們是利用網絡的節點間跳數、識別區域、連通性等信息實現目標節點的定位[6]。主要算法有質心定位算法、DV-HOP(Distance Vector-Hop)定位算法、近似三角形內點測試APIT(Approximate Point-In-Triangulation Text)定位算法、凸規劃定位算法等[7-8]。

為了提高定位算法的精度,本文改進了加權三邊定位算法,同時也借鑒了改進的凸規劃定位算法思想[9],提出一種自適應智能三邊定位算法。該算法先通過測量數據的穩定性,生成自適應因子,縮小定位區域的范圍,再引入最大內接圓算法,能有效降低目標節點的定位誤差。

1 三邊定位算法

本章將介紹傳統三邊定位算法的基本思想、定位原理以及存在的不足之處。

1.1 算法基本思想

三邊定位算法的基本思想是:在同一水平面中,將信標節點均勻分布在待定位的區域內,其數量依據待定位區域的大小以及節點通信范圍而定,一般不小于3個且安裝位置不能共線。移動節點通常帶有信號的發射器與接收器,發射出的調制信號到達信標節點之后,信標節點通過反向散射回一個包含自身信息的信號。移動節點的接收器接收到該信號后解調判斷該信號來自哪個信標節點,并通過測量TOA或相位差PDOA(Phase Difference of Arrival)[10]計算與信標節點間的距離。

1.2 算法定位原理

三邊算法的定位原理是[11]:依次測出移動節點與3個不共線的信標節點之間的距離,分別以這3個信標節點的位置為圓心,相應的距離為半徑作3個圓,如圖1所示。如果測距無誤差,則這3個圓相交于一點,即移動節點的位置坐標。

圖1 三邊定位法示意圖

假設信標節點APi(i=1,2,3)與移動節點的距離分別為di(i=1,2,3),設移動節點的位置坐標為(x,y),信標節點APi的坐標為(xi,yi),根據幾何原理可得如下關系式:

(1)

(2)

1.3 算法的不足之處

由于移動節點與信標節點之間的測距會存在誤差,所作的3個圓并不能交于一點,如圖2所示,黑色實心五角星為移動節點實際位置,由于干擾的不確定性,可能使測距遠大于實際距離或遠小于實際距離。一般的加權三邊定位算法針對圖2(a)的情況,需求出圖中陰影部分的區域交點。首先通過測量計算AP1與AP2兩圓的交點,接著計算由上一步得到的兩個點與第3個圓圓心之間的距離,然后刪除距離大的點,保留距離小的點;用同樣的方法計算出其余兩組組合圓的點,一共能得到3個交點的坐標(xi,yi)(i=1,2,3),最后通過RSSI值或角度權重函數分配權值,以x=a1x1+a2x2+a3x3,y=a1y1+a2y2+a3y3作為移動節點的測算位置坐標[12],其中a1+a2+a3=1。針對圖2(b)的情況,一般加權三邊定位算法不能估算出移動節點的位置[13]。

圖2 有誤差存在時的三邊定位示意圖

文獻[14]的算法思想是通過結合移動節點接收到各信標節點RSSI值之間的比較,進一步縮小圖2(a)的陰影部分面積,以達到提高精度的目的。但該算法主要是針對非測距定位,并且不能解決圖2(b)的情況。

2 自適應智能三邊定位算法

2.1 信標節點的選擇策略

假設待定位區域有n個信標節點,移動節點與信標節點之間最大的通信范圍是lmax。

①當前移動節點與每個信標節點之間都進行k次測量,將數據存放在n×k維的矩陣M中。

②檢查矩陣M中每一行是否有數據大于lmax,如果有則將該行剔除,否則保留。

③在剩余的行列中,求出每一行的方差,然后只留下方差最小的3行數列。此時矩陣M變為矩陣M′是3×k維,以這3行數列對應的信標節點作為最終選定的有效信標節點。

信標節點的選擇策略主要是從若干個信標節點中,選取測量數值波動小的,測量值又沒有超出測量范圍的信標節點。考慮到方差的計算較為復雜,可以以矩陣M中每一行數據中的最大數與最小數之差來替代方差,簡化算法。

2.2 測量距離的處理

信標節點選定以后,假設在實驗中目標節點與各個信標節點進行了5次測距,目標節點對應每個信標節點都有5個測量距離ri(i=1,2,…,5),如圖3(a)所示。假設r1

圖3 距離處理過程

圖5 定位算法的迭代過程

處理測量后的數據,主要是為了降低由環境因素引起的測量誤差,使數據的可靠性更高,能得到更好的定位精度[15]。

2.3 自適應智能三邊算法的實現步驟

經過上述幾個步驟后,得到3個信標節點APi(i=1,2,3)與移動節點之間的距離rai(i=1,2,3),且APi的坐標(xi,yi)已知。

②判斷兩圓位置關系:如果(ra1+ra2)≥d12,說明圓AP1與圓AP2相交或相切;如果(ra1+ra2)

圖4 圓的位置關系

③判斷三圓無有重疊部分:若由上一步得出有任意兩圓相離或相切,則三圓無重疊部分;若由上一步得出有任意兩圓相交,則求出交點坐標,并保留與第3個圓的圓心距離較近的交點,計算此交點與該圓心的距離。如果該距離比第3個圓的半徑小,說明三圓有重疊部分,否則無重疊部分。

④設置自適應因子:先通過式(3),求出3×5維矩陣M′中每一行數據的樣本標準差。

(3)

綜合考慮實驗定位區域面積,定位計算的時間,設置自適應因子β(Si)的公式如下:

(4)

⑥自適應智能三邊算法的迭代過程:

各信標節點APi的位置坐標(xi,yi)不變,通過改變rai,使三圓的重疊區域面積發生變化。如圖5所示,假設β(S1)=5,β(S2)=15,β(S3)=30。

距離半徑變化公式如下:

rai(n)=rai(n-1)+(-1)P(1/2)qβ(Si)

(5)

式中:rai(n)表示本次迭代過程中信標節點APi的半徑;rai(n-1)表示上一次迭代過程中信標節點APi的半徑;初始時刻rai(0)=rai;當三圓無重疊區域時,p=2,否則p=1;q的初始值為0,如果p連續變化兩次且迭代未終止時,q=p的變化次數;迭代終止的條件是3個圓有重疊部分且3個交點兩兩之間的距離小于10.0 cm,或者迭代次數超過100次時終止迭代。距離半徑每變化一次,需求取交點坐標一次,保留與各個圓心距離較近的3個交點。

2.4 求最大內接圓的圓心

設上一步得到的3個交點為K1、K2、K3,任意兩個交點可以確定一段圓弧,設K1K2圓弧段的中點為K12,同理可得K13、K23。連接各點可以得到一個多邊形,如圖6所示,取3個交點K1、K2、K3所組成的三角形的質心為初始圓的圓心O0(x0,y0),求出該圓心到多邊形各邊的最短距離和相應垂足點的位置。各垂足點必須在多邊形上,不能是各邊的延長線上[16]。

圖6 最大內接圓圓心定位示意圖

①從中選取到初始圓心距離最短的垂足點A(xa,ya)和次短的垂足點B(xb,yb),對應的距離長度分別為da和db。現取一參考點C的坐標(xc,yc),如果O0與A、B兩點共線,則使(xc,yc)=(xa,ya),即參考點取A的位置,若不共線,則使

(6)

參考點C(xc,yc)由式(7)計算:

(7)

②連接C和O0,在其延長線上取新的圓心O1(x1,y2),可由式(8)計算:

(8)

式中:δ為校正因子,初始值定位0.618。

④重復步驟①～步驟③,直至校正因子δ減小到0.000 1,則近似可得最大內接圓的圓心,即定位坐標。

3 實驗結果與分析

本次試驗用到7個信標節點,設其最大通信半徑為lmax=L,與移動節點處于同一水平面上。實驗平臺:Windows 7+MATLAB 2012b,試驗場景:L×L的正方形區間,加入均值為0,標準差為0.1×L的高斯白噪聲模擬環境中的各種干擾因素。如圖7(a)、圖7(b)所示,在待定位區域中,正方形代表信標節點的實際位置,加號代表選定的80個待測目標節點的真實位置,星號代表目標節點的估算位置,加號與星號之間的連線表示定位誤差,從圖7可以看出,邊緣待測點的誤差普遍比非邊緣待測點的誤差大。

實驗中對每個待測點各計算10次,取其平均值作為最終的定位結果,然后采用歸一化定位誤差來評估算法的定位精度。

如圖7(c)所示,用擬合歸一化的誤差曲線來對比兩種算法的定位精度,橫坐標代表未知節點的序號,縱坐標代表相應序號的未知節點所對應的歸一化誤差大小,實驗結果驗證了本文算法的定位精度比一般加權三邊算法的定位精度高,誤差的波動范圍也較小。

從表1可以看出,在信標節點的通信半徑、數量、布置位置、環境干擾因素等相同的條件下,本文算法比一般加權三邊算法的平均歸一化定位誤差減小了約3.6%,最大歸一化定位誤差和最小歸一化定位誤差均有所減小。定位算法的時間復雜度主要取決于求解的方法、信標節點個數和迭代次數,在n個信標節點的定位問題中,加權三邊定位算法與本文算法的時間復雜度分別為O(n2)和O(n2+kn),兩者近似相等,其中k為迭代次數,在最壞的情況下,對每種算法分別進行100次的運算,然后求其運行時間的平均值。如表1所示,本文算法的求解時間增加了約0.009 s,在一般的應用場合下,該增量完全可以忽略不計,因此該算法滿足實際的定位要求。

圖7 實驗結果

定位算法最大歸一化誤差最小歸一化誤差平均歸一化誤差平均求解時間/s加權三邊定位算法22.18%0.81%7.73%0.021自適應智能三圓算法13.19%0.58%4.11%0.030

4 結束語

本文提出的自適應智能三邊定位算法是一種普適的三邊室內定位算法,能根據測量數據的波動性,自動地選取合適的變化因子,以及在后續的定位求解過程中,可以智能地微調距離半徑,使定位算法的收斂速度加快,并降低無解的可能性。該算法在計算量略有增加的基礎上有效抑制了由測量值的隨機波動性造成的定位誤差,增強了室內定位系統的魯棒性。此外,在信標節點分布不均勻且數量較少的情況下,該算法都有較好的定位精度,不但對測距的定位系統有實用價值,對非測距的定位系統也有一定的參考意義。

[1] 李守林. 基于物聯網驅動的物流園區信息化研究[D]. 北京:北京交通大學,2016.

[2] 鄧中亮,余彥培,徐連明,等. 室內外無線定位與導航[M]. 北京:北京郵電大學出版社,2013:13-25.

[3] 郄劍文,賈方秀,李興隆,等. 基于組合測距的無線傳感器網絡自定位算法[J]. 傳感技術學報,2016,29(5):744-749.

[4] 閆雷兵,陸音,張業榮. 基于改進最小二乘算法的TDOA/AOA定位方法[J]. 電波科學學報,2016,31(2):394-400.

[5] 何偉俊,周非. 基于粒子濾波的TOA/TDOA融合算法研究[J]. 傳感技術學報,2010,23(3):404-407.

[6] Mahmoud A,Noureldin A,Hassanein H S. Distributed Vehicle Selection for Non-Range Based Cooperative Positioning in Urban Environments[C]//IEEE International Conference on Communications. IEEE,2016:1-6.

[7] 吳凡,彭力,董國勇. WSN中基于中位線分割的APIT定位算法[J]. 小型微型計算機系統,2015,36(7):1583-1586.

[8] 蔣銳,楊震. 基于質心迭代估計的無線傳感器網絡節點定位算法[J]. 物理學報,2016,65(3):9-17.

[9] 任克強,莊放望. 移動錨節點凸規劃定位算法研究及改進[J]. 傳感技術學報,2014,27(10):1406-1411.

[10] Scherhaufl M,Pichler M,Stelzer A. Robust Localization of Passive UHF RFID Tag Arrays Based on Phase-Difference-of-Arrival Evaluation[C]//IEEE Topical Conference on Wireless Sensors and Sensor Networks. 2015:47-49.

[11] Caffery J J. A New Approach to the Geometry of TOA Location[C]//IEEE Vehicular Technology Conference. 2000,4:1943-1949.

[12] 熊志廣,石為人,許磊,等. 基于加權處理的三邊測量定位算法[J]. 計算機工程與應用,2010,46(22):99-102.

[13] Anagnostopoulos C,Hadjiefthymiades S,Kolomvatsos K. Accurate,dynamic,and distributed localization of phenomena for mobile sensor networks[J]. Acm Transactions on Sensor Networks,2016,12(2):9.

[14] 馬駿,王敬東,溫家旺,等. RSSI與凸規劃相結合的無線傳感器網絡定位算法[J]. 指揮控制與仿真,2013,35(4):56-61.

[15] Marc A K J,Kazunori O. LRD:A Distributed and Accurate Localization Technique for Wireless Sensors Networks[C]//TENCON 2010-2010 IEEE Region 10 Conference. 2010:234-239.

[16] 向滿天,羅嗣力,戴美思. 無線傳感器網絡中一種改進的凸規劃定位算法[J]. 傳感技術學報,2014,27(8):1138-1142.

藍威濤(1992-),男,畬族,浙江衢州人,寧波大學信息科學與工程學院集成電路工程專業研究生,研究方向為室內定位系統以及嵌入式系統設計與應用,1569127971@qq.com;

張衛強(1963-),男,漢族,浙江寧波人,寧波大學信息科學與工程學院副教授,碩士生導師,研究方向為電路與系統以及嵌入式系統設計與應用,zhangweiqiang@nbu.edu.cn;

羅健宇(1992-),男,漢族,河南商丘人,寧波大學信息科學與工程學院集成電路工程專業研究生,研究方向為嵌入式系統設計與應用,1210660412@qq.com。

Design and Implementation of Adaptive Intelligent Trilateral Localization Algorithm*

LAN Weitao,ZHANG Weiqiang*,LUO Jianyu,

(Faculty of Electrical Engineering and Computer Science,Ningbo University,Ningbo Zhejiang 315211,China)

In order to effectively restrain the influence of indoor complex environment on the wireless sensor network nodes localization accuracy,and reduce the dependence of the indoor positioning system on the environment,a new adaptive intelligent trilateral localization algorithm is proposed. By measuring the fluctuation of the distance between the mobile node and the beacon nodes,the algorithm generates the corresponding adaptive factor. The variation factor controls the fine tuning of the distance radius in the trilateral localization algorithm,which makes the area of the overlapping part of the three positioning circles smaller than a certain precision. Then the maximum inscribed circle in the overlap region is plotted,and regards the center of the circle as the location of the mobile node. The simulation results show that the proposed algorithm has higher localization accuracy and better robustness than the weighted trilateral localization algorithm,and can adapt to different sizes and types of localization systems.

wireless sensor network;trilateral localization algorithm;adaptive factor;maximum inscribed circle

項目來源:電動車移動定位系統開發項目(81140156)

2016-12-13 修改日期:2017-02-19

TP301.6

A

1004-1699(2017)07-1089-06

C:6150P;7230

10.3969/j.issn.1004-1699.2017.07.020