基于Steffensen迭代和模糊信息的節點定位算法

齊小文

(鄭州工程技術學院信息工程學院,鄭州 450044)

無線傳感器網絡[1]WSN(Wireless Sensor Network)是集無線傳感技術、網絡技術、通信技術于一體的新興網絡。在無線傳感器網絡中,傳感節點的位置確定是進行其他數據采集與發送的基礎。節點的定位算法已成為無線傳感網絡研究的重點和熱點[2-3]。為了提高節點的定位精度,學者們在經典定位算法的基礎上做了進一步的改進。文獻[4]在加權質心定位算法和RSSI測距模型分析的基礎,提出了一種基于自適應迭代搜索的三維質心定位算法;文獻[5]在直線模糊信息的基礎上,提出了一種基于簡單Delaunay三角剖分的模糊信息定位算法,不僅提高了節點定位精度還降低了網絡能耗;文獻[6]引入鄰域思想,將網絡節點與周圍節點按跳數劃分為不同階鄰域,提出一種基于鄰域旋跳迭代機制的節點定位算法;文獻[7]運用海倫公式的四面體體積公式,并結合二維LLSE算法,提出一種低復雜度和低成本的三維定位算法;文獻[8]提出了近似投影校正的無線傳感器網絡非測距三維定位算法;文獻[9]提出了一種基于階次序列和近似三角形內點法的混合定位算法。文獻[10]針對TOF測距提出了一種應用于稀疏網絡的定位算法,算法通過引入泰勒級數展開的最小二乘法計算節點位置,根據無效節點的不同情況實現節點的定位。文獻[11]提出了一種基于方位角的區域定位方法(3D-ADAL)。文獻[12]通過卡爾曼濾波和線性插值法對隨機誤差進行補償以獲得較精確的定位節點并與參考節點進行距離估計,并采用改進的三角質心定位進行測試,使傳統加權質心定位精度有了明顯提高算法利用定向天線確定的旋轉角和傾斜角實現節點的定位。不同定位算法采用不同的定位策略,也就造成了不同的定位精度和復雜度。

實際的無線網絡中,網絡拓撲復雜多變,節點能耗、信息傳送與感知能力有限,種種因素會使無線網絡定位節點帶有隨機性和模糊性。而模糊定位法則是通過視線交叉測得的方向角、俯仰角來定位節點[13-14]。本文在借鑒前人研究成果的基礎上,提出了一種基于Steffensen迭代和模糊信息的節點定位算法。算法在節點模糊信息定位的基礎上引入Steffensen迭代,通過迭代計算,修正第1階段粗略定位的節點位置,實現精確定位。

圖1 傳感器模糊觀測幾何定位

1 相關定義

1.1 模糊信息

(1)

(2)

1.2 Steffensen迭代算法

對于非線性方程f(x)=0,可劃成等價的方程:

x=φ(x)

(3)

選取初始近似值x0構造迭代次序,迭代公式如下:

xk+1=φ(xk),k=0,1,2,…

(4)

式(4)稱為不動點迭代,其中φ(x)為迭代函數。

Steffensen迭代法是一種改進不動點迭代的加速迭代法,能有效的求解非線性方程的根。不僅具有二階收斂速度還具有較高的計算精度[15]。其迭代函數為:

(5)

(6)

Steffensen 加速迭代算法如下:

步驟1 取初始點x0,設最大迭代次數為Num、迭代精度為ε,置k=0;

步驟3 若|xk+1-xk|<ε,則停止計算;

步驟4 若k=Num,則停止計算;否則,置k=k+1,轉到步驟2。

1.3 有效錨節點

在無線傳感器網絡中,已知位置節點稱為錨節點,位置不明節點為未知節點。未知節點的定位一般會基于位置確定的錨節點,但是由于節點間通信易受干擾,在進行未知節點定位前,需要對錨節點的有效性進行確定。初始錨節點的位置會通過北斗或GPS系統獲得,無線網絡初始化各節點的位置分布示意圖如圖2所示。

圖2 無線網絡節點初始位置示意

圖2中星型狀的代表未知節點,圓圈狀的代表錨節點,兩個錨節點Bi(xi,yi,zi)、Bj(xj,yj,zj)之間的距離為:

(7)

兩個錨節點Bi(xi,yi,zi)、Bj(xj,yj,zj)之間的路徑損耗指數L(Bi,Bj),根據文獻[5]路徑耗損公式可得:

RSSI(Bi,Bj)=Pt-PL(d0)-10×L(Bi,Bj)×
lg[d(Bi,Bj)/d0]-X0

(8)

(9)

Pt表示發射功率,PL(d0)表示在d0處的經驗路徑損耗,d0表示天線遠場參考距離。對于每一個錨節點Bi,在其通信半徑范圍內的路徑損耗指數L(Bi):

(10)

定義錨節點局部信號路徑損耗的閾值為τ,在進行未知節點定位時,首先要對錨節點的有效性進行檢驗,即比較錨節點Bi的路徑損耗指數L(Bi)與L(Bi,Bj)的差值與閾值τ的大小,當差值小于閾值時,錨節點Bi是無效的,其中錨節點Bj是有效錨節點:

|n(Bi)-n(Bi,Bj)|<τ

(11)

2 本文節點定位算法

2.1 基于連通度和剩余能量選擇移動錨節點

為了提高節點定位速度,本文需要在網絡中設置一個移動錨節點,通過移動錨節點在網絡中的運動軌跡,輔助其他錨節點對未知節點定位,文章利用移動錨節點的連通度和剩余能量來確定移動錨節點,圖3是移動錨節點運動軌跡示意圖。

圖3 移動錨節點運動軌跡

在定位前,選擇一個錨節點作為移動錨節點。設某一節點Bi的鄰居節點數為Num(Bi),節點總數n,節點Bi與其他鄰居節點間的平均連接性能為:

(12)

錨節點與其他鄰居錨節點間的連通性能和能量剩余情況是選擇移動錨節點必須考慮的兩點,定義無線網絡內某一節點Bi選票值為vote(Bi),節點Bi的剩余能量為E(Bi),初始能量為Es,文章采用與文獻[16]相同的無線節點能耗模型,網絡內節點的最好平均連通度為f(max),則可以得到vote(Bi):

(13)

其中μ和η分別表示連接度和剩余能量的影響系數。利用文獻[17]無線網絡能耗模型求解點Bi的剩余能量為E(Bi)。對于選中的移動錨節點,在每輪循環開始前,都要對移動錨節點的位置信息進行更新:

(14)

(15)

2.2 基于Steffensen迭代模型求解節點位置

設空間內隨機部署n個節點,其中錨節點個數為m(m

根據已知有效移動錨節點的坐標信息,建立如下模型:

(16)

由此,定位問題轉化為求式(16)的最小值,即通過Steffensen迭代運算求得當式(16)取得最小值時的坐標,以此作為第2次定位后的結果。

(17)

要使式(17)取得最小值時,所需的必要條件為:

(18)

對式(18)的各等式進行求解,其中可得:

(19)

(20)

(21)

令Δi為:

(22)

(23)

(24)

(25)

同理,對變量yi進行迭代,可得:

(26)

(27)

(28)

同理,對變量zi進行迭代,可得:

(29)

(30)

(31)

綜合以上內容,基于Steffensen迭代和模糊信息的三維節點定位算法步驟如下:

步驟1 初始化無線傳感網絡,設定路徑損耗閾值τ,迭代最大次數N、迭代精度ε等參數;

步驟2 通過式(7)～式(11)尋找有效錨節點;

步驟3 通過式(12)和式(13)篩選移動錨節點;

步驟4 利用式(1)和式(2)運用模糊信息定位實現節點粗定位(xi,yi,zi);

步驟5 判斷迭代次數是否大于T,迭代精度是否小于ε,若都不是,執行步驟6;否則執行步驟7;

步驟6 根據式(17)～式(31)對步驟4中的粗定位坐標(xi,yi,zi)進行Steffensen迭代求精;

步驟7 定位坐標迭代求精結束,輸出精準定位坐標,并根據式(14)和式(15)對無效錨節點位置更新,循環下一輪。

3 網絡性能對比分析

3.1 網絡延時

文章將對比分析文獻[10]和文獻[11]的網絡延時,無線網絡延時主要包括發送單位比特數據延時ttran、接收單位比特數據的延時trec、位置定位延時tloca、模糊信息計算延時tvag、位置更新延時tupdata,則本文、文獻[10]、文獻[11]網絡總延時為Ttext、Ttof、T3D-ADAL。

(32)

(33)

(34)

式(33)減去式(32)可得:

(35)

式(34)減去式(32)可得:

T3D-ADAL-Ttext=(M-3)·T·(N-M)tloca

(36)

對于式(35),在無線網絡中節點的個數肯定大于3即n>3,并且錨節點的個數也會遠遠小于未知節點即N-M>M,定位循環T>2,而tloca>tvag,R≥2,所以Ttof-Ttext>0。本文算法的延時小于文獻[10]。

對于式(36),在無線網絡中錨節點的個數肯定大于3即M>3,并且錨節點的個數也會遠遠小于未知節點即N-M>M,所以T3D-ADAL-Ttext>0。本文算法的延時小于文獻[11],綜上可知,本文算法的延時少于文獻[10]和文獻[11]。

3.2 能耗分析

無線網絡能耗主要包括發送單位比特數據能耗etran、接收單位比特數據的能耗erec、位置定位能耗eloca、模糊信息計算能耗evag、位置更新能耗eupdata,則本文、文獻[10]、文獻[11]網絡總能耗為Etext、Etof、E3D-ADAL。

(37)

(38)

(39)

式(38)減去式(37)可得:

(40)

式(39)減去式(37)可得:

E3D-ADAL-Etext=(M-3)·T·(N-M)eloca

(41)

對于式(40),在無線網絡中節點的個數肯定大于3即n>3,并且錨節點的個數也會遠遠小于未知節點即N-M>M,定位循環T>2,而eloca>evag,R≥2,所以Etof-Etext>0。本文算法的能耗小于文獻[10]。

對于式(41),在無線網絡中錨節點的個數肯定大于3即M>3,并且錨節點的個數也會遠遠小于未知節點即N-M>M,所以E3D-ADAL-Etext>0。本文算法的嫩好小于文獻[11],綜上可知,本文算法的能耗少于文獻[10-11]。

4 實驗仿真與分析

為了檢驗算法的性能,本文在MATLAB平臺上進行仿真和比較分析。設節點分布在500 m×500 m×500 m的區域內,節點的坐標隨機產生,總數為150,節點初始能量為1 500 J,節點的通信半徑為10 m,節點感知半徑為8 m,發送節點發送數據k=5 byte,位置更新數據包長度l=1 byte,模糊定位精度ε=0.1,連接度和剩余能量影響系數μ=0.6,η=0.4,對3種算法運行100次并求各自的平均值,分析比較各算法的性能。本文定位誤差率通過式(42)計算:

(42)

4.1 定位算法節點變化

圖4為本文定位算法過程中節點變化的比較:在圖4(a)中可見未知節點、普通錨節點和一個移動錨節點,此時為無線網絡的初始分布,節點的實際坐標為(162,185,148);圖4(b)為通過模糊信息粗定位后的無線網絡節點分布,相比圖4(a),在圖4(a)中增加了已定位節點;圖4(c)是在圖4(b)基礎上迭代求精后的節點分布,圖4(c)和圖4(b)對比可知,部分已定位節點位置發生變化,由此可以看出,經過本文的迭代求精,可以一定程度上提高節點的定位精度,降低誤差率。

圖4 本文算法定位過程中節點位置變化比較

圖5 本文算法誤差率比較

4.2 算法定位誤差率

從圖5可以看出隨著節點通信半徑的增大,本文定位算法誤差率降低,這是由于通信半徑的增大,加大節點間的連通,提高了節點的利用率,對同一節點可定位的錨節點個數增多,增加了迭代求精的次數,從而提高了定位精度;在一定的通信半徑上,隨著錨節點移動速度的加快,定位誤差率也在下降,且當錨節點移動速度增加到一定程度時,誤差率不再大幅度降低,這是因為當節點移動速度和迭代求精速度差距太大,使得定位誤差率降低較慢。在定位過程中,在保證定位誤差率的同時,為了節省網絡能量,錨節點移動速度不宜太大。

圖6 3種定位算法誤差率比較

從圖6可以看出隨著算法執行次數的增加,文獻[10]、文獻[11]和本文3種算法的定位誤差率呈下降趨勢,這是因為隨著執行次數的增加,越來越多的未知節點被定位,已定位節點加入到錨節點隊列中,錨節點的位置更新提高了定位精度,而本文算法采用模糊信息定位,利用Steffensen迭代求精,與文獻[10]、文獻[11]的質心定位和加權定位算法相比,精度更高。

4.3 網絡中已定位節點個數比較

由圖7為錨節點個數與已定位節點個數的關系曲線。從圖7(a)中M=20到圖(d)M=60,文獻[10]、文獻[11]和本文3種算法已定位節點的個數總體呈增加趨勢,但各有差異。3D-ADAL算法中已定位節點個數增加緩慢且最低,改進TOF算法中已定位節點數增加適中。本文算法已定位節點數增值幅度最大。這是因為本文算法中模糊信息定位增大了錨節點的可利用率,通過靜態錨節點輔助移動錨節點完成節點定位,利用節點的動態性提高了節點定位速度。定位后的迭代求提高了定位精度,因此本文算法相比其他兩種算法不僅定位速度較快而且定位節點數量多。

圖7 3種算法中已定位節點個數比較

4.4 算法消耗能量比較

從圖8可以看出,3種算法隨著節點通信半徑的增大,能耗逐漸降低,本文算法能耗降低幅度最大且能耗最低,3D-ADAL算法的能耗最大且降低最慢,改進TOF算法的能耗居中。本文算法根據連通度和剩余能量選擇移動錨節點,雖使得局部能耗增加,但靜態錨節點能耗相比其他算法中錨節點能耗低,并且利用模糊信息定位,利用迭代求精提高定位精度,不僅降低了定位算法對初始錨節點個數要求,還降低了網絡能耗。

圖8 3種定位算法中消耗的能量比較

5 總結

針對無線傳感器網絡節點定位算法定位精度低的問題,本文在借鑒前人研究的基礎上提出了一種基于Steffensen迭代和模糊信息的節點定位算法,該算法將錨節點分為移動錨節點和混合錨節點,通過空間中節點之間的模糊信息實現粗定位,然后通過Steffensen迭代求精提高節點的定位精度。仿真對比驗證,本文算法具有較高的定位精度,且定位速度較快,能耗較低。

[1] Massimo Vecchio,Roberto Lopez-Valcarce,Francesco Marcelloni. A Two-Objective Evolutionary Approach Based on Topological Constraints for Node Localization in Wireless Sensor Networks[J]. Applied Soft Computing,2012,12(7):1891-1901.

[2] Vijay K Chaurasiya,Neeraj Jain,Nandi G C. A Novel Distance Estimation Approach for 3D Localization in Wireless Sensor Network Using Multi-Dimensional Scaling[J]. Information Fusion,2014,15:5-18.

[3] Dimitrios Zorbas,Tahiry Razafindralambo. Prolonging Network Lifetime Under Probabilistic Target Coverage in Wireless Mobile Sensor Networks[J]. Computer Communications,2013:1039-1053.

[4] 鄭德忠,李雪,袁鵬,等. 基于自適應迭代搜索的三維質心定位算法[J]. 計量學報,2017,38(3):356-362.

[5] 黨小超,李芬芳,郝占軍. Delaunay三角剖分的節點模糊信息三維定位方法[J]. 計算機工程與應用,2016,52(23):115-122.

[6] 曹世華,王琦暉,王李東. 基于鄰域旋跳迭代機制的無線傳感器網絡節點定位[J]. 計算機工程,2016,42(7):94-100.

[7] 黃慶宇,劉新華. 基于線性最小二乘估計的傳感網節點三維測距定位算法[J]. 計算機工程,2016,42(12):11-16.

[8] 胡中棟,謝金偉. 基于近似投影校正的無線傳感器網絡三維定位機制[J]. 傳感技術學報,2014,27(11):1573-1578.

[9] 韓睿松,楊維. 一種基于SBL和APIT的混合定位算法[J]. 傳感技術學報,2014,27(8):1094-1099.

[10] 魯旭陽,張效義,劉廣怡. 稀疏無線傳感器網絡的節點自定位算法[J]. 計算機工程,2012,38(18):83-86.

[11] Guerrero E,Wang Hao,Alvarez J,et al. A Three-Dimensional Range-Free Localization Algorithm Based on Mobile Beacons for Wireless Sensor Networks[J]. Computer-Aided Design,Drafting and Manufacturing,2010,20(1):83-92.

[12] 趙大龍,白鳳山,董思宇,等. 一種基于卡爾曼和線性插值濾波的改進三角質心定位算法[J]. 傳感技術學報,2015,28(7):1086-1090.

[13] Raju Dutta,Sajal Saha,Asish K. Mukhopadhyay. Tracking Hetergeneous Dynamic Sensor Node using Fuzzy Logic to Prolong System Lifetime in WSN[J]. Procedia Engineering,2012:522-527.

[14] Lü Zhen,Zhang Ying. Hybrid Optimization in WSN Node Localization Algorithm[J]. Computer Systems and Applications,2014,23(7):121-125.

[15] Ezquerro J A,Hernndez-Verón M A. Increasing the Applicability of Steffensen’s Method?[J]. Journal of Mathematical Analysis and Applications,2014,418(2):1062-1073.

[16] Wang Haobo,Ren Weizheng,Cui Yansong. An Adaptive WSN Node Tracking Algorithm Based on Rough-Set Neural Network[J]. Procedia Engineering,2012:1750-1754.

[17] 傅菊平,齊小剛. 基于剩余能量和節點度的無線傳感器網絡分簇算法[J]. 計算機應用研究,2011,28(1):250-253.

[18] 張志東,孫雨耕,劉洋,等. 無線傳感網絡模型[J]. 天津大學學報,2007,40(9):1029-1035.