面向6G承載網(wǎng)的路由優(yōu)化算法研究

張冬月，韓賽，王光全，王澤林，劉暢

（中國聯(lián)合網(wǎng)絡(luò)通信有限公司研究院，北京 100048）

0 引言

隨著5G 商用落地，5G 技術(shù)成功地滲透到各行各業(yè)，實(shí)現(xiàn)了峰值速率、時(shí)延、網(wǎng)絡(luò)能效等方面的顯著提升[1]。6G 作為未來移動通信技術(shù)演進(jìn)的方向，將呈現(xiàn)大量沉浸化、智慧化、全域化的新型業(yè)務(wù)，如無人駕駛、擴(kuò)展現(xiàn)實(shí)（XR,Extended Reality）、感官互聯(lián)等[2-3]。因此，對6G 網(wǎng)絡(luò)的數(shù)據(jù)傳輸速率、網(wǎng)絡(luò)時(shí)延以及連接密度提出了更高的要求與挑戰(zhàn)[4]。6G 相對于5G，其性能指標(biāo)將提升10～100 倍，尤其在時(shí)延性能方面，6G 對端到端時(shí)延的要求是小于0.1 ms[5]，在6G 時(shí)代將會面臨實(shí)時(shí)海量數(shù)據(jù)的傳輸，數(shù)據(jù)的暴增將帶來大量的擁塞和數(shù)據(jù)分組時(shí)延。承載網(wǎng)作為支撐6G 新型業(yè)務(wù)的重要基礎(chǔ)，超低時(shí)延特性將會對承載網(wǎng)提出新的需求?？紤]到空口、核心網(wǎng)等處理時(shí)延，6G 業(yè)務(wù)對承載網(wǎng)絡(luò)傳輸時(shí)延的要求將更加嚴(yán)苛。

為滿足6G 網(wǎng)絡(luò)對承載網(wǎng)超低時(shí)延的要求，需要對現(xiàn)有的IP 路由轉(zhuǎn)發(fā)策略進(jìn)行優(yōu)化，在現(xiàn)網(wǎng)中IP 鏈路的metric 值用于指示網(wǎng)絡(luò)設(shè)備之間傳輸數(shù)據(jù)的代價(jià)，是路由算法用以確定到達(dá)目的地的最佳路徑的計(jì)量標(biāo)準(zhǔn)，作為路由轉(zhuǎn)發(fā)的關(guān)鍵參數(shù)，其設(shè)置結(jié)果至關(guān)重要[6]，直接影響了IP 路由轉(zhuǎn)發(fā)的效率以及網(wǎng)絡(luò)時(shí)延。傳統(tǒng)的metric 設(shè)置方式主要是網(wǎng)絡(luò)專家根據(jù)專家經(jīng)驗(yàn)進(jìn)行人工設(shè)定，嘗試方案少，無法確定其為最優(yōu)方案，存在局限性大、部分IP 鏈路時(shí)延過高、無法滿足6G 超低時(shí)延場景等問題，因此亟需智能化手段來解決上述問題。

伴隨著AI 的蓬勃發(fā)展，AI 技術(shù)與6G 的深度融合作為實(shí)現(xiàn)內(nèi)生智能新型網(wǎng)絡(luò)的重要基礎(chǔ)，將驅(qū)動智慧網(wǎng)絡(luò)不斷升級[5]。目前路由優(yōu)化領(lǐng)域的研究主要有：基于有監(jiān)督學(xué)習(xí)的路由優(yōu)化方法[7-10]，利用監(jiān)督學(xué)習(xí)模型提取流量特征，預(yù)測未來流量，獲取最佳路由策略，或者利用監(jiān)督學(xué)習(xí)模型直接學(xué)習(xí)路徑的研究；基于強(qiáng)化學(xué)習(xí)的路由優(yōu)化算法[11-14]；基于啟發(fā)式算法的路由優(yōu)化算法[15-17]等，但尚未有針對metric 設(shè)計(jì)方法的研究。

針對以上問題，本文提出了一種面向6G 承載網(wǎng)的基于k-means[18]和粒子群優(yōu)化算法（PSO,Particle Swarm Optimization）[19]的路由優(yōu)化算法，可實(shí)現(xiàn)在有效范圍內(nèi)大規(guī)模搜索最優(yōu)方案，克服人工方案的局限性。該算法采用k-means 算法對IP 鏈路進(jìn)行聚類分析，可有效縮小PSO 粒子搜索范圍，提高粒子搜索效率；使用PSO 算法找出最優(yōu)的metric 方案。本算法通過在網(wǎng)絡(luò)仿真平臺[20]上進(jìn)行測試，驗(yàn)證了算法的有效性。

1 基于k-means和PSO的路由優(yōu)化算法

1.1 數(shù)據(jù)

本文采用的數(shù)據(jù)為國際IP 鏈路，每個(gè)IP 鏈路的特征包括：發(fā)送端城市的經(jīng)度、發(fā)送端城市的緯度、發(fā)送端路由的角色、接收端城市的經(jīng)度、接收端城市的緯度、接收端路由的角色、鏈路的時(shí)延、鏈路當(dāng)前的metric 值、鏈路帶寬、是否跨國。其中，路由的角色包括AR、CR 等，不同的角色代表不同的作用。

1.2 路由優(yōu)化算法

本文提出的路由優(yōu)化算法是基于k-means 算法和PSO 算法。k-means 算法是一種經(jīng)典的聚類算法。該算法主要是將樣本按照樣本距離聚集到k個(gè)簇中，最終實(shí)現(xiàn)簇內(nèi)距離小、簇間距離大；PSO 算法是模擬鳥群覓食行為的啟發(fā)式算法，通過鳥群之間的集體協(xié)作使群體獲得最優(yōu)解。具體流程如圖1 所示，主要包括以下兩個(gè)步驟：

圖1 PSO路由優(yōu)化算法流程圖

（1）為縮小PSO 粒子搜索范圍，提高粒子搜索效率，本文采用k-means 算法對IP 鏈路進(jìn)行聚類分析。

（2）使用PSO 算法找出最優(yōu)的metric 方案。

具體流程如下：

（1）采用k-means 算法對IP 鏈路進(jìn)行聚類分析，過程如下：

1）輸入數(shù)據(jù)和參數(shù)，設(shè)置k-means 算法的簇?cái)?shù)K=10。如果（源設(shè)備）國內(nèi)-＞（目的設(shè)備）國外跨國/（源設(shè)備）國外-＞（目的設(shè)備）國內(nèi)跨國：是否跨國設(shè)置為20 000，否則設(shè)置為0。

2）對輸入數(shù)據(jù)做歸一化處理，采用最大最小歸一化（MinMaxScaler）方法，利用數(shù)據(jù)列中的最大值和最小值進(jìn)行標(biāo)準(zhǔn)化處理，標(biāo)準(zhǔn)化后的數(shù)值范圍為[0,1]，計(jì)算方式為數(shù)據(jù)與該列的最小值作差，再除以極差。

3）隨機(jī)選擇K個(gè)點(diǎn)作為點(diǎn)的聚類中心，這表示要將數(shù)據(jù)分為K類。

4）遍歷所有的點(diǎn)P，算出P到每個(gè)聚類中心的距離，此距離采用歐氏距離，將P放到最近的聚類中心的點(diǎn)集中，遍歷結(jié)束后將得到K個(gè)點(diǎn)集。

5）遍歷每一個(gè)點(diǎn)集，算出每一個(gè)點(diǎn)集的中心位置，將其作為新的聚類中心。

6）重復(fù)4）和5），直到聚類中心位置不再移動。

聚類結(jié)果將IP 鏈路分為10 組，根據(jù)組內(nèi)IP 鏈路的原始metric 值的范圍，為每一組的IP 鏈路設(shè)置相同的metric范圍，此取值范圍用于PSO 算法中粒子更新范圍上限和下限的設(shè)置。10 組鏈路的metric 范圍具體如表1 所示：

表1 IP鏈路的metric范圍

（2）根據(jù)聚類結(jié)果對PSO 進(jìn)行參數(shù)設(shè)置，使用PSO 找出最優(yōu)的metric 方案，算法中的每一個(gè)粒子代表一種metric 方案，過程如下：

1）輸入?yún)?shù)：維數(shù)dim設(shè)置為82；粒子的數(shù)量pop設(shè)置為40；粒子搜索的下限lb、粒子搜索的上限ub（設(shè)置方法根據(jù)聚類結(jié)果）；慣性權(quán)重w設(shè)置為0.8；學(xué)習(xí)因子c1和c2均設(shè)置為0.5。

2）初始化粒子群體（群體規(guī)模為pop），包括隨機(jī)位置和速度。

3）根據(jù)損失函數(shù)計(jì)算每個(gè)粒子的損失，該算法的損失函數(shù)為當(dāng)前粒子在網(wǎng)絡(luò)仿真平臺上的全網(wǎng)平均時(shí)延。

4）對于每個(gè)粒子，將其當(dāng)前損失與個(gè)體歷史最佳位置對應(yīng)的損失做比較，如果當(dāng)前的損失更小，則將用當(dāng)前位置更新歷史最佳位置pbest。

5）對于每個(gè)粒子，將其當(dāng)前損失與全局最佳位置對應(yīng)的損失做比較，如果當(dāng)前的損失更小，則將用當(dāng)前粒子的位置更新全局最佳位置gbest。

6）更新每個(gè)粒子的速度與位置，粒子i的第d維速度更新公式為：

其中：

r1、r2：兩個(gè)隨機(jī)函數(shù)，取值范圍為[0,1]，以增加隨機(jī)性；

w：慣性權(quán)重，非負(fù)數(shù)，調(diào)節(jié)對解空間的搜索范圍；

c1、c2：加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長（超參數(shù)）。

粒子i的第d維位置更新公式為：

7）如果沒有滿足結(jié)束條件，則返回3），結(jié)束條件為損失在多次迭代后沒有發(fā)生變化。

1.3 實(shí)驗(yàn)結(jié)果

根據(jù)以上方法，獲得的最優(yōu)metric 方案如表2 所示。由于鏈路較多，本文只展示部分實(shí)驗(yàn)結(jié)果。

表2 部分IP鏈路的metric結(jié)果

本文使用IP 網(wǎng)絡(luò)仿真平臺對metric 方案進(jìn)行驗(yàn)證，此平臺針對IP 數(shù)據(jù)網(wǎng)進(jìn)行路由仿真，涉及IGP/BGP/MPLS 等IP 層面的規(guī)劃設(shè)計(jì)，包括對路由協(xié)議、路徑以及流量的仿真。

本方案在網(wǎng)絡(luò)仿真平臺運(yùn)行結(jié)果顯示：本方案全網(wǎng)平均時(shí)延為174.841 ms，原始的metric 方案的平均時(shí)延為180.975 ms，相對于原始的方案平均時(shí)延降低了3.39%。

2 結(jié)束語

本文研究如何在6G 網(wǎng)絡(luò)超低時(shí)延的要求下有效提升IP 承載網(wǎng)路由轉(zhuǎn)發(fā)效率，結(jié)合人工智能技術(shù)，提出了一種基于k-means 和PSO 的IP 路由優(yōu)化算法。通過k-means算法對現(xiàn)有的IP 鏈路的metric 值進(jìn)行聚類，根據(jù)聚類結(jié)果使用PSO 算法尋找最優(yōu)的metric 組合方案，可進(jìn)一步提升路由轉(zhuǎn)發(fā)效率，最終實(shí)現(xiàn)降低全網(wǎng)業(yè)務(wù)傳輸時(shí)延。通過仿真實(shí)驗(yàn)表明，該算法可以有效降低IP 承載網(wǎng)業(yè)務(wù)傳輸時(shí)延，提高IP 承載網(wǎng)業(yè)務(wù)傳輸效率。