WSN中一種高效節能的分簇路由協議＊

程焱芳，吳玉成

(重慶大學 通信工程學院，重慶 400044)

節能問題一直是無線傳感器網絡WSN(Wireless Sensor Network)的研究熱點，其中基于分簇的路由協議引起了較多的關注[1-2]。分簇協議一般采用多跳通信，但是研究發現，多跳通信會導致離Sink越近的傳感器節點的能量消耗越快[3]，這種現象導致在Sink周圍形成“能量洞”。參考文獻[4]首次提出能量洞問題在節點隨機均勻分布的環境中是不可避免的。同時，從延長網絡生命周期和網絡覆蓋率的角度考慮，參考文獻[5]重點討論了部分覆蓋算法，指出恰當的部分覆蓋可以減少冗余節點，更節省網絡能量。

針對上述問題，本文提出了一種新的分簇算法EEGC，該算法主要針對節點同構、節點隨機均勻分布的網絡環境。EEGC采用基于最小跳數的簇頭競爭方法、內環簇頭直接通信以及外環簇頭多跳通信的方式，緩解了網絡Sink節點周圍能量洞的問題。同時調用部分覆蓋算法，避免了大量冗余節點的能耗，實現了一個高效的節能通信網絡。

1 系統模型和問題分析

1.1 系統模型

本文假設n個傳感器節點隨機均勻地分布在監測區域Aarea內，節點具有相同的初始能量和能耗模型?；静渴鹪趨^域外，由位于監測區域內的Sink節點將收集的信息傳送到基站。所有節點不具有定位功能，節點的無線發射功率可控，可以根據距離來調整發射功率的大小。無線傳感器網絡的能耗主要來自于通信，所有節點發送、接收和融合數據消息的能量消耗模型見參考文獻[1]。

1.2 簇內部分覆蓋算法

定義1 服務質量q(the Desired QoS)定義為所有工作節點構成的有效監測區域面積占整個監測區域Aarea(L×L)面積的比例，即：

其中，Si表示工作節點ni的感知范圍，K表示工作節點的數量。 區域 Aarea中任意一點 Pi(x，y)∈Aarea，Pi(x，y)沒有被K個工作節點覆蓋的概率為：

因此，在區域 Aarea中，任意一點 Pi(x，y)至少被其中一個工作節點覆蓋的概率θ為：

根據服務質量q的定義，可知在區域Aarea中K個工作節點達到的服務質量為：

其中，Rs為感知半徑。由式(4)可知，隨機部署網絡在區域大小和感知半徑已知的情況下，滿足服務質量q要求最少需要選取K個工作節點：

1.3 最佳簇半徑

在EEGC協議中，梯度建立階段網絡耗能固定，簇的構造和簇間路由選擇兩部分的耗能與簇的“死亡”相關。綜上考慮，本協議中實現網絡節能的關鍵是使所有節點在數據傳輸階段每次傳送消息耗能最低。

因此，成員節點每傳輸L比特感知數據耗能為：

簇頭節點的能耗主要包括兩部分：接收、融合成員節點和孩子的數據消息，以及向父節點傳送數據。因此，簇頭節點每傳輸L比特數據消息的耗能為：

其中，Nchild=1是指每個簇頭節點的孩子節點數，kact=K/kexp表示每個簇的工作節點數。

為保證網絡全連通，采用簇間廣播半徑dup=3Rc。因此整個網絡每傳送L比特數據信息消耗的能量為：

對簇半徑Rc求導，得：

將式(5)代入式(10)，并令求導結果等于 0，可得最優簇半徑為：

2 EEGC協議

系統初始化，所有傳感器節點都有唯一ID號，依次為 1、2、3……n，梯度初始值為無窮大。Sink節點 ID號為0，梯度為0。表1列出了所有廣播消息以及其相應的描述信息。

表1 狀態和消息描述

2.1 梯度的建立

梯度生成階段，所有節點接收半徑Rc內的梯度廣播消息，確定自身的梯度值，并記錄相鄰節點的梯度值、能量狀態和ID號。

(1)首先，Sink節點以半徑 Rc廣播Hello消息。其他節點 i(1≤i≤n)收到廣播信息后，按照步驟(2)進行操作。

(2)高梯度節點接收半徑Rc內其他節點的Hello消息，根據廣播節點的梯度值大小修改自身的梯度。例如，節點i收到節點j發送的Hello消息，保存節點 j的消息信息。如果節點i的梯度大于節點j的梯度，則節點i修改自身梯度Gi=Gj+1，并以半徑 Rc廣播 Hello消息；否則，不修改自身梯度值。所有節點重復進行步驟(2)，直到時間tg結束。

(3)tg時刻之后，節點將存在獲得梯度和未獲得梯度兩種狀態。對于未獲得梯度的任意節點i(1≤i≤n)，需要增大自己的發射半徑發送Hello消息，以使距離最近的低梯度節點j接收到該信息。然后節點i根據節點j的響應消息修改自身梯度Gi=Gj+1，并根據接收信號的強度，調整發射功率，縮小沖突范圍。最后，節點i向鄰域內其他節點廣播自己的新梯度信息，網絡內所有節點的梯度建立完成。

2.2 簇的形成

在簇頭選擇階段，每個節點根據存儲的鄰域節點能量值和梯度值，利用式(12)計算t值，并在時刻 t以半徑Rc廣播Head消息競爭簇頭。

如果某個節點在時刻t之前收到其他節點的簇頭廣播Head消息，則節點不再廣播Head消息，直接發送Join_head消息加入該簇。若節點同時收到兩個簇頭廣播Head消息，則加入能量較大的那個簇。如果在T時刻后，節點還未收到簇頭聲明Head，則自己廣播簇頭聲明Head，宣布成為簇頭。

2.3 數據傳輸

根據簇內覆蓋算法，簇頭計算出簇內工作節點數kact=K/kexp，簇頭選擇能量較大的kact-1個成員節點，創建一個TDMA時隙調度，并把該TDMA調度廣播給這kact-1個節點。這kact-1個節點在所分配的時隙將監測數據發送到簇頭，簇內其他節點進入休眠模式。

若簇內工作節點i能量耗盡，則簇頭關閉該工作節點，并調用能量較大的休眠節點j工作，安排節點j在節點i的時隙發送信息。若簇頭節點的能量小于ECHmin，則重新競選簇頭，每個非死亡節點在半徑Rc內廣播自身能量和梯度值，然后重復2.2和2.3的步驟。簇頭節點能量閾值ECHmin為接收、融合簇內工作節點的數據消息，以及發送數據消息損耗的能量，ECHmin=(k-1)lEelec+klEDA+(lEelec+lεfsd2up)。 對于每個簇，重復進行多次簇內和簇間數據傳輸，直到簇頭的剩余能量不足以維持一次數據傳輸過程時，才重新競選簇頭，這樣可以有效地提高每次分簇的效率。

簇間數據傳輸階段，每個簇頭在3Rc半徑內廣播Child消息。內環所有簇頭i(Gi≤3)直接發送數據消息給Sink節點。外環簇頭 i(Gi＞3)存儲接收到的 Child消息，同時選擇Ej/Gj比值較大的低梯度簇頭j作為父節點，進行數據多跳傳輸。如果一條路徑失敗，則選擇3Rc范圍內的其他簇頭節點作為父節點，進行簇間信息傳遞。只有當網絡內所有節點重新進行簇的構建過程，網絡才會重新廣播Child消息構建簇間路由，否則，所有簇頭節點依照儲存的路由表傳遞數據。這種內環簇頭直接通信、外環簇頭多跳通信的方式，能夠減少內環簇頭的負載，緩解內環節點能耗過快的問題。

3 實驗驗證與仿真

為了說明算法效果，使用MATLAB對算法進行了仿真測試，仿真區域 100 m×100 m，仿真場景參數如表 2所示。

3.1 生命周期

圖1比較了LEACH和EEGC協議在不同的節點分布密度下的網絡壽命期望值。由圖1可見，針對不同的節點分布密度，EEGC協議的網絡壽命均優于LEACH。在LEACH協議中，隨著節點分布密度的加大，網絡內冗余節點越來越多，網絡壽命隨著節點分布密度的加大而逐漸降低。而由于EEGC協議采用了部分覆蓋算法，有效調動活動節點，在服務質量q=0.90和q=0.99兩種情況下，網絡壽命隨著節點分布密度的加大而延長。由圖1可以明顯看出，EEGC在延長網絡壽命方面比LEACH協議優秀。

圖2比較了EEGC協議在不同的服務質量QoS下的網絡壽命，選取的仿真節點數目n=100。由圖2可見，網絡壽命隨QoS的提高而降低，這是由于系統內單位時間內要求保持工作狀態的節點減少了，單位時間內的耗能地減少了。

表2 仿真參數

圖1 網絡壽命隨節點數目變化曲線

圖2 網絡壽命隨服務質量變化曲線

3.2 協議性能

圖3、圖4分別比較了 EEGC協議在 n=100、q=0.99/0.90以及 n=400、q=0.99/0.90場景下，網絡壽命與每輪工作節點數目的關系。由圖可見，在q=0.99條件下，網絡要求更多工作節點來換取較小的QoS優勢。

圖3 網絡壽命VS.工作節點數目(n=100)

圖4 網絡壽命VS.工作節點數目(n=400)

圖5比較了EEGC協議和LEACH在n=100條件下的實際網絡服務質量。圖6比較了EEGC協議與LEACH在n=400條件下的實際網絡服務質量。

圖5和圖6均可表明EEGC協議在保證高服務質量的同時，網絡壽命更長。同時，比較EEGC協議在q=0.99、n=400與 q=0.99、n=100兩種情況的曲線圖可知，EEGC協議在高密度環境下的網絡能耗更加均衡，網絡服務質量更高，也驗證了EEGC協議主要是針對高密度的隨機分布網絡環境。

圖5 網絡壽命VS.實際服務質量(n=100)

EEGC協議采用了部分覆蓋算法調度活動節點，有效減少了冗余節點。同時，簇和簇間路由的重構都由簇頭剩余能量值決定，在高能量、高密度的網絡中，這樣可以降低反復重新構建簇及路由的能量損耗；但是在低能量、節點稀疏的網絡，這種網絡重構機制在節能方面并無優勢。同時，本協議的空分路由策略——內環直接通信、外環多跳通信，還有待改進。下一步需要研究更合理的拓撲機制，進一步節省系統能耗，延長網絡壽命。

圖6 網絡壽命VS.實際服務質量(n=400)

[1]HEINZELMAN W，CHANDRAKSAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications， 2002，1(4)：660-670.

[2]沈波，張世永，孫亦平.無線傳感器網絡分簇路由協議[J].軟件學報，2006，17(7)：1588-1600.

[3]宋超，劉明，龔海剛，等.基于蟻群優化解決傳感器網絡中的能量洞問題[J].軟件學報，2009，20(10)：2729-2743.

[4]OLARIU S， STOJMENOVIC I.Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C].Proceedings of the IEEE INFOCOM’06.Barcelona， Spain：IEEE Press，2006-04-06-25.

[5]Zou Yi，CHAKRABARTY K.A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks[J].IEEE Transactions on Wireless Communications， 2005， 54(8)：978-991.

[6]毛鶯池，劉明，陳力軍，等.DELIC：一種高效節能的與節點位置無關的傳感器網絡覆蓋協議 [J].計算機研究與發展，2006，43(2)：187-195.