基于三維球形分割的無線傳感器網絡定位算法*

徐 兵,項順伯,吳憲君

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

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

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

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

1 性能指標

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

(1)

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

(2)

同時令R表示節點通信半徑,S表示監測區域總面積,n表示節點總數,則利用式(3)可以計算得到網絡平均連通度N為:

N=(n/S)πR2

(3)

平均每跳距離D:

(4)

由此得到未知節點到各個錨節點的距離:

(5)

平均定位誤差定義為:

(6)

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

(7)

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

(8)

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

AX=b

(9)

式中:

(10)

(11)

(12)

化簡可得:

X=(ATA)-1ATB

(13)

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

2 改進算法

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

圖1 定位示意圖

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

(14)

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

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

(15)

假設4個已知節點的坐標分別為A(a1,b1,c1)、B(a2,b2,c2)、C(a3,b3,c3)、D(a4,b4,c4),利用改進的多策略粒子群優化人工神經網絡模型得到位置節點到A、B、C、D的距離分別為d1、d2、d3、d4。分別以A、B、C、D做球心,d1、d2、d3、d4做半徑,做球A、球B、球C、球D。假設球A與球B不相交,可得參考點E的坐標:

(16)

球A、球B、球C、球D兩兩為一組可得到6個參考點坐標,將距離值的倒數設為參照權因子可得權值為:

(17)

由此可得位置節點的三維坐標為:

(18)

(19)

(20)

(21)

(22)

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

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

(23)

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

(24)

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

Step 1 初始化人工神經網絡,設置三層拓撲結構,將所有權值和閾值編碼成粒子,并改進多策略粒子群優化模型參數;

Step 2 計算適應度值并更新pbest和gbest:

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

Step 4 構建改進的多策略粒子群優化人工神經網絡模型,輸入RSSIA、B、C、D;

Step 7 算法結束。

3 仿真實驗

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

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

圖2 錨節點密度對定位誤差的影響

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

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

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

圖4 節點密度對定位誤差的影響

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

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

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

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

4 結論

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