三步遞進式蟻群算法在無線傳感器網絡中的應用①

朱大偉,李紀欣

1(太原科技大學 計算機科學與技術學院,太原 030024)

2(中國電子科技集團公司第三十三研究所 科技發展事業部,太原 030032)

無線傳感器網絡(Wireless Sensor Network,WSN)[1]是由大量靜止或移動的傳感器節點組成,節點通過自組織的無線通信協議實現數據處理、傳輸以及通訊等功能形成的分布式并行系統.近年來在野外監控、軍事監測等眾多領域受到廣泛關注和應用.WSN 節點[2]一般隨機部署在目標監測區域內,節點能量通過自身干電池提供,由于地理環境和節點的分布特點,更換電源的可操作性差,所以能量成為制約無線傳感器網絡生命周期的首要因素.為了充分合理利用無線傳感器網絡,依據無線傳感器網絡節點隨機分布和節點能量有限的兩個特性.兩個問題需要著力解決,一個是在隨機分布的節點之中盡快找到一條盡可能最優的收斂路徑,另一個是保證收斂路徑上的節點消耗盡可能少的能量且相對負載均衡,以延長節點使用時長和網絡的生命周期.

為了尋找最佳路徑,國內外展開廣泛深入的研究,很多切實有效的方法被提出.其中最具代表性的是將蟻群算法與無線傳感器網絡路由算法相結合.蟻群優化算法將問題求解的快速性、全局優化性以及高度的自組織性等特點合理結合,與無線傳感器網絡低能耗、自組織的大規模網絡路由快速建立要求極其相似,有助于建立面向數據為中心的匯聚路由[3].梁華為將蟻群算法與無線傳感器網絡路由算法相結合,提出了最基本的蟻群無線傳感器路由算法ARA (ACO-Based Routing Algorithm)[4],尋優能力十分有限.在此基礎上,焦斌改進的蟻群算法IARA (Improved Ant-based Routing Algorithm)[5],綜合考慮了節點剩余能量,傳輸方向和節點距離等因素,重點改進了蟻群算法的概率公式.此外,羅旭提出了改進的蟻群算法OARA (Optimization in Ant-based Routing Algorithm)[6],考慮到節點之間的距離和節點的剩余能量,在概率公式中引入罰函數和動態權重因子.然而上述的各種改進蟻群算法綜合起來存在蟻群算法收斂與否取決于搜索半徑的選擇、路徑存在往返跳躍導致額外能量消耗、選取節點能量過低無法支持信息傳輸等問題.

為了克服上述弊端,本文通過采取“三步遞進式”尋找下一跳候選節點的方法來優化傳統蟻群算法,并分別提出了DEARA (Dynamic Energy ARA)和DDEARA(Dynamic Direction Energy ARA)蟻群算法.首先,DEARA 算法通過分別引入動態半徑搜索因子保證蟻群算法能夠收斂和能量預測因子避免節點能量過度消耗出現負值的不合理現象.其次,DDEARA 算法在DEARA 算法基礎之上引入方向因子[7],避免反方向無關節點被選為下一跳候選節點,進一步提高算法尋優能力.DEARA 和DDEARA 蟻群算法優化措施是在逐步縮小下一跳候選節點的范圍,這一具體的確定性因素,而不是僅僅提高了某些節點被選為下一跳節點的概率值,這一隨機性因素,使得尋優結果符合預期設想.

1 系統模型

1.1 網絡模型

本文研究的無線傳感器網絡模型如圖1所示,由N個隨機分布的無線傳感器節點構成自組網多跳網絡模型[8].圖中,無線傳感器節點隨機的部署在一定區域內,位置相對固定且具備自定位功能.無線傳感器網絡可以通過區域內分布的無線傳感器節點,實時采集區域內的相關信息,并以“自組織”的方式構建一條通路,通過最外側的節點(網關),將信息經基站sink 節點匯總到因特網中,以便后期的分析處理.為了分析方便且不失一般性,考慮網絡中分布的所有節點一致,即符合相同的能量傳輸模型,且初始能量相同為E0(不妨設E0為單位1 J).定義剩余能量值小于Einit(Einit=0.1 J)的節點為死亡節點,該節點的剩余能量已無法成功傳輸一次完整數據,因此不能被選為下一跳候選節點.為了便于死亡節點的分析,下面重點分析節點能量傳輸模型.

圖1 無線傳感器網絡模型

1.2 能量傳輸模型

在無線通信過程中,網絡節點能耗主要包括電路損耗與功率放大損耗[9],文獻[10]給出了相應的能量損耗模型,當前節點W向距離為d的節點傳輸Bbit數據時,如果兩通信節點之間間距為d(d≤d0)就選取自由空間模型,通信節點數據傳播速率衰減和d2成正比.當位置間距為d(d>d0)就選取多路徑衰減模型,且數據傳輸所損耗能量和d4成正比.由此給出節點傳輸數據能耗如式(1)所示:

在節點通信過程中,每個節點接收并處理B bit數據時所需要消耗的能量如式(2)所示:

其中,Eelec表示傳感器網絡在傳輸或者接收數據時電路上的損耗.εamp代表數據在多路徑衰落模型傳輸過程中的損耗.

2 蟻群系統(ACS)算法模型

1992年Dorigom 在他的博士論文中首次引入了蟻群算法(Ant Colony Optimization,ACO)[11].蟻群算法是一種啟發式的仿生進化算法,屬于隨機搜索算法的一種[12].螞蟻從巢穴出發尋找食物的過程中,根據其他螞蟻在路徑上留下的“信息素”濃度,最高效率的尋找到離巢穴最近的食物.基本蟻群算法作為最原始的蟻群算法,在解決小規模旅行商問題時全局收斂速度快,但是在面對大規模旅行商問題時全局收斂速度較慢.針對這些問題,Dorigo 和Gambardella 在1997年共同提出了蟻群系統(Ant Colony System,ACS)[13].在基本螞蟻算法基礎之上提出了3 點改進.首先,下一跳狀態轉移規則得到優化.其次,只在最優路徑上作全局信息素更新.最后,全局信息素的更新的同時結合局部信息素更新規則.

2.1 下一跳狀態轉移規則的優化

在ACS 中,螞蟻 對下一跳節點的選擇都是根據一個偽隨機比例[14]來進行的,從當前節點i到下一節點j的選擇遵循式(3)～式(5).

其中,α表示信息啟發因子,表明軌跡的相對重要性.β表示期望啟發因子,表明能見度的相對重要性.τij表示信息素濃度,ηij為路徑啟發因子,q0(0

2.2 局部信息素的更新

為了加強螞蟻的搜索能力,結合極大極小蟻群算法[15],引入信息素的最小濃度 τmin,信息素的最大濃度τmax,這樣能夠避免因為某些路徑的信息素濃度過大或者過小,導致螞蟻過分集中而陷入局部最優,制約了蟻群算法的全局搜索能力.局部信息素更新公式如式(6)～式(8).

其中,τmin表示信息素最小濃度,τmax是信息素的上限值最大濃度,ρ為信息素的揮發系數,其值越大意味著路徑上的信息素揮發越快,取值范圍在(0,1).? τij表示本次循環中路徑 (i,j)上 的信息素增量,表示螞蟻k在(t,t+1)的時間段內留在路徑(i,j)上的信息素量.Q表示信息素強度,是常量固定值,Lk為螞蟻k在本次循環中經過的路徑長度.

2.3 全局信息素的更新

在ACS 算法中,當所有螞蟻完成一次迭代后,會對螞蟻搜尋到的最優路徑進行全局信息素更新.而其它非最優路徑的信息素則按一定的系數不斷減少.這樣可以使大多數的螞蟻下一次優先選擇最優路徑,提升了ACS 算法收斂速度.信息素全局更新公式如式(9)、式(10).

其中,Lelite表示一代所有螞蟻搜索完成后全局最優路徑的長度.

3 算法改進

傳統蟻群優化算法均集中在提高節點被選中的概率值(隨機事件發生的概率值),依然存在很大的盲目性與不確定性.本文改進算法通過逐步縮小下一跳候選節點的范圍,然后在有限的候選節點范圍內依照概率值進行選取下一跳節點,這樣擺脫了傳統蟻群算法的完全隨機性.

3.1 動態半徑搜索因子

利用動態半徑搜索因子尋找下一跳候選節點能夠提高蟻群算法的收斂性.動態半徑搜索因子使得螞蟻在當前半徑圓內找不到下一跳候選節點時,即可通過擴大搜索半徑直至能夠找到下一跳候選節點為止,從而保證蟻群算法最終能夠收斂.

螞蟻k首先在以當前節點W為圓心,半徑為r的圓內尋找符合條件的下一跳候選節點,如果半徑為r的圓內沒有符合條件的下一跳候選節點,則擴大搜索半徑r至 2r,在半徑為 2r的圓內繼續尋找符合條件的下一跳候選節點.圖2中顯示有符合條件的節點1 和節點2,因此將節點1 和節點2 選為下一跳候選節點.動態半徑搜索因子優勢在于能夠避免螞蟻直接在較大半徑范圍內尋找下一跳候選節點.雖然下一跳節點離當前節點距離越遠,本次螞蟻尋找路徑越容易收斂,但是由于距離較遠,根據能量消耗公式可知,距離越大消耗的能量越大.經過一次完整數據傳輸之后,節點可能消耗了所有的能量,間接導致本次尋優的路徑失效又要重新尋找最優路徑.所以要限制螞蟻搜索半徑范圍,優先在小范圍內尋找下一跳候選節點,這樣能夠使更多節點參與到收斂路徑中,通過多點參與均衡相鄰節點之間距離,降低單個節點能耗,提高單個節點傳輸數據的次數,進而達到延長無線傳感器網絡壽命的目標.

圖2 動態半徑搜索因子示意圖

3.2 能量消耗預測因子

節點能量消耗預測因子的引入,能夠規避當節點消耗完剩余能量卻沒有傳完所有數據的不利情況發生.螞蟻在尋找下一跳候選節點時,首先要判斷當前節點W和下一跳候選節點1 傳輸kbit數據時所要消耗的能量值E2是否大于當前節點W的剩余能量值E1.只有當(E2≤E1)時節點1 才會被成功選為下一跳候選節點.傳統蟻群算法一方面由于沒有能量消耗預測機制,很可能造成當前節點剩余能量值消耗完卻只傳輸了部分數據,這樣的一次傳輸工作是失敗的,不僅浪費了當前節點和之前所有節點傳輸數據消耗的能量,而且還造成當前路徑終點不可達.另一方面傳統蟻群算法默認節點只要有能量就能繼續工作且能夠傳完整數據,可能造成節點工作一次后剩余能量值為負的不合理現象.

3.3 方向因子

通過引入方向因子尋找下一跳候選節點,避免了反方向的無關節點被選中成為下一跳候選節點.傳統的蟻群算法搜索下一跳候選節點時,都是在以當前節點W為圓心,半徑為r的整個圓內尋找下一跳候選節點,可能尋找到與當前節點W和sink 節點N連線反方向范圍內的節點2 作為下一跳候選節點,這樣就增加了路徑長度,既浪費節點能量又弱化算法尋優能力.方向因子的引入,可以限制下一跳候選節點在當前節點W和sink 節點N連線正方向的正負 90?范圍內尋找.如圖3所示,當前節點W在r半徑圓內有符合條件的節點1 和節點2,因為節點2、當前節點W以及sink 節點N形成的夾角 β (β>90?),因此直接舍棄節點2.同理根據方向因子在節點3 和節點4 中選擇節點3 作為下一跳候選節點.這樣有利于螞蟻一直在往 sink 節點N的方向尋找下一跳候選節點,避免找到反方向的無關節點,減少路徑長度節約節點能量消耗,提高算法尋優能力.

圖3 方向因子示意圖

3.4 最優路徑評價公式

傳統蟻群算法依據路徑最短評價指標尋找最優路徑,僅僅考慮路徑的距離長短,評價指標非常單一,本文算法評價指標引入了節點平均剩余能量、節點最小剩余能量、最短路徑長度、條數、節點剩余能量方差.

其中,Eaver表示節點平均剩余能量,Emin表示路徑所經過節點中消耗能量的最小值,表示第m只螞蟻第k次迭代后走過的路徑長度,表示第m只螞蟻第k次迭代后走過的路徑上的節點個數,表示第m只螞蟻第k次迭代后走過的路徑上所有的節點剩余能量值的標準差.

的數值越大代表的路徑越好,每迭代完一次將最大值對應的路徑作為本次迭代最優路徑,然后更新此路徑上的信息素,便于后繼的螞蟻尋找路徑時優先考慮這條路徑,所有的迭代完成后即可選出符合上述條件的最優路徑.評價指標中引入節點剩余能量標準差,有利于最優路徑上各節點剩余能量值大小接近.如果各節點剩余能量值懸殊太大,這樣的路徑可能發送一次完整數據就出現了死亡節點,此條路徑就不能繼續使用,必須重新尋找一條最優路徑.

4 仿真實驗及結果分析

為了驗證上述的優化蟻群算法DDEARA 的有效性,采用蒙特卡洛方法進行計算機模擬仿真實驗.在一個(10×10)的范圍內,隨機布置S(S=100)個傳感器節點.為了便于描述且不失一般性,不妨設點(0,0)為起始發送節點,點(10,10)為終端sink 節點,整個仿真實驗中共有t(t=100)代螞蟻且每一代螞蟻有n(n=100)只.每次傳輸2 000 bit數據.仿真結果如圖4.

4.1 最優路徑連線圖

圖4對比了ARA、IARA、OARA、DEARA、DDEARA 5 種算法最終收斂的最優路徑連線圖,直觀顯示了各種算法路徑經過的節點個數以及節點分布情況.

從表1中可以看出ARA、OARA、IARA 算法各方面性能效果都差,由于ARA、OARA 算法路徑中參與的中間節點個數非常少,導致收斂路徑消耗的能量也非常小,但是相鄰節點之間的距離很大.IARA 算法中參與的中間節點過多,尤其是存在很多反向節點,導致最終收斂路徑長度較長以及路徑耗能非常大.DEARA算法相比上述3 種算法收斂效果明顯改善,最優路徑長度適中,最關鍵的是相鄰節點距離適中,但路徑中仍然有較多中間節點尤其是反向的無關節點,導致路徑消耗的能量僅次于IARA 算法.DDEARA 算法相比上述4 種算法性能效果最好,最優路線長度短,相鄰節點之間距離適中,參與的中間節點個數合理,路徑消耗的能量也很合理.由此可見動態半徑搜索因子能夠提高算法收斂能力,能量預測因子能夠減少節點能量消耗,方向因子能夠避免反向無關節點選取.

圖4 5 種對比算法最優路徑連線圖

表1 不同算法性能對比

4.2 節點消耗總能量、剩余總能量

圖5對比了ARA、IARA、OARA、DEARA、DDEARA 5 種算法各個節點最終平均能量消耗和剩余能量情況,直觀顯示了各個節點能耗分布情況.

從圖5中可以看到,ARA、OARA、IARA 算法出現節點消耗能量值E2(E2>1J)、剩余能力值E1(E1<0J)的不合理現象,而DEARA、DDEARA 算法中節點消耗能量值E2(E2≤1J)、節點剩余能量值E1(E1≥0.1J),能量預測因子避免了節點能量過度消耗,不會出現節點剩余能量值為負的不合理現象.

圖5 5 種算法節點能耗

4.3 DEARA、DDEARA 算法節點能耗

圖6對比了DEARA、DDEARA 2 種算法各個節點平均能量消耗和剩余能量情況,直觀顯示了各個節點能耗分布情況.

圖6 DEARA、DDEARA 算法節點能耗

圖6顯示了在DEARA 算法中節點消耗能量值E2普遍在(0.8?1J)范 圍內,剩余能量值E1普遍在(0?0.2J)范圍內.在DDEARA 算法中接近2/3 的節點產生了能量消耗且能量消耗值均勻分布在(0?1J)范圍內.表明DDEARA 算法中參與的節點數目適中,節點位置分布均勻.

4.4 DEARA、DDEARA 算法每一代節點死亡個數

圖7對比了DEARA、DDEARA 2 種算法每一輪迭代過程中出現的死亡節點個數,直觀顯示了首次出現死亡節點的迭代次數,以及每一代死亡節點個數分布情況.

圖7 DEARA、DDEARA 算法每一代死亡節點個數

由圖7可知 DEARA 和DDEARA 算法都是在45 代首次出現了死亡節點.DEARA 算法單次迭代死亡節點個數最多為8 個,而DDEARA 單次迭代死亡節點個數最多為2 個.DDEARA 算法死亡節點個數以及死亡節點出現的代數明顯優于DEARA 算法.

4.5 DEARA、DDEARA 算法收斂路徑長度

圖8對比了DEARA、DDEARA 算法最終收斂路徑的長度,直觀顯示了兩種算法在整個迭代過程中最優路徑的長度趨勢.

圖8 DEARA、DDEARA 算法收斂路徑長度

圖8顯示DEARA 算法最終收斂路徑長度在18.37,DDEARA 最終收斂路徑長度在15.77,DDEARA 算法由于方向因子的引入,避免選取反向無關節點,使得尋優效果非常好,收斂路徑更短.

5 結論與展望

針對現有的蟻群算法無法保證路徑最終收斂,節點能量過度消耗,路徑上存在無關節點等情況.本文首先通過引入動態半徑搜索因子和能量預測因子,提出了改進的蟻群算法DEARA,一方面動態半徑搜索因子能夠保證蟻群算法最終收斂并提高了蟻群算法的收斂效果.另一方面能量預測因子使得節點能耗均勻且不會出現消耗完節點剩余能量卻不能成功傳輸完整數據的情況.但是在DEARA 算法收斂路徑中仍然存在部分反方向的無關節點,因此在DEARA 算法基礎上通過引入方向因子提出了DDEARA 算法,方向因子避免了路徑中反方向無關節點的選取,優化效果非常明顯.經過“三步遞進式”的蟻群算法優化,首先,使得最終的最優路徑長度較短,經過的中間節點數目適中且位置分布均勻.其次,使得節點能耗較少,不會出現某區域節點集中死亡的現象.最后,使得路徑上沒有反方向的無關節點存在,減小路徑長度,節約節點能耗.“三步遞進式”蟻群算法DDEARA 尋優能力更強且尋優效果更好,提高了無線傳感器網絡的使用性能和壽命.

未來一方面可以著重研究“過載”節點能耗問題,本文沒有考慮某個節點被多條路徑同時選中為下一跳節點的情況,這樣的“過載”節點由于承擔多條線路的數據傳輸任務,導致這樣的“過載”節點耗能嚴重,相比其他節點過早成為死亡節點,嚴重影響網絡使用壽命.未來應該考慮節點的“負重”系數,嚴格限制節點同時被多條路徑經過.另一方面可以考慮路徑中一旦出現死亡節點之后,怎么樣快速尋找其他節點代替死亡節點,恢復正常工作.