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

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

0 引言

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

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

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

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

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

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

1.2 無線傳輸能量模型

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

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

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

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

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

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

2.1 簇頭距離限值

如圖1 所示的無線傳感器網(wǎng)絡(luò)，簇區(qū)域為等邊六角形，簇頭源節(jié)點和基站之間最優(yōu)的通信路徑為直線多跳路由，通信距離最短。在簇頭多跳路由中，簇的半徑是影響能耗的關(guān)鍵因素，由于dlimit的值和簇頭數(shù)目以及簇區(qū)域面積有關(guān)，因此通過取合適的dlimit，可減小較小區(qū)域內(nèi)簇頭太多或較大區(qū)域內(nèi)沒有簇頭的概率，從而均勻部署簇頭。如果dlimit太小，可能會在較小區(qū)域內(nèi)出現(xiàn)多個簇頭，形成多個簇，簇頭收集到簇內(nèi)成員節(jié)點的數(shù)據(jù)后，傳輸給基站時可能導(dǎo)致碰撞或者數(shù)據(jù)傳輸冗余等情況。如果dlimit太大，那么在較大區(qū)域內(nèi)簇頭會減少，簇區(qū)域面積會增大，簇內(nèi)成員節(jié)點和簇頭的通信能耗更多。在無線傳感器網(wǎng)絡(luò)中，取定合適的dlimit可均衡網(wǎng)絡(luò)能耗。文獻［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為信號發(fā)射機發(fā)射每比特數(shù)據(jù)的能量消耗;λ為載波波長;dR為節(jié)點數(shù)據(jù)傳輸率;β 為損耗因子;pthr為能耗閾值。

2.2 分簇流程

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

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

3 簇間路由

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

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

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

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

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

4 仿真與結(jié)論

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

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

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

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

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

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

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

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

圖4 剩余能量對比圖Fig.4 Comparison of the remaining energy

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

5 結(jié)束語

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

［1］ 孫利民.無線傳感器網(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ǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報，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.