大規模無線傳感器網絡環域多扇區多跳分簇路由算法*

，

(廣東工業大學 自動化學院，廣東 廣州 510006)

0 引 言

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

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

上文提到的算法對簇頭選舉進行改進，簇頭選舉考慮節點分布，剩余能量；計算得到網絡內能量消耗最低時最優簇頭數，取得了一定效果。但實際中節點常常隨機分布，統一分簇并不能有效解決簇頭分布不合理造成能耗不均衡的問題。因此，本文提出一種環域多扇區多跳分簇路由(MMCR)算法。

1 系統模型

1.1 能耗模型

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

(1)

接收k位數據能量消耗為

ERX=k×Eele,

(2)

(3)

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

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

1.2 網絡模型

N個同構節點隨機分布半徑為R基站為中心的圓形區域，如圖1。

圖1 網絡模型

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

(4)

具體計算過程見文獻[7]，進而推到得到任意環消耗能量最少時最優分簇個數

(5)

2 MMCR算法

MMCR算法根據分環后各環能量消耗最低時候的最優分簇個數，各環根據最優分簇個數對環域進行多扇區劃分、采用多輪旋轉機制選擇簇頭，簇頭選舉考慮剩余能量、與基站距離因素。

MMCR算法分為3個階段：環域多扇區劃分、簇頭選舉、穩定階段。

2.1 環域扇區劃分

由于LEACH,E-LEACH算法通過隨機選舉簇頭，存在著網絡區域內簇頭數目和簇頭位置不確定的問題，尤其當網絡規模較大的時候，LEACH,E-LEACH簇頭個數、位置隨機地讓有的區域簇頭分布過于密集，而有的區域簇頭過于稀疏，導致網絡消耗能量不均衡。

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

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

2.2 多輪旋轉機制選舉簇頭

由于簇的規模不同，簇頭距離基站距離，需要收集轉發簇內成員信息量不同，同時還對其他簇頭轉發來的數據融合處理并轉發，導致每輪結束后個簇頭能量消耗出現較大差異。合理地選舉簇頭可以更好地均衡網絡內節點能量消耗，降低網絡通信能量消耗，延長網絡生命周期。

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

(6)

式中Eres,Eini,dBS(i),R分別為當前節點剩余能量、節點初始能量、節點距基站距離、網絡區域半徑；影響因子α與節點性質相關的常數。

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

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

2.3 穩定階段

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

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

(7)

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

3 仿真分析

仿真實驗中將8 000個節點隨機分布在半徑720 m區域，K=9，D=80 m。本文將MMCR與LEACH,E-LEACH,ERBMC在Matlab 2010進行仿真，仿真參數：初始節點能量為1 J；數據融合能耗為50 pJ/bit；數據包大小為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剩余能量總量、存活節點數隨輪數變化的情況分別如圖2和圖3所示。

圖2 剩余能量總量與輪數關系

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

圖3 存活節點數目與輪數關系

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

圖4所示為4種算法的基站接收數據總量與輪數之間關系，明顯看出：MMCR在向基站數據發送時比LEACH,E-LEACH,EMBCR更為高效，由于對網絡進行多扇區分簇、保證了簇的均衡形成、簇的規模更優化、簇頭的分布更加均衡，從而提高了網絡內基站接收數據總量。

圖4 基站接收數據量與輪數關系

4 結 論

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

參考文獻:

[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] 易 軍,石為人,許 磊.基于能量優化模型的無線傳感器網絡分簇算法[J].高技術通訊,2010 (2):157-162.

[7] 劉 志,裘正定.基于分環多跳的無線傳感網分簇路由算法[J].通信學報,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.