基于蟻群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )路由算法

隨著(zhù)無(wú)線(xiàn)通信技術(shù)、電子技術(shù)、傳感器技術(shù)和微電系統的飛速發(fā)展，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的研究越來(lái)越受到人們的重視。傳感器網(wǎng)絡(luò )是由部署在觀(guān)測環(huán)境內的大量微型傳感器節點(diǎn)通過(guò)無(wú)線(xiàn)通信方式組成的一種無(wú)線(xiàn)網(wǎng)絡(luò )。

組成傳感器網(wǎng)絡(luò )的節點(diǎn)包括傳感器和匯聚節點(diǎn)(Sink)。傳感器節點(diǎn)的能量十分有限，并且在部署后難以再次補充能量，因此傳感器網(wǎng)絡(luò )存在嚴重的能量約束問(wèn)題[1]。

參考文獻[2]提出一種無(wú)線(xiàn)傳感器網(wǎng)絡(luò )AODV(AdhocOn-DernandDistanceVector)路由協(xié)議改進(jìn)方案，通過(guò)改進(jìn)RREQ協(xié)議幀，使節點(diǎn)的剩余能量值參與到路徑中，優(yōu)化RREQ洪泛傳播。但該算法是基于單路徑數據傳輸，沒(méi)有考慮節點(diǎn)的負載狀況，節點(diǎn)容易產(chǎn)生擁塞，導致數據包的重傳或數據丟失的情況。

參考文獻[3]提出了一種基于蟻群優(yōu)化的路由算法ARAWSN(ACO-BasedRoutingAlgorithmforWirelessSensorNetworks)，該算法在定向擴散協(xié)議的基礎上，通過(guò)搜尋螞蟻以廣播的方式在網(wǎng)絡(luò )中擴散建立起源節點(diǎn)到目的節點(diǎn)的多條路徑的路由表。

利用蟻群算法的轉移概率的方式來(lái)進(jìn)行路徑的選擇，從而平衡網(wǎng)絡(luò )中節點(diǎn)能量的消耗。該算法建立了所有到目的節點(diǎn)的路徑，存在很大的冗余，影響網(wǎng)絡(luò )的實(shí)時(shí)性，且在路由建立過(guò)程中采用洪泛的方式導致網(wǎng)絡(luò )的路由開(kāi)銷(xiāo)比較大。

參考文獻[4]綜合考慮了均衡傳輸能量消耗和節點(diǎn)剩余能量，提出了多種群蟻群優(yōu)化路由算法MACO(MultiAntColonyOptimization)。該算法優(yōu)化了基本蟻群算法的螞蟻前向移動(dòng)的選擇概率模型，同時(shí)利用多種群獲得多條優(yōu)化路徑。但該算法需要進(jìn)行多次迭代，且可能陷入局部最優(yōu)解，影響網(wǎng)絡(luò )數據傳輸的實(shí)時(shí)性。

針對上述路由算法及其存在的不足，本文提出了基于蟻群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )按需多路節能路由算法MP-ACA(On-demandMulti-pathandPower-savingAntColonyAlgorithm)。該算法結合蟻群算法和AODV路由協(xié)議，能夠在源節點(diǎn)和目的節點(diǎn)之間建立起多條鏈路不相關(guān)路由，并改善了蟻群算法在無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中查找路由的多次迭代的策略，有效地減少了擁塞頻率、降低了路由的開(kāi)銷(xiāo)，同時(shí)均衡了節點(diǎn)的能量開(kāi)銷(xiāo)，延長(cháng)了網(wǎng)絡(luò )的生命周期。

1 蟻群算法簡(jiǎn)介

1.1 基本蟻群算法原理

蟻群算法[5]ACA(AntColonyAlgorithm)是一種模擬昆蟲(chóng)王國中螞蟻群體智能行為的仿生優(yōu)化算法，其基本原理可大致描述如下:自然界螞蟻會(huì )在所經(jīng)過(guò)的路徑上釋放一定的信息素，后來(lái)的螞蟻會(huì )根據信息素強度來(lái)選擇路徑，信息素強度越大的路徑被選擇的概率越大，于是就形成了一種正反饋機制，最終螞蟻會(huì )選擇信息素最大的最短路徑。蟻群算法通過(guò)釋放“人工螞蟻”來(lái)模擬自然螞蟻的行為以完成上述的選優(yōu)過(guò)程。

1.2 蟻群算法

根據螞蟻覓食的基本原理，科學(xué)家們設計了尋找最優(yōu)路徑的蟻群算法，其主要步驟為：

2 按需多路節能路由算法設計

針對無(wú)線(xiàn)傳感器網(wǎng)絡(luò )數據多跳傳輸、節點(diǎn)能量有限等特性，本文對基本蟻群算法和MACO算法進(jìn)行改進(jìn)，并結合AODV路由協(xié)議，賦予螞蟻新的特性和路徑搜索方式。下面介紹本文研究中使用的相關(guān)定義。

定義1：從源節點(diǎn)到目的節點(diǎn)的路徑搜索螞蟻稱(chēng)作前向螞蟻，它執行路徑搜索功能，并建立反向信息素表。

定義2：前向螞蟻到達目的節點(diǎn)后，從目的節點(diǎn)返回到源節點(diǎn)的螞蟻稱(chēng)作后向螞蟻，它執行信息素更新功能，并建立路由表。

定義3：前向螞蟻在路徑搜索過(guò)程中，到達某一節點(diǎn)后建立的指向源節點(diǎn)的路由表稱(chēng)作反向信息素表，該表包括源節點(diǎn)、下一個(gè)節點(diǎn)、反向節點(diǎn)信息素τ(j，i)。

2.1 算法設計思想

MP-ACA算法在A(yíng)nt-Net算法[6]的基礎上，將螞蟻分為前向螞蟻和后向螞蟻。為了實(shí)現不同節點(diǎn)的能量消耗均衡，MP-ACA算法中，將前向螞蟻要訪(fǎng)問(wèn)的節點(diǎn)的剩余能量作為影響信息素濃度的一個(gè)參數。MP-ACA算法通過(guò)m只前向螞蟻同時(shí)獨立地進(jìn)行路徑搜索，并建立反向信息素表。

當每個(gè)前向螞蟻到達目的節點(diǎn)時(shí)，它們將立即轉化成一個(gè)后向螞蟻，后向螞蟻根據反向信息素表反向回到源節點(diǎn)后一次路由建立完畢，建立起信息素路由表以代替傳統的網(wǎng)絡(luò )節點(diǎn)路由表，并采用一種新的信息素規則進(jìn)行信息素更新。

同時(shí)MP-ACA算法在極大-極小蟻群算法[7]上將各條路徑上的信息素濃度限制在[τmin，τmax]之間，τmin可以有效地避免算法停滯，τmax避免某條路徑上的信息素遠大于其他路徑，使所有的螞蟻都集中到同一條路徑上面，限制算法的擴散。在MP-ACA算法中，前向螞蟻轉移規則、信息素更新規則詳細設計如下。