基于LEACH的無線傳感器網絡分簇路由協議的改進研究

齊世霞 薛小偉

（1.延安大學數學與計算機科學學院 陜西省延安市 716000 2.延安大學附屬醫院 陜西省延安市 716000）

1 引言

無線傳感器網絡是當前眾多學科研究的熱點，是實現數據的采集、處理和傳輸于一體的綜合型智能網絡，目前正處于蓬勃發展的階段，隨著其應用越來越廣泛，對諸多領域都具有巨大影響。無線傳感器網絡由微傳感器節點組成，這些節點既可以獲取信息數據，也可以進行網絡中繼。每個傳感器節點都由傳感器、微處理器以及無線收發機組成，傳感器節點與節點之間互相緊密相連以獲取物理數據。傳感器節點通過片上微處理器完成復雜任務，通過無線收發機實現互連及數據傳輸。傳感器節點一般都是非動態的，由能量有限的電池提供能源，從而導致網絡拓撲在節點位置不變的情況下也可能會因為其能量管理操作而發生動態變化。在這種情況下，使傳感器節點功耗最小并保持通信是最重要的，高能效機制的無線傳感器網絡相對于還依舊依賴電池的系統具有更長的生存周期。在無線傳感器網絡的網絡協議棧中，網絡層的研究最多，其路由協議的分類以及具體的解決算法主要分為以下四類，如圖1 所示。

圖1 ：WSN 路由協議分類

2 基于分層結構的無線傳感器網絡路由協議

基于分層結構的無線傳感器網絡路由協議在分層結構中組成簇，分簇算法將通信限制在局部區域且只向剩余的網絡部分發送必要的信息，一組節點形成一個簇，簇成員之間通過簇頭進行交互。無線通信的不穩定性和傳感器網絡的特點等這些問題阻礙了應用于WSN 中針對無線自組織網絡的路由協議的發展。為了盡可能的降低能耗，使WSN 的生存周期更長，已經提出了許多基于分層結構的路由算法協議，主要包括以下幾種常見算法：高效自治算法LEACH，執行過程按“輪”進行，每輪包括兩個階段，即簇的形成階段和穩定工作階段，由每個節點根據隨機數自主決定是否當簇頭，保證各個節點等概率的擔任簇頭；以節點地理位置為依據的分簇算法GAF，最初應用在Ad Hoc 網絡中，采用虛擬單元格劃分機制，根據地理位置信息將整個網絡劃分成很多虛擬小區域，每個小區域內定期選舉一個簇頭節點，簇頭節點為正常工作狀態，剩余節點為休眠狀態，每個小區域內的節點互相協作；PEGASIS 算法提出了構造節點鏈來解決簇重疊區域的問題，鏈的創建采用貪婪算法，選擇距離自己最近的鄰居節點進行下一跳；混合能量效率分布式分簇HEED算法是，以節點的剩余能量作為首要因素，簇內的通信代價作為次要因素來進行簇頭的選擇和分簇，按輪進行，每輪包括分簇階段和網絡運行階段；TEEN 算法采用多級分簇結構，簇內節點將采集到的數據傳送給簇頭節點，簇頭節點對數據進行進一步處理后，再傳送給比它高一級的簇頭，層層遞進，最終將數據傳送到匯聚節點，通過設計設置硬門限和軟門限兩種門限值來提供基于響應的應用，以減少發送數據的次數；APTEEN 算法是在TEEN 算法基礎上發展起來的，簇內節點采用時分復用的方式進行數據傳輸，通過設置軟硬兩種門限值確定發送數據的時間和頻率；TopDisc算法是基于最小支配集模型提出的分簇算法，采用啟發式的方法建立骨干網絡拓撲，采用顏色標記理論來選擇簇頭節點，該算法可以在密集部署的傳感器網絡中快速的形成分簇，但在產生簇頭時沒有考慮剩余能量的問題；SOP 算法將網絡中的節點分為兩類，傳感器節點是動態的并負責收集數據，路由節點是靜態的用于形成主干網；EARSN 協議算法是基于三層體系結構的路由協議，由終端用戶在網絡運行前就對傳感器節點進行分簇且簇頭不受能量控制，算法依據兩個節點間的能量消耗、延遲最優化等性能指標計算路徑代價函數，簇頭節點再以此作為鏈路成本選擇最優路徑；除了上述算法外，還有GEAR、SPAN、MECH 等分簇算法，各種基于分層結構的無線傳感器網絡路由協議的性能比較如表1 所示。

表1 ： WSN 路由協議的性能比較

武小年等通過定義節點的能量因子和位置均衡因子建立新的適應度函數，選擇出優秀的候選簇頭節點，之后再通過優化的自適應學習因子加快其位置更新速度；王宗山等提出一種基于人工蜂群算法的能量高效分簇路由協議，在簇頭選舉時通過定義能量因子、位置因子和向心率因子設計高效的適應度函數，在穩定傳輸時通過在每個簇頭和基站間尋找合適路徑并引入了輪詢控制機制來平衡且降低網絡能耗；趙東方等提出了基于路由樹的分布式自適應動態多跳分簇路由協議DABMC，設置剩余能量和延遲時間來選擇簇首，簇間路由為以sink 節點為根節點的動態路由樹來選擇下一跳；茍平章等通過AGNES 算法進行均勻分簇，然后根據剩余能量、節點與基站之間的距離以及兩者的權重因子進行分布式簇頭選舉，并采用改進后的最短路徑優先算法進行多跳路由；王海浪等通過對整個網絡區域進行均勻分區優化以及改進綜合節點的剩余能量、區域內平均能量、距離基站的距離等多個因素來作為判斷是否選擇成為簇頭節點；張本宏等提出一種基于二分K-means 的均勻分簇算法UCOA，利用二分K-means 算法對整個網絡均勻分簇，加入節點的剩余能量、距離因子對簇頭選舉閾值公式進行改進；王出航等提出一種基于改進遺傳算法的WSN 信任感知安全路由方法，采用單個染色體編碼進行簇頭選擇和路由搜索；胡黃水等提出一種結合近鄰傳播算法AP 和遺傳算法的分簇路由協議EAPGA，根據剩余能量、節點間距離、節點到基站的距離以及節點中心度選擇最優簇頭，再通過簇頭能耗偏差和遺傳算法進行尋優；和煦等提出一種基于改進正弦余弦算法的分簇路由協議CRISCA，將正弦余弦算法和慣性權重因子進行結合，得到改進的正弦余弦算法進行最優簇頭的選擇；蘭婷婷等設計了一種最優廣域WSN 數據聚合模型ODAM，在無線接收器中進行節點間的計算，采用花粉算法FPA 對聚合模型進行優化來確保簇中能量的有效排列；趙小強等提出了一種基于模擬退火SA 算法和改進灰狼優化器GWO的HWSN 路由協議SA-MGWO，在選取簇時根據節點能量的異構性對節點定義不同的適應度函數來計算適應值，之后根據狼群與獵物的距離以及系數向量對該值進行動態更新，最后利用模擬退火算法選取最優簇集；余修武等提出了一種基于螢火蟲算法優化模糊C 均值的WSN 路由算法FFACM,在分簇時采用螢火蟲算法計算初始聚類中心，建立適應度函數選取簇首節點并動態更新，建立代價函數選擇簇間多跳路由，降低簇首節點的負載；李蕾等提出一種基于證據理論加權融合的無線傳感器網絡路由算法，引入聚類分析算法進行分簇，之后后采用證據理論計算剩余能量、節點間通信距離、通信能耗的權值進行綜合評價才選出簇首。

3 基于LEACH協議的無線傳感器網絡分簇路由協議優化設計思路

3.1 LEACH協議概述

LEACH 主要通過基于簇的操作使WSN 減少功耗，按照輪次周期性的進行執行，每個輪次由分為兩個階段，在一個輪次中保持簇不變但重新選擇簇頭，每個輪次分為建立階段和穩態階段兩個階段。

在建立階段主要進行簇頭選舉并進行分簇，在簇的形成階段，采用循環選舉機制，使得各個節點等概率的擔任簇頭。其選舉簇頭的過程為：假設網絡中有N 個節點，每輪執行過程生產k 個簇。每個節點i 在第r+1 輪選舉開始時產生一個0～1 之間的隨機數，如果這個數小于設定的閾值P(t)，則該節點被選為簇頭節點。閾值P(t)的計算公式為：

在式（1）中，r 表示選舉輪次數，k 表示選舉的簇頭數目，N 表示網絡中的總節點數，C(t)=0 表示節點i 已經當選過簇頭，C(t)=1 表示還未當選過簇頭，即只有在以前的輪次中沒有做過簇頭的節點才能成為當前輪次的簇頭；在式（2）中，R(i)為0～1 之間的一個隨機數，P(i,r)表示節點i 在第r 輪次成為簇頭的概率。當選舉輪次數r=N/k 時，一個循環選舉周期結束，所有節點都正好當選過一次簇頭。在節點成為簇頭后，采用CSMA 的MAC 協議向鄰居節點廣播通告自己成為簇頭的消息，避免多個簇頭的廣播發生碰撞。

在穩定階段，進行數據傳輸，簇內節點在各自分配的時隙內向簇頭節點發送數據，其他時間睡眠以減少消耗，簇頭節點一直保持活躍，進行數據融合等任務并將處理結果發送給匯聚節點。在持續工作一段時間后，網絡重新選取下一輪次的簇頭并建立新簇。為了節省資源降低功耗，LEACH 穩定階段的持續時間要比建立階段的時間長。

3.2 LEACH算法的優化思路

LEACH 算法將簇頭責任分配給具有更高剩余能量的節點，且使所有節點可以等概率的擔任簇頭，避免了簇頭過分消耗能量，提高了整個網絡的生存時間，但是它由每個節點產生的隨機數對比設定的閾值來確定是否成為簇頭節點，每個周期選舉生成的簇頭的數量和位置都會發生改變，除此之外，周期性的選舉簇頭過于頻繁，引發的通信量也耗費了大量能量。

在LEACH 協議的基礎上，在簇頭節點選取時引入成本函數，每個節點的成本被定義為一個函數，這個函數表示為：

在式（3）和（4）中，E(s)表示節點j 的剩余能量，E(x,y)為節點所在感知區域的剩余總能量，C 為節點i 的感知區域。

簇頭的選擇基于每個節點的感知成本，一個簇內成員的節點只能發送信息到相應的簇頭，從節點i 到匯聚節點的一條路的感知成本可以定義為：

在式（5）和（6）中，C(s,s)是每條鏈路的成本，C(s)是基于成本函數的節點成本，E(s,s)和E(s,s)分別是發送和接收一個分組數據消耗的能量。通過在式（5）和（6）就可以得到一條簇頭到匯聚節點的最小成本路徑。

基于成本函數的操作執行可以分為六個階段：

第一階段：節點和其鄰居節點交換剩余的能量信息，每個節點計算自己的感知成本。

第二階段：簇頭選擇階段，鄰居范圍內最小成本且能量大于一定閾值的節點被選為簇頭。

第三階段：建立簇頭和匯聚節點之間的端到端路徑，網絡中任何節點通過最小成本路徑從匯聚節點收到路由并發現消息。

第四階段：形成簇，每個非簇頭節點選擇最近的簇頭然后通過發送一個入簇消息加入該簇。

第五階段：激活傳感器節點。

第六階段：每個活動節點收集自身信息并上報給簇頭，簇頭匯聚來自簇內多個傳感器節點的數據并發送給匯聚節點。

4 結語

從無線傳感器網絡的發展現狀來看，在國內外，基于分層結構的WSN 路由協議一直在不斷地發展且取得了不錯的研究成果。本文針對傳統的LEACH 協議在簇頭節點的選擇及拓撲結構上的缺點，提出了一種改進的LEACH 算法的優化設計思路，采用基于成本函數的方法進行簇頭的選擇和路由的建立，得到簇頭節點到匯聚節點的最小成本路徑，在感知范圍和生命周期之間有一個較好的平衡。在今后的研究工作中，需要在有限的條件下，實現真實WSN 系統的搭建，以便進一步研究該優化改進算法的性能，從而使簇頭節點的通信路徑選擇更加科學合理。