1、WSN中的路由協議1.WSN的體系結構2.路由協議的定義3.WSN的特點及對路由設計的影響4.路由協議的關鍵問題分析5.路由協議的分類6.典型路由協議及其比較7.WSN的OS,tinyos和nesc8.舉例：Tinyos中的multi-hop routing LEPS協議實現9.程序分析:LEPS-FMACPPT構成WSN的體系結構Node有四個基本組件構成sensing unitprocessing unit Transceiver unitpower unit可能有的取決于應用程序需要的組件location finding system：許多路由技術和傳感任務需要精確獲悉節點位置power

2、 generator：在特定狀況下需要提供長時間的電源支持Mobilizer：需要移動節點到另一個地方執行指定的任務The sensor networks protocol stackphysical layer實現簡單、強壯的數據調制，發送、接收MAC層考慮節點的通信環境噪聲和節點的移動，且需要降低能量消耗，最小化和鄰居節點的廣播沖突.負責數據成幀，幀檢測，媒體訪問控制和差錯控制network layer路由生成和路由選擇transport layer數據流傳輸控制，是保證通信服務質量的重要部分application layer根據傳感任務的不同，可以建立不同的applicationpowe

3、r management plane管理傳感器節點如何使用能源，各個協議層都要考慮節省mobility management plane監測并注冊傳感器節點的移動，維護到匯聚節點的路由，使node能動態跟蹤其鄰居節點的位置task management plane在一個給定的區域內平衡和調度監測任務 路由協議是WSN的關鍵技術之一，它負責將數據分組從源節點通過網絡轉發到目的節點 主要包括兩個方面的功能： 尋找源節點和目的節點的優化路徑 將數據分組沿著優化路徑正確轉發路由協議與有線網絡和蜂窩式無線網絡不同，WSN中沒有基礎設施和全網統一的控制中心在這種無中心的環境下，路由可以看成分布式地獲取網絡

4、拓撲信息，以一定準則計算路徑并對路徑進行維護的過程。 網絡特點是路由設計的主要依據，對網絡特點的分析是進行協議設計的前提WSN的特點及對路由設計的影響 無線傳感網絡中，網絡業務的最大特點是具有明顯的方向性。 為了實現信息采集的目的，WSN的網絡業務大都發生在數據匯聚節點（sink）和普通的傳感器節點之間，包括sink節點到傳感器節點的下行業務（如查詢指令下達）和傳感器節點到sink的上行業務（如采集信息的回傳） 傳感器節點之間的橫向業務所占比例較小，主要是網絡的控制信息和網內信息處理所需要的信息。 無線傳感器網絡的一個基本理念是以大量低成本節點組網，通過節點之間的協作獲得比單一的高精度、高可靠

5、性和高成本的傳感器更好的信息采集效果。單個傳感器低能量和不可靠是無線傳感器網絡固有的，將對協議設計產生較大影響。從對路由協議設計影響的角度，歸納WSN的特點1.形式多樣的信息報告模式WSN中信息報告模式分三類：a.事件觸發：節點采集信息后判斷，若超過一定的閾值，則認為發生了某種事件， 需要立即上報，如用于預警的WSNb.周期的：節點定期把采集到的信息報告給sink。如野生動植物和環境監測WSNc.基于查詢：node不主動向sink上報采集到的信息，而是等待用戶查詢，根據用戶 需要反饋信息。d.混合模式：前三種的綜合。如智能交通的WSN不同的信息報告模式影響路由的觸發機制a.事件觸發模式：從節能

6、的角度，按需建立路由更恰當b.周期報告模式：采用先應式的方法建立路由更加合適c.基于查詢模式：查詢信息的本身就可以輔助建立路由2.多對一和一對多為主的業務模式 WSN的主要業務是傳感器節點把采集到的信息傳給sink和sink向WSN下達查詢命令，這是典型的多對一和一對多的模式。 為了支持這種通信模式，WSN中很多路由協議建立具有樹狀結構的路由此外還有“地域多播（geocast）”的業務模式WSN中，用戶可能對一個地理信息區域內的信息感興趣，因此需要把查詢和命令發送到該區域內的所有節點。以洪泛方式可以支持這種業務，但是開銷太大。針對這種模式設計了以下一些路由協議：LBM：基于位置的多播協議Vor

7、onoi diagram and convex hull based geocasting and routing：基于Voronoi圖和 基于凸包的地域多播協議GEAR: geographical and energy aware routing3.數據為中心的設計理念把WSN看成是一個大型的數據庫，用戶關心的是從這里得到什么信息，而不關心數據庫中的哪個元素（node）提供了該信息 該理念對網絡層的一個重要影響是節點的地址分配 一般情況下沒必要為每個node分配全局唯一地址，node描述信息產生時間，地點和內容即可，統一編址，對大規模WSN開銷過大 特定情況，節點ID和位置具有一定綁定關系，

8、可用ID代替位置。如工業檢測WSN 從實現多跳通信的角度，需要在局部標識不同的節點。 該理念還影響分組轉發的過程 WSN中，原始數據可能存在一定的冗余，在滿足信息采集的要求前提下，可以在數據轉發過程中對其進行修改，甚至把多個分組合并成一個分組，從而降低能耗4.動態變化的網絡拓撲 大部分的WSN中節點并不移動，造成網絡拓撲變化的主要原因是節點的失效和存在不可靠性、非對稱鏈路。為了節能和延長網絡壽命，需要對網絡進行休眠調度，會在一定程度上增加網絡拓撲的動態性。在有些WSN中為了彌補節點失效造成的性能損失，進行再布設（re-deployment），也會使網絡拓撲發生變化。 有些WSN中的節點是可移動

9、的，如醫療監測WSN，候鳥遷徙WSN，網絡拓撲變化比較快5.能量受限、結構簡單的節點Node大都由電池供電，電池體積小，能量有限且難以更換許多場合需要WSN連續工作數年甚至更長。Node結構簡單，存儲、處理、通信能力低，單個節點可靠性差。要求協議盡可能簡單，具有容錯性6.密集布設的大規模網絡WSN通常密集布設大量節點，節點數量達到成千甚至上萬。同時節點的密度也很高，有的情況下可以達到20個/m這些使得協議的可擴展性變得十分重要1.能量有效性提高能量有效性是WSN從硬件設計到軟件開發都必須考慮的問題。從路由協議設計的角度有兩種思路提高能量有效性：a.節能：尋找節能路由，減少路由建立和維護的控制開

10、銷，提高路由可靠性b.能耗均衡：從空間上調度能量資源，使網絡中節點能量均衡消耗路由協議的關鍵問題分析2.可擴展性可擴展性是指網絡的性能不隨著網絡中節點的數量增加而有明顯的下降兩類重要策略：a.分層路由：網絡分成若干層，低一層的群首構成高一層的網絡。節點地位不同， 首為局部控制中心，負責群內路由、信道接入、休眠調度等；大多數節點作為 群成員其操作相對簡單，控制開銷較低b.地理路由：地理位置信息實際上體現節點間相對拓撲關系，利用這一信息路由 能很大程度上降低用于收集拓撲信息付出的開銷，提高協議的可擴展性 地理路由使用的前提是節點能獲得自己和目的節點的地理位置信息 對于節點有移動性，任意兩個節點之間

11、都可能進行通信的網絡，為獲得目的節點 位置信息需不斷更新位置信息，開銷較大，地理路由的優勢就不明顯3.數據傳輸可靠性數據傳輸的可靠性直接關系到WSN是否能給用戶提供準確、全面和可靠的信息，而WSN中節點無線通信能力弱，應用環境復雜，實際的鏈路質量比較低。如何保證數據傳輸的可靠性是WSN路由設計中的一個關鍵問題影響WSN數據傳輸可靠性原因：a.無線信道上的碰撞導致分組無法正確接收b.節點故障使路由不可用，導致分組丟失c.鏈路不可靠，導致分組傳輸出錯或丟失路由協議的解決策略：a.建立多路徑路由：建立信源節點到目標節點的多條路徑，選擇最優路徑作為主路徑，其他路徑為備份使用多條路徑發送原始分組的多個副

12、本，即使其中一些傳輸丟失也不會影響端到端 的可靠性b.選擇可靠鏈路幾十種WSN路由協議，未統一分類標準一種分類方法（5類）：路由協議的分類1.基于聚簇的路由協議 LEACH, PEGASIS, TEEN等2.基于地理位置的路由協議 基于地理位置的距離貪心路由協議，基于地理位置的角度貪心路由協議，GEM,MAP, LCR等3.以數據為中心的路由協議 DD，Rumor-routing，TTDD，支持查詢的近似路由算法等4.能量感知路由協議 Energy aware routing，GEAR,等5.容錯路由協議 建立多條路徑，重復傳輸數據包，基于編碼的機會路由協議（MORE）等泛洪路由(Floodi

13、ng)擴散法(Flooding)是一種傳統的網絡路由協議，不需要知道網絡拓撲結構和使用任何路由算法典型的路由協議分析協議內容：一節點S希望發送一塊數據給節點D，節點S首先通過網絡將數據副本傳送給它的每一個鄰居節點，每一個鄰居節點又將其傳輸給各自的每一個鄰居節點，除了剛剛給它們發送數據副本的節點S外。如此繼續下去，直到將數據傳輸到目標節點D為止或者為該數據所設定的生命期限（在傳感器網絡里面通常定義為最大跳數）變為零為止或者所有節點擁有此數據副本為止。洪泛路由（Flooding）的優點：實現簡單不需要為保持網絡拓撲信息和實現復雜的路由發現算法而消耗計算資源適用于健壯性要求高的場合。洪泛路由（Flo

14、oding）的不足：存在信息爆炸(Implosion)問題，即出現一個節點可能得到一個數據多個副本的現象出現部分重疊(Overlap)現象，如果處于同一觀測環境的兩個相鄰同類傳感器節點 同時對一個事件作出反應，二者采集的數據性質相同，數值相近，那么，這兩個節 點的鄰居節點將收到雙份數據副本盲目使用資源，即擴散法不考慮各節點能量可用狀況因而無法作出相應的自適應 路由選擇。洪泛路由（Flooding）的應用情況：網絡資源過于浪費，實際很少直接采用具有極好的健壯性，可用于軍事應用作為衡量標準評價其它路由算法Gossiping路由協議：Gossiping協議是對Flooding協議的改進,節點將產生或

15、收到的數據隨機轉發給一個或者若干個相鄰節點,避免了內爆,但增加了時延，且無法避免重疊問題。SPIN協議（sensor protocol for information via negotiation）SPIN是最早的以數據為中心的自適應路由協議，通過協商機制來解決洪泛算法中的“內爆”和“重疊”問題，節省了能量的消耗。a.為了避免出現擴散法的信息爆炸問題和部分重疊現象，傳感器節點在傳送數據之前彼此進行協商，協商制度可確保傳輸有用數據b.節點間通過發送元數據(即描述傳感器節點采集的數據屬性的數據，meta-data)，而不是采集的整個數據進行協商。由于元數據大小小于采集的數據，所以，傳輸元數據消耗

16、的能量相對較少。為避免盲目使用資源，所有傳感器節點必須監控各自的能量變化情況。c.在傳輸或接收數據之前，每個節點都必須檢查各自可用的能量狀況，如果處于低能量水平，必須中斷一些操作，比如充當路由器的角色，停止對其他節點的一些數據轉發操作SPIN協議簇有4種不同的形式：SPIN-PP（A 3-Stage Handshake Protocol for Point-to-Point Media）： 適合點對點信道SPIN-EC（SPIN-PP with a Low-Energy Threshold）： 在SPIN-PP基礎上增加了能量限制SPIN-BC（A 3-Stage Handshake Prot

17、ocol for Broadcast Media）： 適合于廣播信道SPIN-RL（SPIN-BC for Lossy Network）：考慮信道上存在分組丟失d. SPIN有3種數據包類型，即ADV、REQ和DATA.節點用ADV宣布有數據發送，用REQ請求希望接收數據，用DATA封裝數據ADV：用于新數據廣播。當一個節點有數據可共享時，它可用ADV數據包(包含元 數據)對外廣播REQ：用于請求發送數據。當一個節點希望接收DATA數據包時，發送REQ數據包DATA：包含附上元數據頭(meta-data header)的傳感器采集的數據的數據包SPIN-PP采用點到點的通信模式，并假定兩節點間

18、的通信不受其他節點的干擾，分組不會丟失，功率沒有任何限制1.在發送一個DATA數據包之前，一個傳感器節點首先對向鄰居節點廣播ADV數據包；2.如果一個鄰居節點在收到ADV后有意愿接收該DATA數據包，那么它向該節點發送 一個REQ數據包，接著節點向該鄰居節點發送DATA數據包。3.類似地進行下去，DATA數據包可被傳輸到遠方匯節點或基站。SPIN-EC在SPIN-PP的基礎上考慮了節點的功耗，只有能夠順利完成所有任務且能量不低于設定閾值的節點才可參與數據交換SPIN-BC設計了廣播信道，使所有在有效半徑內的節點可以同時完成數據交換。為了防止產生重復的REQ請求，節點在聽到ADV消息以后，設定一

19、個隨機定時器來控制REQ請求的發送，其他節點聽到該請求，主動放棄請求權利SPIN-RL它是對SPIN-BC的完善，主要考慮如何恢復無線鏈路引入的分組差錯與丟失。記錄ADV消息的相關狀態，如果在確定時間間隔內接收不到請求數據，則發送重傳請求，重傳請求的次數有一定的限制SPIN協議的優點：1.小ADV消息減輕了內爆問題;2.通過數據命名解決了交疊問題；3.節點根據自身資源和應用信息決定是否進行ADV通告，避免了資源利用盲目問 題，有效地節約了能量。SPIN協議的不足：在傳輸新數據的過程中，直接向鄰居節點廣播ADV數據包，而沒有考慮其所有鄰居節點由于自身能量的原因，不愿承擔起轉發新數據的功能，則新數

20、據無法傳輸，將會出現“數據盲點”，進而影響整個網絡信息的收集MTE(Minimum Transmission Energy)路由協議：在MTE協議中，節點選擇離自己平面距離最近的節點進行路由中轉當且僅當如下公式滿足時，節點A將會選擇B轉發自己的數據到節點C右圖為MTE協議示意圖MTE路由協議的優點：簡單、開銷小，每個節點只需要找到通往Sink節點的下一跳節點，然后把數據發給它MTE路由協議的不足：靠近Sink節點的傳感器節點會一直承擔路由器的角色，節點之間負載不平衡，靠近Sink節點的傳感器節點可能很快就耗盡自己的能源而死亡，縮短整個網絡的生命周期DD（Directed Diffusion）定

21、向擴散路由協議：Directed Diffusion是一種以數據為中心的路由協議，與已有的路由協議有著截然不同的實現機制，其突出特點是引入了梯度來描述網絡中間節點對該方向繼續搜索獲得匹配數據的可能性。DD協議內容：節點用一組來命名它所生成的數據。1.建立路由時，sink節點flooding包含屬性列表、上報間隔、持續時間、地理區域等 信息的查詢請求Interest （該過程本質上是設置一個監測任務，通過分配不同屬性 值來表示不同任務的描述符）。2.每個傳感器節點在收到嗜好（Interest）后保存在各自的Cache中。每個嗜好項 (interest entry)包含一個時間標簽域(timest

22、amp field)和若干個梯度域(gradient field， 按成本最小化和能量自適應原則引導數據擴散的方向)。3.當一個嗜好傳遍整個網絡后，從源節點(即嗜好所在區域的傳感器節點)到sink節點 或基站之間的梯度就建立起來了。4.一旦源節點采集到嗜好所需的數據，那么源節點沿著該嗜好的梯度路徑傳輸數據到 sink節點或基站。其中，源節點采集的數據首先在本地采用數據融合技術進行整合， 然后在網上傳輸。右圖描述DD路由協議的工作原理在Directed Diffusion中，可以對路徑進行修復。在建立多條數據源到Sink節點的路徑之后，Sink節點可以選擇增強其中的一條路徑用于數據的傳輸，而同時

23、保持另外一條低速數據傳輸的路徑。當高速路徑，也就是經過增強的路徑出現故障時，Sink節點可以增強低速路徑，保證源節點到Sink節點的數據傳輸。雖然保持低速路徑的過程需要消耗一些能量，但是在故障時，可以節省很多能量開銷。對于故障比較頻繁的網絡，保持一條低速路徑是很有好處的。DD與SPIN的最大區別：DD采用基于需求的數據查詢機制。在DD中，由Sink節點發出數據查詢請求，而在SPIN中，節點廣播自己的數據，以允許其他節點來查詢。DD路由協議的優點：1.采用多路徑,健壯性好;2.節點只需要和鄰居節點通信，因而不需要全局的地址機制，使用查詢驅動機制按 需建立路由,避免了保存全網信息；3.每個節點都可

24、以進行數據融合操作，能減少數據通信量，節省能量消耗；4.sink點根據實際情況采取增強或減弱方式能有效利用能量；5.節點不需要維護網絡的拓撲結構，數據的發送是基于需求的，因此它是一個非常 節能的路由協議。DD路由協議的優點：1.基于查詢驅動模型的，不適用于環境監測的WSN；2.Gradient的建立開銷很大,不適合多sink點網絡；3.數據聚合過程采用時間同步技術,會帶來較大開銷和時延；4.不同的應用中需要定義不同的命名方案，也就是對，從而限制了它 的應用。Rumor 路由協議（謠傳路由）：Rumor Routing是在Directed Diffusion的基礎上演化而來的。通常情況下，Dir

25、ected Diffusion協議需要向整個網絡廣播興趣，而在某些應用中，只有少量的數據需要從源節點傳遞到Sink節點。在這種情況下，沒有必要向整個網絡廣播興趣。當WSN中的事件（對應著數據的傳遞）數量很少，而查詢（對應著興趣的廣播）數量很多的時候，可以采用廣播事件的方法，以節省能量的消耗。Rumor Routing是一個介于事件廣播（向整個網絡廣播事件）和興趣廣播（向整個網絡廣播興趣）之間的一種路由協議Rumor Routing核心思想：1.借鑒了歐氏平面圖上任意兩條曲線交叉幾率很大的思想2.當節點監測到事件后將其保存，并創建稱為Agent的生命周期較長的包括事件和 源節點信息的數據包，將其

26、按一條或多條隨機路徑在網絡中轉發3.收到Agent的節點根據事件和源節點信息建立反向路徑，并將Agent再次隨機發 送到相鄰節點，并可在再次發送前在Agent中增加其已知的事件信息4.sink點的查詢請求也沿著一條隨機路徑轉發,當兩路徑交叉時則路由建立5.如不交叉,sink點可flooding查詢請求 Rumor協議中Agent傳播和Agent路徑與查詢路徑的交叉在多sink點、查詢請求數目很大、網絡事件很少的情況下，Rumor協議較為有效.但如果事件非常多,維護事件表和收發Agent帶來的開銷會很大。GPSR(Greedy Perimeter Stateless Routing)路由協議：G

27、PSR協議核心思想：GPSR協議是一個典型的基于位置的路由協議。使用GPSR協議，網絡節點都知道自身地理位置并被統一編址，各節點利用貪心算法盡量沿直線轉發數據。產生或收到數據的節點向以歐氏距離計算最靠近目的節點的鄰節點轉發數據，但由于數據會到達沒有比該節點更接近目的點的區域(稱為空洞)，導致數據無法傳輸，當出現這種情況時，空洞周圍的節點能夠探測到，并利用右手法則沿空洞周圍傳輸來解決此問題 空洞出現和繞開空洞GPSR協議優點：1.避免了在節點中建立、維護、存儲路由表，只依賴直接鄰節點進行路由選擇， 幾乎是一個無狀態的協議；2.使用接近于最短歐氏距離的路由，數據傳輸時延小;并能保證只要網絡連通性不

28、 被破壞，一定能夠發現可達路由。GPSR協議的不足：1.當網絡中sink點和源節點分別集中在兩個區域時，由于通信量不平衡易導致部分 節點失效，從而破壞網絡連通性；2.需要GPS定位系統或其他定位方法協助計算節點位置信息。TBF（Trajectory based forwarding）路由協議：TBF路由協議核心思想：1.TBF是一個基于源站和基于位置的路由協議.與GPSR協議不同,TBF協議不是沿著 最短路徑傳播2.與通常的源站路由協議不同,TBF協議利用參數在數據包頭中指定了一條連續的傳 輸軌道而不是路由節點序列3.網絡節點利用貪心算法根據軌道參數和鄰節點位置,計算出最接近軌道的鄰節點 作為

29、下一跳節點TBF協議的優點：1.可利用GPSR協議的方法或其他方法避開空洞;2.通過指定不同的軌道參數,很容易實現多路徑傳播、廣播、對特定區域的廣播 和多播;3.源站路由避免了中間節點存儲大量路由信息;4.指定軌道而不是節點序列,數據包頭的路由信息開銷不會隨著網絡變大而增加, 允許網絡拓撲變化,避免了傳統源站路由協議的缺點TBF路由協議的不足：1.隨著網絡規模變大,路徑加長,沿途節點進行計算的開銷也相應增加2.需要GPS定位系統或其他定位方法協助計算節點位置信息下圖是TBF協議沿著任意曲線傳輸數據 多路徑傳播 廣播 對特定區域的廣播 多播能量感知路由協議（shah等人提出）：Shah協議的核心

30、思想：1.協議的目的主要在于改善Directed Diffusion協議的耗能情況，采用地理位置和數 據類型(即節點類型)標識節點。2.Shah等人認為該協議是按需路由協議，但其含義更多的是查詢驅動的，我們將其 與Directed Diffusion都列為主動路由協議。3.sink節點(Cost(sink)=0)利用受控的flooding發起建立路由請求，產生或轉發路由請 求節點Ni的所有鄰節點Nj測量與Ni的通信開銷以及Ni的剩余能量:Metric(Nj,Ni)。4.Nj根據式(a)計算代價 Nj節點選擇其較小的一些鄰節點反向構造路由表FTj。5.鄰節點Ni被賦予由式(b)計算的路由概率 6

31、.此后Nj節點由式(c)計算自身代價Cost(Nj)7.然后，Nj轉發包含自身代價信息的請求。在通信階段,節點Nj根據 選擇一條 路徑進行數據發送,Nj NiC,Nj NiP,Nj NiPShah路由協議的優點：1.與Directed Diffusion相比,該協議雖然存在多條路徑,但只選用一條,能夠有效節約 能源40%以上;2.隨機選擇路由方式平衡了通信量Shah路由協議的不足：1.sink點需要周期性flooding維護路由信息;2.需要進行節點間收發開銷和剩余能量測量;4.根據概率隨機選擇一條路徑導致其可靠性不如Directed Diffusion協議.LEACH（Low-Energy

32、Adaptive Clustering Hierarchy）路由協議：LEACH是一種基于聚類(Clustering)路由協議，在WSN路由協議占有重要地位，其他基于聚類的路由協議如TEEN、APTEEN、PEGASIS等大都由LEACH發展而來LEACH路由協議的核心思想：1.LEACH協議分為兩個階段操作，即類準備階段(set-up phase)和就緒階段(ready phase)。為了使能耗最小化，就緒階段持續的時間比類準備階段長。類準備階段 和就緒階段所持續的時間總和稱為一輪(round)2.在類準備階段，LEACH協議隨機選擇一個傳感器節點作為類頭節點(cluster head no

33、de)，隨機性確保類頭與基站之間數據傳輸的高能耗成本均勻地分攤到所有傳感 器節點。3.具體的選擇辦法是：一個傳感器節點隨機選擇 0和1之間的一個值，如果選定的值小于某一個 閾值T(n)，那么這個節點成為類頭節點。 T(n)值按右邊公式計算：N：網絡中傳感器節點的總數；p：一輪中網絡的類頭節點數；r：己完成的輪數；Gr：在剩余的N/k-r個回合中未成為類頭節點的傳感器節點組成的集合；4.在類頭節點選定后，該類頭節點對網絡中所有節點進行廣播，廣播數據包含有該節 點成為類頭節點的信息。一旦傳感器節點收到廣播數據包，根據接收到的各個類頭 節點廣播信號強度，該節點選擇信號強度最大的類頭節點加入，向其發送

34、成為其成 員的數據包。類形成后，類頭節點采用TDMA策略分配通道使用權給類內節點。5.一旦處于就緒階段，類頭節點開始接收類內各節點采集的數據，然后采用數據融合 和數據壓縮等技術進行匯聚，將整合后的數據傳輸給Sink節點。在就緒階段持續了 一段時間后，網絡又進入了另一次的類準備階段。LEACH路由協議模型LEACH協議的優點：隨機選擇簇頭，平均分擔路由業務，減小了能耗LEACH協議的不足：不適合大范圍的應用；集群分組方式帶來了額外開銷以及覆蓋問題僅適用于每個節點在單位時間內需要發送的數據量基本相同的情況，而不適合 突發數據通信。PEGASIS（power-efficient gathering

35、in sensor information system）協議PEGASIS由LEACH發展而來，它是LEACH協議的一種改進版本，仍然采用動態選舉簇頭的思想,但為避免頻繁選舉簇頭的通信開銷,采用無通信量的簇頭選舉方法,且網絡中所有節點只形成一個簇,稱為鏈.該協議要求每個節點都知道網絡中其他節點的位置,通過貪心算法選擇最近的鄰節點形成鏈.動態選舉簇頭的方法:設網絡中N個節點都用1N的自然數編號,第j輪選取的簇頭是第i個節點,i=j mod N(i為0時,取N).簇頭與sink點一跳通信,利用令牌控制鏈兩端數據沿鏈傳送到簇頭本身,在傳送過程中可聚合數據.當鏈兩端數據都傳送完成時,開始新一輪選舉與

36、傳輸。PEGASIS的基本原理：PEGAGIS假定組成網絡的傳感器節點是同構和靜止的。節點發送能量遞減的測試信號，通過檢測應答來確定離自己最近的相鄰節點。通過這種方式，網絡中的所有節點能夠了解彼此的位置關系，進而每個節點依據自己的位置選擇所屬的聚類，聚類的簇頭參照位置關系優化計算出到sink節點的最佳鏈路。右圖為PEGAGIS中的聚類由于節點了解彼此的位置信息，因而可以形成到簇頭節點的最佳鏈路。圖中，節點N1到N5都采集到相關的數據需要發送給簇頭節點，節點N1可以將數據發送給N2，N2收到后將其與本身采集的數據進行數據融合操作，然后發送給N5，同樣的N3將數據發送給N4，N4融合后將數據發送給

37、N5，N5收到N2和N4的數據后，和自己的數據進行融合，然后發送給簇頭，簇頭然后將數據發送給Sink節點。PEGASIS的優點：不需要周期性地動態選擇簇頭節點，采用最佳鏈路進行數據傳輸，并且采用數據融合技術減少了數據的發送和接收，因此，整個網絡的功耗比LEACH要小很多。研究結果表明，PEGASIS支持的傳感器網絡的生命周期是LEACH的近兩倍。PEGASIS的不足：1.節點維護位置信息（相當于傳統網絡中的拓撲信息）需要額外的資源；2.固定不變的簇頭使得簇頭成為關鍵點，其失效會導致路由失??；3.且要求節點都具有與sink點通信的能力；4.如果鏈過長，數據傳輸時延將會增大，不適合實時應用；5.成

38、鏈算法要求節點知道其他節點位置，開銷非常大。TEEN（threshold sensitive energy efficient sensor network protocol）協議：TEEN協議是一個層次路由協議，利用過濾方式來減少數據傳輸量TEEN協議的基本原理：1.采用與LEACH協議相同的聚簇方式,但簇頭根據與sink點距離的不同形成層次結構2.聚簇完成后,sink點通過簇頭向全網節點通告兩個門限值(分別稱為硬門限和軟門限) 來過濾數據發送3.在節點第1次監測到數據超過硬門限時,節點向簇頭上報數據,并將當前監測數據保 存為監測值(sensed value,簡稱SV)4.此后只有在監測到的

39、數據比硬門限大且其與SV之差的絕對值不小于軟門限時,節點 才向簇頭上報數據,并將當前監測數據保存為SV。TEEN協議中由聚簇構成的層次結構TEEN協議的優點：1.通過利用軟、硬門限減少了數據傳輸量,且層次型簇頭結構不要求節點具有大功率 通信能力2.數據傳送量比主動網絡少，節省大量能源。適用于響應型(Reactive)應用TEEN協議的不足：如果某個節點的檢測數據始終達不到硬門限，用戶將無法得到任何數據，也無法知道這個節點是否失效，因此這個方法不適用于需周期性采樣的網絡。TTDD（two-tier data dissemination ）路由協議：TTDD協議是一個層次路由協議,主要是解決網絡中

40、存在多sink點及sink點移動問題TTDD協議的基本原理：1.當多個節點探測到事件發生時,選擇一個節點作為發送數據的源節點,源節點以自 身作為格狀網(grid)的一個交叉點構造一個格狀網.2.其過程是:源節點先計算出相鄰交叉點位置,利用貪心算法請求最接近該位置的節 點成為新交叉點；3.新交叉點繼續該過程直至請求過期或到達網絡邊緣.4.交叉點保存了事件和源節點信息.進行數據查詢時,sink點本地flooding查詢請求到 最近的交叉節點,此后查詢請求在交叉點間傳播,最終源節點收到查詢請求,數據反 向傳送到sink點.Sink點在等待數據時,可繼續移動,并采用代理(Agent)機制保證數 據可靠

41、傳遞下圖為TTDD格狀網建立與數據查詢 源節點B發起建立格狀網 Sink點向源節點B查詢數據TTDD協議的優點：與Directed Diffusion協議相比,該協議采用單路徑,能夠提高網絡生存時間TTDD協議的不足：1.計算與維護格狀網的開銷較大;2.節點必須知道自身位置;3.非sink點位置不能移動;4.要求節點密度較大SAR路由協議：SAR協議是第1個在WSNs中保證QoS的主動路由協議SAR路由協議的基本原理：1.sink點的所有一跳鄰節點都以自己為根創建生成樹2.在創建生成樹過程中考慮節點的時延、丟包率等QoS參數以及最大數據傳輸能力3.各個節點從而反向建立了到sink點的具有不同Q

42、oS參數的多條路徑4.節點發送數據時選擇一條或多條路徑進行傳輸SAR路由協議的優點：能夠提供QoS保證SAR路由協議的不足：1.節點中的大量冗余路由信息耗費了存儲資源2.路由信息維護、節點QoS參數與能耗信息的更新均需較大開銷最大化生存時間路由協議（chang etl al）：最大化生存時間路由協議由Chang等人提出，與Shah等人的思想有相似之處,認為最小化傳輸能量并不完全適合WSNs,必須考慮網絡的生存時間最大化生存時間路由協議的基本原理：1.根據節點剩余能量與鏈路發送數據能量要求定義代價函數2.最重要的貢獻在于,利用網絡流建模,采用線性規劃方法來解決最大生存時間問題: 定義代價函數為f

43、(eij,Ei),其中eij是節點i,j發送數據消耗的能量,Ei是節點i剩余的能 量,代價函數是關于eij的增函數、Ei的減函數.最大化生存時間路由協議的評價：數據流在傳輸過程中動態改變流向以達到最大化網絡生存時間,但需要知道各個節點的數據產生速率TinyOS Beaconing路由協議：TinyOS Beaconing路由協議較為簡單1.首先對節點進行編址2.sink點周期性flooding路由更新消息3.信號覆蓋范圍內的節點接收到更新消息后,將發送消息的節點作為父節點保存到 路由表中,然后將該消息在物理信道上廣播,從而構成了一個以sink點為根的廣度 優先的生成樹 TinyOS Beaco

44、ning協議的路由生成樹建立過程TinyOS Beaconing路由協議的優點： 在小規模網絡中簡單、易用TinyOS Beaconing路由協議的不足：1.在較大網絡中將導致節點和sink點間跳數增加;2.廣播式路由更新消息消耗網絡能量;3.路徑建立只與接收到beaconing的時序有關,不進行任何優化,擴展性差;4.sink點周圍的節點由于過多地參與數據傳輸,耗能較多,容易失效最小代價路由協議（Ye et al）：Ye等人提出的最小代價路由協議與很多協議的思想相同,以跳數或能耗作為代價尺度,最終達到最小化代價的目的,其特別之處在于采用退避算法進行代價通告最小代價路由協議的基本原理：1.在初始階段,除sink點將自身代價設為0以外