基于簇的路由協議比較

王改云, 胡錦艷

(桂林電子科技大學 電子工程與自動化學院，廣西 桂林 541004)

基于簇的路由協議比較

王改云, 胡錦艷

(桂林電子科技大學 電子工程與自動化學院，廣西 桂林 541004)

摘要:路由協議作為無線傳感器網絡(WSNs)中的核心技術往往是研究的重點，現今有很多不同的高效路由協議已經提出。在參數選擇和方法方面，每種路由協議都不同，都有自己的選取方式。基于簇的路由協議是著名的路由方法之一，在該結構中，簇首節點收集簇中其他節點的信息進行數據融合處理，然后將融合后的信息發送給基站。有必要對一些典型的分簇結構算法進行比較研究。

關鍵詞：無線傳感器網絡； LEACH； 分簇； 路由協議；比較

0引言

無線傳感器網絡(WSNs)是由一組低功耗、小型、輕便的傳感器節點組成，傳感器中的節點相互之間通信，收集周圍節點的信息。隨著WSNs的發展，使得遠程監控變得更加容易、精度變得更高。節點通常部署在事件發生的區域中或者周圍，每個節點收集到監控區域的信息，然后進行處理，最后傳送給頭節點或者基站進行進一步的處理。通常，將節點的執行過程分成三部分：傳感、計算和通信。節點都是隨機部署在監控區域，網絡中的節點必須具有自組織的能力。節點間的協作是這種網絡的特點，它們相互協作傳遞信息到附近的用戶。WSNs在各個領域中得到廣泛應用，并且應用還在逐步增加,一些主要的應用有：森林火災檢測、停車場、棲息地監測、健康監控、工廠維護、工業自動化、智能家居等[1]。在WSNs中，已經有很多種不同的路由協議提出,其中，分簇算法是一種自主成簇，然后進行簇頭選擇和數據傳輸的路由協議。本文主要對現有的一些分簇路由協議進行比較分析。

1WSNs中基于簇的路由算法

1.1LEACH

2000年，MIT學者Heinzelman等人提出了LEACH，這是第一個低功耗、自適應分簇路由算法，為后人的研究奠定了基礎。在LEACH協議中，節點動態成簇，然后選擇一個節點作為簇首(CH)節點，如圖1所示。

圖1　LEACH協議Fig 1　LEACH protocol

圖1中,黑色節點代表簇首節點，簇首節點負責收集該簇內所有節點的信息，并且進行數據融合然后發送給目的節點，以便進一步的處理。由于簇首節點和其他簇成員節點相比，工作很復雜，消耗的能量較大。LEACH提供相同的概率選擇簇首，確保每個節點都有統一的能量消耗。一旦簇首節點選好，就會給每個成員節點分配時隙進行信息傳遞。一次只能將一個節點信息傳輸給簇首節點。在該結構中，簇首節點忙于通信，簇成員節點可以關閉通信節約能量。

LEACH算法分成兩部分：初始化階段和穩定階段。在算法的初始化階段中，主要是成員節點組織成簇，選舉一個節點作為簇首節點。每個節點會產生一個0～1之間的隨機數，與式(1)相比較，如果比T(n)小，則當選為簇首節點[2]

(1)

式中p為成為簇首的期望百分比，r為輪數，G為1/p輪還沒有當選簇首的節點集合。如果節點i成為簇首節點，廣播ANNOUCE消息宣布成為簇首節點的消息。在這個簇內的簇成員節點收到消息后，就會根據信號的強弱來決定將要加入的簇。如果加入就會對簇首節點回復JOIN的消息。當簇首節點收到來自簇成員節點的加入信息后，簇首節點通過時分多址(time division multiple access，TDMA)方式為簇成員節點分配時間槽，建立階段完成。隨后進入穩定階段，在穩定工作的階段，簇首節點將收集到的簇內成員的信息傳到Sink節點。穩定階段的時間要比建立階段的時間長得多[2]。

1.2Energy LEACH和Multihop LEACH

基于參考能量的LEACH算法和LEACH基本上相同，但是參考能量的算法在原有算法上有一個改進，即簇首的選舉不是通過閾值隨機選取，而是基于節點的最大剩余能量，對閾值進行了修改，這將延長網絡生命周期。不同于LEACH算法中每一個節點都有相同的概率成為簇首節點，改進算法中，能量較少的節點不會有機會成為簇首節點[3，4]。

不同于簡單的LEACH，多跳LEACH協議，以多跳的方式發送數據到基站。這對總能耗影響很大。通過多跳的方式發送數據時，每個參與節點只花了少量的能量，從而防止了單個節點很快耗盡死亡。除了高效節能之外，多跳LEACH協議能使得網絡更持久，適用于大規模網絡[4]。

1.3V—LEACH

在雙簇首LEACH協議中，一個簇結構對應的不是只有一個簇首節點，有2個，一個擔當主簇首，另一個擔當副簇首節點。開始時，主簇首負責收集簇中非簇首節點發送的數據，并將其發送到基站，但是一旦主群簇首節點即將死去，副簇首節點需要擔負起主簇首節點的責任，同時，下一個副簇首節點會選擇出來。這樣防止了簇群因節點突然死亡而失去簇首節點，進一步地預防了數據突然停止傳輸。選舉群簇首節點和副簇首節點是將基于最大剩余能量、節點到基站的最短距離和最小的能耗作為參考標準。雙簇首協議在簇首和基站之間采取單跳傳輸，仿真結果表明，雙簇首協議在延長網絡生命周期方面能比LEACH協議提高49.37 %[5]。

1.4LEACH—R

在LEACH—R協議中，2個節點被選擇作為重要節點。在初始化階段選擇簇首和R節點。起初，簇首節點選擇是通過式(2)進行的，計算閾值，將節點的能量水平作為重要的參數指標

T(n)=

(2)

式中Eresidual為節點的剩余能量，E0為節點的初始能量，δ為連續的輪數，其間的節點尚未當選簇首直到當前輪，一旦節點被選為簇頭，設置該值為0。

當設定好簇首節點，在簇首中選擇一個節點稱為中繼節點(R節點)，通過選定兩個參考指標，分別為剩余能量和離基站的距離。R節點的工作職責是獲取融合后的數據傳遞到基站，這樣，簇首的數據通過2達跳到基站，只需花費較少的能量，避免了節點過早死亡。R節點是通過λ參數選擇的，表示剩余能量和該節點到簇首節點的距離比值。λ的計算公式為[6]

(3)

由式(3)可知，λ和剩余能量呈正比，和距離呈反比[8]。

1.5Cell LEACH

在蜂房結構的LEACH中，每個簇群由7個小單元格組成。每個單元格有一個單元格簇頭，而每個蜂房有一個簇首。如圖2所示，單元格簇頭收集每個單元格里面的數據，然后進行融合，再傳遞給蜂房的簇首節點。這些簇首節點將來自各個蜂房的單元格里面的數據收集、匯總，進行融合再通過多跳傳輸給基站。

圖2　Cell LEACH協議Fig 2　Cell LEACH protocol

最初，簇首節點和單元格簇頭節點的都是隨機選取的，因為所有的節點都具有相同的能量，但一輪后不同的節點含有的能量就不一樣了。當單元格簇頭的剩余能量低于閾值時，它就會向周圍的節點發送消息通知它們，該節點就要消亡了。此外，它通知其他的節點，成為一個單元格簇首節點需要的最低能量。然后每個相鄰節點將其剩余能量進行比較，把結果告知單元格簇首?；诒容^結果，單元格節點將會決定哪些節點以最高的剩余能量獲得下一個擔當單元格節點的對象。

每個簇首都會在自己的表中保存其他簇首節點的記錄，用來計算到基站的最短路徑。由于在每一輪簇首節點都會變化，因此，從簇首節點到基站的路徑也會變化。

只要網絡正常工作，簇和單元格都沒有動態變化,簇首和單元格簇首的結構會變化,一旦網絡建立，基站就會向簇首發送數據請求信息，它將描繪感興趣的區域?；緯⒄埱笮畔l送給單元格簇首，它們將轉發給相應的傳感器節點。如果節點有興趣，并且愿意回應，那么它們會在給定的時間間隙內，把數據一個一個地傳給目的節點[7]。

1.6EEE LEACH

通過實現多級聚類方法來使LEACH實現能量高效的擴展。起初，簇和簇首的選擇方式是和LEACH協議一樣，一旦簇首節點選出，第二層的分簇就開始，緊接著第二層的主簇首節點也選出。如圖3所示，主簇首節點接收到來自簇首節點的融合數據信息，進一步壓縮，融合傳遞給基站。通常情況下，主簇首節點比簇首節點少。通過引入主簇首節點，簇首節點的控制開銷減少了。仿真結果顯示，EEE LEACH在減少能量消耗方面性能優于LEACH[8]。

圖3　EEE LEACH 協議Fig 3　EEE LEACH protocol

1.7LEACH Mobile[9]

LEACH Mobile是一個多跳路由協議，重點主要集中在簇中移動節點成員聲明上。這個協議假定節點是中心可移動的。和基本LEACH協議一樣，它也假設在每一輪有2個階段，穩定階段比初始建立階段長。該協議假定節點總是有數據要發送，簇首節點在合適的時間間隙將數據請求發送到非簇首節點，如果非簇首節點在連續2輪，2個連續的數據請求信息內不回答，不響應，那么，簇首節點就當做該節點已經離開了這個簇，因此，從成員節點中移除，然后簇首節點更新TDMA表。

另一方面，在指定時間里，當移動節點還沒有收到從簇首節點發出的任何的請求信息，它就意識到它不再是這個簇的一員，因此，向周圍的簇廣播加入信息，附近的簇首節點收聽到這個信息，然后傳遞簇首廣告信息給該節點。該移動節點將會決定在當前輪，加入哪一個簇。此外，它必須通知這個新的簇更新簇成員的信息表和TDMA計劃表。該協議的優點是分組丟失少，但是能耗消耗較高。

1.8ECBR[10]

增強的簇路由(enhanced cluster-based routing，ECBR)協議是一種支持節點的移動性的協議。該協議是一種響應路由協議，它是路由在需要的時候計算。 ECBR的每個周期包括5個階段：初始化階段、簇形成階段、簇頭選擇階段、數據傳送階段、再分簇、路由重建階段。在初始化階段，節點發送Hello消息單跳發送到基站。問候消息包含節點的ID、目的節點ID、剩余能量、移動系數、離基站的距離。一個節點如果不發送Hello消息則表示不參加數據傳輸。下一階段是簇的形成階段，其中，節點根據DBSCAN(density-based spatial clustering of applications with noise)算法自動成簇。一旦簇建立完畢，基站就會根據剩余能量、移動性和到基站的距離來選擇簇首節點。簇首就會分配時間間隙，給簇中的每一個節點，數據傳輸階段開始。從源簇首到基站通過最短路徑以多跳形式傳輸。每一輪后，重新分簇，路徑也會重新計算，計算方式和前面的一致[10]。

2路由協議比較

上述協議分析比較如表1所示，其對比分析結果比較全面明確了各種路由協議應用與適用的場合。

3結論

路由分簇協議和其他協議相比較具有延長網絡壽命的優點，這是由它們特定的分簇結構決定的。本文評述了一些基于簇的路由協議，并對其進行比較，這有助于認識哪些協議適合在哪些應用和場景中進行使用，進而節約整個網絡的能量消耗?？梢愿鶕欢ǖ膮等绺兄獏^域的面積、移動性、網絡的壽命等來選擇路由協議。例如，當場景中的監控區域很小時，適合采取單跳路由的方法，而對于大面積的檢測區域，選擇多跳路由協議較好。同樣，在選擇協議之前對其他的因素也要進行分析比較。明確不同種類的基于簇的路由協議和相應的特點將有助于研究的深入。

參考文獻:

[1]袁輝勇,羊四清,李素君.無線傳感器網絡中基于分層的非均衡分簇算法[J].傳感器與微系統,2010，29(2):101-103.

[2]Al-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].Wireless Communications,IEEE,2004,11(6):6-28.

表1　基于簇的路由協議比較

[3]王雍,楊海波,馮淑娟.無線傳感器網絡中一種能量有效的分簇算法[J].傳感器與微系統,2008,27(12):19-21.

[4]Xiangning F,Yulin S.Improvement on LEACH protocol of wireless sensor networks[C]∥2007 International Conference on Sensor Communication Sensor Technologies and Applications,IEEE,2007:260-264.

[5]Ahlawat A,Malik V.An extended vice-cluster selection approach to improve V LEACH protocol in WSNs[C]∥2013 Third International Conference on Advanced Computing and Communication Technologies(ACCT),IEEE,2013:236-240.

[6]Wang N,Zhu H.An energy efficient algorithm based on LEACH protocol[C]∥2012 International Conference on Computer Science and Electronics Engineering(ICCSEE),IEEE,2012:339-342.

[7]Yektaparast A, Nabavi F H, Sarmast A. An improvement on LEACH protocol(Cell—LEACH)[C]∥2012 14th International Conference on Advanced Communication Technology(ICACT),IEEE,2012:992-996.

[8]Sharma M,Sharma K.An energy efficient extended LEACH(EEELEACH)[C]∥2012 International Conference on Communication Systems and Network Technologies(CSNT),IEEE,2012:377-382.

[9]Kim D S,Chung Y J.Self-organization routing protocol supporting mobile nodes for wireless sensor networks[C]∥The First International Multi-Symposiums on Computer and Computational Sciences,IMSCCS’06,IEEE,2006:622-626.

[10] Anitha R U,Kamalakkannan P.Enhanced cluster-based routing protocol for mobile nodes in wireless sensor networks[C]∥2013 International Conference on Pattern Recognition,Informatics and Mobile Engineering(PRIME),IEEE,2013:187-193.

Comparison of routing protocols based on clustering

WANG Gai-yun， HU Jin-yan

(School of Electronic Engineering and Automation,Guilin University of Electronic Technology,Guilin 541004,China)

Abstract:Wireless sensor networks(WSNs)is consists of nodes which are small in size，low power consumption,low price.Until now,many protocols have been proposed,they are different in many aspects,like parameters selection,approach and so on.Among this,clustering routing protocol is one of the most famous approach,which is the core technology in WSNs that is widely used in environmental,medical and other fields.In clustering structure,the cluster head (CH) node gather information of other nodes in cluster for data fusion,and then transmit them to base station.It’s really necessary to carry out comparative study on some typical clustering structure algorithm.

Key words:WSNs; LEACH; clustering; routing protocols;comparison

DOI:10.13873/J.1000—9787(2016)04—0004—04

收稿日期：2015—07—02

中圖分類號：TP 393

文獻標識碼：A

文章編號：1000—9787(2016)04—0004—04

作者簡介:

王改云(1964-)，女，河南鄭州人，教授，碩士生導師，主要研究方向為無線通信、智能控制、數據融合。