摘  要： 針對傳感器網(wǎng)絡(luò)存在的節(jié)點(diǎn)能耗過快問題，提出了一種新的分簇路由協(xié)議EEGC。該協(xié)議底層拓?fù)洳捎梅执丶按貎?nèi)部分覆蓋算法，有效地降低了網(wǎng)絡(luò)能耗。上層拓?fù)洳捎媒仡^單跳通信、遠(yuǎn)簇頭多跳通信的方式，緩解了內(nèi)環(huán)簇頭能耗過快的問題。同時，以簇頭剩余能量決定簇及簇間路由的重構(gòu)，進(jìn)一步提高了控制消息的效率。仿真驗(yàn)證表明，EEGC協(xié)議的網(wǎng)絡(luò)壽命明顯優(yōu)于LEACH。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；能量控制；分簇算法；覆蓋算法；能量洞

　節(jié)能問題一直是無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)的研究熱點(diǎn)，其中基于分簇的路由協(xié)議引起了較多的關(guān)注[1-2]。分簇協(xié)議一般采用多跳通信，但是研究發(fā)現(xiàn)，多跳通信會導(dǎo)致離Sink越近的傳感器節(jié)點(diǎn)的能量消耗越快[3]，這種現(xiàn)象導(dǎo)致在Sink周圍形成“能量洞”。參考文獻(xiàn)[4]首次提出能量洞問題在節(jié)點(diǎn)隨機(jī)均勻分布的環(huán)境中是不可避免的。同時，從延長網(wǎng)絡(luò)生命周期和網(wǎng)絡(luò)覆蓋率的角度考慮，參考文獻(xiàn)[5]重點(diǎn)討論了部分覆蓋算法，指出恰當(dāng)?shù)牟糠指采w可以減少冗余節(jié)點(diǎn)，更節(jié)省網(wǎng)絡(luò)能量。
　針對上述問題，本文提出了一種新的分簇算法EEGC，該算法主要針對節(jié)點(diǎn)同構(gòu)、節(jié)點(diǎn)隨機(jī)均勻分布的網(wǎng)絡(luò)環(huán)境。EEGC采用基于最小跳數(shù)的簇頭競爭方法、內(nèi)環(huán)簇頭直接通信以及外環(huán)簇頭多跳通信的方式，緩解了網(wǎng)絡(luò)Sink節(jié)點(diǎn)周圍能量洞的問題。同時調(diào)用部分覆蓋算法，避免了大量冗余節(jié)點(diǎn)的能耗，實(shí)現(xiàn)了一個高效的節(jié)能通信網(wǎng)絡(luò)。
1 系統(tǒng)模型和問題分析
1.1 系統(tǒng)模型
　本文假設(shè)n個傳感器節(jié)點(diǎn)隨機(jī)均勻地分布在監(jiān)測區(qū)域Aarea內(nèi)，節(jié)點(diǎn)具有相同的初始能量和能耗模型。基站部署在區(qū)域外，由位于監(jiān)測區(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)測區(qū)域面積占整個監(jiān)測區(qū)域Aarea(L×L)面積的比例，即：



　如果某個節(jié)點(diǎn)在時刻t之前收到其他節(jié)點(diǎn)的簇頭廣播Head消息，則節(jié)點(diǎn)不再廣播Head消息，直接發(fā)送Join_head消息加入該簇。若節(jié)點(diǎn)同時收到兩個簇頭廣播Head消息，則加入能量較大的那個簇。如果在T時刻后，節(jié)點(diǎn)還未收到簇頭聲明Head，則自己廣播簇頭聲明Head，宣布成為簇頭。
2.3 數(shù)據(jù)傳輸
　根據(jù)簇內(nèi)覆蓋算法，簇頭計(jì)算出簇內(nèi)工作節(jié)點(diǎn)數(shù)kact=K/kexp，簇頭選擇能量較大的kact-1個成員節(jié)點(diǎn)，創(chuàng)建一個TDMA時隙調(diào)度，并把該TDMA調(diào)度廣播給這kact-1個節(jié)點(diǎn)。這kact-1個節(jié)點(diǎn)在所分配的時隙將監(jiān)測數(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的時隙發(fā)送信息。若簇頭節(jié)點(diǎn)的能量小于ECHmin，則重新競選簇頭，每個非死亡節(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)。對于每個簇，重復(fù)進(jìn)行多次簇內(nèi)和簇間數(shù)據(jù)傳輸，直到簇頭的剩余能量不足以維持一次數(shù)據(jù)傳輸過程時，才重新競選簇頭，這樣可以有效地提高每次分簇的效率。
　簇間數(shù)據(jù)傳輸階段，每個簇頭在3Rc半徑內(nèi)廣播Child消息。內(nèi)環(huán)所有簇頭i(Gi≤3)直接發(fā)送數(shù)據(jù)消息給Sink節(jié)點(diǎn)。外環(huán)簇頭i(Gi>3)存儲接收到的Child消息，同時選擇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ò)才會重新廣播Child消息構(gòu)建簇間路由，否則，所有簇頭節(jié)點(diǎn)依照儲存的路由表傳遞數(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對算法進(jìn)行了仿真測試，仿真區(qū)域100 m×100 m，仿真場景參數(shù)如表2所示。

3.2 協(xié)議性能
　圖3、圖4分別比較了EEGC協(xié)議在n=100、q=0.99/0.90以及n=400、q=0.99/0.90場景下，網(wǎng)絡(luò)壽命與每輪工作節(jié)點(diǎn)數(shù)目的關(guān)系。由圖可見，在q=0.99條件下，網(wǎng)絡(luò)要求更多工作節(jié)點(diǎn)來換取較小的QoS優(yōu)勢。
　圖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ì)量的同時，網(wǎng)絡(luò)壽命更長。同時，比較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é)議主要是針對高密度的隨機(jī)分布網(wǎng)絡(luò)環(huán)境。

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