基于井下異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)

方旺盛, 吳勝寶

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

0 引 言

我國(guó)礦產(chǎn)資源豐富，而礦井安全技術(shù)比較落后，事故隱患多，因此，提高安全生產(chǎn)和監(jiān)測(cè)是一個(gè)必需而且很迫切的要求。由于無(wú)線傳感器節(jié)點(diǎn)的靈活性和多樣性，經(jīng)防爆處理和技術(shù)優(yōu)化后，可用于危險(xiǎn)工作環(huán)境中的實(shí)時(shí)監(jiān)測(cè),有著廣闊的應(yīng)用前景[1]。而傳感器節(jié)點(diǎn)定位又是安全監(jiān)測(cè)最核心的問題，近些年來(lái)有很多關(guān)于井下的無(wú)線傳感器節(jié)點(diǎn)定位算法研究，大致分為兩大類：基于測(cè)距和非測(cè)距，前者利用電磁波的衰減規(guī)律或速度來(lái)測(cè)距，如接收信號(hào)強(qiáng)度指示 (received signal strength indication，RSSI)、到達(dá)時(shí)間(time of arrival，TOA[2])等；后者是利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)轉(zhuǎn)換為實(shí)際距離，如DV-Hop、質(zhì)心算法[3]等。而井下環(huán)境情況復(fù)雜多變，巷道彎曲，通信條件差，存在明顯的多徑效應(yīng)[4],基于測(cè)距的定位算法并不太適合,且節(jié)點(diǎn)都是按需隨機(jī)部署的，不能保證節(jié)點(diǎn)密度[5]，因此,有必要對(duì)當(dāng)前無(wú)需測(cè)距的定位算法進(jìn)行改進(jìn)。梁美玉、李莉等人提出了使用蟻群算法優(yōu)化誤差函數(shù)來(lái)提高定位精度[6]。劉凱、余君君等人提出了一種信標(biāo)節(jié)點(diǎn)優(yōu)選方案和跳數(shù)加權(quán)算法來(lái)提高定位精度[7]。楊順、李龍青利用導(dǎo)標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的幾何拓?fù)潢P(guān)系提高定位精度[8]。綜上所述，目前對(duì)這類算法最主要的改進(jìn)是在目標(biāo)原始位置數(shù)據(jù)采集與濾波[9]，以及在對(duì)節(jié)點(diǎn)在全局位置進(jìn)行估計(jì)時(shí)的估計(jì)算法來(lái)進(jìn)行改進(jìn)[10]。本文從巷道復(fù)雜彎曲和節(jié)點(diǎn)分布不均勻?qū)鹿?jié)點(diǎn)定位精度影響的角度進(jìn)行分析改進(jìn)，在DV-Hop算法的跳數(shù)選取和平均跳距選取過程中引入了篩選因子，使得篩選出來(lái)的平均跳數(shù)和平均跳距更加準(zhǔn)確，也使該算法更加適合于井下傳感器節(jié)點(diǎn)的定位。

1 井下隧道物理模型

1.1 井下空間模型

井下巷道根據(jù)其空間特性和功能，分為垂直巷道、傾斜巷道和水平巷道三大類[11]。為了研究方便，按空間關(guān)系作了一些簡(jiǎn)化，簡(jiǎn)化后，可將井下巷道統(tǒng)一劃分為多層巷道和分支巷道、弧形巷道，如圖1所示。

圖1 分層巷道和分支、弧形巷道簡(jiǎn)化模型

1.2 井下電磁波傳輸模型

在無(wú)線傳感器研究中，電磁波在空間中的傳播損耗模型分為自由空間傳播損耗模型、對(duì)數(shù)路徑損耗模型、屏蔽模型等三類[12]。

然而自由空間損耗模型和對(duì)數(shù)損耗模型將通信環(huán)境描述成理想環(huán)境[13]，但是，在礦井中傳播的無(wú)線電波受到巷道尺寸、拐彎等因素的影響,主要表現(xiàn)在電磁波受發(fā)射端與接收端之間的視距和節(jié)點(diǎn)覆蓋規(guī)則的影響[14],因此，這2種模型并不適合本文的研究需要;而屏蔽模型是對(duì)理想圓形模型進(jìn)行了擴(kuò)展，更加符合礦井中復(fù)雜的環(huán)境，所以，本文采用的路徑損耗模型為屏蔽模型。

屏蔽模型的路徑損耗模型使用了一個(gè)接近中心的距離r0為參考，對(duì)距離為r的平均接收功率P(r)進(jìn)行預(yù)測(cè)，兩者的比值如式(1)

(1)

式中P(r0)為r0的參考功率值，β為路徑衰減指數(shù)，一般為實(shí)際測(cè)量得到的經(jīng)驗(yàn)值,一般情況下為0.4～0.65。式(1)是電磁波在理想情況下的傳輸模型，還需考慮信號(hào)功率的損耗，經(jīng)研究測(cè)量，無(wú)線信號(hào)路徑損耗功率是對(duì)數(shù)正態(tài)隨機(jī)變量[15]，因此，可得出井下無(wú)線信號(hào)傳播模型，如式(2)

(2)

其中,φ為一個(gè)均值為零的高斯分布變量[16]，沒有實(shí)際意義，為了計(jì)算方便，這里不考慮φ影響，可根據(jù)式(1)可推導(dǎo)出通信半徑和節(jié)點(diǎn)間距離的關(guān)系如式(3)所示

(3)

2 DV-HOP算法分析與改進(jìn)

2.1 傳統(tǒng)算法分析

Niculescu D等人提出的DV-Hop節(jié)點(diǎn)定位算法是一種基于距離矢量計(jì)算跳數(shù)的算法[17]。首先，每個(gè)信標(biāo)節(jié)點(diǎn)向所在網(wǎng)絡(luò)廣播包含自身位置信息和跳數(shù)值為0的信息，當(dāng)周圍鄰居節(jié)點(diǎn)接收后，將會(huì)記錄位置信息和跳數(shù)，并將跳數(shù)加1再?gòu)V播出去，整個(gè)過程中只保留收到的包含最小跳數(shù)值的信息，以此類推，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)都獲得與之相鄰的信標(biāo)節(jié)點(diǎn)的位置信息和最小跳數(shù)值。

其次，當(dāng)錨節(jié)點(diǎn)收到其它錨節(jié)點(diǎn)的信息后，可依據(jù)式(4)估算平均每跳距離

(4)

式中 (xi，yi) 和(xj，yj)為錨節(jié)點(diǎn)i和j的坐標(biāo)，hj為錨節(jié)點(diǎn)j到錨節(jié)點(diǎn)i的最小跳數(shù)。

2.2 算法改進(jìn)描述

由于礦井下節(jié)點(diǎn)分布不均勻，通信條件比較差，傳統(tǒng)的校正值不能對(duì)平均每跳距離進(jìn)行精確估計(jì)。如圖2所示，井下節(jié)點(diǎn)通信半徑基本相同，設(shè)定R為巷道中錨節(jié)點(diǎn)通信半徑，當(dāng)錨節(jié)點(diǎn)S(黑色三角形)發(fā)送數(shù)據(jù)時(shí)，因?yàn)楣?jié)點(diǎn)通信半徑大于巷道寬度，布置在巷道側(cè)壁上的未知節(jié)點(diǎn)A和B(白色圓點(diǎn))都落在節(jié)點(diǎn)S的通信半徑R內(nèi)，若按傳統(tǒng)方法計(jì)算跳數(shù)，將會(huì)得到相同的跳數(shù)，即都為1跳。但是，節(jié)點(diǎn)A和節(jié)點(diǎn)B距離錨節(jié)點(diǎn)S卻相差很大，錨節(jié)點(diǎn)通信半徑越大，相差越大。

圖2 巷道中節(jié)點(diǎn)位置與通信半徑的關(guān)系

因此在本文中，跳數(shù)值不僅能以整數(shù)值1跳遞增，也能以小數(shù)值0.5跳遞增，將錨節(jié)點(diǎn)覆蓋區(qū)域劃分為兩部分，取通信半徑的1/2為區(qū)分半徑。由式(3)可將距離差值換算成功率衰減程度，如式(5)所示

P(r0)/P(r)=2β.

(5)

當(dāng)功率衰減程度大2β時(shí)，表明此時(shí)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離大于R/2，此時(shí)就取跳數(shù)值為1;否則,取0.5，如式(6)所示

(6)

前文已經(jīng)提到，井下隧道有很多支道和彎道，如圖3所示，這里給出了井下節(jié)點(diǎn)網(wǎng)絡(luò)基本場(chǎng)景的直線擬合，信標(biāo)節(jié)點(diǎn)N與未知節(jié)點(diǎn)A,B,C,D之間的路徑近似于直線，但由于井下彎道和設(shè)備障礙的存在，在信標(biāo)節(jié)點(diǎn)2,3等之間的路徑形成一定的彎曲度,增大了它們之間的可達(dá)跳數(shù)。

圖3 井下場(chǎng)景直線擬合示意圖

因此，在計(jì)算平均每跳距離avgij時(shí)，就需要篩選一個(gè)比較精確的平均跳距。以信標(biāo)節(jié)點(diǎn)N舉例，給出選擇過程的簡(jiǎn)單描述：

信標(biāo)節(jié)點(diǎn)N與周圍的n-1個(gè)信標(biāo)之間有n-1個(gè)avgij(j=2,3,…，n)，取其中一個(gè)值作為參考對(duì)象，若以信標(biāo)節(jié)點(diǎn)2和1之間的跳距avg21為參考，考慮其他n-2個(gè)avgi1與其之間的偏差程度，用ρj1表示，如式(7)所示

(7)

則每個(gè)偏差度對(duì)應(yīng)的選擇因子αj1可由式(8)表示

(8)

從式中可看出：偏差程度ρj1越小，其選擇因子αj1越大，因此，選擇αj1最大值所相應(yīng)的avgj1作為信標(biāo)節(jié)點(diǎn)1最終與未知節(jié)點(diǎn)之間的平均每跳距離avg1。以此類推，直到其他n-1個(gè)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的平均每跳距離值avgi選擇出來(lái)，再求平均值，得出最終的平均跳距Cavg

(9)

結(jié)合式(6)計(jì)算出來(lái)的跳數(shù)，利用傳統(tǒng)計(jì)算方法計(jì)算出每個(gè)未知節(jié)點(diǎn)到相鄰錨節(jié)點(diǎn)的距離

dn=hopsn×Cavg.

(10)

當(dāng)未知節(jié)點(diǎn)至少獲得與3個(gè)錨節(jié)點(diǎn)間的距離時(shí)，假設(shè)(x,y)為未知節(jié)點(diǎn)坐標(biāo)，它接收到的錨節(jié)點(diǎn)坐標(biāo)為(xn,yn)通過使用最大似然估計(jì)法來(lái)計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，具體計(jì)算公式如式(11)所示

(11)

將前n-1個(gè)方程減去最后一個(gè)方程，再化簡(jiǎn)成線性方程AX=B形式，可得到3個(gè)矩陣A,X,B，如式(12)所示

(12)

再使用標(biāo)準(zhǔn)的最小均差估計(jì)方法可以得到未知節(jié)點(diǎn)的坐標(biāo)(x,y),計(jì)算公式如式(13)所示

=AT(ATA)-1B.

(13)

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

為了驗(yàn)證區(qū)域劃分和篩選因子在定位算法改進(jìn)中的作用，在這里利用Matlab平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)。為了實(shí)驗(yàn)數(shù)據(jù)更為理想，對(duì)每個(gè)實(shí)驗(yàn)場(chǎng)景都執(zhí)行了50次，再求平均。因?yàn)檠芯康氖蔷滤淼?，故選定仿真區(qū)域?yàn)? m×2 000 m的矩形區(qū)域，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)坐標(biāo)隨機(jī)產(chǎn)生，節(jié)點(diǎn)通信半徑相同，仿真結(jié)果如圖4、圖5、圖6所示。

圖4所示是在相同通信半徑情況下,在長(zhǎng)直隧道中,改進(jìn)算法比傳統(tǒng)算法定位精度更高,從圖中可看出：當(dāng)通信半徑為20～30 m時(shí)，定位精度比傳統(tǒng)算法提高了20 %。在篩選平均跳數(shù)和跳距過程中充分利用節(jié)點(diǎn)資源來(lái)減少誤差，有效降低了節(jié)點(diǎn)定位誤差。但當(dāng)半徑較小時(shí)，改進(jìn)算法優(yōu)勢(shì)不很明顯，因?yàn)榘霃教?，就沒有分區(qū)域的必要。隨著通信半徑進(jìn)一步增大時(shí)，定位精度提高有所減少，半徑太大，誤差也大，若再細(xì)分區(qū)域就會(huì)增加節(jié)點(diǎn)計(jì)算量，就會(huì)消耗更多節(jié)點(diǎn)能量，這樣會(huì)影響井下傳感器節(jié)點(diǎn)的壽命。

圖5、圖6中是經(jīng)改進(jìn)的DV-Hop算法，分別在彎曲巷道和長(zhǎng)直巷道以及分層層數(shù)不同幾種情況下與傳統(tǒng)DV-Hop算法的定位誤差的比較，可看出定位誤差隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加而減少,錨節(jié)點(diǎn)數(shù)量在120～150個(gè)時(shí)提高最為明顯，因?yàn)殡S著錨節(jié)點(diǎn)數(shù)量的增加擴(kuò)大了篩選范圍，也提高了跳數(shù)精度。但不能隨意增加錨節(jié)點(diǎn)數(shù)量，隨著錨節(jié)點(diǎn)數(shù)量的增加，錨節(jié)點(diǎn)的計(jì)算量會(huì)急劇增大，當(dāng)錨節(jié)點(diǎn)數(shù)量到了一定數(shù)量時(shí)，定位精度提高的就趨于平緩了。

圖4 錨節(jié)點(diǎn)通信半徑與平均定位誤差的關(guān)系

圖5 錨節(jié)點(diǎn)數(shù)量與平均定位誤差的關(guān)系

綜上所述,通過劃分信號(hào)覆蓋區(qū)域來(lái)提高跳數(shù)精確度和采用篩選因子來(lái)選擇平均跳距的方式能有效提高井下DV-HOP算法的定位精度，尤其是在有彎道和分層的情形下提高更為明顯，更加適合環(huán)境復(fù)雜的井下無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位。

4 結(jié) 論

針對(duì)傳統(tǒng)DV-Hop在井下巷道中的局限性，本文結(jié)合井下隧道彎曲復(fù)雜的特點(diǎn)對(duì)傳統(tǒng)算法提出了改進(jìn)，通過劃分錨節(jié)點(diǎn)信號(hào)區(qū)域的方法來(lái)提高跳數(shù)的精準(zhǔn)度，以減少定位半徑與節(jié)點(diǎn)距離相差太大而造成的跳數(shù)誤差；而在平均跳距選取方面，提出了使用一個(gè)選擇因子來(lái)篩選平均跳距，使得平均每跳距離更加接近于實(shí)際值。進(jìn)而減小由于巷道彎曲所造成的節(jié)點(diǎn)間距離的誤差。仿真結(jié)果表明：在井下巷道有彎曲或者分層情況下，本文的算法比傳統(tǒng)DV-Hop定位算法在定位精度上有很大程度的提高，更加適合井下井下復(fù)雜環(huán)境的節(jié)點(diǎn)定位。

參考文獻(xiàn):

[1] 張江石,傅 貴,陳 娜,等.礦工應(yīng)急處置能力評(píng)估方法研究 [J].煤炭學(xué)報(bào),2012,37(2):290-294.

[2] 周公博.礦井巷道無(wú)線傳感器網(wǎng)絡(luò)分層拓?fù)淇刂撇呗訹J].煤炭學(xué)報(bào)，2010,35(2):333-337.

[3] 薛 霞,孫 勇.監(jiān)測(cè)煤礦的一種無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].傳感器與微系統(tǒng),2010,29(9):119-123.

[4] Xiao Yi,Yu Lin,Lu Deng.An improved DV-Hop positioning algorithm with modified distance error for wireless sensor net-works[C]∥2009 Second International Symposium on Knowledge Acquisition and Modeling,2009:216-218.

[5] 劉志高,李春文,邢智鵬,等.巷道網(wǎng)絡(luò)全局定位系統(tǒng)關(guān)鍵技術(shù)分析與實(shí)驗(yàn)[J].煤炭學(xué)報(bào),2011,36 (3):519-526.

[6] 梁美玉,李 莉,陳 坤.基于蟻群算法的井下無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究[J].煤礦機(jī)械,2010,31 (12):48-50.

[7] 劉 凱,余君君,譚立雄.跳數(shù)加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2012,25(11):1539-1542.

[8] 楊 順,李龍青.井下無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[J].微電子學(xué)與計(jì)算機(jī),2010,27 (11):166-120.

[9] 劉文遠(yuǎn),王恩爽,陳子軍.無(wú)線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J].小型微型計(jì)算機(jī)系統(tǒng),2011,32(6):1071-1075.

[10] 趙清華,劉少飛,張朝霞.一種無(wú)需測(cè)距節(jié)點(diǎn)定位算法的分析改進(jìn)[J].傳感技術(shù)學(xué)報(bào),2010,23(1):122-127.

[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] Madhulika,Kumar A,Varna S.Iterative and distributed range-free localization algorithm for wireless sensor networks [C]∥Proc of IMPACT’09,Aligarh,2009:102-105.

[13] Almuzaini K,Gulliver T A.A new distributed range-free localization algorithm for wireless networks[C]∥Proc of 70th VTC Fall:IEEE,Anchorage,AK,2009:1-5.

[14] Bettstetter C.On the minimum node degree and connectivity of a wireless multi-hop network [C]∥MOBIHOC’02,New York,US:ACM,2002:80- 91.

[15] Poggi C,Mazzini G.Collinearity for sensor network localiza-tion [C]∥Proceedings of 2003 IEEE 58th Vehicular Technology Conference Piscatataway,NI,USA,IEEE,2004:3040-3044.

[16] Huang Qiqian,Selvakenndev S.A range-free localization algorithm for wireless sensor networks [C]∥Proc of 63rd Vehicle Technology Conference:IEEE,Melbourne,Vic,2006:349-35.

[17] Niculescu D,Nath B.DV-based positioning in Ad Hoc network-s[J].Journal of Telecommunication Systems,2003,22(1/4):267-280.