尚興宏，錢煥延，高德民

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京 210094）

0 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）是一種無中心節(jié)點(diǎn)的分布式系統(tǒng)，目前已廣泛應(yīng)用在國防軍事、國家安全、環(huán)境監(jiān)測和醫(yī)療衛(wèi)生等領(lǐng)域。它是繼因特網(wǎng)之后，將對21世紀(jì)人類生活產(chǎn)生重大影響的 IT技術(shù)之一［1，2］。

蟻群優(yōu)化（ACO）算法是一種受自然界蟻群生物行為啟發(fā)而產(chǎn)生的分布式智能模擬算法。1992年，Dorigo M［3］在他的博士論文首先提出了一種全新的蟻群系統(tǒng)啟發(fā)式算法，在此基礎(chǔ)上一種很好的優(yōu)化算法逐步發(fā)展起來。蟻群系統(tǒng)最大的特點(diǎn)就是螞蟻個(gè)體以信息素為媒介進(jìn)行相互的聯(lián)系，螞蟻在需找食物路徑的行動(dòng)中會(huì)在經(jīng)過的地方留下一種稱之為“信息素”（pheromone）的化學(xué)物質(zhì)，后續(xù)的螞蟻在感受到該物質(zhì)后，表現(xiàn)出選擇該路徑的可能性比選擇沒有該物質(zhì)的可能性大得多，并對信息素進(jìn)行增強(qiáng)。經(jīng)過這種不斷的循環(huán)，經(jīng)過螞蟻越多的路徑，所留下信息素就越多，因而，后續(xù)螞蟻選擇該路徑的也就越多。這個(gè)過程將至整個(gè)蟻群選擇出一條最優(yōu)的路徑為止［4］。

傳統(tǒng)的無線網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)主要以避免網(wǎng)絡(luò)擁塞，提高高質(zhì)量的QoS服務(wù)為主要目標(biāo)，而無線傳感器網(wǎng)絡(luò)由于受節(jié)點(diǎn)能量限制，路由協(xié)議的設(shè)計(jì)需要從節(jié)能出發(fā)，最大程度地延長整個(gè)網(wǎng)絡(luò)的生命周期。

1 相關(guān)理論

目前，很多研究者將蟻群算法用于無線傳感器網(wǎng)絡(luò)的路由設(shè)計(jì)。李領(lǐng)治等人［5］根據(jù)螞蟻尋徑與選播路由的相似性，提出了在網(wǎng)絡(luò)負(fù)載較大的情況下實(shí)現(xiàn)多目標(biāo)多路徑的選播路由算法，在減少時(shí)延，實(shí)現(xiàn)復(fù)雜均衡方面較有優(yōu)勢;朱思峰等人［6］通過構(gòu)造人工螞蟻，設(shè)計(jì)了基于ACO的路由算法框架，實(shí)驗(yàn)表明能加快算法收斂性;王睿等人［7］研究了一種分布式、自適應(yīng)的無線傳感器網(wǎng)絡(luò)蟻群自組織算法，通過蟻群間的協(xié)同對節(jié)點(diǎn)的喚醒概率進(jìn)行群體智能優(yōu)化，從而實(shí)現(xiàn)在喚醒較少節(jié)點(diǎn)的前提下，對目標(biāo)保持了較好的探測能力;李聞等人［8］研究了傳感網(wǎng)絡(luò)中基于螞蟻算法的分布式數(shù)據(jù)匯集路由算法，由于該算法不需要網(wǎng)絡(luò)節(jié)點(diǎn)維護(hù)全局信息，且數(shù)據(jù)匯集降低了網(wǎng)絡(luò)路由開銷，因此，該算法是一種節(jié)約能量的分布式路由算法，理論分析和仿真結(jié)果說明了新算法的有效性和可伸縮性;肖偉等人［9］在研究蟻群算法應(yīng)用于QoS路由問題的可能性的基礎(chǔ)上，給出了調(diào)和蟻群算法解決多路徑多約束QoS問題的算法，最后通過仿真實(shí)例得到滿意的結(jié)果。以上的算法在解決其關(guān)注領(lǐng)域方面都有一定創(chuàng)新性，但較少考慮節(jié)點(diǎn)的能耗平衡和路徑最優(yōu)等問題，鑒于此，本文結(jié)合無線傳感器網(wǎng)絡(luò)的特點(diǎn)，將蟻群算法應(yīng)用于無線傳感器網(wǎng)絡(luò)，提出基于能量均衡的無線傳感器網(wǎng)絡(luò)路由算法。該算法將能量因素考慮進(jìn)路徑的概率選擇和信息度的增強(qiáng)計(jì)算當(dāng)中，以期找到條代價(jià)較小，能量較均衡的從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑，從而延長整個(gè)網(wǎng)絡(luò)的生命周期。

2 網(wǎng)絡(luò)模型與算法優(yōu)化

2．1 無線傳感網(wǎng)絡(luò)路由模型

將無線傳感器網(wǎng)絡(luò)抽象成一個(gè)帶權(quán)的無向圖G=〈V，A〉。其中，V為路網(wǎng)的節(jié)點(diǎn)集合V=（V0，V1，…，VN－1，VN），V0為源節(jié)點(diǎn)，VN為目標(biāo)節(jié)點(diǎn);每一節(jié)點(diǎn)具有能量，網(wǎng)絡(luò)位置和通信半徑;A表示邊的集合，每條邊都有自己的權(quán)值，主要為信息素和能量值。改進(jìn)后的蟻群算法被用來尋找圖G中節(jié)點(diǎn)V0到目的節(jié)點(diǎn)VN的能耗代價(jià)最小的最優(yōu)路徑，同時(shí)將能耗均衡性考慮到其中。

2．2 算法改進(jìn)

針對無線傳感器網(wǎng)絡(luò)路由的特性，在尋找最優(yōu)路徑過程中的ACO算法主要步驟如下:

1）初始化相關(guān)參數(shù)

假設(shè)無線傳感器網(wǎng)絡(luò)的源節(jié)點(diǎn)上有m只螞蟻工作，每條路徑賦予相等的信息素痕跡初值與能量初值。

2）狀態(tài)轉(zhuǎn)移規(guī)則

每只螞蟻都努力尋找網(wǎng)絡(luò)中的最小代價(jià)的路徑，螞蟻k在從節(jié)點(diǎn)i根據(jù)下面的概率選擇規(guī)則（等式（1））來選擇其要移動(dòng)到的下一跳節(jié)點(diǎn)j

其中 ，τij（t）為節(jié)點(diǎn)i到節(jié)點(diǎn)j之間鏈路上的信息素，ηij（t）為節(jié)點(diǎn)i到節(jié)點(diǎn)j之間鏈路與能量相關(guān)的啟發(fā)值，α和β分別為控制信息素痕跡和啟發(fā)值相對重要性的參數(shù)，且有α≥0，β≥0。Nk（i）表示螞蟻k下一步可以選擇的節(jié)點(diǎn)集合。節(jié)點(diǎn)j的啟發(fā)值如下列等式（2）所示

其中，E0為節(jié)點(diǎn)初始能量，ei為節(jié)點(diǎn)i的當(dāng)前能量。這將使得螞蟻按照鄰居節(jié)點(diǎn)的能量水平來做下一跳選擇，這也意味著較高能量水平的節(jié)點(diǎn)被選中的概率越高，因此，可以更好地實(shí)現(xiàn)全網(wǎng)能量均衡。

各節(jié)點(diǎn)都實(shí)時(shí)檢測自己的當(dāng)前能量值，當(dāng)能量下降超過設(shè)定的幅度時(shí)，需將其值迅速通知相鄰節(jié)點(diǎn)。

3）路徑適應(yīng)度值

路徑的適應(yīng)度值按照式（3）來計(jì)算

4）信息素更新

在完成一次迭代后，對螞蟻所走過的路徑進(jìn)行信息素更新，按式（4）進(jìn)行

其中，ρ（ρ∈（0，1））表示信息素?fù)]發(fā)系數(shù)，Q表示信息度強(qiáng)度系數(shù)。

5）轉(zhuǎn)到步驟（2）反復(fù)執(zhí)行，直到執(zhí)行完規(guī)定的迭代次數(shù)N，求得最優(yōu)路徑。

3 仿真

在Matlab 7．0仿真環(huán)境中，隨機(jī)產(chǎn)生120個(gè)無線傳感器節(jié)點(diǎn)，無線傳感器節(jié)點(diǎn)隨機(jī)分布在150 m×100 m的平面區(qū)域，模擬場景如圖1所示，所有節(jié)點(diǎn)的傳輸功率是可調(diào)節(jié)的，傳感器節(jié)點(diǎn)根據(jù)實(shí)際需要調(diào)節(jié)傳輸功率與其他節(jié)點(diǎn)進(jìn)行通信。數(shù)據(jù)包大小為512 byte，元數(shù)據(jù)大小為25 byte，傳輸1 bit消息時(shí)能量消耗為E1bit=1 nJ/bit，傳感器節(jié)點(diǎn)的初始能量Estart=10 J，蟻群算法中參數(shù)的設(shè)定均為:信息素?fù)]發(fā)系數(shù) ρ=0．9，信息素強(qiáng)度系數(shù)Q=10，α =0．9，β =2，Q=10，ρ=0．95。

3．1 算法可行性

在模擬場景中尋找從源節(jié)點(diǎn)A到目標(biāo)節(jié)點(diǎn)B的考慮能量消耗的路由，其中節(jié)點(diǎn)C和節(jié)點(diǎn)D能量均較低。算法顯示，節(jié)點(diǎn)A到節(jié)點(diǎn)B的最優(yōu)路徑成功避開了節(jié)點(diǎn)C和節(jié)點(diǎn)D，如圖2所示。

3．2 能耗優(yōu)越性

圖1 模擬場景Fig 1 Simulation scene

圖2 基于改進(jìn)ACO算法的最優(yōu)路徑Fig 2 The optimal path based on improved ACO algorithm

網(wǎng)絡(luò)的總能量消耗越小，表明該網(wǎng)絡(luò)路由代價(jià)較小，因此，網(wǎng)絡(luò)的生命周期也就越長。以傳感器總能量消耗作為衡量指標(biāo)，將本模型與泛洪模型及基本ACO作了比較，結(jié)果如圖3所示。

圖3 能量消耗比較Fig 3 Comparison of energy consumption

從圖3可以看出:本模型的能量消耗要小于泛洪模型和ACO算法的能量消耗，因?yàn)樵陂_始階段，都要進(jìn)行消息的擴(kuò)散傳播，但是，由于泛洪模型中所有的節(jié)點(diǎn)參與興趣和探測數(shù)據(jù)的泛洪，隨著時(shí)間的延長，能量消耗呈現(xiàn)劇烈陡峭增長，ACO利用網(wǎng)絡(luò)延時(shí)信息更新路徑，以及為了優(yōu)化路徑需要較多的螞蟻協(xié)同工作，這樣將消耗過多的傳感器節(jié)點(diǎn)能量，而改進(jìn)ACO模型由于在螞蟻動(dòng)態(tài)尋優(yōu)的同時(shí)考慮了能量均衡特性，避免了周期性的螞蟻擴(kuò)散，節(jié)省了網(wǎng)絡(luò)的能量消耗，也就達(dá)到延長該路徑生命周期的目的。

4 結(jié)束語

本文將蟻群優(yōu)化算法應(yīng)用于無線傳感器網(wǎng)絡(luò)的的路由選擇，并對其進(jìn)行了優(yōu)化。在Matlab 7．0環(huán)境中建立了網(wǎng)絡(luò)模型，并和泛洪模型及基本ACO算法進(jìn)行了路由仿真實(shí)驗(yàn)和對比。仿真實(shí)驗(yàn)結(jié)果表明:本算法較好地平衡了路徑長度和節(jié)點(diǎn)能量消耗兩者關(guān)系，有效地控制了整體網(wǎng)絡(luò)的總能量消耗，從而延長了網(wǎng)絡(luò)的生命周期。

［1］ Akkaya K，Younis M．A survey on routing protocols for wireless sensor networks［J］．Ad Hoc Networks，2005（3）:325 －349．

［2］ 王 殊，閻毓杰，胡富平，等．無線傳感器網(wǎng)絡(luò)的理論及應(yīng)用［M］．北京:北京航天航空大學(xué)出版社，2007:2－6．

［3］ Dorigo M．Optimization，learning and natural algorithms［D］．Milano:Politecnico di Milano，1992:1 －90．

［4］ 邢文訓(xùn)，謝金星．現(xiàn)代優(yōu)化計(jì)算方法［M］．北京:清華大學(xué)出版社，2005:149 －155．

［5］ 李領(lǐng)治，鄭洪源，丁秋林．一種基于改進(jìn)蟻群算法的選播路由算法［J］．電子與信息學(xué)報(bào)，2007，29（2）:340 －344．

［6］ 朱思峰，劉 方，柴爭義．一種基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)路由算法［J］．北京理工大學(xué)學(xué)報(bào)，2010，30（11）:1295－1300．

［7］ 王 睿，梁 彥，潘 泉．無線傳感器網(wǎng)絡(luò)的蟻群自組織算法［J］．電子學(xué)報(bào)，2007，35（9）:1691 －1695．

［8］ 李 聞，林亞平，童調(diào)生，等．傳感網(wǎng)絡(luò)中一種基于螞蟻算法的分布式數(shù)據(jù)匯集路由算法［J］．小型微型計(jì)算機(jī)系統(tǒng)，2005，26（5）:788 －792．

［9］ 肖 偉，全惠云，劉 楓．基于蟻群算法的多路徑多約束QoS路由研究［J］．計(jì)算機(jī)工程與應(yīng)用，2008，44（30）:111 －113．