基于自適應差分進化算法的時間敏感網(wǎng)絡流量調(diào)度

中圖分類號：TP915 文獻標志碼：A 文章編號：1001-3695（2025）06-032-1838-06

doi：10.19734/j. issn.1001-3695.2024.12.0464

Time-sensitive network traffic scheduling based on adaptive differential evolution algorithm

Zong Chuyu，Xu Fangmin?，Li Bin，Zhao Chenglin （SchoolofInformationamp;CommuicationEnginering，BeijingUniersityofPostsamp;Telecommuications，Beijing10o76，China）

Abstract：Toensure the deterministictransmissonof time-sensitive traffcin TSN，thispaper proposedatraffcscheduling method basedontheadaptivediferentialevolutionalgorithm.Itintroducedthelink-balanceconstraintcondition．Wheninitializingthepopulation，itmonitoredthelinkcongestionsituationtoselectpaths.Themethodadjustedparametersthroughthe adaptivealgorithm tojointlyoptimizepath selectionandtrafficscheduling，achievingtheminimizationof thescheduling completiontime.Experimentalresultsverifiytheefectivenessofthealgorithm.Comparedwithmultiplealgorithms，under different scale traffic，the average scheduling completion time decreasesby 10%～25% .Meanwhile，it improves the network resource utilization. The algorithm shows good adaptability and robustness.

Key words：time-sensitive network（TSN）；traffic scheduling；diferential evolution；path selection

0 引言

在TSN中，流量調(diào)度的有效性和穩(wěn)定性至關重要。作為工業(yè)互聯(lián)網(wǎng)和高精度控制系統(tǒng)的關鍵組成部分，TSN要求設備之間以及設備與網(wǎng)絡基礎設施之間的數(shù)據(jù)傳輸具有嚴格的時間確定性，涉及對時間敏感的數(shù)據(jù)流進行精確的路由和調(diào)度。例如，在自動化生產(chǎn)環(huán)境中，TSN通過精準的時鐘同步和帶寬預留機制，支持實時數(shù)據(jù)的傳輸，有效提高生產(chǎn)效率和產(chǎn)品質(zhì)量。在高精度控制系統(tǒng)中，TSN的低時延特性使得系統(tǒng)能夠及時響應傳感器數(shù)據(jù)，進行精準控制，從而實現(xiàn)對機器人、無人駕駛汽車等設備的高效協(xié)同和控制[1]。此外，TSN的融合技術，如5G與TSN的結(jié)合，已成為實現(xiàn)廣域端到端確定性通信的典型架構(gòu)，促進工業(yè)互聯(lián)網(wǎng)的進一步發(fā)展和深度集成[2]。TSN通過精確時鐘同步、帶寬預留和流量整形等措施，提供低時延、低抖動、低數(shù)據(jù)丟失的可靠傳輸，保障實時應用的可靠性和預測性，推動工業(yè)控制系統(tǒng)的智能化轉(zhuǎn)型與未來自動化技術的發(fā)展[3.4]。流量調(diào)度是保障 TSN 確定性傳輸?shù)年P鍵機制，IEEE802.1Qbv標準[5定義的TAS（timeawareshaper）時間感知整形器對流量調(diào)度業(yè)務進行了標準化。TAS機制通過門控列表（gatecontrollist，GCL）限制時間敏感流量的發(fā)送時間和傳輸時機，避免與其他流量的沖突，從而減少時延、抖動和丟包等不利影響，為時間敏感流提供高質(zhì)量的服務，是TSN主流選擇的整形機制[。近年來，隨著網(wǎng)絡規(guī)模的擴大和流量多樣化需求的增加，多種基于時間感知整形器（TAS）的調(diào)度方法被提出并應用于不同場景[]。Jin等人[8]提出的無等待調(diào)度方法結(jié)合了消息分片和SMT模型，通過提高可調(diào)度性有效緩解了網(wǎng)絡擁塞； Kim 等人[9針對汽車以太網(wǎng)場景基于遺傳算法提出一種調(diào)度方法，以最小化端到端延遲、抖動和帶寬利用率，并通過自動駕駛網(wǎng)絡模擬驗證了其有效性。此外，最新研究開始探索流量調(diào)度與聯(lián)合調(diào)度的結(jié)合。TSN與無線接人融合也成為新的應用場景，Li等人[提出了基于貪心策略的分布式估計算法（GE），為TSN與Wi-Fi融合提供了新思路。Xue等人[1]在評估固定路由和聯(lián)合路由調(diào)度方法后，指出聯(lián)合調(diào)度在資源利用率和全局優(yōu)化方面具有顯著優(yōu)勢。為了提升調(diào)度的動態(tài)適應能力，Pahlevan等人[12]提出了一種啟發(fā)式列表調(diào)度（HLS）算法，盡管其靜態(tài)分配策略在部分場景中展現(xiàn)了較高的效率，但在面對大規(guī)模復雜網(wǎng)絡時，容易陷入局部最優(yōu)，限制了全局性能的進一步優(yōu)化。文獻[13]在HLS基礎上支持多隊列配置與兩種接收抖動模式，進一步優(yōu)化網(wǎng)絡調(diào)度性能。但這些算法局限性在于依賴預設狀態(tài)進行靜態(tài)分配，缺乏動態(tài)調(diào)整機制，容易在大規(guī)模網(wǎng)絡中陷入局部最優(yōu)。因此，針對上述算法容易陷入局部最優(yōu)，難以優(yōu)化全局調(diào)度的問題，本文提出一種基于差分進化算法的時間敏感網(wǎng)絡流量調(diào)度方案。通過動態(tài)調(diào)整變異參數(shù)和自適應優(yōu)化策略，確保在大規(guī)模網(wǎng)絡中聯(lián)合優(yōu)化路徑選擇和調(diào)度時序，進一步縮短總體整體調(diào)度完成時間，即makespan。本文方案能夠在不顯著增加計算復雜度的情況下實現(xiàn)更高效的調(diào)度結(jié)果，具有較強的全局搜索能力和參數(shù)自適應性。

1系統(tǒng)模型

1.1 TAS調(diào)度模型

基于IEEE802.1Q中定義，交換機的每個出端口都有8個優(yōu)先級隊列，其中一個或者多個用于傳輸時間敏感TT（timetriggered）流，剩下的隊列用于傳輸音視頻橋接AVB（audiovideobridging）流和盡力而為BE（besteffort）的流。TSN中每個消息可能包含多個幀。優(yōu)先級過濾器用來存放該出端口暫未傳輸?shù)臄?shù)據(jù)流。經(jīng)過優(yōu)先級識別后的數(shù)據(jù)流進入優(yōu)先級隊列進行緩存[14]。當隊列與出端口連接的門開關打開時，相應隊列中的數(shù)據(jù)流才可以傳輸。

門控列表GCL是TAS調(diào)度中的關鍵組件，定義了何時開啟和關閉交換機隊列中的門以控制流量的傳輸，其包含時間間隔和隊列狀態(tài)兩個參數(shù)。時間間隔決定了門控配置的持續(xù)時間。例如，某個數(shù)據(jù)流可能需要每隔一定時間就被調(diào)度一次，在周期內(nèi)為其分配固定的時隙片即可。隊列狀態(tài)有0（open）和C（close）兩種。當門控的狀態(tài)為O時，門開啟，可以從此隊列中選擇數(shù)據(jù)幀進行傳輸；當門控的狀態(tài)為C時，門關閉，不能從此隊列中選擇數(shù)據(jù)幀進行傳輸。門控列表根據(jù)GCL定義的時間間隔和門控周期進行狀態(tài)切換。TAS會根據(jù)門控周期以及GCL進行周期重復的控制。通過此機制，可以為周期性的敏感流創(chuàng)建一條獨享的無沖突通道。如圖1所示：有task1和task2兩個待調(diào)度TT流，優(yōu)先級task1 gt; task2，在TO時段僅打開隊列7，傳輸task1；在T1時段僅打開隊列6，傳輸task2；在T2時段打開剩余隊列，傳輸其他AVB和BE流量。

1.2完全集中式模型

IEEE 802.10cc 標準[15]中定義了TSN完全集中式控制配置模型，如圖2所示，該配置模型的核心是網(wǎng)絡控制器。該架構(gòu)由集中式網(wǎng)絡控制器（centralizednetworkcontroller，CNC）和集中式用戶配置控制器（centralizedusercontroller，CUC）以及TSN交換機組成，形成一個高效的集中式管理系統(tǒng)。CUC位于架構(gòu)的最上層，負責與用戶和應用層交互，完成拓撲展示、交換機基礎配置和用戶管理等核心功能。CUC通過UNI/RESTfulAPI接口將從用戶和應用層收集的實時性需求、帶寬需求等信息傳遞至CNC。CNC是架構(gòu)的核心組件，負責全局的流量調(diào)度和資源分配。CNC主要包含以下模塊：拓撲發(fā)現(xiàn)、調(diào)度策略、配置下發(fā)等。CNC通過實時監(jiān)控網(wǎng)絡拓撲和流量狀態(tài)，制定全局流量調(diào)度和資源分配方案，生成GCL配置。生成的調(diào)度方案包括鏈路信息、優(yōu)先級隊列、偏移時隙、門控周期等多個參數(shù)。這些調(diào)度配置通過NETCONF協(xié)議精準下發(fā)至各TSN交換機，實現(xiàn)端到端的實時數(shù)據(jù)傳輸和資源優(yōu)化。在復雜TSN中，采用這種集中式管控的方式能夠有效應對復雜的多流量傳輸需求，確保TSN的高效運行和實時性保障。

1.3 網(wǎng)絡模型

考慮將時間敏感網(wǎng)絡抽象為一個有向圖 G=（V，E） ，其中V表示網(wǎng)絡節(jié)點集合，包括 TSN交換機SW={sw，sw，，sw_m∣ 和終端設備 S ={ 2 }表示物理鏈路集合，由于TSN建立在全雙工以太網(wǎng)之上，所以節(jié)點 V_a 與 V_b 間的物理鏈路對應兩條單向鏈路 和 。

系統(tǒng)中待調(diào)度的流量集用 F 表示， F={f₁，f₂，f₃，…，f_n} ，每個流量 f_i 用七元組來表示：

f_i={f_i-src，f_i-dest，f_i-T，f_i-L，f_i-ddl，f_i-path，f_i-offset}

其中 ?：f_i-src，f_i-dest 分別表示流 f_i 的源節(jié)點和目的節(jié)點 ;f_i-T 表示流的周期性 ;f_iL 為每個數(shù)據(jù)包的大小 Ω_Jiddl 表示最大端到端時延 σ?f_i-path 為流量的路徑 表示流量的注入時間。

2 時間敏感網(wǎng)絡流量調(diào)度問題

2.1 問題建模

TSN流量調(diào)度是一個NP-hard問題，大規(guī)模組網(wǎng)流量調(diào)度問題的目的是計算GCL調(diào)度表[7]。調(diào)度算法的輸入是：網(wǎng)絡拓撲和一系列的時間敏感流（包括流的源節(jié)點、目的節(jié)點、周期、流的幀長和截止時間），輸出是這一系列時間敏感流注人網(wǎng)絡的時間 f_i-offset 和路徑選擇 f_i-path ，通過這兩個參數(shù)可以確定各網(wǎng)絡設備GCL調(diào)度表。時間敏感流的信息、端設備和交換機處理能力以及路由拓撲由基于IEEE802.1Qcc標準的TSN控制器集中采集。在CNC中完成路由選擇和流量調(diào)度算法的實現(xiàn)，計算出時間敏感流的門控列表并輸出。

本文針對這一問題，通過聯(lián)合路由和流量調(diào)度的方式，為待調(diào)度流量計算出最優(yōu)路徑選擇方案和注入時間，從空間和時間兩個維度避免鏈路擁塞，最小化整體調(diào)度完成時間，即最小化所有實時流傳輸完成時刻的最大值。

對于每個流 f∈F ，其傳輸完成的時間點由流量的注入時間和時延共同決定，時延由路徑上所有鏈路的傳輸時延和處理時延累積計算得到，即式（2）所示。

其中： t_trans（f，l） 表示流的傳輸時延； t_proc（l） 表示鏈路的處理時延。整體調(diào)度完成時間是所有流傳輸完成時間的最大值，即max_f∈Ft_f^fnish ，由此可以得到優(yōu)化目標如式（3）所示。

為保證計算出來的GCL滿足TSN的確定性低時延要求，即時間敏感流在其傳輸周期內(nèi)進行無鏈路爭用的超低延時傳

輸，調(diào)度算法需要滿足以下流量調(diào)度約束和路由約束條件。

2.1.1流量調(diào)度約束

1）幀約束對于待調(diào)度流量的每個幀 f_im 在每段鏈路[V_a，V_b] 要求在周期內(nèi)完成傳輸，并且滿足開始傳輸時間非負，所以對 ?f_i∈F，l∈f_ipath 有

其中 ?f_im 表示流量 f_i 的第 ?_m 個幀； T_start（f_im，l） 表示當前幀在鏈路 l 的開始傳輸時間。

2）鏈路約束在同一鏈路 l 上，任意兩幀的傳輸實例不能在時間上重疊，以防止出現(xiàn)傳輸沖突。設幀 f_im 和 f_jn 在鏈路 ξ_l 上的傳輸時間區(qū)間分別為 T_start（f_im，l） ， T_end（f_im，l）] 和[ T_start 表示當前幀在鏈路 ξ_l 的結(jié)束傳輸時間。對 ?f_im≠f_jn 有

3）流傳輸約束規(guī)定幀通過路徑每條鏈路的時序，即幀在鏈路 ξ_l 上傳輸?shù)慕Y(jié)束時間應小于等于在下一鏈路 l^′ 上的傳輸開始時間，數(shù)學表達式為

T_start（f_im，l^′）?T_start（f_im，l）+t_trans（f_im，l）+t_proc（l）+δ

其中：δ表示時鐘同步誤差。

4）端到端時延約束端到端延時為消息最后一幀到達接收端的時刻與第1幀在發(fā)送端傳輸開始時刻之間的時間間隔。對于每個流量 f_i ，其發(fā)送的幀數(shù) ，其在路徑上的傳輸時延總和不超過其最大允許的延遲 f_i-dd ，數(shù)學表達式為

若滿足時延約束，則當前流是可調(diào)度的；反之，是不可調(diào)度的。

5）幀隔離約束每個流量可能會經(jīng)過多個節(jié)點和隊列傳輸。當多個流量通過同一個隊列時，可能會引起隊列資源的競爭，進而影響幀傳輸?shù)臅r序準確性，甚至導致傳輸延遲超出要求。因此，為了避免這種情況，要求在同一時刻，1條隊列中只能存儲來自1條流的幀。設隊列 q 在時間 χ_t 上的狀態(tài)為 Q（q，t） 則任意兩個來自不同流量的幀 f_im 和 f_jn ，對于 ?t，?q∈[0，7] 有

即對于隊列 q 在 χ_t 時刻存儲幀 f_im ，則同一時刻當前隊列不會在存儲其他流量的數(shù)據(jù)幀。

2.1.2 路由約束

1）有效路徑約束確保所有待調(diào)度流量在網(wǎng)絡中的傳輸路徑必須符合網(wǎng)絡的拓撲結(jié)構(gòu)。要求路徑上的每一對相鄰節(jié)點必須實際存在于網(wǎng)絡拓撲中且有效連接，并且流的源節(jié)點和目的節(jié)點之間存在至少一條完整、連通的路徑。對 ?f_i 有

2）無環(huán)約束環(huán)路的出現(xiàn)可能導致數(shù)據(jù)在網(wǎng)絡中不斷循環(huán)，增加不必要的延遲和資源消耗，甚至可能導致傳輸失敗。因此在傳輸過程中，路徑 不能形成環(huán)路，即對 ?f_i ，對于任意節(jié)點 V_k∈f_i-path ，不允許存在以下條件

?V_k∈f_i-paths.t.（V_k，V_k）∈f_i-path

3）鏈路最大負載約束所選路徑中每條鏈路的負載不得超過其最大承載能力（帶寬上限），以避免鏈路過載，即對 ?f_i 對于任意鏈路 l∈f_i-path 有：

其中： 表示鏈路 ξ_l 的負載； B 是鏈路的帶寬上線。

4）鏈路均衡約束為避免某些鏈路過度負載，進一步提高網(wǎng)絡的資源利用率和系統(tǒng)的穩(wěn)定性，設計負載均衡約束條

件，對 n 條鏈路有

其中： σ_max 是負載標準差的最大容許值。

2.2 算法設計

差分進化算法是一種具有高效全局尋優(yōu)能力的進化算法，它通過進化算子的迭代來進行全局尋優(yōu)，包括變異、交叉和選擇，具有收斂快、控制參數(shù)少且設置簡單、優(yōu)化結(jié)果穩(wěn)健等優(yōu)點[16]。自適應差分進化（adaptive differential evolution，ADE）算法在此基礎上，通過引入自適應參數(shù)調(diào)整策略，提高搜索效率和收斂性能。本文采取ADE算法解決大規(guī)模時間敏感網(wǎng)絡流量調(diào)度問題，通過動態(tài)調(diào)整算法參數(shù)來應對網(wǎng)絡拓撲和流量需求的多變性。

第一步：種群初始化，流程如圖3所示。首先初始化種群P={X₁，X₂，…，X_n} ，每個個體 X_k 代表一個流量調(diào)度方案，包括所有流量的路徑選擇和注入時隙的分配。在CNC數(shù)據(jù)庫中，存儲著所有流量的完整簡單無環(huán)路徑。注人時隙根據(jù)路徑選擇后計算，以確保滿足端到端時延要求和鏈路的幀隔離性。初始化時生成包含隨機個體和優(yōu)秀個體的混合種群，優(yōu)秀個體基于任務優(yōu)先級和鏈路擁塞程度生成。隨機個體通過隨機路徑分配生成。將總種群大小定義為 N ，并根據(jù)設置的優(yōu)秀個體比例 α 來分配優(yōu)秀個體和隨機個體的數(shù)量：

優(yōu)秀個體通過考慮流量優(yōu)先級和鏈路擁塞信息生成，確保在種群中有高質(zhì)量的個體，為后續(xù)迭代提供良好起點。優(yōu)秀個體的選取規(guī)則：對于每條鏈路 ξ_l，ξ 記錄其當前的流量負載link_load[l]=0 ，根據(jù)式（14）對流集中待調(diào)度流量排序。

按照優(yōu)先級排序后的任務列表，依次為每個任務分配擁塞最少的路徑。并實時更新鏈路擁塞程度：

第二步：參數(shù)自適應調(diào)整。在每輪迭代開始時，基于其當前的適應度值動態(tài)調(diào)整變異因子 F 和交叉概率 CR 。若個體成功變異，增加 F ，擴大差分搜索步長；若個體優(yōu)于種群平均效果，增大 CR ，讓當前個體更多地繼承變異向量的特征。具體調(diào)整過程見算法1中偽代碼。

算法1差分進化參數(shù)自適應調(diào)整策略

輸人：種群大小population_size;最大迭代次數(shù)max_iter;縮放因子 F 初始列表 F_? _values;交叉概率 CR ;初始列表 CR_. _values輸出：更新的 F_? _values和 設置 F_? _values初始值為0.5；設置 CR _values初始值為 0.8 根據(jù)式（3）計算當前種群中個體的適應度fitness[i]。判斷個體是否成功變異，根據(jù)式（16）調(diào)整縮放因子 F 判斷個體與種群平均水平大小，根據(jù)式（17）調(diào)整交叉概率 CR （204a）重復步驟c）d）至population_size。b）重復步驟b）至max_iter。c）得到最佳 F values和 CR _values

第三步：變異操作。通過變異操作更新個體中流量 f_i 的路徑索引，探索新的路徑選擇，如式（18）所示。其中task_routes （f_i） 表示當前流量可選路徑的全部數(shù)量，通過取模運算保證路徑索引值在有效范圍內(nèi)。對于每個目標個體 X_k ，從種群中隨機選擇三個不同的個體 X_r，X_s，X_t ，其中 r≠s≠t≠k ，生成變異向量 V_k 。使用縮放因子 F 控制變異幅度。

第四步：交叉操作。生成的變異向量 V_k 與原個體 X_k 進行交叉，形成實驗向量 U_k 。對于個體中的每個流量 f_i 進行式（19）中的操作，其中 CR 是交叉概率，控制從變異向量繼承路徑的比例。

第五步：個體選擇。如果實驗向量的適應度優(yōu)于原個體，則用其替換原個體。采用目標函數(shù)式（3）計算適應度。

第六步：循環(huán)迭代與終止條件。重復執(zhí)行變異、交叉、選擇和參數(shù)調(diào)整，直到達到最大代數(shù)或滿足收斂條件。輸出使得makespan最小化的最佳調(diào)度方案。

當前算法的完整流程如圖4所示。算法實現(xiàn)路徑選擇和流量調(diào)度的時間復雜度主要受到種群大小和最大迭代次數(shù)的影響。隨著種群規(guī)模 N 和迭代次數(shù) T 的增加，算法的搜索空間得以擴展，優(yōu)化的可能性也隨之提高，但同時帶來了更高的時間復雜度。此時算法的時間復雜度為 O（NT） 。因此，為平衡算法的收斂性與計算效率，在實際應用中需要合理設置種群大小和迭代次數(shù)，以確保優(yōu)化效果的同時控制時間復雜度。

3仿真設計與結(jié)果分析

3.1 實驗設計

實驗仿真環(huán)境采用Python編碼實現(xiàn)，運行基于本地計算機和GPU加速的配置。計算機的硬件配置為 CoreTMi5-8300HCPU （8核），內(nèi)存 16GB 。實驗中的計算部分在NVIDIARTX2080TiGPU上運行，以提升算法的并行計算性能并加速模型收斂。

實驗中的網(wǎng)絡拓撲采用擴展星型拓撲結(jié)構(gòu)，以確保拓撲的連通性和復雜性，如圖5所示。拓撲生成使用Erdos-Renyi（ER）[17]模型構(gòu)建骨干網(wǎng)絡，為每個交換機隨機創(chuàng)建互連的骨干拓撲。在每個交換機節(jié)點周圍生成星型子網(wǎng)絡，使每個交換機與多個終端設備相連。連接結(jié)構(gòu)記錄在鄰接矩陣net中，其中每條邊包括鏈路的隊列數(shù)量、數(shù)據(jù)傳輸速率等網(wǎng)絡屬性。生成的拓撲結(jié)構(gòu)被保存為.csv文件，后續(xù)作為算法的輸入。

在流集構(gòu)建部分，隨機生成不同規(guī)模負載的時間敏感流，包括每條流量的源節(jié)點、目的節(jié)點、數(shù)據(jù)大小、周期、截止時間等屬性。函數(shù)通過預設參數(shù)選擇列表生成流集。周期從集合 中隨機生成，數(shù)據(jù)大小從集合 {100，200 300} Byte中隨機生成，截止時間參數(shù)通過路徑跳數(shù)、數(shù)據(jù)大小及延遲范圍生成，以模擬真實網(wǎng)絡的多樣化需求。同時，通過端口利用率限制控制每個終端設備的流量負載不超過0.75，為待調(diào)度流量確定節(jié)點，以保證流量的合理性和拓撲的連通性。生成的流集保存為.csv文件，作為算法的另一輸入。

實驗通過以上兩個.csv文件將流量和拓撲信息輸人集中式控制器，CNC完成聯(lián)合路由和流量調(diào)度的計算并存人數(shù)據(jù)庫，借助基于Web的交互式界面展示生成的模型和調(diào)度解決方案，包括路由圖和調(diào)度時間表。

3.2 結(jié)果分析

3.2.1ADE與傳統(tǒng)DE算法在不同參數(shù)下的性能對比

為了評估自適應差分進化算法（ADE）在時間敏感網(wǎng)絡流量調(diào)度中的性能表現(xiàn)，并驗證其相較于傳統(tǒng)差分進化算法（DE）的改進效果，實驗著重分析了迭代次數(shù)和種群大小這兩個關鍵參數(shù)對調(diào)度結(jié)果的影響。迭代次數(shù)決定了算法探索解空間的深度，而種群大小則直接影響了解空間的覆蓋范圍和算法的多樣性。

首先驗證迭代次數(shù)對算法性能的影響，將最小化整體調(diào)度完成時間（makespan）作為優(yōu)化目標。參數(shù)設置種群大小為30，迭代次數(shù)為 0～200 。傳統(tǒng)DE算法設置縮放因子初始值為0.5，交叉概率初始值為0.8。實驗在統(tǒng)一的條件下，采用圖5所示的網(wǎng)絡拓撲結(jié)構(gòu)進行測試，該拓撲包含10個交換機和30個終端設備節(jié)點，通過42條全雙工物理鏈路連接。在流集規(guī)模固定為100的情況下，分析迭代次數(shù)這一參數(shù)對ADE與DE調(diào)度效果的影響，并對比兩個算法的收斂性能。

實驗結(jié)果如圖6所示，橫坐標為迭代次數(shù)0＼～200，縱坐標為makespan值。ADE在前25次迭代內(nèi)迅速收斂，makespan從初始值降至穩(wěn)定的較低水平；而DE在前50次迭代內(nèi)僅出現(xiàn)較小的優(yōu)化。曲線明顯看出ADE的求解情況普遍比DE更加優(yōu)秀，這是因為在相同的迭代次數(shù)下ADE由于采用了混合初始種群提供了更好的初始解，并且在自適應調(diào)整參數(shù)策略下向最優(yōu)解迭代的速度也同步提高。圖中數(shù)據(jù)顯示ADE的makes-pan穩(wěn)定在約 71.60μs ，而DE為 74.93μs ，相比之下，ADE降低了約 4.44% 。當?shù)螖?shù)超過100后，ADE的優(yōu)化效果不再明顯，表明進一步增加迭代次數(shù)對結(jié)果提升有限。在第85次迭代后基本收斂，優(yōu)化過程平穩(wěn)，驗證了自適應參數(shù)調(diào)整機制有效加速了算法收斂，避免了迭代波動。

接下來驗證種群大小這一參數(shù)對兩種算法調(diào)度效果的影響。實驗使用圖5中的拓撲和規(guī)模為100的流集作為算法輸入，設置種群大小為10＼～50，以10為步長增加，對比ADE和DE兩個算法的調(diào)度效果和運行時間進行比較。

實驗結(jié)果如圖7所示。ADE算法在不同種群大小（10、20、30、40、50）下，makespan隨種群規(guī)模增加逐步降低，表明種群規(guī)模的增大會提升解空間探索能力，從而優(yōu)化調(diào)度性能。相比之下，DE的makespan變化較小，且整體高于ADE，尤其在種群大小為30和50時表現(xiàn)出明顯劣勢。這說明ADE在TSN調(diào)度中的適應性和優(yōu)化能力更強。由于算法時間復雜度為O（N×T） （其中 N 為種群規(guī)模， T 為迭代次數(shù)），兩種算法的運行時間均隨種群規(guī)模線性增長。種群從10增加到50時，ADE運行時間由 961.961ms 增至 4620.352ms ，而DE運行時間相對較低，增長趨勢更平緩。可以看出，ADE在優(yōu)化調(diào)度質(zhì)量的同時，計算開銷有所增加，可能在實際應用中面臨復雜度較大的局限性。為此，可考慮采用并行化設計來降低計算成本。

3.2.2多種調(diào)度算法在不同流量規(guī)模下的性能比較

為進一步驗證本文算法的有效性，將本文算法與DE和文獻[12，13]在不同規(guī)模時間敏感網(wǎng)絡下進行對比，設計實驗流量數(shù)量以50作為起點，50為步長，逐漸增加到 ⁴⁰⁰ 。在達到400個流量時，HLS首次出現(xiàn)調(diào)度不成功的情況。對比四個算法調(diào)度結(jié)果的makespan值。

從圖8實驗結(jié)果可以看出，ADE下相對增速較緩，尤其在流量增加到200以上時，增長趨勢比另外兩條曲線明顯放緩，表現(xiàn)出較好的適應性。DE的makespan增長略高于ADE，但依舊保持在相對穩(wěn)定的范圍內(nèi)。而HLS由于采用啟發(fā)式列表調(diào)度，該方式在處理大規(guī)模流量時，難以全面考量網(wǎng)絡復雜因素，易陷入局部最優(yōu)。實驗結(jié)果表現(xiàn)為HLS的makespan隨流量增加顯著上升，尤其在數(shù)量增加到250和300時延急劇增長，達到 292.4μs ，明顯高其他三種算法。當流數(shù)量達到400時，HLS無法尋找到可行解，調(diào)度失敗。HERMES啟發(fā)式多隊列調(diào)度器的設計在小流量時能憑借其多隊列調(diào)度機制維持穩(wěn)定性能，但未充分考慮到大規(guī)模流量場景下的復雜情況，導致在流量增長時無法有效利用網(wǎng)絡資源。隨著流量的增加達到300時，makespan增長幅度明顯高于ADE，在高負載場景下顯示出較差的擴展性和適應性。根據(jù)圖上數(shù)據(jù)顯示，同流量負載規(guī)模下，ADE比HLS平均優(yōu)化了約 25.37% ，比HLS平均優(yōu)化了接近 10% ?？梢缘贸鯝DE的路徑選擇和自適應參數(shù)調(diào)整使其能夠在大規(guī)模流量場景下保持更優(yōu)的調(diào)度效果這一結(jié)論。

3.2.3ADE算法適應性驗證

進一步驗證所提算法在多場景中的適用性和魯棒性，設計實驗驗證算法在不同拓撲結(jié)構(gòu)和不同流量集下的表現(xiàn)。實驗分別選取了不同類型流量的流集以及多種典型的網(wǎng)絡拓撲結(jié)構(gòu)，通過與其他調(diào)度算法性能的對比，驗證所提算法的適應性。

首先獲取10組基本參數(shù)設置不同的流集，保持拓撲結(jié)構(gòu)不變，每組固定流集規(guī)模為100，將其分別輸入到各算法中進行調(diào)度，對比結(jié)果。差分進化的兩個算法的種群數(shù)量設置為30，最大迭代次數(shù)設置為100。實驗結(jié)果顯示如圖9所示，ADE算法在調(diào)度性能和穩(wěn)定性上均優(yōu)于DE和 HLS 。

分別計算這10組數(shù)據(jù)的平均值和標準差，結(jié)果見表1。ADE在10組流量中的平均makespan為 63640.0ns ，標準差為5151.9ns，性能最優(yōu)且波動最小，展現(xiàn)出當前算法在不同流量條件下具有較高的穩(wěn)定性。相比之下，DE的平均makespan為68640.0ns ，標準差為5283.0ns，穩(wěn)定性稍遜于ADE。HLS的平均makespan最高，為 77040.0ns ，且標準差達到 7517.9ns 離散性最大，在調(diào)度上表現(xiàn)不穩(wěn)定。

為探究拓撲結(jié)構(gòu)類型對算法的影響，進行實驗，比較多種調(diào)度算法在不同網(wǎng)絡拓撲結(jié)構(gòu)下的調(diào)度性能。實驗選擇了四種常見的拓撲結(jié)構(gòu)進行測試：直線拓撲（line）、環(huán)型拓撲（ring）樹型拓撲（tree）和網(wǎng)格拓撲（mesh），如表2所示。在每種拓撲下各算法對同一流集進行流量調(diào)度，并記錄每種算法的調(diào)度完成時間（即makespan），評估算法在不同拓撲結(jié)構(gòu)下的表現(xiàn)差異。

實驗結(jié)果如圖10所示，可以看出，啟發(fā)式調(diào)度算法在處理簡單的拓撲結(jié)構(gòu)（如直線拓撲）時表現(xiàn)較好，而ADE在處理更復雜的網(wǎng)絡結(jié)構(gòu)（如環(huán)型拓撲、樹型拓撲和網(wǎng)格拓撲）時更具優(yōu)勢。取四種拓撲結(jié)構(gòu)下各算法的平均值，可以發(fā)現(xiàn)ADE的調(diào)度時長表現(xiàn)出最低的均值，顯示了其在多種拓撲場景下的普適性和強大的調(diào)度能力，尤其在復雜拓撲中能夠有效減少調(diào)度時間。ADE可以有效解決處理大規(guī)模和復雜網(wǎng)絡的理想選擇，能夠在多樣化的應用場景中保持較為優(yōu)秀的表現(xiàn)。同時，HERMES能夠保持較小的波動，表現(xiàn)出較高的穩(wěn)定性。

4結(jié)束語

本文基于自適應差分進化算法提出的聯(lián)合路由和流量調(diào)度方法，有效提高了調(diào)度效率和資源利用率，尤其在高流量負載環(huán)境下，展現(xiàn)出更優(yōu)的調(diào)度性能。算法以整體調(diào)度完成時間為優(yōu)化目標，對比了傳統(tǒng)差分進化算法和兩種啟發(fā)式列表方法，結(jié)果顯示ADE在路徑選擇及參數(shù)動態(tài)調(diào)整方面具備顯著優(yōu)勢，能夠更好地適應負載變化，優(yōu)化調(diào)度延遲并減小系統(tǒng)開銷，驗證了其在復雜網(wǎng)絡環(huán)境中的擴展性和適應性。

未來工作將致力于探索復雜環(huán)境中多類型混合流量的調(diào)度問題，包括音視頻流量與非時間敏感流量的路由與調(diào)度，以實現(xiàn)更廣泛的工業(yè)場景應用。

參考文獻：

[1]Zhu Libin， Zhao Hongchen，Xu Wenchen，et al.Research on automotive TSN network scheduling analysis and simulation[C]//Proc of the 2nd International Conference on Electrical Engineering，Big Data and Algorithms.Piscataway，NJ： IEEE Press，2023：1267-1270.

[2]Sasiain J，F(xiàn)ranco D，Atutxa A，et al.Toward the integration and convergence between 5G and TSN technologies and architectures for industrial communications：a survey[J].IEEE Communications Surveysamp; Tutorials，2025，27（1） ：259-321.

[3]Xu Chi，Yu Haibin，JinXi，etal.Industrial Internet forintelligent manufacturing： past， present，and future [J]. Frontiers of Information Technologyamp; Electronic Engineering，2024，25（9）：1173-1192.

[4]黃韜，汪碩，黃玉棟，等．確定性網(wǎng)絡研究綜述［J]．通信學報， 2019，40（6）： 160-176.（Huang Tao，Wang Shuo，Huang Yudong， etal.Survey of the deterministic network[J].Journal on Communications，2019，40（6）：160-176.）

[5]Jefree T. IEEE 802.1 Qbv，Enhancements for scheduled traffic [S].Piscataway，NJ： IEEE Press，2016.

[6]張彤，馮佳琦，馬延瀅，等．時間敏感網(wǎng)絡流量調(diào)度綜述［J]. 計算機研究與發(fā)展，2022，59（4）：747-764.（Zhang Tong，F(xiàn)eng Jiaqi，Ma Yanying，et al. Survey on traffc scheduling in timesensitive networking[J].Journal of Computer Research and Development，2022，59（4）：747-764.）

[7] Stuber T， Osswald L，Lindner S，et al.A survey of scheduling algorithms for the time-aware shaper in time-sensitive networking（TSN） [J]．IEEE Access，2023，11：61192-61233.

[8]Jin Xi， Xia Changqing，Guan Nan，et al.Joint algorithmof message fragmentation and no-wait scheduling for time-sensitive networks [J]. IEEE/CAA Journal of Automatica Sinica，2021，8（2）： 478-490.

[9] KimHJ ，Lee K C，Kim M H，et al. Optimal scheduling of timesensitivenetworks for automotive Ethernet based on genetic algorithm [J].Electronics，2022，11（6）：article No.926.

[10]Li Zhong，Yang Jianfeng，Guo Chengcheng，et al.A joint scheduling scheme for Wi-Fi access TSN[J]. Sensors，2024，24（8）：article No. 2554.

[11]Xue Chuanyu，Zhang Tianyu，Zhou Yuanbin，et al．Real-time scheduling for 8O2.1 Qbv time-sensitive networking（TSN）：a systematic review and experimental study[C]//Proc of the 3Oth RealTime and Embedded Technology and Applications Symposium.Piscataway，NJ：IEEE Press，2024：108-121.

[12]Pahlevan M ，Tabassam N，Obermaisser R.Heuristic list scheduler fortime triggered traffic in time sensitive networks[J].ACM SIGBED Review，2019，16（1）：15-20.

[13]Bujosa D，Ashjaei M，Papadopoulos AV，et al.HERMES：heuristic multi-queue scheduler for TSN time-triggered traffc with zero reception jitter capabilities[C]//Proc of the 3Oth International Conference on Real-Time Networks and Systems.New York：ACM Press， 2022： 70- 80.

[14]Doh H W，Ryoo JD，Cheung T，et al.Ranking scheduling precedence of time-sensitive networking traffics for IEEE 802.1 Qbv [C]//Proc of the13th International Conference on Information and Communication Technology Convergence.Piscataway，NJ：IEEE Press，2022：2225-2230.

[15]IEEE GET Program. IEEESTD.2018.8514112， IEEE Standard for Local and Metropolitan Area Networks--Bridges and Bridged Networks --Amendment 31： stream reservation protocol （SRP） enhancements and performance improvements[S].Piscataway，NJ： IEEE Press，2018.

[16]Bujok P，Tvrdik J，Polakov? R.Adaptive differential evolution vs. nature-inspired algorithms：an experimental comparison[C]//Proc ofIEEESymposium SeriesonComputational Inteligence. Piscataway，NJ： IEEE Press， 2017：1-8.

[17]Erdos P，Renyi A. On the evolution of random graphs[J].Transactions of the American Mathematical Society，1960，5：17-61.