解姍姍，曾健民

（閩南理工學(xué)院 信息管理學(xué)院，福建 石獅 362700）

無線傳感器網(wǎng)絡(luò)（WSN）由某固定區(qū)域內(nèi)數(shù)量眾多的各種無線傳感節(jié)點(diǎn)組成，廣泛應(yīng)用于智慧醫(yī)療、環(huán)境監(jiān)控、物流管理和安防監(jiān)控等領(lǐng)域，是目前比較流行的無線網(wǎng)絡(luò)傳輸技術(shù)之一[1]。與適用于室外環(huán)境的GPS（全球定位系統(tǒng)）不同，無線傳感器網(wǎng)絡(luò)可以有效解決室內(nèi)定位問題．無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)需要完成數(shù)據(jù)采集、處理和通信的功能，因此傳感器節(jié)點(diǎn)的準(zhǔn)確定位對(duì)于無線傳感器網(wǎng)絡(luò)的應(yīng)用來說，具有重要的研究?jī)r(jià)值和意義[2-4]。

目前，主流的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法主要分為兩種：基于測(cè)距的算法和無需測(cè)距的算法[5]。基于測(cè)距（range-based）的定位算法是與距離相關(guān)的方案，采用測(cè)量接收信號(hào)強(qiáng)度指示(RSSI)、角度等信息來完成定位．雖然成本較高且能量消耗較大，但節(jié)點(diǎn)定位精確度更具優(yōu)勢(shì)。無需測(cè)距（range-free）的定位算法是與距離無關(guān)的方案，不需要測(cè)量距離，只需要通過節(jié)點(diǎn)間的距離就能夠估計(jì)未知節(jié)點(diǎn)的位置，比如使用跳躍數(shù)。該方法的硬件成本和能耗較低，具有較好的實(shí)用性[6]。

作為WSN中一種無需測(cè)距（range-free）的定位算法，DV-Hop定位算法具有易于實(shí)現(xiàn)、成本低的優(yōu)點(diǎn)，成為了目前研究的主流方向。文獻(xiàn)[7]提出了一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop三維定位算法，該算法設(shè)置跳躍的閾值參數(shù)以降低第一階段的通信成本，并且使用可選的平均跳躍大小而不是第二階段中的固定平均跳躍大小來計(jì)算未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的距離。群智能優(yōu)化算法作為一種人工模仿動(dòng)物群體生活習(xí)性的仿生技術(shù)，在優(yōu)化方面具有較大的應(yīng)用前景。例如，粒子群優(yōu)化算法（PSO）作為群智優(yōu)化的重要方法之一，能夠模擬簡(jiǎn)單群落中個(gè)體以及個(gè)體之間的互動(dòng)行為來搜索全局最優(yōu)解[8]。利用這個(gè)特性，文獻(xiàn)[9]提出了基于PSO的DV-Hop定位算法（PSODV-Hop）。但是，PSO算法易發(fā)生“早熟”現(xiàn)象，從而無法在在迭代后期保持種群的多樣性，不利于提高節(jié)點(diǎn)定位的精度。

因此，在以上研究的基礎(chǔ)上，本文提出了一種基于差異演化粒子群的WSN DV-Hop節(jié)點(diǎn)定位算法。首先通過引入差異演化計(jì)算的變異、交叉及選擇過程，對(duì)傳統(tǒng)粒子群優(yōu)化算法進(jìn)行了改進(jìn)，維持了種群的多樣性，從而提高了算法的全局搜索能力。然后，采用改進(jìn)的粒子群優(yōu)化算法對(duì) DV-Hop進(jìn)行了優(yōu)化計(jì)算并給出了具體流程。仿真實(shí)驗(yàn)結(jié)果顯示，與傳統(tǒng)DV-Hop算法和某些現(xiàn)有的改進(jìn)算法，相比提出的改進(jìn)DV-Hop定位算法能夠有效提升網(wǎng)絡(luò)中節(jié)點(diǎn)定位的精度和穩(wěn)定度。

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

DV-Hop算法的關(guān)鍵是計(jì)算距離矢量跳數(shù)，并采用平均每跳距離和跳數(shù)（未知節(jié)點(diǎn)到參考節(jié)點(diǎn)之間）的乘積，表示未知節(jié)點(diǎn)到參考節(jié)點(diǎn)之間的距離。典型DV-Hop定位算法的主要過程包括[10]：

（1）距離矢量交換

每個(gè)錨節(jié)點(diǎn)i通過網(wǎng)絡(luò)傳送一個(gè)信標(biāo)數(shù)據(jù)包，包含自身ID，坐標(biāo)和初始化為0的跳數(shù)，并計(jì)算未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)之間的最小跳數(shù)。

（2）校正值的計(jì)算及廣播

在錨節(jié)點(diǎn)i獲得了到其他錨節(jié)點(diǎn)的最小跳數(shù)之后，從它的角度來計(jì)算每跳的平均距離，表示為HopSizei，通過以下方程得到：

其中：M表示參考節(jié)點(diǎn)（錨節(jié)點(diǎn)）的數(shù)量；hij為兩個(gè)錨節(jié)點(diǎn)i和j之間的跳數(shù)；(xi，xj)和(yi-yj)分別為兩個(gè)錨節(jié)點(diǎn)i和j的坐標(biāo)。

（3） 定位計(jì)算

每個(gè)未知節(jié)點(diǎn)可以通過公式（1）計(jì)算出自身到各錨節(jié)點(diǎn)i的距離為：

根據(jù)DV-Hop定位算法的主要過程可知，簡(jiǎn)單的平均每跳距離估算會(huì)在很大程度降低DV-Hop算法的定位精度。原因是在未知節(jié)點(diǎn)與參考節(jié)點(diǎn)之間的距離估計(jì)時(shí)，采用平均每跳距離和跳數(shù)的乘積。如圖1所示,當(dāng)傳感器節(jié)點(diǎn)分布狀態(tài)比較稀疏時(shí),傳感器節(jié)點(diǎn)之間的多跳路徑不是直線,因此DV-Hop定位算法計(jì)算出的距離會(huì)出現(xiàn)較大的累積誤差。

2 PSO算法原理

粒子群算法是在1995年由Dr.Kennedy and Dr.Eberhart提出，是基于群體的隨機(jī)優(yōu)化法[11]。 設(shè) W=（w1，w2，…，wn）表示S維空間內(nèi)n個(gè)粒子構(gòu)成的種群，Wi=（wi1，wi2，…，win）T表示第 i粒子的一個(gè) S 維向量，其速度表示為 Vi=（Vi1，Vi2，…，Vis）T，在迭代計(jì)算步驟中，尋找兩個(gè)粒子，前一個(gè)粒子為找到其自身最優(yōu)解，也就是說是其個(gè)體極值，表示為Pi=（Pi1，Pi2，…，Pis）T；后者即為現(xiàn)階段種族的最優(yōu)解，也就是全局最優(yōu)解，表示為 Pg=（Pg1，Pg2，…，Pgs）T。

利用種族最優(yōu)解和自身，粒子更新本身的位置和速度，其公式如下：

圖1 節(jié)點(diǎn)分布對(duì)路徑選擇的影響

其中：d=1,2，…，S；i=1,2，…，n；k 表示迭代次數(shù)；φ1=c1r1，φ2=c2r2，c1和 c2表示學(xué)習(xí)因子，一般 c1和 c2相等，且取值范圍在 0～4之間最佳；r1和r2表示兩個(gè)隨機(jī)數(shù)，分布范圍為[0,1]；mbest表示種群中平均最優(yōu)數(shù)值；γ表示擴(kuò)張調(diào)節(jié)因子，能夠調(diào)節(jié)收斂速度；u和τ表示兩個(gè)隨機(jī)數(shù)，取值范圍為（0,1）。

PSO算法實(shí)現(xiàn)的一般步驟為：

步驟1）粒子群初始化；

步驟2）評(píng)估每個(gè)粒子的空間優(yōu)化函數(shù)的適用值；

步驟3）局部最優(yōu)值和整體最優(yōu)值更新；

步驟4）群體粒子的速度與位置更新，并計(jì)算它們的適應(yīng)度值；分別根據(jù)如下公式（7）和（8）更新群體中粒子的速度Vi和位置Xi，每個(gè)粒子保存其在搜索空間找到的最佳定位。

步驟5）進(jìn)行循環(huán)條件判斷，滿足迭代終止條件 （最優(yōu)的適用值或是最大迭代次數(shù)）的話就結(jié)束；否則，跳轉(zhuǎn)到步驟2，繼續(xù)循環(huán)收斂。粒子群算法抽象概念圖如圖2所示。

3 基于改進(jìn)PSO優(yōu)化的DV-Hop定位算法

3.1 基于差異演化的改進(jìn)PSO算法

圖2 粒子群算法抽象概念

本文通過引入差異演化算法的變異、交叉及選擇過程對(duì)PSO算法進(jìn)行改進(jìn)，以便避免粒子出現(xiàn)“早熟”現(xiàn)象。變異、交叉及選擇的實(shí)施過程如下[12]：

（1）生成初始種群

在n維空間按照公式（9）隨機(jī)生成M個(gè)個(gè)體。

其中，rand（0,1）表示一個(gè)取值范圍為[0,1]的隨機(jī)數(shù)，和分別為個(gè)體的上界和下界。

（2）變異操作

差異演化的核心操作就是變異過程，該過程能夠從取值空間中隨機(jī)選擇3個(gè)個(gè)體xp1，xp2，xp3，且p1≠p2≠p3≠i，則變異個(gè)體 hij（g）的表示方式如式（10）：

其中，F(xiàn)表示縮放因子，取值范圍為[0，2]，Tmax為最大進(jìn)化代數(shù)。

（3）交叉操作

交叉操作最終目的是提高取值空間中適用解的多樣性，具體方法如下：

其中，CR表示交叉概率，其取值范圍為[0，1]，rand(1,n)表示一個(gè)取值范圍為[0，n]的隨機(jī)數(shù)。

(4)選擇操作

按照如式(12)更新目標(biāo)個(gè)體 xij（g）。

其中f為適應(yīng)度函數(shù)。在DV-Hop節(jié)點(diǎn)定位時(shí)，按照如下方程組計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離。

其中，di表示未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的測(cè)量距離。DVHop定位求解過程的節(jié)點(diǎn)坐標(biāo)，就是適應(yīng)度函數(shù)f的零極小值點(diǎn)。

在本文提出的基于差異演化的改進(jìn)PSO算法中，根據(jù)差異演化算法中的公式(10)、(11)和(12)對(duì)每個(gè)粒子的歷史最佳位置Pid進(jìn)行變異，并更新此時(shí)的群體歷史最佳位置Pgd。然后再重新執(zhí)行PSO算法步驟中的步驟2。改進(jìn)PSO算法的流程如圖3所示。

圖3 改進(jìn)PSO算法的流程圖

3.2 定位算法流程

通過改進(jìn)PSO算法對(duì)定位節(jié)點(diǎn)進(jìn)行優(yōu)化的過程如圖4所示。

4 仿真實(shí)驗(yàn)的結(jié)果與討論

4.1 仿真實(shí)驗(yàn)的條件

為了對(duì)本文提出的WSN DV-Hop節(jié)點(diǎn)定位方法進(jìn)行驗(yàn)證和分析，進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)硬件環(huán)境為： Intel(R)Core(TM)i7 CPU(@3.60 GHz)，8 GB內(nèi)存.實(shí)驗(yàn)軟件環(huán)境為：Windows 10操作系統(tǒng)，Matlab7.0仿真軟件。

在仿真實(shí)驗(yàn)中，所有節(jié)點(diǎn)包括錨節(jié)點(diǎn)和未知節(jié)點(diǎn)均隨機(jī)分布在100 m×100 m的網(wǎng)絡(luò)區(qū)域內(nèi)，沒有任何障礙和干擾.WSN網(wǎng)絡(luò)的部署結(jié)構(gòu)如圖5所示，仿真實(shí)驗(yàn)參數(shù)如表1所示。

圖4 定位算法的流程圖

圖5 WSN網(wǎng)絡(luò)的部署結(jié)構(gòu)

表1 WSN仿真參數(shù)

4.2 評(píng)估指標(biāo)

為了對(duì)得出的數(shù)值結(jié)果進(jìn)行統(tǒng)計(jì)平均，仿真實(shí)驗(yàn)重復(fù)實(shí)施了300次，并計(jì)算定位誤差的平均值。設(shè)一次仿真時(shí)，未知節(jié)點(diǎn)i的距離測(cè)量誤差為Eij，則：

其中，N表示未知節(jié)點(diǎn)的數(shù)量。定位誤差越大則定位準(zhǔn)確性越低．則對(duì)半徑歸一化的平均定位誤差[12]為：

其中R為WSN網(wǎng)絡(luò)中的信號(hào)傳輸半徑。

4.3 結(jié)果與討論

當(dāng)WSN網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)量和通信半徑固定（節(jié)點(diǎn)數(shù)量=100，節(jié)點(diǎn)通信半徑=25 m），錨節(jié)點(diǎn)數(shù)目變化時(shí)本文提出算法和典型DV-Hop算法[10]、PSO-DV-Hop算法[9]的平均定位誤差，如圖6所示。從圖6可以看出，3種定位算法的平均定位誤差均隨著錨節(jié)點(diǎn)數(shù)量的增加而不斷減少。但是，在相同錨節(jié)點(diǎn)數(shù)量情況下，相較于典型DV-Hop算法和PSO-DV-Hop算法，提出算法的平均定位誤差值最小。當(dāng)錨節(jié)點(diǎn)數(shù)為50時(shí)，提出算法的精確達(dá) 3.2 m。

當(dāng)圖節(jié)點(diǎn)通信半徑不斷增大時(shí) （R=20，25，30 m），本文提出算法和典型DV-Hop算法、PSO-DV-Hop算法[9]的歸一化平均定位誤差如圖7所示。從圖7可以看出，隨著通信半徑的不斷增加，三種定位算法的定位誤差均隨之減小。此外，在相同通信半徑的情況下，三種定位算法的歸一化平均定位誤差均隨著錨節(jié)點(diǎn)占節(jié)點(diǎn)總數(shù)的比例的增加而不斷減少。但是，相較于其他兩種法，提出算法的歸一化平均定位誤差值最小。

圖6 不同錨節(jié)點(diǎn)數(shù)目的定位誤差對(duì)比

圖7 不同通信半徑的定位誤差對(duì)比

根據(jù)以上仿真實(shí)驗(yàn)結(jié)果可以得出：在相同的WSN網(wǎng)絡(luò)環(huán)境參數(shù)條件下，提出改進(jìn)算法能夠有效提高WSN網(wǎng)絡(luò)的定位精度，并保持一定給的穩(wěn)定性。

5 結(jié)論

提出了一種基于差異演化粒子群的WSN DV-Hop節(jié)點(diǎn)定位算法。首先通過引入差異演化計(jì)算的變異、交叉及選擇過程，對(duì)傳統(tǒng)粒子群優(yōu)化算法進(jìn)行了改進(jìn)，維持了種群的多樣性，從而提高了算法的全局搜索能力．然后，采用改進(jìn)的粒子群優(yōu)化算法對(duì) DV-Hop進(jìn)行了優(yōu)化計(jì)算并給出了具體流程。仿真實(shí)驗(yàn)結(jié)果顯示，與傳統(tǒng)DV-Hop算法和某些現(xiàn)有的改進(jìn)算法，相比提出的改進(jìn)DV-Hop定位算法能夠有效提升網(wǎng)絡(luò)中節(jié)點(diǎn)定位的精度和穩(wěn)定度，具有一定的參考價(jià)值。