大規(guī)模無線傳感器網(wǎng)絡(luò)環(huán)域多扇區(qū)多跳分簇路由算法*

，

(廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州 510006)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)是由大量傳感器節(jié)點(diǎn)部署在人們所關(guān)心區(qū)域，能夠在一些苛刻的環(huán)境下正常工作[1]，在多個(gè)領(lǐng)域得到廣泛應(yīng)用。節(jié)點(diǎn)能量、計(jì)算和存儲(chǔ)能力受限，除了最大化傳感器節(jié)點(diǎn)壽命外，首選均衡整個(gè)網(wǎng)絡(luò)能量消耗,最大限度提高整個(gè)網(wǎng)絡(luò)性能[2]。

根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，WSNs中路由可分為兩類：層次路由和平面路由[3]，層次路由比平面路由能量更高效、擴(kuò)展性更好。為了避免文獻(xiàn)[4]中LEACH隨機(jī)選取簇頭，存在著剩余能量較低節(jié)點(diǎn)當(dāng)選簇頭和遠(yuǎn)距離簇頭與基站直接能耗過高問題，文獻(xiàn)[5]提出E-LEACH算法，主要考慮了節(jié)點(diǎn)能量和數(shù)據(jù)發(fā)送消耗能量優(yōu)化簇頭選舉，每輪的時(shí)間依賴最優(yōu)簇規(guī)模而變化，簇頭由最小生成樹發(fā)送數(shù)據(jù)到基站，剩余能量最大的簇頭作根節(jié)點(diǎn)。文獻(xiàn)[6]的EOMC算法通過建立網(wǎng)絡(luò)能耗優(yōu)化模型，按最優(yōu)簇頭數(shù)分簇，并結(jié)合功率控制限制候選簇頭選舉環(huán)帶寬度，使產(chǎn)生的簇頭分布均衡，分簇時(shí)考慮節(jié)點(diǎn)剩余能量，以均衡節(jié)點(diǎn)能耗，達(dá)到延長網(wǎng)絡(luò)壽命的目的。其最優(yōu)分簇個(gè)數(shù)，各環(huán)內(nèi)構(gòu)建規(guī)模不同的簇以克服網(wǎng)絡(luò)中的“熱點(diǎn)”問題，但是每輪都進(jìn)行簇頭選舉存在開銷過大，而文獻(xiàn)[8]提出一種基于最優(yōu)簇頭個(gè)數(shù)的分環(huán)多跳算法。通過分析一個(gè)簇內(nèi)簇頭對(duì)簇內(nèi)節(jié)點(diǎn)能量消耗的影響，根據(jù)發(fā)送和中繼數(shù)據(jù)包數(shù)量計(jì)算傳感器網(wǎng)絡(luò)能量消耗，通過計(jì)算能量消耗，得到其網(wǎng)絡(luò)內(nèi)最優(yōu)簇頭個(gè)數(shù)，但是以固定頻率隨機(jī)選取簇頭并不能保證簇頭分布的均衡性。為避免文獻(xiàn)[7]中RBMC每輪都進(jìn)行簇頭選舉能耗過高問題，文獻(xiàn)[8]提出的ERBMC采用多輪機(jī)制簇頭選舉且簇頭選舉時(shí)考慮節(jié)點(diǎn)剩余能量。文獻(xiàn)[8,9]分析簇頭對(duì)簇內(nèi)節(jié)點(diǎn)能耗的影響，確定發(fā)送和中繼數(shù)據(jù)包數(shù)量并計(jì)算網(wǎng)絡(luò)能耗，最后得到網(wǎng)絡(luò)內(nèi)最優(yōu)簇頭個(gè)數(shù)，但是以固定頻率隨機(jī)選取簇頭并不能保證簇的均衡分布。文獻(xiàn)[10]提出CEBCRA,簇頭選舉考慮剩余能量和節(jié)點(diǎn)分布密度；節(jié)點(diǎn)根據(jù)簇頭消耗代價(jià)選擇入簇；簇頭根據(jù)自己到基站經(jīng)不同路徑時(shí)的能耗代價(jià)，選取能耗最優(yōu)的中繼簇頭，降低通信能量消耗。

上文提到的算法對(duì)簇頭選舉進(jìn)行改進(jìn)，簇頭選舉考慮節(jié)點(diǎn)分布，剩余能量；計(jì)算得到網(wǎng)絡(luò)內(nèi)能量消耗最低時(shí)最優(yōu)簇頭數(shù)，取得了一定效果。但實(shí)際中節(jié)點(diǎn)常常隨機(jī)分布，統(tǒng)一分簇并不能有效解決簇頭分布不合理造成能耗不均衡的問題。因此，本文提出一種環(huán)域多扇區(qū)多跳分簇路由(MMCR)算法。

1 系統(tǒng)模型

1.1 能耗模型

本文采用和文獻(xiàn)[9]相同的能耗模型。節(jié)點(diǎn)發(fā)送k位數(shù)據(jù)到距離為d的地方，能量消耗公式如下

(1)

接收k位數(shù)據(jù)能量消耗為

ERX=k×Eele,

(2)

(3)

式中k為傳輸數(shù)據(jù)包含兩進(jìn)制數(shù)的位數(shù)，d為節(jié)點(diǎn)發(fā)送距離。當(dāng)節(jié)點(diǎn)發(fā)送距離小于閾值d0時(shí)，采用自由空間模式，功率放大損系數(shù)為εfs；否則，采用多路徑衰減模式，功率放大系數(shù)為εamp。

由式(1)、式(2)看出數(shù)據(jù)發(fā)送比接收消耗能量更多，能量消耗與距離的指數(shù)關(guān)系呈正比，因此，應(yīng)避免過遠(yuǎn)距離的傳輸造成能量消耗代價(jià)過高。

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

N個(gè)同構(gòu)節(jié)點(diǎn)隨機(jī)分布半徑為R基站為中心的圓形區(qū)域，如圖1。

圖1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)劃分為基站為中心分為等間距D的K個(gè)同心圓，其中，R=D×K，由基站向外依次為1,2，…，j(j

(4)

具體計(jì)算過程見文獻(xiàn)[7]，進(jìn)而推到得到任意環(huán)消耗能量最少時(shí)最優(yōu)分簇個(gè)數(shù)

(5)

2 MMCR算法

MMCR算法根據(jù)分環(huán)后各環(huán)能量消耗最低時(shí)候的最優(yōu)分簇個(gè)數(shù)，各環(huán)根據(jù)最優(yōu)分簇個(gè)數(shù)對(duì)環(huán)域進(jìn)行多扇區(qū)劃分、采用多輪旋轉(zhuǎn)機(jī)制選擇簇頭，簇頭選舉考慮剩余能量、與基站距離因素。

MMCR算法分為3個(gè)階段：環(huán)域多扇區(qū)劃分、簇頭選舉、穩(wěn)定階段。

2.1 環(huán)域扇區(qū)劃分

由于LEACH,E-LEACH算法通過隨機(jī)選舉簇頭，存在著網(wǎng)絡(luò)區(qū)域內(nèi)簇頭數(shù)目和簇頭位置不確定的問題，尤其當(dāng)網(wǎng)絡(luò)規(guī)模較大的時(shí)候，LEACH,E-LEACH簇頭個(gè)數(shù)、位置隨機(jī)地讓有的區(qū)域簇頭分布過于密集，而有的區(qū)域簇頭過于稀疏，導(dǎo)致網(wǎng)絡(luò)消耗能量不均衡。

針對(duì)LEACH,E-LEACH出現(xiàn)的不足，尤其網(wǎng)絡(luò)規(guī)模較大時(shí)更為突出。RBMC,ERBMC算法對(duì)網(wǎng)絡(luò)進(jìn)行分環(huán)，在更小的環(huán)域內(nèi)通過計(jì)算得到其能耗代價(jià)最低時(shí)每環(huán)分簇個(gè)數(shù)，確定了各環(huán)內(nèi)分簇個(gè)數(shù)，即保證了整個(gè)網(wǎng)絡(luò)內(nèi)的分簇?cái)?shù)量，同時(shí)簇頭選舉限制于每個(gè)環(huán)域內(nèi)，在規(guī)模較大的網(wǎng)絡(luò)中使簇頭分布更加均衡。

通過上面幾種算法特點(diǎn)分析，由上節(jié)對(duì)各環(huán)能量消耗最低時(shí)得到最優(yōu)分簇個(gè)數(shù)，對(duì)于任意第j環(huán)最優(yōu)簇分簇個(gè)數(shù)為Mj，可根據(jù)公式(5)計(jì)算得到。對(duì)于任意第j環(huán)最優(yōu)分簇個(gè)數(shù)為Mj，第j環(huán)被分為以基站為中心的Mj個(gè)圓心角度都為θ=2π/Mj的扇區(qū)，各環(huán)的扇區(qū)劃分相互獨(dú)立，互不影響。這樣，根據(jù)分環(huán)多跳模型每環(huán)消耗能量最低時(shí)得到的最優(yōu)分簇個(gè)數(shù)，把分環(huán)后網(wǎng)絡(luò)區(qū)域里面每個(gè)環(huán)域里面進(jìn)行扇區(qū)劃分，每個(gè)扇區(qū)作為一個(gè)簇。通過這樣的辦法不僅保證的簇分布的均衡性，而且簇頭只在環(huán)域的扇區(qū)內(nèi)內(nèi)選舉，確保了簇頭分布的均衡，進(jìn)而使整個(gè)網(wǎng)絡(luò)消耗能量均衡。

2.2 多輪旋轉(zhuǎn)機(jī)制選舉簇頭

由于簇的規(guī)模不同，簇頭距離基站距離，需要收集轉(zhuǎn)發(fā)簇內(nèi)成員信息量不同，同時(shí)還對(duì)其他簇頭轉(zhuǎn)發(fā)來的數(shù)據(jù)融合處理并轉(zhuǎn)發(fā)，導(dǎo)致每輪結(jié)束后個(gè)簇頭能量消耗出現(xiàn)較大差異。合理地選舉簇頭可以更好地均衡網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能量消耗，降低網(wǎng)絡(luò)通信能量消耗，延長網(wǎng)絡(luò)生命周期。

簇頭選舉綜合節(jié)點(diǎn)剩余能量、基站距離2個(gè)參數(shù)。根據(jù)權(quán)重最高的節(jié)點(diǎn)當(dāng)選簇頭，即剩余能量大、距離基站近的節(jié)點(diǎn)當(dāng)選簇頭概率大，若不止一個(gè)節(jié)點(diǎn)滿足，則選舉ID較小者，權(quán)重公式如下

(6)

式中Eres,Eini,dBS(i),R分別為當(dāng)前節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)初始能量、節(jié)點(diǎn)距基站距離、網(wǎng)絡(luò)區(qū)域半徑；影響因子α與節(jié)點(diǎn)性質(zhì)相關(guān)的常數(shù)。

每個(gè)環(huán)域的各個(gè)扇區(qū)(簇)內(nèi)簇頭選擇完成后，簇頭發(fā)出廣播信息CH_MSG_AD告知扇區(qū)內(nèi)成員節(jié)點(diǎn)自己成為簇頭，所有的扇區(qū)內(nèi)成員節(jié)點(diǎn)接收到該信息后，自動(dòng)默認(rèn)扇區(qū)劃分為它們所在的簇。接下來的過程中按照時(shí)分多址(time division multiple access,TDMA)各自所分配時(shí)隙，將自己感知信息和能量信息發(fā)送簇頭，其它未輪到的成員節(jié)點(diǎn)保持工作在睡眠狀態(tài)，降低節(jié)點(diǎn)能量消耗。由于計(jì)算消耗能量遠(yuǎn)遠(yuǎn)小于通信能量消耗，簇頭只把節(jié)點(diǎn)感知信息發(fā)送至基站并不發(fā)送節(jié)點(diǎn)能量信息，簇頭計(jì)算其簇內(nèi)所有節(jié)點(diǎn)的平均能量，根據(jù)其平均能量和當(dāng)前簇頭剩余能量關(guān)系，為下一輪簇頭選舉做準(zhǔn)備。

任意環(huán)中任意扇區(qū)內(nèi)，如果簇頭能量低于其劃分扇區(qū)的簇內(nèi)平均能量，則進(jìn)行新一輪簇頭選舉。各環(huán)區(qū)域劃分扇區(qū)相互獨(dú)立，即分簇相互獨(dú)立，任意環(huán)簇頭選舉也互不影響。如圖1所示，對(duì)于任意第j環(huán)中以基站為中心的圓心角為θ=2π/Mj的扇區(qū)CDEF這時(shí)第j環(huán)候以一個(gè)角度θ/n進(jìn)行逆時(shí)針繞基站旋轉(zhuǎn)到C′D′E′F′，通過n次旋轉(zhuǎn)第j環(huán)完成一個(gè)周期回到初始位置，這樣就實(shí)現(xiàn)了多選旋轉(zhuǎn)機(jī)制的簇頭選舉。通過計(jì)算各個(gè)扇區(qū)內(nèi)平均能量，如果扇區(qū)內(nèi)簇頭能量高于平均能量，則繼續(xù)擔(dān)任簇頭，降低了每次都要選舉簇頭能量開銷。只有當(dāng)簇頭能量低于其扇區(qū)內(nèi)能量時(shí)才通過逆時(shí)針旋轉(zhuǎn)改變環(huán)域扇區(qū)的劃分，對(duì)其所在環(huán)內(nèi)進(jìn)行新一輪的簇頭選舉，避免了整個(gè)網(wǎng)絡(luò)大規(guī)模簇頭選舉節(jié)點(diǎn)能量消耗過高的問題。

2.3 穩(wěn)定階段

簇頭選舉完成，由于對(duì)每個(gè)環(huán)域內(nèi)多扇區(qū)分簇，簇規(guī)模較小，簇內(nèi)成員節(jié)點(diǎn)采用單跳方式與簇頭通信更加高效，但是對(duì)于規(guī)模較大網(wǎng)絡(luò)，距離較遠(yuǎn)簇頭無法直接與基站通信或者通信代價(jià)過高，除第一環(huán)外，其它環(huán)顯然采用多跳更為合理。為避免傳統(tǒng)多跳選取距離自己向基站方向最近的簇頭作為中繼節(jié)點(diǎn)可能發(fā)生“纏繞”問題，如圖1中節(jié)點(diǎn)S—B—BS路徑。j環(huán)簇頭結(jié)點(diǎn)集合為Nk{k|k=1,2,…,Mj}，第(j+1)環(huán)簇頭可根據(jù)下式選擇j環(huán)中繼簇頭

d=d2(k,Nk)+d2(Nk,BS),

(7)

式中d2(k,Nk)，d2(Nk,BS)分別為(j+1)環(huán)節(jié)點(diǎn)到j(luò)環(huán)簇頭Nk距離和Nk到基站距離。(j+1)環(huán)簇頭選擇距離權(quán)值d最小的j環(huán)簇頭為下一跳中繼節(jié)點(diǎn)，并且限制多跳次數(shù)小于j。

3 仿真分析

仿真實(shí)驗(yàn)中將8 000個(gè)節(jié)點(diǎn)隨機(jī)分布在半徑720 m區(qū)域，K=9，D=80 m。本文將MMCR與LEACH,E-LEACH,ERBMC在Matlab 2010進(jìn)行仿真，仿真參數(shù)：初始節(jié)點(diǎn)能量為1 J；數(shù)據(jù)融合能耗為50 pJ/bit；數(shù)據(jù)包大小為500 bit；Eele為50 nJ/bit；εfs為10 pJ/bit/m4；εamp為0.001 3 pJ/bit/m2；α為0.7；n為4。

對(duì)于MMCR和LEACH,E-LEAC,ERBMC剩余能量總量、存活節(jié)點(diǎn)數(shù)隨輪數(shù)變化的情況分別如圖2和圖3所示。

圖2 剩余能量總量與輪數(shù)關(guān)系

從圖2明顯看出:在輪數(shù)相同時(shí)，MMCR的剩余能量總量要高于LEACH,ERBMC,E-LEACH，其中能量消耗為初始總能量50%時(shí)，LEACH,ERBMC,E-LEACH,MMCR運(yùn)行輪數(shù)分別為357,673,467,802輪，可見MMCR對(duì)于整個(gè)網(wǎng)絡(luò)能量利用率更高。因?yàn)橥ㄐ拍芰肯恼季W(wǎng)絡(luò)內(nèi)能量消耗比例較大，通信中發(fā)送信息能量消耗是主要部分，發(fā)送能量消耗主要依賴于發(fā)送距離，這里采用均衡分簇和多輪旋轉(zhuǎn)機(jī)制簇頭選舉均衡了簇的分布，降低了各網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的通信能耗，在各環(huán)域內(nèi)劃分根據(jù)最優(yōu)簇頭數(shù)劃分了多扇區(qū)，從扇區(qū)內(nèi)、環(huán)內(nèi)均衡能耗從而均衡整個(gè)網(wǎng)絡(luò)的能耗均衡，提高了網(wǎng)絡(luò)能量利用率。

圖3 存活節(jié)點(diǎn)數(shù)目與輪數(shù)關(guān)系

圖3可以看到:首個(gè)節(jié)點(diǎn)死亡時(shí)，LEACH，E-LEACH，ERBMC運(yùn)行輪數(shù)分別為387,510,671輪，而MMCR運(yùn)行輪數(shù)為814輪；節(jié)點(diǎn)死亡50%時(shí)候，LEACH，ERBMC，E-LEACH，MMCR運(yùn)行輪數(shù)分別為628,928,841,1153；節(jié)點(diǎn)剩余能量總量耗盡時(shí)或節(jié)點(diǎn)全部死亡時(shí)，LEACH,ERBMC,E-LEACH，MMCR分別為1028,1400,1202,1583。明顯看到經(jīng)歷同樣輪數(shù)時(shí)，MMCR存活節(jié)點(diǎn)數(shù)、穩(wěn)定性均優(yōu)于LEACH，ERBMC，E-LEACH，尤其網(wǎng)絡(luò)規(guī)模較大時(shí)候，MMCR優(yōu)勢更為明顯。

圖4所示為4種算法的基站接收數(shù)據(jù)總量與輪數(shù)之間關(guān)系，明顯看出：MMCR在向基站數(shù)據(jù)發(fā)送時(shí)比LEACH,E-LEACH,EMBCR更為高效，由于對(duì)網(wǎng)絡(luò)進(jìn)行多扇區(qū)分簇、保證了簇的均衡形成、簇的規(guī)模更優(yōu)化、簇頭的分布更加均衡，從而提高了網(wǎng)絡(luò)內(nèi)基站接收數(shù)據(jù)總量。

圖4 基站接收數(shù)據(jù)量與輪數(shù)關(guān)系

4 結(jié) 論

本文對(duì)LEACH,E-LEACH,ERBMC等路由算法進(jìn)行分析研究，然后提出MMCR算法：對(duì)網(wǎng)絡(luò)進(jìn)行分環(huán)，依據(jù)各環(huán)能量消耗最低時(shí)得到最優(yōu)簇頭數(shù)Mj，對(duì)各環(huán)進(jìn)行扇區(qū)劃分,即分簇；每扇區(qū)內(nèi)根據(jù)能量和距離產(chǎn)生簇頭，由簇頭計(jì)算扇區(qū)平均能量按照多輪旋轉(zhuǎn)機(jī)制選舉；簇內(nèi)單跳，簇間根據(jù)距離權(quán)值選擇下一跳中繼簇頭，單跳、多跳相結(jié)合與基站通信，均衡了節(jié)點(diǎn)能耗，降低網(wǎng)絡(luò)內(nèi)通信能耗，延長了網(wǎng)絡(luò)壽命。實(shí)驗(yàn)證明:MMCR算法均衡了網(wǎng)絡(luò)能耗，在能量利用率、網(wǎng)絡(luò)壽命方面要優(yōu)于LEACH,E-LEACH,ERBMC，同時(shí)數(shù)據(jù)發(fā)送效率也獲得較好效果。

參考文獻(xiàn):

[1] Patel H,Pandya N.Study and review of routing protocols for wire-

less sensor networks[J].International Journal of Engineering,2013,2(1):1-7.

[2] Singh S K,Singh M P,Singh D K.A survey of energy-efficient hierarchical cluster-based routing in wireless sensor network-s[J].International Journal of Advanced Networking and Application (IJANA),2010,2(2):570-580.

[3] Manap Z,Ali B M,Ng C K,et al.A review on hierarchical routing protocols for wireless sensor networks[J].wireless Personal Communications,2013(2):1-28.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor network-s[C]∥Proceedings of the 33rd IEEE Annual Hawaii International Conference on System Sciences, 2000:10.

[5] Xu J,Jin N,Lou X,et al.Improvement of LEACH protocol for WSN[C]∥2012 The 9th IEEE International Conference on Fuzzy Systems and Knowledge Discovery (FSKD),2012:2174-2177.

[6] 易 軍,石為人,許 磊.基于能量優(yōu)化模型的無線傳感器網(wǎng)絡(luò)分簇算法[J].高技術(shù)通訊,2010 (2):157-162.

[7] 劉 志,裘正定.基于分環(huán)多跳的無線傳感網(wǎng)分簇路由算法[J].通信學(xué)報(bào),2008,29(3):104-113.

[8] Ren Z,Chen Y,Yao Y,et al.Energy-efficient ring-based multi-hop clustering routing for WSNs[C]∥2012 IEEE Fifth International Symposium on Computational Intelligence and Design (ISCID),2012:14-17.

[9] Nam C S,Han Y S,Shin D R.Multi-hop routing-based optimization of the number of cluster-heads in wireless sensor network-s[J].Sensors,2011,11(3):2875-2884.

[10] Kuila P,Jana P K.An energy balanced distributed clustering and routing algorithm for wireless sensor networks[C]∥2012 IEEE 2nd International Conference on Parallel Distributed and Grid Computing (PDGC),2012:220-225.