嚴(yán)長(zhǎng)虹,金 琳

(1.鹽城工學(xué)院信息學(xué)院,江蘇 鹽城 22400;2.鹽城工學(xué)院經(jīng)濟(jì)與管理學(xué)院,江蘇 鹽城 22400)

?

時(shí)間偏移下的多源目標(biāo)精確定位方法

嚴(yán)長(zhǎng)虹1*,金 琳2

(1.鹽城工學(xué)院信息學(xué)院,江蘇 鹽城 22400;2.鹽城工學(xué)院經(jīng)濟(jì)與管理學(xué)院,江蘇 鹽城 22400)

采用到達(dá)時(shí)間(TOA)測(cè)距實(shí)現(xiàn)源目標(biāo)定位的方法比較簡(jiǎn)單,因此在無線傳感器網(wǎng)絡(luò)定位領(lǐng)域得到了廣泛的應(yīng)用。將TOA定位模型轉(zhuǎn)化為線性優(yōu)化問題,提出了一種存在時(shí)間偏移下的多源目標(biāo)精確定位方法。該方法將定位計(jì)算過程分成兩步,包括多源目標(biāo)位置初始值估計(jì)和優(yōu)化計(jì)算過程。兩步計(jì)算方法將定位結(jié)果用代數(shù)解表示,避免了數(shù)值計(jì)算過程中的局部最優(yōu)問題。仿真分析了時(shí)間偏移量及噪聲大小對(duì)定位誤差的影響。結(jié)果表明即使存在較大的時(shí)間偏移量,優(yōu)化計(jì)算后的定位誤差也能非常接近于克拉美羅(CRLB)下界值。

無線傳感器網(wǎng)絡(luò);定位;到達(dá)時(shí)間(TOA);多源目標(biāo)

節(jié)點(diǎn)位置坐標(biāo)的自主估計(jì)是無線傳感器網(wǎng)絡(luò)中的重要內(nèi)容[1-2],為了滿足部署大量無線傳感器節(jié)點(diǎn)的廉價(jià)要求,定位的硬件成本必須較低,因此傳統(tǒng)的GPS定位方法對(duì)無線傳感器網(wǎng)絡(luò)來說是不適合的。GPS定位方法的局限性激發(fā)了一種新的傳感器網(wǎng)絡(luò)定位方法,即利用已知位置的信標(biāo)節(jié)點(diǎn)去推算其余未知源目標(biāo)節(jié)點(diǎn)的位置坐標(biāo)。在這種定位方式下,定位過程可劃分為兩步:借助于一定的方法測(cè)量或估計(jì)節(jié)點(diǎn)間的距離或方向角信息;以節(jié)點(diǎn)間的這些信息通過定位算法求出源節(jié)點(diǎn)坐標(biāo)。因此,定位精度不但取決于測(cè)量技術(shù)的精度,而且也決定于所采用的定位算法。

國內(nèi)外已經(jīng)開展了很多無線傳感器網(wǎng)絡(luò)定位方法的研究,這些定位方法大多數(shù)在定位成本和定位精度間進(jìn)行權(quán)衡選擇[3]。通常測(cè)距誤差越小,定位算法獲得的定位精度越高,當(dāng)然對(duì)測(cè)距方法的要求也就越高。根據(jù)定位過程中是否需要直接測(cè)量節(jié)點(diǎn)間距離,可以把定位算法分為:基于非測(cè)距和測(cè)距的定位算法。非測(cè)距定位算法無需測(cè)量節(jié)點(diǎn)的絕對(duì)距離或方位,而是利用節(jié)點(diǎn)間的鏈路關(guān)系估計(jì)距離并計(jì)算節(jié)點(diǎn)位置,定位成本較低,但定位誤差相對(duì)較大[4]。為獲取較高的定位精度,一般采用測(cè)距定位算法。測(cè)距定位算法需要直接測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方向角,并利用節(jié)點(diǎn)間的實(shí)際距離來計(jì)算未知節(jié)點(diǎn)的位置,該方法需要測(cè)量節(jié)點(diǎn)間間距,常用的測(cè)量有接收信號(hào)強(qiáng)度指示(RSSI)[5-6],到達(dá)時(shí)間(TOA)[7],到達(dá)時(shí)間差(TDOA)[8]和聲音能量強(qiáng)度[9]等方法。

在已知信號(hào)傳播速度的前提下,TOA方法根據(jù)信號(hào)在兩個(gè)目標(biāo)之間的傳播時(shí)間來估計(jì)發(fā)送者和接收者之間的距離,相比較而言,其實(shí)現(xiàn)原理簡(jiǎn)單,因此已有大量的文獻(xiàn)介紹使用該方法實(shí)現(xiàn)目標(biāo)定位[10-14]。Chan等[10]提出了基于一種TOA測(cè)距方法下的最優(yōu)線性無偏估計(jì)方法,但該方法沒有考慮節(jié)點(diǎn)間到達(dá)時(shí)間偏差。文獻(xiàn)[11]以目標(biāo)間的發(fā)射與反射TOA測(cè)距模型,提出了一種精確的被動(dòng)目標(biāo)位置線性估計(jì)方法,但該方法并未考慮節(jié)點(diǎn)間的時(shí)間偏移量。為此Wang等[12]對(duì)存在時(shí)間偏移量下的被動(dòng)目標(biāo)位置估計(jì)進(jìn)行了改進(jìn),并提出了定位計(jì)算方法。也有學(xué)者將定位優(yōu)化模型轉(zhuǎn)化為凸優(yōu)化問題,如文獻(xiàn)[13]提出源節(jié)點(diǎn)信號(hào)發(fā)射時(shí)間未知下的半正定規(guī)劃(SDP)放松定位算法,但該文獻(xiàn)并未考慮多源定位問題。為此文獻(xiàn)[14]介紹采用SDP放松方法將上述TOA定位模型擴(kuò)展到多源目標(biāo)定位。SDP定位方法的不依賴于初始解,但計(jì)算復(fù)雜度較高。

根據(jù)節(jié)點(diǎn)間的TOA往返時(shí)間測(cè)距模型并考慮節(jié)點(diǎn)間存在傳送時(shí)間偏移量,本文將多源目標(biāo)定位問題轉(zhuǎn)化為線性估計(jì)模型,以兩步線性計(jì)算方法精確確定源目標(biāo)位置坐標(biāo),提出了存在時(shí)間偏移量下的多源目標(biāo)精確定位計(jì)算方法。本文第1部分首先介紹了多源TOA定位問題描述;第2部分推導(dǎo)了該定位模型下的CRLB下界值;第3部分詳細(xì)介紹了所設(shè)計(jì)的定位計(jì)算方法,包括目標(biāo)位置初始值估計(jì)及優(yōu)化計(jì)算過程;第4部分為仿真與分析;最后部分為結(jié)論。

1 問題描述

考慮在二維平面上分布著M+N個(gè)節(jié)點(diǎn),其中包括N個(gè)未知位置坐標(biāo)的源節(jié)點(diǎn)(源節(jié)點(diǎn)的坐標(biāo)值假設(shè)為xi=[xiyi]T,i=1,2,…,N)以及M個(gè)已知位置坐標(biāo)的信標(biāo)節(jié)點(diǎn)(其坐標(biāo)值為xj=[xjyj]T,j=N+1,N+2,…,N+M,信標(biāo)節(jié)點(diǎn)位置坐標(biāo)可以預(yù)先部署GPS或依靠人力測(cè)量方式獲取)。信標(biāo)節(jié)點(diǎn)j發(fā)送給源節(jié)點(diǎn)i信號(hào),源節(jié)點(diǎn)i接收到該信號(hào)后立刻又轉(zhuǎn)發(fā)回信標(biāo)節(jié)點(diǎn)j,將節(jié)點(diǎn)間的信號(hào)往返時(shí)間記為ti,j,因此有

(1)

(2)

顯然對(duì)式(2)所描述的優(yōu)化問題可采用數(shù)值方法計(jì)算。然而當(dāng)采用數(shù)值計(jì)算方法時(shí),計(jì)算結(jié)果依賴于初始值,若初始值選擇不合適,可能會(huì)使結(jié)果陷入局部最優(yōu),導(dǎo)致計(jì)算結(jié)果錯(cuò)誤。

為此本文提出一種存在時(shí)間偏移下的多源目標(biāo)位置線性估計(jì)方法。該方法采用兩步線性估計(jì)方法實(shí)現(xiàn),將定位結(jié)果采用代數(shù)解表示,避免了數(shù)值計(jì)算方法下選擇初始解的問題。首先將非線性優(yōu)化定位模型轉(zhuǎn)化為線性估計(jì)問題,初步估計(jì)多源目標(biāo)節(jié)點(diǎn)位置坐標(biāo)。然后對(duì)初步估計(jì)的源目標(biāo)位置進(jìn)行再次優(yōu)化求精計(jì)算,從而得到目標(biāo)位置的精確解。

2 克拉美羅下界值

(3)

式(3)中,

(4)

將式(4)代入式(3)并求微分,因此有F∈R(2N+M)×(2N+M),并且矩陣F的元素值為

(5)

式(5)中,j∈Ai表示了源節(jié)點(diǎn)i與信標(biāo)節(jié)點(diǎn)j間可測(cè)距。向量θ的CRLB下界為F逆矩陣的對(duì)角元素,可以表示為

(6)

(7)

3 多源目標(biāo)定位

式(2)所描述的TOA測(cè)距模型中包含未知參數(shù)τj,故難以實(shí)現(xiàn)對(duì)單源節(jié)點(diǎn)目標(biāo)位置的確定,本節(jié)設(shè)計(jì)了多源目標(biāo)的兩步線性估計(jì)方法,以精確定位目標(biāo)節(jié)點(diǎn)位置坐標(biāo)。

3.1 多源目標(biāo)位置初始值估計(jì)

將式(1)重新表示為

2‖xi-xj‖=c(ti,j-τj-ni,j)

(8)

式(8)中,i=1,2,…,N,j=N+1,N+2,…,N+M且j∈Ai。對(duì)式(8)左右兩邊平方,忽略高階項(xiàng),式(8)再表示為

(9)

由于τj?tij,將式(9)再次表示為

(10)

Aη=b+α

(11)

式(11)中,α為噪聲部分,矩陣A的行向量值為:

當(dāng)所有源節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間共存在L次TOA測(cè)距時(shí),A∈RL×(3N+M),b∈RL×1,α∈RL×1。

根據(jù)線性最小二乘平方原理,未知參數(shù)η的無偏估計(jì)值為

(12)

式(12)中維度為L(zhǎng)×L的矩陣Σα=E(αTα),其值大小為

(13)

式(13)中,Σα的計(jì)算取決于參數(shù)值τj?？深A(yù)先設(shè)置Σα為單位矩陣,近似地求解時(shí)間偏移值τj,j=N+1,N+2,…,N+M,然后以該近似值計(jì)算Σα,再以式(12)重新精確計(jì)算參數(shù)η。

3.2 目標(biāo)位置優(yōu)化計(jì)算

(14)

Δτ=[ΔτN+1ΔτN+2…ΔτN+M]T,可將式(14)寫成如下矩陣形式

CΔθ=d+α

(15)

(16)

式(16)中維度為L(zhǎng)×L的矩陣Σα=E(αTα),其值計(jì)算同式(13)。同樣根據(jù)參數(shù)Δθ的定義,從參數(shù)Δθ抽取出Δxi即為優(yōu)化增量部分。因此最終的源節(jié)點(diǎn)目標(biāo)位置可以表示為

(17)

式(17)中,i=1,2,…,N。

將參數(shù)Δθ的方差表示為ΣΔθ,由式(16)可以推導(dǎo)出ΣΔθ有以下關(guān)系式

(18)

3.3 算法的計(jì)算復(fù)雜度分析

O[2L2(3N+M)+L(3N+M)2+(3N+M)3]≤

O[(3N+M)(2M2N2+3MN2+M2N+(3N+M)2]≈

O(6M2N3+2M3N2)

(19)

O[2L2(2N+M)+L(2N+M)2+(2N+M)3]≤

O[(2N+M)(2M2N2+2MN2+M2N+(2N+M)2]≈

O(4M2N3+2M3N2)

(20)

4 仿真分析

針對(duì)上述所設(shè)計(jì)的兩步線性估計(jì)方法,采用MATLAB軟件進(jìn)行了仿真與分析。在100m×100m的二維平面上,分別設(shè)置5個(gè)信標(biāo)節(jié)點(diǎn)(M=5)在(25,25),(25,50),(50,50),(75,25),(75,75)坐標(biāo)點(diǎn)。同時(shí)隨機(jī)生成了10個(gè)源節(jié)點(diǎn)(N=10),當(dāng)源節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間距離小于60m時(shí),認(rèn)為可實(shí)現(xiàn)TOA測(cè)距,源節(jié)點(diǎn)位置坐標(biāo)及節(jié)點(diǎn)間測(cè)距情況如圖1所示。為評(píng)價(jià)所設(shè)計(jì)算法的定位性能,源節(jié)點(diǎn)的定位精度采用均方誤差(MSE)判斷。假設(shè)目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)間的測(cè)距噪聲都服從均值為0,方差為δ2的高斯分布,首先仿真測(cè)試了不同源節(jié)點(diǎn)ID上的定位誤差結(jié)果。

圖1 節(jié)點(diǎn)地理位置分布

4.1 不同源節(jié)點(diǎn)ID的定位誤差比較

設(shè)置所有源節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的測(cè)距噪聲為δ2=12,所有信標(biāo)節(jié)點(diǎn)上的時(shí)間偏移量τj=τ=20 ns,j=N+1,N+2,…,N+M。對(duì)算法下的MSE定位誤差仿真運(yùn)行5 000次,采用5 000次運(yùn)行結(jié)果的平均值分析其定位誤差,圖2繪出了不同源節(jié)點(diǎn)上的定位誤差比較結(jié)果。由該圖可見,經(jīng)過優(yōu)化計(jì)算后,所有源節(jié)點(diǎn)上的定位結(jié)果較初始估計(jì)值有極大的改善,已基本與CRLB下界值一致。由于所采用的信標(biāo)節(jié)點(diǎn)位置分布不同,經(jīng)過優(yōu)化計(jì)算后各源節(jié)點(diǎn)上的定位誤差有所不同,如源節(jié)點(diǎn)ID為5的對(duì)數(shù)MSE值,即10log(MSE)為-11.7 dB,而源節(jié)點(diǎn)ID為8的對(duì)數(shù)MSE值為-15.4 dB。

圖2 不同源節(jié)點(diǎn)ID的定位誤差比較

圖3 源節(jié)點(diǎn)ID為8時(shí)噪聲對(duì)定位誤差的影響

4.2 噪聲對(duì)定位誤差的影響

調(diào)整噪聲δ2從0.52到52之間變化,即10log(δ2)從-6.0dB到14.0dB之間變化,時(shí)間偏移量τ=20ns,圖3(a)繪出了源節(jié)點(diǎn)ID為8時(shí)定位誤差與噪聲之間的變化關(guān)系。該圖反映的結(jié)果同圖2結(jié)果一致,經(jīng)過優(yōu)化計(jì)算后的源節(jié)點(diǎn)定位結(jié)果較初始估計(jì)值有極大的改善,非常接近CRLB下界值。同時(shí)也可以看出對(duì)數(shù)MSE值與噪聲10log(δ2)之間有近似的線性關(guān)系,隨著噪聲的增加而增大。當(dāng)噪聲10log(δl2)為-6.0dB時(shí),優(yōu)化計(jì)算后的對(duì)數(shù)MSE值為-21.3dB;而當(dāng)噪聲10log(δ2)為14.0dB時(shí),優(yōu)化計(jì)算后的對(duì)數(shù)MSE值增加到了-1.2dB。

設(shè)定δ2為12,時(shí)間偏移量τ=20ns,圖3(b)繪出了5 000次隨機(jī)測(cè)試下、源節(jié)點(diǎn)ID為8的定位誤差的累積分布函數(shù)曲線(CDF)。初始估計(jì)值下僅有15%左右的定位誤差小于CRLB,而經(jīng)過優(yōu)化計(jì)算后,有65%左右的定位誤差小于CRLB下界值,說明經(jīng)過優(yōu)化計(jì)算后,定位誤差大大減少了。

4.3 時(shí)間偏移量對(duì)定位誤差的影響

目標(biāo)位置初始值估計(jì)時(shí),方程對(duì)時(shí)間偏移量進(jìn)行了近似線性處理,導(dǎo)致初始估計(jì)出現(xiàn)偏差,為此仿真分析了時(shí)間偏移量τ對(duì)定位誤差的影響。設(shè)定δ2為12,調(diào)整時(shí)間偏移量τ從20ns到200ns之間變化,圖4繪出了ID為5和8的源節(jié)點(diǎn)的定位誤差隨時(shí)間偏移量的變化關(guān)系曲線。由該圖可見,初始估計(jì)值的定位誤差隨著時(shí)間偏移量τ的增加而增大,而經(jīng)過優(yōu)化計(jì)算后,兩個(gè)節(jié)點(diǎn)的定位誤差隨時(shí)間偏移量τ的增加而保持基本不變。當(dāng)時(shí)間偏移量τ=20ns時(shí),源節(jié)點(diǎn)ID為5的初始估計(jì)的對(duì)數(shù)MSE值為-1.1dB,優(yōu)化計(jì)算后的對(duì)數(shù)MSE為-11.8dB;當(dāng)時(shí)間偏移量τ=200ns時(shí),初始估計(jì)的對(duì)數(shù)MSE值增加到了1.3dB,而優(yōu)化計(jì)算后的對(duì)數(shù)MSE值仍然為-11.8dB,該結(jié)果說明優(yōu)化計(jì)算結(jié)果更加可靠。

圖4 定位誤差隨時(shí)間偏移量的變化關(guān)系

5 結(jié)論

本文介紹了一種存在時(shí)間偏移下的多源目標(biāo)定位方法。該方法通過目標(biāo)位置的初始值估計(jì)和優(yōu)化計(jì)算兩步過程實(shí)現(xiàn),經(jīng)過優(yōu)化計(jì)算后的定位精度可以基本和CRLB下界值一致。以多源目標(biāo)定位問題為出發(fā)點(diǎn),將定位問題模型描述為線性最小二乘估計(jì)問題,避免了數(shù)值計(jì)算方法中因初始值選擇不當(dāng)而引起的局部最優(yōu)問題。仿真結(jié)果發(fā)現(xiàn),優(yōu)化計(jì)算后的定位結(jié)果具有較高的可靠性,在較大的時(shí)間偏移量下,其定位誤差還可以保持穩(wěn)定,非常接近于CRLB下界值。

[1] 葉苗,王宇平.一種新的容忍惡意節(jié)點(diǎn)攻擊的無線傳感器網(wǎng)絡(luò)安全定位方法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(3):532-544.

[2]Zhao Jizhong,Xi Wei,He Yuan,et al.Localization of Wireless Sensor Networks in the Wild:Pursuit of Ranging Quality[J].IEEE Transactions on Networking,2013,12(1):311-323.

[3]Liu Yunhao,Yang Zheng,Wang Xiaoping,et al.Location,Localization,and Localizability[J].Journal of Computer Science and Technology,2010,25(2):274-297.

[4]Zhong Ziguo,He Tian.Achieving Range-Free Localization Beyond Connectivity[C]//Proceedings of ACM SenSys,2009:281-294.

[5]Robin Wentao Ouyang,Albert Kai-Sun Wong,Chin-Tau Lea.Received Signal Strength-Based Wireless Localization Via Semidefinite Programming:Noncooperative and Cooperative Schemes[J].IEEE Transactions on Vehicular Technology,2010,59(3):1307-1318.

[6]吳曉平,陸炳斌,沈浩.基于RSSI定位模型的非視距關(guān)系識(shí)別方法[J].傳感技術(shù)學(xué)報(bào),2013,26(11):1584-1589.

[7]Ismail Güven?,Chong Chiachin.A Survey on TOA Based Wireless Localization and NLOS Mitigation Techniques[J].IEEE Communications Surveys and Tutorials,2009,11(3):107-124.

[8]Yang Le,Ho K C.An Approximately Efficient TDOA Localization Algorithm in Closed-Form for Locating Multiple Disjoint Sources With Erroneous Sensor Positions[J].IEEE Transactions on Signal Processing,2009,57(12):4598-4615.

[9]呂方旭,張金成,劉立陽.基于WSN的多聲源目標(biāo)定位算法[J].傳感技術(shù)學(xué)報(bào),2012,25(8):1121-1125.

[10]Chan F K W,So H C,Zheng J,et al.Best Linear Unbiased Estimator Approach for Time-of-Arrival Based Localisation[J].IET Signal Processing,2008,2(2):156-162.

[11]Shen Junyang,Andreas F Molisch,Jussi Salmi.Accurate Passive Location Estimation Using TOA Measurements[J].IEEE Transactions on Wireless Communications,2012,11(6):2182-2192.

[12]Wang Yuan,Ma Shaodan,Philip Chen C L.TOA-Based Passive Localization in Quasi-Synchronous Networks[J].IEEE Communications Letters,2014,18(4):592-595.

[13]Xu Enyang,Ding Zhi,Dasgupta Soura.Source Localization in Wireless Sensor Networks From Signal Time-of-Arrival Measurements[J].IEEE Transactions on Signal Processing,2011,59(6):2887-2897.

[14]Shen Hong,Ding Zhi,Dasgupta Soura,et al.Multiple Source Localization in Wireless Sensor Networks Based on Time of Arrival Measurement[J].IEEE Transactions on Signal Processing,2014,62(8):1938-1949.

Accurate Positioning Approach of Multiple Source Target Under Time Offest

YANChanghong1*,JINLin2

(1.School of information engineering,Yancheng Institute of Technology,Yancheng Jiangsu 224000,China;2.School of Economics and Managment,Yancheng Institute of Technology,Yancheng Jiangsu 224000,China)

It is relatively simple to utilize time of arrival(TOA)ranging for realizing the positioning of multiple source targets,so it is widely applied in the positioning field of wireless sensor networks.Converting the TOA positioning model to the problem of linear optimization,an accurate positioning method for multiple source targets is put forward when there are time offsets.The method divides the process of positioning calculation into two steps,including the initial estimation of multiple source targets and the process of optimization computation.The two-steps calculation method represents the positioning results as the algebraic solutions and avoids the local optimum problem in the process of numerical calculation.The simulations analyze the impacts of time offsets and noises on the positioning errors.The results show that the positioning errors of the optimization calculation can be very close to the Cramer Rao lower bound(CRLB),even if there are larger time offsets.

wireless sensor networks;localization;time of arrival(TOA);multiple source target

嚴(yán)長(zhǎng)虹(1980-),講師,工學(xué)碩士,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、信號(hào)分析與處理、網(wǎng)絡(luò)安全等。在國內(nèi)外重要會(huì)議及期刊上發(fā)表論文十多篇。

2014-10-13 修改日期:2014-11-26

C:6150P;7110

10.3969/j.issn.1004-1699.2015.02.005

TP393.0

A

1004-1699(2015)02-0178-05