劉 靜，李 琦，吳華偉

（1.湖北文理學(xué)院 機(jī)械與汽車工程學(xué)院，襄陽(yáng) 441053；2.汽車零部件制造裝備數(shù)字化湖北省協(xié)同創(chuàng)新中心，襄陽(yáng) 441053；3.湖北文理學(xué)院 學(xué)工處，襄陽(yáng) 441053）

0 引言

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

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

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

1 路由網(wǎng)絡(luò)模型

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

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

定義2：在無(wú)向賦權(quán)圖G=(V,E)中，源節(jié)點(diǎn)vs到目的節(jié)點(diǎn)vd的所有可行路徑中，評(píng)價(jià)函數(shù)值最大的路徑稱為多QoS約束最優(yōu)路徑，其對(duì)應(yīng)的路徑P即為滿足QoS約束條件的最優(yōu)路徑。

評(píng)價(jià)函數(shù)是用來(lái)評(píng)價(jià)路徑好壞的標(biāo)準(zhǔn)，它將直接反映路徑的優(yōu)劣。本文將路徑時(shí)延，時(shí)延抖動(dòng)、跳數(shù)作為路徑評(píng)價(jià)指標(biāo)，采用加權(quán)法獲得路徑k的評(píng)價(jià)函數(shù)，如式(1)所示：

上式中設(shè)定Hmax為最大路徑跳數(shù)，H(P)為路徑跳數(shù)。從上述評(píng)價(jià)函數(shù)可知，只有時(shí)延最小，時(shí)延抖動(dòng)最小且跳數(shù)最少的路徑是最優(yōu)的，這基本反映了用戶的綜合要求。

2 基于混合優(yōu)化算法的多QoS約束路由優(yōu)化

2.1 信息素初始化

基本蟻群路由算法的缺點(diǎn)之一是初始化所有鏈路的概率均設(shè)置成相等，導(dǎo)致前向螞蟻在初始狀態(tài)時(shí)尋路存在盲目性。為此，本文將在對(duì)每條鏈路賦予初始信息素C0基礎(chǔ)上，根據(jù)鏈路方向?qū)︽溌沸畔⑺貪舛冗M(jìn)行修正，從而獲得鏈路ei,j=(vi,vj)上的初始信息素濃度τij(0)，具體公式如下：

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

2.2 算法設(shè)計(jì)

無(wú)線傳感器網(wǎng)絡(luò)混合路由算法的具體算法步驟如下：

步驟1：初始化參數(shù)。

首先進(jìn)行參數(shù)的初始化，如節(jié)點(diǎn)規(guī)模（螞蟻數(shù)量）n、性價(jià)比因子α、誘發(fā)函數(shù)因子β、性價(jià)比揮發(fā)因子ρ、性價(jià)比總量Q、迭代次數(shù)初值iter=1。

步驟2：構(gòu)建解空間。

以網(wǎng)絡(luò)源節(jié)點(diǎn)作為n個(gè)螞蟻的尋路起點(diǎn)，對(duì)螞蟻k而言，利用下式計(jì)算

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

步驟3：對(duì)上述n個(gè)路由方案（染色體），應(yīng)用遺傳算法進(jìn)行交叉、變異操作，評(píng)價(jià)各方案，采用輪盤賭與最優(yōu)保持策略選擇n個(gè)新種群，并對(duì)信息素濃度進(jìn)行更新。

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

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

步驟3.3：選擇操作。利用評(píng)價(jià)函數(shù)Fi評(píng)價(jià)路徑i轉(zhuǎn)發(fā)數(shù)據(jù)的優(yōu)劣，采用輪盤賭與最優(yōu)保持策略選擇n個(gè)新種群作為蟻群算法中路徑信息素濃度更新的較好路徑。

其中：

步驟5：完成一次迭代后，記錄最優(yōu)路徑的評(píng)價(jià)函數(shù)值與平均評(píng)價(jià)函數(shù)值。若連續(xù)多次計(jì)算結(jié)果沒(méi)有明顯改善（相鄰迭代結(jié)果之差小于ε），則輸出最優(yōu)解；否則，iter=iter+1，清空螞蟻所經(jīng)路徑的記錄表并返回到步驟2。

3 仿真實(shí)驗(yàn)

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

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

表1 算法優(yōu)化結(jié)果對(duì)比表

4 結(jié)論

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

圖1 仿真網(wǎng)絡(luò)拓?fù)鋱D

[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].計(jì)算機(jī)應(yīng)用.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] 柯宗武,李臘元,陳年生.無(wú)線多媒體傳感器網(wǎng)絡(luò)QoS路由博弈算法[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版).2009,33(02)：295-298.

[5] 凌啟東,馬欣榮,詹新生.基于遺傳算法的WSID網(wǎng)絡(luò)路由建模與優(yōu)化[J].江蘇建筑職業(yè)技術(shù)學(xué)院學(xué)報(bào),2012,1(1)：55-58.

[6] 王征應(yīng),石冰心.基于啟發(fā)式遺傳算法的QoS多播路由問(wèn)題求解[J].計(jì)算機(jī)學(xué)報(bào),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].計(jì)算機(jī)學(xué)報(bào).2003,26(6)： 676-681.

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

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

[11] 劉敏,徐世軍,孫思毅,等.基于QoS-PSO的無(wú)線傳感器網(wǎng)絡(luò)路由算法[J].同濟(jì)大學(xué)學(xué)報(bào).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] 王菁,劉三陽(yáng),李祖猛.基于改進(jìn)蟻群算法的QoS單播路由優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào),2009,21(19)：6081-6085.

[14] 石釗,葛連升.一種解多QoS約束組播問(wèn)題的改進(jìn)蟻群算法[J]. 山東大學(xué)(理學(xué)版),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.