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

戴天虹，李　昊

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，哈爾濱　150040)

?

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

戴天虹，李昊

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，哈爾濱150040)

摘要：為了延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network,WSN)的生命周期，均衡各個(gè)節(jié)點(diǎn)間能量消耗，針對(duì)現(xiàn)有的WSN路由優(yōu)化算法存在的問(wèn)題，提出了一種基于改進(jìn)蟻群算法的路由優(yōu)化算法;首先通過(guò)對(duì)蟻群算法和遺傳算法的優(yōu)劣性比較，在蟻群算法的基礎(chǔ)上，結(jié)合遺傳算法的選擇、交叉和變異的操作，從而提高蟻群算法的搜索速度和尋優(yōu)能力;最優(yōu)路徑評(píng)價(jià)函數(shù)綜合考慮節(jié)點(diǎn)能耗及節(jié)點(diǎn)的剩余能量，使剩余能量多的節(jié)點(diǎn)優(yōu)先參與數(shù)據(jù)轉(zhuǎn)發(fā)，均衡節(jié)點(diǎn)間的能量消耗;通過(guò)與經(jīng)典蟻群算法及遺傳算法的對(duì)比實(shí)驗(yàn)表明，隨著數(shù)據(jù)轉(zhuǎn)發(fā)輪數(shù)增加，改進(jìn)的蟻群算法能耗小，剩余能量多，網(wǎng)絡(luò)生命周期明顯延長(zhǎng)；隨著整個(gè)網(wǎng)絡(luò)運(yùn)行時(shí)間的增長(zhǎng)，改進(jìn)的蟻群算法，節(jié)點(diǎn)均衡能耗性好，最優(yōu)路徑搜索的成功率也明顯優(yōu)于其他兩種算法。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；路由優(yōu)化；蟻群算法；遺傳算法

0引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)[1]是由分布在需要監(jiān)測(cè)范圍內(nèi)的大量微型傳感器通過(guò)無(wú)線通信的方式來(lái)傳輸數(shù)據(jù)所組成的一種網(wǎng)絡(luò)，被廣泛應(yīng)用在環(huán)境比較復(fù)雜、人員不能到達(dá)的區(qū)域。傳感器節(jié)點(diǎn)小，數(shù)量多，能量大多數(shù)由電池來(lái)提供，經(jīng)過(guò)部署之后，很難再補(bǔ)充能量[2]。設(shè)計(jì)一個(gè)好的路由協(xié)議對(duì)減少能量消耗并且延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期有著重要的意義。針對(duì)現(xiàn)有的WSN路由優(yōu)化算法，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，文獻(xiàn)[3] Kassabalidis等人首次提出AntNet算法，該算法可以很快的建立好網(wǎng)絡(luò)路由，對(duì)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有著很強(qiáng)的適應(yīng)能力；但沒(méi)有考慮網(wǎng)絡(luò)節(jié)點(diǎn)的能耗，導(dǎo)致整個(gè)網(wǎng)絡(luò)生命周期縮短。文獻(xiàn)[4]提出了一種稱之為ACRA的路由協(xié)議，這個(gè)路由算法，采用了主路徑和備用路由相結(jié)合的方式，同時(shí)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)狀態(tài)更新路由表，從而使得整個(gè)網(wǎng)絡(luò)的時(shí)延和能量消耗的性能有了很大的提高。文獻(xiàn)[5]提出了一種基于地理位置信息的路由協(xié)議POSANT算法，按照鄰居節(jié)點(diǎn)間的距離匯聚節(jié)點(diǎn)的遠(yuǎn)近程度劃分區(qū)域，螞蟻分組使用不同信息素更新策略來(lái)尋找下一跳路由。上述路由算法中，大部分是使網(wǎng)絡(luò)的某一性能有所改善提高，并沒(méi)有綜合考慮多種性能參數(shù)，無(wú)法應(yīng)對(duì)意外狀況的發(fā)生。

如何綜合考慮多種網(wǎng)絡(luò)性能參數(shù)，改進(jìn)蟻群算法使該算法適應(yīng)WSN隨機(jī)的網(wǎng)絡(luò)拓?fù)洵h(huán)境？本文提出了一種基于改進(jìn)蟻群算法的路由優(yōu)化算法，在蟻群算法的基礎(chǔ)上，結(jié)合遺傳算法的選擇、交叉和變異的操作，從而提高蟻群算法的搜索速度和尋優(yōu)能力。最優(yōu)路徑評(píng)價(jià)函數(shù)綜合考慮節(jié)點(diǎn)能耗及節(jié)點(diǎn)的剩余能量，使剩余能量多的節(jié)點(diǎn)優(yōu)先參與數(shù)據(jù)轉(zhuǎn)發(fā)，均衡節(jié)點(diǎn)間的能量消耗，達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。

1無(wú)線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)

無(wú)線傳感器網(wǎng)絡(luò)是由傳感器、感知對(duì)象和觀察者3個(gè)要素所構(gòu)成的。 在無(wú)線傳感器網(wǎng)絡(luò)中，所有的傳感器節(jié)點(diǎn)都是通過(guò)互相協(xié)調(diào)合作的方式來(lái)對(duì)該區(qū)域進(jìn)行監(jiān)測(cè)，并且通過(guò)無(wú)線信號(hào)來(lái)進(jìn)行數(shù)據(jù)的傳輸和處理，最后將結(jié)果反饋給用戶[6]。

無(wú)線傳感器網(wǎng)絡(luò)有以下幾個(gè)特點(diǎn)：

1)每一個(gè)傳感器節(jié)點(diǎn)在工作時(shí)不僅要進(jìn)行數(shù)據(jù)的采集和發(fā)送，而且還要進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。

2)每個(gè)傳感器的節(jié)點(diǎn)都是以單跳或者多跳的方式來(lái)進(jìn)行數(shù)據(jù)的傳輸，最終將信息發(fā)送到匯聚節(jié)點(diǎn)處。

3)匯聚節(jié)點(diǎn)與管理終端的數(shù)據(jù)發(fā)送方式有很多種，比如互聯(lián)網(wǎng)、局域網(wǎng)、衛(wèi)星通信等。

圖1　無(wú)線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)

2蟻群算法

2.1基本的蟻群算法

蟻群算法是意大利學(xué)者M(jìn).Dorigo通過(guò)對(duì)自然界中螞蟻的行為進(jìn)行研究所提出的一種新型的模擬進(jìn)化算法[7]。研究發(fā)現(xiàn)：螞蟻在覓食過(guò)程中，會(huì)釋放出一種信息素，該信息素會(huì)引導(dǎo)螞蟻選擇從洞穴到食物之間的最優(yōu)路徑。螞蟻尋找到食物返回洞穴的過(guò)程中，會(huì)在返回的路徑上留下信息素，后面的螞蟻不但可以檢測(cè)到該信息素的存在，還可以檢測(cè)出信息素的濃度大小[8]。螞蟻會(huì)選擇信息素濃度較高的路徑來(lái)進(jìn)行覓食。同時(shí)，信息素還具有揮發(fā)的特性，隨著時(shí)間的推移，路程較遠(yuǎn)的路徑上的信息素會(huì)慢慢地?fù)]發(fā)，濃度降低，那么螞蟻選擇該路徑的概率會(huì)大大減少。路程較近的路徑留下的信息素濃度增加，螞蟻選擇該路徑的概率會(huì)增加，這種信息素濃度的增加會(huì)使后面的螞蟻更高概率地選擇該路徑，這一現(xiàn)象就是正反饋。通過(guò)這種正反饋，螞蟻總能選擇到食物與洞穴之間的最優(yōu)路徑[9]。

2.2蟻群算法

通過(guò)對(duì)螞蟻覓食的基本原理進(jìn)行研究，科學(xué)家們?cè)O(shè)計(jì)了能夠?qū)ふ易顑?yōu)路徑的蟻群算法，算法的主要步驟為：

1)設(shè)外出尋找食物的螞蟻數(shù)量為m只，并且該m只螞蟻是隨機(jī)出發(fā)的。

2)螞蟻在覓食的過(guò)程中會(huì)在路徑上留下信息素。設(shè)經(jīng)過(guò)時(shí)間t之后，在路徑(i,j)上留下的信息素的濃度為τi,j(t) 。并且在初始時(shí)刻的時(shí)候各個(gè)路徑上的信息素的濃度是相同的，并且τi,j(0)=C，C為常數(shù)。

3)螞蟻從洞穴出發(fā)尋找食物，通過(guò)對(duì)每條路徑上的信息素的濃度進(jìn)行比較，最終決定轉(zhuǎn)移的方向。由以下的公式來(lái)定義螞蟻的選擇概率：

(1)

(2)

4)螞蟻在整個(gè)覓食過(guò)程中，一直在釋放信息素。每條路徑上的信息素濃度一直在發(fā)生著變化[10]。信息素濃度的變化過(guò)程可以用公式(3)來(lái)表示：τ(i,j)←(1-ρ)τ(i,j)+ρΔτk(i,j)

(3)

式中，ρ 表示的是信息素在揮發(fā)時(shí)的參數(shù)。Lk表示的是第k只螞蟻所爬行的總路程。

2.3改進(jìn)的蟻群算法

基本的蟻群算法在尋找最優(yōu)路徑的過(guò)程中，局部尋優(yōu)能力比較強(qiáng)，但是全局搜索能力比較弱。當(dāng)尋找路徑到達(dá)一定程度時(shí)，就會(huì)停滯不前，搜索能力會(huì)大大減慢。為了提高無(wú)線傳感器網(wǎng)絡(luò)的路徑優(yōu)化的效率，提出了一種改進(jìn)的蟻群算法[11]。該改進(jìn)是將遺傳算法中的交叉、選擇和變異等遺傳算子引入到蟻群算法中，來(lái)提高尋找最優(yōu)路徑過(guò)程中的收斂速度和全局搜索的能力。

2.3.1路徑編碼

改進(jìn)的蟻群算法在尋找最優(yōu)路徑之前需要對(duì)路徑進(jìn)行編碼。編碼方式采用實(shí)數(shù)方式，假如整個(gè)傳感器網(wǎng)絡(luò)中的傳感器的數(shù)量為n，則將傳感器節(jié)點(diǎn)分別編碼為1，2，3，…，n。傳感器最終需要將數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)上，那么將最終的匯聚節(jié)點(diǎn)編碼為0。每經(jīng)過(guò)一次循環(huán)，即傳感器采集數(shù)據(jù)，經(jīng)過(guò)各個(gè)節(jié)點(diǎn)的接收和發(fā)送，最終傳輸?shù)絽R聚節(jié)點(diǎn)的過(guò)程，就會(huì)得到一組路徑編碼。比如，獲得的一組編碼是：1，2，4，6，10，0，那么數(shù)據(jù)傳輸?shù)穆窂绞墙?jīng)過(guò)編碼為1，2，4，6，10，0的傳感器。

2.3.2適應(yīng)度函數(shù)的設(shè)計(jì)

無(wú)線傳感器網(wǎng)絡(luò)的適應(yīng)度函數(shù)的設(shè)計(jì)需要考慮多個(gè)因素，比如：路徑的總長(zhǎng)度；每一個(gè)節(jié)點(diǎn)接收和發(fā)送數(shù)據(jù)的能量消耗；整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的能量均衡分布。考慮到以上幾個(gè)因素，一條由n個(gè)傳感器組成的適應(yīng)度函數(shù)可以用以下公式來(lái)表示：

(4)

式中，wd為距離權(quán)重，we為能量消耗權(quán)重，wl為整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的能量消耗權(quán)重，d(p)為該傳輸路徑的總長(zhǎng)度，e(p)為該路徑的能量消耗，l(p)為整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的能量消耗。

2.3.3選擇操作

在選擇操作過(guò)程，每經(jīng)過(guò)一輪尋優(yōu)過(guò)程之后，會(huì)得到一個(gè)路徑集合，將每條路徑進(jìn)行適應(yīng)度函數(shù)的計(jì)算，從中選擇出比較優(yōu)的路徑來(lái)進(jìn)行下一輪的搜索。這樣經(jīng)過(guò)幾次尋優(yōu)過(guò)程之后，會(huì)使比較優(yōu)的路徑上的信息素的濃度越來(lái)越大，該路徑被選擇的概率也越來(lái)越大，這樣大大加快了尋優(yōu)過(guò)程中的收斂速度。

2.3.4交叉操作

為了避免在全局搜索的過(guò)程中出現(xiàn)停滯不前的現(xiàn)象，引入了交叉操作[12]。經(jīng)過(guò)該操作，可以擴(kuò)大搜索的范圍，防止局部最優(yōu)解出現(xiàn)。蟻群算法在經(jīng)過(guò)一輪搜索之后，會(huì)得到一些優(yōu)解和次優(yōu)解的路徑，將優(yōu)解和次優(yōu)解來(lái)進(jìn)行交叉操作，可以得到更多的路徑來(lái)進(jìn)行選擇。假如S1表示最優(yōu)解，S2表示次優(yōu)解，那么交叉操作可以用以下過(guò)程來(lái)表示：

1)產(chǎn)生交叉操作的起始位置和交叉的長(zhǎng)度都是隨機(jī)的。

2)假如S1的路徑為P1,P2,P3。S2的路徑為Q1,Q2,Q3。發(fā)成交叉的位置為P2和Q2，交叉的長(zhǎng)度為P2和Q2。那么經(jīng)過(guò)交叉之后得到的新的路徑為S3:P1,Q2,P2,P3。

3)將S3中重復(fù)的節(jié)點(diǎn)刪除，最后得到一個(gè)新的路徑S3。

4)通過(guò)上述方法得到新的路徑S4。

5)對(duì)路徑S1,S2,S3,S4進(jìn)行適應(yīng)度函數(shù)計(jì)算，最終得到最優(yōu)的一條路徑。

2.3.5變異操作

1)假設(shè)發(fā)生N次變異；

2)隨機(jī)產(chǎn)生兩個(gè)自然數(shù)n1和n2，并且n1,n2

3)將最優(yōu)路徑S上的第n1和n2個(gè)節(jié)點(diǎn)進(jìn)行相互交換，產(chǎn)生新的編碼路徑S1；

4)對(duì)編碼路徑S和S1進(jìn)行適應(yīng)度函數(shù)計(jì)算，最后選擇最優(yōu)編碼路徑進(jìn)行下一步。

2.3.6改進(jìn)蟻群算法路徑優(yōu)化流程

在改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)路徑優(yōu)化過(guò)程中，需要對(duì)無(wú)線傳感器網(wǎng)絡(luò)建立數(shù)學(xué)模型，并且進(jìn)行初始化處理。文獻(xiàn)[13]提出了一種基于路徑平滑和信息素動(dòng)態(tài)更新的自適應(yīng)蟻群算法。在該算法的基礎(chǔ)上得到啟發(fā)：在尋優(yōu)過(guò)程中，進(jìn)行遺傳算法中的選擇、交叉和變異操作，來(lái)加快收斂速度和提高全局搜索的能力，最終得到一條最優(yōu)的數(shù)據(jù)傳輸路徑。整個(gè)工作流程如圖2所示。

圖2改進(jìn)蟻群算法的WSN路徑優(yōu)化流程

3仿真研究

3.1仿真環(huán)境以及參數(shù)設(shè)置

為了更好地驗(yàn)證改進(jìn)的蟻群算法的路徑優(yōu)化性能，需要對(duì)其進(jìn)行仿真研究，采用網(wǎng)絡(luò)模擬軟件NS2來(lái)進(jìn)行仿真。在仿真開(kāi)始之前，需要對(duì)參數(shù)進(jìn)行初步的設(shè)置。進(jìn)行仿真的傳感器點(diǎn)的數(shù)目為10個(gè)。蟻群算法仿真所需要的參數(shù)為：整個(gè)路徑中的螞蟻總個(gè)數(shù)為10個(gè)，α=0.2，β=0.2，ρ=0.3；遺傳算法仿真所需要的參數(shù)為：螞蟻種群的總個(gè)數(shù)為10個(gè)，在進(jìn)化過(guò)程中最多能夠進(jìn)化1 000次，發(fā)生交叉操作的概率為0.9，發(fā)生變異操作的概率為0.01。無(wú)線感器網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。

圖3　無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)圖

3.2算法的性能評(píng)價(jià)指標(biāo)

為了能夠更好地看出每種算法的優(yōu)化效率，讓結(jié)果具有可比性，需要建立算法的性能評(píng)價(jià)指標(biāo)。本次指標(biāo)從路徑能量消耗和尋找最優(yōu)路徑的成功率兩個(gè)方面來(lái)完成。同時(shí)將改進(jìn)的蟻群算法和蟻群算法、遺傳算法相比較，來(lái)體現(xiàn)出改進(jìn)算法的優(yōu)越性[14]。螞蟻在尋找最優(yōu)路徑的過(guò)程中需要不斷的消耗能量，那么在尋找最優(yōu)路徑的過(guò)程中螞蟻消耗的總能量為：

(5)

其中：E表示的是消耗的總能量，ei表示的是每個(gè)節(jié)點(diǎn)消耗的能量。

傳輸過(guò)程中的能量消耗采用自由空間模型計(jì)算。路徑損耗由下面的公式來(lái)計(jì)算：

(6)

(7)

因此在已知傳感器的初始能量、仿真次數(shù)和運(yùn)行時(shí)間的前提下，可以計(jì)算出各個(gè)節(jié)點(diǎn)的剩余能量。

3.3仿真結(jié)果

3.3.1能量消耗仿真結(jié)果

3種算法的能量消耗總量的仿真結(jié)果如圖4所示，從圖中可以看出，改進(jìn)的蟻群算法在尋找最優(yōu)路徑的過(guò)程中消耗的能量最少，其次是蟻群算法，能量消耗最多的是遺傳算法。因此，改進(jìn)的蟻群算法能夠減少能量消耗，延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期[15]。

圖4　3種算法能量消耗

圖5表示的是節(jié)點(diǎn)的平均剩余能量和算法運(yùn)行的時(shí)間長(zhǎng)短之間的關(guān)系。X軸為3種算法進(jìn)行仿真的時(shí)間，本次的仿真時(shí)間為1 200 s，Y軸表示的是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的平均剩余能量。從圖中可以看出，在同一時(shí)刻，改進(jìn)的蟻群算法的節(jié)點(diǎn)平均剩余能量要高于蟻群算法和遺傳算法，表明改進(jìn)的蟻群算法的能量消耗要低于其他的兩種算法。在圖中還可以得到，改進(jìn)的蟻群算法的網(wǎng)絡(luò)生命周期是蟻群算法的1.21倍，是遺傳算法的1.75倍。因此，改進(jìn)的蟻群算法大大延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。

圖5節(jié)點(diǎn)平均剩余能量和算法運(yùn)行時(shí)間的關(guān)系

3.3.2最優(yōu)路徑搜索成功率

表1所示的是3種算法經(jīng)過(guò)100組，每組100次仿真之后得到的最優(yōu)路徑搜索的成功率。在仿真過(guò)程中，通過(guò)適應(yīng)度函數(shù)和能量消耗的計(jì)算可以得到一條從初始節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的一條最優(yōu)路徑S。每次仿真結(jié)束之后會(huì)得到一條路徑S1，將S1與S相比較來(lái)確定該次仿真是否獲得最優(yōu)路徑。從表中可以看出，改進(jìn)的蟻群算法是3種算法中最優(yōu)路徑搜索成功率最高的，其實(shí)是蟻群算法和遺傳算法。改進(jìn)的蟻群算法在蟻群算法的基礎(chǔ)上進(jìn)行選擇、交叉和變異的操作，不僅能夠減少路徑中能量的消耗，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命，還大大提高了搜索最優(yōu)路徑的成功率。

表1　3種算法最優(yōu)路徑搜索成功率

4結(jié)論

通過(guò)本文理論敘述和仿真比較，驗(yàn)證了本文提出的算法在無(wú)線傳感器網(wǎng)絡(luò)實(shí)際應(yīng)用中選擇路徑，均衡能源延長(zhǎng)網(wǎng)絡(luò)生命周期的優(yōu)勢(shì)：

1)本文結(jié)合遺傳算法的選擇、交叉和變異的操作，從而提高蟻群算法的搜索速度和尋優(yōu)能力。使網(wǎng)絡(luò)能夠快速地建立一條最優(yōu)的無(wú)線傳感器網(wǎng)絡(luò)路徑，減少能量消耗，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。

2)本文綜合考慮網(wǎng)絡(luò)各性能指標(biāo)，隨著數(shù)據(jù)轉(zhuǎn)發(fā)輪數(shù)增加，改進(jìn)的蟻群算法能耗小，剩余能量多，網(wǎng)絡(luò)生命周期明顯延長(zhǎng)；

3)隨著整個(gè)網(wǎng)絡(luò)運(yùn)行時(shí)間的增長(zhǎng)，改進(jìn)的蟻群算法，節(jié)點(diǎn)均衡能耗性好，最優(yōu)路徑搜索的成功率也明顯優(yōu)于其他兩種算法。

參考文獻(xiàn)：

[1] 蘇錦，等.改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)路徑優(yōu)化[J].計(jì)算機(jī)仿真，2012,29(8):112-115.

[2] 陳宇，等.基于改進(jìn)蟻群算法的無(wú)線傳感網(wǎng)絡(luò)路由的研究[D].廣州：華南理工大學(xué)，2012.

[3] Caro G D, Dorigo M.AntNet: distributed Stigmergetic control for communication networks [J]. Journal of Artificial Intelligence Research, 1998,9(1):317-365.

[4] Caro D, Ducatelle F, Gambardella L. AntHoc Net: an adaptive nature inspired algorithm for routing in mobile ad hoc networks[J].European Transactions on Telecommunnications, 2005,16(5)：443-455.

[5] Rajagopalan S, Shen C .ASNI: A unicast routing protocol for mobile ad hoc networks using swarm intelligence[A].Proceedings of the International Conference on Artificial Intelligence[C]. Italy, 2005：24-27.

[6] 王永玲，郭愛(ài)煌.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議及仿真[J]．計(jì)算機(jī)工程，2006,32(20):123-125.

[7] 馮寶華. 蟻群優(yōu)化算法的原理及改進(jìn)[J].科技信息, 2007, 31(7):94-95.

[8] 吳虎發(fā).蟻群優(yōu)化算法在求解最短路徑問(wèn)題中的研究與應(yīng)用[D].安徽:安徽大學(xué)，2012.

[9] 程滿中. 螞蟻算法在車輛路徑問(wèn)題中的研究[D].湖北:中南民族大學(xué), 2007.

[10] 龔瑜. 面向無(wú)線傳感器網(wǎng)絡(luò)的多路徑路由協(xié)議研究[D].南京:南京郵電大學(xué),2012.

[11] 黎洋.基于蟻群優(yōu)化策略的WSN路由研究[D].長(zhǎng)沙:長(zhǎng)沙理工大學(xué),2013.

[12] 陳雨.基于改進(jìn)遺傳算法的測(cè)試用例生成[J].電子科技，2009,10(7)：9-12.

[13] 何武.基于蟻群優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)路由算法研究[D].重慶:西南交通大學(xué),2008.

[14] 盧天宇.遺傳蟻群混合算法研究及應(yīng)用[D].西安：西安科技大學(xué)，2012.

[15] 李洪兵.基于蟻群算法的WSN路由算法研究[D].重慶：重慶理工大學(xué)，2011.

Optimization of Wireless Sensor Network Routing Based on Improved Ant Colony Algorithm

Dai Tianhong, Li Hao

(School of Mechanical and Electrical Engineering, Northeast Forestry University, Harbin150040，China)

Abstract:In order to extend wireless sensor networks (WSN) life cycle, to keep each node balance between energy consumption, to optimize existing WSN routing algorithm, we propose a routing optimization algorithm based on improved ant colony algorithm. Firstly, the ant colony algorithm and genetic algorithm comparison of the merits, on the basis of ant colony algorithm based on the combination of genetic algorithm selection, crossover and mutation operation, ant colony algorithm to improve search speed and optimization capabilities. Optimal route evaluation function considering the residual energy of nodes and node energy, the remaining energy of many nodes participate in forwarding priority, energy consumption balanced between the nodes. With the classical ant colony algorithm and genetic algorithms comparative experiments show that the number of rounds increases data transfer, improved ant colony algorithm energy consumption, surplus energy and more significantly prolong the network life cycle; with the growth of the entire network uptime, improved ant colony algorithm, node energy balance is good, the success rate of the optimal path search is also significantly better than the other two algorithms.

Keywords:wireless sensor network; route optimization; ant colony algorithm; genetic algorithms

文章編號(hào)：1671-4598(2016)02-0321-04

DOI：10.16526/j.cnki.11-4762/tp.2016.02.089

中圖分類號(hào)：TN926

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介：戴天虹(1963-)，男，黑龍江哈爾濱人，博士，教授，主要從事自動(dòng)化等方面的教學(xué)與科研工作。

基金項(xiàng)目：哈爾濱市科技創(chuàng)新人才(優(yōu)秀學(xué)科帶頭人計(jì)劃類)基金項(xiàng)目2014RFXXJ086。

收稿日期：2015-08-29；修回日期：2015-10-11。