LEA CH路由協(xié)議的改進(jìn)

吳麗君黃河清

(華東理工大學(xué)信息與工程學(xué)院，上海200237)

1.引言

無線傳感器網(wǎng)絡(luò)(WSN，Wireless Sensor Network)是微機(jī)電系統(tǒng)(MEMS)、片上系統(tǒng)(SOC)、計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)、嵌入式系統(tǒng)、通信技術(shù)、微機(jī)電技術(shù)、分布式信息處理技術(shù)和傳感器技術(shù)等多種領(lǐng)域技術(shù)于一體的新型獲取和處理信息的傳感網(wǎng)絡(luò)，并隨著這些技術(shù)的飛速發(fā)展和日益成熟，出現(xiàn)了更小、更廉價(jià)、更低能量、更靈活的嵌入式系統(tǒng)的并具有感知能力、計(jì)算能力、無線通信能力和控制功能的無線傳感器網(wǎng)絡(luò)[1]。

無線傳感器網(wǎng)絡(luò)在軍用和民用方面具有極高的使用價(jià)值，可以在大范圍內(nèi)用于收集、處理、監(jiān)測和發(fā)布極其復(fù)雜的環(huán)境數(shù)據(jù)，但在現(xiàn)實(shí)使用過程中存在著一些不可避免的約束。無線傳感器網(wǎng)絡(luò)在實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)需要量大，要求單價(jià)便宜，所以一般體積微小，通常攜帶的能量十分有限的電池。而且無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)往往被部署在偏遠(yuǎn)地區(qū)或環(huán)境惡劣的危險(xiǎn)區(qū)域。因此，如何在不影響功能的前提下，盡可能地延長網(wǎng)絡(luò)的生命時(shí)間成為無線傳感器網(wǎng)絡(luò)軟硬件設(shè)計(jì)的核心問題，也是當(dāng)前國內(nèi)外研究機(jī)構(gòu)關(guān)注的焦點(diǎn)問題[2]。

目前，基于節(jié)能的策略的考慮已經(jīng)出現(xiàn)各種各樣的協(xié)議。按照網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，可以分為平面路由協(xié)議和分層路由協(xié)議。在分層路由協(xié)議中，群首選擇的合理性很大程度上決定網(wǎng)絡(luò)的功耗，網(wǎng)絡(luò)的生命周期的長短。目前分層路由協(xié)議中的群首選擇算法主要集中式和分布式兩種基本算法。集中式群首選擇算法要求基站獲得傳感器網(wǎng)絡(luò)全局信息，然后由基站選取群首，再廣播當(dāng)選群首的節(jié)點(diǎn)ID。分布式群首選擇算法則是由每個(gè)節(jié)點(diǎn)獨(dú)立運(yùn)行群首選擇算法，然后自行決定自己是否當(dāng)選為群首。無線傳感器網(wǎng)絡(luò)中基于分層的典型層次型路由算法有：LEACH[3]、HEED[4]、TEEN[5]等。TEEN和LEACH的實(shí)現(xiàn)機(jī)理非常相似，只是前者是響應(yīng)型的，而后者是主動(dòng)型。主動(dòng)型傳感器網(wǎng)絡(luò)會(huì)持續(xù)不間斷地監(jiān)測周圍的物質(zhì)現(xiàn)象，并以恒定速率發(fā)送監(jiān)測數(shù)據(jù)；而響應(yīng)型傳感器網(wǎng)絡(luò)只是在被觀測變量發(fā)生突變時(shí)才進(jìn)行數(shù)據(jù)傳送。

LEACH協(xié)議是第一個(gè)針對(duì)無線傳感器網(wǎng)絡(luò)特點(diǎn)提出的分布式層次路由協(xié)議，其后一些分層協(xié)議大多是在其基礎(chǔ)一種延伸，所以本文選擇經(jīng)典的研究對(duì)象LEACH協(xié)議，提出一種融合的節(jié)點(diǎn)密度控制群首選擇算法，該算法是對(duì)LEACH算法的改進(jìn)，在選取群首的時(shí)候，除了考慮節(jié)點(diǎn)輪流成為群首的問題，考慮節(jié)點(diǎn)的剩余能量，同時(shí)考慮節(jié)點(diǎn)的密度，使得分布密度越大、剩余能量越高的節(jié)點(diǎn)較其它節(jié)點(diǎn)成為群首的可能性更高。NS2仿真實(shí)驗(yàn)表明，新算法能比LEACH算法更有效地降低網(wǎng)絡(luò)的能量消耗，均衡網(wǎng)絡(luò)能耗水平，從而可進(jìn)一步提高傳感器網(wǎng)絡(luò)的生命周期。

2.LEACH協(xié)議

2.1 協(xié)議的基本原理

在LEACH中，各個(gè)節(jié)點(diǎn)自組織成為群，每個(gè)群內(nèi)有一個(gè)群首。所有非群首節(jié)點(diǎn)將自己的數(shù)據(jù)發(fā)送給群首；群首節(jié)點(diǎn)接受所有分群節(jié)點(diǎn)發(fā)送來的數(shù)據(jù)，然后對(duì)數(shù)據(jù)進(jìn)行處理，最后將數(shù)據(jù)發(fā)送給遠(yuǎn)端的基站，由分析可知群首消耗的能量多于非群首節(jié)點(diǎn)。假如群首節(jié)點(diǎn)固定然后一直不變，那么群首節(jié)點(diǎn)將很快消耗掉自己的能量。群首節(jié)點(diǎn)一旦把自己的能量消耗掉，就停止工作，那么其群內(nèi)所有節(jié)點(diǎn)也會(huì)和整個(gè)網(wǎng)絡(luò)失去通信。因此LEACH采用群首位置隨機(jī)輪換機(jī)制，讓各個(gè)節(jié)點(diǎn)輪流的成為群首，這樣避免網(wǎng)絡(luò)中因群首能量消耗過快而死亡。

在初始化階段，群首是通過下面的機(jī)制產(chǎn)生的。傳感器節(jié)點(diǎn)生成0，1之間的隨機(jī)數(shù)，如果大于閾值T，則選該節(jié)點(diǎn)為群首。T的計(jì)算方法如下：

N為網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)，k為群首的數(shù)量，Gi(t)為i節(jié)點(diǎn)時(shí)刻在近幾個(gè)輪中(r⊕(N/k))作為群首的標(biāo)志函數(shù)，由分析可知只有滿足節(jié)點(diǎn)最近不是群首，其能量多于最近剛剛擔(dān)任過群首的節(jié)點(diǎn)。由于經(jīng)過N/k個(gè)循環(huán)后，所有節(jié)點(diǎn)都有一次機(jī)會(huì)成為群首，在隨后的循環(huán)中全部符合群首的條件。

2.2 LEACH優(yōu)缺點(diǎn)分析

由LEACH協(xié)議的運(yùn)行過程可以知道，群首自適應(yīng)地隨機(jī)選取，每個(gè)節(jié)點(diǎn)機(jī)會(huì)相等，在不同的輪中，由不同的節(jié)點(diǎn)去充當(dāng)群首，把網(wǎng)絡(luò)的負(fù)載基本均勻地分布在整個(gè)網(wǎng)絡(luò)中，把遠(yuǎn)距離通信的負(fù)荷基本均衡分配給網(wǎng)絡(luò)中的節(jié)點(diǎn)，有利于均衡節(jié)點(diǎn)的能量消耗，且不需要上層控制或一些全網(wǎng)信息，實(shí)現(xiàn)起來也比較容易。但是群首選擇是隨機(jī)的，節(jié)點(diǎn)擔(dān)任群首是嚴(yán)格等概率的，群首的選擇不考慮節(jié)點(diǎn)的剩余能量，由于群首要收集并融合群內(nèi)信息并直接與基站通信，所以一旦出現(xiàn)能量較低的節(jié)點(diǎn)為群首，其能量很快耗盡，這樣不利于均衡網(wǎng)絡(luò)能量，縮短了網(wǎng)絡(luò)的生命周期。網(wǎng)絡(luò)中的節(jié)點(diǎn)自組織形成群，節(jié)點(diǎn)選擇與之通信能耗最小的群首而加入這個(gè)群，而不考慮群的負(fù)載程度，這樣很可能出現(xiàn)一些不均衡的分群方案，將會(huì)導(dǎo)致各個(gè)群中的節(jié)點(diǎn)數(shù)量嚴(yán)重不均衡，由分析可知群首選擇算法存在不利延長網(wǎng)絡(luò)生命周期的因素，在下章本文提出改進(jìn)的群首選擇算法。

3.加權(quán)群首選擇算法

3.1 網(wǎng)絡(luò)模型假設(shè)

(1)①節(jié)點(diǎn)在需要之時(shí)具有足夠的功率將數(shù)據(jù)發(fā)送給基站；②節(jié)點(diǎn)可以根據(jù)需要改變發(fā)射功率的大小；③節(jié)點(diǎn)總有數(shù)據(jù)發(fā)送給用戶且相互接近的節(jié)點(diǎn)具有相關(guān)數(shù)據(jù)；④節(jié)點(diǎn)一旦布置好就不能移動(dòng)；⑤基站為位置遠(yuǎn)離傳感器收集數(shù)據(jù)區(qū)域，假設(shè)其能量充足，不考慮其能量的消耗；⑥每個(gè)節(jié)點(diǎn)可以感知其剩余能量，鄰居節(jié)點(diǎn)信息；⑦所有節(jié)點(diǎn)的初始能量相同而其有限；⑧無線電信號(hào)在各個(gè)方向上能量消耗相同；由于無線硬件技術(shù)和低功耗的計(jì)算技術(shù)的發(fā)展和進(jìn)步，這些假設(shè)是合理的。

(2)傳輸模型：節(jié)點(diǎn)將l bit的數(shù)據(jù)傳輸距離d耗能為：

接受一條消息的耗能為：

數(shù)據(jù)融合消耗能量：

其中，ETx(l，d)表示發(fā)送端的能量消耗；ERx(l)表示接收端的能量消耗；Eelec表示發(fā)射電路消耗的能量；εfs和εmp放大器的系數(shù)；d0臨界距離。

3.2 節(jié)點(diǎn)密度調(diào)節(jié)函數(shù)

由前文分析可知為了使是每個(gè)群的負(fù)載基本平衡，延長網(wǎng)絡(luò)的生命周期，在選擇群首時(shí)，要盡可能使得密集分布區(qū)域中的節(jié)點(diǎn)應(yīng)比稀疏分布區(qū)域中的節(jié)點(diǎn)具有更大當(dāng)選為群首的概率，使得密集分布區(qū)域比稀疏分布區(qū)域具有更多群首，使得每個(gè)群中成員節(jié)點(diǎn)數(shù)目大致相同。因此，本節(jié)將在LEACH算法的式(3)中引入一個(gè)密度調(diào)節(jié)函數(shù)H(i)，通過密度調(diào)節(jié)函數(shù)H(i)可以使得分布密度越大的節(jié)點(diǎn)有更多機(jī)會(huì)成為群首。其中：密度調(diào)節(jié)函數(shù)的定義采取文獻(xiàn)[6]的定義方式：

其中Nodedensity(i)表示節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)。顯然可知Nodedensity(i)越大，H(i)就越接近1，這樣節(jié)點(diǎn)i成為群首的概率就越大。

節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)為文獻(xiàn)[7]定義方式：

R為節(jié)點(diǎn)i的通訊半徑。節(jié)點(diǎn)可通過改變發(fā)射功率來控制其通信半徑，進(jìn)而改變其鄰居節(jié)點(diǎn)個(gè)數(shù)。N為網(wǎng)絡(luò)中現(xiàn)有節(jié)點(diǎn)數(shù)量。

3.3 剩余能量調(diào)節(jié)函數(shù)

由于在LEACH中，閾值Ti(t)的選取未考慮群首的概率與它的剩余能量之間的關(guān)系，這使得選出的群首可能剩余能量很小，這樣很快死亡，從而它所管理的整個(gè)群在很長一段時(shí)間內(nèi)都處于失效狀態(tài)。盡管節(jié)點(diǎn)輪流當(dāng)選為群首，但它并不沒有很好把網(wǎng)絡(luò)的全部能量平均到每個(gè)節(jié)點(diǎn)上，因此引入剩余能量調(diào)節(jié)函數(shù)如下：

Ei_curent為節(jié)點(diǎn)i的當(dāng)前能量，Eaveraget為節(jié)點(diǎn)當(dāng)前具備的平均能量，由公式可知節(jié)點(diǎn)的剩余能量越大，Z(i)越大，成為群首的概率越大。Eaveraget=Ecurrent_totalt/Network_adlive，Network_adlive表示實(shí)時(shí)的網(wǎng)絡(luò)存活節(jié)點(diǎn)總數(shù)，Ecurrent_totalt為網(wǎng)絡(luò)當(dāng)前的全部能量。

3.4 加權(quán)群首選擇算法

本文是在選擇群首算法上不僅考慮節(jié)點(diǎn)剩余能量，也要考慮節(jié)點(diǎn)分布密度，希望節(jié)點(diǎn)的剩余能量多，節(jié)點(diǎn)分布越密集的節(jié)點(diǎn)有更大的概率成為群首，但在兩個(gè)因素的權(quán)衡中，往往會(huì)出現(xiàn)矛盾的一面，所以引入權(quán)重因子w且，得Ti(t)改進(jìn)為：

w的具體取值，根據(jù)多次實(shí)驗(yàn)結(jié)果決定取得最佳效果的值。

3.5 仿真實(shí)驗(yàn)和結(jié)果分析

在仿真實(shí)驗(yàn)中，采用100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，節(jié)點(diǎn)隨機(jī)分布在(x=0，y=0)和(x=100，y=100)之間，基站位于(x=50，y=175)。信道帶寬設(shè)為1Mb/s，每條消息的長度為500B，各種分組分組頭均長為25B。計(jì)算R=37.5，Eelec=50nJ/bit，εmp=0.0013pJ/bit/m2，εfs=10pJ/bit/m4，Einital=2J，Efuse=5nJ/bit/signal，d0=87.5，選擇w(1，0，0.5，0.2，0.8)進(jìn)行比較實(shí)驗(yàn)，仿真時(shí)間為700s。

由節(jié)點(diǎn)存活仿真結(jié)果圖1可以知道沒有改進(jìn)的LEACH的生命時(shí)間為460s左右。改進(jìn)后LEACH生命時(shí)間對(duì)應(yīng)w(1；0；0.5；0.2；0.8)為600s，570s，490s，530s，620s。網(wǎng)絡(luò)的生命時(shí)間有所延長。其中當(dāng)w=0時(shí)，就是只用H(i)密度調(diào)整函數(shù)有效時(shí)，生命時(shí)間延長了18.75%。w=1延長了30.43%。有公式(7)可以知道，在選擇群首時(shí)，節(jié)點(diǎn)的剩余能量要比節(jié)點(diǎn)分布情況占更大的比重，果然當(dāng)w=0.8時(shí)權(quán)衡了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的分布能量，這時(shí)網(wǎng)絡(luò)的生命時(shí)間延長了37%左右。說明本改進(jìn)方案不僅理論是可行的，仿真也證明了是有效的，可以延長網(wǎng)絡(luò)的生命時(shí)間。由仿真結(jié)果圖2基站節(jié)點(diǎn)接收數(shù)據(jù)包數(shù)可知改進(jìn)后的協(xié)議不影響數(shù)據(jù)的傳輸量，反而提供數(shù)據(jù)的吞吐量。節(jié)點(diǎn)消耗總能量結(jié)果圖3可知改進(jìn)后的協(xié)議單位時(shí)間消化的能量少于改進(jìn)前。說明了改進(jìn)后的LEACH協(xié)議性能得到了改善。

[1]Zhang Xihuang，Xu Wenbo.A New FlowBased Fast Handover Method for Mobile IPv6network with route optirIlization[J].Computer Comunication.2007，(12)

[2]汪益民，吳建國.淺析無線傳感器網(wǎng)絡(luò)節(jié)能策略[J].電腦知識(shí)與術(shù).2008，4(4)：867-868.

[3]Heinzelman W，Chandrakasan A，Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].Wireless Communications.2002，4(1)：660-670

[4]Younis O，F(xiàn)ahmy S.Distributed clustering in adhoc sensor networks a hybrid，energy-efficient approach[C].The 23th Joint Conf on IEEE Computer and Communications Societies[J].2002，629-640

[5]Manjeshwar A.Agrawal D T.A routing protocol for enhanced efficiency in wireless sensor networks[C].The 15th International Parallel and Distributed Processing Symposium.2001，2009-2015

[6]賀智勇，龍陳鋒，尹乾.傳感器網(wǎng)絡(luò)中基于節(jié)點(diǎn)密度的分布式成簇算法[J].計(jì)算機(jī)應(yīng)用與件，2008，25(12)：20-21.

[7]喬俊峰，劉三陽，曹祥宇.無線傳感器網(wǎng)絡(luò)中基于節(jié)點(diǎn)密度的簇算法[J].計(jì)算機(jī)科學(xué)，2009，36(12)：46-49.