狹長直隧道環(huán)境中WSN的RSSI加權質心定位算法

方旺盛,高　銀

(江西理工大學信息工程學院,江西 贛州 341000)

在礦井的安全生產中,依靠無線傳感器網絡技術[1-2]能夠保證管理人員對礦井巷道中的環(huán)境、人員和車輛等實時監(jiān)控,而如何設計一套有效的定位算法對巷道中的人員與車輛定位已經成為一個重要的問題[3]。

目前現有的無線傳感器網絡定位算法[4]主要分為基于測距的(Range-based)定位算法和無需測距的(Range-free)定位算法[5]。這些算法大多未考慮節(jié)點的可移動性[6]和異構性[7]。在實際應用中,井下人員與礦車都具有移動性,且礦下監(jiān)測傳感器節(jié)點多種多樣,如:溫度、適度、粉塵、坑壁壓力、各種氣體濃度參數等不同環(huán)境變量的節(jié)點,這些節(jié)點的部署隨著采掘面的延伸而擴展。移動性和異構性增加了節(jié)點的定位難度,因此,井下無線傳感器網絡節(jié)點的移動性和異構性是井下節(jié)點定位的關鍵問題。

俞黎陽、王能等人提出了基于選址問題的異構節(jié)點部署算法,以優(yōu)化無線傳感器網絡中異構節(jié)點的數量和位置[8],算法僅考慮了節(jié)點的異構性;朱曉娟、孟祥瑞等人利用固定信標節(jié)點和未知節(jié)點的接受信號強度指示值RSSI(Received Signal Strength Indication)作為依據,計算每個固定信標節(jié)點的權值,通過權值來體現固定信標節(jié)點對質心坐標決定權的大小[9],但僅考慮到了信標節(jié)點靜止而待定位節(jié)點隨機移動的情況。

礦井巷道和公路、鐵路隧道都可看作三維狹長隧道,隧道內除少部分區(qū)域存在分支隧道外,大部分區(qū)域都可看作狹長隧道,而這些狹長隧道雖然可能存在部分彎曲,但大多數彎曲半徑較大,可看成狹長直隧道。本算法重點考慮狹長直隧道內節(jié)點的異構性和移動性,在基于RSSI的加權質心定位算法的基礎下,結合狹長直隧道內節(jié)點的分布模型,采用修正加權權重的方法對傳統(tǒng)的質心定位算法[10]進行了改進,使得算法滿足礦井隧道中的無線傳感器節(jié)點移動性和異構性的需要,算法定位精度高、適合于狹長直隧道環(huán)境。

1　狹長直隧道內節(jié)點分布模型

井下隧道根據空間特性和功能,分為垂直巷道、傾斜巷道和水平巷道三大類[11],由于本文所研究的是狹長直隧道[12],為了研究方便,只截取這些巷道中的某一段狹長直隧道來做研究,如圖1所示。

圖1中子圖1(a)表示的是節(jié)點在隧道底面上的投影,其中黑色圓點是信標節(jié)點,圓圈表示的是普通節(jié)點如本文中的監(jiān)測節(jié)點,三角形和正方形分別表示隧道內的工作人員與礦車。圖1(b)所示的是信標節(jié)點在隧道內的空間結構分布模型,其中B1、B4、B7為隧道左側壁上的信標節(jié)點;B2、B5為隧道右側壁上的信標節(jié)點;B3、B6為隧道頂部的信標節(jié)點。將隧道空間節(jié)點按不同平面投影,可得到信標節(jié)點分別在ZX平面與XY平面上的投影。

2　RSSI加權質心算法及改進

2.1　傳統(tǒng)的質心定位算法

質心定位算法最初是由南加州大學Nirupama Bulusu等人提出的一種無需測距的室外定位算法[13]。具體的定位過程為:信標節(jié)點周期性地發(fā)出自身位置坐標信息(xi,yi)的信標信號,當未知節(jié)點接收到來自不同信標節(jié)點的信標分組數量超過一個門限或接收一定時間后,那么就認為未知節(jié)點和這些信標節(jié)點連通,把所有與自己連通的信標節(jié)點組成的多邊形的質心作為自己的估計位置,計算公式為:

(1)

式中(x,y)是未知節(jié)點的坐標;(xi,yi)(i=1,2,…N)為未知節(jié)點能夠接收到其分組的信標節(jié)點坐標。傳統(tǒng)的質心算法的定位精度受到信標節(jié)點的分布情況和分布密度的影響很大。

2.2　基于RSSI的加權質心算法

基于RSSI的加權質心算法是以未知節(jié)點與信標節(jié)點之間的RSSI為依據,計算每個信標節(jié)點坐標對應的加權值,通過加權值來體現信標節(jié)點對質心位置的影響程度,反映他們的內在關系。加權質心算法的計算公式為:

(2)

式中ωi(i=1,2,…N)為每個信標節(jié)點對應的加權值,通常ωi為未知節(jié)點與各個信標節(jié)點之間距離d的函數。

2.3　基于RSSI的加權質心改進算法

對于質心算法和基于RSSI的加權質心算法,由于僅計算節(jié)點自身坐標與各個接收節(jié)點距離發(fā)射點的距離的加權值,因此算法計算簡單,適用于對精度要求不高的大規(guī)模傳感器網絡的定位。且這兩種算法并未考慮節(jié)點的移動與異構情況,因為無線傳感器網絡因其應用場景不同,節(jié)點的分布情況與運動形式也不同,節(jié)點的移動與異構情況決定了質心算法與基于RSSI的加權質心算法不適用于本文所要求的隧道中人員與礦車的定位。隧道空間是三維近似半封閉的,隧道壁分布的信標節(jié)點與隧道內壁監(jiān)測節(jié)點的功能各不相同,從而導致通信半徑也各不相同,且隧道中的人員與礦車是移動的。本文的算法考慮了隧道內節(jié)點的移動與異構情況,將更適合井下應用場景。

本文的算法將定位過程分為兩個階段。第1個階段是隧道內信標節(jié)點的分布和選擇。隧道內人員與礦車的移動所組成的未知節(jié)點在移動過程中可能會接收到來自隧道四周安置的信標節(jié)點的信息,這些節(jié)點在某一時間內處于信標節(jié)點的連通范圍內,但是隨著節(jié)點的移動,其所處的范圍也會隨著變化。本文將信標節(jié)點按圖1(b)所示分布,隧道左右側壁與頂部分別安置一定數量的信標節(jié)點,這些信標節(jié)點組成了三邊或多邊的網絡格型,當未知節(jié)點在某一時刻處于某一位置時,與未知節(jié)點連通的信標節(jié)點組成多邊形,對未知節(jié)點進行定位。由于隧道是空間立體結構的,分布其中的節(jié)點都具有三維坐標,本文需定位的是處于隧道中的工作人員與礦車,這些未知節(jié)點在隧道中Z軸的坐標位置無實用價值,只需考慮在隧道XY平面上的坐標位置,即僅考慮圖1(b)中節(jié)點投影在XY平面上的節(jié)點坐標位置,如圖2所示。設N個固定的信標節(jié)點在XY平面上投影的坐標分別為B1(x1,y1),B2(x2,y2),…,BN(xN,yN),未知節(jié)點M(xest,yest)到各信標節(jié)點的距離分別為d1,d2,d3,…,dn。

圖2　節(jié)點定位算法示意圖

第2個階段主要是根據選擇的信標節(jié)點確定權值并進行定位。加權質心算法主要是利用固定的信標節(jié)點和未知節(jié)點的接收信號強度指示值(RSSI)來計算每個固定信標節(jié)點的權值。在本文中,隧道中信標節(jié)點與監(jiān)測節(jié)點各具有不同的通信半徑,不同的通信半徑對應不同的RSSI值。本文的算法主要參考楊新宇、孔慶茹等人提出的方法[14],把未知節(jié)點接收到各個信標節(jié)點的信號強度的比值作為每個信標的權值,這樣體現不同信標節(jié)點對于未知節(jié)點的影響力的同時,也可以做到環(huán)境改變時權值保持不變,因此提高了算法的精度。未知節(jié)點M分別從信標節(jié)點Bj、Bi接受到的RSSI信號強度比值為Rji,權值為ωi,有:

Rji=Rj/Ri,i=1,2…N,j≠i

(3)

(4)

式(4)的權值是基于同類的信標節(jié)點上獲取的,本文中的隧道存在非同類的信標節(jié)點,對于隧道中存在M類信標節(jié)點,設與未知節(jié)點通信的同類信標節(jié)點個數分別有K1,K2,K3,…KM個。因此非同類信標節(jié)點總數有N=K1+K2+…+KM,這些節(jié)點的通信半徑組成的集合為Sr={r1,r2,r3,…,rN},因此本文的修改算法中,將未知節(jié)點與信標節(jié)點間通信半徑平方的倒數考慮在內修正后的權值ωi為:

(5)

式中ri(i=1,2,…N)為是未知節(jié)點分別與這N個信標節(jié)點間的最大通信半徑,修正后的權值能很好地體現隧道內節(jié)點的異構性對于未知節(jié)點定位的決定權,能更好的適用于隧道內節(jié)點的定位,使得節(jié)點定位更精確。

根據權值ωi與信標節(jié)點的坐標求出加待定位節(jié)點的坐標M(xest,yest):

(6)

(7)

當r1=r2=r3=…=rN時,即各個信標節(jié)點通信半徑相同,為同類的信標節(jié)點,此時節(jié)點的定位算法與同類節(jié)點定位算法相同。

由于狹長隧道的高度一般不超過10 m,隧道壁和頂部的節(jié)點作為信標節(jié)點,隧道內為各種未知的節(jié)點,即將一個區(qū)域劃分為若干個三角形或多邊形,多邊形的頂點為信標節(jié)點,質心作為未知節(jié)點(x,y)。定位算法步驟如下:

(1)信標節(jié)點周期性地廣播信息,信息中包括節(jié)點ID和自身的位置坐標;

(2)待定位節(jié)點接收各信標節(jié)點的信息,在某一時刻記錄各個信標節(jié)點的RSSI值,當所得的信標節(jié)點數大于等于4時,取RSSI值較大的4個信標節(jié)點,即保證信標節(jié)點組由離待定位節(jié)點最近的4個信標節(jié)點組成;

(3)根據第(2)步中得到的4個信標節(jié)點建立2個集合:通信半徑集合Sr={r1,r2,r3,r4};坐標集合P={(x1,y1),(x2,y2),(x3,y3),(x4,y4)};

(4)根據式(5)計算出每一個信標節(jié)點的加權值ωi;

(5)將得到的權值ωi與信標節(jié)點的坐標根據式(6)、式(7)計算出未知節(jié)點的坐標(x,y),該坐標是未知移動節(jié)點的估計坐標。

算法分析如下:

由于本文所研究的是半封閉的狹長直隧道環(huán)境中的節(jié)點定位,無線信號在傳播過程中存在多徑衰落,因狹長直隧道內壁的凹凸不平及信號吸收等原因,多徑反射和散射信標節(jié)點的信號強度一般較弱,如果根據這些信標節(jié)點來計算待定位節(jié)點的位置會增大定位誤差。對于視距信標節(jié)點,信號強度較小的信標節(jié)點距離越遠,當距離達到某一閾值時不能用距離較小時的信號散射模型,否則會增大定位誤差。因此本文算法選取的信標節(jié)點是4個RSSI值較大的信標節(jié)點,這些信標節(jié)點是距離較近的視距節(jié)點,從而基本剔除了由多徑反射和散射信標節(jié)點造成的定位誤差。根據式(6)和式(7),當信標節(jié)點數為N時,其計算量均為N(N-1);本文算法取RSSI值較大的4個信標節(jié)點作為參與定位的節(jié)點,其計算量為4×3=12,能顯著地減小計算量。

3　仿真結果及分析

運用MATLAB進行算法仿真,仿真實驗的初始條件為10 m×2 000 m的矩形區(qū)域,即設定隧道的長度為2 000 m,寬度為10 m。傳感器節(jié)點的部署如圖1所示,為了易于驗證,未知節(jié)點的坐標初始化為原點(0,0),無線信號的載頻為2.4 GHz。在信標節(jié)點數從5到25變化的基礎上對算法進行仿真分析,每個實驗運行500次,仿真結果取500次的平均值。結合隧道中節(jié)點的實際應用環(huán)境,分別從固定在隧道壁上信標節(jié)點數和節(jié)點的通信半徑進行仿真和分析,為了易于仿真計算,當通信半徑不同時,假設存在3類信標節(jié)點,且這3類信標節(jié)點的通信半徑為(r-5)、r、(r+5)。仿真結果如圖3～圖5所示。其中定位誤差的計算公式如式(8)所示

(8)

式中x,y為實際距離,x′,y′為測量值,若未知節(jié)點個數為k,則平均誤差為∑ei/k。

圖3所示的是信標節(jié)點的個數變化對定位誤差的影響,在相同條件下,信標節(jié)點個數由5個變化到20個時,修改后的算法的誤差大大低于傳統(tǒng)的質心算法和基于RSSI值的加權質心算法;當信標節(jié)點的數目增多,未知節(jié)點收到的信標節(jié)點信息較均勻,3種算法誤差的差距減小。圖4圖5所示的是信標節(jié)點通信半徑的變化對定位誤差的影響。當信標節(jié)點的初始通信半徑相同時,隨著節(jié)點的通信半徑增加,可以看到相較于傳統(tǒng)質心算法與基于RSSI值的加權質心算法,本算法能有效的減小定位誤差,但節(jié)點通信半徑的增加,對其定位誤差影響不是很大;當初始通信半徑不同的時候,與同類的節(jié)點定位算法相比,異構信標節(jié)點的定位誤差較小,定位算法的精度有了很大的提高。

圖5　非同類信標節(jié)點時通信半徑的變化對定位誤差的影響

圖3　信標節(jié)點數對定位誤差的影響

圖4　同類信標節(jié)點的通信半徑變化對定位誤差的影響

4　總結

綜上所述,本文提出的狹長直隧道內基于RSSI的質心定位算法在井下人員與礦車的定位上有著明顯的優(yōu)勢,克服了傳統(tǒng)質心加權算法在此環(huán)境下出現的較大誤差,第1步通過對隧道內節(jié)點分布的分析,選擇合適的信標節(jié)點,確保了信標節(jié)點的有效性,第2步根據選擇的信標節(jié)點確定權值從而進行定位,考慮了隧道內節(jié)點的異構性與移動性特點。本文研究的是狹長直隧道內的節(jié)點定位,如何對彎曲和分支隧道內節(jié)點定位是下一步工作的重點。

參考文獻:

[1]Yick J,Mukherjee B,Ghosal D.Wireless Sensor Network Survey[J].Computer Networks,2008,52(12):2292-2330.

[2]Rahman K C.A Survey on Sensor Network[J].Journal of Computer and Information Technology,2010(1):76-87.

[3]楊大明.煤礦井下緊急避險系統(tǒng)的建設與發(fā)展[J].煤炭科學技術,2010(11):6-9.

[4]Mao G,Fidan B,Anderson B.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529-2553.

[5]Chen C C,Chang C Y,Li Y N.Range-Free Localization Scheme in Wireless Sensor Networks Based on Bilateration[J].International Journal of Distributed Sensor Networks,2013,2013.

[6]Zhu Y,Zhang B,Yu,et al.A RSSI Based Localization Algorithm Using a Mobile Anchor Nodefor Wireless Sensor Networks[C]//Computational Sciences and Optimization,2009.CSO 2009.International Joint Conference on.IEEE,2009,1:123-126.

[7]Li X Y,Song W Z,Wang Y.Localized Topology Control for Heterogeneous Wireless Sensor Networks[J].ACM Transactions on Sensor Networks(TOSN),2006,2(1):129-153.

[8]俞黎陽,王能,張衛(wèi).異構無線傳感器網絡中異構節(jié)點的部署與優(yōu)化[J].計算機科學,2008(9):48-51.

[9]朱曉娟,孟祥瑞.基于加權質心的無線傳感器網絡移動節(jié)點定位算法[J].計算機工程與科學,2011,33(11):15-19.

[10]陳維克,李文鋒,首珩,等.基于RSSI的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報,2006,30(12):265-268.

[11]Han Guorui,Zhang Wenmei,Zhang Y P.An Experiment Study of the Propagation of Radio Waves in a Scaled Model of Long-Wall Coal Mining Tunnels[J].IEEE Antennas and Wireless Propagation Letters,2009(8):502-504.

[12]Kavitha K,Teja C R,Gururaj R.Workload-Aware Tree Construction Algorithm for Wireless Sensor Networks[J].International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks,2012,4(1):1-14.

[13]Bulusu N,Heidemann J,Estrin D.GPS-Less Low Cost Outdoor Locali-zation for Very Small Devices[J].IEEE Personal Communications,2000,7(5):28-34.

[14]楊新宇,孔慶茹,戴湘軍.一種改進的加權質心定位算法[J].西安交通大學學報,2010,44(8):1-4.

方旺盛(1963-),男,教授,碩士研究生導師。主要研究方向為無線傳感器網絡,數字水印,基因表達式編程等,fangwangsheng@163.com;

高銀(1987-),男,碩士研究生,主要研究方向為無線傳感器網絡。