高一凡，何鋒，于思凡

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

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

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

時間觸發(fā)網(wǎng)絡(luò)的配置并不總是靜態(tài)的，例如網(wǎng)絡(luò)拓?fù)淇赡軙驗楣?jié)點或鏈路故障而改變［17］；或者因為上層應(yīng)用的變化，數(shù)據(jù)傳輸需求發(fā)生改變［18］，導(dǎo)致需要根據(jù)情況更新已生成的時間觸發(fā)調(diào)度表，而靜態(tài)調(diào)度算法通常需要離線計算時間觸發(fā)調(diào)度表，然后將調(diào)度表配置下載到交換機或端系統(tǒng)中。所以，這類方法難以適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓蛘哒{(diào)度新增時間觸發(fā)流量。

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

調(diào)度表求解時間是調(diào)度算法的關(guān)鍵衡量指標(biāo)之一，尤其是在網(wǎng)絡(luò)拓?fù)浜痛{(diào)度流量頻繁變化的動態(tài)場景中。適用于動態(tài)場景的調(diào)度算法通常需要較短的執(zhí)行時間，并且需要在增量消息調(diào)度過程中不影響已調(diào)度消息的實時性，從而完成調(diào)度表的在線求解?？紤]到數(shù)據(jù)分發(fā)服務(wù)在目前應(yīng)用中的高靈活性，其基于發(fā)布/訂閱的信息交互架構(gòu)，為系統(tǒng)提供了松耦合的集成。本文將時間觸發(fā)機制與數(shù)據(jù)分發(fā)服務(wù)進行結(jié)合，提出了基于發(fā)布/訂閱的時間觸發(fā)架構(gòu)模型，實現(xiàn)主題訂閱和消息轉(zhuǎn)發(fā)分離，一方面基于數(shù)據(jù)中間件的集中控制，對時間觸發(fā)流量進行在線調(diào)度，增加了系統(tǒng)的靈活性；另一方面通過時間觸發(fā)網(wǎng)絡(luò)保證關(guān)鍵消息傳輸?shù)膶崟r性。

本文首先提出了基于發(fā)布/訂閱的時間觸發(fā)網(wǎng)絡(luò)架構(gòu)，將數(shù)據(jù)分發(fā)系統(tǒng)的架構(gòu)拓展到了時間觸發(fā)網(wǎng)絡(luò)中，總結(jié)了基于數(shù)據(jù)中間件生成調(diào)度表面臨的問題；并針對上述問題，提出基于時間分片的在線時間觸發(fā)調(diào)度算法，以提高調(diào)度表的求解速度，實現(xiàn)調(diào)度表的在線生成和增量式調(diào)度。

1 基于發(fā)布/訂閱的時間觸發(fā)網(wǎng)絡(luò)架構(gòu)

1.1 數(shù)據(jù)分發(fā)服務(wù)

數(shù)據(jù)分發(fā)服務(wù)（Data Distribution Service，DDS）是一個以數(shù)據(jù)為中心的中間件協(xié)議和接口標(biāo)準(zhǔn)，采用分布式發(fā)布/訂閱體系架構(gòu)，以中間件的形式提供通信服務(wù)。DDS中間件是一個軟件層，它將應(yīng)用程序從操作系統(tǒng)、網(wǎng)絡(luò)傳輸和底層數(shù)據(jù)格式的細(xì)節(jié)中抽象出來，從而允許應(yīng)用程序在不同的操作系統(tǒng)、編程語言和處理體系架構(gòu)之間交換信息。

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

圖1 DDS系統(tǒng)架構(gòu)Fig.1 System architecture of DDS

1.2 時間觸發(fā)調(diào)度

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

在時間觸發(fā)網(wǎng)絡(luò)的輸出端口中，TTE實行混合關(guān)鍵流量調(diào)度策略。為避免非TT流量對TT流量實時性產(chǎn)生影響，非TT流量在TT流量調(diào)度間隙，利用剩余帶寬根據(jù)優(yōu)先級策略進行調(diào)度傳輸，如圖2所示。

圖2 TTE流量調(diào)度Fig.2 Flow scheduling in TTE

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

1.3 基于發(fā)布/訂閱的時間觸發(fā)架構(gòu)模型

基于發(fā)布/訂閱的時間觸發(fā)架構(gòu)模型如圖3所示，相較于傳統(tǒng)DDS架構(gòu)，該架構(gòu)模型解耦了消息的主題訂閱和消息傳輸。通過將主題訂閱和消息轉(zhuǎn)發(fā)分離，將發(fā)布/訂閱模型用于主題管理并將時間觸發(fā)架構(gòu)用于消息轉(zhuǎn)發(fā)，提高了時間觸發(fā)網(wǎng)絡(luò)的靈活性和擴展性。

圖3 基于發(fā)布/訂閱的時間觸發(fā)架構(gòu)Fig.3 Publish/subscribe based time-triggered architecture

消息的主題訂閱基于發(fā)布/訂閱架構(gòu)中數(shù)據(jù)中間件的集中管理，并通過時間觸發(fā)網(wǎng)絡(luò)進行傳輸，從而保證系統(tǒng)的實時性。在該架構(gòu)下，發(fā)布者發(fā)布消息主題到數(shù)據(jù)中間件，訂閱者訂閱相關(guān)主題，數(shù)據(jù)中間件完成主題的統(tǒng)一匹配。同時，數(shù)據(jù)中間件存儲網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和全局消息主題，從而有效地完成消息分類、優(yōu)先級劃分和傳輸路徑規(guī)劃，并生成時間觸發(fā)調(diào)度表。然后，數(shù)據(jù)中間件將生成的時間觸發(fā)調(diào)度表下發(fā)至網(wǎng)絡(luò)中的每個交換機，同時根據(jù)端系統(tǒng)發(fā)布的主題，向端系統(tǒng)返回相匹配的主題并下發(fā)對應(yīng)的調(diào)度表。端系統(tǒng)根據(jù)下發(fā)的調(diào)度表進行時間觸發(fā)消息的發(fā)送和接收，而交換機也根據(jù)調(diào)度表完成消息的路由與轉(zhuǎn)發(fā)。時間觸發(fā)網(wǎng)絡(luò)則保證了系統(tǒng)中消息傳輸?shù)膶崟r性。

基于發(fā)布/訂閱的時間觸發(fā)架構(gòu)模型，結(jié)合時間觸發(fā)網(wǎng)絡(luò)的特點和需求，在傳統(tǒng)DDS系統(tǒng)架構(gòu)的基礎(chǔ)上進行改進：主要包括發(fā)布/訂閱主題和消息關(guān)聯(lián)、QoS等級轉(zhuǎn)化為時間觸發(fā)網(wǎng)絡(luò)消息分級以及在線時間觸發(fā)調(diào)度表的生成3個方面。

發(fā)布/訂閱主題和消息關(guān)聯(lián)。DDS系統(tǒng)應(yīng)用之間根據(jù)主題匹配進行消息推送，而在時間觸發(fā)網(wǎng)絡(luò)中，則通過不同關(guān)鍵級別的消息傳輸信息。因此，該架構(gòu)中每一個主題對應(yīng)一種消息，數(shù)據(jù)中間件主要完成不同應(yīng)用間消息需求的匹配。

QoS等級轉(zhuǎn)變?yōu)闀r間觸發(fā)消息分級。DDS系統(tǒng)的QoS包含范圍較廣，例如帶寬分配、主題及其內(nèi)容存活時間、截止時間等。對于時間觸發(fā)網(wǎng)絡(luò)，消息會按照關(guān)鍵級別分為TT、RC、BE 3類消息，以不同優(yōu)先級進行傳輸。因此需要將QoS轉(zhuǎn)化為傳輸消息的分級，按照不同消息類型和級別進行不同的處理。

在線時間觸發(fā)調(diào)度表的生成。傳統(tǒng)時間觸發(fā)網(wǎng)絡(luò)通常提前生成離線調(diào)度表，而調(diào)度表一旦生成，就難以更改。如果利用數(shù)據(jù)中間件規(guī)劃調(diào)度表，則會產(chǎn)生新的問題。

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

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

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

2 基于統(tǒng)一時間分片的在線時間觸發(fā)調(diào)度算法

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

2.1 在線時間觸發(fā)調(diào)度規(guī)劃方法

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

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

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

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

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

2.1.2 時間分片劃分和約束

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

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

則一個超周期內(nèi)的時間分段數(shù)Ns為

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

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

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

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

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

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

可得

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

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

因為時間分片是將時間分段按照最大跳數(shù)hopmax劃分得到的，當(dāng)時間分片滿足統(tǒng)一長度約束時，相鄰2個時間分片不會發(fā)生重疊。網(wǎng)絡(luò)鏈路的時間分段和時間分片分別為圖4的上、下部分。

圖4 時間分片F(xiàn)ig.4 Time slicing

2.1.3 時間分片調(diào)度

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

在此條件下，下一跳的時間分片始終晚于上一跳時間分片，即滿足TT消息可調(diào)度且不會沖突。同時滿足消息的發(fā)送時間大于消息產(chǎn)生的時間，且消息到達(dá)時間小于消息的截止期限。

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

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

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

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

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

當(dāng)消息從源節(jié)點到目的節(jié)點的路徑跳數(shù)為hopi時，可以求得該消息滿足約束的時間分片的分組數(shù)目為

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

為了避免消息都集中于某個時間分片中，在消息調(diào)度過程中，選擇消息對應(yīng)的全部時間分片分組中負(fù)載最小的分組，以實現(xiàn)鏈路的負(fù)載均衡：

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

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

2.1.4 算法流程示例

采用簡單拓?fù)鋵η笆稣{(diào)度生成算法及其流程進行說明。示例拓?fù)淙鐖D5所示。

圖5 示例網(wǎng)絡(luò)拓?fù)銯ig.5 Example network topology

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

表1 TT消息參數(shù)Table 1 TT message parameters

圖6 調(diào)度TT1消息Fig.6 Scheduling TT1

第2條消息周期為4 μs，在超周期內(nèi)需要傳輸2次，并且每次傳輸?shù)臅r間分片可行解數(shù)目為4，根據(jù)式（17）選擇對應(yīng)負(fù)載最小的時間分片分組。第3條消息采用的方法類似，放入消息后結(jié)果如圖7所示。

圖7 調(diào)度TT2、TT3Fig.7 Scheduling TT2 and TT3

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

圖8 調(diào)度TT4Fig.8 Scheduling TT4

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

2.2 在線時間觸發(fā)調(diào)度算法部署

2.2.1 系統(tǒng)初始化

1） 數(shù)據(jù)中間件初始化

數(shù)據(jù)中間件主要負(fù)責(zé)TT調(diào)度表生成，其根據(jù)時間分片信息計算出時間觸發(fā)調(diào)度表，并下發(fā)調(diào)度表信息至交換機和端系統(tǒng)中。

數(shù)據(jù)中間件初始化需要3個步驟：加載全局信息、TT消息路徑規(guī)劃、TT調(diào)度表求解。

加載全局信息，包含發(fā)布/訂閱架構(gòu)模型的拓?fù)湫畔?、網(wǎng)絡(luò)帶寬、生成網(wǎng)絡(luò)拓?fù)涞南嚓P(guān)數(shù)據(jù)結(jié)構(gòu)。另外，數(shù)據(jù)中間件需要加載初始TT消息，這是系統(tǒng)啟動的必要消息，初始調(diào)度表的生成也是一個逐條消息調(diào)度的增量過程。

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

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

2） 交換機及端系統(tǒng)初始化

接收到數(shù)據(jù)中間件下發(fā)的TT調(diào)度規(guī)劃信息后，交換機的路由模塊和隊列模塊需要進行初始化，同時端系統(tǒng)應(yīng)用開始根據(jù)調(diào)度表發(fā)送消息。

首先，交換機路由模塊需要根據(jù)配置信息生成TT消息的靜態(tài)路由表，以便將接收到的消息迅速轉(zhuǎn)發(fā)至相應(yīng)的端口隊列。同時，解析得到消息中的TT調(diào)度表配置，生成并下發(fā)各個輸出端口的配置信息。

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

2.2.2 在線增量調(diào)度階段

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

圖9 在線增量調(diào)度流程Fig.9 Online incremental flow scheduling

1） 數(shù)據(jù)中間件在線增量時間觸發(fā)調(diào)度

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

2） 端口隊列在線時間觸發(fā)隊列

端口需要根據(jù)新的配置信息，更新時間分片。新增消息時，將消息對應(yīng)的靜態(tài)路由信息保存在路由模塊中，并根據(jù)時間分片長度重新計算新增消息對應(yīng)的時間分片的起始時刻和結(jié)束時刻。

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

3 算法評價與分析

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

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

圖10 案例1～3拓?fù)浣Y(jié)構(gòu)Fig.10 Topology of case study 1～3

圖11 案例4～5拓?fù)浣Y(jié)構(gòu)Fig.11 Topology of cases 4～5

3.2 實驗案例設(shè)置

設(shè)置5個實驗案例，基于圖10和圖11 2種不同規(guī)模的拓?fù)浣Y(jié)構(gòu)，將本文提出的基于統(tǒng)一時間分片的在線時間調(diào)度算法與傳統(tǒng)SMT算法和新提出的MSS算法［24］的性能表現(xiàn)進行對比。

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

1） 案例1

本案例對比本文所提的在線調(diào)度算法與傳統(tǒng)SMT算法和MSS算法的調(diào)度求解時間。

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

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

2） 案例2

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

表3 調(diào)度方法對比Table 3 Comparison of scheduling methods

圖12 調(diào)度方法延遲對比Fig.12 Comparison of scheduling method delay？

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

3） 案例3

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

圖13 大規(guī)模消息在線調(diào)度最壞延遲Fig.13 Worst-case end-to-end delay of large-scale messages

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

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

4） 案例4

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

圖14 時間觸發(fā)消息調(diào)度成功率Fig.14 Success rate of time-triggered message scheduling

5） 案例5

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

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

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

4 結(jié) 論

本文結(jié)合數(shù)據(jù)分發(fā)服務(wù)中的發(fā)布/訂閱架構(gòu)和時間觸發(fā)調(diào)度網(wǎng)絡(luò)：

1） 構(gòu)建基于發(fā)布/訂閱架構(gòu)的時間觸發(fā)網(wǎng)絡(luò)模型，闡述了時間觸發(fā)架構(gòu)和發(fā)布/訂閱架構(gòu)的結(jié)合方式和其中的關(guān)鍵問題；

2） 提出基于統(tǒng)一時間分片的在線時間觸發(fā)調(diào)度算法，通過優(yōu)化消息的調(diào)度空間，大幅提高調(diào)度表的求解速度；并可在線性時間復(fù)雜度下增量生成調(diào)度表，而且可對已有調(diào)度表進行增加或刪除，實現(xiàn)在線增量式時間觸發(fā)調(diào)度；

3） 利用網(wǎng)絡(luò)典型拓?fù)渖蓪嶒灠咐?，驗證了本文所提算法的性能。對于300條消息的網(wǎng)絡(luò)，相比傳統(tǒng)的SMT算法，本文算法的RC消息最壞端到端時延降低了17.4%，時間觸發(fā)調(diào)度表求解速度提升了數(shù)千倍；算法可以在毫秒級時間生成時間觸發(fā)調(diào)度表，并可在微秒時間內(nèi)增量調(diào)度一條TT消息。

本文建立的架構(gòu)模型及求解方法可以對數(shù)據(jù)中間件應(yīng)用于時間觸發(fā)網(wǎng)絡(luò)消息的在線調(diào)度提供理論依據(jù)。