無線傳感器網(wǎng)絡(luò)的路由協(xié)議綜述

1、無線傳感器網(wǎng)絡(luò)的路由協(xié)議綜述 摘要：區(qū)別于傳統(tǒng)的網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)（ wsns ）高度依賴于具體應(yīng)用，并受到能源、存儲容量和計算能力等因素的嚴重制約。為了延長整個網(wǎng)絡(luò)的壽命，當我們設(shè)計或分析路由協(xié)議時，能源感知是一個重要的考慮因素。在本文中，我們提出了最近的wsns路由協(xié)議的綜合概述，并基于wsns網(wǎng)絡(luò)結(jié)構(gòu)將其分為三類 。然后，我們描述了現(xiàn)有的路由協(xié)議，并討論每個路由算法的優(yōu)點和缺點。最后，我們結(jié)束了開放研究和挑戰(zhàn)的問題。 關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)，路由協(xié)議，網(wǎng)絡(luò)結(jié)構(gòu) 導(dǎo)言 伴隨著電子器件批量制造過程和無線通訊技術(shù)的發(fā)展，組成了大量的微型傳感器節(jié)點，無線傳感器網(wǎng)絡(luò)最近在工業(yè)界和學(xué)術(shù)界成為熱點問

2、題。這些傳感器節(jié)點的低成本、低功耗和多功能等特點已廣泛應(yīng)用于軍事、工業(yè)、交通、環(huán)境保護等諸多領(lǐng)域。特別是在骨干網(wǎng)絡(luò)存在的離線情況下，如人類無法到達的危險區(qū)域，戰(zhàn)場上，和其他破壞性的領(lǐng)域，無線傳感器網(wǎng)絡(luò)的應(yīng)用前景必將是巨大的。目前，相關(guān)研究人員已經(jīng)積累了豐富的成果。 如何有效路由收集到的節(jié)點間的數(shù)據(jù)是wsns極為重要的課題。 以下是一些傳感器網(wǎng)絡(luò)與路由技術(shù)的主要特點： （ 1 ）傳感器節(jié)點是有限的資源（能源、芯片運算能力、存儲空間、通訊距離） ，并部署在預(yù)先確定的或隨機的方式下; （ 2 ）由于傳感器網(wǎng)絡(luò)的節(jié)點具有大量的簇頭和傳感器 1 ，節(jié)點可能沒有全球性識別碼（ id ）。 （ 3 ）通常情

3、況下，傳感器網(wǎng)絡(luò)中的數(shù)據(jù)是從水槽經(jīng)下游到節(jié)點或從節(jié)點經(jīng)上游下沉到水槽。無線傳感器網(wǎng)絡(luò)是一種指定應(yīng)用程序的網(wǎng)絡(luò)。 基于這些路由技術(shù)和wsns的特點 ，研究人員目前已經(jīng)提出了大量的路由協(xié)議在。在本文中，我們調(diào)查了目前具有代表性的路由協(xié)議，并把它們基于網(wǎng)絡(luò)結(jié)構(gòu)歸類為三種。本文安排如下。首先，我們確定了無線傳感器網(wǎng)絡(luò)路由協(xié)議。然后，我們列舉了現(xiàn)有的路由協(xié)議，并分析它們的優(yōu)點和缺點。擴展了這些路由協(xié)議，并討論最新的研究趨勢。最后，我們以談?wù)摤F(xiàn)有的開放研究問題和其他值得考慮的許多方面的問題結(jié)束本文。 二 無線傳感器網(wǎng)絡(luò)的路由協(xié)議的分級由于傳感器節(jié)點本身是有限的資源，因此目前的研究主要集中在如何設(shè)計一個有效

4、并具有能源感知的協(xié)議，以延長整個網(wǎng)絡(luò)的具體應(yīng)用環(huán)境的壽命。由于物理層和數(shù)據(jù)鏈路層是完全獨立的特定應(yīng)用層，我們集中于能源的意識的協(xié)議，特別是網(wǎng)絡(luò)層的節(jié)能路由協(xié)議。然而，路由協(xié)議的網(wǎng)絡(luò)層的設(shè)計依賴于特定的應(yīng)用，需要考慮節(jié)點的限制，如能源、存儲和計算能力。由于傳感器節(jié)點沒有給定一個統(tǒng)一的用來區(qū)別的身份識別id，很多冗余數(shù)據(jù)聚集在目的節(jié)點，還存在著以下幾個方面的限制：能源效率、可擴展性、延遲、容錯性、準確性和服務(wù)質(zhì)量（ qos ）的限制，當我們設(shè)計或選擇wsns的路由協(xié)議時，我們必須仔細考慮。然而，共同的目標是以快速和低成本的方式建立一個穩(wěn)定的傳輸路徑。 當前大量的路由協(xié)議，是基于wsns網(wǎng)絡(luò)結(jié)構(gòu)和數(shù)

5、據(jù)傳輸模式，一般來說，我們可以把路由協(xié)議分為三類：平板式路由（泛洪） ，分層路由（聚類）和基于定位的路由（物理的） 。 1 ）平板式路由（泛洪） 。在平板式路由中，所有節(jié)點通常是平等的行使相同的功能。每個節(jié)點不僅可以收集相關(guān)事件的數(shù)據(jù)，而且還可以作為中繼節(jié)點傳遞信息數(shù)據(jù)。最初的路由表是溢滿形成的。根據(jù)是否建立和維護路由表，最初下沉節(jié)點、平板路由協(xié)議可分為三種模式： a ）傳統(tǒng)泛洪模式：最根本的泛洪、傳感器節(jié)點將收到的訊息傳送給他們的相鄰節(jié)點直到信息到達下沉節(jié)點。 b）事件驅(qū)動的模式：當傳感器節(jié)點感應(yīng)到相關(guān)的數(shù)據(jù)，他們主動將這些信息傳播到下沉節(jié)點，并根據(jù)路由表選擇下一個跳點。 c）查詢驅(qū)動模式：

6、下沉節(jié)點傳播指定的應(yīng)用請求（相關(guān)的）到相鄰節(jié)點 ，泛洪整個網(wǎng)絡(luò)。請求的節(jié)點然后選擇一個適當?shù)穆窂絹砘卮疬@個查詢。 2 ）分層路由（集群聚類） 。這個網(wǎng)絡(luò)中節(jié)點扮演不同的角色。聚類算法主要包括兩層路由，一層用來選取集群頭，另外一層用于路由。算法依據(jù)的是大量的高密度的傳感器節(jié)點，并著重于路由的可擴展性。主要特點是將整個wsns分裂成若干集群方面的具體規(guī)則。 3 ）基于定位的路由（物理的） 。通常假定傳感器節(jié)已知或能計算位置，因此，數(shù)據(jù)傳輸可直接發(fā)送到指定的區(qū)域。從而這些算法可避免數(shù)據(jù)傳輸?shù)膯栴}，如泛洪引起的傳播風(fēng)暴。 三 基于平板的路由（泛洪） a.傳統(tǒng)泛洪模型 泛洪和閑置 2 是最基本的傳統(tǒng)網(wǎng)絡(luò)

7、路由。他們并不需要知道網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。每個傳感器節(jié)點將收到的信息轉(zhuǎn)移到相鄰節(jié)點，反復(fù)進行這一過程，直至信息到達下沉節(jié)點或是由于ttl （通常定義為wsns的最大跳點）超時 。閑置在某些方面提高泛洪算法的性能，每個傳感器節(jié)點的信息只轉(zhuǎn)移給一個隨機的相鄰節(jié)點。不過，即使泛洪和閑置算法非常簡單，并適用于任何網(wǎng)絡(luò)結(jié)構(gòu)，但這兩種算法都沒有實際的應(yīng)用到指定的網(wǎng)絡(luò)，因為他們很容易引起爆炸和重疊的問題。 b 事件驅(qū)動模式 1 ）信息協(xié)商的傳感器協(xié)議（spin） ：spin 3 是第一個以數(shù)據(jù)為中心的路由協(xié)議。協(xié)議認為，相鄰節(jié)點感知數(shù)據(jù)具有相似性，每一個傳感器節(jié)點僅傳播相鄰節(jié)點沒有的不同的數(shù)據(jù)。通過這種方式，s

8、pin消除了冗余的數(shù)據(jù)傳輸，從而有效地降低了能源消耗。與此同時，每一個節(jié)點使用元數(shù)據(jù)來命名他們的數(shù)據(jù)，每一個節(jié)點可以基于數(shù)據(jù)特定的應(yīng)用知識和現(xiàn)有資源的知識來做出決策，使傳感器節(jié)點高效地利用有限的能源來分配數(shù)據(jù)。 spin使用三種信息數(shù)據(jù)：adv、req和data。avd是用來將自己的元數(shù)據(jù)傳播到相關(guān)事件節(jié)點；req發(fā)出通知給相鄰節(jié)點，該節(jié)點發(fā)送的組數(shù)據(jù)，data指的是原始數(shù)據(jù)。 任何數(shù)據(jù)真實傳播之前，節(jié)點執(zhí)行元數(shù)據(jù)的協(xié)商功能。協(xié)商是通過交換adv和req的發(fā)送者和接受者信息。 spin不需要維持相鄰的信息，它可以使自己適應(yīng)情況，節(jié)點在一定程度轉(zhuǎn)移；仿真結(jié)果表明，spin比傳統(tǒng)的模式更節(jié)能。然而

9、，該算法不能確保數(shù)據(jù)到達目標節(jié)點，尤其不適合用于高密度分布的節(jié)點。 2 ）謠傳路由 4 每個節(jié)點維護一個事件表，該表條目包含該事件的基本描述，源節(jié)點，最后一個跳節(jié)點；此外，存在著一種長壽命的信息，這是用來傳播wsns的事件描述。謠傳路由在本質(zhì)和spin是相同的；主要區(qū)別是，它包含一系列的事件信息表，因此，保持一個到達源節(jié)點的路徑。泛洪初始化后，相應(yīng)的路徑資訊已經(jīng)建立。因此，它避免了spin中大量的泛洪過程，大大節(jié)省能源。 該協(xié)議主要適用于那些大量查詢和少量活動的情景。如果網(wǎng)絡(luò)拓撲結(jié)構(gòu)經(jīng)常變化，謠傳路由的執(zhí)行力將大大減少。 3 ）能源感知路由 能源感知路由 5 考慮，是否所有的數(shù)據(jù)都通過最優(yōu)路徑

10、傳送，與這些路徑相關(guān)的能源節(jié)點是否會很快用盡。因此，在建立路由路徑這一過程中，一些次優(yōu)路徑和概率模型將保持在同一時間。然后，我們根據(jù)每個路徑的概率值來選擇傳輸路徑，以使最初的網(wǎng)絡(luò)負載平衡，從而延長了整個網(wǎng)絡(luò)的壽命。能源感知路由的缺點是需要交換相鄰節(jié)點之間的當?shù)匦畔?，所有?jié)點有一個統(tǒng)一的地址，這就增加了建設(shè)路由路徑的成本。沒有充分考慮單一節(jié)點傳送失敗的可能性，不適合于具有移動功能的傳感器節(jié)點。 c 查詢驅(qū)動模式 1 ）定向擴散 命名后，數(shù)據(jù)將在節(jié)點之間定向傳送，由下降節(jié)點提供。 在定向擴散中，存在著利益信息，以一個屬性值的方式，其中載有相關(guān)屬性查詢和梯度場，傳播過程中不斷更新。查詢轉(zhuǎn)化為有利益擴

11、散或泛洪在利益節(jié)點地區(qū)。當該地區(qū)的傳感器節(jié)點接收到利益，它的傳感器被激活，并開始監(jiān)測此利益事件。遙感數(shù)據(jù)以反向路徑返回利益的復(fù)制值。下沉節(jié)點激發(fā)利益穿過泛洪，到達所有的傳感器網(wǎng)絡(luò)節(jié)點；節(jié)點將利益信息保持在本地緩存。如果數(shù)據(jù)適合利益要求，它就將沿路徑前進。 定向擴散最明顯的特點是提前傳播查詢利益信息和以泛洪方式建立下沉節(jié)點之間和所有其他傳感器節(jié)點的路徑。然而，這也限制了這種協(xié)議的應(yīng)用范圍。例如，某特定的應(yīng)用需要下沉節(jié)點可以訪問不同類型的數(shù)據(jù)，那么保持每個傳感器節(jié)點的緩存成本將大幅度增加。 2 ）基于梯度的路由 該算法 6 是定向擴散的改進算法，以獲得最低的總跳躍數(shù)量而不是總最短時間。傳遞利益信息

12、的過程中，該算法取的是下沉節(jié)點和傳感器節(jié)點到達其高值時的最小跳躍，并計算出其與其鄰近的節(jié)點為連接梯度的兩個節(jié)點的高度差。路由數(shù)據(jù)未滿，節(jié)點選擇連接最大的梯度到數(shù)據(jù)。當數(shù)據(jù)泛洪，利息信息記錄跳躍數(shù)。這使節(jié)點可以發(fā)現(xiàn)跳躍到下沉節(jié)點的最低數(shù)目，稱為節(jié)點高度。節(jié)點高度和它的相鄰節(jié)點高度之間的差別被看成是梯度鏈接。鏈接與最大坡度相關(guān)。雖然來提高網(wǎng)絡(luò)壽命的技術(shù)建立在gbr基礎(chǔ)上，主要原則是它一般足夠并且也適用于其他特設(shè)的路由協(xié)議。 該算法還介紹了一些輔助方法，如數(shù)據(jù)集成和負載平衡，以提高wsns最高壽命周期。 四 層次路由（聚類） a 單層模式（單并列） 1 ）leach（低能量自適應(yīng)聚類層次） 該算法

13、7 主要是基于選擇一個節(jié)點作為一組節(jié)點的簇頭。簇頭負責下沉節(jié)點和其組節(jié)點的數(shù)據(jù)匯聚。這樣，在傳感器節(jié)點之間的數(shù)據(jù)交換數(shù)量就減少了。因此，該算法對節(jié)能具有較大貢獻。如果當前值低于門檻值，該節(jié)點輪流成為簇頭。選出的ch傳播廣告的信息給網(wǎng)絡(luò)中的其余節(jié)點，其余節(jié)點是新的簇頭。 leach是完全分布式的，數(shù)據(jù)傳輸延遲非常小。然而，該算法假設(shè)，即所有的簇頭可以直接與水槽通信，因此，假設(shè)可能并不實際，則就不能適合大規(guī)模的應(yīng)用。與此同時，這種劃分集群的做法可能帶來額外的成本和重疊的問題。 2 ） pegasis和層次pegasis 考慮到劃分集群的間接問題，pegasis在leach基礎(chǔ)上進行了改進，設(shè)計一個

14、節(jié)點鏈來取代群集組。在所有的傳感器節(jié)點中，只選擇一個節(jié)點作為網(wǎng)關(guān)來與水槽通信，鏈中的其他節(jié)點輪流把網(wǎng)關(guān)。在收到信息以后，每個節(jié)點需要聚集自己的遙感數(shù)據(jù)。最后，將這些數(shù)據(jù)傳送到網(wǎng)關(guān)節(jié)點。 雖然在消除動態(tài)集群形成的過頭方面，pegasis 8 表現(xiàn)優(yōu)于leach，因為是異步傳輸，傳輸?shù)臅r間延長了太多。層次pegasis進行了進一步的改進，節(jié)點不相鄰時它也允許同時傳輸。 與leach相比，后兩個算法消除形成集群的過頭問題，但兩者選擇路由路徑時，都沒有考慮下個跳躍的能源條件，因此它們不適合于重負載網(wǎng)絡(luò)。當wsns中節(jié)點數(shù)量很大時，數(shù)據(jù)傳輸?shù)闹袛喾浅Ｃ黠@，所以他們也沒有較大規(guī)模的應(yīng)用，也不適合于全球性知

15、識不容易獲得的傳感器網(wǎng)絡(luò)。 b 層次模式（層次并列） 1 ）teen和apteen 在leach基礎(chǔ)上，teen（閾值敏感的高效率能源的傳感器網(wǎng)絡(luò)協(xié)議） 9 兩次分組集群傳感器節(jié)點，以檢測現(xiàn)場突然發(fā)生變化的遙感屬性，如溫度。集群形成以后，teen將簇頭分離成雙層簇頭，并使用硬閾值和軟閾值來檢測突然變化。硬閾值用來觸發(fā)傳感器節(jié)點，在分布式的感應(yīng)值回應(yīng)數(shù)據(jù)查詢時；當傳感式分布中很少或根本沒有變化值時，軟閾值將進一步減少傳輸數(shù)量。 teen不適合于需要定期報告的應(yīng)用模式。 apteen （自適應(yīng)閾值敏感節(jié)能傳感器網(wǎng)絡(luò)協(xié)議）在其基礎(chǔ)上進行了改進，旨在支持時間要求嚴格的事件進行定期報告。兩種算法的主要缺

16、點是超過開支和形成集群的復(fù)雜性。 2 ）基于集群的網(wǎng)絡(luò)的能源敏感 該算法 10 也是leach的改進，介紹了一種資源無限網(wǎng)關(guān)節(jié)點。通過兩個級別組的方式，網(wǎng)關(guān)節(jié)點可以聚集數(shù)據(jù)和改變節(jié)點的狀態(tài)：休眠，遙感或中繼符合檢測傳感器節(jié)點的能量。 為了克服模棱兩可的信號傳播或獲得更好的路由性能，根據(jù)網(wǎng)絡(luò)吞吐量和端到端的延遲，提出許多路由方法的變量。由于空間有限，在這里我們不逐一分析。 五 基于定位的路由（物理協(xié)議） 這些算法需要傳感器節(jié)點的位置信息。我們假定傳感器節(jié)點可以直接獲得他們的位置或根據(jù)其他已知節(jié)點的位置計算距離。值得指出的是，在ad hoc網(wǎng)絡(luò)中有許多基于定位的協(xié)議，當我們以某些方式為無線傳感器網(wǎng)

17、絡(luò)移植研究成果，這種算法的影響很大。 a gear（地理和能源感知路由） 這樣做是為了限制利益在定向擴散中的數(shù)量，并添加地理信息到利息數(shù)據(jù)包，只需要考慮某一地區(qū)而不是以泛洪的方式發(fā)送利益到整個網(wǎng)絡(luò)。gear 11 利用能源感應(yīng)，地理性地通知相關(guān)選擇，啟發(fā)路由數(shù)據(jù)包向目標區(qū)域。因此用這種方式gear能大大節(jié)省能源消耗 。gear引進了估計成本和學(xué)習(xí)費用，并通過計算估計費用和學(xué)習(xí)費用之間的差價來選擇下一跳躍。 b mecn （最低能源通信網(wǎng)） mecn 12 起先是專為無線網(wǎng)絡(luò)設(shè)計，后來研究人員發(fā)現(xiàn)它也可以直接應(yīng)用于wsns。注意到兩個節(jié)點直接通信的成本高于幾個中繼節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的成本。所以mecn

18、為每個節(jié)點確定了中繼區(qū)域，其中包括所有中繼節(jié)點，比直接傳輸具有更高的能源效率。當兩個節(jié)點需要交流信息時， mecn將根據(jù)貝爾曼-福特最短路徑的方法選擇一個最小的能量路徑來傳輸數(shù)據(jù)。 因此， mecn是自我改造，并可以動態(tài)地解決節(jié)點的故障問題或部署新的傳感器。然而，該算法是最適用于非移動的傳感器網(wǎng)絡(luò)，流動性wsns情況下 ，中繼地區(qū)計算路徑的能源成本將大幅上升。 存在著許多其他基于定位的路由協(xié)議，如gedir、 goafr和span，可直接應(yīng)用于無線傳感器網(wǎng)絡(luò)。然而出于篇幅和內(nèi)容的限制，這些算法在本文中將不予討論。 六 結(jié)論和遺留的問題 近年來，wsns路由協(xié)議已經(jīng)成為研究領(lǐng)域一個最重要的議題，

19、并已存在了大量的研究成果。在本文中，我們提出了大量的分析和研究，并根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)進行分類，將路由協(xié)議分為三類：平面路由（泛洪） 、分層路由（聚類）和基于定位的路由（地理）。還有從其他角度展開的一些研究人員，給出其他類型的分類，我們出于篇幅和內(nèi)容限制在這里不予討論。盡管如此，關(guān)于wsns路由協(xié)議仍然存在著一系列的挑戰(zhàn)。 正如我們的研究顯示，一個路由算法不可能適用于所有情況和所有應(yīng)用程序。雖然針對wsns提出了許多路由協(xié)議，很多問題仍然存在，傳感器網(wǎng)絡(luò)依然有許多挑戰(zhàn)需要解決。以下部分描述了一些問題和挑戰(zhàn)： 效果：針對具體應(yīng)用，如何有效地利用帶寬和能源；如何有效地將整個網(wǎng)絡(luò)進行分組和協(xié)調(diào)所有傳感器節(jié)點

20、的工作量。 適應(yīng)性：如何適應(yīng)移動的傳感器網(wǎng)絡(luò)，使傳感器節(jié)點能自組織和自重構(gòu)。 可伸縮性：如何讓大量的節(jié)點滿足高密集的傳感器網(wǎng)絡(luò)，并延長壽命。 安全性：如何使wsns路由協(xié)議安全，保證傳播的信息不會被竊聽和篡改。 參考文獻 1 i. akyildiz, w. su, y. sankarasubramaniam, and e. cayiri, “a survey on sensor networks,” ieee communications magazine, vol.40, issue:8 pp. 102-114, august 2002. 2 s. hedetniemi, a. liestm

21、an. “a survey of gossiping and broadcasting in communication networks. networks,” 1988, 18(4): 319349. 3 w. heinzelman, j. kulik, h. balakrishnan. “adaptive protocols for information dissemination in wireless sensor networks,” proc. 5th acm/ieee mobicom conference (mobicom99), seattle, wa, august, 1

22、999, 174185. 4 d. braginsky, d. estrin, “rumor routing algorithm for sensor networks. in the proceedings of the first workshop on sensor networks and applications (wsna),” atlanta, ga, october 2002. 5 r. shah, j. rabaey, “energy aware routing for low energy ad hoc sensor networks,” in the proceeding

23、s of the ieee wireless communications and networking conference (wcnc), orlando, fl, march 2002. 6 c. schurgers, m.b. srivastava, “energy efficient routing in wireless sensor networks,” in the milcom proceedings on communications for network-centric operations: creating the information force, mclean

24、, va, 2001. 7 heinzelman, wendi b., anantha p. chandrakasan, hari balakrishnan, “an application-specific protocol architecture for wireless microsensor networks,” ieee transactions on wireless communications 1, 2002. no. 4. 8 s. lindsey, c. s. raghavendra, “pegasis: power efficient gathering in sensor information systems,” in the proceedings of the ieee aerospace conference, big sky, montana, march 2002. 9 a. manjeshwar, d. p. agrawal, “teen: a protocol for enhanced efficiency in wireless sensor networks,” in