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

吳麗君黃河清

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

1.引言

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

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

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

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

2.LEACH協(xié)議

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

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

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

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

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

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

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

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

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

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

接受一條消息的耗能為：

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

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

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

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

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

節(jié)點的鄰居節(jié)點個數(shù)為文獻[7]定義方式：

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

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

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

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

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

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

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

3.5 仿真實驗和結(jié)果分析

在仿真實驗中，采用100個節(jié)點的網(wǎng)絡(luò)，節(jié)點隨機分布在(x=0，y=0)和(x=100，y=100)之間，基站位于(x=50，y=175)。信道帶寬設(shè)為1Mb/s，每條消息的長度為500B，各種分組分組頭均長為25B。計算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)進行比較實驗，仿真時間為700s。

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

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