無(wú)線傳感網(wǎng)絡(luò)LEACH協(xié)議的優(yōu)化研究

舒冰，蘇震

(中國(guó)傳媒大學(xué) 信息工程學(xué)院，北京 100024)

?

無(wú)線傳感網(wǎng)絡(luò)LEACH協(xié)議的優(yōu)化研究

舒冰，蘇震

(中國(guó)傳媒大學(xué) 信息工程學(xué)院，北京 100024)

摘要：LEACH(Low-Energy Adaptive Clustering Hierarchy低功耗自適應(yīng)分簇)算法可以有效地解決傳感器節(jié)點(diǎn)能量限制的問(wèn)題，顯著地延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期。但在分簇簇頭的選擇過(guò)程中僅考慮此節(jié)點(diǎn)是否在之前的輪中擔(dān)任過(guò)簇頭節(jié)點(diǎn)，并未考慮節(jié)點(diǎn)剩余的能量與其所處的位置，使得簇頭的選擇并非最優(yōu)。針對(duì)這種情況，本文在原有LEACH路由算法的基礎(chǔ)上從節(jié)點(diǎn)剩余能量與節(jié)點(diǎn)分布位置兩方面對(duì)其進(jìn)行優(yōu)化，提出了一種新的路由優(yōu)化算法為I-LEACH。仿真結(jié)果顯示I-LEACH較LEACH協(xié)議延長(zhǎng)了網(wǎng)絡(luò)生存周期，降低了網(wǎng)絡(luò)總體能耗，使無(wú)線傳感網(wǎng)的整體性能得到一定提升。

關(guān)鍵詞：LEACH；無(wú)線傳感網(wǎng)絡(luò)；分簇；簇頭選擇；能耗；生存周期

1引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)由許多具有低功率無(wú)線收發(fā)裝置的傳感器節(jié)點(diǎn)組成，能夠采集周?chē)h(huán)境信息并傳送到遠(yuǎn)處的基站進(jìn)行處理。由于傳感器節(jié)點(diǎn)的電池能量有限，因此節(jié)點(diǎn)的通信應(yīng)該有效地利用能量，以延長(zhǎng)網(wǎng)絡(luò)的生命周期。

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)要進(jìn)行數(shù)據(jù)通信就要有相應(yīng)的無(wú)線網(wǎng)絡(luò)協(xié)議(包括MAC層、路由、網(wǎng)絡(luò)層、應(yīng)用層等)，傳統(tǒng)的無(wú)線協(xié)議很難適應(yīng)WSN的低花費(fèi)、低能量、高容錯(cuò)性等的要求。在這種情況下，ZigBee協(xié)議應(yīng)運(yùn)而生，Zigbee的基礎(chǔ)是IEEE 802.15.4。但I(xiàn)EEE僅處理低級(jí)MAC層和物理層協(xié)議，而Zigbee聯(lián)盟擴(kuò)展了IEEE，對(duì)其網(wǎng)絡(luò)層協(xié)議進(jìn)行了標(biāo)準(zhǔn)化。但值得注意的是，在已經(jīng)發(fā)布的ZigbeeV1.0中并沒(méi)有規(guī)定具體的路由協(xié)議。

網(wǎng)絡(luò)數(shù)據(jù)傳輸離不開(kāi)路由協(xié)議，路由協(xié)議是其組網(wǎng)的基礎(chǔ)，路由技術(shù)是WSN通信層的核心技術(shù)。路由選擇問(wèn)題是WSN網(wǎng)絡(luò)構(gòu)建時(shí)所要著重考慮的一個(gè)問(wèn)題，從路由的角度來(lái)看，WSN有其自身的特點(diǎn)，使它既不同于傳統(tǒng)固定網(wǎng)絡(luò)，又不同于無(wú)線自組網(wǎng)AdHoc網(wǎng)絡(luò)。在其研究初期，人們認(rèn)為成熟的Internet技術(shù)加上AdHoc路由機(jī)制對(duì)WSN的設(shè)計(jì)是足夠充分的，但是深入地研究表明，WSN有不同于傳統(tǒng)無(wú)線網(wǎng)絡(luò)和AdHoc網(wǎng)絡(luò)的特點(diǎn)，前者以數(shù)據(jù)為中心，而后兩者以傳輸數(shù)據(jù)為目的。由于WSN與傳統(tǒng)網(wǎng)絡(luò)對(duì)數(shù)據(jù)的側(cè)重點(diǎn)不同，使得傳統(tǒng)的無(wú)線AdHoc網(wǎng)絡(luò)路由協(xié)議并不適合用于WSN，所以我們必須設(shè)計(jì)全新的、適合于WSN特點(diǎn)的路由協(xié)議。雖然已經(jīng)提出了很多的路由協(xié)議，但是到底哪一種是最合適的還沒(méi)有一個(gè)定論，因此WSN路由協(xié)議的研究與設(shè)計(jì)是近年來(lái)國(guó)內(nèi)外研究的熱點(diǎn)課題。

LEACH協(xié)議是為WSN專(zhuān)門(mén)設(shè)計(jì)的低功耗自適應(yīng)分簇路由協(xié)議，是一種基于分簇結(jié)構(gòu)和完全分布式的層次路由協(xié)議，其后的大部分層次式路由協(xié)議都是在此基礎(chǔ)上發(fā)展而來(lái)。它將傳感器網(wǎng)絡(luò)節(jié)點(diǎn)以一定限制條件劃分成簇，在工作過(guò)程中各節(jié)點(diǎn)獨(dú)立地按照概率隨機(jī)決定自己是否做簇頭，通過(guò)周期性的簇頭選舉和網(wǎng)絡(luò)重組過(guò)程，形成了輪轉(zhuǎn)的工作方式。這樣可有效平衡網(wǎng)絡(luò)負(fù)載，大大節(jié)約了通信過(guò)程中的能量消耗。另外，簇頭節(jié)點(diǎn)在處理數(shù)據(jù)的時(shí)候用到了數(shù)據(jù)融合技術(shù)和數(shù)據(jù)壓縮技術(shù)，使得傳輸?shù)臄?shù)據(jù)量大大減小。因此如何優(yōu)化簇頭的選擇是算法設(shè)計(jì)中所必須考慮的重要問(wèn)題之一。然而由于LEACH協(xié)議的簇頭選擇僅以此節(jié)點(diǎn)是否在過(guò)去幾輪擔(dān)任過(guò)簇頭這一標(biāo)準(zhǔn)，在實(shí)際應(yīng)用中，會(huì)使擁有較低剩余能量的節(jié)點(diǎn)同較高剩余能量的節(jié)點(diǎn)具有相同的概率成為簇頭節(jié)點(diǎn)，并未能達(dá)到簇頭選擇的最優(yōu)化。

本文針對(duì)LEACH簇頭選擇算法的不足之處，在LEACH簇頭選擇算法的基礎(chǔ)上，提出將節(jié)點(diǎn)剩余能量與節(jié)點(diǎn)到基站的距離作為簇頭選擇的考慮因素，根據(jù)節(jié)點(diǎn)所在區(qū)域的不同將上述的兩個(gè)參數(shù)進(jìn)行加權(quán)處理，最后根據(jù)加權(quán)簇頭選擇閾值選出更加合理的簇頭，進(jìn)而合理分配網(wǎng)絡(luò)節(jié)點(diǎn)能耗，提高網(wǎng)絡(luò)的生命周期。

2LEACH協(xié)議

LEACH協(xié)議的主要目的是均衡網(wǎng)絡(luò)能耗以增加網(wǎng)絡(luò)生命周期。為達(dá)到此目的LEACH路由算法使用分層方式將網(wǎng)絡(luò)分為一系列的簇，每個(gè)簇由一個(gè)簇頭控制。簇頭按照TDMA(Time Division Multiple Access，時(shí)分多址機(jī)制)分配時(shí)隙給每個(gè)簇成員節(jié)點(diǎn)，使其可在分配的時(shí)隙內(nèi)向簇頭發(fā)送數(shù)據(jù)以及對(duì)接收的數(shù)據(jù)進(jìn)行聚合處理以去除多余的相關(guān)數(shù)據(jù)進(jìn)而減少發(fā)送能耗，最后簇頭將處理后的數(shù)據(jù)直接發(fā)送至基站，LEACH協(xié)議網(wǎng)絡(luò)拓?fù)淙鐖D1所示。LEACH協(xié)議的流程以輪作為基本單元，每輪又由兩個(gè)階段組成，分別是簇形成階段與穩(wěn)定傳輸階段。

圖1　LEACH協(xié)議網(wǎng)絡(luò)拓?fù)鋱D

2.1　簇形成階段

2.1.1　簇頭選擇輪轉(zhuǎn)算法

確定當(dāng)前節(jié)點(diǎn)i是否成為簇頭節(jié)點(diǎn)，i節(jié)點(diǎn)在0到1之間選擇一個(gè)隨機(jī)數(shù)V，隨后將此V值與簇頭選擇閾值T(n)進(jìn)行比較，若V

(1)

式中，P是簇頭的節(jié)點(diǎn)占節(jié)點(diǎn)總數(shù)的百分比，r為當(dāng)前循環(huán)輪數(shù)，G為在過(guò)去輪中沒(méi)有當(dāng)選成簇頭的節(jié)點(diǎn)集合，符號(hào)mod是求模運(yùn)算符，使用這個(gè)閾值，每個(gè)節(jié)點(diǎn)會(huì)在輪操作內(nèi)擔(dān)當(dāng)一次簇頭節(jié)點(diǎn)。

在每輪循環(huán)中，如果節(jié)點(diǎn)己經(jīng)當(dāng)選過(guò)簇頭，則把T(n)設(shè)置為0，這樣該節(jié)點(diǎn)不會(huì)再次當(dāng)選為簇頭。對(duì)于未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)，則將以T(n)的概率當(dāng)選；隨著當(dāng)選過(guò)簇頭的節(jié)點(diǎn)數(shù)目增加，剩余節(jié)點(diǎn)當(dāng)選的閾值T(n)隨之增大，節(jié)點(diǎn)產(chǎn)生小于T(n)的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選簇頭的概率增大，這樣才能保證每一輪中簇頭的個(gè)數(shù)保持均衡。當(dāng)只剩下一個(gè)節(jié)點(diǎn)未當(dāng)選簇頭時(shí)，設(shè)其T(n)=1，表示還沒(méi)有做過(guò)簇頭的節(jié)點(diǎn)，即這個(gè)節(jié)點(diǎn)一定當(dāng)選為簇頭節(jié)點(diǎn)，因?yàn)樗械墓?jié)點(diǎn)的標(biāo)志值都是在0-1之間的，等過(guò)了1/P輪以后，所有的節(jié)點(diǎn)就又可以重新充當(dāng)簇頭節(jié)點(diǎn)了。

2.1.2　簇形成算法

一旦某些節(jié)點(diǎn)被選定為簇頭，這些簇頭必須讓網(wǎng)絡(luò)中其它節(jié)點(diǎn)知道在當(dāng)前輪中他們成為簇頭的消息。這要求每個(gè)簇頭使用CSMA(Carrier Sense Multiple Access，載波偵聽(tīng)多路訪問(wèn))MAC協(xié)議向剩余節(jié)點(diǎn)們廣播自己成為簇頭的宣告消息。剩余節(jié)點(diǎn)在簇頭廣播階段必須將接收器持續(xù)打開(kāi)以接聽(tīng)簇頭們的宣告消息，在一定時(shí)間間隔接收到多個(gè)宣告消息之后，根據(jù)接收到宣告消息的強(qiáng)度來(lái)決定加入哪個(gè)簇。這是由于宣告消息的強(qiáng)度越大說(shuō)明這個(gè)節(jié)點(diǎn)和發(fā)出此消息的簇頭的距離越近，從而加入此簇頭所在的簇相對(duì)可以節(jié)省能量。

在每個(gè)節(jié)點(diǎn)確定加入哪個(gè)簇之后，它必須告訴簇頭它成為這個(gè)簇的成員。每個(gè)節(jié)點(diǎn)同樣使用CSMA MAC協(xié)議發(fā)送加入此簇申請(qǐng)消息到相應(yīng)的簇頭。簇頭接收所有的申請(qǐng)消息后根據(jù)簇成員節(jié)點(diǎn)的數(shù)目，以TDMA方式為每個(gè)簇成員節(jié)點(diǎn)分配時(shí)隙并用廣播的形式發(fā)送到本簇內(nèi)所有的簇成員節(jié)點(diǎn)，每個(gè)簇成員節(jié)點(diǎn)便可以在自己分配到的時(shí)隙中進(jìn)入了穩(wěn)定傳輸階段。

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

在此階段，簇成員節(jié)點(diǎn)周期地采集傳感數(shù)據(jù)并在分配到的時(shí)隙中向簇頭發(fā)送采集到的數(shù)據(jù)。整個(gè)傳輸階段以幀為單位分為等時(shí)間間隔的時(shí)隙，在發(fā)送完數(shù)據(jù)后，簇成員節(jié)點(diǎn)進(jìn)入休眠狀態(tài)以減少能耗。建立數(shù)據(jù)發(fā)送時(shí)序表是為了避免同時(shí)向簇頭發(fā)送數(shù)據(jù)時(shí)所產(chǎn)生的碰撞，并且增加每一個(gè)非簇頭節(jié)點(diǎn)的休眠時(shí)間以減少能耗。LEACH協(xié)議時(shí)序流程如圖2所示。

圖2　LEACH協(xié)議時(shí)序流程圖

3I-LEACH優(yōu)化協(xié)議

由于LEACH路由算法中簇頭選擇方式單一，僅考慮其在之前的輪中是否已被選為簇頭節(jié)點(diǎn)這一條限制條件。而在實(shí)際情況中，僅此一條限制條件無(wú)法達(dá)到簇頭的最優(yōu)選擇。針對(duì)LEACH路由算法的這種缺點(diǎn)，本文在LEACH協(xié)議簇頭選擇算法的基礎(chǔ)上從能量與距離兩個(gè)方面對(duì)算法提出優(yōu)化。

本文使用的傳感網(wǎng)絡(luò)仿真區(qū)域分為3個(gè)部分。根據(jù)節(jié)點(diǎn)當(dāng)前能量與初始能量的比值與簇頭到基站的距離作為簇頭選擇的兩個(gè)主要參數(shù)，在不同的子區(qū)域內(nèi)能量與距離的加權(quán)處理方式不同。式(2)為I-LEACG協(xié)議T(n)的表達(dá)式：

(2)

式中，α為能量和距離的加權(quán)因子為一常數(shù)值0.75，dtoBS是傳感節(jié)點(diǎn)到基站的距離，Ecurrent是本輪當(dāng)前節(jié)點(diǎn)能量值，Einit是傳感節(jié)點(diǎn)初始能量值：

同LEACH算法一樣，每個(gè)傳感節(jié)點(diǎn)選擇一個(gè)隨機(jī)數(shù)，但在本文提出的優(yōu)化路由算法中此隨機(jī)數(shù)的取值范圍有所不同，即在0至narea_i之間隨機(jī)選擇一個(gè)數(shù)值為V，同時(shí)在不同的節(jié)點(diǎn)分布區(qū)域內(nèi)narea_i的取值范圍不同，具體取值方法如下：

接著將此隨機(jī)數(shù)V與優(yōu)化的簇頭選擇閾值進(jìn)行比較。假如，v

圖3　I-LEACH協(xié)議簇頭選擇算法流程圖

4仿真結(jié)果與分析

本文使用Matlab軟件仿真路由算法優(yōu)化的結(jié)果。WSN區(qū)域是一個(gè)200m×200m的正方形區(qū)域，基站位于原點(diǎn)處，分別以?xún)蓚€(gè)半徑不同的同心圓弧(半徑分別為100m和200m)將整個(gè)網(wǎng)絡(luò)區(qū)域分為三個(gè)子區(qū)域，網(wǎng)絡(luò)節(jié)點(diǎn)區(qū)域分布仿真如圖4所示以及仿真參數(shù)的具體設(shè)定如表1所示。

表1　仿真參數(shù)的設(shè)定

圖4　網(wǎng)絡(luò)節(jié)點(diǎn)區(qū)域分布仿真圖

4.1　網(wǎng)絡(luò)生存周期

如圖5所示的是網(wǎng)絡(luò)存活節(jié)點(diǎn)總數(shù)隨輪數(shù)的變化曲線，此曲線即是整個(gè)網(wǎng)絡(luò)的生存周期圖。從圖中可以明顯看出I-LEACH協(xié)議的仿真曲線比LEACH協(xié)議下降的更慢，這說(shuō)明I-LEACH協(xié)議在接下來(lái)的周期里存活節(jié)點(diǎn)數(shù)比LEACH協(xié)議更多。在此兩種路由協(xié)議管理下的網(wǎng)絡(luò)失效周期即無(wú)存活節(jié)點(diǎn)周期分別為L(zhǎng)EACH(460輪左右)而I-LEACH(850輪左右)，I-LEACH協(xié)議網(wǎng)絡(luò)的生存周期相較LEACH協(xié)議幾乎增大了一倍。這是因?yàn)镮-LEACH路由算法在進(jìn)行簇頭選擇時(shí)考慮到了更多實(shí)際因素，使得網(wǎng)絡(luò)整體能耗更加趨于合理，從而增加了網(wǎng)絡(luò)的生存周期。

圖5　網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)對(duì)比圖

圖6　網(wǎng)絡(luò)能耗對(duì)比圖

4.2　網(wǎng)絡(luò)能量消耗

網(wǎng)絡(luò)能耗的主要來(lái)源為簇頭接收和融合數(shù)據(jù)能耗、簇頭發(fā)送數(shù)據(jù)到基站能耗、簇成員節(jié)點(diǎn)發(fā)送數(shù)據(jù)到簇頭能耗。這里假設(shè)簇內(nèi)數(shù)據(jù)的接收與發(fā)送距離較短，可以使用自由空間模型建模。而簇頭與基站的距離較遠(yuǎn)，采用多徑衰落模型建模，兩種模型的區(qū)分標(biāo)準(zhǔn)如下所示：

設(shè)一個(gè)區(qū)分兩種空間模型的距離臨界值d0，如果收發(fā)距離大于d0，則收發(fā)能耗按照多徑衰落模型計(jì)算，反之，按照自由空間模型計(jì)算。式(3)為d0的計(jì)算公式：

(3)

發(fā)送或接收l(shuí) bit的數(shù)據(jù)在距離為d的條件下發(fā)送能耗ETX公式與接收數(shù)據(jù)能耗ERX分別如式(4)-(6)所示：

如果d

ETX(l，d)=Eelec·l+Efs·l·d2

(4)

如果d>d0，符合多徑衰落信道模型，

ETX(l，d)=Eelec·l+Efs·l·d4

(5)

ERX=Eelec+EDA·l

(6)

式中，Eelec是收發(fā)電路發(fā)送或接收每比特?cái)?shù)據(jù)的能耗值；Emp是在多徑衰落信道中的信號(hào)放大能耗；Efs是在自由空間信道中的信號(hào)放大能耗；EDA是數(shù)據(jù)聚合能耗值。

網(wǎng)絡(luò)總體能耗計(jì)算模型如式(7)-(10)所示：

簇頭能耗：

ECH=ERX+ETX(l，d)

=(Eelec+EDA)·l+Eelec·l+Emp·l+d4

(7)

簇成員能耗：

ECM=ETX(l，d)=Eelec·l+Efs·l·d2

(8)

單個(gè)簇群能耗：

(9)

網(wǎng)絡(luò)總能耗：

(10)

其中，k是本簇內(nèi)共有的簇成員數(shù)，countCHs是每輪網(wǎng)絡(luò)選出的簇頭總數(shù)。

如圖6所示的是兩種路由協(xié)議下的網(wǎng)絡(luò)總體能耗圖，從零輪起I-LEACH路由算法能量消耗增長(zhǎng)的速率明顯低于LEACH協(xié)議，其中LEACH路由協(xié)議在300輪左右就達(dá)到了網(wǎng)絡(luò)能耗的最大值，而I-LEACH網(wǎng)絡(luò)能耗達(dá)到最大值(與LEACH的相同)則是在750輪左右。此圖說(shuō)明I-LEACH協(xié)議下網(wǎng)絡(luò)的整體能耗在0至750輪之間比LEACH協(xié)議要小，進(jìn)而使網(wǎng)絡(luò)的生存周期有所延長(zhǎng)。

5結(jié)論

本文針對(duì)LEACH路由協(xié)議簇頭選擇參考因素單一的缺點(diǎn)，從節(jié)點(diǎn)本輪能量與初始能量比值和節(jié)點(diǎn)與基站之間的距離二者加權(quán)的簇頭選擇閾值對(duì)LEACH路由協(xié)議進(jìn)行優(yōu)化，進(jìn)而提出了I-LEACH路由協(xié)議算法。通過(guò)仿真結(jié)果可知，此優(yōu)化協(xié)議較LEACH延長(zhǎng)了網(wǎng)絡(luò)生存周期，降低了網(wǎng)絡(luò)總體能耗，使無(wú)線傳感網(wǎng)絡(luò)的整體性能得到進(jìn)一步提升，對(duì)WSN路由協(xié)議設(shè)計(jì)與研究提供了一些參考。

參考文獻(xiàn)

[1]Gajjar S H，Dasgupta K S，Pradhan S N，Vala K M.Lifetime Improvement of LEACH Protocol for Wireless Sensor Network[C].NIRMA University International Conference on Engineering，2012.

[2]Handy M，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C].IEEE International Conference on Mobile Wireless Communications Networks，September 2002：368-372.

[3]孫利民，李建中，陳渝.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[4]張浩，李臘元.基于LEACH 協(xié)議的能耗均衡路由算法[J].計(jì)算機(jī)工程，2011，7(7)：91-93.

[5]謝冬梅.無(wú)線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議的研究[D].南京：河海大學(xué)計(jì)算機(jī)及信息工程學(xué)院，2007.

(責(zé)任編輯：王謙)

The Optimization Research of LEACH Protocol In Wireless Sensor Network

SHU Bing，SU Zhen

(College of Information and Engineering，Communication University of China，Beijing 100024，China)

Abstract：LEACH (Low-Energy Adaptive Clustering Hierarchy)can effectively solve the problem which is the energy of sensor node is limited，and significantly extend the lifetime of the whole network.But in the process of the election of cluster head (CH) only consider whether this node in the previous round was served as CH nodes，don’t consider the node residual energy and location，making CH selection is not optimal.In view of this kind of situation，this paper have improved LEACH routing algorithm from the aspects of node location and residual energy of nodes，therefore an optimized algorithm is proposed and called I-LEACH.The simulation results show that I-LEACH extend the network lifetime much longer than LEACH and reduce the network total energy consumption，so making the performance of WSN have been promoted.

Keywords：LEACH；WSN；clustering；selection of CH；energy consumption；lifetime of WSN

作者簡(jiǎn)介：舒冰(1986-)，男(漢族)，山西太原人，中國(guó)傳媒大學(xué)碩士研究生.E-mail：shubing062022104@163.com

收稿日期：2015-04-12

中圖分類(lèi)號(hào)：TN915.02

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-4793(2015)05-0054-06