基于遺傳-蟻群優化算法的QoS組播路由算法設計

史鄭延慧, 何剛

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

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

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

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

1 QoS組播路由算法設計

1.1 采集網絡數據

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

步驟1將時間序列作為依據采集網絡數據,傳感器在數據采集與建模期間內不傳輸數據。

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

步驟3計算采集數據的整體誤差,根據計算結果對節點采樣頻率展開調整。

通過回歸模型建模分析節點感知數據,并計算對應的回歸參數,將回歸參數傳輸到網絡的CHN(clearing house net)節點中,以此為依據建立簇內SN節點(業務節點)對應的回歸模型,利用回歸模型預測節點感知的網絡數據。

預測數據變化的一元線性回歸模型為

β′=β+bt

(1)

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

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

(2)

將式(2)計算得到的β、b代入模型[式(1)]中,獲得預測節點采集數據的回歸模型,以此分析網絡與節點狀態。

1.2 QoS組播路由優化模型

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

(3)

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

(4)

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

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

所提方法建立的QoS組播路由優化模型為

F=minAs,d(t)

(5)

設置模型的約束條件。

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

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

(6)

條件2節點在網絡中產生的緩存需求需要小于緩存最大值,即

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

(7)

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

條件3節點在t時刻不處于切換狀態,即

Di(t)=Dj(t)=1

(8)

1.3 基于遺傳-蟻群優化算法的路由優化

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

(9)

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

傳統啟發函數沒有考慮螞蟻在優化搜索過程中表現出的隨機性,為此,所提算法設置閾值ξ對函數κi,j(t)展開改進調整,即

(10)

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

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

(11)

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

對個體的變異概率展開調整,即

(12)

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

完成變異方式的調整,即

(13)

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

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

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

(14)

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

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

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

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

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

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

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

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

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

2 實驗與分析

為了驗證基于遺傳-蟻群優化算法的QoS組播路由算法的整體有效性,需要對其展開測試,本次測試的網絡結構如圖1所示,網絡參數如表1所示。

表1 網絡參數Table 1 Network parameters

1～7為節點代號圖1 網絡結構Fig.1 Network structure

實驗過程如下。

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

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

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

(4)結果輸出:輸出最優路徑及其相關參數。

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

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

1～7為節點代號圖2 不同算法的最優路徑Fig.2 Optimal path of different algorithms

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

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

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

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

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

圖5 路徑代價Fig.5 Path cost

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

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

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

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

3 結論

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

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