基于可靠錨節(jié)點(diǎn)和粒子群優(yōu)化的DV?Hop 算法

李同鋒，杜秀娟，謝 平，楊 帆

（青海師范大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧 810000）

0 引言

無(wú)線傳感器定位算法通常分為基于測(cè)距算法（Range?based Algorithm）和無(wú)需測(cè)距算法（Range?free Algorithm）兩類(lèi)[1?3]。無(wú)需測(cè)距算法DV?Hop 因其實(shí)現(xiàn)成本低、算法簡(jiǎn)單等優(yōu)點(diǎn)得到了廣泛應(yīng)用，是當(dāng)今研究的熱點(diǎn)之一[4]。近年來(lái)，國(guó)內(nèi)外諸多學(xué)者[5?9]針對(duì)DV?Hop算法的不足之處進(jìn)行了改進(jìn)，效果明顯。本文針對(duì)DV?Hop 算法的不足之處進(jìn)行了改進(jìn)，仿真結(jié)果表明效果明顯。

1 DV?Hop 算法原理及誤差分析

DV?Hop 算法定位過(guò)程包括以下階段[9?10]。

1.1 泛 洪

錨節(jié)點(diǎn)首先向鄰居節(jié)點(diǎn)廣播包含自身位置、ID 號(hào)和跳數(shù)值為0 的信息，鄰居節(jié)點(diǎn)第一次收到該信息后，保留該信息，并將跳數(shù)加1 發(fā)送到它的鄰居節(jié)點(diǎn)。對(duì)于收到同一個(gè)錨節(jié)點(diǎn)發(fā)來(lái)的信息，以最小原則更新本地跳數(shù)值。該階段完成后，監(jiān)測(cè)區(qū)域中所有節(jié)點(diǎn)都已知道錨節(jié)點(diǎn)的位置坐標(biāo)及到錨節(jié)點(diǎn)的最小跳數(shù)。

1.2 計(jì)算錨節(jié)點(diǎn)平均跳距

每一個(gè)錨節(jié)點(diǎn)通過(guò)式（1）計(jì)算自身的平均跳距。

式中：(xi,yi)表示錨節(jié)點(diǎn)i的坐標(biāo)；hopsij為錨節(jié)點(diǎn)i和j之間的最小跳數(shù)。計(jì)算完成后向網(wǎng)絡(luò)廣播它們的HopSize。

1.3 計(jì)算未知節(jié)點(diǎn)坐標(biāo)

未知節(jié)點(diǎn)采用距離本身最近的錨節(jié)點(diǎn)的平均跳距作為自己的平均跳距。未知節(jié)點(diǎn)k到錨節(jié)點(diǎn)i的估算距離記為dik：

式中：HopSizei代表距離k節(jié)點(diǎn)最近的錨節(jié)點(diǎn)平均跳距；hopik為錨節(jié)點(diǎn)i到未知節(jié)點(diǎn)k的最小跳數(shù)。根據(jù)式（2）和基本定位法進(jìn)行定位，用方程組表示為：

把式（3）寫(xiě)成AX=B的形式，A，B和X的具體值如下：

解之可得：

1.4 誤差分析

1）曲線代直線和通信范圍內(nèi)節(jié)點(diǎn)跳數(shù)均視為1 跳。在傳統(tǒng)DV?Hop 算法中，錨節(jié)點(diǎn)的平均跳距是根據(jù)錨節(jié)點(diǎn)之間的實(shí)際距離與兩者之間跳數(shù)的比值求得，監(jiān)測(cè)區(qū)域中的錨節(jié)點(diǎn)是隨機(jī)分布的，路徑不可能都是直線，錨節(jié)點(diǎn)之間的跳數(shù)越多，計(jì)算得到的平均跳距誤差越大。

在計(jì)算跳數(shù)時(shí)，通信范圍內(nèi)的跳數(shù)均視為1 跳。錨節(jié)點(diǎn)B和C都在錨節(jié)點(diǎn)A的通信范圍內(nèi)，傳統(tǒng)DV?Hop算法都按照1 跳距離計(jì)算A與B，A與C之間的跳數(shù)。但實(shí)際上錨節(jié)點(diǎn)B和C到錨節(jié)點(diǎn)A的跳數(shù)存在誤差，如圖1所示。

圖1 一跳距離示意圖

2）未知節(jié)點(diǎn)僅僅采用單一錨節(jié)點(diǎn)的平均跳距。在傳統(tǒng)DV?Hop 算法里，未知節(jié)點(diǎn)采用距離自身最近的錨節(jié)點(diǎn)的跳距作為平均跳距，求得兩者之間的距離，但是監(jiān)測(cè)區(qū)域里的節(jié)點(diǎn)是隨機(jī)分布的，距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)不能反映其他錨節(jié)點(diǎn)的分布情況。

2 改進(jìn)的DV?Hop 算法

2.1 可信錨節(jié)點(diǎn)選擇和跳數(shù)修正

針對(duì)1.4 節(jié)1）中誤差的原因，在計(jì)算錨節(jié)點(diǎn)平均跳距時(shí)選用可信度較高的錨節(jié)點(diǎn)，即選用共線度較高的錨節(jié)點(diǎn)。

式中：δ為理想平均跳距；dij為錨節(jié)點(diǎn)之間的實(shí)際距離；R為節(jié)點(diǎn)的通信半徑。錨節(jié)點(diǎn)計(jì)算自身平均跳數(shù)，如大于δ，則認(rèn)為在該路徑上錨節(jié)點(diǎn)之間的共線度較低，即可信度較低，如用來(lái)參與計(jì)算錨節(jié)點(diǎn)的平均跳距，會(huì)引起較大誤差，故刪除該錨節(jié)點(diǎn)。

采用文獻(xiàn)[11]中的方法對(duì)跳數(shù)進(jìn)行修正，分別引入最優(yōu)跳數(shù)值（hij）、實(shí)際偏差值（εij）和跳數(shù)因子（fij）修正跳數(shù)，具體定義如下：

修正后，錨節(jié)點(diǎn)間的跳數(shù)計(jì)算公式為：

因此，求解錨節(jié)點(diǎn)的平均跳距改為：

2.2 未知節(jié)點(diǎn)平均跳距的修正

針對(duì)1.4 節(jié)2）中存在的問(wèn)題，區(qū)別于傳統(tǒng)DV?Hop算法，采用滿足定位條件的錨節(jié)點(diǎn)的平均跳距誤差為權(quán)重，綜合求得未知節(jié)點(diǎn)的平均跳距。

式中errorij為錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j之間的距離誤差。平均距離誤差為：

式中：h_errori為錨節(jié)點(diǎn)i的平均距離誤差；M為錨節(jié)點(diǎn)i周?chē)^節(jié)點(diǎn)的數(shù)目。

錨節(jié)點(diǎn)i的權(quán)重為：

結(jié)合式（16），未知節(jié)點(diǎn)k的平均跳距為：

2.3 采用粒子群算法優(yōu)化未知節(jié)點(diǎn)位置

2.3.1 粒子群算法原理

粒子群優(yōu)化算法[11?13]是一種基于群體智能理論的模擬技術(shù)，其基本原理是：每個(gè)粒子視為可行解空間中的一個(gè)解，粒子具有初始位置和初始速度，粒子自由運(yùn)動(dòng)，通過(guò)式（18）和式（19）不斷更新自身速度和位置，直到迭代次數(shù)大于最大迭代次數(shù)或滿足一定誤差范圍，算法停止，從而得到最優(yōu)解。

式中：Vij(t+1)為粒子的速度，i為粒子個(gè)數(shù)，j為維數(shù)；ω為慣性權(quán)重；t為迭代次數(shù)；c1和c2分別表示自身學(xué)習(xí)能力和全局學(xué)習(xí)能力；γ1和γ2為[0，1]之間的隨機(jī)數(shù)。

2.3.2 算法實(shí)現(xiàn)步驟

1）初始化粒子速度、位置和數(shù)目，算法在初始階段，粒子的初始位置就是全局最優(yōu)位置。

2）計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)：

3）粒子與適應(yīng)度函數(shù)作比較，并通過(guò)式（18）和式（19）更新自身速度和位置。

4）當(dāng)達(dá)到最大迭代次數(shù)后，算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

采用Matlab R2015b 仿真平臺(tái)對(duì)本文改進(jìn)的算法進(jìn)行仿真，并與傳統(tǒng)DV?Hop 算法和DV?Hop+PSO 算法進(jìn)行對(duì)比。實(shí)驗(yàn)環(huán)境設(shè)置如下：仿真區(qū)域大小為100 m×100 m，隨機(jī)放置100 個(gè)傳感節(jié)點(diǎn)，其中錨節(jié)點(diǎn)的比例為8%，傳感節(jié)點(diǎn)的通信半徑為R=30 m。采用節(jié)點(diǎn)平均定位誤差errorave作為本次算法結(jié)果的評(píng)價(jià)標(biāo)準(zhǔn)。

網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布如圖2 所示，其中網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為100，錨節(jié)點(diǎn)數(shù)為8。

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布圖

圖3 表示錨節(jié)點(diǎn)數(shù)為8，節(jié)點(diǎn)傳輸半徑為30 m 時(shí)，本文改進(jìn)的DV?Hop 算法、傳統(tǒng)DV?Hop 算法和DV?Hop+PSO 算法的節(jié)點(diǎn)定位誤差，從圖3 中仿真結(jié)果看出，本文改進(jìn)的算法定位誤差相對(duì)較低。

圖3 仿真結(jié)果對(duì)比

1）不同錨節(jié)點(diǎn)數(shù)對(duì)定位的影響

圖4 表示錨節(jié)點(diǎn)數(shù)對(duì)節(jié)點(diǎn)平均定位誤差的影響，設(shè)置節(jié)點(diǎn)總數(shù)為100，節(jié)點(diǎn)傳輸半徑為30 m，錨節(jié)點(diǎn)數(shù)依次取10，15，20，25，30 時(shí)對(duì)平均定位誤差的影響。從仿真結(jié)果圖中可以看出，隨著錨節(jié)點(diǎn)數(shù)量的增加，節(jié)點(diǎn)的平均定位誤差在減小，定位精度在提高，說(shuō)明增加錨節(jié)點(diǎn)數(shù)量，能夠提高定位精度，也揭示了該算法依賴錨節(jié)點(diǎn)進(jìn)行定位的本質(zhì)。

圖4 錨節(jié)點(diǎn)數(shù)對(duì)定位的影響

2）不同通信半徑對(duì)定位的影響

圖5 表示在節(jié)點(diǎn)總數(shù)為100，錨節(jié)點(diǎn)數(shù)為10 時(shí)，通信半徑大小對(duì)節(jié)點(diǎn)定位的影響。從仿真結(jié)果看出，隨著節(jié)點(diǎn)通信半徑的增加，平均定位誤差在逐步減少，定位精度在提高。說(shuō)明通信半徑影響著節(jié)點(diǎn)之間的跳數(shù)，如果通信半徑設(shè)置的過(guò)小，導(dǎo)致很多節(jié)點(diǎn)之間無(wú)法通信，進(jìn)而無(wú)法完成定位工作；反之，則導(dǎo)致定位誤差增大。

圖5 通信半徑對(duì)定位的影響

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)DV?Hop 算法的不足，本文提出了一種改進(jìn)的DV?Hop 算法，通過(guò)仿真結(jié)果看出，改進(jìn)的算法在定位精度上優(yōu)于傳統(tǒng)DV?Hop 算法和DV?Hop+PSO 算法。但在網(wǎng)絡(luò)開(kāi)銷(xiāo)、PSO優(yōu)化上還存在不足，這也是后期研究的方向。