基于BPSDV—Hop的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法

戴天虹 王碩

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

【關(guān)鍵詞】BPSDV-HOP算法 無線傳感器網(wǎng)絡(luò) DV-HOP算法 混合粒子群優(yōu)化算法 蝙蝠算法

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）的基礎(chǔ)，在WSN研究中，將節(jié)點(diǎn)定位技術(shù)當(dāng)作現(xiàn)階段研究的首要任務(wù)，它的應(yīng)用前景極為廣泛，在一些復(fù)雜多變的環(huán)境中有很高的利用價(jià)值，眾所周知的安全探測、軍事環(huán)境等，運(yùn)用極多。

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

本文提出一種基于BA校正的混合粒子群優(yōu)化WSN定位算法即BPSDV-Hop定位算法，這一算法先通過優(yōu)化混合粒子群對一些未知節(jié)點(diǎn)精細(xì)計(jì)算，計(jì)算出跳距范圍，其次在應(yīng)用DV-Hop算法計(jì)算未知節(jié)點(diǎn)的自身位置時(shí)摒棄以往常用的最小二乘法，對于那些未知節(jié)點(diǎn)的坐標(biāo)的判斷要利用好蝙蝠算法，通過這一特性不斷優(yōu)化定位方法，確定精度，準(zhǔn)確定位WSN節(jié)點(diǎn)。

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

1.1 DV-Hop定位算法

第一步，獲取錨節(jié)點(diǎn)和計(jì)算跳距范圍；

第二步，獲取跳段距離。錨節(jié)點(diǎn)i的平均每跳距離計(jì)算公式為：

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

最后，計(jì)算未知節(jié)點(diǎn)的坐標(biāo)：設(shè)這n個(gè)錨節(jié)點(diǎn)的坐標(biāo)為，待定節(jié)點(diǎn)的坐標(biāo)為（x，y），待定節(jié)點(diǎn)與錨節(jié)點(diǎn)估計(jì)距離分別為d1，d2，…，dn，由此可建立如下方程：

在WSN測距過程當(dāng)中難免產(chǎn)生數(shù)據(jù)錯(cuò)誤，因此線性方程組為AL+N=b，其中，N為誤差向量，最小二乘法距離方程為：

1.2 DV-Hop定位誤差分析

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

由式（4）知，節(jié)點(diǎn)所在位置必定不會(huì)超出該區(qū)域范圍，且f（x，y）為定位總誤差，當(dāng)其獲取最小值時(shí)，該定位判斷得到的誤差最小，未知節(jié)點(diǎn)的最優(yōu)值即為坐標(biāo)（x，y），采用數(shù)學(xué)化模型的方法優(yōu)化定位問題，利用蝙蝠算法求解未知坐標(biāo)，防止誤差擴(kuò)大化。

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

2 BPSDV-Hop定位算法

2.1 蝙蝠算法

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

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

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

式中，隨機(jī)變量，At為所有蝙蝠的平均聲強(qiáng)。聲強(qiáng)和脈沖發(fā)射率的更新公式如式（7）所示：

2.2 混合粒子群優(yōu)化算法

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

假設(shè)當(dāng)前網(wǎng)絡(luò)中存在N個(gè)未知節(jié)點(diǎn)和M個(gè)錨節(jié)點(diǎn)，節(jié)點(diǎn)的坐標(biāo)集為，其中，錨節(jié)點(diǎn)的坐標(biāo)分別為，則未知節(jié)點(diǎn)的坐標(biāo)為，，，則定位問題就可用下面的公式來描述

表示第i個(gè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的實(shí)際距離與測量距離的誤差，而定位問題相應(yīng)的轉(zhuǎn)化為定位誤差的最小值。

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

2.3 適應(yīng)值函數(shù)設(shè)計(jì)

蝙蝠的優(yōu)劣位置是通過對混合粒子群優(yōu)化算法的特點(diǎn)分析和適應(yīng)度的關(guān)系來判斷的，其中適應(yīng)度函數(shù)計(jì)算公式為：

式中，M為錨節(jié)點(diǎn)的個(gè)數(shù)，表示未知節(jié)點(diǎn)與第i個(gè)錨節(jié)點(diǎn)之間測量距離的權(quán)重大小，權(quán)重的大小是由未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)決定的，權(quán)重值和跳數(shù)的關(guān)系是相反的，這完全符合實(shí)際情況。其次，未知節(jié)點(diǎn)的估計(jì)距離是根據(jù)最小化適應(yīng)度函數(shù)的目標(biāo)值來判斷確定的。

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

首先，混合粒子群在BA校正的基礎(chǔ)上，不斷優(yōu)化無線傳感器網(wǎng)絡(luò)定位，將求解位置坐標(biāo)問題轉(zhuǎn)化成一個(gè)全局最優(yōu)化問題，其次在應(yīng)用DV-Hop算法計(jì)算未知節(jié)點(diǎn)的自身位置時(shí)摒棄以往常用的最小二乘法，對于那些未知節(jié)點(diǎn)的坐標(biāo)的判斷要利用好蝙蝠算法，通過這一特性不斷優(yōu)化定位方法，確定精度，從而獲取更加理想的WSN定位結(jié)果，具體實(shí)現(xiàn)流程如圖2所示。

3 仿真實(shí)例

3.1 仿真環(huán)境

充分利用Matlab仿真平臺(tái)，在相同網(wǎng)絡(luò)環(huán)境下對比實(shí)驗(yàn)DV-Hop定位算法測試驗(yàn)證BPSDV-Hop算法的定位性能，在其他條件相同的前提下，改變錨節(jié)點(diǎn)的密度、通訊半徑以及節(jié)點(diǎn)的數(shù)量，采用平均定位誤差對比兩種算法的定位性能，具體如下：

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

3.2 結(jié)果與分析

3.2.1 對兩種算法的定位誤差進(jìn)行比較

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

3.2.2 錨節(jié)點(diǎn)個(gè)數(shù)對算法定位性能的影響

在比較錨節(jié)點(diǎn)個(gè)數(shù)對算法定位性能的影響時(shí)，保持節(jié)點(diǎn)個(gè)數(shù)不變，使錨節(jié)點(diǎn)得比例不同，兩種算法的定位誤差變化曲線如圖4所示。由圖4知，當(dāng)錨節(jié)點(diǎn)的比例相同時(shí)，BPSDV-Hop算法的定位誤差更小，且其能在較小的錨節(jié)點(diǎn)密度下實(shí)現(xiàn)更精確的定位。

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

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

3.2.4 節(jié)點(diǎn)個(gè)數(shù)對算法定位性能的影響

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

4 結(jié)束語

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

參考文獻(xiàn)

[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]葉蓉，趙靈鍇.基于蟻群粒子群混合的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)測量與控制，2011，19（03）：732-735.

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

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

[5]譚愛平，陳浩，吳伯橋.基于BADV-Hop的傳感器節(jié)點(diǎn)定位方法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（17）：125-129.

[6]劉運(yùn)杰，金明錄，崔承毅.基于RSSI的無線傳感器網(wǎng)絡(luò)修正加權(quán)定位算法[J].傳感技術(shù)學(xué)報(bào)，2009，23（05）：717-721.

[7]鄧力.基于遺傳算法WSN節(jié)點(diǎn)定位算法研究[J].計(jì)算機(jī)仿真，2011，28（09）：161-164.

[8]王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào)，2005，16（05）：857-868.

[9]李輝，熊盛武，劉毅等.無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進(jìn)[J].傳感技術(shù)學(xué)報(bào)，2011，24（12）：1782-1786.

[10]劉少飛，趙清華.基于平均跳距估計(jì)和位置修正的DV-Hop定位算法[J].傳感器技術(shù)學(xué)報(bào)，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ī)器人系統(tǒng)協(xié)調(diào)路徑規(guī)劃[J]. 機(jī)械工程學(xué)報(bào)，2005（02）：194-198+204.

[13]凌琳.基于混合粒子群算法的無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位研究[D].江西師范大學(xué)，2013.

作者單位

東北林業(yè)大學(xué)機(jī)電工程學(xué)院 黑龍江省哈爾濱市 150040