基于快速檢測(cè)和恢復(fù)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議研究

高秀娥，萬(wàn)兵，劉長(zhǎng)征

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

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

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

目前，在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議中，有關(guān)對(duì)故障路徑進(jìn)行快速檢測(cè)和恢復(fù)的協(xié)議方面的報(bào)道很少?；诖耍疚奶岢隽酥髀窂焦?jié)點(diǎn)故障快速檢測(cè)和恢復(fù)（FDFR）的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議，該協(xié)議針對(duì)節(jié)點(diǎn)的具體故障原因進(jìn)行快速檢測(cè)并恢復(fù)主路徑，能將故障節(jié)點(diǎn)及其相關(guān)路徑從網(wǎng)絡(luò)中完全移除，旨在避免能量的浪費(fèi)和數(shù)據(jù)信息的丟失。

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

1．1 DD路由協(xié)議容錯(cuò)的優(yōu)點(diǎn)

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

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

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

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

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

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

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

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

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

2．1 自身檢測(cè)法

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

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

2．2 后節(jié)點(diǎn)檢測(cè)法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

［2］曹冬磊，曹建農(nóng)，金蓓弘．一種無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中事件區(qū)域監(jiān)測(cè)的容錯(cuò)算法［J］．計(jì)算機(jī)學(xué)報(bào)，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．