基于簇的路由協(xié)議比較

王改云, 胡錦艷

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

基于簇的路由協(xié)議比較

王改云, 胡錦艷

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

摘要:路由協(xié)議作為無線傳感器網(wǎng)絡(luò)(WSNs)中的核心技術(shù)往往是研究的重點(diǎn)，現(xiàn)今有很多不同的高效路由協(xié)議已經(jīng)提出。在參數(shù)選擇和方法方面，每種路由協(xié)議都不同，都有自己的選取方式?；诖氐穆酚蓞f(xié)議是著名的路由方法之一，在該結(jié)構(gòu)中，簇首節(jié)點(diǎn)收集簇中其他節(jié)點(diǎn)的信息進(jìn)行數(shù)據(jù)融合處理，然后將融合后的信息發(fā)送給基站。有必要對(duì)一些典型的分簇結(jié)構(gòu)算法進(jìn)行比較研究。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； LEACH； 分簇； 路由協(xié)議；比較

0引言

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

1WSNs中基于簇的路由算法

1.1LEACH

2000年，MIT學(xué)者Heinzelman等人提出了LEACH，這是第一個(gè)低功耗、自適應(yīng)分簇路由算法，為后人的研究奠定了基礎(chǔ)。在LEACH協(xié)議中，節(jié)點(diǎn)動(dòng)態(tài)成簇，然后選擇一個(gè)節(jié)點(diǎn)作為簇首(CH)節(jié)點(diǎn)，如圖1所示。

圖1　LEACH協(xié)議Fig 1　LEACH protocol

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

LEACH算法分成兩部分：初始化階段和穩(wěn)定階段。在算法的初始化階段中，主要是成員節(jié)點(diǎn)組織成簇，選舉一個(gè)節(jié)點(diǎn)作為簇首節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)會(huì)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，與式(1)相比較，如果比T(n)小，則當(dāng)選為簇首節(jié)點(diǎn)[2]

(1)

式中p為成為簇首的期望百分比，r為輪數(shù)，G為1/p輪還沒有當(dāng)選簇首的節(jié)點(diǎn)集合。如果節(jié)點(diǎn)i成為簇首節(jié)點(diǎn)，廣播ANNOUCE消息宣布成為簇首節(jié)點(diǎn)的消息。在這個(gè)簇內(nèi)的簇成員節(jié)點(diǎn)收到消息后，就會(huì)根據(jù)信號(hào)的強(qiáng)弱來決定將要加入的簇。如果加入就會(huì)對(duì)簇首節(jié)點(diǎn)回復(fù)JOIN的消息。當(dāng)簇首節(jié)點(diǎn)收到來自簇成員節(jié)點(diǎn)的加入信息后，簇首節(jié)點(diǎn)通過時(shí)分多址(time division multiple access，TDMA)方式為簇成員節(jié)點(diǎn)分配時(shí)間槽，建立階段完成。隨后進(jìn)入穩(wěn)定階段，在穩(wěn)定工作的階段，簇首節(jié)點(diǎn)將收集到的簇內(nèi)成員的信息傳到Sink節(jié)點(diǎn)。穩(wěn)定階段的時(shí)間要比建立階段的時(shí)間長(zhǎng)得多[2]。

1.2Energy LEACH和Multihop LEACH

基于參考能量的LEACH算法和LEACH基本上相同，但是參考能量的算法在原有算法上有一個(gè)改進(jìn)，即簇首的選舉不是通過閾值隨機(jī)選取，而是基于節(jié)點(diǎn)的最大剩余能量，對(duì)閾值進(jìn)行了修改，這將延長(zhǎng)網(wǎng)絡(luò)生命周期。不同于LEACH算法中每一個(gè)節(jié)點(diǎn)都有相同的概率成為簇首節(jié)點(diǎn)，改進(jìn)算法中，能量較少的節(jié)點(diǎn)不會(huì)有機(jī)會(huì)成為簇首節(jié)點(diǎn)[3，4]。

不同于簡(jiǎn)單的LEACH，多跳LEACH協(xié)議，以多跳的方式發(fā)送數(shù)據(jù)到基站。這對(duì)總能耗影響很大。通過多跳的方式發(fā)送數(shù)據(jù)時(shí)，每個(gè)參與節(jié)點(diǎn)只花了少量的能量，從而防止了單個(gè)節(jié)點(diǎn)很快耗盡死亡。除了高效節(jié)能之外，多跳LEACH協(xié)議能使得網(wǎng)絡(luò)更持久，適用于大規(guī)模網(wǎng)絡(luò)[4]。

1.3V—LEACH

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

1.4LEACH—R

在LEACH—R協(xié)議中，2個(gè)節(jié)點(diǎn)被選擇作為重要節(jié)點(diǎn)。在初始化階段選擇簇首和R節(jié)點(diǎn)。起初，簇首節(jié)點(diǎn)選擇是通過式(2)進(jìn)行的，計(jì)算閾值，將節(jié)點(diǎn)的能量水平作為重要的參數(shù)指標(biāo)

T(n)=

(2)

式中Eresidual為節(jié)點(diǎn)的剩余能量，E0為節(jié)點(diǎn)的初始能量，δ為連續(xù)的輪數(shù)，其間的節(jié)點(diǎn)尚未當(dāng)選簇首直到當(dāng)前輪，一旦節(jié)點(diǎn)被選為簇頭，設(shè)置該值為0。

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

(3)

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

1.5Cell LEACH

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

圖2　Cell LEACH協(xié)議Fig 2　Cell LEACH protocol

最初，簇首節(jié)點(diǎn)和單元格簇頭節(jié)點(diǎn)的都是隨機(jī)選取的，因?yàn)樗械墓?jié)點(diǎn)都具有相同的能量，但一輪后不同的節(jié)點(diǎn)含有的能量就不一樣了。當(dāng)單元格簇頭的剩余能量低于閾值時(shí)，它就會(huì)向周圍的節(jié)點(diǎn)發(fā)送消息通知它們，該節(jié)點(diǎn)就要消亡了。此外，它通知其他的節(jié)點(diǎn)，成為一個(gè)單元格簇首節(jié)點(diǎn)需要的最低能量。然后每個(gè)相鄰節(jié)點(diǎn)將其剩余能量進(jìn)行比較，把結(jié)果告知單元格簇首?；诒容^結(jié)果，單元格節(jié)點(diǎn)將會(huì)決定哪些節(jié)點(diǎn)以最高的剩余能量獲得下一個(gè)擔(dān)當(dāng)單元格節(jié)點(diǎn)的對(duì)象。

每個(gè)簇首都會(huì)在自己的表中保存其他簇首節(jié)點(diǎn)的記錄，用來計(jì)算到基站的最短路徑。由于在每一輪簇首節(jié)點(diǎn)都會(huì)變化，因此，從簇首節(jié)點(diǎn)到基站的路徑也會(huì)變化。

只要網(wǎng)絡(luò)正常工作，簇和單元格都沒有動(dòng)態(tài)變化,簇首和單元格簇首的結(jié)構(gòu)會(huì)變化,一旦網(wǎng)絡(luò)建立，基站就會(huì)向簇首發(fā)送數(shù)據(jù)請(qǐng)求信息，它將描繪感興趣的區(qū)域?；緯?huì)將請(qǐng)求信息發(fā)送給單元格簇首，它們將轉(zhuǎn)發(fā)給相應(yīng)的傳感器節(jié)點(diǎn)。如果節(jié)點(diǎn)有興趣，并且愿意回應(yīng)，那么它們會(huì)在給定的時(shí)間間隙內(nèi)，把數(shù)據(jù)一個(gè)一個(gè)地傳給目的節(jié)點(diǎn)[7]。

1.6EEE LEACH

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

圖3　EEE LEACH 協(xié)議Fig 3　EEE LEACH protocol

1.7LEACH Mobile[9]

LEACH Mobile是一個(gè)多跳路由協(xié)議，重點(diǎn)主要集中在簇中移動(dòng)節(jié)點(diǎn)成員聲明上。這個(gè)協(xié)議假定節(jié)點(diǎn)是中心可移動(dòng)的。和基本LEACH協(xié)議一樣，它也假設(shè)在每一輪有2個(gè)階段，穩(wěn)定階段比初始建立階段長(zhǎng)。該協(xié)議假定節(jié)點(diǎn)總是有數(shù)據(jù)要發(fā)送，簇首節(jié)點(diǎn)在合適的時(shí)間間隙將數(shù)據(jù)請(qǐng)求發(fā)送到非簇首節(jié)點(diǎn)，如果非簇首節(jié)點(diǎn)在連續(xù)2輪，2個(gè)連續(xù)的數(shù)據(jù)請(qǐng)求信息內(nèi)不回答，不響應(yīng)，那么，簇首節(jié)點(diǎn)就當(dāng)做該節(jié)點(diǎn)已經(jīng)離開了這個(gè)簇，因此，從成員節(jié)點(diǎn)中移除，然后簇首節(jié)點(diǎn)更新TDMA表。

另一方面，在指定時(shí)間里，當(dāng)移動(dòng)節(jié)點(diǎn)還沒有收到從簇首節(jié)點(diǎn)發(fā)出的任何的請(qǐng)求信息，它就意識(shí)到它不再是這個(gè)簇的一員，因此，向周圍的簇廣播加入信息，附近的簇首節(jié)點(diǎn)收聽到這個(gè)信息，然后傳遞簇首廣告信息給該節(jié)點(diǎn)。該移動(dòng)節(jié)點(diǎn)將會(huì)決定在當(dāng)前輪，加入哪一個(gè)簇。此外，它必須通知這個(gè)新的簇更新簇成員的信息表和TDMA計(jì)劃表。該協(xié)議的優(yōu)點(diǎn)是分組丟失少，但是能耗消耗較高。

1.8ECBR[10]

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

2路由協(xié)議比較

上述協(xié)議分析比較如表1所示，其對(duì)比分析結(jié)果比較全面明確了各種路由協(xié)議應(yīng)用與適用的場(chǎng)合。

3結(jié)論

路由分簇協(xié)議和其他協(xié)議相比較具有延長(zhǎng)網(wǎng)絡(luò)壽命的優(yōu)點(diǎn)，這是由它們特定的分簇結(jié)構(gòu)決定的。本文評(píng)述了一些基于簇的路由協(xié)議，并對(duì)其進(jìn)行比較，這有助于認(rèn)識(shí)哪些協(xié)議適合在哪些應(yīng)用和場(chǎng)景中進(jìn)行使用，進(jìn)而節(jié)約整個(gè)網(wǎng)絡(luò)的能量消耗?？梢愿鶕?jù)一定的參數(shù)如感知區(qū)域的面積、移動(dòng)性、網(wǎng)絡(luò)的壽命等來選擇路由協(xié)議。例如，當(dāng)場(chǎng)景中的監(jiān)控區(qū)域很小時(shí)，適合采取單跳路由的方法，而對(duì)于大面積的檢測(cè)區(qū)域，選擇多跳路由協(xié)議較好。同樣，在選擇協(xié)議之前對(duì)其他的因素也要進(jìn)行分析比較。明確不同種類的基于簇的路由協(xié)議和相應(yīng)的特點(diǎn)將有助于研究的深入。

參考文獻(xiàn):

[1]袁輝勇,羊四清,李素君.無線傳感器網(wǎng)絡(luò)中基于分層的非均衡分簇算法[J].傳感器與微系統(tǒng),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　基于簇的路由協(xié)議比較

[3]王雍,楊海波,馮淑娟.無線傳感器網(wǎng)絡(luò)中一種能量有效的分簇算法[J].傳感器與微系統(tǒng),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

中圖分類號(hào)：TP 393

文獻(xiàn)標(biāo)識(shí)碼：A

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

作者簡(jiǎn)介:

王改云(1964-)，女，河南鄭州人，教授，碩士生導(dǎo)師，主要研究方向?yàn)闊o線通信、智能控制、數(shù)據(jù)融合。