張?jiān)姁?，吳建德?，王曉東，2，范玉剛，2，冷婷婷

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

1 概述

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

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

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

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

2.2 能耗模型

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

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

3 ECRED 算法

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

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

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

3.2 簇頭選擇

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

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

3.3 簇的建立和簇間路由

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

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

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

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

4 算法仿真與性能驗(yàn)證

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

為驗(yàn)證ECRED 算法的性能，將EECS 和ECRED算法進(jìn)行仿真對(duì)比。仿真參數(shù)如下:忽略信道通信干擾和信號(hào)碰撞等因素，將100 個(gè)節(jié)點(diǎn)隨機(jī)部署到100 ×100 的監(jiān)控區(qū)域當(dāng)中，基站坐標(biāo)(50，175)，數(shù)據(jù)包長(zhǎng)度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 對(duì)網(wǎng)絡(luò)密度的適應(yīng)性

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

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

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

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

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

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

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

圖4 Einitial=1 J，N=100 時(shí)的生命曲線

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

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

5 結(jié)束語(yǔ)

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

雖然本文提出的ECRED 算法在平衡網(wǎng)絡(luò)能耗上有一定的優(yōu)勢(shì)，但仍有一些問(wèn)題需要深入研究。未來(lái)的研究主要包括:(1)在節(jié)約能耗的基礎(chǔ)上增加對(duì)分簇路由算法安全性能的考慮，設(shè)計(jì)一種安全的路由算法;(2)對(duì)簇頭數(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ú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，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.