趙麗萍

(華東交通大學(xué) 軟件學(xué)院，江西 南昌 330013)

計(jì)算與測試

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

趙麗萍

(華東交通大學(xué) 軟件學(xué)院，江西 南昌 330013)

如何在資源受限的無線傳感器網(wǎng)絡(luò)中進(jìn)行高效的數(shù)據(jù)路由是無線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)之一?；谌褐悄軆?yōu)化技術(shù)的蟻群優(yōu)化算法被廣泛應(yīng)用于網(wǎng)絡(luò)路由算法。提出一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法，能夠保持網(wǎng)絡(luò)的生存時(shí)間最長，同時(shí)能找到從源節(jié)點(diǎn)到基站節(jié)點(diǎn)的最短路徑；采用的多路數(shù)據(jù)傳輸也可提供高效可靠的數(shù)據(jù)傳輸，同時(shí)考慮節(jié)點(diǎn)的能量水平。仿真結(jié)果表明：提出的算法延長了無線傳感器網(wǎng)絡(luò)的壽命，實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)在通信過程中快速、節(jié)能的路由。

無線傳感器網(wǎng)絡(luò); 網(wǎng)絡(luò)路由； 蟻群優(yōu)化; 路由算法

0 引 言

由于低功耗無線通信、低功耗模擬和數(shù)字電子技術(shù)的發(fā)展，開發(fā)低成本、低功耗、體積小的傳感器節(jié)點(diǎn)已受到越來越多的關(guān)注[1]。無線傳感器網(wǎng)絡(luò)應(yīng)用于各種領(lǐng)域如環(huán)境檢測、健康監(jiān)測、車輛跟蹤系統(tǒng)、軍事偵察和地震觀察等，但其也存在一些限制，如有限的節(jié)點(diǎn)能量、有限的計(jì)算能力和通信能力等[2]。

為了延長無線傳感器網(wǎng)絡(luò)的壽命，路由算法中的網(wǎng)絡(luò)參數(shù)優(yōu)化被視為組合優(yōu)化問題。許多研究人員研究了生物物種(如螞蟻)的自然集體行為，從而建立組合優(yōu)化問題模型[3]。本文基于群智能優(yōu)化技術(shù)，能夠保持網(wǎng)絡(luò)的生存時(shí)間更長，同時(shí)能找到從源節(jié)點(diǎn)到基礎(chǔ)節(jié)點(diǎn)的最短路徑。采用的多路數(shù)據(jù)傳輸也可提供可靠的網(wǎng)絡(luò)操作，同時(shí)考慮節(jié)點(diǎn)的能量水平。仿真結(jié)果表明：與基于節(jié)能的螞蟻路由(EEABR)算法相比，本文方法的效果更好。

1 提供的路由方案

無線傳感器網(wǎng)絡(luò)路由主要考慮的問題包括穩(wěn)定、有限的移動(dòng)節(jié)點(diǎn)和基站節(jié)點(diǎn)[4]。為了實(shí)現(xiàn)高效、強(qiáng)壯的路由操作，主要考慮無線傳感器網(wǎng)絡(luò)的路由算法。

第一，相比傳統(tǒng)的網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)中通信節(jié)點(diǎn)失效的概率更高[5]。為了保證正常的網(wǎng)絡(luò)路由多采用自適應(yīng)結(jié)構(gòu)；同時(shí)為了保證數(shù)據(jù)的完整性，采用信號(hào)確認(rèn)機(jī)制。

第二，無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)有嚴(yán)格的能量約束，節(jié)點(diǎn)間的通信會(huì)消耗較多的能量。節(jié)點(diǎn)的能量水平也被視為路徑長度，數(shù)據(jù)的傳輸選擇能量較高的節(jié)點(diǎn)。

第三，無線傳感器網(wǎng)絡(luò)中的無線鏈路的帶寬是有限的，所以數(shù)據(jù)傳輸時(shí)，本文使用螞蟻代理通信技術(shù)。

第四，節(jié)點(diǎn)的移動(dòng)性，即在一些特定的無線傳感器網(wǎng)絡(luò)的應(yīng)用中允許節(jié)點(diǎn)的移動(dòng)[6]。為了保證網(wǎng)絡(luò)運(yùn)行的安全性，算法通過路徑的重組來實(shí)現(xiàn)，數(shù)據(jù)包的傳輸會(huì)隨著時(shí)間增長不斷地探索新路徑。

1.1 蟻群優(yōu)化路由

在蟻群優(yōu)化(ant colony optimization,ACO)的方法中，每只螞蟻試圖找到網(wǎng)絡(luò)中最低成本的路徑。螞蟻從源節(jié)點(diǎn)s出發(fā)，通過鄰居中繼節(jié)點(diǎn)ri，最終到達(dá)基站d。當(dāng)一個(gè)節(jié)點(diǎn)的數(shù)據(jù)被傳送到基站，螞蟻開始發(fā)射。發(fā)射后，根據(jù)概率決策規(guī)則(1)選擇下一個(gè)節(jié)點(diǎn)r

(1)

其中,[τ(r,s)]為信息素濃度，η(r,s)為與能量相關(guān)的啟發(fā)值，tabur為之前接收的數(shù)據(jù)包的標(biāo)識(shí)列表，α和β為控制信息素和啟發(fā)式值的2個(gè)參數(shù)。節(jié)點(diǎn)r的啟發(fā)值由公式(2)表示

(2)

其中，I為最初的能量，er為接收節(jié)點(diǎn)r的當(dāng)前能源。這樣可根據(jù)鄰居節(jié)點(diǎn)的能量決定下一個(gè)節(jié)點(diǎn)，能量較低的節(jié)點(diǎn)被選中的概率也較低。如果檢測到能量值發(fā)生變化，節(jié)點(diǎn)會(huì)通知鄰居節(jié)點(diǎn)。

在傳統(tǒng)蟻群算法，螞蟻需建立特殊的內(nèi)存Mk記錄訪問過的節(jié)點(diǎn)。在公式(1)中，訪問過的節(jié)點(diǎn)標(biāo)識(shí)被保存在節(jié)點(diǎn)內(nèi)存中，所以,在數(shù)據(jù)傳輸過程中不需要傳輸Mk列表數(shù)據(jù)。這種方法降低了數(shù)據(jù)的大小，并且節(jié)省了能量。在公式(1)中，每個(gè)接收節(jié)點(diǎn)檢查tabu列表決定是否接收到來的螞蟻k。接收節(jié)點(diǎn)r若較早接收完數(shù)據(jù)包，它會(huì)發(fā)送消息給發(fā)送節(jié)點(diǎn)，同時(shí)將自己轉(zhuǎn)變?yōu)榭臻e模式，直到新的數(shù)據(jù)包的到來。

當(dāng)所有螞蟻找到路徑結(jié)束后，每個(gè)螞蟻k會(huì)釋放信息素Δτk(t)，其計(jì)算如下

(3)

τ(r,s)(t)←τ(r,s)(t)+Δτ(r,s)(t),

?l(r,s)∈wk(t)，k=1,…,m.

(4)

信息素值保存在節(jié)點(diǎn)內(nèi)存中，每個(gè)節(jié)點(diǎn)都有其鄰居節(jié)點(diǎn)的信息素值。在每次路徑尋優(yōu)過程中，螞蟻k會(huì)從基站沿原路返回源節(jié)點(diǎn)，釋放信息素量Δτk(t)，同時(shí)也會(huì)傳輸確認(rèn)信號(hào)。隨著路徑的不斷增長，信息素量不斷增加，Jw(t)將產(chǎn)生正反饋。為了便于控制，信息素量按照公式(5)蒸發(fā)

τi,j(t)←(1-ρ)τi,j(t).

(5)

其中，控制系數(shù)ρ∈(0,1)決定每次傳輸蒸發(fā)的量值。

1.2 數(shù)據(jù)傳輸

包含事件信息的源節(jié)點(diǎn)將事件通過鄰居節(jié)點(diǎn)的傳輸最終發(fā)送到基站。相關(guān)的數(shù)據(jù)被分成N片，稱為數(shù)據(jù)包，N也表示在每條路由任務(wù)中包含的代理螞蟻數(shù)。

由源節(jié)點(diǎn)發(fā)送的事件數(shù)據(jù)稱為原始數(shù)據(jù)，原始數(shù)據(jù)包括了源節(jié)點(diǎn)標(biāo)識(shí)、事件標(biāo)識(shí)、時(shí)間以及相關(guān)的事件數(shù)據(jù)。原始數(shù)據(jù)被分成N片，如圖1所示。每個(gè)數(shù)據(jù)包的大小由WSNs通信芯片的緩沖區(qū)大小決定。

圖1 原始數(shù)據(jù)分段Fig 1 Segment of original datas

圖2 數(shù)據(jù)包Fig 2 Data packets

確定劃分的數(shù)據(jù)包的大小非常重要，因?yàn)槲浵仈?shù)與數(shù)據(jù)包數(shù)是相同的。數(shù)據(jù)包的大小是在系統(tǒng)初始化時(shí)根據(jù)事件數(shù)據(jù)的平均大小和硬件特性決定的。若數(shù)據(jù)包含了MAC幀，數(shù)據(jù)包的大小需滿足MAC最小值。在仿真實(shí)驗(yàn)中，數(shù)據(jù)包大小設(shè)置為1 Mb。

1.3 確認(rèn)機(jī)制

數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)较乱秽従庸?jié)點(diǎn)后，基站通過不同的路徑接收到數(shù)據(jù)包。選擇不同路徑是為了保證可靠的傳輸，避免統(tǒng)治地位路由的癱瘓。同時(shí)，為了避免數(shù)據(jù)包的丟失，采用確認(rèn)機(jī)制。在收到一個(gè)數(shù)據(jù)包后，基站根據(jù)公式(3)計(jì)算Δτk值，形成確認(rèn)包如圖3，并通過相同的路徑廣播到源節(jié)點(diǎn)，如圖4。

圖3 確認(rèn)信號(hào)Fig 3 Signal confirmation

圖4 確認(rèn)信號(hào)傳輸Fig 4 Confirmation of signal transmission

節(jié)點(diǎn)接收到確認(rèn)包后，檢查S_N值。如果在節(jié)點(diǎn)內(nèi)存中找到該值，則該信號(hào)被廣播到路徑中的其他節(jié)點(diǎn)，同時(shí)該節(jié)點(diǎn)通過公式(4)更新信息素值；如果沒找到該值，則丟棄該信號(hào)，不做任何操作；若源節(jié)點(diǎn)沒收到確認(rèn)信號(hào)，則重發(fā)數(shù)據(jù)包。

1.4 鄰居節(jié)點(diǎn)的能量參數(shù)

公式(1)需要鄰居節(jié)點(diǎn)的能量參數(shù)，所以,每個(gè)節(jié)點(diǎn)需要告訴其鄰居節(jié)點(diǎn)自己的能量參數(shù)。當(dāng)檢測到能量參數(shù)發(fā)生改變，節(jié)點(diǎn)進(jìn)行廣播。節(jié)點(diǎn)在監(jiān)聽或傳輸數(shù)據(jù)后，能量參數(shù)會(huì)發(fā)生改變，所以,在傳輸數(shù)據(jù)后能量狀態(tài)的改變可立即檢測到。

2 仿真與分析

為了驗(yàn)證所提出的方法的成功，與EEABR算法進(jìn)行比較[7]。模擬環(huán)境設(shè)置為：傳感器隨機(jī)部署在200 m×200 m(10個(gè)節(jié)點(diǎn))，300 m×300 m(20個(gè)節(jié)點(diǎn))，400 m×400 m(30個(gè)節(jié)點(diǎn))，500 m×500 m(40個(gè)節(jié)點(diǎn))和600 m×600 m(50,60,70,80和100個(gè)節(jié)點(diǎn))區(qū)域內(nèi)監(jiān)控靜態(tài)事件，事件和匯聚節(jié)點(diǎn)的位置事先未知。參數(shù)設(shè)置為：參數(shù)α=1，β=5，ρ=0.5。在該方案中，事件附近的節(jié)點(diǎn)將相關(guān)數(shù)據(jù)通過鄰居節(jié)點(diǎn)發(fā)送到匯聚節(jié)點(diǎn)，同時(shí)計(jì)算能量的消耗。隨著匯聚節(jié)點(diǎn)數(shù)據(jù)包的增加，節(jié)點(diǎn)的平均剩余能量不斷降低，如圖5所示。在模擬中，所提出的方法給出了更好的結(jié)果，提供更長的網(wǎng)絡(luò)壽命和消耗更少的能量，尤其是對(duì)高密度網(wǎng)絡(luò)。

圖6顯示了在不同節(jié)點(diǎn)數(shù)的無線傳感器網(wǎng)絡(luò)中，256個(gè)數(shù)據(jù)包到達(dá)匯聚節(jié)點(diǎn)的歸一化平均剩余能量。從圖中可以看出:隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加，能量水平的差異增大到10 %。

圖6 接收256個(gè)數(shù)據(jù)包的平均剩余能量Fig 6 Average residual energy of recieved 256 data packets

3 結(jié)束語

本文提出的無線傳感器網(wǎng)絡(luò)路由協(xié)議基于ACO算法，提供了一種在節(jié)點(diǎn)故障情況下的多路徑數(shù)據(jù)傳輸方式，實(shí)現(xiàn)了可靠的通信，保持網(wǎng)絡(luò)生命時(shí)間最長，同時(shí)能高效地實(shí)現(xiàn)數(shù)據(jù)的傳輸。仿真結(jié)果表明:與基于事件的模擬器蟻群算法EEABR相比，本文所提的方法在網(wǎng)絡(luò)平均能量消耗方面有顯著的改善。

[1] 張海娟,付爭方.基于蟻群的無線傳感器網(wǎng)絡(luò)路由算法[J].傳感器與微系統(tǒng),2010,20(1):84-86.

[2] 梁華為，陳萬明.一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法[J].傳感技術(shù)學(xué)報(bào)，2007,20(11)：2450-2455.

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

[4] Dorigo M，Stutzle T． Ant colony optimization [M]．Cambridge:The MIT Press，2006:71-83．

[5] 鄭 巍，劉三陽，寇曉麗．基于蟻群策略的無線傳感器網(wǎng)絡(luò)能量有效路由算法[J]．系統(tǒng)工程與電子技術(shù)，2009，31(8):1993-1996．

[6] 尚興宏，錢煥延，高德民.基于改進(jìn)蟻群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)路由研究[J].傳感器與微系統(tǒng),2012,31(9):36-38.

[7] Camilo T,Carreto C,Silva J,et al.An energy-efficient ant base routing algorithm for wireless sensor networks[C]∥Fifth International Workshop on Ant Colony Optimization and Swarm Intelligence,ANTS 2006，2006:49-59.．

ACO-based routing algorithm for WSNs*

ZHAO Li-ping

(School of Software，East China Jiaotong University，Nanchang 330013，China)

How to get high-efficient data routing for the limited energy resource networks is one of the hot spot in the study of wireless sensor networks(WSNs).Ant colony optimization(ACO) algorithm, a swarm intelligence-based optimization technique,is widely used in network routing.Present a WSNs ACO routing algorithm,which can maintain network lifetime to be longest,while discovering the shortest paths from source nodes to base station node;multi-path data transmission can also provide high-efficient reliable network operations,while considering energy levels of nodes simultaneously.Simulation results show that this proposed algorithm prolongs lifetime of WSNs and fast and energy-efficient routing of WSNs in communication process is realized.

wireless sensor networks(WSNs); network routing; ant colony optimization(ACO); routing algorithm

2013—10—15

國家自然科學(xué)基金資助項(xiàng)目(61162001)；華東交通大學(xué)校立科研基金資助項(xiàng)目(10RJ04)

TP 393

A

1000—9787(2014)04—0112—03

趙麗萍(1981-)，女，山西朔州人，碩士，講師，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)路由技術(shù)。