一種能耗均衡的無線傳感器網絡分簇路由算法

張詩悅，吳建德，2，王曉東，2，范玉剛，2，冷婷婷

(1.昆明理工大學a.信息工程與自動化學院;b.土木工程學院，昆明 650500;2.云南省礦物管道輸送工程技術研究中心，昆明 650500)

1 概述

路由技術是無線傳感器網絡研究的熱點，也是核心技術之一。由于節點多采用能量有限的電池進行供電，如何最大限度地平衡能耗以延長網絡生命周期就成為了研究的重點。分簇式路由協議由于實際應用效果優于平面型路由協議，已經逐漸成為了研究的熱點方向，其中，LEACH［1］就是最典型的分簇式路由協議。然而，LEACH 協議存在簇頭隨機選取、簇頭分布不均以及簇頭同基站單跳通信、能耗過大容易死亡等缺點，針對這些問題，目前已經提出了很多改進的路由算法。文獻［2］分析指出，在單跳情況下，節點同基站距離越遠其通信能耗越大，越容易死亡［3］;在多跳情況下，同基站距離越近其能耗越大，越容易失效［4］。為此，EECS 算法［5］讓距離基站較遠的簇的尺寸較大，距離基站較近的簇的尺寸較小，以此平衡簇頭能耗。EEUC 算法［6］在非均勻分簇的基礎上，考慮節點剩余能量和同基站的距離來選擇中繼節點進行多跳路由，同時計算非均勻分簇的競爭半徑，距離基站遠的簇的競爭半徑較大，這一點類似EECS 算法。ACOUC 算法［7］在非均勻分簇的基礎上加入基于定向的蟻群優化算法優化多跳路徑，在首輪節點全部參與競選簇頭、后續輪內自行更換的方法來節省能耗。CEB-UC 算法［8］將網絡分成不同的區域，使距離基站近的分區內簇的數量多，而簇內節點數目較少，以此平衡網絡開銷。此外，研究者利用將已有的優化算法加入到路由算法的設計中，如遺傳算法［9］、貝葉斯游戲［10］等，從而達到提高網絡性能的目的。本文則提出一種基于能量和距離因子的非均勻分簇的能耗均衡路由算法(ECRED)。

2 網絡模型與能耗分析

2.1 網絡模型

本文所采用的模型設定如下:(1)基站位于監控區域外部，位置固定，能量無限且只有一個;(2)所有節點同構且具有唯一ID，位置一旦固定則不再移動;(3)節點能量有限且初始能量相同;(4)節點發射功率可調;(5)無線鏈路是對稱的;(6)節點均具有相應的計算處理等能力。

2.2 能耗模型

文獻［11］研究表明:進行無線電收發時所消耗的電量要遠大于節點休眠時消耗的電量。每傳輸1 bit數據所消耗的電量可以執行數千條CPU 指令，且消耗的時間也更少［12］。假設發射電路能耗為Eelec(nJ/bit)，計算能耗為Eda(nJ/bit)，數據包長度為l(bit)，消息長度k(bit)，d0為選擇空間模型的劃分閾值，小于d0選擇自由空間模型，功率放大能耗為Efs;大于d0選擇多路徑衰減模型，功率放大能耗為Emp。若忽略空閑和休眠的能耗，則簇成員數為N 的單簇建簇所消耗的能量為Eone，計算公式如下:

簇成員數為N 的簇在計算分配時隙所消耗的能量為Est，計算公式如下:

3 ECRED 算法

3.1 最優簇頭數

在分簇路由協議中，簇頭所占比例p 的確定對于網絡的能耗有很大的影響［13］，很多學者針對最優的p 值進行了研究［14］，多數文獻傾向于取該值為0.05，即100 個節點中選擇5 個節點作為簇頭。采用均勻分簇即每個簇節點數目相同，非均勻分簇則簇內節點數目不均等。本文根據節點到基站距離的遠近來進行非均勻分簇，第i 個簇的簇內節點總數Nopt(CHi)的計算公式如下:

其中，ceil 是向上取整函數;Dis是第i 個簇頭到基站的距離;Dmin是所有節點到基站距離的最小值;Dmax是所有節點到基站距離的最大值;p 是簇頭占節點總數的百分比。本文設定單簇最少節點數為8，小于8則解散該簇。

3.2 簇頭選擇

簇頭選擇過程基本同LEACH 協議一樣，本算法稍作改進。采用備擇簇頭更替策略，當簇頭能量小于最低能量閾值，則轉交簇頭權限給備擇簇頭，減少建簇次數。首先基站廣播競選信息，收到消息的節點隨機產生一個(0，1)隨機數，如果該數大于閾值T(n)則標記為備擇簇頭，等待時間T 后廣播當選信息，標記為簇頭;如果在等待時間T 內收到其他節點的當選信息，則加入與其通信代價最小的簇頭所在的簇。改進后的閾值公式為:

其中，r 為當前的輪數;Ecur為節點剩余能量;dis為節點到基站距離;G 為在1/p 輪中未當選為簇頭的節點集合。改進后的公式使得當節點的剩余能量Ecur越大、節點到基站的距離dis越小，閾值T(n)越大，從而該節點當選為簇頭的幾率越大，反之當選為簇頭的幾率越小。

3.3 簇的建立和簇間路由

由于單簇的規模有限，簇成員節點同簇頭以單跳方式通信即可，為避免信號沖突，簇內通信采用TDMA 機制。由于部分簇頭可能距離基站較遠，而通信能耗隨距離的增加呈幾何增長，因此簇間路由采用多跳方式，簇間通信采用CSMA 機制。節點在分配的時隙之內發送數據，在其他時隙則進入休眠狀態，從而降低能耗。

由于部分節點距離基站較近，單跳同基站通信的能耗要小于通過簇頭轉發的能耗，因此設定單跳距離閾值，當節點同基站的距離小于該單跳閾值時直接發送數據到基站。這樣可以節約網絡能耗，減少“熱點”壓力。

簇頭需要知道其通信范圍內一跳鄰居簇頭的相關信息，選擇中繼權值最大的簇頭作為下一跳中繼簇頭。節點i 同一跳鄰居節點j 的中繼權值的計算公式如下:

其中，Ecur_j表示簇頭j 的剩余能量;di，j表示簇頭i 到簇頭j 的距離;dis_j表示簇頭j 到基站的距離;簇頭i從所有一跳鄰居節點里面選擇中繼權值最大的作為中繼簇頭，直到所有的簇頭都加入到路由鏈當中為止。如果簇頭i 在通信范圍內沒有找到其他簇頭，則提高發射功率廣播，并重新計算中繼權值。

4 算法仿真與性能驗證

4.1 仿真參數設定

為驗證ECRED 算法的性能，將EECS 和ECRED算法進行仿真對比。仿真參數如下:忽略信道通信干擾和信號碰撞等因素，將100 個節點隨機部署到100 ×100 的監控區域當中，基站坐標(50，175)，數據包長度4 000 bit，距離閾值d0=877 058 m，發送/接收電路能耗Eelec=50 nJ/bit，數據融合能耗Eda=5 nJ/bit/signal。

4.2 仿真結果分析

4.2.1 對網絡密度的適應性

當初始能量Einitial=0.5 J，節點總數N=100 時，ECRED 算法和EECS 算法的網絡生命曲線如圖1所示;當Einitial=0.5 J，N=200 時，2 種算法的生命曲線如圖2 所示。從圖中可以看出，相對EECS 算法，ECRED 算法的網絡生命周期都有所延長，當N=100時，網絡壽命延長了8.4%，而當N=200 時，網絡壽命延長了8.0%，由此可見，ECRED 算法對網絡密度具有很好的適應性。

圖3 是2 種算法的網絡能耗對比，可以看出，開始時兩者能耗差別極小，但隨著輪數的增加，ECRED算法的網絡能耗相對EECS 算法更小，通過對比可以發現，網絡密度對網絡能耗稍有影響。

圖1 Einitial=0.5 J，N=100 時的網絡生命曲線

圖2 Einitial=0.5 J，N=200 時的網絡生命曲線

圖3 Einitial=0.5 J，N=100 時的網絡能耗

4.2.2 對初始能量的適應性

為驗證ECRED 算法對網絡密度的適應性，本文將初始能量Einitial作為自變量，分別取0.5 J 和1 J，節點數N=100，其他參數同上，得到生命曲線和網絡能耗如圖4 和圖5 所示。

圖4 Einitial=1 J，N=100 時的生命曲線

圖5 Einitial=1 J，N=100 時的網絡能耗

對比圖1 和圖4 可以看出，初始能量越大，網絡性能越好。當Einitial=0.5 J 時，ECRED 算法的生命周期相對于EECS 算法提高了7.4%;而當Einitial=1 J時，性能提高了11.9%。可見，ECRED 算法的性能和初始能量成正比，且性能要相對優于EECS算法。

5 結束語

本文提出一種基于能量和距離因子的非均勻分簇的能耗均衡路由算法(ECRED)。該算法采用能量和距離雙因子確定簇頭，在廣播時增加等待時間以便接收其他節點建簇信息，增加備擇簇頭，減少建簇次數，降低網絡能耗;同時采用單跳和多跳路由方法降低“熱區”節點能耗。文中給出了非均勻分簇的簇內節點數計算公式，使得距離基站近的簇規模相對較小，而距離基站較遠的簇規模較大，同時避免了極小簇的存在。通過仿真實驗表明，ECRED 算法可以有效地平衡網絡能耗，延長網絡壽命。

雖然本文提出的ECRED 算法在平衡網絡能耗上有一定的優勢，但仍有一些問題需要深入研究。未來的研究主要包括:(1)在節約能耗的基礎上增加對分簇路由算法安全性能的考慮，設計一種安全的路由算法;(2)對簇頭數目進行優化，進一步減少能耗損失。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks［C］//Proceedings of the 33rd Hawaii International Conference on System Science.Hawaii，USA:［s.n.］，2000:3005-3014.

［2］Perillo M，Zhao Cheng，Heinzelman W.On the Problem of Unbalanced Load Distribution in Wireless Sensor Networks［C］//Proceedings of IEEE GLOBECOM'04.Dallas，USA:IEEE Press，2004:74-79.

［3］Soro S，Heinzelman W.Prolonging the Lifetime of Wireless Sensor Network via Unequal Clustering［C］//Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium.Denver，USA:IEEE Press，2005:365.

［4］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1):27-36.

［5］Ye Mao，Li Chengfa，Chen Gguihai，et al.An Energy Efficient Clustering Scheme in Wireless Sensor Networks［C］//Proceedings of IEEE International Performance Computing and Communications Conference.Phoenix，USA:IEEE Press，2005:535-540.

［6］Li Chengfa，Ye Mao，Chen Guihai，et al.An Energyefficient Unequal Clustering Mechanism for Wireless Sensor Networks ［C］//Proceedings of 2005 IEEE International Conference on Mobile Ad-hoc and Sensor Systems.Washington D.C.，USA:IEEE Press，2005:597-604.

［7］Zhang Rongbo，Cao Jianfu.Uneven Clustering Routing Algorithm for Wireless Sensor Networks Based on Ant Colony Optimization［J］.Journal of Xi'an Jiaotong University，2010，44(6):33-38.

［8］Wang Yi，Zhang Deyun，Liang Taotao.Cell Energy Balanced Uneven Clustering Hierarchy Scheme for Wireless Sensor Networks［J］.Journal of Xi'an Jiaotong University，2008，42(4):389-394.

［9］Noyouzi A，Babanir F S，Zaim A H.A New Clustering Protocol for Wireless Sensor Networks Using Genetic Algorithm Approach［J］.Wireless Sensor Network，2011，3(11)，362-370.

［10］Zheng Gengzhong，Liu Sanyang，Qi Xiaogang.Clustering Routing Algorithm of Wireless Sensor Networks Based on Bayesian Game［J］.Journal of Systems Engineering and Electronics，2012，23(1):154-159.

［11］Larios D F，Barbancho J，Rodríguez G，et al.Energy Efficient Wireless Sensor Network Communications Based on Computational Intelligent Data Fusion for Environmental Monitoring［J］.IET Communications，2012，6(14):2189-2197.

［12］Min R，Bhardwaj M，Cho S H，et al.Energy-Centric Enabling Technologies for Wireless Sensor Networks［J］.IEEE Wireless Communications，2002，9 (4):28-39.

［13］Heinzelman W，Chandrakasan A，Balakrishnan H.An Application-specific Protocol Architecture for Wireless Sensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［14］Bandyopadhyay S，Coyle E J.An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks［C］//Proceedings of IEEE INFOCOM'03.San Francisco，USA:IEEE Computer Society，2003:1713-1723.