高秀娥

（大連大學(xué) 信息工程學(xué)院, 遼寧 大連 116622）

無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議的容錯(cuò)性研究

高秀娥

（大連大學(xué) 信息工程學(xué)院, 遼寧 大連 116622）

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)能量有限、布置環(huán)境惡劣、通信能力有限等條件，具有容錯(cuò)能力的路由協(xié)議已經(jīng)變成當(dāng)前的熱點(diǎn)問(wèn)題，本文總結(jié)和分析了現(xiàn)有路由協(xié)議的容錯(cuò)性，為進(jìn)一步的研究提供一定新的思路。

容錯(cuò)性；無(wú)線傳感器網(wǎng)絡(luò)；路由協(xié)議

1 引言

隨著無(wú)線傳感器網(wǎng)絡(luò)的廣泛應(yīng)用，大量的路由協(xié)議成為研究的熱點(diǎn)。而傳感器網(wǎng)絡(luò)節(jié)點(diǎn)通常會(huì)存在能量消耗大，硬件損壞，惡意攻擊，通信失效等特點(diǎn)，這些勢(shì)必影響整個(gè)網(wǎng)絡(luò)的性能。移動(dòng)自組織網(wǎng)絡(luò)或者有線網(wǎng)絡(luò)的協(xié)議并不能直接應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)中，對(duì)無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)技術(shù)的研究，應(yīng)當(dāng)將無(wú)線通信網(wǎng)絡(luò)容錯(cuò)技術(shù)和有線傳感器網(wǎng)絡(luò)容錯(cuò)技術(shù)有機(jī)的結(jié)合起來(lái)。

容錯(cuò)是保證網(wǎng)絡(luò)節(jié)點(diǎn)的軟、硬件出現(xiàn)故障時(shí)，能夠通過(guò)應(yīng)用一定的容錯(cuò)技術(shù)使整個(gè)系統(tǒng)自動(dòng)調(diào)整或者自動(dòng)重構(gòu)，糾正錯(cuò)誤，保證任務(wù)的正常執(zhí)行，提高系統(tǒng)的可靠性和穩(wěn)定性。

無(wú)線傳感器網(wǎng)絡(luò)的許多路由協(xié)議在文獻(xiàn)[1,2]中進(jìn)行了相關(guān)的論述。本文的核心是針對(duì)現(xiàn)有的具有典型意義的路由協(xié)議進(jìn)行一定的容錯(cuò)分析，為進(jìn)一步的容錯(cuò)研究提供一定的新的思路。

2 路由協(xié)議中的容錯(cuò)機(jī)制

容錯(cuò)機(jī)制可以提高系統(tǒng)的可靠性，可用性和持續(xù)穩(wěn)定性。目前最常用的容錯(cuò)方法是多路徑技術(shù)，即在路由協(xié)議的算法實(shí)現(xiàn)中始終維護(hù)著源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的多條路徑。因此當(dāng)一條路徑因?yàn)楣?jié)點(diǎn)發(fā)生故障時(shí)，能夠迅速切換到另外一條路徑，從而具有一定的容錯(cuò)性。這種容錯(cuò)機(jī)制通常分為2種類型，即重復(fù)發(fā)送策略和復(fù)制策略。

3 現(xiàn)有路由協(xié)議容錯(cuò)性分析

3.1 重復(fù)發(fā)送策略

重復(fù)發(fā)送是最受歡迎的一種策略，它能根據(jù)網(wǎng)絡(luò)需要，在一定時(shí)間前提下，利用最短的跳數(shù)和最小的能量消耗，選擇其中一條路徑，重復(fù)發(fā)送數(shù)據(jù)包到目標(biāo)節(jié)點(diǎn)。當(dāng)數(shù)據(jù)包成功接收之后，目標(biāo)節(jié)點(diǎn)發(fā)回一個(gè)確認(rèn)信息。當(dāng)源節(jié)點(diǎn)在一定時(shí)間內(nèi)沒(méi)有收到確認(rèn)信息，則數(shù)據(jù)包重新發(fā)送。但是，這種策略會(huì)消耗更多的能量，同時(shí)在傳送確認(rèn)信息時(shí)會(huì)提高傳輸延遲以及因?yàn)榕鲎伯a(chǎn)生的包丟失現(xiàn)象。因此，源節(jié)點(diǎn)需要更大的內(nèi)存空間來(lái)處理這些過(guò)程。

基于這種策略的路由協(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]中的最大特點(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)周圍節(jié)點(diǎn)的信息傳輸速率突然增加，即此路徑發(fā)生故障，然后此節(jié)點(diǎn)便會(huì)發(fā)送否定加強(qiáng)信號(hào)直到source節(jié)點(diǎn)。如圖1(a)所示，當(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(b)所示，當(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)。

圖1 DD協(xié)議中移除故障節(jié)點(diǎn)

3.1.2 HREEMR協(xié)議

HREEMR協(xié)議[4]是在DD協(xié)議的基礎(chǔ)上進(jìn)行改進(jìn)，避免了周期泛洪的成本，選取不相交的多條路徑，便于在故障出現(xiàn)能迅速切換到另外一條備份路徑上。協(xié)議的容錯(cuò)性主要體現(xiàn)在在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間建立多條路徑，其中的一條路徑作為主路徑傳遞數(shù)據(jù)包，而備選路徑只需要發(fā)送“Keep-alive”信號(hào)保證迅速切換路徑即可。

3.1.3 REAR協(xié)議

REAR協(xié)議[5]主要思想是這個(gè)協(xié)議提出一種能量保存策略。當(dāng)sink從source node收到an interest不在路由表里，sink建立兩條不相交的路徑到source，一條用來(lái)傳數(shù)據(jù)，一條備用，兩條路徑的選取方法根據(jù)prbd的值，prbd是REAR中一個(gè)重要量，表示path-request broadcasting delay（prbd），當(dāng)中間節(jié)點(diǎn)收到路徑請(qǐng)求的時(shí)候，它并不立刻廣播信息到他鄰居節(jié)點(diǎn)，首先檢查它的有效能量，看看夠不夠operation energy（比方定一個(gè)數(shù)量級(jí)是轉(zhuǎn)發(fā)能量的2倍），如果不夠，就放棄接受請(qǐng)求應(yīng)答。如圖2，有兩個(gè)中間節(jié)點(diǎn)，a和b都收到路徑請(qǐng)求，但是不同的路由策略建立的結(jié)果不同。

圖2 REAR中路徑的建立

圖2表示了其他路由協(xié)議和REAR協(xié)議的區(qū)別。假設(shè)節(jié)點(diǎn)IN_b是到S_1和S_2的時(shí)間最短路徑,按照傳統(tǒng)的選擇最短路徑的方法，都選擇IN_b作為中間節(jié)點(diǎn)來(lái)傳輸，但是中間節(jié)點(diǎn)因?yàn)槟芰坑邢?，很快?huì)消耗完，導(dǎo)致故障出現(xiàn)，而在REAR中IN_b是唯一連接s2的節(jié)點(diǎn)，則sink-b-s2建立，因?yàn)橹虚g節(jié)點(diǎn)b的能量被預(yù)留，所以在判斷節(jié)點(diǎn)的有效能量的時(shí)候就把節(jié)點(diǎn)b排除，進(jìn)而選擇a節(jié)點(diǎn)作為到S_1的中間節(jié)點(diǎn)。這樣大大提高網(wǎng)絡(luò)的使用壽命，提高網(wǎng)絡(luò)的生命周期。

3.2 復(fù)制策略

基于復(fù)制策略的路由協(xié)議已經(jīng)有大量的文獻(xiàn)進(jìn)行研究。它的主要思想是在多條路徑上將同一個(gè)包發(fā)送多遍，以提高網(wǎng)絡(luò)的可靠性。具有代表性的協(xié)議是Reliable Information Forwarding (ReInForm)[4]，它的主要主要思想是：

①源節(jié)點(diǎn)根據(jù)傳輸數(shù)據(jù)的可靠性需求計(jì)算需要的傳輸路徑數(shù)目；

②在鄰居節(jié)點(diǎn)中選擇一些節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，并根據(jù)比例給每個(gè)選取的節(jié)點(diǎn)分配路徑數(shù)目；

③源節(jié)點(diǎn)將分配的路徑數(shù)作為數(shù)據(jù)報(bào)文中的一個(gè)字段發(fā)給鄰居節(jié)點(diǎn)；

④收到源節(jié)點(diǎn)發(fā)來(lái)數(shù)據(jù)的每個(gè)鄰居節(jié)點(diǎn)，將自己當(dāng)做源節(jié)點(diǎn)，重復(fù)前面的源節(jié)點(diǎn)選路過(guò)程。

ReInForm的容錯(cuò)性是在隨機(jī)選擇的路徑上，發(fā)送同一個(gè)包的多份拷貝到Sink節(jié)點(diǎn)。這種復(fù)制策略不僅僅是對(duì)源節(jié)點(diǎn)而言，中間的節(jié)點(diǎn)都采用這種策略，這樣在網(wǎng)絡(luò)中，即使原始的數(shù)據(jù)包丟失，后來(lái)的數(shù)據(jù)包也會(huì)傳輸?shù)絊ink節(jié)點(diǎn)，達(dá)到很高的傳輸率。但是，這種策略為了達(dá)到很高的可靠性，在數(shù)據(jù)包拆分、傳送和重構(gòu)過(guò)程中，會(huì)消耗很大的能量,所以在網(wǎng)絡(luò)的可靠性和費(fèi)用方面需要找到一個(gè)平衡點(diǎn)。

4 討論與總結(jié)

本文選取的幾種協(xié)議都是無(wú)線傳感器路由協(xié)議中比較有典型意義的協(xié)議，并對(duì)它們進(jìn)行了容錯(cuò)性分析，容錯(cuò)策略主要分為兩類，即復(fù)制和重復(fù)發(fā)送策略。在以后的工作中，需要進(jìn)行的研究應(yīng)該包括（1）如何去權(quán)衡容錯(cuò)、能量消耗和內(nèi)存使用以及延遲等多因素。（2）現(xiàn)有的路由協(xié)議多數(shù)是針對(duì)靜止的傳感器節(jié)點(diǎn)，而對(duì)移動(dòng)節(jié)點(diǎn)沒(méi)有給予考慮。

[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ú)線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)管理與監(jiān)控。