無線傳感器網絡節點的三維定位技術

高瑞娟，陳桂芬，徐 赫

(長春理工大學 電子信息工程學院，吉林 長春 130022)

0 引 言

傳感器節點包括靜止節點和移動節點，這些節點通過自組織的方式構成無線傳感器網絡(wireless sensor networks，WSN)[1,2]。基于無線傳感器的研究主要有節點定位技術、網絡覆蓋技術和路由協議技術等方面，本文將對眾多技術中的定位技術進行研究。

隨著當今時代技術的發展，許多傳感器技術被應用于大型農業中，例如無線溫度傳感器、無線光照傳感器等。然而在規模較大、環境惡劣、地形較復雜的農田中部署的傳感器一般是通過飛機隨機拋灑的，這就意味著對隨機拋灑的傳感器節點進行準確定位成為獲取農田可靠溫度、光照、氣體等信息的前提。目前，有許多學者對DV-Hop定位算法進行了改進[3-5]，但這些僅適用于二維空間。由于實際環境的復雜性，二維空間的定位算法已經滿足不了定位精度的需求，需上升到三維空間進行研究。

目前為止，三維空間中的定位算法有Landscape-3D(landscape three-dimensional)算法[6]、APIS(approximate point in sphere)算法[7]、3D-DV-Hop (three-dimensional distance vector-hop)算法[8]、Constrained-3D(constrained three-dimensional)算法[9]等。其中，眾多算法中的3D-DV-Hop定位算法計算相對簡單，所以有許多學者將其進行改進[10,11]。但這些改進算法并沒有考慮錨節點共面問題，因此本文將對節點定位中存在的共面問題進行深刻研究，提出一種適用于三維空間中的錨節點組按規定路徑移動的非測距定位算法。

1 3D-DV-Hop定位算法介紹

三維空間中DV-Hop定位原理類似于二維空間中DV-Hop定位原理，具體介紹如下：

(1)獲取最小跳數

大量節點在監測區域內被隨機部署后，錨節點通過向周圍節點發送自身包含ID號、位置信息以及跳數hi的數據包信息[12]。其中，跳數hi開始值記為0。未知節點不斷接收來自周圍錨節點的數據包，若接收到的數據包中的跳數小于已經保存的最小跳數，則拋棄已經保存的跳數，同時把當前跳數進行加一，并將自身的信息傳送到網絡中。

(2)估算平均跳距

用錨節點間坐標之差除以錨節點間的跳數求得檢測區域內所有錨節點間的平均跳距HopSizeij為

(1)

式中：(xi,yi,zi)、(xj,yj,zj)分別為錨節點i、j的位置坐標，hij為錨節點i和錨節點j之間的跳數。進一步可得出未知節點與錨節點i之間距離di為

di=hij×HopSizeij,(i≠j)

(2)

(3)計算未知節點位置

最后，經過以上計算后，若未知節點附近的鄰居錨節點數等于4個，傾向于選擇四邊測量法獲得未知節點的坐標。若未知節點附近的鄰居錨節點數超過4個，傾向于選擇極大似然估計法獲得未知節點的坐標。

2 算法改進思想

本文的改進算法具體介紹如下：

2.1 分層式錨節點組移動路徑

在三維空間中，節點部署雜亂無序。為了定位計算容易，將三維空間分層為無數個二維空間進行處理。三維空間的分層式劃分如圖1所示。

監測區域經過分層處理后，在監測區域邊界處部署一組移動錨節點組，并使錨節點組按一定的靜態移動路徑移動。其中，移動錨節點組的相對位置關系如圖2所示。

圖1 三維空間的分層式劃分

圖2 移動錨節點組的相對位置關系

接下來，讓錨節點組在監測區域內按規定的移動路徑開始移動，如圖3所示。

圖3 錨節點組移動路徑

2.2 計算錨節點共面度值

為了解決共面現象導致未知節點不能確定的問題，必須要采取一些度量標準衡量四面體的質量。現有的衡量四面體質量的標準有系數γ、半徑比ρ、最小立體角θ等，考慮到衡量四面體網格質量標準方法的準確性幾乎等價，本文采用最小立體角θ的測量方式測量共面度，具體介紹如下：

在4個錨節點構成的四面體中，4個夾角分別用θ1、θ2、θ3、θ4表示，具體計算如式(3)所示

(3)

式中：V表示四面體的體積，lij表示錨節點i、j之間的距離。將θ1、θ2、θ3、θ4這4個角度進行對比，取其中的最小角度θ作為衡量四面體的平面度值，如式(4)所示

θ=MIN(θ1、θ2、θ3、θ4)

(4)

(5)

2.3 虛擬錨節點組平均跳距

3D-DV-Hop定位算法是用平均跳距等于錨節點間距離除以錨節點間跳數。但在本文中提出的錨節點組按規定路徑移動的三維定位算法中，錨節點組是按靜態移動路徑SCAN移動整個三維區域，遍移動后的區域中不存在錨節點，且未知節點所獲得信息均來源于虛擬錨節點并非錨節點。因此，無法直接計算錨節點間的平均跳距。

接下來，用一種計算虛擬錨節點組間的距離方法解決移動路徑中存在的問題，即用篩選出來的r組虛擬錨節點組來估算平均每跳距離，如式(6)所示

(6)

2.4 未知節點位置重新定位

最后，將節點之間的距離進行共面度加權處理，如下式(7)所示

(7)

式中：(x,y,z)表示待定位節點坐標，(xn,yn,zn)表示虛擬錨節點組的位置，wi表示平面度加權值，di(i=1,2,…,n)表示節點間的距離。

將式(7)化簡后可得

AX=b

(8)

其中

(9)

(10)

(11)

最終求得未知節點的坐標為

X=(ATA)-1ATb

(12)

3 仿 真

為驗證提出的移動錨節點組按規定移動路徑移動的定位算法能夠有效降低節點定位誤差，本文對算法進行了仿真，并與3D-DV-Hop算法以及其它的改進算法進行比較。仿真中，平均定位誤差的衡量標準如式(13)所示

(13)

式中：待定位未知節點的實際坐標用(xi,yi,zi)表示，待定位未知節點的所求坐標用(xj,yj,zj)表示，監測區域內待定位未知節點的數量用N表示，監測區域內節點的通信范圍半徑用R表示。相關的仿真參數見表1。

表1 仿真參數

將通信半徑R為40 m的500個節點隨機拋灑在100 m*100 m*100 m的監測區域內，節點隨機拋灑生成圖如圖4所示。其中，錨節點為100個，符號為“*”，未知節點400個，符號為“°”。

為了仿真結果的可靠性，對節點隨機分布進行500次仿真，仿真的相對平均誤差如圖5所示。由500次仿真結果可知，除了個別次仿真外，改進算法的定位誤差均在0.21 m上下浮動，定位誤差較穩定。

圖4 未知節點定位誤差

圖5 loop次相對平均誤差

圖6為錨節點比例對平均定位誤差的影響仿真圖。仿真中，設監測區域為邊長100 m的三維空間，在監測區域內隨機分布500個節點，且節點通信半徑固定為40 m，改變網絡中錨節點的比例，從10%逐步增加到40%，同時對本文算法、傳統算法、文獻[10]算法以及文獻[11]算法進行仿真對比。

圖6 錨節點比例對平均定位誤差的影響仿真

根據圖6中的數據線變化能夠看到，當錨節點數達到總節點數的20%以上時，節點定位誤差變化開始緩慢。4種算法平均定位誤差隨著錨節點的比例增大均有所下降，本文算法的平均定位誤差相對于傳統定位算法、文獻[10]算法、文獻[11]算法分別降低了29.76%、10.22%、4.31%。

圖7為節點通信半徑對平均定位誤差的影響仿真圖。網絡中總節點為500，錨節點比例為20%，讓節點通信半徑逐漸遞增，對算法進行仿真。

圖7 節點通信半徑對平均定位誤差的影響仿真

從圖7中的數據線變化可以明顯看出當節點通信半徑達到40 m時，節點定位誤差的變化開始平緩。4種算法的平均定位誤差隨著通信半徑的增大均有明顯下降，本文算法的平均定位誤差相對于傳統定位算法、文獻[10]算法、文獻[11]算法分別降低了37.26%、13.85%、8.96%。

圖8為總節點個數對平均定位誤差的影響仿真圖。在監測區域中分別部署100個、200個、300個、400個、500個節點，網絡中錨節點占比固定為總節點的20%，節點通信半徑固定為40 m，對算法進行仿真。

圖8 總節點個數對平均定位誤差的影響仿真

從圖8中可以看出，傳統定位算法、文獻[10]算法、文獻[11]算法以及本文提出的定位算法隨著總節點個數的增加，平均定位誤差都有所下降。在同等總節點個數情況下，本文提出的定位算法的平均定位誤差相對于傳統定位算法、文獻[10]算法、文獻[11]算法分別降低了36.25%、12.77%、16.83%。

4 結束語

當三維空間中錨節點組出現共面現象時，將會導致未知節點無法定位。針對這個現象，提出一種適用于三維空間中的錨節點組按規定路徑移動的非測距定位算法。通過對監測區域進行分層式錨節點組移動路徑規劃，計算虛擬錨節點組的共面度值以及用虛擬錨節點組計算平均跳距，最終對節點間距離進行共面度加權計算出待定位節點位置。實驗結果表明本文提出的算法有效的避免了錨節點共面現象，進而提高了未知節點的定位精度。接下來的工作是針對算法中存在的共線問題進行研究。