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

李 鋒

(廣東交通職業(yè)技術學院計算機工程學院 廣東 廣州 510650)

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

李 鋒

(廣東交通職業(yè)技術學院計算機工程學院 廣東 廣州 510650)

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

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

0 引 言

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

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

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

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

1 標準粒子群算法

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

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

(1)

(2)

(3)

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

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

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

定義與目的節(jié)點相鄰的四個特征節(jié)點向量A(xa,ya,za)、B(xb,yb,zb)、C(xc,yc,zc)和D(xd,yd,zd)。初始化搜索空間與粒子狀態(tài)，選出最小值和最大值構成矩形搜索邊界區(qū)域，邊界點分別為T1(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)。粒子將在此該閉空間按照適應度大小迭代搜索四個特征向量。

2.2 構建適應度函數(shù)

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

(4)

其中RSSI(d)為距離源節(jié)點d處接收到的信號強度，RSSI(d0)為距離d0處測得的信號強度，β為路徑衰減指數(shù)，Xδ為標準偏差為δ的正態(tài)隨機變量。

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

(z-zi)2-dn2)]

(5)

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

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

2.3PSO算法流程

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

(2) 根據(jù)式(5)適應度評價函數(shù)計算當前每個粒子適應值；

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

(4) 計算當前Fi適應度值Fibest，如果Fibest

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

3 定位過程

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

(6)

由lAB和lAC可求出內切圓O1圓心S1，其坐標為：

(7)

內切圓O2圓心S2坐標為：

(8)

(9)

(10)

取直線l1與l2交點計算球心坐標，定位節(jié)點位置：

(11)

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

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

(12)

目的節(jié)點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上任意一點p坐標為(xp,yp,zp)，代入式(13)得出直線l對稱方程：

(14)

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

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

(15)

計算三個平面交點區(qū)域重心坐標:

(16)

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

4 仿真測試

4.1 測試環(huán)境

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

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

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

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

4.3 移動節(jié)點定位誤差比較

對200節(jié)點在[0,5]區(qū)間內隨機初始化移動速度，平均定位誤差評價公式為：

(17)

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

圖6 移動節(jié)點定位誤差圖

5 結 語

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

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

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

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

[4] 呂良彬，曹陽，高洵，等.基于球殼交集的傳感器網(wǎng)絡三維定位算法[J].北京郵電大學學報,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。全國交通運輸職業(yè)教育教學指導委員會2015年交通運輸職業(yè)教育科研項目(2015B21)；廣東省高等職業(yè)技術教育研究會重點課題(GDGZ15Z007)；中國交通教育研究會教育科學研究課題(1402-136)。。李鋒，講師，主研領域：計算機系統(tǒng)結構和網(wǎng)絡安全。

TP393

A

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