一種自適應(yīng)智能三邊定位算法的設(shè)計與實現(xiàn)*

藍威濤,張衛(wèi)強,羅健宇

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

?

一種自適應(yīng)智能三邊定位算法的設(shè)計與實現(xiàn)*

藍威濤,張衛(wèi)強*,羅健宇

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

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

無線傳感器網(wǎng)絡(luò);三邊定位算法;自適應(yīng)因子;最大內(nèi)接圓

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

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

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

1 三邊定位算法

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

1.1 算法基本思想

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

1.2 算法定位原理

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

圖1 三邊定位法示意圖

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

(1)

(2)

1.3 算法的不足之處

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

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

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

2 自適應(yīng)智能三邊定位算法

2.1 信標節(jié)點的選擇策略

假設(shè)待定位區(qū)域有n個信標節(jié)點,移動節(jié)點與信標節(jié)點之間最大的通信范圍是lmax。

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

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

③在剩余的行列中,求出每一行的方差,然后只留下方差最小的3行數(shù)列。此時矩陣M變?yōu)榫仃嘙′是3×k維,以這3行數(shù)列對應(yīng)的信標節(jié)點作為最終選定的有效信標節(jié)點。

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

2.2 測量距離的處理

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

圖3 距離處理過程

圖5 定位算法的迭代過程

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

2.3 自適應(yīng)智能三邊算法的實現(xiàn)步驟

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

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

圖4 圓的位置關(guān)系

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

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

(3)

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

(4)

⑥自適應(yīng)智能三邊算法的迭代過程:

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

距離半徑變化公式如下:

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

(5)

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

2.4 求最大內(nèi)接圓的圓心

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

圖6 最大內(nèi)接圓圓心定位示意圖

①從中選取到初始圓心距離最短的垂足點A(xa,ya)和次短的垂足點B(xb,yb),對應(yīng)的距離長度分別為da和db?，F(xiàn)取一參考點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。

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

3 實驗結(jié)果與分析

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

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

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

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

圖7 實驗結(jié)果

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

4 結(jié)束語

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

[1] 李守林. 基于物聯(lián)網(wǎng)驅(qū)動的物流園區(qū)信息化研究[D]. 北京:北京交通大學,2016.

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

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

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

[5] 何偉俊,周非. 基于粒子濾波的TOA/TDOA融合算法研究[J]. 傳感技術(shù)學報,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]. 小型微型計算機系統(tǒng),2015,36(7):1583-1586.

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

[9] 任克強,莊放望. 移動錨節(jié)點凸規(guī)劃定位算法研究及改進[J]. 傳感技術(shù)學報,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] 熊志廣,石為人,許磊,等. 基于加權(quán)處理的三邊測量定位算法[J]. 計算機工程與應(yīng)用,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與凸規(guī)劃相結(jié)合的無線傳感器網(wǎng)絡(luò)定位算法[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] 向滿天,羅嗣力,戴美思. 無線傳感器網(wǎng)絡(luò)中一種改進的凸規(guī)劃定位算法[J]. 傳感技術(shù)學報,2014,27(8):1138-1142.

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

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

羅健宇(1992-),男,漢族,河南商丘人,寧波大學信息科學與工程學院集成電路工程專業(yè)研究生,研究方向為嵌入式系統(tǒng)設(shè)計與應(yīng)用,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

項目來源:電動車移動定位系統(tǒng)開發(fā)項目(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