煤礦巷道中無線傳感器網絡的可靠路由算法

胡長俊，洪炎，唐超禮，鐘鳴宇，姚善化

安徽理工大學電氣與信息工程學院，安徽淮南 232001

煤礦巷道中無線傳感器網絡的可靠路由算法

胡長俊，洪炎，唐超禮，鐘鳴宇，姚善化

安徽理工大學電氣與信息工程學院，安徽淮南 232001

1 引言

可靠有效的井下監測系統對我國的煤礦生產安全有重要意義。無線傳感器網絡（WSN）具有靈活、廉價、低功耗、自組織的特點，在煤礦井下空間有著廣闊的應用前景[1-2]。

路由是WSN的重要技術之一，對網絡性能影響很大[3]。目前針對井下通信環境中無線傳感器網絡的路由技術已經有了一定的研究。文獻[4]采用非均勻分簇策略，提出一個簇規模自適應調節的能量均勻分簇路由協議。文獻[5]提出一種基于位置估計的多跳路由協議，選擇恰當的移動節點作為轉發節點，延長信標節點的生存時間。文獻[6]提出一種綜合優化的分簇路由協議，采用“局部協商”策略減少路由重疊，改善了簇頭分布及熱區問題。文獻[7]提出一種基于位置信息和網絡梯度的貪婪型路由算法，解決了節點走出空洞及如何選擇下一跳節點的問題，算法有較好擴展性。文獻[8]分析了LEACH協議應用于井下環境的優勢與不足，提出了適合于井下的LEACH-I協議。李輝等[9]將煤礦井下監測節點分布簡化為鏈式2層拓撲結構，利用無線信號模型尋找使每回合能耗最小的最優簇數，同時利用設備排列的有序性引入虛擬地址的方法來分簇，提出了基于虛擬地址的能量有效路由協議。梁瑩等[10]根據井下通信環境較差的情況，提出多路徑的傳輸方式。文獻[11]在傳統的AODV路由思想基礎上提出了一種基于最小跳數的相交多路徑路由算法，均衡了網絡能耗。文獻[12]提出一種基于信標路由協議；文獻[13]提出的CWU MSN用于監測井下環境和礦工位置，文中還討論了一種最少密度簇頭節點布置策略。TEEN[14]采用了一定措施提高路由效率，延長網絡壽命。

以上算法分別從路由的可靠，減少節點能耗，延長網絡的生存期等某方面考慮而不能兼顧其他因素。井下通信環境要求傳感器網絡必須在滿足實時、可靠的同時，兼顧網絡的使用壽命。本文在對以上路由算法和數據可靠傳輸方法分析基礎上，針對井下巷道的環境特點，提出了一種多跳可靠路由算法。和其他同類算法相比，本文的算法具有傳遞時延小，路由可靠性強，容易實現等特點。

2 問題描述與系統模型

本文把井下巷道空間近似看成長方體區域，假設傳感器節點等距離部署在井下巷道的兩側等高的兩條水平線上，每個節點與另一側與其位置對應節點的連線與巷道側壁垂直，sink節點位于巷道的一頭，信息源節點通過巷道兩邊的節點以多跳的方式傳遞信息到sink節點。在井下巷道環境中，當電磁波沿著巷道的一邊側壁傳遞時，受巷道表面的結構和材質影響，信號衰減較大，傳播距離有限，為了減少能耗，本文采用不同側節點交替傳遞的方式，如圖1所示。節點電磁波傳遞模型與自由空間模型類似。同時，為了減少節點轉發次數和到達sink節點的時間，降低信息傳輸的平均能耗，發送節點盡可能和通信范圍內較遠的接收節點通信。

圖1 巷道內節點部署及消息傳遞

假設DIS(Va，Vb)表示節點a，b的距離，DIS(Va，sink)表示節點Va到sink的距離，節點的通信半徑為R，給出以下定義。

定義1節點的有效接收節點，對節點Vi而言，其有效接受節點為集合{Vj|DIS(Vi，Vj)＜R且DIS(Vj，sink)＜DIS(Vi，sink)，且Vj與Vi不在巷道同一側}。

每個節點往往有多個有效接受節點，為了防止多個節點轉發相同的信息，造成后續節點接收信息沖突以及無謂的能量損耗，本文采取節點屏蔽措施，即每個節點接收到信息后根據自己的位置信息和剩余能量確定一個等待時間T，在等待時間后再發送信息；如果在等待時間T之內收到其他節點的信息，則表示信息已經被其他節點轉發，節點放棄發送。接收節點收到信息后，按照公式（1）確定自己的等待時間T：

其中Er為節點剩余能量。本文規定當節點剩余能量Er達到初始能量Eo的5%時，發出告警信息提示更換節點，同時不再轉發其他節點信息，對其他節點視為失效。c1、c2兩個因子分別表示節點的接收角度和剩余能量在決定等待時間T中所占的比重，具體取值要在實際環境下通過仿真實驗測試得出。一般在網絡初始階段，節點剩余的能量相對充足，主要考慮節點的位置因素，而隨著系統的運行，節點能量因素所占比例越來越大。由于發射節點對面的節點接收角度為90°，規定對面節點的等待時間為有效接收節點等待時間的最大值Tmax。

從式（1）可知，對于那些接收角度較小，剩余能量多的節點，等待時間T較短，優先被確定為轉發節點發送信息，算法兼顧了消息傳遞時延和節點的能耗均衡。

如圖1所示，b、c、d是節點a的有效接收節點，收到a的信息后，b節點由于接收角度較小，等待時間短，優先轉發信息，c、d節點在各自的等待時間T內收到b的信息后放棄發送，a收到b的信息則確定信息已經被b轉發。

由于井下通信環境的特殊性，為了保證節點通信路由的可靠，當接收節點失效時，算法采用路由切換的方式繼續路由過程。

如圖1所示，當節點m轉發信息后，其有效接收節點（圖中陰影表示）都已失效，其對面的節點n收到m的轉發消息后，啟動一個定時器Tmax，如果在Tmax內沒有收到其他節點轉發的有效信號時，則節點b將信息轉發給自己的有效接收節點，繼續多跳傳遞過程。節點a收到對面節點b的轉發信息后即知道自己的有效接收節點都已失效，立即發出告警，提示替換失效節點，在新節點補充前臨時增大發射半徑為NR(N=2，3)以保證路由功能。如果節點b也沒有有效的接收節點（在b的有效接收節點等待時間T內沒有收到回應），也采取臨時增大發射半徑、告警提示替換失效節點等措施。新的節點部署后，立即向周圍發送廣播信息，通知以新節點為有效接收節點的節點恢復原來的發射半徑R，即圖1中替換失效節點的新節點會通知m節點恢復原來的發射半徑R。

3 路由算法過程

節點部署完成后進行初始化，每個節點獲得左右相鄰和正對面位置節點的信息，包括節點ID和坐標。檢測到信息的源節點以半徑R向周邊發送信息，根據上文中的描述，接受到信息的節點處理過程為：

步驟1首先判斷信息是否來自對面的節點的消息，如果不是，轉步驟2；否則進一步判斷信息是否是重復信息，如果不是設置等待時間Tmax，并轉步驟5；否則發出告警提示補充節點，轉步驟7。

步驟2如果自己不是消息的有效接收節點，直接轉步驟7；否則轉步驟3。

步驟3根據收到信息計算接收角度θ和等待時間T。

步驟4如果在T內收到其他節點轉發的相同信息則丟棄，轉步驟7；否則轉步驟6。

步驟5如果在Tmax內收到其他節點轉發的信息則丟棄信息，轉步驟7；否則轉步驟6。

步驟6以半徑R發送信息。

步驟7結束。

節點發送消息的格式為：

（節點ID，節點坐標，發射半徑，消息ID，消息內容）

每個節點在轉發消息前會在消息內加入自己的ID、坐標信息即發射半徑。接收節點用這些內容判斷有效接收節點和計算等待時間。一個信息源節點產生的消息ID在整個傳遞過程不變，這樣既可以把不同的消息區別開，也能防止對重復消息處理。

4 算法性能分析

4.1 單次消息傳遞跳數分析

消息傳遞跳數和節點的部署密度及節點的位置都有直接關系，在實際應用時，可以采用平均等距的節點部署方式，假設節點的傳遞模型為自由空間模型，在事先確定節點通信半徑R的前提下，可以將節點的有效接收節點置于節點通信半徑位置處，如圖2所示。

圖2 節點等距部署時消息傳遞過程

設源節點S距離sink節點的距離為L，巷道寬為W，則消息從源節點傳遞到sink節點經過的跳數H為：

當有效接收節點失效時，啟動路由切換過程，消息傳遞跳數加1，在最壞情況下單次消息傳遞跳數為O(H)。

4.2 單次消息的路由時間分析

由4.1節分析知，在一般情況下，巷道中沒有失效節點時，單次消息路由時間由跳數H決定。由公式（1）知，在節點能量差別不大的情況下，由于有效接收節點位置固定（如圖2），節點轉發的時間T也是固定的。

節點的接收角度為：

在最壞情況下，消息每經過一次轉發就啟動路由切換過程，即一半節點通過路由切換轉發消息，則路由的總時間Trout_time為：

當失效節點數更多時，可能會使有些節點增加通信半徑，路由時間減少；也可能造成路由失敗。

5 仿真與結果分析

為了檢驗算法的效果，在上文所述網絡模型基礎上使用NS2仿真工具對算法進行了仿真。節點通信模型采用自由空間模型，不考慮節點傳輸中的相互干擾及時間同步問題，MAC層采用802.15.4協議，信道使用的參數如表1所示，主要考察算法的消息成功傳遞的概率、路由平均時延等方面的性能，并與文獻[4-5，8，13]提出的路由算法在同等環境下分別做了比較。

表1中的發射數據能耗和接收數據能耗是在半徑R內的能耗值，當發射距離和接受距離超過半徑R時，節點能耗的計算采用文獻[15]描述的方法。公式（1）中c1、c2參數都取0.5。

表1 節點參數設置表

5.1 路由的平均時間

本文用源節點的信息到達sink節點經過中間節點轉發的次數來表示路由的時間。仿真環境中節點數取50～100，從監測區域中隨機設10個信息源點，取形成的10個路由上節點轉發次數的平均值作為分析對象，結果如圖3所示。

圖3 路由轉發次數比較

由圖3中所示，本文提出的算法平均轉發次數基本在25次以下，這是由于算法傾向選擇通信距離較遠的節點，當點數較少時，節點的有效接收節點相對偏少，會出現借助于對面的節點轉發及增加通信半徑轉發的情況，轉發次數增加。而文獻[4]的分區算法的轉發次數和分區數直接相關，而分區數是按照節點的能耗、節點數目及巷道長度確定的，與節點的通信半徑無直接關系，當節點密度達到一定要求，路由平均次數變化不大。其他三種算法更多考慮節點能耗的均衡，平均轉發次數明顯多于本文算法的轉發次數。

5.2 成功傳遞率

傳感器節點數取50～100，在監測區域中隨機取50個信息源點，分別在幾種算法運行過程中統計50個源點產生的消息成功傳遞到sink節點的次數（每個源點成功傳遞次數取10次運行的平均值），結果如圖4所示。

圖4 成功傳遞率比較

從圖4可以看出，隨著節點數的增加，文獻[4]的分區算法中，節點數較少時，路由容易出現中斷，成功傳遞次數偏低；隨著節點數增加，成功傳遞次數也相應增加。文獻[5]使用了移動節點作為中轉，帶有一定隨機性，成功傳遞的次數低于其他算法。文獻[8]選擇路由節點主要考慮轉發所消耗的能量及節點的剩余能量因素，節點數較少時成功傳遞率與文獻[4]接近。文獻[13]提出的方法得到的成功傳遞率總體介于以上三種方法之間。而本文算法中的消息成功傳遞次數則基本在45次以上，與節點數無關，原因是提出的算法采用了路由切換和增加通信半徑等手段保證了成功傳遞概率，對不同節點數目的網絡有很好的適應性，能滿足井下通信可靠性的要求。

6 結束語

本文結合井下巷道的實際環境提出了一種無線傳感器網絡路由方法。節點在巷道兩側等距部署，采用對邊節點多跳的通信方式傳遞信息到sink節點。按照節點的位置和能量確定下一跳轉發節點，減少了傳遞能耗和時間，在節點失效時利用路由切換技術增加路由的可靠性。仿真結果說明了算法的有效性，其更適用于井下巷道環境對信息的實時傳遞和可靠性的要求。今后，將在本文算法基礎上進一步均衡節點的能耗，延長網絡的生存期。

[1]孫利民，李建中，陳渝.無線傳感器網絡[M].北京：清華大學出版社，2005.

[2]周公博.面向窄長空間的無線傳感器網絡可靠性關鍵技術研究[D].徐州：中國礦業大學機電工程學院，2010.

[3]沈波，張世永，鐘亦平.無線傳感網網絡分簇路由協議[J].軟件學報，2006，17（7）：1588-1600．

[4]吳華君，張自力，李衛.一種適用于煤礦井下無線傳感網的能量均衡路由協議[J].計算機科學，2011，38（4）：145-150．

[5]喬剛柱，曾建潮，趙明.基于位置估計的井下無線傳感器網絡路由算法[J].系統工程理論與實踐，2011，31（10）：175-180.

[6]呂振，孫延飛，李亞杰，等.一種綜合優化的礦用無線傳感器網絡路由協議[J].傳感器與微系統，2010，29（4）：74-77.

[7]童敏明，楊禮現，劉曉文，等.礦井無線傳感器檢測網絡路由改進算法的研究[J].傳感技術學報，2008，21（11）：1892-1895.

[8]吳青，張申，李曙俏，等.一種應用于煤礦井下LEACH路由協議的改進[J].傳感器與微系統，2012，31（4）：23-25.

[9]李輝，張曉光，劉穎.基于煤礦設備有序拓撲的能量有效路由協議[J].中國礦業大學學報，2011，40（5）：774-780.

[10]梁瑩，李曉，張記龍，等.井下無線通信網絡路由快速建立的方法[J].煤炭科學技術，2011，39（8）：93-96.

[11]高鶯.礦山井下無線傳感器網絡多徑路由協議的研究[D].北京：北京交通大學，2010.

[12]Sun Zheng，Zhang Xiaoguang，Li Hui，et al.The application of TinyOS beaconing WSN routing protocol in mine safety monitoring[C]//Proceedings of 2008 IEEE/ASME International ConferenceonMechtronicandEmbeddedSystemsand Applications（MESA）.Piscataway：IEEE Press，2008：415-419.

[13]Chen Guangzhu，Zhu Zhencai，Zhou Gongbo，et al.Sensor deployment strategy for chain-type wireless underground mine sensor network[J].Journal of China University of Mining and Technology，2008，18（4）：561-566.

[14]Manjeshwar A，Agrawal D P.TEEN：a routing protocol forenhanced efficiency in wireless sensor networks[C]//Proc of the 15th International Parallel and Distributed Symposium，San Francisco，CA，USA，2001：2009-2015.

[15]楊光松，肖明波，程恩.水聲傳感網中節省能量的尋路機制[J].北京郵電大學學報，2009，32（4）：88-92.

HU Changjun,HONG Yan,TANG Chaoli,ZHONG Mingyu,YAO Shanhua

School of Electric and Information Engineering,Anhui University of Science and Technology,Huainan,Anhui 232001,China

A routing algorithm of Wireless Sensor Network（WSN）is proposed for roadway in coal mines according to its working environment.Firstly,the algorithm determines the optimal forwarding node based on the location and remaining energy of the node,which shortens the time to deliver the message in the multi-hop route and balances the node energy consumption.When nodes fail in the routing process,the algorithm,using routing switching technology,generates complementary route to continue the routing procedure through the opposite side of the node,greatly increases the reliability of routing.Simulation and analysis show that,compared with other typical partitioning algorithm for the roadway,the route generated from the algorithm has a shorter latency and a higher data transfer rate and is more suitable for the coal mines environment.

Wireless Sensor Network（WSN）;routing;multi-hop delivery;switch

根據井下巷道的實際工作環境，提出了一種適用于井下巷道的無線傳感器網絡路由算法。算法根據接收節點的位置和剩余能量來確定最優轉發節點，既減少了多跳路由傳遞的時間又均衡了節點能耗；算法在路由過程中節點失效時利用路由切換技術，通過對側的節點形成互補路由來繼續路由過程，大大增加路由的可靠性。仿真實驗及分析表明，與其他典型的井下巷道分區算法相比，該算法生成的路由有更短的時延和更高的數據傳遞率，適合于井下巷道環境。

無線傳感器網絡；路由；多跳傳遞；切換

A

TP393

10.3778/j.issn.1002-8331.1305-0498

HU Changjun,HONG Yan,TANG Chaoli,et al.Reliable routing protocol of wireless sensor networks for roadway in coal mines.Computer Engineering and Applications,2013,49（19）：96-99.

國家自然科學基金（No.51274011，No.51104003）；安徽高校省級自然科學研究重點項目（No.KL2011A077）；安徽高校省級自然科學研究項目（No.KJ2012Z083）。

胡長俊（1973—），男，講師，主要研究方向為無線傳感器網絡；洪炎（1979—），男，副教授，主要研究方向為計算機監控技術；唐超禮（1980—），男，副教授，主要研究方向為井下通信技術；鐘鳴宇（1982—），男，講師，主要研究方向為信號處理；姚善化（1967—），男，博士，教授，主要研究方向為井下通信技術。E-mail：601254090@qq.com

2013-06-04

2013-08-01

1002-8331（2013）19-0096-04

◎數據庫、數據挖掘、機器學習◎