葛文庚, 陳 萍

(黃淮學(xué)院信息工程學(xué)院，河南駐馬店 463000)

0 引言

節(jié)點(diǎn)定位已成為無線傳感網(wǎng)絡(luò)(wireless sensor networks, WSNs)領(lǐng)域的焦點(diǎn)[1-4]，研究人員提出了測(cè)距定位算法、非測(cè)距定位算法等。測(cè)距定位算法雖然精度較高，但因?yàn)樾枰母吖β嗜ゾS持未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的通信，而節(jié)點(diǎn)常采用小電池容量供電，應(yīng)用局限性較大。非測(cè)距定位算法主要分為兩類：?jiǎn)l(fā)式和分析式定位算法[5-7]。DV-Hop就是典型的啟發(fā)式算法，通過未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的跳數(shù)估計(jì)它們間的距離；分析式算法是基于節(jié)點(diǎn)具有圓形無線電傳播模型假設(shè)(radio propagation pattern, RPP)利用理論分析并推導(dǎo)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離[6-7]。

文獻(xiàn)[8]提出的分布式求精算法，引用“磁極”思想，縮小定位誤差，但未考慮無線電傳播模型問題；文獻(xiàn)[9]提出基于遺傳優(yōu)化DV-Hop定位算法，但該算法與文獻(xiàn)[8]存在同樣沒有考慮到無線電傳播模型對(duì)定位精度影響的問題。而在真實(shí)的傳輸環(huán)境中，常存在信號(hào)衰落、陰影以及干擾、各向異性的信號(hào)衰減等因素，導(dǎo)致節(jié)點(diǎn)的傳輸模型為非圓形RPP[10]。

為此，提出面向非圓形RPP的基于人工神經(jīng)網(wǎng)絡(luò)的加權(quán)質(zhì)心定位算法(artificial neural networks-based weighted centroid localization, ANNs-WCL)。ANNs-WCL算法充分考慮了因非圓形RPP問題，建立新的測(cè)距模型，然后再應(yīng)用人工神經(jīng)網(wǎng)絡(luò)修正測(cè)距，最后利用加權(quán)質(zhì)心定位算法估計(jì)未知節(jié)點(diǎn)位置。仿真結(jié)果表明，提出的ANNs-WCL算法能夠有效地降低均方根誤差。

1 網(wǎng)絡(luò)模型以及問題表述

1.1 網(wǎng)絡(luò)模型

N個(gè)傳感節(jié)點(diǎn)隨機(jī)分布于二維網(wǎng)絡(luò)?？紤]全球定位系統(tǒng)GPS的成本，僅部分節(jié)點(diǎn)配備了GPS，這些節(jié)點(diǎn)知曉自己的位置，為錨節(jié)點(diǎn)。而未裝備GPS的節(jié)點(diǎn)稱為未知節(jié)點(diǎn)。假定，未知節(jié)點(diǎn)的位置坐標(biāo)為θ=[x,y]T，且θ∈R2。通過m個(gè)錨節(jié)點(diǎn)估計(jì)未知的位置。第k個(gè)錨節(jié)點(diǎn)的位置為β=[xk,yk]T，且k=1,2,…,m。所有節(jié)點(diǎn)的傳輸半徑為R。

1.2 問題描述

非圓形的RPP如圖1所示，傳感節(jié)點(diǎn)分布于面積為S2的區(qū)域。實(shí)線的圓圈表示圓狀的RPP，而虛線表示非圓形的RPP。

圖1 網(wǎng)絡(luò)模型

如果在定位算法中仍假定節(jié)點(diǎn)的傳輸范圍是圓形RPP，必然會(huì)引起測(cè)距誤差。因此，考慮利用ANNs系統(tǒng)訓(xùn)練定位模型，修正測(cè)距值。

2 測(cè)距原理

(1)

式中ni,k表示節(jié)點(diǎn)i離錨節(jié)點(diǎn)k的跳數(shù)；hav表示平均每跳的距離。

對(duì)于高節(jié)點(diǎn)密度情況，常采用泊松有限理論估計(jì)hav，或者引用所有最短路徑的平均跳距代替hav。

(2)

假定節(jié)點(diǎn)傳輸范圍為圓形RPP，首先定義重疊區(qū)域A，如圖2所示。未知節(jié)點(diǎn)i以自己位置為圓心，以傳輸距離R為半徑形成的圓表示為D(i,R)。類似地，錨節(jié)點(diǎn)k也以自己的位置為圓心，以ni,kR為半徑的圓，即D(k,ni,kR)。因此，重疊的圓A的定義如式(3)所示。

圖2 重疊區(qū)域

A=D(k,ni,kR)∩D(i,R)

(3)

(4)

式中ψ(A)為di,k與A的關(guān)系函數(shù)；Amin和Amax分別表示A的最小值和最大值；fA(a)為概率密度函數(shù)。

利用地理特性和幾何知識(shí)，可得式(5)[11]：

(5)

式中Φ=ψ-1表示ψ的逆函數(shù)。由于Φ(di,k)是關(guān)于di,k的復(fù)雜函數(shù)，推導(dǎo)ψ(A)閉合表達(dá)式比較復(fù)雜。

此外, 假定A均勻分布于[Amin,Amax]。當(dāng)di,k=ni,kR時(shí)，A取最大值A(chǔ)max；而當(dāng)di,k=(ni,k-1)R時(shí)，A取最小值A(chǔ)min。因此，可得概率密度函數(shù)fA(a)的表達(dá)式為：

(6)

(7)

式中，Φ(1)是Φ的一階導(dǎo)數(shù)。

(8)

3 ANNs-WCL定位

ANNs-WCL定位算法主要由3個(gè)階段構(gòu)成。第一階段，未知節(jié)點(diǎn)以多跳方式收集信息，然后再利用式(8)估計(jì)離錨節(jié)點(diǎn)間的距離；第二階段，利用ANNs修正測(cè)距，降低測(cè)距誤差；最后，利用加權(quán)質(zhì)心定位算法，估計(jì)未知節(jié)點(diǎn)位置。

3.1 未知節(jié)點(diǎn)測(cè)距

在ANNS-WCL定位過程中，首先錨節(jié)點(diǎn)廣播數(shù)據(jù)包，由首部和數(shù)據(jù)兩部分構(gòu)成。首部包含錨節(jié)點(diǎn)位置，而數(shù)據(jù)部分存有跳數(shù)值，且最初跳數(shù)值為1。

圖3 轉(zhuǎn)發(fā)數(shù)據(jù)包的流程

3.2 測(cè)距修正

圖4 測(cè)距修正過程

3.3 加權(quán)的質(zhì)心定位算法

依據(jù)3.2節(jié)測(cè)距修正后，未知節(jié)點(diǎn)獲取距多個(gè)錨節(jié)點(diǎn)的距離。再?gòu)闹羞x擇離自己最近的4個(gè)錨節(jié)點(diǎn)，即利用測(cè)距值最小的4個(gè)錨節(jié)點(diǎn)構(gòu)成加權(quán)質(zhì)心定位算法。

假定Aa，Ab，Ac，Ad分別為已選的4個(gè)錨節(jié)點(diǎn)，相應(yīng)的，ra,rb,rc,rd分別表示離未知節(jié)點(diǎn)i的距離。首先，以錨節(jié)點(diǎn)為圓心，以離未知節(jié)點(diǎn)的距離為半徑畫圓，4個(gè)錨節(jié)點(diǎn)共形成4個(gè)圓，有4個(gè)交點(diǎn)，假定交點(diǎn)分別為O1,O2,O3,O4。然后，依據(jù)這4個(gè)交點(diǎn)構(gòu)成4個(gè)不同的三角形，再計(jì)算這4個(gè)三角形的質(zhì)心。傳統(tǒng)的質(zhì)心定位算法就是將4個(gè)質(zhì)心坐標(biāo)的均值作為未知節(jié)點(diǎn)的位置。引用加權(quán)質(zhì)心定位算法，即計(jì)算每個(gè)質(zhì)心的權(quán)值，再依據(jù)這些權(quán)值，估計(jì)未知節(jié)點(diǎn)的位置。

以Aa,Ab,Ac這3個(gè)圓為例，其交點(diǎn)分別為O1,O2,O3。利用3個(gè)圓的半徑ra，rb，rc以及3個(gè)錨節(jié)點(diǎn)Aa，Ab，Ac的坐標(biāo)(Xa,Ya)，(Xb,Yb)，(Xc,Yc)，可計(jì)算3個(gè)交點(diǎn)坐標(biāo)。可利用式(9)所示的方程組中任意兩個(gè)等式求解交點(diǎn)O1的坐標(biāo)(XO1,YO1)：

(9)

同理可計(jì)算其他交點(diǎn)的坐標(biāo)。計(jì)算交點(diǎn)O1,O2,O3坐標(biāo)后，便可計(jì)算這由3個(gè)交點(diǎn)所構(gòu)成的三角形的質(zhì)心E1坐標(biāo)(X1,Y1)：

(10)

圖5 加權(quán)質(zhì)心定位算法

(11)

4 性能仿真

4.1 仿真環(huán)境

利用MATLAB7.1軟件建立仿真平臺(tái)，節(jié)點(diǎn)隨機(jī)分布于100 m×100 m區(qū)域。節(jié)點(diǎn)傳輸半徑為18 m，錨節(jié)點(diǎn)數(shù)為20。此外，利用文獻(xiàn)[10]非圓形的RPP模型，并引用變量不圓形度DDOI。

為了更好地分析ANNs-WCL定位算法的性能，選用同類算法DV-Hop[5]、LAEP[6]和MLPNN-CGFR[12]進(jìn)行比較。同時(shí)，引用均方根誤差ERMS作為性能指標(biāo)：

(12)

4.2 定位的ERMS

首先考查ERMS隨節(jié)點(diǎn)數(shù)N和DDOI的變化情況，實(shí)驗(yàn)數(shù)據(jù)如圖6所示，其中圖6(a)表示在DDOI=0.06時(shí)，節(jié)點(diǎn)數(shù)N從200變化至800時(shí)，ERMS的變化數(shù)據(jù)；圖6(b)表示在N=300時(shí)，節(jié)點(diǎn)數(shù)DDOI從0變化至0.15時(shí)，ERMS的變化數(shù)據(jù)。

圖6 定位的歸一化的均方根誤差

從圖6(a)可知，在DDOI=0.06時(shí)，ERMS隨節(jié)點(diǎn)數(shù)的增加而下降，節(jié)點(diǎn)數(shù)增加，獲取的網(wǎng)絡(luò)拓?fù)湫畔⒃蕉?，越有利于定位精度的上升。與DV-Hop[5]、LAEP[6]和MLPNN-CGFR[10]相比，提出的ANNs-WCL算法的ERMS得到有效下降。當(dāng)N=400時(shí)，ANNs-WCL算法的ERMS為0.4 m，而LAEP、DV-hop和MLPNN-CGFR的ERMS分別高達(dá)1.31 m，1.1 m，0.98 m。

從圖6(b)可知，在N=300時(shí)，ERMS隨DDOI增加而上升。原因在于：DDOI越高，節(jié)點(diǎn)的RPP模型越偏離圓形，測(cè)距誤差越大，最終，定位精度就下降。與圖6(a)類似，與DV-Hop、LAEP和MLPNN-CGFR相比，ANNs-WCL的ERMS仍是最低的。這些數(shù)據(jù)表明，ANNs-WCL算法能夠在真實(shí)環(huán)境中獲取高的定位精度。

4.3 ERMS的CDF曲線

N=300，DDOI=0.06四個(gè)算法ERMS的累積分布函數(shù)FCDF曲線如圖7，且從圖7可知，提出的ANNs-WCL定位算法有99%節(jié)點(diǎn)獲取同一個(gè)定位精度，而MLPNN-CGFR只有61%，DV-Hop只有43%，而LAEP僅為30%。這些數(shù)據(jù)表明，在存在異構(gòu)信號(hào)衰減的環(huán)境下，ANNs-WCL定位性能優(yōu)于同類算法。

圖7 CDF曲線

5 總結(jié)

針對(duì)真實(shí)環(huán)境中的非圓形RPP問題，提出面向非圓形RPP的基于人工神經(jīng)網(wǎng)絡(luò)的加權(quán)質(zhì)心定位算法 ANNs-WCL。ANNs-WCL算法先推理測(cè)距表達(dá)式，然后利用ANNs修正測(cè)距值，最后，利用加權(quán)質(zhì)心定位算法估計(jì)未知節(jié)點(diǎn)位置。仿真結(jié)果表明，提出的ANNs-WCL算法能夠有效地降低均方根誤差，提高了定位精度。