李 鋒

(廣東交通職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程學(xué)院 廣東 廣州 510650)

粒子群APIS-3D算法在三維傳感網(wǎng)絡(luò)中的定位研究

李 鋒

(廣東交通職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程學(xué)院 廣東 廣州 510650)

無(wú)線傳感網(wǎng)絡(luò)三維空間定位算法大都是將二維向量轉(zhuǎn)化為三維空間，其原理與平面定位基本相同，實(shí)現(xiàn)簡(jiǎn)單，沒(méi)有考慮節(jié)點(diǎn)移動(dòng)對(duì)定位偏差的影響。提出一種基于粒子群APIS-3D定位算法，利用粒子模擬節(jié)點(diǎn)移動(dòng)狀態(tài)，并根據(jù)RSSI信號(hào)指紋的動(dòng)態(tài)反饋過(guò)程建立適應(yīng)度函數(shù)，通過(guò)定位球體交集區(qū)域重心以計(jì)算節(jié)點(diǎn)坐標(biāo)。仿真實(shí)驗(yàn)證明，新算法在保持抽樣概率不變情況下，對(duì)移動(dòng)節(jié)點(diǎn)平均定位偏差在2.42%以?xún)?nèi)，能很好滿(mǎn)足工程應(yīng)用要求。

無(wú)線傳感網(wǎng)絡(luò) 三維定位 APIS-3D RSSI

0 引 言

無(wú)線傳感網(wǎng)絡(luò)是一種由大量傳感節(jié)點(diǎn)構(gòu)成的分布式網(wǎng)絡(luò)系統(tǒng)。由于傳感節(jié)點(diǎn)采集到的信息通常與其自身位置相關(guān)，因此對(duì)節(jié)點(diǎn)定位是無(wú)線傳感網(wǎng)絡(luò)首要解決的基礎(chǔ)問(wèn)題。在實(shí)際工程中，傳感器往往會(huì)隨機(jī)空投至三維區(qū)域，如對(duì)高地森林、海洋湖泊和太空的觀測(cè)等，并會(huì)隨洋流和空間的變化而移動(dòng)。對(duì)三維空間移動(dòng)節(jié)點(diǎn)定位成為無(wú)線傳感網(wǎng)絡(luò)研究的難點(diǎn)和熱點(diǎn)。

與二維平面相比，三維空間節(jié)點(diǎn)定位更為復(fù)雜，定位精準(zhǔn)度和穩(wěn)定性亟待提高。其中3D DV-Hop算法、3D DV-Distance算法和3D Centorid算法只是簡(jiǎn)單地將二維向量轉(zhuǎn)化為三維空間，其原理與二維平面定位基本相同，算法簡(jiǎn)單，但定位精度較低[1,2]?；谇驓そ患腁PIS定位算法以節(jié)點(diǎn)為球心，以鄰居節(jié)點(diǎn)距離為半徑，將三維空間劃分成不同大小的同心球體，通過(guò)判斷定位節(jié)點(diǎn)是否在球體區(qū)域并計(jì)算區(qū)域重心以定位節(jié)點(diǎn)坐標(biāo)，定位精確程度與其鄰居節(jié)點(diǎn)位置相關(guān)。Landscape 3D算法通過(guò)接收鄰居節(jié)點(diǎn)位置信息和RSSI指紋轉(zhuǎn)換為參考距離完成節(jié)點(diǎn)定位。受環(huán)境影響較大，定位穩(wěn)定性不高[3]。APIS-3D算法結(jié)合APIS和Landscape 3D兩者思想[4]，通過(guò)交換鄰居節(jié)點(diǎn)位置信息并根據(jù)RSSI接收信號(hào)強(qiáng)度計(jì)算鄰居節(jié)點(diǎn)參考距離，然后將周邊區(qū)域劃分成多個(gè)互相重疊的球體，根據(jù)判斷節(jié)點(diǎn)位于哪個(gè)球體內(nèi)部和利用窮盡組合方式計(jì)算球體交集區(qū)域重心實(shí)現(xiàn)節(jié)點(diǎn)定位，算法復(fù)雜，但定位精度較高，對(duì)環(huán)境依賴(lài)程度較小，見(jiàn)圖1所示。

圖1 APIS-3D 節(jié)點(diǎn)定位圖

然而，上述三維空間定位過(guò)程都沒(méi)有考慮到節(jié)點(diǎn)移動(dòng)問(wèn)題，在實(shí)際工程中傳感節(jié)點(diǎn)往往會(huì)因洋流和空氣對(duì)流影響而漂移。鄰居之間交換的RSSI信號(hào)指紋是一個(gè)動(dòng)態(tài)變化過(guò)程。假如算法利用RSSI信號(hào)指紋形成動(dòng)態(tài)反饋機(jī)制，不僅可以適應(yīng)節(jié)點(diǎn)位置變化，減少對(duì)節(jié)點(diǎn)密度依賴(lài)程度，還可以有效提高定位精準(zhǔn)度和標(biāo)識(shí)移動(dòng)軌跡。因此本文提出一種基于粒子群的APIS-3D 定位算法，利用粒子模擬節(jié)點(diǎn)移動(dòng)狀態(tài)，并根據(jù)RSSI信號(hào)指紋的動(dòng)態(tài)反饋過(guò)程建立適應(yīng)度函數(shù)，發(fā)揮粒子群快速收斂?jī)?yōu)勢(shì)找出四個(gè)鄰居節(jié)點(diǎn)向量，最后通過(guò)定位球體交集區(qū)域重心以計(jì)算節(jié)點(diǎn)坐標(biāo)。

1 標(biāo)準(zhǔn)粒子群算法

粒子群PSO算法是基于鳥(niǎo)類(lèi)群體覓食行為研究的模擬算法。在封閉空間中，鳥(niǎo)群隨機(jī)搜索食物，假如所有的鳥(niǎo)都知道當(dāng)前位置與食物節(jié)點(diǎn)之間距離，找到全局最優(yōu)解的方法則可以轉(zhuǎn)換為從其最近的鳥(niǎo)周?chē)鷧^(qū)域方向搜尋[5，6]。在標(biāo)準(zhǔn)粒子群算法中，搜索空間的每只鳥(niǎo)對(duì)應(yīng)尋找全局最優(yōu)的每個(gè)解，稱(chēng)為粒子，每個(gè)粒子的初始狀態(tài)代表鳥(niǎo)的當(dāng)前位置和飛行速度。每個(gè)粒子通過(guò)搜尋附近粒子最優(yōu)信息以改變當(dāng)前位置和方向，直到找出全局最優(yōu)解。算法思想如下：

在一個(gè)d維搜索空間，存在由n個(gè)粒子組成的粒子群X[7-9]，X=(X1，X2，…，Xn)T。定義第i個(gè)粒子位置信息為Xi=(Xi1，Xi2，…，Xid)T，速率為Vi=(Vi1，Vi2，…，Vid)T，第i個(gè)粒子的極值為Pi=(Pi1，Pi2，…，Pid)T，粒子群全局極值為Pg=(Pg1，Pg2，…，Pgd)T，則每個(gè)粒子以全局最優(yōu)解出發(fā)，按式(1)-式(3)更新當(dāng)前位置和速度：

(1)

(2)

(3)

2 粒子群算法在節(jié)點(diǎn)定位中的作用

2.1 初始化節(jié)點(diǎn)和搜索空間

在RSSI指紋信號(hào)定位中，粒子群中的每個(gè)粒子代表傳感網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，定義由n個(gè)粒子組成的粒子群X，X=(X1，X2，…，Xn)T，令第i個(gè)粒子位置信息為Xi=(Xi1，Xi2，…，Xid)T，速率是Vi=(Vi1，Vi2，…，Vid)T，第i個(gè)粒子極值為Pi=(Pi1，Pi2，…，Pid)T，例子種群全局極值是Pg=(Pg1，Pg2，…，Pgd)T。

定義與目的節(jié)點(diǎn)相鄰的四個(gè)特征節(jié)點(diǎn)向量A(xa,ya,za)、B(xb,yb,zb)、C(xc,yc,zc)和D(xd,yd,zd)。初始化搜索空間與粒子狀態(tài)，選出最小值和最大值構(gòu)成矩形搜索邊界區(qū)域，邊界點(diǎn)分別為T(mén)1(xmin,ymin,zmin)、 T2(xmax,ymin,zmin)、T3(xmin,ymax,zmin)、T4(xmax,ymax,zmin)、T5(xmin,ymax,zmax)、T6(xmax,ymin,zmax)、T7(xmin,ymax,zmax)、T8(xmax,ymax,zmax)。粒子將在此該閉空間按照適應(yīng)度大小迭代搜索四個(gè)特征向量。

2.2 構(gòu)建適應(yīng)度函數(shù)

搜集鄰居之間交換的RSSI動(dòng)態(tài)信號(hào)指紋形成反饋機(jī)制以建立適應(yīng)度評(píng)價(jià)函數(shù)，其中RSSI信號(hào)傳播損耗模型公式為：

(4)

其中RSSI(d)為距離源節(jié)點(diǎn)d處接收到的信號(hào)強(qiáng)度，RSSI(d0)為距離d0處測(cè)得的信號(hào)強(qiáng)度，β為路徑衰減指數(shù)，Xδ為標(biāo)準(zhǔn)偏差為δ的正態(tài)隨機(jī)變量。

建立適應(yīng)度函數(shù)是為了迭代搜索特征向量坐標(biāo)，尋找四個(gè)鄰居節(jié)點(diǎn)特征向量的過(guò)程通過(guò)PSO算法轉(zhuǎn)變?yōu)榍蠼馀c目的節(jié)點(diǎn)距離最小的方程組近優(yōu)解。適應(yīng)度函數(shù)為：

(z-zi)2-dn2)]

(5)

每個(gè)粒子找到下一粒子后按式(1)-式(3)更新當(dāng)前位置和速率，從而找出全局四個(gè)近優(yōu)解。粒子群搜索空間和位置更新過(guò)程見(jiàn)圖2所示。

圖2 粒子搜索空間和位置更新圖

2.3PSO算法流程

(1) 初始化粒子種群和搜索空間，定義慣性權(quán)重W和最大迭代次數(shù)m；

(2) 根據(jù)式(5)適應(yīng)度評(píng)價(jià)函數(shù)計(jì)算當(dāng)前每個(gè)粒子適應(yīng)值；

(3) 更新個(gè)體最優(yōu)值點(diǎn)和全局最優(yōu)點(diǎn)。對(duì)每個(gè)粒子而言，比較下一位置點(diǎn)的適應(yīng)值Fi和當(dāng)前最優(yōu)值Pibest，如果Fi< Pibest,則更新Pibest；

(4) 計(jì)算當(dāng)前Fi適應(yīng)度值Fibest，如果Fibest

(5) 判定是否滿(mǎn)足結(jié)束條件，若超出迭代次數(shù)m或者Fgbest小于閾值δ，則計(jì)算特征點(diǎn)向量坐標(biāo)，算法終止，否則返回步驟(2)。

3 定位過(guò)程

3.1 特征點(diǎn)都在同心球體區(qū)域的定位過(guò)程

(6)

由lAB和lAC可求出內(nèi)切圓O1圓心S1，其坐標(biāo)為：

(7)

內(nèi)切圓O2圓心S2坐標(biāo)為：

(8)

(9)

(10)

取直線l1與l2交點(diǎn)計(jì)算球心坐標(biāo)，定位節(jié)點(diǎn)位置：

(11)

圖3 相同球體區(qū)域節(jié)點(diǎn)定位圖

3.2 特征點(diǎn)在不同球體區(qū)域的定位過(guò)程

(12)

目的節(jié)點(diǎn)S在球S1、S2和S3交集區(qū)域重心，則S在平面N1與N2的交線l上，由式(11)求出交線l方向向量為：

(xd-xc,yd-yc,zd-zc)=(i,j,k)

(13)

其中，i、j、k是直線l的方向向量。

令直線l上任意一點(diǎn)p坐標(biāo)為(xp,yp,zp)，代入式(13)得出直線l對(duì)稱(chēng)方程：

(14)

則經(jīng)過(guò)點(diǎn)p并且垂直于直線l的平面Nr(r=1,2,3)為：

Nr:i(x-xp)+j(y-yp)+k(z-zp)=0

(15)

計(jì)算三個(gè)平面交點(diǎn)區(qū)域重心坐標(biāo):

(16)

圖4 不同球體區(qū)域節(jié)點(diǎn)定位圖

4 仿真測(cè)試

4.1 測(cè)試環(huán)境

仿真環(huán)境設(shè)為100×100×100三維空間，未知節(jié)點(diǎn)數(shù)量200，錨節(jié)點(diǎn)數(shù)量20，其中錨節(jié)點(diǎn)統(tǒng)一均勻放置，其他節(jié)點(diǎn)隨機(jī)放置，節(jié)點(diǎn)通信半徑為10m，初始化粒子群規(guī)模300，最大迭代次數(shù)m=500。

4.2 靜止節(jié)點(diǎn)定位誤差比較

新算法和APIS-3D算法定位誤差見(jiàn)圖5所示。在APIS-3D算法中，節(jié)點(diǎn)定位最大誤差0.771米，平均定位誤差0.306米，定位比例為98.381%。新算法節(jié)點(diǎn)定位最大誤差0.427米，平均定位誤差0.162米，定位比例為99.57%。由于節(jié)點(diǎn)靜止，PSO適應(yīng)度函數(shù)的動(dòng)態(tài)反饋機(jī)制得不到有效發(fā)揮，兩者定位結(jié)果差別不大，但新算法更為精確。

圖5 靜止節(jié)點(diǎn)定位誤差圖

4.3 移動(dòng)節(jié)點(diǎn)定位誤差比較

對(duì)200節(jié)點(diǎn)在[0,5]區(qū)間內(nèi)隨機(jī)初始化移動(dòng)速度，平均定位誤差評(píng)價(jià)公式為：

(17)

測(cè)試結(jié)果見(jiàn)圖6所示。其中三角形表示節(jié)點(diǎn)物理位置，圓圈表示APIS-3D估算位置，星號(hào)是新算法估算位置。從圖中可以看出，APIS-3D算法對(duì)移動(dòng)節(jié)點(diǎn)定位不理想，節(jié)點(diǎn)移動(dòng)對(duì)定位結(jié)果產(chǎn)生較大影響，平均偏差達(dá)5.316%。而新算法在保持抽樣概率不變的情況下，通過(guò)適應(yīng)度函數(shù)動(dòng)態(tài)反饋機(jī)制更新粒子當(dāng)前位置和速率，快速收斂找到全局近優(yōu)解計(jì)算節(jié)點(diǎn)坐標(biāo)，平均偏差為2.42%。新算法對(duì)移動(dòng)節(jié)點(diǎn)定位優(yōu)勢(shì)明顯。

圖6 移動(dòng)節(jié)點(diǎn)定位誤差圖

5 結(jié) 語(yǔ)

本文提出一種基于粒子群APIS-3D定位算法，能有效發(fā)揮粒子群正向反饋和快速收斂?jī)?yōu)勢(shì)定位節(jié)點(diǎn)坐標(biāo)。下一步工作將計(jì)算和仿真節(jié)點(diǎn)運(yùn)動(dòng)軌跡，并對(duì)算法收斂性進(jìn)行細(xì)致分析，從而提高算法性能，降低節(jié)點(diǎn)功耗。

[1] 張榮磊,劉琳嵐,舒堅(jiān),等.基于多維定標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法[J].計(jì)算機(jī)應(yīng)用研究，2009,26(8):3100-3104.

[2] 朱紅霞,陳曙.一種新的基于非測(cè)距的無(wú)線傳感器網(wǎng)絡(luò)三維定位算法[J].傳感技術(shù)學(xué)報(bào)，2009,22(11):1655-1660.

[3] 金衛(wèi)民,神顯豪.基于RSSI的室外無(wú)線傳感網(wǎng)絡(luò)自定位算法[J].計(jì)算機(jī)工程,2008,34(13):89-91.

[4] 呂良彬，曹陽(yáng)，高洵，等.基于球殼交集的傳感器網(wǎng)絡(luò)三維定位算法[J].北京郵電大學(xué)學(xué)報(bào),2006,29(Sup.):48-51.

[5]HeT,HuangCD,BlumBM,etal.Range-freelocaliza-tionschemesforlargescalesensornetworks[C]//Proceedingsofthe9thAnnualInternationalConferenceonMobileComputingandNetworking，2003:81-95.

[6]GaneriwalS,KumarR,SrivastavaMB.Timing-SyncProtocolforSensorNetwork[C]//Proceedingsofthe1stinternationalconferenceonEmbeddednetworkedsensorsystems，2003:138-149.

[7]PoJenChuang,ChengPeiWu.AnEffectivePSO-BasedNodeLocalizationSchemeforWirelessSensorNetworks[C]//the2008NinthInternationalConferenceononParallelandDistributedComputing,ApplicationsandTechnologies，2008:187-194.

[8]SzynkiewiczEN,MarksM.OptimizationSchemesforWirelessSensorNetworksLocalization[J].InternationalJournalofAppliedMathematicsandComputerScience，2009,19(2):291-302.

[9]DenisB,PierrotJB,RjeilyCA.JointdistributedsynchronizationandpositioninginUWBAdhocnetworksusingTOA[J].IEEETransactionsonMicrowaveTheoryandTechniques，2006,54(4):1896-1911.

RESEARCH ON LOCATION OF PSO AND APIS-3D ALGORITHM IN 3D WSN

Li Feng

(SchoolofComputerEngineering,GuangdongCommunicationPolytechnic,Guangzhou510650,Guangdong,China)

3D space location algorithms of wireless sensor networks are mostly to convert the 2D vector into 3D space,its principle is basically the same as plane location and is simple in implementation,but does not consider the impact of node mobility on location errors.This paper puts forward a new PSO and APIS-3D-based location algorithm,it uses particles to simulate node mobility status, sets up fitness function according to the dynamic feedback process of RSSI signal fingerprint, and calculates the coordinate of nodes by locating the centre of gravity of sphere intersection region.Simulation experimental results show that the new algorithm achieves the average location error less than 2.42% on mobile nodes under the condition of keeping the sampling probability unchanged,and can well meet the requirements of engineering applications.

Wireless sensor networks 3D location APIS-3D RSSI

2015-07-21。全國(guó)交通運(yùn)輸職業(yè)教育教學(xué)指導(dǎo)委員會(huì)2015年交通運(yùn)輸職業(yè)教育科研項(xiàng)目(2015B21)；廣東省高等職業(yè)技術(shù)教育研究會(huì)重點(diǎn)課題(GDGZ15Z007)；中國(guó)交通教育研究會(huì)教育科學(xué)研究課題(1402-136)。。李鋒，講師，主研領(lǐng)域：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)和網(wǎng)絡(luò)安全。

TP393

A

10.3969/j.issn.1000-386x.2017.03.059