無線傳感網中的一種能量均衡算法的研究

傅 彬

(紹興職業技術學院,浙江 紹興 312000)

無線傳感網中的一種能量均衡算法的研究

傅 彬

(紹興職業技術學院,浙江 紹興 312000)

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

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

0 引言

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

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

1 路由算法與能量消耗關系簡述

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

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

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

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

2.1 Leach簇頭選擇

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

2.1.1 最優簇頭計算

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

(1)

式中,k為數據包大小,EDA為數據融合消耗的能量,D是簇頭節點發送數據的距離。因此簇內節點與簇頭之間通信的能耗為：

(2)

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

(3)

結合無線傳感網中網絡節點均勻分布的特點,將式(2)和式(3)結合：

(4)

因此,簇內發送整個一幀數據的能量消耗為：

(5)

在覆蓋區域中,簇內發送一幀數據的的總能耗為：

(6)

對式(6)求導,取其極小值得到最優簇頭數為:

(7)

2.1.2 染色體編碼

得到最優簇頭數目之后,采用遺傳算法中的固定長度的染色體編碼,將最優簇頭數目設定為染色體長度。編碼按照節點剩余能量標準來進行衡量。在整個無線傳感網中,剩余能量采用如下方法來獲得：

(8)

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

2.2 簇間路由選擇

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

2.2.1 最優跳數的確定

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

(9)

因此,總體耗能為：

(10)

因此按照如下公式計算最優跳數:

(11)

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

2.2.2 轉發概率函數

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

(12)

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

2.2.3 最優中間節點選擇

簇與簇之間的信息轉發都是通過中間節點傳輸到達基站的,因此中間節點能量消耗也是無線傳感網中能耗的重要組成部分。假設中間節點1、中間節點2和基站從左到右依次排列,節點1發送數據到基站必須經過節點2。節點1到節點2的距離為r1,節點2到基站的距離為r2,節點1到基站的距離為r,當節點1向基站發送數據時,節點1到節點2,以及節點2到基站的能量消耗為：

(13)

(14)

因此傳輸的能量總消耗為：

(15)

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

(16)

(17)

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

(18)

3 仿真實驗

3.1 仿真環境

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

3.2 仿真結果分析

3.2.1 節點死亡時間

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

圖1 節點死亡時間與輪數的關系

3.2.2 數據包接收

圖2 數據包接收與輪數的關系

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

3.2.3 能量消耗

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

圖3 能量消耗與輪數的關系

4 結束語

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

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

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

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

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

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

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

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

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

[9] 鄔學軍.基于能量控制的無線傳感網絡最優化算法研究[J].傳感技術學報,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

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

2016-11-02)

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