王?；ǎ瑒?云，向 嬋

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

在無線傳感器網(wǎng)絡(luò)(WSN)中，延長網(wǎng)絡(luò)生命周期[1]是目前研究的一個(gè)關(guān)鍵領(lǐng)域。由于傳感器節(jié)點(diǎn)數(shù)目龐大，且大多數(shù)節(jié)點(diǎn)離基站距離較遠(yuǎn)，導(dǎo)致能量利用效率過低，網(wǎng)絡(luò)生命時(shí)間過短等問題[2]。

Heinzelman W[3]等人提出了LEACH協(xié)議，通過分簇，以循環(huán)的方式隨機(jī)選舉簇頭，集中式處理節(jié)點(diǎn)到基站之間的數(shù)據(jù)傳輸，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)節(jié)點(diǎn)上，一定程度上降低了節(jié)點(diǎn)的能耗[4]，延長了網(wǎng)絡(luò)生命時(shí)間。但是由于LEACH協(xié)議存在多次分簇的缺陷，造成了能量浪費(fèi)。

蘭慎[5]等人又在LEACH協(xié)議的基礎(chǔ)上提出了S_LEACH協(xié)議，該算法通過一次分簇，形成工作簇頭和休眠簇頭，并隨機(jī)選擇休眠簇頭進(jìn)入工作狀態(tài)，節(jié)省了大量因多次分簇所造成的能量損失。

LEACH協(xié)議和S_LEACH協(xié)議都在原有基礎(chǔ)上降低了能耗，延長了生命時(shí)間。但是LEACH協(xié)議多次分簇，且大量工作負(fù)載都集中在簇頭節(jié)點(diǎn)上進(jìn)行，造成能量浪費(fèi)，S_LEACH協(xié)議隨機(jī)選擇休眠簇頭，不能保障簇頭之間的能量平衡，無法保障穩(wěn)定性，并且讓被替換掉的工作簇頭繼續(xù)充當(dāng)普通節(jié)點(diǎn)工作，也造成了簇頭節(jié)點(diǎn)的能量損失。

本文借助S_LEACH協(xié)議的優(yōu)勢提出了能量感知選擇休眠簇頭算法ELSS。

1 模型建立

在無線傳感器網(wǎng)絡(luò)中，為了使網(wǎng)絡(luò)生命時(shí)間最大化，就必須使傳感器節(jié)點(diǎn)能量得到最大利用。相對而言，在網(wǎng)絡(luò)工作過程中，簇頭節(jié)點(diǎn)工作負(fù)載更大，需要消耗的能量也就更多，因此若想保障網(wǎng)絡(luò)生命時(shí)間，就必須保障簇頭節(jié)點(diǎn)的正常工作，此時(shí)就必須尋找額外的傳感器節(jié)點(diǎn)來分擔(dān)簇頭節(jié)點(diǎn)的工作壓力[6-7]。顯然，LEACH協(xié)議已不能提供足夠的網(wǎng)絡(luò)需求，而S_LEACH協(xié)議雖然可以提供休眠簇頭來輪流充當(dāng)簇頭工作，但是由于其隨機(jī)性仍然不能保障休眠簇頭的能量平衡，以及其將替換掉的簇頭作為普通節(jié)點(diǎn)繼續(xù)探測工作也造成簇頭節(jié)點(diǎn)能量損失，從而不能保障簇頭節(jié)點(diǎn)能量最大化利用。

因此，本文在LEACH協(xié)議基礎(chǔ)上對S_LEACH協(xié)議做出如下改進(jìn)，從而提出能量感知選擇簇頭算法-ELSS，算法模型如圖1所示。

圖1 ELSS算法模型

首先，定義該無線傳感網(wǎng)絡(luò)中各子網(wǎng)絡(luò)的工作簇頭用集合{Aio|Aio=A1o,A2o,A3o,…,Ako}表示；某個(gè)子網(wǎng)絡(luò)中的各休眠簇頭用集合{Ais|Ais=A1s,A2s,…,Ans}表示；子網(wǎng)絡(luò)中各節(jié)點(diǎn)整體的剩余平均能量為Ea，工作簇頭節(jié)點(diǎn)剩余能量為E1，各休眠簇頭節(jié)點(diǎn)剩余能量分別為E1l，E2l，E3l,…,Enl，除休眠簇頭以外的各節(jié)點(diǎn)剩余能量為E1，E2，E3,…,En。

其次，假設(shè)有N個(gè)節(jié)點(diǎn)均勻分布在一個(gè)A=M×M區(qū)域，且基站離監(jiān)測節(jié)點(diǎn)都相對較遠(yuǎn)。在這種情況下存在兩種能量衰退模型，一種是多路徑衰退模型，其衰退系數(shù)為εmp，另一種是自由空間衰退模型，其衰退系數(shù)為εfs。如果網(wǎng)絡(luò)中各節(jié)點(diǎn)到基站的距離用dtoBS表示，那么網(wǎng)絡(luò)中所存在的最優(yōu)工作簇頭個(gè)數(shù)kopt可通過式(1)[8]計(jì)算得出

(1)

其中節(jié)點(diǎn)到基站的平均距離dtoBS可由式(2)計(jì)算得出

(2)

其中，x和y是以基站為原點(diǎn)，任意方向?yàn)檎较蛳赂鞴?jié)點(diǎn)的坐標(biāo)值。

同理將監(jiān)測區(qū)域內(nèi)的每一個(gè)子網(wǎng)格看成是另一個(gè)分簇網(wǎng)絡(luò)結(jié)構(gòu)，其中的工作簇頭就相當(dāng)于基站，確定的休眠簇頭就相當(dāng)于整個(gè)網(wǎng)絡(luò)中的工作簇頭。此時(shí)，假設(shè)其中某個(gè)子網(wǎng)格中有n個(gè)節(jié)點(diǎn)均勻分布，子網(wǎng)格大小為a=m×m，工作簇頭位于子網(wǎng)格的中心位置，子網(wǎng)格中各節(jié)點(diǎn)到工作簇頭的平均距離用dtoHS表示，那么該子網(wǎng)格中所需要的休眠工作簇頭的個(gè)數(shù)k1就可以由式(3)[9-10]計(jì)算得出

(3)

其中節(jié)點(diǎn)到工作簇頭的平均距離dtoHS可由式(4)[11]計(jì)算得出

(4)

其中，x和y是以工作簇頭為原點(diǎn)，任意方向?yàn)檎较蛳伦泳W(wǎng)格中各節(jié)點(diǎn)的坐標(biāo)值。

2 ELSS算法

2.1 算法描述

假設(shè)經(jīng)計(jì)算所得最優(yōu)簇頭數(shù)為k，則根據(jù)計(jì)算所得簇頭數(shù)k在監(jiān)測區(qū)域等面積劃分為k個(gè)子區(qū)域，并在相應(yīng)區(qū)域?qū)ふ乙粋€(gè)最接近中心位置的傳感器節(jié)點(diǎn)作為首個(gè)工作簇頭節(jié)點(diǎn)A1o，A2o，A3o,…,Ako。至此，各分簇簇頭節(jié)點(diǎn)已經(jīng)選定。

在各分簇簇頭產(chǎn)生之后，簇頭節(jié)點(diǎn)Aio向周圍所有傳感器節(jié)點(diǎn)普遍發(fā)送當(dāng)選簇頭信息，各傳感器節(jié)點(diǎn)根據(jù)收到簇頭節(jié)點(diǎn)信號的強(qiáng)度選擇信號最強(qiáng)的簇頭節(jié)點(diǎn)加入其所在簇，并將加入信息回復(fù)給簇頭節(jié)點(diǎn)[12-14]。然后，簇頭節(jié)點(diǎn)根據(jù)回復(fù)信號強(qiáng)弱選擇信號最強(qiáng)的n個(gè)節(jié)點(diǎn)A1s，A2s,…,Ans作為休眠簇頭(n為式(2)計(jì)算所得分簇休眠簇頭數(shù))，并根據(jù)節(jié)點(diǎn)ID將選舉結(jié)果通知相應(yīng)休眠簇頭節(jié)點(diǎn)。最后簇頭節(jié)點(diǎn)將收錄得到的信息，包括休眠簇頭信息通知基站，并收到基站的回復(fù)。這樣，整個(gè)分簇過程才是成功的，簇頭組形成，分簇階段結(jié)束[15]。

在分簇階段結(jié)束過后，WSN就將進(jìn)入工作階段。工作階段首先由首次選定的工作簇頭Aio開始工作，管理與收發(fā)所在簇內(nèi)各節(jié)點(diǎn)信息。同時(shí)簇頭節(jié)點(diǎn)不停地探測簇內(nèi)各節(jié)點(diǎn)的剩余能量，并通過求均值函數(shù)式(5)取得整體剩余能量均值Ea。

(5)

然后將Ea與自身剩余能量El比較，若EaEl時(shí)，Aio根據(jù)探測得到的休眠簇頭Ais剩余能量多少利用取最大值公式(6)選擇能量最高的休眠簇頭，并根據(jù)其ID向其發(fā)送喚醒消息。

MAX{E1l，E2l，E3l，…，Enl}

(6)

當(dāng)Ais接收到消息后做好工作準(zhǔn)備并回復(fù)消息給Aio，Aio收到回復(fù)后立即將更換簇頭消息發(fā)送給基站，得到基站的回復(fù)后再將更換簇頭信息及新簇頭ID發(fā)送給簇內(nèi)所有節(jié)點(diǎn)，包括新簇頭Ais，Ais收到信息后立即開始工作，并再次回復(fù)Aio，Aio收到回復(fù)進(jìn)入休眠。這個(gè)過程依次反復(fù)，直到所有節(jié)點(diǎn)能量耗盡。

2.2 算法分析

相比較LEACH協(xié)議算法和S_LEACH協(xié)議，ELSS算法在延長網(wǎng)絡(luò)生命周期方面做出了進(jìn)一步的改進(jìn)。由于ELSS算法在分簇階段采用的是S_LEACH協(xié)議的分簇機(jī)制，所以相對于LEACH協(xié)議在延長生命時(shí)間方面做出的改進(jìn)在文獻(xiàn)[2]中已有分析，通過避免多次分簇所造成的能量損失來延長網(wǎng)絡(luò)生命時(shí)間。因而本算法將不再針對LEACH協(xié)議進(jìn)行比較分析，而將著力比較S_LEACH協(xié)議，從能耗和能量平衡兩方面來分析本算法對延長網(wǎng)絡(luò)生命時(shí)間所作出的改進(jìn)。

(1)能耗分析。在子網(wǎng)絡(luò)中，假設(shè)所有簇頭(包括初始工作簇頭和休眠簇頭)的初始能量均為Em1，簇頭節(jié)點(diǎn)工作平均每個(gè)單位時(shí)長消耗能量為m1；所有工作中的節(jié)點(diǎn)(包括普通傳感節(jié)點(diǎn)和工作簇頭節(jié)點(diǎn))的初始平均能量為Em2，平均每個(gè)節(jié)點(diǎn)每單位時(shí)長消耗能量為m2；易知：Em1>Em2，m1>m2。在S_LEACH協(xié)議中，由于被替換掉的簇頭節(jié)點(diǎn)將被降為普通節(jié)點(diǎn)，所以每個(gè)簇頭節(jié)點(diǎn)只工作一次。于是令從第一個(gè)簇頭節(jié)點(diǎn)開始，每個(gè)簇頭節(jié)點(diǎn)工作的時(shí)長分別為T1，T2，T3，…，Tn。

在S_LEACH協(xié)議中，當(dāng)初始簇頭節(jié)點(diǎn)工作完畢時(shí)，已知其節(jié)點(diǎn)剩余能量約等于所有節(jié)點(diǎn)的平均剩余能量，于是可得等式

Em1=m1T1=Em2-m2T1

(7)

即可以表示出第1個(gè)簇頭節(jié)點(diǎn)工作時(shí)間為

(8)

那么，第1個(gè)簇頭節(jié)點(diǎn)所造成的能量損失為

(9)

第2個(gè)簇頭節(jié)點(diǎn)工作完畢剩余能量等式為

(10)

即第2個(gè)簇頭節(jié)點(diǎn)工作時(shí)間為

(11)

那么，第2個(gè)簇頭節(jié)點(diǎn)所造成的能量損失為

(12)

同理可得第3個(gè)簇頭節(jié)點(diǎn)所造成的能量損失為

(13)

(14)

因此，ELSS算法相對于S_LEACH協(xié)議在簇頭組內(nèi)所減少的能量損耗為

(15)

(2)能量均衡分析。能量平衡對于傳感網(wǎng)絡(luò)的穩(wěn)定性有著至關(guān)重要的影響。S_LEACH協(xié)議在簇頭節(jié)點(diǎn)更換時(shí)使用隨機(jī)選擇機(jī)制，這樣有可能選擇到能量較低的休眠簇頭進(jìn)行工作，而這樣的簇頭不能保證長時(shí)間的工作，就需要頻繁更換簇頭，不僅造成了能量在更換簇頭時(shí)的浪費(fèi)，而且容易造成部分簇頭節(jié)點(diǎn)過早死亡，導(dǎo)致傳感網(wǎng)絡(luò)的穩(wěn)定性下降。

當(dāng)用ELSS算法來代替S_LEACH協(xié)議進(jìn)行更換簇頭，該算法將會(huì)對休眠簇頭剩余能量進(jìn)行比較選擇能量最高的休眠簇頭來代替原有工作簇頭進(jìn)行持續(xù)工作。這樣可以使整個(gè)簇頭組節(jié)點(diǎn)能量穩(wěn)步減少，保障簇頭組內(nèi)節(jié)點(diǎn)能量的平衡，不僅避免了簇頭頻繁更換造成的能量損失，而且提高了整個(gè)網(wǎng)絡(luò)的穩(wěn)定性，從而保障網(wǎng)絡(luò)更持續(xù)長久的工作。

3 仿真結(jié)果

本文以Matlab作為實(shí)驗(yàn)仿真平臺，在區(qū)域?yàn)?00 m×100 m的范圍內(nèi)隨機(jī)部署100個(gè)節(jié)點(diǎn)，基站位置為(175，50)，節(jié)點(diǎn)初始能量為0，5 J。針對網(wǎng)絡(luò)整體平均剩余能量隨時(shí)間的變化趨勢和死亡節(jié)點(diǎn)數(shù)隨時(shí)間的變化趨勢來研究網(wǎng)絡(luò)的生命時(shí)間問題進(jìn)行了仿真分析。

圖2 3種算法的生命時(shí)間

圖2表示隨著時(shí)間的增加3種不同算法整體平均剩余能量的變化，表明了兩個(gè)問題：其一，ELSS算法下整個(gè)網(wǎng)絡(luò)的整體平均剩余能量相較于LEACH協(xié)議和S_LEACH協(xié)議下降趨勢明顯更緩慢，在減少到0之前持續(xù)的時(shí)間更長久；其二，ELSS算法下整個(gè)網(wǎng)絡(luò)的整體平均剩余能量相較于LEACH協(xié)議和S_LEACH協(xié)議下降的趨勢更平緩。從而驗(yàn)證了ELSS算法對延長整個(gè)網(wǎng)絡(luò)生命時(shí)間周期起到了促進(jìn)作用，同時(shí)也保障了整個(gè)無線傳感網(wǎng)絡(luò)工作的穩(wěn)定性。

圖3 3種算法的死亡節(jié)點(diǎn)數(shù)比較

圖3表明ELSS算法下整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)的死亡時(shí)間相對于LEACH協(xié)議和S_LEACH協(xié)議得到有效的延遲。ELSS算法一部分減少了S_LEACH協(xié)議算法中簇頭節(jié)點(diǎn)降為普通節(jié)點(diǎn)所造成的簇頭組能量損失；另一部分又通過能量感知選擇最高能量休眠簇頭來分擔(dān)工作簇頭的工作壓力，保障了簇頭組之間的能量平衡，從而大幅降低簇頭組節(jié)點(diǎn)的死亡概率。兩部分的優(yōu)勢促使了ELSS算法能夠有效保障整個(gè)網(wǎng)絡(luò)持續(xù)工作，從而有效延長了網(wǎng)絡(luò)的生命時(shí)間。

4 結(jié)束語

介紹了LEACH協(xié)議和S_LEACH協(xié)議協(xié)議的工作原理，并針對這兩種算法的不足在其基礎(chǔ)上提出了一種能量感知選擇簇頭的算法-ELSS，該算法通過感知休眠簇頭的能量，選擇能量最多的休眠簇頭替換工作簇頭。ELSS算法與LEACH協(xié)議相比避免了多次分簇造成的能量損失，與S_LEACH協(xié)議相比減少了簇頭傳感器的能量消耗并保障了休眠簇頭傳感器之間的能量平衡。仿真分析表明，ELSS算法的穩(wěn)定性更好，并且能夠在能量有限的前提下更大限度地延長網(wǎng)絡(luò)生命時(shí)間。