高秀娥，萬兵，劉長征

（1大連大學(xué)信息工程學(xué)院計算機系，大連116622；2大連大學(xué)網(wǎng)絡(luò)重點實驗室，大連116622；3石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，石河子832003）

無線傳感器網(wǎng)絡(luò)中的每個傳感器節(jié)點具備信號采集、數(shù)據(jù)處理、相互通信的功能，具有很大的靈活性，因此，該網(wǎng)絡(luò)在軍事、環(huán)境監(jiān)測等方面有很大的潛在應(yīng)用價值［1－2］。由于在無人監(jiān)測或環(huán)境惡劣的條件下，加上節(jié)點有限的能量的消耗，無線傳感器網(wǎng)絡(luò)很容易出現(xiàn)故障［1－5］。因此，容錯問題是設(shè)計無線傳感器網(wǎng)絡(luò)路由協(xié)議時必須考慮的重要因素。

隨著對無線傳感器網(wǎng)絡(luò)研究的深入，很多相關(guān)的路由協(xié)議［3－6］被提出，其中定向擴散（directed diffusion，DD）路由協(xié)議是最早提出的無線傳感器網(wǎng)絡(luò)路由協(xié)議之一。但是，由于DD路由協(xié)議不能檢測出故障的具體節(jié)點，也不能將出現(xiàn)故障的節(jié)點及其路徑從無線傳感器網(wǎng)絡(luò)中完全移除，使得還有信息繼續(xù)傳向這些節(jié)點，導(dǎo)致大量節(jié)點能量浪費和信息數(shù)據(jù)丟失。

目前，在無線傳感器網(wǎng)絡(luò)路由協(xié)議中，有關(guān)對故障路徑進行快速檢測和恢復(fù)的協(xié)議方面的報道很少。基于此，本文提出了主路徑節(jié)點故障快速檢測和恢復(fù)（FDFR）的無線傳感器網(wǎng)絡(luò)路由協(xié)議，該協(xié)議針對節(jié)點的具體故障原因進行快速檢測并恢復(fù)主路徑，能將故障節(jié)點及其相關(guān)路徑從網(wǎng)絡(luò)中完全移除，旨在避免能量的浪費和數(shù)據(jù)信息的丟失。

1 DD路由協(xié)議的容錯

1．1 DD路由協(xié)議容錯的優(yōu)點

DD路由協(xié)議［2］中的最大特點就是利用加強機制。主路徑上的中間節(jié)點可以在此主路徑出現(xiàn)故障后利用加強信號進行局部修復(fù)，出現(xiàn)路徑故障的原因有節(jié)點能量耗盡、安全攻擊、環(huán)境因素（比如出現(xiàn)障礙物）等。若主路徑上某節(jié)點發(fā)現(xiàn)來自上游節(jié)點的信息數(shù)據(jù)速率突然減小，或者發(fā)現(xiàn)周圍節(jié)點的信息傳輸速率突然增加，即此路徑發(fā)生故障，然后此節(jié)點便會發(fā)送否定加強信號直到source節(jié)點。如圖1a所示，當(dāng)sink節(jié)點發(fā)現(xiàn)此主路徑發(fā)生故障時，便會沿著主路徑發(fā)送否定加強信息，主路徑上的每個節(jié)點接收到否定加強信息后，便會將原來建立的加強的梯度消除。

圖1 DD路由協(xié)議中移除故障節(jié)點Fig．1Removing fault node in DD protocol

1．2 DD路由協(xié)議的缺陷

然而如圖1b所示，當(dāng)否定加強信息傳到故障節(jié)點時，由于該節(jié)點已經(jīng)發(fā)生故障，不能將此否定加強信息繼續(xù)傳播，因此，由于沒有把從source到故障節(jié)點的路徑刪除，source節(jié)點還會繼續(xù)向此路徑發(fā)送數(shù)據(jù)信息，導(dǎo)致大量信息數(shù)據(jù)的丟失和能量的浪費。

此外，由于DD路由協(xié)議中，當(dāng)出現(xiàn)路徑故障時，不能立即檢測到故障節(jié)點并重新選取新的主路徑，而是必須等到下一次探索信息泛洪時，才能重新找到主路徑，即：

式（1）中，Tr表示恢復(fù)故障所需時間，Te表示source節(jié)點下一次發(fā)送探索信息的時間，Tf表示出現(xiàn)故障時的時間。從式（1）中可以看出，若故障出現(xiàn)在剛發(fā)送了探索信息之后，則整個網(wǎng)絡(luò)必須等待很長時間才能找到新的主路徑，而在這段時間內(nèi)，將會有大量的信息數(shù)據(jù)丟失和節(jié)點能量的浪費。

因此，在無線傳感器網(wǎng)絡(luò)中，出現(xiàn)節(jié)點故障的主要原因有：節(jié)點能量耗盡、安全攻擊、環(huán)境因素等。由于主路徑上的節(jié)點傳輸信息數(shù)據(jù)量大、頻繁、能量消耗迅速，能量耗盡是路徑故障的一個很重要因素。DD路由協(xié)議的缺點是不能快速的檢測節(jié)點錯誤，為了能夠減少故障恢復(fù)時間，降低數(shù)據(jù)傳輸?shù)膩G失率，需要對DD路由協(xié)議進行改進。

2 FDFR路由協(xié)議的提出

針對于DD路由協(xié)議容錯的不足，本文提出的FDFR路由協(xié)議能夠及時確定該節(jié)點，并快速糾錯和重新選取新路徑。其可利用能量閾值實現(xiàn)節(jié)點故障的自身檢測；而對于安全攻擊，環(huán)境因素等造成的故障，由于節(jié)點已經(jīng)失去了和其它節(jié)點通信的功能，則采用后節(jié)點檢測方法。

2．1 自身檢測法

在設(shè)定能量閾值的自身檢測方法中，首先將主路徑上的傳感器節(jié)點設(shè)定一個能量閾值En，En的大小為該節(jié)點發(fā)送信息回到source節(jié)點所需要的能量與該節(jié)點轉(zhuǎn)發(fā)1次信息數(shù)據(jù)包所需能量之和。節(jié)點在每次轉(zhuǎn)發(fā)數(shù)據(jù)前，都要將所剩能量Eava和En進行比較。若Eava＜En，則該節(jié)點停止轉(zhuǎn)發(fā)信息數(shù)據(jù)，并由主路徑發(fā)送請求探索信息（ExploreRequest）直到source節(jié)點（圖2a）。當(dāng)source節(jié)點接收到請求探索信息后，停止向該路徑發(fā)送信息數(shù)據(jù)，并立即發(fā)送探索信息（exploratory data）以重新尋找主路徑；另一方面，為了將故障路徑和節(jié)點完全從網(wǎng)絡(luò)中刪除，首先，發(fā)送請求探索信息時，該故障節(jié)點把與下游節(jié)點相連的梯度刪除，當(dāng)請求探索信息到達某一節(jié)點時，便會檢查該節(jié)點是否有與故障節(jié)點相連的梯度，若有，便將該梯度刪除（圖2b）。

圖2 設(shè)定能量值的節(jié)點檢測Fig．2Detecting node according to set energy

2．2 后節(jié)點檢測法

當(dāng)某個節(jié)點出現(xiàn)故障時，便不能轉(zhuǎn)發(fā)信息數(shù)據(jù)。后節(jié)點檢測法的主要思想是讓主路徑上的每一個節(jié)點為其前一個節(jié)點設(shè)置一個時間限制Tim，如果定時器時間到了Tim而此節(jié)點仍未接收到來自上游節(jié)點的信息數(shù)據(jù)，此節(jié)點便會判斷其上游節(jié)點發(fā)生故障，緊接著，該節(jié)點便會泛洪發(fā)送ExploreRequest直到source節(jié)點，當(dāng)source節(jié)點接收到請求探索信息后便會立即全網(wǎng)泛洪發(fā)送exploratory data尋找新的主路徑。另外，當(dāng)節(jié)點接收到請求探索信息時，也會將與故障節(jié)點相連的梯度刪除。

傳感器節(jié)點發(fā)送信息數(shù)據(jù)是通過無線電通信技術(shù)。由于無線電通信過程容易發(fā)生錯誤導(dǎo)致信息數(shù)據(jù)包丟失，后節(jié)點檢測法必須把節(jié)點被破壞（安全攻擊，環(huán)境因素等）導(dǎo)致的發(fā)送失敗和無線電故障導(dǎo)致的間接性發(fā)送失敗區(qū)分開來。事實上，由無線電故障導(dǎo)致的間歇性發(fā)送失敗是應(yīng)該被容忍的。因此，決定時間限制Tim大小的因素主要有：無線電通信故障發(fā)生的時間長度、探索信息的發(fā)送時間間隔、加強信息發(fā)送的時間間隔。由于要容忍由無線電通訊故障導(dǎo)致的信息數(shù)據(jù)包丟失，時間限制Tim必須大于無線電通訊故障時間長度（Trad）。

由于無線電通信傳輸很容易出現(xiàn)故障，一個兩種狀態(tài)（故障和正常）的馬爾可夫模型（圖3）被Gilbert提出，即在每一次的發(fā)送信息數(shù)據(jù)間隔期間，無線電通訊信道都可能變成另一種狀態(tài)。符合幾何分布規(guī)律的變量BL表示逗留在故障狀態(tài)的時間，因此，處在故障狀態(tài)的平均時間E（BL）即為：

式（2）中，p表示連續(xù)2個信息數(shù)據(jù)包丟失的概率。

為了保證能夠容忍由無線電故障導(dǎo)致的發(fā)送信息數(shù)據(jù)失敗，計算無線電通訊故障時間長度Trad如下：

在計算Trad時，在平均故障時間的基礎(chǔ)上加上了標(biāo)準(zhǔn)差，這樣能保證后節(jié)點檢測法能夠容忍合理時間長度的無線電故障，也能夠更好地將無線電故障同其它節(jié)點故障原因區(qū)分開來。

圖3 Gilbert－Elliott模型Fig．3Gilbert－Elliott model

綜合考慮無線電故障時間Trad，加強信息時間間隔Ir和探索信息時間間隔Ie，設(shè)定的時間限制Tim應(yīng)為：

首先，利用式（4）計算出該無線傳感器網(wǎng)絡(luò)在當(dāng)前環(huán)境下的Tim值。

當(dāng)主路徑上的每個傳感器節(jié)點接收到第1個加強信息開始，便為其上游節(jié)點計時。當(dāng)出現(xiàn)以下情況時，便重新開始計時：①節(jié)點接收到上游節(jié)點發(fā)送的信息數(shù)據(jù)包；②探索信息全網(wǎng)泛洪發(fā)生（表明正在尋找新的主路徑）。

否則，如果Tim到達最大值，則說明該節(jié)點的上游節(jié)點發(fā)生故障。緊接著，該節(jié)點便會生成請求探索信息（包括故障節(jié)點ID信息等）并發(fā)送給所有周圍鄰居節(jié)點，以泛洪方式直到source節(jié)點。在泛洪的過程中，每到一個中間節(jié)點，便會檢測該節(jié)點的所有相連路徑是否含有故障節(jié)點，若有，則將此路徑刪除。當(dāng)請求探索信息到達source節(jié)點后，source節(jié)點便會立即發(fā)送探索信息，當(dāng)探索信息到達sink節(jié)點后，便選出了新的主路徑（圖4）。

圖4 FDFR路由協(xié)議故障節(jié)點的刪除和主路徑的建立Fig．4Removement of the fault node and establishment of the main path in FDFR

在FDFR路由協(xié)議中，2種檢測法同時作用在主路徑上的節(jié)點中。當(dāng)某節(jié)點由于能量消耗導(dǎo)致即將故障時，設(shè)定能量閾值的自身檢測法便能檢測出來，并立即執(zhí)行恢復(fù)的步驟。而當(dāng)安全攻擊或環(huán)境因素等導(dǎo)致節(jié)點故障時，自身檢測法便失效。此時，當(dāng)過了Tim時間后，后節(jié)點檢測法便能檢測出錯誤并執(zhí)行恢復(fù)過程?？梢?，自身檢測法比后節(jié)點檢測法略快，但是后節(jié)點檢測法能夠檢測的故障更多。

3 仿真實驗結(jié)果與分析

仿真實驗條件：傳感器節(jié)點均勻地分布在一個正方形的區(qū)域，故障節(jié)點分為兩類，一類可以通信，但不能轉(zhuǎn)發(fā)數(shù)據(jù)，使用自身檢測法；另一類既不能通信，也不能轉(zhuǎn)發(fā)數(shù)據(jù)，使用后節(jié)點檢測法。采用信息數(shù)據(jù)包的丟失率和故障恢復(fù)時間來評價仿真的效果。

（1）信息數(shù)據(jù)包丟失率（Lr）。

式（5）中，Lp表示丟失的信息數(shù)據(jù)包數(shù)量，Rp表示Sink節(jié)點接收到信息數(shù)據(jù)包數(shù)量。

圖5顯示了FDFR路由協(xié)議和DD路由協(xié)議在不同節(jié)點數(shù)量時信息數(shù)據(jù)包丟失率的對比?？芍?，相同節(jié)點數(shù)量FDFR路由協(xié)議的信息丟失率比DD路由協(xié)議的丟失率低。這是因為當(dāng)出現(xiàn)節(jié)點故障時，F(xiàn)DFR路由協(xié)議能夠快速恢復(fù)，選擇新的主路徑，并且將故障路徑從網(wǎng)絡(luò)中刪除，從而大大減少了信息數(shù)據(jù)包的丟失。

圖5 信息數(shù)據(jù)包的丟失率對比Fig．5Comparison of information packet loss

圖6 故障恢復(fù)時間對比Fig．6Comparison of fault recovery time

（2）故障恢復(fù)時間。

故障恢復(fù)時間即從故障發(fā)生到發(fā)現(xiàn)故障并重新選取主路徑的時間。圖6顯示了50個故障節(jié)點的故障恢復(fù)時間。其中，Tim＝30s，Ie＝100s。從圖中數(shù)據(jù)可算出，DD路由協(xié)議的平均恢復(fù)時間為57 s，而FDFR路由協(xié)議平均只需要22s。

4 結(jié)語

針對DD路由協(xié)議不能快速檢測節(jié)點錯誤的缺點，本文提出了能夠快速檢測節(jié)點故障并恢復(fù)主路徑的FDFR路由協(xié)議，介紹了根據(jù)設(shè)定能量閾值的自身檢測法和設(shè)定時間限制的后節(jié)點檢測法，根據(jù)導(dǎo)致故障的原因不同采取靈活的檢錯辦法。仿真結(jié)果表明，F(xiàn)DFR路由協(xié)議減少了故障恢復(fù)的時間和降低了信息數(shù)據(jù)包的丟失率。在今后的研究中，將考慮能量、內(nèi)存等因素對網(wǎng)絡(luò)容錯性能的影響，使FDFR路由協(xié)議適應(yīng)復(fù)雜多變的無線傳感器網(wǎng)絡(luò)。

［1］陳彥明，王秋光，徐勇軍．無線傳感器網(wǎng)絡(luò)容錯技術(shù)綜述［J］．計算機科學(xué)，2008，35（11）：87－90，175．

［2］曹冬磊，曹建農(nóng)，金蓓弘．一種無線傳感器網(wǎng)絡(luò)中事件區(qū)域監(jiān)測的容錯算法［J］．計算機學(xué)報，2007，30（10）：1770－1776．

［3］L Carvalho，J Angeja，A Navarro．A new packet loss model of the ieee 802．11g wireless network for multimedia communications［J］．In Consumer Electronics，IEEE Transactions，2005，51：809－814．

［4］Zabin F S．Misra S，Woungang I，et al．REEP：data－centric，energy－efficient and reliable routing protocol for wireless sensor networks［J］．Communications，IET，2008，2（8）：995－1008．

［5］Chalermek Intanagonwiwat，Ramesh Govindan，Deborah Estrin．Directed diffusion for Wireless Sensor Networking［J］．IEEE／ACM Transactions on Networking，2003，11（1）：2－16．

［6］Boukerche A，Chatzigiannakisb I，Nikoletseas S．A new energy efficient and fault－tolerant protocol for data propagation in smart dust networks using varying transmission range［J］．Science Direct，2006，29（20）：477－489．