藍(lán)威濤,張衛(wèi)強(qiáng),羅健宇

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

?

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

藍(lán)威濤,張衛(wèi)強(qiáng)*,羅健宇

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

為了有效抑制室內(nèi)復(fù)雜環(huán)境對(duì)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位精度的影響,以及降低室內(nèi)定位系統(tǒng)對(duì)環(huán)境的依賴性,提出了一種自適應(yīng)智能三邊定位算法。該算法通過測(cè)量移動(dòng)節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)的距離值的波動(dòng)情況,生成相應(yīng)的自適應(yīng)因子。該變化因子控制三邊定位算法中距離半徑的微調(diào)量,使3個(gè)定位圓的重疊部分的面積小于一定的數(shù)量級(jí),然后在重疊區(qū)域中作最大內(nèi)接圓,將圓心作為移動(dòng)節(jié)點(diǎn)的位置。仿真結(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ā)展,人們對(duì)室內(nèi)定位與導(dǎo)航的需求日益增大[1]。隨著無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)技術(shù)的不斷發(fā)展,室內(nèi)定位的方法也變得也來越多,系統(tǒng)的精度、識(shí)別范圍、魯棒性等均有提升[2]。

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

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

1 三邊定位算法

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

1.1 算法基本思想

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

1.2 算法定位原理

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

圖1 三邊定位法示意圖

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

(1)

(2)

1.3 算法的不足之處

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

圖2 有誤差存在時(shí)的三邊定位示意圖

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

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

2.1 信標(biāo)節(jié)點(diǎn)的選擇策略

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

①當(dāng)前移動(dòng)節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)之間都進(jìn)行k次測(cè)量,將數(shù)據(jù)存放在n×k維的矩陣M中。

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

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

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

2.2 測(cè)量距離的處理

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

圖3 距離處理過程

圖5 定位算法的迭代過程

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

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

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

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

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

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

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

(3)

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

(4)

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

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

距離半徑變化公式如下:

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

(5)

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

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

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

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

①從中選取到初始圓心距離最短的垂足點(diǎn)A(xa,ya)和次短的垂足點(diǎn)B(xb,yb),對(duì)應(yīng)的距離長度分別為da和db?，F(xiàn)取一參考點(diǎn)C的坐標(biāo)(xc,yc),如果O0與A、B兩點(diǎn)共線,則使(xc,yc)=(xa,ya),即參考點(diǎn)取A的位置,若不共線,則使

(6)

參考點(diǎn)C(xc,yc)由式(7)計(jì)算:

(7)

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

(8)

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

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

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

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

實(shí)驗(yàn)中對(duì)每個(gè)待測(cè)點(diǎn)各計(jì)算10次,取其平均值作為最終的定位結(jié)果,然后采用歸一化定位誤差來評(píng)估算法的定位精度。

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

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

圖7 實(shí)驗(yàn)結(jié)果

定位算法最大歸一化誤差最小歸一化誤差平均歸一化誤差平均求解時(shí)間/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ù)測(cè)量數(shù)據(jù)的波動(dòng)性,自動(dòng)地選取合適的變化因子,以及在后續(xù)的定位求解過程中,可以智能地微調(diào)距離半徑,使定位算法的收斂速度加快,并降低無解的可能性。該算法在計(jì)算量略有增加的基礎(chǔ)上有效抑制了由測(cè)量值的隨機(jī)波動(dòng)性造成的定位誤差,增強(qiáng)了室內(nèi)定位系統(tǒng)的魯棒性。此外,在信標(biāo)節(jié)點(diǎn)分布不均勻且數(shù)量較少的情況下,該算法都有較好的定位精度,不但對(duì)測(cè)距的定位系統(tǒng)有實(shí)用價(jià)值,對(duì)非測(cè)距的定位系統(tǒng)也有一定的參考意義。

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

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

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

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

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

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

[9] 任克強(qiáng),莊放望. 移動(dòng)錨節(jié)點(diǎn)凸規(guī)劃定位算法研究及改進(jìn)[J]. 傳感技術(shù)學(xué)報(bào),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)處理的三邊測(cè)量定位算法[J]. 計(jì)算機(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ò)中一種改進(jìn)的凸規(guī)劃定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(8):1138-1142.

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

張衛(wèi)強(qiáng)(1963-),男,漢族,浙江寧波人,寧波大學(xué)信息科學(xué)與工程學(xué)院副教授,碩士生導(dǎo)師,研究方向?yàn)殡娐放c系統(tǒng)以及嵌入式系統(tǒng)設(shè)計(jì)與應(yīng)用,zhangweiqiang@nbu.edu.cn;

羅健宇(1992-),男,漢族,河南商丘人,寧波大學(xué)信息科學(xué)與工程學(xué)院集成電路工程專業(yè)研究生,研究方向?yàn)榍度胧较到y(tǒng)設(shè)計(jì)與應(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

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