李志明 唐永中

(河西學(xué)院信息技術(shù)中心 甘肅 張掖 734000)

基于差分算法的無線傳感器網(wǎng)絡(luò)路由分簇協(xié)議

李志明 唐永中

(河西學(xué)院信息技術(shù)中心 甘肅 張掖 734000)

針對(duì)異構(gòu)無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議存在節(jié)點(diǎn)能耗不均衡問題，提出一種基于差分進(jìn)化算法的路由協(xié)議及基于節(jié)點(diǎn)能耗的分簇協(xié)議。該協(xié)議首先以最大化網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的最小生存周期為目標(biāo)，建立函數(shù)優(yōu)化模型，并采用差分進(jìn)化算法對(duì)其進(jìn)行優(yōu)化，從而延長(zhǎng)網(wǎng)絡(luò)整體的生存周期；然后根據(jù)節(jié)點(diǎn)通信列表中的簇頭數(shù)目進(jìn)行分簇，將節(jié)點(diǎn)分配給能耗因子較低的簇頭，以達(dá)到均衡網(wǎng)絡(luò)能耗的目的，延長(zhǎng)普通節(jié)點(diǎn)的生存周期。仿真結(jié)果表明，基于差分的路由分簇協(xié)議能有效均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，顯著延長(zhǎng)網(wǎng)絡(luò)的生存周期并提高網(wǎng)絡(luò)能量利用率。

異構(gòu)無線傳感器網(wǎng)絡(luò) 路由 分簇 差分算法

0 引 言

無線傳感器網(wǎng)絡(luò)受到了國(guó)內(nèi)外學(xué)者們的廣泛關(guān)注，它可以被應(yīng)用在環(huán)境監(jiān)測(cè)、醫(yī)療等領(lǐng)域[1]。然而由于傳感節(jié)點(diǎn)的能量有限，直接限制了網(wǎng)絡(luò)的工作時(shí)間。尤其在戰(zhàn)爭(zhēng)、森林等復(fù)雜環(huán)境里，節(jié)點(diǎn)很難被訪問、更換或充電。因此，對(duì)無線傳感器網(wǎng)絡(luò)來說，最大化網(wǎng)絡(luò)的工作時(shí)間是非常關(guān)鍵的問題。

為降低節(jié)點(diǎn)通信中的網(wǎng)絡(luò)能耗，廣泛使用的一種策略是分簇[2]，即網(wǎng)絡(luò)中的節(jié)點(diǎn)被組織分配到特定數(shù)量的獨(dú)立區(qū)域內(nèi)，每個(gè)區(qū)域選出一個(gè)負(fù)責(zé)接收、融合和轉(zhuǎn)發(fā)本區(qū)間內(nèi)的節(jié)點(diǎn)監(jiān)測(cè)信息的簇頭，每個(gè)節(jié)點(diǎn)只與一個(gè)簇頭連接，簇頭將融合后的信息通過單跳或多跳的方式傳輸給基站。如文獻(xiàn)[3]提出LEACH策略，通過周期性的選取簇頭的方式以平衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗。然而由于節(jié)點(diǎn)攜帶能量較低，充當(dāng)簇頭的節(jié)點(diǎn)會(huì)較快地耗費(fèi)掉自身能量，且頻繁更換簇頭有需要重新設(shè)計(jì)簇頭節(jié)點(diǎn)的路由通信鏈路，這會(huì)為網(wǎng)絡(luò)帶來較大的通信開銷。對(duì)此，文獻(xiàn)[4]提出了一種改進(jìn)策略PEGASIS，該算法相比于LEACH雖能在一定程度上延長(zhǎng)網(wǎng)絡(luò)生存周期，但是它需要對(duì)網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)拓?fù)湔{(diào)整，如果網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較多，則網(wǎng)絡(luò)延遲將會(huì)相當(dāng)大，因此該算法不適合于大規(guī)模傳感網(wǎng)絡(luò)。

為進(jìn)一步解決網(wǎng)絡(luò)生存周期較低的問題，文獻(xiàn)[5-6]采用向網(wǎng)絡(luò)中布撒高能節(jié)點(diǎn)充當(dāng)簇頭節(jié)點(diǎn)，以延長(zhǎng)網(wǎng)絡(luò)生存周期。 這種方式相比于同構(gòu)網(wǎng)絡(luò)雖然較大程度的延長(zhǎng)了網(wǎng)絡(luò)壽命，但由于簇頭節(jié)點(diǎn)能耗較大，因此網(wǎng)絡(luò)壽命仍然面臨著能耗的限制，因此采用合理的路由拓?fù)浣Y(jié)構(gòu)和均衡的分簇算法對(duì)網(wǎng)絡(luò)顯得尤為重要，對(duì)此文獻(xiàn)[7]提出GLBCA算法；文獻(xiàn)[8]提出基于GA的路由分簇算法；文獻(xiàn)[9]提出的GAR算法。這三種算法雖然在一定程度上優(yōu)化了拓?fù)浣Y(jié)構(gòu)延長(zhǎng)了網(wǎng)絡(luò)生存周期，然而都沒有從節(jié)點(diǎn)的生存周期這一根本目標(biāo)出發(fā)對(duì)網(wǎng)絡(luò)進(jìn)行優(yōu)化。

基于以上分析，為降低節(jié)點(diǎn)在通信中的能耗、延長(zhǎng)網(wǎng)絡(luò)生存周期，本文結(jié)合差分算法[9]較好的優(yōu)化性能，提出了基于差分的路由分簇算法。首先以最大化最小簇頭節(jié)點(diǎn)的生存周期為目標(biāo)，采用差分算法對(duì)其進(jìn)行優(yōu)化，以盡量延長(zhǎng)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的最短生存周期；然后根據(jù)節(jié)點(diǎn)的能耗，建立了能耗因子，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行分簇時(shí)，選擇能耗因子最小，也即能最好均衡普通節(jié)點(diǎn)和高能節(jié)點(diǎn)能耗的簇頭。實(shí)驗(yàn)表明，本文算法能夠有效的均衡網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)生存周期。

1 能耗模型

本文采用LEACH提出的能量模型[10]。假設(shè)發(fā)送端能耗包括信號(hào)處理和功率放大兩個(gè)部分，接收端能耗為信號(hào)處理和數(shù)據(jù)融合。則根據(jù)無線通信理論，兩個(gè)距離為d的傳感器節(jié)點(diǎn)之間發(fā)送和接受lbit數(shù)據(jù)時(shí)，發(fā)送端消耗的能量為:

(1)

其中，d0為判決閾值，εfsd2和εmpd4是發(fā)送每比特?cái)?shù)據(jù)放大器的能量消耗，Eelec是每比特?cái)?shù)據(jù)在發(fā)送電路和接收電路消耗的能量。節(jié)點(diǎn)接收l比特?cái)?shù)據(jù)時(shí)的能量消耗如式(2)所示。

ER(l)=lEelec

(2)

2 基于DE的路由算法

對(duì)異構(gòu)無線傳感器網(wǎng)絡(luò)，由于受能量的限制，因此必須設(shè)計(jì)合理的拓?fù)浣Y(jié)構(gòu)降低節(jié)點(diǎn)能耗以延長(zhǎng)網(wǎng)絡(luò)生命周期，對(duì)此本文提出了基于DE算法的路由算法以及基于簇頭節(jié)點(diǎn)能耗的分簇算法，距離過程描述如下。

2.1 基于差分的路由算法

假設(shè)網(wǎng)絡(luò)中的簇頭個(gè)數(shù)為5，當(dāng)簇頭gi與簇頭gj的距離滿足式(3)-式(4)，則說明兩個(gè)簇頭可進(jìn)行通信且簇頭gj比gi更靠近基站，因此將gj存入gi的通信列表中。

dis(gi,gj)

(3)

dis(gj,BS)

(4)

則簇頭節(jié)點(diǎn)的可通信列表如表1所示。

表1 簇頭節(jié)點(diǎn)通信列表

則種群中的粒子Xi,d表示粒子i的第d個(gè)簇頭在選擇下一跳簇頭時(shí)的概率值，假設(shè)粒子i的初始化結(jié)果為[0.54,0.36,0.11,0.36,0.37]，則通過計(jì)算可得到網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的連接列表，具體如表2所示。

表2 簇頭選擇下一跳列表

當(dāng)采用差分算法對(duì)簇頭節(jié)點(diǎn)的通信鏈路進(jìn)行規(guī)劃時(shí)，需要為算法設(shè)定目標(biāo)函數(shù)，因?yàn)楫悩?gòu)無線傳感器網(wǎng)絡(luò)首要考慮的因素是網(wǎng)絡(luò)生存周期，而簇頭節(jié)點(diǎn)不僅要接收轉(zhuǎn)發(fā)其他簇頭的信息包，還要接收轉(zhuǎn)發(fā)本簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)信息，因此簇頭節(jié)點(diǎn)的能量消耗較大。所以簇頭節(jié)點(diǎn)的工作時(shí)間，決定了傳感網(wǎng)絡(luò)的監(jiān)測(cè)效果，對(duì)此，本文將最大化簇頭節(jié)點(diǎn)的最短生命周期作為算法的目標(biāo)函數(shù)，具體如式(5)所示。

f=Max(min{(lifetime_gi)|?i,1≤i≤D})

(5)

其中，lifetime_gi表示簇頭節(jié)點(diǎn)gi在不考慮接收融合簇內(nèi)節(jié)點(diǎn)時(shí)的生存周期。則簇頭節(jié)點(diǎn)的網(wǎng)絡(luò)生存周期如式(6)所示。

lifetime_gi=E/(ER×NIN(gi)+(NIN(gi)+1)×ET(gi,NextHop(gi)))

(6)

其中，E表示簇頭節(jié)點(diǎn)的總能量；NIN(gi)表示簇頭gi接收到的來自其他簇頭的數(shù)據(jù)包的個(gè)；(gi,NextHop(gi))表示簇頭gi與它下一跳簇頭的距離。

2.2 基于能量的分簇算法

由式(1)可知，普通節(jié)點(diǎn)與其簇頭節(jié)點(diǎn)通信距離的不同，則在每輪通信中的能耗不同，也即具有不同的網(wǎng)絡(luò)周期；另外，簇頭節(jié)點(diǎn)接收和融合本簇內(nèi)節(jié)點(diǎn)時(shí)也需增加一定的能耗，且隨著簇內(nèi)節(jié)點(diǎn)數(shù)目的增多，簇頭節(jié)點(diǎn)的能耗壓力會(huì)逐漸增大。因此，為了使普通節(jié)點(diǎn)和高能節(jié)點(diǎn)的生存周期都達(dá)到最大，本文提出基于簇頭節(jié)點(diǎn)能耗的分簇算法，具體描述如下。

1) 根據(jù)普通節(jié)點(diǎn)的位置及它的通信距離得到每個(gè)普通節(jié)點(diǎn)可連接簇頭的通信列表；

2) 以列表中含有簇頭數(shù)目的多少為順序?qū)ζ胀ü?jié)點(diǎn)進(jìn)行分簇，節(jié)點(diǎn)可連接的簇頭數(shù)越少，則可選擇簇頭的機(jī)會(huì)就越少，因此從連接矩陣較小的普通節(jié)點(diǎn)開始分簇；

3) 分簇時(shí)，要兼顧普通節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的網(wǎng)絡(luò)生存周期，也即兼顧普通節(jié)點(diǎn)和簇頭節(jié)點(diǎn)在每輪通信中的能耗情況。當(dāng)將一個(gè)節(jié)點(diǎn)i分配給簇頭k時(shí)，一方面簇頭節(jié)點(diǎn)增加了接收和融合的能耗，另一方面節(jié)點(diǎn)Si的發(fā)送距離是基于與簇頭gk的距離計(jì)算的，因此對(duì)監(jiān)測(cè)節(jié)點(diǎn)來說，其可連接簇頭矩陣中必然存在一個(gè)能較好均衡節(jié)點(diǎn)能耗與簇頭能耗的簇頭節(jié)點(diǎn)，則將節(jié)點(diǎn)連接到該簇頭上。具體的衡量節(jié)點(diǎn)和簇頭能耗的能耗因子如式(7)所示：

lk=αEgk+βE(sk,gk)

(7)

其中Egk表示節(jié)點(diǎn)si的可連接簇頭列表中第gk個(gè)簇頭的總能耗；E(si,gk)表示將節(jié)點(diǎn)si分配給簇頭gk時(shí)的傳輸能耗；α和β表示普通節(jié)點(diǎn)生存周期和簇頭節(jié)點(diǎn)生存周期的權(quán)重因子。因?yàn)榇仡^節(jié)點(diǎn)要接收轉(zhuǎn)發(fā)其它節(jié)點(diǎn)發(fā)來的信息，因此相比于普通節(jié)點(diǎn)，簇頭節(jié)點(diǎn)的生存周期應(yīng)受到更多的關(guān)注，當(dāng)計(jì)算完節(jié)點(diǎn)si與其矩陣中的簇頭gk之間的能耗因子后，將節(jié)點(diǎn)連接到能耗因子最小的簇頭上。通過實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)α取值為0.8、β取值為0.2時(shí)，得到的實(shí)驗(yàn)效果較好。

2.3 基于DE的路由分簇算法步驟

設(shè)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的個(gè)數(shù)為D，種群規(guī)模為N，則基于差分的路由分簇算法的具體操作步驟如下：

1) 向網(wǎng)絡(luò)中布撒傳感節(jié)點(diǎn)，得到每個(gè)節(jié)點(diǎn)的位置坐標(biāo)；

2) 對(duì)比通信距離，得到每個(gè)簇頭的節(jié)點(diǎn)的可連接路由列表；

3) 對(duì)比通信距離，得到每個(gè)普通節(jié)點(diǎn)的可連接簇頭列表；

4) 種群初始化，采用差分算法對(duì)最大化最小簇頭生存周期進(jìn)行優(yōu)化；

5) 根據(jù)差分算法得到的最優(yōu)值，得到路由通信列表并得到此時(shí)每個(gè)簇頭節(jié)點(diǎn)在每輪通信中的能耗；

6) 對(duì)每個(gè)普通節(jié)點(diǎn)，按照其簇頭集合的規(guī)模并通過比較能耗因子將節(jié)點(diǎn)進(jìn)行分簇，且每個(gè)普通節(jié)點(diǎn)完成分簇后，更新簇頭節(jié)點(diǎn)的能耗值。

3 實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文算法的有效性和先進(jìn)性，選擇了目前針對(duì)異構(gòu)無線傳感器網(wǎng)絡(luò)優(yōu)化效果較好的GLBCA、GA和GAR等算法，在不同基站位置、布撒不同比例的普通節(jié)點(diǎn)和高能節(jié)點(diǎn)等情況下進(jìn)行對(duì)比驗(yàn)證本文算法的性能。實(shí)驗(yàn)中的相關(guān)參數(shù)如表3所示。三個(gè)算法中的參數(shù)采用相關(guān)文獻(xiàn)給出的數(shù)值進(jìn)行設(shè)置。每組實(shí)驗(yàn)保證初始的節(jié)點(diǎn)布撒場(chǎng)景相同。

表3 參數(shù)設(shè)置

3.1 路由算法有效性驗(yàn)證

為驗(yàn)證本文提出的基于差分的路由算法的有效性，分別與GLBCA、GA和GAR進(jìn)行對(duì)比，具體如圖1所示。其中，圖1為基站位置在(250,250)時(shí)，向網(wǎng)絡(luò)中布撒50個(gè)高能節(jié)點(diǎn)時(shí)，四種算法得到的拓?fù)浣Y(jié)構(gòu)。

(a) DE (b) GLBCA

(c) GA (d) GAR

從圖1中可以看出，DE、GLBCA、GA和GAR四種算法優(yōu)化網(wǎng)絡(luò)得到的拓?fù)浣Y(jié)構(gòu)差異較大。因?yàn)榇仡^節(jié)點(diǎn)更靠近基站，所以會(huì)接收和轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù)信息給基站，而接收轉(zhuǎn)發(fā)信息會(huì)消耗一定的能量，因此，靠近基站的簇頭將會(huì)率先耗盡自身的能量，也即每條通信鏈路上含有的節(jié)點(diǎn)數(shù)目越少，則靠近基站的簇頭的生存周期越長(zhǎng)。從圖中可以看出DE算法得到的網(wǎng)絡(luò)中最長(zhǎng)通信鏈路上的簇頭數(shù)為9個(gè)，GLBCA的最大通信鏈路上的簇頭數(shù)為16個(gè)，GA為14個(gè)，GAR為14個(gè)。也即DE算法優(yōu)化的網(wǎng)絡(luò)中，靠近基站的簇頭能耗更低，因此具備更長(zhǎng)的網(wǎng)絡(luò)生存周期。

3.2 路由分簇算法性能對(duì)比

通過對(duì)比不同基站位置、不同普通節(jié)點(diǎn)數(shù)和不同高能節(jié)點(diǎn)數(shù)目下， 驗(yàn)證DE、GLBCA、GA和GAR的算法性能。表4、表5是在基站位置在 (250,250)時(shí)，分別布撒20和50高能節(jié)點(diǎn)，普通節(jié)點(diǎn)數(shù)目在200～500之間各個(gè)算法獲得網(wǎng)絡(luò)生命周期的對(duì)比情況。表6、表7是在基站位置在(250,500)時(shí)，分別布撒20和50高能節(jié)點(diǎn)，普通節(jié)點(diǎn)數(shù)目在200～500之間各個(gè)算法的對(duì)比情況。

表4 基站在(250,250)，簇頭數(shù)為20不同算法性能對(duì)比

表5 基站在(250,250)時(shí)，簇頭數(shù)為50不同算法性能對(duì)比

表6 基站在(250,500)，簇頭數(shù)為20不同算法性能對(duì)比

表7 基站在(250,500)，簇頭數(shù)為50不同算法性能對(duì)比

從表4-表7可以看出：

1) 隨節(jié)點(diǎn)數(shù)目的增多，四種算法優(yōu)化的網(wǎng)絡(luò)生存周期都逐漸下降，這是因?yàn)楣?jié)點(diǎn)數(shù)目的增加，簇頭節(jié)點(diǎn)接收融合信息的能耗也隨之增加；

2) 當(dāng)基站位置及普通節(jié)點(diǎn)的數(shù)目相同時(shí)，布撒50路由節(jié)點(diǎn)的能耗高于布撒20路由節(jié)點(diǎn)，這是因?yàn)閷?shí)驗(yàn)中假設(shè)不論本簇內(nèi)含有普通節(jié)點(diǎn)的數(shù)目是多少，每個(gè)路由節(jié)點(diǎn)發(fā)送融合后的數(shù)據(jù)包大小相同；

3) 當(dāng)基站位置不同、路由節(jié)點(diǎn)數(shù)不同或普通節(jié)點(diǎn)數(shù)不同時(shí)，基于差分的分簇路由協(xié)議與其他三種算法相比有著明顯的優(yōu)勢(shì)，也即能得到生存周期更長(zhǎng)的異構(gòu)網(wǎng)絡(luò)。

綜上說明，在不同基站位置、不同路由節(jié)點(diǎn)和普通節(jié)點(diǎn)布撒數(shù)目的情況下，本文算法在優(yōu)化異構(gòu)無線傳感器網(wǎng)絡(luò)時(shí)，都能更好地延長(zhǎng)網(wǎng)絡(luò)整體的工作時(shí)間。

4 結(jié) 語

針對(duì)異構(gòu)傳感器網(wǎng)絡(luò)中的能耗不均問題，本文提出一種基于差分進(jìn)化算法的路由算法和基于節(jié)點(diǎn)能耗的分簇算法。首先以網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的最短生存周期為目標(biāo)，采用差分算法對(duì)其進(jìn)行優(yōu)化，降低了通信中各個(gè)簇頭節(jié)點(diǎn)的能耗差異，然后根據(jù)節(jié)點(diǎn)與簇頭的距離、網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的負(fù)載壓力以及兩種節(jié)點(diǎn)的能量差異對(duì)各個(gè)節(jié)點(diǎn)進(jìn)行分簇，使簇頭和節(jié)點(diǎn)的壽命都盡可能達(dá)到最大。實(shí)驗(yàn)仿真表明，本文算法在不同節(jié)點(diǎn)數(shù)目以及不同的環(huán)境下，均能使整個(gè)網(wǎng)絡(luò)的生存周期達(dá)到最大，驗(yàn)證了本文算法的有效性及先進(jìn)性。

[1] Chong C Y, Kumar S P. Sensor networks: evolution, opportunities, and challenges[J].Proceedings of the IEEE, 2003, 91(8):1247-1256.

[2] Abbasi A A, Younis M. A survey on clustering algorithms for wireless sensor networks[J].Computer Communications, 2007,30(14-15):2826-2841.

[3] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocols for wireless microsensor networks[C]//Proceedings of the Hawaaian International Conference on Systems Sciences, Hawaii,2000:3005-3014.

[4] 余勇昌, 韋崗. 無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進(jìn)算法[J].電子學(xué)報(bào),2008,36(7):1309-1313.

[5] Tang J, Hao B, Sen A. Relay node placement in large scale wireless sensor networks[J].Computer Communications,2006,29(4):490-501.

[6] 孫力娟, 魏靜, 郭劍,等.面向異構(gòu)無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)調(diào)度算法[J].電子學(xué)報(bào),2014,42(10):1907-1912.

[7] Low C P, Fang C, Ng J M, et al. Efficient Load-Balanced Clustering Algorithms for wireless sensor networks[J].Computer Communications,2008,31(4):750-759.

[8] Gupta S K, Jana P K. Energy Efficient Clustering and Routing Algorithms for Wireless Sensor Networks: GA Based Approach[J].Wireless Personal Communications, 2015,83(3):2403-2423.

[9] Gupta S K, Kuila P, Jana P K. GAR: An Energy Efficient GA-Based Routing for Wireless Sensor Networks[C]//9th International Conference on Distributed Computing and Internet Technologies, 2013:267-277.

[10] Heinzelman W B, Chandrakasan A P, Balakrishnan H. Application-specific protocol architectures for wireless networks[D].Cambridge, MA, USA: Massachusetts Institute of Technology,2000.

ROUTING CLUSTERING PROTOCOL FOR WIRELESS SENSOR NETWORKS BASED ON DIFFERENCE ALGORITHM

Li Zhiming Tang Yongzhong

(CenterforInformationTechnology,HexiUniversity,Zhangye734000，Gansu，China)

Aiming at the problem of node energy consumption imbalance in heterogeneous wireless sensor networks, a routing protocol based on differential evolution algorithm and a clustering protocol based on node energy consumption are proposed. The protocol first aims at maximizing the minimum lifetime of cluster head nodes in the network to establish the function optimization model, and uses differential evolution algorithm to optimize it to extend the whole life cycle of the network. Then, the nodes are clustered according to the number of cluster heads in the node communication list, and the nodes are allocated to the cluster head with lower energy consumption, so as to balance the energy consumption of the network and extend the life cycle of the common nodes. The simulation results show that the difference-based routing clustering protocol can effectively balance the energy consumption of nodes in the network, extend the life cycle of the network and improve the network energy efficiency.

Heterogeneous wireless sensor networks Routing Clustering Difference algorithm

2016-05-31。李志明，講師，主研領(lǐng)域：圖像處理，計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用。唐永中，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.01.024