異構(gòu)傳感網(wǎng)中一種能量均衡非均勻分簇算法

武 朗，胡艷軍

(安徽大學(xué) 計算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039)

無線傳感器網(wǎng)絡(luò)(wireless sensor network， 簡稱WSN)由許多具有感知能力、功率低的傳感器節(jié)點(diǎn)組成，已得到廣泛應(yīng)用，如遠(yuǎn)程監(jiān)控環(huán)境、棲息地、汽車和災(zāi)區(qū).WSN具有耗能較低、節(jié)點(diǎn)數(shù)量多、以數(shù)據(jù)為中心和動態(tài)拓?fù)涞忍攸c(diǎn)，此特點(diǎn)決定了現(xiàn)有的網(wǎng)絡(luò)協(xié)議很難適應(yīng)WSN對網(wǎng)絡(luò)生存時間、擴(kuò)展性和負(fù)載均衡的需求.對于具有大量節(jié)點(diǎn)的WSN，分簇算法可有效提高網(wǎng)絡(luò)壽命，同時其擴(kuò)展性可滿足網(wǎng)絡(luò)負(fù)載均衡要求[1-4]. LEACH分簇算法[5]基于“輪”的思想選取簇頭(cluster heads，簡稱CHs)，但其對CHs的選取是隨機(jī)的，導(dǎo)致整個WSN中CHs能量消耗不均衡.SEP分簇算法[6]中CHs選取由節(jié)點(diǎn)初始能量決定，但沒有考慮節(jié)點(diǎn)的當(dāng)前能量.DEEC分簇算法[7]中CHs的選擇基于節(jié)點(diǎn)的剩余能量與網(wǎng)絡(luò)平均能量的比值，需要計算網(wǎng)絡(luò)平均能量.BEEC分簇算法[8]在CHs選取的最終階段引入了競爭機(jī)制，在簇構(gòu)建階段，只考慮了節(jié)點(diǎn)到CHs的距離，并沒有考慮整個WSN因傳輸路徑規(guī)劃不合理導(dǎo)致的能量消耗.HEED分簇算法[9]根據(jù)節(jié)點(diǎn)剩余能量概率選取候選簇頭，再依據(jù)簇內(nèi)通信代價的高低產(chǎn)生最終的CHs.非均勻分簇算法[10-11]解決了多跳通信帶來的簇間能耗不均衡問題，但沒有考慮異構(gòu)網(wǎng)絡(luò)的情況.筆者針對異構(gòu)網(wǎng)絡(luò)中的單跳通信，提出一種適用于異構(gòu)無線傳感網(wǎng)的能量均衡非均勻分簇(energy equilibrium non-uniform clustering，簡稱EENC)算法.

1 能量均衡非均勻分簇算法

不同類型的傳感器節(jié)點(diǎn)初始狀態(tài)下配置的能量不同，感知區(qū)域內(nèi)隨機(jī)分布的節(jié)點(diǎn)在運(yùn)行時消耗剩余能量也不同，導(dǎo)致傳感器網(wǎng)絡(luò)不同節(jié)點(diǎn)出現(xiàn)能量異構(gòu)[7].在異構(gòu)傳感網(wǎng)單跳均勻分簇路由協(xié)議中，遠(yuǎn)離BS的CHs消耗更多能量，導(dǎo)致CHs間能量消耗不均衡.下面具體介紹筆者提出的EENC算法細(xì)節(jié).

1.1 初始化

異構(gòu)傳感網(wǎng)由2級能量異構(gòu)節(jié)點(diǎn)構(gòu)成，在感知區(qū)域內(nèi)隨機(jī)分布一定比例的普通節(jié)點(diǎn)和高級節(jié)點(diǎn).對網(wǎng)絡(luò)節(jié)點(diǎn)假設(shè)如下：

(1) 每個節(jié)點(diǎn)都有唯一的ID；

(2) 根據(jù)節(jié)點(diǎn)與接收者的距離，調(diào)整發(fā)射功率；

(3) 一旦節(jié)點(diǎn)部署完成，所有節(jié)點(diǎn)保持靜止；

(4) 節(jié)點(diǎn)根據(jù)接收信號強(qiáng)度(RSSI)計算發(fā)送者到自己的距離；

(5) 每個節(jié)點(diǎn)知道基站位置.

初始化階段涉及的信息如表1所示.

表1 節(jié)點(diǎn)信息表

1.2 簇頭選取

簇頭選取分為臨時簇頭選取和最終簇頭確定.臨時簇頭選取采用LEACH算法中“輪”的思想和DEEC算法中簇頭選取方法.最終簇頭確定中，引入非均勻競爭機(jī)制，根據(jù)能量因子從臨時簇頭中選取最優(yōu)簇頭.

1.2.1 臨時簇頭選取

臨時簇頭選取直接采用LEACH和DEEC簇頭算法，兩算法的詳細(xì)介紹見文獻(xiàn)[4，6].LEACH算法中簇頭選取的閾值T(i)定義如下

(1)

其中：p為傳感器節(jié)點(diǎn)當(dāng)選CHs的比例，r為當(dāng)前輪數(shù)，G為當(dāng)前1/p輪數(shù)中未能成為CHs的節(jié)點(diǎn)集合.

2級能量異構(gòu)網(wǎng)絡(luò)中，DEEC算法中高級節(jié)點(diǎn)和普通節(jié)點(diǎn)當(dāng)選臨時簇頭的概率分別為

(2)

(3)

將式(2)，(3)計算出的概率padv，pnrm，替代式(1)中的p，得到不同能級節(jié)點(diǎn)當(dāng)選臨時簇頭對應(yīng)的閾值.比較節(jié)點(diǎn)隨機(jī)產(chǎn)生的值與閾值的大小，確定該節(jié)點(diǎn)能否在本輪中當(dāng)選臨時簇頭.

1.2.2 簇頭最終確定

簇頭最終確定要使用非均勻多跳路由EEUC算法，并引入競爭機(jī)制選取簇頭.依據(jù)臨時簇頭與基站間的距離設(shè)定臨時簇頭競爭范圍，距離基站遠(yuǎn)的臨時簇頭競爭范圍小，距離基站近的臨時簇頭競爭范圍大.臨時簇頭通過競爭產(chǎn)生最終簇頭，使距離基站較遠(yuǎn)的簇內(nèi)擁有較少的節(jié)點(diǎn)，這樣可減少該簇頭向基站傳輸?shù)臄?shù)據(jù)量，從而緩解單跳分簇路由中，因簇頭與基站距離的不同而造成的簇頭能量消耗不均衡.離基站相對較近的節(jié)點(diǎn)可以直接向基站傳輸數(shù)據(jù)，進(jìn)一步減少該區(qū)域內(nèi)簇頭的負(fù)擔(dān).圖1為經(jīng)過非均勻競爭后簇頭的最終分布，圖中大小不等的圓表示簇頭競爭范圍.

圖1 經(jīng)過非均勻競爭后簇頭的最終分布

不同的臨時簇頭i分別引入不同的競爭半徑Ri，其表達(dá)式如下

(4)

其中：dmax為傳感網(wǎng)中臨時簇頭與BS間的最大距離，dmin為臨時簇頭與BS間的最小距離，di_to_BS為臨時簇頭i與BS的距離，Rc為最小競爭半徑，c為0到1之間的常數(shù).由(4)式可知，臨時簇頭競爭半徑Ri與其到基站的距離di_to_BS有關(guān).di_to_BS越大時，Ri值越小，即當(dāng)其位置離基站越遠(yuǎn)時，其競爭范圍越小.

每個臨時簇頭在各自的競爭范圍內(nèi)，根據(jù)自身能量因子γi=Ei/di_to_BS的大小，與其他臨時簇頭競爭最終簇頭.Ei為臨時簇頭i的剩余能量，di_to_BS為臨時簇頭i與基站的距離.競爭范圍內(nèi)一旦臨時簇頭i競選成功，則成為最終簇頭CHi.其他臨時簇頭則退出競爭，成為節(jié)點(diǎn)成員，簇頭選取流程如圖2所示.

圖2 簇頭選取流程

1.3 簇的構(gòu)建

根據(jù)文獻(xiàn)[7]中FORM節(jié)點(diǎn)能量模型可知，節(jié)點(diǎn)的能量消耗與其傳輸距離密切相關(guān).BEEC算法中，如果只考慮節(jié)點(diǎn)與簇頭間距及簇頭的剩余能量這兩種因素，則節(jié)點(diǎn)加入簇頭的過程如圖3實(shí)線所示.

節(jié)點(diǎn)i，j加入簇頭CH1后，簇頭CH1對節(jié)點(diǎn)i，j傳來的數(shù)據(jù)進(jìn)行接收、融合，并把融合后的數(shù)據(jù)傳輸給BS. 這樣雖然減少了剩余能量少的簇頭能量消耗，卻增加了整個網(wǎng)絡(luò)的能量消耗.合理的傳輸路徑不僅考慮節(jié)點(diǎn)與簇頭間距、簇頭剩余能量，還要考慮節(jié)點(diǎn)與基站的位置關(guān)系.如圖3虛線所示，節(jié)點(diǎn)i，j加入簇頭CH2，CH2向BS傳輸數(shù)據(jù)，這樣可大大縮短總的傳輸距離，減少網(wǎng)絡(luò)的總能量消耗.

圖3 節(jié)點(diǎn)加入簇頭的示意圖

節(jié)點(diǎn)加入簇頭前，要計算節(jié)點(diǎn)i與基站的距離di_to_BS及與簇頭的最短距離dmin(CH_to_BS).如果di_to_BS小于最短距離dmin(CH_to_BS)，則節(jié)點(diǎn)i直接向BS傳輸數(shù)據(jù)，這既減少了節(jié)點(diǎn)自身的通信損耗，也降低了簇頭的負(fù)擔(dān).否則，節(jié)點(diǎn)將加入最大的costjoin_to_CHk對應(yīng)的簇頭，costjoin_to_CHk的表達(dá)式如下

(5)

1.4 數(shù)據(jù)傳輸

一旦完成簇的構(gòu)建，則進(jìn)入數(shù)據(jù)傳輸階段.節(jié)點(diǎn)能量消耗公式[12]為

ERX(l,d)=l·Eele，

(6)

(7)

其中：ERX(l,d)為接收端接收l比特(bit)數(shù)據(jù)量所消耗的能量；ETX(l,d)為發(fā)送端發(fā)送l比特(bit)數(shù)據(jù)量所需要的能量；Eele為發(fā)送或接受單位比特(bit)數(shù)據(jù)消耗的能量，Eele=5 nJ·bit-1；εfs，εamp分別為自由空間和多徑衰落信道中放大器的能耗，εfs=10 pJ·bit-1·m-2,εamp=0.001 3 pJ·bit-1·m-4；d0為距離閾值，d0=87 m.

2 仿真及分析

對提出的EENC算法在網(wǎng)絡(luò)生存周期、吞吐量和網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量方面與LEACH，SEP，DEEC算法進(jìn)行比較.簇頭每向基站發(fā)送一次數(shù)據(jù)視為網(wǎng)絡(luò)執(zhí)行一輪，仿真采用MATLAB數(shù)學(xué)工具，以下的實(shí)驗(yàn)值是20次實(shí)驗(yàn)的平均值.仿真中使用的參數(shù)見表2.

表2 仿真參數(shù)

在簇頭最終確定階段，對臨時簇頭引入競爭機(jī)制.變量Rc的值決定最終簇頭的數(shù)量，影響網(wǎng)絡(luò)生存周期.Rc值增加，臨時簇頭的競爭范圍變大，生成的最終簇頭數(shù)量就會減少，反之Rc值減小，生成的最終簇頭數(shù)量就會增加.下面通過仿真選取Rc的最佳值.

圖4 網(wǎng)絡(luò)生存周期所對應(yīng)輪數(shù)與簇頭競爭半徑的關(guān)系

由圖4可以看出，Rc=15 m時網(wǎng)絡(luò)生存時間最長.簇頭競爭半徑較小時，網(wǎng)絡(luò)簇頭數(shù)量較多，大量節(jié)點(diǎn)與基站通信，網(wǎng)絡(luò)能耗快.而當(dāng)競爭半徑較大時，網(wǎng)絡(luò)簇頭數(shù)量較少，簇頭處理簇內(nèi)數(shù)據(jù)的能耗增多，第一個節(jié)點(diǎn)會過早死亡.

2.1 網(wǎng)絡(luò)生存周期

從開始到第1個節(jié)點(diǎn)死亡所經(jīng)歷的輪數(shù)為網(wǎng)絡(luò)生存周期.在2級能量異構(gòu)網(wǎng)絡(luò)下，圖5為網(wǎng)絡(luò)節(jié)點(diǎn)生存數(shù)隨輪數(shù)變化情況.

圖5 網(wǎng)絡(luò)節(jié)點(diǎn)生存數(shù)隨輪數(shù)變化

從圖5中可以看出，筆者提出的EENC算法網(wǎng)絡(luò)生存周期長，非穩(wěn)定時間短，EENC，DEEC，SEP，LEACH算法對應(yīng)的網(wǎng)絡(luò)生存周期分別為1628，1487，1261，989.EENC算法的網(wǎng)絡(luò)生存周期相對DEEC，SEP，LEACH的，分別提高了9%，29%，64%.因此，EENC算法延長了網(wǎng)絡(luò)生存周期，均衡了網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗.

2.2 網(wǎng)絡(luò)吞吐量

圖6 為基站接收的數(shù)據(jù)量隨輪數(shù)的變化情況.由圖6可知，網(wǎng)絡(luò)中第一個節(jié)點(diǎn)死亡之前，即曲線拐點(diǎn)處，基站接收的數(shù)據(jù)量隨輪數(shù)近似線性變化.由于節(jié)點(diǎn)過早死亡，導(dǎo)致基站接收數(shù)據(jù)量的速率下降，表現(xiàn)為曲線斜率逐漸變緩，直至所有節(jié)點(diǎn)死亡，曲線趨于水平.EENC算法基站最終接收數(shù)據(jù)總量比其他算法更大.

圖6 基站接收的數(shù)據(jù)量隨輪數(shù)的變化

2.3 網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量

圖7為網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量隨輪數(shù)變化的情況.由圖7可知，與其他算法相比，EENC算法網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量隨輪數(shù)變化的斜率最小，說明EENC算法整個網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗速率較慢.從第一個網(wǎng)絡(luò)節(jié)點(diǎn)死亡到整個網(wǎng)絡(luò)節(jié)點(diǎn)死亡，EENC算法網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量隨輪數(shù)增大而緩慢遞減，且無明顯的拐點(diǎn).EENC算法能很好地均衡整個網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗，能量利用率高.

圖7 網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量隨輪數(shù)的變化

3 結(jié)束語

筆者針對能量異構(gòu)無線傳感網(wǎng)單跳分簇路由的特點(diǎn)，提出了能量均衡非均勻分簇算法.該算法在簇頭最終確定階段對臨時簇頭引入不同的競爭半徑，使整個網(wǎng)絡(luò)形成非均勻分簇結(jié)構(gòu)，緩解距離基站較遠(yuǎn)的簇頭消耗過多能量.在簇的構(gòu)建階段，考慮節(jié)點(diǎn)與基站的距離因素，降低了整個網(wǎng)絡(luò)的能量消耗.與LEACH，SEP，DEEC算法相比，該算法有效均衡了簇頭能量消耗、延長了網(wǎng)絡(luò)壽命.

參考文獻(xiàn)：

[1] SOHRABI K, GAO J, AILAWADHI V, et al. Protocols for self-organization of a wireless sensor network[J]. IEEE Personal Communications, 2000, 7 (5): 16-27.

[2] SIRSIKAR S, WANKHEDE K. Comparison of clustering algorithms to design new clustering approach[C] //International Conference on Advances in Computing, Communication and Control(ICAC3’15), 2015: 147-154.

[3] LIU X X . A typical hierarchical routing protocols for wireless sensor networks: a review[J]. IEEE Sensors Journal, 2015, 15 (10): 5372-5383.

[4] NAM C S, CHO H Y, SHIN D R. Setting up the threshold based on cluster head selection algorithm in wireless sensor networks[C]//IEEE Education Technology and Computer (ICETC), Shanghai, 2010: 22-24.

[5] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communication, 2002, 1 (4): 660-670.

[6] SMARAGDAKIS G, MATTA I, BESTAVROS A. SEP: a stable election protocol for clustered heterogeneous wireless sensor networks[C]//Proceedings of 2nd International Workshop on SANPA, 2004 : 1-11.

[7] 卿利, 朱清新, 王明文. 異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效成簇算法[J]. 軟件學(xué)報, 2006, 17 (3): 481-489.

[8] LIU J J, HU Y J. A balanced and energy-efficient clustering algorithm for heterogeneous wireless sensor networks[C]//IEEE Wireless Communications and Signal Processing (WCSP), Hefei, 2014: 1-6.

[9] YOUNIS O, FAHMY S. HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing, 2004, 3 (4): 660-669.

[10] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Washington, 2005: 597-604.

[11] 李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計算機(jī)學(xué)報, 2007, 30 (1): 27-36.

[12] HEINZELMAN W B, CHANDRANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1 (4): 660-670.