粒子群離散算法在無線傳感網(wǎng)絡(luò)中的應(yīng)用*

李 鋒

(廣東交通職業(yè)技術(shù)學(xué)院，廣東 廣州510650)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)由大量傳感節(jié)點以多跳自組織方式構(gòu)成，通過數(shù)據(jù)采集、協(xié)調(diào)感知完成信息搜集和管理任務(wù)。無線傳感器網(wǎng)絡(luò)一般應(yīng)用于惡劣環(huán)境或是人無法抵達區(qū)域，受鋪設(shè)成本和能源供給限制，只有少數(shù)匯聚節(jié)點配備GPS定位裝置，通過與網(wǎng)絡(luò)其他傳感器節(jié)點接力通信完成對其定位過程。典型的WSN由傳感器節(jié)點、匯聚節(jié)點和管理節(jié)點組成，如圖1所示。傳感器節(jié)點感知目標信息后以多跳接力方式傳給匯聚節(jié)點，匯聚節(jié)點對附近傳感器節(jié)點信息匯總后通過衛(wèi)星基站、互聯(lián)網(wǎng)傳送給管理用戶[1]。由于傳感器節(jié)點一般可移動部署以適應(yīng)環(huán)境變化，如何精確定位傳感器節(jié)點坐標成為WSN研究的熱點和難點。

圖1 WSN體系結(jié)構(gòu)

1 WSN定位算法分類

無線傳感器網(wǎng)絡(luò)節(jié)點定位算法分為基于測距和無需測距算法兩類[2]。對于大部分傳感節(jié)點而言，當定位誤差小于節(jié)點通信半徑的40%時，定位誤差對節(jié)點精確度的影響不大[2]。若使用測距定位不僅要配備額外硬件設(shè)備，增加節(jié)點成本，還會加重電源補給負荷。無需測距算法通過節(jié)點之間通信估算彼此之間距離、定位節(jié)點坐標，簡單方便，得到廣泛應(yīng)用。其中最為經(jīng)典的是DVHop算法。

2 DV-Hop算法

DV-Hop稱為距離向量跳段定位算法，用網(wǎng)絡(luò)平均跳距和節(jié)點間最短跳數(shù)乘積表示節(jié)點之間距離，再利用大量冗余信息節(jié)點實現(xiàn)定位。整個過程分為3個階段：

(1)計算抵達鄰居節(jié)點跳數(shù)。傳感節(jié)點定期向鄰居節(jié)點交換抵達網(wǎng)絡(luò)中其他節(jié)點距離，以跳數(shù)為單位。最終每個傳感節(jié)點{xi，yi}都獲得自身參考節(jié)點跳數(shù) hi及參考坐標{xi，yi，hi}。

(2)每個傳感節(jié)點使用式(1)計算到達其他參考節(jié)點的距離。

(3)傳感節(jié)點得到與其他參考節(jié)點距離后，通過三角或多邊測量建立方程組，最后利用最小二乘法求解方程組獲得節(jié)點坐標。

DV-Hop實現(xiàn)簡單、方便快捷，但算法中的距離通過節(jié)點跳數(shù)乘以網(wǎng)絡(luò)平均跳距得出[3]，不可避免地存在誤差，加上最小二乘法求解精度依賴于網(wǎng)絡(luò)跳距初始參數(shù)，導(dǎo)致產(chǎn)生的誤差呈指數(shù)增長、定位精度不高，并且節(jié)點密度越低，拓撲越不規(guī)則，誤差越大。

3 基于粒子群定位算法思想

傳 感 節(jié) 點 記 為 P1(x1，y1)，P2(x2，y2)， … ，Pn(xn，yn)，根據(jù)DV-Hop前兩階段估算的抵達網(wǎng)絡(luò)其他節(jié)點距離分別是d1，d2…，dn，估算距離與真實距離之間差值分別為ε1，ε2，…，εn，得以下方程組：

傳 感 節(jié) 點 坐 標 (x?，y?)應(yīng) 同 時 滿 足 式 (2)方 程 組 要 求 ，若|ε1|+|ε2|+…+|εn|和 越 小 ，則 節(jié) 點(x?，y?)坐 標 越 優(yōu) 、 定 位越精確，從而可利用最小二乘法求解過程轉(zhuǎn)換為使用粒子群算法求解全局最小最優(yōu)解的問題，如式(3)所示。

本文提出將粒子群(PSO)離散算法替代DV-Hop中的最小二乘法，用于求解節(jié)點最優(yōu)坐標，既可以發(fā)揮PSO全局搜索能力，又可以避免標準PSO算法中過早收斂問題，由此減小網(wǎng)絡(luò)跳距誤差對定位精度的影響范圍。

4 標準粒子群算法

粒子群算法是基于鳥類群體行為研究的模擬算法。鳥群在封閉空間隨機搜索食物，并且在這個空間只有一個全局最優(yōu)值[4]。假如所有鳥只都知道當前位置與搜索食物之間的距離，那么找到全局最優(yōu)解的最優(yōu)方案就是從身邊最近的鳥周圍區(qū)域進行搜尋[5]。在粒子群算法中，尋找最優(yōu)問題的每個解對應(yīng)搜索空間的每只鳥，稱為粒子。每個粒子的初始化向量代表鳥的飛行位置和速率，每個粒子通過尋找附近粒子迭代搜尋最優(yōu)解，具體算法如下：

假設(shè)在一個d維搜索空間中，有n個粒子組成的粒子群 X=(X1，X2，…，Xn)T，其中第 i個粒子位置為 Xi=(Xi1，Xi2，…，XiD)T，速率為 Vi=(Vi1，Vi2，…，Vid)T，極值為 Pi=(Pi1，Pi2，…，Pid)T，種群全局極 值為 Pg=(Pg1，Pg2，…，Pgd)T，每個粒子找到下一粒子后按以下公式更新當前位置和速率[6]：

5 新算法定位模型

5.1 離散粒子群算法

粒子群算法前期收斂速率快，但容易出現(xiàn)前期局部最優(yōu)、后期收斂緩慢的問題。改進離散粒子群算法在于更新粒子當前位置和速率前引入離散運動方程式：

5.2 新算法適應(yīng)度值選擇

新算法通過估計的距離與真實距離之間的差值ε1+ε2+…+εn之和判斷粒子所處位置優(yōu)劣，以此確定是否符合全局最優(yōu)解要求。差值之和越小，適應(yīng)度值越大。求解適應(yīng)度公式為：

其中，n為傳感節(jié)點數(shù)量；hi為傳感節(jié)點抵達網(wǎng)絡(luò)其他節(jié)點跳數(shù)，由DV-Hop算法第一階段獲得。由于傳感節(jié)點跳數(shù)越多，誤差累積越大，因此在計算適應(yīng)度時加入權(quán)重，hi越大的傳感節(jié)點對適應(yīng)值影響越小。

5.3 新算法粒子聚集度

在標準PSO算法中，兩個粒子之間的距離表示其相似程度大小，距離越近相似度越高。新算法用s(i，j)表示粒子i和粒子j之間的相似度，滿足以下條件：

其中，d(i，j)為粒子 i和粒子 j之間的距離，dmin、dmax表示所有粒子之間距離的最小值和最大值。隨著迭代次數(shù)增多，粒子適應(yīng)度越大，與最優(yōu)粒子相似度越高，位置越趨于全局最優(yōu)解，最終聚集在一起。新算法聚集度為：

其中，C(t)是粒子群經(jīng)t次迭代的聚集度，m為種群規(guī)模。種群聚集度最密的粒子群收斂于當前全局最優(yōu)解。

5.4 新算法定位流程

新算法采用改進PSO離散算法替代DV-Hop算法中第3階段的最小二乘法，利用離散PSO迭代求解避免網(wǎng)絡(luò)跳距誤差對定位精度帶來的影響，并得到3個全局體極值的幾何質(zhì)心解，最后計算傳感節(jié)點坐標。具體步驟如下。

(1)基于DV-Hop算法第1階段和第2階段，傳感節(jié)點間通過與鄰居節(jié)點通信獲得自身參考坐標{xi，yi，hi}，并計算抵達網(wǎng)絡(luò)其他節(jié)點距離。

(2)根據(jù)網(wǎng)絡(luò)節(jié)點規(guī)模和區(qū)域大小初始化種群，計算每個粒子適應(yīng)度，每個粒子位置都是節(jié)點定位坐標的可行解。

(3)根據(jù)適應(yīng)度大小更新粒子個體極值，同時找出全局適應(yīng)度最好的3個個體極值保存在近優(yōu)解集合中。

(4)根據(jù)粒子速率利用離散運動方程式(7)對粒子群狀態(tài)進行躍遷，避免算法過早收斂。

(5)根據(jù)式(4)重新計算粒子當前位置和速率。

(6)根據(jù)式(9)計算每個粒子與全局近優(yōu)解相似度，并根據(jù)式(10)計算當前迭代種群的聚集度。

(7)判斷是否滿足結(jié)束條件（達到最大迭代次數(shù)或保存近優(yōu)數(shù)組中的3個個體極值都達到最優(yōu)要求)，結(jié)束迭代循環(huán)，獲得3個全局體極值坐標，否則跳到步驟(3)。

(8)通過極值幾何質(zhì)心坐標計算定位傳感節(jié)點位置。

6 仿真測試

6.1 仿真環(huán)境

仿真環(huán)境設(shè)為100 m×100 m二維區(qū)域，節(jié)點通信半徑為20 m，傳感節(jié)點比例為80%，初始化粒子群規(guī)模200，最大迭代次數(shù) 500，慣性權(quán)重 Wmax=0.9，Wmin=0.4，平均定位誤差評價為：

6.2 定位誤差分析

新算法用 PSO離散（DPSO）算法替代 DV-Hop中的最小二乘法以計算節(jié)點坐標，減小DV-Hop網(wǎng)絡(luò)跳距誤差對定位精度的影響。在相同網(wǎng)絡(luò)環(huán)境下，新算法在測距誤差為 20%的定位誤差明顯小于DV-Hop算法，如圖2所示。

圖2 測距誤差為 20%的定位誤差圖

6.3 標準偏差分析

在測距誤差逐漸增加時，開始兩種算法定位標準偏差都有所增長，但新算法相比DV-Hop中的標準偏差增長更為緩慢，如圖3所示。因為新算法誤差增長受節(jié)點平均距離誤差影響，而DV-Hop算法誤差激增是由于最小二乘法對節(jié)點平均距離誤差放大的結(jié)果。當新算法測距誤差增長到10%時，標準偏差開始降低，這是由于在計算適應(yīng)度時加入權(quán)重，hi越大的傳感節(jié)點對適應(yīng)值影響越小，節(jié)點平均距離誤差隨節(jié)點距離增長影響越弱，最大測距標準偏差收斂于2 m以內(nèi)，可見新算法在定位平均測距誤差較大的情況下更具優(yōu)勢。

圖3 平均偏差比較圖

6.4 收斂性分析

圖4 收斂性分析圖

與標準PSO算法相比，兩種算法定位誤差都隨迭代次數(shù)增多而減小，如圖4所示。在迭代次數(shù)較少時兩種算法誤差較大，這是因為粒子群初始化過程中粒子分布隨機性造成的。標準PSO算法在迭代次數(shù)達到100時，曲線趨于平穩(wěn)，定位誤差起伏不大，算法開始收斂，但定位誤差明顯大于新算法，由此推斷算法過早收斂陷入局部最優(yōu)解。而新算法在迭代次數(shù)達到120時，定位誤差才接近最優(yōu)解，最終定位誤差收斂于2 m以內(nèi)，這與圖3實驗數(shù)據(jù)一致。

本文采用粒子群離散算法替代DV-Hop算法中的最小二乘法，避免網(wǎng)絡(luò)跳距估計誤差對定位精度帶來的影響。接下來的工作將著眼于減少算法復(fù)雜度，降低無線傳感網(wǎng)絡(luò)能耗問題，以減少實際部署中對環(huán)境的依賴程度。

[1]NICULESCU D.Localized positioning in ad-hoc networks[J].IEEE International Workshop on Sensor Network Protocols and Applications，2003，1(2)：42-50.

[2]PATWARI N.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing，2003，51(8)：2137-2148.

[3]RANDOLPH.A self-localization method for wireless sensor networks[J].EURASIP Journal on Applied Signal Processing，2003(4)：348-358.

[4]LANGENDOEN K.Distributed localization in wireless sensor networks[J].Computer Networks.2003，43(4)：499-518.

[5]GUSTAFSSON F.Mobile positioning using wireless networks[J].IEEE Signal Processing Magazine，2005，22(4)：41-53.

[6]YEDAVALLI K.Sequence-based localization in wireless sensor networks[J].IEEE Transactions on Mobile Computing，2008，7(1)：81-94.