一種雙層樹型高能效多鏈路由算法*

胡中棟,張 康,王振東

(江西理工大學信息工程學院,江西 贛州 341000)

無線傳感器網絡WSN(Wireless Sensor Networks)是廣泛應用于氣象、環境、農業和軍事等領域[1]的一種信息獲取及處理技術,其綜合了傳感器技術、微電子技術和無線通信技術等多學科技術,被認為是本世紀改變世界的十大技術之一[2]。WSN的主要組成部分是作為微電子設備的傳感器節點,一般外形小巧,功耗較低,能量有限且不可再生,因目前對節點生存時間有較大影響的電池技術沒有突破性發展,于是對網絡結構特性和傳輸協議的研究是提高網絡壽命的重要研究方向。

為減少網絡能耗、提高網絡壽命,Lindsey S等人在LEACH算法[3]的基礎上改進提出了PEGASIS算法[4],該算法采用鏈式結構,網絡結構固定,減少了簇結構算法的頻繁重構開銷,但由于網絡結構是一條長鏈,時延[5]較大,不適用實時性要求高的場景,且一旦鏈中某一節點失效,則整個網絡癱瘓,魯棒性[6]差。為此,Quazi等人又改進提出了COSEN算法[7],其采用多鏈組網,有效降低網絡時延,增強了網絡魯棒性,但多鏈組網也未能解決交叉鏈和長鏈多、數據逆傳遞嚴重等問題。鑒于上述,本文提出一種雙層樹型高能效多鏈路由算法TTEMR(A Two-layer Tree-type Energy Efficient Multi-link Routing Algorithm)。

1 相關研究

1.1 經典協議

經典的平面型路由協議由于傳輸跳數過多,導致傳輸時延高、能量浪費嚴重,而層次路由協議的分簇、成鏈等思想能有效聚合數據,降低傳輸平均路徑長度,減小時延,已成為當前路由算法研究的熱點。

1.1.1 LEACH協議描述

LEACH協議算法采用分簇思想,成簇階段,通過隨機選取節點來作為簇頭,非簇頭節點就近加入簇。數據傳輸階段,簇內節點將數據發送給簇頭,然后簇頭將數據匯聚融合[8]后直接發給Sink節點。

1.1.2 PEGASIS協議描述

PEGASIS協議算法采用鏈式結構,建鏈階段通過貪婪算法將網絡中的所有節點組織成一條鏈路,每輪隨機選擇一個節點充當與Sink通信的鏈頭。數據傳輸階段,采用令牌機制,沿形成的鏈路逐跳收集、融合數據,直至傳送至鏈頭,最后由鏈頭將數據直接發送給Sink節點。

1.1.3 COSEN協議描述

COSEN協議算法在建鏈階段采用貪婪算法,當形成的鏈上節點數占全網節點數20%時,終止建鏈,從下跳節點開始重復上述步驟建立新鏈,直至全網節點皆已成鏈。然后選取每條鏈上節點剩余能量最大的節點為鏈頭,各鏈頭再建立鏈頭鏈,鏈頭鏈選取剩余能量最大的為主鏈頭。數據傳輸階段,各鏈頭分別發送令牌以控制本鏈節點數據收集傳輸,最終主鏈頭將各分鏈鏈頭數據收集融合并傳遞至Sink節點。

1.2 算法分析

對上述三種協議算法進行優缺點分析:

1.2.1 LEACH算法

簇頭隨機周期性選取可有效減少網絡能耗分部不均,實現網絡能耗負載均衡。但仍存在以下缺點:①簇頭以單跳通信方式與Sink傳輸數據,造成簇頭節點能量的大量浪費;②由于簇頭是隨機選取,易導致簇頭位置過偏或過于集中。

1.2.2 PEGASIS算法

算法采用鏈式結構,網絡結構固定,節點間平均路徑長度短,數據傳輸階段每次只有一個節點與Sink通信,減少了簇結構算法的頻繁重構開銷,但 PEGASIS 算法仍存在著以下不足:①在成鏈過程中容易形成長鏈,位于長鏈上的節點死亡較快;②總鏈路較長,從鏈兩端到鏈頭的傳輸時延長;③選擇鏈頭未考慮距離影響造成遠離Sink的鏈頭節點過快死亡;④一旦有節點死亡,整個WSN需要重新構建鏈路,網絡維護成本高。

1.2.3 COSEN算法

算法采用多鏈方式,每個分鏈數據收集和發送同時進行,可大大降低網絡時延。當網絡中某個節點失效死亡時,只對當前分鏈和鏈頭鏈進行維護即可,維護成本低,魯棒性高。但依然有以下不足:①交叉鏈多,成鏈陷入局部最優;②分鏈構造中后期鏈端為尋找下一跳未入鏈的節點易形成長鏈結構;③鏈頭選取未考慮距離和位置問題易導致鏈頭鏈形成超長鏈,加重數據逆傳遞[9]。

2 TTEMR算法

2.1 分鏈成鏈

首先對Sink附近的節點進行不入鏈操作,然后采用貪婪算法進行成鏈,但在成鏈過程中采用啟發式算法進行優化,對孤立點[10]進行樹型[11]結構化處理。

2.1.1 不入鏈處理

由于鏈的單向傳遞特點,會使部分節點集將數據向遠離Sink的方向傳遞,然后通過某幾個節點匯聚融合后再向Sink發送,這稱為數據的逆傳遞。

因為Sink節點靠近WSN但不位于其內,若靠近Sink的普通節點不將其作為數據傳遞的下一跳,而是選擇與距離較遠的節點成鏈,則會造成該節點數據最終逆傳遞至主鏈頭,不但加重了該分鏈和鏈頭鏈能耗,而且增加了網絡時延,所以合理分配Sink附近節點的傳遞路徑可有效降低全網能耗。如圖1所示,因為dbS≤dba、dcS≤dcd,所以節點b、c直接向Sink傳遞數據而不選擇與其他節點成鏈。

圖1 Sink附近節點路徑處理

2.1.2 啟發式算法

①消除鏈內交叉

最優鏈路中必定不含有交叉路徑[12],因此對于一條鏈內出現交叉情況時要將它消除。如圖2所示,找到兩個交叉路徑af和de,刪除其連接后連接ae和df。

②消除鏈間交叉

雖然通過消除鏈內交叉可保證WSN局部區域不再出現交叉,但由于整個區域內存在多條鏈中,分鏈之間還會出現交叉情況,鏈間交叉是算法局部最優而非全局最優的直接表現。如圖3所示,找到交叉鏈路bf和ec,刪除其連接,建立bc和ef鏈接。

圖2 消除鏈內交叉

圖3 消除鏈間交叉

③消除長路徑

長鏈的產生一般是由于靜態規則化分建鏈空間或算法陷入局部最優造成的,原本相距較近的節點卻因為所屬空間不同而不能夠加入同一條鏈,這造成了數據傳遞能耗浪費、時延增長。如圖4所示,找到長鏈ab,刪除ab連接,連接ac,并將節點b加入距離較近的節點f所在的鏈路。

圖4 消除長鏈

設dbound為長短鏈界限值,定義如式(1),兩節點間距離小于等于dbound則為短鏈,超過dbound則為長鏈。

dbound=αE(dij)

(1)

式中:α為長鏈系數,E(dij)為節點i到下一跳節點j距離的期望。根據文獻[13]實驗可知,α初始值為1.5時效果最好,但當遇到以下兩種情況時,長鏈系數的取值應該適當增大:①WSN稀疏時,網絡中短鏈較少,長鏈較多,導致成鏈數較多、孤立點較多,此時鏈的維護成本將增大。②在WSN運行的中后期,由于出現了大量節點死亡,導致網絡節點間距增大,此時可適當增大長鏈系數避免形成過多分鏈和孤立點。

2.1.3 孤立點樹型結構化處理

孤立點直接與Sink節點通信會造成能量損耗過快,因此將孤立點以合適的方式加入附近的分鏈才是首選,產生孤立點主要有下面幾種情況:①在消除鏈內、鏈間交叉時,導致個別節點孤立于分鏈附近;②在網絡邊緣或稀疏區域產生的長鏈,通過刪除長鏈會產生離周圍分鏈都較遠的孤立點;③中后期網絡中節點不斷死亡,導致產生距離過遠的孤立點。

如圖5(a)所示,節點d為消除交叉鏈時產生的孤立點,節點e為上述②、③情況產生的孤立點。文獻[13]中對孤立點的處理是首先找到距離孤立點d最近的節點b,判斷節點b的上一跳節點a和下一跳節點c到孤立點d的距離,將孤立點d插入節點b和距離較近節點a之間,形成如圖5(b)所示的鏈路。

TTEMR算法運用樹的思想,直接比較孤立點d到節點a、b、c的距離,建立如圖5(c)所示距離較近的bd連接,b為父節點,d為其子節點。對于孤立點e,由于到周圍節點距離都為長鏈,則尋找距離孤立點e最近的分鏈節點或Sink節點構建鏈路,如圖5(c)建立ec鏈路,c為父節點,e為其子節點。

圖5 孤立點入鏈

本文采用文獻[14]中的能量模型,假設每個數據包有kbit的數據,則發送端消耗的能量為式(2):

(2)

(3)

接收端消耗的能量為式(4):

ERX=kEelec

(4)

數據匯聚融合消耗的能量為式(5):

EDA=kEda

(5)

式中:Eelec=50 nJ/bit,表示收發電路能耗;Eda=5 nJ/bit,表示單位數據融合能耗;dij表示節點i到節點j的距離;d0表示能量損耗的界限值。

設節點a為靠近鏈頭方向,則圖5(b)鏈路段bda能耗為式(6),圖5(c)鏈路樹dba能耗為式(7):

(6)

(7)

因為dab

2.2 鏈頭鏈成鏈

2.2.1 選取主鏈頭

在鏈式協議算法中,主鏈頭和分鏈鏈頭的選取會對WSN中節點數據的整體傳遞方向產生較大影響,若主鏈頭和分鏈鏈頭靠近Sink,則網絡中數據總體向Sink方向移動;若主鏈頭和分鏈鏈頭遠離Sink,則網絡中數據總體向遠離Sink方向移動,最后通過主鏈頭轉發至Sink,因此合理選取主鏈頭和分鏈鏈頭可減少WSN內的數據逆傳遞。

在COSEN算法中,主鏈頭和分鏈鏈頭的選取只考慮了剩余能量,這導致距離Sink較遠的節點被選為主鏈頭、不同分鏈中距離較遠的兩個節點可能會被選為相鄰鏈頭,形成如圖6(b)中ed、db、主鏈頭c到Sink這樣的長鏈,且ed鏈會引起嚴重的數據逆傳遞。TTEMR算法綜合考慮了節點剩余能量和到Sink的距離,根據式(8)在全網節點中選取主鏈頭C0。

(8)

式中:Ei為節點i的剩余能量,di to S為節點i到Sink節點的距離,N為全網節點數,η越大被選為主鏈頭概率越大。

2.2.2 選取分鏈鏈頭

分鏈鏈頭選取步驟如下:①令主鏈頭C0所在分鏈編號為0,主鏈頭所在的鏈稱為主分鏈,主鏈頭也是主分鏈的分鏈鏈頭。

②確定距主分鏈最近分鏈的鏈頭Ck。距離C0最近的非本鏈節點所在的鏈就是與主分鏈最近的分鏈,令該分鏈為當前鏈,鏈號為k,根據式(9)選取鏈頭Ck。

③確定距當前鏈最近的分鏈的鏈頭Ck+1。距離當前鏈鏈頭最近的無鏈頭非本鏈節點所在的鏈就是與當前鏈最近的分鏈,令該分鏈為當前鏈,鏈號為k+1,根據式(9)選取鏈頭Ck+1。

④重復步驟③,直至每個分鏈確定鏈頭。

(9)

2.2.3 鏈頭鏈成鏈規則

TTEMR算法鏈頭鏈成鏈規則如下:①若某一分鏈鏈頭到主鏈頭或其他分鏈鏈頭的距離大于等于到Sink節點的距離,則應直接與Sink通信以減少數據逆傳遞。如圖1,鏈頭C3到相鄰鏈頭的距離d(C3,C0)≥d(C3,S)、d(C3,C1)≥d(C3,S),所以鏈頭C3直接向Sink傳遞數據而不參與鏈頭鏈成鏈。②采用貪婪算法以主鏈頭為起始點,將其余各分鏈鏈頭組成鏈頭鏈;③對成鏈過程中產生的鏈內交叉按2.1.2①節消除鏈內交叉進行優化;④對成鏈過程中產生的孤立點鏈頭作如下處理:(a)若相鄰鏈頭間為短鏈則將孤立點鏈頭按2.1.3節孤立點樹型結構化處理;(b)若相鄰鏈頭間皆為長鏈則首先尋找距離孤立點鏈頭最近的相鄰鏈頭Ck(k=0,1,2,…),鏈頭Ck所在分鏈編號k,然后尋找孤立點鏈頭距離分鏈k上最近的節點j,將孤立點鏈頭作為子節點加入分鏈k,j為其父節點,最后孤立點鏈頭通過分鏈k中的普通節點中轉傳遞數據至相鄰鏈頭Ck。

在數據傳輸階段,各分鏈鏈頭控制本鏈令牌,收集融合本鏈數據。主鏈頭控制鏈頭鏈令牌,收集融合各分鏈鏈頭數據并最終傳遞至Sink節點。

3 算法仿真與分析

為了驗證TTEMR算法的性能,本文對該算法進行了MATLAB 模擬仿真實驗,并與LEACH、PEGASIS、COSEN算法進行對比。仿真區域為100 m×100 m,區域內節點隨機分布且不能移動,當節點剩余能量低于1%后則認為該節點死亡,仿真參數見表1。

3.1 節點成鏈情況分析

圖6(a)、6(b)分別為PEGASIS和COSEN算法的鏈式結構,可以看出這兩種算法成鏈雜亂無章,交叉鏈、長鏈多。圖6(b)中COSEN算法鏈頭鏈幾乎全是長鏈,其中ed鏈將數據向遠離Sink方向傳遞,數據逆傳遞嚴重。圖6(c)、6(d)分別為TTEMR算法底層分鏈結構和頂層鏈頭鏈結構,有明顯樹型特征,節點間跨度小,成鏈區域自適應,分鏈長度適中且沒有交叉鏈,長鏈較少,且長鏈長度比PEGASIS和COSEN算法中的長鏈短,圖6(d)中鏈頭數據總體向Sink方向傳遞,因為鏈頭g到Sink節點的距離小于等于到其他鏈頭的距離,所以鏈頭g不參與鏈頭鏈成鏈,有效避免了逆傳遞帶來的能量消耗。

3.2 能耗分析

本文以全網節點向Sink發送一次數據為一“輪”,對比四種算法每輪存活節點數,從圖7可以看出,TTEMR算法相對于LEACH、PEGASIS、COSEN算法,首節點死亡輪數和最后一個節點死亡輪數都有明顯的延長,節點死亡輪數曲線在最上方。這是由于TTEMR算法采用了樹型成鏈方法,優化了主鏈頭、分鏈鏈頭選取策略,有效減少了長鏈節點傳輸能耗和網絡數據逆傳遞情況。

圖7 每輪存活節點對比

從WSN開始運行到第一個節點死亡所經歷的輪數稱為穩定周期,從網絡開始運行到50%的節點死亡所經歷的輪數稱為生命周期。由表2可知,TTEMR算法穩定穩定周期比LEACH、PEGASIS、COSEN提升約145%、227%、37%,生命周期提升約89%、44%、12%,在網絡20%、80%節點死亡情況下,TTEMR算法仍比上述三種算法有較明顯的提升。

由圖8可知,在每輪收集數據后,COSEN算法全網剩余能量僅比PEGASIS略高,這是因為其并沒有從根本上解決能耗浪費嚴重的長鏈和數據逆傳遞問題,而TTEMR每輪全網剩余能量均高于LEACH、PEGASIS、COSEN這三種算法,這表明TTEMR在網絡節能方面更加優越。

表2 網絡生存周期對比

圖8 網絡剩余總能量對比

3.3 單位鏈路段平均路徑長度分析

本文稱兩個相連接的底層節點間的鏈路為單位鏈路段,則所有單位鏈路段路徑長度之和除以單位鏈路段數量為單位鏈路段平均路徑長度,簡稱平均路徑長度。其反應成鏈規則的優劣,平均路徑長度越短則成鏈規則越合理,傳遞數據越節約能量。

圖9中,PEGASIS、COSEN、LEACH算法前期平均路徑長度沒有改變是因為網絡中沒有節點死亡,網絡結構沒有變化,而LEACH算法每幾輪便重新隨機選取簇頭,導致網絡結構變化頻繁,因此平均路徑長度變動幅度大,且LEACH算法的平均路徑最長,這是因為其普通節點以單跳方式向簇頭傳遞數據;COSEN算法的節點間平均路徑比PEGASIS略短,因為其未從根本上減少交叉鏈和長鏈;而TTEMR算法的平均路徑長度較其他算法有較明顯降低,這是因為在鏈路中采用了啟發式算法和樹型結構優化,消除了交叉鏈,減少了長鏈路。

圖9 單位鏈路段平均路徑長度對比

4 結束語

本文在分析了LEACH、PEGASIS、COSEN協議算法優缺點的基礎上,提出了TTEMR算法。TTEMR將網絡構造成雙層樹型多鏈路結構,分鏈和鏈頭鏈均通過啟發式算法優化,并對網絡孤立點進行樹型結構化處理,降低了數據傳遞路徑長度;通過優化主鏈頭和分鏈鏈頭的選取策略及成鏈規則,并對Sink附近的普通節點和鏈頭作不入鏈操作,減弱了網絡的數據逆傳遞。本文對每輪節點的存活數量、網絡的穩定周期和生命周期、每輪剩余總能量及單位鏈路段平均路徑長度這五項性能指標進行仿真實驗,仿真實驗結果顯示,TTEMR算法在上述五項性能指標對比中表現比其他三種算法優異。但TTEMR需要構造樹型結構,計算量比COSEN要大,鏈頭鏈需要多跳中轉,所以延遲略大于COSEN,在實時傳輸場景下有所受限。