高景菊,張文娟,譚永杰

(周口師范學院計算機科學與技術(shù)學院,河南周口466001)

在無線傳感器網(wǎng)絡(luò)中,路由協(xié)議的設(shè)計對網(wǎng)絡(luò)通信的能量消耗有著重要影響。當前,對無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究從網(wǎng)絡(luò)拓撲結(jié)構(gòu)上講主要分為兩個方面:平面路由協(xié)議和分簇路由協(xié)議[1,2]。在平面路由協(xié)議中,各個節(jié)點之間沒有等級結(jié)構(gòu),平等的節(jié)點之間通過平面路由算法形成路由機制。典型的平面路由協(xié)議有Flooding協(xié)議及Gossiping協(xié)議[3],DD(Driected Diffusion)協(xié)議[4,5],Runor協(xié)議[6],SPIN(sensor protocol for information via negotiation)協(xié)議[7],SMECN(small minimum energy communication network)協(xié)議[8],GEM(graph embedding)協(xié)議[9],GEAR(geographical and energy aware routing)路由協(xié)議[10]。平面路由協(xié)議具有簡單、健壯性好、不需要維護拓撲結(jié)構(gòu)的優(yōu)點。分簇路由機制中節(jié)點分為簇頭節(jié)點和普通節(jié)點。由于分簇路由機制中具有便于管理,數(shù)據(jù)融合等優(yōu)點,成為當前無線傳感器網(wǎng)絡(luò)中的研究熱點。典型的分簇路由協(xié)議有LEACH(Low Energy Adaptive Clustering Hierarchy)[11],GAF(geographical adaptive fidelity)算法[12],最小ID算法(LID)[13],等。

本文在典型的平面路由協(xié)議DD的基礎(chǔ)上,結(jié)合分簇機制,提出一種基于分簇的DD協(xié)議(CDD),并根據(jù)不同的應(yīng)用,詳細說明其工作原理,并仿真證明其有效性。

1 研究現(xiàn)狀

無線傳感器定向擴散路由協(xié)議(Driected Dif-fusion)[4,5]是一種典型的以數(shù)據(jù)為中心的框架性路由協(xié)議。為了在相應(yīng)區(qū)域內(nèi)查找匯聚節(jié)點(sink節(jié)點)感興趣的事件,首先由匯聚節(jié)點發(fā)出查詢消息,此消息即是匯聚節(jié)點感興趣的事件的一串屬性值。該消息由匯聚節(jié)點發(fā)出,通過洪泛方式傳播給傳感器節(jié)點。當傳感器節(jié)點收到這個消息時,先查看自己的存儲器里有沒有相應(yīng)的屬性值。如果沒有,則加入;如有,則更新。在消息洪泛的過程中,節(jié)點記錄梯度信息(即自己接收到的消息是從哪個節(jié)點傳播過來的),當消息傳播結(jié)束后,傳感器節(jié)點沿傳播興趣消息的反方向(根據(jù)梯度信息)進行數(shù)據(jù)傳輸。為了選擇最優(yōu)路徑進行較快的數(shù)據(jù)收集,在DD中,采用路徑加強的方式,即選擇適當?shù)姆绞郊訌娛占⒌哪承┞窂?部分路徑失效),從而達到快速高效收集消息的目的。DD是周期性的協(xié)議,其周期性表現(xiàn)在sink節(jié)點周期性地向傳感器節(jié)點發(fā)送廣播興趣。

概括來說,定向擴散路由協(xié)議的工作過程分為“興趣擴散-梯度建立-路徑加強”三個階段[4,5](如圖1所示)。興趣擴散階段采用洪泛方式進行;梯度建立依據(jù)興趣擴散的路徑完成;路徑加強在消息傳遞過程中由各個節(jié)點(包括匯聚節(jié)點和傳感器節(jié)點)之間相互作用完成。DD中仿真采用的方式是節(jié)點選擇最先接收到傳來興趣消息的節(jié)點作為一個加強的路徑。

圖1 定向擴散的簡單示例

從DD協(xié)議的工作過程可以發(fā)現(xiàn),在DD協(xié)議中,在興趣擴散階段,傳感器網(wǎng)絡(luò)為傳播興趣消息要消耗大量能量,而在路徑加強階段,由于節(jié)點之間要傳遞控制消息(要加強路徑的消息或者使某個路徑失效的消息)也要消耗較多的能量。由于節(jié)能是無線傳感器網(wǎng)絡(luò)的重要指標,因此無線傳感器網(wǎng)絡(luò)的設(shè)計必須把節(jié)省能量放在重要位置。

目前,已提出了多個DD協(xié)議的改進協(xié)議。對DD協(xié)議的改進主要是基于減少DD協(xié)議在“興趣擴散-梯度建立-路徑加強”三個階段的能量消耗。其中一類是不改變整個通信的拓撲結(jié)構(gòu),主要從減少DD協(xié)議中洪泛方式傳播興趣消息的能量消耗出發(fā),來減少興趣擴散階段的能量消耗,其中文獻[14-17]都是采用這種方式;另一類是不改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu),省略梯度建立和路徑加強階段,即定向擴散完成后即形成了數(shù)據(jù)傳遞的路徑,文獻[18,19]即是采用這種方式;還有一類就是改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu),采用分簇的方式對DD協(xié)議進行改進,其中大部分都是采用被動分簇方式。即初始狀態(tài)下傳感節(jié)點地位平等,隨著興趣消息的擴散采用不同的機制形成簇結(jié)構(gòu),這樣形成的簇主要是來傳播傳感器收集到的信息[20,21],顯然并沒有節(jié)省興趣擴散階段的能量。文獻[22]采用主動分簇的方式,結(jié)合DD和LEACH,其通信方式為“形成簇結(jié)構(gòu)-興趣擴散-梯度建立-路徑較強”四個階段,相對DD而言,其能量節(jié)省主要在興趣擴散階段和數(shù)據(jù)傳輸時。文獻[22]沒有考慮如果事件只是在整個網(wǎng)絡(luò)部署區(qū)域中的一小部分區(qū)域發(fā)生,也沒有考慮路徑加強階段的能量消耗。還有其他的改進方法,如通過決策函數(shù)選擇轉(zhuǎn)發(fā)點的協(xié)議[23],通過調(diào)整剩余能量的閾值限制低能量節(jié)點加入路徑[24],等。

本文提出了對定向擴散路由協(xié)議的改進算法。該算法結(jié)合定向擴散路由協(xié)議的特點,在分簇機制下對定向擴散路由協(xié)議的通信機制進行改進,不同于其他以分簇方式對DD協(xié)議進行改進的方法。本協(xié)議采用主動分簇方式,且考慮事件的發(fā)生情況,簡化通信機制的形成,以減少整個通信過程中的能量消耗,仿真證明了算法的有效性。

2 分簇定向擴散路由算法

由于DD是以數(shù)據(jù)為中心的路由協(xié)議,假設(shè)事件只發(fā)生在某一個相關(guān)區(qū)域之內(nèi)。我們知道,sink節(jié)點感興趣的只是和自己發(fā)出的興趣消息相匹配的信息,而對于沒有收集到該興趣消息的節(jié)點,完全可以不理會相關(guān)事件的發(fā)生進入休眠狀態(tài),從而達到節(jié)省能量,延長網(wǎng)絡(luò)的生命周期的目的。

圖2 事件圖

圖2中灰色的節(jié)點為能收集到sink感興趣信息的節(jié)點,而其余節(jié)點都是不能收集到sink感興趣信息的節(jié)點。我們知道,如果按照DD的工作方式,經(jīng)過洪泛的方式進行興趣擴散,那么,每個節(jié)點都要進入活動狀態(tài)來匹配興趣消息和信息的收集,這樣會消耗大量能量。另外,不論以何種工作方式,如果所有節(jié)點的接受興趣消息也將有相應(yīng)的能量消耗。

本文選擇GAF的改進算法[25]來生成簇。由于GAF算法沒有給出具體的路由過程,我們將以其思想進行路由傳輸(具體過程如圖3所示)。由于在DD算法中,每個傳感器節(jié)點都攜帶有GPS定位系統(tǒng),目的是要收集檢測區(qū)域的數(shù)據(jù),而GAF算法是基于地理位置單元格劃分的經(jīng)典算法。DD算法和GAF算法都是對地理位置有較大要求的算法,在這個方面DD算法和GAF算法是一致的。GAF算法適用于規(guī)模和密度比較大的傳感器網(wǎng)絡(luò)中,在進行簇頭選取的時候采取GAF的改進算法比較合理。所以,從圖3可以看出,大部分節(jié)點的這種工作是沒有必要的。下面將從這種思想出發(fā),提出我們的算法。圖3為CDD算法的執(zhí)行過程圖。

算法描述如下:

1 )簇生成。在形成簇結(jié)構(gòu)的階段,要選擇GAF的改進算法形成簇結(jié)構(gòu)。如圖3中1)所示,其中A、B、C、D、E、F、G、I為簇頭節(jié)點。

2 )將sink節(jié)點發(fā)出的興趣消息沿簇頭節(jié)點進行傳播,如圖3中2)所示。

3 )等待一定的時間,若有簇頭節(jié)點和相應(yīng)興趣消息匹配的數(shù)據(jù),該簇頭節(jié)點在其通信范圍內(nèi)向周圍節(jié)點廣播該興趣消息,如圖3中3)所示。

4 )所有收到興趣消息的節(jié)點和簇頭節(jié)點進行信息收集,收集到的數(shù)據(jù)按照簇結(jié)構(gòu)進行傳送,如圖3中4)所示。

在第1)步時,如無簇頭節(jié)點和相應(yīng)興趣消息匹配的數(shù)據(jù),則所有簇頭節(jié)點向其簇內(nèi)進行興趣消息廣播,所有簇內(nèi)節(jié)點接收到相應(yīng)消息后進行。若有相匹配的信息,則進行信息收集并把收集到的信息傳給簇頭,簇頭節(jié)點負責把數(shù)據(jù)傳給sink節(jié)點。其工作原理如圖3所示。

在本算法中,簇的形成是周期性的。

本算法主要考慮事件只在一部分小區(qū)域內(nèi)發(fā)生的情況下,相對于DD協(xié)議來說,其優(yōu)勢主要在于大大減少了洪泛方式進行興趣傳播的能量消耗,也省去了梯度建立和路徑加強方面的能量消耗。該算法的能量消耗主要在成簇階段,但相比DD算法仍能節(jié)省較多能量。如無簇頭節(jié)點和相應(yīng)興趣消息匹配的數(shù)據(jù)則所有簇頭節(jié)點向其簇內(nèi)進行興趣消息廣播時,即可能監(jiān)測到時間的節(jié)點都是非簇頭節(jié)點,那么進行廣播興趣消息的做法可以確保監(jiān)測事件能傳給sink節(jié)點。該算法仍有不足之處,例如如果能感知到興趣消息事件的節(jié)點分布的區(qū)域較大時,CDD算法對于DD算法優(yōu)越性不強且可靠性不強,這方面有待于進一步地研究。

3 仿真實驗

如下設(shè)置仿真環(huán)境:將600個傳感器節(jié)點放置在坐標(0,0)到(600X600)m2的正方形區(qū)域內(nèi),節(jié)點攜帶GPS定位系統(tǒng),初始能量都設(shè)置為2J,sink節(jié)點位于檢測區(qū)域之外位置為(610,300)m的位置,節(jié)點的能量模型參考如下:

仿真主要從能量消耗和節(jié)點的存活個數(shù)兩個方面對傳統(tǒng)的DD協(xié)議和CDD協(xié)議進行比對,如圖4和圖5所示。

仿真結(jié)果表明,在傳輸相同數(shù)據(jù)時,CDD協(xié)議比傳統(tǒng)DD協(xié)議的能量消耗有所降低,傳輸相同數(shù)據(jù)后CDD協(xié)議比傳統(tǒng)DD協(xié)議的節(jié)點存活個數(shù)也相應(yīng)較多。

表1 參數(shù)表

4 總結(jié)

本文在對定向擴散路由算法(DD算法)分析的基礎(chǔ)上,引入主動分簇的思想對該算法進行改進并對改進的算法進行了詳細的描述。仿真證明改進CDD算法比傳統(tǒng)的DD算法在傳輸相同的數(shù)據(jù)任務(wù)時能量消耗小,節(jié)點存活個數(shù)多。該算法適合于興趣區(qū)域范圍較小的情況下,對算法進行擴展是下一步要研究的一個方向。

[1]孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社,2005:2-15.

[2]沈波,張世永,鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學報,2006,17(7):1588-1600.

[3]HAAS Z J,HALPERN J Y,LI Li.Gossipb-ased Ad hoc routing[C]//Proc of IEEE INFOCOM.New York: IEEE Communications Society,2002:1707-1716.

[4]Intanagonwiwat C,Govindan R,Estrin D,et al.Directed Diffusion for Wireless Sensor Networking[J].IEEE/ ACM Trans on Networking.2003,1l(1):2-16.

[5]Intanagonwiwat C,Govindan R,Estrin D.Directed Diffusion:A Scalable and Robust nununication Paradigm for Sensor Networks[C]//Proc of the 6th Annum ACM/ IEEE lnt1'Conf on Mobile Computing and Networking, 2000:56-67.

[6]Braginsky D,Estrin D.Rumor routing algorithm for sensor networks[M]//Proc.of the 1st Workshop on Sensor Networks and Applications.Atlanta:ACM Press,2002:22-31.

[7]KULIK J,HEINZELMAN W R,BALAKRISHNAN H.Negotiation-based protocols for disseminating information in wireless sensor networks[J].Wireless Networks,2002,8(2/3):169-185.

[8]LI Li,HALPERN J Y.Minimum energy mobile wireless networks revisited[C]//Proc of IEEE International Conferenee on Communications.Piscataway:IEEE, 2001:278-283.

[9]NEWSOME J,SONG D.GEM:graph embedding for routing and data centric storage in sensor networks without geographic information[C]//Proc of the 1st ACM Conf on Embedded Networked Sensor Systems, 2003:76-88.

[10]Yu Y,Estrin D,Govindan R.Geographical and energyaware routing:a recursive data dissemination protocol for wireless sensor networks[J].UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023,los angeles:University of California,2001:1-11.

[11]Heinzelman W,Chandrakasan A,Balakrishnan H. Application-specific protocol architecture for wireless microsensor networks[C]//EEE Transaction on wireless communications,2002,1(4):660-670.

[12]Xu Y,Heidemann J,Estrin D.Geography-informed energy conservation for ad hoc routing[C]//Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking(Mobi-Com'01)Rome,2001:70-84.

[13]Ephremides A,Wieselthier J E,Bader D J A.Design concept for reliable mobile radio networks with frequency hopping signaling[J].Proceeding of IEEE,1987,75 (1):56-73.

[14]李應(yīng)娣,單志龍.無線傳感器網(wǎng)絡(luò)定向擴算路由協(xié)議研究[J].計算機技術(shù)與發(fā)展,2010,20(9):40-43.

[15]趙奇,王汝傳,孫力娟.傳感器網(wǎng)絡(luò)定向擴算協(xié)議研究及改進[J].計算機工程與設(shè)計,2007,28(12):2825-2828.

[16]李戈陽,曹陽,馬曦.基于遺傳優(yōu)化的無線傳感器網(wǎng)絡(luò)定向擴散協(xié)議[J].湖南大學學報,2009,36(9):84-86.

[17]Miresmaeil Mirnbibaboli,Mehdi Mirfattahi,Mher Markosyan.Improving the Directed Diffusion in Order to Reduce the Average of Energy Consumption in Wireless Sensor Network[C]//the fifth international conference on sensor technologies and applications,IARIA,2011: 223-228.

[18]萬健,吳建榮,徐向華.無線傳感器網(wǎng)絡(luò)定向擴算路由協(xié)議研究[J].計算機工程與科學,2009,31(6):99-102.

[19]SCHURGERS C,SRIVASTAVA M B.Energy efficient routing in wireless sensor networks[C]//Proc of Communications for Network.Centric Operations:Creating the Information Force,2001:357-361.

[20]Vlado Handziski,Andreas Kopke,Holger Karl.Improing the Energy Efficiency of Directed Diffusion Using Passive Clustering[C]//In Proc.of 1st European Workshop on Wiress Sensor Networks:Berlin,2004:172-187.

[21]李桂青,高仲合,王楠楠.基于簇頭集的無線傳感器網(wǎng)絡(luò)定向擴散協(xié)議[J].山東大學學報,2010,45(11):37-42.

[22]CUI Yanrong,CAO Jiaheng.An improved Directed Diffision for wireless sensor networks[C]//Wireless Communications,Networking and Mobile Computing, shanghai,2007:2380-2383.

[23]駱海燕,鄭淑麗,李少林.一種改進的無線傳感器網(wǎng)絡(luò)定向擴散協(xié)議[J].合肥工業(yè)大學學報,2010,33(6):851-854.

[24]仲盈,馮金鑫,熊慶旭.確定性無線傳感器網(wǎng)絡(luò)定向擴散路由協(xié)議[J].北京航空航天大學學報,2007,33(10): 1230-1232.

[25]Sami P,Simon J.Silence Is Golden with High Probability:Maintaining a Connected Backbone in Wireless Sensor Networks[C]//Wireless Sensor Networks:First EuropeanWorkshop.Berlin,Germany:EWSN,2004:106-118.