無線傳感器網絡混合路由算法研究

劉 靜，李 琦，吳華偉

（1.湖北文理學院 機械與汽車工程學院，襄陽 441053；2.汽車零部件制造裝備數字化湖北省協同創新中心，襄陽 441053；3.湖北文理學院 學工處，襄陽 441053）

0 引言

無線多媒體傳感器網絡在戰場監控、環境監測、智能家庭護理和目標跟蹤等方面得到了越來越多的廣泛應用。但同時無線傳感器網絡存在資源受限、數據高度冗余，需要不同的QoS保障，使其路由問題變得復雜[1]，在滿足QoS要求的無線傳感器網絡中，不僅要保證網絡的連通性，還要滿足用戶對線路的帶寬、延遲、延遲抖動、跳數、能量均衡等要求，故多約束QoS無線傳感器網絡路由問題成為研究熱點。QoS網絡路由問題是一個NP-hard問題[2]，因而傳統算法對于此類問題面臨計算復雜度高、計算時間長等問題，為此利用啟發式算法成為學者們的首選，如蟻群算法[3,4]、遺傳算法[5,6]、貪婪算法[7]、免疫算法[8]、模擬退火算法[9]、量子遺傳算法[10]、粒子群算法[11]等。特別對蟻群算法的研究，將路由優化引向深入。

蟻群算法是1991年意大利學者Dorigo M等人[12]通過模擬自然界螞蟻尋食的行為提出的一種全新的啟發式算法。該算法不依賴于具體的數學描述，具有全局優化、自組織、自學習的能力和本質上的并行性等優點，是一種性能優良的啟發式優化算法。該算法在求解復雜優化問題，特別是離散優化問題方面有很大的優越性和廣闊的應用前景，但存在易陷入局部最優和前期搜索效率較低等缺點[13]。

針對蟻群算法缺點，本文結合無線傳感器網絡路由問題的特點，提出了一種基于蟻群算法的混合優化算法對無線傳感器網絡路由問題進行優化。該算法在初始化鏈路信息素濃度時，根據鏈路方向向量與鏈路起點指向目的節點的方向向量間夾角大小進行初始化賦值，減少螞蟻前期尋路的盲目性；將交叉、變異、選擇等遺傳算子引入算法中，進行信息素更新之前對路徑的調整或攝動，提高蟻群算法所獲得路徑的質量并擴展搜索區域；應用多屬性決策方法利用加權法將延遲、延遲抖動、跳數等屬性組合成路徑評價函數，從而更加全面反映各條路徑的綜合信息。

1 路由網絡模型

考慮鏈路帶寬、延遲、延遲抖動等約束的多QoS路由問題，即在無線傳感器網絡中找到一條從源節點到目的節點滿足帶寬、延遲、延遲抖動等諸多約束的最優路徑。無線傳感器網絡可以抽象為一個無向賦權圖G=(V,E)進行研究，其中V表示無線傳感器網絡的節點集合，用V=(v1,v2,…,vn)表示，其中，n為無線傳感器網絡節點的數目，E表示由傳感器節點與節點之間構成的鏈路集合。假設邊ei,j=(vi,vj)∈E，表示由傳感器節點(vi,vj)構成的一條無線多媒體傳感器網絡的鏈路，在圖G中，從源節點vs到目的節點vd的一條路徑用P來表示，即

定義1：設B(P)為路徑上鏈路帶寬最小值；D(P)為路徑上鏈路的時延之和；J(P)為路徑上鏈路時延抖動之和。則多QoS約束路由問題可描述為在無線傳感器網絡中尋找一條滿足下列約束條件的最優路徑：

定義2：在無向賦權圖G=(V,E)中，源節點vs到目的節點vd的所有可行路徑中，評價函數值最大的路徑稱為多QoS約束最優路徑，其對應的路徑P即為滿足QoS約束條件的最優路徑。

評價函數是用來評價路徑好壞的標準，它將直接反映路徑的優劣。本文將路徑時延，時延抖動、跳數作為路徑評價指標，采用加權法獲得路徑k的評價函數，如式(1)所示：

上式中設定Hmax為最大路徑跳數，H(P)為路徑跳數。從上述評價函數可知，只有時延最小，時延抖動最小且跳數最少的路徑是最優的，這基本反映了用戶的綜合要求。

2 基于混合優化算法的多QoS約束路由優化

2.1 信息素初始化

基本蟻群路由算法的缺點之一是初始化所有鏈路的概率均設置成相等，導致前向螞蟻在初始狀態時尋路存在盲目性。為此，本文將在對每條鏈路賦予初始信息素C0基礎上，根據鏈路方向對鏈路信息素濃度進行修正，從而獲得鏈路ei,j=(vi,vj)上的初始信息素濃度τij(0)，具體公式如下：

其中θ為R1與R2間的夾角，R1表示為節點vi指向它的鄰域節點vj的方向向量，R2示為節點vi指向目的節點vd的方向向量。式(2)表示R1與R2同向時，才為鏈路ei,j=(vi,vj)賦正值，否則賦零，即從節點vi開始選擇下一跳節點時，只考慮前向節點。

2.2 算法設計

無線傳感器網絡混合路由算法的具體算法步驟如下：

步驟1：初始化參數。

首先進行參數的初始化，如節點規模（螞蟻數量）n、性價比因子α、誘發函數因子β、性價比揮發因子ρ、性價比總量Q、迭代次數初值iter=1。

步驟2：構建解空間。

以網絡源節點作為n個螞蟻的尋路起點，對螞蟻k而言，利用下式計算

ηij(t)為誘發函數，表示從節點i到節點j傳輸數據的時延大小；α為性價比因子，越小的α值表示性價比在選擇下一跳過程中影響越小；β為誘導函數因子，越小的β值表示誘發函數在選擇下一跳過程中的影響越小。Allowed(i)表示節點i可訪問的鄰域節點集合。初始信息素濃度采用式(2)計算獲得。利用輪盤賭的方法選出螞蟻k從節點i到節點j的路線（即要訪問的下一個節點j）。以此方法，直到螞蟻k尋到目的節點。

步驟3：對上述n個路由方案（染色體），應用遺傳算法進行交叉、變異操作，評價各方案，采用輪盤賭與最優保持策略選擇n個新種群，并對信息素濃度進行更新。

步驟3.1：交叉操作。為了避免交叉操作產生非法路徑，采用了如下單點交叉操作：根據交叉率在父代中隨機選取若干染色體對進行交叉操作，比較兩個父代染色體，并找到所有相同的基因（即節點），隨機從這些相同基因中選取一個作為交叉點，交換從交叉點開始的后續所有基因。例如父代染色體（3 6 12 45 21 5）和（9 10 43 12 7 21 73 14）包含兩個相同基因12與21，隨機選擇基因12作為交叉點，則交叉后得到子代個體為（3 6 12 7 21 73 14）與（9 10 43 12 45 21 5）。

步驟3.2：變異操作。為避免產生非法路徑，采用如下變異過程：根據變異率任選取一個染色體，在該染色體中隨機選擇節點p，并將節點p之前的所有節點加入到子代中，然后以節點p為起點，以目的節點為終點，使用隨機走動法在前向節點集中找到一條不含有節點p之前所有節點的隨機路徑，將該路徑加到子代的后面。

步驟3.3：選擇操作。利用評價函數Fi評價路徑i轉發數據的優劣，采用輪盤賭與最優保持策略選擇n個新種群作為蟻群算法中路徑信息素濃度更新的較好路徑。

其中：

步驟5：完成一次迭代后，記錄最優路徑的評價函數值與平均評價函數值。若連續多次計算結果沒有明顯改善（相鄰迭代結果之差小于ε），則輸出最優解；否則，iter=iter+1，清空螞蟻所經路徑的記錄表并返回到步驟2。

3 仿真實驗

仿真實驗采用Waxman提出的隨機圖模型生成仿真網絡拓撲圖[15]。該模型在平面[a,b]上，采用泊松分布隨機布置節點。本文生成的是234個節點隨機布置在150×150范圍內，節點之間的通訊距離為20，節點的度為2。實驗時，帶寬設置為1～10之間的隨機數，鏈路間的時延是[8,16]間的隨機數，鏈路間的時延抖動為[0.01,0.1]之間的隨機數，假設QoS需求Bmin為5；Dmax為170，Jmax為1；Hmax為100。設置試驗中蟻群算法的性價比因子α=1，誘發函數因子β=5，性價比揮發因子ρ=1，ω1、ω2、ω3分別設定為0.6、0.2、0.2。遺傳算法的參數設置為：遺傳代數為50，種群大小為20；交叉率為0.8；變異率為0.1。設定源節點是節點188，匯聚節點是節點145，得到的優化路徑為[188, 191, 1, 35, 230, 176, 91, 31, 156, 42, 11, 161, 145]。

為了進一步驗證本文設計算法的有效性，應用路徑時延和運算時間作為路由問題求解主要考察指標。分別應用遺傳算法[16]、蟻群算法[17]以及遺傳-蟻群算法[18]對上述案例進行計算，對應設置與本文設計的混合算法相同的參數值，則優化結果對比情況如表1所示。在5次隨機計算過程中，本文設計的混合算法所求最優路徑時延均值與計算時間都要優于GA算法、ACO算法、GA-ACO算法，并且能較好地解決大規模無線傳感器路由問題。

表1 算法優化結果對比表

4 結論

本文基于無線傳感器路由問題特性分析，提出了基于蟻群算法的無線傳感器網絡混合路由求解算法。該算法引用了鏈路方向的概念，并將遺傳算法的交叉、變異及選擇算子引入算法中，同時應用多屬性決策方法將路徑時延、時延抖動、跳數三個路徑評價屬性整合為路徑考察指標，從而使算法具有較好的全局搜索能力與局部搜索能力，且能綜合反映路徑的優劣。仿真實驗表明：本文所設計算法要優于蟻群算法，遺傳算法以及遺傳-蟻群算法。并且算法具有較強的靈活性，只需要改變路徑時延、時延抖動、跳數三個路徑評價屬性的權重就可反映不同用戶對網絡服務要求的偏好。

圖1 仿真網絡拓撲圖

[1] Aky ildiz I F, Melo dia T, Chow dhur y K R. A surveyon w ir eless multimedia sensor netw orks[J].omputer Netw o rks,2007, 51(4)：921-960.

[2] 陳年生,李臘元,等.基于混合遺傳算法的QoS多播路由算法[J].計算機應用.2005,25(7);1485-1487.

[3] Rahman MA,GhasemAghaei R, El Saddik A, et al. M-IAR： biologically inspired routing protocol for wireless multimedia sensor networks[A].proceedings of the 2008 IEEE Instrumentation and Measurement Technology Conference (IMTC '08),Victoria, British Columbia, Canada,[C].IEEE Computer Society Press, 2008.

[4] 柯宗武,李臘元,陳年生.無線多媒體傳感器網絡QoS路由博弈算法[J].武漢理工大學學報(交通科學與工程版).2009,33(02)：295-298.

[5] 凌啟東,馬欣榮,詹新生.基于遺傳算法的WSID網絡路由建模與優化[J].江蘇建筑職業技術學院學報,2012,1(1)：55-58.

[6] 王征應,石冰心.基于啟發式遺傳算法的QoS多播路由問題求解[J].計算機學報,2001,24(1)：56-61.

[7] He Tian, Stankovic JA,Lu CY, et al. A spatiotemporal communication protocol for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(10)：995-1006.

[8] 劉芳,馮小軍.免疫組播路由選擇算法[J].計算機學報.2003,26(6)： 676-681.

[9] 胡世余,謝劍英.基于模擬退火的QoS路由算法[J].計算機工程, 2004,30(5)：109-110.

[10] 唐義龍,潘煒,李念強,等.基于量子遺傳算法的無線傳感器網絡路由研究[J].傳感器與微系統.2011,30(12)：68-70.

[11] 劉敏,徐世軍,孫思毅,等.基于QoS-PSO的無線傳感器網絡路由算法[J].同濟大學學報.2010,38(12)：1846-1850.

[12] Colorni A, Dorigo M, Maniezzo V.Distributed Optimization by Ant Colonies[A].Proceedings of the First European Conference on Artificial Life,1991.Paris, France：Elsevier Publishing, Amsterdam[C].1991：134-142.

[13] 王菁,劉三陽,李祖猛.基于改進蟻群算法的QoS單播路由優化[J].系統仿真學報,2009,21(19)：6081-6085.

[14] 石釗,葛連升.一種解多QoS約束組播問題的改進蟻群算法[J]. 山東大學(理學版),2007,42(9)：41-45.

[15] Waxman BM.Routing of multipoint Connections[J]. IEEE Journal on Selected Areas in Commuciations,1988,6(9)：1617-1622.

[16] Neeraj Kumar，Rahat Iqbal，Naveen Chilamkurti. An ant based multi constraints QoS aware service selection algorithm in wireless Mesh networks[J].Simulation Modelling Practice and Theory,2011,19(9)：1933-1945.

[17] LEELA R,THANULEKSHMI N,SELVAKUMAR S. Multiconstraint Qos unicast routing using genetic algorithm (MURUGA)[J]. Applied Soft Computing,2011,11(2)：1753-1761.

[18] Zeng X, Tu Z Y.A study on the optimization of the constrained routing problem based on genetic-ant colony algorithm[J].IEEE Computer Society,2010,218：860-863.