WSN中一種高效節(jié)能的分簇路由協(xié)議＊

程焱芳，吳玉成

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

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

針對(duì)上述問題，本文提出了一種新的分簇算法EEGC，該算法主要針對(duì)節(jié)點(diǎn)同構(gòu)、節(jié)點(diǎn)隨機(jī)均勻分布的網(wǎng)絡(luò)環(huán)境。EEGC采用基于最小跳數(shù)的簇頭競(jìng)爭(zhēng)方法、內(nèi)環(huán)簇頭直接通信以及外環(huán)簇頭多跳通信的方式，緩解了網(wǎng)絡(luò)Sink節(jié)點(diǎn)周圍能量洞的問題。同時(shí)調(diào)用部分覆蓋算法，避免了大量冗余節(jié)點(diǎn)的能耗，實(shí)現(xiàn)了一個(gè)高效的節(jié)能通信網(wǎng)絡(luò)。

1 系統(tǒng)模型和問題分析

1.1 系統(tǒng)模型

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

1.2 簇內(nèi)部分覆蓋算法

定義1 服務(wù)質(zhì)量q(the Desired QoS)定義為所有工作節(jié)點(diǎn)構(gòu)成的有效監(jiān)測(cè)區(qū)域面積占整個(gè)監(jiān)測(cè)區(qū)域Aarea(L×L)面積的比例，即：

其中，Si表示工作節(jié)點(diǎn)ni的感知范圍，K表示工作節(jié)點(diǎn)的數(shù)量。 區(qū)域 Aarea中任意一點(diǎn) Pi(x，y)∈Aarea，Pi(x，y)沒有被K個(gè)工作節(jié)點(diǎn)覆蓋的概率為：

因此，在區(qū)域 Aarea中，任意一點(diǎn) Pi(x，y)至少被其中一個(gè)工作節(jié)點(diǎn)覆蓋的概率θ為：

根據(jù)服務(wù)質(zhì)量q的定義，可知在區(qū)域Aarea中K個(gè)工作節(jié)點(diǎn)達(dá)到的服務(wù)質(zhì)量為：

其中，Rs為感知半徑。由式(4)可知，隨機(jī)部署網(wǎng)絡(luò)在區(qū)域大小和感知半徑已知的情況下，滿足服務(wù)質(zhì)量q要求最少需要選取K個(gè)工作節(jié)點(diǎn)：

1.3 最佳簇半徑

在EEGC協(xié)議中，梯度建立階段網(wǎng)絡(luò)耗能固定，簇的構(gòu)造和簇間路由選擇兩部分的耗能與簇的“死亡”相關(guān)。綜上考慮，本協(xié)議中實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)能的關(guān)鍵是使所有節(jié)點(diǎn)在數(shù)據(jù)傳輸階段每次傳送消息耗能最低。

因此，成員節(jié)點(diǎn)每傳輸L比特感知數(shù)據(jù)耗能為：

簇頭節(jié)點(diǎn)的能耗主要包括兩部分：接收、融合成員節(jié)點(diǎn)和孩子的數(shù)據(jù)消息，以及向父節(jié)點(diǎn)傳送數(shù)據(jù)。因此，簇頭節(jié)點(diǎn)每傳輸L比特?cái)?shù)據(jù)消息的耗能為：

其中，Nchild=1是指每個(gè)簇頭節(jié)點(diǎn)的孩子節(jié)點(diǎn)數(shù)，kact=K/kexp表示每個(gè)簇的工作節(jié)點(diǎn)數(shù)。

為保證網(wǎng)絡(luò)全連通，采用簇間廣播半徑dup=3Rc。因此整個(gè)網(wǎng)絡(luò)每傳送L比特?cái)?shù)據(jù)信息消耗的能量為：

對(duì)簇半徑Rc求導(dǎo)，得：

將式(5)代入式(10)，并令求導(dǎo)結(jié)果等于 0，可得最優(yōu)簇半徑為：

2 EEGC協(xié)議

系統(tǒng)初始化，所有傳感器節(jié)點(diǎn)都有唯一ID號(hào)，依次為 1、2、3……n，梯度初始值為無窮大。Sink節(jié)點(diǎn) ID號(hào)為0，梯度為0。表1列出了所有廣播消息以及其相應(yīng)的描述信息。

表1 狀態(tài)和消息描述

2.1 梯度的建立

梯度生成階段，所有節(jié)點(diǎn)接收半徑Rc內(nèi)的梯度廣播消息，確定自身的梯度值，并記錄相鄰節(jié)點(diǎn)的梯度值、能量狀態(tài)和ID號(hào)。

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

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

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

2.2 簇的形成

在簇頭選擇階段，每個(gè)節(jié)點(diǎn)根據(jù)存儲(chǔ)的鄰域節(jié)點(diǎn)能量值和梯度值，利用式(12)計(jì)算t值，并在時(shí)刻 t以半徑Rc廣播Head消息競(jìng)爭(zhēng)簇頭。

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

2.3 數(shù)據(jù)傳輸

根據(jù)簇內(nèi)覆蓋算法，簇頭計(jì)算出簇內(nèi)工作節(jié)點(diǎn)數(shù)kact=K/kexp，簇頭選擇能量較大的kact-1個(gè)成員節(jié)點(diǎn)，創(chuàng)建一個(gè)TDMA時(shí)隙調(diào)度，并把該TDMA調(diào)度廣播給這kact-1個(gè)節(jié)點(diǎn)。這kact-1個(gè)節(jié)點(diǎn)在所分配的時(shí)隙將監(jiān)測(cè)數(shù)據(jù)發(fā)送到簇頭，簇內(nèi)其他節(jié)點(diǎn)進(jìn)入休眠模式。

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

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

3 實(shí)驗(yàn)驗(yàn)證與仿真

為了說明算法效果，使用MATLAB對(duì)算法進(jìn)行了仿真測(cè)試，仿真區(qū)域 100 m×100 m，仿真場(chǎng)景參數(shù)如表 2所示。

3.1 生命周期

圖1比較了LEACH和EEGC協(xié)議在不同的節(jié)點(diǎn)分布密度下的網(wǎng)絡(luò)壽命期望值。由圖1可見，針對(duì)不同的節(jié)點(diǎn)分布密度，EEGC協(xié)議的網(wǎng)絡(luò)壽命均優(yōu)于LEACH。在LEACH協(xié)議中，隨著節(jié)點(diǎn)分布密度的加大，網(wǎng)絡(luò)內(nèi)冗余節(jié)點(diǎn)越來越多，網(wǎng)絡(luò)壽命隨著節(jié)點(diǎn)分布密度的加大而逐漸降低。而由于EEGC協(xié)議采用了部分覆蓋算法，有效調(diào)動(dòng)活動(dòng)節(jié)點(diǎn)，在服務(wù)質(zhì)量q=0.90和q=0.99兩種情況下，網(wǎng)絡(luò)壽命隨著節(jié)點(diǎn)分布密度的加大而延長(zhǎng)。由圖1可以明顯看出，EEGC在延長(zhǎng)網(wǎng)絡(luò)壽命方面比LEACH協(xié)議優(yōu)秀。

圖2比較了EEGC協(xié)議在不同的服務(wù)質(zhì)量QoS下的網(wǎng)絡(luò)壽命，選取的仿真節(jié)點(diǎn)數(shù)目n=100。由圖2可見，網(wǎng)絡(luò)壽命隨QoS的提高而降低，這是由于系統(tǒng)內(nèi)單位時(shí)間內(nèi)要求保持工作狀態(tài)的節(jié)點(diǎn)減少了，單位時(shí)間內(nèi)的耗能地減少了。

表2 仿真參數(shù)

圖1 網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)數(shù)目變化曲線

圖2 網(wǎng)絡(luò)壽命隨服務(wù)質(zhì)量變化曲線

3.2 協(xié)議性能

圖3、圖4分別比較了 EEGC協(xié)議在 n=100、q=0.99/0.90以及 n=400、q=0.99/0.90場(chǎng)景下，網(wǎng)絡(luò)壽命與每輪工作節(jié)點(diǎn)數(shù)目的關(guān)系。由圖可見，在q=0.99條件下，網(wǎng)絡(luò)要求更多工作節(jié)點(diǎn)來換取較小的QoS優(yōu)勢(shì)。

圖3 網(wǎng)絡(luò)壽命VS.工作節(jié)點(diǎn)數(shù)目(n=100)

圖4 網(wǎng)絡(luò)壽命VS.工作節(jié)點(diǎn)數(shù)目(n=400)

圖5比較了EEGC協(xié)議和LEACH在n=100條件下的實(shí)際網(wǎng)絡(luò)服務(wù)質(zhì)量。圖6比較了EEGC協(xié)議與LEACH在n=400條件下的實(shí)際網(wǎng)絡(luò)服務(wù)質(zhì)量。

圖5和圖6均可表明EEGC協(xié)議在保證高服務(wù)質(zhì)量的同時(shí)，網(wǎng)絡(luò)壽命更長(zhǎng)。同時(shí)，比較EEGC協(xié)議在q=0.99、n=400與 q=0.99、n=100兩種情況的曲線圖可知，EEGC協(xié)議在高密度環(huán)境下的網(wǎng)絡(luò)能耗更加均衡，網(wǎng)絡(luò)服務(wù)質(zhì)量更高，也驗(yàn)證了EEGC協(xié)議主要是針對(duì)高密度的隨機(jī)分布網(wǎng)絡(luò)環(huán)境。

圖5 網(wǎng)絡(luò)壽命VS.實(shí)際服務(wù)質(zhì)量(n=100)

EEGC協(xié)議采用了部分覆蓋算法調(diào)度活動(dòng)節(jié)點(diǎn)，有效減少了冗余節(jié)點(diǎn)。同時(shí)，簇和簇間路由的重構(gòu)都由簇頭剩余能量值決定，在高能量、高密度的網(wǎng)絡(luò)中，這樣可以降低反復(fù)重新構(gòu)建簇及路由的能量損耗；但是在低能量、節(jié)點(diǎn)稀疏的網(wǎng)絡(luò)，這種網(wǎng)絡(luò)重構(gòu)機(jī)制在節(jié)能方面并無優(yōu)勢(shì)。同時(shí)，本協(xié)議的空分路由策略——內(nèi)環(huán)直接通信、外環(huán)多跳通信，還有待改進(jìn)。下一步需要研究更合理的拓?fù)錂C(jī)制，進(jìn)一步節(jié)省系統(tǒng)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命。

圖6 網(wǎng)絡(luò)壽命VS.實(shí)際服務(wù)質(zhì)量(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]沈波，張世永，孫亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào)，2006，17(7)：1588-1600.

[3]宋超，劉明，龔海剛，等.基于蟻群優(yōu)化解決傳感器網(wǎng)絡(luò)中的能量洞問題[J].軟件學(xué)報(bào)，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：一種高效節(jié)能的與節(jié)點(diǎn)位置無關(guān)的傳感器網(wǎng)絡(luò)覆蓋協(xié)議 [J].計(jì)算機(jī)研究與發(fā)展，2006，43(2)：187-195.