第五章無線傳感網路由協議

路由協議是解決數據傳輸路徑問題，它完成將數據分組從源節點轉發到目的節點的功能，是無線傳感網的關鍵技術之一。與傳統通信網絡不同，無線傳感網中沒有基礎設施和全網統一的控制中心，是一種分布式的自組織網絡，必須采取分布式的方式獲取網絡拓撲信息。由于無線傳感網是由大量的結構簡單的低成本、能量受限、通信能力受限以及存儲和處理能力受限的節點構成，網絡拓撲結構動態變化。所以，傳統的自組織網絡的路由協議不能直接使用，必須針對傳感網的特點和應用設計高能效的傳感網路由協議。本章針對傳感網的特點，分析了路由協議考慮的因素以及分類方式，分別介紹了能量感知路由協議、平面路由協議、分層路由協議、基于查詢的路由協議和基于地理位置路由協議。內容提要5.1概述5.2能量感知路由協議5.3平面路由協議5.4層次路由協議5.5基于查詢的路由協議5.6基于地理位置路由5.7本章小結思考題5.1概述5.1.1WSN路由協議的特點5.1.2路由協議的分類5.1.1WSN路由協議的特點無線傳感網路由協議負責將分組從源節點通過網絡轉發到目的節點，它主要包括兩個方面的功能：①尋找源節點和目的節點間的優化路徑；②將數據分組沿著優化路徑正確轉發。傳統無線網絡的目標：提供高服務質量和公平高效地利用網絡帶寬.因此這些網絡路由協議的主要任務是尋找源節點到目的節點間通信延遲小的路徑，同時提高整個網絡的利用率，避免產生通信擁塞并均衡網絡流量等，而能量消耗問題不是這類網絡考慮的重點。無線傳感網節點能量有限（一般由電池供電），并且由于網絡中節點數目往往過大，節點只能獲取局部拓撲結構信息，因此要求路由協議不僅要高效的利用能量，還要在此基礎上能夠在只獲取局部網絡信息的情況下選擇合適的路徑。5.1.1WSN路由協議的特點與傳統網絡的路由協議相比，無線傳感網路由協議具有以下的特點：（1）能量優先。傳統路由協議在選擇最優路徑時，很少考慮節點的能量消耗問題。而無線傳感網中節點的能量有限，延長整個網絡的生存期成為傳感網路由協議設計的重要目標，因此需要考慮節點的能量消耗以及網絡能量均衡使用的問題。（2）基于局部拓撲信息。無線傳感網為了節省通信能量，通常采用多跳的通信模式，而節點有限的存儲資源和計算資源，使得節點不能存儲大量的路由信息，不進行太復雜的路由計算。在節點只能獲取局部拓撲信息和資源有限的情況下，如何實現簡單高效的路由機制是無線傳感網的一個基本問題。（3）以數據為中心。傳統的路由協議通常以地址作為節點的標識和路由的依據，而無線傳感器網絡中大量節點隨機部署，所關注的是監測區域的感知數據，而不是具體哪個節點獲取的信息。用戶使用傳感網查詢事件時，直接將所關心的事件通告給網絡，而不是通告給某個確定編號的節點。網絡在獲得指定事件的信息后匯報給用戶。這種以數據本身作為查詢或傳輸線索的思想更接近于自然語言交流的習慣。所以通常又說傳感網是一個以數據為中心的網絡。（4）應用相關。傳感網的應用環境千差萬別，數據通信模式不同，沒有一個路由機制適合所有的應用，這是傳感網應用相關性的一個體現。5.1.2路由協議的分類1．按源節點獲取路徑策略劃分（1）主動路由協議。也叫表驅動(TableDriven)路由協議，主動路由的路由發現策略與傳統路由協議類似，節點通過周期性地廣播路由信息分組，交換路由信息，主動發現路由。節點必須維護去往全網所有節點的路由，并且每一個節點都要保存一個或更多的路由表來存儲路由信息。當網絡拓撲結構發生變化時，節點就在全網內廣播路由更新信息，這樣每一個節點就能連續不斷地獲得網絡拓撲信息。優點是只要目的節點路由存在，所需的延時就會很小。缺點是需要花費較大開銷，盡可能使得路由更新能夠緊隨當前拓撲結構的變化，浪費了一些資源來建立和重建那些根本沒有被使用的路由。（2）按需路由協議。也稱被動路由協議，只有在源節點需要發送數據到目的節點時，源節點才發起創建路由的過程。路由表的內容是按需建立的，它可能僅僅是整個拓撲結構信息的一部分，在通信過程中維護路由，通信完畢后便不再對其進行維護。按需路由的優點是不需要周期性的路由信息廣播，路由表僅僅是局部路由，因而節省了一定的網絡資源。缺點是發送數據分組時，如果沒有去往目的節點的路由，需要計算路由，因此時延較大。（3）混合路由協議：混合路由則綜合利用了主動和按需路由兩種方式。一般來說，對于經常被使用并且拓撲變化不大的網絡部分，可以采用主動路由的方式建立并維護相應的路由信息，而對于傳輸數據較少或拓撲變化較快的網絡部分，則采用按需路由的方式建立路由，以取得效用和時延的折中。5.1.2路由協議的分類2．按通信的邏輯結構劃分（1）平面路由協議：網絡中的所有節點的地位都是平等的，實現的路由功能也大致相同。當一個節點需要發送數據的時候，可能以其他節點為中繼節點進行轉發，最后到達目的節點。通常來說，在目的節點附近的節點參與數據中繼的概率要比遠離目的節點的節點參與數據中繼的概率高。因此，目的節點附近的節點由于過于頻繁地參與數據中繼，會較快地耗盡能量。所以，平面路由協議的優點是網絡中沒有特殊節點，網絡流量均勻地分散在網絡中，路由算法易于實現。缺點是可擴展性小，在一定程度上限制了網絡的規模。（2）層次路由協議：將若干個相鄰節點構成一個簇，每一個簇有一個簇首。簇與簇之間可以通過網關通信。網關可以是簇首也可以是其它簇成員。網關之間的連接構成上層骨干網，所有簇間通信都通過骨干網轉發。每個簇群內收集到的監控信息都交給簇首節點，簇首節點完成數據聚集和融合過程減少傳播的信息量。相比于其他路由協議，層次型路由協議能滿足傳感網的可擴展性需求，能有效地減少傳輸節點的能量消耗，從而延長網絡生命周期。但是，在此類協議中，簇首節點的能量消耗遠大于其他節點，因此其網絡協議需要采取選擇滿足條件的節點輪流擔當簇首節點的方法來均衡能耗。5.1.2路由協議的分類3．按路由的發現過程劃分（1）以位置信息為中心的路由協議：它利用節點的位置信息，把查詢或者數據轉發給需要的地域，從而縮小了數據的傳送范圍。許多傳感網的路由協議都假設節點的位置信息是已知的，所以可以方便地利用節點的位置信息將節點分為不同的域，并基于域進行數據傳送，能縮小傳送范圍，減少中間節點的能耗，從而延長網絡的生命周期。（2）以數據為中心的路由協議：它提出對傳感網中的數據用特定的描述方式命名，數據傳送基于數據查詢并依賴于數據命名，所有的數據通信都被限制在局部范圍內。這種通信方式不再依賴于特定的節點，而是依賴于網絡中的數據，從而減少了網絡中傳送的大量重復的冗余數據，降低了不必要的開銷，從而延長了網絡生命周期。另外，還可以按路由選擇是否考慮服務質量(QoS)約束來劃分，基于QoS的路由協議是指在路由建立時，考慮時延、丟包率等QoS參數，從多條可行的路由中選擇一條最適合QoS應用要求的路由。或者是根據業務類型，選擇能保證滿足不同業務需求的QoS路由協議。由于無線傳感網路由協議種類繁多，其分類方法也多種多樣，除了上述介紹的分類方法之外還有根據路徑數量、應用場合、數據傳輸方式等方法的劃分。5.2能量感知路由協議高效利用網絡能量是傳感網路由協議的一個重要特征。早期提出的傳感網路由協議，為了強調能量效率的重要性，往往僅僅考慮了能量因素，可以將它們劃分為能量感知路由協議，該協議從數據傳輸中的能量消耗出發，討論最優的能量消耗傳輸路經。5.2能量感知路由協議5.2.1能量路由5.2.2能量多路徑路由高效利用網絡能量是傳感網路由協議的一個重要特征。早期提出的傳感網路由協議，為了強調能量效率的重要性，往往僅僅考慮了能量因素，可以將它們劃分為能量感知路由協議，該協議從數據傳輸中的能量消耗出發，討論最優的能量消耗傳輸路經。5.2.1能量路由能量路由是最早提出的傳感網路由協議之一，它根據節點的可用能量（poweravailable，PA）或傳輸路徑上的能量需求，選擇數據的轉發路徑。節點可用能量就是節點當前的剩余能量。如圖5-1所示，網絡中的大寫字母表示節點符號，如節點A，節點右側括號內的數字表示節點的可用能量，如PA=2，表示節點A的能量為2，圖中的雙向線表示節點之間的通信鏈路，鏈路上的數字表示在該鏈路上發送數據消耗的能量。源節點是一般功能的傳感器節點，完成數據采集工作，匯聚節點是數據發送的目標節點。5.2.1能量路由從源節點到匯聚節點的可能路徑有：(1)路徑1：源節點—B—A—匯聚節點，所有節點PA之和為4，發送分組需要的能量之和為3；(2)路徑2：源節點—C—B—A—匯聚節點，所有節點PA之和為6，發送分組需要的能量之和為6；(3)路徑3：源節點—D—匯聚節點，所有節點PA之和為3，發送分組需要的能量之和為4；(4)路徑4：源節點—F—E—匯聚節點，所有節點PA之和為5，發送分組需要的能量之和為6。圖5-1能量路由算法示意圖5.2.1能量路由_能量路由策略

（1）最大PA路由：從數據源到匯聚節點的所有路徑中選取節點PA之和最大的路徑。在圖5-1中路徑2的PA之和最大，但路徑2包含了路徑1，因此不是高效的，從而被排除，選擇路徑4。（2）最小能量消耗路由：從數據源到匯聚節點的所有路徑中選取節點耗能之和最少的路徑。在圖5-1中選擇路徑1。（3）最少跳數路由：選取從數據源到匯聚節點跳數最少的路徑。在圖5-1中選擇路徑3。（4）最大最小PA節點路由：每條路徑上有多個節點，且節點的可用能量不同，從中選取每條路徑中可用能量最小的節點來表示這條路徑的可用能量。如路徑4中節點E的可用能量最小為1，所以該路徑的可用能量是1。最大最小PA節點路由策略就是選擇路徑可用能量最大的路徑。在圖5-1中選擇路徑3。5.2.2能量多路徑路由傳統網絡的路由機制往往選擇源節點到目的節點之間跳數最小的路徑傳輸數據，但在無線傳感網中，如果頻繁使用同一條路徑傳輸數據，就會造成該路徑上的節點因能量消耗過快而過早失效，從而使整個網絡分割成互不相連的孤立部分，減少了整個網絡的生存期。為了避免這種情況的出現。要盡可能地保證每個節點都有較為公平的機會成為路徑上的一環，各個節點在相對較長的時間內，能量消耗的比例一致。能量多路徑路由機制：就是在源節點和目的節點之間建立多條路徑，根據路徑上節點的通信能量消耗以及節點的剩余能量情況，給每條路徑賦予一定的選擇概率，使得數據傳輸均衡消耗整個網絡的能量，延長整個網絡的生存期。能量多路徑路由協議：包括路徑建立、數據傳播和路由維護三個過程。路徑建立過程是該協議的重點內容。每個節點需要知道到達目的節點的所有下一跳節點，并計算選擇每個下一跳節點傳輸數據的概率。概率的選擇是根據節點到目的節點的通信代價來計算的。因為每個節點到達目的節點的路徑很多，所以這個代價值是各個路徑的加權平均值。5.2.2能量多路徑路由（1）發起路徑建立過程目的節點向鄰居節點廣播路徑建立消息，啟動路徑建立過程。路徑建立消息中包含一個代價域，表示發出該消息的節點到目的節點路徑上的能量信息，初始值設置為0。（2）判斷是否轉發路徑建立消息當節點收到鄰居節點發送的路徑建立消息時，相對發送該消息的鄰居節點，只有當自己距源節點更近，而且距目的節點更遠的情況下，才需要轉發該消息，否則將丟棄該消息。（3）計算能量代價如果節點決定轉發路徑建立消息，需要計算新的代價值來替換原來的代價值。當路徑建立消息從節點Ni發送到節點Nj時，該路徑的通信代價值為節點的代價值加上兩個節點間的通信能量消耗，即：節點Nj到節點Ni的通信能量消耗（4）節點加入路徑條件節點要放棄代價太大的路徑，節點j將節點i加入本地路由表中的條件是：其中α為大于1的系統參數。（5）節點選擇概率計算節點為路由表中每個下一跳節點計算選擇概率，節點選擇概率與能量消耗成反比。節點使用如下公式計算選擇節點的概率：

（6）代價平均值計算節點根據路由表中每項的能量代價和下一跳節點選擇概率計算本身到目的節點的代價。其定義為經由路由表中節點到達目的節點代價的平均值，即：

節點Nj將用cos（Nj）值替換消息中原有的代價值，然后向鄰居節點廣播該路由建立消息。在數據傳播階段，對于接收的每個數據分組，節點根據概率從多個下一跳節點中選擇一個節點，并將數據分組轉發給該節點。路由的維護是通過周期性地從目的節點到源節點實施洪泛查詢來維持所有路徑的活動性。能量多路徑路由綜合考慮了通信路徑上的消耗能量和剩余能量，節點根據概率在路由表中選擇一個節點作為路由的下一跳節點。由于這個概率是與能量相關的，可以將通信能耗分散到多條路徑上，從而可實現整個網絡的能量均衡，最大限度地延長網絡的生存期。5.3平面路由協議5.3.1Flooding和Gosipping協議5.3.2SPIN協議5.3平面路由協議基于平面結構的路由協議是最簡單的路由形式，其中每一個點都具有對等的功能。其優點是不存在特殊節點，路由協議的魯棒性較好，通信流量被平均地分散在網絡中，而其缺點是缺乏可擴展性，限制了網絡規模。最有代表性的算法是泛洪Flooding算法、Gosipping以及SPIN算法。5.3.1Flooding和Gosipping協議1．洪泛路由協議洪泛路由協議（FloodingProtocol）是一種最早的路由協議，接收到消息的節點以廣播的形式轉發報文給所有的鄰居節點。如圖5-2所示，源節點S希望發送數據給目的節點D，首先要通過網絡將數據分組傳送給它的每一個鄰居節點，各個鄰居節點又將其傳播給各自的鄰居節點，直到數據遍歷全網或者達到規定的最大跳數。洪泛法的優點和缺點都十分突出。優點：是不用維護網絡拓撲結構和路由計算，實現簡單，適用于健壯性要求高的場合，缺點：是存在信息內爆、重疊以及資源盲點等問題，如圖5-2所示。1．洪泛路由協議——內爆圖5-2Flooding的“內暴”現象內爆現象：如圖5-2所示，節點S通過廣播將數據發送給自己的鄰居節點A、B和C，A、B和C又將同樣的數據包轉發給D，這種將同一個數據包多次轉發給同一個節點的現象就是內爆，這極大浪費節點能量。1．洪泛路由協議——重疊重疊現象：是無線傳感器網絡特有的，如圖5-3所示，節點A和B感知范圍發生了重疊，重疊區域的事件被相鄰的兩個節點探測到，那么同一事件被傳給它們共同的鄰居節點C多次，這也浪費能量。重疊現象是一個很復雜的問題，比內爆問題更難解決。圖5-3Flooding的“重疊”現象2.Gosipping協議--閑聊法閑聊法（Gossiping）是洪泛法的改進版本。為了減少資源的無謂消耗，閑聊法引入了隨機發送數據的方法。某一個節點發送數據時，不再像洪泛法那樣給它的每個鄰后節點都發送數據副本，而是隨機選擇某個鄰居節點，向它發送一份數據副本。接收到數據的節點采用相同的方法，隨機選擇下一個接收節點發送數據，如圖5-4所示。需要注意的是，如果一個節點已收到了它的鄰居節點B的數據副本，若再次收到，那么它會將此數據發回它的鄰居節點B。由于一般無線傳感網的鏈路冗余度較大，適當選擇轉發的鄰居數量，可以保證幾乎所有節點都可以接收到數據包。5.3.2SPIN協議基于信息協商機制的傳感網協議（SensorProtocolforInformationViaNegotiation,SPIN）是最早的—類無線傳感器路由協議的代表，它主要是對洪泛路由協議的改進。SPIN協議是一種以數據為中心的自適應路由協議。該協議考慮到了WSN中的數據冗余問題。臨近的節點所感知的數據具有相似性，通過節點間協商（Nagotiation）的方式減少網絡中數據的傳輸數據量。節點只廣播其他節點所沒有的數據以減少冗余數據，從而有效減少能量消耗。1．SPIN協議工作原理先介紹SPIN協議中的基本概念。①元數據（metedata）。元數據是原始感知數據的一個映射，用來描述原始感知數據。元數據所需的數據位比原始感知數據要小，采用這種變相的數據壓縮策略可以進一步減少通信過程中的能量消耗。②SPIN協議采用三次握手協議來實現數據的交互，協議運行過程中使用三種報文數據，分別為ADV、REQ和DATA。ADV:用于數據的廣播，當某一個節點有數據可以共享時，用ADV數據包通知其鄰居節點；REQ:用于請求發送數據，當某一個收到ADV的節點希望接收DATA數據包時，發送REQ數據包；DATA:為原始感知數據包，里面裝載了原始感知數據。③SPIN協議有兩種工作模式：SPIN1和SPIN2，SPIN2在SPIN1的基礎上作了一些能量上的考慮，本質上還是一樣的。SPIN1協議的工作過程(1)當節點A感知到新事件后，主動給其鄰居節點廣播描述該事件的元數據ADV報文.(2)節點B收到A的報文,檢查自己是否擁有ADV報文中所描述的數據，如果沒有的話，節點B就向A發送REQ報文，在REQ報文列出需要A節點給出的數據列表，如圖(b)。(3)當節點A收到了REQ請求報文，它就將相關的數據發送給節點B，如圖(c)。(4)節點B發送ADV報文通知其鄰居節點自已有新的消息，如圖(d).由于A節點中保存有ADV的內容，A節點不會響應B節點的ADV消息。(5)如果收到ADV報文的節點發現自己已經擁有了ADV報文中描述的數據，那么它不發送REQ報文，圖(e)中有一個節點沒有發送RCQ報文。SPIN協議特點SPIN協議下，節點不需要維護鄰居節點的信息，一定程度上能適應節點移動的情況。在能耗方面，比傳統模式減少一半以上。不過，該算法不能確保數據一定能到達目標節點，尤其是不適用于高密度節點分布的情況。由于SPIN協議通過節點之間的協商，解決了flooding協議的內爆和重疊現象。SPIN協議是一種不需要了解網絡拓撲結構的路由協議，由于它幾乎不需要了解“一跳”范圍內的節點狀態，網絡的拓撲改變對它的影響有限，因此該協議也適合在節點可以移動的WSN中使用。SPIN協議通過使用協商機制和能量自適應機制，節省了能量，解決了內爆的問題。SPIN協議引入了元數據的概念，通過這種數據壓縮方法來減少數據的傳輸量，是一種值得借鑒的方法。在SPIN協議中出現了多個節點向同一個節點同時發送請求的情況，有關的退避機制需要考慮。5.4層次路由協議5.4.1LEACH協議5.4.2PEGASIS協議5.4.3TEEN協議5.4層次路由協議在基于層次的路由協議中，網絡被劃分為大小不等的簇（CIuster）。簇.就是具有某種關聯的網絡節點集合。每個簇由一個簇頭（Clusterhead）和多個簇內成員（Clustermember）組成。在分層的簇結構網絡中，低一級網絡的簇頭是高一級網絡中的簇內成員，由最高層的簇頭與匯聚節點（Sinknode）通信。這類算法將整個網絡劃分為相連的區域。在分簇的拓撲管理機制下，網絡中的節點可以劃分為簇頭節點和簇內成員節點兩大類。在每個簇內，根據一定的算法選取某個節點作為簇頭，用于管理或控制整個簇內成員節點，協調成員節點之間的工作，負責簇內信息的收集和數據的融合處理以及簇間轉發。層次路由的優點：是適合大規模的傳感器網絡環境，可擴展性較好，而其缺點是簇頭節點的可靠性和穩定性對全網性能的影響較大，信息的采集和處理也會消耗簇頭節點的大量能量。典型的層次路由協議，LEACH協議、PEGASIS協議以及TEEN協議。5.4.1LEACH協議低功耗自適應聚類分級（LowEnergyAdaptiveClusteringHierarchy，LEACH）協議采用層次路由算法。定義出了輪的概念，每一輪有初始狀態和穩定運行狀態兩種模式。初始狀態是用來根據算法隨機選擇簇頭節點，同時廣播自己成為簇頭節點的事實，其它節點收到廣播信號后通過判斷信號的強弱來決定加入哪個簇，并告知簇頭節點。穩定工作時候，節點將信息傳遞給簇頭節點，然后簇頭節點將信息傳遞給匯集節點。當一輪完成后重新選舉簇頭。該算法通過輪流擔任簇頭的方式來均等消耗能量，達到延長網絡生存周期的目的。但是因為每一個節點都可以成為簇頭，也即都可以將數據直接傳給匯集節點，該算法只是適用于單跳的小型網絡。LEACH節約能量的主要原因：就是它運用了數據壓縮技術和分簇動態路由技術，通過本地的聯合工作來提高網絡的可擴展性和魯棒性，通過數據融合來減少發送的數據量，通過把節點隨機的設置成“簇頭節點”來達到在網絡內部負載均衡的目的，防止簇頭節點的過快死亡。1．分簇式路由協議的工作原理通過等概率地隨機循環選擇簇頭，將整個網絡的能量負載平均分配到每個傳感器節點，從而達到降低網絡能量耗費、延長網絡生命周期的目的。分簇式路由協議的執行過程是以輪(round)為單位的，每輪循環的基本過程是：（1）簇的建立階段。每個節點選取一個介于0和1之間的隨機數，如果這個數小于某個閾值，該節點成為簇頭。然后，簇頭向所有節點廣播自己成為簇頭的消息。每個節點根據接收到廣播信號的強弱來決定加入哪個簇，并回復該簇簇頭。（2）數據傳輸階段。簇內的所有節點按照TDMA（時分復用）時隙向簇頭發送數據。簇頭將數據融合之后把結果發給匯聚節點。（3）重新成簇。在持續工作一段時間之后，網絡重新進入啟動階段，進行下一輪的簇頭選取并重新建立簇。2.LEACH協議工作原理LEACH協議的工作分為兩個階段：（1）簇的建立階段：負責簇的形成和簇頭的選舉。在LEACH協議中，節點決定自己是否成為簇頭的算法如下：每個傳感器節點產生一個0~1之間的隨機數，如果這個數小于概率值T(n)，則發布自己是簇頭的公告消息。在每輪循環中，如果節點己經當選過簇頭，則設T(n)=0，這樣該節點不會再次當選為簇頭。對于未當選過簇頭的節點，則將以T(n)的概率當選；隨著當選過簇頭的節點數目增加，剩余節點當選簇頭的閾值T(n)隨之增大，節點產生小于T(n)的隨機數的概率隨之增大，所以節點當選簇頭的概率增大。當只剩下一個節點未當選時，T(n)=1，表示這個節點一定當選。2.LEACH協議工作原理(2)概率表達式為：其中：p是簇頭占所有節點的百分比，即節點當選簇頭的概率；r是目前循環進行的輪數；G是最近1/p輪中還未當選過簇頭的節點集合。所有被推選出的簇頭都向網絡中的其它節點廣播一個通告來宣布自己的簇頭角色。而所有其它節點在收到這些通告之后，會根據通告的強度來決定自己到底加入哪個簇。簇頭節點在收到愿意加入簇的節點的回應信息后，就會根據簇內節點的數目創建一個TDMA表為每個簇內節點分配一個傳輸時隙。最后簇頭節點將這張表的信息以廣播的方式告知簇內的成員。同時不同的簇用不同的TDMA通信方式，這樣就減少了不同簇的節點之間的干擾。2.LEACH協議工作原理(3)（2）穩定階段：負責收集數據和給簇頭傳輸數據。簇頭節點在收到簇內成員的數據之后會對這些數據進行聚合后傳送給匯集結點。經過一段時間之后，網絡就會再一次回到協議的建立階段，開始新一輪的工作。3.LEACH協議的特點優點：①將區域劃分成簇、簇內本地化協調和控制的形式有效的進行了數據收集。大多數的節點只需要短距離的數據傳輸到簇頭節點，僅有小部分的節點（簇頭節點）負責遠距離的數據傳送到匯集節點，從而節省更多節點的能量。②獨特的選簇算法保證簇頭位置的隨機輪換，節點是否決定要成為簇頭要看其是否在輪中當選過簇頭。同時所做決定是獨立于其它節點不需要協商的。這種機制保證了能量消耗平均分布于全網。③運用了數據融合技術本地數據融合大大減少了簇頭節點傳送到匯集節點的數據量，進一步減少了能量消耗提高了網絡壽命。3.LEACH協議的特點（2）缺點：①簇頭能量消耗比較大：由于簇頭節點負責接收簇內成員節點發送的數據，進行數據融合，然后將數據傳送到基站，簇頭消耗能量比較大，是網絡中的瓶頸。②LEACH協議中簇頭選舉是隨機循環選舉，有可能簇頭位于網絡的邊緣或者幾個簇頭相鄰較近，某些節點不得不傳輸較遠的距離來與簇頭通信，這就導致消耗的能耗大大增加。③簇頭選舉沒有根據節點的剩余能量以及位置等因素，會導致有的簇過早死亡，簇與簇之間節點的能量消耗不均衡。④LEACH協議要求節點之間以及節點與匯集節點之間均可以直接通信，網絡的擴展性不強，不適用于大型網絡。對于大型網絡而言，對離簇頭較遠的簇內節點和離匯聚節點較遠的簇頭而言，傳輸所消耗的能量大大增加。這樣簇頭節點能耗分布不均勻，導致某些節點快速死亡，從而降低了網絡的性能。5.4.2PEGASIS協議高能效采集傳感器信息系統（Power-EfficientGatheringinSensorInformationSystems，PEGASIS）并不是嚴格意義上的分簇路由協議，它只是借鑒了LEACH中分簇算法的思想。PEGASIS中的簇是一條基于地理位置的鏈。其成簇的基本思想是，假設所有節點都是靜止的，根據節點的地理位置形成一條相鄰節點之間距離最短的鏈。這類似于旅行商問題，是一個經典的NP問題。其算法是假設節點通過定位裝置或者通過發送能量遞減的測試信號來發現距自己最近的鄰居節點，然后從距匯集節點最遠的節點開始，采用貪婪算法來構造整條鏈。與LEACH算法相比，PEGASIS中通信只限于相鄰節點之間。這樣，每個節點都以最小功率發送數據，并且每輪只隨機選擇一個簇頭與匯集節點通信，減少了數據通信量。PEGASIS支持的傳感網的生命周期是LEACH的近兩倍。5.4.2PEGASIS協議（2）PEGASIS的模型假設如下。（1）節點都知道其他節點的位置信息，每個節點都具有直接和匯集節點（基站）通信的能力。（2）傳感器節點不具有移動性。（3）其他的模型假設和LEACH中的相同。該路由協議使用貪婪算法（GreedyAlgorithm）來形成鏈，如圖5-6所示。在每一輪通信之前才形成鏈。為確保每個節點都有其相鄰節點，鏈從離基站最遠的節點開始構建，鏈中鄰居節點的距離會逐漸增大，因為已經在鏈中的節點不能再次被訪問。當其中一個節點失效時，鏈必須重構。5.4.2PEGASIS協議（3）PEGASIS協議中數據的傳輸使用Token令牌機制，Token很小，故耗能較少。在一輪中，簇頭用Token控制數據從鏈尾開始傳輸。網絡中某些節點可能因與鄰居節點距離較遠而消耗能量較大。可以通過設置一個門限值限定此節點作為接頭。當該鏈重構時，此門限值可被改變以重新決定哪些節點可做簇頭，從而增強網絡的健壯性。圖中，c2為簇頭，將token沿著鏈傳輸給c0，c0傳送數據給c1，c1將c0數據與自身數據進行融合形成一個相同長度的數據包，再傳給c2。此后，c2將token傳給c3，并以同樣的方式收集c3和c4的數據。這些數據在c2處進行融合后，被發送給基站5.4.3TEEN協議閾值敏感的高效傳感器網絡協議（ThresholdSensitiveEnergyeEfficientSensorNetworkProtocol，TEEN）采用類似LEACH的分簇算法，只是在數據傳送階段使用不同的策略。根據數據傳輸模式的不同，通常可以簡單地把傳感器網絡分為主動型（proactive）和響應型（reactive）兩種類型。主動型網絡不斷采集被監測對象的相關信息，并以特定時間間隔向匯集節點發送這些信息；響應型網絡主要用來監測某個特定事件的發生，傳感器節點只有在節點檢測到相關事件時才會向匯集節點發送信息，如對災害的監測、暖通空調設備的防凍監測等。對于監測特定的事件，適于使用響應型無線傳感器網絡。TEEN協議是專門為響應型應用環境下的網絡路由協議，利用過濾方式來減少數據傳輸量。TEEN和LEACH的實現機制是相似的，只是LEACH適用于主動型網絡。與LEACH一樣，TEEN也采用分簇結構和近于相同的運行方式，具體做法是在協議中設置了硬、軟兩個閾值，以減少發送數據的次數。5.4.3TEEN協議(2)TEEN協議實現簇的建立過程中，隨著簇頭節點的選定，簇頭除了通過TDMA方式調度數據外，同時向簇內成員廣播發送有關數據的硬閾值和軟閾值參數，兩個參數用來決定是否發送監測數據。硬閾值用于監視被監測值的絕對大小，軟閾值用于監視被監測值的變化幅度。在傳感器節點簇進入穩定工作階段后，傳感器節點不斷感知及監測周圍環境中的被監測參量。當首次監測到數據超過硬閾值時，便向簇頭傳送數據，同時將該監測數據保存為監測值(sensorvalue)。此后，只有在監測到的數據值比硬閾值大，并且與保存的監測值SV之差的絕對值不小于軟閾值時，節點才向簇頭上傳數據，同時將當前監測數據保存為SV。TEEN通過調節兩個閾值的大小，可以在精度要求和系統能耗之間取得合理的平衡。采用這樣的方法，可以監視一些突發事件和熱點地區，減少網絡通信量。5.4.3TEEN協議(3)如果一輪的運行已經結束，開始了又一個新的輪，并且在初始化階段中，簇頭已經確定，則該簇頭將重新設定和發布硬閾值和軟閾值參數。這一過程如圖5-7所示。5.4.3TEEN協議(3)TEEN路由協議適用于對一些事件的實時感知偵測，并利用軟閾值、硬閾值設置來較大幅度地減小數據傳輸量。在輪的更替中，隨著簇頭的變化，用戶可以根據需要重新設定軟、硬閾值參數值，來控制數據傳輸的次數。TEEN路由協議同LEACH協議類似，協議實現的一個前提就是網絡中所有的節點都能夠與網關節點直接建立通信，這就限制了該協議僅適合于小規模的無線傳感網。5.5基于查詢的路由協議5.5.1定向擴散路由5.5.2謠傳路由5.5基于查詢的路由協議在需要不斷查詢傳感器節點采集的數據的應用中，通信流量主要產生于查詢節點和傳感器節點之間的命令和數據傳輸。同時傳感器節點的采樣信息通常要在傳輸路徑上進行數據融合，并通過減少通信流量來節省能量。5.5.1定向擴散路由定向擴散（Directedfusion，DD)路由協議是一種基于查詢的路由方法，這和傳統路由算法的概念不同。DD算法是一種基于數據相關的路由算法，匯集節點周期地通過洪泛的方式廣播一種稱為“興趣”的數據包，告訴網絡中的節點它需要收集什么樣的信息。“興趣”在網絡中擴散的時候同時也建立了路由路徑，采集到和“興趣”相關的數據的節點通過“興趣”擴散階段建立的路徑將采集到的“興趣”數據傳送到匯集節點。在興趣消息的傳播過程中，協議逐跳地在各個傳感器節點上建立反向的從數據源到匯聚節點的數據傳輸梯度(Gradient)，傳感器節點將采集到的數據沿著梯度方向傳送到匯聚節點。定向擴散路由機制包括周期性的興趣擴散、梯度建立、數據傳播與路徑加強等階段。在梯度建立后或者路徑加強后都不可避免地要進行數據傳輸，這也是路由協議的最終目的。廣義來說，數據傳輸也算是該路由機制中的一個階段。5.5.1定向擴散路由如圖5-8所示為DD協議的幾個階段的數據傳播路徑和方向。1．興趣擴散階段

在定向擴散協議中，首先描述需要感知的任務，并選擇一個簡單的屬性組命名機制來描述興趣消息和分組數據。在興趣擴散階段，匯聚節點周期性地向鄰居節點廣播興趣消息。興趣消息中包括任務類型、事件區域、數據發送速率、時間戳等參數。每個節點都在本地保存一個興趣列表，對于每一個興趣，列表中都有一個表項來記錄該消息的鄰居節點、數據發送速率和時間戳等任務相關的信息，以建立該節點向匯聚節點傳遞數據的梯度關系。—個興趣可能對應多個鄰居節點，一個鄰居節點對應一個梯度信息。通過定義不同的梯度相關參數，可以滿足不同的應用需求。每個表項中還有一個字段用來表示該表項的有效時間值。超過這個時間后，節點將刪除這個表項。節點接收到鄰居節點的興趣消息時，首先檢查興趣列表中是否存有參數類型與收到興趣相同的表項，而且其對應的發送節點也是該鄰居節點。如果有對應的表項，就更新該項的有效時間值。如果只是參數類型相同，但不包含發送該興趣消息的鄰居節點，就在相應表項中添加這個鄰居節點。對于任何其他的情況，都需要建立一個新表項來記錄這個新的興趣。如果收到的興趣消息和節點剛剛轉發的興趣消息是一樣的，為避免消息循環，則丟棄該信息。否則。轉發收到的興趣消息。2．梯度建立階段DD協議需要在傳感器節點和匯集節點之間建立梯度，以保證可靠的數據傳輸。網絡中的節點從鄰居節點接收到一個興趣消息時，無法判斷此消息是否是已處理過的，或者是否和另一個方向的鄰居節點發來的興趣消息相同，所以當興趣消息在整個網絡擴散的時候，相鄰的節點彼此都建立一個梯度。這樣的優點是加快了無效路徑的修復，有利于路徑的加強，從而不會產生持久的環路，但同時也會導致一個節點可能接收到多個相同的興趣消息，造成消息在網絡中的泛濫。3．數據傳播階段當傳感器節點采集到與興趣匹配的數據時，就把數據發送到梯度上的鄰居節點，并按照梯度上的數據傳輸速率設定傳感器模塊采集數據的速率。由于可能會從多個鄰居節點收到興趣消息，而且節點會向多個鄰居節點發送數據，匯聚節點可能會接收到經過多個不同路徑的相同數據，中間節點收到其他節點轉發的數據后，首先查詢興趣列表的表項。如果沒有匹配的興趣表項就丟棄數據，如果存在相應的興趣表項，則檢查與這個興趣對應的數據緩沖區，其中數據緩沖區保存了最近轉發的數據。如果在數據緩沖區中有與接收到的數據匹配的副本，則說明巳經轉發過這個數據了，為避免出現傳輸環路，將丟棄這個數據。否則，檢查該興趣表頂中的鄰居節點信息。如果設置的鄰居節點的數據發送速率大于等于接收的數據速率，則全部轉發接收的數據。如果記錄的鄰居節點的數據發送速率小于接收的數據速率，則按照比例轉發。對于轉發的數據，數據緩沖區將保留一個副本，并記錄轉發時間。4．路徑加強階段定向擴散路由機制通過正向加強機制來建立優化路徑，并根據網絡拓撲的變化修改數據轉發的梯度關系。興趣擴散階段要建立源節點到匯聚節點的數據傳輸路徑，數據源節點將以較低的速率采集和發送數據，稱這個階段建立的梯度為探測梯度（ProbeGradient）。匯聚節點在收到從源節點發來的數據后，啟動建立匯聚節點到源節點的加強路徑的過程，后續數據將沿著加強路徑以較高的數據速率進行傳輸，加強后的梯度被稱為數據梯度（DataGradient）。DD路由特點定向擴散路由是一種以數據為中心的經典的路由機制。為了動態適應節點失效、拓撲變化等情況。定向擴散路由周期性地進行興趣擴散、梯度建立、數據傳播與路徑加強4個階段的操作。定向擴散路由在路由建立時需要有一個擴散的洪泛傳播，其能量和時間開銷都比較大，尤其是當底層MAC協議采用了休眠機制時，可能會造成興趣建立的不一致。DD路由協議中，為了對失效路徑進行修復和重建，規定已經加強過的路徑上的節點都可以觸發和啟動路徑的加強過程。DD算法中采用了數據融合的方法，數據融合包括梯度建立階段興趣消息的融合和數據發送階段的數據融合，這兩種融合方法都需要緩存數據。DD中數據融合采用的是抑制副本的方法，即記錄轉發過的數據，收到重復的數據不予轉發。其中采用的這些數據融合方法、實現起來簡單，與路由技術結合能夠有效地減少網絡中的數據量，節省節點能量、提高帶寬利用率。5.5.2謠傳路由在有些傳感器網絡的應用中，數據傳輸量較少或者已知事件區域，如果采用定向擴散路由，需要經過查詢消息的洪泛傳播和路徑加強機制才能確定一條優化的數據傳輸路徑。因此，在這類應用中，定向擴散路由并不是高效的路由機制。謠傳路由（rumorrouting）適用于數據傳輸量較小的無線傳感網。謠傳路由機制引入了查詢消息的單播隨機轉發，克服了使用洪泛方式建立轉發路徑帶來的開銷過大問題。謠傳路由的基本思想是：事件區域中的傳感器節點產生代理（agent）消息，代理消息沿隨機路徑向外擴散傳播，同時匯聚節點發送的查詢消息也沿隨機路徑在網絡中傳播。當代理消息和查詢消息的傳輸路徑交叉在一起時，就會形成一條匯聚節點到事件區域的完整路徑。謠傳路由的原理如圖所示，灰色區域表示發生事件的區域，圓點表示傳感器節點，黑色圓點表示代理消息經過的傳感器節點，灰色節點表示查詢消息經過的傳感器節點，連接灰色節點和部分黑色節點的路徑表示事件區域到匯聚節點的數據傳輸路徑。謠傳路由的工作過程（1）（1）每個傳感器節點維護一個鄰居列表和一個事件列表。事件列表的每個表項都記錄事件相關的信息，包括事件名稱、到事件區域的跳數和到事件區域的下一跳鄰居等信息。當傳感器節點在本地監測到一個事件發生時，在事件列表中增加一個表項，設置事件名稱、跳數（為零）等，同時根據一定的概率產生一個代理消息。（2）代理消息是一個包含生命期等事件相關信息的分組，用來將攜帶的事件信息通告給它傳輸經過的每一個傳感器節點。對于收到代理消息的節點，首先檢查事件列表中是否有該事件相關的表項，列表中存在相關表項就比較代理消息和表項中的跳數值，如果代理中的跳數小，就更新表項中的跳數值，否則更新代理消息中的跳數值。如果事件列表中沒有該事件相關的表項，就增加一個表項來記錄代理消息攜帶的事件信息。然后，節點將代理消息中的生存值減1，在網絡中隨機選擇鄰居節點轉發代理消息，直到其生存值減少為零。通過代理消息在其有限生存期的傳輸過程，形成一段到達事件區域的路徑。謠傳路由的工作過程（2）（3）網絡中的任何節點都可能生成一個對特定事件的查詢消息。如果節點的事件列表中保存有該事件的相關表項，說明該節點在到達事件區域的路徑上，它沿著這條路徑轉發查詢消息。否則，節點隨機選擇鄰居節點轉發查詢消息。查詢消息經過的節點按照同樣方式轉發，并記錄查詢消息中的相關信息，形成查詢消息的路徑。查詢消息也具有一定的生存期，以解決環路問題。（4）如果查詢消息和代理消息的路徑交叉，交叉節點會沿查詢消息的反向路徑將事件信息傳送到查詢節點。如果查詢節點在一段時間沒有收到事件消息，就認為查詢消息沒有到達事件區域，可以選擇重傳、放棄或者洪泛查詢消息的方法。由于洪泛查詢機制的代價過高，一般作為最后的選擇。與定向擴散路由相比，謠傳路由可以有效地減少路由建立的開銷。但是，由于謠傳路由使用隨機方式生成路徑，所以數據傳輸路徑不是最優路徑，并且可能存在路由環路問題。5.6基于地理位置路由5.6.1GEAR路由5.6.2GAF路由5.6.3GPSR路由在無線傳感網中，節點通常需要獲取它的位置信息，這樣它采集的數據才有意義。如在森林防火的應用中，消防人員不僅要知道森林中發生火災事件，而且還要知道火災的具體位置。地理位置路由假設節點知道自己的地理位置信息，以及目的節點或者目的區域的地理位置，利用這些地理位置信息作為路由選擇的依據，節點按照一定策略轉發數據到目的節點。地理位置的精確度和代價相關，在不同的應用中會選擇不同精確度的位置信息來實現數據的路由轉發。5.6.1GEAR路由GEAR（geographicalandenergyawarerouting）路由機制根據事件區域的地理位置信息，建立匯聚節點到事件區域的優化路徑，避免了洪泛傳播方式，從而減少了路由建立的開銷。GEAR路由假設已知事件區域的位置信息，每個節點知道自己的位置信息和剩余能量信息，并通過一個簡單的Hello消息交換機制知道所有鄰居節點的位置信息和剩余能量信息。在GEAR路由中，節點間的無線鏈路是對稱的。GEAR路由中查詢消息傳播包括兩個階段。首先匯聚節點發出查詢命令，并根據事件區域的地理位置將查詢命令傳送到區域內距匯聚節點最近的節點，然后從該節點將查詢命令傳播到區域內的其他所有節點。監測數據沿查詢消息的反向路徑向匯聚節點傳送。（1）查詢消息傳送到事件區域GEAR路由用實際代價（learnedcost）和估計代價（estimatecost）兩種代價值表示路徑代價。當沒有建立從匯聚節點到事件區域的路徑時，中間節點使用估計代價來決定下一跳節點。估計代價定義為歸一化的節點到事件區域的距離以及節點的剩余能量兩部分，節點到事件區域的距離用節點到事件區域幾何中心的距離來表示。由于所有節點都知道自己的位置和事件區域的位置，因而所有節點都能夠計算出自己到事件區域幾何中心的距離。節點計算自己到事件區域估計代價的公式如下：（5.7）式中，C(N,R)為節點N到事件區域R的估計代價，d(N,R)為節點N到事件區域R的距離，e(N)為節點的剩余能量，α為比例參數。式中的d()和e()都是歸一化后的參數值。查詢信息到達事件區域后，事件區域的節點沿查詢路徑的反方向傳輸監測數據，數據消息中“捎帶”每跳節點到事件區域的實際能量消耗值。對于數據傳輸經過的每個節點，首先記錄捎帶信息中的能量代價，然后將消息中的能量代價加上它發送該消息到下一跳節點的能量消耗，替代消息中的原有“捎帶”值來轉發數據。節點下一次轉發查詢消息時，用剛才記錄的到事件區域的實際能量代價代替式（5.7）中的d(N,R)，計算它到匯聚節點的實際代價。節點用調整后的實際代價選擇到事件區域的優化路徑。從匯聚節點開始的路徑建立過程采用貪婪算法，節點在鄰居節點中選擇到事件區域代價最小的節點作為下一跳節點，并將自己的路由代價設為該下一跳節點的路由代價加上到該節點一跳通信的代價。如果節點的所有鄰居節點到事件區域路由代價都比自己的大，則陷入了路由空洞（routingvoid）。路由空洞如圖所示，節點C是節點S的鄰居節點中到目的節點T代價最小的節點，但節點G，H，I為失效節點，節點C的所有鄰居節點到節點T的代價都比節點C大。可采用如下方式解決路由空洞問題：節點C選取鄰居中代價最小的節點B作為下一跳節點，并將自己的代價值設為B的代價加上節點C到節點B一跳通信的代價，同時將這個新代價值通知節點S。當節點S再轉發查詢命令到節點T時就會選擇節點B而不是節點C作為下一跳節點。

（2）查詢消息在事件區域內傳播當查詢命令傳送到事件區域后，可以通過洪泛方式傳播到事件區域內的所有節點。但當節點密度比較大時，洪泛方式開銷比較大，這時可以采用迭代地理轉發策略。如圖5-12所示，事件區域內首先收到查詢命令的節點將事件區域分為若干子區域，并向所有子區域的中心位置轉發查詢命令。在每個子區域中，最靠近區域中心的節點（如圖5-12中Ni節點）接收查詢命令，并將自己所在的子區域再劃分為若干子區域并向各個子區域中心轉發查詢命令。該消息傳播過程是一個迭代過程，當節點發現自己是某個子區域內惟一的節點，或者某個子區域沒有節點存在時，停止向這個子區域發送查詢命令。當所有子區域轉發過程全部結束時，整個迭代過程終止。圖5-12GEAR路由特點洪泛機制和迭代地理轉發機制各有利弊。當事件區域內節點較多時，迭代地理轉發的消息轉發次數少，而節點較少時使用洪泛策略的路由效率高。GEAR路由可以使用如下方法在兩種機制中作出選擇：當查詢命令到達區域內的第一個節點時，如果該節點的鄰居數量大于一個預設的閾值，則使用迭代地理轉發機制，否則使用洪泛機制。GEAR路由通過定義估計路由代價:為節點到事件區域的距離和節點剩余能量，并利用捎帶機制獲取實際路由代價，進行數據傳輸的路徑優化，從而形成能量高效的數據傳輸路徑。GEAR路由采用的貪婪算法是一個局部最優的算法，適合無線傳感器網絡中節點只知道局部拓撲信息的情況，其缺點是由于缺乏足夠的拓撲信息，路由過程中可能遇到路由空洞，反而降低了路由效率。如果節點擁有相鄰兩跳節點的地理位置信息，可以大大減少路由空洞的產生概率。GEAR路由中假設節點的地理位置固定或變化不頻繁，適用于節點移動性不強的應用環境。5.6.2GAF路由地域自適應保真算法（GeographicAdaptiveFidility，GAF）是基于有限能量和位置信息的路由算法。GAF原本是為移動AdHoc網絡設計的，但同樣可以應用于傳感器網絡，因為它的虛擬網格思想為分族機制提供了新思路，GAF在不影響路由有效性的情況下，通過關閉一些不需要的節點來節省能量，同時還考慮了所有節點能量消耗的均衡性。在GAF路由協議中，網絡被劃分為若干固定區域，形成了一個虛擬網格。節點通過GPS定位獲取自己在網格中所處的“位置”，如果兩個節點處在相同的“位置”，則認為它們在路由時是等價的，前提是它們分組轉發能耗水平相等。等價節點中只需有一個處于工作狀態，其余節點可以進入睡眠。如圖5-13所示。因此，GAF能夠有效地延長網絡的生命周期。圖5-13在圖5-14中的節點2、3、4在同一個柵格B中，因此只需要保留其中一個節點處于工作狀態，另外兩個可以處于睡眠狀態。而這在adHoc網絡中是絕對不可取的，因為在AdHoc網絡中，即使是同一個柵格內的節點，也還是代表了不同的移動終端，根本不能相互代替。但在WSN中，這就是一個優點，相當于用1個節點代表了3個節點，類似于層次路由中的簇頭節點，但這個類似于簇頭的代表節點卻不進行柵格內的數據融合。節點間的數據通信只能在相鄰柵格間進行，即A柵格內的節點1只能與B柵格內的2、3、4節點通信，而不能直接和C柵格內的節點5通信。圖5-14雖然GAF按柵格選擇代表節點的方法和SOA選擇靜止節點做轉發點的方法不同，但兩者都是在全部節點中選擇部分節點，相當于從整個集合中選擇子集，并且都是根據節點的當前狀態來決定是否選擇該節點作為轉發節點，它們都能有效地延長網絡的生存時間。GAF算法的執行過程包括兩個階段。（1）第一階段是虛擬網格的劃分。根據節點的位置信息和通信半徑，將網絡區域劃分成若干虛擬網格，保證相鄰單元格中的任意兩個節點都能夠直接通信。假設節點已知整個監測區域的位置信息和本身的位置信息，則可以通過計算得知自己屬于哪個網格。（2）第二階段是虛擬網格中簇頭節點的選擇。節點周期性地進入睡眠和工作狀態，從睡眠狀態喚醒之后與本單元其他節點交換信息，以確定自已是否需要成為簇頭節點。每個節點都處于發現(Discovery)、活動(Active)以及睡眠(sleeping)3種狀態，如圖5-15所示。在網絡初始化時，所有節點都處于發現狀態，每個節點都通過發送消息通告自己的位置、ID等信息。經過這個階段，節點能得知同一單元格內其他節點的信息。然后，每個節點將自身定時器設置為某個區間內的隨機值。一旦定時器超時，節點就發送消息，聲明它進入活動狀態，并成為簇頭節點。節點如果在定時器超時之前收到來自同一單元格內其他節點成為簇頭的聲明，說明它自己這次競爭簇頭失敗，從而轉入睡眠狀態。成為簇頭的節點設置定時器，代表它處于活動狀態的時間。在超時之前，簇頭節點定期發送廣播包聲明自己處于活動狀態，以抑制其他處于發現狀態的節點進入活動狀態。在超時后，簇頭節點重新回到發現狀態。處于睡眠狀態的節點設置定時器為，并在超時后，節點重新回到發現狀態。處于活動狀態或發現狀態的節點如果發現本單元格中出現了更適合成為簇頭的節點時，會自動進入睡眠狀態。由于節點處于監聽狀態也會消耗很多能量，讓節點盡量處于睡眠狀態成為傳感器網絡拓撲算法中經常采用的方法。GAF是較早采用這種方法的算法。由于傳感器節點自身體積和資源受限，GAF對傳感器節點提出的要求較高。且GAF算法是基于平面模型的，沒有考慮到實際網絡中節點之間距離的鄰近并不能代表節點之間可以直接通信的問題，因此存在一些不足。5.6.3GPSR路由無狀態的貪婪周邊路由協議（GreedyPerimeterStatelessRouting，GPSR）是一個典型的基于位置的路由協議。該協議，網絡中的所有傳感器節點均知道自身的坐標位置信息，而且這些坐標位置被統一編址，傳感器節點按照貪婪算法盡量地沿直線將數據傳送出去。采集到數據的節點經過判別哪個相鄰節點與目標節點的距離最近，就將數據傳送給該鄰居節點。數據可以使用兩種模式來傳送：貪婪轉發模式和周邊轉發模式。使用貪婪轉發模式時，接收到數據的傳感器節點，查詢它的鄰節點表，如果某個鄰節點與網關節點的距離小于自身節點到網關節點的距離，就保持當前的數據模式，同時將數據轉發給選定的鄰節點；如果滿足不了上述要求，就改變數據模式為周邊轉發模式。GPSR路由工作原理在傳送的數據包中包括目標節點的位置信息，中繼轉發節點利用貪婪轉發模式來確定下一跳的節點，這個節點是距離目標節點最近的那個鄰節點。用這種方式連續不斷的選擇距目標節點更近的節點進行數據中繼轉發，直至將數據傳送給目標節點為止。使用貪婪轉發策略選擇下一跳節點的情況如圖5-16所示。設定中繼節點A接收到一個到目標節點D的數據包，節點A的傳輸覆蓋范圍是以A點為圓心的虛線圓區域，以D點為圓心，線段DB為半徑畫圓，圓弧交節點B，由于節點B與目標節點D之間的距離小于A節點所有的其它鄰節點，因此就選節點B做下一跳節點。按照這種方式繼續前向轉發傳遞數據，直到目標節點D獲得數據為止。GPSR路由工作原理GPSR路由工作原理-路由空洞產生空洞的情況如圖5-17所示，給定網絡特定的拓撲及傳感器節點的位置分布，節點T到目標節點D的距離要小于相鄰兩個節點U、V到目標節點D的距離。將數據由節點T轉發給目標節點D，有兩條路徑：(T-U-W-D)和(T-V-X-D)，但是使用貪婪轉發策略進行數據轉發時，就不會選擇U或V作為下一跳的節點，因為節點T到目標節點D的距離要小于U或V各自到D的距離，這樣就出現了空洞，導致數據無法傳輸。要解決空洞現象，可以使用周邊轉發機制，這里的闡述就從略了。GPSR路由特點使用貪婪轉發策略會出現所謂路由空洞的缺欠。使用該協議避免了在節點中建立、維護和存儲路由表的工作，僅使用直接毗鄰的節點進行路由選擇。另外，路由選擇中是使用接近于最短歐氏距離的路由，數據傳輸時延小，實時性增強。5.6.4GEM路由GEM（graphembedding）路由是—種適用于數據中心存儲方式的地理路由。基本思想是建立一個虛擬極坐標系統來表示實際的網絡拓撲結構，由于匯集節點將角度范圍分配給每個子節點，每個子節點得到的角度范圍正比于以該節點為根的子樹大小，子節點按照同樣的方式將自己的角度范圍分配給它的子節點，這個過程一直持續進行，直到每個子節點都分配到一個角度范圍。這樣，節點可以根據一個統一規則（如順時針方向）為子節點設定角度范圍，使得同一級節點的角度范圍順序遞增或遞減，于是到匯聚節點跳數相同的節點就形成了一個環形結構，整個網絡則形成一個以匯聚節點為根的帶環樹。GEM路由工作機制節點在發送消息時，如果目的節點位置的角度不在自己的角度范圍內，就將消息傳送給父節點。父節點按照同樣的規則處理，直到該消息到達角度范圍包含目的節點位置的某個節點，這個節點是源節點和目的節點的共同祖先。消息再從這個節點向下傳送，直至到達目的節點，如圖5-18(a)所示。上述算法需要上層節點轉發消息，開銷比較大，可作適當改進。節點在向上傳送消息之前，首先檢查鄰節點是否包含目的節點位置的角度。如果包含，則直接傳送給該鄰節點而不再向上傳送，如圖5-18(b)所示。更進一步的改進算法是可利用前面提到的環形結構，節點檢查相鄰節點的角度范圍是否離目的地的位置更近，如果更近就將消息傳送給該鄰節點，否則才向上層傳送，如圖5-18(c)所示。GEM路由機制圖5-18GEM路由機制（a）消息直接向上層傳遞圖5-18（b）檢查鄰居節點的角度范圍圖5-18（c）利用環形樹結構5.7基于QoS的路由協議無線傳感網的某些應用對通信質量有較高要求，如高可靠性和實用性等；而由于網絡鏈路的穩定性難以保證，通信信道質量比較低，拓撲變化比較頻繁，要在無線傳感網中實現一定服務質量的保證，需要設計基于QoS的路由協議。5.7.1SPEED5.7.2SAR5.7.3ReInForM5.7.1SPEED

SPEED協議是一種實時有效的可靠路由協議，在一定程度上實現了端到端的傳輸速率保證、網絡擁塞控制以及負載平衡機制。該協議首先在相鄰節點之間交換傳輸延遲，以得到網絡負載情況。然后利用局部地理信息和傳輸速率信息選擇下一跳節點，同時通過鄰居反饋機制保證網絡傳輸暢通，并通過反向壓力路由變更機制避開延遲太大的鏈路和“洞”現象。SPEED協議主要由四部分組成。1.延遲估計機制：延遲估計機制用來得到網絡的負載狀況，判斷網絡是否發生擁塞。節點記錄到鄰節點的通信延遲以表示網絡的局部通信負載。具體過程是：發送節點給數據分組并加上時間戳；接收節點計算從收到數據分組到發出ACK的時間間隔，并將其作為一個字段加入ACK報文；發送節點收到ACK后，從收發時間差中減去接收節點的處理時間，得到一跳的通信延遲。

2.SNGF算法：SNGF算法用來選擇滿足傳輸速率要求的下一跳節點。鄰節點分為兩類：比自己距離目標區域更近的節點和比自己距離目標區域更遠的節點，前者稱為“候選轉發節點集合(FCS)”。節點計算到其FCS集合中的某個節點的傳輸速率。FCS集合中的節點又根據傳輸速率是否滿足預定的傳輸速率閾值，再分為兩類：大于速率閡值的鄰節點和小于速率閾值的鄰節點。若FCS集合中有節點的傳輸速率大于速率閡值，則在這些節