基于改進蟻群優(yōu)化算法的網(wǎng)絡(luò)服務(wù)質(zhì)量路由算法

馬世歡，李 偉

(河南工業(yè)職業(yè)技術(shù)學(xué)院計算機工程系，河南 南陽 473000)

0 引言

隨著計算機信息技術(shù)與通信技術(shù)的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)在軍事、工業(yè)監(jiān)控、環(huán)境監(jiān)測等領(lǐng)域得到了成功應(yīng)用［1］。路由技術(shù)是無線傳感器網(wǎng)絡(luò)的核心技術(shù)，傳感器節(jié)點的能量、計算能力有限，再加上網(wǎng)絡(luò)環(huán)境的不穩(wěn)定性，如何對無線網(wǎng)絡(luò)路由算法進行優(yōu)化和設(shè)計，以滿足用戶對網(wǎng)絡(luò)服務(wù)質(zhì)量(Quality of Service，QoS)要求成為當(dāng)前研究熱點［2-3］。

根據(jù)無線傳感器網(wǎng)絡(luò)的特點，許多國內(nèi)外學(xué)者對無線路由算法進行了深入的研究，取得一些研究成果［4］。傳統(tǒng)QoS 的路由算法沒有考慮無線網(wǎng)絡(luò)的特殊性，如實時性差、外界干擾大等，因此不能直接應(yīng)用于無線網(wǎng)絡(luò)路由設(shè)計和優(yōu)化中［5］。傳統(tǒng)無線網(wǎng)絡(luò)路由算法只考慮單一的QoS 指標(biāo)，如網(wǎng)絡(luò)延時、端到端帶寬、網(wǎng)絡(luò)丟包率、延時抖動等［6］，由于單一指標(biāo)不能全面、準(zhǔn)確描述無線路由性能，因此難以建立整體性能最優(yōu)的數(shù)據(jù)轉(zhuǎn)發(fā)路由，魯棒性比較差，應(yīng)用范圍受限［8］。針對單一指標(biāo)存在的不足，根據(jù)組合優(yōu)化理論，一些學(xué)者提出了一些多指標(biāo)QoS 的無線網(wǎng)絡(luò)路由算法，如文獻(xiàn)［9］提出了基于遺傳算法的多約束QoS 路由算法，綜合考慮無線網(wǎng)絡(luò)的帶寬、延時、延時抖動等數(shù)據(jù)鏈路指標(biāo)，將QoS 路由問題看作是一個多約束的優(yōu)化問題，通過全局搜索能力強的遺傳算法進行求解，找到了最優(yōu)數(shù)據(jù)轉(zhuǎn)發(fā)路由方案，一定程度上解決了傳統(tǒng)路由算法存在的不足。隨后有學(xué)者提出采用蟻群優(yōu)化算法(Ant Colony Optimization，ACO)、混沌遺傳算法、量子遺傳算法、文化算法等對無線網(wǎng)絡(luò)路由算法進行優(yōu)化，提高QoS 路由算法的求解速度［10-13］。

為了獲得更加理想的QoS 路由算法，本文提出一種基于改進蟻群優(yōu)化算法的QoS 路由算法MACO)，根據(jù)無線網(wǎng)絡(luò)的路由特點，對標(biāo)準(zhǔn)蟻群算法進行相應(yīng)的改進，最后通過仿真實驗測試其性能。實驗結(jié)果表明，本文算法減少了網(wǎng)絡(luò)丟包率和平均延時，提高了網(wǎng)絡(luò)通信的質(zhì)量。

1 QoS 路由問題描述

1.1 QoS 參數(shù)選擇

QoS 指無線網(wǎng)絡(luò)為用戶提供的服務(wù)質(zhì)量，隨著無線網(wǎng)絡(luò)范圍不斷擴大，不同領(lǐng)域的QoS 參數(shù)不相同［14］。結(jié)合無線網(wǎng)絡(luò)特點，可以采用一個帶有權(quán)重信息的無向連通圖對無線網(wǎng)絡(luò)結(jié)構(gòu)進行描述，G=＜V，E ＞，其中V 表示網(wǎng)絡(luò)中所有節(jié)點的集合，E 為所有鏈路集合，P(s，d)表示從源節(jié)點s 到目的節(jié)點d的一條路經(jīng)。本文選擇的QoS 參數(shù)主要包括帶寬(B)、端到端的延時(D)、數(shù)據(jù)包丟失率(L)、時延抖動(G)、鏈路花費(C)等［15］。

1.2 QoS 路由數(shù)學(xué)模型

設(shè)s 到d 之間的路徑帶寬滿足:

其中，B 為要求最小帶寬。

延時滿足:

其中，D 為要求最大延時。

丟包率滿足:

其中，L 為要求的最大丟包率。

時延抖動滿足:

其中，J 為要求的最大時延抖動。

花費滿足:

多約束路由的主要目標(biāo)是在滿足QoS 參數(shù)帶寬、延時、時延抖動、丟包率約束條件下，尋找一條最優(yōu)服務(wù)路徑，同時保證鏈路花費少，收斂于最優(yōu)路徑速度快，且有較高的QoS 滿意率。

2 改進蟻群算法的QoS 路由算法

2.1 標(biāo)準(zhǔn)蟻群算法

ACO 算法是一種性能優(yōu)良的啟發(fā)式優(yōu)化算法，采用正反饋機制實現(xiàn)分布式全局優(yōu)化，通過信息素不斷更新，最終收斂于最優(yōu)路徑上。采用標(biāo)準(zhǔn)蟻群算法來對QoS 路由問題進行求解時，首先將蟻群起始點與食物轉(zhuǎn)換成QoS 路由的源節(jié)點與目標(biāo)節(jié)點，然后模擬蟻群覓食機制最終得到最優(yōu)的路由。

狀態(tài)轉(zhuǎn)移概率的計算如下。

螞蟻k 在t 時刻由節(jié)點i 到節(jié)點j 的概率計算公式為:

其中，τij(t)為節(jié)點i 與j 的信息強度;ηij(t)為啟發(fā)因子;allowedk為可選的節(jié)點;α 為信息啟發(fā)因子，β 為期望啟發(fā)因子［16］。

螞蟻在尋找路徑的過程中會不斷留下信息素，當(dāng)信息素累積過多時，啟發(fā)信息就會受到影響，所以信息素需要不斷更新，各路徑下的信息素全局和局部更新方式為:

其中，ρ 為信息素?fù)]發(fā)系數(shù);Δτij(t)為新增加的信息素總和，為遺留信息素總和，其計算公式如下:

其中，Q 為信息素強度;Lk為螞蟻k 行走的所有路徑長度之和。

2.2 蟻群算法的改進

1)狀態(tài)轉(zhuǎn)移概率的改進。網(wǎng)絡(luò)路由優(yōu)化問題具有自身的特殊點，選擇路由節(jié)點時，需考慮帶寬、端到端的延遲、數(shù)據(jù)丟包率以及時延抖動，因此在進行節(jié)點的狀態(tài)轉(zhuǎn)移過程中，將延時和延時抖動引入到狀態(tài)轉(zhuǎn)移概率計算中，具體為:

其中，q0為［0 1］之間的常數(shù)，q 為［0 1］之間的隨機數(shù)。

啟發(fā)因子ηij(t)為延時和延時抖動和倒數(shù)的函數(shù)，這樣數(shù)據(jù)可以選擇質(zhì)量更好的路由進行轉(zhuǎn)發(fā)。

2)信息素更新策略的改進。為了提高算法的收斂速度，本文在進行信息素更新策略時，同時考慮信息素的局部和全局更新。信息素更新思路具體為:在螞蟻k 經(jīng)過路徑(i，j)時，仍根據(jù)式(8)進行信息素局部更新;其所經(jīng)過全部路徑的信息素全局更新方式為:

對其它未經(jīng)過的路徑上的信息素更新方式為:

其中，ρ1仍然為信息素的保留系數(shù)，Q=AQ1+BQ2，Q1表示路徑(i，j)和節(jié)點i 上的丟包率和延時抖動之和，Q2表示路徑(i，j)上的時延，B 為總帶寬。

2.3 算法工作步驟

1)根據(jù)QoS 網(wǎng)絡(luò)的約束條件，刪除不滿足條件的網(wǎng)絡(luò)節(jié)點，建立一個新的網(wǎng)絡(luò)拓?fù)鋱D。

2)初始化網(wǎng)絡(luò)，初始各鏈路上的信息素以及蟻群算法相關(guān)參數(shù)值，將螞蟻置于源節(jié)點上。

3)每只螞蟻根據(jù)式(10)選擇路徑，根據(jù)式(8)對路上信息素進行局部更新，根據(jù)式(11)和式(12)對路上信息素進行全局更新。

4)如果迭代次數(shù)超過最大迭代次數(shù)，搜索終止，輸出最優(yōu)路由選擇方案;不然，迭代次數(shù)增加，轉(zhuǎn)至步驟3)繼續(xù)搜索。

3 仿真實驗

3.1 仿真環(huán)境

為了測試改進蟻群優(yōu)化算法的QoS 路由算法的性能，在Intel 4 核3.0 GHz 的CPU，4 GB RAM，Windows 7 操作系統(tǒng)的計算機上，采用NS2 仿真軟件進行仿真實驗。仿真參數(shù)如表1 所示，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1 所示。

表1 仿真參數(shù)設(shè)置

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3.2 對比算法及性能評價標(biāo)準(zhǔn)

為了使MACO 算法的結(jié)果更具說服力，選擇遺傳算法(GA)［17］進行對比實驗，MACO 算法參數(shù)設(shè)置:α=2，β=2，Q=50，ρ=2.5，GA 的參數(shù)設(shè)置為:交叉概率為0.85，變異概率為0.05，種群規(guī)模為20，最大迭代次數(shù)為500，選擇平均延時、包投遞率對算法性能的優(yōu)劣進行評價。

3.3 結(jié)果與分析

3.3.1 平均延時對比

GA 和MACO 算法的平均延時變化曲線如圖2所示。從圖2 可以知道，隨著仿真時間的增加，MACO、GA 路由的平均延時不斷減小，MACO 算法的平均延時下降比較平緩，而且一直小于GA 的平均延時，這主要是由于MACO 算法具有更好的搜索能力，找到性能更優(yōu)的數(shù)據(jù)轉(zhuǎn)發(fā)路由，使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)十分穩(wěn)定，變化比較小，減少了數(shù)據(jù)包從源節(jié)點傳輸目標(biāo)節(jié)點的平均延時，對比結(jié)果表明，MACO 算法選擇的數(shù)據(jù)路由響應(yīng)速度更快，建立的鏈路路由質(zhì)量更高，可以滿足用戶服務(wù)質(zhì)量要求。

圖2 MACO 算法與對比算法的延時對比曲線

3.3.2 包投遞率對比

GA 和MACO 算法的包投遞率變化曲線如圖3所示。從圖3 可以知道，隨著仿真時間的增加，MACO、GA 路由的包投遞率不斷上升，MACO 算法的包投遞率一直高于GA 的包投遞率，這主要是由于MACO 算法建立比較理想的數(shù)據(jù)轉(zhuǎn)發(fā)路由，減少了數(shù)據(jù)的丟包率和網(wǎng)絡(luò)擁塞概率，保證了數(shù)據(jù)包轉(zhuǎn)發(fā)的可靠性。

圖3 MACO 算法與對比算法的包投遞率對比曲線

4 結(jié)束語

為了提高無線網(wǎng)絡(luò)通信的可靠性，節(jié)約通信成本，本文提出了一種基于改進蟻群優(yōu)化算法QoS 路由算法，并通過仿真對比實驗對算法的性能進行分析。實驗結(jié)果表明，改進蟻群優(yōu)化算法在滿足網(wǎng)絡(luò)通信質(zhì)量要求的條件下，不僅大幅度減少了網(wǎng)絡(luò)的平均延時，加快了數(shù)據(jù)傳輸速度，而且提高了包投遞率，降低了網(wǎng)絡(luò)的丟包率，在無線網(wǎng)絡(luò)中具有廣泛的應(yīng)用前景。

［1］Ehsan S，Hamdaoui B.A survey on energy-efficient routing techniques with QoS assurances for wireless multimedia senor networks［J］.IEEE Communications Surveys ＆Tutorials，2012，14(2):265-278.

［2］葛連升，江林，秦豐林.QoS 組播路由算法研究綜述［J］.山東大學(xué)學(xué)報(理學(xué)版)，2010，32(1):55-65.

［3］Denouri D，Balasingham I.Traffic differentiation based modular QoS localized routing for wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2011，10(6):797-809.

［4］Jakllari U，Eidcnbcnz S，Hengartner N，et al.Link positions matter:A non-commutative routing metric for wireless mesh networks［J］.IEEE Transactions on Mobile Computing，2012，11(1):61-72.

［5］Hou R，Lui K S，Baker F，et al.Hop-by-hop routing in wireless mesh networks with bandwidth guarantees［J］.IEEE Transactions on Mobile Computing，2012，11(2):261-277.

［6］王鋒.基于遺傳算法的多參數(shù)QoS 網(wǎng)絡(luò)路由算法［J］.計算機與數(shù)字工程，2014，42(5):785-786.

［7］王浩，曹仲偉.基于遺傳蟻群算法的QoS 路由約束問題的研究［J］.湖北工業(yè)大學(xué)學(xué)報，2011，26(2):71-73.

［8］鐘李全，孟李林，柯冰，等.基于分級結(jié)構(gòu)的優(yōu)化QoS 路由算法［J］.光通信研究，2014，184(4):31-33.

［9］劉欣，李飛，鄭寶玉.基于量子遺傳算法的多約束QoS路由算法［J］.南京郵電大學(xué)學(xué)報(自然科學(xué)版)，2011，31(2):31-35.

［10］何志東，俞鶴偉，陶銘.雙向搜索蟻群算法在QoS 單播路由中的應(yīng)用［J］.計算機工程與應(yīng)用，2011，46(31):106-108.

［11］王鎮(zhèn)，劉學(xué)軍.WSN 中基于蟻群算法的QoS 路由協(xié)議［J］.傳感技術(shù)學(xué)報，2011，24(11):1625-1631.

［12］于淼，白光偉，沈航，等.無線傳感器網(wǎng)絡(luò)啟發(fā)式QoS 路由協(xié)議［J］.計算機科學(xué)，2014，41(7):171-177.

［13］葉仕通，萬智萍.高效的遺傳蟻群組合算法在QoS 路由上的運用［J］.重慶大學(xué)學(xué)報，2013，36(10):82-88.

［14］Yen Yun-sheng，Chao Han-chieh，Chang Ruay-shiung，et al.Flooding limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs［J］.Mathematical and Computer Modeling，2011，53(11-12):2238-2250.

［15］Leela R，Selvakumar S.Genetic algorithm approach to dynamic multiconstraint multi-path QoS routing algorithm for IP networks［J］.International Journal of Communication Networks and Distributed Systems，2010，5(4):392-411.

［16］萬博，盧星，陳立云，等.基于改進蟻群算法的擁塞規(guī)避QoS 路由算法［J］.計算機工程，2011，37(20):49-51.

［17］張月華，孫學(xué)梅，張明偉，等.基于文化算法的無線Mseh網(wǎng)QoS 路由算法［J］.計算機應(yīng)用與軟件，2012，29(11):264-268.