基于遺傳-蟻群優(yōu)化算法的QoS組播路由算法設計

史鄭延慧, 何剛

(北京郵電大學人工智能學院, 北京 100876)

在網(wǎng)絡通信領(lǐng)域中,服務質(zhì)量(quality of service, QoS)組播路由算法屬于重要研究內(nèi)容,其主要目的是提高組播通信的服務質(zhì)量。QoS組播路由優(yōu)化過程中需要考慮多種QoS指標,包括數(shù)據(jù)傳輸時延、數(shù)據(jù)丟包率以及時延抖動等。網(wǎng)絡通信需求在網(wǎng)絡技術(shù)飛速發(fā)展的背景下逐漸提升,為了適應各種應用場景,需要對QoS組播路由算法展開優(yōu)化設計[1-2],促進網(wǎng)絡通信技術(shù)的發(fā)展,提高網(wǎng)絡整體性能與服務質(zhì)量。

文獻[3]中采用菱形結(jié)構(gòu)保證量子克隆在組播通信過程中的保真度,通過量子克隆機克隆單光子偏振-空間模量子態(tài),同時考慮克隆保真度、量子跳數(shù)以及量子超糾纏資源數(shù),在Steiner樹的基礎(chǔ)上建立組播樹,完成路由選擇。但是,該算法組建的組播樹中存在較多的冗余子樹,難以有效獲取最優(yōu)路由,存在路由優(yōu)化效果差的問題。文獻[4]中在網(wǎng)絡中采用混合元啟發(fā)式算法選擇可靠鄰居節(jié)點,在此基礎(chǔ)上采用適應度排序馬鹿-貓群優(yōu)化(fitnesssorted red deer-cat swarm optimization, FRD-CSO)算法實現(xiàn)路由優(yōu)化。但是,該算法在路由優(yōu)化過程中未考慮到數(shù)據(jù)傳輸存在的時延問題,導致時延抖動高。文獻[5]中考慮節(jié)點傳輸代價、剩余帶寬以及鏈路質(zhì)量,將最小路徑代價作為目標,建立QoS路由優(yōu)化模型,引入Adam算法實現(xiàn)路由優(yōu)化。但是,該算法獲取最優(yōu)路徑所需的迭代次數(shù)較多,導致其搜索效率較低。文獻[6]中結(jié)合遺傳算法與支持向量回歸提出一種支持向量回歸的建模與基于遺傳算法的優(yōu)化方法(modeling based on support vector regression and optimizing based on a genetic algorithm, MSOG),對網(wǎng)絡數(shù)據(jù)包傳輸、延時、數(shù)據(jù)包到達時間以及接收信號強度展開建模優(yōu)化,實現(xiàn)路由優(yōu)化。但是,該算法在優(yōu)化過程中忽略了網(wǎng)絡本身的高動態(tài)性,導致該方法優(yōu)化后的路徑代價較高。

為了實現(xiàn)路由優(yōu)化,提高路由請求成功率,現(xiàn)提出基于遺傳-蟻群優(yōu)化算法的QoS組播路由算法,通過結(jié)合遺傳算法和蟻群算法,更有效地優(yōu)化QoS組播路由,降低路徑長度和路徑代價,從而提高網(wǎng)絡的性能和效率;同時,設計一種自適應變頻采集策略,根據(jù)網(wǎng)絡和節(jié)點信息的變化實時調(diào)整采集頻率,提供及時準確的數(shù)據(jù)支持,有助于優(yōu)化路由決策過程。

1 QoS組播路由算法設計

1.1 采集網(wǎng)絡數(shù)據(jù)

對時間序列展開分析發(fā)現(xiàn),如果節(jié)點在相同時間內(nèi)采集網(wǎng)絡中的數(shù)據(jù),那么采集的數(shù)據(jù)之間是存在時間關(guān)聯(lián)的,在連續(xù)時間上節(jié)點感知的信息差異較小。所提算法根據(jù)上述特點建立一元線性回歸模型用于逼近估計感知數(shù)據(jù),設計自適應變頻采集策略采集網(wǎng)絡數(shù)據(jù),以此分析網(wǎng)絡和節(jié)點的狀態(tài),為后續(xù)QoS組播路由優(yōu)化提供依據(jù),該策略的主要過程如下。

步驟1將時間序列作為依據(jù)采集網(wǎng)絡數(shù)據(jù),傳感器在數(shù)據(jù)采集與建模期間內(nèi)不傳輸數(shù)據(jù)。

步驟2引入最小二乘法[7-8]建立用于預測后續(xù)數(shù)據(jù)變化的一元線性回歸模型。

步驟3計算采集數(shù)據(jù)的整體誤差,根據(jù)計算結(jié)果對節(jié)點采樣頻率展開調(diào)整。

通過回歸模型建模分析節(jié)點感知數(shù)據(jù),并計算對應的回歸參數(shù),將回歸參數(shù)傳輸?shù)骄W(wǎng)絡的CHN(clearing house net)節(jié)點中,以此為依據(jù)建立簇內(nèi)SN節(jié)點(業(yè)務節(jié)點)對應的回歸模型,利用回歸模型預測節(jié)點感知的網(wǎng)絡數(shù)據(jù)。

預測數(shù)據(jù)變化的一元線性回歸模型為

β′=β+bt

(1)

式(1)中:b為回歸系數(shù);β、β′分別為t時刻節(jié)點采集的真實值與預測值。

按照時間順序根據(jù)節(jié)點在網(wǎng)絡中感知的數(shù)據(jù),建立數(shù)據(jù)集YD={(t1,β1),(t2,β2),…,(tn,βn)}。

(2)

將式(2)計算得到的β、b代入模型[式(1)]中,獲得預測節(jié)點采集數(shù)據(jù)的回歸模型,以此分析網(wǎng)絡與節(jié)點狀態(tài)。

1.2 QoS組播路由優(yōu)化模型

基于遺傳-蟻群優(yōu)化算法的QoS組播路由算法將路徑代價最小作為目標建立QoS組播路由優(yōu)化模型,路徑代價通常由總端到端時延、傳播時延和跳數(shù)組成[9-10],所提算法在優(yōu)化過程中考慮了逐跳轉(zhuǎn)發(fā)過程中數(shù)據(jù)包的不可預知性以及網(wǎng)絡的高動態(tài)性,設As,d(t)代表t時刻源節(jié)點s在網(wǎng)絡中到達目的節(jié)點d產(chǎn)生的路徑代價,表達式為

(3)

式(3)中:ks,d為路徑中網(wǎng)絡節(jié)點的實際跳數(shù);ω1為的是鏈路代價相應的權(quán)值;ω2為路徑節(jié)點數(shù)對應的權(quán)值;Oi,j(t)為節(jié)點i在t時刻到達網(wǎng)絡節(jié)點j產(chǎn)生的單鏈路代價。

(4)

式(4)中:tout為出隊速度;Zi,j為路徑對應的實際長度;c為數(shù)據(jù)在鏈路中的傳播速度;Wi,j為數(shù)據(jù)隊列對應的長度。

節(jié)點i在t時刻與節(jié)點j之間存在的流量可表示為gi,j(t),針對網(wǎng)絡中存在的物理節(jié)點與虛擬節(jié)點v,所提算法用Dv(t)表示兩者之間的切換狀態(tài),如果參數(shù)Dv(t)的值為1,表明兩者之間未切換,如果參數(shù)Dv(t)的值為零,表明兩者之間完成切換。

所提方法建立的QoS組播路由優(yōu)化模型為

F=minAs,d(t)

(5)

設置模型的約束條件。

條件1鏈路在t時刻的可行流量gi,j(t)需要低于其在網(wǎng)絡中的剩余帶寬Bi,j(t),即

0≤gi,j(t)≤Bi,j(t)

(6)

條件2節(jié)點在網(wǎng)絡中產(chǎn)生的緩存需求需要小于緩存最大值,即

gi,j(t)+Uj(t)≤Bufj

(7)

式(7)中:Uj(t)為t時刻節(jié)點緩存的占用情況;Bufj為節(jié)點在網(wǎng)絡中的緩存大小。

條件3節(jié)點在t時刻不處于切換狀態(tài),即

Di(t)=Dj(t)=1

(8)

1.3 基于遺傳-蟻群優(yōu)化算法的路由優(yōu)化

所提算法結(jié)合蟻群算法與遺傳算法的優(yōu)點,提出遺傳-蟻群算法,求取1.2節(jié)優(yōu)化模型的最優(yōu)解,以此獲得最優(yōu)路由。

(9)

式(9)中:α、χ為啟發(fā)式因子;集合A由可選路徑對應的坐標點構(gòu)成;κi,j(t)為啟發(fā)函數(shù),κi,j(t)=1/di,j,其中di,j為節(jié)點i與j之間存在的路徑。

傳統(tǒng)啟發(fā)函數(shù)沒有考慮螞蟻在優(yōu)化搜索過程中表現(xiàn)出的隨機性,為此,所提算法設置閾值ξ對函數(shù)κi,j(t)展開改進調(diào)整,即

(10)

式(10)中:di=min(di,j)為di,j的最小值。

m只螞蟻開始搜索最優(yōu)路由,獲得相同數(shù)量的坐標點α1={a1,a2,…,al},α2={b1,b2,…,bl},…,αm={m1,m2,…,ml},保存上述集合中存在的最優(yōu)解ybest,并確定其平均值ybave,建立集合B用于存儲優(yōu)于平均值ybave的螞蟻個體。引入遺傳算法對B中存在的坐標展開變異操作與免疫操作[13-14],并對個體的免疫位長度展開調(diào)整,即

(11)

式(11)中:H1(Bi,B)、H2(Bi,B)為免疫函數(shù),第一個函數(shù)中存在較多的免疫位,第二個函數(shù)中存在較少的免疫位;G(Bi)為第i個螞蟻在集合B中的距離值;G表為一次搜索獲得的最優(yōu)解;ζ為設置的閾值。

對個體的變異概率展開調(diào)整,即

(12)

式(12)中:G1為當前解對應的距離值;η為閾值。

完成變異方式的調(diào)整,即

(13)

式(13)中:ν為變異閾值。

用Δτi,j表示螞蟻在搜索路徑時產(chǎn)生的信息素濃度;螞蟻完成全部可行解周游后,更新信息素[15-16],更新公式為

τi,j(t+1)=(1-ρ)τi,j(t)+ρΔτi,j

(14)

式(14)中:參數(shù)ρ用于衡量信息素的揮發(fā)情況。螞蟻在最大迭代次數(shù)內(nèi)輸出的最優(yōu)解即為QoS組播路由優(yōu)化模型的最優(yōu)解,獲得最優(yōu)路由。

所提算法采用遺傳-蟻群算法求解QoS組播路由優(yōu)化模型的具體過程如下。

步驟1對遺傳算法和蟻群算法的參數(shù)展開初始化處理[17-18],并設置算法目前的迭代次數(shù)T與最大迭代次數(shù)Tmax。

步驟2利用式(9)所示的啟發(fā)函數(shù)控制螞蟻搜索路徑,由搜索結(jié)果α1={a1,a2,…,al},α2={b1,b2,…,bl},…,αm={m1,m2,…,ml}構(gòu)成集合S。

步驟3計算m條路徑的ybest與ybave,建立集合B用于存放優(yōu)于平均值B的螞蟻個體。

步驟4利用式(11)～式(13)調(diào)整螞蟻個體的免疫長度、變異概率與變異方式.

步驟5通過式(14)更新螞蟻個體的信息素[19-20],T=T+1。

步驟6設置算法終止條件T>Tmax,如果滿足該條件,進入下一步,如果不滿足該條件返回步驟2。

步驟7輸出QoS組播路由優(yōu)化模型的最優(yōu)解,獲得最優(yōu)路由。

2 實驗與分析

為了驗證基于遺傳-蟻群優(yōu)化算法的QoS組播路由算法的整體有效性,需要對其展開測試,本次測試的網(wǎng)絡結(jié)構(gòu)如圖1所示,網(wǎng)絡參數(shù)如表1所示。

表1 網(wǎng)絡參數(shù)Table 1 Network parameters

1～7為節(jié)點代號圖1 網(wǎng)絡結(jié)構(gòu)Fig.1 Network structure

實驗過程如下。

(1)數(shù)據(jù)采集:使用自適應變頻采集策略收集當前網(wǎng)絡的帶寬、時延、丟包率等關(guān)鍵參數(shù),并對節(jié)點信息進行實時更新,包括節(jié)點的負載情況、處理能力等。

(2)計算路徑代價:根據(jù)采集到的數(shù)據(jù),計算每條路徑的代價,之后,建立QoS組播路由優(yōu)化模型,并設置約束條件。

(3)遺傳-蟻群優(yōu)化算法的實現(xiàn):初始化種群,每個個體代表一條可能的路徑,通過選擇、交叉、變異等操作,生成新的個體。根據(jù)信息素濃度和啟發(fā)式信息,更新個體的路徑選擇概率。持續(xù)迭代優(yōu)化,直至滿足終止條件。

(4)結(jié)果輸出:輸出最優(yōu)路徑及其相關(guān)參數(shù)。

為避免實驗結(jié)果過于單一,將文獻[3]、文獻[5]算法作為對比,分析3種方法的分析3種方法的迭代次數(shù)與路徑長度、時延抖動情況、路徑代價、平均路由請求成功率。

實驗環(huán)境:將節(jié)點1作為源節(jié)點,節(jié)點7作為目的節(jié)點,尋找兩個節(jié)點之間的最優(yōu)路徑。采用所提算法、文獻[3]算法和文獻[5]算法展開最優(yōu)路徑測試,結(jié)果如圖2所示。

1～7為節(jié)點代號圖2 不同算法的最優(yōu)路徑Fig.2 Optimal path of different algorithms

根據(jù)圖2和圖3中的數(shù)據(jù)發(fā)現(xiàn),所提算法在迭代次數(shù)達到10次之前,就可以獲得最短路徑,且最優(yōu)路徑的長度小于其他兩種算法。而文獻[3]、文獻[5]算法分別在迭代次數(shù)達到10次以上、20次以上才可以獲得最短路徑。通過上述測試驗證了所提算法具有較高的搜索效率與路由優(yōu)化效果。這是因為所提算法結(jié)合遺傳算法和蟻群算法的優(yōu)勢,在搜索空間中探索并找到最優(yōu)解。遺傳算法擅長全局搜索,蟻群算法擅長局部搜索,二者結(jié)合能夠在早期迭代中更快地收斂到最優(yōu)解。

圖3 迭代次數(shù)與路徑長度Fig.3 Iteration times and path length

經(jīng)上述算法優(yōu)化后,路徑的時延抖動如圖4所示。分析圖4可知,傳送數(shù)據(jù)包時,所提算法優(yōu)化后的路徑時延抖動小于文獻[3]算法和文獻[5]算法。所提算法的時延抖動范圍在-0.13～0.15 s,文獻[3]算法的時延抖動范圍在-0.41～0.40 s,而文獻[5]算法的時延抖動范圍在-0.44～0.43 s。這是因為所提算法在優(yōu)化QoS組播路由之前通過網(wǎng)絡數(shù)據(jù)采集獲取了網(wǎng)絡與節(jié)點目前的狀態(tài),同時考慮排隊時延和傳輸時延建立QoS組播路由優(yōu)化模型,進而降低了路徑時延抖動。

圖4 不同方法的時延抖動情況Fig.4 Delay jitter situation of different methods

利用式(3)測試所提算法、文獻[3]算法和文獻[5]算法優(yōu)化后節(jié)點1—5、1—7、1—8、1—6的路徑代價,測試結(jié)果如圖5所示。

圖5 路徑代價Fig.5 Path cost

路徑代價越低,表明路由優(yōu)化效果越好,分析徑圖5中的數(shù)據(jù)可知,在不同路徑中所提算法的路代價均低于其他兩種算法。所提算法的路徑代價始終未超過0.3,這是因為所提算法在優(yōu)化過程中將路徑代價最小作為目標,提高了路由優(yōu)化效果。

將平均路由請求成功率作為指標,進一步測試上述算法的路由性能,結(jié)果如表2所示。

表2 平均路由請求成功率Table 2 Average routing request success rate

由表2可知,三種算法的迭代次數(shù)與平均路由請求成功率之間呈正比,表明三種算法在迭代過程中不斷優(yōu)化路由。在相同迭代次數(shù)下,所提算法的平均路由請求成功率最高。整體來看,文獻[3]算法、文獻[5]算法的平均路由請求成功率最大值分別為81.3%、76.9%,而所提算法的平均路由請求成功率始終未低于80.0%,表明所提算法優(yōu)化后的路由具有良好的性能。這是因為所提算法應用自適應變頻采集策略能夠?qū)崟r采集網(wǎng)絡和節(jié)點信息,為路由優(yōu)化提供準確的數(shù)據(jù)支持。準確的數(shù)據(jù)支持有助于算法根據(jù)實際情況作出最佳的路由選擇,從而提高了路由請求成功率。

3 結(jié)論

針對目前路由算法存在的一些問題,提出基于遺傳-蟻群優(yōu)化算法的QoS組播路由算法,該算法根據(jù)網(wǎng)絡和節(jié)點目前的狀態(tài)建立QoS組播路由優(yōu)化模型,結(jié)合蟻群算法和遺傳算法獲得路徑代價最小的最優(yōu)路由,經(jīng)驗證,所提算法具有良好的路由優(yōu)化效果,可有效降低時延抖動,提高路由請求成功率。

在中國日益增長的互聯(lián)網(wǎng)用戶數(shù)量和數(shù)據(jù)流量背景下,穩(wěn)定的網(wǎng)絡傳輸是保障用戶體驗的關(guān)鍵因素,提高路由請求成功率對于確保網(wǎng)絡通信的順暢更是至關(guān)重要,本文算法有助于提供更穩(wěn)定、更可靠的網(wǎng)絡服務,能夠幫助網(wǎng)絡快速響應并滿足用戶的通信需求。