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

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

1 概述

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

2 網(wǎng)絡(luò)模型與能耗分析

2.1 網(wǎng)絡(luò)模型

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

2.2 能耗模型

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

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

3 ECRED 算法

3.1 最優(yōu)簇頭數(shù)

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

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

3.2 簇頭選擇

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

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

3.3 簇的建立和簇間路由

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

由于部分節(jié)點距離基站較近，單跳同基站通信的能耗要小于通過簇頭轉(zhuǎn)發(fā)的能耗，因此設(shè)定單跳距離閾值，當(dāng)節(jié)點同基站的距離小于該單跳閾值時直接發(fā)送數(shù)據(jù)到基站。這樣可以節(jié)約網(wǎng)絡(luò)能耗，減少“熱點”壓力。

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

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

4 算法仿真與性能驗證

4.1 仿真參數(shù)設(shè)定

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

4.2 仿真結(jié)果分析

4.2.1 對網(wǎng)絡(luò)密度的適應(yīng)性

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

圖3 是2 種算法的網(wǎng)絡(luò)能耗對比，可以看出，開始時兩者能耗差別極小，但隨著輪數(shù)的增加，ECRED算法的網(wǎng)絡(luò)能耗相對EECS 算法更小，通過對比可以發(fā)現(xiàn)，網(wǎng)絡(luò)密度對網(wǎng)絡(luò)能耗稍有影響。

圖1 Einitial=0.5 J，N=100 時的網(wǎng)絡(luò)生命曲線

圖2 Einitial=0.5 J，N=200 時的網(wǎng)絡(luò)生命曲線

圖3 Einitial=0.5 J，N=100 時的網(wǎng)絡(luò)能耗

4.2.2 對初始能量的適應(yīng)性

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

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

圖5 Einitial=1 J，N=100 時的網(wǎng)絡(luò)能耗

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

5 結(jié)束語

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

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

［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］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機(jī)學(xué)報，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.