基于蝙蝠算法的無線傳感器網(wǎng)絡定位研究

李鵬，陳桂芬，劉歡

（長春理工大學 電子信息工程學院，長春 130022）

無線傳感器網(wǎng)絡WSNs（Wireless Sensor Networks）是當前信息科學技術領域研究的熱點之一，可實現(xiàn)特殊情況下信號的收集、處理和發(fā)送。由于其獨特的學科交叉性，成為了二十一世紀極具發(fā)展?jié)摿Φ年P鍵技術。無線傳感器網(wǎng)絡是僅次于互聯(lián)網(wǎng)的第二大網(wǎng)絡，具有低成本、體積小、傳輸距離遠等優(yōu)勢，廣泛應用于軍事、醫(yī)療環(huán)境監(jiān)測等方面［1］。無線傳感器網(wǎng)絡是物聯(lián)網(wǎng)最基本的組成部分，它對于實現(xiàn)各種類型數(shù)據(jù)融合和遠程控制功能起到了不可替代的重要作用。定位是無線傳感器網(wǎng)絡重要的支撐技術。

DV-Hop算法是目前應用最廣的一種無需測距的定位算法。但是已知節(jié)點與未知節(jié)點的距離計算存在誤差，導致DV-Hop算法定位精度不高。多年來國內外學者針對傳統(tǒng)DV-Hop提出了多種改進算法，文獻［2］在DV-Hop算法中引入介質訪問機制來調節(jié)距離誤差；文獻［3］將RSSI策略引入到DV-Hop算法節(jié)點距離計算中，減小節(jié)點間誤差，提高定位精度；文獻［4］提出單純形法與遺傳算法相結合的混合算法用于計算未知節(jié)點坐標，以提高定位精度；文獻［5］提出了遺傳粒子群優(yōu)化的DV-Hop的定位算法，有效解決了局部搜索的定位精度問題；文獻［6］提出了加權DV-Hop定位算法和Min-Max修正算法，達到提高定位精度的目的；文獻［7］針對信標節(jié)點密度提出基于DV-Hop的修改算法，從源頭上減小誤差；文獻［8］將模擬退火算法應用于基于測距修正的DV-Hop算法；文獻［9］提出基于跳數(shù)修正和改進粒子群優(yōu)化DV-Hop定位算法，進一步優(yōu)化定位精度。近幾年蝙蝠算法是一種群智能優(yōu)化算法，在準確性和有效性方面相較其他算法有很大優(yōu)勢，且沒有許多參數(shù)要調整，為DV-Hop算法誤差校正提供了一種新的研究思路［10］。

綜合考慮以上算法的優(yōu)缺點，提出了一種將改進后的蝙蝠算法應用到DV-Hop算法的新算法，首先對頻率公式中的參數(shù)β進行改進，在此基礎上在蝙蝠算法中引入自學習算法，在提高節(jié)點距離計算精度的同時，避免算法陷入局部最優(yōu)。仿真結果表明，與DV-Hop算法和BADV-Hop算法相比，SLBA-DV-Hop算法在不同實際情況下均能有效提高節(jié)點的定位精度。

1 DV-Hop算法及誤差分析

1.1 DV-Hop算法

DV-Hop算法是根據(jù)矢量路由的原理提出的一種無需測距的定位算法，該定位算法的過程可以分為3步。

第一步：WSN中的參考節(jié)點首先利用洪泛算法將自身位置信息向全網(wǎng)廣播，網(wǎng)絡中的參考節(jié)點通過典型的距離矢量交換協(xié)議廣播自身位置分組，使得網(wǎng)絡中的所有節(jié)點獲得距離參考節(jié)點最小的跳數(shù)信息。

第二步：.每個參考節(jié)點利用其它參考節(jié)點的位置信息和相隔最小跳數(shù)計算平均每跳距離，并將其作為一個校正值廣播到網(wǎng)絡中。網(wǎng)絡中未知節(jié)點接收到該信息后，將其與到各錨節(jié)點的跳數(shù)的乘積作為未知節(jié)點到各錨節(jié)點距離的估算量。然后通過錨節(jié)點計算HopSize，并廣播到整個網(wǎng)絡。

式中，Hopsizei表示參考節(jié)點i的平均跳距，坐標（xi,yi），（xj,yj）分別表示參考節(jié)點i與參考節(jié)點j的坐標。hij為節(jié)點i與節(jié)點j之間的最小跳數(shù)。再由下式計算參考節(jié)點與未知節(jié)點距離。

第三步：當知道未知節(jié)點與兩個以上參考節(jié)點的距離時，使用三邊測距法或極大似然估計法，計算未知節(jié)點坐標。

1.2 DV-Hop算法誤差分析

（1）跳距誤差：節(jié)點大部分是隨機拋灑在想要監(jiān)測的各個區(qū)域，很容易產(chǎn)生參考節(jié)點分布不均的情況。這種情況下，節(jié)點間的跳距會有較大差距，這種情況下只是利用平均跳距乘以最小跳數(shù)來計算就會帶來很大誤差。

（2）錨節(jié)點密度：綜合考慮參考節(jié)點成本和能量消耗的情況下，參考節(jié)點數(shù)量不會很多，在需要大范圍的監(jiān)控區(qū)域只有十幾個甚至幾個參考節(jié)點時，其定位精度會受到很大影響，無法滿足高定位精度的實際需求。

（3）算法本身的計算誤差：三邊測距法計算方法雖然簡單精煉，但一旦未知節(jié)點與參考節(jié)點距離存在較大誤差，就會隨著每步的進行逐漸放大誤差，極大似然估計法計算方法較復雜一些，對較大誤差的估計距離無過濾作用。

2 SLBADV-Hop算法的節(jié)點定位

2.1 蝙蝠算法的步驟

蝙蝠算法是受自然界中的蝙蝠依靠回聲定位方法避開障礙以及搜尋食物行為的啟發(fā)，并將遺傳進化機制與多智能體系相結合發(fā)展而來的一種新型群體智能啟發(fā)式算法。當蝙蝠出發(fā)時，響度最大而脈沖發(fā)射率最小，蝙蝠探測到獵物之后，在飛向獵物的過程中，響度逐漸減小而脈沖發(fā)射率不斷增大。蝙蝠正是通過這種回聲定位方式進行精確定位以確定飛行方向和搜尋獵物的。將蝙蝠算法視為函數(shù)minf(x)求目標變量為X=(x1,x2,…,xd)T的優(yōu)化問題，具體步驟如下：

第一步：蝙蝠種群初始化，蝙蝠在N維空間隨機飛行看做即函數(shù)在某一區(qū)域的初始解。蝙蝠飛行產(chǎn)生的搜索聲波頻率范圍為［fmin,fmax］、最大脈沖響度A0、最大脈沖發(fā)射率R0。脈沖響度衰減系數(shù)α，脈沖發(fā)射率增加系數(shù)γ，搜索精度ε或最大迭代次數(shù)iter_max。

第二步：隨機初始化蝙蝠的位置xi，并根據(jù)適應度值的優(yōu)劣情況尋找當前的最優(yōu)解x?，即初始種群的最優(yōu)位置，然后調節(jié)此時的脈沖頻率，更新蝙蝠個體i在t時刻的位置和速度，具體公式如下所示。

第三步：蝙蝠通過迭代縮小搜索范圍后，會進入局部搜索階段。蝙蝠會在它附近按公式（6）隨機運動并產(chǎn)生一個新解xnew，而xold為當前時刻選出的最佳解。At表示t時刻蝙蝠響度平均值。θ是一個隨機數(shù)，在0～1之間均勻分布。

At表示t時刻蝙蝠響度平均值。θ為0～1之間服從均勻分布的隨機數(shù)。

第四步：蝙蝠種群個體在不斷更新。當蝙蝠個體在t時刻接近獵物時，聲波響度逐漸降低，同時脈沖速率逐漸增高，直到蝙蝠個體i搜索到獵物時Ai=0，此時聲波停止。更新公式如下：

第五步：在所有蝙蝠的適應度值中找出當前最優(yōu)解，重復第二、三、四步，找到最優(yōu)解時或滿足最大迭代次數(shù)后結束循環(huán)，最后通過最優(yōu)解輸出全局最優(yōu)值。

2.2 蝙蝠算法適應值函數(shù)的設計

蝙蝠算法每次迭代結束后，蝙蝠所處位置的優(yōu)劣都要通過適應值來判斷。將蝙蝠種群中的每一個蝙蝠看做未知節(jié)點的一個隨機解。適應值函數(shù)計算公式為：

式中，n為參考節(jié)點的個數(shù)，hi為未知節(jié)點到參考節(jié)點的跳數(shù)。hi通過DV-Hop算法的第一階段得到，而未知節(jié)點的估計距離是通過最小化適應度函數(shù)的目標值確定的。

2.3 蝙蝠算法的改進

2.3.1 改變參數(shù)β

蝙蝠在搜索定位過程中通過調整fi獲得新的位置。在公式（3）中，β作為0～1之間均勻分布的隨機因子，實質是蝙蝠個體的變異因子。該值越大，對fi的解作用越大，反之越小。因此合理改變β的值可以提高種群多樣性，避免早熟。進而提高蝙蝠種群的尋優(yōu)精度。

在基本的蝙蝠算法中，β是一個常數(shù)，并不隨著蝙蝠搜索時間的變化而變化。現(xiàn)對β做如下定義：

Gmax為最大迭代次數(shù)，g為蝙蝠當前迭代次數(shù)。迭代過程中，該算法通過改變β值，優(yōu)化頻率公式，改進后的頻率更新公式如下：

2.3.2 改進速度和位置更新公式

根據(jù)蝙蝠算法的原理和公式可知，蝙蝠算法的蝙蝠種群多樣性很差，優(yōu)化過程中極易陷入局部最優(yōu)值。現(xiàn)對其加以改進，并將改進后的算法用于解決無線傳感器網(wǎng)絡定位問題，提高節(jié)點定位精度。假設蝙蝠個體擁有本身速度決定飛行方向和距離。他們可以自行判斷t時刻本體的位置以及t時刻發(fā)現(xiàn)的最優(yōu)位置。甚至可以發(fā)現(xiàn)該時刻其它蝙蝠個體發(fā)現(xiàn)的最優(yōu)位置，蝙蝠綜合這三點因素，“自行學習”最佳的飛行位置。

在標準蝙蝠算法中，蝙蝠速度只是當前位置的函數(shù)，提出的自學習算法中蝙蝠個體的飛行速度會隨著蝙蝠位置的變化而變化。通過此自學習策略，蝙蝠個體通過迭代，逐步尋找當前最優(yōu)蝙蝠的位置。假設蝙蝠i在n維空間的速度和位置分別為vi=(vi,1vi,2vi,d）以及xi=(xi,1,xi,2,xi,d），每進行一次搜索，蝙蝠通過跟蹤兩個最優(yōu)解改變自己位置。第一個是蝙蝠個體本身找到的最佳解，記為a。第二個是整個種群該時刻找到的最優(yōu)解，記為b。蝙蝠個體會根據(jù)這兩個最優(yōu)值更新自己的速度和方位，具體公式如下：

c1，c2為蝙蝠算法的自學習參數(shù)，是蝙蝠個體自學習和學習種群最佳個體的關鍵，這樣才能保證個體對整體最優(yōu)位置的搜尋。為保證算法整體性能，這里取c1=c2=2。

r1，r2是0～1之間均勻分布的隨機數(shù)。

2.4 SLBADV-Hop算法定位步驟

（1）首先在待檢測區(qū)域隨機拋灑節(jié)點，進行經(jīng)典DV-Hop算法前兩步驟，獲得所有節(jié)點與參考節(jié)點間的最小跳數(shù)信息以及每個節(jié)點與參考節(jié)點間距離。第三步應用改進后的自學習蝙蝠算法實現(xiàn)。

（2）設置如下參數(shù)：蝙蝠數(shù)量n，蝙蝠個體i，搜素空間d維，聲波頻率fi，脈沖發(fā)射率R(i)，響度A(i)。初始化蝙蝠種群中每個個體的速度和位置。采用自學習算法修改原蝙蝠算法中蝙蝠個體i在t時刻的位置。a，b分別為蝙蝠本身及種群找到的最優(yōu)解，c1，c2為自學習參數(shù)。由公式（3）、（11）、（12）對蝙蝠個體的速度和位置進行優(yōu)化更新。

（3）每次搜索完成后，如果蝙蝠i的位置好于上次迭代最佳蝙蝠的位置，則用公式（7）、（8）更新脈沖發(fā)射率和響度。

（4）找出當前具有最優(yōu)蝙蝠個體的適應值函數(shù)以及當前速度和具體位置。

（5）重復步驟（2），（3），直到達到預先設定好的迭代次數(shù)。搜索結束后，處于最佳位置的蝙蝠就是未定位節(jié)點的最優(yōu)位置近似值。

3 算法仿真

為了準確了解定位精度問題，用Matlab軟件對改進后的算法進行仿真。假設理想條件下，在邊長100m的正方形網(wǎng)絡中，隨機分布100個傳感器節(jié)點，節(jié)點通信半徑為40m。分別討論不同參考節(jié)點數(shù)量，總節(jié)點數(shù)量以及探測區(qū)域面積對傳統(tǒng)DV-Hop算法、BADV-Hop算法、SLBADV-Hop算法定位精度的影響。每種實驗進行一百次，為減小定位誤差，取一百次的平均值。節(jié)點定位誤差用如下公式表示。

式中（xk,yk）是節(jié)點k的估計坐標，（x，y）為未知節(jié)點k定位后的坐標，節(jié)點k通信半徑為R。

（1）參考節(jié)點比例對平均定位精度影響

邊長為100m的正方形區(qū)域中，通信半徑固定為40m。隨機分布100個節(jié)點。參考節(jié)點比例分別為5%、10%、15%、20%、25%、30%。改變參考節(jié)點比例觀測平均定位精度的變化情況。同時對三種算法進行仿真，仿真結果如下圖。

圖1 節(jié)點總數(shù)不變參考節(jié)點比例改變的定位誤差比較

從圖中可以看出隨著參考節(jié)點比例的提高，三種算法平均定位誤差都在下降，但SLBADV-Hop算法定位誤差明顯小于前兩個算法。當參考節(jié)點比例增大到15%以上時，定位精度誤差有大幅度提高。但是當參考節(jié)點比例增加到一定程度時，三種算法的誤差差距逐漸減小。

（2）網(wǎng)絡節(jié)點總數(shù)對平均定位精度的影響

在邊長為100m的正方形區(qū)域中，分別隨機分布100、150、200、250、300個節(jié)點，通信半徑固定為40m。參考節(jié)點比例15%。改變網(wǎng)絡節(jié)點總數(shù)觀測平均定位精度變化情況。同時對三種算法進行仿真，仿真結果如下圖。

圖2 參考節(jié)點比例不變節(jié)點總數(shù)改變的定位誤差比較

從圖中可以看出隨著參考節(jié)點比例的提高，三種算法平均定位誤差都在下降，其中SLBADV-Hop誤差率是最低的。當總節(jié)點數(shù)介于100和150之間時誤差下降最為明顯，定位精度提高了20%左右。但是可以明顯看出，當節(jié)點總數(shù)增大到一定數(shù)目時節(jié)點密度并沒有大幅度提升，節(jié)點密度過大，節(jié)點間通信浪費了更多能耗，還增加了不必要的成本。所以應根據(jù)實際情況合理選擇節(jié)點數(shù)量。

（3）定位區(qū)域面積對平均定位精度的影響

在邊長依次為100、150、200、250、300m的正方形區(qū)域中，通信半徑固定為40m，隨機分布100個節(jié)點，參考節(jié)點比例15%。改變如上的定位區(qū)域面積觀測定位精度變化情況。同時對三種情況進行仿真，仿真結果如下圖。

圖3 節(jié)點總數(shù)和參考節(jié)點總數(shù)不變定位區(qū)域面積改變的定位誤差比較

從圖中可以看出隨著參考節(jié)點比例的提高，三種算法定位誤差均有不同程度的提高，但SLBADV-Hop算法誤差比前兩者低很多。由于節(jié)點總數(shù)不變，定位區(qū)域增大，導致節(jié)點密度相對稀疏，降低定位精度。當邊長超過260m時，誤差增大的情況愈發(fā)明顯。這種情況下，SLBADV-Hop算法依然保持了較低的誤差。比應用于DV-Hop的蝙蝠算法平均提高了9.1%的定位精度。

4 結論

針對無線傳感器網(wǎng)絡定位誤差較大的問題，提出了一種將DV-Hop算法與改進蝙蝠算法相結合的算法。改進了影響蝙蝠收斂性的參數(shù)β，又在蝙蝠速度和位置更新公式中引入學習因子，解決局部最優(yōu)問題。仿真結果表明，本文提出的算法有效提高了節(jié)點的定位精度，且該算法迭代次數(shù)少，收斂性好，易于實現(xiàn)。由于本算法沒有考慮障礙物密集度較高的情況，下一步工作中將隨機設置一定數(shù)量的障礙物，使該算法應用范圍更廣。