無線傳感網(wǎng)中的一種能量均衡算法的研究

傅 彬

(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

無線傳感網(wǎng)中的一種能量均衡算法的研究

傅 彬

(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

如何能夠降低無線傳感網(wǎng)中的節(jié)點(diǎn)能量消耗一直都是研究的熱門。針對基本Leach路由算法存在節(jié)點(diǎn)能量消耗大、負(fù)載不均衡的缺點(diǎn),文章一方面在Leach算法的簇頭選擇中首先進(jìn)行最優(yōu)解計(jì)算,其次通過遺傳算法的染色體編碼概念對簇內(nèi)其他節(jié)點(diǎn)能量排序進(jìn)行優(yōu)化,得到最優(yōu)簇頭；另一方面在簇間路由中進(jìn)行最優(yōu)跳數(shù)的確定,引入轉(zhuǎn)發(fā)概率函數(shù)和最優(yōu)中間點(diǎn)的選擇提高路由效率。在仿真實(shí)驗(yàn)中,與基本Leach算法相比，改進(jìn)算法在節(jié)點(diǎn)死亡時(shí)間、數(shù)據(jù)包接收和能量消耗方面都具有明顯的改善。

無線傳感；Leach；簇頭；簇間

0 引言

如何能夠降低無線傳感網(wǎng)中的能量消耗一直都是研究的熱門方向,這主要是因?yàn)闊o線傳感網(wǎng)的數(shù)據(jù)之間傳輸逐漸增多,能量消耗也在不斷增大。文獻(xiàn)[1]提出一種兼顧節(jié)點(diǎn)密度的能耗均衡分簇算法，仿真實(shí)驗(yàn)表明該算法能夠有效地降低節(jié)點(diǎn)消耗的能量;文獻(xiàn)[2]挑選出最小跳數(shù)和能量高的路徑傳輸,可以有效地降低網(wǎng)絡(luò)的能量消耗,避免節(jié)點(diǎn)的負(fù)載過大;文獻(xiàn)[3]利用節(jié)點(diǎn)自身的剩余能量和周圍鄰居節(jié)點(diǎn)的平均剩余能量計(jì)算簇頭報(bào)文發(fā)送的標(biāo)志,進(jìn)一步降低了無效節(jié)點(diǎn)的能量消耗;文獻(xiàn)[4]提出了一種能量潛能機(jī)會路由算法，取得了比較好的效果;文獻(xiàn)[5]提出一種基于能量均衡的WSN路由算法,該算法采用回退機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)的自適應(yīng)調(diào)整,有效地保證節(jié)點(diǎn)以較高的幾率成為簇首,該算法能夠有效延長網(wǎng)絡(luò)壽命;文獻(xiàn)[6]提出將監(jiān)測區(qū)域看成以基站為中心的扇形區(qū)域,并將此劃分為多個(gè)弧形方塊并成為簇,采用單跳和多跳相結(jié)合來實(shí)現(xiàn)簇間通信;文獻(xiàn)[7]提出將區(qū)域劃分為4個(gè)大小相同的局部區(qū)域,然后選擇節(jié)點(diǎn)能量方差最小的局部區(qū)域作為路由選擇區(qū)域,采用概率機(jī)制選擇路徑傳輸節(jié)點(diǎn);文獻(xiàn)[8]提出一種能量負(fù)載均衡的多跳路由協(xié)議，采用遺傳模擬退火算法進(jìn)行分簇,并計(jì)算每個(gè)簇的聚類中心,在簇間路由階段,采用最短路徑進(jìn)行多跳路由選擇;文獻(xiàn)[9]提出采用布爾傳感模型確定覆蓋率與單位面積內(nèi)傳感器節(jié)點(diǎn)密度的函數(shù)關(guān)系,依靠Prim算法的貪心策略,有效地降低整個(gè)網(wǎng)絡(luò)中的能量消耗。

本文在以上研究的基礎(chǔ)上，從改進(jìn)Leach算法作為解決能量負(fù)載不均衡入手,對算法的簇頭進(jìn)行最優(yōu)解計(jì)算,通過遺傳算法中的染色體概念對簇內(nèi)節(jié)點(diǎn)能量排序,同時(shí)引入轉(zhuǎn)發(fā)概率函數(shù)在最優(yōu)中間點(diǎn)中進(jìn)行選擇,提高了算法性能,并通過實(shí)驗(yàn)說明了本文算法具有明顯的改善。

1 路由算法與能量消耗關(guān)系簡述

無線傳感網(wǎng)中的路由選擇是非常關(guān)鍵的,它主要負(fù)責(zé)將數(shù)據(jù)從源節(jié)點(diǎn)傳送到目的節(jié)點(diǎn)。由于其中節(jié)點(diǎn)的能量有限,因此能量均衡是路由算法需要考慮的問題。在無線傳感網(wǎng)中節(jié)點(diǎn)能量有限,路由算法在設(shè)計(jì)過程中需要將節(jié)點(diǎn)權(quán)重作為參考權(quán)重,使用過濾機(jī)制,去除大量冗余的數(shù)據(jù),將節(jié)點(diǎn)采集的數(shù)據(jù)進(jìn)行融合,減少不必要的能量消耗；同時(shí)應(yīng)該保持通信負(fù)載的網(wǎng)絡(luò)平衡,在設(shè)計(jì)路由算法時(shí)增加對路由選擇的隨機(jī)性,避免最優(yōu)路徑節(jié)點(diǎn)頻繁使用而位置較差的節(jié)點(diǎn)使用少而導(dǎo)致節(jié)點(diǎn)過早死亡。因此下一跳的節(jié)點(diǎn)剩余能量的選擇需要結(jié)合路由算法來進(jìn)行考慮。

Leach協(xié)議是一種經(jīng)典的層次路由協(xié)議,其過程是循環(huán)更新簇。首先隨機(jī)選擇簇頭節(jié)點(diǎn)并進(jìn)行分簇,其他未加入簇的節(jié)點(diǎn)選擇通信代價(jià)最小的簇節(jié)點(diǎn)加入；其次是所有節(jié)點(diǎn)采集到的數(shù)據(jù)發(fā)給自己所在的簇節(jié)點(diǎn),簇節(jié)點(diǎn)將各個(gè)成員的節(jié)點(diǎn)進(jìn)行信息處理,通過數(shù)據(jù)融合將數(shù)據(jù)傳遞給基站,通過不斷地迭代,將簇節(jié)點(diǎn)的能量分?jǐn)偨o簇內(nèi)每一個(gè)節(jié)點(diǎn),降低能量消耗,但其自身存在簇節(jié)點(diǎn)選擇隨機(jī)性、負(fù)載不均衡性和未考慮簇節(jié)點(diǎn)與基站距離等缺點(diǎn)。

2 基于改進(jìn)的能量均衡算法的研究

針對Leach算法存在的不足,本文假設(shè)在以下前提下進(jìn)行研究：傳感器節(jié)點(diǎn)已經(jīng)知道自己的位置,節(jié)點(diǎn)之間的傳輸耗能相同。從簇頭選擇和簇間路由進(jìn)行改進(jìn)。

2.1 Leach簇頭選擇

簇頭選擇在無線傳感網(wǎng)中的分簇算法中是非常重要的,它決定了整個(gè)網(wǎng)絡(luò)的性能。如果一個(gè)簇頭的位置不好或者能量不足就會導(dǎo)致整個(gè)網(wǎng)絡(luò)資源的消耗增加,并且還有可能使網(wǎng)絡(luò)性能下降,因此如何選擇簇頭成為解決問題的關(guān)鍵。遺傳算法是一種基于自然選擇的生物進(jìn)化算法,通過染色體編碼進(jìn)行優(yōu)化,從而找到最優(yōu)解。遺傳算法能夠自動地控制優(yōu)化的搜索方向,因此非常適合用于復(fù)雜度高的分簇方法。

2.1.1 最優(yōu)簇頭計(jì)算

在無線傳感網(wǎng)中,假設(shè)有N個(gè)節(jié)點(diǎn)分布在m×m區(qū)域中,分配h個(gè)簇,因此每個(gè)簇內(nèi)平均有N/h個(gè)節(jié)點(diǎn),其中N/h-1為簇內(nèi)非簇頭節(jié)點(diǎn),設(shè)定網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)都是按照多跳傳輸方式進(jìn)行發(fā)送數(shù)據(jù),設(shè)定傳輸距離為D,簇頭的能量消耗包括簇內(nèi)成員的信息、數(shù)據(jù)融合和數(shù)據(jù)傳送三個(gè)部分的能量消耗。因此每個(gè)簇頭節(jié)點(diǎn)的能量消耗為：

(1)

式中,k為數(shù)據(jù)包大小,EDA為數(shù)據(jù)融合消耗的能量,D是簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離。因此簇內(nèi)節(jié)點(diǎn)與簇頭之間通信的能耗為：

(2)

其中,dtoCH為成員節(jié)點(diǎn)與簇頭之間的距離。設(shè)定該區(qū)域?yàn)閳A形,簇頭位于簇中間位置,則得到：

(3)

結(jié)合無線傳感網(wǎng)中網(wǎng)絡(luò)節(jié)點(diǎn)均勻分布的特點(diǎn),將式(2)和式(3)結(jié)合：

(4)

因此,簇內(nèi)發(fā)送整個(gè)一幀數(shù)據(jù)的能量消耗為：

(5)

在覆蓋區(qū)域中,簇內(nèi)發(fā)送一幀數(shù)據(jù)的的總能耗為：

(6)

對式(6)求導(dǎo),取其極小值得到最優(yōu)簇頭數(shù)為:

(7)

2.1.2 染色體編碼

得到最優(yōu)簇頭數(shù)目之后,采用遺傳算法中的固定長度的染色體編碼,將最優(yōu)簇頭數(shù)目設(shè)定為染色體長度。編碼按照節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)來進(jìn)行衡量。在整個(gè)無線傳感網(wǎng)中,剩余能量采用如下方法來獲得：

(8)

式中,Eave表示整個(gè)無線傳感網(wǎng)中的剩余平均能量,將節(jié)點(diǎn)剩余能量大于Eave的節(jié)點(diǎn)從1到M編號來代替染色體中的0,1編碼。

2.2 簇間路由選擇

在無線傳感網(wǎng)中,當(dāng)簇形成之后,簇頭節(jié)點(diǎn)收到來自簇內(nèi)成員的數(shù)據(jù)之后,通過融合,向基站發(fā)送數(shù)據(jù)。當(dāng)遠(yuǎn)離基站時(shí)，簇頭節(jié)點(diǎn)就會消耗過多的能量,因此采用傳統(tǒng)的多跳方式顯然不是很好的解決辦法,本文將多跳與單跳方式相結(jié)合來降低簇頭與基站之間的信號消耗。

2.2.1 最優(yōu)跳數(shù)的確定

在半徑為R的無線傳感區(qū)域內(nèi)分布了N個(gè)節(jié)點(diǎn),將節(jié)點(diǎn)與基站的距離劃分為n個(gè)區(qū)域,半徑為r1,r2,…rn。為了簡化計(jì)算,假設(shè)簇頭位于區(qū)域中間位置,每個(gè)區(qū)域的寬度為r,大致估算出r1區(qū)域簇頭半徑為r/2,依次類推rn區(qū)域簇頭的半徑為n+(r/2)。當(dāng)處于r1區(qū)域的簇頭節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)為k時(shí),每個(gè)簇頭能量消耗為：

(9)

因此,總體耗能為：

(10)

因此按照如下公式計(jì)算最優(yōu)跳數(shù):

(11)

式(11)中,當(dāng)簇頭與基站的距離小于d0時(shí),使用單跳傳輸；否則,采用多跳傳輸。

2.2.2 轉(zhuǎn)發(fā)概率函數(shù)

在基站點(diǎn)附近的多跳路由都具有節(jié)點(diǎn)能量消耗快的特點(diǎn),因此造成了靠近基站的節(jié)點(diǎn)能量容易過早消耗的現(xiàn)象,雖然本文之前描述了單跳和多跳傳輸?shù)倪x擇,但仍然存在這樣的問題。根據(jù)這種情況,本文設(shè)定一個(gè)轉(zhuǎn)發(fā)概率函數(shù)來使得簇間的路由在單跳和多跳中進(jìn)行選擇,盡可能地避免因?yàn)榫嚯x的問題而產(chǎn)生能耗不均勻的問題。轉(zhuǎn)發(fā)公式如下：

(12)

式中,r為簇頭與基站之間的距離,Elast為簇頭內(nèi)的剩余能量,ρ為均衡系數(shù)。通過概率轉(zhuǎn)發(fā)函數(shù)可以選擇比較好的路由，均衡簇頭之間的能量消耗,有效延長簇頭壽命。

2.2.3 最優(yōu)中間節(jié)點(diǎn)選擇

簇與簇之間的信息轉(zhuǎn)發(fā)都是通過中間節(jié)點(diǎn)傳輸?shù)竭_(dá)基站的,因此中間節(jié)點(diǎn)能量消耗也是無線傳感網(wǎng)中能耗的重要組成部分。假設(shè)中間節(jié)點(diǎn)1、中間節(jié)點(diǎn)2和基站從左到右依次排列,節(jié)點(diǎn)1發(fā)送數(shù)據(jù)到基站必須經(jīng)過節(jié)點(diǎn)2。節(jié)點(diǎn)1到節(jié)點(diǎn)2的距離為r1,節(jié)點(diǎn)2到基站的距離為r2,節(jié)點(diǎn)1到基站的距離為r,當(dāng)節(jié)點(diǎn)1向基站發(fā)送數(shù)據(jù)時(shí),節(jié)點(diǎn)1到節(jié)點(diǎn)2,以及節(jié)點(diǎn)2到基站的能量消耗為：

(13)

(14)

因此傳輸?shù)哪芰靠傁臑椋?/p>

(15)

節(jié)點(diǎn)1到基站之間的能量消耗表達(dá)如下：

(16)

(17)

綜上所述,當(dāng)簇頭節(jié)點(diǎn)的坐標(biāo)為(x,y)時(shí),最優(yōu)下一步的中間點(diǎn)的坐標(biāo)為(xopt,yopt),且：

(18)

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

3.1 仿真環(huán)境

為了進(jìn)一步說明本文算法在降低能量消耗方面的作用,模擬真實(shí)環(huán)境,節(jié)點(diǎn)數(shù)量為1 000個(gè),分布在100 m×100 m的區(qū)域中,基站處于區(qū)域的中心位置(50 m,50 m),節(jié)點(diǎn)之間的最大通信距離為85 m,能量比較高的節(jié)點(diǎn)占據(jù)總節(jié)點(diǎn)數(shù)量的10% ,傳輸能耗ξfs為1×10-11J。 硬件系統(tǒng)CPU采用酷睿i3,內(nèi)存為4GB，硬盤容易為500GB。軟件采用Windows7,仿真環(huán)境為MATLAB2010。

3.2 仿真結(jié)果分析

3.2.1 節(jié)點(diǎn)死亡時(shí)間

圖1表示了仿真環(huán)境下的節(jié)點(diǎn)有效生存時(shí)間。從圖中可以發(fā)現(xiàn)基本Leach算法的第一個(gè)節(jié)點(diǎn)死亡時(shí)間比本文算法的節(jié)點(diǎn)死亡時(shí)間早,這說明基本Leach算法的網(wǎng)絡(luò)效率開始下降,當(dāng)經(jīng)過一段時(shí)間之后,Leach算法仍然有一部分節(jié)點(diǎn)存活時(shí)間長,這說明Leach算法負(fù)載不均衡導(dǎo)致了節(jié)點(diǎn)的使用效率低。本文算法的第一個(gè)節(jié)點(diǎn)死亡時(shí)間要晚于基本Leach算法,這是因?yàn)楸疚乃惴ㄔ诖仡^節(jié)點(diǎn)的選擇上使用了單跳與多跳相結(jié)合的方式來降低網(wǎng)絡(luò)整體的能量消耗。 在整個(gè)網(wǎng)絡(luò)中,本文算法比基本Leach算法具有更好的曲線傾斜度,這說明整個(gè)無線傳感網(wǎng)的節(jié)點(diǎn)死亡時(shí)間更加集中,具有更好的負(fù)載性。

圖1 節(jié)點(diǎn)死亡時(shí)間與輪數(shù)的關(guān)系

3.2.2 數(shù)據(jù)包接收

圖2 數(shù)據(jù)包接收與輪數(shù)的關(guān)系

圖2表示了基站接收數(shù)據(jù)包的數(shù)據(jù)量與時(shí)間的關(guān)系。在算法運(yùn)行初期,本文算法與基本Leach算法數(shù)據(jù)包是一致的,經(jīng)過一段時(shí)間后,Leach算法接收的數(shù)據(jù)包有所下降,主要是因?yàn)長each算法中存在的負(fù)載不均衡問題容易導(dǎo)致部分節(jié)點(diǎn)能耗過大而失效。而本文算法采用單跳與多跳相結(jié)合的方式使得負(fù)載均衡,無線傳感網(wǎng)絡(luò)的生命周期有所增長,數(shù)據(jù)包接收數(shù)量較基本Leach算法多。

3.2.3 能量消耗

圖3為能量消耗與時(shí)間的關(guān)系,與基本的Leach算法相比,本文算法的總體能量消耗趨于平穩(wěn),這是因?yàn)樵谒惴ǔ跗?本文算法采用了多跳路由算法與基站進(jìn)行通信,一定程度上降低了節(jié)點(diǎn)的能耗,經(jīng)過一段時(shí)間之后,由于大部分節(jié)點(diǎn)已經(jīng)失效,本文算法的覆蓋面積要大于基本Leach算法,因此能耗比較大。從整個(gè)過程來看,本文算法的網(wǎng)絡(luò)一直保持比較穩(wěn)定的能量消耗速度,說明本文算法具有很好的穩(wěn)定性,這主要是由于簇頭節(jié)點(diǎn)選擇和簇間路由方面都考慮了節(jié)點(diǎn)負(fù)載的均衡性,達(dá)到了在無線傳感網(wǎng)中的能量均衡目的。

圖3 能量消耗與輪數(shù)的關(guān)系

4 結(jié)束語

針對無線傳感網(wǎng)中的能量消耗問題,本文在Leach算法的基礎(chǔ)上,對其進(jìn)行改進(jìn),提高了算法的有效性能,降低了能耗。仿真實(shí)驗(yàn)表明,通過與基本Leach算法在節(jié)點(diǎn)死亡時(shí)間、數(shù)據(jù)包接收和能量消耗方面進(jìn)行對比，本文方法都具有明顯的改善。

[1] 曹立志,陳瑩.基于學(xué)習(xí)自動機(jī)的無線傳感網(wǎng)能量均衡分簇算法[J].傳感技術(shù)學(xué)報(bào),2013,26(11):1590-1596.

[2] 樊志平,謝冬青,金政哲.無線傳感網(wǎng)絡(luò)能量有效負(fù)載均衡的多路徑路由策略[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(2):253-257.

[3] 陳志.一種能量感知的無線傳感網(wǎng)拓?fù)淇刂扑惴╗J].傳感技術(shù)學(xué)報(bào),2013,26(3):382-387.

[4] 田賢忠,肖赟.一種能量捕獲無線傳感網(wǎng)絡(luò)機(jī)會路由算法[J].計(jì)算機(jī)科學(xué),2016，41(s1):288-290.

[5] 李運(yùn)濤,朱敏,劉昊霖,等.基于能量均衡的無線傳感網(wǎng)絡(luò)路由算法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,49(1):69-74.

[6] 張偉龍,郭成芳.基于能量均衡的無線傳感器網(wǎng)絡(luò)路由算法[J].激光雜志,2014,35(12):96-98.

[7] 吳三斌,柳強(qiáng),李成博.基于能量均衡的無線傳感器網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(4):1465-1469.

[8] 張世偉,張海濤,張士杰.基于固定分簇和能量均衡的無線傳感器網(wǎng)絡(luò)多跳路由算法[J].傳感器與微系統(tǒng),2013,32(8):117-120.

[9] 鄔學(xué)軍.基于能量控制的無線傳感網(wǎng)絡(luò)最優(yōu)化算法研究[J].傳感技術(shù)學(xué)報(bào),2011,24(3):436-439.

Research of an energy balance algorithm in wireless sensor network

Fu Bin

(Shaoxing Vocational & Technical College,Shaoxing 312000, China)

How to reduce the node energy consumption in wireless sensor has always been a hotspot of research. Aiming at the basic Leach routing algorithm’s defects of large node energy consumption and unbalanced load, this paper firstly calculates the optimal solution in the cluster head selection of Leach algorithm, and then optimizes the energy sequence of other nodes within the cluster through the chromosome encoding concept of genetic algorithm to obtain the optimal cluster on one hand; on the other hand, through determining the optimal number of hops in the cluster routing, probability function is introduced and the optimal intermediate point is chosen to improve the route’s efficiency. In simulation experiment, compared with basic Leach algorithm, the algorithm has been significantly improved in node death time, data package receiving and energy consumption.

wireless sensor; Leach; cluster head; inter cluster

TP393

A

10.19358/j.issn.1674- 7720.2017.07.021

傅彬.無線傳感網(wǎng)中的一種能量均衡算法的研究[J].微型機(jī)與應(yīng)用，2017,36(7)：70-73，77.

2016-11-02)

傅彬(1980-),男,碩士,講師,主要研究方向：信息安全、無線傳感。