基于LEACH協(xié)議的簇頭優(yōu)化協(xié)議研究

張長(zhǎng)宏，昝風(fēng)彪，唐明虎

（青海民族大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧 810007）

無(wú)線傳感器網(wǎng)絡(luò) WSN （Wireless Sensor Network）是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過無(wú)線通信方式形成一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。目的是協(xié)作感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息，并發(fā)送給觀察者。傳感器網(wǎng)絡(luò)在軍事和民用領(lǐng)域都有著非常廣闊的應(yīng)用前景[1]。但是這些傳感器節(jié)點(diǎn)體積小，能量有限，不能更換電池，因此，將最大限度延長(zhǎng)網(wǎng)絡(luò)的生命周期作為一個(gè)路由協(xié)議的評(píng)價(jià)標(biāo)準(zhǔn)。從網(wǎng)絡(luò)的拓?fù)浣嵌确譃槠矫媛酚蓞f(xié)議和分層路由協(xié)議。對(duì)于大規(guī)模網(wǎng)絡(luò)而言，分簇的層次路由協(xié)議相比于平面路由協(xié)議，其采用簇頭節(jié)點(diǎn)的融合功能有效地減少了數(shù)據(jù)通信量，從而顯著延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命時(shí)間。LEACH（Low Energy Adaptive Clustering Hierarchy）[2]協(xié)議是一種典型的分簇層次路由協(xié)議。LEACH中簇頭節(jié)點(diǎn)的選擇是隨機(jī)產(chǎn)生的，沒有考慮到節(jié)點(diǎn)的剩余能量，另外從簇頭到基站采用的是單跳的方式，當(dāng)距離遠(yuǎn)時(shí)，能量消耗太快。本文基于以上兩點(diǎn)對(duì)簇頭進(jìn)行了優(yōu)化。

1 LEACH協(xié)議概述

1.1 LEACH算法

LEACH是Heinzelman等為WSN設(shè)計(jì)的，仿真表明，它與一般的平面多跳路由協(xié)議和靜態(tài)分簇路由協(xié)議相比，無(wú)論是第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)和最后一個(gè)節(jié)點(diǎn)死亡的輪數(shù)都提高了3倍[3]。LEACH的每輪分為簇的建立階段和數(shù)據(jù)傳輸階段兩個(gè)部分。為節(jié)省能量，一般數(shù)據(jù)傳輸持續(xù)時(shí)間要大于建立時(shí)間。

1.1.1 簇的建立階段

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

其中，G表示節(jié)點(diǎn)在前r mod（1/p）輪沒有當(dāng)選簇頭節(jié)點(diǎn)的集合；p表示最優(yōu)簇頭數(shù)占所有節(jié)點(diǎn)數(shù)的比例，p=k/N，N表示節(jié)點(diǎn)總數(shù)，k為分簇?cái)?shù)。在第1輪中每個(gè)節(jié)點(diǎn)成為簇頭的概率為p，選出的簇節(jié)點(diǎn)個(gè)數(shù)都為N×p。在接下來的 N/k－1輪中不會(huì)當(dāng)選簇頭，利用式（1）計(jì)算可知，在沒有節(jié)點(diǎn)死亡時(shí)每輪選出的簇頭都為N×p，但實(shí)際中有一定的波動(dòng)。選為簇頭的節(jié)點(diǎn)向網(wǎng)絡(luò)廣播信息，通知產(chǎn)生了一個(gè)新簇頭，接收到信息的節(jié)點(diǎn)根據(jù)信號(hào)的強(qiáng)度選擇一個(gè)距離其最近的簇頭，并告知簇頭節(jié)點(diǎn)，最后，簇頭采用TDMA方法為簇中每個(gè)節(jié)點(diǎn)分配向其傳送數(shù)據(jù)的時(shí)間片。

1.1.2 數(shù)據(jù)傳輸階段

傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)按照簇頭分配的時(shí)隙傳送到簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合將結(jié)果直接發(fā)送到基站。

1.2 網(wǎng)絡(luò)模型和最優(yōu)簇頭數(shù)的計(jì)算

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

傳感器節(jié)點(diǎn)發(fā)送l bit數(shù)據(jù)消耗的能量為：

傳感器節(jié)點(diǎn)接收l(shuí) bit數(shù)據(jù)消耗的能量為：

假設(shè)基站遠(yuǎn)離隨機(jī)分布的節(jié)點(diǎn)（d＞d0），每一輪中，簇頭節(jié)點(diǎn)消耗的能量模型為：

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

隨機(jī)分布的節(jié)點(diǎn)（d≤d0），每一輪中，非簇頭節(jié)點(diǎn)消耗的能量模型為：

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

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

每輪中，一個(gè)簇所消耗的能量為：

整個(gè)網(wǎng)絡(luò)的能量消耗為：

對(duì)式（8）取 k值變化的最優(yōu)簇頭數(shù)目：dEtotal/dk=0，求得最優(yōu)簇頭數(shù)為：

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

2 優(yōu)化的協(xié)議

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

2.1 簇的建立

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

其中，r為當(dāng)前運(yùn)行的輪次，N0為無(wú)線傳感器網(wǎng)絡(luò)的預(yù)計(jì)運(yùn)行輪次，E0為節(jié)點(diǎn)的初始能量，Ei為節(jié)點(diǎn) i的剩余能量。使每個(gè)節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)與 Ki′（t）相比較，剩余的能量越大，比值EE越大，當(dāng)選簇頭的可能就越大；反之，剩余的能量越小，比值EE越小，當(dāng)選簇頭的可能就越小，從而避免了低能量節(jié)點(diǎn)能量耗盡。當(dāng)選簇頭的節(jié)點(diǎn)向網(wǎng)絡(luò)廣播信息，通知產(chǎn)生了一個(gè)新簇頭，接收到信息的節(jié)點(diǎn)根據(jù)信號(hào)的強(qiáng)度選擇一個(gè)簇頭，并告知簇頭節(jié)點(diǎn)。

此外，各簇頭節(jié)點(diǎn)向基站發(fā)送廣播信息，基站根據(jù)信號(hào)的強(qiáng)度選與其距離最近的節(jié)點(diǎn)為超級(jí)節(jié)點(diǎn)，并給選定的超級(jí)節(jié)點(diǎn)發(fā)信息，超級(jí)節(jié)點(diǎn)根據(jù)各簇頭節(jié)點(diǎn)廣播的信息，選擇最近的簇頭節(jié)點(diǎn)為下一跳，并發(fā)送廣播通知下一節(jié)點(diǎn)，下一節(jié)點(diǎn)重復(fù)同樣的操作，直到所有的簇頭加入鏈。

2.2 穩(wěn)定傳輸階段

傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)按照簇頭分配的時(shí)隙傳送到簇頭節(jié)點(diǎn)，鏈中最后一個(gè)簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合，將結(jié)果傳送到鏈中的下一簇頭節(jié)點(diǎn)，下一級(jí)簇頭節(jié)點(diǎn)接收到所有簇內(nèi)節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的信息后進(jìn)行數(shù)據(jù)融合，再傳到鏈中的下一個(gè)簇頭節(jié)點(diǎn)。進(jìn)行反復(fù)操作，直到超級(jí)節(jié)點(diǎn)融合數(shù)據(jù)后直接發(fā)送到基站。

3 仿真結(jié)果分析

實(shí)驗(yàn)采用MATLAB進(jìn)行仿真，模擬實(shí)現(xiàn)了LEACH和本文提出的優(yōu)化的新協(xié)議的性能比較。仿真主要參數(shù)如下：100個(gè)節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的區(qū)域中，基站位于（50，175）。式（9）選定的最佳簇?cái)?shù)為 5，則簇頭的概率p=0.05，節(jié)點(diǎn)的預(yù)計(jì)運(yùn)行輪次N0=1 500輪。其他主要參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)

圖1給出了優(yōu)化的新協(xié)議與LEACH協(xié)議網(wǎng)絡(luò)生存周期的比較，以仿真輪數(shù)代表時(shí)間。LEACH協(xié)議和新協(xié)議的第一個(gè)節(jié)點(diǎn)死亡出現(xiàn)的輪數(shù)分別為667、961，半數(shù)節(jié)點(diǎn)死亡的輪數(shù)分別為913、1 117，最后一個(gè)節(jié)點(diǎn)死亡的輪數(shù)分別為1 719、1 494。從圖1中可以看出，新協(xié)議第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)和半數(shù)節(jié)點(diǎn)死亡的輪數(shù)都比LEACH長(zhǎng)，尤其是第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間比LEACH長(zhǎng)了44%。

圖1 網(wǎng)絡(luò)生存周期比較

在無(wú)線傳感器網(wǎng)絡(luò)中，將從仿真開始到第一個(gè)節(jié)點(diǎn)死亡的時(shí)期稱為穩(wěn)定期，該值越大，網(wǎng)絡(luò)的性能越好。將第一個(gè)節(jié)點(diǎn)死亡到全部節(jié)點(diǎn)死亡稱為不穩(wěn)定期，不穩(wěn)定的長(zhǎng)短表明了網(wǎng)絡(luò)的收斂性，不穩(wěn)定期越長(zhǎng)，網(wǎng)絡(luò)性能越長(zhǎng)。從圖1中還看到，新協(xié)議比LEACH協(xié)議有更好的收斂性。

根據(jù)結(jié)果分析出主要的原因，一方面是對(duì)于簇頭的優(yōu)化，另一方面是采用多跳的傳輸技術(shù)比較節(jié)省能量，并且使能量的分布更加均衡，從而使第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)時(shí)間比較晚，同時(shí)使網(wǎng)絡(luò)有了很好的收斂性。

本文在分析LEACH協(xié)議的基礎(chǔ)上提出了一種簇頭優(yōu)化協(xié)議，仿真結(jié)果顯示，第一個(gè)節(jié)點(diǎn)死亡的時(shí)間相比LEACH協(xié)議有了很大提高，同時(shí)，網(wǎng)絡(luò)的不穩(wěn)定期縮短，有很好的收斂性，提高了網(wǎng)絡(luò)的性能。

[1]孫利民.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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路由協(xié)議[J].傳感技術(shù)學(xué)報(bào)，2009（7）：1013-1017.