王 鎮(zhèn)，劉學(xué)軍

(南京工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，南京 210009)

隨著傳感器網(wǎng)絡(luò)規(guī)模的指數(shù)增長(zhǎng)使得一些網(wǎng)絡(luò)動(dòng)態(tài)特性更加突出，因此需要數(shù)據(jù)傳輸路徑能夠隨著網(wǎng)絡(luò)結(jié)構(gòu)的變化而自適應(yīng)地改變。傳統(tǒng)的路由算法已經(jīng)不能適應(yīng)這種情況的需求，為解決傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)據(jù)擁塞、傳輸延時(shí)、能量消耗過大等問題，必須提出更為有效的QoS路由算法，一方面要路徑盡量短，以滿足實(shí)用性;另一方面又要避開負(fù)載較重的鏈路，保持網(wǎng)絡(luò)負(fù)載分布的平衡性。

蟻群算法是一種基于種群的模擬進(jìn)化算法，主要是通過螞蟻覓食過程中群體之間的信息傳遞而達(dá)到尋優(yōu)的目的，其原理是一種正反饋機(jī)制，通過信息素的不斷更新達(dá)到最終收斂于最優(yōu)路徑上的目的，同時(shí)算法具有隨機(jī)自適應(yīng)性、全局優(yōu)化和分布式等特點(diǎn)。蟻群算法的隨機(jī)自適應(yīng)性使得它很適合應(yīng)用于無線傳感器網(wǎng)絡(luò)環(huán)境中［1－2］，所以將蟻群算法應(yīng)用于無線傳感器網(wǎng)絡(luò)中的QoS(Quality of Service)研究有著重要的意義。

1 相關(guān)工作

AntNet［3］是將蟻群優(yōu)化算法應(yīng)用于網(wǎng)絡(luò)路由問題的經(jīng)典算法。在AntNet中，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)路由表和一個(gè)網(wǎng)絡(luò)狀態(tài)表，路由表中記錄著該節(jié)點(diǎn)到達(dá)下一個(gè)目的節(jié)點(diǎn)的所有下一跳的信息素強(qiáng)度，數(shù)據(jù)包將根據(jù)信息素強(qiáng)度計(jì)算下一跳的選擇路徑。AntNet中使用了前向螞蟻(Forward ant)和后向螞蟻(Backward ant)兩種移動(dòng)代理。前向螞蟻根據(jù)路由表信息，采用啟發(fā)式算法尋找到達(dá)目的節(jié)點(diǎn)的路徑，并收集路徑上的網(wǎng)絡(luò)狀態(tài)，前向螞蟻到達(dá)目的節(jié)點(diǎn)后即消亡，同時(shí)產(chǎn)生后向螞蟻沿原路返回，并更新所經(jīng)過的節(jié)點(diǎn)的路由表。文獻(xiàn)［4］對(duì)AntNet路由的性能進(jìn)行了分析，并對(duì)AntNet與Dijkstra進(jìn)行了比較，仿真結(jié)果表明兩者性能相近，但在通信量較大的網(wǎng)絡(luò)中，AntNet優(yōu)于 Dijkstra算法。文獻(xiàn)［5］中，提出了EEABR算法，算法的核心思想是參考路徑中的能量改進(jìn)信息素的更新過程。如果某條路徑上平均剩余能量較多，那么該路徑上信息素的濃度會(huì)增加得越多，從而使得路徑有更高的被選擇的機(jī)會(huì)，但是一個(gè)剩余能量較少的節(jié)點(diǎn)仍有可能出在一條具有較高平均剩余能量的路徑上，從而該節(jié)點(diǎn)會(huì)過早死亡，縮短網(wǎng)絡(luò)生命周期。文獻(xiàn)［6］分析了以數(shù)據(jù)為中心的無線傳感器蟻群優(yōu)化路由算法，并針對(duì)蟻群優(yōu)化路由算法的缺陷提出了一種改進(jìn)算法，通過增加一個(gè)稱之為搜索螞蟻(seach ant)的新型移動(dòng)代理，幫助前向螞蟻避免陷入環(huán)路陷阱。Reza GhasemAghaeil［7］等人提出了一種基于生物學(xué)啟發(fā)式智能群體路由算法(SIBR)。作者提出兩種基于智能群體的自適應(yīng)路由算法:自適應(yīng)路由算法(AR)和改進(jìn)型自適應(yīng)路由算法(IAR)。他們通過去除隊(duì)列參數(shù)和加入強(qiáng)化學(xué)習(xí)概念(reinforcement learning concept)，改進(jìn)了 ADR［8］(基于蟻群算法的自適應(yīng)動(dòng)態(tài)路由)算法，由此產(chǎn)生了AR算法［9］。然而，AR算法不能產(chǎn)生最優(yōu)解。因此，通過增加系數(shù)，即鄰居節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的“代價(jià)”，作者提出了IAR算法，從而進(jìn)一步改善了AR算法的性能。在文獻(xiàn)［10］中，蘇淼等人在傳感器網(wǎng)絡(luò)分層路由協(xié)議LEACH基礎(chǔ)上，重新定義了“輪”的概念，提出了基于蟻群的無線傳感器網(wǎng)絡(luò)雙簇頭算法(ACDCHA)，算法把每一輪劃分成3個(gè)階段而不是傳統(tǒng)的兩個(gè)階段。根據(jù)信息素濃度在每一簇中選擇具有分工特征的主簇頭和副簇頭，主簇頭進(jìn)行數(shù)據(jù)收集和融合，副簇頭進(jìn)行數(shù)據(jù)傳輸工作。該算法較好的平衡了網(wǎng)絡(luò)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期。文獻(xiàn)［11］提出了一種基于多路徑蟻群算法的無線傳感器網(wǎng)絡(luò)的路由(MACS)，該算法利用蟻群的自組織、自適應(yīng)能力，并行地尋找最優(yōu)傳輸路徑，保留次優(yōu)傳輸路徑，以達(dá)到多路徑傳輸?shù)哪康?，使網(wǎng)絡(luò)能量均衡消耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期，但是沒有考慮網(wǎng)絡(luò)的QoS問題。文獻(xiàn)［12］提出了一種面向傳感器網(wǎng)絡(luò)的蟻群優(yōu)化路徑恢復(fù)算法，通過建立一種兼顧節(jié)點(diǎn)能量消耗和節(jié)點(diǎn)剩余能量的路徑選擇概率模型，使得算法能夠找到一條從源節(jié)點(diǎn)到sink的能量有效路徑，提高了全網(wǎng)的能量有效性，但是在概率選擇模型中沒有考慮路徑的延遲和帶寬等因素。

WSN中現(xiàn)有的蟻群算法，一般是使用跳數(shù)［13］或者歐幾里得距離［14］來計(jì)算下一跳概率的，他們幾乎沒有提及QoS問題。與上述研究不同，本文為了解決傳感器網(wǎng)絡(luò)的數(shù)據(jù)擁塞、傳輸延時(shí)、能量消耗過大等問題，本文提出了一種基于蟻群算法的傳感器網(wǎng)絡(luò)QoS路由算法。

2 基于蟻群算法的QoS路由算法

2.1 網(wǎng)絡(luò)模型

給定網(wǎng)絡(luò)G=(V，S，E)，其中V為傳感器節(jié)點(diǎn)集，S為源節(jié)點(diǎn)集且S∩V=Φ，E為邊集，假設(shè)所有的邊都是雙向的。對(duì)于任何節(jié)點(diǎn)v∈(S∪V)有一個(gè)最大傳輸距離r，用R(vi，vj)表示節(jié)點(diǎn)vi和vj的距離，如果R(vi，vj)≤r，則存在一條邊e(vi，vj)∈E。本文討論的無線傳感器網(wǎng)絡(luò)QoS路由是尋找到滿足不同QoS需求的路徑p。路徑p滿足QoS需求的目標(biāo)函數(shù)如下:

其中，bandwidth(p)為路徑p的帶寬需求，delay(p)為路徑p的延時(shí)需求，式(1)的目的是通過調(diào)整參數(shù)δ和σ從而使路徑p達(dá)到滿足不同QoS需求的目的。當(dāng)δ=0時(shí)，目的是搜索滿足延時(shí)需求的路徑p;當(dāng)σ=0時(shí)，目的是搜索滿足帶寬需求的路徑p;當(dāng)δ≠0且σ≠0時(shí)，目的是通過調(diào)整兩個(gè)參數(shù)的大小，搜索到一條既滿足一定的延時(shí)需求又滿足一定的帶寬需求的路徑p。

定義1高帶寬路徑，即找到的路徑p滿足如下條件:

定義2低延時(shí)路徑，即找到的路徑p滿足如下條件:

其中Bmin是最小帶寬需求，Dmax是最大延時(shí)需求。

2.2 路由建立

2.2.1 下一跳節(jié)點(diǎn)的選擇

首先，sink節(jié)點(diǎn)會(huì)向所有節(jié)點(diǎn)發(fā)送一個(gè)廣播報(bào)文，該報(bào)文中記錄了跳數(shù)、帶寬和能量值，當(dāng)前節(jié)點(diǎn)收到報(bào)文后，它會(huì)計(jì)算自己到達(dá)sink節(jié)點(diǎn)的跳數(shù)，本文用跳數(shù)來衡量各個(gè)節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的距離，當(dāng)一個(gè)源節(jié)點(diǎn)想要發(fā)送數(shù)據(jù)，它就會(huì)按照一定的概率來選擇下一跳節(jié)點(diǎn)，這個(gè)概率與節(jié)點(diǎn)到sink的跳數(shù)和節(jié)點(diǎn)間的可用帶寬有關(guān)，還與節(jié)點(diǎn)的剩余能量有關(guān)。本文將此問題抽象為基于最小費(fèi)用流的組合規(guī)劃問題，計(jì)算公式如下:

即節(jié)點(diǎn)vi根據(jù)最大的概率P(vi，vk)選擇下一跳的節(jié)點(diǎn)vk。

其中各個(gè)字符的意義如下:P(vi，vj)，螞蟻k將報(bào)文從節(jié)點(diǎn)vi傳遞到節(jié)點(diǎn)vj的概率，即節(jié)點(diǎn)vi選擇下一跳節(jié)點(diǎn)的概率;λ，權(quán)值常數(shù)，0＜λ＜1，反映節(jié)點(diǎn)剩余能量在概率選擇中所占比重的大小;τ(vi，vj)，節(jié)點(diǎn)vi到節(jié)點(diǎn)vj路徑上的pheromone素濃度;d(vi，vj)，節(jié)點(diǎn)vi經(jīng)過節(jié)點(diǎn)vj到達(dá)sink節(jié)點(diǎn)的跳數(shù)的倒數(shù);b(vi，vj)，節(jié)點(diǎn)vi到節(jié)點(diǎn)vj路徑上的可用帶寬;Nvi，節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn);α、β，參數(shù)，分別反映延時(shí)和帶寬相對(duì)重要程度的參數(shù);Evj，節(jié)點(diǎn)vj的剩余能量;Evu，節(jié)點(diǎn)vu的剩余能量。

下一跳節(jié)點(diǎn)采用上述方式時(shí)，會(huì)綜合考慮帶寬、延時(shí)、能量因素，可以根據(jù)節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的可用帶寬以及節(jié)點(diǎn)vj到達(dá)sink節(jié)點(diǎn)的跳數(shù)選擇出高帶寬路徑和低延時(shí)路徑，同時(shí)還考慮到了能量的因素，這樣能量小的節(jié)點(diǎn)，被選擇成為下一跳節(jié)點(diǎn)的概率會(huì)大大減小，從而保證算法能量消耗的均衡性。因此算法可以根據(jù)QoS需求選擇相應(yīng)的路徑，進(jìn)行數(shù)據(jù)傳輸。不過某些程度上增加了算法的復(fù)雜性，但是在WSN中，不可靠性一直是其最大的缺點(diǎn)之一，用一定的計(jì)算代價(jià)換來有一定QoS保證的數(shù)據(jù)傳輸，這種代價(jià)是值得的。

2.2.2 pheromone 素的更新規(guī)則

(1)局部信息素更新規(guī)則

當(dāng)某個(gè)螞蟻經(jīng)過鏈路(vi，vj)時(shí)，鏈路(vi，vj)上的信息素強(qiáng)度根據(jù)如下公式更新:

其中 ρ為 pheromone素?fù)]發(fā)因子，φ(根據(jù)對(duì)QoS的具體要求程度而定)為修正系數(shù)，Δτb(vi，vj)和Δτd(vi，vj)為信息素的變化量，定義如下:

定義3高帶寬路徑pheromone素變化大小Δτb(vi，vj)，表示pheromone素更新過程中高帶寬路徑上進(jìn)行信息素的更新程度，計(jì)算公式如下:

其中b(vi，vj)為節(jié)點(diǎn)vi到節(jié)點(diǎn)vj路徑上的可用帶寬，Δwvu為節(jié)點(diǎn)vi到其鄰居節(jié)點(diǎn)的所有可用帶寬之和，Evj為節(jié)點(diǎn)vj的剩余能量，Evu為節(jié)點(diǎn)vu的剩余能量，Nvi為節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn)。

定義4低延時(shí)路徑pheromone素變化大小Δτd(vi，vj)，表示 pheromone素更新過程中低時(shí)延路徑上進(jìn)行信息素的更新程度，計(jì)算公式如下:

其中Δwvj為節(jié)點(diǎn)vj將其收到的數(shù)據(jù)經(jīng)低延時(shí)路徑發(fā)送到sink節(jié)點(diǎn)的總代價(jià)，dvi為節(jié)點(diǎn)vi到達(dá)sink節(jié)點(diǎn)的跳數(shù)，dvj為節(jié)點(diǎn)vj到達(dá)sink節(jié)點(diǎn)跳數(shù)，Rvj為所有經(jīng)過節(jié)點(diǎn)vj的源節(jié)點(diǎn)的集合，Nvi為節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn)。Hvu，vj為上述源節(jié)點(diǎn)各自到達(dá)節(jié)點(diǎn)vj的跳數(shù)的總和，Evj為節(jié)點(diǎn)vj的剩余能量，Evu為節(jié)點(diǎn)vu的剩余能量。

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

當(dāng)算法搜索到一條路徑p時(shí)，由sink發(fā)送后向螞蟻(backward ant)對(duì)該路徑上的節(jié)點(diǎn)進(jìn)行全局信息素更新，更新規(guī)則為:

其中ρ為pheromone素?fù)]發(fā)因子，φ和θ(根據(jù)具體的 QoS需求而定)為調(diào)整參數(shù)，Δτb(vi，vj)和Δτd(vi，vj)分別為高帶寬路徑和低延時(shí)路徑信息素的變化量，Bmin是路徑P上的瓶頸帶寬，Hp是路徑p的跳數(shù)。全局信息素更新式(8)的目的是為具有較大可能的瓶頸帶寬和較小路徑跳數(shù)的路徑分配較強(qiáng)的信息素，同時(shí)根據(jù)應(yīng)用來調(diào)整參數(shù)θ的值來完成最小瓶頸帶寬限制。

2.3 算法可行性分析

本節(jié)首先證明pheromone素的濃度τ(vi，vj)被限制在τmax和τmin之間，然后證明了算法以無限接近于1的概率搜索到最優(yōu)路徑。

引理1設(shè)信息素濃度τ(vi，vj)的全局最大值為τmax，則對(duì)于任意τ(vi，vj)有下式成立:

證明假定第一只螞蟻經(jīng)過任意鏈路(vi，vj)后，鏈路(vi，vj)上的增加信息量不會(huì)超過Δτ，信息素的初始值為τ0。顯然在第一只螞蟻選擇鏈路(vi，vj)后，最大可能的信息量為(1－ρ)·τ0+φΔτ;第二只螞蟻選擇鏈路(vi，vj)后，則為(1－ρ)2·τ0+φ［(1－ρ)Δτ+Δτ］;其余依次類推。因此，由于信息素的揮發(fā)，在第t只螞蟻選擇鏈路(vi，vj)后，信息量的上限值為:

由此，當(dāng)ρ∈(0，1)時(shí)，其和將最終收斂到:

引理2設(shè)信息素濃度τ(vi，vj)的全局最小值為τmin，若采用全局信息素更新規(guī)則，對(duì)于任意鏈路(vi，vj)∈p*且τ*(vi，vj)≥τmin(p*為最優(yōu)路徑)，則在搜索到最優(yōu)路徑p*后，該最優(yōu)路徑p*的τ*(vi，vj)會(huì)單調(diào)增加，且有:

引理2的證明是引理1的證明過程的重復(fù)，只不過是將引理1中的τ0用(vi，vj)來代替(vi，vj)為最優(yōu)路徑p*上鏈路(vi，vj)的信息素濃度，其中t*是搜索到最優(yōu)路徑p*時(shí)選擇鏈路(vi，vj)的螞蟻的個(gè)數(shù)。這里就不在重復(fù)定理2的證明過程。

定理1如果搜索螞蟻個(gè)數(shù)足夠多，則可保證該算法以無限接近于1的概率搜索到滿足QoS需求的最優(yōu)路徑p*。假設(shè)p*(t)為t(0＜t＜m)只搜索螞蟻進(jìn)行搜索后發(fā)現(xiàn)最優(yōu)路徑p*的概率，則對(duì)于任意小的ε＞0和足夠多的搜索螞蟻個(gè)數(shù)m，有:

證明由于pheromone素的濃度τ(vi，vj)被限制在τmax和τmin之間，因此在螞蟻尋找最優(yōu)路徑的過程中，狀態(tài)轉(zhuǎn)移概率p(vi，vj)＞0，且有:

其中，Nvi為節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn)之和。從而對(duì)于任意一只搜索螞蟻均可以p(t)＞(pmin(vi，vj))h＞0的概率搜索到最優(yōu)路徑，其中h表示路徑p的跳數(shù)，p(t)螞蟻選擇路徑p的概率。假定只要有一只搜索螞蟻搜索到最優(yōu)路徑即可滿足要求，由此，p*(t)的一個(gè)下界為:

其中p*(t)蟻群算法搜索到最優(yōu)路徑的概率，對(duì)于任意小的ε＞0，搜索螞蟻個(gè)數(shù)足夠多時(shí)，有p*(t)＞1－ε，從而有p*(t)=1。

2.4 算法流程圖及協(xié)議描述

(1)算法流程圖和偽代碼

算法偽代碼如下:

(2)協(xié)議描述

圖1 算法流程圖

本文路由協(xié)議的主要思想是通過在源節(jié)點(diǎn)周期性地向目的節(jié)點(diǎn)發(fā)送螞蟻，找到滿足QoS(定義1和定義2)的路徑，并盡可能的使網(wǎng)絡(luò)的能量消耗最小、負(fù)載處于平衡狀態(tài)。每個(gè)節(jié)點(diǎn)都包含所有相鄰鏈路的剩余帶寬和距離sink節(jié)點(diǎn)的最小跳數(shù)信息。如果由于某些環(huán)境因素或者節(jié)點(diǎn)自身能量耗盡出現(xiàn)路徑斷裂，那么根據(jù)式(4)從斷裂節(jié)點(diǎn)的上一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選擇概率較大的下一跳節(jié)點(diǎn);如果由于某些環(huán)境因素或者節(jié)點(diǎn)自身能量消耗出現(xiàn)路徑退化，那么協(xié)議會(huì)根據(jù)局部信息素濃度更新式(5)和全局信息素濃度更新式(8)自適應(yīng)的調(diào)整路徑上的信息素濃度，從而保證路徑一直維持在比較好的狀態(tài)，進(jìn)行數(shù)據(jù)傳輸?；具^程如下:

描述1:按照網(wǎng)絡(luò)負(fù)載的分配狀態(tài)，初始化信息素濃度值，設(shè)為τ0。按照式(4)初始化每個(gè)節(jié)點(diǎn)的信息素表。當(dāng)給定源節(jié)點(diǎn)集S和一個(gè)目的節(jié)點(diǎn)時(shí)，就周期性地在源節(jié)點(diǎn)釋放一定數(shù)量的以該目的節(jié)點(diǎn)為目的地的螞蟻分組。當(dāng)螞蟻到達(dá)某個(gè)中間節(jié)點(diǎn)u時(shí)，首先在該信息素表中選擇滿足式(4)的相鄰節(jié)點(diǎn)作為螞蟻移動(dòng)的下一跳節(jié)點(diǎn)。

描述2:在螞蟻從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的過程中，根據(jù)式(5)、式(6)、式(7)記錄所訪問過的節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的剩余帶寬信息和到目的節(jié)點(diǎn)的跳數(shù)信息。如果鏈路(vi，vj)的傳輸延遲之和滿足式(3)和剩余帶寬滿足式(4)，則螞蟻發(fā)送到下一跳節(jié)點(diǎn)vj，同時(shí)用局部信息素更新式(5)更新鏈路(vi，vj)的信息素濃度。當(dāng)螞蟻運(yùn)動(dòng)到目的節(jié)點(diǎn)時(shí)，除了重復(fù)以上過程外，同時(shí)利用全局信息素更新式(8)更新路徑上所有鏈路的信息素濃度。

描述3:根據(jù)不同的QoS需求，選擇不同的路徑，進(jìn)行數(shù)據(jù)傳輸。

從以上描述可以看出，一旦搜索到最優(yōu)路徑，協(xié)議就能夠選擇滿足不同QoS需求的路徑。描述中每個(gè)節(jié)點(diǎn)的路由信息(即每個(gè)節(jié)點(diǎn)的信息素表)的收集的能耗相對(duì)于大量的數(shù)據(jù)傳輸?shù)哪芎膩碚f很小，可以忽略不計(jì)。

3 算法仿真研究

本文采用NS2模擬仿真環(huán)境，在500 m×500 m的區(qū)域內(nèi)隨機(jī)部署300個(gè)傳感器節(jié)點(diǎn)(包括基站)，基站位置(250，250)在無線傳感器網(wǎng)絡(luò)中，相對(duì)于數(shù)據(jù)無線發(fā)送接收來說，節(jié)點(diǎn)進(jìn)行計(jì)算和儲(chǔ)存的能耗基本可以忽略不計(jì)，所以網(wǎng)絡(luò)的生存時(shí)間主要取決于數(shù)據(jù)傳輸。設(shè)定節(jié)點(diǎn)初始能量為50 J，發(fā)送和接收能耗均為5×10－8J/bit，空閑能耗為 4×10－9J/bit。數(shù)據(jù)融合功耗為 5×10－9J/bit，放大電路功耗為 5×10－8J/bit，通信距離為50 m～60 m。

為了驗(yàn)證本文所提出的給予蟻群算法的QoS路由協(xié)議的有效性，本文從多個(gè)角度對(duì)該協(xié)議進(jìn)行了分析，并與傳統(tǒng)蟻群算法和LEACH算法進(jìn)行了比較。

為了獲得較優(yōu)的;路徑平均傳輸時(shí)延的優(yōu)化值，討論了2個(gè)參數(shù)α，λ對(duì)路徑平均傳輸端到端時(shí)延的影響，實(shí)驗(yàn)中，變化其中參數(shù)，從 0.1～0.9，另外一個(gè)個(gè)參數(shù)為剩余比例，如 α=0.3，則 λ=0.7，結(jié)果表明當(dāng)兩個(gè)參數(shù)在0.47附近時(shí)，路徑平均傳輸端到端延時(shí)較優(yōu)，結(jié)果如圖2所示。

圖2 參數(shù)－端到端延遲影響

為了獲得較優(yōu)的路徑平均傳輸帶寬的優(yōu)化值，討論了3個(gè)參數(shù)β，θ，λ對(duì)路徑平均傳輸帶寬的影響，實(shí)驗(yàn)中，變化其中參數(shù)，從0.1～0.9，其余兩個(gè)參數(shù)等分剩余比例，如 β=0.6，則 λ=θ=0.2，結(jié)果表明當(dāng)三個(gè)參數(shù)在0.4附近時(shí)，路徑平均傳輸帶寬較優(yōu)，結(jié)果如圖3所示。

圖4顯示了網(wǎng)絡(luò)節(jié)點(diǎn)能量的總剩余率，本文算法在保證QoS要求的前提下，綜合考慮了能量因素，優(yōu)先選擇能量較大的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，使網(wǎng)絡(luò)能量消耗更加均衡，使整個(gè)網(wǎng)絡(luò)生命周期得到改善。本文算法網(wǎng)絡(luò)能量消耗較好于LEACH協(xié)議，但是相比較傳統(tǒng)蟻群算法而言，有明顯優(yōu)勢(shì)。

圖3 參數(shù)－平均傳輸帶寬影響

圖4 能量剩余率

圖5顯示了算法從開始到搜索到最優(yōu)路徑后的平均時(shí)延情況，由仿真曲線可以看出算法的收斂速度比較快，經(jīng)過短暫的搜索過程后，平均時(shí)延逐漸下降，并最終達(dá)到穩(wěn)定狀態(tài)。

圖5 時(shí)間步和平均延時(shí)的關(guān)系

某一時(shí)刻的路由拓?fù)浣Y(jié)構(gòu)圖6所示。

圖6 某一時(shí)刻協(xié)議路由示例

圖6給出了某一時(shí)刻三種不同的路徑形態(tài):Ⅰ保證低數(shù)據(jù)傳輸延遲和高帶寬需求的情況下，能量消耗較小的路徑;Ⅱ低延遲路徑，即在保證低數(shù)據(jù)傳輸延遲的情況下，能量消耗較小的路徑;Ⅲ高帶寬路徑，即在保證數(shù)據(jù)可靠性的情況下，能量消耗較小的路徑。

表1顯示了3種算法在3種網(wǎng)絡(luò)性能方面的表現(xiàn)，由于本文協(xié)議采用了基于蟻群算法的QoS保證機(jī)制，因此增加了網(wǎng)絡(luò)的等效帶寬，縮短了端到端的時(shí)延，增加了網(wǎng)絡(luò)可靠性。

表1 網(wǎng)絡(luò)性能統(tǒng)計(jì)

4 結(jié)束語

本文提出了一種WSN中基于蟻群算法的QoS路由算法，綜合考慮能量、時(shí)延、帶寬等因素，將如何搜索最佳路徑問題抽象為組合規(guī)劃問題，根據(jù)最小費(fèi)用流規(guī)則定義了高帶寬和低時(shí)延路徑的判決條件，利用蟻群優(yōu)化算法，尋找到兩條不同目標(biāo)函數(shù)的路徑，達(dá)到滿足不同QoS需求的目的。仿真實(shí)驗(yàn)表明，本文算法在滿足不同QoS需求的同時(shí)，較好的減少了網(wǎng)絡(luò)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期，但是在如何降低算法復(fù)雜度的方面需要做進(jìn)一步的研究。

［1］田麗娟，張愛華，盧秀清.基于蟻群算法的無線傳感器網(wǎng)絡(luò)中心點(diǎn)融合算法研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23(4):579－581.

［2］胡彧，王靜.基于蟻群算法的LEACH協(xié)議研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24(5):747－751.

［3］Dicaro G，Dorigo M.AntNet Distributed Stigmergetic Control for Communications Networks［J］.Vivck，1999，12(3/4):2－37.

［4］Dhillon S S，Vanmieghem P.Performance Analysis of the AntNet algorithm［J］.Computer Networks，2007，51(8):2104－2125.

［5］Camilo T，Careeto C，Silva J S，et al.An Energe-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks［C］//LNCS 4150:Proc of ANTS 2006.Heideberg:Springer，2006:49－59.

［6］Ge C，Tiande G，Wenguo Y，et al.An Improved Ant-Based Routing Protocol in Wireless Sensor Networks［C］//Proc of 2006 Int Conf on Collaborative Computing:Networking，Applications and Worksharing.Los Alamitos，CA:IEEE Computer Society，2006:442－448.

［7］Aghaeil R G，Rahman M A，Gueaieb W，et al.Ant Colony-Based Reinforcement Learing Alg-orithm for Routing in Wireless Sensor Networks［C］//Instrumentation and Measurement Technology Conference-IMTC 2007.Warsaw，Poland，May 2007.

［8］Lu Y，Zhao G，Su F.Adaptive Ant-Based Dynamic Routing Algorithm［C］//Proceedings of the 5th World Congress on Intelligent Control and Automation.IEEE，Hangzhou，China，June 2004:2694－2697.

［9］Zhang Y，Kuhn L D，F(xiàn)romherz M P J.Improvement on Ant Routing for Sensor Networks［C］//Intelligence Workshop on Ant Colony Optimization and Swarm Intelligence.Sep.2004.

［10］蘇淼，錢還，王煦法.基于蟻群的無線傳感器網(wǎng)絡(luò)雙簇頭算法［J］.計(jì)算機(jī)工程，2008，34(13):174－176.

［11］任秀麗，梁紅偉，汪宇.基于多路徑蟻群算法的無線傳感器網(wǎng)絡(luò)路由［J］.計(jì)算機(jī)科學(xué)，2009，36(4):116－118.

［12］鄭巍，劉三陽，寇曉麗.一種面向傳感器網(wǎng)絡(luò)的蟻群優(yōu)化路徑恢復(fù)算法［J］.西安交通大學(xué)學(xué)報(bào)，2010，44(1):83－86.

［13］Liao W H，Kao Y，F(xiàn)an C M.Data aggregation in wireless sensor networks using ant colony algorithm［J］.Networks and Computer Applications，2008，31(4):387－401.

［14］Misra R，Mandal C.Ant-aggregation for optimal data aggregation in wireless sensor networks［C］//Proc on Int Conf on Wireless and Optical Communications Neworks.New York:IEEE，2006:349－353.