基于三維球形分割的無(wú)線傳感器網(wǎng)絡(luò)定位算法*

徐 兵,項(xiàng)順伯,吳憲君

(廣東石油化工學(xué)院 計(jì)算機(jī)與電子信息學(xué)院,廣東 茂名 525000)

隨著科學(xué)技術(shù)的飛速發(fā)展,無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)在各個(gè)行業(yè)及領(lǐng)域都得到了極大的應(yīng)用;當(dāng)前階段,WSN節(jié)點(diǎn)定位已經(jīng)成為研究的趨勢(shì)與焦點(diǎn)[1-7],它直接影響數(shù)據(jù)檢測(cè)、路由等信息。當(dāng)前,無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位技術(shù)主要包括非測(cè)距與測(cè)距。非測(cè)距定位算法成本相對(duì)偏低,容易實(shí)施,但是定位精度偏低,而測(cè)距定位算法具有較高的精度,但其成本開銷也相應(yīng)較大?；跍y(cè)距的定位算法通過(guò)分析RSSI根據(jù)路徑傳輸損耗模型計(jì)算接收距離,此方法需要依賴充足的經(jīng)驗(yàn),且計(jì)算結(jié)果容易受環(huán)境變化的影響。而無(wú)需測(cè)距的定位算法主要利用網(wǎng)絡(luò)連通性等信息、通過(guò)布置信標(biāo)節(jié)點(diǎn)來(lái)實(shí)現(xiàn)定位,定位精度較高。傳統(tǒng)非測(cè)距定位算法主要分為如下3個(gè)階段:①錨節(jié)點(diǎn)通過(guò)廣播自身信息,讓其余節(jié)點(diǎn)獲得與錨節(jié)點(diǎn)相同的最小跳數(shù);②根據(jù)步驟①獲得跳數(shù)及位置信息計(jì)算錨節(jié)點(diǎn)之間的平均距離;③重復(fù)上述步驟①、步驟②直到待定位節(jié)點(diǎn)獲取到 3個(gè)或3個(gè)以上的錨節(jié)點(diǎn)位置時(shí),通過(guò)幾何算法對(duì)待定位節(jié)點(diǎn)位置進(jìn)行確定,結(jié)束算法。

基于測(cè)距的定位方法有RSSI、ARL、SzAPSO、CALL等。文獻(xiàn)[8]提出一種比較常用的通信測(cè)距的方式,即不確定性數(shù)據(jù)聚類方式,借助數(shù)學(xué)統(tǒng)計(jì)特征以實(shí)現(xiàn)較高精度定位。文獻(xiàn)[9]明確指出,ARL定位算法可以對(duì)節(jié)點(diǎn)之間的平均距離予以準(zhǔn)確估算,繼而獲得準(zhǔn)確的位置信息,同時(shí)檢驗(yàn)該信息是否可信,通過(guò)仿真實(shí)驗(yàn)表明了算法具有有效性和安全性。文獻(xiàn)[10]通過(guò)利用SzAPSO方法和相鄰未知節(jié)點(diǎn)之間的距離約束實(shí)現(xiàn)定位,這樣可以降低錨節(jié)點(diǎn)密度,并且無(wú)需至少和3個(gè)錨節(jié)點(diǎn)相鄰。文獻(xiàn)[11]通過(guò)提出構(gòu)件方式來(lái)建立一種CALL定位算法,以此提高節(jié)點(diǎn)之間的合作關(guān)系。通過(guò)大量文獻(xiàn)數(shù)據(jù),我們找到幾種以非測(cè)距定位方法,具體包括以下幾種類型,分別為MDS-MAP、DV-hop等。文獻(xiàn)[12]詳細(xì)地闡述了 DV-hop 算法存在的問(wèn)題,并予以完善及修正,顯著提升定位精度,其核心思路是基于錨節(jié)點(diǎn)信任度求解未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離。文獻(xiàn)[13]使用輔助變量將自定位問(wèn)題表述為線性最小二乘問(wèn)題,并基于封閉形式的解決方案建立了一種新的基于輔助變量的偽線性估計(jì)器。文獻(xiàn)[14]提出了一種新的與位置相關(guān)的密鑰管理協(xié)議LKMP,并且與現(xiàn)有的依賴于位置的端到端數(shù)據(jù)安全性和MKMP方案相比,該方案在數(shù)據(jù)機(jī)密性、計(jì)算和通信方面具有較大優(yōu)勢(shì)。文獻(xiàn)[15]提出的Hophole定位方法是基于跳數(shù)距離的,并且能夠較好地解決有洞的各項(xiàng)異性的網(wǎng)絡(luò)節(jié)點(diǎn)定位問(wèn)題。文獻(xiàn)[16]在分簇機(jī)制上以選擇鄰居節(jié)點(diǎn)最多的節(jié)點(diǎn)作為起始節(jié)點(diǎn),融合三角不等式法則和最短路徑法測(cè)距,實(shí)現(xiàn)了較小的定位誤差。

在上述工作的基礎(chǔ)上,本文基于三維球形分割[17-18]提出了一種新的無(wú)線傳感器網(wǎng)絡(luò)定位算法。該算法給出了未知節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)距離和定位誤差計(jì)算方法,詳細(xì)闡述了位置節(jié)點(diǎn)的三維坐標(biāo)獲取方法,并通過(guò)實(shí)驗(yàn)仿真算法的有效性。本文結(jié)構(gòu)如下:第1節(jié)對(duì)無(wú)線傳感器定位相關(guān)性能指標(biāo)進(jìn)行闡述;第2節(jié)對(duì)定位算法建模過(guò)程進(jìn)行分析和闡述;第3節(jié)主要進(jìn)行數(shù)學(xué)仿真;第4節(jié)對(duì)全文進(jìn)行總結(jié)。

1 性能指標(biāo)

在無(wú)線傳感器網(wǎng)絡(luò)中,錨節(jié)點(diǎn)將跳數(shù)數(shù)據(jù)包周期性地傳送至臨近的鄰居節(jié)點(diǎn),內(nèi)部包含有相關(guān)聯(lián)的位置信息;初始狀態(tài)下,我們將其設(shè)置為0;當(dāng)鄰居節(jié)點(diǎn)接收到上述數(shù)據(jù)信息時(shí),首先對(duì)錨節(jié)點(diǎn)等進(jìn)行更新,而且以最小跳數(shù)為單元予以更新,然后將數(shù)據(jù)信息予以存儲(chǔ),并轉(zhuǎn)發(fā)傳輸。具體應(yīng)用過(guò)程中,hij代表錨節(jié)點(diǎn)i和j之間的跳數(shù),錨節(jié)點(diǎn)i對(duì)應(yīng)的坐標(biāo)可以由(xi,yi)予以表示,錨節(jié)點(diǎn)j坐標(biāo)為(xj,yj),則錨節(jié)點(diǎn)之間的每跳平均距離表達(dá)公式如下:

(1)

假設(shè)未知節(jié)點(diǎn)x和y到錨節(jié)點(diǎn)i的最小跳數(shù)分別為dmin(x,i)和dmin(y,i),節(jié)點(diǎn)x是未知的,對(duì)應(yīng)的所有鄰居節(jié)點(diǎn)集合可以由nbs(x)予以表示,那么我們將x與i之間的跳數(shù)表示為d(x,i);x周邊區(qū)域所有鄰居節(jié)點(diǎn)數(shù)目可以由|nbs(x)|予以表示,然后通過(guò)式(2)計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù),具體如下:

(2)

同時(shí)令R表示節(jié)點(diǎn)通信半徑,S表示監(jiān)測(cè)區(qū)域總面積,n表示節(jié)點(diǎn)總數(shù),則利用式(3)可以計(jì)算得到網(wǎng)絡(luò)平均連通度N為:

N=(n/S)πR2

(3)

平均每跳距離D:

(4)

由此得到未知節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的距離:

(5)

平均定位誤差定義為:

(6)

通常情況下,未知節(jié)點(diǎn)必須通過(guò)某種有效的方式獲取3個(gè)錨節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)信息,才能夠保證后續(xù)計(jì)算工作的開展,針對(duì)未知節(jié)點(diǎn)坐標(biāo)則可以通過(guò)我們比較常用的最小二乘法予以實(shí)現(xiàn);設(shè)未知節(jié)點(diǎn)坐標(biāo)為(x,y),各個(gè)錨節(jié)點(diǎn)坐標(biāo)分別為(x1,y1),(x2,y2),…,(xn,yn),那么未知節(jié)點(diǎn)與錨節(jié)點(diǎn)相互之間的平均距離可以由以下數(shù)學(xué)公式予以計(jì)算,分別用d1,d2,…,dn予以表示:

(7)

利用式(6)中的前n-1項(xiàng)依次與最后一項(xiàng)做減法得到式(7):

(8)

式(7)可用線性方程表示,即為:

AX=b

(9)

式中:

(10)

(11)

(12)

化簡(jiǎn)可得:

X=(ATA)-1ATB

(13)

因此,由式(13)可得待定位未知節(jié)點(diǎn)的位置坐標(biāo)。

2 改進(jìn)算法

目前,針對(duì)二維空間的無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究比較深入,而三維空間的定位算法則相對(duì)薄弱。對(duì)此,本文基于三維球形分割來(lái)建立無(wú)線傳感器網(wǎng)絡(luò)定位算法。如圖1所示結(jié)構(gòu)中,假設(shè)無(wú)線傳感器網(wǎng)絡(luò)位于第1象限中,在未知節(jié)點(diǎn)Nj影響范圍內(nèi),Ai表示對(duì)應(yīng)范圍的標(biāo)識(shí)符為i的錨節(jié)點(diǎn),mj表示Nj影響范圍內(nèi)的錨節(jié)點(diǎn)個(gè)數(shù),未知節(jié)點(diǎn)Nj的標(biāo)識(shí)符表示為j。同時(shí),假設(shè)錨距離ai表示原點(diǎn)與Ai間的距離,錨線OAi(i∈M)表示原點(diǎn)與Ai間的連線,錨角αi、βi、γi(i∈M)分別表示錨線OAi與對(duì)應(yīng)平面的夾角。

圖1 定位示意圖

如果通信半徑固定,那么節(jié)錨之間距離的最大通信范圍設(shè)定為R,否則Nj到Ai的距離設(shè)定為dij。同時(shí),錨球Cij表示最大傳輸半徑為R,球心為Ai的球面。則錨節(jié)點(diǎn)密度ρ的計(jì)算公式如下:

(14)

令測(cè)量值與真實(shí)值之間的誤差值與節(jié)點(diǎn)無(wú)線范圍的比值由ξ予以表示,我們將其稱之為測(cè)距誤差,Ai與Nj實(shí)際距離可以由eij表示;Nj測(cè)得與Ai之間的距離由dij表示。假設(shè)μ代表(0,1)之間隨機(jī)數(shù),由此可得到節(jié)錨距離的測(cè)量值與真實(shí)值間的關(guān)系:

dij=eij+ξ×R×(1-2μ),1≤i≤m,m+1≤j≤n

(15)

假設(shè)4個(gè)已知節(jié)點(diǎn)的坐標(biāo)分別為A(a1,b1,c1)、B(a2,b2,c2)、C(a3,b3,c3)、D(a4,b4,c4),利用改進(jìn)的多策略粒子群優(yōu)化人工神經(jīng)網(wǎng)絡(luò)模型得到位置節(jié)點(diǎn)到A、B、C、D的距離分別為d1、d2、d3、d4。分別以A、B、C、D做球心,d1、d2、d3、d4做半徑,做球A、球B、球C、球D。假設(shè)球A與球B不相交,可得參考點(diǎn)E的坐標(biāo):

(16)

球A、球B、球C、球D兩兩為一組可得到6個(gè)參考點(diǎn)坐標(biāo),將距離值的倒數(shù)設(shè)為參照權(quán)因子可得權(quán)值為:

(17)

由此可得位置節(jié)點(diǎn)的三維坐標(biāo)為:

(18)

(19)

(20)

(21)

(22)

慣性權(quán)重w對(duì)粒子的飛行速度影響較大,固定的w會(huì)導(dǎo)致粒子無(wú)法遍歷整個(gè)搜索空間,使用迭代次數(shù)線性遞減的w使前期搜索能力較強(qiáng),后期較弱。本文提出改進(jìn)的混沌慣性權(quán)重策略,添加隨機(jī)數(shù)r3,并且r3為(0,1)內(nèi)的隨機(jī)變量,降低粒子后期在解空間飛行時(shí)的趨同性:

wt+1=4r3×wt(1-wt)

(23)

t為迭代次數(shù),w1∈(0,1),wt為對(duì)應(yīng)的慣性權(quán)重。具體應(yīng)用過(guò)程中,粒子聚攏度較高時(shí),速度和位置變化很小,無(wú)法繼續(xù)在全局范圍內(nèi)搜索,需要適時(shí)引入擾動(dòng)策略,本文基于高斯分布和柯西分布提出了一種卡方(ε2(n))變異擾動(dòng)因子,當(dāng)自由度n很大時(shí),分布近似為高斯分布。對(duì)粒子位置進(jìn)行修改得:

(24)

式(22)中,k∈[0,1]。由上述公式及第1節(jié)提出的相關(guān)描述可得出本文基于三維球形分割的無(wú)線傳感器網(wǎng)絡(luò)定位算法如下:

Step 1 初始化人工神經(jīng)網(wǎng)絡(luò),設(shè)置三層拓?fù)浣Y(jié)構(gòu),將所有權(quán)值和閾值編碼成粒子,并改進(jìn)多策略粒子群優(yōu)化模型參數(shù);

Step 2 計(jì)算適應(yīng)度值并更新pbest和gbest:

Step 3 判斷是否滿足終止條件;假設(shè)達(dá)到最大迭代次數(shù)Tmax或小于最小誤差minError,則保存全局最優(yōu)粒子位置,輸出最優(yōu)權(quán)值和閾值;否則重新返回至Step 3;

Step 4 構(gòu)建改進(jìn)的多策略粒子群優(yōu)化人工神經(jīng)網(wǎng)絡(luò)模型,輸入RSSIA、B、C、D;

Step 7 算法結(jié)束。

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

為了檢驗(yàn)上述算法的適用性,本文搭建了無(wú)線傳感網(wǎng)仿真環(huán)境,并利用MATLAB進(jìn)行仿真實(shí)驗(yàn)。假設(shè)通信半徑R=10 m,在4/3πR3的球體內(nèi)隨機(jī)投擲一定數(shù)量的節(jié)點(diǎn)作為錨節(jié)點(diǎn)。節(jié)點(diǎn)A、B、C、D的坐標(biāo)分別為A(1,0,0.8)、B(3,0,2.02)、C(0,3.1,1.2)、D(3.5,3.1,1.2),同時(shí)初始化改進(jìn)的多策略粒子群優(yōu)化人工神經(jīng)網(wǎng)絡(luò)模型參數(shù):Tmax=200,粒子最大速度Vmax=0.6,改進(jìn)混沌慣性權(quán)重w1=0.30,學(xué)習(xí)因子c1=1.98,c2=2.02,minError=0.000 1,種群規(guī)模NP=50,ε2(n)變異擾動(dòng)因子中自由度取11。

錨節(jié)點(diǎn)信息是多維質(zhì)心定位算法的最主要信息,會(huì)對(duì)定位算法的性能產(chǎn)生重要干擾與影響;ξ為0.05時(shí),其結(jié)果參如圖2所示。從圖2可以看出,隨著錨節(jié)點(diǎn)密度的增大定位誤差隨之減小。并且未知節(jié)點(diǎn)周圍的平均錨節(jié)點(diǎn)數(shù)為3時(shí),本算法的定位誤差大約在38%附近。而當(dāng)未知節(jié)點(diǎn)附件的錨節(jié)點(diǎn)數(shù)量達(dá)到8時(shí),本文算法的定位誤差下降到28%以下。若錨節(jié)點(diǎn)密度持續(xù)增加,本文算法的定位誤差仍呈直線下降趨勢(shì)。

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

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

為了獲得更為準(zhǔn)確的定位信息,需要依靠較為可靠的通信環(huán)境和節(jié)點(diǎn)設(shè)備。圖3給出了不同測(cè)距誤差對(duì)算法的敏感性影響情況。這里設(shè)置錨節(jié)點(diǎn)密度為3,錨節(jié)點(diǎn)比值為10%,測(cè)距誤差的變化范圍為0～1。從圖3可以看出,本算法的定位誤差隨測(cè)距誤差的增加整體上呈現(xiàn)上升趨勢(shì)。并且當(dāng)錨節(jié)點(diǎn)比例和密度不變時(shí),測(cè)距誤差為0時(shí),所對(duì)應(yīng)的最小定位誤差大約為35%左右,隨后因測(cè)距誤差的遞增,定位誤差變化緩慢。因此可以看出測(cè)距誤差對(duì)本文算法性能影響較小。

節(jié)點(diǎn)網(wǎng)絡(luò)連通度的大小主要受節(jié)點(diǎn)密度大小的影響,因此有必要分析節(jié)點(diǎn)密度對(duì)算法性能的影響。假設(shè)測(cè)距誤差為0.05,錨節(jié)點(diǎn)比例為10%,圖4給出了算法定位性能與節(jié)點(diǎn)密度之間的關(guān)系。從圖4可以看出,隨著節(jié)點(diǎn)密度的增加,定位誤差呈現(xiàn)先降低后逐漸增大的趨勢(shì)。當(dāng)節(jié)點(diǎn)密度小于9時(shí),網(wǎng)絡(luò)中的定位誤差呈現(xiàn)緩慢下降的趨勢(shì);當(dāng)節(jié)點(diǎn)密度位于9～15之間時(shí),定位誤差呈上升趨勢(shì);當(dāng)節(jié)點(diǎn)密度大于15時(shí),定位誤差呈現(xiàn)快速增長(zhǎng)趨勢(shì)。因此,將節(jié)點(diǎn)密度設(shè)置為9能夠得到最低的定位誤差,使得算法性能最優(yōu)。

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

這里進(jìn)一步對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)對(duì)定位誤差的影響進(jìn)行研究。本文算法在錨節(jié)點(diǎn)分布率分別取10%、20%、30%時(shí),圖5給出了網(wǎng)絡(luò)總結(jié)點(diǎn)數(shù)對(duì)節(jié)點(diǎn)定位性能的對(duì)比曲線,其中,實(shí)驗(yàn)結(jié)果為100次仿真實(shí)驗(yàn)的平均取值。在圖中,隨著網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的增加,節(jié)點(diǎn)定位的誤差呈現(xiàn)下降趨勢(shì);仔細(xì)觀察,我們發(fā)現(xiàn),當(dāng)錨節(jié)點(diǎn)分布越密集時(shí),則系統(tǒng)產(chǎn)生的定位精度越高,對(duì)應(yīng)的誤差數(shù)值也就越小。這是因?yàn)?網(wǎng)絡(luò)連通性會(huì)隨著網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的增加而增強(qiáng),即未知節(jié)點(diǎn)可用多跳的形式與錨節(jié)點(diǎn)進(jìn)行通信,并且,當(dāng)錨節(jié)點(diǎn)數(shù)量增加時(shí),網(wǎng)絡(luò)連通性也會(huì)變好,此時(shí)與錨節(jié)點(diǎn)直接通信的節(jié)點(diǎn)數(shù)目也會(huì)增加,因此,綜合上述兩個(gè)原因,定位誤差會(huì)逐漸減小。

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

圖6 不同算法中未知節(jié)點(diǎn)數(shù)目對(duì)節(jié)點(diǎn)誤差能耗積的影響曲線

最后,圖6給出了不同算法的未知節(jié)點(diǎn)數(shù)目對(duì)節(jié)點(diǎn)誤差能耗積的影響曲線。其中,假設(shè)節(jié)點(diǎn)通信半徑都相同,為10 m。節(jié)點(diǎn)數(shù)目的變化范圍為75個(gè)～280個(gè)。可觀察到,隨著節(jié)點(diǎn)數(shù)目的快速增加,兩種算法的誤差能耗積都有上升趨勢(shì),但DV-HOP算法增幅明顯,本文算法增幅極小。綜上所述,我們認(rèn)為本文計(jì)算方法可以在能耗、定位精度兩個(gè)方面取得較好優(yōu)勢(shì)。

4 結(jié)論

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)定位精度問(wèn)題,本文基于三維球形分割技術(shù)建立了一種新的定位算法。首先,在計(jì)算過(guò)程中,將各個(gè)錨節(jié)點(diǎn)之間的網(wǎng)絡(luò)連通度、平均距離予以綜合考量,進(jìn)而計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)相互之間的距離,然后將對(duì)應(yīng)的數(shù)據(jù)予以存儲(chǔ),同時(shí)更新與錨節(jié)點(diǎn)的最小跳數(shù)并進(jìn)行轉(zhuǎn)發(fā)。當(dāng)未知節(jié)點(diǎn)獲取到至少3個(gè)信標(biāo)節(jié)點(diǎn)信息時(shí),通過(guò)最小二乘法求得出未知節(jié)點(diǎn)的坐標(biāo)。其次,基于三維球形分割對(duì)上述指標(biāo)進(jìn)行優(yōu)化,為了使尋求最優(yōu)解效率達(dá)到較優(yōu),本文在PSO中添加反向?qū)W習(xí)策略,并建立了無(wú)線傳感器網(wǎng)絡(luò)定位算法。最后,通過(guò)仿真實(shí)驗(yàn)深入研究影響該算法的關(guān)鍵因素。通過(guò)比較分析節(jié)點(diǎn)密度、信標(biāo)節(jié)點(diǎn)個(gè)數(shù)、定位誤差和測(cè)距誤差等參數(shù)。實(shí)驗(yàn)結(jié)果表明,該算法較DV-HOP和加權(quán)質(zhì)心算法在性能得到較大提高。在后續(xù)研究中,可以考慮結(jié)合融合多種測(cè)距和非測(cè)距定位算法來(lái)提高無(wú)線傳感器網(wǎng)絡(luò)的定位精度。