基于分區(qū)簇頭選擇簇間多跳的路由協(xié)議

劉愛東，盧中武，許 芹

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

0 引言

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

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

1 LEACH 路由協(xié)議

1.1 LEACH協(xié)議成簇算法

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

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

簇內(nèi)節(jié)點收到TDMA后就進入休眠，直到自己的時間槽才醒來發(fā)送數(shù)據(jù)給自己的簇頭。當簇頭收

1.2 協(xié)議在能耗方面存在的不足

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

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

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

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

2 改進的路由協(xié)議

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

2.1 基于分區(qū)的簇頭選擇

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

圖1 監(jiān)測區(qū)域分成環(huán)形區(qū)域

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

式中：SZONEi為區(qū)域i的面積；Sopt為最優(yōu)面積。由文獻[6]可知，LEACH 中簇的最優(yōu)數(shù)如下式所示。

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

各區(qū)域根據(jù)期望的簇頭數(shù)進行簇頭選舉，選舉的閾值為：

式中：k'為某環(huán)形區(qū)域期望的簇頭數(shù)；N'為該環(huán)形區(qū)域節(jié)點數(shù)；r為輪數(shù)；rs為節(jié)點連續(xù)未成為簇頭的輪數(shù)；Eres為節(jié)點剩余能量；Einit為節(jié)點初始能量。

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

2.2 簇間多跳的數(shù)據(jù)傳輸

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

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

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

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

3 仿真與驗證

3.1 仿真環(huán)境設置

本文選用UC Berkley 分校研發(fā)的網(wǎng)絡仿真工具NS2[8]作為仿真平臺，通過仿真比較改進后的協(xié)議和LEACH協(xié)議。設定在邊長為100 m的方形監(jiān)測區(qū)域內(nèi)隨機布置100個節(jié)點，參數(shù)如表1所示。

表1 仿真實驗參數(shù)

3.2 仿真結果及分析

如圖2所示，兩種協(xié)議第一個節(jié)點死亡時間(FND，F(xiàn)irst Node Die)和最后一個節(jié)點死亡時間(LND，Last Node Die)進行對比，新協(xié)議分別延長了26.5%和21.5%。同一時刻網(wǎng)絡中存活節(jié)點數(shù)進行對比，新協(xié)議要優(yōu)于LEACH協(xié)議，具體見圖3。

圖2 網(wǎng)絡生存時間對比

圖3 同一時刻存活節(jié)點數(shù)對比

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

圖4 基站接收數(shù)據(jù)量對比

圖5 能量消耗對比

4 總結

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

[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]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機學報,2007,30(1)∶27-36.

[5]崔莉,鞠海玲,苗勇,等.無線傳感器網(wǎng)絡研究進展[J].計算機研究與發(fā)展,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與網(wǎng)絡模擬[M].北京∶人民郵電出版社,2003∶1-5.