基于蟻群算法的無(wú)線傳感網(wǎng)路由協(xié)議的應(yīng)用研究

崔慶華，王兆龍，聶宗瑤

(1.安徽城市管理職業(yè)學(xué)院 院辦,安徽 合肥 230011; 2. 安徽城市管理職業(yè)學(xué)院 城市建設(shè)系,安徽 合肥 230011)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network)是可以做到實(shí)時(shí)通信和計(jì)算，并且是由很多非常小的節(jié)點(diǎn)組成的一種分散式的無(wú)線網(wǎng)絡(luò)[1]。隨著物聯(lián)網(wǎng)的普及，無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的越來(lái)越廣泛，目前能夠應(yīng)用于入侵檢測(cè)、環(huán)境檢測(cè)、醫(yī)療衛(wèi)生及軍事等眾多領(lǐng)域。盡管具有廣泛的應(yīng)用前景，但是數(shù)據(jù)在傳輸中的安全性、節(jié)點(diǎn)的能耗及抗干擾等問(wèn)題亟待解決。為了提高數(shù)據(jù)在無(wú)線傳感網(wǎng)中傳輸?shù)挠行院蛯?shí)時(shí)性，本文在學(xué)習(xí)相關(guān)算法的基礎(chǔ)上，提出改進(jìn)的基于蟻群算法的無(wú)線傳感網(wǎng)路由協(xié)議，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證本文提出的算法。

1 基于蟻群算法的無(wú)線傳感網(wǎng)路由協(xié)議

1.1 蟻群算法原理

仿生學(xué)家通過(guò)大量的實(shí)驗(yàn)研究發(fā)現(xiàn)，螞蟻之所以能找到一條最短路徑源于螞蟻在行進(jìn)過(guò)程中會(huì)釋放一種叫做“信息素(Pheromone)”的物質(zhì)[2]，蟻群中的螞蟻之間通過(guò)信息素傳遞信息[3]。學(xué)者們從螞蟻尋覓食物源的行為過(guò)程得到了一種啟示，即將螞蟻整個(gè)覓食的過(guò)程抽象成一種路由算法并應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)中去。因此，蟻群算法(Ant Colony Algorithm)是模仿自然界中螞蟻的運(yùn)動(dòng)行為，是一種仿生物的智能算法[4]。

1.2 蟻群算法的實(shí)現(xiàn)過(guò)程

傳統(tǒng)蟻群算法的具體實(shí)現(xiàn)過(guò)程如下：

(1)首先假定有x只螞蟻不定時(shí)的從洞穴出發(fā)尋找食物。

(2)當(dāng)螞蟻在選擇的路徑往返時(shí)，會(huì)在經(jīng)過(guò)的足跡中留下信息素標(biāo)志。在螞蟻未出洞之前，假定各條路徑上的信息素強(qiáng)度一樣都為τm,n(0)= C，C為常數(shù)。同時(shí)設(shè)定任意時(shí)刻在路徑(m，n)上殘留的信息素強(qiáng)度與時(shí)間點(diǎn)的關(guān)系為τm,n(t)。

(3)當(dāng)螞蟻從洞穴出發(fā)尋找食物時(shí)，會(huì)先判斷它可走的各條路徑上信息素強(qiáng)度[5]，根據(jù)信息素強(qiáng)度來(lái)選擇運(yùn)動(dòng)方向，由此定義出轉(zhuǎn)移概率公式為：

(1)

當(dāng)螞蟻尋找到食物后，可以按原路返回，在返回的過(guò)程中按式(2)調(diào)節(jié)路徑上的信息素。如式(3)所示。

(2)

(3)

2 改進(jìn)的基于蟻群算法的無(wú)線傳感網(wǎng)路由協(xié)議

由于無(wú)線傳感網(wǎng)中存在節(jié)點(diǎn)能耗、多跳數(shù)據(jù)傳輸?shù)葐?wèn)題，所以在傳統(tǒng)的蟻群算法基礎(chǔ)上提出一種改進(jìn)的路由算法——按需多路節(jié)能路由算法[6]，該算法結(jié)合了傳統(tǒng)蟻群算法、MACO算法及AODV路由協(xié)議的優(yōu)點(diǎn)，在移動(dòng)的螞蟻身上增加一些新的特性，重新設(shè)置路徑搜索規(guī)則[7]。該算法在傳統(tǒng)蟻群算法的基礎(chǔ)上主要做了兩方面的改變：

(1)前向螞蟻轉(zhuǎn)移規(guī)則

(4)

在式(4)中，θ(m,n)k是一個(gè)運(yùn)算因子，是指第k只螞蟻所在節(jié)點(diǎn)m和節(jié)點(diǎn)n之間的信息素強(qiáng)度與下一節(jié)點(diǎn)剩余能量的運(yùn)算因子[8]，通常用式(5)來(lái)計(jì)算。

(5)

(2)信息素更新規(guī)則

通常前向螞蟻k抉擇一條路徑上的相鄰節(jié)點(diǎn)m，n，當(dāng)?shù)竭_(dá)目的節(jié)點(diǎn)時(shí)通過(guò)以下的前兩個(gè)式子來(lái)調(diào)節(jié)信息素強(qiáng)度。如果每個(gè)螞蟻到達(dá)目的地之后馬上回到開(kāi)始的地方，在這之中它會(huì)一直沿著反向信息素回到始發(fā)點(diǎn)。兩頭中的節(jié)點(diǎn)收到后向螞蟻時(shí)，將根據(jù)式(6)和式(8)更新信息素強(qiáng)度。

(6)

前向螞蟻信息素增量公式：

(7)

后向螞蟻信息增量公式：

(8)

式(7)中，En是節(jié)點(diǎn)n的當(dāng)前能量；Δτk(m,n)表示第k只螞蟻留在路徑(m,n)上的信息素強(qiáng)度；式(8)中，h是尋找到的路徑的總跳數(shù)；E為前向螞蟻搜索到路徑上的總能量。

該算法的核心就是將下一跳節(jié)點(diǎn)的剩余能量作為影響信息素的一個(gè)因素，以此來(lái)改變轉(zhuǎn)移概率值，同時(shí)限定每條可能路徑上的信息素最大值τmax和最小值τmin，最大值τmax是避免該路徑上螞蟻過(guò)多，限定擴(kuò)散范圍；最小值τmin避免算法停滯。

3 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)采用MATLAB軟件將改進(jìn)的蟻群算法和傳統(tǒng)的蟻群算法進(jìn)行了仿真對(duì)比。在300*300的范圍內(nèi)，我們隨機(jī)選取若干節(jié)點(diǎn)，分別計(jì)算第1,5,10,15,20,25,30,35,40,45,50個(gè)死亡節(jié)點(diǎn)所經(jīng)歷的周期數(shù)及50，100,150,200個(gè)節(jié)點(diǎn)的平均能耗，并且每次傳輸實(shí)現(xiàn)數(shù)據(jù)融合，這里假設(shè)所有的傳輸節(jié)點(diǎn)都是4000bit數(shù)據(jù)，基站位于(100,200)，初始能量是Q=0.6J。具體仿真實(shí)驗(yàn)結(jié)果及分析如下：

(1)節(jié)點(diǎn)生存期比較

圖1 節(jié)點(diǎn)生存期比較圖

從圖1中可以看出，改進(jìn)的蟻群算法中選取節(jié)點(diǎn)的生存期比傳統(tǒng)的蟻群算法的節(jié)點(diǎn)的生存期都高，在有限的條件下盡可能保證網(wǎng)絡(luò)的暢通，同時(shí)也不需要因?yàn)楣?jié)點(diǎn)的減少而頻繁的更新路由表信息，延長(zhǎng)網(wǎng)絡(luò)的生命周期，提高了網(wǎng)絡(luò)的利用率。

(2)平均能耗比較

圖2 平均能耗比較圖

從圖2中可以看出，在50到200個(gè)節(jié)點(diǎn)中，改進(jìn)的蟻群算法平均能耗低于傳統(tǒng)蟻群算法的平均能耗，同時(shí)隨著節(jié)點(diǎn)數(shù)目增加，改進(jìn)的蟻群算法與傳統(tǒng)蟻群算法之間的平均能耗差越來(lái)越大，當(dāng)節(jié)點(diǎn)數(shù)目較多時(shí)，改進(jìn)蟻群算法全局能量均衡提高約50%，同時(shí)也使網(wǎng)絡(luò)能耗做到了均衡，最終整個(gè)網(wǎng)絡(luò)周期延長(zhǎng)了。

4 結(jié) 論

本文是在傳統(tǒng)蟻群算法的基礎(chǔ)上加以改進(jìn)，能夠做到將網(wǎng)絡(luò)生命周期與路由收斂速度的最佳平衡點(diǎn)找出來(lái)，從而提高了無(wú)線傳感網(wǎng)數(shù)據(jù)傳輸效率，延長(zhǎng)了網(wǎng)絡(luò)生命周期。因此，該算法在當(dāng)前物聯(lián)網(wǎng)的實(shí)際應(yīng)用中具有一定的實(shí)用價(jià)值。