基于AODV的無線多媒體傳感器網(wǎng)絡路由協(xié)議

張德海,韓帥帥,王寶林

(西安電子科技大學 電子工程學院,陜西 西安 710071)

基于AODV的無線多媒體傳感器網(wǎng)絡路由協(xié)議

張德海,韓帥帥,王寶林

(西安電子科技大學 電子工程學院,陜西 西安 710071)

研究了AODV路由協(xié)議,分析了多路徑路由實現(xiàn)機制,提出了一種可應用于無線多媒體傳感器網(wǎng)絡的能量均衡多路徑AODV路由協(xié)議。該協(xié)議建立從源節(jié)點到目的節(jié)點的多條路徑,在路徑的選擇上綜合考慮了路徑跳數(shù)和節(jié)點剩余能量,用以保證負載均衡,延長網(wǎng)絡生存期,該算法使用了分流的方式避免擁塞。通過使用NS2仿真軟件對EEMP-AODV路由協(xié)議進行仿真,結果顯示其在擁塞避免、實時性、吞吐量和網(wǎng)絡生存期方面的性能有明顯提升。

無線多媒體傳感器網(wǎng)絡;路由;能量均衡;多路徑

無線多媒體傳感器網(wǎng)絡(Wireless Multimedia Sensor Networks,WMSN)是無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSN)與多媒體處理技術相結合的產(chǎn)物,音頻和視頻信息的引入要求傳感器網(wǎng)絡傳輸、處理大量數(shù)據(jù),使得針對WSN的路由協(xié)議難以直接應用于WMSN[1]。因此,雖有大量針對WSN的路由協(xié)議被提出,但關于WMSN的路由協(xié)議仍是一個值得開發(fā)的研究領域。路由作為無線多媒體傳感器網(wǎng)絡的重要支撐技術也成為了研究熱點。

近年來,一些專門針對WMSN的路由協(xié)議被提出,這些協(xié)議是在針對WSN的路由協(xié)議基礎上進行改進,或使用新方式提出新的解決方案,如使用MIMO系統(tǒng)、多通道、多路徑或以上方法的混合。針對WMSN的經(jīng)典路由協(xié)議有SAR(Sequential Assignment Routing)[2]、REAR(Real-time and Energy Aware QoS Routing)[3]、TPGF(Two-Phase geographic Greedy Forwarding)[4]、SPEED[5]。本文針對WMSN傳輸大量多媒體數(shù)據(jù)的特點,分析常見多路徑機制和擁塞避免方式,在經(jīng)典AODV(Ad Hoc on Demand Distance Vector)路由協(xié)議[6]的基礎上提出了一種新型的多路徑路由協(xié)議,并提出“反向分流”措施避免數(shù)據(jù)擁塞。

1 AODV路由協(xié)議

AODV路由協(xié)議中使用了3種控制消息:路由請求(Route REQest,RREQ)、路由應答(Route REPly,RREP)和路由錯誤(Route ERRor,RERR)。

RREQ和RREP控制消息用于路由建立。當源節(jié)點需向目的節(jié)點發(fā)送數(shù)據(jù)包時,便會通過廣播RREQ消息進行路由的發(fā)現(xiàn),中間節(jié)點可根據(jù)RREQ消息建立到達源節(jié)點的路由,稱為“反向路由”。當RREQ到達了目的節(jié)點,或具有可通向目的節(jié)點路由的中間節(jié)點后,就可確定一條從源節(jié)點到目的節(jié)點的路由。目的節(jié)點或中間節(jié)點沿“反向路由”發(fā)送RREP消息,完成路由的建立。

圖1說明源節(jié)點S到目的節(jié)點D的路由建立過程。首先源節(jié)點S進行RREQ消息的廣播,其他中間節(jié)點收到該RREQ消息,并繼續(xù)廣播。當S收到節(jié)點G發(fā)送的RREQ時,將其丟棄。從而可避免環(huán)路S-A-G-S的產(chǎn)生。當節(jié)點C和節(jié)點D再次收到相同的RREQ時,也進行丟棄處理,可以減少在網(wǎng)絡中廣播的消息。最終,目的節(jié)點D收到RREQ消息,并向源節(jié)點S回復該消息,完成路由S-E-F-D的建立。

圖1 AODV路由建立過程

RERR消息在鏈路出現(xiàn)故障后使用。當節(jié)點確定鄰居節(jié)點的鏈路丟失,將發(fā)送RERR消息,通知使用此條路徑的節(jié)點刪除該路徑,源節(jié)點將再次進行路由發(fā)現(xiàn)過程。但每次鏈路丟失后均進行路由發(fā)現(xiàn)將消耗過多資源。因此,AODV使用了本地修復措施。AODV具有簡潔的路由表結構,減少內(nèi)存占用,提供了環(huán)路避免機制。但也存在一些缺點,如使用單路徑傳輸,可靠性低,并未提供擁塞避免機制,且不適用于大量數(shù)據(jù)的傳輸。

針對AODV算法存在的缺點,一些改進算法被提出,典型的如AOMDV(Ad Hoc on Demand Multipath Distance Vector)[7]路由協(xié)議。AOMDV使用多路徑機制來保證數(shù)據(jù)的可靠傳輸,在節(jié)點內(nèi)保存可到達目的節(jié)點的多條路徑,只有在所有可到達目的節(jié)點的路徑均失去時,才進行路由發(fā)現(xiàn)過程,從而減少了由于網(wǎng)絡變化導致的頻繁路由發(fā)現(xiàn)。但AOMDV算法未考慮擁塞情況,路徑選擇也并未考慮節(jié)點的剩余能量,故不利于網(wǎng)絡的能量均衡。

2 EEMP-AODV路由協(xié)議實現(xiàn)

能量均衡的多路徑AODV路由協(xié)議的關鍵部分包括多路徑路由的建立、路徑選擇和擁塞避免措施。多路徑機制可保證網(wǎng)絡安全,有效提高網(wǎng)絡服務質(zhì)量。路徑選擇是多路徑路由協(xié)議必須考慮的問題,最佳路徑不但可提供高效的數(shù)據(jù)傳輸服務,還能提高網(wǎng)絡整體性能。針對WMSN傳輸大量數(shù)據(jù)的需要,有必要提供擁塞避免機制。

2.1 多路徑機制

多路徑路由結構可分為[8]節(jié)點不相交路徑(Node-Disjoint Paths)、鏈路不相交路徑(Link-Disjoint Path)和部分不相交路徑(Partially Disjoint Paths)。3類多路徑路由結構如圖2所示。對于節(jié)點不相交路徑,路徑間沒有共同的鏈路和節(jié)點,節(jié)點或鏈路的失效只會造成該路徑的失敗,卻不會影響到其他路徑,但選擇其他路徑繼續(xù)傳輸將導致數(shù)據(jù)延遲。鏈路不相交路徑中有共同的節(jié)點,但鏈路不會共享,共同節(jié)點的存在,可能會在傳輸大量數(shù)據(jù)時造成該節(jié)點處的數(shù)據(jù)包出現(xiàn)擁塞。部分不相交路徑既存在共享的節(jié)點,又存在共享的鏈路。

圖2 多路徑路由結構

為解決節(jié)點不相交路徑在面對鏈路失效時的低效性,及鏈路不相交和部分不相交路徑中共享節(jié)點可能出現(xiàn)的擁塞問題,需使用一種新型的多路徑路由結構。本文提出的EEMP-AODV路由協(xié)議使用部分不相交路由結構,但對該結構有一定的限制,要求鏈路一旦在某個節(jié)點分離,只有在目的節(jié)點相聚。該結構如圖3所示,如在“分叉”節(jié)點A,鏈路分為兩條支路,這兩條支路在目的節(jié)點之前既不共享節(jié)點,也不共享鏈路。

EEMP-AODV的路由結構有以下優(yōu)點:在鏈路或節(jié)點失效后,前向“分叉”節(jié)點可快速選擇其他路徑進行數(shù)據(jù)傳輸,減少數(shù)據(jù)丟失,降低延遲;不存在多條鏈路相聚而引起的共享節(jié)點擁塞問題;傳輸大量數(shù)據(jù)時,可使用多條鏈路進行數(shù)據(jù)分流,有效避免了擁塞,進而提高傳輸速率。

圖3 EEMP-AODV路由結構

EEMP-AODV路由協(xié)議也使用RREQ和RREP消息進行路由建立,為形成圖3所示的路由結構,節(jié)點對路由發(fā)現(xiàn)消息的處理過程與傳統(tǒng)AODV路由協(xié)議不同。EEMP-AODV路由協(xié)議要求目的節(jié)點接收所有的RREQ消息并回復RREP消息,中間節(jié)點也將轉(zhuǎn)發(fā)接收到的所有RREP消息,保證可建立起由源節(jié)點到目的節(jié)點的多條路徑。中間節(jié)點則丟棄相同的RREQ消息,避免分離的鏈路相聚。

2.2 最佳路徑選擇

傳統(tǒng)AODV路由協(xié)議在節(jié)點內(nèi)只保存一條目前所發(fā)現(xiàn)的最少跳數(shù)路徑,而EEMP-AODV保存了多條路徑,需要進行路徑選擇。為保持節(jié)點能量均衡,本算法綜合考慮路徑跳數(shù)和節(jié)點剩余能量。使用如下公式進行路徑質(zhì)量的衡量

Path_Score(Pi)=αRE(Pi)+(1-α)HC(Pi)

(1)

其中

(2)

(3)

ren1,ren2,…,renm為路徑Pi上m個節(jié)點的剩余能量,IE為節(jié)點初始能量,LP1,LP2,…,LPw分別表示從源節(jié)點到sink節(jié)點的w條路徑節(jié)點跳數(shù)。Path_Score(0

在進行路徑選擇時,選擇了節(jié)點剩余能量高且跳數(shù)較少的路徑,但長時間使用同一路徑傳輸數(shù)據(jù),可能導致該路徑上節(jié)點耗盡能量,造成空洞,不利于延長網(wǎng)絡壽命。因此,除因丟失到達目的節(jié)點的路由而進行路由發(fā)現(xiàn)外,EEMP-AODV算法還周期性進行路由發(fā)現(xiàn)和路徑選擇。

2.3 擁塞避免措施

改進算法提出了“反向分流”的擁塞避免機制。在使用最佳路徑進行數(shù)據(jù)包傳輸過程中,若某一節(jié)點內(nèi)緩存過多數(shù)據(jù)包,意味著該節(jié)點有較大可能出現(xiàn)擁塞。此時該節(jié)點沿“反向路由”發(fā)送一Warning信息,直到到達“分叉”節(jié)點,“分叉”節(jié)點將本應傳送到該節(jié)點所在路徑的一部分數(shù)據(jù)流分流到另一條路徑上,以此避免由于擁塞造成的數(shù)據(jù)延遲和數(shù)據(jù)包丟失。若“分叉”節(jié)點再次收到Warning信息,則將繼續(xù)向前傳送,直至到達源節(jié)點。

當源節(jié)點接收到Warning信息時,有可能是因數(shù)據(jù)傳輸量過大,已超過網(wǎng)絡承載能力,也有可能因網(wǎng)絡動態(tài)變化導致路徑丟失。為解決后類情況,每當源節(jié)點接收到RERR信息后,均將進行最初路徑數(shù)和現(xiàn)有路徑數(shù)的統(tǒng)計,當路徑丟失率高于設置上限,且收到Warning信息,則進行新的路由發(fā)現(xiàn)和建立過程。

3 仿真分析

為對設計協(xié)議進行仿真,在Linux操作系統(tǒng)下建立仿真環(huán)境,使用NS2的版本為2.35,26個節(jié)點隨機分布。表 1列出了對網(wǎng)絡中重要參數(shù)的設置。

表1 仿真參數(shù)設置

(1)AODV、AOMDV和EEMP-AODV路由協(xié)議的時延對比,如圖4所示。

圖4 AODV、AOMDV和EEMP-AODV協(xié)議的延時比較

在數(shù)據(jù)傳輸速率低于70 kbit·s-1時,3種協(xié)議情況相似,均使用單條路徑進行數(shù)據(jù)傳輸,此時傳輸延時曲線幾乎重合。隨著傳輸速率的增加,數(shù)據(jù)量超過AODV和AOMDV單條路徑的傳輸能力,節(jié)點將對數(shù)據(jù)進行緩存,導致延時增大。而EEMP-AODV可使用多條路徑進行傳輸,有效減少了數(shù)據(jù)的延時。

(2)AODV、AOMDV和EEMP-AODV路由協(xié)議的丟包情況,如圖5所示。

圖5 AODV、AOMDV和EEMP-AODV協(xié)議的丟包率比較

與延遲情況類型,在傳輸速率較低時,3種協(xié)議的性能相同。但隨著數(shù)據(jù)傳輸率的增加,導致某些節(jié)點緩存過多數(shù)據(jù)包,此時節(jié)點將丟棄部分數(shù)據(jù)包,造成丟包率隨著傳輸速率上升的現(xiàn)象。AOMDV協(xié)議可在一條鏈路失效后及時使用后備路徑,一定程度上減少了丟包率。而EEMP-AODV路由協(xié)議除可使用后備路徑外,還使用了“反向分流”措施,避免了節(jié)點由于緩存過多數(shù)據(jù)包而造成擁塞,大幅降低了丟包率。

(3)如圖6所示,隨著源節(jié)點發(fā)送速率的增加,網(wǎng)絡的數(shù)據(jù)傳輸量也在增加。當數(shù)據(jù)傳輸速率過大時,網(wǎng)絡有限的帶寬、節(jié)點有限的存儲空間將導致數(shù)據(jù)包丟失,限制傳輸量的增加。因此,網(wǎng)絡的吞吐量趨于平衡。AOMDV無需進行頻繁路由發(fā)現(xiàn),可及時應對鏈路失效情況,使其相對AODV有較高吞吐量。而EEMP-AODV路由協(xié)議將數(shù)據(jù)進行分流的措施使網(wǎng)絡有更高的傳輸能力,使其相對AODV和AOMDV路由協(xié)議有著更高的吞吐量上限。

圖6 AODV、AOMDV和EEMP-AODV協(xié)議的吞吐量性能比較

(4)本文使用網(wǎng)絡中最早耗盡能量節(jié)點的生存時間衡量網(wǎng)絡生存期。如圖7曲線所示,節(jié)點在不進行數(shù)據(jù)傳輸時處于休眠狀態(tài),耗能較少;但隨傳輸速率的增加,休眠時間縮短,耗能增加,節(jié)點壽命縮短。當傳輸速率過高時,節(jié)點不間歇進行數(shù)據(jù)的接收與發(fā)送,無休眠時間,此時節(jié)點的壽命趨于最小值。AOMDV協(xié)議可避免頻繁路由發(fā)現(xiàn),一定程度上減少耗能,但效果并不明顯。在各個傳輸速率上,EEMP-AODV路由協(xié)議均有著更長的網(wǎng)絡生存期。由此說明,EEMP-AODV路由協(xié)議基于節(jié)點剩余能量和路徑跳數(shù)的路由選擇措施可有效避免網(wǎng)絡節(jié)點過早死亡,延長網(wǎng)絡壽命。

圖7 AODV、AOMDV和EEMP-AODV協(xié)議網(wǎng)絡生存期比較

4 結束語

本文在傳統(tǒng)AODV路由協(xié)議的基礎上設計了一款能量均衡的多路徑AODV路由協(xié)議,以滿足WMSN傳輸大量數(shù)據(jù)的需求。仿真結果表明,該協(xié)議可有效避免網(wǎng)絡擁塞,減少網(wǎng)絡延遲和丟包率,且路徑選擇時對節(jié)點剩余能量的考慮也有效增加了網(wǎng)絡壽命。

[1] Islam T Almalkawi,Manel Guerrero Zapata,Jamal N Al-Karaki.A secure cluster-based multipath routing protocol for WMSNs[J].Sensors,2011(11):4401-4424.

[2] Sohrabi K,Gao J,Allawadhi V,et al.Protocols for self organization of a wireless sensor network[J].IEEE Perseeding Communications,2000,7(5):25-30.

[3] Lan Y,Wenjing W,Fuxiang G.A real-time and energy aware QoS routing protocol for Multimedia Wireless Sensor Networks[C].Chongqing,China:In Proceedings of 7th World Congress on Intelligent Control and Automation,WCICA’08,2008:3321-3326.

[4] Shu L,Zhang Y,Yang L T,et al.Geographic routing in wireless multimedia sensor networks[C].In Proceedings of the 2nd International Conference on Future Generation Communication and Networking (FGCN ’08),2008:68-73.

[5] He T,Stankovic J A,Lu C,et al.Speed:a stateless protocol for real-time communication in sensor networks[C].Providence,RI,United States:in 23rd IEEE International Conference on Distributed Computing Systems (ICDCS-03),2003:46-55.

[6] Charles E Perkins,Elizabeth M Royer.Ad Hoc on-demand distance vector routing[C].New Orleans:In Proceedings of the 2ed IEEE Workshop on Mobile Computing Systems and Applications,1999:90-100.

[7] Mahesh K Marina,Samir R Das.Ad Hoc on-demand multipath distance vector routing[J].Wireless Communications Mobile Computer,2006(6):969-988

[8] Marjan Radi,Behnam Dezfouli,Kamalrulnizam Abu Bakar,et al.Multipath routing in wireless sensor networks:survey and research challenges[J].Sensors,2012(12):650-685.

Research on Routing Protocol for Wireless Sensor Networks Based on AODV

ZHANG Dehai,HAN Shuaishuai,WANG Baolin

(School of Electronic Engineering,Xidian University,Xi’an 710071,China)

This paper researches the AODV routing protocol,analyzes the multipath routing protocol,and puts forward an energy efficient multipath AODV routing protocol for wireless multimedia sensor networks.EEMP-AODV builds multipath from source node to destination node.In order to achieve load balancing and extend the entire network lifetime,it takes hop count and nodes’ residual energy into account in route choice.EEMP-AODV avoids congestion by divide rate into multipath.Finally,NS2 is used to simulate the proposed routing protocol.The result shows EEMP-AODV routing algorithm has a significant improvement in congestion avoidance,real-time performance,throughput and lifetime.

wireless multimedia sensor networks;routing;energy efficient;multipath

2014- 08- 19

張德海(1989—),男,碩士研究生。研究方向:無線多媒體傳感器網(wǎng)絡。E-mail:380483289@qq.com

10.16180/j.cnki.issn1007-7820.2015.03.023

TN926;TP212.9

A

1007-7820(2015)03-087-04