時間偏移下的多源目標精確定位方法

嚴長虹,金 琳

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

?

時間偏移下的多源目標精確定位方法

嚴長虹1*,金 琳2

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

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

無線傳感器網(wǎng)絡;定位;到達時間(TOA);多源目標

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

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

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

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

1 問題描述

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

(1)

(2)

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

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

2 克拉美羅下界值

(3)

式(3)中,

(4)

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

(5)

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

(6)

(7)

3 多源目標定位

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

3.1 多源目標位置初始值估計

將式(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。對式(8)左右兩邊平方,忽略高階項,式(8)再表示為

(9)

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

(10)

Aη=b+α

(11)

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

當所有源節(jié)點與信標節(jié)點間共存在L次TOA測距時,A∈RL×(3N+M),b∈RL×1,α∈RL×1。

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

(12)

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

(13)

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

3.2 目標位置優(yōu)化計算

(14)

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

CΔθ=d+α

(15)

(16)

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

(17)

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

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

(18)

3.3 算法的計算復雜度分析

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 仿真分析

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

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

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

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

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

圖3 源節(jié)點ID為8時噪聲對定位誤差的影響

4.2 噪聲對定位誤差的影響

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

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

4.3 時間偏移量對定位誤差的影響

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

圖4 定位誤差隨時間偏移量的變化關系

5 結(jié)論

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

[1] 葉苗,王宇平.一種新的容忍惡意節(jié)點攻擊的無線傳感器網(wǎng)絡安全定位方法[J].計算機學報,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定位模型的非視距關系識別方法[J].傳感技術(shù)學報,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的多聲源目標定位算法[J].傳感技術(shù)學報,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

嚴長虹(1980-),講師,工學碩士,主要研究方向為無線傳感器網(wǎng)絡、信號分析與處理、網(wǎng)絡安全等。在國內(nèi)外重要會議及期刊上發(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