一種面向不規則的無線電傳播模型下的節點定位算法

葛文庚, 陳 萍

(黃淮學院信息工程學院，河南駐馬店 463000)

0 引言

節點定位已成為無線傳感網絡(wireless sensor networks, WSNs)領域的焦點[1-4]，研究人員提出了測距定位算法、非測距定位算法等。測距定位算法雖然精度較高，但因為需要消耗高功率去維持未知節點與錨節點間的通信，而節點常采用小電池容量供電，應用局限性較大。非測距定位算法主要分為兩類：啟發式和分析式定位算法[5-7]。DV-Hop就是典型的啟發式算法，通過未知節點與錨節點間的跳數估計它們間的距離；分析式算法是基于節點具有圓形無線電傳播模型假設(radio propagation pattern, RPP)利用理論分析并推導錨節點與未知節點間的距離[6-7]。

文獻[8]提出的分布式求精算法，引用“磁極”思想，縮小定位誤差，但未考慮無線電傳播模型問題；文獻[9]提出基于遺傳優化DV-Hop定位算法，但該算法與文獻[8]存在同樣沒有考慮到無線電傳播模型對定位精度影響的問題。而在真實的傳輸環境中，常存在信號衰落、陰影以及干擾、各向異性的信號衰減等因素，導致節點的傳輸模型為非圓形RPP[10]。

為此，提出面向非圓形RPP的基于人工神經網絡的加權質心定位算法(artificial neural networks-based weighted centroid localization, ANNs-WCL)。ANNs-WCL算法充分考慮了因非圓形RPP問題，建立新的測距模型，然后再應用人工神經網絡修正測距，最后利用加權質心定位算法估計未知節點位置。仿真結果表明，提出的ANNs-WCL算法能夠有效地降低均方根誤差。

1 網絡模型以及問題表述

1.1 網絡模型

N個傳感節點隨機分布于二維網絡。考慮全球定位系統GPS的成本，僅部分節點配備了GPS，這些節點知曉自己的位置，為錨節點。而未裝備GPS的節點稱為未知節點。假定，未知節點的位置坐標為θ=[x,y]T，且θ∈R2。通過m個錨節點估計未知的位置。第k個錨節點的位置為β=[xk,yk]T，且k=1,2,…,m。所有節點的傳輸半徑為R。

1.2 問題描述

非圓形的RPP如圖1所示，傳感節點分布于面積為S2的區域。實線的圓圈表示圓狀的RPP，而虛線表示非圓形的RPP。

圖1 網絡模型

如果在定位算法中仍假定節點的傳輸范圍是圓形RPP，必然會引起測距誤差。因此，考慮利用ANNs系統訓練定位模型，修正測距值。

2 測距原理

(1)

式中ni,k表示節點i離錨節點k的跳數；hav表示平均每跳的距離。

對于高節點密度情況，常采用泊松有限理論估計hav，或者引用所有最短路徑的平均跳距代替hav。

(2)

假定節點傳輸范圍為圓形RPP，首先定義重疊區域A，如圖2所示。未知節點i以自己位置為圓心，以傳輸距離R為半徑形成的圓表示為D(i,R)。類似地，錨節點k也以自己的位置為圓心，以ni,kR為半徑的圓，即D(k,ni,kR)。因此，重疊的圓A的定義如式(3)所示。

圖2 重疊區域

A=D(k,ni,kR)∩D(i,R)

(3)

(4)

式中ψ(A)為di,k與A的關系函數；Amin和Amax分別表示A的最小值和最大值；fA(a)為概率密度函數。

利用地理特性和幾何知識，可得式(5)[11]：

(5)

式中Φ=ψ-1表示ψ的逆函數。由于Φ(di,k)是關于di,k的復雜函數，推導ψ(A)閉合表達式比較復雜。

此外, 假定A均勻分布于[Amin,Amax]。當di,k=ni,kR時，A取最大值Amax；而當di,k=(ni,k-1)R時，A取最小值Amin。因此，可得概率密度函數fA(a)的表達式為：

(6)

(7)

式中，Φ(1)是Φ的一階導數。

(8)

3 ANNs-WCL定位

ANNs-WCL定位算法主要由3個階段構成。第一階段，未知節點以多跳方式收集信息，然后再利用式(8)估計離錨節點間的距離；第二階段，利用ANNs修正測距，降低測距誤差；最后，利用加權質心定位算法，估計未知節點位置。

3.1 未知節點測距

在ANNS-WCL定位過程中，首先錨節點廣播數據包，由首部和數據兩部分構成。首部包含錨節點位置，而數據部分存有跳數值，且最初跳數值為1。

圖3 轉發數據包的流程

3.2 測距修正

圖4 測距修正過程

3.3 加權的質心定位算法

依據3.2節測距修正后，未知節點獲取距多個錨節點的距離。再從中選擇離自己最近的4個錨節點，即利用測距值最小的4個錨節點構成加權質心定位算法。

假定Aa，Ab，Ac，Ad分別為已選的4個錨節點，相應的，ra,rb,rc,rd分別表示離未知節點i的距離。首先，以錨節點為圓心，以離未知節點的距離為半徑畫圓，4個錨節點共形成4個圓，有4個交點，假定交點分別為O1,O2,O3,O4。然后，依據這4個交點構成4個不同的三角形，再計算這4個三角形的質心。傳統的質心定位算法就是將4個質心坐標的均值作為未知節點的位置。引用加權質心定位算法，即計算每個質心的權值，再依據這些權值，估計未知節點的位置。

以Aa,Ab,Ac這3個圓為例，其交點分別為O1,O2,O3。利用3個圓的半徑ra，rb，rc以及3個錨節點Aa，Ab，Ac的坐標(Xa,Ya)，(Xb,Yb)，(Xc,Yc)，可計算3個交點坐標。可利用式(9)所示的方程組中任意兩個等式求解交點O1的坐標(XO1,YO1)：

(9)

同理可計算其他交點的坐標。計算交點O1,O2,O3坐標后，便可計算這由3個交點所構成的三角形的質心E1坐標(X1,Y1)：

(10)

圖5 加權質心定位算法

(11)

4 性能仿真

4.1 仿真環境

利用MATLAB7.1軟件建立仿真平臺，節點隨機分布于100 m×100 m區域。節點傳輸半徑為18 m，錨節點數為20。此外，利用文獻[10]非圓形的RPP模型，并引用變量不圓形度DDOI。

為了更好地分析ANNs-WCL定位算法的性能，選用同類算法DV-Hop[5]、LAEP[6]和MLPNN-CGFR[12]進行比較。同時，引用均方根誤差ERMS作為性能指標：

(12)

4.2 定位的ERMS

首先考查ERMS隨節點數N和DDOI的變化情況，實驗數據如圖6所示，其中圖6(a)表示在DDOI=0.06時，節點數N從200變化至800時，ERMS的變化數據；圖6(b)表示在N=300時，節點數DDOI從0變化至0.15時，ERMS的變化數據。

圖6 定位的歸一化的均方根誤差

從圖6(a)可知，在DDOI=0.06時，ERMS隨節點數的增加而下降，節點數增加，獲取的網絡拓撲信息越多，越有利于定位精度的上升。與DV-Hop[5]、LAEP[6]和MLPNN-CGFR[10]相比，提出的ANNs-WCL算法的ERMS得到有效下降。當N=400時，ANNs-WCL算法的ERMS為0.4 m，而LAEP、DV-hop和MLPNN-CGFR的ERMS分別高達1.31 m，1.1 m，0.98 m。

從圖6(b)可知，在N=300時，ERMS隨DDOI增加而上升。原因在于：DDOI越高，節點的RPP模型越偏離圓形，測距誤差越大，最終，定位精度就下降。與圖6(a)類似，與DV-Hop、LAEP和MLPNN-CGFR相比，ANNs-WCL的ERMS仍是最低的。這些數據表明，ANNs-WCL算法能夠在真實環境中獲取高的定位精度。

4.3 ERMS的CDF曲線

N=300，DDOI=0.06四個算法ERMS的累積分布函數FCDF曲線如圖7，且從圖7可知，提出的ANNs-WCL定位算法有99%節點獲取同一個定位精度，而MLPNN-CGFR只有61%，DV-Hop只有43%，而LAEP僅為30%。這些數據表明，在存在異構信號衰減的環境下，ANNs-WCL定位性能優于同類算法。

圖7 CDF曲線

5 總結

針對真實環境中的非圓形RPP問題，提出面向非圓形RPP的基于人工神經網絡的加權質心定位算法 ANNs-WCL。ANNs-WCL算法先推理測距表達式，然后利用ANNs修正測距值，最后，利用加權質心定位算法估計未知節點位置。仿真結果表明，提出的ANNs-WCL算法能夠有效地降低均方根誤差，提高了定位精度。