曹志鵬，劉勤讓，劉冬培，張 霞

（中國人民解放軍戰(zhàn)略支援部隊信息工程大學信息技術(shù)研究所，鄭州450001）

0 概述

時間敏感網(wǎng)絡(luò)（Time-Sensitive Network，TSN）是一種新型的數(shù)據(jù)確定性傳輸網(wǎng)絡(luò)，在以太網(wǎng)的基礎(chǔ)上加入了時間同步、傳輸調(diào)度、路徑控制、資源預(yù)留、可靠冗余等新機制，使得時間關(guān)鍵或任務(wù)關(guān)鍵應(yīng)用的服務(wù)質(zhì)量（Quality of Service，QoS）得到保證［1］。TSN 支持時間敏感流量和盡力而為（Best Effort，BE）流量在同一網(wǎng)絡(luò)中進行傳輸，并對前者提供低延遲、低抖動和低丟包率［2］服務(wù)。由于TSN 能夠?qū)⒁蕴W(wǎng)的低成本、高帶寬特點與高質(zhì)量的數(shù)據(jù)傳輸相結(jié)合，因此TSN 相關(guān)技術(shù)已經(jīng)得到了學術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注［3-5］。盡管TSN 具有以上優(yōu)點，但是在實際的分析和計算中，由于網(wǎng)絡(luò)結(jié)構(gòu)眾多、數(shù)據(jù)流QoS 各異，因此會導(dǎo)致TSN 系統(tǒng)的調(diào)度計算呈現(xiàn)出復(fù)雜性。已有眾多研究表明，TSN 中的流量調(diào)度問題是NP 完全問題［6-8］。低效率、拓展性差的調(diào)度計算方法將會導(dǎo)致計算時間消耗大、計算顆粒度粗等問題，不利于TSN 系統(tǒng)的快速、高質(zhì)量部署。

眾多學者針對上述問題進行了大量研究。ARESTOVA 等［7］綜合考慮了網(wǎng)絡(luò)設(shè)備、TSN 流的屬性和不同路由方式帶來的影響，設(shè)計一種基于混合遺傳算法的計算方法，并對調(diào)度結(jié)果進行壓縮。PAHLEVAN 等［9］同時考慮路由約束和調(diào)度約束，采用啟發(fā)式列表調(diào)度方法提高計算性能，并對分布式系統(tǒng)、多播流和流關(guān)系進行討論。GAVRILUT 等［10］在計算中增加了對AVB 流量的考慮，利用GRASP 算法同時進行路由和調(diào)度計算，使得系統(tǒng)中的時間敏感流量和AVB 流量都能滿足傳輸需求。DURR 等［11］針對計算粒度粗、帶寬浪費等問題，將調(diào)度問題映射到經(jīng)典JSP 問題，利用禁忌搜索進行調(diào)度計算，并通過調(diào)度壓縮節(jié)省帶寬?？傮w而言，上述各項研究均從不同角度完成了對TSN 網(wǎng)絡(luò)的路由和調(diào)度計算，但也存在路由調(diào)度分離、計算效率低、顆粒度粗等問題，在計算速度和優(yōu)化效果上有待提升。

本文從高效率流量路由調(diào)度計算的角度出發(fā)，提出一種基于最短路徑負載均衡和改進遺傳算法的流量調(diào)度方法。在路由計算部分，考慮到流與流在傳輸過程中的相互影響，利用鏈路負載均衡的思想進行規(guī)劃。在調(diào)度計算部分，使用優(yōu)勢個體保留的選擇算子和自適應(yīng)交叉變異概率，對遺傳算法進行改進，防止過早收斂和陷入局部極值，以充分提升算法的搜索效率。

1 問題建模

1.1 網(wǎng)絡(luò)模型與流量模型

在TSN 網(wǎng)絡(luò)模型中包含終端、交換機、傳輸鏈路這3 種要素，其中終端和交換機合稱為節(jié)點。各個節(jié)點均是支持TSN 特性的設(shè)備，傳輸鏈路是全雙工的以太網(wǎng)鏈路。將網(wǎng)絡(luò)屬性歸結(jié)為關(guān)于拓撲τ和節(jié)點數(shù)量n的二元組，如式（1）所示：

對于特定拓撲的網(wǎng)絡(luò)而言，可以將其表示為有向圖，如式（2）所示：

其中：vi∈V表示節(jié)點，包含終端和交換機；(va,vb),(vb,va)∈E表示節(jié)點之間雙向鏈路的集合。

將從源節(jié)點開始且按照一定要求傳輸?shù)侥康墓?jié)點的有序數(shù)據(jù)序列稱為流，并將所有時間敏感流的集合記為F。對于每種不同的流，其主要參數(shù)包含流的傳輸路徑R、流的傳輸周期T、流的負載值P、流的端到端時間限制D。例如，對于流fi，可用以下四元組表示：

不同的流可能通過不同的路徑進行傳輸，對于源節(jié)點是vsrc、目的節(jié)點是vdst且中間經(jīng)過v1,v2,…,vn共n個節(jié)點的流，可將其路徑表示為。流負載的單位是字節(jié)，每個幀的最大長度為以太網(wǎng)的最大傳輸單元（Maximum Transmission Unit，MTU）。每個時間敏感流都有端到端的時間限制，即目的節(jié)點處的接收時間與源節(jié)點處的發(fā)送時間之差應(yīng)在規(guī)定范圍內(nèi)，用Di表示。

1.2 TSN 傳輸約束

在TSN 網(wǎng)絡(luò)中，為了確保時間敏感的數(shù)據(jù)流量能夠及時準確送達，需要對網(wǎng)絡(luò)傳輸行為施加一定的約束。本文的研究目標是求出在滿足這些約束條件下的可行解，并去尋求最優(yōu)解或近似最優(yōu)解，同時盡量提高計算效率和可擴展性。路由問題的核心是在減小鏈路負載和擁塞的情況下，求解不同流的傳輸路徑。調(diào)度問題的核心可以歸結(jié)為計算每條鏈路上傳輸時間窗的開窗時間與關(guān)窗時間。在TSN 中，共有5 種傳輸約束［12-14］。

約束1對于任一條鏈路上的時間窗而言，其開窗時間不應(yīng)超過其關(guān)窗時間，如式（4）所示：

其中：fe i,m表示流fi在鏈路e上的第m幀；ts表示開窗時間；te表示關(guān)窗時間。

約束2對于同一條鏈路，應(yīng)當滿足首幀的發(fā)送時間為非負，且各幀按照先后順序進行發(fā)送，如式（5）、式（6）所示：

約束3在同一段傳輸時隙內(nèi)，鏈路資源應(yīng)當是被當前流所獨占的，不同的流之間不會發(fā)生碰撞，如式（7）、式（8）所示：

約束4同一數(shù)據(jù)流在不同鏈路上的傳輸是有先后順序的，如式（9）所示：

約束5流的端到端時延不應(yīng)超出最大限制，如式（10）所示：

2 基于最短路徑負載均衡與MGA的流量調(diào)度

2.1 基于K 最短路徑的負載均衡路由算法

根據(jù)IEEE Std 802.1Qca-2015［15］，傳統(tǒng)TSN 系統(tǒng)中采用帶有約束的最短路徑優(yōu)先（Constrained Shortest Path First，CSPF）路由。如果同源節(jié)點和目的節(jié)點之間同時有多條最短路徑路由，那么會根據(jù)一定的約束條件進行剪枝。然而文獻［16］研究表明，采用最短路徑算法（Shortest Path Algorithm，SPA）有可能產(chǎn)生額外的延遲。數(shù)據(jù)的路由不僅需要減少轉(zhuǎn)發(fā)操作，而且要使其路由通過有較少數(shù)據(jù)重疊的路徑。當每種數(shù)據(jù)流僅按照自身的最短路徑進行路由而不考慮流與流之間的相互影響時，雖然自身可能是最優(yōu)解，但是也可能會導(dǎo)致整體時延的增加。因此，本文提出一種基于K 最短路徑的負載均衡路由算法（Load Balancing Routing Algorithm based on K Shortest Path，LBRA-KSP）。該算法能夠針對不同的數(shù)據(jù)流尋找路由，使得鏈路負載達到最小。LBRA-KSP 算法流程如圖1所示。

圖1 LBRA-KSP 算法流程Fig.1 Procedure of LBRA-KSP algorithm

LBRA-KSP 算法的輸入為網(wǎng)絡(luò)拓撲、數(shù)據(jù)流及其屬性，輸出為每條流所對應(yīng)的路由路徑，主要步驟如下：

1）數(shù)據(jù)的初始化。對于輸入的拓撲結(jié)構(gòu)，將圖中各條鏈路的初始負載值設(shè)置為0。對于輸入的流，LBRA-KSP 算法主要考慮其源地址、目的地址和流負載這3 種屬性，并將所有的輸入流按照流負載從小到大進行排序。

2）計算備選路徑。LBRA-KSP 算法綜合考慮路徑長度和流之間的相互作用，以此來獲得更優(yōu)質(zhì)的傳輸路徑。對于某條流，采用KSP 算法，計算從源節(jié)點到目的節(jié)點的前K條最小距離路由。

3）路由選優(yōu)。路由選優(yōu)是LBRA-KSP 算法的關(guān)鍵，對于計算所得到的K條路由路徑，計算每條備選路徑的負載值，將新的負載值更新為歷史負載值和新添加負載值之和，然后選擇其中總負載值最小的那條路徑作為該流的傳輸路徑。

算法1路由選優(yōu)算法

2.2 MGA 算法

遺傳算法借助生物界中的優(yōu)勝劣汰思想和基因遺傳原理，通過對自然種群繁衍進化的模擬來求得優(yōu)化過程中的最優(yōu)解。但是，遺傳算法通常存在搜索效率較低、過早收斂、容易陷入局部極值等問題，JIA 等［17］針對上述問題進行優(yōu)化形成改進的遺傳算法（Modified Genetic Algorithm，MGA）。本文對MGA的選擇算子和交叉變異概率進行改進，并結(jié)合LBRA-KSP 的結(jié)果進行計算，全面提升了MGA 的運行效果，如圖2所示。為便于計算，本文采取與文獻［11］相同的假設(shè)，即各流的傳輸周期保持相同。

圖2 改進的MGA 算法流程Fig.2 Procedure of improved MGA algorithm

2.2.1 路徑矩陣與時間矩陣

路徑矩陣用于表示每條待調(diào)度的流所經(jīng)過的各段鏈路，如式（11）所示：

在路徑矩陣中，行表示流的數(shù)量，列表示流的傳輸路徑，行與列的下標均從0 開始計數(shù)。例如，流3表示其傳輸路徑經(jīng)過鏈路11、鏈路4、……、鏈路9。相同的鏈路用同一種數(shù)字表示，不同的鏈路用不同的數(shù)字表示。例如，流1 所經(jīng)過的第0 個傳輸鏈路與流3 所經(jīng)過的第1 個傳輸鏈路、流4 所經(jīng)過的第1 個傳輸鏈路是相同的。為了防止鏈路沖突的發(fā)生，需要進一步的調(diào)度計算。

時間矩陣表示數(shù)據(jù)流在每條鏈路上傳輸所消耗的時間，如式（12）所示：

時間矩陣ttime與路徑矩陣rroute一一對應(yīng)，在每條傳輸路徑上可以根據(jù)負載值計算出相對應(yīng)的數(shù)據(jù)傳輸用時。

2.2.2 適應(yīng)度函數(shù)

時間敏感網(wǎng)絡(luò)的核心為關(guān)鍵流量的確定性傳輸，并且對于每一條時間敏感的流，其端到端的傳輸時間不能夠超過其最大時限。從整體而言，整個網(wǎng)絡(luò)的流量調(diào)度總時間也要盡量短，使得整體GCL 調(diào)度表盡量緊湊。因此，在調(diào)度計算時，不但需要滿足每條流的時限，而且需要總?cè)蝿?wù)的完成時間盡可能短。將適應(yīng)度函數(shù)定義為：若某條染色體未能在時限內(nèi)完成調(diào)度，則規(guī)定其適應(yīng)度為-1，在之后的計算中將直接被淘汰，而其余在時限內(nèi)的染色體適應(yīng)度值設(shè)置為最大關(guān)窗時間減去最小開窗時間，如式（13）所示：

算法2適應(yīng)度計算算法

2.2.3 基于優(yōu)勢個體保留的選擇算子

輪盤賭是遺傳算法中最常見的選擇算子，輪盤賭選擇算子的基本思想為：個體選中的概率與其適應(yīng)度函數(shù)的函數(shù)值成正比，以便能夠盡可能多地復(fù)制種群中的優(yōu)秀個體。假設(shè)群體的大小為n，個體i的適應(yīng)度為Fi，則個體i被選中遺傳到下一代群體的概率如式（14）所示：

然而，在遺傳算法的實際運行過程中，當?shù)幱诔跏茧A段時，輪盤賭選擇算子會選擇較多的高適應(yīng)度個體，這些高適應(yīng)度個體經(jīng)過復(fù)制所得到的子代數(shù)目也會相應(yīng)增加，導(dǎo)致整體種群喪失了多樣性。當?shù)幱谀┪矔r期時，種群個體之間的差異已很小，適應(yīng)度非常接近，此時再采用輪盤賭策略意義不大，于是本文使用優(yōu)勢個體保留的思想對其進行改進，具體步驟為：

步驟1對種群進行適應(yīng)度排序，按照適應(yīng)度從高到低的順序分成優(yōu)秀個體、一般個體和較差個體這3 個分區(qū)。

步驟2淘汰所有較差個體分區(qū)內(nèi)的染色體，并用優(yōu)秀個體中的染色體進行替代。

步驟3對步驟2 中的種群進行交叉和變異操作得到新的子代，再將該種群按照步驟1～步驟3 的順序進行操作，以此類推，直到生成最終結(jié)果。

2.2.4 自適應(yīng)交叉和變異算子

交叉算子采用順序交叉（Order Crossover，OX）算子，基本操作過程為：首先選擇一對用于交換的父代染色體，并且隨機選擇用于交換的基因片段；然后根據(jù)切割點，生成新的子代，并且保證切割區(qū)域內(nèi)的內(nèi)容不變；最后按照順序依次將另一個父代中的其他基因填入子代中的空白區(qū)域。交叉算子的操作過程如圖3所示。變異算子采用位置變異算子，對于某條染色體，隨機產(chǎn)生兩個變異的位置并對其進行交換。變異算子的操作過程如圖4所示。

圖3 交叉算子的操作過程Fig.3 Operation process of crossover operator

圖4 變異算子的操作過程Fig.4 Operation process of mutation operator

在遺傳算法中，參數(shù)的交叉概率和變異概率對算法的性能有著較大的影響。對于交叉算子，在迭代前期交叉概率取大值為佳，能擴大搜索范圍和加快進化速度。在后期交叉概率取小值為佳，使得種群相對穩(wěn)定。對于變異算子，在迭代后期時，變異概率應(yīng)當增加，以防止陷入局部極值，減弱種群的多樣性。因此，本文采用簡單遺傳算法（Simple Genetic Algorithm，SGA）［18］自適應(yīng)的遺傳概率，交叉概率Pc和變異概率Pm能夠根據(jù)適應(yīng)度自動做出改變，如式（15）、式（16）所示：

其中：fmax為每代群體中的最大適應(yīng)度；favg為每代群體中的平均適應(yīng)度；f′為需要交叉的兩個個體中較大的適應(yīng)度值；f為需要變異的個體的適應(yīng)度值。

3 實驗與結(jié)果分析

3.1 實驗平臺與參數(shù)設(shè)置

為證明本文方法的可行性與高效性，將LBRAKSP+MGA 與SPA+MGA 和LBRA-KSP+SGA 方法進行對比分析。相關(guān)程序使用Python 3.7 進行編寫，硬件環(huán)境為Intel Core i5-7300HQ 和16 GB RAM。所采用的IDE 為PyCharm Community 2019.3 版本。

為了體現(xiàn)本文方法在各種應(yīng)用場景下的普適性，首先采用與文獻［16］相同的方法，產(chǎn)生隨機的ER 網(wǎng)絡(luò)［19］和隨機的BA 網(wǎng)絡(luò)［20］進行仿真驗證，再針對真實的網(wǎng)絡(luò)場景數(shù)據(jù)集進行仿真計算。對于隨機生成流，源節(jié)點和目的節(jié)點在可選范圍內(nèi)隨機生成，流負載值參考文獻［9］進行設(shè)定，每條流在［1，99］中任意選取。6 種配置場景下的拓撲規(guī)模（節(jié)點數(shù)量與鏈路數(shù)量）如表1所示。

表1 實驗參數(shù)設(shè)置Table 1 Setting of experimental parameters

本文采用MGA 進行調(diào)度，由于MGA 特性導(dǎo)致運行結(jié)果具有一定的隨機性，因此為了保證數(shù)據(jù)的正確性，每組實驗均進行5 次并取其平均值作為最終數(shù)據(jù)。MGA 算法參數(shù)設(shè)置如表2所示。

表2 MGA 算法參數(shù)設(shè)置Table 2 Setting of MGA algorithm parameters

3.2 結(jié)果分析

實驗1對比并分析LBRA-KSP 路由算法與SPA 路由算法對調(diào)度計算的影響（均使用MGA 進行調(diào)度計算）。該實驗采用表1 中的參數(shù)設(shè)置，對比在相同節(jié)點數(shù)量和相同流數(shù)量情況下，算法最終收斂的f值。圖5 分別給出了流數(shù)量為5、10 和25 下的調(diào)度結(jié)果?？梢钥闯?，LBRA-KSP 路由算法能夠明顯地降低每次調(diào)度的最大完成時間，而SPA 路由算法僅考慮自身的最短路徑，在流與流之間發(fā)生相互影響時，會導(dǎo)致調(diào)度時延的增加。而由于鏈路負載生成的隨機性，可能會導(dǎo)致LBRA-KSP+MGA 方法最終的最大適應(yīng)度值f偏大，但是從統(tǒng)計意義上看，LBRA-KSP+MGA 方法在整體上還是降低了f值，平均比SPA 路由算法降低了23.11%。

圖5 LBRA-KSP 和SPA 路由算法的最大完成時間對比Fig.5 Comparison of the maximum completion time between LBRA-KSP and SPA routing algorithms

實驗2對比并分析MGA 和SGA 算法對調(diào)度計算的影響（均使用LBRA-KSP 進行路由計算）。如圖6所示，該實驗主要將LBRA-KSP+MGA 和LBRA-KSP+SGA 方法進行對比研究，觀察收斂性能。實驗分別選擇以下4 種情況進行對比分析：1）配置場景為ER2、節(jié)點數(shù)量為20、流數(shù)量為10；2）配置場景為ER3、節(jié)點數(shù)量為20、流數(shù)量為25；3）配置場景為BA2、節(jié)點數(shù)量為20、流數(shù)量為10；4）配置場景為BA3、節(jié)點數(shù)量為30、流數(shù)量為25。從圖6 中可以看出，帶有MGA 的方法相較SGA 方法明顯迭代次數(shù)更少，收斂到的終值質(zhì)量更優(yōu)，并且隨著網(wǎng)絡(luò)規(guī)模的增加，最終收斂到的f值也會相應(yīng)增大。

圖6 MGA 和SGA 調(diào)度對比Fig.6 Scheduling comparison between MGA and SGA

實驗3對比并分析不同節(jié)點數(shù)量和流數(shù)量對于LBRA-KSP+MGA 方法調(diào)度計算的影響。該實驗在ER1-ER3、BA1-BA3 場景配置下，對應(yīng)的節(jié)點數(shù)量分別設(shè)置為10、20 和30，流數(shù)量分別為5、10 和25。主要考察最終收斂到的f值與平均收斂的迭代次數(shù)i，經(jīng)過仿真運行得到的結(jié)果如表3所示。由于啟發(fā)式算法的隨機性和流負載生成的隨機性，會導(dǎo)致部分數(shù)據(jù)比較特殊。從整體趨勢上看，節(jié)點數(shù)量越多，調(diào)度最終收斂到的f值越大，而平均迭代次數(shù)i值會變??；從流數(shù)量的角度上看，隨著流數(shù)量的增加，f值和i值都在不斷增加，而ER 和BA 配置場景對調(diào)度的影響較小。

表3 不同參數(shù)對LBRA-KSP+MGA 方法的影響Table 3 The influence of different parameters on the LBRA-KSP+MGA method

實驗4驗證LBRA-KSP 算法在真實網(wǎng)絡(luò)環(huán)境下能進行有效的流量調(diào)度。對于有限帶寬且多節(jié)點的控制系統(tǒng)、工業(yè)互聯(lián)網(wǎng)、汽車內(nèi)網(wǎng)等復(fù)雜大型系統(tǒng)中的內(nèi)部網(wǎng)絡(luò)，能夠同時產(chǎn)生和傳輸多種不同QoS要求的流量。本文選取TSN 領(lǐng)域中基于SAE 環(huán)境和CEV 環(huán)境的數(shù)據(jù)集［2］。SAE 和CEV 環(huán)境下的拓撲結(jié)構(gòu)如圖7、圖8所示，其中，SW1～SW7 表示交換節(jié)點，es 前綴表示終端節(jié)點。

圖7 SAE 環(huán)境下的拓撲結(jié)構(gòu)Fig.7 Topology structure under SAE environment

圖8 CEV 環(huán)境下的拓撲結(jié)構(gòu)Fig.8 Topology structure under CEV environment

在數(shù)據(jù)預(yù)處理階段，對于數(shù)據(jù)流按照式（3），針對不同實驗拓撲將各條流整理為包含源端口、目的端口、流負載和流的端到端時延的四元組。在SAE環(huán)境中待調(diào)度的時間敏感數(shù)據(jù)流共有40 條，在CEV環(huán)境中待調(diào)度的時間敏感數(shù)據(jù)流共有30 條。該實驗對比并分析了LBRA-KSP+MGA、LBRA-KSP+SGA、SPA+MGA、SPA+SGA 這4 種方法，運行結(jié)果如圖9、圖10所示。可以看出，在兩種運行場景下，LBRA-KSP+MGA 方法在收斂速度、最終f值的指標上均有明顯優(yōu)勢，其收斂的平均迭代次數(shù)為52 和46，最終的平均f值為15.58 ms 和6.35 ms?？紤]到路由的影響，LBRA-KSP 相較SPA 算法，最終f值分別下降了57.7%和59.4%，大幅減小了因為鏈路擁塞而導(dǎo)致的時延，而在調(diào)度上通過利用MGA 算法，使計算結(jié)果快速收斂?？梢?，LBRA-KSP 算法在真實網(wǎng)絡(luò)環(huán)境下能進行有效的流量調(diào)度。

圖9 基于SAE 環(huán)境的數(shù)據(jù)集運行結(jié)果Fig.9 Running results of dataset based on SAE environment

圖10 基于CEV 環(huán)境的數(shù)據(jù)集運行結(jié)果Fig.10 Running results of dataset based on CEV environment

4 結(jié)束語

本文針對TSN 時間敏感流量調(diào)度中存在的計算效率低、迭代收斂慢和路由路徑之間相互影響等問題，提出一種基于最短路徑負載均衡和改進遺傳算法的流量調(diào)度方法。在路由計算上，解決了由于使用CSPF 路由而導(dǎo)致的時延增加問題，借助鏈路負載均衡的思想，盡可能降低擁塞的發(fā)生概率。在調(diào)度計算上，對傳統(tǒng)遺傳算法選擇算子的交叉與遺傳概率進行改進，提升了迭代收斂的效率。仿真實驗和真實網(wǎng)絡(luò)環(huán)境實驗結(jié)果表明，本文方法能夠有效縮短時延敏感流量調(diào)度任務(wù)的完成時間，提高調(diào)度與路由計算效率。后續(xù)將在時間敏感流量調(diào)度計算的基礎(chǔ)上添加其他數(shù)據(jù)流量進行計算，以實現(xiàn)更系統(tǒng)高效的流量調(diào)度。