郭曉雷 于 寧 吳銀鋒 萬(wàn)江文
(北京航空航天大學(xué) 儀器科學(xué)與光電工程學(xué)院,北京 100191)
可容忍信標(biāo)誤差的三維傳感網(wǎng)節(jié)點(diǎn)定位方法
郭曉雷 于 寧 吳銀鋒 萬(wàn)江文
(北京航空航天大學(xué) 儀器科學(xué)與光電工程學(xué)院,北京 100191)
針對(duì)信標(biāo)位置存在誤差情況下的三維無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問(wèn)題,提出一種基于正交回歸的多跳定位方法.同時(shí)考慮到自變量誤差和因變量偏差對(duì)節(jié)點(diǎn)坐標(biāo)估計(jì)的影響,基于約束加權(quán)正交回歸參數(shù)估計(jì)準(zhǔn)則,建立可容忍信標(biāo)位置誤差的三維多跳定位模型,解決了信標(biāo)位置和距離估計(jì)兩方面的誤差并存時(shí)的節(jié)點(diǎn)自定位問(wèn)題,并給出求解節(jié)點(diǎn)坐標(biāo)最優(yōu)值的數(shù)值方法;推導(dǎo)出相應(yīng)的坐標(biāo)估計(jì)精度評(píng)估標(biāo)準(zhǔn)3D-MCRB(3D Multi-hop Cramér-Rao Bound).仿真結(jié)果表明:此方法對(duì)信標(biāo)位置誤差和距離估計(jì)誤差都具有較好的抑制能力,在大多數(shù)實(shí)驗(yàn)條件下,能將定位精度提高10%以上.
無(wú)線(xiàn)傳感器網(wǎng)絡(luò);三維定位;信標(biāo)位置誤差;正交回歸;Cramér-Rao界
無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs,Wireless Sensor Networks)是由大量的傳感器節(jié)點(diǎn)以無(wú)線(xiàn)通訊的方式組成的多跳自組織網(wǎng)絡(luò)系統(tǒng),網(wǎng)絡(luò)化智慧感知、低成本和布置靈活的優(yōu)勢(shì)使其成為目前IT領(lǐng)域的研究熱點(diǎn)之一[1].在實(shí)際應(yīng)用中,傳感器節(jié)點(diǎn)通常隨機(jī)部署(如飛機(jī)布撒等)在不同的環(huán)境中執(zhí)行各種監(jiān)測(cè)任務(wù),自身的位置無(wú)法事先確定,因此節(jié)點(diǎn)在部署后首先需要實(shí)時(shí)地進(jìn)行自定位.
近些年,許多學(xué)者都致力于傳感網(wǎng)定位技術(shù)方面的研究,文獻(xiàn)[2-3]對(duì)現(xiàn)有的研究成果進(jìn)行了系統(tǒng)的綜述.信標(biāo)節(jié)點(diǎn)作為傳感網(wǎng)定位的基礎(chǔ),位置坐標(biāo)的準(zhǔn)確性直接影響到整個(gè)傳感網(wǎng)的定位性能,目前大多數(shù)經(jīng)典定位算法都是在信標(biāo)位置完全準(zhǔn)確的理想條件下實(shí)現(xiàn)定位.然而,在實(shí)際中,由于信標(biāo)節(jié)點(diǎn)通常依靠GPS(Global Positioning System)或人工部署的方式來(lái)獲取自身的位置信息,坐標(biāo)往往存在一定的不確定性,如何提高傳感網(wǎng)定位對(duì)信標(biāo)位置誤差的容忍能力是一個(gè)亟需解決的重要問(wèn)題.
目前針對(duì)信標(biāo)位置存在誤差情況下傳感網(wǎng)定位的解決方案不多,主要有:文獻(xiàn)[4]提出一種基于二階錐規(guī)劃的分布式定位算法,信標(biāo)節(jié)點(diǎn)通過(guò)與鄰居節(jié)點(diǎn)交互信息的方式,減小自身的位置誤差,然而頻繁的信息交換使得這種算法能耗較高;文獻(xiàn)[5]針對(duì)傳感網(wǎng)迭代定位中初始信標(biāo)及二次信標(biāo)位置存在不確定性的問(wèn)題,分別利用貝葉斯和最小二乘線(xiàn)性估計(jì)法,以及Monte Carlo重要性采樣和成本函數(shù)法,求出未知節(jié)點(diǎn)坐標(biāo)的后驗(yàn)分布;文獻(xiàn)[6]針對(duì)水下/地下傳感網(wǎng)集中式定位問(wèn)題,建立全局極大似然估計(jì)函數(shù),采用半定規(guī)劃技術(shù)實(shí)現(xiàn)信標(biāo)位置誤差獨(dú)立分布條件下的所有節(jié)點(diǎn)定位;文獻(xiàn)[7]通過(guò)坐標(biāo)求精的方法來(lái)解決信標(biāo)位置非理想條件下的傳感網(wǎng)定位問(wèn)題,在一定程度上提高了系統(tǒng)的定位性能.
以上方法主要集中在二維平面分析問(wèn)題,大多對(duì)網(wǎng)絡(luò)的連通性要求較高,通訊消耗較大,算法的擴(kuò)展性也較差,不太適用于大規(guī)模無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的應(yīng)用.
本文從傳感網(wǎng)分布式多跳定位的角度出發(fā),將信標(biāo)位置誤差和距離估計(jì)偏差同時(shí)引入到節(jié)點(diǎn)坐標(biāo)估計(jì)過(guò)程中,在不增加通訊消耗的基礎(chǔ)上,利用正交回歸方法增強(qiáng)系統(tǒng)對(duì)信標(biāo)位置誤差的容忍能力,提高傳感網(wǎng)的定位性能.同時(shí),給出了信標(biāo)位置非理想條件下三維多跳定位的Cramér-Rao界,作為評(píng)估算法定位精度的標(biāo)準(zhǔn).
如圖1所示,未知節(jié)點(diǎn)Nu的坐標(biāo)為Xu=[xu,yu,zu]T,信標(biāo)節(jié)點(diǎn) Na(a=1,2,…,K)的實(shí)際坐標(biāo)為 Xa=[xa,ya,za]T,聲明的坐標(biāo)為 X'a=[x'a,y'a,z'a]T.通過(guò)節(jié)點(diǎn)間直接測(cè)距和多跳信息交互,Nu可以估計(jì)出自身到信標(biāo)節(jié)點(diǎn)Na的多跳距離d'a,距離估計(jì)誤差為ea.這樣,Nu的定位可以看作是如下非線(xiàn)性回歸模型的參數(shù)估計(jì)問(wèn)題:
式中,Xa為自變量,其觀(guān)測(cè)值為信標(biāo)節(jié)點(diǎn)聲明的坐標(biāo){X'1,X'2,…,X'K};da為因變量,其觀(guān)測(cè)值為距離估計(jì)值{d'1,d'2,…,d'K},相應(yīng)的觀(guān)測(cè)誤差為{e1,e2,…,eK};Xu為模型的回歸參數(shù).
對(duì)于Xu的求解,通常采用非線(xiàn)性最小二乘法(NLSE,Nonlinear Least Squares Estimator)即
圖1 節(jié)點(diǎn)三維定位示意圖
當(dāng)信標(biāo)節(jié)點(diǎn)的坐標(biāo)不存在誤差,且ea服從均值為0的正態(tài)分布時(shí),NLSE可以最大限度降低距離估計(jì)誤差對(duì)節(jié)點(diǎn)定位的影響,是Xu的極大似然最優(yōu)估計(jì).但在實(shí)際應(yīng)用中,NLSE為最優(yōu)估計(jì)的前提條件并不滿(mǎn)足,主要體現(xiàn)在兩個(gè)方面:
1)從幾何意義上講,NLSE的目標(biāo)是尋找一條(個(gè))觀(guān)測(cè)點(diǎn)到其垂直距離(觀(guān)測(cè)方向上)平方和為最小的曲線(xiàn)(面),它僅僅考慮了因變量存在的誤差,未將自變量誤差考慮在內(nèi).當(dāng)所有變量都存在誤差時(shí),NLSE的擬合效果和穩(wěn)定性都較差.在傳感網(wǎng)節(jié)點(diǎn)定位中,受到GPS精度或環(huán)境干擾等影響,信標(biāo)節(jié)點(diǎn)聲明的坐標(biāo)并不完全準(zhǔn)確,如果不對(duì)其位置誤差(自變量誤差)進(jìn)行有效處理,得到的定位結(jié)果可信度不高.
2)在多跳定位中,距離估計(jì)誤差由測(cè)距誤差(隨機(jī)誤差)和多跳折線(xiàn)累積誤差(系統(tǒng)誤差)共同組成,即使節(jié)點(diǎn)間的測(cè)距誤差ε服從理想的零均值高斯分布ε~N(0,λ2),多跳距離估計(jì)誤差分布的均值也不一定為0.在ε~N(0,λ2)的條件下,統(tǒng)計(jì)λ分別為(2,4,6)時(shí)多跳距離估計(jì)誤差的概率密度分布(PDF,Probability Distribution Function)結(jié)果如圖2所示.圖2驗(yàn)證了多跳距離估計(jì)誤差近似有偏正態(tài)分布的特性.因此,在求解節(jié)點(diǎn)坐標(biāo)時(shí),還需要將距離估計(jì)偏差(因變量偏差)考慮在內(nèi).
圖2 多跳距離估計(jì)誤差概率密度分布統(tǒng)計(jì)圖
針對(duì)NLSE方法存在的問(wèn)題,本文將信標(biāo)位置誤差和距離估計(jì)偏差同時(shí)引入到節(jié)點(diǎn)坐標(biāo)估計(jì)過(guò)程中,提出一種基于正交回歸的傳感網(wǎng)多跳定位方法.
設(shè)Na聲明的坐標(biāo)在(x,y,z)方向上的誤差(vax,vay,vaz)相互獨(dú)立,均服從均值為 μa、方差為的正態(tài)分布,則Na的位置誤差向量為Va=,其分布,均值向量 Ma=[μa,μa,μa]T.在多跳定位中,ea的分布規(guī)律隨網(wǎng)絡(luò)部署環(huán)境的不同而變化,設(shè)ea~,均值(距離估計(jì)偏差)b和方差都為未知數(shù).考慮到約束加權(quán)正交回歸(CWOR,Constrained Weighted Orthogonal Regression)方法可以同時(shí)降低因變量和自變量?jī)煞矫娴臄_動(dòng)對(duì)回歸參數(shù)估計(jì)的影響,且有效避免局部最優(yōu)值的出現(xiàn),這里將其應(yīng)用于信標(biāo)位置誤差和ea并存時(shí)的節(jié)點(diǎn)坐標(biāo)估計(jì)中,由此建立三維無(wú)線(xiàn)傳感器網(wǎng)絡(luò)多跳定位模型為
當(dāng)pa=qa時(shí),式(2)的目標(biāo)是尋找一個(gè)觀(guān)測(cè)點(diǎn)到其正交距離平方和為最小的曲面,它能最小化自變量和因變量?jī)煞矫嬲`差對(duì)模型參數(shù)估計(jì)的影響,因此是一種較為理想的回歸方法.
在式(2)中,目標(biāo)函數(shù)包含的平方項(xiàng)個(gè)數(shù)為4K,回歸參數(shù)個(gè)數(shù)為3K+4,而NLSE目標(biāo)函數(shù)中平方項(xiàng)和回歸參數(shù)的個(gè)數(shù)僅為K和3.相對(duì)于NLSE,CWOR模型的求解規(guī)模明顯增大.如果仍采用傳統(tǒng)的適用于NLSE的數(shù)值方法求解式(2)的最優(yōu)值Z^,所需的計(jì)算量和存儲(chǔ)量都較大.為了簡(jiǎn)化Z^的求解過(guò)程,本文參考文獻(xiàn)[8]中數(shù)值計(jì)算的思想,對(duì)其中算法進(jìn)行局部修改或簡(jiǎn)化,同時(shí)引入約束條件,得到求解信標(biāo)位置非理想條件下CWOR定位模型最優(yōu)值的數(shù)值方法.
這樣式(2)可以轉(zhuǎn)化為
目標(biāo)函數(shù)S(Z)的梯度G(Z)=2J(Z)T·f(Z),其中J(Z)為f(Z)的Jacobian矩陣,表達(dá)式為
步驟2求 解 S(Z)的 梯 度 G(i)=2(J(i))Tf(i),其中 J(i)=J(Z(i)),f(i)=f(Z(i)).如果‖G(i)‖2≤τ1成立(τ1為一極小門(mén)限值),轉(zhuǎn)到步驟9;否則,執(zhí)行下一步.
步驟3求解一個(gè)正交矩陣Q(i),使得
具體方法如下:
2)對(duì)J(i)a做QR分解,得到這樣
4)分別取a=(1,2,…,K),進(jìn)行K次上述運(yùn)算,得到所有的和
步驟4求解如下帶約束條件的線(xiàn)性最小二乘問(wèn)題,得到和Δb(i):
其中
上式的求解,可以通過(guò)變量代換將其轉(zhuǎn)化為最小距離規(guī)劃(LDP,Least Distance Programming)問(wèn)題[9]來(lái)實(shí)現(xiàn).
步驟5分別取a=(1,2,…,K),求解如下線(xiàn)性方程,得到所有的ΔV(i)a:
步驟6令,其中ΔZ(i)=
步驟7如果|ΔS(i)|≤τ2和‖ΔZ(i)‖2≤τ3中任意一個(gè)成立(τ2和τ3都為極小的門(mén)限值),轉(zhuǎn)到步驟9;否則,令i=i+1,轉(zhuǎn)到下一步.
步驟8如果i≥Imax,轉(zhuǎn)到步驟9,Imax為迭代運(yùn)算的最大允許次數(shù);否則,轉(zhuǎn)到步驟2.
步驟9運(yùn)算停止,輸出
通過(guò)上述運(yùn)算,可以得到信標(biāo)位置誤差和距離估計(jì)誤差并存時(shí)的節(jié)點(diǎn)坐標(biāo)估計(jì)值.
基于估計(jì)理論中的克拉美-羅界(CRB,Cramér-Rao Bound)原理給出一種評(píng)價(jià)標(biāo)準(zhǔn),對(duì)定位精度進(jìn)行評(píng)價(jià).設(shè),其中 Z1=是隨機(jī)參數(shù)向量是非隨機(jī)參數(shù)向量.這樣,對(duì)于式(2)所示的多參數(shù)聯(lián)合估計(jì)問(wèn)題,可以采用隨機(jī)和非隨機(jī)參數(shù)聯(lián)合無(wú)偏估計(jì)的CRB作為其估計(jì)性能的評(píng)估標(biāo)準(zhǔn)[10].文獻(xiàn)[5]給出了信標(biāo)位置不確定條件下二維傳感網(wǎng)迭代定位的CRB,在此基礎(chǔ)上,本文將其推廣到三維傳感網(wǎng)多跳定位的場(chǎng)合,給出節(jié)點(diǎn)定位所能達(dá)到的誤差下界3D-MCRB(3D Multihop CRB).
F1和F2的取值分別為
F1中的聯(lián)合條件分布對(duì)數(shù)似然函數(shù)為
其相應(yīng)的偏導(dǎo)數(shù)為
根據(jù)ED'{(D'-D -B)(D'-D -B)T}=Σ2,可得
F2表達(dá)式中的聯(lián)合分布對(duì)數(shù)似然函數(shù)為
其偏導(dǎo)數(shù)為
于是,F(xiàn)2表達(dá)式中的左上角塊矩陣為
通過(guò)上述推導(dǎo),b無(wú)偏估計(jì)的CRB不等式為
式中
Xu無(wú)偏估計(jì)的CRB不等式為
式中
這樣,通過(guò)計(jì)算I(Xu)可以推出節(jié)點(diǎn)坐標(biāo)估計(jì)誤差的下限,即信標(biāo)位置和距離估計(jì)兩方面的誤差并存時(shí)三維傳感網(wǎng)多跳定位所能達(dá)到的最高精度.
在200×200×200的三維空間區(qū)域內(nèi)隨機(jī)部署200個(gè)傳感器節(jié)點(diǎn),其中信標(biāo)節(jié)點(diǎn)個(gè)數(shù)S1=20,未知節(jié)點(diǎn)個(gè)數(shù)S2=180.在默認(rèn)條件下,網(wǎng)絡(luò)連通度為12,節(jié)點(diǎn)間測(cè)距誤差ε~N(0,12),信標(biāo)位置誤差向量V~N(M,σ2I),M=[μ,μ,μ]T,μ=1,σ=1.為了避免參考野值的出現(xiàn),將信標(biāo)節(jié)點(diǎn)坐標(biāo)在任一方向上的誤差都限制在±15之內(nèi).仿真中,相同條件下的實(shí)驗(yàn)都運(yùn)行100次,取NLSE和CWOR兩種方法的平均定位誤差(ALE,Average Localization Error)與相應(yīng)的3D-MCRB進(jìn)行比較.ALE和3D-MCRB的計(jì)算公式如下:
分別改變信標(biāo)位置誤差的均值μ和標(biāo)準(zhǔn)差σ,得到兩種方法的ALE和相應(yīng)的3D-MCRB對(duì)比結(jié)果如圖3和圖4所示.隨著μ增大,NLSE的ALE大致呈逐漸增長(zhǎng)的趨勢(shì),在μ=5時(shí),其ALE超過(guò)50%;CWOR受μ的影響較小,其ALE始終不超過(guò)30%;由于節(jié)點(diǎn)坐標(biāo)無(wú)偏估計(jì)的CRB與μ無(wú)關(guān),因此圖3中的3D-MCRB幾乎為一條直線(xiàn).圖4中,3條曲線(xiàn)都隨σ的增大逐漸上升,其中NLSE的曲線(xiàn)變化最為明顯,CWOR和3D-MCRB的變化趨勢(shì)大致相同;CWOR的定位精度始終比NLSE的高14%以上,在 σ=8時(shí)甚至能達(dá)到26%.3D-MCRB顯示了節(jié)點(diǎn)坐標(biāo)無(wú)偏估計(jì)可能達(dá)到的誤差下界,在兩種情況下,CWOR僅比3DMCRB高10%左右.綜上分析,CWOR對(duì)信標(biāo)位置誤差具有較強(qiáng)的容忍能力.
圖3 信標(biāo)位置誤差均值對(duì)定位性能的影響
圖5為平均定位誤差隨測(cè)距誤差標(biāo)準(zhǔn)差λ變化的關(guān)系圖.在不同λ下,NLSE的ALE始終高于節(jié)點(diǎn)通訊半徑的40%,最大為58.7%.在 λ≤6時(shí),CWOR的ALE變化不明顯,始終處于25% ~27%之間;在λ=7時(shí),也僅為30%;繼續(xù)增大λ,CWOR的ALE在λ=9時(shí)才略超過(guò)40%(仍比NLSE低13%,相應(yīng)的3D-MCRB此時(shí)已經(jīng)達(dá)到26%).因此,CWOR對(duì)測(cè)距誤差具有一定的抑制能力,在λ不大時(shí)效果較明顯.
圖4 信標(biāo)位置誤差標(biāo)準(zhǔn)差對(duì)定位性能的影響
圖5 測(cè)距誤差標(biāo)準(zhǔn)差對(duì)定位性能的影響
改變R,得到不同連通度下傳感網(wǎng)定位精度對(duì)比曲線(xiàn)如圖6所示.
圖6 網(wǎng)絡(luò)連通度對(duì)定位性能的影響
隨著網(wǎng)絡(luò)連通度的增大,不相鄰節(jié)點(diǎn)間的最短路徑接近直線(xiàn)的概率增大(多跳折線(xiàn)累積誤差減小),同時(shí)未知節(jié)點(diǎn)在信息幀生命周期(TTL,Time To Live)范圍內(nèi)可以獲得的參考信息數(shù)量增加,因此兩種方法的ALE都呈逐漸下降的趨勢(shì).在網(wǎng)絡(luò)連通度較小時(shí)(不大于9),相對(duì)于NLSE,CWOR能夠顯著提高傳感網(wǎng)的定位精度(超過(guò)30%),其ALE接近3D-MCRB;在網(wǎng)絡(luò)連通度為15時(shí),CWOR仍能將定位精度提高約14%.
由于信標(biāo)位置的不確定性和多跳距離估計(jì)的有偏性,節(jié)點(diǎn)自定位時(shí)需要將自變量誤差和因變量偏差同時(shí)考慮在內(nèi).本文給出一種適用于大規(guī)模三維無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)多跳定位方法,采用正交回歸技術(shù),最小化信標(biāo)位置和距離估計(jì)兩方面的擾動(dòng)對(duì)節(jié)點(diǎn)坐標(biāo)估計(jì)的影響,增強(qiáng)傳感網(wǎng)定位系統(tǒng)的容錯(cuò)性能.在大多數(shù)實(shí)驗(yàn)條件下,相對(duì)于非線(xiàn)性最小二乘法,CWOR能將定位精度提高10%以上,定位誤差更接近3D-MCRB;在網(wǎng)絡(luò)連通度較小時(shí),CWOR具有更加明顯的優(yōu)勢(shì).
References)
[1] BurattiC,Conti A,DardariD,et al.An overview on wireless sensor networks technology and evolution[J].Sensors,2009,9(9):6869-6896
[2] Boukerche A,Oliveira H A B F,Nakamura E F,el al.Localization systems for wireless sensor networks[J].IEEE Wireless Communications,2007,14(6):6 -12
[3] Mao G Q,F(xiàn)idan B,Anaderson B D O.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2529-2553
[4] Srirangarajan S,Tewfik A H,Luo ZQ.Distributed sensor network localization using SOCP relaxation[J].IEEE Transactions on Wireless Communications,2008,7(12):4886 -4895
[5] Vemula M,Bugallo M E,Djuric PM.Sensor self-localization with beacon position uncertainty[J].Signal Processing,2009,89(6):1144-1154
[6] Lui KW K,Ma W K,So H C,et al.Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed[J].IEEE Transactions on Signal Processing,2009,57(2):752 -763
[7] Wan Jiangwen,Yu Ning,F(xiàn)eng Renjian,et al.Localization refinement for wireless sensor networks[J].Computer Communications,2009,32(13 -14):1515 -1524
[8] Schwetlick H,Tiller V.Numerical methods for estimating parameters in nonlinear models with errors in the variables[J].Te chnometrics,1985,27(1):17 - 24
[9] Lawson C L,Hanson R J.Solving least squares problem[M].Philadelphia:Society for Industrial and Applied Mathematics,1995
[10] Messer H.The hybrid Cramer-Rao lower bound-from practice to theory[C]//In Proceedings of Fourth IEEE Workshop on Sensor Array and Multichannel Processing.Waltham:Signal Processing Society,2006:304 -307
(編 輯:劉登敏)
Beacon error-tolerable method for node localization in 3D w ireless sensor networks
Guo Xiaolei Yu Ning Wu Yinfeng Wan Jiangwen
(School of Instrument Science and Opto-electronics Engineering,Beijing University of Aeronautics and Astronautics,Beijing 100191,China)
For 3D wireless sensor networks(WSNs)with inaccurately positioned beacon nodes,a novel multi-hop node localizationmethod that can tolerate beacon position errorswas proposed.The influences of independent variable errors and dependent variable biases on node coordinate estimation were taken into account simultaneously.Based on the principle of constrained weighted orthogonal regression,a reliable 3Dmulti-hop localization model was constructed,and the numerical method for calculating the optimum value of node coordinates was given.The 3D multi-hop Cramér-Rao bound(3D-MCRB)for node localization under combined uncertainties in beacon positions and estimative distances was also derived.Simulation results show that the novel method is robust against beacon position errors and distance estimation errors.Inmostexperiment conditions,the multi-hop localization accuracy can be improved by at least10%.
wireless sensor networks;3D localization;beacon position error;orthogonal regression;Cramér-Rao bound
TP 393
A
1001-5965(2012)06-0810-06
2011-03-24;網(wǎng)絡(luò)出版時(shí)間:2012-06-15 15:44
www.cnki.net/kcms/detail/11.2625.V.20120615.1544.034.htm l
國(guó)家自然科學(xué)基金資助項(xiàng)目(60974121,61001138)
郭曉雷(1983 -),男,河北石家莊人,博士生,sensory@buaa.edu.cn.