高數據融合的非均勻分簇無線傳感器網絡路由協議

（廣東工業大學 自動化學院，廣州 510006）

摘 要：

探討了基于非均勻分簇的無線傳感器網絡路由協議，提出了一種高數據融合的非均勻分簇無線傳感器網絡路由協議。仿真實驗結果表明，該路由協議有效地平衡了無線傳感器網絡的節點能耗，延長了網絡的存活時間。

關鍵詞：無線傳感器網絡； 路由； 非均勻分簇； 高數據融合

中圖分類號：TP393.04文獻標志碼：A

文章編號：1001-3695(2009)04-1269-03

Highly data fusion unequal clustering routing protocol forwireless sensor networks

LU Xu， CHENG Liang-lun

(College of Automatization， Guangdong University of Technology， Guangzhou 510006， China)

Abstract:

This paper discussed the unequal clustering routing protocol for wireless sensor networks， and then presented a highly data fusion unequal clustering routing protocol for wireless sensor networks. Simulation results show that the routing protocol efficiently balances the energy consumption of nodes in wireless sensor networks， and prolongs the network lifetime.

Key words：wireless sensor networks(WSN); routing; unequal clustering; highly data fusion

0 引言

無線傳感器網絡(WSN)可以定義為部署在監控區域內的大量傳感器節點所組成的無線網絡。該網絡能夠協作地實時監測、采集和處理節點分布區域內的各種環境或監測對象的信息，并將處理后的數據傳送到網絡中的特定位置[1]。其應用前景非常廣闊，可應用于各種布線和電源供給困難的區域、人員不能到達的區域（如受到污染、環境不能被破壞或敵對區域）和一些臨時場合（如發生自然災害時，固定通信網絡被破壞）等[2]。

無線傳感器網絡中傳感器節點的能量資源、計算能力和帶寬都非常有限，而且節點十分密集，設計有效的策略延長網絡的生命周期成為無線傳感器網絡的首要問題[3]。路由協議是網絡節點相互通信的基礎，無線傳感器網絡路由協議負責尋找一條傳輸路徑， 將數據分組從數據源節點通過網絡多跳轉發至目標節點[4]。設計合理的路由協議對降低及平衡網絡中節點的能耗，延長網絡的存活時間有著重要意義。

基于簇的路由協議是目前研究人員比較關注的一類無線傳感器網絡路由協議。在基于簇的路由協議中，網絡被劃分為一些各自獨立的簇。每個簇由一個簇首和多個簇內成員組成。簇首根據一定的算法機制選出，用于管理或控制整個簇內成員節點，協調成員節點之間的工作，負責簇內信息的收集、數據的融合處理和簇間轉發以及最終與網關（sink）通信。簇的建立和簇首的特定任務分配對于整個系統的可擴展性、網絡壽命和能量有效性的提高具有很重要的意義，典型的基于簇的路由協議有LEACH[5]、TEEN[6]、APTEEN[7]、GAF[8]以及HEED[9]等。圖1所示為基于簇的路由協議的拓撲結構。



基于簇的路由協議中，由于簇首距離sink的距離一般較遠，在簇首與sink之間通信時采取多跳的方式（即通過簇首組成的骨干網實現多跳路由）更有利于節約能量[10]。而且采用簇首轉發數據的方法，傳輸鏈路經過的跳數較少，網絡延時也較小。但是當簇首以多跳通信的方式將數據傳輸至sink時，靠近sink的簇首由于轉發大量數據而負載過重，可能過早耗盡能量而失效，這就導致了所謂的熱區問題。

1 EEUC路由協議

能量高效的非均勻分簇（energy-efficient unequal clustering， EEUC）路由協議[11]是一種新穎的無線傳感器網絡路由協議，可以比較好地解決熱區問題。該路由協議利用非均勻的競爭半徑，使靠近sink的簇成員數目相對較小，從而使簇首能夠節約能量以供數據轉發使用，達到均衡簇首能量消耗的目的。

圖2為EEUC路由協議的示意圖。其中大小不等的圓表示簇首節點的大小非均勻的競爭范圍；帶箭頭的線表示簇首間的多跳數據傳輸。

EEUC路由協議的核心是一個能量高效的非均勻分簇算法。該算法是一個分布式的競爭算法，以節點的剩余能量為主要比較依據。

EEUC路由協議的非均勻簇的形成過程如下：

依概率在網絡中選出部分節點成為候選簇首，參與競選。未參與競選的節點進入睡眠狀態，直到簇首競選過程結束。候選簇首根據自身到sink的距離信息計算其競爭區域，區域的半徑記做Rc。假設節點ni為一個候選簇首，則其競爭半徑：

Rc=(1-c(dmax-d(ni，DS))/(dmax-dmin))R0c

其中：dmax和dmin分別為網絡中的節點到sink距離的最大值和最小值；d(ni，DS)為節點ni到sink的距離，算法需要控制競爭半徑的取值范圍；R0c表示候選簇首競爭半徑的最大取值；c是用于控制取值范圍的參數，在0~1取值。簇的成員數目之間的非均勻程度由c決定。R0c和c的優化取值可以優化網絡中節點的能量消耗，延長網絡的存活時間。

競選過程由一個EEUC的簇首競選算法控制。該算法以候選簇首的剩余能量為競爭比較依據。在競選過程中，若候選簇首宣布其競選獲勝，則在該簇首的競爭半徑Rc內的所有候選簇首均不能成為最終簇首，需要退出競選過程。競選算法過程結束之后，之前未參與競選的節點從睡眠狀態喚醒；隨后競選產生的簇首就向全網廣播其競選獲勝的消息；普通節點選擇簇內通信代價最小亦即接收信號強度最大的簇首，發送其加入消息通知該簇首。這樣，網絡中的節點便組成了Voronoi圖結構的簇[12]。

非均勻簇形成之后，在傳輸數據的穩定階段，EEUC路由協議的數據通信分為簇內通信和簇首與sink間的通信兩部分：簇內通信采用單跳的方式，簡單易實現；簇首與sink間通信采用多跳的方式，避免長距離數據傳輸造成能量浪費。文獻[5]中的實驗結果表明，與LEACH等無線傳感器網絡路由協議相比，EEUC路由協議有效地解決了多跳通信方式下簇首能量消耗不均衡的問題，優化了網絡中各節點的能量消耗，顯著地延長了網絡的存活時間。

2 HDF-EEUC路由協議

在文獻[11]中，作者假設數據的冗余度有限，來自不同簇的數據無法進一步融合，中繼簇首節點只是簡單轉發來自其他簇首的數據。于是在EEUC算法中的路由選擇機制中，作者引入一個閾值TD_MAX。若簇首到sink的距離小于TD_MAX，則它直接與sink進行通信；否則就盡量使用多跳路由的方式將數據傳送給sink。

在實際應用中，來自不同簇的數據之間存在大量冗余數據，把這些數據經過融合之后，網絡中傳輸的數據總量將會有一定程度的減小。從圖2可以看出，圖中陰影部分為發送數據到sink的各條路徑之間的冗余數據，這部分數據經過融合與壓縮之后可以有效減少發送到sink的數據總量。本文提出一種高數據融合的非均勻分簇（highly data fusion unequal clustering，HDF-EEUC）無線傳感器網絡路由協議來解決此問題。

HDF-EEUC路由協議中，也將無線傳感器網絡細分為輪，每一輪又分為兩個階段，即簇的建立階段和傳輸數據的穩定階段。在簇的建立階段采用與EEUC路由協議相同的建立非均勻簇的算法，此處不再贅述。在傳輸數據的穩定階段，在路由路徑的選擇上對EEUC協議進行改進，在與sink距離小于閾值TD_MAX的簇首中選擇一個主簇首，所有簇首的數據都聚合到主簇首，經過融合與壓縮后發送到sink，如圖3所示。



為了節約和均衡簇首通信能耗，HDF-EEUC路由算法中選擇主簇首的策略為：

a）在所有與sink距離小于閾值TD_MAX的簇首中選出剩余能量最多的兩個i和j，假設i和j的剩余能量分別是Ei和Ej，與sink的距離分別是di和dj。

b）根據文獻[5]中的一階通信模型，傳輸距離為k發送一個k bit大小的信號，無線通信設備消耗能量為

ETx(k，d)=ETx-elec(k)+ETx-amp(k，d)ETx(k，d)=Eelec×k+εamp×k×d2(1)

其中：Eelec和εamp在無線傳感器網絡運行時為固定值；k為當前輪發送到sink的數據總量（周期性網絡中k值較穩定，本算法中根據網絡存活節點數估算k值）。由簇首i和j發送k bit大小數據到sink所消耗的能量分別是

ETi(k，di)=Eelec×k+εamp×k×d2i(2)

ETi(k，dj)=Eelec×k+εamp×k×d2j(3)

則經過簇首i和j發送k bit大小數據到sink所消耗的能量之差為

ΔEij=εamp×k×(d2i-d2j)(4)

比較Ei-Ej和εamp×k×(d2i-d2j)的大小。若前者比后者大，選擇i為主簇首；若后者比前者大，選擇j為主簇首。即只有在離sink較遠的簇首的剩余能量比離sink較近的簇首的剩余能量大很多時，才會選擇離sink較遠的簇首作為主簇首。這樣的選擇策略不是單純只考慮簇首剩余能量而忽略網絡總能耗，也不是只考慮通信距離而忽略簇首間的能耗平衡。

選出主簇首之后，就由主簇首把數據發送到sink。由于數據經過高度融合，總數據量大大減小。根據上述一階通信模型，傳輸的數據大小k對通信能耗有著巨大影響。而HDF-EEUC路由協議中經過高度融合后數據總量減少，所以能耗也相應地減小。本文選擇主簇首的策略使得HDF-EEUC路由協議在網絡總能耗和均勻分布簇首間能耗之間取得一個較好的平衡，從而有效延長了無線傳感器網絡的存活時間。

3 仿真結果與分析

本文使用網絡仿真器NS-2分別對HDF-EEUC、EEUC以及LEACH協議進行仿真，通過仿真結果比較其性能。由于HDF-EEUC協議在非均勻簇建立階段與EEUC協議相同，采用與文獻[5]中相同的經過優化取值的參數來進行仿真實驗，如表1所示。

由于簇首消耗的能量占網絡中能量消耗的最主要部分，而且成員節點所消耗的總能量在每種協議中相差不大，首先對上述三種協議的簇首在一輪中所消耗的能量總和進行比較。從實驗中隨機選取10輪，統計各輪中所有簇首消耗的能量之和，結果如圖4所示。可以看出，HDF-EEUC的簇首消耗的能量最低，遠小于LEACH，也小于EEUC。LEACH的簇首能耗之和之所以較高，是LEACH的簇首采用單跳的方式發送數據到sink，而且由于LEACH沒有控制簇首在網絡中的分布，簇首能耗之和有明顯的波動。而在EEUC和HDF-EEUC中，簇首采取多跳的通信方式發送數據到sink，顯著地降低了能耗，而且采用了一定的控制策略使得簇首分布較為合理，使得每一輪簇首能耗之和變化較小，有利于延長網絡壽命。又因為HDF-EEUC中發送到基站的數據經過高度融合，使得發送的總數據量有所減少，從而使得簇首所耗能量總量也相應地減少。

下面比較各種協議的網絡存活時間。圖5顯示了網絡存活節點數隨時間變化的情況。



從圖5可知，無論是第一個節點死亡的時間還是最后一個節點死亡的時間，HDF-EEUC都優于LEACH和EEUC，可見其有效地延長了無線傳感器網絡的壽命(以第一個節點死亡的時間計，HDF-EEUC約為LEACH的2.9倍，約為EEUC的1.2倍)，而且HDF-EEUC中從第一個節點死亡到最后一個節點死亡的時間跨度與EEUC一樣很小。這說明在HDF-EEUC中，在路由選擇階段的選擇主簇首的策略較好地均衡了網絡能耗，從而高效地利用了網絡中有限的能量。

4 結束語

基于簇的無線傳感器網絡路由協議通常采用多跳的通信方式將數據發送到sink，這就導致了網絡中常見的“熱區”問題。本文首先探討了一種能夠較好地解決“熱區”問題的能量高效的非均勻分簇（EEUC）路由協議，然后提出了一種高數據融合的非均勻分簇（HDF-EEUC）路由協議。實驗結果表明，與LEACH以及EEUC路由協議相比，HDF-EEUC路由協議有效地平衡了無線傳感器網絡的節點能耗，延長了網絡的存活時間。

參考文獻:

[1]孫利民，李建中，陳渝，等. 無線傳感器網絡[M].北京：清華大學出版社，2005:3-4.

[2]馬祖長，孫怡寧，梅濤. 無線傳感器網絡綜述[J].通信學報，2004，25(4):114-124.

[3]任豐原，黃海寧，林闖. 無線傳感器網絡[J].軟件學報，2003，14(7):1282-1291.

[4]張衡陽，李瑩瑩，劉云. 基于地理位置的無線傳感器網絡路由協議研究進展[J].計算機應用研究，2008，25(1):18-28.

[5]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii International Conference on System Sciences. Maui，HI:[s.n.]，2000:1-10.

[6]MANJESHWAR A， AGARWAL D P. TEEN: a routing protocol for enhanced efficiency in wireless sensor networks[C]//Proc of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing. 2001: 2009-2015.

[7]MANJESHWAR A， AGRAWAL D P. APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks[C]//Proc of the 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing. Ft.Lauderdale，FL:[s.n.]， 2002:195-202.

[8]XU Y， HEIDEMANN J， ESTRIN D. Geography informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking. 2001: 70-84.

[9]YOUNIS O， FAHMY S. Heed: a hybrid， energy-efficient， distributed clustering approach for Ad hoc sensor networks [J]. IEEE Trans on Mobile Computing，2004， 3(4):660-669.

[10]MHATRE V， ROSENBERG C. Design guidelines for wireless sensor networks:communication， clustering and aggregation[J]. Ad hoc Networks， 2004，2(1):45-63.

[11]LI Cheng-fa， YE Mao， CHEN Gui-hai， et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//Proc of the 2nd IEEE International Conference on Mobile Ad hoc and Sensor Systems(MASS 2005). Washington DC:[s.n.]，2005.

[12]SHANG Rui-qiang， ZHAO Jian-li， SUN Qiu-xia， et al. A hierarchical network based on Voronoi diagram[J]. Journal of China Ordnance， 2006，2(2):157-160.