基于蟻群算法的非均勻分簇水聲傳感網能量優化路由研究

王 磊,喬 莉,齊俊艷,劉志中

(1.河南理工大學 計算機科學與技術學院,河南 焦作 454000;2.大連理工大學 海岸和近海工程國家重點實驗室,遼寧 大連 116024)

0 概述

水聲傳感網因其應用前景廣闊,受到各國研究學者們的重視[1-3]。但由于節點能量受限,水下通過聲波傳輸需要消耗更多能量,因此提高能量利用率、延長網絡運行時間的能量優化方法是研究重點。對水聲傳感器網絡能量優化方法的研究應結合網絡自身特點,當前主要能量優化方法包括物理層數據傳輸優化、節點部署優化、網絡層路由協議優化等。其中,網絡層路由協議的優化方法由于具有更高的實用性、健壯性、穩定性、有效性等特性,成為學者們解決水聲傳感網絡能量問題的核心方法[4-6]。

但由于無線傳感網在水下受到帶寬窄、誤碼率高、節點存儲能量有限又不易更換等諸多因素[7]的影響,網絡的存活周期大幅降低,因此需設計一種降低并均衡能量損耗、延長網絡收集時間的路由算法。由于分簇算法能夠把較大規模的網絡分成幾個獨立的區,每個簇首在消息傳輸前進行消息聚合和處理,以此提高整個網絡的消息收發能力,并且該算法具有低功耗、易擴展的優點,因此獲得了廣泛的應用。LEACH[8]是針對陸地無線傳感網的一個集簇分層協議,此協議中簇首隨機選擇且單跳傳輸,但在水下環境中聲信號衰減嚴重且能量耗損與距離成正比,這使得與基站距離較遠的節點提前失效,降低網絡生存周期。鑒于此,有學者提出簇間采用多跳路由方式發送數據[9],提高能量利用率,但由于多跳傳輸造成距離基站近的節點需承當更多的傳播使命而變成“熱區”漏洞。因此,學者們提出了非均等成簇EEUC[10]算法,根據節點到基站距離不同形成大小不均等的簇,到基站距離越近簇半徑越小、成員數越少,從而緩解“熱區”問題。能量均衡的非均等成簇DEBUC[11]采用基于時間的簇首競爭僅考慮節點所剩能量,一定程度上規避了能量較少的節點參加競選,但并未考慮節點到SINK節點間距與能量損耗成比例的情況。文獻[12]的EOUCR協議對DEBUC算法進行改進,簇頭競選考慮節點所剩能量、與Sink間距和相鄰節點平均剩余能量的因素,但沒有考慮到競選成功的簇頭是否能充分發揮作用;同時,簇間采用貪婪算法進行多跳傳輸,簇間路徑不具有動態性,尋找的路徑亦不是能耗最低的。能量高效的多跳非均等成簇EEMUC[13]算法根據節點綜合屬性值選舉簇首,雖然在一定程度上提高了水聲傳感網能量的利用率,延長了網絡的存活周期,但隨著傳感網的運轉,節點綜合屬性值減小,網絡能耗急劇增加,同時多跳傳輸路徑并非最優路徑。

為解決簇頭分布不均勻、水聲能耗不均衡、多跳傳輸路徑非最優以及參數因素考慮不全等問題,本文設計一種非均勻成簇及簇間路由能量優化算法,并通過仿真實驗進行對比分析。

1 網絡與能耗模型

1.1 網絡模型

為了方便研究路由算法對水下網絡性能的影響,本文考慮二維靜態水下傳感網,對改進算法的網絡模型作如下假設:

1)所有節點具有相似的處理/通信能力、初始能量相同且具有唯一的ID號;

2)所有節點可以通過水聲信號強度來測算到基站距離,自動控制發射功率以減少能耗;

3)節點部署在水下特定范圍內,位置不變且能量有限,而Sink節點有持續的能量源不許考慮能耗;

4)所有節點鏈路對稱可感知自己所剩能量并進行數據融合。

二維靜態水下傳感網絡模型如圖1所示。

圖1 二維靜態水下傳感網絡模型

1.2 能耗模型

水下傳感器網絡通過聲信號作為信息載體把數據傳播出去,不同于陸地節點的能量消耗,水下傳感節點的能耗隨著距離的增加成指數級增長,且水下節點的能耗主要由傳輸能耗構成。本文算法采用與文獻[14]相同的水聲通信能耗模型,式(1)給出了節點能耗模型:

(1)

其中,f是聲信號頻率,d是傳播距離,k為路徑耗損指數。式(2)是由于多普勒效應而造成與聲信號頻率f關聯的能量衰減指數:

2.75×10-4f2+0.003

(2)

2 蟻群優化的成簇算法

改進的蟻群優化成簇算法流程如圖2所示。在水下傳感網絡的初始階段,基站首先廣播一條提前分配給各個節點的TDMA時隙消息,節點在收到這條消息后,根據接收到信號強度不同估算到匯聚節點間的距離,節點據此確定信號的發射功率及如何進行分簇。

圖2 改進的蟻群優化成簇算法流程

對本文算法的設計優化,每一輪均包含非均等成簇和簇間多跳傳播2個階段。首先節點形成一個0-1之間的隨機數u,然后計算成為待選簇首的閾值T(n),閾值T(n)與u進行比較,若u

2.1 非均等成簇

2.1.1 候選簇首生成

式(3)、式(4)分別為EOUCR算法和本文提出的改進算法的簇首選舉閾值公式。從式(3)可以看出,原EOUCR算法僅考慮了節點的所剩能量,并沒有考慮候選簇首與匯聚節點距離。對此,改進后的閾值公式增加了節點自身所剩能量與到基站距離,一定范圍內規避了所剩能量較少、距離基站較遠的節點參與競選。若參選節點的所剩能量較充裕,到基站距離較近時,此節點有更大幾率變成候選簇首;同時,考慮到隨著網絡的運行節點能量一直在減少,這導致被選為候選簇首的節點數量越來越少,為此增加能耗因子γ(1-Ei-res/Ei-init)對閾值大小進行調整,能更好地平衡網絡能耗。閾值T(n)new計算公式如式(4)所示。

(3)

(4)

其中,α、β、γ為參數控制因子且α+β+γ=1,p為簇頭數目與總節點數目比重,r為當前輪數,在前r×mod(1/p)輪中,沒有參選過候選簇首的所有節點組成的一個群集G,Ei_cur為節點所剩能量,Ei_init為節點初始能量,daver為節點到基站的平均距離大小,dmax、d(i,bs)分別為節點到基站的最大距離與當前節點到基站的距離。

2.1.2 節點競爭半徑計算

由于水聲網絡對能量的要求較為苛刻,為此,參考文獻[15]中節點競爭半徑的計算,引入因節點所剩能量和到基站的距離而動態變化的節點競爭半徑Rcom,計算公式如式(5)所示。

(5)

其中,ξ、φ為參數控制因子,Eaver為節點平均剩余能量,R0為節點最大競爭半徑,其余參數與式(3)意義相同。在網絡初始時期,節點初始能量相等,競爭半徑大小主要取決于節點與基站的距離,隨著網絡的運轉,節點的能量在減少,這時競爭半徑由節點所剩能量和到基站的距離共同決定,由此形成的競爭半徑不會由于遠離基站而保持著較大的簇規模,控制簇頭的分布范圍,從而均衡節點能量耗損。

2.1.3 成簇權值計算

水聲無線傳感網的生存周期能否得以延長主要為能否降低節點能耗,因此,需考慮簇首的能耗,簇首耗能不僅包含簇間數據傳輸而且包含簇內數據收集,所以,在節點選擇入簇時要考慮節點的入簇權值。本文算法在參考了文獻[16]中入簇權值(式(6))的基礎上進行改進,改進算法的入簇權值不僅考慮了簇首的能量剩余、到基站距離,同時考慮到簇內成員數目。改進成簇權值計算函數Wi如式(7)所示。

(6)

(7)

其中,λ1、λ2、λ3為參數控制因子且λ1+λ2+λ3=1,Ech-init為簇節點初始能量,Ech-cur為簇節點所剩能量,d(i,bs)與式(3)意義相同,d(i,ch)為節點i到簇首的間距,Nnb為當前簇首的成員數目,N為總結點數目。從式(6)可知,當節點所要加入簇的簇首所剩能量Ech-cur越大、兩者的歐式間距d(i,ch)越小且簇內成員數目Nnb較少時,則節點更有可能進入該簇,實現合理均衡分簇。

2.2 簇間多跳路由

在簇間多跳路由階段,對于如何選擇最優的通信路徑問題,本文通過改善蟻群算法的啟發函數,以找到能量消耗盡量小、跳數路徑盡量最優的途徑。蟻群算法[17]用于通過信息素痕跡和啟發函數信息的指引來構造最優路徑。

2.2.1 啟發函數的改進

蟻群算法起初用于解決旅行商問題[18],僅考慮兩點間的距離并且在多路徑優化方面有很好的效果。若把此算法引入傳感網用來尋找最優路徑問題,不能單一考慮兩節點間距。針對文獻[19]中啟發函數(如式(8)所示)僅考慮到簇節點間距及剩余能量所帶來的因跳數較多而造成的能耗問題,本文改進的啟發函數在考慮了簇節點間距及剩余能量的同時考慮到了節點跳數問題,由此,本文新啟發函數定義如式(9)所示。

(8)

(9)

2.2.2 信息素更新

螞蟻k從簇節點i跳轉到簇節點j后,要對此段路上的信息素按式(10)進行更新:

τ(i,j)new=(1-×Δt)×τ(i,j)old+Δτ(i,j)

(10)

(11)

(12)

其中,e為默許的信息素揮發系數,ω為默許的信息素局部更新增量。由于傳播距離和跳數共同決定數據的能耗,因此從式(8)可知,新的啟發函數將降低節點傳播能耗。

2.2.3 路徑選擇概率

螞蟻k在t時間內從節點i跳轉到節點j,可由式(13)、式(14)的選取函數來決定:

(13)

(14)

其中,θt(i,j)為t時間從節點i到節點j的決策因子,Zk(i)為螞蟻k在節點i下一跳簇節點群集,q0為控制采取先驗常識與摸索新路徑的緊要性,規避節點能耗不均的情況,q是0-1之間的隨機數,若q≤q0,則選取決策因子極大的節點,反之,則根據下一跳節點的幾率進行選取。決策因子θt(i,j)的計算如式(15)所示。

θt(i,j)=ατt(i,j)+βηt(i,j)

(15)

其中,τt(i,j)表示t時刻鏈路i節點與j節點間的信息素濃度,ηt(i,j)表示在同樣的鏈路下的啟發函數,α、β分別為信息素濃度和啟發函數的參數控制因子。

3 仿真實驗與結果分析

本文算法使用Matlab仿真軟件進行仿真實驗,針對水下傳感器網絡的環境特性,將200個傳感節點隨機部署在1 000 m×1 000 m區域中,基站位置為(500 m,1 050 m)。仿真實驗實現對LEACH、EEUC、EEMUC和本文算法在網絡穩健性、簇首能耗和網絡所剩能量方面的分析對照。仿真參數如表1示。

表1 實驗仿真參數設置

節點存活數量多少是權衡水聲傳感網性能的指標之一。

如圖3所示,在仿真輪數相同的情況下,本文算法一直都較LEACH、EEUC和EEMUC算法的存活節點數多且最晚死亡,這是由于本文算法成簇時包括了節點所剩能量、到基站間距大小,同時在節點入簇時考慮了成簇能耗且簇間使用改善的蟻群算法進行消息的多跳傳輸,從而更有利于均衡能耗。

圖3 4種算法的生存節點數目比較

圖4(a)～圖4(d)分別表示在網絡沒有任何節點失效時4種算法的簇首個數分布情況。

圖4 4種算法簇首個數分布情況

網絡拓撲結構的穩健性取決于節點的存活數和簇首數目的變動范圍。由圖4可知,LEACH算法簇首變動范圍[7,28],高于其他2種算法,其主要原因是LEACH采用隨機選取策略使簇首很難控制;EEUC算法簇首變動范圍[9,19],較LEACH算法的簇首變動范圍有所縮減,其原因是EEUC算法在簇首競選時加入了節點的所剩能量,從而在一定程度上控制了簇首變動范圍;EEMUC算法簇首變動范圍[12,19],本文算法為[13,18],簇首變動范圍最小。這是由于本文算法對閾值公式進行改進優化選舉簇首,考慮節點所剩能量同時考慮節點與基站間距大小,節點入簇時考慮成簇能耗,這保證了最終簇首在局部范圍內生成,故簇首變動范圍較小,網絡拓撲結構較穩定,這也與圖3中的本文算法的節點存活曲線相一致。

如圖5所示,本文算法簇首耗能最少,其原因是本文算法簇首采用多跳的方式與基站進行數據傳輸,且傳輸路徑是根據改進蟻群算法探索到的最好途徑;EEMUC與EEUC算法簇首耗能次之;LEACH算法的簇首耗能最大,這不僅因為其簇首采取隨機選舉策略,而且也由于簇首單跳方式進行消息傳遞,所以與基站通信耗能較大。

圖5 簇首耗能之和對比

如圖6所示,LEACH算法網絡能耗最大,這是因為簇首分布不均,距離更遠的節點單跳傳輸需耗損大量能量,所以網絡耗能最大、生存時間最短;EEUC算法網絡耗能次之,其原因是簇首的選舉考慮節點能量且多跳傳輸,與LEACH算法相比網絡耗能有一定的減少;EEMUC算法又較EEUC能耗有所縮減,是因為簇首的競選考慮了節點能量、到基站間距和節點度,不僅簇內消息接收且簇間數據傳輸均有足夠的能量,但隨著網絡的運轉,簇首得不到合理選擇,能量耗損急速增長;本算法網絡能耗最少,主要由于對簇首閾值進行改進,選舉合理的簇首且在節點入簇時考慮入簇耗能并加入簇首能量較大的簇,在簇間引入改進的蟻群算法得到最優數據傳輸路徑,使能量消耗進一步減小、生存周期得到延伸。

圖6 網絡所剩能量對比

4 結束語

為平衡水聲無線傳感網的能耗、延長網絡生存周期,本文設計一種非均勻成簇及簇間路由能量優化的算法。該算法簇首閾值公式考慮了節點所剩能量、到基站距離與能耗因子,隨著網絡的運行,選舉的簇首不會因節點所剩能量的減少而出現不均勻的情況;引入的競爭半徑隨著節點能量多少與到基站距離大小而動態變化,從而均衡節點能耗;改進的入簇權值考慮了簇首能量、節點到簇首距離與簇內成員數目,實現合理均衡分簇;簇間引入改善的蟻群算法,不僅啟發函數考慮了節點能量、節點跳數與下一跳轉發節點距離,且在信息素更新時引入簇節點所剩能量百分比,以便在尋找到最優的數據傳輸路徑時規避信息素濃度高而節點所剩能量少的情況,延長網絡生存時間。仿真結果表明,與LEACH、EEUC和EEMUC算法相比,該算法平衡了傳感網能量耗損、提升了能量使用率,延長了傳感網生存周期。