黃 靜

（泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院慈山分院，福建 泉州 360003）

無(wú)線傳感器網(wǎng)絡(luò)LEACH算法淺析

黃 靜

（泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院慈山分院，福建 泉州 360003）

LEACH算法就是針對(duì)于無(wú)線傳感器網(wǎng)絡(luò)而提出的一種經(jīng)典的層次型拓?fù)浣M織算法。對(duì)LEACH算法進(jìn)行詳細(xì)的描述，闡述了該算法的不足，然后重點(diǎn)就現(xiàn)有的LEACH改進(jìn)算法進(jìn)行分析和比較，總結(jié)各自的優(yōu)缺點(diǎn)，最后給出該算法研究發(fā)展方向。

無(wú)線傳感器網(wǎng)絡(luò)；LEACH；LEACH-C；HEED；PEGASIS

引言

無(wú)線傳感器網(wǎng)絡(luò)是一種全新的信息獲取技術(shù)，是新興的下一代無(wú)線網(wǎng)絡(luò)，具有廣泛的應(yīng)用前景。傳感器節(jié)點(diǎn)主要由電池供電，且大都分布在無(wú)人看管、幾乎不可能更換電池的環(huán)境中，如何能提高能量的有效利用率并延長(zhǎng)網(wǎng)路壽命是一個(gè)重要的問(wèn)題。對(duì)網(wǎng)絡(luò)通信及拓?fù)淇刂品矫娴难芯楷F(xiàn)在正成為無(wú)線傳感器網(wǎng)絡(luò)研究中的熱點(diǎn)。LEACH（低功耗自適應(yīng)分簇）算法就是針對(duì)無(wú)線傳感器網(wǎng)絡(luò)而提出的一種層次型拓?fù)浣M織算法。本文首先對(duì)經(jīng)典的LEACH算法進(jìn)行深入研究，并結(jié)合前人工作已提出的一些較為重要的改進(jìn)算法進(jìn)行對(duì)比和剖析。最后探討了今后研究的方向，指出了下一步研究中的重點(diǎn)。

1 .LEACH算法

LEACH（Low-Energy Adaptive Clustering Hierarchy）是一種自適應(yīng)分簇拓?fù)渌惴?，它的?zhí)行過(guò)程是周期性的，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。在簇的建立階段，相鄰節(jié)點(diǎn)隨機(jī)產(chǎn)生簇頭，動(dòng)態(tài)地形成簇；在數(shù)據(jù)通信階段，簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)發(fā)送給簇頭，簇頭進(jìn)行數(shù)據(jù)融合并把結(jié)果發(fā)送給匯聚節(jié)點(diǎn)。LEACH算法中簇頭的選擇是依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點(diǎn)總數(shù)和迄今為止每個(gè)節(jié)點(diǎn)已成為簇頭的次數(shù)來(lái)決定的。具體的選擇辦法是：每個(gè)傳感器節(jié)點(diǎn)選擇0-1之間的一個(gè)值，如果選定的值小于某個(gè)閾值，那么這個(gè)節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)。節(jié)點(diǎn)當(dāng)選簇頭以后，廣播告知其他節(jié)點(diǎn)自己是新簇頭。非簇頭節(jié)點(diǎn)根據(jù)自己與簇頭之間的距離來(lái)選擇加入哪個(gè)簇，并告知該簇頭。當(dāng)簇頭接收到所有的加入信息后，就產(chǎn)生一個(gè)TDMA定時(shí)消息，并且通知該簇中所有節(jié)點(diǎn)。為了避免附近簇的信號(hào)干擾，簇頭可以決定本簇中所有節(jié)點(diǎn)所用的CDMA編碼。這個(gè)用于當(dāng)前階段的CDMA編碼連同TDMA定時(shí)一起發(fā)送。當(dāng)簇內(nèi)節(jié)點(diǎn)收到這個(gè)消息后，它們就會(huì)在各自的時(shí)間槽內(nèi)發(fā)送數(shù)據(jù)。經(jīng)過(guò)一段時(shí)間的數(shù)據(jù)傳輸，簇頭節(jié)點(diǎn)將運(yùn)行數(shù)據(jù)融合算法來(lái)處理收到的數(shù)據(jù)，并將結(jié)果直接發(fā)送給匯聚節(jié)點(diǎn)。

2 .存在不足

LEACH算法還沒(méi)有考慮節(jié)點(diǎn)的能量狀態(tài)，如果某一節(jié)點(diǎn)的剩余能量很小，仍有同樣幾率被當(dāng)選為簇頭；在LEACH算法中，簇頭的產(chǎn)生具有隨機(jī)性，簇頭分布不均勻，有可能會(huì)出現(xiàn)部分地區(qū)簇頭密度大，部分地區(qū)簇頭稀少的現(xiàn)象；LEACH 算法選舉簇頭的機(jī)制也具有隨機(jī)性，沒(méi)有控制每輪簇頭的數(shù)量；LEACH算法還是經(jīng)典的一跳算法，即簇內(nèi)成員向簇頭發(fā)送信息是一跳將數(shù)據(jù)發(fā)送給簇頭。它要求節(jié)點(diǎn)具備較大的通信能力，以滿足節(jié)點(diǎn)間能進(jìn)行直接通信。這也使得部分網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗過(guò)快，不利于網(wǎng)絡(luò)能量的充分利用。

3 .現(xiàn)有改進(jìn)

HEED算法主要是針對(duì)LEACH算法生成簇的簇首分布不均勻這個(gè)問(wèn)題進(jìn)行了改進(jìn)。該算法構(gòu)建了一種節(jié)能、分布式的成簇策略，但在選擇簇頭時(shí)需要在一定的迭代次數(shù)內(nèi)與周圍鄰居節(jié)點(diǎn)不斷地緊系信息交互，因此該算法的實(shí)現(xiàn)也需要額外的通信代價(jià)。同時(shí)，針對(duì)節(jié)點(diǎn)一跳發(fā)送數(shù)據(jù)造成的能量過(guò)快消耗問(wèn)題，在LEACH算法的基礎(chǔ)上，Lindsey等人提出了PEGASIS算法，其思想是進(jìn)一步減少直接與基站通信的節(jié)點(diǎn)。PEGASIS將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)連成一條鏈，數(shù)據(jù)在鏈上進(jìn)行融合處理，最后傳輸至基站。但是，該算法需要知道每個(gè)節(jié)點(diǎn)的位置信息，開(kāi)銷非常大。文提出通過(guò)構(gòu)造生成樹(shù)，使得簇內(nèi)生成樹(shù)中的節(jié)點(diǎn)基本都是選擇距離自身最近的簇成員節(jié)點(diǎn)為自己的父節(jié)點(diǎn)，簇首生成樹(shù)中的簇首節(jié)點(diǎn)基本都是選擇距離自身最近的簇首為父節(jié)點(diǎn)。所以，在數(shù)據(jù)收集中，各個(gè)節(jié)點(diǎn)都基本上與距離自身最近的節(jié)點(diǎn)通信，而且沒(méi)有增加LEACH的時(shí)延（不像PEGASIS）。但是它也有其局限性。由于傳感器節(jié)點(diǎn)的處理能力有限，對(duì)于需要大量原始數(shù)據(jù)上傳、聚合過(guò)程復(fù)雜或聚合后數(shù)據(jù)尺寸急劇膨脹的應(yīng)用場(chǎng)景，文中算法就不太適用。因此，該算法只適用于中小型無(wú)線傳感器網(wǎng)絡(luò)。

4 .小結(jié)

目前，對(duì)于LEACH算法的改進(jìn)大都只是從個(gè)別的幾個(gè)因素來(lái)考慮，很少關(guān)注全局的網(wǎng)絡(luò)特征。還不存在一個(gè)能適用于所有網(wǎng)絡(luò)場(chǎng)景的十全十美的算法，每種算法都存在某些方面的劣勢(shì)。而且改進(jìn)的策略有相當(dāng)部分在仿真實(shí)驗(yàn)中可以取得較好的效果，在實(shí)際網(wǎng)絡(luò)中往往會(huì)有些偏差，還是有待進(jìn)一步的驗(yàn)證。

[1] 熊昊翔，李峰，李平. 基于節(jié)能的無(wú)線傳感器網(wǎng)絡(luò) LEACH協(xié)議改進(jìn)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2007，（11）.

[2] 陳建明，王青海，路建軍. 自適應(yīng)分簇拓?fù)渌惴‥C-LEACH的研究[J]. 測(cè)試技術(shù)學(xué)報(bào)，2008，（6）.

TP212

A

1008-7427（2010）01-0160-01

2009-11-18