李夢娥，張登銀
(1．南京郵電大學計算機學院，江蘇省南京市210003；
2．南京郵電大學訊號處理與傳輸研究院，江蘇省南京市210003)
0引言wsn(無線感測器網路)由部署在監測區域內的大量廉價的微型感測器節點組成，通過無線通訊方式形成乙個多跳、自組織的網路系統，其目的是協作地感知、採集和處理網路覆蓋區域中感知物件的資訊，並傳送給觀察者。wsn的隨機布設、自組織、環境適應等特點使其在軍事國防、工農業、城市管理、生物醫療、環境監測、搶險救災、防恐反恐、危險區域遠端控制等領域具有廣闊的應用前景和很高的應用價值。而源於wsn自身的特點，路由協議成為其研究的重點之一。
目前，已有很多路由協議，其目的是要節省系統的能量，延長系統的生命週期，提高系統的效能。主要有平面路由協議和層次路由協議。層次路由協議的基本思想是選取一些節點負責某個區域的路由，相對於其他節點具有更大的責任，而節點之間不是完全平等的關係。
簇類協議具有良好的節能效果和可擴充套件性。具有代表性的、成熟的路由協議主要有：leach(low-energy adaptive clustering hierarchy)、teen(thresholdsensitive energy efficient sensor network protocol)、pe-gasis (power-efficient gathering in sensor informationsystems)，以及在此基礎上改進的協議。
1 leach類協議
1.1 leach協議
leach的基本思想是將整個網路劃分為不同的簇，簇類節點的資料傳送和接收由簇頭負責，簇頭節點以迴圈的方式隨機選擇。leach定義了"輪"的概念，leach的執行過程就是輪不斷迴圈的過程。每個輪分成兩個階段：
簇的建立階段和傳輸資料的穩定階段。在簇的建立階段，相鄰節點動態地形成簇，隨機產生簇頭；在資料通訊階段，簇內節點把資料發給簇頭，簇頭進行資料融合後把結果傳送給基站。其中，簇的建立過程又可以分成4個階段：
簇首節點的選擇、簇首節點的廣播、簇的建立和排程機制的生成。
關於簇頭選擇的演算法，leach採用分布式。選擇簇頭的具體做法是：在每乙個回合即輪的第1階段，感測器節點隨機的選擇0～1之間的乙個數值，如果這個數值小於某乙個閾值t(n)，那麼這個節點就被選為簇頭節點。
節點n的閾值t(n)的計算公式如下：
式中：n為網路中感測器節點的總數；k為一輪網路中的簇頭節點數；r為已完成的輪數；g為在剩餘的r輪中未成為簇頭節點的感測器節點的集合。
leach這種簇首隨機選擇機制的優點在於，通過把網路的負載均勻地分布在整個網路上，很大程度上節約了通訊過程中的能量損耗。每一輪中，由不同的節點充當簇頭，從而網路中的節點都有機會來擔當遠距離通訊的任務。而且，簇頭節點在把簇內節點傳送來的資料傳送給bs(基站)之前，先進行資料融合與壓縮，進而減少資料的傳輸量，節省了能量。
leach實現起來相對簡單，操作也比較靈活。
leach的不足在於，每輪進行選擇簇頭並劃分簇，並且簇頭需要一直處於醒著的狀態以接收資料，這樣系統開銷較大，離散式區域演算法雖然對節點位置等要求不高，但無法確定最優的簇數目。leach採用tdma的mac層機制，而事實上，在分配給節點的每個時隙，節點並不是都有資料要傳送給簇頭，這樣的通訊機制不能有效利用頻寬，浪費了能量。leach還要求節點之間以及節點與sink之間都可以直接通訊，因此侷限了網路的可擴充套件性，不適用於大型的網路。
1.2 leach-ee協議
高效聚類路由演算法leach-ee是在leach基礎上改進的，不同於leach的單跳路徑選擇模式，而leach-ee是簇頭間多跳路徑選擇模式。leach-ee的基本思想大部分繼承了leach的模式，協議的執行過程就是簇不斷迴圈重構的過程，每一輪也分為簇的建立階段和傳輸資料的穩定階段，簇的建立階段也分為4個階段：簇首節點的選擇、簇首節點的廣播、簇的建立和排程機制的生成。
與leach不同的是在簇首節點廣播的階段和傳輸資料的穩定階段。在簇首節點的廣播階段，每個簇頭節點需要計算出自己與其他簇頭之間的距離，以及自己與sink之間的距離；在傳輸資料的穩定階段，由sink發起，遍歷所有的簇頭節點，尋找與sink路徑最短的簇頭，找到後，再尋找與這個簇頭路徑最短的下乙個簇頭，以此類推，直到所有的簇頭節點遍歷完了，建立一條通往sink的最短路徑，資料就可以由這條路徑融合並經多跳傳送給sink。
leach-ee的這種多跳路由模式把能量消耗均勻地分擔到每個節點，網路的壽命延長，而且就算bs與檢測距離變大，也不會使得離bs遠的節點迅速死亡。而leach中離sink較遠的節點因為遠距離單跳傳輸資料，能量消耗比較多，相對容易過早地死亡。這一點，leach-ee要優於leach。
leach-ee也有不足，在簇首節點的廣播階段和資料傳輸階段的簇頭之間距離的計算和最短路徑的計算都需要消耗節點的能量和時間，增加了每個節點的開銷，也沒有考慮到簇頭節點維護的開銷，這一點不利於網路的負載平衡。
1.3 deeac協議
deeac是與leach類似的分布式能量有效的成簇演算法。與leach不同的在於deeac的簇頭選擇方式上，其資料傳輸過程相同。deeac的做法是：
網路中的每個節點根據某個閾值自主判斷自己是否成為臨時簇首，這個閾值由網路所決定的最優簇首概率popt確定，然後，臨時簇首負責收集簇內節點的資訊，根據簇內通訊總能耗最小化原則，選擇乙個使得每一輪簇內通訊能量消耗最小的節點作為真正的簇首。臨時簇首判斷簇類通訊總能耗最小，是根據簇內節點和bs的距離，而簇內節點與bs的距離的計算，通過在網路配置階段，bs向全網廣播的訊息hello。
臨時簇首選擇中，節點si隨機選擇0～1之間的乙個值，該值若小於節點的閾值t(si)，那麼這個節點就成為臨時簇首節點。t(si)計算公式如下：
式中：r為當前的輪數；g為在最近r mod(1／popt)輪中沒有成為簇首的節點的集合。
deeac演算法不是通過優化leach演算法達到網路內能耗盡可能均勻分布的目標，而是通過優化leach隨機生成的簇結構來減少每一輪的能量消耗，進而不僅使網路能耗均勻分布，而且延長網路的整體壽命。
1.4 leach-new協議
leach-new的做法是：基站在距離r內廣播查詢訊息(nfo)，統計距離r範圍內的感測器節點數，並在這些節點中選擇簇首，其中r是每個感測器節點的發射距離。每個簇頭允許簇內最大的跳數由某個計算值k確定。
簇的建立過程是：當距離基站r範圍內的簇頭確定後，簇頭廣播自己的d和k，那些接收到廣播資訊的節點將k減去1，並選擇加入到k>0的最近的簇頭節點中，並不加入到k為0的節點，如此繼續廣播。而最終那些既沒有收到廣播資訊又不是簇頭的節點，過一段時間後，自選為簇頭，稱為被迫簇頭。
若在協議執行過程中，某些中間節點死亡，那麼在下一輪的路由選擇中，已經死亡的節點就不再加入任何簇內。leach-new簇的建立過程是在簇內節點到簇頭之間形成了多跳路由。而後的過程與leach相似。
leach-new只在距離bs為r的範圍內選擇簇首，因此，資訊可以經簇頭直接傳送至bs，避免了節點離bs的距離近於節點離簇頭的距離，從而節省了能量。實驗**證明leach-new比leach更延長了網路壽命。但是，leach-new只在距離bs為r的範圍內選擇簇首，這一點並不適用於大型感測器網路。
1.5 leach-c協議
leach-c是一種集中式的簇首選擇機制，不同於leach分布式隨機選擇簇頭的方式，它要求只有能量高於網路平均剩餘能量的節點才有可能被選為簇首。leach-c通過每個節點與bs直接通訊以匯報自己的位置和能量資訊的方式，來評估網路剩餘能量的平均值和優化簇首的選擇。bs根據各節點傳送來的資訊選擇簇頭，這樣使得每個區域內的節點數大致相同，實現負載均衡，因而leach-c的效能要優於leach。
顯然，這個過程需要消耗較多的通訊能量，但卻延長了網路第1個節點死亡的時間。
2 teen協議
leach是響應型感測器網路，而teen是主動型感測器網路。所謂主動型感測器網路，它持續監測周圍的物質現象，並以恆定速率傳送監測資料。所謂響應型感測器網路，只在被觀測變數發生突變時才傳送資料。
後者更適合應用在對時問敏感的場合中。teen的基本思想是設定硬、軟閾值以減少資料的傳輸量。硬、軟閾值在每次簇頭輪換時廣播出去，節點監測到的資料第1次超過設定的硬閾值時，就把這次資料設為新的硬閾值，並在下乙個時隙傳送給簇頭。
然後在下面的過程中，只有當監測到的資料超過硬閾值並且監測資料的變化幅度大於軟閾值時，節點才會傳送最新的監測資料，並將它設為新的硬閾值。 teen根據硬、軟兩個閾值來確定是否傳送資料，傳送的資料量要比主動網路少得多，所以節點因傳送資料消耗的能量也減少。**結果也表明，teen在平均能量消耗和存活的總節點數這兩個效能方面要優於leach。
teen存在的問題是：一方面，如果節點監測的資料一直不能超過設定的硬閾值，節點就不會傳送資料，使用者將無法得到任何資料，也不知道這個節點是否失效了；另一方面，節點監測到合適的資料會實時傳送資料，採用tdma的機制會造成資料延遲。
3 pegasis協議
pegasis並不是非常嚴格的簇類協議，卻延用了簇的思想。pegasis的基本思想是：節點通過定位裝置或者通過傳送能量遞減的測試訊號來發現距自己最近的鄰居節點，然後從距基站最遠的節點開始，採用貪婪演算法來構造一條鏈，這條基於地理位置的鏈就是pegasis中的簇。
鏈上的相鄰節點是地理位置上距離最短的兩個鄰居節點，前提是假設這些節點都是靜止的。pegasis中的資料傳輸使用令牌(token)機制：簇頭產生乙個令牌，傳送到鏈的一端，通知末梢節點開始傳輸資料，簇頭與末梢之間的每個節點接收到資料之後，先與自己採集的資料進行融合處理，再向下乙個節點**，直至資料傳輸到簇頭，簇頭受到一側的資料後再將令牌傳送到鏈的另一端，開始同樣的過程。
簇接收到兩側傳送來的資料後再傳送給bs。
pegasis中的資料在距離最短的相鄰節點之間傳輸，因而節點只以最小功率傳送資料分組，在每個中間節點還進行了資料融合，這樣減少了業務流量，整個網路的功耗也就減少了。而事實上，研究結果也表明，使用pegasis的感測器網路的生命週期是使用leach的網路的近2倍。
pegasis採用令牌方式傳送資料，先在簇的一側融合資料，再在另一側融合資料，這樣卻增加了延遲。
4比較與研究
以上介紹的各種wsn中分簇的路由演算法，有的優化簇頭的產生，有的優化簇內的拓撲結構，有的優化簇的資料傳輸。表1中，對具有代表性的簇類協議leach、teen、pegasis，從幾個效能標準方面進行比較。
leach、leach-ee、deeac、leach-new、pegasis都是分布式成簇演算法。所謂分布式演算法，是指通過節點之間的資訊互動和反饋成簇，而在實際應用中，wsn的感測器節點是隨機分布、不完全均勻的，而這種基於區域性資訊成簇的方式容易導致網路負載整體不均勻，造成區域性網路負載過重。但是，這種分布式演算法有較好的擴充套件性、較快的收斂速度和能量的高效性。
相對於分布式成簇演算法，leach-c是集中式成簇方式。集中式演算法基於全域性資訊由基站選擇簇頭，因而生成的簇比較均衡，避免了分布式演算法的不均衡的缺陷，而且集中式演算法的健壯性也比較好。但是，leach-c中的節點必須周期性地向bs匯報它們的能量和位置資訊，能量開銷比較大，擴充套件性也不好，一般只適合中小型網路。
無線感測器網路中的能量高效多路徑路由協議
作者 王強 中小企業管理與科技 上旬刊 2014年第12期 摘要 無線感測器網路中能量高效路由協議的目標是盡可能延長網路生存時間。多路徑路由協議可以使網路流量在多條節點不相交路徑間均衡分配，從而可以有效增加網路壽命。另外，安全的資料傳輸也成為wsn廣泛應用所必須的重要提前。本文提出一種無線感測器網路...
無線感測器網路中的能量高效多路徑路由協議
作者 王強 中小企業管理與科技 上旬刊 2014年第12期 摘要 無線感測器網路中能量高效路由協議的目標是盡可能延長網路生存時間。多路徑路由協議可以使網路流量在多條節點不相交路徑間均衡分配，從而可以有效增加網路壽命。另外，安全的資料傳輸也成為wsn廣泛應用所必須的重要提前。本文提出一種無線感測器網路...
無線感測器網路路由協議研究進展及發展趨勢
摘要 描述了無線感測器路由協議所面臨的問題與挑戰，分析和比較了典型的平面路由協議及層次路由協議。最後總結了理想路由協議應該具有的特點以及路由協議未來的研究策略及發展趨勢。關鍵詞 無線感測器網路 路由協議 平面路由 層次路由 研究進展 中圖分類號 tp393文獻標誌碼 a 文章編號 1001 3695...