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

陳志奎， 司 威

（大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116023）

0 引言

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

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

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

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

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

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

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

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

1.2 慣性權(quán)重

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

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

1.3 適應(yīng)度函數(shù)計(jì)算

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

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

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

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

1.4 粒子保活性

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

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

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

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

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

② 根據(jù)式(6)計(jì)算每個(gè)粒子的適應(yīng)度值；

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

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

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

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

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

2 仿真實(shí)驗(yàn)

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

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

2.2 仿真結(jié)果分析

仿真實(shí)驗(yàn)主要分析了錨節(jié)點(diǎn)密度、網(wǎng)絡(luò)連通度、測(cè)距誤差對(duì)節(jié)點(diǎn)定位的影響，并與最小二乘法進(jìn)行比較分析。

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

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

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

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

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

圖3 測(cè)距誤差對(duì)平均定位誤差的影響

3 結(jié)語

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

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

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

[3] 明光照, 李鷗, 張延軍. 基于無線傳感器網(wǎng)絡(luò)的職能家居系統(tǒng)設(shè)計(jì)[J]. 通信技術(shù), 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īng).保持活性的改進(jìn)粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(11)：16-38.