基于發布訂閱架構的在線時間觸發調度方法

高一凡，何鋒，于思凡

北京航空航天大學 電子信息工程學院，北京 100191

隨著分布式綜合模塊化航空電子 （Distributed Integrated Modular Avionics，DIMA）架構［1］的發展，航空電子系統需要具有更高的實時性、可靠性和安全性。機載網絡［2］作為航空電子系統互聯的關鍵技術，需要支持不同實時性需求的應用進行通信。時間觸發以太網［3］（Time-Triggered Ethernet，TTE）采用了全局同步時鐘，以保證時間觸發消息確定性到達和有界抖動。

時間觸發以太網依賴調度表對時間觸發消息進行確定性調度，而調度表的求解和優化是典型 的NP（Non-deterministic Polynomial）難 問題［4-6］。傳統的基于求解器的調度求解方法包括可滿足性模理論［7-10］（Satisfiability Modulo Theories，SMT）、混 合 整 數 線 性 規 劃［11］（Mixed Interger Linear Programming，MILP）等約束求解方法。有學者通過拓撲分解［12］、簡化約束條件［13］對SMT 法進行優化，減少了調度生成所需的時間。這些方法通過將網絡拓撲、流量傳輸、應用需求等構造為一組約束方程并求解，從而得到可行調度表。但這類方法通常復雜度較高，難以在短時間內求解，因此更適用于小規模網絡。另一類基于啟發式的算法，如元啟發式算法［14-15］、分組調度［16］等優化方法，它們擁有更快的求解速度，更好地平衡了調度表的求解時間和調度最優性，但啟發式算法的性能與參數設置緊密相關且模型難以泛化，較難適用于不同的應用場景。

時間觸發網絡的配置并不總是靜態的，例如網絡拓撲可能會因為節點或鏈路故障而改變［17］；或者因為上層應用的變化，數據傳輸需求發生改變［18］，導致需要根據情況更新已生成的時間觸發調度表，而靜態調度算法通常需要離線計算時間觸發調度表，然后將調度表配置下載到交換機或端系統中。所以，這類方法難以適應網絡拓撲的變化，或者調度新增時間觸發流量。

為了解決動態時間觸發調度問題，增量式調度算法［19-20］被提出，它可以在已有調度表的基礎上對新增時間觸發流量進行調度，但所需時間仍然較長。另外，有學者提出離線等價策略［21-22］，該類方法提前計算離線調度表，然后進行在線更新，大大減少了對存儲空間的需求和調度求解時間，但是該類方法只適合初始信息已知并且只有少量更新的場景。Li等［23］提出了一種基于ILP求解器的動態調度方法，該方法可以較快地生成自適應調度方案，但其中部分約束條件僅適用于特定的場景。本文提出了一種聯合流量調度順序和流量偏置進行調度求解的方法，該方法基于映射評價分數，同時求解流量調度順序與偏置，但在大規模流量求解時，該方法的求解時間仍然過長。

調度表求解時間是調度算法的關鍵衡量指標之一，尤其是在網絡拓撲和待調度流量頻繁變化的動態場景中。適用于動態場景的調度算法通常需要較短的執行時間，并且需要在增量消息調度過程中不影響已調度消息的實時性，從而完成調度表的在線求解。考慮到數據分發服務在目前應用中的高靈活性，其基于發布/訂閱的信息交互架構，為系統提供了松耦合的集成。本文將時間觸發機制與數據分發服務進行結合，提出了基于發布/訂閱的時間觸發架構模型，實現主題訂閱和消息轉發分離，一方面基于數據中間件的集中控制，對時間觸發流量進行在線調度，增加了系統的靈活性；另一方面通過時間觸發網絡保證關鍵消息傳輸的實時性。

本文首先提出了基于發布/訂閱的時間觸發網絡架構，將數據分發系統的架構拓展到了時間觸發網絡中，總結了基于數據中間件生成調度表面臨的問題；并針對上述問題，提出基于時間分片的在線時間觸發調度算法，以提高調度表的求解速度，實現調度表的在線生成和增量式調度。

1 基于發布/訂閱的時間觸發網絡架構

1.1 數據分發服務

數據分發服務（Data Distribution Service，DDS）是一個以數據為中心的中間件協議和接口標準，采用分布式發布/訂閱體系架構，以中間件的形式提供通信服務。DDS中間件是一個軟件層，它將應用程序從操作系統、網絡傳輸和底層數據格式的細節中抽象出來，從而允許應用程序在不同的操作系統、編程語言和處理體系架構之間交換信息。

系統的基本架構如圖1所示。DDS把所有本地存儲的數據稱作全局數據空間，統一管理主題訂閱情況，并進行主題匹配。DDS提供了服務質量（Quality of Service，QoS）保證的數據共享。QoS為每個主題提供專屬的服務策略，用于保證DDS消息的實時性，提高系統帶寬利用率。應用程序通過發布和訂閱由其主題名稱標識的主題進行通信，并以主題中的數據對象作為信息共享的單元。

圖1 DDS系統架構Fig.1 System architecture of DDS

1.2 時間觸發調度

時間觸發以太網提供了3種不同的流量類型：時間觸發（Time-Triggered，TT）流量，速率約 束（Rate-Constrained， RC）流 量 和 盡 力 傳（Best-Effort，BE）流量。其中TT流量延遲抖動最小，需要同步時鐘的支持，用于對網絡延遲、延遲抖動及傳輸確定性要求十分嚴格的應用。所有的TT流量消息按照預先設定好的時刻發送，優先級最高。RC流量消息的延遲確定且存在上界，用于對確定性和實時性要求稍弱一些的應用，并兼容航空電子全雙工交換式以太網（Avionics Full DupleX switched Ethernet，AFDX）網絡中的流量。BE流量用于實時性要求弱的應用，與傳統以太網中的流量兼容。

在時間觸發網絡的輸出端口中，TTE實行混合關鍵流量調度策略。為避免非TT流量對TT流量實時性產生影響，非TT流量在TT流量調度間隙，利用剩余帶寬根據優先級策略進行調度傳輸，如圖2所示。

圖2 TTE流量調度Fig.2 Flow scheduling in TTE

時間觸發調度可根據TT消息調度窗口的分布情況分為集中調度模式和多孔調度模式。集中調度模式下，調度表包含一個由若干個基本周期組成的矩陣周期，且每個基本周期又分為2段，TT消息集中于基本周期的前一段發送，后一段則用于傳輸RC消息和BE消息，并在每個基本周期末尾預留一定時間長度的保護間隔。多孔調度模式同樣符合矩陣周期和基本周期的概念，但TT消息在基本周期中沒有集中調度窗口的限制，TT消息根據自己的周期和偏置在基本周期中安排調度窗口，從而在TT調度窗口之間形成多個時間孔隙，用于RC消息和BE消息的傳輸。

1.3 基于發布/訂閱的時間觸發架構模型

基于發布/訂閱的時間觸發架構模型如圖3所示，相較于傳統DDS架構，該架構模型解耦了消息的主題訂閱和消息傳輸。通過將主題訂閱和消息轉發分離，將發布/訂閱模型用于主題管理并將時間觸發架構用于消息轉發，提高了時間觸發網絡的靈活性和擴展性。

圖3 基于發布/訂閱的時間觸發架構Fig.3 Publish/subscribe based time-triggered architecture

消息的主題訂閱基于發布/訂閱架構中數據中間件的集中管理，并通過時間觸發網絡進行傳輸，從而保證系統的實時性。在該架構下，發布者發布消息主題到數據中間件，訂閱者訂閱相關主題，數據中間件完成主題的統一匹配。同時，數據中間件存儲網絡的拓撲結構和全局消息主題，從而有效地完成消息分類、優先級劃分和傳輸路徑規劃，并生成時間觸發調度表。然后，數據中間件將生成的時間觸發調度表下發至網絡中的每個交換機，同時根據端系統發布的主題，向端系統返回相匹配的主題并下發對應的調度表。端系統根據下發的調度表進行時間觸發消息的發送和接收，而交換機也根據調度表完成消息的路由與轉發。時間觸發網絡則保證了系統中消息傳輸的實時性。

基于發布/訂閱的時間觸發架構模型，結合時間觸發網絡的特點和需求，在傳統DDS系統架構的基礎上進行改進：主要包括發布/訂閱主題和消息關聯、QoS等級轉化為時間觸發網絡消息分級以及在線時間觸發調度表的生成3個方面。

發布/訂閱主題和消息關聯。DDS系統應用之間根據主題匹配進行消息推送，而在時間觸發網絡中，則通過不同關鍵級別的消息傳輸信息。因此，該架構中每一個主題對應一種消息，數據中間件主要完成不同應用間消息需求的匹配。

QoS等級轉變為時間觸發消息分級。DDS系統的QoS包含范圍較廣，例如帶寬分配、主題及其內容存活時間、截止時間等。對于時間觸發網絡，消息會按照關鍵級別分為TT、RC、BE 3類消息，以不同優先級進行傳輸。因此需要將QoS轉化為傳輸消息的分級，按照不同消息類型和級別進行不同的處理。

在線時間觸發調度表的生成。傳統時間觸發網絡通常提前生成離線調度表，而調度表一旦生成，就難以更改。如果利用數據中間件規劃調度表，則會產生新的問題。

首先，時間觸發調度表生成時間過長。航空電子系統對實時性要求嚴苛，如果在線調度生成時間較久，將嚴重受影響系統的正常運行。目前常用的時間觸發調度生成方法有約束求解器、啟發式算法等，它們在固定的TT消息分布下雖然展現出了良好的性能，但是生成時間過長，且只能用于離線調度的場景。

其次，調度表的計算資源有限。調度表生成是一個完全NP問題，屬于計算密集型問題。傳統啟發式算法通過多次迭代求得相應的結果，需要消耗巨大的計算資源。而數據中間件作為控制中心，其計算資源十分有限，傳統啟發式算法難以直接應用，因此需要降低現有調度表生成方法的復雜度。

最后，增量式調度的影響。離線調度表生成算法很少考慮網絡和消息的動態變化，不適用于動態場景。動態時間觸發調度求解主要針對具有強實時性要求的TT流量的動態變化。在消息傳輸過程中，可能會出現新增、減少或者改變TT流量的情況，而RC流量和BE流量在TT流量傳輸的空閑時間內傳輸，調度表求解的過程中不需要考慮這兩類流量的變化。傳統求解方法在TT流量發生變化時，需要重新求解網絡中全部的時間觸發消息。若需要進行在線調度求解，則當網絡中有新增待調度消息，需要在已有調度表中找到一個合適的時間窗口，而刪除已調度消息會產生閑置時隙，需要處理相應時隙并用于新增TT消息的調度。因此，需要設計一個靈活的增量式在線調度算法。

2 基于統一時間分片的在線時間觸發調度算法

傳統的離線調度表生成方法通常不支持TT消息增量調度，而已有的增量式調度方法計算時間過長，隨著網絡規模的增加，求解時間更加難以符合要求。因此，提出了一種基于統一時間分片的在線時間觸發調度算法。首先將時間軸離散化為時間分片，調度消息至特定的時間分片；然后進一步提出時間分片的統一長度約束，縮減調度求解的搜索空間，大大縮短了調度表生成時間；并且可以在線性時間復雜度下逐條消息增量式調度生成初始調度表，還可對已生成調度表進行增加或刪除。其次，描述了基于統一時間分片的在線時間觸發調度算法在發布/訂閱架構下的實現過程，包括系統中數據中間件和交換機的初始化和在線調度階段的運行流程，使系統可以利用數據中間件實現基于統一時間分片的在線時間觸發調度算法。

2.1 在線時間觸發調度規劃方法

2.1.1 網絡模型

一個典型的通信網絡可以看作是實時應用的調度平臺，可以將其建模為圖G={V，E}，其中V為網絡節點集合，包括端系統節點和交換機節點vk∈V，E為有向邊的集合。(va，vb)∈E表示連接頂點va到vb的一條物理鏈路。

M為網絡中的時間觸發消息集合，其中消息mi∈M是周期性消息。每條消息mi用五元組＜Ti，li，ri，σi，δi＞表示。其中，Ti為消息的周期，li為消息的長度，ri為消息的傳輸路徑，σi為消息的源端系統節點，δi為消息的目的端系統節點。

消息從源節點到目的節點的傳輸路徑可以表示為

由消息周期Ti，可以求得該消息組中消息周期的最小公倍數Tlcm和最大公約數Tgcd，則該消息組中任意一條消息的周期Ti=niTgcd，其中ni∈?。本文采用最短路徑算法生成TT消息路徑，消息集合中的消息最大跳數為hopmax。由于TT消息具有周期性，因此只需要規劃消息集合在其周期的最小公倍數Tlcm（即消息超周期）時間內的消息調度表即可。

2.1.2 時間分片劃分和約束

為了優化調度搜索空間，提高調度求解速度，考慮將時間軸離散，將連續的時間偏置選擇轉變為離散的時隙選擇。因為調度求解是針對消息集合的超周期Tlcm考慮，而集合中的消息周期長度不小于Tgcd。因此，首先將一個超周期長度按照消息周期的最大公約數Tgcd均分成時間分段。另外消息需要在截止期限前經過多跳傳輸到達目的節點，所以根據網絡最大跳數進一步將時間分段劃分為時間分片，并將消息調度至路徑上各跳鏈路的時間分片中，占據時間分片中對應長度的時隙進行傳輸。這樣可以保證在一個時間分段長度內，集合中周期最小的消息經過最大跳數傳輸，仍能在截止期限內到達目的節點。調度求解問題本質上是將鏈路資源與消息傳輸需求進行匹配，通過時間分片的劃分，將鏈路資源表示為離散的時間分片，將消息傳輸與時間分片匹配，從而優化調度求解過程，提高求解效率。以下為具體劃分和表示過程。

首先將網絡中各鏈路(va，vb)上的一個超周期時間長度Tlcm按照消息周期的最大公約數均分成 時 間 分 段si，(va，vb)，并 以 消 息 周 期 的 最 大 公 約 數Tgcd作為時間分段的長度，表示為

則一個超周期內的時間分段數Ns為

將每一個時間分段按照網絡最大跳數hopmax劃 分 為 時 間 分 片pi，(va，vb)，表 示 鏈 路(va，vb)上的第i個時間分片：

式 中：startpi，(va，vb)為 時 間 分 片pi，(va，vb)的 起 始 偏 置 時刻；endpi，(va，vb)為 時 間 分 片pi，(va，vb)的 結 束 偏 置 時 刻，lengthpi，(va，vb)為時 間分片pi，(va，vb)的長度。

時間分片的長度取決于時間分片中傳輸的具體的TT消息長度和網絡的物理鏈路帶寬。假設時間分片包含一組消息M={mj}，鏈路的帶寬為B，則在不考慮消息傳輸切換間隔下，鏈路(va，vb)上的時間分片長度滿足：

將鏈路(va，vb)上一個超周期內的時間分片，表示為

在一個時間分段si內，時間分片由左向右延拓，其余時間分片則由中心節點向外延拓，這樣可以盡可能減少消息調度過程中由于時間分片長度不斷增加而發生重疊的情況。可以得出，對于si，(va，vb)分 段 中 的p1，(va，vb)和phopmax，(va，vb)，其 時 間 分片分布為

對于其他的節點，即當1＜j＜hopmax時，根據消息最大跳數hopmax，可以求出pj，(va，vb)的中心點為

可得

則時間分片不發生重疊（即無沖突）的條件為startpj，(va，vb)≥endpj-1，(va，vb)。

在消息傳輸過程中，要保證消息前后兩跳時間分片不沖突，需要檢測該跳鏈路的上一跳鏈路的時間分片結束時刻，滿足上一跳鏈路的時間分片結束時刻不大于該跳鏈路當前時間分片的開始時刻；另外需要檢測該鏈路下一跳鏈路的時間分片開始時刻，滿足其開始時刻大于該跳鏈路當前時間分片的結束時刻。由于網絡中各鏈路的時間分片長度獨立，上述驗證過程復雜度過高，求解時間較長，不適合實時在線進行計算，因此進一步提出時間分片統一長度約束，限制時間分片的長度滿足：

因為時間分片是將時間分段按照最大跳數hopmax劃分得到的，當時間分片滿足統一長度約束時，相鄰2個時間分片不會發生重疊。網絡鏈路的時間分段和時間分片分別為圖4的上、下部分。

圖4 時間分片Fig.4 Time slicing

2.1.3 時間分片調度

對于某條消息mi，該消息需要在超周期Tlcm的時間內傳輸Tlcm/Ti次。設消息在第k跳鏈路所對應的時間分片下標為idi，k，其中id用于標識消息傳輸占用的時間分片的下標。因此根據消息的傳輸路徑，第n個消息傳輸時，只需滿足：

在此條件下，下一跳的時間分片始終晚于上一跳時間分片，即滿足TT消息可調度且不會沖突。同時滿足消息的發送時間大于消息產生的時間，且消息到達時間小于消息的截止期限。

在此模式下，需要判斷在消息加入后，時間分片的長度是否滿足約束中的統一長度。此時，滿足式（12）條件的時間分片數目為

即在符合條件的時間分片中，選出消息傳輸路徑跳數hopi個時間分片即可。則式（14）的復雜度為復雜度分布不均且可能會非常高。求解時間難以滿足在線調度的實時性要求。

因此，本文約束消息在傳輸路徑中相鄰跳數對應的時間分片也必須相鄰，即

在此條件下，由于最大跳數和時間分片均為固定值，單條消息可以在不超過復雜度下得到求解，時間分片長度等于分片內消息傳輸所需的時間。

對于某條消息mi，其傳輸路徑為ri，將消息傳輸路徑中各條鏈路對應的時間分片定義為一個時間分片分組：

當消息從源節點到目的節點的路徑跳數為hopi時，可以求得該消息滿足約束的時間分片的分組數目為

為避免下一條TT消息放入過程中超過時間分片的最大約束長度，將TT消息傳輸路徑上各鏈路對應的時間分片中，最長消息長度作為其路徑負載：

為了避免消息都集中于某個時間分片中，在消息調度過程中，選擇消息對應的全部時間分片分組中負載最小的分組，以實現鏈路的負載均衡：

從而不僅可以避免TT消息集中于個別時間分片內，還保證了RC消息傳輸所需時隙，降低了RC消息的排隊延遲，提高了算法的調度性能。

基于統一時間分片的在時間觸發調度算法優化了消息調度求解的搜索空間，顯著提高了調度表的求解速度，可以在線性時間復雜度O(n)下，迅速地生成大規模消息的時間觸發調度表。同時，在消息增加和刪除時，可以在常數階時間復雜度O(1)內得到修改后的調度表。該方法不依賴離線調度表，可進行在線時間觸發調度求解，能夠應用在高實時性需求的機載網絡中。

2.1.4 算法流程示例

采用簡單拓撲對前述調度生成算法及其流程進行說明。示例拓撲如圖5所示。

圖5 示例網絡拓撲Fig.5 Example network topology

現有TT消息參數如表1所示。由表1可以計算出該組消息的周期最小公倍數為8 ，最大公約數為2 ，消息傳輸路徑的最大跳數為3。對于第1條消息，周期為2 μs，在超周期內需要傳輸4次，并且每次只有1組時間分片可行解，則第1條消息調度的結果如圖6所示。

表1 TT消息參數Table 1 TT message parameters

圖6 調度TT1消息Fig.6 Scheduling TT1

第2條消息周期為4 μs，在超周期內需要傳輸2次，并且每次傳輸的時間分片可行解數目為4，根據式（17）選擇對應負載最小的時間分片分組。第3條消息采用的方法類似，放入消息后結果如圖7所示。

圖7 調度TT2、TT3Fig.7 Scheduling TT2 and TT3

TT4消息的周期為4 μs，超周期內需要傳輸2次。根據式（16）可以得到共有4個可行的時間分片分組，對應的負載loadri(n)分別為TT1、TT2、TT3和TT1所占用的時間窗長度。選取其中最小的，將消息TT4放入，結果如圖8所示。

圖8 調度TT4Fig.8 Scheduling TT4

由上述調度過程可以看出，在劃分時間分段和時間分片后，只需要把消息放入對應的時間分片中，并根據消息長度之和和鏈路的帶寬計算出消息傳輸所需時間，從而得到時間分片長度。

2.2 在線時間觸發調度算法部署

2.2.1 系統初始化

1） 數據中間件初始化

數據中間件主要負責TT調度表生成，其根據時間分片信息計算出時間觸發調度表，并下發調度表信息至交換機和端系統中。

數據中間件初始化需要3個步驟：加載全局信息、TT消息路徑規劃、TT調度表求解。

加載全局信息，包含發布/訂閱架構模型的拓撲信息、網絡帶寬、生成網絡拓撲的相關數據結構。另外，數據中間件需要加載初始TT消息，這是系統啟動的必要消息，初始調度表的生成也是一個逐條消息調度的增量過程。

TT消息路徑規劃，是根據全局拓撲，生成TT消息的傳輸路徑。為加快求解速度、減少路由跳數，以減少時間片的分片個數，本文采用最短路徑算法生成路由。因為最大跳數直接影響時間片分片的數目，進而影響TT消息增量規劃時所需的計算時間。在消息路徑規劃時，需要遍歷TT消息，記錄TT消息的最小公倍數Tlcm，最大公約數Tgcd和對應的最大跳數hopmax。

TT調度表求解。根據TT消息周期的Tlcm，Tgcd和hopmax，可以為每一條鏈路規劃一個基本的時間分段列表和時間分片列表，并初始化其長度為0。此時遍歷TT消息，根據2.1節的在線調度算法，確定每個TT消息對應的時間分片，將消息調度至其中。利用鏈路帶寬和TT消息的長度計算出所需要的傳輸時間，并更新時間分片的長度。在消息調度過程中，根據時間分片的分配進行負載均衡，提高消息的可調度性。

2） 交換機及端系統初始化

接收到數據中間件下發的TT調度規劃信息后，交換機的路由模塊和隊列模塊需要進行初始化，同時端系統應用開始根據調度表發送消息。

首先，交換機路由模塊需要根據配置信息生成TT消息的靜態路由表，以便將接收到的消息迅速轉發至相應的端口隊列。同時，解析得到消息中的TT調度表配置，生成并下發各個輸出端口的配置信息。

隊列模塊根據消息周期的Tlcm和Tgcd生成對應的時間分片，解析配置信息中的消息序號和消息長度，并依次放入對應的時間分片中。根據時間分片計算公式，得到時間分片的起始時間和終止時間，并開始進行時間分片的輪轉。

2.2.2 在線增量調度階段

由于系統運行過程中，會有主題的匹配和解耦，導致TT消息調度表會隨時改變，數據中間件在消息調度生成和端口隊列處理時間分片的變化都需要快速調整，處理流程如圖9所示。

圖9 在線增量調度流程Fig.9 Online incremental flow scheduling

1） 數據中間件在線增量時間觸發調度

在完成主題匹配和解耦后，會引發TT調度表變化。當新增TT消息時，模型的端口隊列根據時間分片信息，根據2.1節中的算法插入新增消息并更新時間觸發調度表。當刪除已調度TT消息時，根據TT消息傳輸路徑，遍歷輸出端口對應的時間分片隊列，找到該TT消息對應的時間分片，并刪除TT消息。

2） 端口隊列在線時間觸發隊列

端口需要根據新的配置信息，更新時間分片。新增消息時，將消息對應的靜態路由信息保存在路由模塊中，并根據時間分片長度重新計算新增消息對應的時間分片的起始時刻和結束時刻。

根據2.1節算法，當時間分片位置不同時，需進行不同處理。當時間分片序號對hopmax取模運算等于1的時候，表示該時間分片是對應的時間分段中的第1個時間分片，因此時間分片的起始時刻固定，只需改變時間分片的結束時刻。當序號對hopmax取模運算等于hopmax時，表示該時間分片是對應的時間分段中的最后一個時間分片，因此時間分片的結束時刻固定，只需要改變時間片的起始時刻。當序號對hopmax取模運算結果介于1和hopmax之間時，時間分片的中心位置固定，起始時刻和結束時刻都會改變。由于時間分片之間不會重疊，不會影響上一跳和下一跳的時間片，仍可以保證TT調度表的合理性。

3 算法評價與分析

3.1 實驗參數設置

實驗采用如圖10和圖11所示的2種拓撲結構，圖10為小規模拓撲結構，包含8臺端系統和4臺交換機，以及1個數據中間件。每個交換機與2個端系統以及另外3個交換機和數據中間件相連，鏈路帶寬為1 Gbit/s；圖11采用基于空客A380的拓撲結構，包含8個交換機和16個端系統，以及1個數據中間件，拓撲連接關系如圖11所示（其中數據中間件與8臺交換機連接），鏈路帶寬為1 Gbit/s。數據流的配置信息隨機生成，其中設置TT消息周期的Tlcm=2 ms，Tgcd=32 ms。消息的源節點與目的節點從端系統中隨機選取（源節點與目的節點不相同且之間經過交換機），同時根據航空電子系統中的消息特點，TT消息長度在64～1 518 bytes均勻分布選取。計算機CPU為英特爾i7-9750h處理器，標準頻率為2.60 GHz，最高主頻4.2 GHz，內存為24 GB，64位操作系統，實驗基于OMNeT++網絡仿真平臺。

圖10 案例1～3拓撲結構Fig.10 Topology of case study 1～3

圖11 案例4～5拓撲結構Fig.11 Topology of cases 4～5

3.2 實驗案例設置

設置5個實驗案例，基于圖10和圖11 2種不同規模的拓撲結構，將本文提出的基于統一時間分片的在線時間調度算法與傳統SMT算法和新提出的MSS算法［24］的性能表現進行對比。

案例1～案例3基于圖10所示的小規模拓撲。案例1根據調度求解時間，比較3種算法的求解速度；案例2進一步對比本文算法與SMT算法求解生成的調度表中RC消息的平均延遲和最壞延遲，比較2種方法的調度求解性能。在保證時間觸發消息的實時性前提下，RC消息延遲越小表示調度算法的性能越好。案例3用于驗證本文算法最大調度規模。在典型拓撲結構下，分別對含有1 000、1 500、2 000條TT消息的網絡進行調度求解，計算RC消息最壞延遲并驗證其是否滿足最晚截止期限要求。為進一步驗證本文算法的調度性能，案例4和案例5采用圖11所示的基于空客A380的拓撲結構，對比本文算法與MSS算法在不同流量規模下的表現。案例4對比本文算法與MSS算法的調度成功率，調度成功率越高則表示算法求解的可調度性越好，能夠求解更大規模消息的調度表。案例5對比2種算法的鏈路時隙資源利用率和鏈路時隙占用方差。鏈路時隙利用率高說明消息傳輸利用了鏈路資源更加有效。而鏈路時隙占用方差則可以衡量算法在負載均衡方面的性能。

1） 案例1

本案例對比本文所提的在線調度算法與傳統SMT算法和MSS算法的調度求解時間。

表2為在不同消息規模下，2種方法的求解時間。由于SMT算法不支持增量調度，所以表中的TT消息數目表示網絡中傳輸的TT消息總數。因為本文所提算法是逐條消息進行調度，因此通過表中每行之間求解時間的差值可以算出本文方法進行增量式調度所需要的時間。由表2可以看出本文所提算法求解速度遠快于傳統SMT算法和MSS算法。本文方法基本可以在毫秒級時間求解生成調度表。同時隨著TT消息的數目的增加，本文算法求解的時間近似線性增加，即隨著已調度消息規模的增加，增量調度每條消息的時間始終不變，約為0.037 ms。而SMT求解器的求解時間近似為指數增長，SMT求解器通過遍歷所有情況得到可行解，當TT消息較少的時候，搜索空間較小且可行解數目較多，因此可以在秒級的時間內得到結果。但隨著TT消息增加，搜索空間驟增，而可行解數目下降，導致求解時間大幅增加。MSS算法的求解時間隨著消息規模的增加近似為平方增長，在TT消息數目不超過200條時，MSS算法的求解時間比SMT算法快，但相比本文所提算法，求解時間仍然過長，約是本文算法求解時間的40倍；而當TT消息數較大時，MSS算法的求解時間遠遠超過本文所提算法的求解時間，當調度2 000條TT消息時，MSS算法的求解時間是本文的500倍左右。對于航電系統而言，實時性至關重要，在消息規模增加時，本文所提算法生成時間仍然較短，更適用于系統的在線調度。

表2 求解時間對比Table 2 Comparison of solution time

2） 案例2

在時間觸發調度求解過程中，除了需要保證TT消息的可調度性外，還需要考慮RC消息的端到端延遲。在確保TT實時調度的前提下，應盡可能降低RC消息的端到端時延。本案例對比基于統一時間分片的在線時間觸發調度算法與離線調度算法（SMT算法）下RC消息的平均端到端延遲和最壞端到端延遲。案例隨機生成100條TT消息和200條RC消息，分別采用SMT求解的調度表和在線時間觸發調度算法生成的調度表進行求解，得到的結果如圖12和表3所示。

表3 調度方法對比Table 3 Comparison of scheduling methods

圖12 調度方法延遲對比Fig.12 Comparison of scheduling method delay？

可以看出，在線式集中調度求解所得的RC消息的平均延遲相比SMT離線調度算法降低了9.98%，RC消息的最壞延遲降低了17.44%。而在線式集中調度求解觸發調度表的時間要遠遠小于SMT求解時間，本文所提方法可以在毫秒級求解得到TT調度表，規劃一條單獨的TT消息，所花費的時間在微秒級別，可以滿足航電網絡在線調度的實時性要求，同時RC消息的最壞延遲仍滿足要求。本案例表明本文方法提升了RC消息的調度性能，同時大大降低了時間觸發調度表的生成時間，使得本文方法更加有可能用于在線生成時間觸發調度表的情況，符合航空電子系統對時間觸發調度生成的實時性要求，從而增強了系統的靈活性。

3） 案例3

大規模流量調度分析。SMT算法求解TT調度表困難，耗時較長，當TT消息上升到500條時，會出現求解時間過長和難以求解的問題。而本文所提在線調度算法仍可以快速求解得到對應的TT調度表。因此，本案例隨機生成不同規模的TT消息，并生成對應規模的RC消息，使得RC消息和TT消息的比例為2∶1，通過仿真得到不同規模下RC消息的最壞端到端測試本文算法在大規模消息下的調度性能表現，其結果如圖13所示。

圖13 大規模消息在線調度最壞延遲Fig.13 Worst-case end-to-end delay of large-scale messages

由圖13（a）可以看出，當TT消息數目為500和1 000時，RC消息的最壞延遲仍較低。當TT消息數目上升到1 500時，即含有1 500條TT消息和3 000條RC消息，此時RC消息的最壞端到端時延明顯變大，但此時的最壞延遲依然滿足RC消息的實時性需求，不會影響規劃的時間觸發調度表的可調度性。

當消息規模上升到2 000條TT消息和4 000條RC消息時，其平均延遲和最壞延遲如圖13（b）所示。當消息達到此規模時，RC的消息的最壞端到端時延顯著增加，此時所規劃的調度表已無法滿足系統的實時性要求。由此可以看出，本文所提算法針對案例中的實驗參數設置，最少可以支持1 500條TT消息和3 000條RC消息規模的實時性調度，同時求解調度表所需時間保持在毫秒級，因此可以應用于在線調度。

4） 案例4

調度成功率對比。流量的調度成功率定義為成功調度的流量數占網絡中總流量數的比例。圖14為2種方法在不同時間觸發流量數下的調度成功率。當消息數為200條時，2種方法調度成功率均為100%，當消息數為500條時，本文算法調度成功率比MSS算法提高了3.5%，而隨著網絡中的TT流數目的進一步增加，MSS方法的調度成功率相比本文算法分別提高3.2%，4.9%和6.1%。由此可得在小規模流量下，本文算法的調度成功率略高于MSS算法，在大規模流量下，本文算法的調度成功率略低于MSS算法。結合案例1的實驗結果，本文算法在流量數目較多時的求解速度遠遠高于MSS方法，因此本文所提算法針對大規模流量時，在保證較高調度成功率的前提下，僅犧牲了一部分調度成功率，但大大提高了算法的求解速度，保證了算法的求解效率和求解成功率。

圖14 時間觸發消息調度成功率Fig.14 Success rate of time-triggered message scheduling

5） 案例5

鏈路時隙利用率和鏈路時隙占用方差對比。鏈路時隙利用率定義為鏈路中被占用的時隙數與鏈路總時隙數之比，鏈路時隙利用率高則代表網絡中的TT流占據了更多的時隙，更加有效地利用了鏈路資源，結果如圖15中折線所示。而鏈路時隙占用方差則定義為網絡鏈路的時隙中傳輸的TT消息長度的方差，以此來衡量網絡的負載均衡程度。鏈路時隙占用方差越小，意味著負載均衡程度越高，結果如圖15中柱狀圖所示。

圖15 鏈路時隙資源對比Fig.15 Network link time slot resource comparison

從圖15可以看出，本文所提算法在不同TT流數目下的性能表現均高于MSS算法，而隨著TT流量規模的增加，2種方法的表現逐漸接近。在TT流數目為20條和1 000條時，本文所提方法的鏈路利用率相比MSS算法分別提高了3.1%和0.6%，在不同TT流數目下本文算法的方差均小于MSS算法。實驗案例表明：由于本文所提算法在調度流時考慮了可調度的時間分片的占用情況，因此避免將流量調度至占用率較高的時間分片中，從而實現了不同鏈路負載的均衡。

4 結 論

本文結合數據分發服務中的發布/訂閱架構和時間觸發調度網絡：

1） 構建基于發布/訂閱架構的時間觸發網絡模型，闡述了時間觸發架構和發布/訂閱架構的結合方式和其中的關鍵問題；

2） 提出基于統一時間分片的在線時間觸發調度算法，通過優化消息的調度空間，大幅提高調度表的求解速度；并可在線性時間復雜度下增量生成調度表，而且可對已有調度表進行增加或刪除，實現在線增量式時間觸發調度；

3） 利用網絡典型拓撲生成實驗案例，驗證了本文所提算法的性能。對于300條消息的網絡，相比傳統的SMT算法，本文算法的RC消息最壞端到端時延降低了17.4%，時間觸發調度表求解速度提升了數千倍；算法可以在毫秒級時間生成時間觸發調度表，并可在微秒時間內增量調度一條TT消息。

本文建立的架構模型及求解方法可以對數據中間件應用于時間觸發網絡消息的在線調度提供理論依據。