基于井下異構無線傳感器網絡DV-Hop定位算法的改進

方旺盛, 吳勝寶

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

0 引 言

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

1 井下隧道物理模型

1.1 井下空間模型

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

圖1 分層巷道和分支、弧形巷道簡化模型

1.2 井下電磁波傳輸模型

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

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

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

(1)

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

(2)

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

(3)

2 DV-HOP算法分析與改進

2.1 傳統算法分析

Niculescu D等人提出的DV-Hop節點定位算法是一種基于距離矢量計算跳數的算法[17]。首先，每個信標節點向所在網絡廣播包含自身位置信息和跳數值為0的信息，當周圍鄰居節點接收后，將會記錄位置信息和跳數，并將跳數加1再廣播出去，整個過程中只保留收到的包含最小跳數值的信息，以此類推，直到網絡中所有節點都獲得與之相鄰的信標節點的位置信息和最小跳數值。

其次，當錨節點收到其它錨節點的信息后，可依據式(4)估算平均每跳距離

(4)

式中 (xi，yi) 和(xj，yj)為錨節點i和j的坐標，hj為錨節點j到錨節點i的最小跳數。

2.2 算法改進描述

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

圖2 巷道中節點位置與通信半徑的關系

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

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

(5)

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

(6)

前文已經提到，井下隧道有很多支道和彎道，如圖3所示，這里給出了井下節點網絡基本場景的直線擬合，信標節點N與未知節點A,B,C,D之間的路徑近似于直線，但由于井下彎道和設備障礙的存在，在信標節點2,3等之間的路徑形成一定的彎曲度,增大了它們之間的可達跳數。

圖3 井下場景直線擬合示意圖

因此，在計算平均每跳距離avgij時，就需要篩選一個比較精確的平均跳距。以信標節點N舉例，給出選擇過程的簡單描述：

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

(7)

則每個偏差度對應的選擇因子αj1可由式(8)表示

(8)

從式中可看出：偏差程度ρj1越小，其選擇因子αj1越大，因此，選擇αj1最大值所相應的avgj1作為信標節點1最終與未知節點之間的平均每跳距離avg1。以此類推，直到其他n-1個信標節點與未知節點之間的平均每跳距離值avgi選擇出來，再求平均值，得出最終的平均跳距Cavg

(9)

結合式(6)計算出來的跳數，利用傳統計算方法計算出每個未知節點到相鄰錨節點的距離

dn=hopsn×Cavg.

(10)

當未知節點至少獲得與3個錨節點間的距離時，假設(x,y)為未知節點坐標，它接收到的錨節點坐標為(xn,yn)通過使用最大似然估計法來計算未知節點的坐標，具體計算公式如式(11)所示

(11)

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

(12)

再使用標準的最小均差估計方法可以得到未知節點的坐標(x,y),計算公式如式(13)所示

=AT(ATA)-1B.

(13)

3 實驗仿真

為了驗證區域劃分和篩選因子在定位算法改進中的作用，在這里利用Matlab平臺上進行仿真實驗。為了實驗數據更為理想，對每個實驗場景都執行了50次，再求平均。因為研究的是井下隧道，故選定仿真區域為5 m×2 000 m的矩形區域，信標節點和未知節點坐標隨機產生，節點通信半徑相同，仿真結果如圖4、圖5、圖6所示。

圖4所示是在相同通信半徑情況下,在長直隧道中,改進算法比傳統算法定位精度更高,從圖中可看出：當通信半徑為20～30 m時，定位精度比傳統算法提高了20 %。在篩選平均跳數和跳距過程中充分利用節點資源來減少誤差，有效降低了節點定位誤差。但當半徑較小時，改進算法優勢不很明顯，因為半徑太小，就沒有分區域的必要。隨著通信半徑進一步增大時，定位精度提高有所減少，半徑太大，誤差也大，若再細分區域就會增加節點計算量，就會消耗更多節點能量，這樣會影響井下傳感器節點的壽命。

圖5、圖6中是經改進的DV-Hop算法，分別在彎曲巷道和長直巷道以及分層層數不同幾種情況下與傳統DV-Hop算法的定位誤差的比較，可看出定位誤差隨著錨節點個數的增加而減少,錨節點數量在120～150個時提高最為明顯，因為隨著錨節點數量的增加擴大了篩選范圍，也提高了跳數精度。但不能隨意增加錨節點數量，隨著錨節點數量的增加，錨節點的計算量會急劇增大，當錨節點數量到了一定數量時，定位精度提高的就趨于平緩了。

圖4 錨節點通信半徑與平均定位誤差的關系

圖5 錨節點數量與平均定位誤差的關系

綜上所述,通過劃分信號覆蓋區域來提高跳數精確度和采用篩選因子來選擇平均跳距的方式能有效提高井下DV-HOP算法的定位精度，尤其是在有彎道和分層的情形下提高更為明顯，更加適合環境復雜的井下無線傳感器網絡節點定位。

4 結 論

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

參考文獻:

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

[2] 周公博.礦井巷道無線傳感器網絡分層拓撲控制策略[J].煤炭學報，2010,35(2):333-337.

[3] 薛 霞,孫 勇.監測煤礦的一種無線傳感器網絡節點定位算法[J].傳感器與微系統,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] 劉志高,李春文,邢智鵬,等.巷道網絡全局定位系統關鍵技術分析與實驗[J].煤炭學報,2011,36 (3):519-526.

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

[7] 劉 凱,余君君,譚立雄.跳數加權DV-Hop定位算法[J].傳感技術學報,2012,25(11):1539-1542.

[8] 楊 順,李龍青.井下無線傳感器網絡DV-Hop定位算法的改進[J].微電子學與計算機,2010,27 (11):166-120.

[9] 劉文遠,王恩爽,陳子軍.無線傳感器網絡中DV-Hop定位算法的改進[J].小型微型計算機系統,2011,32(6):1071-1075.

[10] 趙清華,劉少飛,張朝霞.一種無需測距節點定位算法的分析改進[J].傳感技術學報,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.