基于BPSDV—Hop的無線傳感器網絡節點定位算法

戴天虹 王碩

摘 要 為了盡量避免誤差的擴大化，定位更加準確，增強無線傳感器網絡節點的靈敏程度，混合粒子群在BA校正的基礎上，不斷優化無線傳感器網絡定位，充分利用BPSDV-Hop定位算法，這一算法先通過優化混合粒子群對一些未知節點精細計算，計算出跳距范圍，其次在應用DV-Hop算法計算未知節點的自身位置時摒棄以往常用的最小二乘法，對于那些未知節點的坐標的判斷要利用好蝙蝠算法，通過這一特性不斷優化定位方法，確定精度，最后要充分發揮Matlab平臺的作用，利用這一平臺，對算法細致化分析與探究。據可靠分析顯示：BPSDV-Hop定位算法遠遠優越于DV-Hop定位算法，它對未知坐標的判斷和定位準確度非常之高，在WSN中具有廣泛的應用前景。

【關鍵詞】BPSDV-HOP算法 無線傳感器網絡 DV-HOP算法 混合粒子群優化算法 蝙蝠算法

節點定位技術是無線傳感器網絡（Wireless Sensor Network，WSN）的基礎，在WSN研究中，將節點定位技術當作現階段研究的首要任務，它的應用前景極為廣泛，在一些復雜多變的環境中有很高的利用價值，眾所周知的安全探測、軍事環境等，運用極多。

目前，國內外專家和學者對WSN其展開了一系列的分析探索，定位算法有測距和非測距之分，作用各不相同。DV-Hop 算法是免測距算法中比較成熟的算法，它的定位方法比起其它算法來說較為容易，通過一少部分的錨節點就能實現快捷定位，但缺點是定位精度略低。因此，學者們對 DV-Hop 算法進行了一系列的改進用于提高其定位精度，例如：在DV-Hop算法的節點距離計算中使用RSSI策略，縮小節點之間的誤差，提高WSN定位精度；將介質訪問機制引進DV-Hop算法中優化距離誤差；在錨節點間進行距離計算時，為實現平均跳距計算的準確性，采用最佳調整因子不斷優化經過一系列分析得出的定位結果；運用混合粒子群優化算法求解DV-Hop 定位算法中未知節點的平均跳距，減少定位誤差提高定位準確性；不過這些算法仍然存在較多的問題，不能充分考慮到算法的全面性，從而忽視了搜索的空間大小問題，對WSN節點的定位精度產生重要影響。為了避免這種情況，我們要開拓思維另辟蹊徑。終于在2010年，蝙蝠算法（BA）正式被楊新社教授提出，他充分利用蝙蝠的回聲定位的特性，進行大量實驗數據分析提出該算法，蝙蝠算法在實際應用中具有很多優良特性，尤其表現在迭代尋優方面，且不需要對大量的參數進行調整，所以為了減少誤差，提高WSN節點的定位精度，本文將引入BA算法為校正DV-Hop 算法的誤差提供一種新的研究思路。

本文提出一種基于BA校正的混合粒子群優化WSN定位算法即BPSDV-Hop定位算法，這一算法先通過優化混合粒子群對一些未知節點精細計算，計算出跳距范圍，其次在應用DV-Hop算法計算未知節點的自身位置時摒棄以往常用的最小二乘法，對于那些未知節點的坐標的判斷要利用好蝙蝠算法，通過這一特性不斷優化定位方法，確定精度，準確定位WSN節點。

1 DV-Hop定位算法及誤差分析

1.1 DV-Hop定位算法

第一步，獲取錨節點和計算跳距范圍；

第二步，獲取跳段距離。錨節點i的平均每跳距離計算公式為：

式中，hij是錨節點i和j之間的跳數，（xi，yi）、（xj，yj）是節點i和j的坐標。之后將所有錨節點的跳距的范圍平均映射到每一部分，未知節點的每次跳距之間的距離范圍即映射得到的錨節點的跳距范圍相同，錨節點的跳段距離就是平均每跳的距離范圍與最小的跳數之積。

最后，計算未知節點的坐標：設這n個錨節點的坐標為，待定節點的坐標為（x，y），待定節點與錨節點估計距離分別為d1，d2，…，dn，由此可建立如下方程：

在WSN測距過程當中難免產生數據錯誤，因此線性方程組為AL+N=b，其中，N為誤差向量，最小二乘法距離方程為：

1.2 DV-Hop定位誤差分析

先假設錨節點i和未知節點之間的實際距離為ri，測距誤差為εi，（x，y）符合約束條件|ri-di|<εi，求解（x，y），使得

由式（4）知，節點所在位置必定不會超出該區域范圍，且f（x，y）為定位總誤差，當其獲取最小值時，該定位判斷得到的誤差最小，未知節點的最優值即為坐標（x，y），采用數學化模型的方法優化定位問題，利用蝙蝠算法求解未知坐標，防止誤差擴大化。

此外，DV-Hop定位算法的定位原理為將錨節點當作未知節點，它們之間的平均跳距用兩錨節點之間的平均跳距表示，這就很容易在兩點之間的定位出現誤差。因此，本文采用混合粒子群優化算法求解未知節點的平均跳距，減少定位誤差。

2 BPSDV-Hop定位算法

2.1 蝙蝠算法

將蝙蝠的回聲定位理想化，每個虛擬蝙蝠在位置xi（問題的解）均有對應的飛行速度vi，剛開始尋找獵物時，蝙蝠發出低頻高聲強的超聲波，用以擴大搜索范圍，發現獵物后，逐漸減小聲強并增加脈沖的頻率，以精確定位獵物。

其中，虛擬蝙蝠的實時位置和速度如式（5）所示：

式中，fi，fmax，fmin依次表示為當前時刻第i只蝙蝠發出的脈沖頻率，最大脈沖頻率和最小脈沖頻率，按照均勻分布原則，其中β為隨機因子，x*為此前最優解。在搜索產生局部新解的過程中，要充分利用隨機游走的原則，當其中一個最優解被選中時，按照原則進行合理化分析判斷：

式中，隨機變量，At為所有蝙蝠的平均聲強。聲強和脈沖發射率的更新公式如式（7）所示：

2.2 混合粒子群優化算法

相對粒子群算法（PSO）的弊端較為明顯，經常出現最優解判斷不全等問題；顯而易見，模擬退火算法則很好的解決了這一問題，它的優勢不僅體現在搜索的全面性上，它的搜索效率也比PSO算法顯著提高；這里提到的混合粒子群優化算法（PSO-SA），本質上就是上面兩種算法的結合體，將優勢相融合，還具有一定的學習能力，充分利用了模擬退火算法的特性--退火特征。為了避免陷入局部最優解，按照Metropolis機制對粒子的位置和速度進行合理化的判斷分析，及時進行數據更新，對初始種群中的粒子進行最優解的搜索，確定其初始參數，再執行其退火過程。

假設當前網絡中存在N個未知節點和M個錨節點，節點的坐標集為，其中，錨節點的坐標分別為，則未知節點的坐標為，，，則定位問題就可用下面的公式來描述

表示第i個錨節點與未知節點之間的實際距離與測量距離的誤差，而定位問題相應的轉化為定位誤差的最小值。

在混合粒子群優化算法中，溫度對粒子群算法影響不是很大，根據模擬退火算法的特性，對溫度T的進行如下設置：從粒子群中選出粒子的適應度最小與最大的粒子，其中適應度值為fmin，fmax，在退火過程中按蒙特卡羅準則以一定概率p0接受重要狀態，設初始溫度為，同時，在粒子進行迭代過程中，按照的速度降低溫度，。在實際過程中，當p0=0.85，λ=0.95時，算法才有最好的優良性能。在混合粒子群優化算法中，粒子群優化算法的結束的條件是給定粒子群的最大速度和坐標情況，當算法達到這個值時，算法結束；然而，對于模擬退火算法，它的結束條件則通過比較相鄰之間最優解的目標函數增量△f與一定程度ε的大小來判斷是否進行降溫處理。混合粒子群優化算法流程圖如圖1所示。

2.3 適應值函數設計

蝙蝠的優劣位置是通過對混合粒子群優化算法的特點分析和適應度的關系來判斷的，其中適應度函數計算公式為：

式中，M為錨節點的個數，表示未知節點與第i個錨節點之間測量距離的權重大小，權重的大小是由未知節點到錨節點的跳數決定的，權重值和跳數的關系是相反的，這完全符合實際情況。其次，未知節點的估計距離是根據最小化適應度函數的目標值來判斷確定的。

2.4 BPSDV-Hop定位算法的工作流程

首先，混合粒子群在BA校正的基礎上，不斷優化無線傳感器網絡定位，將求解位置坐標問題轉化成一個全局最優化問題，其次在應用DV-Hop算法計算未知節點的自身位置時摒棄以往常用的最小二乘法，對于那些未知節點的坐標的判斷要利用好蝙蝠算法，通過這一特性不斷優化定位方法，確定精度，從而獲取更加理想的WSN定位結果，具體實現流程如圖2所示。

3 仿真實例

3.1 仿真環境

充分利用Matlab仿真平臺，在相同網絡環境下對比實驗DV-Hop定位算法測試驗證BPSDV-Hop算法的定位性能，在其他條件相同的前提下，改變錨節點的密度、通訊半徑以及節點的數量，采用平均定位誤差對比兩種算法的定位性能，具體如下：

在100m×100m的二維空間內隨機安排100個節點，其中節點的通信半徑為30m，錨節點占全部節點的10%，參數設置如下：蝙蝠種群大小m=100，最大聲強A=0.20，聲強衰減系數及脈沖頻度增加系數均為0.05，搜索脈沖頻率范圍[0，100]，最大脈沖頻度r0=0.75，所有結果為平均運行50次后取平均值。

3.2 結果與分析

3.2.1 對兩種算法的定位誤差進行比較

DV-Hop算法和BPSDV-Hop算法的未知節點的定位誤差如圖3所示。由圖3知，BPSDV-Hop算法的定位的平均誤差并不大且明顯小于DV-Hop算法的誤差值，結果表明，BPSDV-Hop算法提高了定位精度。

3.2.2 錨節點個數對算法定位性能的影響

在比較錨節點個數對算法定位性能的影響時，保持節點個數不變，使錨節點得比例不同，兩種算法的定位誤差變化曲線如圖4所示。由圖4知，當錨節點的比例相同時，BPSDV-Hop算法的定位誤差更小，且其能在較小的錨節點密度下實現更精確的定位。

3.2.3 通信半徑對算法定位性能的影響

節點個數不變，錨節點比例為10%，當通信半徑不同，兩種定位算法的變化趨勢如圖5所示。由圖5知，相同通信半徑條件下，BPSDV-Hop算法的定位精度提高了25%-35%，有效降低了WSN節點的定位誤差。

3.2.4 節點個數對算法定位性能的影響

在判斷節點個數對算法定位性能的影響時，保持錨節點的比例不變，使節點個數不同，這兩種算法的定位變化趨勢如圖6所示。由圖6可知，節點數量的變化對BPSDV-Hop算法的影響相對較小，實驗結果表明，BPSDV-Hop定位算法具有良好的魯棒性。

4 結束語

為了盡量避免誤差的擴大化，定位更加準確，增強無線傳感器網絡節點的靈敏程度，混合粒子群在BA校正的基礎上，不斷優化無線傳感器網絡定位，充分利用BPSDV-Hop定位算法，這一算法先通過優化混合粒子群對一些未知節點精細計算，計算出跳距范圍，其次在應用DV-Hop算法計算未知節點的自身位置時摒棄以往常用的最小二乘法，對于那些未知節點的坐標的判斷要利用好蝙蝠算法，通過這一特性不斷優化定位方法，確定精度。實驗結果表明：BPSDV-Hop定位算法遠遠優越于DV-Hop定位算法，它對未知坐標的判斷和定位準確度非常之高，在WSN中具有廣泛的應用前景。

參考文獻

[1]Gao Y，Zhao W S，Jing C，et al.WSN node localization algorithm based on adaptive swarm optimization[J].Applied Mechanics and Materials，2012（143）：303-306.

[2]葉蓉，趙靈鍇.基于蟻群粒子群混合的無線傳感器網絡定位算法[J].計算機測量與控制，2011，19（03）：732-735.

[3]趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網絡定位算法[J].計算機應用與軟件，2009，26（10）：189-192.

[4]白進京，嚴新平.基于加權質心和DV-hop混合算法WSN定位方法研究[J].計算機應用研究，2009，26（06）：2248-2251.

[5]譚愛平，陳浩，吳伯橋.基于BADV-Hop的傳感器節點定位方法[J].計算機工程與應用，2014，50（17）：125-129.

[6]劉運杰，金明錄，崔承毅.基于RSSI的無線傳感器網絡修正加權定位算法[J].傳感技術學報，2009，23（05）：717-721.

[7]鄧力.基于遺傳算法WSN節點定位算法研究[J].計算機仿真，2011，28（09）：161-164.

[8]王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報，2005，16（05）：857-868.

[9]李輝，熊盛武，劉毅等.無線傳感器網絡DV-HOP定位算法的改進[J].傳感技術學報，2011，24（12）：1782-1786.

[10]劉少飛，趙清華.基于平均跳距估計和位置修正的DV-Hop定位算法[J].傳感器技術學報，2009，22（08）：1154-1158.

[11]Yang X S，Gandomi A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computations，2012，29（05）：464-483.

[12]陳志翔，殷樹言，盧振洋.基于遺傳模擬退火算法的弧焊機器人系統協調路徑規劃[J]. 機械工程學報，2005（02）：194-198+204.

[13]凌琳.基于混合粒子群算法的無線傳感網絡節點定位研究[D].江西師范大學，2013.

作者單位

東北林業大學機電工程學院 黑龍江省哈爾濱市 150040