郭海生,王德政,熊 瑋,王大勇

(中興通訊股份有限公司南京研發(fā)中心網(wǎng)管產(chǎn)品部,南京210012)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[1]是由一定數(shù)量的傳感器節(jié)點(diǎn)通過某種無(wú)線通信協(xié)議聯(lián)結(jié)而成的測(cè)控系統(tǒng),其作用是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息,并發(fā)送給觀察者。無(wú)線傳感器網(wǎng)絡(luò)由于其潛在的實(shí)時(shí)應(yīng)用獲得了許多關(guān)注,應(yīng)用范圍也隨之?dāng)U大,應(yīng)用場(chǎng)景也擴(kuò)展到許多惡劣的環(huán)境。

但由于硬件條件和供能限制,使得一個(gè)節(jié)點(diǎn)很容易發(fā)生故障,因此無(wú)線傳感器網(wǎng)絡(luò)工作在非常惡劣的環(huán)境下可能很容易受到破壞。在一塊很重要的覆蓋區(qū)域,整個(gè)網(wǎng)絡(luò)被分成了若干個(gè)區(qū)域,如圖1所示,由于重大破壞,該網(wǎng)絡(luò)被分成了7個(gè)區(qū)域,每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)能夠正常通信,但是區(qū)域之間不連通。孤立的區(qū)域之間彼此不能正常通信,將嚴(yán)重影響網(wǎng)絡(luò)的整體性能。所以重建區(qū)域之間的連通對(duì)于恢復(fù)網(wǎng)絡(luò)通信有著至關(guān)重要的作用。

目前關(guān)于故障恢復(fù)的研究都是著重在單個(gè)節(jié)點(diǎn)的恢復(fù)策略上。例如在簇形結(jié)構(gòu)下恢復(fù)的節(jié)點(diǎn)故障[2],以及引入了secondary cell作為cell manager[3]的備用節(jié)點(diǎn),對(duì)于每個(gè)節(jié)點(diǎn)都享有平等的權(quán)利,克服了簇結(jié)構(gòu)中簇頭節(jié)點(diǎn)周圍節(jié)點(diǎn)容易衰竭的缺陷。但這類方法都不能解決多個(gè)節(jié)點(diǎn)同時(shí)發(fā)生故障的情況,因?yàn)檫@些方法都需要依賴故障節(jié)點(diǎn)的鄰居節(jié)點(diǎn),這類節(jié)點(diǎn)在大型災(zāi)難中也有可能發(fā)生故障。為了解決這類故障,有研究網(wǎng)絡(luò)被分塊的情況[4-5],但是僅僅考慮了單個(gè)節(jié)點(diǎn)造成的區(qū)域之間不能正常通信的情況。DORMS算法[6]能夠解決多個(gè)節(jié)點(diǎn)同時(shí)發(fā)生故障造成網(wǎng)絡(luò)分塊的情況,但是該算法需要將每個(gè)分塊區(qū)域的所屬轉(zhuǎn)置節(jié)點(diǎn)[4]移動(dòng)到網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域的中心,對(duì)于位于網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域邊緣的分塊區(qū)域而言,需要移動(dòng)較長(zhǎng)的距離和消耗節(jié)點(diǎn)較多的能量。這樣造成恢復(fù)過程時(shí)間過長(zhǎng),對(duì)無(wú)線傳感器網(wǎng)絡(luò)的及時(shí)通信造成很大的影響。

圖1 被分塊的無(wú)線傳感器網(wǎng)絡(luò)

本文提出的方法針對(duì)DORMS算法的缺陷進(jìn)行了改進(jìn),通過將分塊的區(qū)域移動(dòng)到固定的最近同心圓上,然后進(jìn)行恢復(fù)各個(gè)分塊區(qū)域的連通工作。由于每個(gè)分塊區(qū)域不需要都往監(jiān)測(cè)中心區(qū)域移動(dòng),減少轉(zhuǎn)置節(jié)點(diǎn)的移動(dòng)距離和節(jié)省了節(jié)點(diǎn)的能量,也極大地減少了恢復(fù)過程的時(shí)間。

1 故障恢復(fù)算法

基于被分塊的無(wú)線傳感器網(wǎng)絡(luò)的故障恢復(fù)算法(recovery from fragmented wireless sensor networks,RF),其主要思想是將分塊區(qū)域(Segments)的轉(zhuǎn)置節(jié)點(diǎn)移動(dòng)到最近的同心圓進(jìn)行連通工作,從而達(dá)到恢復(fù)網(wǎng)絡(luò)連通性的目的。

1.1 基本原理及特征

對(duì)于較大規(guī)模的 WSN,基于如下假設(shè):每個(gè)分塊區(qū)域的周圍都布置好轉(zhuǎn)置節(jié)點(diǎn)(relay node,RN);RN的能量是充足的、不受限制的,而普通傳感器節(jié)點(diǎn)的能量有限,計(jì)算和存儲(chǔ)能力也有限,并假設(shè)它們的初始能量基本相同。每個(gè)轉(zhuǎn)置節(jié)點(diǎn)都可以移動(dòng)。

RF的原理是先將整個(gè)網(wǎng)絡(luò)分為固定的同心圓集,每個(gè)分塊區(qū)域?qū)⒆约旱霓D(zhuǎn)置節(jié)點(diǎn)代表移動(dòng)到離自己最近的同心圓,然后在每個(gè)同心圓進(jìn)行連通工作,由于每個(gè)同心圓都是根據(jù)網(wǎng)絡(luò)的實(shí)際情況劃分,每次恢復(fù)過程中每個(gè)同心圓的個(gè)數(shù)不固定,彼此都不知道對(duì)方所在,所以同心圓集內(nèi)的每個(gè)元素還需要進(jìn)行連通。這樣整個(gè)網(wǎng)絡(luò)的分塊區(qū)域就通過這些同心圓重新恢復(fù)了連通性。

RF的主要特性是為了減少轉(zhuǎn)置節(jié)點(diǎn)的移動(dòng)距離,引入了同心圓的概念,每個(gè)分塊區(qū)域都只需移動(dòng)到最近的同心圓上。

1.2 RF算法

RF算法采取的最近同心圓處理分塊區(qū)域方法不同于DORMS算法的中心區(qū)域處理方法,能夠用較少的轉(zhuǎn)置節(jié)點(diǎn)恢復(fù)網(wǎng)絡(luò)分塊區(qū)域的連通性,將恢復(fù)過程分為劃分固定的同心圓、分塊區(qū)域派遣轉(zhuǎn)置節(jié)點(diǎn)到最近同心圓、同心圓內(nèi)的連通、同心圓之間的連通等4個(gè)步驟。

1.2.1 劃分固定的同心圓

假定網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域的整個(gè)網(wǎng)絡(luò)區(qū)域的中心坐標(biāo)(x0,y0)和最遠(yuǎn)分塊區(qū)域的邊緣轉(zhuǎn)置節(jié)點(diǎn)坐標(biāo)(x1,y2)都可以通過sin k節(jié)點(diǎn)獲得,轉(zhuǎn)置節(jié)點(diǎn)的通信半徑為R。規(guī)定C為同心圓集合:{ci|i≥0},每個(gè)元素也是一個(gè)集合:{i,r|序號(hào),半徑值},最遠(yuǎn)邊緣區(qū)域到區(qū)域中心的距離為d。劃分過程步驟如下:

(1)計(jì)算d的值:

(2)將d每次減少2R,作為新的同心圓的半徑:d←d-2R;

(3)將新確定的同心圓加入到C中,并且i自動(dòng)增加1;

(4)判斷d是否小于2R:如果不是,就回到步驟(2),繼續(xù)劃分;如果是,就結(jié)束劃分過程。

1.2.2 分塊區(qū)域派遣轉(zhuǎn)置節(jié)點(diǎn)到最近同心圓

每個(gè)轉(zhuǎn)置節(jié)點(diǎn)將自己標(biāo)記為RNid,i為分塊區(qū)域(segments)的序號(hào),d為Pi(轉(zhuǎn)置節(jié)點(diǎn)移動(dòng)到最近同心圓的路徑)上的排列信息。例如,第一個(gè)分塊區(qū)域的轉(zhuǎn)置節(jié)點(diǎn)代表就將自己標(biāo)記為RN10。每個(gè)區(qū)域的轉(zhuǎn)置節(jié)點(diǎn)代表事先計(jì)算自己到哪個(gè)同心圓最近,判斷結(jié)束就開始級(jí)聯(lián)移動(dòng)[6](cascaded movement)。

具體過程:在RNi0移動(dòng)前,RNi0發(fā)一個(gè)開始移動(dòng)的信息(START_MOVE)給它所在區(qū)域中最近的鄰居轉(zhuǎn)置節(jié)點(diǎn),這個(gè)信息包括自己的排列信息,即d的值。從RNi0收到START_MOVE信息的轉(zhuǎn)置節(jié)點(diǎn)將序列值(即d)的值增加1并且把自己標(biāo)記為RNi1,同時(shí)RNi1開始向RNi0移動(dòng)的方向移動(dòng)。在RNi1開始移動(dòng)前,也會(huì)識(shí)別自己最近的鄰居節(jié)點(diǎn),然后重復(fù)RNi0的過程。在RNi0到達(dá)目的地之前,不斷重復(fù)這個(gè)過程。

在Pi上,相鄰轉(zhuǎn)置節(jié)點(diǎn)之間相隔距離長(zhǎng)度為R,所以轉(zhuǎn)置節(jié)點(diǎn)可以達(dá)到的最大數(shù)目:NPi,見式(2)。

同時(shí)可以推導(dǎo)出,序列信息值 d的最大值為NPi-1,整個(gè)網(wǎng)絡(luò)中 NPi的總個(gè)數(shù)NNPi,見式(3)

公式推導(dǎo)說(shuō)明:

公式2:Pi上相鄰轉(zhuǎn)置節(jié)點(diǎn)之間相隔的距離為R,轉(zhuǎn)置節(jié)點(diǎn)的總個(gè)數(shù)為路徑Pi長(zhǎng)度除以節(jié)點(diǎn)的相隔距離R得到的值取上限。

公式3:每個(gè)孤立區(qū)域都有一條到達(dá)中心點(diǎn)的路徑Pi,但是并不是每個(gè)區(qū)域派出的轉(zhuǎn)置節(jié)點(diǎn)都會(huì)到達(dá)中心節(jié)點(diǎn),我們規(guī)定最先到達(dá)的轉(zhuǎn)置節(jié)點(diǎn)作為中心節(jié)點(diǎn),負(fù)責(zé)與其他RNi0的連通工作。因此整個(gè)網(wǎng)絡(luò)布置在路徑上的轉(zhuǎn)置節(jié)點(diǎn)總個(gè)數(shù)是小于等于所有區(qū)域路徑上所需要的轉(zhuǎn)置節(jié)點(diǎn)的總和。

圖2給出了該過程的示例,為簡(jiǎn)化問題,序號(hào)為0的分塊區(qū)域由自己的轉(zhuǎn)置節(jié)點(diǎn)代表表示。

圖2 標(biāo)號(hào)為O的分塊區(qū)域派遣轉(zhuǎn)置節(jié)點(diǎn)代表移動(dòng)到同心圓

1.2.3 同心圓內(nèi)的連通

當(dāng)每個(gè)分塊區(qū)域的轉(zhuǎn)置節(jié)點(diǎn)代表移動(dòng)到同心圓上,彼此間不知道對(duì)方存在,需要進(jìn)行連通工作,才能保證各個(gè)區(qū)域的連通。

規(guī)定從中心軸半徑開始每隔R的位置放非移動(dòng)節(jié)點(diǎn),如果遇到轉(zhuǎn)置節(jié)點(diǎn)就跳過該位置,繼續(xù)布置。非移動(dòng)節(jié)點(diǎn)布置完后,圓上的每個(gè)轉(zhuǎn)置節(jié)點(diǎn)就發(fā)一個(gè)消息給鄰居的非移動(dòng)節(jié)點(diǎn),報(bào)告自己的所在位置,非移動(dòng)節(jié)點(diǎn)收到消息后就發(fā)回一個(gè)確定消息。這樣,每個(gè)同心圓的轉(zhuǎn)置節(jié)點(diǎn)都能夠正常通信。

1.2.4 同心圓之間的連通

每個(gè)同心圓都是獨(dú)立存在的,沒有與其他同心圓進(jìn)行聯(lián)系,導(dǎo)致互相之間不能正常通信。所以,為了保證同心圓之間能夠連通,我們規(guī)定在每個(gè)同心圓上能夠記錄最晚到達(dá)該同心圓的轉(zhuǎn)置節(jié)點(diǎn),由該轉(zhuǎn)置節(jié)點(diǎn)啟動(dòng)到相鄰?fù)膱A的連通工作。

為了減少轉(zhuǎn)置節(jié)點(diǎn)個(gè)數(shù),我們利用Pi路徑上的節(jié)點(diǎn),規(guī)定該路徑上d值最大的節(jié)點(diǎn)RNid的最近鄰居節(jié)點(diǎn)向與RNid反方向移動(dòng),再次啟動(dòng)級(jí)聯(lián)移動(dòng)過程。如圖2所示,則由RN03的最近鄰居節(jié)點(diǎn)向Ci移動(dòng)。

2 RF算法性能分析

由于無(wú)線傳感器網(wǎng)絡(luò)的特性,故障恢復(fù)算法需要盡可能節(jié)省成本和能量。在RF算法中,轉(zhuǎn)置節(jié)點(diǎn)的個(gè)數(shù)和移動(dòng)的總距離是需要考慮的主要因素。RF算法引入同心圓的概念,極大地減少了轉(zhuǎn)置節(jié)點(diǎn)的個(gè)數(shù)和移動(dòng)距離,同時(shí)在移動(dòng)過程中采取級(jí)聯(lián)移動(dòng)算法也避免了大規(guī)模的移動(dòng)節(jié)點(diǎn),節(jié)省了時(shí)間和能量,延長(zhǎng)了網(wǎng)絡(luò)的整體壽命。

為了驗(yàn)證該算法,通過Matlab進(jìn)行仿真,對(duì)比RF算法和DORMS算法的轉(zhuǎn)置節(jié)點(diǎn)個(gè)數(shù)和移動(dòng)總距離。建立仿真模型如下:

在1 000 m×1 000 m的區(qū)域內(nèi),隨機(jī)分布N個(gè)轉(zhuǎn)置節(jié)點(diǎn)(每個(gè)轉(zhuǎn)置節(jié)點(diǎn)代表一個(gè)分塊區(qū)域),每個(gè)轉(zhuǎn)置節(jié)點(diǎn)的通信半徑為40。運(yùn)行仿真程序,進(jìn)行了200余次實(shí)驗(yàn),得到如圖3和圖4的數(shù)據(jù)。仿真結(jié)果顯示RF的移動(dòng)距離要遠(yuǎn)比DORMS算法少,而轉(zhuǎn)置節(jié)點(diǎn)個(gè)數(shù)相差不大。

圖3 RF與DORMS移動(dòng)總距離比較

圖4 RF與DORMS所需轉(zhuǎn)置節(jié)點(diǎn)比較

3 結(jié)語(yǔ)

本文介紹了一種解決無(wú)線傳感器網(wǎng)絡(luò)被分塊的故障恢復(fù)方法,該方法不同于DORMS算法將分塊的區(qū)域的轉(zhuǎn)置代表節(jié)點(diǎn)移動(dòng)到網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域中心進(jìn)行連通,而是將整個(gè)網(wǎng)絡(luò)區(qū)域劃分成若干個(gè)同心圓,每個(gè)區(qū)域的轉(zhuǎn)置節(jié)點(diǎn)都只需移動(dòng)較少的距離到最近的同心圓,極大地減少了節(jié)點(diǎn)的移動(dòng)距離,縮短了恢復(fù)過程的時(shí)間,延長(zhǎng)了網(wǎng)絡(luò)的壽命。

[1]Paradis,Han L,Q.A survey of fault management in wireless sensor networks[J].Journal of Network and Systems Management,2007,15(2):171-190.

[2]Venkataraman,G,Emnianuel S,etc.A cluster-based approach to fault detection and recovery in wireless sensor networks[A].Ramjee Prasad.2007 Fourth International Symposium on Wireless Communication Systems[C],Belin:Springer-Verlag,2007,1:782-786.

[3]Asim,M,Mokhtar H,etc.A cellular approach to fault detection and recovery in wireless sensor networks[A].Hovem J H.2009 3rd International Conference on Sensor Technologies and Applications(Sensorcomm 2009)[C].USA:IEEE.,2009:352-357.

[4]Abbasi,A A,Akkaya K,etc.A Distributed Connectivity Restoration Algorithm in Wireless Sensor and Actor Networks[A].32nd IEEE Conference on in Local Computer Networks,2007.LCN[C].OSA:IEEE.,2007:233-241.

[5]Akkaya,K.Distributed Recovery of Actor Failures in Wireless Sensor and Actor Networks[A].Hovem J M.Wireless Communications,2008.WCNC 2008[C].USA:IEEE.,2008:415-422.

[6]Lee,S,Younis M.Recovery from multiple simultaneous failures in wireless sensornetworks usingminimum Steiner tree[J].Journal of Parallel and Distributed Computing,2010,70(5):525-536.