徐 兵,項順伯,吳憲君

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

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

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

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

1 性能指標(biāo)

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

(1)

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

(2)

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

N=(n/S)πR2

(3)

平均每跳距離D:

(4)

由此得到未知節(jié)點到各個錨節(jié)點的距離:

(5)

平均定位誤差定義為:

(6)

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

(7)

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

(8)

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

AX=b

(9)

式中:

(10)

(11)

(12)

化簡可得:

X=(ATA)-1ATB

(13)

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

2 改進(jìn)算法

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

圖1 定位示意圖

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

(14)

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

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

(15)

假設(shè)4個已知節(jié)點的坐標(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é)點到A、B、C、D的距離分別為d1、d2、d3、d4。分別以A、B、C、D做球心,d1、d2、d3、d4做半徑,做球A、球B、球C、球D。假設(shè)球A與球B不相交,可得參考點E的坐標(biāo):

(16)

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

(17)

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

(18)

(19)

(20)

(21)

(22)

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

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

(23)

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

(24)

式(22)中,k∈[0,1]。由上述公式及第1節(jié)提出的相關(guān)描述可得出本文基于三維球形分割的無線傳感器網(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 計算適應(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 仿真實驗

為了檢驗上述算法的適用性,本文搭建了無線傳感網(wǎng)仿真環(huán)境,并利用MATLAB進(jìn)行仿真實驗。假設(shè)通信半徑R=10 m,在4/3πR3的球體內(nèi)隨機投擲一定數(shù)量的節(jié)點作為錨節(jié)點。節(jié)點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),同時初始化改進(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)變異擾動因子中自由度取11。

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

圖2 錨節(jié)點密度對定位誤差的影響

圖3 測距誤差對定位誤差的影響

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

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

圖4 節(jié)點密度對定位誤差的影響

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

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

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

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

4 結(jié)論

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