基于蟻群算法和能耗均衡的改進(jìn)LEACH協(xié)議*

周智勇，陳　暉，王海濤，王世界

(1.解放軍理工大學(xué) 通信工程學(xué)院研三隊(duì),江蘇 南京 210007；2.解放軍理工大學(xué) 訓(xùn)練部, 江蘇 南京 210007)

?

基于蟻群算法和能耗均衡的改進(jìn)LEACH協(xié)議*

周智勇1，陳暉2，王海濤2，王世界1

(1.解放軍理工大學(xué) 通信工程學(xué)院研三隊(duì),江蘇 南京 210007；2.解放軍理工大學(xué) 訓(xùn)練部, 江蘇 南京 210007)

摘要：在分布式傳感器網(wǎng)絡(luò)的場(chǎng)景下，結(jié)合傳統(tǒng)的LEACH協(xié)議提出了一種基于有限信道信息的蟻群優(yōu)化(ACO)路由算法。該算法中傳感器節(jié)點(diǎn)只需要獲取與相鄰節(jié)點(diǎn)間的信道信息，而不需要了解網(wǎng)絡(luò)的全局信息，就能夠逐步逼近最優(yōu)路徑。在此基礎(chǔ)上，提出了一種基于能耗均衡的路由傳輸方案，有效改善了LEACH協(xié)議中簇頭節(jié)點(diǎn)能耗不均衡的情況。仿真實(shí)驗(yàn)表明：基于蟻群算法和能耗均衡的改進(jìn)路由方案，能夠利用局部信息快速搜索到能耗最低的路徑，并在傳輸過程中有效地均衡簇頭能耗，從而有效提高了網(wǎng)絡(luò)生存時(shí)間。

關(guān)鍵詞：網(wǎng)絡(luò)生存時(shí)間；LEACH協(xié)議；蟻群算法；能耗均衡

0引言

近年來，無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)技術(shù)在物聯(lián)網(wǎng)、戰(zhàn)場(chǎng)目標(biāo)監(jiān)控和信息收集等領(lǐng)域的得到了廣泛的應(yīng)用[1]。傳感器網(wǎng)絡(luò)由分布在一定區(qū)域內(nèi)的大量傳感器節(jié)點(diǎn)和負(fù)責(zé)收集信息的匯聚節(jié)點(diǎn)組成。通常情況下，傳感器節(jié)點(diǎn)由自身攜帶的電池供電，因而能量有限并且難以再次充電。如何降低傳感器網(wǎng)絡(luò)中的能量消耗已經(jīng)成為了當(dāng)前傳感器網(wǎng)絡(luò)的研究熱點(diǎn)，而路由協(xié)議的設(shè)計(jì)就是其能耗優(yōu)化的關(guān)鍵技術(shù)之一。

文獻(xiàn)[2]提出的LEACH(low energy adaptive clustering hierarchy)協(xié)議是一種典型的分層路由協(xié)議，LEACH協(xié)議通過簇結(jié)構(gòu)分層的方式,當(dāng)傳感器節(jié)點(diǎn)有傳輸數(shù)據(jù)包的需求時(shí)固定向上層的簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，少量的簇頭節(jié)點(diǎn)間通過接力等方式將數(shù)據(jù)包傳送到Sink節(jié)點(diǎn)處。這種分層的方式有效避免了節(jié)點(diǎn)在傳輸信息時(shí)的無方向和無序性，避免信息洪泛所造成的網(wǎng)絡(luò)冗余信息過多的現(xiàn)象。文獻(xiàn)[3-6]等對(duì)傳統(tǒng)的LEACH進(jìn)行了改進(jìn)，其中文獻(xiàn)[3-4]主要針對(duì)LEACH協(xié)議中簇頭節(jié)點(diǎn)的選取規(guī)則進(jìn)行重新設(shè)計(jì)，在簇結(jié)構(gòu)形成階段選取簇頭時(shí)考慮各個(gè)傳感器節(jié)點(diǎn)的剩余能量、與其他節(jié)點(diǎn)的平均距離等因素，文獻(xiàn)[5-6]則在不同限制條件下對(duì)于簇結(jié)構(gòu)的形成和簇頭節(jié)點(diǎn)的形成進(jìn)行了討論?？梢钥闯?，當(dāng)前對(duì)于LEACH協(xié)議的改進(jìn)主要集中在LEACH協(xié)議第一階段，也就是對(duì)于簇結(jié)構(gòu)和簇頭節(jié)點(diǎn)選取的規(guī)則進(jìn)行優(yōu)化。而對(duì)于簇形成之后簇頭節(jié)點(diǎn)信息傳遞過程中的不同路由方式對(duì)于提升網(wǎng)絡(luò)生存時(shí)間的影響研究則比較少，尤其是對(duì)于沒有統(tǒng)一的管理節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)均不了解網(wǎng)絡(luò)全局信息的分布式傳感器網(wǎng)絡(luò)的場(chǎng)景的研究比較缺乏。

文獻(xiàn)[7]提出的定向擴(kuò)散的方法，使距離Sink節(jié)點(diǎn)較遠(yuǎn)的外層節(jié)點(diǎn)方向性地向距離Sink節(jié)點(diǎn)較近的節(jié)點(diǎn)傳送數(shù)據(jù)。文獻(xiàn)[8-10]提出在分布式傳感器網(wǎng)絡(luò)中基于搜索樹的路由方案?？梢园l(fā)現(xiàn)，當(dāng)前對(duì)于簇結(jié)構(gòu)形成之后路由的搜索主要以能耗最低的最優(yōu)路由為目標(biāo)。文獻(xiàn)[11]的NBEERP(negotiation-based energy efficient routing protocol)路由協(xié)議提出節(jié)點(diǎn)保留多條可以到達(dá)網(wǎng)絡(luò)匯聚節(jié)點(diǎn)Sink的路由，但其保留多條路徑的目的在于提高網(wǎng)絡(luò)的魯棒性，而沒有關(guān)注保留多條路徑對(duì)于均衡簇頭節(jié)點(diǎn)能耗、提升網(wǎng)絡(luò)生存時(shí)間的意義。針對(duì)這一研究現(xiàn)狀，本文提出了一種能夠綜合利用多條路徑均衡傳送信息的路由傳輸方案。

文章著重了研究基于蟻群算法和能耗均衡的LEACH路由方案，并對(duì)該方案的網(wǎng)絡(luò)生存時(shí)間和覆蓋性能進(jìn)行了仿真和對(duì)比，具體的工作和章節(jié)安排如下所示：

(1)第二部分在接力傳輸方式下對(duì)傳感器網(wǎng)絡(luò)的能耗情況進(jìn)行系統(tǒng)描述和公式建模，對(duì)與傳統(tǒng)的LEACH協(xié)議和蟻群算法的運(yùn)行過程進(jìn)行了簡(jiǎn)要的描述；

(2)第三部分主要描述了本文提出的基于蟻群算法和能耗均衡的路由方案的運(yùn)行過程，給出算法的細(xì)節(jié)，并對(duì)該方案的有效性進(jìn)行了初步的分析；

(3)第四部分在分布式傳感器網(wǎng)絡(luò)中基于有限的信道信息條件下對(duì)于蟻群算法搜索最優(yōu)路徑的有效性進(jìn)行了仿真驗(yàn)證，并對(duì)本文提出的基于蟻群算法和能耗均衡的路由方案與其他文獻(xiàn)中提出的路由方案進(jìn)行了比較仿真。

(4)第五部分對(duì)實(shí)驗(yàn)結(jié)果和本文的主要工作進(jìn)行總結(jié)。

1模型描述

1.1通信模型

傳感器網(wǎng)絡(luò)采用傳統(tǒng)的LEACH分簇路由協(xié)議[2]。設(shè)定我們需要監(jiān)控的區(qū)域?yàn)槎S區(qū)域A，以匯聚節(jié)點(diǎn)Sink(0,0)為圓心，半徑為y=250 m的圓形區(qū)域。監(jiān)控目標(biāo)D在區(qū)域A內(nèi)隨機(jī)出現(xiàn)。當(dāng)監(jiān)控目標(biāo)D在傳感器節(jié)點(diǎn)m的感知距離內(nèi)時(shí)，傳感器節(jié)點(diǎn)m生成可以傳輸?shù)男畔?。生成的?shù)據(jù)包將通過LEACH協(xié)議傳輸?shù)絽R聚節(jié)點(diǎn)Sink處。

1.2能耗模型

本文中點(diǎn)對(duì)點(diǎn)通信采用QPSK方式，根據(jù)文獻(xiàn)[12]，該通信方式的誤碼率特性為：

(1)

bQPSK=sin2(π/4)

(2)

式中，ρ表示接收端信噪比。若通信需要的最低誤碼率要求為ΨQPSK≤ρrequire時(shí)，通過查表的方式可以逆向得到最低接收信噪比為ρ0。發(fā)送功率與接收端信噪比滿足路徑損耗方程：

(3)式中，P、N0分別為發(fā)送功率、噪聲功率，h為理想瑞利信道的衰落系數(shù)，d為發(fā)送端和接收端的距離，α為路徑損耗系數(shù)，Gt、Gr分別為發(fā)送和接收天線增益。當(dāng)ρ=ρ0時(shí)，可以計(jì)算出發(fā)送端需要的發(fā)送功率：

(4)

1.3LEACH協(xié)議

LEACH協(xié)議的運(yùn)作過程可以準(zhǔn)備階段和穩(wěn)定階段，在準(zhǔn)備階段進(jìn)行簇頭節(jié)點(diǎn)的選取和簇的形成，在穩(wěn)定階段進(jìn)行數(shù)據(jù)的搜集和傳輸。網(wǎng)絡(luò)循環(huán)經(jīng)歷準(zhǔn)備階段和穩(wěn)定階段。如圖1所示。

圖1　LEACH協(xié)議運(yùn)行過程

在準(zhǔn)備階段，節(jié)點(diǎn)隨機(jī)被選作簇頭節(jié)點(diǎn)，所有簇頭節(jié)點(diǎn)廣播通告信息ADV，其他傳感器節(jié)點(diǎn)根據(jù)接收到的不同的ADV信號(hào)強(qiáng)度選擇加入信號(hào)最強(qiáng)的簇頭所在的簇。

在穩(wěn)定階段，當(dāng)有傳感器節(jié)點(diǎn)需要向Sink節(jié)點(diǎn)傳輸數(shù)據(jù)，該節(jié)點(diǎn)首先將數(shù)據(jù)包發(fā)送至其所在的簇的簇頭節(jié)點(diǎn)，由簇頭節(jié)點(diǎn)通過其他簇頭節(jié)點(diǎn)將信息接力到Sink節(jié)點(diǎn)處。

1.4蟻群算法

蟻群算法(Ant Colony Algorithm, ACO)是一種新興的仿生算法，具有較強(qiáng)的魯棒性和優(yōu)良的分布式計(jì)算機(jī)制，適合本文分布式傳感器網(wǎng)絡(luò)的場(chǎng)景中。蟻群算法用于解決本文路由搜索為的基本流程如圖2所示。

圖2　蟻群算法運(yùn)行流程

1.5網(wǎng)絡(luò)生存時(shí)間

文獻(xiàn)[13-15]對(duì)網(wǎng)絡(luò)生存時(shí)間進(jìn)行了不同的定義，其中文獻(xiàn)[13-14]將網(wǎng)絡(luò)生存時(shí)間定義為從網(wǎng)絡(luò)開始運(yùn)行到出現(xiàn)能量耗盡的節(jié)點(diǎn)時(shí)所經(jīng)歷的時(shí)間，而文獻(xiàn)[15]將網(wǎng)絡(luò)生存時(shí)間定義為從網(wǎng)絡(luò)開始運(yùn)行到網(wǎng)絡(luò)對(duì)監(jiān)控目標(biāo)區(qū)域的覆蓋率下降到容忍值的時(shí)間。本文采取前一種的定義方式，這是因?yàn)橐坏┚W(wǎng)絡(luò)中出現(xiàn)死亡節(jié)點(diǎn)，死亡節(jié)點(diǎn)周邊其他傳感器節(jié)點(diǎn)的能耗急劇增加，導(dǎo)致其他的傳感器節(jié)點(diǎn)很快耗盡電池的能量。能夠有效推遲第一個(gè)節(jié)點(diǎn)的死亡時(shí)間的節(jié)點(diǎn)分布模型具有很大可能能夠推遲大部分節(jié)點(diǎn)的死亡。

2基于蟻群算法和能耗均衡的LEACH路由方案

在本文提出的基于蟻群算法和能耗均衡的LEACH路由方案中，蟻群算法主要用于在LEACH協(xié)議中簇結(jié)構(gòu)形成之后簇頭間的路由搜索過程。由于蟻群算法只需要各個(gè)簇頭間的信道信息而不需要了解網(wǎng)絡(luò)的全局信息，因而蟻群算法的路由搜索方案適用于不存在中心控制節(jié)點(diǎn)的分布式傳感器網(wǎng)絡(luò)當(dāng)中。各個(gè)簇頭節(jié)點(diǎn)間的信道信息可以在簇頭節(jié)點(diǎn)選取和簇結(jié)構(gòu)形成階段獲取，各簇頭節(jié)點(diǎn)根據(jù)其他簇頭節(jié)點(diǎn)廣播的ADV信息，獲取臨近的信道狀態(tài)，并將這些信道狀態(tài)作為初始的局部信息。

各簇首節(jié)點(diǎn)確定初始信道信息之后，向周圍簇頭發(fā)送少量數(shù)據(jù)，數(shù)據(jù)的在節(jié)點(diǎn)之間的接力傳輸過程遵循蟻群算法。各數(shù)據(jù)包每前進(jìn)一步，所在的簇首節(jié)點(diǎn)即存儲(chǔ)并更新禁忌表(這里禁忌表即為數(shù)據(jù)包已經(jīng)訪問過的簇首集合)，若發(fā)現(xiàn)禁忌表中已經(jīng)包含了Sink節(jié)點(diǎn)，則立即停止該數(shù)據(jù)包的傳遞。將所有數(shù)據(jù)包均前進(jìn)一步作為一個(gè)循環(huán)，每次循環(huán)之后需要進(jìn)行信息素的更新，即各簇首節(jié)點(diǎn)根據(jù)自身發(fā)送功率分布情況，以節(jié)點(diǎn)間傳輸?shù)墓β市畔㈩惐茸鳛橄伻核惴ㄖ械男畔⑺剡M(jìn)行實(shí)時(shí)更新，進(jìn)而獲得新的路由轉(zhuǎn)移概率值，為下一個(gè)循環(huán)中各數(shù)據(jù)的傳遞提供參考。至此，蟻群路由算法的一個(gè)運(yùn)轉(zhuǎn)周期結(jié)束。經(jīng)過足夠多個(gè)周期的運(yùn)轉(zhuǎn)之后，各簇首節(jié)點(diǎn)能夠根據(jù)所存儲(chǔ)的轉(zhuǎn)移概率值和禁忌表信息，建立路由表。

為了找到與Sink之間的最優(yōu)路徑，簇頭節(jié)點(diǎn)需要根據(jù)反饋信息不斷更新和存儲(chǔ)最優(yōu)路徑。通過這一過程，能夠?qū)崿F(xiàn)從局部最優(yōu)路徑逐步逼近全局最優(yōu)路徑。

能耗均衡的方案主要用于網(wǎng)絡(luò)穩(wěn)定運(yùn)行階段，其主要思想是當(dāng)簇頭節(jié)點(diǎn)需要向Sink節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)，依概率選擇能耗最低和次最低的路徑進(jìn)行傳輸。能耗均衡的主要目的是避免過度使用同一條路徑對(duì)該路徑上的傳感器節(jié)點(diǎn)造成過大的能耗壓力。本文設(shè)定選擇最優(yōu)能耗路徑和次優(yōu)能耗路徑的概率與其路徑能耗成反比，即能耗較低的路徑被選擇的概率大，而能耗較高的路徑被選擇的概率小。設(shè)定選擇最優(yōu)路徑的概率為：

(5)

選擇次優(yōu)路徑的概率為：

(6)

式中，Eoptimal和Esub_optimal分別表示最優(yōu)路徑和次優(yōu)路徑上的能耗。網(wǎng)絡(luò)經(jīng)過足夠長(zhǎng)時(shí)間的運(yùn)行，最優(yōu)和次優(yōu)路徑上的能耗均為：

(7)

雖然能耗均衡的方法提升了每次傳輸所消耗的能量，但能耗均衡的方法能夠較好的分配數(shù)據(jù)傳輸所產(chǎn)生的傳輸能耗，降低只利用最優(yōu)路徑進(jìn)行傳輸對(duì)于最優(yōu)路徑上的節(jié)點(diǎn)的能耗壓力?？梢酝茰y(cè)，當(dāng)網(wǎng)絡(luò)規(guī)模較大，尤其是簇頭節(jié)點(diǎn)數(shù)量較多時(shí)，最優(yōu)路徑和次優(yōu)路徑能耗差值較小，此時(shí)能耗均衡的方案效果更佳明顯。本文提出的基于蟻群算法和能耗均衡的LEACH路由方案具體細(xì)節(jié)如下：

算法名稱：基于蟻群算法和能耗均衡的LEACH協(xié)議改進(jìn)方案。

輸入：傳感器節(jié)點(diǎn)與鄰近節(jié)點(diǎn)間信道信息。

輸出：

步驟1：

根據(jù)LEACH協(xié)議，網(wǎng)絡(luò)中的節(jié)點(diǎn)選舉簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)向周圍節(jié)點(diǎn)等功率廣播被選作簇頭節(jié)點(diǎn)的信息ADV，其他節(jié)點(diǎn)依據(jù)接收信號(hào)ADV的強(qiáng)度加入各個(gè)簇，其他簇頭節(jié)點(diǎn)根據(jù)接收信號(hào)ADV得到信道信息。

步驟2：

整個(gè)論壇都炸開來，網(wǎng)友回帖回了十幾頁，有鼓勵(lì)，有驚嘆，有支持，惟獨(dú)沒有抨擊。太多人知道羅漠的寂寞，有人對(duì)他說，你們的愛情感動(dòng)了所有人，可是逝者已矣，如果楚西有靈，她也必是不愿見你孤獨(dú)一生。

各簇頭節(jié)點(diǎn)根據(jù)先驗(yàn)信息和功率信息素初始值，對(duì)各自狀態(tài)轉(zhuǎn)移概率進(jìn)行初始化設(shè)置。隨后各簇頭根據(jù)初始轉(zhuǎn)移概率向Sink節(jié)點(diǎn)發(fā)送少量數(shù)據(jù)包，任意數(shù)據(jù)包在接力傳輸過程中每實(shí)現(xiàn)一跳，相應(yīng)的簇頭節(jié)點(diǎn)立即對(duì)禁忌表進(jìn)行修改并存儲(chǔ)，當(dāng)全部數(shù)據(jù)包均前進(jìn)一步完成一個(gè)周期之后，所有簇頭節(jié)點(diǎn)更新功率信息素，并計(jì)算存儲(chǔ)新的狀態(tài)轉(zhuǎn)移概率值，進(jìn)入新的周期。經(jīng)過充分迭代之后，蟻群算法實(shí)現(xiàn)收斂，輸出路由表信息。

步驟3：

根據(jù)步驟4輸出的路由表信息，各個(gè)簇頭節(jié)點(diǎn)都能搜索各自到Sink節(jié)點(diǎn)的能耗最優(yōu)和次優(yōu)路徑，并將最優(yōu)和次優(yōu)路徑保存。

步驟4：

步驟5：

經(jīng)過一段時(shí)間的運(yùn)行，網(wǎng)絡(luò)進(jìn)行簇頭節(jié)點(diǎn)的重新選舉和簇的重構(gòu)。

3仿真和數(shù)據(jù)分析

設(shè)定監(jiān)控區(qū)域?yàn)槎S區(qū)域A為以匯聚節(jié)點(diǎn)Sink(0,0)為圓心，半徑為y=250m的圓形區(qū)域。需要監(jiān)控的目標(biāo)隨機(jī)出現(xiàn)在區(qū)域A內(nèi)，且目標(biāo)的分布滿足均勻分布。區(qū)域A內(nèi)傳感器總數(shù)為100個(gè)。其它仿真參數(shù)的設(shè)置如表1所示。

表1　仿真參數(shù)設(shè)置

圖3展示了傳統(tǒng)的以能耗最低路徑為搜索目標(biāo)的方案和本文基于ACO和能耗均衡的方案網(wǎng)絡(luò)的生存時(shí)間的對(duì)比。這里的網(wǎng)絡(luò)生存時(shí)間指網(wǎng)絡(luò)從開始運(yùn)行到網(wǎng)絡(luò)出現(xiàn)第一個(gè)節(jié)點(diǎn)因耗盡能量而死亡的時(shí)間。從圖中可以看到，在5次仿真中，本文提出的基于ACO和能耗均衡的LEACH算法能夠有效延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間，提升的幅度最大可以達(dá)到12.5%。從而說明，能耗均衡能夠較好地均衡網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的傳輸能耗，從而推遲網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡時(shí)間的到來。

圖3　網(wǎng)絡(luò)生存時(shí)間比較

本文進(jìn)而仿真了網(wǎng)絡(luò)的覆蓋率隨著時(shí)間的變化情況。網(wǎng)絡(luò)覆蓋率定義為網(wǎng)絡(luò)中所有傳感器能夠探測(cè)到的區(qū)域面積占目標(biāo)總區(qū)域的比例。選擇對(duì)于網(wǎng)絡(luò)的覆蓋率變化情況進(jìn)行仿真的原因在于網(wǎng)絡(luò)覆蓋率的變化很大程度上反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的死亡情況。網(wǎng)絡(luò)覆蓋率的下降說明網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)量的增加。另外，網(wǎng)絡(luò)覆蓋率是網(wǎng)絡(luò)實(shí)現(xiàn)其功能最重要的指標(biāo)，當(dāng)覆蓋率下降到一定程度時(shí)網(wǎng)絡(luò)已經(jīng)失去正常運(yùn)行的功能。

圖4展示了在網(wǎng)絡(luò)達(dá)到網(wǎng)絡(luò)生存時(shí)間后，即出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡后，網(wǎng)絡(luò)覆蓋率隨時(shí)間變化情況。仿真中每隔10 000輪進(jìn)行網(wǎng)絡(luò)覆蓋率的測(cè)算，由于仿真采用蒙特卡洛方法，因而曲線呈現(xiàn)略微的抖動(dòng)。從圖中可以看出，兩種方案的初始覆蓋率相當(dāng)，并隨著時(shí)間的推移逐漸下降，說明不斷有節(jié)點(diǎn)因?yàn)槟芰亢谋M而死亡。對(duì)比文獻(xiàn)[9]中的搜索樹的路由方法和本文中的基于ACO和能耗均衡的LEACH方案的覆蓋率情況，網(wǎng)絡(luò)在9×105輪之前，本文提出的方案覆蓋率較高，而在9×105之后，本文的方案覆蓋率較低。而網(wǎng)絡(luò)在9×105輪時(shí)網(wǎng)絡(luò)的覆蓋率為50%，即網(wǎng)絡(luò)只能對(duì)50%的區(qū)域?qū)崿F(xiàn)有效的探測(cè)和信息感知，網(wǎng)絡(luò)已經(jīng)基本失去其基本功能。因而可以總結(jié)：本文提出的基于蟻群算法和能耗均衡的LEACH方案在網(wǎng)絡(luò)正常運(yùn)行的大部分時(shí)間覆蓋率較之前以能耗最優(yōu)路徑為搜索目標(biāo)的方案高，從而證明了本文提出的算法的優(yōu)越性。

圖4　網(wǎng)絡(luò)覆蓋率隨時(shí)間變化的比較

4結(jié)語

針對(duì)傳感器網(wǎng)絡(luò)中較為關(guān)心的提升能量利用效率和網(wǎng)絡(luò)生存時(shí)間問題，本文就分布式傳感器網(wǎng)絡(luò)的場(chǎng)景設(shè)計(jì)了一種基于蟻群算法和能耗均衡的改進(jìn)LEACH協(xié)議方案。通過引入蟻群算法實(shí)現(xiàn)了數(shù)據(jù)路由過程中局部最優(yōu)向全局最優(yōu)的逼近，從而解決了有限信息條件下的路徑搜索問題。在此基礎(chǔ)上進(jìn)一步設(shè)計(jì)了能耗均衡的路由選路方案，平衡了各個(gè)節(jié)點(diǎn)的傳輸能耗。改進(jìn)的LEACH協(xié)議更加貼近于實(shí)際應(yīng)用場(chǎng)景，同時(shí)具有更優(yōu)的能耗性能。仿真結(jié)果表明本文提出的方法在提升網(wǎng)絡(luò)生存時(shí)間和覆蓋率等方面的優(yōu)勢(shì)。

參考文獻(xiàn)：

[1]Akyildiz I F, SU W, Cayirci E. A Survey on Sensor Networks[J]. Communications Magazine IEEE,2002,40(8):102-114.

[2]Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]// Proceedings of the 33rd Hawaii International Conference on System Sciences,Hawaii:IEEE Press,2000:8020.

[3]Manjeshwar A, Agrawal D P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[J]. Proc Ipdps Workshops,2001:2009-2015.

[4]白永祥. 一種LEACH路由協(xié)議算法的改進(jìn)與分析[J]. 通信技術(shù): 2015, 48(09):1062-1067.

BAI Yong-xiang. Improvement and Analysis of LEACH Routing Protocol Algorithm. Communications Technology: 2015, 48(09):1062-1067.

[5]Heinzelman W B, Chandrakasan A P, Balakrishnan H. AnApplication-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.

[6]Tripathi M, Gaur M S, Laxmi V, et al. Energy Efficient LEACH-C Protocol for Wireless Sensor Network[C]// The 3rd International Conference on Computational Intelligence and Information Technology. CIIT 2013: IET Press, 2013:402-405.

[7]Kulik J, Heinzelman W, Balakrishnan H. Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks[J]. Wireless Networks, 1999, 8(2/3):169-185.

[8]Gagarin A, Hussain S, YANG L T. Distributed Hierarchical Search for Balanced Energy Consumption Routing Spanning Trees in Wireless Sensor Networks [J]. Journal of Parallel & Distributed Computing, 2010, 70(9):975-982.

[9]Chang R Y,Chung W H. Best-First Tree Search with Probabilistic Node Ordering for MIMO Detection: Generalization and Performance-Complexity Tradeoff[J]. IEEE Transactions on Wireless Communications,2012,11(2):780-789.

[10]GUidoni D L,Boukerche A,Villas L A, et al. A Tree-based Approach to Design Heterogeneous Sensor Networks Based on Small World Concepts[C]// The 36th Conference on Local Computer Networks (LCN 2011). Bonn:IEEE,2011:666-672.

[11]王王春. 無線傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)與仿真[D].成都：電子科技大學(xué), 2004.

WANG Chun. Design and Simulation of Routing Protocol for Wireless Sensor Networks[D]. University of Electronic Science and Technology of China,2004.

[12]LIU K J R. Cooperative Communications and Networking[M]. Cambridge:Cambridge University Press,2009.

[13]CHENG P, CAI C N, LIU X. Energy-Aware Node Placement in Wireless Sensor Networks[C]//Global Telecommunications Conference, 2004. Dallas: IEEE Press, 2004: 3210-3214.

[14]ZHANG J, SONG C, Sharif H, et al. A Battery-Aware Deployment Scheme for Cooperative Wireless Sensor Networks[C]// Global Telecommunications Conference, 2009. Hawaii: IEEE Press, 2009:1-5.

[15]IShizuka M, Aida M. Performance Study of Node Placement in Sensor Networks[C]// International Conference on Distributed Computing Systems Workshops, 2004. Tokyo: IEEE Press, 2004: 598-603.

Modified LEACH Protocol based on Ant Colony Optimization and Energy Balance

ZHOU Zhi-yong1，CHEN Hui2，WANG Hai-tao2，WANG Shi-jie1

(1.Institute of Communications Engineering;2.Department of Training, PLA University of Science and Technology,Nanjing Jiangsu 210007,China )

Abstract：Under the scenario of distributed wireless sensor networks, and in combination with the traditional LEACH protocol, an ACO(Ant Colony Optimization) routing algorithm based on limited channel information is proposed. This algorithm,with only a limited neighbor channel information required for each node, and no need for global information,could generally approach the optimal route. In light of this, a route transmit scheme based on load balance is suggested, which could effectively solve the problem of energy consumption unbalance of between the cluster heads in LEACH. Simulation experiments show that the modified routing algorithm based on ACO and energy balance could search for the optimal route in a high speed with local message, and in addition, could effectively balance the energy consumption of between the cluster heads,and prolong the network lifetime.

Key words：network lifetime; LEACH protocol; ant colony optimization; energy balance

doi:10.3969/j.issn.1002-0802.2016.04.013

*收稿日期：2015-11-09；修回日期：2016-02-20Received date:2015-11-09；Revised date：2016-02-20

基金項(xiàng)目：國(guó)家自然科學(xué)基金(No.61301157)

Foundation Item:National Natural Science Foundation of China (No.61301157)

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

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1002-0802(2016)04-0446-06

作者簡(jiǎn)介：

周智勇(1990—)，男，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)信息系統(tǒng)工程；

陳暉(1974—)，男，教授，主要研究方向?yàn)榫W(wǎng)絡(luò)信息系統(tǒng)工程；

王海濤(1976—)，男，副教授，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用；

王世界(1990—)，男，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)信息系統(tǒng)工程。