基于發(fā)布訂閱架構(gòu)的在線時(shí)間觸發(fā)調(diào)度方法

高一凡，何鋒，于思凡

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.2 時(shí)間分片劃分和約束

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

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

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

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

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

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

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

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

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

可得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.4 算法流程示例

采用簡(jiǎn)單拓?fù)鋵?duì)前述調(diào)度生成算法及其流程進(jìn)行說(shuō)明。示例拓?fù)淙鐖D5所示。

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

現(xiàn)有TT消息參數(shù)如表1所示。由表1可以計(jì)算出該組消息的周期最小公倍數(shù)為8 ，最大公約數(shù)為2 ，消息傳輸路徑的最大跳數(shù)為3。對(duì)于第1條消息，周期為2 μs，在超周期內(nèi)需要傳輸4次，并且每次只有1組時(shí)間分片可行解，則第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í)間分片可行解數(shù)目為4，根據(jù)式（17）選擇對(duì)應(yīng)負(fù)載最小的時(shí)間分片分組。第3條消息采用的方法類(lèi)似，放入消息后結(jié)果如圖7所示。

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

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

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

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

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

2.2.1 系統(tǒng)初始化

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

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

數(shù)據(jù)中間件初始化需要3個(gè)步驟：加載全局信息、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)啟動(dòng)的必要消息，初始調(diào)度表的生成也是一個(gè)逐條消息調(diào)度的增量過(guò)程。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法評(píng)價(jià)與分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

圖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í)驗(yàn)案例設(shè)置

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

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

1） 案例1

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

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

表2 求解時(shí)間對(duì)比Table 2 Comparison of solution time

2） 案例2

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

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

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

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

3） 案例3

大規(guī)模流量調(diào)度分析。SMT算法求解TT調(diào)度表困難，耗時(shí)較長(zhǎng)，當(dāng)TT消息上升到500條時(shí)，會(huì)出現(xiàn)求解時(shí)間過(guò)長(zhǎng)和難以求解的問(wèn)題。而本文所提在線調(diào)度算法仍可以快速求解得到對(duì)應(yīng)的TT調(diào)度表。因此，本案例隨機(jī)生成不同規(guī)模的TT消息，并生成對(duì)應(yīng)規(guī)模的RC消息，使得RC消息和TT消息的比例為2∶1，通過(guò)仿真得到不同規(guī)模下RC消息的最壞端到端測(cè)試本文算法在大規(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時(shí)，RC消息的最壞延遲仍較低。當(dāng)TT消息數(shù)目上升到1 500時(shí)，即含有1 500條TT消息和3 000條RC消息，此時(shí)RC消息的最壞端到端時(shí)延明顯變大，但此時(shí)的最壞延遲依然滿足RC消息的實(shí)時(shí)性需求，不會(huì)影響規(guī)劃的時(shí)間觸發(fā)調(diào)度表的可調(diào)度性。

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

4） 案例4

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

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

5） 案例5

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

圖15 鏈路時(shí)隙資源對(duì)比Fig.15 Network link time slot resource comparison

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

4 結(jié) 論

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

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

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

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

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