一種能量有效的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇及簇間路由算法

李燈熬 郝海龍 郭錦龍 趙菊敏

(太原理工大學(xué)信息工程學(xué)院1，山西 太原 030024;國(guó)網(wǎng)山西省電力公司電力科學(xué)研究院2，山西 太原 030001)

0 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)是由大量傳感器節(jié)點(diǎn)通過(guò)無(wú)線(xiàn)通信方式組成的多跳自組織網(wǎng)絡(luò)。在網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)感知并收集監(jiān)視區(qū)域的監(jiān)測(cè)數(shù)據(jù)。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)具有廣泛的應(yīng)用領(lǐng)域，如地震監(jiān)測(cè)、環(huán)境檢測(cè)、戰(zhàn)場(chǎng)監(jiān)視等。

傳感器節(jié)點(diǎn)只能攜帶有限的能量，且一般情況下難以補(bǔ)充，因此如何有效利用有限能源是現(xiàn)在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)研究的重點(diǎn)之一［1］。網(wǎng)絡(luò)的能量消耗主要和通信距離有關(guān)，因此為了減少能量消耗，應(yīng)該盡可能地減小通信距離。解決這些問(wèn)題比較有效的方法是層次型路由算法，這種算法有利于網(wǎng)絡(luò)的擴(kuò)展和簡(jiǎn)化，也不需要建立和維護(hù)路由信息，而且將進(jìn)一步減少長(zhǎng)距離通信的能量消耗［2］。簇大小和傳輸范圍分配(arranging cluster sizes and transmission range，ACT)協(xié)議分簇復(fù)雜，而且沒(méi)有優(yōu)化簇間路由［3］。分布式能量均衡非均勻分簇(distributed energy-balanced unequal clustering，DEBUC)協(xié)議在簇頭競(jìng)爭(zhēng)階段采用計(jì)時(shí)廣播機(jī)制，但沒(méi)有優(yōu)化簇間路由引入代價(jià)函數(shù)來(lái)降低控制消息開(kāi)銷(xiāo)，節(jié)約單個(gè)節(jié)點(diǎn)的能量［4］。LEACH 算法周期性、等概率地選擇簇頭，簇頭收集鄰居節(jié)點(diǎn)的數(shù)據(jù)來(lái)分簇，對(duì)簇首的選擇具有很大的隨機(jī)性，且沒(méi)有考慮簇間路由，與基站單跳通信［5-6］。在LEACH 改進(jìn)算法中，LEACH-C 基站計(jì)算出一個(gè)能量閾值，將高于能量閾值的節(jié)點(diǎn)設(shè)為候選簇頭，選擇簇頭也具有隨機(jī)性，與基站單跳通信［7］。在節(jié)能非均勻分簇(energy-efficient uneven clustering，EEUC)協(xié)議中，設(shè)定門(mén)限值來(lái)設(shè)定候選簇頭，然后根據(jù)簇頭與基站的信號(hào)強(qiáng)度計(jì)算來(lái)選擇簇頭，但在簇間路由中沒(méi)有考慮與基站距離，達(dá)不到全局優(yōu)化的目的［8］。

為了改善傳感器節(jié)點(diǎn)分簇時(shí)的不均勻，均衡能耗現(xiàn)象，本文基于節(jié)點(diǎn)能量剩余和簇頭間的距離等因素來(lái)選擇簇頭;分簇后，綜合考慮簇頭與基站的距離、簇頭能量以及簇內(nèi)成員節(jié)點(diǎn)數(shù)量三種因素，計(jì)算代價(jià)值，選擇下一跳簇頭節(jié)點(diǎn)。這樣通過(guò)簇間距離可均勻分簇，簇間路由通過(guò)選擇最小代價(jià)值來(lái)減少并均衡能耗。

1 網(wǎng)絡(luò)與能耗模型

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

假設(shè)在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，N 個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署到M×M 的矩形區(qū)域中。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)具有如下性質(zhì):①所有節(jié)點(diǎn)能量有限，基站位置固定，能量不受限;②節(jié)點(diǎn)具有唯一ID，均勻分布在監(jiān)測(cè)區(qū)域;③所有節(jié)點(diǎn)具有相同能力(計(jì)算、儲(chǔ)存、通信)，且地位同等;④節(jié)點(diǎn)通信功率可調(diào);⑤節(jié)點(diǎn)具有位置感知能力;⑥每個(gè)節(jié)點(diǎn)可進(jìn)行數(shù)據(jù)融合。

1.2 無(wú)線(xiàn)傳輸能量模型

本文采用文獻(xiàn)［9］中的能耗模型來(lái)構(gòu)建簇內(nèi)通信能耗和簇間通信能耗。簇內(nèi)能耗Ein包括節(jié)點(diǎn)數(shù)據(jù)傳遞和簇頭節(jié)點(diǎn)接收數(shù)據(jù)的能耗。

式中:m 為簇的成員節(jié)點(diǎn)數(shù);di為第i 個(gè)成員節(jié)點(diǎn)和簇頭的距離;Eelec為發(fā)送或接收每bit 數(shù)據(jù)消耗的能量;εamp為多徑衰減信道的功率放大器能耗。

簇間能耗Einter是簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗和以跳級(jí)模式將數(shù)據(jù)信息傳遞到匯聚節(jié)點(diǎn)的能耗。

式中:k 為跳數(shù);q 為第i 個(gè)簇頭的鄰居簇頭數(shù);di為第i個(gè)簇頭距下一級(jí)跳簇頭的距離。

2 網(wǎng)絡(luò)分簇

分簇算法在基站中進(jìn)行，在分簇過(guò)程中綜合考慮節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)距離等因素來(lái)進(jìn)行簇頭選擇以及分簇。

2.1 簇頭距離限值

如圖1 所示的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，簇區(qū)域?yàn)榈冗吜切?，簇頭源節(jié)點(diǎn)和基站之間最優(yōu)的通信路徑為直線(xiàn)多跳路由，通信距離最短。在簇頭多跳路由中，簇的半徑是影響能耗的關(guān)鍵因素，由于dlimit的值和簇頭數(shù)目以及簇區(qū)域面積有關(guān)，因此通過(guò)取合適的dlimit，可減小較小區(qū)域內(nèi)簇頭太多或較大區(qū)域內(nèi)沒(méi)有簇頭的概率，從而均勻部署簇頭。如果dlimit太小，可能會(huì)在較小區(qū)域內(nèi)出現(xiàn)多個(gè)簇頭，形成多個(gè)簇，簇頭收集到簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)后，傳輸給基站時(shí)可能導(dǎo)致碰撞或者數(shù)據(jù)傳輸冗余等情況。如果dlimit太大，那么在較大區(qū)域內(nèi)簇頭會(huì)減少，簇區(qū)域面積會(huì)增大，簇內(nèi)成員節(jié)點(diǎn)和簇頭的通信能耗更多。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，取定合適的dlimit可均衡網(wǎng)絡(luò)能耗。文獻(xiàn)［10］基于六角簇區(qū)域，求得最優(yōu)的簇半徑r 如式(3)所示，距離限值如式(4)所示。

圖1 基于簇間多跳的網(wǎng)絡(luò)分簇結(jié)構(gòu)Fig.1 The clustering structure of network based on multiple hops between the clusters

式中:ee為信號(hào)發(fā)射機(jī)發(fā)射每比特?cái)?shù)據(jù)的能量消耗;λ為載波波長(zhǎng);dR為節(jié)點(diǎn)數(shù)據(jù)傳輸率;β 為損耗因子;pthr為能耗閾值。

2.2 分簇流程

在每輪分簇過(guò)程中，首先計(jì)算所有節(jié)點(diǎn)Ni(i =n)的剩余平均能量，設(shè)定能量閾值，設(shè)剩余能量高于能量閾值的節(jié)點(diǎn)為候選簇頭Mi(i=1，2，…，m)。依次為節(jié)點(diǎn)M1～Mm分配簇內(nèi)成員節(jié)點(diǎn)，每次為一個(gè)Mi分配簇內(nèi)成員節(jié)點(diǎn)，若Mi與M1，M2，…，Mi-1中至少一個(gè)的距離小于距離限值dlimit，則不為Mi分配簇內(nèi)成員節(jié)點(diǎn)并將Mi作為成員節(jié)點(diǎn)分配給M1，M2，…，Mi-1中距離最近的簇頭。設(shè)最終的簇頭集合為CHi(i =1，2，…，c)。由于成員節(jié)點(diǎn)數(shù)與簇頭的能耗有關(guān)，為了均衡能耗，將當(dāng)前簇頭的成員節(jié)點(diǎn)數(shù)和與簇頭的距離作為參數(shù)定義一個(gè)代價(jià)函數(shù)(5)，網(wǎng)絡(luò)中其余節(jié)點(diǎn)Nj選擇代價(jià)值S(CHi，Nj)值最小的簇頭CHi作為成員節(jié)點(diǎn)加入。這樣成員節(jié)點(diǎn)不僅可以選擇相對(duì)較小距離的簇頭加入，而且使得簇內(nèi)的成員節(jié)點(diǎn)數(shù)更加均衡。直到遍歷完所有候選簇頭Mi(i=1，2，…，m)，分簇完成后，基站向全網(wǎng)絡(luò)廣播簇頭節(jié)點(diǎn)ID 和各簇內(nèi)成員節(jié)點(diǎn)的ID。

式中:dCHi，Ni為簇頭CHi和節(jié)點(diǎn)Nj的距離;dmax為網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的最大距離;mh為簇頭CHi的當(dāng)前成員節(jié)點(diǎn)數(shù);N 為網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)的總數(shù);α 和β 為權(quán)重因子，且α+β=1;f 為路徑損耗指數(shù)。

3 簇間路由

當(dāng)與基站距離較遠(yuǎn)的簇頭將數(shù)據(jù)傳輸?shù)交緯r(shí)，如果簇頭單跳將數(shù)據(jù)傳輸?shù)交荆仡^容易耗完能量成為死亡節(jié)點(diǎn)。若簇頭與基站通信采用多跳路由可均衡能耗，并減少由于長(zhǎng)距離通信的路徑損耗而浪費(fèi)的能量。在分簇階段，基站根據(jù)收集到的網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的位置信息，計(jì)算簇頭與基站的距離，然后反饋給每個(gè)節(jié)點(diǎn)。當(dāng)簇頭與基站通信時(shí)，若簇頭與基站的距離小于或等于dlimit，簇頭與基站直接單跳通信。若簇頭與基站的距離大于dlimit，則建立簇間多跳路由與基站進(jìn)行通信。多跳路由建立流程如下。

(1)與基站進(jìn)行通信的簇頭源節(jié)點(diǎn)向鄰居簇頭節(jié)點(diǎn)發(fā)送詢(xún)問(wèn)數(shù)據(jù)包，詢(xún)問(wèn)信息包括簇頭ID、簇頭與基站的距離以及簇頭的剩余能量。鄰居簇頭節(jié)點(diǎn)收到詢(xún)問(wèn)數(shù)據(jù)包后，向簇頭源節(jié)點(diǎn)發(fā)送應(yīng)答數(shù)據(jù)包。

(2)簇頭源節(jié)點(diǎn)根據(jù)應(yīng)答數(shù)據(jù)包中的信息，基于式(6)計(jì)算所有鄰居簇頭節(jié)點(diǎn)的簇間權(quán)重值WCHi，j，選擇權(quán)重值WCHi，j最小的鄰居簇頭節(jié)點(diǎn)作為下一跳簇頭節(jié)點(diǎn)，簇間權(quán)重值包括簇頭與基站距離、簇頭剩余能量和簇內(nèi)成員節(jié)點(diǎn)數(shù)這三個(gè)因素。

式中:i≠j，dCHi，j為簇頭i 與簇頭j 的距離;dm為網(wǎng)絡(luò)中簇頭與基站的最遠(yuǎn)距離;f 為路勁損耗因子;Ej為簇頭j的剩余能量;Emaxj 為節(jié)點(diǎn)初始化的最大能量;mj為簇頭所屬簇內(nèi)成員節(jié)點(diǎn)個(gè)數(shù);α、β 和γ 為權(quán)重因子，且α +β+γ=1。

(3)基于步驟(2)，選擇下一跳簇頭，直到出現(xiàn)一個(gè)簇頭與基站的距離比其他所有鄰居簇頭與基站的距離小時(shí)，這個(gè)簇頭直接與基站進(jìn)行通信，簇頭與基站的多跳通信完成。

4 仿真與結(jié)論

本文采用Matlab 進(jìn)行仿真實(shí)驗(yàn)。為了證明該算法的有效性，將本文算法與LEACH-C 和EEUC 算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比。模擬實(shí)驗(yàn)場(chǎng)景為1 000 m×1 000 m，隨機(jī)部署節(jié)點(diǎn)總數(shù)為1 000，基站的坐標(biāo)為(1 100，500)，其他仿真參數(shù)如表1 所示。

表1 仿真參數(shù)表Tab.1 The simulation parameters

通過(guò)仿真比較網(wǎng)絡(luò)的生命周期、接收數(shù)據(jù)包和能量消耗來(lái)觀(guān)察本文算法性能。圖2 為本文算法與LEACH-C 以及EEUC 算法的生命周期對(duì)比圖。

圖2 網(wǎng)絡(luò)生命周期對(duì)比圖Fig.2 Comparison of network life cycle

從圖2 可以看出，本文算法與LEACH-C 以及EEUC 分別在900 輪、750 輪以及600 輪節(jié)點(diǎn)全部死亡，與其他兩種算法相比生命周期延長(zhǎng)了91%以及20%。LEACH-C 選擇簇頭具有隨機(jī)性，導(dǎo)致分簇不均勻，而且簇頭與基站間單跳通信;而EEUC 中臨時(shí)簇頭未考慮能量，并且所有節(jié)點(diǎn)都要做競(jìng)爭(zhēng)半徑等更多計(jì)算，簇頭較容易死亡，且分簇更加頻繁;本文算法根據(jù)簇頭間的合理距離限值均勻分簇，并且簇頭間根據(jù)路徑權(quán)值選擇最佳路徑，減小了能耗。

基站接收數(shù)據(jù)量對(duì)比如圖3 所示。

由圖3 所示，本文算法的基站接收數(shù)據(jù)量均高于LEACH-C 以及EEUC 算法。本文算法不僅根據(jù)最優(yōu)距離限值均勻分簇，而且簇頭間的路徑權(quán)值可減少能耗;而LEACH-C 未考慮簇頭間路由，EEUC 未考慮臨時(shí)簇頭的能量以及節(jié)點(diǎn)計(jì)算耗能。因此本文算法在節(jié)點(diǎn)全部死亡前可進(jìn)行更長(zhǎng)時(shí)間的運(yùn)行，即消耗相同的能量傳送更多的數(shù)據(jù)到基站。

圖4 為三種算法的網(wǎng)絡(luò)剩余能量仿真圖。

圖4 剩余能量對(duì)比圖Fig.4 Comparison of the remaining energy

圖4 顯示，隨著仿真時(shí)間的推移，本文算法的剩余能量均高于其他兩種算法。本文算法的分簇是基于最優(yōu)距離限值，并且選擇了最優(yōu)的簇頭間路由，而LEACH-C 隨機(jī)選擇簇頭，且單跳與基站進(jìn)行通信;EEUC 算法忽略了臨時(shí)簇頭的能量，且節(jié)點(diǎn)的計(jì)算能耗也更大。因此，和其他兩種算法相比，本文算法更加節(jié)省能耗。

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

通過(guò)對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)路由能量?jī)?yōu)化模型、分簇模型以及簇間路由的研究，提出了基于簇頭距離限值的分簇算法以及基于路徑權(quán)值的簇間路由算法。通過(guò)合理配置簇頭距離限值，能夠均勻分簇，使得在一定區(qū)域內(nèi)有數(shù)量合理的簇頭。在簇間路由選擇中，綜合考慮簇頭與基站距離、簇頭能量以及簇內(nèi)節(jié)點(diǎn)數(shù)量計(jì)算路徑權(quán)值，在保證節(jié)點(diǎn)數(shù)據(jù)傳遞的同時(shí)，均衡能耗，提高能量利用率，最終延長(zhǎng)網(wǎng)絡(luò)的生存周期。

［1］ 孫利民.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)［M］. 北京:清華大學(xué)出版社有限公司，2005.

［2］ Latif K，Jaffar M，Javaid N，et al.Performance analysis of hierarchical routing protocols in wireless sensor networks［J］. International Conference on Broadband，Wireless Computing，Communication Applications，2012，49(1):620-625.

［3］ Lai W K，F(xiàn)an C S，Lin L Y.Arranging cluster sizes and transmission ranges for wireless sensor networks［J］.Information Sciences，2012，183(1):117 -131.

［4］ Wan M，Zhu Y. An energy efficient routing protocol for wireless sensor networks［C］//International Conference on Computational Intelligence and Communication Networks，2012:95 -97.

［5］ 沈波，張世永，鐘亦平.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2006，17(7):1588 -1600.

［6］ Chen X，Wang Z，Wu J.The improved wireless sensor network routing algorithm based on LEACH［J］. Chinese Journal of Sensors and Actuators，2013(1):025.

［7］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An applicationspecific protocol architecture for wireless microsensor networks［J］.Wireless Communications，IEEE Transactions on，2002，1(4):660-670.

［8］ Kim D H. Tuning of a PID controller using an artificial immune network model and local fuzzy set［C］//IFSA World Congress and 20th NAFIPS International Conference，2001. Joint 9th. IEEE，2001:2698 -2703.

［9］ Ibrahim R，Ho Q D，Le-Ngoc T. An energy-efficient and loadbalancing cluster-based routing algorithm for CSMA-based wireless sensor networks［C］//Vehicular Technology Conference (VTC Spring)，2013 IEEE 77th，2013:1 -5.