無線傳感器網絡中面向動態多跳的非均勻分簇路由

李超良 ，胡春華

(1. 湖南商學院 計算機與電子工程學院，湖南 長沙，410205;2. 中南大學 信息科學與工程學院，湖南 長沙，410083)

隨著微型傳感器技術、無線通信技術以及嵌入式計算技術的發展，無線傳感器網絡現已得到越來越廣泛的關注[1-2]。無線傳感器網絡是由大量廉價的微型傳感器節點組成的無線自組織網絡。每個傳感器節點通常由傳感單元、計算單元、無線通信單元和存儲單元等構成。無線傳感器網絡可以使人們在任何時間、任何地點和任何環境下獲取大量詳實、可靠的信息，應

用于國防、環境監測、交通管理、醫療衛生、制造業、反恐、抗災等許多領域。路由是無線傳感器網絡的關鍵技術之一，目前，無線傳感器網絡中的路由協議主要可以分為3類：以數據為中心的路由協議、層次式路由協議、基于位置的路由協議[3]。以數據為中心的路由協議主要包括以下幾種：Leach-E[4]，Rumor[5]，Cadr[6]和Acquire[7]等。層次型路由協議主要包括Dbs[8]。還有一些獨立發展的層次路由協議[9-10]，如RCR[11]，Sop[12]，Hmrp[13]，Ehrp[14]，Lrp[15]和 RESEE[16]等。層次式路由協議與單層的路由協議相比具有更好的可擴展性，更易于進行數據之間的融合，從而減少網絡中能量的消耗，提高網絡的生存周期?；谖恢玫穆酚蓞f議主要有M&S[17]和Dgr[18]等。由于有位置信息，根據這些信息計算節點之間的距離，預先估計節點能量的消耗情況，從而構建更加高效的路由協議，有利于網絡生命周期的延長。LEACH協議是最早出現的一種分簇路由算法，它的執行過程是周期性地循環進行，每輪循環分為2個階段，即簇的建立階段和穩定的數據通信階段。LEACH通過隨機地選擇簇頭，平均分擔中繼通信業務，網絡生命周期有所延長，但它仍然存在一些缺陷：(1) 節點等概率地擔當簇頭的這種簇頭選擇機制，沒有充分地考慮節點能量的使用情況及剩余能量，也沒有考慮節點的地理位置；(2) 在向匯聚節點的數據傳輸過程中，所有簇頭都是直接向匯聚節點進行發送，這樣簇頭消耗的能量很大，容易導致網絡分割。基于以上這些缺點，Heinzelman等[19]在LEACH協議的基礎上加以改進提出了基于匯聚節點控制的協議LEACH-C。通過對分簇方案進行改進，延長網絡生命周期。但該方案也存在簇頭產生方式開銷較大、算法不夠健壯等缺點。傳感器網絡運行中不是所有節點消耗的能量都相同，在每一輪中每個簇的簇頭消耗的能量是最多的，若簇頭可以根據節點的能量消耗而不是隨機地選擇進行動態調整形成非均勻的簇，則可以均衡簇之間的能量消耗，延長整個網絡的生存時間。李成法等[20]提出了一種非均勻分簇的網絡路由協議，靠近匯聚節點的簇較小，而遠離匯聚節點的簇則較大。簇頭除了發送本簇中的節點收集的數據外，還需為其他的簇頭轉發信息，采用這種方式，在一定程度上可以延長網絡的生存周期。但該文獻中每個簇的競爭半徑是固定的，而事實上，某些靠近匯聚節點的簇頭可能會由于轉發過多的簇間信息而耗盡能量，導致網絡失效?；谏鲜隹紤]，本文作者提出一種多跳模式下的動態非均勻分簇路由協議(Dynamic non-uniform clustering routing protocol, DNCRP)。DNCRP算法在簇內采用單跳方式通信，而在簇間采用多跳通信，由簇頭向匯聚節點轉發信息。在網絡運行過程中，根據網絡的能量狀況，動態地選舉簇頭，自適應地根據網絡中簇的能量狀況改變簇的大小，這樣就可以在整個網絡中均衡節點能量，而不只是在簇中均衡節點的能量消耗。由于充分利用了整個網絡中所有節點的能量，所以，可以大幅度延長傳感器網絡生命周期。

1 系統模型

1.1 網絡結構模型

對網絡模型進行較通用的假設：

(1) 傳感器網絡部署之后,節點都不移動；

(2) 節點同構，初始能量相同；

(3) 匯聚節點位于離傳感器網絡較遠的區域，某些簇中的數據需要靠近匯聚節點的簇頭通過多跳才能提交信息；

(4) 傳感器節點的發射功率可以進行調節；

(5) 簇頭可以根據節點能量動態地進行選??；

(6) 簇的大小可以根據能量狀況自適應、動態地調整。

1.2 能量消耗模型

在分析傳感器節點的能量消耗時，采用如圖1所示的無線傳輸能量消耗模型(REDM)[21]。

無線傳感器網絡中的節點經過分簇以后，形成了多個大小不一的簇，簇內的節點與簇頭通過單跳方式進行通信，而遠離匯聚節點的簇則需要通過多個簇頭經過多跳之后才能向匯聚節點傳遞信息，這樣，靠近匯聚節點的簇頭就有可能由于轉發過多的數據而過早死亡，從而導致整個網絡不可用。本文采取一種動態非均勻的分簇方式來克服上述問題：一方面，在簇中選擇能量最大的節點充當簇頭；另一方面，根據簇頭的能量消耗情況動態地調整簇的大小，能量消耗較小的簇頭所在的簇較大，而能量消耗較多的簇則較小。實驗表明，采用該方法后，網絡的生存時間明顯延長。

這樣的網絡具有以下2個主要特征：

(1) 在網絡分簇過程中，離匯聚節點較近的簇劃分得較小(轉發數據較多、任務較重)，而遠離匯聚節點的簇則可以劃分得較大(轉發數據較少、任務較輕)。

(2) 隨著網絡的運行，簇的大小、簇頭的選取可以自適應地根據簇頭能量的消耗情況實時地調整，以實現整個網絡生命周期的最大化。

圖1 無線傳輸能量模型Fig.1 Energy model of wireless transmission

2 DNCRP路由算法

2.1 簇頭選取

在網絡部署時，由于節點的初始能量是相同的，所以，對于首輪中簇頭的選取采用LEACH 協議隨機地產生簇頭，再根據簇頭離匯聚節點的遠近產生非均勻的簇，離匯聚節點近的簇劃分得較小，而遠離匯聚節點的簇則較大。

2.2 簇的形成

每一輪中，當某個節點當選簇頭之后，就在本簇內廣播一個hello消息，該消息中包含閾值LT，用于確定簇的大小。第1輪的LT固定，設定為LT=6。每個簇中的節點收到該廣播消息就保存，然后，將該閾值減小1后傳給下其鄰居節點，如此循環，直到閾值減少至0為止。若在成簇過程中節點收到多個消息，則只保存第1次的值作為本節點與簇頭的距離。

2.3 下一輪簇頭的選取

第1輪的簇的大小由LT決定。從第2輪開始，每個簇中的簇頭由該簇中能量最高的節點擔任，而簇的大小則根據簇頭的能量消耗情況自動地進行調整。

簇頭的能量消耗 EC主要包括處理數據消耗的能量ED和通信消耗的能量EP。而通信消耗能量EP包含節點接收數據消耗的能量ER和傳輸數據能量ET。

為了準確地描述簇，根據簇頭的剩余能量自動調整簇的大小的過程，給出如下簇頭剩余能量因子 ρ，用于描述節點的能量消耗情況，作為下一輪簇大小調整的依據。

其中：EOC為節點的初始能量；EC為節點已經消耗的能量。

節點的能量因子ρ包含在交換的消息中。當節點接收其他節點的數據時，將其中的ρ存儲下來，并更新ρ表格。在每一輪的簇形成階段，當選簇頭會將本節點的ρ與它的一跳鄰居節點的ρ比較，若簇頭節點的ρ最小，則說明節點在上一輪網絡運行中消耗的能量較小，在下一輪中可以增大簇的范圍，即將LT增大；反之，若簇頭的ρ最大，則表示在上一輪中簇頭消耗的能量較小，減小簇的范圍，即LT減小。通過這樣的簇頭篩選方法以及簇的半徑動態調整機制，使得每個簇中簇頭的能量是最大的，這樣可以確保簇既能收集本簇中其他節點的信息，也能轉發其他簇頭的信息。網絡運行后，有的簇可能比較大，有的簇可能比較小，這是符合網絡運行的實際情況的。因為網絡運行中節點收集信息量是隨機的，并不一定完全均勻，有些熱點地區數據可能比較多，相應地消耗的簇頭能量也比較多，而有些地區就比較少。為了有效地提高網絡的生存時間，網絡在轉發信息時應該根據簇頭節點能量來選擇路徑，而不僅僅是嚴格按照簇頭離匯聚節點的遠近來進行信息轉發。在這樣的簇頭及簇半徑的形成機制下，在網絡運行的下一輪選舉中，轉發數據較多的節點周圍自然會形成較小的簇，而轉發數據較少的簇頭周圍相應地就會形成一個比較大的簇，半徑較小的簇在本輪中會轉發較少的信息，而半徑較大的簇則會轉發較多的信息，于是，簇的大小會隨著簇能量的大小而呈現一種“大小相間”變化的趨勢，充分利用整個網絡中每個節點的能量，從而最大限度地利用節點的剩余能量，延長網絡的生命周期。

2.4 算法描述

算法的偽代碼如下：

① LT=6；/*設定簇的最大跳數閾值為6*/

② while(LT≠0) /*第1輪分簇*/

{

③ Broadcast(“hello”);/*簇頭節點向周圍節點廣播*/

④ Receive(node_Msg); /*接收信息存儲在自己的鄰表NT[ ]中，這些節點構成1個簇*/

⑤ if (Nd.LT＜hello.LT) /*如果節點收到的閾值大于自身的閾值*/

{

⑥ Nd.LT=hello.LT； /*將收到的閾值存儲為自身的閾值*/

⑦ LT=LT-1； /*將消息的閾值減小1*/

}}

⑧ while(ND. ρ＜NT[].P) /*開始簇大小的動態調整，將p與其鄰居的p比較*/

⑨ LT=LT+1; /*如果簇頭p小于其鄰居的p，將LT的值增大1，擴大簇的范圍*/

⑩ else LT=LT-1;/*否則，不作調整*/

3 仿真及性能分析

對所提出的模型采用 OPNET進行仿真實驗，具體的實驗參數如表1所示。如果節點的剩余能量小于或等于 10-4J，則節點宣布死亡。節點的最大通信半徑為100 m，每個數據包長度為100 byte。

表1 實驗參數設置表Table 1 Experimental parameters table

將文中提出的動態多跳非均勻分簇機制(DNCRP)應用在LEACH和HEED上，分別比較對固定簇、單跳簇和動態多跳非均勻分簇(DNCRP) 3種方式對LEACH和HEED協議的性能的影響。

single(單跳模式)、fixed(固定模式)、DNCRP(動態非均勻分簇模式) 3種不同機制與LEACH結合后的網絡生存時間和節點數的關系如圖2所示。

從圖2可以看出：多跳模式(固定模式和動態非均勻分簇模式)的網絡生存時間多于單挑模式下的網絡生存時間，大約多40%。這主要是因為在單跳模式下，簇頭的數量較多，每次交互信息時廣播次數和應答次數也較多，導致節點能量消耗較多，因此，網絡生存時間是最短的。LEACH-fixed模式的生存時間要比LEACH-DNCRP模式下的網絡生存時間大約低10%。其主要原因在于后者在選擇簇頭時每次選擇的是簇中能量最大的節點，并且在每輪中簇頭會根據能量的多少動態地調整簇的大小。如果能量較多，就擴大簇的半徑，反之，就縮小簇的半徑，這樣就使得能量在整個監測區域內得到均衡，最大限度地利用所有節點的能量，從而使得網絡的生命周期得到最大限度地延長。

圖2 LEACH結合不同機制的生存時間比較Fig.2 Comparison of survival time in network based on LEACH combining different mechanisms

單跳模式、固定模式、非均衡分簇模式與HEED結合后的網絡生存時間和節點數的關系如圖3所示。

從圖3可以看出：在多跳模式(固定模式和動態非均勻分簇模式)下，網絡生存時間都要長于單跳模式，而動態非均勻分簇同HEED結合后，網絡的生存時間是最長的。主要原因如下：在單跳模式下，簇頭在網絡運行時，需要發送和接收數據的次數較多，從而消耗了節點較多的能量，網絡的生命周期也縮短很多。而在多跳模式下(包括多跳和動態非均勻分簇)，節點的能量能在網絡監測區域較大范圍內得到均衡，在一定程度上延長了網絡的生存周期。

圖3 HEED在3種模式下生存時間比較Fig.3 Comparison of survival time in network based on HEED combining three mechanisms

從上述2個實驗結果可以看出：動態非均勻分簇機制能夠均衡整個網絡的能量消耗，延長網絡的生存時間。

固定模式(fixed)、動態非均勻分簇模式與 2種典型的算法LEACH和HEED相結合后，網絡生存時間性能的對比情況如圖4所示。

從圖4可以看出：動態非均勻分簇模式(DNCRP)與兩者結合可以最大程度地延長網絡的生存時間；此外，由于HEED本身的性能要優于LEACH的性能；因此，從整體上來說，HEED與2個機制(固定模式和動態非均勻分簇)結合后的性能也要優于LEACH與上述2種模式結合后的網絡性能。

圖4 2種不同模式應用于LEACH和HEED生存時間比較Fig.4 Survival time of network based on two mechanisms applying in LEACH and HEED

在網絡運行過程中，節點剩余能量也能反映系統模式的性能。圖5所示為2種狀態即固定模式和動態非均勻分簇模式與HEED進行結合后，節點剩余能量的變化情況。

從圖5可以看出：隨著網絡的運行，網絡中節點的能量在不斷地減少，節點的失效率也在不斷地增加，HEED-fixed協議和HEED-DNCRP協議的節點失效率也隨著增加；當運行時間達到20 s左右時，HEED-fixed模式的節點失效率將近17%，而HEED-DNCRP模式的節點失效率為14%左右；而當運行時間為60 s時，HEED-fixed模式的節點失效率為 40%左右，HEEDDNCRP模式的節點失效率為35%；隨著運行時間的延長，采用動態非均勻分簇協議的節點失效率總是比固定模式下的節點失效率要低。可見：動態非均勻分簇協議的節能效果優于固定模式以及單跳模式的節能效果。

圖5 節點失效比率與運行時間關系Fig.5 Relationship between node disability rate and run-time

從上述幾種典型的路由協議與LEACH和HEED 2種模式相結合后的節能效果以及網絡生存時間的比較可以看出：動態非均勻分簇協議具有較好的性能。

4 結論

(1) 采用動態、非均勻的分簇路由方式，提出了一種自適應的DNCRP算法，與傳統的一些算法相比，網絡的能量消耗大幅度降低，網絡的生存時間有較大提高。

(2) 本研究所提出的策略協作能從網絡的整體來平衡節點的能量，充分利用了每一個節點的剩余能量。這也是 DNCRP協議具有較好的節能效果的直接原因。

(3) 由于算法預置了一些參數如網絡監測范圍、節點初始能量、簇閾值，這些參數的設置具有一定經驗性，如何優化這些配置參數以提高網絡性能，一方面需要從理論上進行系統研究，另一方面也需要更精確的模擬測試。這有待于進一步研究。

[1] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[2] 孫利民, 李建中, 陳渝, 等. 無線傳感器網絡[M]. 北京: 清華大學出版社, 2005: 1-3.SUN Li-min, LI Jian-zhong, CHEN Yu, et al. Wireless sensor networks[M]. Beijing: Tsinghua University Press, 2005: 1-3.

[3] Keremal A, Mohamed Y. A survey on routing protocols for wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(3):325-349.

[4] PENG Duo, ZHANG Qiu-yu. An energy efficient cluster-Routing protocol for wireless sensor networks[C]//Proceedings of the International Conference on Computer Design and Applications. Qinhuangdao, China, 2010: 2530-2533.

[5] Bragomsky D, Estrin D. Rumor routing algorithm for sensor networks[C]//Proceedings of the First Workshop on Sensor Networks and Applications (WSNA). Atlanta, United States,2002: 22-31.

[6] Chu M, Haussecker H, Zhao F. Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks[J]. The International Journal of High Performance Computing Applications, 2002, 16(3): 293-313.

[7] Ssdagopan N. The acquire mechanism for efficient querying in sensor networks[C]//Proceedings of the First International Workshop on Sensor Network Protocol and Applications.Anchorage, USA, 2003: 149-155.

[8] Amini N, Miremadi D, Seyde G, et al. A hierarchical routing protocol for energy load balancing in wireless sensor networks[C]//Proceedings of Canadian Conference on Electrical and Computer Engineering. Vancouver, Canada, 2007:1086-1089.

[9] Youssef M, Younis M, Arisha K. A constrained shortest-path energy-aware routing algorithm for wireless sensor networks[C]//Proceedings of the IEEE Wireless Communication and Networks Conference. Orlando, USA, 2002: 794-799.

[10] Younis M, Munshi P, Al-Shere E. Architecture for efficient monitoring and management of sensor networks[C]//Proceedings of the IFIP/IEEE Workshop on End-to-End Monitoring Techniques and Services. Belfast, Ireland, 2003: 488-502.

[11] 蔡海濱, 琚小明, 曹奇英. 多級能量異構無線傳感器網絡的能量預測和可靠聚簇路由協議[J]. 計算機學報, 2009, 32(12):2393-2402.CAI Hai-bing, JU Xiao-ming, CAO Qi-ying. Energy prediction and reliable clustering routing protocol for multilevel energy heterogeneous wireless sensor networks[J]. Chinese Journal of Computers, 2009, 32(12): 2393-2402.

[12] Younis M, Youssef M, Arisha K. Energy-aware routing in cluster-based sensor networks[C]//Proceedings of the 10th IEEE International Symposium on Modeling, Analysis Simulation of Computer and Telecommunication Systems. Fort Worth, USA,2002: 129-136.

[13] WANG Ying-hong, Tsai C H, HUANG Hui-min. A hierarchy-based multi-path routing protocol for wireless sensor networks[J]. International Journal of Information and Management Sciences, 2008, 19(2): 353-366.

[14] Mollanejad A, Khanli L M, Zeynali M. EHRP: Novel energy-aware hierarchical routing protocol in wireless sensor network[C]//Proceedings of the International Congress on Ultra Modern Telecommunications and Control Systems and Workshops. Moscow, Russia, 2010: 970-975.

[15] Huruiala M, Petre C, Urzoca A. Hierarchical routing protocol based on evolutionary algorithms for wireless sensor networks[C]//Proceedings of 9th RoEduNet IEEE International Conference. Sibiu, Romania, 2010: 387-392.

[16] 李戈陽, 曹陽, 馮浩, 等. 基于節點剩余能量調配的無線傳感器網絡能量均衡路由協議[J]. 中南大學學報: 自然科學版,2009, 40(6): 1642-1648.LI Ge-yang, CAO Yang, FENG Hao, et al. Residual energy scheming based energy equilibrium routing protocol for wireless sensor network[J]. Journal of Central South University: Science and Technology, 2009, 40(6): 1642-1648.

[17] Yan Y, Estrin D, Govindan R. Geographical and energy-aware routing: a recursive data dissemination protocol for wireless sensor networks. UCLA Computer Science Department Technical Report[R]. Cos Angeles, USA, UCLA-CSD TR-O1-0023, 2001.

[18] ZHANG Jian, BAI Yan, LI Yu-kai. A state-free directional geographical routing protocol in dynamic wireless sensor networks[C]//Proceedings of the Second International Intelligent Computation Technology and Automation. Changsha, 2009:430-433.

[19] Heinzelman W. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[20] 李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網絡路由協議[J]. 計算機學報, 2007, 30(1): 27-36.LI Cheng-fa, CHEN Gui-hai, YE Mao, et al. An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Journal of Computer, 2007, 30(1): 27-36.

[21] Oberg l, XU You-zhi. A complete energy dissipation model for wireless sensor networks[C]//Proceedings of the International Conference on Sensor Technologies and Applications. Valencia,Spain, 2007: 531-540.