無線傳感器網絡LEACH協議的改進

牛建兵，劉廣鐘

（上海海事大學 信息工程學院，上海 201306）

0 引言

無線傳感器網絡 （Wireless Sensor Network，WSN）是由部署在監測區域內大量的廉價微型傳感器節點通過無線通信方式連接形成的一個多跳的自組織的網絡系統，其目的是協作地感知、采集和處理網絡覆蓋區域中感知對象的信息，并發送給觀察者[1]。WSN不需要固定的網絡支持，具有快速展開、抗毀性強等特點，可廣泛應用于軍事偵察、環境監測、醫療監護和其他商業領域[1]。

在WSN體系結構中，網絡層的路由技術對WSN性能的好壞有重要影響。隨著國內外對WSN的研究，許多路由協議被提了出來，從網絡拓撲結構可以分為兩類：平面路由協議和分簇路由協議。在WSN的實際應用中，由于通信損耗能量與傳送的數據量和到達目標的距離平方成正比，因此采用基于分簇的路由協議相對平面路由協議具有更好的適應性和節能性[2]。

本文提出的路由協議是基于最經典的分簇路由協議 LEACH（Low Energy Adaptive Clustering Hierarchy）提出的，協議中簇首的選擇分為奇數和偶數輪。奇數輪簇首選擇中引入節點能量等參數，避免低能量的節點成為簇首。簇首確定后，簇首廣播自己為簇首的消息，其他節點根據接收到的信號強度加入不同的簇。在偶數輪簇首的選擇時，網絡不再大規模地動態生成簇，只是選擇上一輪中簇內節點能量最大的節點作為本輪的簇首節點，簇首節點選擇后，通過廣播通知其簇內節點自己成為簇首節點。通過能量參數的引入使得簇首選擇避免了低能量節點成為簇首節點，而且引入奇數和偶數輪降低了簇的生成開銷，有效節省了網絡的能量，延長了網絡的生命周期。

1 LEACH協議

該協議使用自適應成簇和簇首節點輪換技術，周期性地執行任務，每一個周期分為兩個階段，分別是簇的建立階段和穩定運行階段，這兩個階段的時間比在協議中是1：19，穩定運行時間要遠遠長于建簇時間，這可避免分簇過于頻繁造成過多的能量損失。在穩定運行階段，各個非簇首節點將按簇首分給的時隙來發送數據給簇首，簇首收到各個簇成員發來的數據進行綜合處理后再發給Sink節點。

LEACH[3]協議選擇簇首策略具體如下：在建簇中的簇首選擇階段，每個節點在0～1之間隨機選擇一個數與閾值T（n）進行大小比較，如果小于閾值，則其將被選中成為新一輪的簇首，并廣播自己是簇首的消息。如果節點已經被當選過簇首，則將 T（n）置為0，這樣將不可能再當選簇首了。閾值T（n）表示為：

其中，n表示傳感器節點數，k表示簇頭節點數，r為輪數，G為網絡生存期的總回合數。

LEACH協議適用于大型的無線傳感器網絡，與平面路由協議相比，LEACH協議在節能方面有比較突出的表現，但也存在一些問題，比如LEACH算法簇頭的選擇沒有考慮到節點的能量問題，如果一些能量較低的節點成為了簇首節點，那么此節點很快就會將能量耗盡而退出網絡，降低了網絡的壽命；同時LEACH算法簇的生成過于頻繁，按照輪的方式運行，每輪完成后，網絡將重新進入簇的生成階段，簇的頻繁生成將會增大網絡的能量消耗。

2 LEACH-OE

在研究了LEACH協議存在的一些問題后，本文提出了一種基于奇偶輪選擇簇首的協議LEACH-OE（Odd and Even number round of LEACH）。該協議大大降低了成簇的輪數，只有在奇數輪才會進行簇首的隨機選擇和簇內節點入簇操作，而且簇首選擇時，考慮了能量因素，使得能量高的節點成為簇首節點的概率更大，在偶數輪僅僅是選擇簇內能量最高的節點作為本輪的簇首節點，之后通知其他簇內節點自己為簇首節點，節省了成簇時的能量消耗。

2.1 模型介紹

（1）網絡模型：基站（BS）固定且能量供應充足；各節點同構且具有節點編號；各節點可感知它的剩余能量；各節點可以與基站直接通信；各節點可根據接收者距離調整發射功率[4]。

（2）信道模型：傳感器節點發送k bit消息d距離時消耗的能量 ETX（k，d）：

接收 k bit消息消耗的能量 ETR（k）是：

在式（2）中，發送與接收節點距離大于臨界值 d0=使用多路徑模型；否則使用自由空間模型。Eelec是發射電路和接收電路消耗的能量，εfs和 εamp都是發射放大器所消耗的能量。

2.2 算法思想

（1）基于剩余能量的簇首選舉

本協議在簇首的選擇和成簇機制上進行了改進，簇首選擇時，分為奇數輪和偶數輪。當奇數輪時 （r mod 2==1）采用簇首的隨機生成，此過程中，不但考慮節點是否當選過簇首節點，還考慮節點的能量因素，降低了低能量節點優先成為簇首節點的概率。由各個傳感器節點隨機生成一個[0，1]之間的隨機數，比較此隨機數與閾值 F（n）的大小，如果小于 F（n）則成為簇首節點，然后廣播自己成為簇首節點的信息，而其他節點根據接收到的信息的強度自主加入相應的簇。閾值F（n）表示如下：

當偶數輪（r mod 2==0）時，根據各個簇內節點的能量信息，由上輪簇首節點決定本輪簇首節點的選擇，上輪簇首根據簇內節點能量 Ecur（i）的大小將簇內節點進行排序，然后簇首將能量最大節點的編號ID向簇內進行廣播，簇內各個節點根據接收到的信息和自己節點ID進行比較，當節點ID與接收到的信息中的節點ID相同時，該節點廣播自己成為本輪簇首節點的信息，各個簇僅僅是改變了簇首而簇內節點不發生變化。圖1是簇首選擇流程圖。

圖1 簇首選擇流程圖

（2）數據發送階段

在簇首選擇成功后，簇首根據成員節點數目創建TDMA時間表，并告知成員節點發送數據的時隙，成員節點只有在所分配的時隙內發送數據，其余時間則處于休眠狀態以節約能量，成員節點發送的數據在簇首處融合并最終由簇首發送至基站。在數據的傳送中為了防止簇與簇之間的通信干擾，每個簇都使用一個特殊的代碼，簇頭到基站的數據發送采用載波檢測多址接入技術（CSMA）。當簇頭有數據發送時，先檢測信道是否空閑，當信道有數據傳送時節點等待，直到信道空閑一段時間后再進行數據的發送。

（3）能耗分析

在M×M的區域部署N個無線傳感器節點，分為k個簇，每個簇中有個節點（一個簇首節點，其余為非簇首節點），傳感器節點發送l bit數據，簇首在一輪中消耗的能量為：

簇中每個非簇首消耗的能量為：

一個簇簇首和非簇首節點消耗的總能量為：

k個簇消耗的總能量為：

從以上可知，傳感器網絡中，網絡的能耗主要是簇傳輸數據能量消耗和成簇的能量消耗。在已知網絡中，節點數N、發送和接收電路的能耗Eelec、功率放大系數εamp和 εfs、數據融合能耗 EDA都是一定的，而簇數 k、簇首節點到基站的距離dtoBS、簇內成員到簇首的距離dtoCH是不確定的，但是在本文討論的網絡中因為都是隨機的，假設其差別不大。現在能量消耗的節省主要從成簇方面進行考慮，Etotal是一定的，因為引入奇數、偶數輪成簇機制，每兩輪才產生一輪成簇的能量消耗，很顯然延長了總的網絡壽命，同時，在簇首的選擇時，只有那些剩余能量較高的節點優先選為簇首節點，可以有效均衡網絡能耗，進一步延長網絡壽命。

3 仿真結果及其分析

3.1 仿真環境

為了驗證本文算法的性能，在MATLAB平臺上進行仿真比較。100個無線傳感器節點隨機分布在100 m×100 m的區域內，根據參考文獻[5]的分析，LEACH算法每輪最佳簇首個數約為節點總數的5%，仿真中選擇k為5，仿真參數如表1所示。

表1 網絡參數

3.2 LEACH和LEACH-OE性能的比較

在MATLAB環境下仿真LEACH-OE與LEACH協議，兩種協議運行5 000輪后生存和死亡節點的分布如圖2所示。LEACH協議在1 127輪開始有節點死亡，而LEACH-OE在1 435輪開始有節點死亡，這是因為在簇首選擇時LEACH-OE考慮了能量因素。而節點完全死亡LEACH-OE達到了2 782輪，遠遠大于LEACH的2 237輪，輪數提高了24.5%左右。因為LEACH-OE協議引入了奇數輪成簇機制，更節省網絡的整體能量，延緩節點死亡的時間，從而使網絡生命周期得到延長。

圖2 LEACH和LEACH-OE死亡節點的比較

兩種協議能量的消耗如圖3所示，比較可知在運行同等輪數的情況下，LEACH-OE能量的消耗明顯比LEACH要小，在運行輪數為1 000的情況下，LEACHOE比LEACH能量消耗要少21%左右，如圖可知，最終網絡中節點全部死亡的時候網絡總的能量消耗是相等的，運行的時間越長，網絡更有優勢。

圖3 LEACH和LEACH-OE能量消耗的比較

4 結論

為提高網絡的生存時間，平衡節點的能量消耗，本文提出了一種基于能量和奇偶輪的分簇式無線傳感器網絡路由協議（LEACH-OE），在奇數輪成簇的過程中，簇首的選擇考慮到節點的能量因素，選擇能量更高的節點作為簇首，在偶數輪直接選擇能量最高節點作為簇首節點。通過MATLAB仿真實驗，對LEACH和LEACH-OE在能量消耗、運行輪數方面進行比較。結果表明，LEACH-OE協議在負載均衡和能量消耗方面有很大的改善，可以有效地延長網絡生存時間。

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

[2]AKYKLDIZ I F.Wireless sensor networks：a survey[J].Computer Network，2002，38（4）：393-422.

[3]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.An application-specific protocol architecture for wirelessmicrosensornetworks[J].IEEE Transaction on Wireless Communications，2002，1（4）：660-670.

[4]BANDYOPADHYAY S，COYLE E J.Minimizing communication costs in hierarchically clustered networks of wireless sensors[J].Wireless Communications and Networking，2003（2）：1274-1279.

[5]張輝，許峰.WSN中基于權值的Leach協議的研究與改進[J].微計算機信息，2010，26（8）：199-201.