基于LEACH協議的簇頭優化協議研究

張長宏，昝風彪，唐明虎

（青海民族大學 計算機學院，青海 西寧 810007）

無線傳感器網絡 WSN （Wireless Sensor Network）是由部署在監測區域內大量的廉價微型傳感器節點組成，通過無線通信方式形成一個多跳的自組織的網絡系統。目的是協作感知、采集和處理網絡覆蓋區域中感知對象的信息，并發送給觀察者。傳感器網絡在軍事和民用領域都有著非常廣闊的應用前景[1]。但是這些傳感器節點體積小，能量有限，不能更換電池，因此，將最大限度延長網絡的生命周期作為一個路由協議的評價標準。從網絡的拓撲角度分為平面路由協議和分層路由協議。對于大規模網絡而言，分簇的層次路由協議相比于平面路由協議，其采用簇頭節點的融合功能有效地減少了數據通信量，從而顯著延長了整個網絡的生命時間。LEACH（Low Energy Adaptive Clustering Hierarchy）[2]協議是一種典型的分簇層次路由協議。LEACH中簇頭節點的選擇是隨機產生的，沒有考慮到節點的剩余能量，另外從簇頭到基站采用的是單跳的方式，當距離遠時，能量消耗太快。本文基于以上兩點對簇頭進行了優化。

1 LEACH協議概述

1.1 LEACH算法

LEACH是Heinzelman等為WSN設計的，仿真表明，它與一般的平面多跳路由協議和靜態分簇路由協議相比，無論是第一個節點死亡的輪數和最后一個節點死亡的輪數都提高了3倍[3]。LEACH的每輪分為簇的建立階段和數據傳輸階段兩個部分。為節省能量，一般數據傳輸持續時間要大于建立時間。

1.1.1 簇的建立階段

設某個時刻 t，每個傳感器節點在第 r輪時從（0，1）之間選擇一個隨機數,如果選定的值小于某個閾值Kn(t)，這個節點就成為簇首節點，Ki（t）由式（1）計算得到。

其中，G表示節點在前r mod（1/p）輪沒有當選簇頭節點的集合；p表示最優簇頭數占所有節點數的比例，p=k/N，N表示節點總數，k為分簇數。在第1輪中每個節點成為簇頭的概率為p，選出的簇節點個數都為N×p。在接下來的 N/k－1輪中不會當選簇頭，利用式（1）計算可知，在沒有節點死亡時每輪選出的簇頭都為N×p，但實際中有一定的波動。選為簇頭的節點向網絡廣播信息，通知產生了一個新簇頭，接收到信息的節點根據信號的強度選擇一個距離其最近的簇頭，并告知簇頭節點，最后，簇頭采用TDMA方法為簇中每個節點分配向其傳送數據的時間片。

1.1.2 數據傳輸階段

傳感器節點將采集的數據按照簇頭分配的時隙傳送到簇頭節點，簇頭節點進行數據融合將結果直接發送到基站。

1.2 網絡模型和最優簇頭數的計算

網絡由N個隨機部署的傳感器節點組成，同時有以下假設：（1）傳感器網絡為高密度靜態網絡，傳感器節點和基站部署后均不再發生位置移動，基站唯一，而且基站的能量是無限制的，其他節點有相同的能量；（2）節點具備數據融合功能，每個傳感器節點都有一個唯一的標識（ID）；（3）節點可以根據接收方距離的遠近調整其發射功率以減小能量消耗。LEACH協議采用的一階無線電模型，當發送距離較近時（d≤d0），采用自由空間信道模型；當發送距離較遠時（d＞d0），采用多路徑衰減模型。具體如下：

傳感器節點發送l bit數據消耗的能量為：

傳感器節點接收l bit數據消耗的能量為：

假設基站遠離隨機分布的節點（d＞d0），每一輪中，簇頭節點消耗的能量模型為：

其中，EDA數據融合能量參數，dtoBS是簇頭到基站距離。

隨機分布的節點（d≤d0），每一輪中，非簇頭節點消耗的能量模型為：

其中，dtoCH是簇成員到簇頭距離。

其中，ρ是簇的密度，ρ=k/M2，則 E[dtoCH2]=M2/2πk。

每輪中，一個簇所消耗的能量為：

整個網絡的能量消耗為：

對式（8）取 k值變化的最優簇頭數目：dEtotal/dk=0，求得最優簇頭數為：

根據式（9）可知，最優簇頭數與分布的節點數成正比，與到基站的距離成反比。這代表著最優簇頭隨節點數的增加而增大，另外，離基站越遠，簇頭數越少，因此，向基站傳送數據必須先進行融合，再進行傳輸，這樣才能最大程度地節省能量。當節點部署在100×100正方形區域，基站在坐標（50，175）位置時，基站到簇頭的最小距離是75 m，最大距離是185 m，則最佳簇頭數的范圍為 1～6，取 5，則 popt=0.05。

2 優化的協議

根據上面的分析可知，LEACH協議中簇頭的選擇是隨機產生的，每個節點每次傳輸信息消耗的能量是不同，雖然每個節點都得到了均衡的使用，但每個節點的剩余能量不同，這使得部分節點提前耗盡能量，網絡進入不穩定期。另外，LEACH協議采用單跳的方式傳輸信息，當簇頭離基站較遠時，使部分節點的能耗加大，壽命縮短。針對LEACH協議的這些缺陷，提出了新的協議。該協議的基本思想是對LEACH協議的簇頭進行優化，并形成多跳機制進行數據傳輸。與LEACH協議相近，本協議也采用了輪，每輪分為簇的建立和穩定傳輸兩個階段。在簇的建立階段引入了節點剩余能量和估計能量的比值 EE，對 LEACH協議中的閾值 Ki（t）進行優化，選出初級簇頭。然后以距離最近的原則選出離基站最近的節點為超級節點，再采用貪婪算法將初級簇頭組成一條鏈，每個節點將采集的數據傳給初級簇頭進行數據融合后沿著鏈最后發給基站。該算法不僅考慮了節點的剩余能量，同時以最小的代價將數據傳給基站，有效地延長了網絡的壽命。

2.1 簇的建立

LEACH協議在簇頭選擇過程中，每個節點都要產生一個 0～1的隨機數與閾值 Ki（t）進行比較，小于閾值則選為簇頭。參考文獻[4]通過先用LEACH協議產生臨時簇頭，再根據節點的平均能量和質心位置去優化選簇，這就需要額外的廣播信息告知自己的位置信息和能量信息，還要進行大量的計算，使簇的建立階段浪費了許多能量。因此，基于既要考慮節點的剩余能量，又要降低開銷的思路，引入了節點剩余能量和估計能量的比值EE，其計算式如下：

其中，r為當前運行的輪次，N0為無線傳感器網絡的預計運行輪次，E0為節點的初始能量，Ei為節點 i的剩余能量。使每個節點產生的隨機數與 Ki′（t）相比較，剩余的能量越大，比值EE越大，當選簇頭的可能就越大；反之，剩余的能量越小，比值EE越小，當選簇頭的可能就越小，從而避免了低能量節點能量耗盡。當選簇頭的節點向網絡廣播信息，通知產生了一個新簇頭，接收到信息的節點根據信號的強度選擇一個簇頭，并告知簇頭節點。

此外，各簇頭節點向基站發送廣播信息，基站根據信號的強度選與其距離最近的節點為超級節點，并給選定的超級節點發信息，超級節點根據各簇頭節點廣播的信息，選擇最近的簇頭節點為下一跳，并發送廣播通知下一節點，下一節點重復同樣的操作，直到所有的簇頭加入鏈。

2.2 穩定傳輸階段

傳感器節點將采集的數據按照簇頭分配的時隙傳送到簇頭節點，鏈中最后一個簇頭節點進行數據融合，將結果傳送到鏈中的下一簇頭節點，下一級簇頭節點接收到所有簇內節點和簇頭節點的信息后進行數據融合，再傳到鏈中的下一個簇頭節點。進行反復操作，直到超級節點融合數據后直接發送到基站。

3 仿真結果分析

實驗采用MATLAB進行仿真，模擬實現了LEACH和本文提出的優化的新協議的性能比較。仿真主要參數如下：100個節點隨機分布在100 m×100 m的區域中，基站位于（50，175）。式（9）選定的最佳簇數為 5，則簇頭的概率p=0.05，節點的預計運行輪次N0=1 500輪。其他主要參數如表1所示。

表1 仿真環境參數

圖1給出了優化的新協議與LEACH協議網絡生存周期的比較，以仿真輪數代表時間。LEACH協議和新協議的第一個節點死亡出現的輪數分別為667、961，半數節點死亡的輪數分別為913、1 117，最后一個節點死亡的輪數分別為1 719、1 494。從圖1中可以看出，新協議第一個節點死亡的輪數和半數節點死亡的輪數都比LEACH長，尤其是第一個死亡節點出現的時間比LEACH長了44%。

圖1 網絡生存周期比較

在無線傳感器網絡中，將從仿真開始到第一個節點死亡的時期稱為穩定期，該值越大，網絡的性能越好。將第一個節點死亡到全部節點死亡稱為不穩定期，不穩定的長短表明了網絡的收斂性，不穩定期越長，網絡性能越長。從圖1中還看到，新協議比LEACH協議有更好的收斂性。

根據結果分析出主要的原因，一方面是對于簇頭的優化，另一方面是采用多跳的傳輸技術比較節省能量，并且使能量的分布更加均衡，從而使第一個死亡節點出現時間比較晚，同時使網絡有了很好的收斂性。

本文在分析LEACH協議的基礎上提出了一種簇頭優化協議，仿真結果顯示，第一個節點死亡的時間相比LEACH協議有了很大提高，同時，網絡的不穩定期縮短，有很好的收斂性，提高了網絡的性能。

[1]孫利民.無線傳感器網絡[M].北京：清華大學出版社，2005.

[2]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy efficientcommunication protocolforwireless microsensor networks[C].Proceedings of the 33rd Hawaii International Conference on System Sciences，2000.

[3]HEINZELMAN W R.An application-specific protocol architecture forwirelessmicrosensornetworks[J].IEEE Transactions on Wireless Communications， 2002， 1 （4）：660-670.

[4]張品，徐智福，孫巖.一種新的基于簇頭的WSN路由協議[J].傳感技術學報，2009（7）：1013-1017.