基于蟻群優化的無線傳感器網絡路由算法*

趙麗萍

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

計算與測試

基于蟻群優化的無線傳感器網絡路由算法*

趙麗萍

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

如何在資源受限的無線傳感器網絡中進行高效的數據路由是無線傳感器網絡研究的熱點之一。基于群智能優化技術的蟻群優化算法被廣泛應用于網絡路由算法。提出一種無線傳感器網絡蟻群優化路由算法，能夠保持網絡的生存時間最長，同時能找到從源節點到基站節點的最短路徑；采用的多路數據傳輸也可提供高效可靠的數據傳輸，同時考慮節點的能量水平。仿真結果表明：提出的算法延長了無線傳感器網絡的壽命，實現無線傳感器網絡在通信過程中快速、節能的路由。

無線傳感器網絡; 網絡路由； 蟻群優化; 路由算法

0 引 言

由于低功耗無線通信、低功耗模擬和數字電子技術的發展，開發低成本、低功耗、體積小的傳感器節點已受到越來越多的關注[1]。無線傳感器網絡應用于各種領域如環境檢測、健康監測、車輛跟蹤系統、軍事偵察和地震觀察等，但其也存在一些限制，如有限的節點能量、有限的計算能力和通信能力等[2]。

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

1 提供的路由方案

無線傳感器網絡路由主要考慮的問題包括穩定、有限的移動節點和基站節點[4]。為了實現高效、強壯的路由操作，主要考慮無線傳感器網絡的路由算法。

第一，相比傳統的網絡，無線傳感器網絡中通信節點失效的概率更高[5]。為了保證正常的網絡路由多采用自適應結構；同時為了保證數據的完整性，采用信號確認機制。

第二，無線傳感器網絡的節點有嚴格的能量約束，節點間的通信會消耗較多的能量。節點的能量水平也被視為路徑長度，數據的傳輸選擇能量較高的節點。

第三，無線傳感器網絡中的無線鏈路的帶寬是有限的，所以數據傳輸時，本文使用螞蟻代理通信技術。

第四，節點的移動性，即在一些特定的無線傳感器網絡的應用中允許節點的移動[6]。為了保證網絡運行的安全性，算法通過路徑的重組來實現，數據包的傳輸會隨著時間增長不斷地探索新路徑。

1.1 蟻群優化路由

在蟻群優化(ant colony optimization,ACO)的方法中，每只螞蟻試圖找到網絡中最低成本的路徑。螞蟻從源節點s出發，通過鄰居中繼節點ri，最終到達基站d。當一個節點的數據被傳送到基站，螞蟻開始發射。發射后，根據概率決策規則(1)選擇下一個節點r

(1)

其中,[τ(r,s)]為信息素濃度，η(r,s)為與能量相關的啟發值，tabur為之前接收的數據包的標識列表，α和β為控制信息素和啟發式值的2個參數。節點r的啟發值由公式(2)表示

(2)

其中，I為最初的能量，er為接收節點r的當前能源。這樣可根據鄰居節點的能量決定下一個節點，能量較低的節點被選中的概率也較低。如果檢測到能量值發生變化，節點會通知鄰居節點。

在傳統蟻群算法，螞蟻需建立特殊的內存Mk記錄訪問過的節點。在公式(1)中，訪問過的節點標識被保存在節點內存中，所以,在數據傳輸過程中不需要傳輸Mk列表數據。這種方法降低了數據的大小，并且節省了能量。在公式(1)中，每個接收節點檢查tabu列表決定是否接收到來的螞蟻k。接收節點r若較早接收完數據包，它會發送消息給發送節點，同時將自己轉變為空閑模式，直到新的數據包的到來。

當所有螞蟻找到路徑結束后，每個螞蟻k會釋放信息素Δτk(t)，其計算如下

(3)

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

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

(4)

信息素值保存在節點內存中，每個節點都有其鄰居節點的信息素值。在每次路徑尋優過程中，螞蟻k會從基站沿原路返回源節點，釋放信息素量Δτk(t)，同時也會傳輸確認信號。隨著路徑的不斷增長，信息素量不斷增加，Jw(t)將產生正反饋。為了便于控制，信息素量按照公式(5)蒸發

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

(5)

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

1.2 數據傳輸

包含事件信息的源節點將事件通過鄰居節點的傳輸最終發送到基站。相關的數據被分成N片，稱為數據包，N也表示在每條路由任務中包含的代理螞蟻數。

由源節點發送的事件數據稱為原始數據，原始數據包括了源節點標識、事件標識、時間以及相關的事件數據。原始數據被分成N片，如圖1所示。每個數據包的大小由WSNs通信芯片的緩沖區大小決定。

圖1 原始數據分段Fig 1 Segment of original datas

圖2 數據包Fig 2 Data packets

確定劃分的數據包的大小非常重要，因為螞蟻數與數據包數是相同的。數據包的大小是在系統初始化時根據事件數據的平均大小和硬件特性決定的。若數據包含了MAC幀，數據包的大小需滿足MAC最小值。在仿真實驗中，數據包大小設置為1 Mb。

1.3 確認機制

數據從源節點傳輸到下一鄰居節點后，基站通過不同的路徑接收到數據包。選擇不同路徑是為了保證可靠的傳輸，避免統治地位路由的癱瘓。同時，為了避免數據包的丟失，采用確認機制。在收到一個數據包后，基站根據公式(3)計算Δτk值，形成確認包如圖3，并通過相同的路徑廣播到源節點，如圖4。

圖3 確認信號Fig 3 Signal confirmation

圖4 確認信號傳輸Fig 4 Confirmation of signal transmission

節點接收到確認包后，檢查S_N值。如果在節點內存中找到該值，則該信號被廣播到路徑中的其他節點，同時該節點通過公式(4)更新信息素值；如果沒找到該值，則丟棄該信號，不做任何操作；若源節點沒收到確認信號，則重發數據包。

1.4 鄰居節點的能量參數

公式(1)需要鄰居節點的能量參數，所以,每個節點需要告訴其鄰居節點自己的能量參數。當檢測到能量參數發生改變，節點進行廣播。節點在監聽或傳輸數據后，能量參數會發生改變，所以,在傳輸數據后能量狀態的改變可立即檢測到。

2 仿真與分析

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

圖6顯示了在不同節點數的無線傳感器網絡中，256個數據包到達匯聚節點的歸一化平均剩余能量。從圖中可以看出:隨著網絡中節點數的增加，能量水平的差異增大到10 %。

圖6 接收256個數據包的平均剩余能量Fig 6 Average residual energy of recieved 256 data packets

3 結束語

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

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

[2] 梁華為，陳萬明.一種無線傳感器網絡蟻群優化路由算法[J].傳感技術學報，2007,20(11)：2450-2455.

[3] 朱思峰，劉 方，柴爭義．一種基于蟻群優化的無線傳感器網絡路由算法[J]． 北京理工大學學報，2010，30(11):1295-1300.

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

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

[6] 尚興宏，錢煥延，高德民.基于改進蟻群優化算法的無線傳感器網絡路由研究[J].傳感器與微系統,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

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

TP 393

A

1000—9787(2014)04—0112—03

趙麗萍(1981-)，女，山西朔州人，碩士，講師，研究方向為無線傳感器網絡路由技術。