傅 彬

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

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

傅 彬

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

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

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

0 引言

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

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

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

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

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

2 基于改進的能量均衡算法的研究

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

2.1 Leach簇頭選擇

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

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

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

(1)

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

(2)

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

(3)

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

(4)

因此,簇內(nèi)發(fā)送整個一幀數(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é)點剩余能量標準來進行衡量。在整個無線傳感網(wǎng)中,剩余能量采用如下方法來獲得：

(8)

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

2.2 簇間路由選擇

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

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

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

(9)

因此,總體耗能為：

(10)

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

(11)

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

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

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

(12)

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

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

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

(13)

(14)

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

(15)

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

(16)

(17)

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

(18)

3 仿真實驗

3.1 仿真環(huán)境

為了進一步說明本文算法在降低能量消耗方面的作用,模擬真實環(huán)境,節(jié)點數(shù)量為1 000個,分布在100 m×100 m的區(qū)域中,基站處于區(qū)域的中心位置(50 m,50 m),節(jié)點之間的最大通信距離為85 m,能量比較高的節(jié)點占據(jù)總節(jié)點數(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é)點死亡時間

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

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

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

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

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

3.2.3 能量消耗

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

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

4 結(jié)束語

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

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

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

[3] 陳志.一種能量感知的無線傳感網(wǎng)拓撲控制算法[J].傳感技術(shù)學(xué)報,2013,26(3):382-387.

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

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

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

[7] 吳三斌,柳強,李成博.基于能量均衡的無線傳感器網(wǎng)絡(luò)路由算法[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é)報,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].微型機與應(yīng)用，2017,36(7)：70-73，77.

2016-11-02)

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