，

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

0 引 言

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

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

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

1 系統(tǒng)模型

1.1 能耗模型

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

(1)

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

ERX=k×Eele,

(2)

(3)

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

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

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

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

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

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

(4)

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

(5)

2 MMCR算法

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

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

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

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

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

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

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

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

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

(6)

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

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

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

2.3 穩(wěn)定階段

簇頭選舉完成，由于對每個環(huán)域內(nèi)多扇區(qū)分簇，簇規(guī)模較小，簇內(nèi)成員節(jié)點采用單跳方式與簇頭通信更加高效，但是對于規(guī)模較大網(wǎng)絡(luò)，距離較遠簇頭無法直接與基站通信或者通信代價過高，除第一環(huán)外，其它環(huán)顯然采用多跳更為合理。為避免傳統(tǒng)多跳選取距離自己向基站方向最近的簇頭作為中繼節(jié)點可能發(fā)生“纏繞”問題，如圖1中節(jié)點S—B—BS路徑。j環(huán)簇頭結(jié)點集合為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é)點到j(luò)環(huán)簇頭Nk距離和Nk到基站距離。(j+1)環(huán)簇頭選擇距離權(quán)值d最小的j環(huán)簇頭為下一跳中繼節(jié)點，并且限制多跳次數(shù)小于j。

3 仿真分析

仿真實驗中將8 000個節(jié)點隨機分布在半徑720 m區(qū)域，K=9，D=80 m。本文將MMCR與LEACH,E-LEACH,ERBMC在Matlab 2010進行仿真，仿真參數(shù)：初始節(jié)點能量為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。

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻:

[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é)報,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.