高秀娥
(大連大學(xué) 信息工程學(xué)院, 遼寧 大連 116622)
無線傳感器網(wǎng)絡(luò)路由協(xié)議的容錯性研究
高秀娥
(大連大學(xué) 信息工程學(xué)院, 遼寧 大連 116622)
針對無線傳感器網(wǎng)絡(luò)能量有限、布置環(huán)境惡劣、通信能力有限等條件,具有容錯能力的路由協(xié)議已經(jīng)變成當(dāng)前的熱點問題,本文總結(jié)和分析了現(xiàn)有路由協(xié)議的容錯性,為進(jìn)一步的研究提供一定新的思路。
容錯性;無線傳感器網(wǎng)絡(luò);路由協(xié)議
隨著無線傳感器網(wǎng)絡(luò)的廣泛應(yīng)用,大量的路由協(xié)議成為研究的熱點。而傳感器網(wǎng)絡(luò)節(jié)點通常會存在能量消耗大,硬件損壞,惡意攻擊,通信失效等特點,這些勢必影響整個網(wǎng)絡(luò)的性能。移動自組織網(wǎng)絡(luò)或者有線網(wǎng)絡(luò)的協(xié)議并不能直接應(yīng)用到無線傳感器網(wǎng)絡(luò)中,對無線傳感器網(wǎng)絡(luò)容錯技術(shù)的研究,應(yīng)當(dāng)將無線通信網(wǎng)絡(luò)容錯技術(shù)和有線傳感器網(wǎng)絡(luò)容錯技術(shù)有機的結(jié)合起來。
容錯是保證網(wǎng)絡(luò)節(jié)點的軟、硬件出現(xiàn)故障時,能夠通過應(yīng)用一定的容錯技術(shù)使整個系統(tǒng)自動調(diào)整或者自動重構(gòu),糾正錯誤,保證任務(wù)的正常執(zhí)行,提高系統(tǒng)的可靠性和穩(wěn)定性。
無線傳感器網(wǎng)絡(luò)的許多路由協(xié)議在文獻(xiàn)[1,2]中進(jìn)行了相關(guān)的論述。本文的核心是針對現(xiàn)有的具有典型意義的路由協(xié)議進(jìn)行一定的容錯分析,為進(jìn)一步的容錯研究提供一定的新的思路。
容錯機制可以提高系統(tǒng)的可靠性,可用性和持續(xù)穩(wěn)定性。目前最常用的容錯方法是多路徑技術(shù),即在路由協(xié)議的算法實現(xiàn)中始終維護(hù)著源節(jié)點到目標(biāo)節(jié)點的多條路徑。因此當(dāng)一條路徑因為節(jié)點發(fā)生故障時,能夠迅速切換到另外一條路徑,從而具有一定的容錯性。這種容錯機制通常分為2種類型,即重復(fù)發(fā)送策略和復(fù)制策略。
重復(fù)發(fā)送是最受歡迎的一種策略,它能根據(jù)網(wǎng)絡(luò)需要,在一定時間前提下,利用最短的跳數(shù)和最小的能量消耗,選擇其中一條路徑,重復(fù)發(fā)送數(shù)據(jù)包到目標(biāo)節(jié)點。當(dāng)數(shù)據(jù)包成功接收之后,目標(biāo)節(jié)點發(fā)回一個確認(rèn)信息。當(dāng)源節(jié)點在一定時間內(nèi)沒有收到確認(rèn)信息,則數(shù)據(jù)包重新發(fā)送。但是,這種策略會消耗更多的能量,同時在傳送確認(rèn)信息時會提高傳輸延遲以及因為碰撞產(chǎn)生的包丟失現(xiàn)象。因此,源節(jié)點需要更大的內(nèi)存空間來處理這些過程。
基于這種策略的路由協(xié)議中,有DD(Directed Diffusion)協(xié)議[3],HREEMR(Highly Resilient,Energy Efficient Multipath Routing)協(xié)議[4],REAR(Reliable Energy Aware Routing)協(xié)議[5]。
3.1.1 DD協(xié)議
DD協(xié)議[3]中的最大特點就是利用加強機制。主路徑上的中間節(jié)點可以在主路徑出現(xiàn)故障后利用加強信號進(jì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é)點。如圖1(a)所示,當(dāng)sink節(jié)點發(fā)現(xiàn)此主路徑發(fā)生故障時,便會沿著主路徑發(fā)送否定加強信息,主路徑上的每個節(jié)點接收到否定加強信息后,便會將原來建立的加強的梯度消除。然而如圖1(b)所示,當(dāng)否定加強信息傳到故障節(jié)點時,由于該節(jié)點已經(jīng)發(fā)生故障,不能將此否定加強信息繼續(xù)傳播,因此,由于沒有把從source到故障節(jié)點的路徑刪除,source節(jié)點還會繼續(xù)向此路徑發(fā)送數(shù)據(jù)信息,導(dǎo)致大量信息數(shù)據(jù)的丟失和能量的浪費。
圖1 DD協(xié)議中移除故障節(jié)點
3.1.2 HREEMR協(xié)議
HREEMR協(xié)議[4]是在DD協(xié)議的基礎(chǔ)上進(jìn)行改進(jìn),避免了周期泛洪的成本,選取不相交的多條路徑,便于在故障出現(xiàn)能迅速切換到另外一條備份路徑上。協(xié)議的容錯性主要體現(xiàn)在在源節(jié)點和目標(biāo)節(jié)點之間建立多條路徑,其中的一條路徑作為主路徑傳遞數(shù)據(jù)包,而備選路徑只需要發(fā)送“Keep-alive”信號保證迅速切換路徑即可。
3.1.3 REAR協(xié)議
REAR協(xié)議[5]主要思想是這個協(xié)議提出一種能量保存策略。當(dāng)sink從source node收到an interest不在路由表里,sink建立兩條不相交的路徑到source,一條用來傳數(shù)據(jù),一條備用,兩條路徑的選取方法根據(jù)prbd的值,prbd是REAR中一個重要量,表示path-request broadcasting delay(prbd),當(dāng)中間節(jié)點收到路徑請求的時候,它并不立刻廣播信息到他鄰居節(jié)點,首先檢查它的有效能量,看看夠不夠operation energy(比方定一個數(shù)量級是轉(zhuǎn)發(fā)能量的2倍),如果不夠,就放棄接受請求應(yīng)答。如圖2,有兩個中間節(jié)點,a和b都收到路徑請求,但是不同的路由策略建立的結(jié)果不同。
圖2 REAR中路徑的建立
圖2表示了其他路由協(xié)議和REAR協(xié)議的區(qū)別。假設(shè)節(jié)點IN_b是到S_1和S_2的時間最短路徑,按照傳統(tǒng)的選擇最短路徑的方法,都選擇IN_b作為中間節(jié)點來傳輸,但是中間節(jié)點因為能量有限,很快會消耗完,導(dǎo)致故障出現(xiàn),而在REAR中IN_b是唯一連接s2的節(jié)點,則sink-b-s2建立,因為中間節(jié)點b的能量被預(yù)留,所以在判斷節(jié)點的有效能量的時候就把節(jié)點b排除,進(jìn)而選擇a節(jié)點作為到S_1的中間節(jié)點。這樣大大提高網(wǎng)絡(luò)的使用壽命,提高網(wǎng)絡(luò)的生命周期。
基于復(fù)制策略的路由協(xié)議已經(jīng)有大量的文獻(xiàn)進(jìn)行研究。它的主要思想是在多條路徑上將同一個包發(fā)送多遍,以提高網(wǎng)絡(luò)的可靠性。具有代表性的協(xié)議是Reliable Information Forwarding (ReInForm)[4],它的主要主要思想是:
①源節(jié)點根據(jù)傳輸數(shù)據(jù)的可靠性需求計算需要的傳輸路徑數(shù)目;
②在鄰居節(jié)點中選擇一些節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點,并根據(jù)比例給每個選取的節(jié)點分配路徑數(shù)目;
③源節(jié)點將分配的路徑數(shù)作為數(shù)據(jù)報文中的一個字段發(fā)給鄰居節(jié)點;
④收到源節(jié)點發(fā)來數(shù)據(jù)的每個鄰居節(jié)點,將自己當(dāng)做源節(jié)點,重復(fù)前面的源節(jié)點選路過程。
ReInForm的容錯性是在隨機選擇的路徑上,發(fā)送同一個包的多份拷貝到Sink節(jié)點。這種復(fù)制策略不僅僅是對源節(jié)點而言,中間的節(jié)點都采用這種策略,這樣在網(wǎng)絡(luò)中,即使原始的數(shù)據(jù)包丟失,后來的數(shù)據(jù)包也會傳輸?shù)絊ink節(jié)點,達(dá)到很高的傳輸率。但是,這種策略為了達(dá)到很高的可靠性,在數(shù)據(jù)包拆分、傳送和重構(gòu)過程中,會消耗很大的能量,所以在網(wǎng)絡(luò)的可靠性和費用方面需要找到一個平衡點。
本文選取的幾種協(xié)議都是無線傳感器路由協(xié)議中比較有典型意義的協(xié)議,并對它們進(jìn)行了容錯性分析,容錯策略主要分為兩類,即復(fù)制和重復(fù)發(fā)送策略。在以后的工作中,需要進(jìn)行的研究應(yīng)該包括(1)如何去權(quán)衡容錯、能量消耗和內(nèi)存使用以及延遲等多因素。(2)現(xiàn)有的路由協(xié)議多數(shù)是針對靜止的傳感器節(jié)點,而對移動節(jié)點沒有給予考慮。
[1] KARAKIJN Al, KAMALA E. Routing techniques in wireless sensor networks: A survey [J]. IEEE Wireless Communications, 2004, 11(6): 6-28.
[2] AKKAYA K, YOUNIS M. A survey on routing protocols for wireless Sensor network [J]. Elsevier Ad Hoc Network Journal, 2005, 3(3): 325-349.
[3] INTANAGONWIWAT C, GOVINDAN R, ESTRIN D. Directed diffusion: A scalable and robust communication paradigm for sensor networks [M]. AC MIntl. Conf. on Mobile Computing and Networking, 2000: 56-67.
[4] GANESAN D, GOVINDAN R, SHENKER S, et al. Highly resilient, energy-efficient multipath routing in wireless sensor networks [M]. ACM MobiHoc’01, CA, Long Beach, USA, 2001.
[5] HASSANEIN H, LUO J. Reliable energy aware routing in wireless sensor networks [J]. Second IEEE Workshop on Dependability and Security in Sensor Networks and Systems, 2006.
Research on Fault-Tolerant Routing Protocol for Wireless Sensor Networks
GAO Xiu-e
(College of Information Engineering, Dalian University, Dalian 116622, China)
For the reason of the limited energy of wireless sensor network, the bad environment, and the limited conditions of communication ability, the routing protocol with the fault tolerance has become the hot issue.This paper summarizes and analyzes the fault tolerance of the existed routing protocol to provide some new ideas for further study.
fault tolerance; wireless sensor networks; routing protocol
TP393
A
1008-2395(2012)03-0021-03
2012-03-09
高秀娥(1976-),女,博士研究生,講師,研究方向:無線傳感器網(wǎng)絡(luò),網(wǎng)絡(luò)管理與監(jiān)控。