基于能耗梯度的無(wú)線傳感器網(wǎng)絡(luò)路由算法*

劉　帥，李正煒，吳元昊，王　斌，楊永健

（1.中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，長(zhǎng)春130033；2.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012）

基于能耗梯度的無(wú)線傳感器網(wǎng)絡(luò)路由算法*

劉帥1*，李正煒1，吳元昊1，王斌1，楊永健2

（1.中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，長(zhǎng)春130033；2.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012）

無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能量有限且較難補(bǔ)給，網(wǎng)絡(luò)生命周期難以保證，這大大影響了其應(yīng)用的場(chǎng)景和范圍。為解決上述問(wèn)題，提出了一種新的路由算法EDROPL，算法通過(guò)將網(wǎng)絡(luò)進(jìn)行區(qū)域劃分，引入能耗梯度概念，采用適當(dāng)?shù)脑u(píng)價(jià)函數(shù)指導(dǎo)簇首節(jié)點(diǎn)的選擇，同時(shí)采用簇首之間層次轉(zhuǎn)發(fā)數(shù)據(jù)等方法優(yōu)化路由。仿真實(shí)驗(yàn)表明，EDROPL相對(duì)于LEACH算法以及LEACH-A算法、HRPNC等其他能耗模型算法能更好的均衡網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)生命周期。

無(wú)線傳感器網(wǎng)絡(luò)；路由；能耗梯度；網(wǎng)絡(luò)生命周期

無(wú)線傳感器網(wǎng)絡(luò)（WSNs）是一種通過(guò)將大量節(jié)點(diǎn)以自組織的方式進(jìn)行連接，節(jié)點(diǎn)之間相互通信，從而實(shí)現(xiàn)信息發(fā)送和采集的目的［1］網(wǎng)絡(luò)結(jié)構(gòu)。由于WSNs的自組織特性［2］，其通常被安排在操作環(huán)境比較惡劣，不方便人為干預(yù)的地點(diǎn)工作［3］。WSNs中的節(jié)點(diǎn)一般由傳感器、處理器和無(wú)線收發(fā)模塊組成，由于WSNs工作環(huán)境的特殊性，其能耗供給方式大多為采用電池提供［4-5］，因此降低網(wǎng)絡(luò)能耗是提高網(wǎng)絡(luò)生命周期的關(guān)鍵。

WSNs的節(jié)點(diǎn)中，無(wú)線收發(fā)模塊會(huì)消耗90%以上的能量，因此采用合適的路由算法優(yōu)化節(jié)點(diǎn)收發(fā)信息時(shí)采用的功率可以最大限度的降低網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)生命周期［6］。

目前主流的路由算法可以分為平面路由算法和層次路由算法［7］。平面路由算法由于其高昂的路由建立和維護(hù)代價(jià)而漸漸地被層次路由算法所替代［8］。最經(jīng)典層次路由算法是由MIT的Heinzelman提出LEACH算法［9］。該算法通過(guò)一定的簇首選舉和入簇策略，建立多個(gè)層次結(jié)構(gòu)，通過(guò)簇間轉(zhuǎn)發(fā)的方式，降低通信能耗。文獻(xiàn)［10］通過(guò)一種非均勻成簇方法（UCA）來(lái)以降低能耗。文獻(xiàn)［3］提出了一種對(duì)節(jié)點(diǎn)進(jìn)行能耗分級(jí)的非均勻分簇算法CHCI，在網(wǎng)絡(luò)生存時(shí)間方面有了一定的提升。文獻(xiàn)［11］采用了抑制低能量節(jié)點(diǎn)的數(shù)據(jù)發(fā)送量，簇內(nèi)可變通信周期等策略，提出了ACPSEB-LEACH算法，該算法可以減少部分節(jié)點(diǎn)的能量消耗。文獻(xiàn)［12］提出的HRPNC算法通過(guò)分層機(jī)制及競(jìng)爭(zhēng)半徑機(jī)制選取簇首，使簇首節(jié)點(diǎn)分布更加合理，能有效均衡節(jié)點(diǎn)的能量消耗。采用能量模型的路由算法中，由劉永超等提出的A-LEACH算法［13］比較有代表性。A-LEACH算法綜合考慮了節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)密集程度在簇首節(jié)點(diǎn)選擇中的分量，在一定程度上提高了網(wǎng)絡(luò)的生命周期。本文主要針對(duì)大部分層次路由算法在均衡能耗［14］和延長(zhǎng)網(wǎng)絡(luò)生命周期的不足，提出了綜合考慮能耗，節(jié)點(diǎn)密度和基站位置的EDROPL算法。

本文提出的EDROPL算法將節(jié)點(diǎn)通信距離和節(jié)點(diǎn)能耗梯度加入到簇首選舉代價(jià)函數(shù)，并在簇首之間采取多跳傳輸方式實(shí)現(xiàn)網(wǎng)絡(luò)通信。能在網(wǎng)絡(luò)能耗，網(wǎng)絡(luò)生命有效周期和吞吐量方面有較好的提高。

1　典型層次路由算法簡(jiǎn)介

1.1LEACH

LEACH是最早被提出的層次路由算法，算法的建簇工作采用以下方式進(jìn)行。在每一輪次開(kāi)始時(shí)，每個(gè)存活的節(jié)點(diǎn)產(chǎn)生一個(gè)（0，1）區(qū)間上的隨機(jī)數(shù)，如果該隨機(jī)數(shù)小于閾值T（n），則節(jié)點(diǎn)n當(dāng)選為簇首節(jié)點(diǎn)。T（n）的計(jì)算方法如公式1.1所示。

其中，r是當(dāng)前輪次，p是網(wǎng)絡(luò)中簇首節(jié)點(diǎn)的比例，G是一個(gè)集合，其中的元素是最近1/p輪次內(nèi)沒(méi)有當(dāng)選過(guò)簇首的節(jié)點(diǎn)。從公式中可以看出，在每一個(gè)1/p輪次之內(nèi)，隨著輪次的增加，T（n）的值越來(lái)越大，則節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率也更大。一旦節(jié)點(diǎn)成為簇首，則在接下來(lái)的1/p輪次之內(nèi)其將不再參與簇首的競(jìng)選。當(dāng)簇首選舉結(jié)束之后，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)自己到簇首節(jié)點(diǎn)的距離采用就近原則加入簇內(nèi)，成簇工作完畢。

LEACH算法的簇首選擇方法在一定程度上保證了網(wǎng)絡(luò)的公平性。使得節(jié)點(diǎn)都相對(duì)均勻的成為簇首，防止了某些節(jié)點(diǎn)多次成為簇首而導(dǎo)致的過(guò)早死亡。但LEACH算法也存在一些不足，主要包括：①穩(wěn)定性比較差，選擇簇首時(shí)采用的隨機(jī)策略，導(dǎo)致每一輪次的簇首數(shù)量變化比較劇烈；②沒(méi)有考慮簇首節(jié)點(diǎn)密度的問(wèn)題，導(dǎo)致可能出現(xiàn)某一區(qū)域簇首節(jié)點(diǎn)聚集或十分稀少的現(xiàn)象；③不能動(dòng)態(tài)調(diào)節(jié)簇首的選擇，某些能量低的節(jié)點(diǎn)在純隨機(jī)的選舉策略下仍然有概率成為簇首［15］。

1.2A-LEACH

A-LEACH算法是一種典型的采用能耗和距離模型的WSNs路由算法。該算法的過(guò)程主要分為以下幾個(gè)階段。

①分區(qū)階段

算法根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)到基站的距離將節(jié)點(diǎn)分入不同的區(qū)域，簇首只在本區(qū)域內(nèi)招募簇內(nèi)成員。

②簇首選舉階段

A-LEACH算法綜合考慮了節(jié)點(diǎn)的剩余能量以及與鄰居節(jié)點(diǎn)的緊密程度，給出了一個(gè)節(jié)點(diǎn)當(dāng)選簇首的概率計(jì)算函數(shù)：

其中，c1，c2是權(quán)重系數(shù)，E（i）是節(jié)點(diǎn)目前輪次的剩余能量，Eave代表所有節(jié)點(diǎn)能量的平均值，Nneigh（i）是節(jié)點(diǎn)的密集程度，nalive是網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)量。每一輪次計(jì)算每個(gè)節(jié)點(diǎn)的P值，選最大的節(jié)點(diǎn)作為簇首，其他節(jié)點(diǎn)按照就近原則選擇自己加入的簇。

③信息傳輸階段

采用簇首接收簇內(nèi)成員消息，進(jìn)行融合操作，之后將融合結(jié)果通過(guò)距離基站更近的節(jié)點(diǎn)轉(zhuǎn)發(fā)的方式，傳輸?shù)交竟?jié)點(diǎn)。

A-LEACH算法創(chuàng)新性地將節(jié)點(diǎn)剩余能量比的概念引入到路由算法之中，用節(jié)點(diǎn)的剩余能量作為選舉簇首時(shí)的重要參數(shù)，在一定程度上保證了節(jié)點(diǎn)之間能耗的公平性，提高了網(wǎng)絡(luò)生存周期。但節(jié)點(diǎn)的剩余能量并不能很好地預(yù)測(cè)該節(jié)點(diǎn)未來(lái)的能耗速度和預(yù)期存活時(shí)間。

1.3HRPNC

文獻(xiàn)［11］提出了一種采用增加分層機(jī)制和競(jìng)爭(zhēng)半徑機(jī)制，從而節(jié)約能耗的層次路由算法。

該算法的主要工作過(guò)程如下：

層次劃分：將整個(gè)網(wǎng)絡(luò)區(qū)域按照距離基站的距離進(jìn)行區(qū)域劃分，將小于d0的區(qū)域劃分為第一區(qū)域，之后按照劃分間隔進(jìn)行其他區(qū)域的劃分。

①計(jì)算簇首數(shù)量

按照一定的百分比為各個(gè)區(qū)域分配一定數(shù)量的簇首。

②計(jì)算競(jìng)爭(zhēng)半徑

采用式（3）計(jì)算出基準(zhǔn)競(jìng)爭(zhēng)半徑。其中Ak是區(qū)域k的面積，mk是該區(qū)域的簇首節(jié)點(diǎn)數(shù)量。再根據(jù)式（4）計(jì)算出每個(gè)節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑。其中ri為節(jié)點(diǎn)與基站的距離，rmin，rmax分別為該層次距離基站的最近和最遠(yuǎn)距離，K1=0.5，K2=2。

③成簇

選擇和LEACH算法相同的簇首候選方法，即根據(jù)式（1）選出候選簇首，之后候選簇首判斷在自己的競(jìng)爭(zhēng)半徑中是否存在其他候選簇首，如果不存在則自己當(dāng)選簇首，其他的節(jié)點(diǎn)按照就近原則加入簇內(nèi)。

HRPNC算法能在一定程度上保證簇首分布的均勻性，提高了路由效率。該算法的局限性在于只考慮了簇首的分布對(duì)能耗的影響，沒(méi)有將能耗速度作為另外的參考標(biāo)準(zhǔn)，使得對(duì)能耗速度控制不足。

2　基于能耗梯度的EDROPL算法

EDROPL算法，本質(zhì)上是一種采用功率控制手段達(dá)到網(wǎng)絡(luò)拓?fù)浣⒌姆椒?。其要求無(wú)線傳感器網(wǎng)絡(luò)具備以下幾個(gè)特點(diǎn)：①由相同的傳感器節(jié)點(diǎn)組成網(wǎng)絡(luò)（同構(gòu)性）；②傳感器節(jié)點(diǎn)擁有自己的位置信息；③網(wǎng)絡(luò)中存在唯一的基站；④網(wǎng)絡(luò)中節(jié)點(diǎn)擁有唯一標(biāo)識(shí)號(hào)。

2.1區(qū)域劃分

首先根據(jù)各個(gè)節(jié)點(diǎn)到基站的距離，將整個(gè)網(wǎng)絡(luò)區(qū)域進(jìn)行劃分。劃分方法為基站向整個(gè)網(wǎng)絡(luò)廣播自己的位置信息和區(qū)域劃分策略；該劃分策略的主要參數(shù)是節(jié)點(diǎn)到基站的距離以及與基站之間的相對(duì)位置關(guān)系。節(jié)點(diǎn)收到該廣播信息之后，通過(guò)自己的位置和基站的位置，計(jì)算自己與基站之間的距離，同時(shí)計(jì)算自己相對(duì)于基站的方位，并根據(jù)廣播中的區(qū)域劃分策略將自己歸入固定的區(qū)域之內(nèi)，保存區(qū)域信息。分區(qū)效果如圖1所示。

從圖1中的區(qū)域劃分方法可以看出EDROPL算法和A-LEACH算法在網(wǎng)絡(luò)分區(qū)部分的處理方式基本相同。

圖1　區(qū)域劃分結(jié)果

2.2簇首選舉和節(jié)點(diǎn)入簇

簇首的選舉工作在各個(gè)區(qū)域內(nèi)同時(shí)進(jìn)行。首先引入選舉簇首評(píng)價(jià)函數(shù)，如式（5）所示。

其中，α，β，γ為權(quán)重系數(shù)，Edrop是節(jié)點(diǎn)能耗梯度值；D是節(jié)點(diǎn)密度，ls是節(jié)點(diǎn)到基站的距離評(píng)價(jià)值。Edrop的計(jì)算方法如公式（6）所示。

其中，EΔr代表第r輪次開(kāi)始之前和第r-1輪次開(kāi)始之前，節(jié)點(diǎn)的剩余能量的差，Er代表當(dāng)前第r輪次開(kāi)始之前，網(wǎng)絡(luò)中節(jié)點(diǎn)的總剩余能量，k用來(lái)控制梯度精度，成為能耗梯度系數(shù)，nalives代表當(dāng)前網(wǎng)絡(luò)中剩余的存活節(jié)點(diǎn)的數(shù)量。因此Edrop就代表了節(jié)點(diǎn)最近k輪次的平均能耗速度，相對(duì)于整個(gè)生存周期而言，它可以稱為r輪次附近的瞬時(shí)能耗速度，反映了當(dāng)前節(jié)點(diǎn)的存活時(shí)間的期望。

D的計(jì)算方法如式（7）所示。

其中dij是節(jié)點(diǎn)i與在鄰域Δ為范圍內(nèi)的鄰居節(jié)點(diǎn)j的距離，A是網(wǎng)絡(luò)區(qū)域的規(guī)模。D體現(xiàn)了節(jié)點(diǎn)i與其鄰居節(jié)點(diǎn)在位置上的緊密程度，其值越小代表與鄰居節(jié)點(diǎn)越緊密。

ls的計(jì)算方法如式（8）所示。

其中Dis是節(jié)點(diǎn)i到達(dá)基站的距離，A是網(wǎng)絡(luò)區(qū)域的規(guī)模。ls體現(xiàn)了節(jié)點(diǎn)i到達(dá)基站的距離評(píng)價(jià)。

所有節(jié)點(diǎn)根據(jù)自己的當(dāng)前信息，利用式（15）來(lái)計(jì)算自己的評(píng)價(jià)函數(shù)值Wi，并生成一個(gè)四元組，其中Si為i節(jié)點(diǎn)所屬的區(qū)域編號(hào)，idi是節(jié)點(diǎn)編號(hào)，posi是節(jié)點(diǎn)的位置信息。當(dāng)節(jié)點(diǎn)j接收到來(lái)自于節(jié)點(diǎn)i的四元組信息時(shí)，首先通過(guò)Si判斷i節(jié)點(diǎn)是否與自己屬于同一個(gè)區(qū)域，如果Si≠Sj，則j節(jié)點(diǎn)將此消息忽略；網(wǎng)絡(luò)中所有節(jié)點(diǎn)都維護(hù)一個(gè)評(píng)價(jià)函數(shù)排序表T，如果Si=Sj，則j節(jié)點(diǎn)將i節(jié)點(diǎn)視為候選簇首，并將idi放入表T內(nèi)，其位置滿足以下要求：Wi的值大于等于排在idi之前所有節(jié)點(diǎn)的W值，同時(shí)Wi的值小于等于排在idi之后所有節(jié)點(diǎn)的W值。按照這種方法，當(dāng)所有節(jié)點(diǎn)完成四元組的發(fā)送和接收之后，任意一個(gè)節(jié)點(diǎn)都保存著與其屬于同一個(gè)區(qū)域的鄰居節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值和排序結(jié)果。各節(jié)點(diǎn)按照排序結(jié)果決定自己是否成為簇首節(jié)點(diǎn)。要求任意兩個(gè)簇首之間的距離不能過(guò)近，否則容易出現(xiàn)過(guò)于集中的簇，導(dǎo)致網(wǎng)絡(luò)資源浪費(fèi)。

選舉結(jié)束之后，當(dāng)選為簇首的節(jié)點(diǎn)向自己的鄰域內(nèi)廣播成為簇首的消息，各節(jié)點(diǎn)根據(jù)最近原則選擇入簇。

2.3消息傳輸

簇建立結(jié)束之后，簇首要選擇自己發(fā)送消息的目的節(jié)點(diǎn)，即下一跳簇首節(jié)點(diǎn)。要求簇首的下一跳節(jié)點(diǎn)必須處于編號(hào)更小的區(qū)域之內(nèi)，即距離基站更近，當(dāng)前簇首節(jié)點(diǎn)只考慮距離自己最近的更近區(qū)域的簇首作為下一跳節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)已經(jīng)處于距基站最近的區(qū)域時(shí)，下一跳節(jié)點(diǎn)就是基站。這里為了減少消息發(fā)送數(shù)，規(guī)定，若當(dāng)前節(jié)點(diǎn)到基站距離d＜d0（見(jiàn)式（9）），則直接發(fā)送費(fèi)基站，否則采用多跳方式發(fā)送。

3　仿真實(shí)驗(yàn)

本文采用Matlab仿真軟件對(duì)EDROPL與第1小節(jié)中介紹的LEACH、A-LEACH和HRPNC算法進(jìn)行仿真對(duì)比。設(shè)計(jì)的網(wǎng)絡(luò)區(qū)域?yàn)?00 m×100 m的矩形區(qū)域，表1給出了該仿真實(shí)驗(yàn)的具體參數(shù)。

表1　仿真實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)中的通信能耗模型采用公式（9）所示。

式（5）中取α=0.7，β=0.2，γ=0.1，這樣做的目的是保證能耗梯度分量占據(jù)主要作用，網(wǎng)絡(luò)規(guī)模A采用網(wǎng)絡(luò)區(qū)域邊長(zhǎng)衡量。在實(shí)際應(yīng)用中，我們也建議將α的值選取為三個(gè)因子中最大的，能耗梯度是指導(dǎo)路由的最關(guān)鍵因素，因子β，γ的選擇依賴于原始網(wǎng)絡(luò)的狀態(tài)，若網(wǎng)絡(luò)中存在較多的分散的節(jié)點(diǎn)，則取β稍大些，以更容易推薦緊密程度高的節(jié)點(diǎn)，而當(dāng)網(wǎng)絡(luò)中存在較多的距離基站節(jié)點(diǎn)超過(guò)d0的節(jié)點(diǎn)時(shí)，則取γ更大一些，以更容易選取距離基站更近的節(jié)點(diǎn)作為簇首。

實(shí)驗(yàn)將本文提出的 EDROPL算法和經(jīng)典LEACH算法以及經(jīng)典的能耗拓?fù)渌惴ˋ-LEACH、HRPNC算法進(jìn)行對(duì)比，共進(jìn)行1900輪次的仿真。主要對(duì)比了各個(gè)算法在保證網(wǎng)絡(luò)拓?fù)浞€(wěn)定性、提高生命周期和降低網(wǎng)絡(luò)能耗等方面的表現(xiàn)。

圖2中對(duì)比了A-LEACH、HRPNC和EDROPL算法在網(wǎng)絡(luò)拓?fù)浞€(wěn)定方面的表現(xiàn)，當(dāng)各個(gè)節(jié)點(diǎn)有比較均衡的的機(jī)會(huì)成為簇首節(jié)點(diǎn)時(shí)，整個(gè)網(wǎng)絡(luò)的穩(wěn)定性會(huì)相對(duì)較好，從圖2可以看出，在A-LEACH和HRPNC算法中，由于網(wǎng)絡(luò)中存在比較明顯的集中分布現(xiàn)象，導(dǎo)致某些節(jié)點(diǎn)鄰域內(nèi)的節(jié)點(diǎn)總數(shù)一直保持較高的水平，因此導(dǎo)致這些節(jié)點(diǎn)過(guò)多的擔(dān)任了簇首工作，同時(shí)存在一些節(jié)點(diǎn)幾乎沒(méi)有當(dāng)選過(guò)簇首。EDROPL算法由于引入了能耗梯度的分量，能保證節(jié)點(diǎn)都有較為均衡的機(jī)會(huì)擔(dān)任簇首，某些地理位置相對(duì)集中的節(jié)點(diǎn)，會(huì)導(dǎo)致前期更多地?fù)?dān)任簇首工作，同時(shí)也因此導(dǎo)致能耗下降速度也更快，逐漸降低擔(dān)任簇首的可能性。

圖2　節(jié)點(diǎn)擔(dān)任簇首次數(shù)

圖3是對(duì)4種算法在各個(gè)輪次結(jié)束之后，網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)量的對(duì)比結(jié)果。LEACH算法在第803輪次出現(xiàn)首個(gè)死亡節(jié)點(diǎn)，A-LEACH算法在623輪出現(xiàn)首個(gè)死亡節(jié)點(diǎn)，HRPNC算法在630輪出現(xiàn)首個(gè)死亡節(jié)點(diǎn)，EDROPL算法的首個(gè)死亡節(jié)點(diǎn)出現(xiàn)在716輪。當(dāng)出現(xiàn)首個(gè)死亡節(jié)點(diǎn)之后，LEACH算法的死亡節(jié)點(diǎn)數(shù)會(huì)快速增加，存活節(jié)點(diǎn)數(shù)下降比較迅速，A-LEACH 和HRPNC算法的節(jié)點(diǎn)死亡速度要更低一些，但其在1 200和1 180輪次之前的存活節(jié)點(diǎn)數(shù)量都少于LEACH算法，當(dāng)?shù)竭_(dá)約 1 600和 1 800輪次時(shí)，A-LEACH和 HRPNC算法的節(jié)點(diǎn)全部死亡。EDROPL算法表現(xiàn)出了更低的死亡速度，且首個(gè)死亡節(jié)點(diǎn)較其他兩種能耗算法出現(xiàn)的更晚，這是因?yàn)閷?duì)能耗速度下降的估計(jì)，可以有效地指導(dǎo)簇首節(jié)點(diǎn)的選擇，A-LEACH算法僅僅對(duì)節(jié)點(diǎn)的剩余能量進(jìn)行評(píng)價(jià)，能耗下降速度相比剩余能量更能反映出節(jié)點(diǎn)的預(yù)計(jì)的生存時(shí)間。同時(shí)，當(dāng)仿真輪次到達(dá)1 100輪時(shí)，EDROPL算法的節(jié)點(diǎn)存活數(shù)量較LEACH算法更多，并保持了更低的死亡速度。對(duì)于無(wú)線傳感器網(wǎng)絡(luò)而言，保證一定量的冗余節(jié)點(diǎn)是必要的，當(dāng)節(jié)點(diǎn)存活數(shù)高于某一數(shù)值（一般為40%）時(shí)，網(wǎng)絡(luò)就可以正常工作。圖中可以看出，采用LEACH、A-LEACH和HRPNC算法時(shí)，當(dāng)仿真輪次到達(dá)1 200輪時(shí)，存活節(jié)點(diǎn)數(shù)量減少到40個(gè)，而EDROPL算法運(yùn)行至1 500輪次時(shí)，存活節(jié)點(diǎn)數(shù)減小到40個(gè)。所以，EDROPL較其他三種方法相比可以使網(wǎng)絡(luò)保持更長(zhǎng)的正常工作時(shí)間。

圖3　網(wǎng)絡(luò)節(jié)點(diǎn)存活數(shù)量

圖4是4種算法在網(wǎng)絡(luò)能量方面的表現(xiàn)。由于在仿真初期，節(jié)點(diǎn)剩余能量相差不大，速度下降經(jīng)驗(yàn)值不足，導(dǎo)致各個(gè)算法在前450輪次的能耗表現(xiàn)基本相同，同時(shí)由于A-LEACH算法更多地依賴距離分量，導(dǎo)致前期過(guò)多節(jié)點(diǎn)多次擔(dān)任簇首，能耗下降速度更高一些。當(dāng)輪次在500輪之后，本文提出的EDROPL算法表現(xiàn)出使用能耗梯度經(jīng)驗(yàn)值來(lái)選舉簇首的優(yōu)越性，其下降曲率逐漸低于LEACH和A-LEACH算法，在600輪之后，算法逐漸優(yōu)于HRPNC。該算法能更好的保護(hù)估計(jì)剩余時(shí)間更少的節(jié)點(diǎn)。從圖3和圖4可以看出，當(dāng)?shù)竭_(dá)1 500輪次時(shí)，LEACH和A-LEACH算法中的節(jié)點(diǎn)基本全部死亡，而EDROPL算法中還38個(gè)節(jié)點(diǎn)存活，在1680輪次時(shí)HRPNC算法節(jié)點(diǎn)全部死亡，EDROPL仍然存活12個(gè)節(jié)點(diǎn)。

圖4　網(wǎng)絡(luò)剩余總能量

圖5為4種算法中，基站收到的消息數(shù)目?？梢钥闯觯琇EACH和A-LEACH算法在仿真至1 100輪次左右時(shí)開(kāi)始出現(xiàn)數(shù)據(jù)包下降現(xiàn)象，說(shuō)明網(wǎng)絡(luò)中的存活節(jié)點(diǎn)已經(jīng)不多，進(jìn)而導(dǎo)致簇首節(jié)點(diǎn)減少，HRPNC在1 500輪次時(shí)消息數(shù)量開(kāi)始明顯減少，而EDROPL算法的表現(xiàn)比較好，最后發(fā)送的數(shù)據(jù)總量約為前兩種算法的1.8倍，HRPNC的1.3倍，表明其可以有較好的網(wǎng)絡(luò)吞吐量的保證。

圖5　基站收到的消息數(shù)

圖6是EDROPL算法運(yùn)行至1 500輪次時(shí)，網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的剩余能量直方圖表示?？梢钥闯?，網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)能量相差不多，EDROPL很好的做到了能量平均。在此之后，EDROPL又繼續(xù)運(yùn)行了大概400輪次，直到所有節(jié)點(diǎn)死亡。

圖6　EDROPL算法在1500輪次時(shí)節(jié)點(diǎn)的剩余能量

最后我們給出式（6）中的能耗精度控制系數(shù)k的取值與節(jié)點(diǎn)存活率的關(guān)系。圖7是當(dāng)仿真運(yùn)行至1 500輪次時(shí)的情況。可以看到，k的取值會(huì)比較大的影響到節(jié)點(diǎn)的存活率，取k=4時(shí)，存活率達(dá)到最大值，此時(shí)網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)為38個(gè)，而其他取值，無(wú)論大于4還是小于4，存活數(shù)都更低一些。這是因?yàn)?，k值直接決定了采用的能耗梯度的精度，當(dāng)k值較小時(shí)，式（6）可以代表此時(shí)瞬時(shí)的能耗速度，但采樣較少，代表性較低，而當(dāng)k值較大時(shí)，又降低了瞬時(shí)性的意義，使得式（6）的值趨于平均化，同樣降低了能耗速度的代表性。

圖7　能耗梯度系數(shù)k與存活節(jié)點(diǎn)數(shù)的關(guān)系

4　總結(jié)

對(duì)于節(jié)點(diǎn)資源有限的無(wú)線傳感器網(wǎng)絡(luò)，如何降低能耗是一個(gè)重要問(wèn)題。本文提出了一種采用能耗梯度作為評(píng)價(jià)參數(shù)的路由算法EDROPL。通過(guò)仿真實(shí)驗(yàn)的方式證明了EDROPL算法的可行性，由于引入了能耗梯度的計(jì)算，為分簇算法提供的能耗經(jīng)驗(yàn)值可以很好的均衡網(wǎng)絡(luò)能量。相比經(jīng)典的LEACH算法、改進(jìn)的A-LEACH和HRPNC算法，EDROPL算法在保證網(wǎng)絡(luò)拓?fù)浞€(wěn)定，延長(zhǎng)網(wǎng)絡(luò)生命周期，降低和均衡節(jié)點(diǎn)能耗和提高網(wǎng)絡(luò)吞吐量等方面有明顯的提升。

［1］洪鋒，褚紅偉，金宗科，等.無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)最新進(jìn)展綜述［J］.計(jì)算機(jī)研究與發(fā)展，2010，47：81-87.

［2］宋立新，戴赫.基于蟻群算法的WSN路由協(xié)議研究［J］.哈爾濱理工大學(xué)學(xué)報(bào)，2014，16（6）：88-92.

［3］康琳，董增壽.基于簇頭分級(jí)的改進(jìn)非均勻分簇算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（12）：1841-1844.

［4］張偉偉.無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂撇呗匝芯浚跠］.曲阜師范大學(xué)，2009.

［5］王科強(qiáng)，張彥波，項(xiàng)伍鋒，等.無(wú)線傳感器網(wǎng)絡(luò)分層帶寬自適應(yīng)路由協(xié)議［J］.傳感器與微系統(tǒng)，2014，33（3）：132-134.

［6］李芳芳，王靖.一種基于LEACH協(xié)議的無(wú)線傳感器網(wǎng)絡(luò)路由算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25（10）：1445-1452.

［7］白鳳娥，李環(huán).能量均衡的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇算法的研究［J］.計(jì)算機(jī)與數(shù)字工程，2012，40（1）：28-31

［8］Heinzelman W B，Chandrakasan A P.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］. IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［9］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Sensor Networks［C］// Proceedings of 33th IEEE Annual Hawaii International Conference on System Sciences，2000：10.

［10］Yuan Huiyong，Liu Yongyi，Yu Jiaping.A New Energy-Efficient Unequal Clustering Algorithm for Wireless Sensor Networks［C］// IEEE Conference Proceedings，2011：431-434.

［11］葉繼華，王文，江愛(ài)文，等.一種基于LEACH的異構(gòu)WSN能量均衡成簇協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2015，28（12）：1853-1860.

［12］黃廷輝，伊凱，崔更申，等.基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)分層路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用，2016，36（1）：66-71.

［13］劉永超，張?jiān)孪?，繆旻，等.基于能量和距離的分區(qū)域選擇簇首WSNs路由算法［J］.傳感器與微系統(tǒng)，2015，34（1）：124-127.

［14］Y.Jennifer，M.Biswanath，G.Dipak.Wireless Sensor Network Survey.Computer Networks，2008（52）：2292-2330.

［15］孫建偉，王紹辰，賈軍營(yíng)，等.一種針對(duì)無(wú)線傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進(jìn)算法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24（12）：186-190.

劉帥（1988-），男，吉林長(zhǎng)春人，初級(jí)研究員，碩士，現(xiàn)主要從事無(wú)線傳感器網(wǎng)絡(luò)路由算法，PSN網(wǎng)絡(luò)路由算法等方向研究，149390771@qq.com；

李正煒（1988-），男，福建龍巖人，博士研究生，主要從事無(wú)線傳感器網(wǎng)絡(luò)等方面的研究；

吳元昊（1977-），男，吉林長(zhǎng)春人，副研究員，博士，主要從事無(wú)線傳感器網(wǎng)絡(luò)，圖像處理算法等方面的研究。

Routing Algorithm for Wireless Sensor Network Based on Energy Consumption Gradient*

LIU Shuai1*，LI Zhengwei1，WU Yuanhao1，WANG Bin1，YANG Yongjian2
（1.Changchun Institute of Optics，F(xiàn)ine Mechanics and Physics，Chinese Academy of Sciences，Changchun 130033 China；2.College of Computer Science and Technology，Jilin University，Changchun 130012，China）

The energy of the nodes in wireless sensor network is limited and difficult to be supplied，so the network life circle is hard to be ensured，which has a negative effect on being used in so fields and ranges.To overcome the disadvantages above，a new routing algorithm called EDROPL is proposed.This algorithm optimize routing by dividing sections，importing the concept of energy gradient，choosing the cluster heads by some appropriate evaluation function，and transmitting packages between cluster heads.The simulation result shows that EDROPL has a better performance in balancing the network energy consumption and improving the network life circle comparing with LEACH，LEACH-A and HRPNC energy based algorithm.

wireless sensor network；routing；energy consumption gradient；network life circle

TP393

A

1004-1699（2016）08-1247-06

EEACC：6150P10.3969/j.issn.1004-1699.2016.08.021

項(xiàng)目來(lái)源：國(guó)家高技術(shù)研究發(fā)展計(jì)劃（863計(jì)劃）項(xiàng)目（2013AA8083042）；國(guó)家自然科學(xué)基金項(xiàng)目（61272412）；教育部博士項(xiàng)目基金項(xiàng)目（20120061110044）；吉林省科技發(fā)展計(jì)劃項(xiàng)目（20120303）

2016-01-20修改日期：2016-03-30