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

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

一、算法的基本思想

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

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

(二) 采用數據融合的思想，簇內成員節(jié)點僅與簇頭節(jié)點通信，簇頭節(jié)點將收集的數據進行融合處理后，以多跳的方式傳輸到SINK。

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

(四) 在簇間路由過程中，當簇頭節(jié)點將本簇內數據進行融合處理后，只需將數據傳輸到距離它最近的相鄰簇頭節(jié)點，并且該相鄰簇頭節(jié)點比自己距離SINK更近。

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

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

(一)簇的形成階段

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

(二)簇間路由建立階段

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

(三)數據傳輸階段

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

三、算法分析

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

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

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

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

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

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

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

首先，在算法開始時，SINK向全網廣播一條“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的消息。因此整個網絡的消息總開銷大概為：

1+N×T（n）+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數量變少，使得很多能量較高的節(jié)點不能參與競爭，從而影響簇頭的選舉質量，最終導致整個網絡的性能。相反，如果T(n)過大，將大大影響算法的消息開銷，也會使得整個網絡能量開銷過大，影響網絡生存時間。所以T(n)的取值對延長網絡生存時間來說，也起到非常重要的作用。

五、結論

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

參考文獻：

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

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

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