移動自組織網(wǎng)絡(luò)Q學(xué)習(xí)和改進(jìn)蟻群QoS路由算法

高 良 誠

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,合肥 230009；2.銅陵職業(yè)技術(shù)學(xué)院 信息工程系,安徽 銅陵 244061)

?

移動自組織網(wǎng)絡(luò)Q學(xué)習(xí)和改進(jìn)蟻群QoS路由算法

高 良 誠1,2

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,合肥 230009；2.銅陵職業(yè)技術(shù)學(xué)院 信息工程系,安徽 銅陵 244061)

針對移動自組織網(wǎng)絡(luò)的QoS路由問題,提出一種結(jié)合Q學(xué)習(xí)和改進(jìn)蟻群算法的QoS路由算法,該算法綜合Q學(xué)習(xí)和蟻群算法的優(yōu)點(diǎn),把Q學(xué)習(xí)算法的Q值作為蟻群算法的初始信息素,提高了算法初期的收斂速度,同時在路徑選擇時綜合考慮節(jié)點(diǎn)的能量和負(fù)載.仿真實(shí)驗(yàn)表明,該算法在保證QoS需求的前提下,增加了路由的有效性和魯棒性,降低了能耗,包投遞率、網(wǎng)絡(luò)生存時間等指標(biāo)均較好.

移動自組織網(wǎng)絡(luò)；服務(wù)質(zhì)量；Q學(xué)習(xí)；改進(jìn)蟻群算法；路由算法

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展,移動自組織網(wǎng)絡(luò)以其組網(wǎng)便捷性和網(wǎng)絡(luò)健壯性得到越來越多地應(yīng)用.移動自組織網(wǎng)絡(luò)用戶需求趨向多樣化,對網(wǎng)絡(luò)服務(wù)質(zhì)量QoS提出了越來越高的要求,因此如何設(shè)計(jì)出在數(shù)據(jù)傳輸過程中能滿足帶寬、傳輸時延、丟包率等服務(wù)要求的高效QoS路由算法已成為目前該領(lǐng)域的研究熱點(diǎn)[1-2].

移動自組織網(wǎng)絡(luò)具有拓?fù)鋭討B(tài)、多跳路由和能量受限等特點(diǎn),多個QoS參數(shù)間存在聯(lián)合或?qū)α⒌年P(guān)系,因此,多約束QoS路由是一個NP-Complete問題[3].針對QoS路由問題,人們一般采用啟發(fā)式算法解決,使蟻群算法、遺傳算法、粒子群算法和模擬退火算法等智能算法得到廣泛應(yīng)用[4-8].蟻群算法通過模擬自然界螞蟻群體覓食行為,成功地解決了諸多離散優(yōu)化問題,具有健壯性、靈活性和求解精度高等特點(diǎn).ADRA算法[9]將蟻群算法運(yùn)用到路由選擇過程中,能體現(xiàn)QoS參數(shù)要求,但算法搜索時間長,易陷入局部最優(yōu).文獻(xiàn)[10]未能將QoS約束條件與蟻群算法進(jìn)行有效融合,路徑選擇時啟發(fā)函數(shù)不能很好地反映鏈路狀況,導(dǎo)致鏈路穩(wěn)定性欠佳,影響路由性能.基于此,本文提出一種移動自組織網(wǎng)絡(luò)中Q學(xué)習(xí)結(jié)合改進(jìn)蟻群算法的QoS路由算法(QRQIA),把Q學(xué)習(xí)中的Q值作為蟻群算法的初始信息素,加快了算法初期的收斂速度,路由選擇時綜合考慮節(jié)點(diǎn)的能量和負(fù)載,在保證QoS需求的前提下,增加了路由的有效性和魯棒性.

1 網(wǎng)絡(luò)模型及問題描述

移動自組織網(wǎng)絡(luò)QoS路由是一種實(shí)現(xiàn)端到端滿足QoS參數(shù)需求的路由機(jī)制,網(wǎng)絡(luò)模型可用圖G=(V,E)表示,其中:V(G)={v1,v2,…,vn}表示網(wǎng)絡(luò)節(jié)點(diǎn)集合;E(G)={e1,e2,…,en}表示網(wǎng)絡(luò)中邊的集合.對于任意邊e∈E(G),邊的權(quán)值對應(yīng)帶寬、時延等QoS屬性.因此,網(wǎng)絡(luò)路徑選擇問題可轉(zhuǎn)換為求解集合E(G)的子集P,其中,集合P為在滿足一定QoS需求下,路由費(fèi)用值最小的從源節(jié)點(diǎn)S(S∈G)到目的節(jié)點(diǎn)D(D∈G)的路徑集.

路由QoS參數(shù)指標(biāo)一般有累加性參數(shù)、累積性參數(shù)和最小性參數(shù)3類.累加性參數(shù)時延為

(1)

累積性參數(shù)丟包率Packet-loss為

最小性參數(shù)帶寬BandWidth為

本文主要考慮帶寬、時延和跳數(shù)等QoS路由參數(shù).

定義1QoS路由路徑費(fèi)用函數(shù)定義為

(4)

其中:Hosps為路由跳數(shù);w1,w2和w3為比例系數(shù),其值可根據(jù)時延和丟包率在QoS路由中的比重設(shè)定.由式(4)可見,費(fèi)用函數(shù)與帶寬成反比,而與時延、丟包率和跳數(shù)成正比.因此,本文的QoS路由算法即為在滿足上述QoS約束條件的前提下,尋找性能最優(yōu)且cost(P)值最小的路徑.

2 QoS路由算法

2.1Q學(xué)習(xí)算法

Q學(xué)習(xí)是一種特殊的強(qiáng)化學(xué)習(xí)算法[11],強(qiáng)調(diào)在與環(huán)境的交互中學(xué)習(xí),通過一定策略學(xué)習(xí)和強(qiáng)化狀態(tài)-行動函數(shù)值,選擇到達(dá)目標(biāo)的最優(yōu)動作.在學(xué)習(xí)過程中,根據(jù)動作a,提供報(bào)酬信息,引導(dǎo)動作接近目標(biāo).用Q(s,a)表示動作a的累積回報(bào),在每個時刻t,根據(jù)狀態(tài)s選擇動作a,并獲得即時報(bào)酬rt,Q值更新公式為

(5)

其中:δ為學(xué)習(xí)因子,δ∈(0,1);rt+1為t+1時刻的報(bào)酬;γ為折扣因子,γ∈(0,1).

上述狀態(tài)概率轉(zhuǎn)移公式反映了Q學(xué)習(xí)算法和蟻群算法的內(nèi)在聯(lián)系,因而可將Q值作為蟻群算法中的信息素[12-13].本文QRQIA算法將Q學(xué)習(xí)算法的Q值作為蟻群算法的初始信息素,可加快算法初期的收斂速度.

2.2改進(jìn)蟻群算法

蟻群算法解決旅行商問題(TSP)[14]的核心思想是螞蟻根據(jù)路徑轉(zhuǎn)移概率選擇下一節(jié)點(diǎn),信息素濃度高和路徑啟發(fā)函數(shù)值大的路徑被選擇的概率更大,并通過信息素更新機(jī)制驅(qū)動螞蟻選擇最優(yōu)路徑.

本文算法在路徑啟發(fā)函數(shù)中考慮節(jié)點(diǎn)能耗,并在信息素更新機(jī)制中引入負(fù)載信息和路徑費(fèi)用函數(shù),從而在滿足QoS需求的前提下,找出最優(yōu)路徑.

2.2.1 路徑轉(zhuǎn)移概率 在QRQIA算法中,ID為k的螞蟻在節(jié)點(diǎn)i處選擇下一節(jié)點(diǎn)j的概率為

(6)

其中:μij(t)為時刻t信息素濃度;ηij(t)為時刻t路徑啟發(fā)函數(shù),表示路徑能見度;α為殘留信息素啟發(fā)因子,表示路徑的重要性;β為期望啟發(fā)因子,表示能見度的重要性;tabuk為螞蟻k的禁忌表,存儲螞蟻k當(dāng)前所走過的節(jié)點(diǎn).

本文算法在計(jì)算路徑啟發(fā)函數(shù)ηij時考慮節(jié)點(diǎn)的能量,采用文獻(xiàn)[15]的能量模型.節(jié)點(diǎn)i向距離為d的節(jié)點(diǎn)j發(fā)送n字節(jié)數(shù)據(jù)的能量消耗為

(7)

其中:Eω為收發(fā)1 bit數(shù)據(jù)時無線收發(fā)器所消耗的能量;εfs為當(dāng)d

定義2路徑啟發(fā)函數(shù)定義為

(8)

其中:Ej為節(jié)點(diǎn)j的剩余能量;Ej-init為節(jié)點(diǎn)j的初始能量;dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離;λ為能見度系數(shù),可以平衡時延和能量消耗.

由式(8)可知,路徑啟發(fā)函數(shù)與節(jié)點(diǎn)能量狀況和節(jié)點(diǎn)距離有關(guān),節(jié)點(diǎn)能量狀況越好、節(jié)點(diǎn)間的距離越短,該節(jié)點(diǎn)被選擇的概率越大,因而最優(yōu)路徑上節(jié)點(diǎn)剩余能量更大,消耗能量更小,從而提高路由的魯棒性.

2.2.2 信息素更新 當(dāng)螞蟻經(jīng)過某路徑時信息素會發(fā)生變化,路過螞蟻越多的路徑信息濃度越大,該路徑成為最優(yōu)路徑的概率越大.同時,為防止算法過快陷入局部最優(yōu),信息素按一定系數(shù)揮發(fā).

設(shè)μij(t)為時刻t邊E(i,j)的信息素濃度,其初始值為Q學(xué)習(xí)算法的Q值,信息素在時間間隔Δt內(nèi)更新規(guī)則如下：

其中:δ為信息素?fù)]發(fā)因子;γ為折扣因子;Δμij(t)為Δt時間內(nèi)信息素的增量,且

(11)

其中:Q為初始信息素;cost(k)為螞蟻k從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)所經(jīng)過路徑的費(fèi)用函數(shù),由式(4)計(jì)算;L為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)平均負(fù)載;Lj為節(jié)點(diǎn)j的負(fù)載,計(jì)算公式如下:

(12)

其中,q(x)為節(jié)點(diǎn)j某時刻待發(fā)送數(shù)據(jù)隊(duì)列的長度,節(jié)點(diǎn)的數(shù)據(jù)隊(duì)列信息通過周期性發(fā)送hello包,獲取節(jié)點(diǎn)隊(duì)列長度,并取平均值,進(jìn)而得到節(jié)點(diǎn)j的負(fù)載Lj.

由式(11)可見,螞蟻所經(jīng)過路徑節(jié)點(diǎn)負(fù)載越小,費(fèi)用越低,則信息素增量越大,對其他螞蟻的吸引作用越大,如果負(fù)載大于平均負(fù)載,則信息素增量為負(fù).從而費(fèi)用低、負(fù)載小的路徑被選擇的概率變大.

2.3QRQIA算法實(shí)現(xiàn)

本文算法中螞蟻請求數(shù)據(jù)包AREQ(ant request)包含螞蟻ID、源節(jié)點(diǎn)ID、目的節(jié)點(diǎn)ID、螞蟻禁忌表tabu等信息；螞蟻應(yīng)答數(shù)據(jù)包AREP(ant reply)包含螞蟻ID、源節(jié)點(diǎn)ID、目的節(jié)點(diǎn)ID、上一節(jié)點(diǎn)ID等信息；節(jié)點(diǎn)信息表包含ID(螞蟻ID)、目的節(jié)點(diǎn)ID、下一節(jié)點(diǎn)ID、鄰居節(jié)點(diǎn)ID、鄰居節(jié)點(diǎn)能量、鄰居節(jié)點(diǎn)負(fù)載、cost值等信息.算法步驟如下：

1)初始化網(wǎng)絡(luò),根據(jù)給定的QoS條件,刪除不滿足帶寬要求的鏈路和獨(dú)立節(jié)點(diǎn)集;

2)把Q學(xué)習(xí)算法迭代產(chǎn)生的Q值作為蟻群算法的初始信息素,設(shè)置蟻群算法迭代次數(shù)為NC;

3)將m只螞蟻放置到源節(jié)點(diǎn)上;

4)將源節(jié)點(diǎn)放到螞蟻禁忌表tabu中,對于每個螞蟻請求數(shù)據(jù)包AREQ,根據(jù)式(6)選擇狀態(tài)轉(zhuǎn)移概率大的鄰居節(jié)點(diǎn)作為下一個節(jié)點(diǎn);

5)螞蟻每經(jīng)過一個節(jié)點(diǎn),根據(jù)式(9)進(jìn)行信息素更新,并將該節(jié)點(diǎn)放到禁忌表tabu中;更新節(jié)點(diǎn)信息表,建立反向路由,將下一個節(jié)點(diǎn)ID中填入上游節(jié)點(diǎn)的ID值；

6)重復(fù)4)和5),直到螞蟻到達(dá)目的節(jié)點(diǎn)或不滿足QoS條件限制;

7)所有螞蟻到達(dá)目的節(jié)點(diǎn)后,選擇路徑費(fèi)用函數(shù)值最小且滿足QoS條件的螞蟻路徑,沿反向路由向源節(jié)點(diǎn)發(fā)送螞蟻應(yīng)答數(shù)據(jù)包AREP,并更新節(jié)點(diǎn)信息表,建立前向路由;

8)重復(fù)3)～7),直到迭代次數(shù)超過NC,保存滿足QoS要求的cost(P)值最小和次小的路徑,選擇cost(P)值最小的路徑傳輸數(shù)據(jù).

2.4路由維護(hù)

由于節(jié)點(diǎn)的移動性和鏈路的擁塞,移動自組織網(wǎng)中鏈路斷開較頻繁.為了快速進(jìn)行路由修復(fù),本文采用冗余路徑策略,當(dāng)最優(yōu)路徑失效時,使用次優(yōu)路徑;如果次優(yōu)路徑也失效,則由失效節(jié)點(diǎn)的前一節(jié)點(diǎn)查詢該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是否有到目的節(jié)點(diǎn)的路徑,如果有,則選擇cost值小的路徑,否則,啟動路由發(fā)現(xiàn)過程.這樣不僅增強(qiáng)了路由的魯棒性,且減少了路由發(fā)現(xiàn)次數(shù).

3 仿真與分析

本文采用NS2進(jìn)行仿真,仿真環(huán)境1 000 m×1 000 m,100個節(jié)點(diǎn)中4個節(jié)點(diǎn)為目的節(jié)點(diǎn),其他節(jié)點(diǎn)隨機(jī)分布,以Random Waypoint模型運(yùn)動,最大移動速度30 m/s,節(jié)點(diǎn)最大傳輸范圍為250 m,數(shù)據(jù)包大小為512 B,發(fā)包率為10包/s,仿真時間500 s,螞蟻數(shù)量50,迭代次數(shù)NC=120.路由QoS約束條件為最大時延40 ms,最小帶寬2 MB/s,最大跳數(shù)5,最大丟包率20%.設(shè)置參數(shù)δ=0.8,γ=1.1,α=1,β=1.2,Δt=1,θ=90,節(jié)點(diǎn)初始能量為10 J.

圖1為不同算法隨迭代次數(shù)增加時的費(fèi)用函數(shù).由圖1可見,隨著迭代次數(shù)的增加,QRQIA算法、AODV算法和文獻(xiàn)[10]算法的費(fèi)用函數(shù)cost(P)均下降,QRQIA算法達(dá)到最優(yōu)費(fèi)用函數(shù)速度更快,費(fèi)用更小,這是因?yàn)樵谒惴ㄟ\(yùn)行過程中,Q學(xué)習(xí)和改進(jìn)蟻群算法的融合加快了算法收斂速度,且在螞蟻信息素更新時優(yōu)先考慮費(fèi)用小的路徑所致.

圖2為不同算法隨節(jié)點(diǎn)運(yùn)動速度變化時的包投遞率.由圖2可見,隨著節(jié)點(diǎn)運(yùn)動速度的提高,QRQIA算法、AODV算法和文獻(xiàn)[10]算法的包投遞率均下降,但QRQIA算法的包投遞率高于AODV和文獻(xiàn)[10]算法,且投遞率下降趨勢不明顯,這是因?yàn)镼RQIA采用Q學(xué)習(xí)算法生產(chǎn)初始信息素,算法收斂速度快,路由尋徑效率高,在螞蟻信息素更新時偏好負(fù)載小的節(jié)點(diǎn)和費(fèi)用小的路徑,路由的路徑帶寬和時延性能較好,且能避開負(fù)載大的節(jié)點(diǎn),降低了丟包率和時延.因而,QRQIA算法有更高的包投遞率.

圖1 費(fèi)用函數(shù)Fig.1 Cost function

圖2 包投遞率Fig.2 Packet delivery ratio

圖3 網(wǎng)絡(luò)生存時間Fig.3 Network lifetime

網(wǎng)絡(luò)生存時間是指從仿真實(shí)驗(yàn)開始到第一個節(jié)點(diǎn)能量耗盡為止所需的時間.圖3為不同算法隨節(jié)點(diǎn)運(yùn)動速度變化時的網(wǎng)絡(luò)生存時間.由圖3可見,隨著節(jié)點(diǎn)運(yùn)動速度的增加,網(wǎng)絡(luò)生存時間逐漸下降,QRQIA算法的網(wǎng)絡(luò)生存時間高于AODV算法和文獻(xiàn)[10]算法,且隨運(yùn)動速度的增加,其下降幅度較小,這是因?yàn)镼RQIA算法在路徑選擇時考慮節(jié)點(diǎn)的剩余能量和能量消耗,選擇剩余能量大和能量消耗小的路徑所致,因而,網(wǎng)絡(luò)中節(jié)點(diǎn)能量更均衡,網(wǎng)絡(luò)生存時間更長.對于式(8)中λ,取λ=1.0和λ=0.5進(jìn)行對比,λ=1.0表示QoS參數(shù)中對時延要求不高,通信距離小的節(jié)點(diǎn)被選擇可能性變大,節(jié)點(diǎn)采用多跳短距離方式傳輸數(shù)據(jù),節(jié)點(diǎn)消耗能量更小,網(wǎng)絡(luò)生存時間變長；λ=0.5表示QoS參數(shù)中對時延要求高,通信距離大的節(jié)點(diǎn)被優(yōu)先選擇可能性變大,節(jié)點(diǎn)通信距離變大,節(jié)點(diǎn)消耗能量變大,網(wǎng)絡(luò)生存時間變短.因此,在滿足QoS時延約束的前提下,設(shè)置更大的λ值,有利于延長網(wǎng)絡(luò)生存時間.

綜上所述,本文提出了一種移動自組織網(wǎng)絡(luò)中Q學(xué)習(xí)結(jié)合改進(jìn)蟻群算法的QoS路由算法(QRQIA),為加快算法初期收斂速度,使用Q學(xué)習(xí)算法生成蟻群算法的初始信息素,在蟻群算法的路徑選擇中,優(yōu)先選擇剩余能量大、距離短、負(fù)載小的鄰居節(jié)點(diǎn),并綜合考慮鏈路的費(fèi)用,在滿足QoS需求的前提下,增加了算法的有效性和魯棒性,加快了算法的收斂速度,降低了數(shù)據(jù)傳輸?shù)哪芎?仿真實(shí)驗(yàn)表明,該算法在包投遞率、網(wǎng)絡(luò)生存時間等性能指標(biāo)上更具優(yōu)越性.

[1] 謝小民,王興偉,溫占考,等.一種面向認(rèn)知網(wǎng)絡(luò)的QoS路由協(xié)議 [J].計(jì)算機(jī)學(xué)報(bào),2013,36(9)：1807-1815.(XIE Xiaomin,WANG Xingwei,WEN Zhankao,et al.A QoS Routing Protocol for Congnitive Networks [J].Chinese Journal of Computers,2013,36(9)：1807-1815.)

[2] Gulati M K,Kumar K.QoS Routing Protocols for Mobile Ad Hoc Networks：A Survey [J].International Journal of Wireless and Mobile Computing,2012,5(2)：107-118.

[3] WANG Zheng,Crowcroft J.Quality-of-Service Routing for Supporting Multimedia Applications [J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234.

[4] Saleem M,Caro G A D,Farooq M,et al.Swarm Intelligence Baased Routing Protocol for Wireless Sensor Networks:Survery and Future Directions [J].Information Sciences,2011,181(20):4597-4624.

[5] Correia F,Vazao T.Simple Ant Routing Algorithm Strategies for a (Multipurpose)MANET Model [J].Ad Hoc Networks,2010,8(8):810-823.

[6] 李麗芬,張群艷,朱永利,等.基于多蟻群算法的無線傳感器網(wǎng)絡(luò)路由的跨層設(shè)計(jì) [J].計(jì)算機(jī)科學(xué),2011,38(2)：59-62.(LI Lifen,ZHANG Qunyan,ZHU Yongli,et al.Cross-Layer Routing Design for Wireless Sensor Networks Based on Multiple Ant Colony Algorithm [J].Computers Science,2011,38(2)：59-62.)

[7] 萬博,盧昱,陳立云,等.基于改進(jìn)蟻群算法的擁塞規(guī)避QoS路由算法 [J].計(jì)算機(jī)工程,2011,37(20)：49-51.(WAN Bo,LU Yu,CHEN Liyun,et al.QoS Rounting Algorithm with Congnitive Avoidance Based on Improved Ant Colony Algorithm [J].Computer Engineering,2011,37(20)：49-51.)

[8] 周少瓊,徐祎,姜麗,等.蟻群優(yōu)化算法在Ad Hoc網(wǎng)絡(luò)路由中的應(yīng)用 [J].計(jì)算機(jī)應(yīng)用,2011,31(2)：332-334.(ZHOU Shaoqiong,XU Yi,JIANG Li,et al.Ant Colony Optimization Applied in Ad Hoc Network Routing [J].Journal of Computer Applications,2011,31(2)：332-334.)

[9] ZHENG Xiangquan,GUO Wei,LIU Renting.An Ant-Based Distributed Routing Algorithm for Ad-Hoc Networks [C]//International Conference on Communications,Circuits and Systems.Prscataway,NJ:IEEE,2004:412-417.

[10] Ahokerani H,Jabbendari S.An Ant-Based QoS Routing Algorithm for Mobile Ad Hoc Networks [C]//International Conference on Ubiquitous and Future Networks.Prscataway,NJ:IEEE,2009:79-83.

[11] Liu J,Zeng J.Community Detection Based on Modualarity Density and Gennetic Algorithm [C]//Proceedings of the 2010 International Conference on Computational Intelligence and Security.New York:ACM Press,2010:29-32.

[12] 王慶文,史浩山,戚茜.Ad Hoc網(wǎng)絡(luò)Q學(xué)習(xí)穩(wěn)定蟻群路由算法 [J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2012,44(7)：120-125.(WANG Qingwen,SHI Haoshan,QI Qian.A Stable Ant Colony Routing Algorithm Based onQ-Learning for Ad Hoc Networks [J].Journal of Harbin Institute of Technology,2012,44(7)：120-125.)

[13] 黨小超,姚浩浩,郝占軍.Q學(xué)習(xí)和蟻群優(yōu)化混合的無線傳感器網(wǎng)絡(luò)移動代理路由算法 [J].計(jì)算機(jī)應(yīng)用,2013,33(9)：2440-2443.(DANG Xiaochao,YAO Haohao,HAO Zhanjun.Mobile Agent Routing Algorithm for WSN Based onQLearning Hybrid with Ant Colony Optimization [J].Journal of Computer Applications,2013,33(9)：2440-2443.)

[14] 孫凱,吳紅星,王浩,等.蟻群與粒子群混合算法求解TSP問題 [J].計(jì)算機(jī)工程與應(yīng)用,2012,48(34)：60-63.(SUN Kai,WU Hongxing,WANG Hao,et al.Hybrid Ant Colony and Particle Swarm Algorithm for Solving TSP [J].Computer Engineering and Applications,2012,48(34)：60-63.)

[15] Sim K M,Sun W H.Ant Colony Optimization for Routing and Load Balancing：Survey and New Directions [J].IEEE Transactions on Systems,Man,and Cybermetics,Part A：Systems and Humans,2003,33(5)：560-572.

(責(zé)任編輯：韓 嘯)

QoSRoutingAlgorithmBasedonQ-LearningandImprovedAntColonyinMobileAdHocNetworks

GAO Liangcheng1,2

(1.SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009,China；2.DepartmentofInformationEngineering,TonglingVocationalandTechnicalCollege,Tongling244061,AnhuiProvince,China)

In view of QoS rounting problem in mobile ad hoc networks,the author proposed a QoS routing algorithm integrated withQ-learning and improved ant colony algorithm.The algorithm combines the advantages ofQ-learning with those of ant colony algorithm,and it takesQvalue ofQ-learning algorithm as the initial pheromone of ant colony algorithm,improves the initial convergence speed of the algorithm,at the same time,takes the node energy and load into account in path selection.Simulation results show that on the premise of guaranteeing QoS demand,the algorithm increases the effectiveness and robustness of routing and reduces energy consumption,and besides,packet delivery ratio,network lifetime and other indicators display better performances.

mobile ad hoc network;quality of service(QoS);Q-learning;improved ant colony algorithm;routing algorithm

10.13413/j.cnki.jdxblxb.2015.03.26

2014-09-29.

高良誠(1971—),男,漢族,碩士,副教授,從事認(rèn)知無線網(wǎng)絡(luò)和人工智能的研究,E-mail：glc912@126.com.

國家自然科學(xué)基金(批準(zhǔn)號:61201252)和安徽省高校自然科學(xué)研究項(xiàng)目(批準(zhǔn)號:KJ2012Z418).

TP393

：A

：1671-5489(2015)03-0483-06