一種無線傳感器網(wǎng)絡(luò)分簇路由算法分析

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A摘要：本文根據(jù)候選簇頭到SINK的距離將網(wǎng)絡(luò)劃分成大小不等的簇，在每個(gè)簇內(nèi)以節(jié)點(diǎn)的剩余能量作為重要參數(shù)最終選擇出簇頭；其次，在簇間采用多跳路由的方式，利用改進(jìn)的Dijkstra算法求解每個(gè)簇頭節(jié)點(diǎn)到SINK的最短路徑，使得離基站較遠(yuǎn)的簇頭節(jié)點(diǎn)沿著最短路徑傳輸信息。

關(guān)鍵詞：無線傳感器；分簇作為一種新的信息處理模式和信息獲取方式，WSN引起了全世界研究學(xué)者的廣泛關(guān)注。路由技術(shù)是WSN比較重要的核心技術(shù)，對(duì)WSN的發(fā)展起著關(guān)鍵作用。由于分簇路由能夠有效進(jìn)行網(wǎng)內(nèi)數(shù)據(jù)融合，減少冗余數(shù)據(jù)量，延長(zhǎng)網(wǎng)絡(luò)生命周期，己經(jīng)成為WSN的熱門研究領(lǐng)域。

一、算法的基本思想

在采用分簇結(jié)構(gòu)的WSN中，簇頭是最重要的節(jié)點(diǎn)。它不僅要管理簇內(nèi)成員節(jié)點(diǎn)，協(xié)調(diào)其成員節(jié)點(diǎn)按照一定的順序進(jìn)行數(shù)據(jù)傳輸，還要將收集到的成員節(jié)點(diǎn)數(shù)據(jù)進(jìn)行融合，最后將融合后的數(shù)據(jù)發(fā)送給SINK。由于簇頭節(jié)點(diǎn)的責(zé)任較大、負(fù)擔(dān)較重，因此，本算法采用周期性輪換方法，在每一輪開始時(shí)，首先考慮所選簇頭節(jié)點(diǎn)的狀態(tài)，之后在成員節(jié)點(diǎn)加入某個(gè)簇時(shí)，考慮所加入簇的簇頭節(jié)點(diǎn)剩余能量。

(一) 將網(wǎng)絡(luò)劃分成大小不等的簇。由于距離SINK節(jié)點(diǎn)越近的簇頭節(jié)點(diǎn)所承擔(dān)的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)越重，所消耗的能量就越大。因此，只有減少距離SINK節(jié)點(diǎn)較近的簇頭節(jié)點(diǎn)的簇內(nèi)能量消耗，才能使簇頭節(jié)點(diǎn)有更多的能量來進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)工作，從而解決平衡整個(gè)網(wǎng)絡(luò)簇頭節(jié)點(diǎn)能量消耗問題。

(二) 采用數(shù)據(jù)融合的思想，簇內(nèi)成員節(jié)點(diǎn)僅與簇頭節(jié)點(diǎn)通信，簇頭節(jié)點(diǎn)將收集的數(shù)據(jù)進(jìn)行融合處理后，以多跳的方式傳輸?shù)絊INK。

(三) 簇內(nèi)通信采用TDMA方式。為了避免簇內(nèi)數(shù)據(jù)傳輸時(shí)發(fā)生沖突，簇結(jié)構(gòu)建立后，簇頭節(jié)點(diǎn)創(chuàng)建TDMA時(shí)間表，為每個(gè)簇成員節(jié)點(diǎn)分配時(shí)隙，簇成員節(jié)點(diǎn)只有在自己的時(shí)隙內(nèi)進(jìn)行數(shù)據(jù)發(fā)送，而在其它時(shí)隙內(nèi)節(jié)點(diǎn)關(guān)閉無線收發(fā)器，以節(jié)省能量。

(四) 在簇間路由過程中，當(dāng)簇頭節(jié)點(diǎn)將本簇內(nèi)數(shù)據(jù)進(jìn)行融合處理后，只需將數(shù)據(jù)傳輸?shù)骄嚯x它最近的相鄰簇頭節(jié)點(diǎn)，并且該相鄰簇頭節(jié)點(diǎn)比自己距離SINK更近。

二、算法的執(zhí)行步驟

該算法的執(zhí)行過程分為三個(gè)階段：簇的形成階段，簇間路由建立階段和數(shù)據(jù)傳輸階段。

(一)簇的形成階段

WSN部署完成之后，初始化網(wǎng)絡(luò)參數(shù)。SINK以給定的發(fā)送功率向網(wǎng)絡(luò)內(nèi)廣播一個(gè)“HELLO”信號(hào)，每個(gè)傳感器節(jié)點(diǎn)在收到此信號(hào)后，依據(jù)接收信號(hào)的強(qiáng)度計(jì)算出它到SINK的近似距離。然后，依據(jù)節(jié)點(diǎn)的剩余能量選擇部分節(jié)點(diǎn)作為候選簇頭(tentative_cluster_head)，tentative_cluster_head根據(jù)自身到SINK的距離計(jì)算它的競(jìng)爭(zhēng)區(qū)域，區(qū)域的競(jìng)爭(zhēng)半徑記作Rc。每個(gè)tentative_cluster_head以Rc為半徑建立大小不等的簇。每個(gè)tentative_cluster_head以Rc為半徑廣播競(jìng)爭(zhēng)簇頭的消息，假如si為tentative_cluster_head，那么以Rc為半徑的圓內(nèi)的候選簇頭組成集合si.CH。在該面積內(nèi)選擇剩余能量Ecurrent最多的tentative_cluster_head作為最終簇頭(final_cluster_head)。如果有多個(gè)最大能量相同的tentative_cluster_head，選擇ID號(hào)最小的tentative_cluster_head作為final_cluster_head。然后刪除此面積內(nèi)的其他tentative_cluster_head，最后final_cluster_head以2Rc為半徑廣播成為簇頭的消息。簇頭選擇過程結(jié)束。網(wǎng)絡(luò)中的非簇頭節(jié)點(diǎn)則根據(jù)自己到各個(gè)簇頭的距離(選擇距離最近的簇頭)來選擇它要加入的簇，并告知相應(yīng)的簇頭。簇劃分完成。

(二)簇間路由建立階段

簇建立完成之后，在每個(gè)簇頭節(jié)點(diǎn)上運(yùn)行改進(jìn)的Dijkstra算法，尋找簇頭到SINK的最短路徑，運(yùn)行完成后每個(gè)簇頭節(jié)點(diǎn)都保存一張到達(dá)SINK的最短路徑信息表。當(dāng)簇頭節(jié)點(diǎn)要與SINK進(jìn)行通訊時(shí)，將沿著最短路徑進(jìn)行數(shù)據(jù)傳輸。

(三)數(shù)據(jù)傳輸階段

簇成員節(jié)點(diǎn)將收集的數(shù)據(jù)在自己的時(shí)隙內(nèi)發(fā)送給簇頭節(jié)點(diǎn)，簇頭將收到的所有數(shù)據(jù)進(jìn)行融合處理，然后沿著最短路徑將數(shù)據(jù)發(fā)送到SINK。每輪數(shù)據(jù)傳輸結(jié)束后，簇頭節(jié)點(diǎn)檢測(cè)自己的Ecurrent。當(dāng)Ecurrent

三、算法分析

該算法以整個(gè)傳感器網(wǎng)絡(luò)為出發(fā)點(diǎn)，從多個(gè)角度考慮如何平衡節(jié)點(diǎn)的能量消耗問題。該算法是一個(gè)分布式動(dòng)態(tài)算法，簇的建立階段在采用大小不等的分簇思想的基礎(chǔ)上，融入了節(jié)點(diǎn)的能量因素，即在鄰居候選簇頭集合中以節(jié)點(diǎn)的Ecurrent為主要依據(jù)來選擇最終簇頭。在簇間多跳路由中，用改進(jìn)的Dijkstra算法尋找各簇頭節(jié)點(diǎn)到SINK的最短路徑，相當(dāng)于給每個(gè)簇頭節(jié)點(diǎn)創(chuàng)建了一條通往SINK的能量消耗最少的路徑，當(dāng)簇頭節(jié)點(diǎn)要發(fā)送數(shù)據(jù)到SINK時(shí)，將沿著該路徑進(jìn)行傳輸。本算法具有以下特點(diǎn)：

(一) 在最終簇頭節(jié)點(diǎn)的選舉過程中，盡可能的選擇能量大的節(jié)點(diǎn)作為簇頭，有效的延長(zhǎng)網(wǎng)絡(luò)的生存周期。

(二) 在簇的建立過程中，采用大小不等的分簇思想，使得距離SINK較近的簇頭覆蓋的面積較小，從而減少簇頭在管理簇內(nèi)成員節(jié)點(diǎn)時(shí)的能量消耗，節(jié)省的能量用來中繼轉(zhuǎn)發(fā)，有效的解決路由中的“熱區(qū)”問題，平衡簇頭節(jié)點(diǎn)之間的能量消耗。

(三) 該算法是分布式的，簇頭的產(chǎn)生通過局部競(jìng)爭(zhēng)，無需迭代，保證算法的快速收斂性和較好的伸縮性。

(四) 簇間路由采用多跳通信方式，避免了遠(yuǎn)離SINK的簇頭與SINK直接通信，并綜合考慮中繼簇頭之間的距離，根據(jù)預(yù)先設(shè)置的權(quán)值進(jìn)行路徑選擇，有效的平衡簇頭節(jié)點(diǎn)的能量消耗。

四、算法的消息復(fù)雜度分析

(一) 在監(jiān)測(cè)區(qū)域內(nèi)，DEUC算法的消息復(fù)雜度為O(N)。

首先，在算法開始時(shí)，SINK向全網(wǎng)廣播一條“HELLO”消息給每個(gè)節(jié)點(diǎn)。其次，大概有N×T(n)個(gè)參與競(jìng)爭(zhēng)的tentative_cluster_head節(jié)點(diǎn)，共廣播N×T(n)條參與的消息com_head_msg，最終每個(gè)tentative_cluster_head廣播一條成功競(jìng)選的消息final_head_msg，或者宣布退出競(jìng)選的消息quit_com_head _msg。假設(shè)共有X個(gè)tentative_cluster_head成為最終簇頭final_head，每個(gè)簇頭廣播一條head_msg，共有X條消息，則有N-X條join_ cluster_ head_msg的消息。因此整個(gè)網(wǎng)絡(luò)的消息總開銷大概為：

1+N×T（n）+N×T（n）+X+N-X=1+2N×T+N=2（T+1）N+1

所以消息復(fù)雜度為O(N)，說明本算法開銷小，能量高效。

(二) 閾值T(n)決定算法中參與競(jìng)爭(zhēng)的tentative_cluster_head的個(gè)數(shù)，從而影響算法的消息開銷。

閾值T(n)選擇的合適與否，直接影響參與競(jìng)爭(zhēng)的候選簇頭的多少。如果T(n)的取值偏小的話，將直接導(dǎo)致參與競(jìng)爭(zhēng)的tentative_cluster_head數(shù)量變少，使得很多能量較高的節(jié)點(diǎn)不能參與競(jìng)爭(zhēng)，從而影響簇頭的選舉質(zhì)量，最終導(dǎo)致整個(gè)網(wǎng)絡(luò)的性能。相反，如果T(n)過大，將大大影響算法的消息開銷，也會(huì)使得整個(gè)網(wǎng)絡(luò)能量開銷過大，影響網(wǎng)絡(luò)生存時(shí)間。所以T(n)的取值對(duì)延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間來說，也起到非常重要的作用。

五、結(jié)論

本算法之所以優(yōu)于其它算法，其原因主要有以下幾點(diǎn)：① 因?yàn)閭鞲衅骶W(wǎng)絡(luò)節(jié)點(diǎn)之間，即成員節(jié)點(diǎn)與簇頭、簇頭與簇頭和簇頭與SINK之間的距離不會(huì)太大，因此節(jié)點(diǎn)之間的通信只需要遵循自由空間(freespace)模型，避免采用多路衰減模型。② 網(wǎng)絡(luò)分成大小不等的簇，使得距離SINK越近的簇頭節(jié)點(diǎn)擁有的成員節(jié)點(diǎn)越少，這樣，可以減少靠近SINK的簇頭節(jié)點(diǎn)的簇內(nèi)通信能耗，以達(dá)到平衡整個(gè)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)能量消耗的目的。③ 簇間采用多跳通信方式，網(wǎng)絡(luò)中以簇頭節(jié)點(diǎn)為骨干網(wǎng)建立簇頭到SINK的最短路徑，簇頭沿著最短路徑將融合后的數(shù)據(jù)發(fā)送到SINK。④ 本協(xié)議具有很好的擴(kuò)展性。

參考文獻(xiàn)：

[1] 劉琴，王福豹，馬峻巖等.無線傳感器網(wǎng)絡(luò)中一種有效的分布式簇劃分算法[J].計(jì)算機(jī)應(yīng)用， 2007， 27(1): 4-6.

[2] 王桂鳳. 無線傳感器網(wǎng)絡(luò)智能分簇路由算法研究[D].桂林：桂林電子科技大學(xué)，2010.

[3]劉琴，王福豹，馬峻巖等.無線傳感器網(wǎng)絡(luò)中一種有效的分布式簇劃分算法[J].計(jì)算機(jī)應(yīng)用， 2007， 27(1): 4-6.