無線傳感器網絡節點定位算法優化研究

段林妍

四川省計算機研究院,四川 成都 610041

0 引言

無線傳感器網絡是一種分布式傳感網絡,它是可感知和檢查外部世界的傳感器。無線傳感器網絡中的傳感器通過無線方式通信,因此網絡設置靈活,設備位置可隨時更改,還可與互聯網進行有線或無線方式的連接,形成一個多跳自組織網絡。

無線傳感器網絡中需要收集各網絡節點傳感器采集的數據,實現數據匯總和交互,因此,需要對節點的位置進行準確的描述,才能確保采集數據的準確性。

節點定位計算是無線傳感器網絡中的核心問題。現有的定位算法分為基于距離的定位算法和距離無關的定位算法[1]。基于距離的定位算法適用于定位精度要求較高的應用場景,對傳感器節點的硬件要求較高。距離無關的定位算法適用于定位精度要求不高或者硬件功耗低等場景,常用的算法有DV-Hop定位算法、質心定位算法、APIT定位算法等[2]。

目前實際應用較多節點定位算法是DV-Hop算法。DV-Hop定位算法的核心思路是基于距離矢量路由計算,通過節點之間的跳數和平均跳距的乘積來表示節點之間的距離[3]。DV-Hop定位算法是目前應用最廣泛的非測距定位算法,該算法在各向同性網絡環境中可獲得較好的定位效果,但在節點隨機分布的網絡環境中,由于平均跳距計算誤差大、用直線路徑代替實際路徑等原因,存在較大的定位誤差[4]。

本文針對DV-Hop算法中存在的不足,提出了改進優化思路和相應的算法,后續算例驗證了改進算法的有效性。

1 現有節點定位算法存在的不足

現有DV-Hop算法的定位思路是采用傳統網絡中的距離向量路由機制,DV-Hop算法的整個定位過程分為3個部分。

1)計算未知節點到錨節點之間的最小跳數,使用距離矢量交換協議,使網絡中所有節點均獲得距各錨節點的最小跳數。

2)計算錨節點與未知節點之間的距離。單個錨節點依據來自其他錨節點的位置坐標以及與其自身之間的最小跳數,可計算出其平均每跳距離,即平均跳距。錨節點計算完自身的平均每跳距離后,利用洪泛法將其廣播出去,網絡中所有節點只接收距離自己最近錨節點的平均跳距,未知節點收到距離自身最近的錨節點的平均跳距后,將其乘以該錨節點到未知節點的最小跳數,即為未知節點到該錨節點的距離。

在DV-Hop算法中,采用錨節點與未知節點之間的最小平均跳距與跳數乘積進行計算,容易產生定位誤差,現有的算法主要存在以下不足。

傳統的DV-Hop算法中未知節點只將最近的錨節點的平均跳距值作為其平均跳距計算的估計值,而實際情況中,未知節點與多個信標節點間跳數值為1跳時,節點之間的實際距離不一致,傳統節點定位算法將節點間估算距離均是按照1跳來處理,從而造成估算誤差。由于無線傳感器網絡部署時因為地理因素會存在空洞現象,造成節點間最短通信距離發生曲折變化。因此,使用DV-Hop算法會帶來較大的距離誤差,需要根據實際場景進行調整,現有算法適應能力較弱。

2 DV-Hop算法的優化

2.1 優化思路

目前,DV-Hop定位算法的改進思路主要是通過對節點通信距離進行取樣,例如錨節點和未知節點的通信距離為R,可將節點通信距離取1/4、1/2、3/4計算跳數,以提高跳數計數的精度。文獻[5]中提出了一種基于雙通信半徑的DV-hop算法,未知節點使用通信半徑R,而信標節點使用R和0.5R進行通信,仿真結果表明其定位精度有所提升,但這種改進算法需要依賴實際工程經驗才能確定通信半徑設置是否合理,能夠適配的應用場景較為有限。

本文改進思路是在得到全網平均每跳距離的基礎上,通過分析任意錨節點的平均每跳距離誤差,修正全網平均每跳距離,使其能接近真實值,從而降低誤差,提高精度。

一般來說,錨節點的平均每跳距離誤差定義為[6]：

(1)

由式(1)可知,可從2個方面減少平均每跳距離誤差,一是降低各錨節點計算本節點的平均每跳跳距誤差,修正全網的平均每跳跳距值;二是提升節點之間的跳數hij,可將節點通信半徑多次取樣,以增加節點之間的跳數,逼近1跳的真實距離。

由于未設置準入門檻，“糧食銀行”運營主體可能會沖破道德的約束，過分追求經濟利益導致企業無法正常運轉或破產，出現“跑路”風險，損害農民利益。江西省社科院農村經濟研究所副所長尹小健表示，農民將糧食存入“糧食銀行”，存在一定風險，糧食行情下行時，經營者的資金鏈一旦斷裂或遭遇不可抗的自然災害，無力支付利息或提供農資時，“跑路”就不足為奇。

根據現有文獻可知,經過大量統計分析,無線傳感器分布呈泊松分布[6]。根據參數估計理論,使用均方差比方差更有效[7]。在概率論中,方差是衡量隨機變量或對一組數據離散程度的度量[8]。均方誤差是各數據偏離真實值差值的平方和的平均數,也就是誤差平方和的平均數[9]。

(2)

(3)

式中：dij為錨節點i和j之間的真實距離;ri為錨節點i的平均每跳距離估算值;hij為錨節點i和j之間的跳數;N為總的節點數。

整個無線傳感器網絡的整體誤差為：

(4)

用最小二乘法求解,可得修正過后的平均每跳距離估算值為：

(5)

2.2 改進算法的工作流程

改進算法的工作流程步驟如下。①無線傳感器網絡初始化。②使用典型的距離矢量交換協議,錨節點在無線傳感器網絡中廣播包含自身位置信息的數據包,使網絡中所有節點獲得錨節點之間的跳數。③錨節點i利用式(5)計算修正后的平均每跳距離,并廣播帶有跳數和平均跳距的分組,其他錨節點均需要廣播相應的分組。④利用極大似然估計法估算其坐標,程序結束。

3 仿真分析

由于DV-Hop定位算法受網絡拓撲結構的影響較大,對于不同的網絡結構,定位算法的精度會發生變化。因此,為驗證本文提出的優化DV-Hop定位算法的普適性,本文針對不同通信半徑和錨節點情況分別多次進行了網絡仿真試驗。

無線傳感器網絡區域大小為300 m×300 m,隨機布設150個節點,經過多次試驗后,取平均值作為仿真的結果。使用MATLAB仿真經典DV-Hop定位算法與本文提出的改進DV-Hop定位算法的性能指標,并進行對比分析。

圖1為通信半徑為10 m時,本文提出的改進定位算法與傳統DV-Hop算法在相對定位誤差與錨節點數量之間的關系圖。

圖1 通信半徑為10 m時的相對定位誤差比較

圖2為通信半徑增大到50 m時,本文提出的改進定位算法與傳統DV-Hop算法在相對定位誤差與錨節點數量之間的關系圖。

圖2 通信半徑為50 m時的相對定位誤差比較

從圖1和圖2變化可知：一是在錨節點數量依次遞增且通信半徑不變的情況下,相對定位誤差逐漸變小;二是隨著通信半徑的增大,相對定位誤差逐漸減小。究其原因,通信半徑的提升意味著網絡連通度的提升,相對誤差會減小,說明本文提出算法符合無線傳感器網絡部署的實際情況。

本文提出的改進算法利用均方差的計算方法,從全網誤差的角度進行優化,可有效降低整體誤差,并且這種優化方式與無線傳感器網絡拓撲架構無關。因此,本文提出的改進算法相對于改進跳數計數的優化方法,應用場景更廣,更具有普適性。

4 結束語

本文在DV-Hop算法基礎上提出了一種改進算法,在得到全網平均每跳距離的基礎上,通過分析任意錨節點的平均每跳距離誤差,建立均方差優化模型,修正全網平均每跳距離,使其能接近真實值,從而減小誤差,提高精度。仿真結果表明改進算法在減小誤差和提高精度方面均有所提升。