劉 政

（桂林航天工業(yè)學(xué)院自動(dòng)化系，廣西桂林541004）

基于粒子群優(yōu)化的多維標(biāo)度節(jié)點(diǎn)定位算法*

劉 政*

（桂林航天工業(yè)學(xué)院自動(dòng)化系，廣西桂林541004）

針對(duì)無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位易受外部環(huán)境影響的問題，提出一種基于粒子群尋優(yōu)的多位標(biāo)度定位算法。利用基于動(dòng)態(tài)路徑損耗指數(shù)的接受信號(hào)強(qiáng)度測(cè)距，建立距離矩陣，使用多維標(biāo)度方法構(gòu)建節(jié)點(diǎn)的相對(duì)坐標(biāo)，通過四參數(shù)坐標(biāo)轉(zhuǎn)換模型得到絕對(duì)坐標(biāo)，再用絕對(duì)坐標(biāo)與實(shí)際坐標(biāo)的差異度作為粒子群尋優(yōu)的適應(yīng)度函數(shù)，通過分群搜索，優(yōu)化節(jié)點(diǎn)位置估計(jì)。仿真結(jié)果表明：改進(jìn)算法對(duì)實(shí)際環(huán)境影響具有較好的魯棒性，節(jié)點(diǎn)定位精度有了明顯的提高，能夠滿足定位系統(tǒng)需求。

無(wú)線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；多維標(biāo)度；粒子群

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由一些隨機(jī)部署在檢測(cè)區(qū)域內(nèi)的無(wú)線傳感器節(jié)點(diǎn)通過節(jié)點(diǎn)間的無(wú)線通信而形成的自組織網(wǎng)絡(luò)系統(tǒng)［1］。在無(wú)線傳感器網(wǎng)絡(luò)研究、應(yīng)用中，節(jié)點(diǎn)定位一直是個(gè)熱門的應(yīng)用方向。到目前為止，很多專家、學(xué)者提出了各種關(guān)于無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法，這些算法在定位精度、平均定位誤差、定位節(jié)點(diǎn)的連通率、節(jié)點(diǎn)能量損耗、信標(biāo)節(jié)點(diǎn)分布密度等指標(biāo)上進(jìn)行不斷的改進(jìn)。

多維標(biāo)度法（Multidimensional-Scaling，MDS）是一種把實(shí)體間的相關(guān)性轉(zhuǎn)換為空間坐標(biāo)的數(shù)據(jù)分析方法，利用網(wǎng)絡(luò)分布中節(jié)點(diǎn)間的相關(guān)信息來(lái)確定節(jié)點(diǎn)的空間坐標(biāo)。早期，由Shang等提出的MDS-MAP［2-4］多維標(biāo)度定位算法，利用節(jié)點(diǎn)間的距離信息構(gòu)造目標(biāo)對(duì)象間的相異性距離矩陣，再求解中心內(nèi)積矩陣的非零特征值及特征向量，最終求得相對(duì)坐標(biāo)。后期，相繼有人提出了基于MDS的改進(jìn)算法，比如：距離重構(gòu)MDS［5］、改進(jìn)分布式MDS［6-7］、分布加權(quán)式MDS［8-9］、非線性濾波MDS［10］等。以上基于MDS的定位算法實(shí)際上是利用WSN網(wǎng)絡(luò)中可通信節(jié)點(diǎn)間的關(guān)聯(lián)信息來(lái)獲取節(jié)點(diǎn)的空間坐標(biāo)，即使網(wǎng)絡(luò)中沒有信標(biāo)節(jié)點(diǎn)，也能計(jì)算定位節(jié)點(diǎn)的相對(duì)坐標(biāo)，只需補(bǔ)充少量信標(biāo)節(jié)點(diǎn)，就能將相對(duì)坐標(biāo)轉(zhuǎn)換為定位節(jié)點(diǎn)的絕對(duì)坐標(biāo)。然而，MDS算法的基礎(chǔ)是計(jì)算網(wǎng)絡(luò)中定位節(jié)點(diǎn)間歐氏距離組成的距離矩陣，而節(jié)點(diǎn)間距信息的獲取易受外部環(huán)境影響，會(huì)引入較大的測(cè)距誤差，降低定位精度。

為了提高定位精度，本文引入改進(jìn)RSSI測(cè)距來(lái)降低測(cè)距誤差影響，并用分群PSO算法搜索MDS坐標(biāo)變換的最小坐標(biāo)差異度，尋找最優(yōu)位置估計(jì)。仿真實(shí)驗(yàn)驗(yàn)證，改進(jìn)算法優(yōu)化了節(jié)點(diǎn)坐標(biāo)估計(jì)，有效地提高了節(jié)點(diǎn)定位精度。

1 SPSO-MDS算法

1.1 MDS算法

設(shè)r維空間中的n個(gè)點(diǎn)表示為X1,X2,…,Xn，用矩陣表示為X=(X1,X2,…,Xn)′，稱X為距離陣D的一個(gè)擬合構(gòu)圖，求得的n個(gè)點(diǎn)之間的距離陣稱為D的擬合距離陣，和 D盡可能接近。如果，則稱X為D的一個(gè)構(gòu)圖。

對(duì)應(yīng)歐氏空間的n個(gè)點(diǎn)，其距離陣為D=(dij)n×n，它們所對(duì)應(yīng)的空間的維數(shù)為r，第i個(gè)節(jié)點(diǎn)對(duì)應(yīng)的點(diǎn)記為 Xi，則 Xi的坐標(biāo)記作

設(shè)B=(bij)n×n，其中：

用矩陣表示為：

記λ1≥λ2≥…≥λr為B的正特征根，λ1,λ2,…, λr對(duì)應(yīng)的單位特征向量為 e1,e2,…,er，Γ=(e1,e2,…,er)是單位特征向量為列組成的矩陣，則，X矩陣中每一行對(duì)應(yīng)空間中的一個(gè)點(diǎn)，第i行即為 Xi。令Λ=diag(λ1,λ2,…,λr)，那么：

多維空間中的節(jié)點(diǎn)相對(duì)坐標(biāo)為：

按照式（2）求出各個(gè)點(diǎn)對(duì)之間的內(nèi)積，得到內(nèi)積矩陣B的r個(gè)非零特征值及所對(duì)應(yīng)的一組特征向量，再根據(jù)式（4）即可求出X矩陣的r個(gè)列向量或空間n個(gè)點(diǎn)的坐標(biāo)。若使用二維坐標(biāo)，只需保留兩個(gè)最大的特征值及對(duì)應(yīng)的特征向量，若使用三維坐標(biāo)，需要保留三個(gè)最大的特征值及對(duì)應(yīng)的特征向量，傳感器網(wǎng)絡(luò)各節(jié)點(diǎn)的相對(duì)坐標(biāo)即可得到［11］。

通過以上多維標(biāo)度法獲得的節(jié)點(diǎn)坐標(biāo)是相對(duì)坐標(biāo)，需要變換到信標(biāo)節(jié)點(diǎn)的絕對(duì)坐標(biāo)系中。在二維空間有3個(gè)以上信標(biāo)節(jié)點(diǎn)或者在三維空間有4個(gè)以上信標(biāo)節(jié)點(diǎn)，就可以利用信標(biāo)節(jié)點(diǎn)的絕對(duì)坐標(biāo)位置，通過平移、旋轉(zhuǎn)和映射等線性變換，將相對(duì)坐標(biāo)轉(zhuǎn)換到信標(biāo)節(jié)點(diǎn)所在的絕對(duì)坐標(biāo)系中去?？紤]到二維空間的適用性，利用四參數(shù)坐標(biāo)轉(zhuǎn)換模型建立兩個(gè)平面坐標(biāo)系的轉(zhuǎn)換關(guān)系，它包括兩個(gè)平移參數(shù)、一個(gè)旋轉(zhuǎn)參數(shù)和尺度參數(shù)，其轉(zhuǎn)換模型為：

式中：(y1,y2)為轉(zhuǎn)換后的絕對(duì)坐標(biāo)，(x1,x2)為相對(duì)坐標(biāo)，Δx1、Δx2為平移參數(shù)，m為尺度參數(shù)，α為旋轉(zhuǎn)參數(shù)。

1.2 SPSO尋優(yōu)算法

粒子群算法（Particle Swarm Optimization，PSO）通過迭代計(jì)算當(dāng)前搜索到的局部最優(yōu)值來(lái)尋找全局最優(yōu)值，并建立適應(yīng)度函數(shù)來(lái)評(píng)價(jià)解空間的性能。為了加快尋優(yōu)速度，對(duì)PSO算法進(jìn)行改進(jìn)，得到SPSO算法。

SPSO算法描述：設(shè)由N個(gè)粒子組成的粒子群以一定的速度在二維空間中搜索最優(yōu)解，粒子i在二維空間的位置表示為Zid=（zi1,zi2），飛行的速度表示為Vid=（vi1,vi2），經(jīng)過迭代計(jì)算，每個(gè)粒子搜索個(gè)體最優(yōu)位置Pdbest=（pd1,pd2）和全局最優(yōu)位置Pgbest=（pg1,pg2）。每個(gè)粒子在找到個(gè)體和全局兩個(gè)最優(yōu)值后，根據(jù)式（6）來(lái)更新速度與位置：

式中：w為慣性權(quán)重，k是迭代次數(shù)，c1和c2是加速因子，r1和r2是［0，1］之間的隨機(jī)數(shù)。

建立以winner粒子為核心的多個(gè)子群［12］。在每次迭代完后，winner粒子的適應(yīng)度函數(shù)filter(zj,vj)需滿足式（7）要求，以winner粒子為中心進(jìn)行分群搜索，比較winner粒子Pdbest與分群Psgbest的適應(yīng)度函數(shù)，得到子群最優(yōu)；再比較Pdbest與種群Pgbest的適應(yīng)度函數(shù)，找到種群最優(yōu)。

分群搜索過程描述如下：

將種群分割成成若干個(gè)子群，將種群大搜索分解為子群同步小搜索，既縮小了搜索范圍，又提高了收斂速度。

1.3 改進(jìn)RSSI測(cè)距

基于RSSI測(cè)距的前提是路徑損耗指數(shù)為常數(shù)，但是如果區(qū)域環(huán)境發(fā)生變化，那么不同區(qū)域的路徑損耗指數(shù)存在差異，所以未經(jīng)修正的RSSI測(cè)距會(huì)引入較大的誤差，為了減少這種誤差，考慮找到能夠描述區(qū)域路徑損耗指數(shù)的算式［13］。

對(duì)數(shù)-常態(tài)分布模型：

式中，RSSI（d）：接收信號(hào)強(qiáng)度；Pt：發(fā)射信號(hào)功率；PL(d)：路徑損耗；d0：近地參考距離；PL(d0)：傳輸d0距離的路徑損耗；n：路徑損耗指數(shù)；Xσ：平均值為0的高斯分布隨機(jī)變數(shù)。

通過計(jì)算區(qū)域鄰居信標(biāo)節(jié)點(diǎn)（B1、B2、B3）間的RSSI值，得到當(dāng)前區(qū)域內(nèi)的路徑損耗指數(shù)：

合并式（9）、式（10），得到路徑損耗指數(shù)算式：

將式（11）代入式（8），得到基于動(dòng)態(tài)路徑損耗指數(shù)的RSSI測(cè)距算式

1.4 SPSO-MDS算法描述

由MDS算法中的式（5）坐標(biāo)轉(zhuǎn)換模型得到絕對(duì)坐標(biāo)：

設(shè)定diver(x,y)函數(shù)來(lái)衡量實(shí)際坐標(biāo)(z1,z2)和轉(zhuǎn)換后絕對(duì)坐標(biāo)(y1,y2)的差異度［14］：

將差異度函數(shù)diver(x,y)作為SPSO尋優(yōu)過程中的適應(yīng)度函數(shù)filter(z,v)：

通過分群搜索，尋找全局最優(yōu)位置Pgbest：

SPSO-MDS算法描述如下：

步驟1改進(jìn)RSSI測(cè)距，獲取節(jié)點(diǎn)間的距離，構(gòu)成距離陣D；

步驟2由式（1）～式（5）得到節(jié)點(diǎn)MDS相對(duì)坐標(biāo)和絕對(duì)坐標(biāo)，作為SPSO粒子初始位置；

步驟3由式（6）更新粒子位置和速度，用式（7）搜索winner粒子；

步驟4由式（14）得到的差異度函數(shù)替代SPSO尋優(yōu)的適應(yīng)度函數(shù)，找到群最優(yōu)。

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

本文基于MATLAB平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，仿真參數(shù)設(shè)置：信標(biāo)節(jié)點(diǎn)20個(gè)，未知節(jié)點(diǎn)60個(gè)，隨機(jī)分布在100 m×100 m的正方形區(qū)域，節(jié)點(diǎn)通信半徑30 m。

評(píng)價(jià)指標(biāo)：平均定位誤差（Average Position Error，APE）。

式中：xest為估計(jì)位置，xreal為實(shí)際位置，N為待定位節(jié)點(diǎn)個(gè)數(shù)，R為節(jié)點(diǎn)通信半徑。

比較SPSO-MDS算法與MDS-MAP、MDS-MAP（P）算法之間的性能差異，分別以測(cè)距誤差、信標(biāo)節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)連通度對(duì)APE的影響程度來(lái)驗(yàn)證改進(jìn)效果。

2.1 測(cè)距誤差對(duì)APE的影響

從圖1可以看出，在同等測(cè)距誤差影響下，SPSOMDS算法的平均定位誤差小于MDS-MAP和MDSMAP（P）算法。隨著測(cè)距誤差的增大，三種算法的平均定位誤差都有逐漸增大的趨勢(shì)，但改進(jìn)算法的定位誤差增長(zhǎng)率最小，相比較另外兩種算法，改進(jìn)算法對(duì)測(cè)距誤差的影響具有最好的魯棒性，這是因?yàn)槔肦SSI改進(jìn)測(cè)距算式（12）獲取動(dòng)態(tài)路徑損耗指數(shù)，減少了外部環(huán)境影響，降低了測(cè)距誤差。

圖1 定位誤差受測(cè)距誤差的影響

2.2 信標(biāo)節(jié)點(diǎn)數(shù)對(duì)APE的影響

從圖2可以看出，當(dāng)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)數(shù)量相同時(shí)，SPSO-MDS算法的平均定位誤差小于MDS-MAP和MDS-MAP（P）算法。隨著信標(biāo)節(jié)點(diǎn)數(shù)逐漸增加，三種算法的平均定位誤差都有下降的趨勢(shì)。當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)處于5%～30%之間時(shí)，平均定位誤差下降迅速；當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)超過30%，平均定位誤差的下降趨勢(shì)變緩且趨于穩(wěn)定。整體來(lái)看，改進(jìn)算法的效果明顯優(yōu)于另外兩種算法。

圖2 定位誤差受信標(biāo)節(jié)點(diǎn)數(shù)的影響

2.3 網(wǎng)絡(luò)連通度對(duì)APE的影響

獲取網(wǎng)絡(luò)連通度對(duì)定位誤差的影響，可以通過保持信標(biāo)節(jié)點(diǎn)數(shù)不變，調(diào)整節(jié)點(diǎn)通信半徑來(lái)比較效果。從圖3可以看出，當(dāng)網(wǎng)絡(luò)連通度處于［5-25］區(qū)間，隨著連通度的增加，三種算法的平均定位誤差降低都比較明顯，其中改進(jìn)算法最顯著；當(dāng)連通度超過25以后，三種算法的平均定位誤差下降變緩，連通度的影響逐漸弱化，反而由于可通信范圍內(nèi)節(jié)點(diǎn)數(shù)的增加，導(dǎo)致節(jié)點(diǎn)通信開銷的增加。

圖3 定位誤差受網(wǎng)絡(luò)連通度的影響

3 結(jié)束語(yǔ)

通過獲取動(dòng)態(tài)路徑損耗指數(shù)，減少外部環(huán)境影響，降低測(cè)距誤差，將改進(jìn)測(cè)距應(yīng)用于基于多維標(biāo)度法的節(jié)點(diǎn)定位，提高距離矩陣精度，并進(jìn)行分群粒子群搜索，對(duì)坐標(biāo)差異度尋優(yōu)。實(shí)驗(yàn)結(jié)果表明，與其它多維標(biāo)度定位算法相比，同等影響因素下SPSO-MDS算法具有更高的定位精度，對(duì)實(shí)際環(huán)境的影響具有較好的魯棒性，可以適用于無(wú)線傳感器網(wǎng)絡(luò)定位應(yīng)用。

［1］孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005.

［2］Shang Y，Ruml W，Zhang Y.Localization from Mere Connectivity in Sensor Network［C］//Proceeding of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2003：201-212.

［3］Shang Y，Ruml W.Improved MDS-Based Localization［C］//Proc of IEEE INFOCOM.Hong Kong：IEEE Press，2004：2640-2651.

［4］Shang Y，Ruml W，Zhang Y.Localization from Connectivity in Sensor Networks［J］.IEEE Trans on Parallel and Distributed System，2004，15（11）：961-973.

［5］黃亮，王福豹，段渭軍，等.基于距離重構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)多維定標(biāo)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（9）：1284-1287.

［6］劉健苗，許新忠，黃書廣，等.改進(jìn)的分布式無(wú)線傳感器網(wǎng)絡(luò)多維標(biāo)度定位算法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（5）：692-697.

［7］Gopakumar Aloor，Lillykutty Jacob.Distributed Wireless Sensor Network Localization Using Stochastic Proximity Embedding［J］.Computer Communications，2010，33（6）：745-755.

［8］Chan F，So H C.Efficient Weighted Multidimensional Scaling for Wireless Sensor Network Localization［J］.IEEE Trans on Signal Processing，2009，57（11）：4548-4553.

［9］王新生，胡玉蘭，劉永帥.一種改進(jìn)的傳感器節(jié)點(diǎn)多維標(biāo)度定位算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（4）：727-731.

［10］陳歲生，盧建剛，樓曉春.基于MDS-MAP和非線性濾波的WSN定位算法［J］.浙江大學(xué)學(xué)報(bào)：工學(xué)版，2012，5（5）：866-872.

［11］秦爽.參數(shù)化多維標(biāo)度定位方法研究［D］.成都：電子科技大學(xué)，2012.

［12］張亞明，史浩山，程偉，等.一種無(wú)線傳感器網(wǎng)絡(luò)中的進(jìn)化定位機(jī)制［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2013，31（4）：633-638.

［13］劉政.基于權(quán)重動(dòng)態(tài)離散模型的WSNs定位算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（3）：437-442.

［14］石欣，印愛民，陳曦.基于RSSI的多維標(biāo)度室內(nèi)定位算法［J］.儀器儀表學(xué)報(bào)，2014，35（2）：261-268.

劉 政（1981-），男，講師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，智能儀器，davidbetty@163.com。

Node Localization Algorithm Based on Particle Swarm Optimization and Multidimensional Scaling*

LIU Zheng*
（Department of Automation，Guilin University of Aerospace Technology，Guilin Guangxi 541004，China）

Aiming to reduce the interference with the external environment in position algorithms for wireless sensor networks，an improved multidimensional scaling algorithm based on particle swarm optimization is proposed.RSSI based on dynamic path loss exponent is used to range，establish a distance matrix，build a relative coordinate with multidimensional scaling，and acquire absolute coordinate through four parameters coordinate transformation model.Then the difference of relative coordinate between absolute coordinate is utilized as the fitness function of particle swarm optimization and optimizes the node position estimation through sub-swarm search.The simulation reveals that the improved algorithm has good robustness to actual environmental impact，improves the node localization accuracy，and satisfies the needs of positioning system.

wireless sensor networks；node localization；multidimensional scaling；particle swarm optimization

TP393

A

1004-1699（2015）08-1228-05

??7230

10.3969/j.issn.1004-1699.2015.08.021

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61202007）；桂林航天工業(yè)學(xué)院基金項(xiàng)目（YJ1302）

2014-11-13 修改日期：2015-05-27