鄭州旅游職業(yè)學院　王桂鳳　王小會

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

鄭州旅游職業(yè)學院王桂鳳王小會

摘要：本文根據(jù)候選簇頭到SINK的距離將網(wǎng)絡劃分成大小不等的簇,在每個簇內以節(jié)點的剩余能量作為重要參數(shù)最終選擇出簇頭；其次,在簇間采用多跳路由的方式,利用改進的Dijkstra算法求解每個簇頭節(jié)點到SINK的最短路徑,使得離基站較遠的簇頭節(jié)點沿著最短路徑傳輸信息。

關鍵詞：無線傳感器；分簇

中圖分類號：TP393

文獻標識碼：A

文章編號：1671-864X（2015）03-0198-01

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

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

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

(一)簇的形成階段

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

(二)簇間路由建立階段

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

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

簇成員節(jié)點將收集的數(shù)據(jù)在自己的時隙內發(fā)送給簇頭節(jié)點，簇頭將收到的所有數(shù)據(jù)進行融合處理，然后沿著最短路徑將數(shù)據(jù)發(fā)送到SINK。每輪數(shù)據(jù)傳輸結束后，簇頭節(jié)點檢測自己的Ecurrent。當Ecurrent＜ECH，進入下一輪循環(huán)，重新進行網(wǎng)絡劃分。

二、算法分析

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

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

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

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

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

三、算法的消息復雜度分析

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

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

1+N×T（n)+X+N-X=1+2N×T+N=2(T+1)N+1

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

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

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

四、結論

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

參考文獻：

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

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

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