一種高效節能的無線傳感器網絡分簇路由算法

2018-09-11 02:12:34施志剛李桂娟張持健

傳感器與微系統 2018年9期

施志剛，李桂娟，李亮，張持健

(安徽師范大學物理與電子信息學院，安徽蕪湖 241000)

0 引言

無線傳感器網絡(wireless sensor networks,WSNs)在智能交通、環境監測、工業控制等領域有著相當的發展優勢，但電池更換困難，因此設計一種高效節能的路由算法，最大限度地延長網絡生存周期尤為重要。Heinzelman W等人[1]在2000年提出了分簇路由算法的典型代表LEACH算法。近年來,在LEACH算法基礎上相繼提出了多種改進方法，pLEACH算法[2]中提出將網絡分區，然后在各個子區域中選出剩余能量最高的節點作為簇頭；覃海生等人[3]在細胞膜優化算法的基礎上通過濃度、能量和距離三因子完成對節點的分簇；羅琴等人[4]運用模糊理論計算節點擔任簇頭的概率來改進閾值公式；嚴斌亨等人[5]通過節點的剩余能量和連通度來優化簇頭選舉。上述算法在一定程度上降低了網絡能耗，但簇頭分布的隨機性沒有得到很好解決,且未從全局和局部兩個方面來考慮簇內、簇頭間的能耗問題。

本文給出了一種高效節能的WSNs分簇路由算法(efficient and energy-saving clustering routing algorithm for WSNs，ECRAW)，其特點在于：結合最優簇頭數運用遺傳算法(genetic algorithm,GA)和引力對簇的形成進行改進；簇頭選舉時考慮節點的剩余能量、節點與基站以及節點與簇中心之間的距離；引入通信代價函數建立簇頭與基站的多跳通信。

1 經典LEACH算法不足

雖然相比于傳統的平面路由算法,LEACH算法將網絡生存周期提高了15 %[6]，但仍存在一些問題：1)簇頭選舉的隨機性導致簇頭分布不均勻；2)簇頭的選舉未考慮節點的剩余能量，低能量的節點擔任簇頭會導致簇頭過早死亡，影響數據的傳輸，出現監測盲區現象；3)數據傳輸采用單跳的方式，遠距離傳輸消耗大量的能量，不適用于大規模的無線傳感網絡。

2 ECRAW算法

本文從分簇方式、簇頭的選舉和路由方式3個方面對LEACH算法加以改進，與LEACH算法類似，每一輪也分為簇的建立和穩定傳輸，不同的是ECRAW算法在簇的建立階段先進行簇的劃分，再執行簇頭選舉。

2.1 最優簇頭數

本文采用文獻[7]的最優簇頭數K計算方法為

(1)

2.2 GA和引力改進簇的形成

本文采用GA優化初始聚類中心，以避免聚類效果受初始聚類中心的干擾，陷入局部最優。優化步驟如下：

1)編碼方式:隨機選取K個節點組成1個個體，染色體采用節點下標進行編碼，即1,2,…,K；

2)初始化種群，按上述編碼方式，重復H次得到種群；

3)構造適應度函數(式(2))；

4)經過選擇、交叉和變異操作得到新的種群；

5)重復步驟(4)，達到最大的迭代次數，并輸出種群中適應度最大的個體即優化之后的初始聚類中心。

在簇的形成過程中引入引力思想，傳感節點看成是有質量無體積的質點，引力大小和簇內節點個數(質點質量)正比，與質點之間的距離成反比。由于只需比較兩個引力相對大小，每次待分簇的質點在參與引力運算時，其個數一直是1，即可省略一個m，同時G可以忽略不計。為了避免簇內節點數過多，所造成引力過大帶來“黑洞”問題以及簇頭負載過重加快死亡現象，改進后的引力公式為

(2)

根據式(2)知，待分簇節點與簇中心的距離越小，簇內節點越多，引力就越大,該節點加入該簇的機會就越大。簇的形成過程如下：

1)設置GA運行參數，執行GA算法，適應度最大的個體即初始聚類中心；

2)基站逐一計算網絡節點與K個初始聚類中心間引力大小，并加入引力較大的簇，開始成簇，并更新簇中心；

3)基站逐一計算剩余網絡節點與更新后的聚類中心之間的引力大小，并更新簇中心；

4)重復步驟(3)，直到所有節點均入簇，分簇完成。

2.3 簇頭選舉

分簇完成之后，在簇內進行簇頭的選舉，結合最優簇頭比例在LEACH算法基礎上，考慮節點的剰余能量、節點到基站以及節點到簇中心的距離，得到新的閾值為

(3)

(4)

每輪中節點通過rand(1,1)隨機產生1個數，若小于式(3)，節點當選為該簇的簇頭，重復上述過程，在每個簇中選出簇頭。改進后的閾值計算公式使剩余能量較多、距離基站和距離簇中心較近的節點有更多的機會當選為簇頭，在一定程度上使簇頭分布均勻，均衡網絡能耗。

2.4 穩定傳輸

ECRAW算法整體流程如圖1。

圖1 ECRAW算法工作流程

3 算法仿真及對比分析

3.1 實驗網絡參數

為了驗證ECRAW算法的性能，采用一階無線通信能耗模型[8]，本文通過MATLAB 2014a平臺將其與LEACH,LEACH-EC算法[5]在死亡節點數、剩余能量和消耗能量3個方面進行了仿真比較。設有100個初始能量為1J的節點隨機部署在100 m×100 m的區域中，基站位于(50 m,50 m)處，實驗的相關網絡參數如下：數據包長度4 000 bits，εfs為10 pJ/bit/m2，εamp為0.001 3 pJ/bit/m4，數據融合能耗EDA為5 nJ/bit，收發電路能耗Eelec為50 nJ/bit。

3.2 仿真結果

評價網絡的生存周期通常看第1個節點死亡時間(first node dead-time,FND)和1/2節點死亡時間(half node dead-time,HND)。圖2中相比于LEACH和LEACH-EC算法本文算法從FND到最后一個節點死亡時間均滯后，延長了網絡的生存周期。本文算法FND出現在第2 375輪，較LEACH提高了1.64倍，較LEACH-EC延長了58.4 %；HND出現在2 521輪，較LEACH提高1.09倍，較LEACH-EC延長23.3 %；另外圖中本文算法的曲線陡峭，說明節點能量消耗均衡性較好，可見，本文算法具有明顯的優勢，主要原因是改進了簇的形成和簇頭的選舉，使簇頭分布更均勻，簇頭與基站通信的機制的改進降低了網絡能耗。

圖2 網絡生存周期對比

隨著網絡的運行，圖3說明了網絡能量在不斷消耗，相比之下，在相同的時間內，運用本文算法消耗的總能量少于其他2種算法；相同的初始能量下，總能量耗盡較晚。圖4中本文算法的剩余能量高于其他2種算法，表明了在相同的初始能量下，改進后的算法較LEACH 和 LEACH-EC 能耗較小，有效地節約能量，另外，ECRAW算法傾斜度較為平緩，說明網絡性能較為穩定。