目標監(jiān)測傳感器網(wǎng)絡中錨節(jié)點優(yōu)化布設

汪 晗，王 坤，張 磊，宋樹偉

(1.陸軍工程大學 指揮控制工程學院，江蘇 南京 210007；2.94860部隊 自動化站，江蘇 南京 210018；3.陸軍參謀部，北京 100042)

0 引 言

傳感器網(wǎng)絡定位技術[1-3]作為無線傳感器網(wǎng)絡的核心支撐技術得到學術界的廣泛關注。為了獲得網(wǎng)絡中傳感器節(jié)點的絕對位置，通常需要布設一些位置已知的錨節(jié)點，其它位置未知的節(jié)點(待定位節(jié)點)通過測量與錨節(jié)點之間的位置約束關系，進而采用定位算法解算出自身的位置。目前傳感器網(wǎng)絡定位的研究工作大多集中于定位算法的設計與改進[4-7]，這些定位算法通?？紤]在錨節(jié)點的數(shù)量和布設位置已知的情況下，如何提高定位算法的位置解算精度。然而從定位系統(tǒng)的架構層面而言，傳感器網(wǎng)絡中如何布設錨節(jié)點是首要解決的問題，對整個網(wǎng)絡的節(jié)點定位精度具有重要影響。

目前傳感器網(wǎng)絡錨節(jié)點優(yōu)化布設已成為節(jié)點定位技術研究的重要方向，具有較大的實用價值。例如在橋梁健康監(jiān)測應用中，通過優(yōu)化布設少量傳感器節(jié)點，對橋梁的關鍵部位進行實時的形變監(jiān)測，可以提前發(fā)現(xiàn)橋梁病害，降低橋梁事故概率。當錨節(jié)點布設不佳，例如錨節(jié)點與待定位節(jié)點構成的幾何形狀較差時，無論采用何種定位算法，節(jié)點定位精度的提高都將受限[8]。目前錨節(jié)點優(yōu)化布設方面的研究工作大多著眼于確保節(jié)點可定位[9]，較少考慮錨節(jié)點幾何形狀對定位精度的影響。優(yōu)化布設工作大多基于搜索方法[10]來提高定位精度，即在錨節(jié)點布設組合空間內搜索優(yōu)化布設方案，而基于理論推導的錨節(jié)點優(yōu)化布設工作較少。

本文首先從理論上分析研究了錨節(jié)點幾何形狀對定位精度的影響，基于到達時間TOA測距推導出幾何精度因子GDOP[11](geometric dilution of precision)表達式，揭示了同一定位算法在測距誤差相同的情況下節(jié)點定位精度不同的本質原因。給定待監(jiān)測目標點，首先從理論上推導出錨節(jié)點最優(yōu)幾何排列需滿足的充要條件，并仿真推導出錨節(jié)點幾何面積對目標位移監(jiān)測精度的影響。大規(guī)模仿真實驗表明，在相同的測距誤差分布和定位算法下，錨節(jié)點優(yōu)化布設算法與隨機布設算法比較而言，前者能夠顯著提高定位精度，在目標定位監(jiān)測等應用中具有實用價值。

1 幾何精度因子

圖1表示測距誤差ε相同時，由于錨節(jié)點與待定位節(jié)點的幾何形狀不同，將造成待定位節(jié)點的定位誤差存在較大區(qū)別，如陰影所示，幾何形狀越好，定位誤差越小，對應的陰影面積也越小。

圖1 定位誤差

圖2表示2維空間中(D=2)單節(jié)點的定位問題，p=(x,y)表示待定位節(jié)點O的真實位置，qi=(xi,yi),(i=1,…,M)表示M個錨節(jié)點的位置，錨節(jié)點與待定位節(jié)點之間的幾何排列Ψ可用矩陣G來定量表示。

圖2 二維中的定位情形

(1)

式中:v表示信號傳播速度，ni表示對應于第i個錨節(jié)點的TOA測量誤差。

假設測量誤差n=(n1,n2,…,ni…,nM)服從均值為零的高斯分布，并且n的協(xié)方差矩陣C滿秩。那么TOA的測量值τ=(τ1,τ2,…,τi…,τM)的概率密度函數(shù)(PDF)可以表示為

(2)

據(jù)此可以求出對應的費希爾信息矩陣J

J=E{[▽lnf(τ;p)][▽lnf(τ;p)]T}

(3)

其中，▽表示對p求梯度，E(·)表示對τ求期望。根據(jù)定義及式(3)，待定位節(jié)點的定位誤差克拉美羅下界(Cramer-Rao lower bound，CRLB)可以表示為

(4)

其中

(5)

gi是單位長度矢量，G是D×M矩陣，tr(·)表示求跡運算。

假設測量誤差n是相互獨立的高斯分布，且均值為零，方差為σ2，那么n的協(xié)方差矩陣C可以用式(6)表示

C=σ2IM×M

(6)

I表示單位方陣。從式(4)、式(6)可計算出待定位節(jié)點的定位誤差克拉美羅下界

(7)

當定位算法是無偏估計時，σCRLB可以近似表示σp

(8)

幾何精度因子GDOP定義為定位誤差σp與測距誤差σ的比值，見式(9)

GDOP=σp/σ

(9)

將式(8)代入式(9)可得到幾何精度因子的最終表達式

(10)

由式(10)可知，GDOP與測距誤差無關，僅與G有關。給定錨節(jié)點與待定位節(jié)點之間的幾何排列Ψ，可根據(jù)式(5)計算出矩陣G，此時在定位誤差中幾何排列Ψ對測距誤差σ的放大系數(shù)GDOP也唯一確定。

2 最優(yōu)幾何排列

本文從單跳傳感器網(wǎng)絡中錨節(jié)點的優(yōu)化布設入手，考慮當網(wǎng)絡中所有節(jié)點間的距離都在信號單跳傳播范圍內時，如何優(yōu)化布設錨節(jié)點使得單個待定位節(jié)點的定位精度最高。

從式(8)和式(10)推導可得式(11)

σp≈σCRLB=σ·GDOP

(11)

證明：假設GGT的特征值為λi，λi>0，那么根據(jù)特征值的定義可知(GGT)-1的特征值是1/λi。由于

根據(jù)Cauchy-Schwarz不等式

所以有

(12)

由于

tr(GGT)=M

(13)

tr(GGT)=tr(λI)=λtr(I)=λD

(14)

對比式(13)、式(14)可知M=λD=>λ=M/D。

滿足條件GGT=(M/D)I的矩陣G稱為錨節(jié)點最優(yōu)排列Ψopt。

根據(jù)式(5)中G的定義，tr[(GGT)-1]可以變形為式(15)

(15)

θi表示節(jié)點坐標系x軸正方向與第i個錨節(jié)點至待定位節(jié)點連線的夾角。

在2維定位情形下，即D=2時，我們對錨節(jié)點最優(yōu)排列形式進行推導。在橋梁形變監(jiān)測等目標點監(jiān)測應用中，待監(jiān)測點可以位于錨節(jié)點所構成的閉合區(qū)域內也可位于閉合區(qū)域外，下面分別對兩種情形進行推導。

(1)待監(jiān)測點位于錨節(jié)點閉合區(qū)域內

待監(jiān)測目標點與錨節(jié)點的位置關系如圖3所示，虛線表示錨節(jié)點形成的閉合區(qū)域，目標點O與各錨節(jié)點i(i=1,2,…,M)之間連線的夾角用θij表示。

圖3 待監(jiān)測點位于錨節(jié)點閉合區(qū)域內

圖3中，由于待監(jiān)測目標節(jié)點位于錨節(jié)點形成的閉合區(qū)域內，因此顯而易見相鄰錨節(jié)點之間的夾角和為2π，即

θ12+θ23+…+θM1=2π

(16)

因此在二維定位情形下(D=2)尋找圖3中的最優(yōu)錨節(jié)點形狀，等價于在式(16)的約束條件下求式(15)的最小值。我們利用拉格朗日乘數(shù)法構造如下輔助函數(shù)

(17)

(18)

當θ12=θ23=…=θM1=2π/M時滿足式(18)，此時錨節(jié)點呈現(xiàn)均勻等角的布設形狀，即錨節(jié)點與目標節(jié)點的連線平分圓周角2π。為表述簡潔以目標點為中心建立坐標系，此時各錨節(jié)點的位置矢量可表示為

以M=4，D=2為例，其最優(yōu)排列如圖4所示，此時各錨節(jié)點的方位角為

圖4 最優(yōu)排列

對應的錨節(jié)點位置矢量坐標分別為：g1=[cosα,sinα]，g2=[cos(π/2+α),sin(π/2+α)],g3=[cos(π+α),sin(π+α)]，g4=[cos(3π/2+α),sin(3π/2+α)]。

(2)待監(jiān)測點位于錨節(jié)點閉合區(qū)域外

圖5表示待監(jiān)測點O位于閉合區(qū)域外的情形，此時M個錨節(jié)點與目標節(jié)點連線的夾角必然存在一個最大值，其它錨節(jié)點均位于該最大夾角內，且該最大夾角為其它所有相鄰錨節(jié)點間的夾角之和。在圖5中θM1最大，因此有

θ12+θ23+…+θ(M-1)M=θM1

(19)

圖5 待監(jiān)測點位于錨節(jié)點閉合區(qū)域外

利用拉格朗日乘數(shù)法，構造輔助函數(shù)見式(20)

(20)

(21)

結合式(19)的約束條件θ12+θ23+…+θ(M-1)M=θM1(θM1<2π)可知：

(22)

以M=4，D=2為例，其最優(yōu)排列如圖6所示，此時各錨節(jié)點的方位角表達式見式(23)

(23)

圖6 最優(yōu)排列

3 仿真分析

對于橋梁形變監(jiān)測等靜態(tài)目標監(jiān)測應用中，需要對特定點進行精確的定位監(jiān)測，以實時發(fā)現(xiàn)細微的位移形變，進而提前進行預防和拯救。前面已通過理論推導出錨節(jié)點與單個待監(jiān)測點的最優(yōu)幾何排列形式為均勻等角布設，下面我們通過仿真進一步研究當待監(jiān)測點出現(xiàn)微小形變時，如何優(yōu)化布設錨節(jié)點進而提高待監(jiān)測點的定位精度。

3.1 幾何面積的影響

仿真設計如圖7所示，3個錨節(jié)點與待監(jiān)測點成均勻等角布設，假設待監(jiān)測點在半徑d=3米的圓面內發(fā)生形變，且形變概率服從均勻分布，改變錨節(jié)點與待監(jiān)測點間的距離值r，進而改變錨節(jié)點的幾何面積。

圖7 仿真場景

假設測距誤差服從均值為0的高斯分布N(0,δ2)，δ=0.5米，且節(jié)點間的測距誤差相互獨立；在[5,50]米的區(qū)間內均勻改變距離值r，對于每一個r值，在圓面內等概率改變待監(jiān)測點的位置，蒙特卡洛仿真N=10000次取平均定位均方根誤差RMS作為距離值r對應的定位結果。

RMS的定義見式(24)

(24)

仿真結果如圖8所示，從圖可知，隨著r值的增大，錨節(jié)點幾何面積也增大，圓面區(qū)域內的定位誤差逐漸變小，這帶給我們的啟示是：為了提高待監(jiān)測點的定位精度，在錨節(jié)點幾何形狀不變(均勻等角布設)的情況下，幾何面積起到了更大的作用，因而在錨節(jié)點優(yōu)化布設時，要兼顧考慮幾何面積的大小，使之覆蓋盡可能大的監(jiān)測區(qū)域。鑒于無線信號的傳播距離及衰減特性，在應用中要綜合考慮信號傳播、布設環(huán)境與布設面積之間關系，優(yōu)化錨節(jié)點的布設。

圖8 錨節(jié)點幾何面積對定位誤差的影響

3.2 優(yōu)化布設性能

前面章節(jié)已通過理論推導出錨節(jié)點與單個待監(jiān)測點的最優(yōu)幾何排列形式：當錨節(jié)點呈現(xiàn)均勻等角布設時，對應的GDOP值最??；并通過仿真指出錨節(jié)點幾何面積對目標位移監(jiān)測精度的影響，錨節(jié)點幾何面積越大，對位移監(jiān)測的精度越高。下面我們通過仿真實例探討錨節(jié)點優(yōu)化布設與隨機布設的定位性能差異。

仿真場景如圖9所示，待監(jiān)測點位于100×100米的正方形區(qū)域的中央，根據(jù)上述結論，3個錨節(jié)點的優(yōu)化布設形狀為均勻等夾角布設且在區(qū)域內布設的錨節(jié)點幾何面積要盡量大。

圖9 錨節(jié)點最優(yōu)排列

假設測量誤差服從均值為0的高斯分布N(0,δ2)，δ在[0,2]米之間均勻取值，且節(jié)點間的測距誤差相互獨立；對于每一個δ值，蒙特卡洛仿真N=10000次取平均定位精度值(定位均方根誤差RMS)作為測距誤差δ對應的定位結果，仿真基于MATLAB R2012b軟件平臺實現(xiàn)。

錨節(jié)點在區(qū)域內的優(yōu)化布設位置如圖9所示。待監(jiān)測點在錨節(jié)點優(yōu)化布設下的定位精度與隨機布設下的定位精度對比如圖10所示，從圖10可知，在不同的測距誤差δ下，錨節(jié)點優(yōu)化布設對應的定位精度明顯高于隨機布設的定位精度，并與定位誤差CRLB接近。這表明仿真實驗與理論推導相符合，對實際應用中的錨節(jié)點優(yōu)化布設具有正確的指導意義。

圖10 定位精度對比

4 結束語

本文在單跳傳感器網(wǎng)絡中優(yōu)化錨節(jié)點布設以提高待監(jiān)測點定位精度，通過推導幾何精度因子的表達式指出測距誤差相同時，錨節(jié)點幾何形狀對目標節(jié)點定位誤差的乘性影響。基于此從理論上嚴格推導出錨節(jié)點最優(yōu)幾何排列的充要條件，并給出最優(yōu)幾何排列的實例。仿真結果表明，在錨節(jié)點幾何形狀不變的情況下，錨節(jié)點幾何面積越大，待監(jiān)測點的位移監(jiān)測越準確；錨節(jié)點優(yōu)化布設下的定位精度遠高于隨機布設精度，這對監(jiān)測應用中優(yōu)化布設錨節(jié)點具有實際的應用價值。