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

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

煤礦巷道中無線傳感器網(wǎng)絡(luò)的可靠路由算法

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

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

1 引言

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

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

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

2 問題描述與系統(tǒng)模型

本文把井下巷道空間近似看成長方體區(qū)域，假設(shè)傳感器節(jié)點等距離部署在井下巷道的兩側(cè)等高的兩條水平線上，每個節(jié)點與另一側(cè)與其位置對應(yīng)節(jié)點的連線與巷道側(cè)壁垂直，sink節(jié)點位于巷道的一頭，信息源節(jié)點通過巷道兩邊的節(jié)點以多跳的方式傳遞信息到sink節(jié)點。在井下巷道環(huán)境中，當(dāng)電磁波沿著巷道的一邊側(cè)壁傳遞時，受巷道表面的結(jié)構(gòu)和材質(zhì)影響，信號衰減較大，傳播距離有限，為了減少能耗，本文采用不同側(cè)節(jié)點交替?zhèn)鬟f的方式，如圖1所示。節(jié)點電磁波傳遞模型與自由空間模型類似。同時，為了減少節(jié)點轉(zhuǎn)發(fā)次數(shù)和到達(dá)sink節(jié)點的時間，降低信息傳輸?shù)钠骄芎?，發(fā)送節(jié)點盡可能和通信范圍內(nèi)較遠(yuǎn)的接收節(jié)點通信。

圖1 巷道內(nèi)節(jié)點部署及消息傳遞

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

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

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

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

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

如圖1所示，b、c、d是節(jié)點a的有效接收節(jié)點，收到a的信息后，b節(jié)點由于接收角度較小，等待時間短，優(yōu)先轉(zhuǎn)發(fā)信息，c、d節(jié)點在各自的等待時間T內(nèi)收到b的信息后放棄發(fā)送，a收到b的信息則確定信息已經(jīng)被b轉(zhuǎn)發(fā)。

由于井下通信環(huán)境的特殊性，為了保證節(jié)點通信路由的可靠，當(dāng)接收節(jié)點失效時，算法采用路由切換的方式繼續(xù)路由過程。

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

3 路由算法過程

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

步驟1首先判斷信息是否來自對面的節(jié)點的消息，如果不是，轉(zhuǎn)步驟2；否則進(jìn)一步判斷信息是否是重復(fù)信息，如果不是設(shè)置等待時間Tmax，并轉(zhuǎn)步驟5；否則發(fā)出告警提示補(bǔ)充節(jié)點，轉(zhuǎn)步驟7。

步驟2如果自己不是消息的有效接收節(jié)點，直接轉(zhuǎn)步驟7；否則轉(zhuǎn)步驟3。

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

步驟4如果在T內(nèi)收到其他節(jié)點轉(zhuǎn)發(fā)的相同信息則丟棄，轉(zhuǎn)步驟7；否則轉(zhuǎn)步驟6。

步驟5如果在Tmax內(nèi)收到其他節(jié)點轉(zhuǎn)發(fā)的信息則丟棄信息，轉(zhuǎn)步驟7；否則轉(zhuǎn)步驟6。

步驟6以半徑R發(fā)送信息。

步驟7結(jié)束。

節(jié)點發(fā)送消息的格式為：

（節(jié)點ID，節(jié)點坐標(biāo)，發(fā)射半徑，消息ID，消息內(nèi)容）

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

4 算法性能分析

4.1 單次消息傳遞跳數(shù)分析

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

圖2 節(jié)點等距部署時消息傳遞過程

設(shè)源節(jié)點S距離sink節(jié)點的距離為L，巷道寬為W，則消息從源節(jié)點傳遞到sink節(jié)點經(jīng)過的跳數(shù)H為：

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

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

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

節(jié)點的接收角度為：

在最壞情況下，消息每經(jīng)過一次轉(zhuǎn)發(fā)就啟動路由切換過程，即一半節(jié)點通過路由切換轉(zhuǎn)發(fā)消息，則路由的總時間Trout_time為：

當(dāng)失效節(jié)點數(shù)更多時，可能會使有些節(jié)點增加通信半徑，路由時間減少；也可能造成路由失敗。

5 仿真與結(jié)果分析

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

表1中的發(fā)射數(shù)據(jù)能耗和接收數(shù)據(jù)能耗是在半徑R內(nèi)的能耗值，當(dāng)發(fā)射距離和接受距離超過半徑R時，節(jié)點能耗的計算采用文獻(xiàn)[15]描述的方法。公式（1）中c1、c2參數(shù)都取0.5。

表1 節(jié)點參數(shù)設(shè)置表

5.1 路由的平均時間

本文用源節(jié)點的信息到達(dá)sink節(jié)點經(jīng)過中間節(jié)點轉(zhuǎn)發(fā)的次數(shù)來表示路由的時間。仿真環(huán)境中節(jié)點數(shù)取50～100，從監(jiān)測區(qū)域中隨機(jī)設(shè)10個信息源點，取形成的10個路由上節(jié)點轉(zhuǎn)發(fā)次數(shù)的平均值作為分析對象，結(jié)果如圖3所示。

圖3 路由轉(zhuǎn)發(fā)次數(shù)比較

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

5.2 成功傳遞率

傳感器節(jié)點數(shù)取50～100，在監(jiān)測區(qū)域中隨機(jī)取50個信息源點，分別在幾種算法運(yùn)行過程中統(tǒng)計50個源點產(chǎn)生的消息成功傳遞到sink節(jié)點的次數(shù)（每個源點成功傳遞次數(shù)取10次運(yùn)行的平均值），結(jié)果如圖4所示。

圖4 成功傳遞率比較

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

6 結(jié)束語

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

[1]孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2]周公博.面向窄長空間的無線傳感器網(wǎng)絡(luò)可靠性關(guān)鍵技術(shù)研究[D].徐州：中國礦業(yè)大學(xué)機(jī)電工程學(xué)院，2010.

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

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

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

[6]呂振，孫延飛，李亞杰，等.一種綜合優(yōu)化的礦用無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].傳感器與微系統(tǒng)，2010，29（4）：74-77.

[7]童敏明，楊禮現(xiàn)，劉曉文，等.礦井無線傳感器檢測網(wǎng)絡(luò)路由改進(jìn)算法的研究[J].傳感技術(shù)學(xué)報，2008，21（11）：1892-1895.

[8]吳青，張申，李曙俏，等.一種應(yīng)用于煤礦井下LEACH路由協(xié)議的改進(jìn)[J].傳感器與微系統(tǒng)，2012，31（4）：23-25.

[9]李輝，張曉光，劉穎.基于煤礦設(shè)備有序拓?fù)涞哪芰坑行酚蓞f(xié)議[J].中國礦業(yè)大學(xué)學(xué)報，2011，40（5）：774-780.

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

[11]高鶯.礦山井下無線傳感器網(wǎng)絡(luò)多徑路由協(xié)議的研究[D].北京：北京交通大學(xué)，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]楊光松，肖明波，程恩.水聲傳感網(wǎng)中節(jié)省能量的尋路機(jī)制[J].北京郵電大學(xué)學(xué)報，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

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

無線傳感器網(wǎng)絡(luò)；路由；多跳傳遞；切換

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.

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

胡長?。?973—），男，講師，主要研究方向為無線傳感器網(wǎng)絡(luò)；洪炎（1979—），男，副教授，主要研究方向為計算機(jī)監(jiān)控技術(shù)；唐超禮（1980—），男，副教授，主要研究方向為井下通信技術(shù)；鐘鳴宇（1982—），男，講師，主要研究方向為信號處理；姚善化（1967—），男，博士，教授，主要研究方向為井下通信技術(shù)。E-mail：601254090@qq.com

2013-06-04

2013-08-01

1002-8331（2013）19-0096-04

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎