基于分區簇頭選擇簇間多跳的路由協議

劉愛東，盧中武，許 芹

（1.海軍航空工程學院 a.兵器科學與技術系；b.研究生管理大隊，山東 煙臺 264001；2.煙臺東方威思頓電氣有限公司，山東 煙臺 264000）

0 引言

在集群路由協議中，典型的協議低能耗自適應集簇分層型協議(Low Energy Adaptive Clustering Hierarchy，LEACH)是一種以最小化傳感器網絡能量損耗為目標的集群式路由協議，是應用較廣泛的協議之一[1-2]。響應型協議TEEN與LEACH的實現機制非常相似，只是更適合應用在環境變化較頻繁的場合中[3-4]。對高能效傳感信息采集協議PEGASIS，當節點規模龐大時該協議的容錯性不佳[5]。

本文針對LEACH協議中成簇算法沒有考慮節點的剩余能量、數據傳輸時簇頭和基站直接通信等不足，提出一個基于分區簇頭選擇和簇間多跳的路由協議。

1 LEACH 路由協議

1.1 LEACH協議成簇算法

LEACH協議選舉簇頭的過程如下：節點產生一個0和1之間的隨機數，如果這個數小于閾值T (n)，則廣播自己成為簇頭。

非簇頭節點收到廣播后選擇離自己最近的簇頭加入，當簇頭節點收到所有簇內節點的加入信息后，產生TDMA 信息并通知該簇中所有節點。

簇內節點收到TDMA后就進入休眠，直到自己的時間槽才醒來發送數據給自己的簇頭。當簇頭收

1.2 協議在能耗方面存在的不足

與一般的平面多跳路由協議相比，LEACH協議可以延長網絡生存周期15%以上[7]，但該協議在能耗方面仍然存在以下不足：

1)簇頭選舉時沒有考慮節點的剩余能量，這就可能使剩余能量少的節點也被選為簇頭，從而加速了該節點的死亡。

2)簇頭分布不均勻，使得有些區域的節點需長距離與簇頭通信。

3)節點與基站直接通信，使離基站遠的簇頭消耗了更多的能量。集完數據，進行融合后直接發給基站[6]。

2 改進的路由協議

本文針對LEACH在能耗方面存在的不足，提出一種分區簇頭選擇、簇間多跳的路由協議，并在相同的環境參數下對兩種協議進行了仿真。

2.1 基于分區的簇頭選擇

新協議充分考慮了簇頭節點在空間上的分布，由基站控制發射能量，廣播不同強度的信息，將監測區域分成環形區域。如圖1所示，監測區域被分成3個環形區域。

圖1 監測區域分成環形區域

基站根據各區域面積和最佳面積的比值決定各區域期望的簇頭數。簇頭數由下式確定，

式中：SZONEi為區域i的面積；Sopt為最優面積。由文獻[6]可知，LEACH 中簇的最優數如下式所示。

參照文獻[6]，在本文中取Kopt=5。為了使監測區域中簇頭分布盡量均勻，且確保簇內節點與簇頭之間的通信距離盡可能小，同時考慮不同強度信號的衰減距離以及傳感器節點接收器的敏感強度，可將監測區域分成3個環形區域。離基站距離小于d0的為ZONE0，大于 d0小于d的區域作為ZONE1，剩余區域為ZONE2，其中ZONE0 選出1個簇頭，ZONE1和ZONE2 各選出2個簇頭。

各區域根據期望的簇頭數進行簇頭選舉，選舉的閾值為：

式中：k'為某環形區域期望的簇頭數；N'為該環形區域節點數；r為輪數；rs為節點連續未成為簇頭的輪數；Eres為節點剩余能量；Einit為節點初始能量。

節點隨機產生一個0和1之間的隨機數，如果該數小于T(n)則廣播自己成為簇頭的消息，該消息包含自己所在的區域以及自身的剩余能量。非簇頭節點收到消息后選擇距離自己最近的簇頭加入，簇頭根據加入的節點數產生TDMA。

2.2 簇間多跳的數據傳輸

簇頭節點收集完簇內節點的數據后，進行數據融合并選擇下一跳簇頭節點進行傳送。簇頭節點通過計算自身的權值和其他簇頭節點的權值，選擇比自己權值大的最大權值簇頭進行數據傳輸。下一跳簇頭的權值計算如式(5)所示：

式(5)中：Er'es為下一跳簇頭的剩余能量；為該簇頭節點到下一跳簇頭節點的距離的平方；為下一跳簇頭節點與基站的距離的平方。

自身的權值計算如公式(6)所示：

式(6)中：Eres為該簇頭的剩余能量；為該簇頭到基站的距離的平方。當自身權值為最大權值時，將數據直接發送給基站。

3 仿真與驗證

3.1 仿真環境設置

本文選用UC Berkley 分校研發的網絡仿真工具NS2[8]作為仿真平臺，通過仿真比較改進后的協議和LEACH協議。設定在邊長為100 m的方形監測區域內隨機布置100個節點，參數如表1所示。

表1 仿真實驗參數

3.2 仿真結果及分析

如圖2所示，兩種協議第一個節點死亡時間(FND，First Node Die)和最后一個節點死亡時間(LND，Last Node Die)進行對比，新協議分別延長了26.5%和21.5%。同一時刻網絡中存活節點數進行對比，新協議要優于LEACH協議，具體見圖3。

圖2 網絡生存時間對比

圖3 同一時刻存活節點數對比

如圖4、5所示，在新協議下基站接收的數據量要大于LEACH，而每輪消耗的能量要比LEACH協議要低。

圖4 基站接收數據量對比

圖5 能量消耗對比

4 總結

相對于LEACH，本文所提出的改進協議，采用分區簇頭選舉，有利于整個網絡簇頭的均勻分布；穩定階段采用簇間多跳的方式，減少了傳輸的能量消耗。仿真結果證明了本文的策略具有良好的效果。與眾多的改進協議相比，本文的改進協議比較簡單且容易實現，并且本文在改進LEACH時并沒有附加額外的條件。因此，本文的方案更加適合硬件資源有限的無線傳感器網絡，且適用范圍更廣。

[1]CHEN XIAOBO,NIU ZHISHENG.A randomly delayed clustering method for wireless sensor networks[C]//Proc.of IEEE International Conference on Communications.IEEE Press,2006∶578-580.

[2]YE FEI,HUA YAO,NIU ZHISHENG.Sub cluster aided data collection in multi-hop wireless sensor networks[EB/OL].(2007-03-11)[2011-03-10]http∶//network.ee.tsinghua.edu.cn/research/detail.php?paperid=108.

[3]AKKAYA K,YOUNIS M.A survey on routing protocols for wireless sensor networks[J].Elsevier Ad Hoc Networks Journal,2005,3(3)∶325-349.

[4]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(1)∶27-36.

[5]崔莉,鞠海玲,苗勇,等.無線傳感器網絡研究進展[J].計算機研究與發展,2005,42(1)∶163-174.

[6]HEINZELMAN WR,CHANDRAKASAN A,BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor network[J].IEEE Transactions on Wireless Communications,2002,1(4)∶660-670.

[7]HEINZELMAN WR,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proc.of HICSS’00 Los.Alamitos,CA,USA∶IEEE Press,2000.

[8]徐雷鳴,龐博,趙耀.NS與網絡模擬[M].北京∶人民郵電出版社,2003∶1-5.