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

1系統(tǒng)模型

1.1 TAS調(diào)度模型

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

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

1.2完全集中式模型

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

1.3 網(wǎng)絡(luò)模型

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

系統(tǒng)中待調(diào)度的流量集用 F 表示， F={f₁，f₂，f₃，…，f_n} ，每個(gè)流量 f_i 用七元組來(lá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é)點(diǎn)和目的節(jié)點(diǎn) ;f_i-T 表示流的周期性 ;f_iL 為每個(gè)數(shù)據(jù)包的大小 Ω_Jiddl 表示最大端到端時(shí)延 σ?f_i-path 為流量的路徑 表示流量的注入時(shí)間。

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

2.1 問題建模

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

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

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

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

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

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

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

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

其中 ?f_im 表示流量 f_i 的第 ?_m 個(gè)幀； T_start（f_im，l） 表示當(dāng)前幀在鏈路 l 的開始傳輸時(shí)間。

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

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

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

其中：δ表示時(shí)鐘同步誤差。

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

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

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

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

2.1.2 路由約束

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

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

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

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

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

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

件，對(duì) n 條鏈路有

其中： σ_max 是負(fù)載標(biāo)準(zhǔn)差的最大容許值。

2.2 算法設(shè)計(jì)

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

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

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

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

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

算法1差分進(jìn)化參數(shù)自適應(yīng)調(diào)整策略

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

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

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

第五步：個(gè)體選擇。如果實(shí)驗(yàn)向量的適應(yīng)度優(yōu)于原個(gè)體，則用其替換原個(gè)體。采用目標(biāo)函數(shù)式（3）計(jì)算適應(yīng)度。

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

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

3仿真設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

實(shí)驗(yàn)中的網(wǎng)絡(luò)拓?fù)洳捎脭U(kuò)展星型拓?fù)浣Y(jié)構(gòu)，以確保拓?fù)涞倪B通性和復(fù)雜性，如圖5所示。拓?fù)渖墒褂肊rdos-Renyi（ER）[17]模型構(gòu)建骨干網(wǎng)絡(luò)，為每個(gè)交換機(jī)隨機(jī)創(chuàng)建互連的骨干拓?fù)洹Ｔ诿總€(gè)交換機(jī)節(jié)點(diǎn)周圍生成星型子網(wǎng)絡(luò)，使每個(gè)交換機(jī)與多個(gè)終端設(shè)備相連。連接結(jié)構(gòu)記錄在鄰接矩陣net中，其中每條邊包括鏈路的隊(duì)列數(shù)量、數(shù)據(jù)傳輸速率等網(wǎng)絡(luò)屬性。生成的拓?fù)浣Y(jié)構(gòu)被保存為.csv文件，后續(xù)作為算法的輸入。

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

實(shí)驗(yàn)通過(guò)以上兩個(gè).csv文件將流量和拓?fù)湫畔⑤斎思惺娇刂破鳎珻NC完成聯(lián)合路由和流量調(diào)度的計(jì)算并存人數(shù)據(jù)庫(kù)，借助基于Web的交互式界面展示生成的模型和調(diào)度解決方案，包括路由圖和調(diào)度時(shí)間表。

3.2 結(jié)果分析

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

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

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

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

接下來(lái)驗(yàn)證種群大小這一參數(shù)對(duì)兩種算法調(diào)度效果的影響。實(shí)驗(yàn)使用圖5中的拓?fù)浜鸵?guī)模為100的流集作為算法輸入，設(shè)置種群大小為10＼～50，以10為步長(zhǎng)增加，對(duì)比ADE和DE兩個(gè)算法的調(diào)度效果和運(yùn)行時(shí)間進(jìn)行比較。

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

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

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

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

3.2.3ADE算法適應(yīng)性驗(yàn)證

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

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

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

為探究拓?fù)浣Y(jié)構(gòu)類型對(duì)算法的影響，進(jìn)行實(shí)驗(yàn)，比較多種調(diào)度算法在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的調(diào)度性能。實(shí)驗(yàn)選擇了四種常見的拓?fù)浣Y(jié)構(gòu)進(jìn)行測(cè)試：直線拓?fù)洌╨ine）、環(huán)型拓?fù)洌╮ing）樹型拓?fù)洌╰ree）和網(wǎng)格拓?fù)洌╩esh），如表2所示。在每種拓?fù)湎赂魉惴▽?duì)同一流集進(jìn)行流量調(diào)度，并記錄每種算法的調(diào)度完成時(shí)間（即makespan），評(píng)估算法在不同拓?fù)浣Y(jié)構(gòu)下的表現(xiàn)差異。

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

4結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

[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)絡(luò)研究綜述［J]．通信學(xué)報(bào)， 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]張彤，馮佳琦，馬延瀅，等．時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度綜述［J]. 計(jì)算機(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.