WSN中基于蟻群算法的QoS路由協議*

王 鎮，劉學軍

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

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

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

1 相關工作

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

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

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

2.1 網絡模型

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

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

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

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

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

2.2 路由建立

2.2.1 下一跳節點的選擇

首先，sink節點會向所有節點發送一個廣播報文，該報文中記錄了跳數、帶寬和能量值，當前節點收到報文后，它會計算自己到達sink節點的跳數，本文用跳數來衡量各個節點與sink節點之間的距離，當一個源節點想要發送數據，它就會按照一定的概率來選擇下一跳節點，這個概率與節點到sink的跳數和節點間的可用帶寬有關，還與節點的剩余能量有關。本文將此問題抽象為基于最小費用流的組合規劃問題，計算公式如下:

即節點vi根據最大的概率P(vi，vk)選擇下一跳的節點vk。

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

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

2.2.2 pheromone 素的更新規則

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

當某個螞蟻經過鏈路(vi，vj)時，鏈路(vi，vj)上的信息素強度根據如下公式更新:

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

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

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

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

其中Δwvj為節點vj將其收到的數據經低延時路徑發送到sink節點的總代價，dvi為節點vi到達sink節點的跳數，dvj為節點vj到達sink節點跳數，Rvj為所有經過節點vj的源節點的集合，Nvi為節點vi的所有鄰居節點。Hvu，vj為上述源節點各自到達節點vj的跳數的總和，Evj為節點vj的剩余能量，Evu為節點vu的剩余能量。

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

當算法搜索到一條路徑p時，由sink發送后向螞蟻(backward ant)對該路徑上的節點進行全局信息素更新，更新規則為:

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

2.3 算法可行性分析

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

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

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

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

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

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

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

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

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

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

2.4 算法流程圖及協議描述

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

算法偽代碼如下:

(2)協議描述

圖1 算法流程圖

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

描述1:按照網絡負載的分配狀態，初始化信息素濃度值，設為τ0。按照式(4)初始化每個節點的信息素表。當給定源節點集S和一個目的節點時，就周期性地在源節點釋放一定數量的以該目的節點為目的地的螞蟻分組。當螞蟻到達某個中間節點u時，首先在該信息素表中選擇滿足式(4)的相鄰節點作為螞蟻移動的下一跳節點。

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

描述3:根據不同的QoS需求，選擇不同的路徑，進行數據傳輸。

從以上描述可以看出，一旦搜索到最優路徑，協議就能夠選擇滿足不同QoS需求的路徑。描述中每個節點的路由信息(即每個節點的信息素表)的收集的能耗相對于大量的數據傳輸的能耗來說很小，可以忽略不計。

3 算法仿真研究

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

為了驗證本文所提出的給予蟻群算法的QoS路由協議的有效性，本文從多個角度對該協議進行了分析，并與傳統蟻群算法和LEACH算法進行了比較。

為了獲得較優的;路徑平均傳輸時延的優化值，討論了2個參數α，λ對路徑平均傳輸端到端時延的影響，實驗中，變化其中參數，從 0.1～0.9，另外一個個參數為剩余比例，如 α=0.3，則 λ=0.7，結果表明當兩個參數在0.47附近時，路徑平均傳輸端到端延時較優，結果如圖2所示。

圖2 參數－端到端延遲影響

為了獲得較優的路徑平均傳輸帶寬的優化值，討論了3個參數β，θ，λ對路徑平均傳輸帶寬的影響，實驗中，變化其中參數，從0.1～0.9，其余兩個參數等分剩余比例，如 β=0.6，則 λ=θ=0.2，結果表明當三個參數在0.4附近時，路徑平均傳輸帶寬較優，結果如圖3所示。

圖4顯示了網絡節點能量的總剩余率，本文算法在保證QoS要求的前提下，綜合考慮了能量因素，優先選擇能量較大的節點作為下一跳節點，使網絡能量消耗更加均衡，使整個網絡生命周期得到改善。本文算法網絡能量消耗較好于LEACH協議，但是相比較傳統蟻群算法而言，有明顯優勢。

圖3 參數－平均傳輸帶寬影響

圖4 能量剩余率

圖5顯示了算法從開始到搜索到最優路徑后的平均時延情況，由仿真曲線可以看出算法的收斂速度比較快，經過短暫的搜索過程后，平均時延逐漸下降，并最終達到穩定狀態。

圖5 時間步和平均延時的關系

某一時刻的路由拓撲結構圖6所示。

圖6 某一時刻協議路由示例

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

表1顯示了3種算法在3種網絡性能方面的表現，由于本文協議采用了基于蟻群算法的QoS保證機制，因此增加了網絡的等效帶寬，縮短了端到端的時延，增加了網絡可靠性。

表1 網絡性能統計

4 結束語

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

［1］田麗娟，張愛華，盧秀清.基于蟻群算法的無線傳感器網絡中心點融合算法研究［J］.傳感技術學報，2010，23(4):579－581.

［2］胡彧，王靜.基于蟻群算法的LEACH協議研究［J］.傳感技術學報，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，Fromherz M P J.Improvement on Ant Routing for Sensor Networks［C］//Intelligence Workshop on Ant Colony Optimization and Swarm Intelligence.Sep.2004.

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

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

［12］鄭巍，劉三陽，寇曉麗.一種面向傳感器網絡的蟻群優化路徑恢復算法［J］.西安交通大學學報，2010，44(1):83－86.

［13］Liao W H，Kao Y，Fan 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.