無線傳感器網絡的錨節點優化布設算法

, ,,

(1.解放軍理工大學 指揮信息系統學院,南京 210007; 2.94860部隊,南京 210018; 3.94789部隊,南京 210018)

0 概述

在無線傳感器網絡(Wireless Sensor Network,WSN)應用中,針對微型傳感器節點監測、感知和采集的各種環境或對象信息,只有與特定的節點位置相結合才能為相關應用提供有效的決策支持。無線傳感器網絡在戰場偵查[1]、環境生態監測[2-3]、人員跟蹤定位[4]等方面應用廣泛。除了錨節點通過配備GPS接收機或人工手動配置等方法獲得自身位置外,剩余的大量節點通過測量與錨節點的距離信息,并使用某些定位算法來間接獲得自身的位置。由于靜態錨節點一經布設其位置便不再移動,且所有節點的位置解算都要以錨節點的位置為參考,因此,錨節點的位置對節點的定位效果具有直接影響,進而影響網絡的應用性能,例如提高監測區域的覆蓋率[5]、降低網絡壽命[6]等。

本文研究單跳定位的場景,從理論分析入手,研究分析錨節點幾何形狀對定位精度的影響,以到達時間(Time of Arrival,TOA)測距為例,給出幾何精度因子(Geometric Dilution of Precision,GDOP)[7]的計算公式,揭示同一種定位算法下,當測距誤差相同時,節點定位精度不同的本質原因。本文提出區域定位的概念,并給出區域定位精度的評價指標,即區域定位誤差均界。通過仿真分析研究錨節點布設因素(錨節點質心、幾何形狀、幾何面積)對區域定位精度的影響,據此設計錨節點優化布設的啟發式(Heuristic Optimization Anchor node Deployment,HOAD)算法。

1 相關工作

關于錨節點布設的工作較多。文獻[8]提出了以每個節點至少被3個錨節點覆蓋為約束,在一個規則網絡中計算定位所需的最少錨節點數目。文獻[9-10]給定一些已布設的錨節點,并在此基礎上利用人或移動的機器人增加額外的錨節點,以擴大錨節點的覆蓋區域。這些工作主要著眼于確保節點的可定位,未考慮錨節點布設的幾何形狀對定位精度的影響。相關定位算法的研究大多著眼于給定錨節點的數量和在網絡中的布設位置后,如何盡可能地提高算法的定位精度[11]。然而從定位系統架構的角度上看,當錨節點布設不佳時,例如錨節點與待定位節點構成的幾何形狀較差時,無論采用何種定位算法,節點定位精度的提高都將受限。

目前從提高定位精度角度優化錨節點的布設大多基于搜索方法[12-14]。給定待布設的錨節點個數M,先設定優化目標函數,再將待定位區域進行離散劃分,將離散點作為錨節點的候選位置,從中任選M個進行窮盡組合,計算每種組合下的目標函數值,將最小值對應的位置組合作為錨節點的最終位置。這類基于搜索的方法雖能確保定位精度,但計算復雜度非常高,在錨節點個數多、網絡布設區域大、形狀復雜時,難以實現準確的定位。因而有必要提出一種復雜度低、易于實現的啟發式錨節點優化布設策略,在給定待布設的錨節點個數和區域形狀的情況下,從區域中選擇錨節點的優化位置,在確保待定位節點定位精度的前提下降低計算復雜度。

2 錨節點對定位精度的影響

2.1 定位誤差界和幾何精度因子

定位誤差的克拉美羅下界(Cramer-Rao Lower Bound,CRLB)[15]是節點位置無偏估計的誤差協方差下界,通常用于衡量定位算法所能達到的性能。GDOP表征了當存在測量誤差時,錨節點和目標節點的幾何排列Ψ對定位誤差的影響。本文基于TOA測距進行定位問題的描述和定位誤差界及GDOP的推導。

圖1 二維中的定位情形

由于在測量中受環境噪聲、時鐘同步誤差等因素的影響,錨節點i與目標節點之間的信號TOA測量值τi含有誤差,表示為:

其中,v表示信號傳播速度,ni表示信號的TOA測量誤差。

假設TOA的測量誤差n服從均值為零的高斯分布,并且n的協方差矩陣C滿秩,那么TOA的測量值τ的概率密度函數(Probability Density Function,PDF)可以表示為[16]:

(2)

據此可以求出對應的費希爾信息矩陣J:

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

(3)

其中,▽表示對p求梯度,E(·)表示對τ求期望。

根據定義及式(2)、式(3),單目標節點的定位誤差CRLB可以表示為:

其中:

gi是單位長度矢量,‖gi‖=1,方向從錨節點qi指向目標節點p,G是D×M矩陣,由目標節點和錨節點的幾何位置決定,tr(·)表示求跡運算。

將式(4)開根號可得到定位誤差的CRLB:

GDOP概念來自衛星幾何學[17],定義為:

σGDOP=σp/σm

(7)

其中,σp和σm分別表示位置估計和距離測量的均方根(Root Mean Square,RMS)誤差。當TOA的測量誤差n服從均值為零、方差為σ2的高斯獨立同分布時,σm=vσ,且n的協方差矩陣C具有如下形式:

C=σ2IM×M

(8)

其中,σ2表示高斯分布的方差,I表示單位方陣。

對于無偏估計的定位算法而言,σp可以用定位誤差下界σCRLB來近似表示[16,18]:

將σm=vσ和式(8)、式(9)代入式(7)可得到GDOP的表達式:

對式(7)進行變形得到式(11):

由式(10)可知,GDOP僅由矩陣G決定,G由幾何排列Ψ決定。從式(11)可以更直觀地看出定位誤差與幾何精度因子的關系:GDOP表征了當存在測距誤差σm時,在定位誤差σp中幾何排列Ψ對σm的放大作用。

2.2 區域定位問題和搜索布設算法

第2.1節研究了錨節點和單個目標節點構成的幾何形狀對定位精度的影響,下面研究區域定位問題,即多個目標節點在凸區域A內隨機均勻布設時,錨節點對多個目標節點平均定位精度的影響。給定錨節點的個數M,從區域A內選出M個錨節點的位置qi,i=1,2,…,M,使得隨機布設的目標節點在A內的平均定位精度最高。

從第2.1節可知單個目標節點的定位精度可用定位誤差CRLB表示。對于區域定位問題,A內隨機布設的每個目標節點都對應一個幾何排列和CRLB,因此,平均定位精度可用CRLB均值來表示,稱該均值為區域定位誤差均界。

當錨節點位置qi改變時,對于目標節點(x,y)而言,CRLB(x,y)會發生變化,對應的目標函數F值亦發生變化。為了在區域內尋找錨節點的最優布設位置,使目標函數F值最小,最直觀的方法是搜索法,將區域A離散化,將其均勻劃分為N個小格,小格的端點代表錨節點的位置候選點,從中任選M個位置組合Bt作為錨節點的坐標,然后計算在該組合Bt下,N個點的平均CRLB值,作為區域定位誤差均界,從而將式(12)的積分轉化為式(13)的求和:

算法1錨節點搜索布設算法

Bopt= null; %最優的錨節點位置組合

Fopt= inf; %最優的目標函數值為無窮大

用式(13)計算區域內N個點的平均CRLB值Ft;

If Ft< Fopt

Bopt= Bt;

Fopt= Ft;

End

End

3 啟發式優化布設算法

鑒于錨節點搜索布設算法的計算復雜度較高,有必要提出啟發式的布設方式。對錨節點布設的構成因素,例如錨節點質心、錨節點幾何形狀、錨節點幾何面積等進行仿真分析,給出定性結論,并在此基礎上提出錨節點的啟發式優化布設算法。

3.1 仿真分析

以3個錨節點為例,在100 m×100 m的正方形區域內進行布設,假設測距誤差σ=1 m,探討錨節點質心的位置、錨節點的面積、錨節點的幾何形狀3個因素對區域定位誤差均界的影響。

3.1.1 質心因素

仿真配置為:由錨節點構成正三角形,極徑20 m,保持幾何形狀和角度不變,僅改變錨節點在區域內的質心。錨節點和質心的移動示意圖如圖2所示。

圖2 錨節點和質心的移動

將正方形區域離散化,使其劃分為5 m×5 m的小格,每個小格的端點作為待定位點的位置,然后利用式(13)計算錨節點、質心位于不同位置處的區域定位誤差均界,仿真結果如圖3所示。

圖3 錨節點質心對定位誤差的影響

從圖3可知,錨節點幾何質心從區域中心向區域邊緣移動的過程中,定位誤差均界呈單調增加的趨勢,當錨節點幾何質心與區域中心(0,0)重合時,區域定位誤差均界達到最小值。因此,為了降低區域定位誤差, 錨節點的幾何中心要盡量與區域中心重合。

3.1.2 幾何形狀因素

仿真配置為:錨節點位于以區域中心為原點的圓周上,圓半徑20 m,其中一個錨節點位于x軸正方向上,坐標為(20,0)不變,第2個錨節點保持極角為120°不變,改變第3個錨節點對應的極角θ,在[150°,330°]范圍內每隔30°變化一次θ。錨節點的幾何形狀如圖4所示。

圖4 錨節點的幾何形狀

將正方形區域離散化,使其劃分為5 m×5 m的小格,每個小格的端點作為待定位點的位置,然后利用式(13)計算第3個錨節點對應的極角θ在[150°,330°]范圍內每隔30°變化一次時的區域定位誤差均界。幾何形狀對定位誤差的影響結果如圖5所示。其中,x軸表示第3個錨節點的極角θ,對應三角形的幾何形狀,y軸表示區域定位誤差均界。

圖5 幾何形狀對定位誤差的影響

從圖5可知,當錨節點間的夾角(120°,θ-120°,360°-θ)越接近時,區域定位誤差越小。當θ=240°時,區域定位誤差均界達到最小值,此時錨節點呈均勻等角布設。因此,為了降低區域定位誤差, 錨節點間的夾角要盡量接近;在同等條件下,當夾角相等時,區域定位誤差均界最小。

3.1.3 幾何面積因素

仿真配置為:由錨節點構成正三角形,質心與正方形的中心重合,逐步增大三角形對應的半徑r。錨節點幾何面積變化示意圖如圖6所示,通過改變三角形的幾何面積,將正方形區域離散化,使其劃分為5 m×5 m的小格,每個小格的端點作為待定位節點的位置,然后利用式(13)計算錨節點半徑r取不同值時對應的區域定位誤差均界。仿真結果如圖7所示。

圖6 錨節點幾何面積的變化

圖7 幾何面積對定位誤差的影響

從圖7可知,隨著錨節點面積的增大,區域定位誤差逐漸變小。因此,為了降低區域定位誤差, 錨節點的幾何面積要盡量大,覆蓋盡可能廣的待定位區域。

當錨節點不構成正三角形時,考察錨節點幾何形狀與幾何面積對區域定位誤差均界的影響。錨節點間的夾角保持120°不變,為保持錨節點三角形(正三角形、非正三角形)的幾何面積相等,非正三角形的極徑設置如圖8所示。

圖8 不同的錨節點形狀

改變極徑r值大小,使不同形狀三角形的幾何面積同步增大,計算不同r值對應的區域定位誤差均界,仿真結果如圖9所示。

圖9 幾何面積相等時極徑對錨節點形狀的影響

從圖9可知,不管是正三角形還是非正三角形,隨著錨節點幾何面積的增大,區域定位誤差逐漸變小。將正三角形和非正三角形進行對比發現,當幾何面積相等時,區域定位誤差亦相差不大。雖然非正三角形的幾何形態不如正三角形,但當其面積更大時,對應的誤差均界更小。因此,為了提高區域定位精度,相較于錨節點的幾何形狀,錨節點的幾何面積起到了更大的作用,因而在錨節點優化布設時,要優先考慮幾何面積的大小,使之覆蓋的待定位區域盡可能大。

3.2 算法設計

從上述仿真結果可知,錨節點幾何中心的位置、幾何形狀和幾何面積對區域定位誤差均界存在影響,且錨節點幾何中心與區域質心越接近、錨節點幾何形狀越接近均勻等角、錨節點幾何面積越大時,區域定位誤差均界越小。與幾何形狀相比,幾何面積的影響更大,因此,應該優先考慮錨節點的幾何面積。據此,設計啟發式的錨節點布設算法(Heuristic Optimized Anchor Deployment,HOAD)。

算法2HOAD算法

輸入給定一個凸區域A和待布設的錨節點個數M

輸出將夾角αmax對應的交點{b1,b2,…,bM}max作為M個錨節點的布設位置

步驟1選取區域A的質心c。

步驟2以點c為中心,均勻等角布設M個錨節點,第1個錨節點與水平正方向的夾角為α。相鄰錨節點的夾角等于2π/M,第i個錨節點與區域邊界的交點記為bi。

步驟3改變α的大小,使之在0～2π/M間變換。計算α=αk時,錨節點位置{b1,b2,…,bM}k構成的幾何面積Sk,從中選出最大面積Smax對應的角度,將其標記為αmax。

算法2的原理如圖10所示。

圖10 HOAD算法原理示意圖

3.3 算法性能分析

為評價HOAD算法的性能,與算法1窮盡式搜索方法進行定位精度和運行時間的比較。考慮在一個不規則凸區域內,布設3個錨節點的情形。仿真使用Matlab7.0,PC機的CPU為2.33 GHz雙核,內存為4 GB。假設節點間的測距誤差服從獨立同高斯分布N(0,σ2),其中σ=5 m,隨機布設的節點數N=1 000,搜索步長在20 m～40 m之間變化。

定位精度的評價指標為區域均方根定位誤差rRMS,定義如下:

圖11表示采用啟發式錨節點優化布設算法HOAD選取的錨節點位置,其中,實線表示區域邊界。采用搜索法時首先將區域均勻劃分為1 m×1 m的小格,然后使用不同的搜索步長在離散的小格內窮盡式搜索錨節點的最優位置,比較HOAD算法和搜索法的定位精度和計算復雜度,結果如圖12和圖13所示。

圖11 HOAD算法運行結果

圖12 2種算法定位精度對比

圖13 2種算法運行時間對比

從圖12、圖13看出,對于搜索法本身而言,隨著搜索步長的增大,算法運行時間下降很快。從圖13可以看出,HOAD的運行時間與搜索法存在3個～5個數量級的差異。綜合上述仿真分析可知,HOAD算法兼具定位精度高、計算開銷小的優勢,更能適用于實際應用場景。

4 結束語

在無線傳感器網絡中,本文基于定位誤差CRLB的推導,揭示了錨節點與待定位節點構成的幾何形狀對節點定位精度的影響。從提高區域平均定位精度和降低計算復雜度的角度研究了錨節點優化布設問題,提出了錨節點布設性能的評價標準,即區域定位誤差均界。采用仿真手段研究了錨節點質心、幾何形狀、幾何面積對區域定位性能的影響,據此提出了啟發式的錨節點優化布設算法HOAD,并與經典的搜索法進行了定位精度和計算復雜度的比較。仿真結果表明,HOAD算法的計算開銷明顯小于搜索法,因而實用價值更高。