陸以勤 黃成海 陳嘉睿 王海瀚 覃健誠 方婷

（1.華南理工大學 電子與信息學院，廣東 廣州 510640；2.華南理工大學 信息網(wǎng)絡工程研究中心，廣東 廣州 510640；3.華南理工大學 微電子學院，廣東 廣州 511442）

隨著現(xiàn)代網(wǎng)絡（如智能駕駛車載網(wǎng)、工業(yè)互聯(lián)網(wǎng)和5G通信等場景）的快速發(fā)展，越來越多的數(shù)據(jù)采集節(jié)點和計算節(jié)點導致網(wǎng)絡設計復雜化和通信鏈路上大量的數(shù)據(jù)負載。目前，雖然以太網(wǎng)具備了高帶寬的要求以及各種專用設備的無縫連接，但并不提供實時的時間敏感功能，如低抖動、低網(wǎng)絡延時以及高效帶寬分配等功能。而低延時的實時確定性傳輸功能是網(wǎng)絡物理系統(tǒng)必不可少的，現(xiàn)存的工業(yè)和車載網(wǎng)絡由于不能互通而增加了網(wǎng)絡結構的復雜性。IEEE802.1 工作組開發(fā)的TSN（時間敏感網(wǎng)絡）標準協(xié)議［1］作為涵蓋確定性網(wǎng)絡不同方面的標準，包括提高可靠性、延遲控制、時間同步和資源管理，希望以統(tǒng)一的網(wǎng)絡結構解決現(xiàn)代網(wǎng)絡中關鍵型任務應用程序的嚴格時間限制問題。

時間敏感網(wǎng)絡的核心基本組件包括時間同步、流量調度、流量整形、路由策略以及冗余預留和容錯機制等。其中，TSN流量調度機制定義了門控列表（GCL）表示隊列門在每個時刻的狀態(tài)，要求數(shù)據(jù)鏈路在嚴格的時間同步條件下將時間劃分為時隙，通過GCL讓時間敏感流的每一幀都在計劃時隙內進行無爭用通信。求解合成GCL要求調度算法根據(jù)不同網(wǎng)絡拓撲以及流量模型計算出符合調度約束的調度方案，這類似裝箱問題［2］，是NP難問題，尤其是當需要考慮到流的路由和流量聯(lián)合調度的多跳網(wǎng)絡時。當前求解流量調度的數(shù)學優(yōu)化方法主要有可滿足性模理論（SMT）和優(yōu)化模理論（OMT）、啟發(fā)式算法和元啟發(fā)式算法、整數(shù)線性規(guī)劃（ILP）。文獻［3］是最早在時間觸發(fā)以太網(wǎng)（TTE）中，針對多跳網(wǎng)絡利用SMT求解器來綜合路由和調度的研究之一；而在TSN離線調度規(guī)劃中，文獻［4］在采用SMT尋找滿足調度和時間約束的解決方案的同時，使用OMT指定最小化所使用隊列的數(shù)量作為優(yōu)化目標；一種基于時間感知整形器（TAS）的實時自適應門控調度方案在文獻［5］中提出，它將調度問題表述為布爾可滿足性問題（SAT），并提出采用基于現(xiàn)場可編程門陣列（FPGA）的求解器實現(xiàn)運行時快速計算。它們是TSN尋找可行GCL的主要研究方向，但缺點是具有較高的算法復雜度，特別是當它們應用于具有路由規(guī)劃和調度綜合的大規(guī)模網(wǎng)絡模型時。與前面的求解方法相比，文獻［6］和［7］分別采用啟發(fā)式列表調度（HLS）和元啟發(fā)式遺傳算法，基于無等待方法［8］進行路由和調度約束聯(lián)合調度。使用同為元啟發(fā)式算法的禁忌搜索進行無等待的時間敏感流調度也在文獻［8］中提出。他們都采用具有更低算法復雜度的流量調度方法，但大都是基于無等待的方法進行調度計算，求解空間有所減小，實際應用效率低。

本研究建立在GCL 調度部署的網(wǎng)絡管理基礎上，其相關的協(xié)議主要有IEEE 802.1Qbv增強型流量調度和以IEEE 802.1Qcc為背景的集中管理機制。TSN 中的網(wǎng)絡管理需要針對GCL 進行部署，因此IEEE 802.1Qbv 標準［9］描述了以時分多址技術（TDMA）為基本原理的TAS。GCL除了要保證數(shù)據(jù)無爭用傳輸之外，還需要實現(xiàn)關鍵流量的低延時零抖動傳輸以及遵從時間敏感網(wǎng)絡的調度約束。文獻［4］基于TSN關鍵參數(shù)進行離線推導約束，以此保證關鍵通信流的低抖動和端到端確定時延，但是這種方法忽略了由于多個流選擇相同路徑帶來的負載不平衡。而考慮流的各種路徑來確定優(yōu)化調度方案極其困難，因此低復雜度算法對其十分重要，如貪婪隨機自適應搜索算法［10］、遺傳算法［11］等調度方法，均為尋求更低復雜度的GCL計算方案。

此外，IEEE 802.1Qbv 的另一個重要機制是保護帶，其在隊列關閉之前一定時間內限制數(shù)據(jù)包的傳輸，以防止與傳輸槽關聯(lián)的流量延遲分配給后續(xù)傳輸窗口導致關鍵流的數(shù)據(jù)傳輸未完成而延遲。但是保護帶是一個不能傳輸流量的時間間隔，存在帶寬浪費的現(xiàn)象，因此有關文獻［12］采用基于大小的隊列（SBQ）提高帶寬利用率。在運行時重構TAS 方面，文獻［13］中提出了一種包含自適應帶寬共享（ABS）和自適應槽位窗口（ASW）機制。文獻［14］提出了一種方法，它可以根據(jù)需求動態(tài)地重新配置具有時間感知能力的整形器，該方法采用TSN集中式網(wǎng)絡和分布式用戶混合模型進行控制。上述文獻均以較高復雜度的算法進行精確解的計算，忽視了采用犧牲部分精度降低算法復雜度的元啟發(fā)式算法。

針對上述TSN調度中存在的問題，本文設計了一種性能更優(yōu)的路由優(yōu)化遺傳算法Routing-GA。Routing-GA 綜合考慮算法的收斂速度、適應度函數(shù)設計、實時路由約束和可擴展性等因素，通過設計針對TSN流量調度問題的遺傳算法編碼、交叉和變異機制，在嚴格遵守TSN調度約束的同時解決現(xiàn)存大規(guī)模路由與約束聯(lián)合調度問題。本文第1節(jié)簡要介紹時間敏感網(wǎng)絡相關機制；第2節(jié)詳述調度系統(tǒng)以及調度約束公式化表述；第3節(jié)提出低復雜度的Routing-GA，詳述流狀態(tài)編碼的算法結構設計及建模，并分析相對于傳統(tǒng)遺傳算法的種群初始化和交叉變異過程的優(yōu)化；最后在第4節(jié)驗證算法的相關性能。

1 時間敏感網(wǎng)絡

TSN 由一系列IEEE 802.1Q［1］標準提供支持，目的是確保滿足時間要求，但實際的具體功能特性依賴于應用的需求。本文主要研究TSN中基于GCL調度部署的網(wǎng)絡管理，其相關的協(xié)議主要有IEEE 802.1Qbv增強型流量調度和以IEEE 802.1Qcc為背景的集中管理機制。另外，時間敏感網(wǎng)絡的調度約束也是關注的重點，下文會對他們進行簡要介紹。

1.1 時間感知整形器

本文采用TAS 結構框圖，具體如圖1 所示。時間同步技術的精度和效率直接影響TAS 的功能和TSN 的性能，因此TAS 設備需要IEEE 802.1AS 提供時間同步工作機制支持。時間感知整形器會劃分時隙，并將已定義的8個分組隊列綁定設備對應的傳輸端口。接著在對應隊列的端口傳輸中，為了保證無爭用數(shù)據(jù)傳輸，即避免對來自其他隊列的數(shù)據(jù)包的干擾，802.1Qbv 引入了門控機制，相當于給每個隊列出口安裝了開關，并且為不同隊列分配不重疊的傳輸時隙。當門狀態(tài)為1時，隊列數(shù)據(jù)從對應端口中輸出；相反地，當門狀態(tài)變?yōu)?時，數(shù)據(jù)停止從隊列中輸出。而門在對應時刻的開啟和關閉由GCL決定，TAS會根據(jù)門控周期以及GCL進行周期重復的控制。

圖1 時間感知整形器結構框圖［14］Fig.1 Structure of time-aware shaper［14］

本文提出的Routing-GA 支持由IEEE 802.1Qbv定義的流量調度增強部分功能，通過輸出GCL來控制設備端口在指定的時隙內選擇所輸出的隊列。如圖1（引用文獻［14］的結構圖）中GCL 所示，T3時刻“1000 0000”表示隊列門控0 打開，數(shù)據(jù)從端口傳輸，隊列門控1-7關閉。本文提出的調度方法支持由IEEE 802.1Qbv流量調度增強功能。

1.2 集中網(wǎng)絡配置和集中用戶配置

為了對復雜的TSN功能進行配置，以保證預期的服務質量（QoS），IEEE 802.1Qcc 定義的集中用戶配置（CUC）和支持NETCONF 或RESTCONF 協(xié)議的集中網(wǎng)絡配置（CNC）為本文提供集中管理機制支持，類似軟件定義網(wǎng)絡（SDN）的方式［15］，如圖2（引用文獻［16］的框架圖）所示的集中式管理框架。CUC 給關鍵應用程序提供時間敏感流的注冊服務，收集流的周期、長度、發(fā)送和接收節(jié)點、最大時延等信息，并通過用戶網(wǎng)絡接口（UNI）與CNC 進行新設備注冊交換信息。CNC負責計算和配置GCL，當在大規(guī)模的網(wǎng)絡模型中進行動態(tài)調度時，要求其核心的調度方案計算方法具有較低的時間復雜度以應對嚴格的實時要求。

圖2 集中管理框架［16］Fig.2 Centralized management framework［16］

集中管理還需要能保證流確定性的TSN 交換機，要求具備支持IEEE 802.1Qbv 門控制機制、IEEE 802.1AS 時間同步協(xié)議以及NETCONF［17］或者OPC-UA 統(tǒng)一架構等能力。集中式管理機制對比分布式方法在TSN流量或網(wǎng)絡配置發(fā)生變化時具有更高的靈活性和效率，因為集中管理的計算和部署GCL或者自動配置機制都必須要求獲得流和整個網(wǎng)絡的信息。

2 時間敏感流量調度問題

2.1 時間敏感流量調度系統(tǒng)

在前面所提的時間感知整形器以及集中式配置機制的基礎上，本文提出TSN調度系統(tǒng)?？梢哉J為TSN流量調度是一個NP難問題［4］，時間敏感的流信息、端設備和交換機處理能力以及路由拓撲由基于IEEE802.1Qcc標準的TSN控制器集中采集。如圖3所示，主要對輸入網(wǎng)絡拓撲節(jié)點能力以及流信息進行處理，可以采用精確求解或啟發(fā)式算法等方法，計算輸出時間敏感流的門控列表。

圖3 時間敏感流量調度處理過程Fig.3 Time-sensitive traffic scheduling process

TSN是建立在全雙工的以太網(wǎng)基礎上的，鏈路[na，nb]可由一個三元組定義：

其分別代表鏈路帶寬、傳播速率以及出端口隊列數(shù)。

時間敏感流可以由一個六元組定義：

其分別代表發(fā)送節(jié)點、接收節(jié)點、最大所能容忍的抖動時延、最大端到端時延、周期以及每周期所發(fā)送的數(shù)據(jù)量。

最后輸出的結果可以定義三元組表示：

流量調度算法負責保證計算得出的門控列表方案在滿足第1節(jié)調度約束的前提下，所有實例幀無沖突地傳輸，并盡可能優(yōu)化端到端時延等傳輸指標。

2.2 時間敏感流量調度約束

為保證計算出來的GCL滿足TSN的確定性低時延要求，即時間敏感流在其傳輸周期內進行無鏈路爭用的超低延時傳輸，調度算法需要滿足以下的約束條件。

（1）幀約束。針對每一段鏈路[na，nb]，保證對于每個幀必須在其對應周期內完成傳輸，即在一個周期內的最遲開始傳輸時間小于的周期減去對應鏈路所需的傳輸時長。數(shù)學表達如下：

（2）鏈路約束。對于任意兩個需要通過同一段鏈路[na，nb]的幀和，要求其在超周期Thyper時域上沒有重合，也就是幀的傳輸需要提供其獨占鏈路的時間。

α、β為整數(shù)，且，Thyper為所有流周期的最小公倍數(shù)，稱為超周期。Tx、Ty分別為流x和流y的周期。

（3）流傳輸約束。同一個幀在通過其路徑上的不同鏈路段時，需要按照鏈路段的物理連接次序依次進行傳輸。也就是幀fij開始在[nx′，nb]鏈路段傳輸?shù)臅r間要求大于fij在前一段鏈路[na，nx′]傳輸結束的時間。而fij在對應鏈路段[na，nx′]傳輸結束的時間等于fij在該鏈路段的開始傳輸時間Φij加上幀傳輸時長tij、處理時長tp，ax′、時鐘的最大誤差tsyn。具體如下所示：

（4）端到端約束。該約束表示對于每一個流Fi的最大端到端時延小于其最大能容忍的端到端時延De2e，i，也就是該流的最后一幀到達接收端的時間與第1幀開始傳輸?shù)臅r間之差小于De2e，i：

式中，LMTU為一個MTU 的數(shù)據(jù)量，為流i每次發(fā)送的幀數(shù)。

（5）幀隔離約束。當同個隊列的幀同時到達交換機節(jié)點的時候會出現(xiàn)幀交織，或者傳輸途中出現(xiàn)幀缺失而導致調度的時隙出現(xiàn)偏差。因為TSN調度需要引入幀隔離約束以避免上述情況，所以幀隔離要求同一個隊列在同一時刻只能存儲一條流的幀，也就是需要當一個幀離開隊列時，另外一個幀才可以進入隊列，但是如果兩個幀分別在不同的隊列當中就沒有此約束：

（6）抖動約束。實際與理想狀態(tài)的傳輸以及處理總時延差不能大于其所能容忍的最大抖動時延：

其中，Di為理想狀態(tài)下流i從發(fā)送端到接收端前一個節(jié)點之前的總傳輸、傳播和處理時延，Wi為理想狀態(tài)下流i的總等待時延。

2.3 時間敏感流量路由約束

時間敏感網(wǎng)絡流量調度中，路由約束指的是網(wǎng)絡流量在傳輸過程中必須滿足的約束條件。這些約束條件通常包括以下幾個方面。

（1）拓撲約束。每個實例幀在網(wǎng)絡中傳輸?shù)墓?jié)點必須在拓撲中有連接。針對每個幀fij的傳輸路由中的任意節(jié)點na，其下一個目標節(jié)點ηija等于nb的條件是[na，nb]∈ri。即

（2）無環(huán)約束。指定流的傳輸路徑不能形成環(huán)路，以避免數(shù)據(jù)包重復傳輸和死鎖等問題?？梢缘葍r為對于每個幀fij傳輸路由中任意兩個節(jié)點na、nb的下一個目標節(jié)點ηija、ηijb不相等，具體而言，可以通過以下公式表達無環(huán)約束：

（3）路由約束。該約束確保從源節(jié)點到終節(jié)點找到完整且連接的路徑。假設幀fij在節(jié)點na時的下一個目標節(jié)點ηija為nb，且nb不是終節(jié)點，那么必定存在與nb相連的節(jié)點及鏈路[nb，nx]：

（4）鏈路負載約束。保證交換機間傳輸時間敏感流所占用的鏈路負載不會小于某個閾值，防止帶寬資源被過度占用，從而導致網(wǎng)絡擁塞和性能下降：

3 基于遺傳算法的時間敏感流量調度算法

本文提出一種模擬生物進化的隨機搜索算法Routing-GA用于計算調度方案。遺傳算法在文獻［7］的工作中被證實可以很好地解決時間敏感網(wǎng)絡中的調度問題，但是其難點在于遺傳算法問題建模。這需要在同時考慮調度的性能和質量情況下，為不同的復雜問題找到最優(yōu)或近似最優(yōu)解。

3.1 遺傳算法的實現(xiàn)

本文根據(jù)時間敏感網(wǎng)絡調度問題的特性，設計對應的編碼、群體初始化、交叉、變異，以最小端到端時延為優(yōu)化目標：

式中，C為流的總數(shù)量。嚴格遵守TSN 中路由和調度約束，尋找近似最優(yōu)解。Routing-GA的個體代表一個調度方案，也可以體現(xiàn)為一個超周期內的GCL門控表。而該個體是由一系列基因組成的，每個基因對應每個時間敏感任務流當前所處的節(jié)點位置。根據(jù)調度約束要求，每個個體可以計算出一個描述個體素質的適應度值，該適應度體現(xiàn)為端到端時延。同時，為了創(chuàng)造新的個體，Routing-GA提供不依賴第三方庫的交叉、變異方法來進行配對和進化種群中的個體。并且為了優(yōu)化種群，采用基于適應度的評價和替換方法，使子代中適應度較好的個體取代父代中的劣勢個體。

具體的生成流程如圖4所示。圖中實線為傳統(tǒng)GA 的迭代流程，虛線為本文提出的路由優(yōu)化Routing-GA。具體步驟如下：

圖4 遺傳算法實現(xiàn)流程圖Fig.4 Flow chart of genetic algorithm

步驟1設置遺傳算法的參數(shù)，參數(shù)包含種群數(shù)量、交叉概率、變異概率以及最大迭代次數(shù)。另外以端到端時延為適應度值，通過1.2節(jié)中集中式網(wǎng)絡管理機制進行流量以及網(wǎng)絡拓撲信息采集。每當流量或者網(wǎng)絡拓撲發(fā)生變化時，通過該管理機制能及時更新算法相關參數(shù)，并調整個體基因以保證算法的正常迭代。

步驟2進行種群初始化，采用隨機和路由優(yōu)化組合方式生成初始種群。

步驟3對群體進行變異和交叉操作，并按照適應度值的優(yōu)勝劣汰原則篩選種群中的個體。

步驟4經(jīng)過一定次數(shù)的迭代后，輸出最小端到端時延的調度方案。圖5 所示為按照9 節(jié)點網(wǎng)格拓撲隨機5 條時間敏感流調度結果的時間窗示例。圖例中f1 包括f1.0-f1.1 所有超周期內的流，以此類推?？筛鶕?jù)調度規(guī)模以及求解時間要求適當調整算法的基本參數(shù)，以得到最理想解。

圖5 調度時間窗示例Fig.5 An example of schedule window

基于上述流程，本文所提出的調度方法采用的初始化、交叉和變異算子能有效加速算法的收斂過程，并在一定的時間內找到近最優(yōu)解。因此，該方案具有低算法復雜度、高性能、高靈活性等優(yōu)點。Routing-GA的核心機制將在如下詳述。

3.2 基因編碼

如圖6 所示，本文定義TSN 時間表在染色體中的編碼為一個二維數(shù)組。數(shù)組的橫坐標的作用是記錄流的單步前進的次序，例如當從τi′到τi′+1時，F(xiàn)0到Fm中只變化其中一個流的位置，代表其中一條流的某一步驟前進一步。數(shù)組的縱坐標為流的編號，記為Fi，代表第i條流。而二維數(shù)組上的元素代表的是Fi流在所有流總步數(shù)中第τi′步所處的節(jié)點位置，記為si，i′。通過這樣一個二維數(shù)組記錄個體，把每個步驟次序中各個流所在的節(jié)點位置作為基因，這樣既可以充分記錄個體路由和流約束的聯(lián)合調度方案，又能夠降低適應度計算函數(shù)的時間復雜度。計算適應度函數(shù)時僅需按照個體基因逐步計算對應滿足TSN調度約束的可行時間窗，并采用貪心算法計算出最早開始傳輸?shù)臅r間。假設約束計算與現(xiàn)有研究的時間復雜度相同且忽略不計，則本文采用貪心算法計算填充時間窗的時間復雜度為O（n）。另外，該編碼方式在遺傳算法的核心步驟交叉、變異中約束限制較小，操作方便，降低了交叉和變異的時間復雜度。在本例中，算法僅假設每個流都有一個接收端。但在多播流的情況下，只需將流拆分為多個以同個節(jié)點為起點但不同節(jié)點為終點的流分開單獨進行基因的編碼即可。

圖6 編碼方式Fig.6 Encoding method

基于上述的基因編碼方式，個體對應的適應度函數(shù)可以直接體現(xiàn)為調度方案的端到端時延，即算法采取一個個體基因對應一個調度方案，因此算法在優(yōu)化迭代的過程中任意一個個體均是可行解，能準確且實時地反映出流量調度過程中的時延。當輸入時間敏感流或網(wǎng)絡拓撲發(fā)生變化時，對應生成的基因編碼也會隨之變化，不影響算法的迭代搜索功能。另外，采用該方式僅需起始節(jié)點和終止節(jié)點就可根據(jù)網(wǎng)絡拓撲進行調度方案的編碼生成，可以應用于TSN流量調度中分布式遺傳算法的計算，具有高拓展性。與現(xiàn)有在TSN領域的遺傳算法相比，它還可以不受路由長度影響，即不同長度的個體基因仍可以比較方便地進行交叉和變異操作。

3.3 種群初始化

種群的初始化對遺傳算法全局搜索效率和優(yōu)化收斂速度具有十分重要的影響，而基于遺傳算法的車間調度方法［18］在許多工作中被證明是很好的，因此參考文獻［11］中采用的車間調度算法，本文種群的初始化采用隨機和路由優(yōu)化聯(lián)合生成的方法，在符合TSN約束要求的條件下生成可以保證初始群體的多樣性和合法性。

具體的初始化流程如圖7所示，步驟如下。

圖7 初始化過程Fig.7 Initialization procedure

步驟1隨機初始化根據(jù)每一個流的發(fā)送端和接收端遍歷兩點之間的所有可行路由。

步驟2計算每個流所選路由的笛卡爾積，也就是各個流選擇路由的組合。

步驟3從中選出算法所需初始化的種群數(shù)量即可，無需完全遍歷笛卡爾積。驗證生成的個體是否符合約束，若符合則生成對應的個體基因，否則丟棄。

路由優(yōu)化初始化會對每個鏈路中的負載數(shù)據(jù)量進行累加，選出最大負載鏈路負載值并與路由總長度進行加權和，從中選擇最小的個體作為種群的初始化成員：

式中，L(ri)為ri的長度，為節(jié)點na與nb間的傳輸速率。

隨機和路由優(yōu)化組合初始化方式在保證種群的隨機多樣同時，確保種群中具有較好適應度的個體作為收斂的參考方向，減少無效搜索的幾率，大大提高了算法的迭代效率。

3.4 交叉

遺傳算法中的交叉運算是借鑒達爾文的進化論以及孟德爾的遺傳定律的原理，也是控制搜索的核心支撐之一。按照前面所提出的編碼方式，本文開發(fā)出對應的隨機交叉和路由優(yōu)化的組合交叉互換機制。由于TSN 流量調度問題的復雜性，不同個體的基因長度可能不同，這是因為每個流可選的路由之間長度可能不同，本文提出的編碼方式可對任意滿足條件的基因進行交叉，無需額外對不同長度的基因進行處理，提高了交叉機制的效率，具體步驟如下。

步驟1根據(jù)預先設置的交叉幾率判斷對應個體是否發(fā)生交叉。

步驟2若發(fā)生交叉，則交叉機制會進行比較，求出兩個父代個體中基因的交集，并隨機選出其中的一段基因作為交叉的參考基因。如圖8所示，假設ai，i′、bi，i′分別是父代A 和B 的基因元素，交叉開始時會查找父代中相同基因段，如圖8中虛線框所示，ai，i′=bi，i′=si，i′。這個基因代表的是父母中有完全相同的一個時刻，這個時刻父母個體的所有時間敏感流對應其所在節(jié)點的位置相同。

圖8 基因交叉Fig.8 Gene crossing

步驟3如圖8 中所示的交換示例，算法將父母個體中以此基因作為分界的前后所有基因進行交叉互換。

步驟4判斷交叉后子代基因的路由是否使鏈路最大數(shù)據(jù)負載量增加以及路由長度增加，若增加則放棄對應子代；否則保留該子代并添加到群體當中。

步驟5交換操作完成之后判斷個體基因是否重復出現(xiàn)和是否符合TSN流量調度約束，若出現(xiàn)以上情況則舍棄該新個體基因。

本文提出的路由優(yōu)化的交叉機制在隨機交叉的基礎上約束子代基因的鏈路負載均衡度。該操作降低了交叉機制搜索無效解的幾率，提高了算法求解效率。本文所提出的交換機制不依賴第三方的交叉算子庫，并且解決了遺傳算法在TSN流量調度領域由于基因長度不同而引起的交叉算法復雜度較高等問題。交叉之后既可以保證了個體的可行性，又提高了交叉算法的搜索效率。

3.5 變異

為了避免局部最優(yōu)收斂，遺傳算法的變異機制可以使某個染色體段突變，從而產(chǎn)生新的個體。這有助于搜索最優(yōu)解的時候跳出局部最優(yōu)解，提供僅靠交叉無法搜索到的解，達到全局最優(yōu)或似最優(yōu)。

圖9 所示是本文開發(fā)的變異示例。具體步驟如下：

圖9 基因變異Fig.9 Gene mutation

步驟1根據(jù)預設定的變異幾率，判斷個體是否發(fā)生基因變異；

步驟2當發(fā)生變異時，在發(fā)生變異的個體中隨機選出變異起始和變異終止基因段，圖9中虛線框為選取基因段中一條流的變異起始基因和變異終止基因；

步驟3根據(jù)基因段中每個流的變異起始節(jié)點和變異終止節(jié)點重新隨機選擇一條對應的路由進行替換，生成新的基因段，如圖9，虛線框內及其之間的新基因取代其原基因生成變異基因；

步驟4判斷基因是否符合約束，最后再生成新的個體。

本文提出的路由優(yōu)化變異方法與傳統(tǒng)遺傳算法相比，主要區(qū)別在于變異所選擇的新路由在不增加路由長度的基礎上，遵從不增加鏈路最大數(shù)據(jù)負載量的原則進行變異，這不僅保證了變異機制能有效跳出局部最優(yōu)解，并且約束變異的方向，減少了無效搜索的概率，提高了算法進化率。此過程的變異操作在染色體中引入了一個大小隨機的變化，既可以產(chǎn)生較大的基因段變異，也可以只引起最小3個基因長度的變異。

4 仿真設計與結果分析

4.1 仿真設計

算法實驗采用Python 實現(xiàn)，運行在配備3.7 GHz AMD Ryzen 7 八核CPU 和64 GB 內存的計算機上。本文實驗求解輸入不同數(shù)量時間敏感流條件下的調度問題。實驗遺傳算法基本參數(shù)設置如下：種群的個體數(shù)量為30，突變概率和交叉概率分別為0.1 和0.8，迭代的最大次數(shù)為200。圖10 為實驗所用的網(wǎng)格拓撲，本文主要為了評估算法聯(lián)合路由和TSN約束調度時算法的收斂能力、求解質量和速度，而網(wǎng)格拓撲在連通性上具有較好的代表性，為每條時間敏感流提供了更多的路由可能，因此實驗采用網(wǎng)格拓撲來評估聯(lián)合路由和約束調度的性能。每個網(wǎng)格由9個交換機組成，而每個交換機連接3個端系統(tǒng)設備，鏈路上的數(shù)據(jù)傳輸速度假設為125 byte/μs。在不同的調度規(guī)模問題上進行了實驗，設置不同數(shù)量、周期和大小的流以及迭代次數(shù)，目的是為了驗證算法應對不同規(guī)模問題的有效性，同時評估求解算法性能以及靈活性。

圖10 最優(yōu)解分布對比Fig.10 Distribution of optimal solution

仿真實驗隨機生成不同周期及長度的時間敏感流，如表1所示。其中生成的流周期主要為500 μs、750 μs 以及1 500 μs，目的是為了設置超周期以及GCL周期為1 500 μs，流大小在350 byte到3 350 byte之間隨機產(chǎn)生，流的發(fā)送端和接收端從27 個端系統(tǒng)中隨機均勻選擇，使執(zhí)行傳輸任務的收發(fā)節(jié)點均勻分配到整個拓撲的端系統(tǒng)。

表1 仿真業(yè)務流設置Table 1 Simulate service flow setting

實驗通過XML 文件將流和拓撲信息輸入調度器，并采用一個基于Web的交互式用戶界面來顯示模型和解決方案，包括路由圖和時間表。流信息主要包括流的周期和長度、流對應的發(fā)送端和接收端以及最大可容忍時延；拓撲信息包括端系統(tǒng)和交換機處理能力、鏈路傳輸速率以及拓撲情況。本文主要對比傳統(tǒng)遺傳算法（未加入優(yōu)化機制的方法）與Routing-GA的靜態(tài)離線調度性能，其主要以端到端時延作為優(yōu)化目標。

4.2 仿真結果分析

表2 為傳統(tǒng)GA 和Routing-GA 分別進行10 次仿真實驗得出的端到端時延及其進化率?？梢钥闯霰疚脑O計的Routing-GA可以有效減少時間敏感流的端到端時延；與傳統(tǒng)GA 相比，Routing-GA 具有更低的端到端時延和更高的進化率，并且在相同的條件下隨著調度的時間敏感流數(shù)量增加進化率也有明顯的提高，最高可達到24.42%。這里需要注意的是，調度50 條流時進化率發(fā)生下降是因為達到近最優(yōu)解所需的迭代次數(shù)超出了200，但仍能夠達到平均10%以上。這說明Routing-GA的優(yōu)勢隨著調度規(guī)模擴大而更加顯著。

表2 端到端時延對比實驗結果Table 2 End-to-end delay comparison experimental results

圖11所示為傳統(tǒng)GA與Routing-GA的端到端時延進化迭代對比曲線。在9個交換機節(jié)點的網(wǎng)格拓撲圖中調度50 條流時，可以看出傳統(tǒng)GA 從第1 個可行解到近最優(yōu)解時間敏感流的端到端時延從8 076 μs 降低到6 814 μs，Routing-GA 從6 488 μs 降低到4 757 μs，算法均有效地減少了TSN流量調度中的端到端時延。Routing-GA進化停滯的代數(shù)不超過5，而傳統(tǒng)GA進化停滯狀態(tài)最長可達到20代，可以看出Routing-GA中交叉、變異方法能有效解決TSN流量調度中的進化停滯問題，有效跳出局部最優(yōu)狀態(tài)，使端到端時延整體上保持逐漸縮小的趨勢。另外，第1個可行解最短可以在560.75 ms內找到。

圖11 端到端時延進化迭代對比曲線Fig.11 Evolution iteration comparison curve of end-to-end time delay

設置10 組實驗組，每組隨機生成40 條流，輸入兩種算法中分別迭代200次所得到的最優(yōu)解情況如圖12所示?？梢钥闯?，傳統(tǒng)GA的結果離散程度比Routing-GA更大，這是由于Routing-GA的初始化以及交叉變異策略具有更好的穩(wěn)定性。Routing-GA最優(yōu)解情況普遍比傳統(tǒng)GA 更加優(yōu)秀，這是因為在相同的迭代次數(shù)下Routing-GA的初始化策略提供了更好的初始解，并且在優(yōu)化的交叉變異策略下向最優(yōu)解迭代的速度也同步提高。

圖12 最優(yōu)解分布對比Fig.12 Comparison of optimal solution distribution

實驗對比采用傳統(tǒng)GA 和Routing-GA 的調度方法，圖13 所示為不同時間敏感流數(shù)量（20、30、40、50 條流）算例下的算法平均運行時間結果?？梢钥闯鼋?jīng)過交叉變異過程的優(yōu)化，Routing-GA的每次迭代所需計算時間平均僅為傳統(tǒng)GA 計算時間的12%。這表明Routing-GA可以有效減少單次迭代中所需的計算時間。另外，隨著時間敏感流數(shù)量增加，傳統(tǒng)GA 單次迭代所需計算時間增長由30%增加到83%，而Routing-GA平均增長為45%。這說明Routing-GA能有效減少大規(guī)模調度計算時間。

圖13 算法單次迭代運行時間Fig.13 Running time of a single iteration of algorithm

5 結論

時間敏感網(wǎng)絡是當今和未來網(wǎng)絡應用的主要需求之一，其中包括無人駕駛、VR 技術以及5G/6G移動設備。本文研究了如何通過遺傳算法解決TSN流量調度中復雜的路由和約束聯(lián)合調度優(yōu)化問題；提出一套編碼方案以優(yōu)化求解速度，通過交叉變異以找到一個接近最優(yōu)的調度方案，并且與傳統(tǒng)GA進行實驗對比。實驗結果表明Routing-GA相較于傳統(tǒng)GA 具有更優(yōu)的性能，且能夠有效解決現(xiàn)存大規(guī)模路由與約束聯(lián)合調度復雜問題，其簡單且高效的問題建模和迭代機制為實際的流量調度應用提供了可行的參考方案。該方案在滿足時延確定性要求的前提下具有靈活性高、計算速率快的優(yōu)點，以上結論通過計算機仿真得到了驗證。

未來的工作將更多地關注處理動態(tài)變化時間敏感流的方法，該方法能夠根據(jù)每次新增或減少時間敏感流的數(shù)量，實現(xiàn)有效的局部調度計算；另外，可以考慮采用軟硬件協(xié)同調度的方法優(yōu)化調度性能，其中用硬件處理動態(tài)變化的局部調度計算、軟件實現(xiàn)全局的調度計算。