基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)的路由優(yōu)化

沙娓娓，劉增力

（1. 昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650500；2. 昆明理工大學(xué) 民航學(xué)院，云南 昆明 650500）

0 引言

無線傳感器網(wǎng)絡(luò)：指利用無線通信的方法，將微型傳感器節(jié)點（被感知對象的內(nèi)部、附件之中）組成多跳自組織網(wǎng)絡(luò)，在環(huán)境監(jiān)測、國家安全以及軍事偵察等相關(guān)領(lǐng)域得以普遍應(yīng)用[1]。傳感器節(jié)點由電池提供能量，同時具有數(shù)量多、體積小等特點，一旦完成部署，即難以繼續(xù)補充能量。所以在設(shè)計無線傳感器網(wǎng)絡(luò)路由協(xié)議時，要充分考慮節(jié)點能量問題，以延長網(wǎng)絡(luò)生存周期達到傳輸大量數(shù)據(jù)的要求[2]。

Dorigo針對TSP的問題，提出全新的模擬進化算法——蟻群優(yōu)化算法[3]。與此同時隨著該算法的應(yīng)用，有效解決指派、調(diào)度以及旅行商等各類優(yōu)化組合問題[4]。

Kassabalidis等潛心多年研究，結(jié)合蟻群算法，提出Ant-Net算法[5]，該算法中螞蟻主要可分為兩大類：其一是具有收集節(jié)點信息作用的前向螞蟻；其二為返回螞蟻，將前向螞蟻收集的信息，反饋在路由表之中。

Schoonderwoerd R等人通過概率選擇和更新路徑的方式，提出ABC算法[6]，此算法中螞蟻從源節(jié)點到達目的節(jié)點后就死亡，同時更新路由表。文獻[7]基于 DD算法[8]提出一種全新的算法——ARAWSN，有助于改善能耗問題，可找到源節(jié)點到目的節(jié)點間最短的路徑。

本文提出IARA這一全新優(yōu)化的算法，在源節(jié)點選擇下一跳節(jié)點，兼顧了節(jié)點的能量、傳輸方向、節(jié)點間距離等因素，通過改進的信息素更新公式、啟發(fā)函數(shù)、選擇概率這三個方面，不僅降低了節(jié)點能耗，同時有助于延長網(wǎng)絡(luò)生存周期。

1 無線傳感器網(wǎng)絡(luò)通信的能耗模型

在能耗模型方面，本文考慮選擇同文獻[9]的模型，將k bit的數(shù)據(jù)發(fā)送到d節(jié)點時，可用如下公式表示這一過程消耗的能量。

此時接收節(jié)點消耗能量：

融合數(shù)據(jù)消耗能量：

式（1）～（3）中：elecE、ampE、fuseE分別指發(fā)送和接收、傳輸放大以及融合數(shù)據(jù)等單元功耗，如果傳輸距離較大，則通常建議選擇運用多路徑衰減模型，相反的如果較小，則一般運用自由能量模型。

2 改進的WSN蟻群路由算法描述

在具體設(shè)計 WSN路由時，應(yīng)充分考慮到無線傳感器網(wǎng)絡(luò)節(jié)點的特殊性，即其能量有限。針對這一問題，本文緊扣“有效性”這一原則，充分考慮下一跳節(jié)點的能量參數(shù)以及實際傳輸距離、方向等問題，使蟻群在自動尋優(yōu)的同時，也具有能量感知意識。

2.1 路徑概率選擇

從路徑探索的角度出發(fā)，非常有必要結(jié)合某種概率訪問周圍節(jié)點：而從路徑尋優(yōu)這一層面分析，為避免局部最優(yōu)解，在訪問時節(jié)點時，如果僅以概率為基礎(chǔ)，其獲得的最優(yōu)解并非都有意義[10]。因此，引入傳輸方向參數(shù)，改進后的轉(zhuǎn)移概率公式如下：

式（4）中，表示第k只螞蟻從節(jié)點i向節(jié)點j轉(zhuǎn)移的概率；用于表示k可通信節(jié)點集合，如果其通信節(jié)點并非可允許的節(jié)點，那么此時概率應(yīng)等于0；這里τij、ηij分別表示信息素濃度、啟發(fā)函數(shù)，兩者的權(quán)重值分別為α、β。假設(shè)α值較大，則對應(yīng)的信息素濃度發(fā)揮的作用相對較大，換言之即螞蟻會以已經(jīng)走過的路徑為主，彼此間具有較強的協(xié)同能力；相反的如果β值較大，則對應(yīng)說明啟發(fā)函數(shù)可發(fā)揮更大的作用，此時以未探索過的節(jié)點為主，換言之即螞蟻具有較強的探索能力，可探索新節(jié)點。θ為下一跳節(jié)點 next,源節(jié)點 source和目的節(jié)點destination的夾角；γ為定義的常量，指明了傳輸方向?qū)?jié)點路由選擇的影響程度。

如圖1所示，即為θ的示意圖，通過該圖可充分說明，假設(shè)θ越小，那么對應(yīng)的d1+d3越小，傳輸方向越接近于節(jié)點next到destination節(jié)點的連線方向，且

圖1 傳輸方向Fig.1 Direction of communication

2.2 本地啟發(fā)函數(shù)

螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點j的期望程度用啟發(fā)函數(shù)ijη表示。由于最初是針對TSP的問題而提出該算法，所以啟發(fā)函數(shù)并未充分考慮其它因素，僅以兩節(jié)點的距離為考量重點。而無線傳感器網(wǎng)絡(luò)，除應(yīng)充分重視距離因素之外，還需綜合考慮諸如節(jié)點、鄰居節(jié)點剩余能量等多方面的問題?；诖耍缡剑?）所示，即為本文的啟發(fā)函數(shù)定義：

式（6）中，Ecurrent(j)為節(jié)點 i的鄰居節(jié)點 j當前剩余能量；Ni(k)表示集合節(jié)點i的鄰居節(jié)點集合；(k)為節(jié)點i所有鄰居節(jié)點的剩余能量。節(jié)點剩余能量與該節(jié)點是否會被選擇有直接的關(guān)系，節(jié)點的能量水平越低，被選擇的概率也會越低；dij表示的是節(jié)點i和節(jié)點j之間的距離。

2.3 信息素更新

螞蟻選擇下一跳節(jié)點時，會在經(jīng)過路徑上釋放出信息素，從而形成并增加可用于引導(dǎo)后來螞蟻的信息素濃度。由改進后的公式可知，節(jié)點剩余能量越多的路徑上累積的信息素濃度也會越高，這樣有助于避免由于路徑（最短）的信息素濃度過大，而出現(xiàn)螞蟻過分集中的問題，有助于避免節(jié)點能量消耗過快。給出信息素更新公式如下：

其中：Lk為螞蟻k從源節(jié)點到目的節(jié)點所經(jīng)過的路徑長度；λ為一個全局設(shè)定的常量； Ek_min、Ek_avg分別可用于表示螞蟻k經(jīng)過路徑節(jié)點的最小能量、平均能量。如式（8）所示，綜合考慮了路徑中最小能量、平均能量以及路徑總長度這三個因素。假設(shè)在更新路徑信息素時，未充分考慮這一情況 ，僅以節(jié)點能量為依據(jù)，那么運用此算法，則路徑不一定最短。

2.4 IARA算法的實現(xiàn)

具體實現(xiàn)步驟如下：

（1）初始化。清空螞蟻路徑，初始化訪問標志，顯示為未訪問；在源節(jié)點中放m只螞蟻，同時設(shè)置為已訪問，此為路線的第一個節(jié)點，另外各節(jié)點的初始值均為常數(shù)，且包含同樣的信息素；信息素增量在初始時為0；

（2）Antnum等于0，即到達目的節(jié)點的螞蟻數(shù)為0；

（3）螞蟻數(shù)k等于0；

（4）通過計算求出節(jié)點間距離；

（5）運用（4）式計算轉(zhuǎn)移概率，并確定節(jié)點j，把螞蟻k轉(zhuǎn)移至此j，同時設(shè)置該節(jié)點為已訪問，除了要修改螞蟻節(jié)點的能量外，還應(yīng)對應(yīng)修改前一節(jié)點能量；

（6）如果有節(jié)點能量耗盡，則直接跳至（9），如果沒有則依據(jù)（7）進行；

（7）k等于k+1，對比該值與m大小，較小轉(zhuǎn)（5），否則轉(zhuǎn)（8）；

（8）判斷Antnum是否等于m，若兩者相等，即此時螞蟻都到目的節(jié)點，則轉(zhuǎn)（9），如果沒有則轉(zhuǎn)（3）；

（9）計算螞蟻經(jīng)過的整個路徑的長度，比較得出最優(yōu)路徑；

（10）如果通過計算，并未有節(jié)點耗盡能量，則根據(jù)式（7）、（8）進行信息素的全局更新后轉(zhuǎn)（2）執(zhí)行；否則轉(zhuǎn)（11）；

（11）如上述循環(huán)結(jié)束，最終輸出結(jié)果。

3 仿真及結(jié)果分析

通過Matlab訪真、驗證IARA算法，在此基礎(chǔ)上對比分析了 ACO算法（文獻[3]），仿真范圍為100 m×100 m，并在這一范圍內(nèi)播撒（隨機）50個節(jié)點，將設(shè)定目標節(jié)點（50,50）。

考慮到測試的方便性，本文中設(shè)螞蟻總數(shù)為50只，即等于節(jié)點個數(shù)；無線傳感器節(jié)點每次傳輸相同大小的數(shù)據(jù)包，參數(shù)初值為：α=1，β=2，γ=1，λ =1，rmax=50，每個節(jié)點初始能量為0.5J。

正如上文所述，引入本算法的目的，即在延長網(wǎng)絡(luò)使用時長的同時，最小化能量消耗。所以本文基于螞蟻群算法，提出IACA法，該法改進了相關(guān)參數(shù)，通過傳輸距離、節(jié)點能量、傳輸方向這三者的綜合考慮，從而找到理想的延長網(wǎng)絡(luò)生存時間的方法。因此，為了驗證算法的性能，對比ACO算法，具體體現(xiàn)在如下兩個方面：其一網(wǎng)絡(luò)節(jié)點能耗總量；其二死亡節(jié)點數(shù)。

3.1 節(jié)點能耗

本文中的網(wǎng)絡(luò)生存時間，由所有節(jié)點消耗的能量之和反映，假設(shè)能耗越大，那么其生存時間就會越短；也就是說，一定時間內(nèi)消耗大量的能量，則其對應(yīng)的網(wǎng)絡(luò)生存時間較短；相反的，如果能量消耗較小，則說明具有較長的生存時間，全網(wǎng)節(jié)點共計50個，每個節(jié)點的初始能量為0.5J，因此全網(wǎng)總能量為25J，圖2 IARA和ACO能量消耗對比圖。從圖2中可以看出，IARA和ACO分別在930、710輪時全網(wǎng)能量消耗殆盡。

3.2 死亡節(jié)點數(shù)

能耗與死亡節(jié)點有一定關(guān)系，但是兩者又存在一定差異性。通過能耗量可充分說明在接收或者發(fā)送數(shù)據(jù)的消耗量，但是節(jié)點平均能耗與死亡節(jié)點數(shù)沒有必然的聯(lián)系，即死亡節(jié)點數(shù)不會單純因為節(jié)點平均能耗多而增多。假設(shè)僅少數(shù)節(jié)點消耗了能量，其它節(jié)點并未消耗或者基本沒有消耗能量，這種情況下死亡節(jié)點數(shù)較少，但是不可忽視的是極有可能死亡節(jié)點均處于關(guān)鍵路徑上，即使得整個網(wǎng)絡(luò)癱瘓，對應(yīng)的其網(wǎng)絡(luò)生存的時間必然也會很短；假設(shè)由多個節(jié)點共同消耗節(jié)點能量，即屬于平均消耗，那么就算最后有很多死亡節(jié)點，也不易出現(xiàn)關(guān)鍵節(jié)點完全失效的問題，即相應(yīng)的出現(xiàn)網(wǎng)絡(luò)癱瘓的機率也會較小，這樣一來，即有延長網(wǎng)絡(luò)生存時間的作用。從圖3中可以看出，IARA和ACO分別在930、710輪時全部節(jié)點死亡，因此IARA算法的生命周期比ACO要長，達到了預(yù)期的效果，證明了算法的有效性。

圖2 能量消耗Fig.2 Energy consumption

圖3 死亡節(jié)點數(shù)Fig.3 Nodes death

4 總結(jié)

本文基于無線傳感器網(wǎng)絡(luò)的特殊性，即節(jié)點能量少，引入具有健壯性、自組織性、自治性等優(yōu)點的蟻群算法，提出改進的蟻群路由算法 IARA，在基本蟻群算法的基礎(chǔ)上綜合考慮了節(jié)點的能量、距離、傳輸方向等參數(shù)。仿真結(jié)果表明：通過該算法解決了無線傳感器網(wǎng)絡(luò)瓶頸問題，即能耗大、網(wǎng)絡(luò)生存時間短，形成了節(jié)能、快速的路由來滿足網(wǎng)絡(luò)使用需要。

[1] 段海濱. 蟻群算法及其應(yīng)用[M]. 北京: 科學(xué)出版社2007:1389.DUAN H B, Ant colony algorithm and its application[M].Beijing: Science Press 2007: 1389.

[2] 陳宇, 等. 基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)路由的研究[D]. 廣州: 華南理工大學(xué), 2012.CHEN Y, et al. Research on routing of wireless sensor networks based on improved ant colony algorithm[D]. Guangzhou:South China University of Technology, 2012.

[3] Dorigo M, Gambardella L M. Ant colony system a cooperative learning approach to the travelling salesman problem[J].IEEE Transactions on Evolutionary Computation. 1997, 1(1): 53-66.

[4] Sim K M, Sun W H. Multiple ant-colony optimization for network routing[C]//Proceedings of the 1st International Symposium on Cyber Worlds, Washington DC, USA, 2001:277-281.

[5] Kassabalidis I, El-Sharkaw M A, Marks R J. Swarm intelligence for routing in communication networks[J]. Global telecommunications 2001, 6(6): 3613-3617.

[6] Schoonderwoerd R, Holland O, Bruten J, et al. Ants for load balancing in telecommunication networks[R]. Bristol: Hewlett Packard Lab, 1996. M. Goldfarb. Analog baseband IC for use in direct conversion W-CDMA receivers. IEEE.

[7] 梁華為, 陳萬明, 李帥, 等．一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法[J]. 傳感器技術(shù)學(xué)報, 2007, 20(11): 2450-2455.LIANG W H, CHEN W M, LI S et al. Ant colony optimization routing algorithm for Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(11): 2450-2455.

[8] Intanagonmimwt C, Govindan R, Estrin D. Directed diffusion for wireless sensor networking[J]. IEEE/ACM Trans on Networking, 2003, 11(1): 2-16.

[9] Heinzelman W R. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communication, 2002, 1(4): 660-670.

[10] 滑楠, 史浩山, 高程, 等． 一種適用于無線傳感器網(wǎng)絡(luò)路由的改進蟻群算法[J]. 傳感技術(shù)學(xué)報, 2007, 20(7):1063-1069.HUA N, SHIH S, GAO C, et al. An improved ant colony algorithm for routing in Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(7): 1063-1069.