陳志奎， 司 威

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

0 引言

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

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

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

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

1 傳感器網(wǎng)絡的粒子群優(yōu)化定位算法

1.1 粒子群優(yōu)化算法

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

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

1.2 慣性權重

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

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

1.3 適應度函數(shù)計算

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

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

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

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

1.4 粒子保活性

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

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

1.5 傳感器網(wǎng)絡的粒子群優(yōu)化定位算法

傳感器網(wǎng)絡的粒子群優(yōu)化定位算法流程如下：

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

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

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

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

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

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

⑦ 輸出全局極值對應的粒子位置，退出循環(huán)。

2 仿真實驗

2.1 仿真環(huán)境設置

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

2.2 仿真結果分析

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

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

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

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

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

圖2 網(wǎng)絡連通度對平均定位誤差的影響

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

3 結語

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

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

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

[3] 明光照, 李鷗, 張延軍. 基于無線傳感器網(wǎng)絡的職能家居系統(tǒng)設計[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] 盧克中,王汝傳,帥小應.保持活性的改進粒子群優(yōu)化算法[J].計算機工程與應用,2007,43(11)：16-38.