周 濤 蔣占軍 路宇挺 楊永紅

(蘭州交通大學電子與信息工程學院 甘肅 蘭州 730070)

0 引 言

節(jié)點定位技術是無線傳感器網(wǎng)絡(Wireless Sensor Networks，WSN)的關鍵支撐技術之一，其基本思想是在目標區(qū)域內(nèi)已知信標節(jié)點信息的基礎上，通過一定的定位算法獲取未知節(jié)點的信息[1]。該技術廣泛應用于軍事偵查、石油管道泄露監(jiān)測、地震救災等諸多領域的事件監(jiān)測系統(tǒng)中，是社會生產(chǎn)信息化進程中重要的組成部分。

WSN中的節(jié)點定位算法通常分為兩類，分別是基于測距(range-based)和非測距(range-free)[2]。其中，基于測距的定位算法是利用工具儀器測量得到已知節(jié)點與待測節(jié)點之間的位置與角度信息，進而通過距離運算預測出未知節(jié)點的位置；非測距的定位算法是利用WSN內(nèi)部信標節(jié)點與鄰居節(jié)點之間的連通性實現(xiàn)對未知節(jié)點的定位預測?；跍y距的定位算法雖然定位精度高，但是對節(jié)點本身的硬件設備性能要求較高，不易于在WSN環(huán)境中廣泛部署；非測距的定位算法相較測距的定位算法來講，無需硬件設備支持且成本較低，適于大規(guī)模在WSN環(huán)境中部署，但缺點是定位精度較低。

常見的非測距類算法有質(zhì)心定位算法、APIT算法、DV_Hop算法等。其中，質(zhì)心算法是通過計算多邊形的所有頂點的平均值坐標來估算未知節(jié)點的坐標，其主要優(yōu)點是無需知道未知節(jié)點與信標節(jié)點之間的距離，缺點是定位精度易受到節(jié)點分布和密度影響。APIT算法是將未知節(jié)點相鄰的信標節(jié)點任選三個構成一個三角形，這樣將構成多個三角形；然后，利用數(shù)學公式求解這些三角形交叉區(qū)域的質(zhì)心坐標，得到該質(zhì)心坐標當作待測節(jié)點的估計坐標。該算法的優(yōu)點是定位精度較高，但實現(xiàn)復雜且易受節(jié)點分布密度的影響。

DV_Hop算法的基本思想是在取得信標節(jié)點最小跳數(shù)與平均跳距的情況下，通過計算得出未知節(jié)點的估計坐標。DV_Hop算法最大優(yōu)勢是部署簡單且硬件設備要求低，易于廣泛部署[3]，但是節(jié)點定位精度較差。目前對該算法的研究主要從優(yōu)化距未知節(jié)點最近的信標節(jié)點的最小跳數(shù)值和校正錨節(jié)點平均跳距兩個方面來減小定位誤差。其中雙通信半徑DV_Hop算法就是通過優(yōu)化節(jié)點間最小跳數(shù)，得出較為精確的跳數(shù)值，提高了對未知節(jié)點的定位精度。然而，當雙通信半徑DV_Hop采用三角測量法或者極大似然估計法計算待測節(jié)點坐標值時，還具有定位精度不高的缺陷。

為了提高待測節(jié)點的定位精度，同時節(jié)約WSN節(jié)點部署的成本。近年來有學者將遺傳算法(Genetic Algorithm)、模擬退火法(Simulated Annealing)、粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)、蟻群算法(Ant Colony)等生物智能優(yōu)化算法應用到對待測節(jié)點定位精度的優(yōu)化中。其中，遺傳算法具有強容錯性和并行性，但計算復雜不易大規(guī)模部署[4]；模擬退火算法雖然具有計算簡單，能夠優(yōu)化多維數(shù)據(jù)的優(yōu)勢，但不易收斂容易陷入局部最優(yōu)解[5]；蟻群算法能夠?qū)崿F(xiàn)對最優(yōu)路徑的探索，具有節(jié)約節(jié)點能量、平衡網(wǎng)絡負載的效果，故經(jīng)常用在WSN路由協(xié)議中，但在WSN節(jié)點定位方面較少[6]。相比于其他算法，粒子群算法更易實現(xiàn)、收斂速度快、計算量較小，且易于大規(guī)模部署，所以受到大多數(shù)研究者青睞[7]。

本文主要研究在原DV_Hop算法的基礎上，信標節(jié)點在平均跳距的計算與廣播階段先后使用兩個不同的通信半徑廣播自身位置，形成雙通信半徑DV_Hop算法，接著引進一個修正因子來校正平均跳距，精確節(jié)點間最小跳數(shù)值；然后利用基于慣性權重的線性優(yōu)化和學習因子的線性加權改進的粒子群算法代替三角測量法或者極大似然估計法，對校正后的雙通信半徑DV_Hop算法中待測節(jié)點產(chǎn)生的誤差進行優(yōu)化使其達到最小值，從而提高待測節(jié)點的定位精度。

1 DV_Hop算法誤差分析及其改進

1.1 DV_Hop算法原理及誤差分析

DV_Hop算法實現(xiàn)分為距離矢量交換、平均跳距的計算與廣播、定位計算3個階段。在距離矢量交換階段中，當信標節(jié)點的鄰居節(jié)點在通信半徑R之內(nèi)時，就記該鄰居節(jié)點與信標節(jié)點的跳數(shù)為1[8]。然而，這樣不管信標節(jié)點與鄰居節(jié)點之間的實際距離，將它們之間的跳數(shù)值取為1，會導致DV_Hop算法的定位精度下降，同時也使算法的穩(wěn)定性下降。除此之外，由于兩節(jié)點之間所求出的估計距離是若干個連續(xù)跳段的距離，并不是直線距離，存在跳距誤差。在兩節(jié)點跳數(shù)不斷增加的情況下，節(jié)點之間的累計誤差將逐漸增大。

雙通信半徑DV_Hop算法采用R、0.5R兩種通信半徑廣播來優(yōu)化節(jié)點間的最小跳數(shù)。如圖1所示，記N個節(jié)點為si，i=1,2,…,N，其中sp為信標節(jié)點，在平均跳距的計算與廣播階段sp先以半徑R進行廣播，將在R范圍內(nèi)的節(jié)點與sp間的跳數(shù)記為1；然后再以通信半徑0.5R進行廣播，將0.5R內(nèi)的節(jié)點與sp間的跳數(shù)更新為0.5，記節(jié)點si與信標節(jié)點sp之間的跳數(shù)為hip，距離為rip，則：

圖1 DV_Hop算法節(jié)點分布圖

通過該方法能夠減小相同跳數(shù)實際距離相差較大而存在的誤差，使信標節(jié)點與未知節(jié)點之間的跳距更加接近真實值，優(yōu)化了信標節(jié)點間的跳數(shù)，使得到的最小跳數(shù)值更加精準。

1.2 基于修正跳距的雙通信半徑DV_Hop算法

雙通信半徑DV_Hop算法在計算未知節(jié)點與信標節(jié)點之間估計距離時，在目標區(qū)域內(nèi)待測節(jié)點與距其環(huán)境條件和位置關系最近的信標節(jié)點相似。從理論上講，待測節(jié)點將與其所處環(huán)境條件與位置關系最近的信標節(jié)點的平均跳距作為自身平均跳距，來估算與目標信標節(jié)點之間的距離是可行的。但是WSN節(jié)點分布不均勻且位置關系復雜多樣、節(jié)點靈活性低。如果僅僅使用距待測節(jié)點最近的信標節(jié)點的平均跳距，來估算與目標信標節(jié)點之間的距離，會存在較大誤差，獲取的待測節(jié)點位置精度較低。

在WSN中，除了利用信標節(jié)點的坐標計算出不同信標節(jié)點之間的真實距離外，還可以利用信標節(jié)點的真實距離與平均跳數(shù)之間的關系，在信標節(jié)點計算完自身平均跳距之后，根據(jù)平均跳距計算出與其他信標節(jié)點之間的估計距離?；诖丝紤]，如圖2所示，假設sm是與待測節(jié)點si距離最接近的信標節(jié)點，Dip和Dmp分別為sm和si與sp之間的平均距離，hmp為sm和sp之間的最小跳數(shù)值。在雙通信半徑DV_Hop算法的第二階段中引入修正因子Dmp/hmp來校正優(yōu)化待測節(jié)點與目標信標節(jié)點間的平均跳距，即：

(1)

從而使待測節(jié)點與信標節(jié)點的平均跳距根據(jù)距其最近的信標節(jié)點的平均跳距進行自適應性調(diào)整。

圖2 跳距修正原理

將校正優(yōu)化后的平均跳距用于估算待測節(jié)點與其他信標節(jié)點之間的距離，與原DV_Hop算法相比，基于修正跳距的雙通信半徑DV_Hop算法除了優(yōu)化節(jié)點間的最小跳數(shù)外，引入的修正因子使待測節(jié)點根據(jù)距離它位置與環(huán)境條件最近的信標節(jié)點進行自適應性調(diào)整，可以提高DV_Hop算法的定位精度。

2 DV_Hop算法優(yōu)化設計

2.1 粒子群算法原理

粒子群算法是一種智能優(yōu)化算法，其基本原理是使用一群一定數(shù)量的粒子，在目標區(qū)域內(nèi)通過彼此間的協(xié)作和信息資源共享，在具體問題的可行解中搜索滿足條件的解，并選擇最優(yōu)的或者相對最優(yōu)的解作為問題的解[9]。

在粒子群算法中，粒子在目標區(qū)域內(nèi)尋找最優(yōu)解的過程中，需要控制粒子的移動方向和快慢以及最優(yōu)位置，分別用速度矢量和位置矢量表示。其中，位置矢量分為局部最優(yōu)位置pbest和全局最優(yōu)位置gbest。

粒子之間除了時刻更新自己的位置之外，在迭代尋優(yōu)的空間中用一個相關的適應度函數(shù)來衡量一個粒子位置的好壞以及控制算法在尋優(yōu)過程中粒子的運動基準。

基本PSO算法具體過程如下：

假設某粒子群中有N個粒子，尋優(yōu)空間是一個D維空間。該粒子在目標區(qū)域中尋找pbest和gbest的過程中，第i個粒子的位置向量記為：

Xi=(xi1,xi2,…,xiD)i=1,2,…,N

(2)

第i個粒子在初始尋找pbest的過程中運動速度矢量記為：

Vi=(vi1,vi2,…,viD)i=1,2,…,N

(3)

第i個粒子在目標區(qū)域迭代尋優(yōu)過程中截止到某個時間，達到的局部最優(yōu)位置記為：

pbest=(pi1,pi2,…,piD)i=1,2,…,N

(4)

整個尋優(yōu)過程中，所有粒子在某一時刻達到的全局最優(yōu)位置記為：

gbest=(pg1,pg2,…,pgD)i=1,2,…,N

(5)

每個粒子在迭代尋優(yōu)過程中不同時刻的速度和位置更新表示為：

(6)

(7)

式中：ω稱為粒子的慣性權重，主要作用是通過控制迭代過程中粒子向最優(yōu)解靠攏的快慢、均衡迭代效率和尋優(yōu)精度，增強粒子在下一時刻的搜索能力；c1、c2稱為學習因子，主要作用是控制粒子的尋優(yōu)路徑，體現(xiàn)了粒子對速度更新的影響；λ1、λ2取[0,1]范圍內(nèi)的均勻隨機數(shù)。

最后，所有粒子在經(jīng)歷過pbest后整體最終達到的gbest為：

(8)

2.2 優(yōu)化慣性權重和改進學習因子的PSO

DV_Hop算法求未知節(jié)點在監(jiān)控區(qū)域中的坐標問題，從數(shù)學的角度，可以轉(zhuǎn)化為在目標區(qū)域中求坐標最優(yōu)解的優(yōu)化問題。PSO的主要優(yōu)勢就是在目標區(qū)域內(nèi)尋找最優(yōu)位置時，粒子通過不斷的速度和位置迭代的更新，迫使大量的粒子能夠達到最優(yōu)化的全局位置或者相對的局部最優(yōu)位置。

然而，PSO的缺點就是在目標區(qū)域內(nèi)迭代收斂速度不能動態(tài)調(diào)整，在運算搜索中會陷入搜索速度慢、全局最優(yōu)解位置變化很小的過程中[10]；在搜索后期尋優(yōu)粒子極易陷入局部極小值、迭代循環(huán)和出現(xiàn)多峰函數(shù)早熟收斂等問題，這些會給求解待定位節(jié)點最優(yōu)坐標帶來誤差，導致最優(yōu)解不準確等問題。針對PSO自身存在的局限性問題，本文采用一種基于線性優(yōu)化慣性權重與改進學習因子使兩者同步變化的PSO優(yōu)化修正跳距的雙通信半徑DV_Hop算法[11-13]。從決定PSO性能的3個關鍵參數(shù)ω、c1、c2對PSO進行優(yōu)化和改進，避免粒子過早地陷入局部最優(yōu)位置和多峰函數(shù)早熟收斂，從而提高粒子全局尋優(yōu)的能力，提高粒子的尋優(yōu)精度。

(1) 慣性權重ω的線性優(yōu)化。為增強粒子在尋優(yōu)過程中的速度，在較短時間內(nèi)尋找到最佳的最優(yōu)解，引入如下的線性優(yōu)化權重公式：

(9)

式中：f表示節(jié)點的適應度，favg表示監(jiān)控區(qū)域內(nèi)平均適應度，fmin表示最小適應度。通過仿真實驗表明，當ωmax=0.9，ωmin=0.4時，PSO算法的尋優(yōu)精度較高。即，線性優(yōu)化的慣性權重ω取值為：

(10)

(2) 學習因子的線性加權改進。從控制粒子在目標區(qū)域內(nèi)尋找最優(yōu)位置對當前迭代速度影響的角度出發(fā)。本文提出通過改進學習因子即增加一個逃逸因子來控制局部迭代循環(huán)，通過粒子進行中心學習，生成中心學習解，來提高種群多樣性。

(11)

式中：cend為線性加權改進的學習因子，用于控制局部迭代循環(huán)：

(12)

(3) 適應度函數(shù)。為了更好地度量PSO算法優(yōu)化雙通信半徑DV_Hop改進算法粒子在尋找最優(yōu)解過程中位置的好壞，引入適應度函數(shù)。同時，為了減少待測節(jié)點到目標信標節(jié)點之間距離的累計誤差給適應度函數(shù)帶來的影響，引入一個權重因子ωip。

本文采用如下適應度函數(shù)：

(13)

2.3 算法優(yōu)化步驟

基于粒子群的DV_Hop算法優(yōu)化的流程如圖3所示。

圖3 基于粒子群的DV_Hop算法優(yōu)化流程圖

具體步驟如下：

(1) 網(wǎng)絡初始化階段。在待定位區(qū)域內(nèi)，將WSN中的各節(jié)點隨機部署，并啟動定位過程。

(2) 啟動雙通信半徑DV_Hop法。信標節(jié)點先以通信半徑R進行廣播，將位于R內(nèi)的信標節(jié)點與鄰居節(jié)點之間的跳數(shù)記為1，生成鄰居節(jié)點組1。然后，信標節(jié)點以通信半徑0.5R廣播，將位于0.5R內(nèi)的信標節(jié)點與鄰居節(jié)點之間的跳數(shù)記為0.5，生成鄰居節(jié)點2。

(3) 更新計算階段。由于生成的鄰居節(jié)點組2是鄰居節(jié)點組1的子集。將組2中與組1中相同的鄰居節(jié)點的最小跳數(shù)更新為0.5，其他鄰居節(jié)點的最小跳數(shù)仍舊保持為1。

(4) 通過步驟(2)和步驟(3)，計算得到最小跳數(shù)hi與估算距離di。

(5) 設定粒子群的數(shù)目，并且初始化迭代過程中的各類參數(shù)。

(6) 根據(jù)式(10)和式(12)更新粒子的ω、c1、c2。

(7) 根據(jù)式(2)和式(3)更新粒子的尋優(yōu)區(qū)域中位置xi和迭代速度vi。

(8) 根據(jù)式(13)計算粒子的fitness值，更新粒子的最優(yōu)值pbest與gbest。檢查算法是否達到迭代次數(shù)上限值，如果達到，算法退出；否則返回步驟(6)。

3 仿真及結(jié)果分析

3.1 仿真環(huán)境及分析

仿真參數(shù)設置為：粒子群個體數(shù)量為20個，粒子在100 m×100 m區(qū)域的2維區(qū)域迭代優(yōu)化；最大迭代次數(shù)20次，ω根據(jù)式(10)進行動態(tài)變化，學習因子c1=c2=c3=2，各算法的最終定位誤差都取50次重復仿真的平均值。

在節(jié)點隨機部署的情況下，從總節(jié)點數(shù)、錨節(jié)點數(shù)、通信半徑三個方面，對原DV_Hop算法、雙通信半徑DV_Hop算法與加修正因子的改進算法以及本文改進算法進行對比和分析。定義待測節(jié)點Si的誤差公式為：

(14)

3.2 節(jié)點個數(shù)對定位誤差的影響

設置錨節(jié)點的通信半徑R為25 m，總節(jié)點個數(shù)從50開始，每50個節(jié)點線性地遞增到300，錨節(jié)點比例為20%。變化曲線如圖4所示。

圖4 不同節(jié)點個數(shù)的平均定位誤差

從圖4可以看出，在WSN監(jiān)測區(qū)域內(nèi)總節(jié)點個數(shù)線性地增加情況下，平均定位誤差都在不斷降低。出現(xiàn)這種情況的主要原因是節(jié)點數(shù)量的不斷增多，使得WSN環(huán)境中孤立的節(jié)點減少，錨節(jié)點與未知節(jié)點之間連通的節(jié)點增多，未知節(jié)點的平均定位誤差降低。

從整體上看，在節(jié)點數(shù)量一定的條件下，這三種改進算法與原DV_Hop算法相比都有很大的改進。雙通信半徑DV_Hop改進算法與未加修正因子之前，定位精度更加準確，誤差更小。本文改進算法比其他兩種改進算法的平均定位誤差都要低。這就說明本文改進算法對提高目標未知節(jié)點的定位精度方面作用還是比較明顯。同時，當總節(jié)點個數(shù)增加到一定程度時，平均定位誤差變化幅度很小，表明本文改進算法的魯棒性較好[12]。

3.3 錨節(jié)點個數(shù)對定位誤差的影響

設置總節(jié)點數(shù)為100個，通信半徑R為25 m，錨節(jié)點個數(shù)從5%開始，每5%個錨節(jié)點線性地逐漸遞增到50%，這4種算法的平均定位誤差變化曲線如圖5所示。

圖5 不同錨節(jié)點定位誤差

從圖5能夠看出，在監(jiān)控區(qū)域內(nèi)不斷增加錨節(jié)點比例地情況下，這4種算法的平均定位誤差不斷減小。當錨節(jié)點在目標區(qū)域內(nèi)達到某一程度時，待測節(jié)點的定位幅度偏差變化都比較小，并且逐漸趨于穩(wěn)定。由于在WSN環(huán)境中，當錨節(jié)點數(shù)量較少時，孤立節(jié)點個數(shù)較多，節(jié)點彼此之間連通的數(shù)量較少，并且估算距離存在較大的誤差累計等，影響了節(jié)點的定位精度；當錨節(jié)點個數(shù)增多時，網(wǎng)絡環(huán)境中節(jié)點之間連通的個數(shù)較多，估算距離誤差累計較低，節(jié)點偏差逐漸減小，節(jié)點定位精度較高。

特別地，當錨節(jié)點比例為25%時，雙通信半徑DV_Hop改進算法相比未加修正因子的雙通信半徑DV_Hop算法在未知節(jié)點的平均定位誤差精度上提升了11%左右；與原DV_Hop算法的平均定位誤差相比增加了14%左右。而本文改進算法相比雙通信半徑DV_Hop改進算法與未加修正因子的雙通信半徑DV_Hop算法的定位誤差分別提升了18%、29%左右。從整體上來看，本文對于采用的粒子群算法對加修正因子的雙通半徑DV_Hop算法的優(yōu)化使錨節(jié)點在數(shù)量達到一定的程度的情況下，對于待測節(jié)點的定位更加準確，效果也更加明顯，同時能夠減少無線傳感器節(jié)點定位成本[14]。

3.4 通信半徑對節(jié)點定位誤差的影響

設置WSN監(jiān)控區(qū)域內(nèi)節(jié)點個數(shù)為100，錨節(jié)點的通信半徑R從15 m開始，規(guī)則地遞增到40 m，錨節(jié)點為20，這4種算法的平均定位誤差變化曲線如圖6所示。

圖6 不同通信半徑節(jié)點誤差

從圖6可以看出，在通信半徑R規(guī)則地增大的情況下，這4種算法的平均定位誤差也降低，只不過降低的幅度有的大、有的小。特別地，當通信半徑大于30 m時，信號輻射半徑地增大，增加了節(jié)點之間的通信跳數(shù)和節(jié)點之間的累計誤差，導致原DV_Hop算法的平均定位誤差逐漸上升，節(jié)點定位精度下降。同時，在該仿真試驗中，可以看出雙通信半徑 DV_Hop改進算法與未加修正因子的該算法，平均定位誤差變化趨勢基本相同。而當通信半徑大于30 m時，本文改進算法變化趨勢相對穩(wěn)定，增減幅度比較小，說明粒子群優(yōu)化算法對此時節(jié)點的定位誤差敏感度降低。

4 結(jié) 語

本文首先對DV_Hop算法的定位原理及誤差產(chǎn)生的原因進行了分析，針對DV_Hop算法在計算節(jié)點跳距時，隨著節(jié)點數(shù)目的遞增節(jié)點間的誤差累計增大的問題，在平均跳距的計算與廣播階段信標節(jié)點，讓信標節(jié)點先后使用兩個通信半徑廣播自身位置信息，同時加入了一個修正因子來校正平均跳距，精確了節(jié)點間的最小跳數(shù)值，得到更精確的未知節(jié)點坐標。接著對校正后的DV_Hop算法在求解待測節(jié)點坐標時存在誤差等問題，采用基于線性優(yōu)化慣性權重與線性加權改進的學習因子同步變化的粒子群算法優(yōu)化待測節(jié)點產(chǎn)生的累計誤差，減小了節(jié)點的平均定位誤差。最后，通過選取合適的參數(shù)變量，對本文提出的改進算法從三個方面進行仿真驗證。結(jié)果表明，本文優(yōu)化算法的定位精度及魯棒性更加良好。