摘 要： 無線傳感器網絡通過少數確定錨節點計算到其他節點距離，確定節點坐標。其中DV-Hop定位算法通過最小二乘法求解坐標，累計誤差隨節點平均距離誤差呈指數增長，定位精度較低。提出了用粒子群PSO離散算法替代DV-Hop中的最小二乘法, 既發揮PSO全局搜索能力，又避免標準PSO算法過早收斂的問題。實驗結果表明，新算法定位精度很高，受距離誤差影響不大，能很好地應用于無線傳感器網絡的定位過程。
關鍵詞： 無線傳感器網絡；粒子群；DV-Hop定位算法；離散算法
無線傳感器網絡WSN(Wireless Sensor Networks)由大量傳感節點以多跳自組織方式構成，通過數據采集、協調感知完成信息搜集和管理任務。無線傳感器網絡一般應用于惡劣環境或是人無法抵達區域，受鋪設成本和能源供給限制，只有少數匯聚節點配備GPS定位裝置，通過與網絡其他傳感器節點接力通信完成對其定位過程。典型的WSN由傳感器節點、匯聚節點和管理節點組成，如圖1所示。傳感器節點感知目標信息后以多跳接力方式傳給匯聚節點，匯聚節點對附近傳感器節點信息匯總后通過衛星基站、互聯網傳送給管理用戶[1]。由于傳感器節點一般可移動部署以適應環境變化，如何精確定位傳感器節點坐標成為WSN研究的熱點和難點。
1 WSN定位算法分類
無線傳感器網絡節點定位算法分為基于測距和無需測距算法兩類[2]。對于大部分傳感節點而言，當定位誤差小于節點通信半徑的40%時，定位誤差對節點精確度的影響不大[2]。若使用測距定位不僅要配備額外硬件設備，增加節點成本，還會加重電源補給負荷。無需測距算法通過節點之間通信估算彼此之間距離、定位節點坐標，簡單方便，得到廣泛應用。其中最為經典的是DV-Hop算法。
2 DV-Hop算法
DV-Hop稱為距離向量跳段定位算法，用網絡平均跳距和節點間最短跳數乘積表示節點之間距離，再利用大量冗余信息節點實現定位。整個過程分為3個階段：
(1)計算抵達鄰居節點跳數。傳感節點定期向鄰居節點交換抵達網絡中其他節點距離，以跳數為單位。最終每個傳感節點{xi，yi}都獲得自身參考節點跳數hi及參考坐標{xi，yi，hi}。
(2)每個傳感節點使用式(1)計算到達其他參考節點的距離。
(3)傳感節點得到與其他參考節點距離后，通過三角或多邊測量建立方程組，最后利用最小二乘法求解方程組獲得節點坐標。
DV-Hop實現簡單、方便快捷，但算法中的距離通過節點跳數乘以網絡平均跳距得出[3]，不可避免地存在誤差，加上最小二乘法求解精度依賴于網絡跳距初始參數，導致產生的誤差呈指數增長、定位精度不高，并且節點密度越低，拓撲越不規則，誤差越大。
3 基于粒子群定位算法思想
傳感節點記為P1(x1，y1)，P2(x2，y2)，…，Pn(xn，yn)，根據DV-Hop前兩階段估算的抵達網絡其他節點距離分別是d1，d2…，dn，估算距離與真實距離之間差值分別為ε1，ε2，…，εn，得以下方程組：
傳感節點坐標應同時滿足式(2)方程組要求，若|ε1|+|ε2|+…+|εn|和越小，則節點坐標越優、定位越精確，從而可利用最小二乘法求解過程轉換為使用粒子群算法求解全局最小最優解的問題，如式(3)所示。
本文提出將粒子群(PSO)離散算法替代DV-Hop中的最小二乘法，用于求解節點最優坐標，既可以發揮PSO全局搜索能力，又可以避免標準PSO算法中過早收斂問題，由此減小網絡跳距誤差對定位精度的影響范圍。
4 標準粒子群算法
粒子群算法是基于鳥類群體行為研究的模擬算法。鳥群在封閉空間隨機搜索食物，并且在這個空間只有一個全局最優值[4]。假如所有鳥只都知道當前位置與搜索食物之間的距離，那么找到全局最優解的最優方案就是從身邊最近的鳥周圍區域進行搜尋[5]。在粒子群算法中，尋找最優問題的每個解對應搜索空間的每只鳥，稱為粒子。每個粒子的初始化向量代表鳥的飛行位置和速率，每個粒子通過尋找附近粒子迭代搜尋最優解，具體算法如下：
假設在一個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]：
其中，k表示迭代次數，c1、c2為加速系數，rand是[0，1]區間選取的隨機數，p是第i個粒子的個體極值在第d維的分量，p是群體全局極值在第d維的分量，x、v分別是第i個粒子經k次迭代后的第d維位置和速率，w是粒子保持運動慣性權重。粒子通過不斷更新當前位置和速率最終找到全局最優解，完成搜索過程。
5 新算法定位模型
5.1 離散粒子群算法
粒子群算法前期收斂速率快，但容易出現前期局部最優、后期收斂緩慢的問題。改進離散粒子群算法在于更新粒子當前位置和速率前引入離散運動方程式：
d維分量。粒子的位置只有“0”、“1”兩種狀態，速率越小，粒子取“0”幾率越大，反之取“1”。改進離散粒子群算法使得函數sig(V)不會過于接近“0”或“1”，保證算法以一定概率從一種狀態躍遷到另一種狀態，從而避免算法過早收斂，出現局部最優現象。
5.2 新算法適應度值選擇
新算法通過估計的距離與真實距離之間的差值ε1+ε2+…+εn之和判斷粒子所處位置優劣，以此確定是否符合全局最優解要求。差值之和越小，適應度值越大。求解適應度公式為：
其中，n為傳感節點數量；hi為傳感節點抵達網絡其他節點跳數，由DV-Hop算法第一階段獲得。由于傳感節點跳數越多，誤差累積越大，因此在計算適應度時加入權重，hi越大的傳感節點對適應值影響越小。
5.3 新算法粒子聚集度
在標準PSO算法中，兩個粒子之間的距離表示其相似程度大小，距離越近相似度越高。新算法用s(i，j)表示粒子i和粒子j之間的相似度，滿足以下條件：
其中，d(i，j)為粒子i和粒子j之間的距離，dmin、dmax表示所有粒子之間距離的最小值和最大值。隨著迭代次數增多，粒子適應度越大，與最優粒子相似度越高，位置越趨于全局最優解，最終聚集在一起。新算法聚集度為：
其中，C(t)是粒子群經t次迭代的聚集度，m為種群規模。種群聚集度最密的粒子群收斂于當前全局最優解。
5.4 新算法定位流程
新算法采用改進PSO離散算法替代DV-Hop算法中第3階段的最小二乘法，利用離散PSO迭代求解避免網絡跳距誤差對定位精度帶來的影響，并得到3個全局體極值的幾何質心解，最后計算傳感節點坐標。具體步驟如下。
(1)基于DV-Hop算法第1階段和第2階段，傳感節點間通過與鄰居節點通信獲得自身參考坐標{xi，yi，hi}，并計算抵達網絡其他節點距離。
(2)根據網絡節點規模和區域大小初始化種群，計算每個粒子適應度，每個粒子位置都是節點定位坐標的可行解。
(3)根據適應度大小更新粒子個體極值，同時找出全局適應度最好的3個個體極值保存在近優解集合中。
(4)根據粒子速率利用離散運動方程式(7)對粒子群狀態進行躍遷，避免算法過早收斂。
(5)根據式(4)重新計算粒子當前位置和速率。
(6)根據式(9)計算每個粒子與全局近優解相似度，并根據式(10)計算當前迭代種群的聚集度。
(7)判斷是否滿足結束條件（達到最大迭代次數或保存近優數組中的3個個體極值都達到最優要求)，結束迭代循環，獲得3個全局體極值坐標，否則跳到步驟(3)。
(8)通過極值幾何質心坐標計算定位傳感節點位置。
6 仿真測試
6.1 仿真環境
仿真環境設為100 m×100 m二維區域，節點通信半徑為20 m，傳感節點比例為80%，初始化粒子群規模200，最大迭代次數500，慣性權重Wmax=0.9，Wmin=0.4，平均定位誤差評價為：
6.2 定位誤差分析
新算法用PSO離散（DPSO）算法替代DV-Hop中的最小二乘法以計算節點坐標，減小DV-Hop網絡跳距誤差對定位精度的影響。在相同網絡環境下，新算法在測距誤差為 20%的定位誤差明顯小于DV-Hop算法，如圖2所示。
6.3 標準偏差分析
在測距誤差逐漸增加時，開始兩種算法定位標準偏差都有所增長，但新算法相比DV-Hop中的標準偏差增長更為緩慢，如圖3所示。因為新算法誤差增長受節點平均距離誤差影響，而DV-Hop算法誤差激增是由于最小二乘法對節點平均距離誤差放大的結果。當新算法測距誤差增長到10%時，標準偏差開始降低，這是由于在計算適應度時加入權重，hi越大的傳感節點對適應值影響越小，節點平均距離誤差隨節點距離增長影響越弱，最大測距標準偏差收斂于2 m以內，可見新算法在定位平均測距誤差較大的情況下更具優勢。
6.4 收斂性分析
與標準PSO算法相比，兩種算法定位誤差都隨迭代次數增多而減小，如圖4所示。在迭代次數較少時兩種算法誤差較大，這是因為粒子群初始化過程中粒子分布隨機性造成的。標準PSO算法在迭代次數達到100時，曲線趨于平穩，定位誤差起伏不大，算法開始收斂，但定位誤差明顯大于新算法，由此推斷算法過早收斂陷入局部最優解。而新算法在迭代次數達到120時，定位誤差才接近最優解，最終定位誤差收斂于2 m以內，這與圖3實驗數據一致。
本文采用粒子群離散算法替代DV-Hop算法中的最小二乘法，避免網絡跳距估計誤差對定位精度帶來的影響。接下來的工作將著眼于減少算法復雜度，降低無線傳感網絡能耗問題，以減少實際部署中對環境的依賴程度。
參考文獻
[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 sensornetworks[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.