傳感器網絡的粒子群優化定位算法

陳志奎， 司 威

（大連理工大學 軟件學院，遼寧 大連 116023）

0 引言

隨著物聯網研究和應用的深入，由信息采集層和信息傳輸層構成的信息感知體系是物聯網應用推進的主要領域，而無線傳感器網絡行業在其中起到關鍵的推動作用。無線傳感器網絡是一個多跳自組織網絡系統，傳感器節點之間協作地感知、采集和處理網絡覆蓋區域中感知對象的信息，并通過傳感器網絡發送給需求者。無線傳感器網絡由于具有遠程監控、實時監測并且能在惡劣或特殊環境工作等諸多優點而被廣泛應用于智能交通、國防軍事、環境監測、醫療衛生、空間探索、精細農業等諸多領域[1-3]，其中節點定位技術則是無線傳感器網絡進行目標識別、監控、跟蹤等眾多應用的前提。

定位技術是無線傳感器網絡的主要支撐技術之一。獲取傳感器節點的位置信息是傳感器網絡應用的一種重要部分，在傳感器網絡執行監測活動時，事件發生的位置和觀測節點的位置信息往往是傳感器節點采集數據中不可缺少的部分，沒有位置信息，網絡所獲得的數據將毫無意義。

無線傳感器網絡定位可分為基于測距的定位和無需測距的定位算法，其主要區別在于是否需要距離信息。基于測距的定位算法中節點使用測距技術獲得距離信息，定位精度較高但是需要額外的設備，其中常用的測距技術有接收信號強度RSSI[4]，信號到達時間TOA[5]，信號到達時間差 TDOA[6]和信號到達角度 AOA[7]等；而無需測距的定位算法僅依靠相鄰節點間的連通關系進行定位，無需基礎網絡設施的支持，定位精度較低。

由于傳統的節點定位算法采用最小二乘法求解非線性方程組很容易受到測距誤差的影響。為了提高節點的定位精度，將粒子群優化算法引入到無線傳感器網絡定位中，通過迭代算法尋求最優解，有效抑制了測距誤差的累積對定位精度的影響，而且該算法需要的錨節點個數相對較少，一定程度地降低了網絡費用。

1 傳感器網絡的粒子群優化定位算法

1.1 粒子群優化算法

粒子群優化算法是基于群體智能理論的一種新興演化計算技術，通過個體間的協作與競爭，實現復雜空間中最優解的搜索。

粒子群優化算法數學模型描述為：假設粒子群的群體規模為 S,其中在 d維搜索空間中第 i個粒子的位置和速度可以分別表示為通過適應度函數，確定t時刻每個粒子所經過的最佳位置以及群體所發現的最佳位置Pg,再按照如下公式分別更新粒子的速度和位置[8]：其中，w為慣性因， c1和 c2為正的加速常數， r1和 r2為[0,1]間均勻分布的隨機數。假設粒子的最大速度為 vmax，則粒子的速度通常設為每維變換范圍的10%～20%[9]。

1.2 慣性權重

慣性權重 w的大小決定了粒子對當前速度繼承的多少，通過權重 w可有效控制算法的搜索能力和挖掘能力。若 w取值較大，則粒子的全局搜索能力較強，有利于粒子跳出局部極小點；若 w取值較小，則粒子的局部挖掘能力較強，有利于算法收斂。文獻[10]通過實驗證明，w的取值隨著算法迭代而線性減小時，算法具有較強的收斂性。

其中，maxw 和minw 分別是初始和終止慣性權重，t是當前迭代次數，maxt 是最大迭代次數。

1.3 適應度函數計算

適應度函數用來評價各個粒子在種群中達到或接近于最優解的優劣程度，從中選出每個粒子的個體極值和種群的全局極值。

假設二維空間中有 M個錨節點，N個未知節點。已知M個錨節點的坐標 AI( xi, yi),i = 1 ,2,… ,M ,未知節點到錨節點的距離 di,i = 1 ,2,… ,M ，則未知節點坐標(x , y )滿足公式(4)：

由于存在測距誤差、環境因素等影響，測量距離總存在一定誤差使上述公式不能全部成立。假設 fi,i = 1 ,2,…,M為未知節點到錨節點之間的測距誤差值，則 fi滿足：

無線傳感器網絡定位中，測距誤差值 fi越小，定位結果越精確。因此適應度函數定義為：

1.4 粒子保活性

粒子群優化算法的尋優能力主要依賴粒子之間的相互作用和相互影響，而粒子自身沒有變異能力。這表明當單個粒子陷入局部極值時可以通過借助其它粒子來逃逸局部極值點；但當大部分粒子均被相同的局部極值所限制時，整個算法就會進展緩慢，甚至出現停滯現象。

為了保持粒子的活性[11]，首先，判斷粒子是否失活（失活指在迭代過程中連續一定代數粒子的適應值都沒有優于歷史最優的適應值），若粒子失活，則對失活粒子進行變異，即要么使粒子以較小的變異概率在其迭代過程中獲得的維空間內重新初始化；要么使粒子在其當前位置進行擾動，并將變異或擾動的結果無條件地接受為當前粒子的歷史最優。以此來增強全局搜索能力,克服粒子群陷入局部解的缺點，同時又可以加快收斂速度、提高搜索精度。

1.5 傳感器網絡的粒子群優化定位算法

傳感器網絡的粒子群優化定位算法流程如下：

①初始化所有粒子，群體規模為 S。在部署區域內隨機初始粒子的位置和速度，計算每個粒子的適應度值，選擇適應度值最小的粒子位置初始化為全局極值，其它粒子的適應值初始化為粒子的個體極值，然后轉向步驟⑥；

② 根據式(6)計算每個粒子的適應度值；

③ 對每個粒子，將其當前的適應度值與其歷史最優位置所對應的適應度值進行比較，如果當前粒子的適應度值小于歷史最優位置所對應的適應度值，則用粒子當前位置更新粒子最優位置，否則判斷粒子是否失活（即粒子在一定迭代次數內都沒有取得好于粒子最優位置的適應度值），若失活則粒子進行變異，保持粒子活性，否則執行步驟④；

④ 對每個粒子，將其當前最優位置對應的適應度值與群體歷史最優位置對應的適應度值進行比較，如果當前粒子的適應度值小于群體歷史最優位置所對應的適應度值，則將粒子當前位置作為群體最優位置；

⑤ 檢查終止條件（達到最大迭代次數或者適應度值在測距誤差范圍內）。若終止條件滿足，轉向步驟⑦，否則轉向步驟⑥。

⑥ 根據式（1）和式（2）更新粒子的速度和位置，轉向步驟②；

⑦ 輸出全局極值對應的粒子位置，退出循環。

2 仿真實驗

2.1 仿真環境設置

使用 MATLAB對傳感器網絡的粒子群優化定位算法進行仿真，仿真過程中，節點隨機分布在一個無障礙的 100 m×100 m的正方形區域內，其中網絡規模為 100，錨節點比例為10%，節點的無限射程40 m。種群規模S=20，最大迭代次數 tmax=50，最大速度 vmax=10,初始慣性權重wmax=0.9，終止慣性權重 wmin=0.2，c1=c2=2。

2.2 仿真結果分析

仿真實驗主要分析了錨節點密度、網絡連通度、測距誤差對節點定位的影響，并與最小二乘法進行比較分析。

錨節點密度反映了每個未知節點周圍的錨節點個數。圖 1描述了錨節點密度對平均定位誤差的影響。由于錨節點本身的成本較高，因而錨節點的密度將直接影響網絡的整體成本。由下圖可知，隨著錨節點密度的增加，平均定位誤差將逐漸下降，但當錨節點密度達到 10%時，平均定位誤差下降速度緩慢，因而粒子群優化的定位算法對錨節點的密度要求不是很高，在錨節點密度相對較小時，也能達到很好的定位效果。

圖1 錨節點密度對平均定位誤差的影響

網絡連通度反映了能相互通信的節點間的通信量，在仿真過程中可以通過改變節點的無線射程來改變網絡的連通度。圖 2顯示了網絡連通度對平均定位誤差的影響，由圖可知，隨著網絡連通度的增大，節點的平均定位誤差變化相對緩慢，說明粒子群優化的定位算法對未知節點間通信量要求不大，定位節點的能耗較小。

測距誤差直接影響距離測量值的準確度。圖 3顯示了平均定位誤差隨測距誤差變化的情況，由圖可知，隨著測距誤差的增大，平均定位誤差也逐漸增大，但粒子群優化的定位算法有更小的定位誤差，達到較高的定位精度。

圖2 網絡連通度對平均定位誤差的影響

圖3 測距誤差對平均定位誤差的影響

3 結語

粒子群優化的傳感器網絡定位算法通過采用迭代的方式搜索節點的位置。仿真結果表明：粒子群優化的定位算法有效地提高節點的定位精度，尤其在測距誤差較大的情況大具有較好的定位效果，適用于無線傳感器網絡定位。然而，該算法仍然存在一些不足，下一階段的工作是考慮算法的能耗，進一步改進算法提高算法的穩定性及定位精度。

[1] 鄭丹玲,董宏成.無線傳感器網絡與其關鍵技術[J].通信技術,2008，41(08)：179-197.

[2] 范波,苗偉.無線傳感器網絡及其在環境監測應用概況[J].通信技術,2009,42(12)：170-172.

[3] 明光照, 李鷗, 張延軍. 基于無線傳感器網絡的職能家居系統設計[J]. 通信技術, 2009,42(02)：233-237.

[4] DOHERTY L, PISTER K S J, E I GHAOUI L. Convex Position Estimation in Wireless Sensor Networks[C]NJ： IEEE, 2001：1655-1663.

[5] GRIOD L, ESTRIN D. Robust Range Estimation Using Acoustic and Multimodal Sensing[C]. USA： IEEE Computer Society,2001：1312-1320.

[6] SAVVIDES A, HAN C C, STRIVASTAVA M B. Dynamic Fine-grained Localization in Ad-hoc Networks of Sensors [C]New York： ACM Press, 2001： 166-179.

[7] NICULESC D, NATH B. Ad Hoc Positioning Systems(APS) Using AOA[J].In：Proc. of the IEEE INFOCOM 2003, 2003(03)：1734-1743.

[8] SHI Y,EBERHART R C.A Modified Particle Swarm Optimizer[C]. USA：IEEE,1998：69-73.

[9] EBERHART R,SHI Y H. Particle Swarm Optimization： Developments,Applications and Resources[C].USA：IEEE, 2001： 81-86.

[10] BERGH F,ENGELBRECHT A P.A Cooperative Approach to Particle Swarm Optimization[J]. IEEE Trans. on Evolutionary Computation, 2004, 8(03)： 225-239.

[11] 盧克中,王汝傳,帥小應.保持活性的改進粒子群優化算法[J].計算機工程與應用,2007,43(11)：16-38.