低功耗自適應(yīng)分群分層LEACH協(xié)議的研究

韓春霞，王琳杰

(1.銅仁學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,554300；2.銅仁學(xué)院計(jì)算機(jī)應(yīng)用技術(shù)研究所，貴州銅仁,554300)

目前，無線傳感器網(wǎng)絡(luò)的路由協(xié)議是國(guó)內(nèi)研究的熱點(diǎn)。一個(gè)路由協(xié)議往往對(duì)能量有效性、可擴(kuò)展性、數(shù)據(jù)傳輸可靠性、實(shí)現(xiàn)復(fù)雜度、穩(wěn)健性等很多因素進(jìn)行綜合考慮而折中得到的。根據(jù)節(jié)點(diǎn)在路由過程中是否有層次結(jié)構(gòu)、作用是否有差異，可分為平面路由協(xié)議和層次路由協(xié)議。平面路由協(xié)議簡(jiǎn)單、健壯性好，但建立、維護(hù)路由的開銷大，可以用于中小規(guī)模的網(wǎng)絡(luò)；層次路由則能夠提高協(xié)議的可擴(kuò)展性，同時(shí)還能方便地支持?jǐn)?shù)據(jù)聚合，適用于大規(guī)模網(wǎng)絡(luò)，成為當(dāng)前重點(diǎn)研究的路由技術(shù)。

無線傳感器網(wǎng)絡(luò)低能量自適應(yīng)分群分層LEACH（Low Energy Adaptive Clustering Hierarchy）是一個(gè)協(xié)議體系，進(jìn)行本地計(jì)算以減少發(fā)送數(shù)據(jù)量，采用本地控制進(jìn)行網(wǎng)絡(luò)配置和網(wǎng)絡(luò)操作。LEACH將能量高效分群路由協(xié)議和MAC協(xié)議與應(yīng)用特定數(shù)據(jù)累積綜合在一起，共同達(dá)到良好的系統(tǒng)壽命、時(shí)延、應(yīng)用感覺到的服務(wù)質(zhì)量。LEACH是能夠組織大量節(jié)點(diǎn)的分布式分群技術(shù)，實(shí)現(xiàn)均勻分布所有節(jié)點(diǎn)間能量的自適應(yīng)算法和群首位置循環(huán)算法。

LEACH協(xié)議有更優(yōu)于其他的路由協(xié)議的特性，但也存在著許多的不足之處有待研究改進(jìn)，本文就LEACH協(xié)議的改進(jìn)方案作為研究的主要目標(biāo)。

1 LEACH協(xié)議概述

低功耗自適應(yīng)分群算法(LEACH)并不是一個(gè)單純的路由協(xié)議，它提供了一個(gè)包括分群、路由、MAC和物理層的完整的無線傳感器網(wǎng)絡(luò)的協(xié)議框架。LEACH把網(wǎng)絡(luò)的工作過程分成輪，每一輪包括建立期和穩(wěn)定期。在建立期執(zhí)行分群協(xié)議，把網(wǎng)絡(luò)分成若干個(gè)群；穩(wěn)定期分成若干幀，在每一幀，成員節(jié)點(diǎn)向群首發(fā)送數(shù)據(jù)，群首合并后發(fā)送給遠(yuǎn)端的BS。

在LEACH協(xié)議中，群首是本地控制中心，協(xié)調(diào)其群內(nèi)的數(shù)據(jù)傳輸。其中，主要是分群建立階段、數(shù)據(jù)穩(wěn)定傳輸階段。在分群建立階段，傳感器節(jié)點(diǎn)隨機(jī)生成一個(gè)0-1之間的隨機(jī)數(shù)，如果選定的值小于某一域值T(n)，那么這個(gè)節(jié)點(diǎn)成為群首節(jié)點(diǎn)。在數(shù)據(jù)穩(wěn)定傳輸階段，傳感器節(jié)點(diǎn)在自己的時(shí)隙中將采集的數(shù)據(jù)傳送到群首節(jié)點(diǎn)，群首節(jié)點(diǎn)經(jīng)過數(shù)據(jù)融合再將數(shù)據(jù)傳送到BS基站。每個(gè)群采用不同的CDMA代碼進(jìn)行通信減少其他群內(nèi)節(jié)點(diǎn)的干擾，詳細(xì)的LEACH協(xié)議工作流程可參見文獻(xiàn)資料。

2 LEACH的改進(jìn)策略

2.1 LEACH協(xié)議的優(yōu)缺點(diǎn)

相比于其他路由協(xié)議，雖然LEACH協(xié)議擁有許多優(yōu)點(diǎn)。比如動(dòng)態(tài)分配群首算法、分層簇型結(jié)構(gòu)等。盡管如此，LEACH也存在著許多不足，在LEACH協(xié)議中，群首的選擇由隨機(jī)數(shù)產(chǎn)生，很少考慮當(dāng)前節(jié)點(diǎn)剩余能量及當(dāng)前節(jié)點(diǎn)與Sink節(jié)點(diǎn)的位置關(guān)系，導(dǎo)致WSN中節(jié)點(diǎn)間的能量不均衡及位置分布不均勻。在每次建立分群的過程中，每個(gè)非群首節(jié)點(diǎn)也要參與其中，這就增加了分群的復(fù)雜程度。在數(shù)據(jù)傳輸階段，由于群首節(jié)點(diǎn)與Sink節(jié)點(diǎn)直接通信，導(dǎo)致遠(yuǎn)離Sink節(jié)點(diǎn)的群首消耗更多的能量，致使該節(jié)點(diǎn)迅速死亡，出現(xiàn)監(jiān)控盲區(qū)。

2.2 LEACH的改進(jìn)策略

LEACH算法的改進(jìn)是多種多樣的，近年來，國(guó)內(nèi)外許多研究學(xué)者提出了很多改進(jìn)算法。在LEACH協(xié)議改進(jìn)中，很多人一直是把改進(jìn)群首選擇算法作為研究的重點(diǎn)，比如在早期的改進(jìn)算法中有DCHS，它的改進(jìn)是在選取群首概率公式中加入了能量比例因子，使剩余能量較高的節(jié)點(diǎn)有更多的機(jī)會(huì)當(dāng)選為群道節(jié)點(diǎn)，但這并沒有考慮這個(gè)節(jié)點(diǎn)是否曾當(dāng)選過群首節(jié)點(diǎn)。

LEACH-C和LEACH-F采用的都是中心分群算法，它們?cè)跀?shù)據(jù)穩(wěn)定傳輸階段與LEACH協(xié)議相同。在分群建立階段，是通過每個(gè)節(jié)點(diǎn)發(fā)送其當(dāng)前位置信息和能量信息給BS進(jìn)行信息交互，為此，BS根據(jù)所得的每個(gè)節(jié)點(diǎn)的信息，結(jié)合全局信息尋找最佳群首。但是這兩種算法，每次通信每個(gè)節(jié)點(diǎn)都要與BS進(jìn)行交互信息，增加了不少的能量消耗。

王萬良等人提出了一種基于LEACH的改進(jìn)算法，改進(jìn)思想是在分群的建立階段，所有候選節(jié)點(diǎn)必須是曾從未當(dāng)選過群首的節(jié)點(diǎn)，并且該侯選節(jié)點(diǎn)的能量必須大于前r輪中群首節(jié)點(diǎn)的平均能量，防止個(gè)別節(jié)點(diǎn)快速死亡。該算法的缺點(diǎn)是每個(gè)參與競(jìng)爭(zhēng)群首的節(jié)點(diǎn)必須知道前r輪群首節(jié)點(diǎn)的平均能量，需要多次與BS進(jìn)行信息交互，增加了一定的能量消耗。

顧相平等人提出了LEACH-ED算法，該分群算法結(jié)合了剩余能量和群首間距離約束。在選擇群首時(shí)，如果生成的隨機(jī)數(shù)小于加入能量因素的閥值，就計(jì)算該節(jié)點(diǎn)與群首間的距離，當(dāng)大于某一距離時(shí)，該節(jié)點(diǎn)才能成為群首。由于每次都需要計(jì)算競(jìng)選群首節(jié)點(diǎn)與現(xiàn)有群首節(jié)點(diǎn)間的距離，這不僅增加了算法的復(fù)雜度，還增加了節(jié)點(diǎn)的能量消耗。

李天池提出了LEACH-IMP算法，該算法主要針對(duì)群首選擇提出的改進(jìn)策略。LEACH-IMP將LEACH群首選擇分為了全網(wǎng)群首選擇，半網(wǎng)群首選擇，群內(nèi)群首選擇。在改進(jìn)算法中，先設(shè)置了一個(gè)能量閥值，每個(gè)分群周期開始時(shí)，計(jì)算平均群能量和群內(nèi)平均能量，判斷現(xiàn)有群中的平均群能量是否小于能量閥值，如果是，啟動(dòng)半網(wǎng)群首選擇號(hào)召，這時(shí)其他的群根據(jù)自己群的情況決定是否要響應(yīng)半網(wǎng)群首選擇號(hào)召，所有響應(yīng)半網(wǎng)群首選擇號(hào)召的群將在下一輪中按照全網(wǎng)選擇規(guī)則進(jìn)行重選。否則，每個(gè)群首再判斷自己的剩余能量是否小于群內(nèi)平均能量，如果比群內(nèi)平均能量小，則在本群內(nèi)響應(yīng)群首選擇，否則，不進(jìn)行任何群首選擇。此算法的改進(jìn)，可以避免每輪群首選擇時(shí)，都要進(jìn)行全網(wǎng)群首選擇。設(shè)置每隔一定輪數(shù)后，強(qiáng)制進(jìn)行全網(wǎng)選擇，可以平衡半網(wǎng)選擇導(dǎo)致的能量不均衡。在全網(wǎng)選擇機(jī)制和半網(wǎng)選擇機(jī)制中，改進(jìn)算法均考慮了能量因子和距離因子，使距離近的節(jié)點(diǎn)能更大的機(jī)會(huì)當(dāng)選為群首，以更好地均衡能量消耗。但在半網(wǎng)選擇中，每一輪，都要計(jì)算群內(nèi)平均能量，一定程度上，又增加了能量消耗，從改進(jìn)算法的流程看，又增加算法的復(fù)雜度。

柳麗娜提出的LEACH-L算法針對(duì)LEACH算法中群首選擇的不均以及能耗較大等問題進(jìn)行改進(jìn)。在群首選舉階段，改進(jìn)主要通過引入時(shí)間延遲Twait ，使剩余能量越大的節(jié)點(diǎn)以更大的可能性成為群首，這就使整個(gè)網(wǎng)絡(luò)系統(tǒng)的能耗更為均衡，同時(shí)從覆蓋面積的角度進(jìn)行考量，使群首的分布更加均勻。在數(shù)據(jù)傳輸階段，LEACH-L采用的是單跳和多跳相結(jié)合的方式。最開始選取群首的時(shí)候所有節(jié)點(diǎn)都向基站發(fā)送了信息，基站對(duì)每個(gè)群首的地理位置和剩余能量等信息都了如指掌，并且因?yàn)榛镜奈恢檬枪潭ú蛔兊?，所以每個(gè)群首到基站的距離都是可以知道的，于是把群首剩余能量和他們與基站的距離作為判斷的標(biāo)準(zhǔn)來確定是選擇單跳還是多跳的方式進(jìn)行數(shù)據(jù)通信。

劉長(zhǎng)江提出了一種加權(quán)的最優(yōu)閥值路由算法LEACH-M，LEACH-M算法在群首選擇時(shí)，改進(jìn)重點(diǎn)是提出新的節(jié)點(diǎn)閥值計(jì)算公式T（n），該公式考慮了能量和節(jié)點(diǎn)未當(dāng)選群首的的輪數(shù)。在群的建立時(shí)，LEACH-M引入權(quán)重因子F，該公式綜合考慮了節(jié)點(diǎn)與群首、群首與BS間距離、群首剩余能量等因素。這樣引入F，在群的建立階段，盡可能使群首分布均勻，而且減少網(wǎng)絡(luò)中能量的消耗，達(dá)到節(jié)能。

李成岳等人提出的LEACH-T算法的改進(jìn)主要針對(duì)群首的選擇過程。在群首選擇時(shí)，引入一個(gè)隨機(jī)時(shí)間間隔，為每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)計(jì)時(shí)器T，T的計(jì)算綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)距離BS的位置、節(jié)點(diǎn)曾經(jīng)當(dāng)選群首的次數(shù)，當(dāng)?shù)竭_(dá)計(jì)時(shí)時(shí)間后，具有最短時(shí)間間隔的節(jié)點(diǎn)有更大機(jī)會(huì)成為群首節(jié)點(diǎn)。與原有的LEACH算法相比，LEACH-T具有更好的性能，它不僅保留了分布式群首產(chǎn)生的優(yōu)點(diǎn)，還避免了每輪產(chǎn)生群首個(gè)數(shù)的不確定性，更能均勻分布群首節(jié)點(diǎn)，使群首節(jié)點(diǎn)的選擇趨于合理，從而達(dá)到網(wǎng)絡(luò)能耗均衡，節(jié)省能量，最大化生命周期的目的。

3 總結(jié)

LEACH算法的改進(jìn)是多種多樣的，在上述的改進(jìn)方案中，有的提出了一套完整的從群首選擇到數(shù)據(jù)傳輸?shù)男碌乃惴ǎ械母倪M(jìn)算法只是針對(duì)其中一個(gè)階段提出了新的想法。以上關(guān)于LEACH協(xié)議算法的改進(jìn)仍然保留著原有的LEACH協(xié)議算法思想，都是以如何節(jié)省能量和延長(zhǎng)網(wǎng)絡(luò)生命周期作為改進(jìn)考慮的核心問題。對(duì)以上算法的改進(jìn)，仿真實(shí)驗(yàn)表明，相比于傳統(tǒng)的LEACH在延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間、節(jié)省能量和平衡節(jié)點(diǎn)能量消耗等方面有更優(yōu)的性能。

[1]陳林星編著.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].電子工業(yè)出版社.2009.3:151-156

[2]Handy M J,Haase M,Timmermann D.Low Energy Adaptive Clustering Hierarchy W it h Deter ministic C luster-head Selection[C]//Proceedings of the 4th I EEE Conference on Mobile and Wireless Communications Networks.I EEE Communications Society,2002:368-372.

[3]Heinzelman W B.Application-Specific Prot ocol Architect u res for Wireless Network s[D].Ph.D Dissertation.Boston:Massachusetts Institute of Technology,2000.

[4]王萬良,陳陪俊,鄭建煒.一種基于 LEACH的無線傳感器路由算法及其仿真[J].系統(tǒng)仿真技術(shù),2008,4(2):75-79

[5]顧相平,孫彥景,錢建生.一種改進(jìn)的無線傳感器網(wǎng)絡(luò) LEACH-ED 算法[J].傳感技術(shù)學(xué)報(bào),2008,21(10):1770-1774

[6]李天池.無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的算法改進(jìn)[D],山東大學(xué).2012.3

[7]柳麗娜.無線傳感器網(wǎng)絡(luò)中LEACH算法的研究和改進(jìn)[D],吉林大學(xué).2012.5

[8]劉長(zhǎng)江.基于能耗優(yōu)化的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議研究與改進(jìn)[D].廣西大學(xué).2012.6

[9]李成岳,申鉉京,陳海鵬,孫恩巖.無線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進(jìn)[J].傳感技術(shù)學(xué)報(bào).2010年8月第23卷第8期:1163-1167