4.4.2　基于集群結構的路由協議

通俗地說，基于集群結構的路由協議就是一種分層的路由協議，在該思想下，網絡被劃分為多個簇，每個簇都由一個簇頭和許多個簇成員組成，每個簇成員如需跟其余簇的成員通信，要先與簇頭通信，通過簇頭來與其余簇進行通信。在網絡規模比較大的情況下，簇頭又可以再次分簇，從而形成一個多層網絡。簇頭節點的職責就是管理好本簇內節點，完成本簇分布范圍內數據的搜集，并負責簇間的通信。分層路由的擴展性非常好，對于大規模的無線傳感器應用具有很高的使用價值。下面簡單地介紹常用的兩種分層路由協議。

1. LEACH路由協議

LEACH（Low Energy Adaptive Clustering Hierarchy）是第一個提出數據聚合的層次型路由協議，采用隨機選擇簇首的方式來避免簇首過度消耗能量；通過數據聚合有效地減少網絡的通信量。LEACH是基于簇（Cluster）的協議，協議隨機挑選一些節點作為簇首（Cluster Heads）節點，這些簇首節點負責收集并融合周圍節點的數據，然后發送給Sink節點。LEACH路由協議的工作過程是一輪一輪地進行的，每一輪均分為兩個階段。

1）建立階段（Setup Phase）

隨機選擇一些節點作為簇首節點，具體方法是：節點n選擇一個0～1之間的隨機數，并且與T(n)做比較，如果小于T(n)，該節點就成為簇首節點。

式中，p代表簇首節點占總節點數的比例，如p=0.05；r為當前的輪數，G為前1/p次輪回中未被選擇作為簇首的節點。

當前一輪的簇首選定后，這些簇首節點就對周圍節點進行廣播，使用載波偵聽多路訪問（Carrier Sense Multiple Access，CSMA）MAC協議，并且所有的廣播都用相等的能量發送。所有的非簇首節點都要偵聽任何簇首節點發來的廣播信息，根據接收到的廣播能量強弱決定歸屬于哪個簇首節點管理的簇，并且通知該簇首節點。簇首節點根據加入的節點數量，分配給每個簇內節點一個TDMA時隙。

2）就緒階段（Steady State Phase）

一旦簇首節點確定下來，TDMA時隙也分配好后，網絡就進入了就緒階段。非簇首節點負責采集數據，如果需要發送數據，就用最小的能耗發送給它的簇首節點，非簇首節點在不屬于自己時隙的期間可以進入睡眠狀態以節省能耗，而簇首節點則必須始終處于接收狀態。所有TDMA時隙都輪過后，簇首節點對接收到的數據進行融合壓縮，然后直接發送給Sink節點。

就緒階段經過一段時間后，網絡重新選擇簇首節點，進入新的一輪。相對于非簇首節點，簇首節點的能量消耗得非常快，如維護簇、融合壓縮數據、直接傳送數據給Sink節點等。從理論上講，所有的節點都有機會成為簇首節點，從而均勻分配了能量消耗，避免網絡生命周期過快結束。不同的簇首節點與Sink節點通信時會相互干擾，可采用CDMA接入方式來解決這個問題，即每個簇首節點隨機選擇一種CDMA碼與Sink節點通信。

由于LEACH路由協議每一輪都采用隨機選擇簇首的機制，使能量消耗均勻分布到每個節點，并且由簇首節點進行數據融合后直接發送給基站，可減少與基站直接通信的節點數量，從而延長網絡的生命周期。但是該協議也存在一些問題，如每一輪開始都要重新進行一次簇的建立過程，由此帶來的控制和計算開銷很大，也相應增加了每個節點的能耗；簇首節點直接與基站通信，在LEACH的無線通信模型中，節點發送消息的能耗模型服從自由空間模型（與距離的2次方成正比），當距離大于一定值時，服從多徑衰弱模型（與距離的4次方成正比），所以在基站距離較遠的情況下，直接通信的代價很大；由于簇首節點的產生在很大程度上依賴于各個節點生成的隨機數，這種通過隨機數與計算得到的閾值比較的機制只是從簇首節點數目的期望值是最優的角度考慮的，而簇首節點的分布、相應的簇成員數目、簇的大小都不穩定，當簇首節點位置分布較差時，簇內通信不再滿足自由空間模型，且存在簇間信號干擾、負載不平衡等問題，這將導致很大的能量開銷；簇首節點的選擇在考慮節點當前剩余能量的狀況時，需要計算網絡全部節點的當前能量總和。

2. TEEN協議

針對LEACH協議所存在的不足，研究人員對LEACH協議進行了一定改進，提出了幾種新的算法，典型的是TEEN（Threshold Sensitive Energy Efficient Sensor Network）協議。

1）基本思想

按照應用模式的不同，TEEN協議將無線傳感器網絡分為主動型（Proactive）和響應型（Reactive）。主動型無線傳感器網絡持續監測周圍的物質現象，并以恒定速率發送監測數據，而響應型無線傳感器網絡只是在被觀測變量發生突變時才傳送數據。相比之下，響應型無線傳感器網絡更適合應用在對時間敏感的應用中。TEEN和LEACH協議的實現機制非常相似，只是前者是響應型的，而后者屬于主動型無線傳感器網絡。在TEEN協議中定義了兩個門限的概念。

? 硬門限：當傳感器節點收集到的數據高于這個門限值時，節點開始向簇首節點匯報數據；

? 軟門限：當節點感應到的數據變化值大于這個門限值時，節點開始向簇首節點匯報數據。

在匯報數據之外的時間里，傳感器節點將關閉它們的無線發送模塊。TEEN協議采用了和LEACH協議相同的成簇機制，在每次簇重組后，簇首節點除了廣播數據屬性，還要廣播硬門限和軟門限的值。該協議的工作過程是：在成簇工作結束后，基站節點通過簇首節點向全網公告了兩個門限值；各個傳感器節點持續進行監測工作，在傳感器節點監測到的數據值大于硬門限值的情況下，傳感器節點打開無線發送模塊向簇首節點匯報數據，并且把這個監測到的數據緩存為監測值（Sensed Value，SV）；在后續的監測中，如果監測數據大于硬門限值，并且與SV的差值大于或者等于軟門限值，傳感器節點才向簇首節點匯報數據，同時把監測值更新為當前監測到的新值。

2）主要問題

在重新選擇簇首節點的過程中，簇首節點一旦確定，便會重新選擇硬門限和軟門限這兩個參數，設置這兩個值能在很大程度上減少數據傳送的次數，相比LEACH協議可節省更多的能量，適用于實時應用系統，對突發事件可以快速反應；另外，由于軟門限可以改變，監控者通過設置不同的軟門限值可以方便地平衡監測準確性與系統的節能指標。隨著簇首節點的變化，用戶也可以根據需要重新設定硬門限和軟門限這兩個參數的值，從而控制數據傳輸的次數，但TEEN協議不適合應用在需要周期性采集的應用系統中，這是因為如果網絡中的節點沒有收到相關的門限值，那么節點就不會與Sink節點進行通信，用戶也就完全得不到網絡中的任何數據。

根據TEEN協議的這個不足，APTEEN協議在TEEN協議的基礎上提出了一種改進型算法，它能夠同時解決LEACH協議的實時性不足問題和TEEN協議不能夠周期性發送數據等問題，APTEEN協議是一種結合了響應型和主動性兩種算法的混合協議，節點在監測突發事件的時候，采用的就是跟TEEN協議一樣的響應性機制，為了改進TEEN協議不能周期性發送數據的不足，APTEEN協議在響應性機制的基礎上增加了一個計時器，節點發送完一次數據之后就將計時器清零，當計時器時間到達時如果還沒有數據發送，那么協議不管有沒有達到軟門限或者硬門限的要求都會發送這個數據；并且APTEEN協議還提出了三種查詢方式，即對歷史數據的查詢、對當前網絡的一次查詢和對某一時間的周期性連續查詢。圖4.5是TEEN協議和APTEEN協議的時間線。

APTEEN協議可以根據用戶需要和應用類型來改變TEEN協議的周期性和相關閾值的設定，既能周期性地采集數據，又能對突發事件做出反應。它最大的特點就是隨著簇首節點的確定，簇首節點要向簇內所有成員廣播4類參數，包括用戶期望獲取的一組物理屬性，硬門限值和軟門限值，采用TDMA方式為簇內每個節點分配的時間片，節點成功發送報告的最長時間周期。運行APTEEN協議的節點在發送數據時會采用與TEEN協議相同的數據發送方式，并且規定如果節點在計數時間內沒有發送任何數據，便強迫節點向Sink節點傳送數據。

TEEN協議和APTEEN協議的主要缺點體現在：構建多層簇以及設置門限值在實現上較為復雜，基于屬性命名的查詢機制也會帶來額外的開銷。