一種無線傳感器網絡分簇路由算法分析

鄭州旅游職業學院　王桂鳳　王小會

一種無線傳感器網絡分簇路由算法分析

鄭州旅游職業學院王桂鳳王小會

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

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

中圖分類號：TP393

文獻標識碼：A

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

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

一、算法的執行步驟

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

(一)簇的形成階段

WSN部署完成之后，初始化網絡參數。SINK以給定的發送功率向網絡內廣播一個“HELLO”信號，每個傳感器節點在收到此信號后，依據接收信號的強度計算出它到SINK的近似距離。然后，依據節點的剩余能量選擇部分節點作為候選簇頭(tentative_cluster_head)，tentative_cluster_head根據自身到SINK的距離計算它的競爭區域，區域的競爭半徑記作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為半徑廣播成為簇頭的消息。簇頭選擇過程結束。網絡中的非簇頭節點則根據自己到各個簇頭的距離(選擇距離最近的簇頭)來選擇它要加入的簇，并告知相應的簇頭。簇劃分完成。

(二)簇間路由建立階段

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

(三)數據傳輸階段

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

二、算法分析

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

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

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

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

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

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

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

首先，在算法開始時，SINK向全網廣播一條“HELLO”消息給每個節點。其次，大概有N×T(n)個參與競爭的tentative_cluster_head節點，共廣播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的消息。因此整個網絡的消息總開銷大概為：

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

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

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

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

四、結論

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

參考文獻：

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

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

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