李鵬，陳桂芬，劉歡

（長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院，長(zhǎng)春 130022）

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

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

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

1 DV-Hop算法及誤差分析

1.1 DV-Hop算法

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

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

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

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

第三步：當(dāng)知道未知節(jié)點(diǎn)與兩個(gè)以上參考節(jié)點(diǎn)的距離時(shí)，使用三邊測(cè)距法或極大似然估計(jì)法，計(jì)算未知節(jié)點(diǎn)坐標(biāo)。

1.2 DV-Hop算法誤差分析

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

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

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

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

2.1 蝙蝠算法的步驟

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

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

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

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

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

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

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

2.2 蝙蝠算法適應(yīng)值函數(shù)的設(shè)計(jì)

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

式中，n為參考節(jié)點(diǎn)的個(gè)數(shù)，hi為未知節(jié)點(diǎn)到參考節(jié)點(diǎn)的跳數(shù)。hi通過(guò)DV-Hop算法的第一階段得到，而未知節(jié)點(diǎn)的估計(jì)距離是通過(guò)最小化適應(yīng)度函數(shù)的目標(biāo)值確定的。

2.3 蝙蝠算法的改進(jìn)

2.3.1 改變參數(shù)β

蝙蝠在搜索定位過(guò)程中通過(guò)調(diào)整fi獲得新的位置。在公式（3）中，β作為0～1之間均勻分布的隨機(jī)因子，實(shí)質(zhì)是蝙蝠個(gè)體的變異因子。該值越大，對(duì)fi的解作用越大，反之越小。因此合理改變?chǔ)碌闹悼梢蕴岣叻N群多樣性，避免早熟。進(jìn)而提高蝙蝠種群的尋優(yōu)精度。

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

Gmax為最大迭代次數(shù)，g為蝙蝠當(dāng)前迭代次數(shù)。迭代過(guò)程中，該算法通過(guò)改變?chǔ)轮?，?yōu)化頻率公式，改進(jìn)后的頻率更新公式如下：

2.3.2 改進(jìn)速度和位置更新公式

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

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

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

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

2.4 SLBADV-Hop算法定位步驟

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

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

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

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

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

3 算法仿真

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

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

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

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

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

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

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

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

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

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

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

在邊長(zhǎng)依次為100、150、200、250、300m的正方形區(qū)域中，通信半徑固定為40m，隨機(jī)分布100個(gè)節(jié)點(diǎn)，參考節(jié)點(diǎn)比例15%。改變?nèi)缟系亩ㄎ粎^(qū)域面積觀測(cè)定位精度變化情況。同時(shí)對(duì)三種情況進(jìn)行仿真，仿真結(jié)果如下圖。

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

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

4 結(jié)論

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