趙長(zhǎng)嘯，戴駿，董方正，李道俊

1.中國(guó)民航大學(xué) 安全科學(xué)與工程學(xué)院，天津 300300

2.民航航空器適航審定技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300300

綜合化是航空電子系統(tǒng)的發(fā)展方向，綜合模塊化航電（Integrated Modular Avionics System，IMA）已在B787、A380 等大型客機(jī)上成功應(yīng)用。隨著對(duì)IMA 航電系統(tǒng)故障封閉、系統(tǒng)重構(gòu)、分區(qū)調(diào)度任務(wù)分配等［1-3］研究的逐步深入，為優(yōu)化IMA 架構(gòu)，研究者們后續(xù)提出了分布式綜合模塊化航電（Distributed Integrated Modular Avionics System，DIMA）架構(gòu)［4-5］。DIMA 綜合了分立式IMA 與集中式IMA 的優(yōu)點(diǎn)［6］，被視為未來(lái)航電系統(tǒng)的發(fā)展方向，DIMA 中所有模塊相連并且提供高容錯(cuò)，因此對(duì)航電系統(tǒng)中確定性、實(shí)時(shí)性需求的保證能力要求更高。現(xiàn)應(yīng)用于IMA 中的機(jī)載網(wǎng)絡(luò)（Avionics Full Duplex Ethernet，AFDX）是基于以太網(wǎng)的事件觸發(fā)（Event-Trigger）網(wǎng)絡(luò)，在實(shí)時(shí)性、確定性等方面難以滿足DIMA 需求［7］。支持時(shí)間觸發(fā)（Time-Trigger，TT）技術(shù)的通信網(wǎng)絡(luò)開始受到機(jī)載系統(tǒng)領(lǐng)域的關(guān)注［8-9］。洛克希德·馬丁公司與空客集團(tuán)研發(fā)的奧賴恩（Orion）飛船［10］，以及NASA 的門戶空間站（Lunar Gateway）均運(yùn)用了支持時(shí)間觸發(fā)的通信網(wǎng)絡(luò)。由IEEE（Institute of Electrical and Electronics Engineers）推出的時(shí)間敏感網(wǎng)絡(luò)（Time Sensitive Network，TSN）是支持TT 技術(shù)的新一代機(jī)載網(wǎng)絡(luò)的候選者之一［11-12］。與同樣支持TT技術(shù)的TTE［8，13-14］相比，TSN 技術(shù)具有配置更加靈活、可按需預(yù)留帶寬、可更好支持不同類型的流量等優(yōu)點(diǎn)。NASA 的星載鏈路項(xiàng)目已啟動(dòng)了對(duì)TSN 技術(shù)的研究，SAE 中的AS-1A 工作組也在尋求與TSN 工作組聯(lián)合，制定航空航天領(lǐng)域的TSN 應(yīng)用標(biāo)準(zhǔn)［15］。

機(jī)載網(wǎng)絡(luò)作為支持航電系統(tǒng)運(yùn)行的基礎(chǔ)網(wǎng)絡(luò)，首先需要解決傳輸任務(wù)的可調(diào)度性，其次需要滿足航電功能的實(shí)時(shí)性需求。眾多研究［16-18］表明，時(shí)間觸發(fā)通信的路由與調(diào)度問(wèn)題可以轉(zhuǎn)換為一個(gè)NP 問(wèn)題。何鋒等［19］針對(duì)機(jī)載時(shí)間觸發(fā)以太網(wǎng)中時(shí)間觸發(fā)（TT）通信調(diào)度給出了多種約束引導(dǎo)下的調(diào)度模型，并形成了基于強(qiáng)化學(xué) 習(xí)（Reinforcement Learning，RL）的調(diào)度方法，對(duì)調(diào)度數(shù)量、消息延遲進(jìn)行了優(yōu)化。Raagaard 等［20］使用混合整數(shù)規(guī)劃（Mixed Integer Programming，MLP）為TT 流量提供調(diào)度方法、最小化TT 隊(duì)列數(shù)與時(shí)延。Dürr 等［21］利用禁忌搜索（Tabu Search）與Heuristic（貪心算法）復(fù)合方法優(yōu)化總傳輸時(shí)長(zhǎng)。Li 等［22］使用基于可滿足性模理論（Satisfiability Modulo Theories，SMT）得到時(shí)間觸發(fā)通信調(diào)度方法，優(yōu)化了調(diào)度速度。Vlk 等［23］開發(fā)了一種高效的調(diào)度方法EPIC，優(yōu)化了調(diào)度數(shù)量與調(diào)度速度。álvarez等［24］提出的主動(dòng)傳播復(fù)制幀（Proactive Transmission of Replicated Frames）機(jī)制允許臨時(shí)錯(cuò)誤鏈接，提高了TSN 網(wǎng)絡(luò)通信安全性。Ali等［25］提出容錯(cuò)瓶頸啟發(fā)式算法，在車載網(wǎng)絡(luò)中使用可靠幀復(fù)制和消除（Frame Replication and Elimination for Reliability）提升TSN 流量傳輸安全性。但是，由于不同的航電系統(tǒng)保證飛機(jī)安全性的能力不同，現(xiàn)有的僅關(guān)注任務(wù)流量屬性的調(diào)度方式，很容易引起風(fēng)險(xiǎn)匯集，使某條鏈路失效，進(jìn)而可能導(dǎo)致多個(gè)安全關(guān)鍵功能失效，在最壞情況下甚至?xí)l(fā)生機(jī)毀人亡的災(zāi)難性事故。

機(jī)載網(wǎng)絡(luò)可分為總線式網(wǎng)絡(luò)和交換式網(wǎng)絡(luò)，對(duì)總線式網(wǎng)絡(luò)（1553B、ARINC429 等）而言，其網(wǎng)絡(luò)的結(jié)構(gòu)決定了不同終端進(jìn)行任務(wù)傳輸時(shí)可共享的物理網(wǎng)絡(luò)資源僅有主干總線，無(wú)法為傳輸任務(wù)分配網(wǎng)絡(luò)資源。當(dāng)主干總線發(fā)生鏈路失效，接入總線的各端系統(tǒng)共享的網(wǎng)絡(luò)資源均會(huì)受到影響，所以總線式網(wǎng)絡(luò)并沒(méi)有鏈路失效風(fēng)險(xiǎn)集中的問(wèn)題。在以AFDX 為代表的事件觸發(fā)型交換式機(jī)載網(wǎng)絡(luò)中，由于其采用交換式結(jié)構(gòu)，任務(wù)傳輸時(shí)的可選網(wǎng)絡(luò)（鏈路）資源較多。在網(wǎng)絡(luò)機(jī)制上AFDX 支持虛擬鏈路（Virtual Link，VL）技術(shù)，AFDX 通過(guò)為不同的VL 分配時(shí)隙，模擬端到端的邏輯連接。針對(duì)AFDX 鏈路失效的相關(guān)研究有：基于VL 對(duì)AFDX 進(jìn)行鏈路風(fēng)險(xiǎn)均衡的RBPP 算法［26］、考慮鏈路失效的AFDX 動(dòng)態(tài)故障樹可靠性分析［27］、利用新型的冗余拓?fù)浣Y(jié)構(gòu)降低鏈路失效等風(fēng)險(xiǎn)［28］。而在時(shí)間觸發(fā)的機(jī)載交換式網(wǎng)絡(luò)TSN 中，由于時(shí)間觸發(fā)技術(shù)是依靠占用時(shí)隙實(shí)現(xiàn)的，所以它與AFDX 緩解鏈路風(fēng)險(xiǎn)集中的具體實(shí)現(xiàn)手段是有所區(qū)別的。

時(shí)間敏感網(wǎng)絡(luò)中的時(shí)間觸發(fā)流量相較于事件觸發(fā)流量有著更好的實(shí)時(shí)性與確定性，時(shí)間觸發(fā)流量實(shí)現(xiàn)高確定性與實(shí)時(shí)性的基礎(chǔ)是提前對(duì)時(shí)間觸發(fā)傳輸任務(wù)提供確定的傳輸路徑和傳輸偏移規(guī)劃。但在機(jī)載網(wǎng)絡(luò)的背景下，任務(wù)支持功能的安全關(guān)鍵程度不同，任務(wù)的安全關(guān)鍵程度也有所差異。在進(jìn)行任務(wù)傳輸路徑規(guī)劃時(shí)，網(wǎng)絡(luò)中某（些）鏈路相較于其他鏈路所承載的安全關(guān)鍵任務(wù)更多或承載的任務(wù)安全關(guān)鍵程度更高（即此鏈路對(duì)于網(wǎng)絡(luò)的安全關(guān)鍵程度高），則會(huì)造成風(fēng)險(xiǎn)匯集，這些鏈路失效時(shí)其承載的任務(wù)會(huì)對(duì)飛機(jī)造成更大影響?；诖?，本研究通過(guò)在機(jī)載時(shí)間敏感網(wǎng)絡(luò)任務(wù)調(diào)度的過(guò)程中對(duì)任務(wù)傳輸路徑與傳輸偏移進(jìn)行約束與優(yōu)化，緩解鏈路的風(fēng)險(xiǎn)匯集現(xiàn)象。

本文提出了機(jī)載TSN 安全關(guān)鍵度均衡的調(diào)度方法，提供了機(jī)載網(wǎng)絡(luò)中鏈路安全關(guān)鍵度的量化模型，建立機(jī)載TSN 安全關(guān)鍵度均衡調(diào)度模型，并基于約束規(guī)劃的方法求解調(diào)度結(jié)果，利用仿真實(shí)驗(yàn)對(duì)調(diào)度方法進(jìn)行分析。針對(duì)機(jī)載時(shí)間敏感網(wǎng)絡(luò)中多數(shù)據(jù)混傳可能導(dǎo)致的風(fēng)險(xiǎn)匯集問(wèn)題，綜合考慮機(jī)載網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)牡膶?shí)時(shí)性與安全性需求，提出了一種鏈路安全關(guān)鍵度均衡的調(diào)度方法?；趯＜以u(píng)價(jià)和熵權(quán)法量化系統(tǒng)任務(wù)安全關(guān)鍵度，通過(guò)任務(wù)映射表征鏈路安全關(guān)鍵度，構(gòu)建機(jī)載TSN 鏈路安全關(guān)鍵度均衡的調(diào)度模型；基于配合約束規(guī)劃的方法構(gòu)建鏈路安全關(guān)鍵度均衡（Link Safety Criticality Balancing，LSCB）調(diào)度方法，在任務(wù)數(shù)分別為50 和100 的場(chǎng)景中LSCB 調(diào)度方法對(duì)于鏈路安全關(guān)鍵度的均衡作用相較于LB 方法和SP 方法均有所提升，表明LSCB 在保證任務(wù)傳輸延遲上界的基礎(chǔ)上，可有效緩解風(fēng)險(xiǎn)匯集。

1 問(wèn)題描述

目前在民用飛機(jī)領(lǐng)域，系統(tǒng)安全性設(shè)計(jì)與評(píng)估主要基于SAE ARP4754 標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)針對(duì)不同功能失效對(duì)飛機(jī)的安全性影響定義了5 類不同的失效狀態(tài)：Ⅰ類（災(zāi)難級(jí)）、Ⅱ類（危險(xiǎn)級(jí)）、Ⅲ類（較大的）、Ⅳ類（較小的）、Ⅴ類（無(wú)安全性影響）。不同航電功能對(duì)飛機(jī)的安全飛行能力保障不同［29］，其關(guān)聯(lián)的失效狀態(tài)類別和數(shù)量也存在較大差異，如航電核心系統(tǒng)支撐了多個(gè)航電功能的處理與傳輸任務(wù)，其失效直接影響飛行安全。某型客機(jī)的功能危害性評(píng)估清單中，航電核心處理系統(tǒng)涉及21 個(gè)Ⅰ類失效狀態(tài)，5 個(gè)Ⅱ類失效狀態(tài)，8個(gè)Ⅲ類失效狀態(tài)，而同機(jī)型中客艙的娛樂(lè)系統(tǒng)不涉及Ⅳ類以上的失效狀態(tài)。機(jī)載互聯(lián)系統(tǒng)是支撐這些航電系統(tǒng)運(yùn)行的數(shù)據(jù)與指令通路，在429、1553 等總線型網(wǎng)絡(luò)中，不同航電任務(wù)在其傳輸時(shí)間內(nèi)對(duì)網(wǎng)絡(luò)傳輸介質(zhì)具有獨(dú)占性，而機(jī)載TSN 網(wǎng)絡(luò)為交換式網(wǎng)絡(luò)時(shí)，多航電任務(wù)共享傳輸介質(zhì)，會(huì)導(dǎo)致不同功能的不同安全關(guān)鍵任務(wù)在網(wǎng)絡(luò)中混合傳輸，可能使某些鏈路風(fēng)險(xiǎn)匯集。如果在任務(wù)鏈路規(guī)劃時(shí)不考慮任務(wù)的安全關(guān)鍵程度，極易導(dǎo)致某條鏈路上承載多個(gè)高安全關(guān)鍵等級(jí)的任務(wù)，一旦該鏈路失效，極端情況下甚至?xí)a(chǎn)生導(dǎo)致機(jī)毀人亡的Ⅰ類失效狀態(tài)。如某型民機(jī)航電系統(tǒng)中，完全喪失通信系統(tǒng)或完全喪失導(dǎo)航系統(tǒng)均屬III 類失效狀態(tài)，但是同時(shí)喪失通信系統(tǒng)和導(dǎo)航系統(tǒng)則屬于Ⅰ類失效狀態(tài)，如圖1 所示。圖1包含3 個(gè)交換機(jī)（SW）與6 個(gè)端系統(tǒng)（ES）；任務(wù)F1、F2、F3分屬通信功能、導(dǎo)航功能、客艙娛樂(lè)功能，其傳輸路徑以不同線型的虛線體現(xiàn)。在SW1與SW3 之間的鏈路為L(zhǎng)S1，S3，由紅色 線表示，它 同時(shí)承載了任務(wù)F1和F2，造成了風(fēng)險(xiǎn)的匯集。如果鏈路LS1，S3發(fā)生失效，就會(huì)引起通信功能、導(dǎo)航功能的故障甚至失效，導(dǎo)致無(wú)法接受的后果［30］。Yang 等［31］結(jié)合廣義隨機(jī)petri 網(wǎng)（GSPN）分析了航電系統(tǒng)安全性，并對(duì)AFDX 機(jī)載網(wǎng)絡(luò)等部分進(jìn)行了深入分析，在AFDX 中網(wǎng)絡(luò)雙通道失效是可能導(dǎo)致IMA 架構(gòu)失效的條件之一。其中鏈路失效是導(dǎo)致網(wǎng)絡(luò)通道失效的原因之一。從各航電功能角度來(lái)說(shuō)，當(dāng)鏈路失效時(shí)，其上的所有傳輸任務(wù)均受影響，可能的失效狀態(tài)包括功能的全部或部分喪失。對(duì)機(jī)載網(wǎng)絡(luò)而言，風(fēng)險(xiǎn)匯集是設(shè)計(jì)和分析中應(yīng)重點(diǎn)關(guān)注的問(wèn)題。本文提出了機(jī)載時(shí)間敏感網(wǎng)絡(luò)鏈路安全關(guān)鍵度均衡調(diào)度方法以緩解風(fēng)險(xiǎn)匯集現(xiàn)象。

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

目前應(yīng)用較多的交換式機(jī)載網(wǎng)絡(luò)AFDX 中，其路徑選擇是以VL 技術(shù)為基礎(chǔ)的，VL 技術(shù)利用網(wǎng)絡(luò)時(shí)隙模擬邏輯上的端到端鏈接，即任務(wù)的路徑由其發(fā)送終端與接收終端所定義的VL 決定，設(shè)計(jì)了VL 就決定了各傳輸任務(wù)的發(fā)送路徑。但在時(shí)間敏感網(wǎng)絡(luò)中，以IEEE 802.1Q 標(biāo)準(zhǔn)（原為802.1Qbv，后全部并入802.1Q）中定義的時(shí)間感知整形器（Time-Aware Shaper，TAS）為基礎(chǔ)，TAS 機(jī)制中門控列表（Gate Control List，GCL）控制交換機(jī)上的各隊(duì)列的GATE，使確定的數(shù)據(jù)幀通過(guò)，網(wǎng)絡(luò)中各交換機(jī)的GCL 需要基于TSN調(diào)度結(jié)果生成。TSN 的調(diào)度便是基于此機(jī)制，通過(guò)在一個(gè)調(diào)度周期（超周期）內(nèi)調(diào)度，使任務(wù)規(guī)劃能夠滿足資源等約束，得到調(diào)度結(jié)果（各任務(wù)的傳輸偏移與傳輸路徑）生成，同樣發(fā)送、接收終端的各任務(wù)的傳輸路徑可以不同。本文方法基于TAS 機(jī)制進(jìn)行時(shí)間敏感任務(wù)的調(diào)度，在實(shí)驗(yàn)中主要關(guān)注滿足各約束基礎(chǔ)上調(diào)度方法對(duì)于鏈路風(fēng)險(xiǎn)集中的緩解情況。

2 機(jī)載TSN 安全關(guān)鍵度均衡調(diào)度模型

2.1 系統(tǒng)模型

TSN 網(wǎng)絡(luò)模型包括節(jié)點(diǎn)集N與鏈路集L，節(jié)點(diǎn)集合N包含網(wǎng)絡(luò)中所有的交換機(jī)（Switch）與終端（End System），n為節(jié)點(diǎn)數(shù)目，鏈接集L包含網(wǎng)絡(luò)中所有節(jié)點(diǎn)間的直接鏈接。Ni為單個(gè)節(jié)點(diǎn)，布爾變量Li，j為網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)Ni與節(jié)點(diǎn)Nj是否存在直接鏈接，當(dāng)Li，j=1 時(shí)表示Ni與Nj存在直接鏈接，為零時(shí)則相反。TSN 節(jié)點(diǎn)間為全雙工，所以對(duì)于任意2 個(gè)相連的節(jié)點(diǎn)Ni和Nj，有Li，j=1=Lj，i∈L。對(duì)于每個(gè)鏈接集L中的鏈路Li，j有以下相關(guān)參數(shù)：δi，j為鏈路Li，j上的傳播延遲；εi為Ni節(jié)點(diǎn)交換機(jī)的結(jié)構(gòu)切換延遲；網(wǎng)絡(luò)中的所有節(jié)點(diǎn)時(shí)鐘同步，設(shè)d為設(shè)備間的時(shí)鐘之間的最大差值。

任務(wù)定義為從一個(gè)終端到另一終端的周期性的數(shù)據(jù)傳輸，F(xiàn)為所有任務(wù)的集合。對(duì)于F中任意一個(gè)任務(wù)Fk（k為任務(wù)編號(hào)）：數(shù)據(jù)由網(wǎng)絡(luò)的發(fā)送端Dk傳輸至網(wǎng)絡(luò)的接收端Rk（由任務(wù)自帶的屬性決定，Dk、Rk對(duì)應(yīng)網(wǎng)絡(luò)中的節(jié)點(diǎn)）；任務(wù)Fk的傳輸持續(xù)時(shí)間為ηk（表示任務(wù)Fk從任何節(jié)點(diǎn)傳輸?shù)狡湎噜徆?jié)點(diǎn)所需的時(shí)間）；任務(wù)Fk的周期為pk。任務(wù)Fk的安全關(guān)鍵度為wk。

2.2 安全關(guān)鍵度

為更好地評(píng)價(jià)風(fēng)險(xiǎn)匯集程度，引入功能、任務(wù)、鏈路的安全關(guān)鍵度，分別表示功能、任務(wù)、鏈路的安全關(guān)鍵程度。

2.2.1 任務(wù)安全關(guān)鍵度

目前較為成熟的民用飛機(jī)安全性設(shè)計(jì)與評(píng)估體系是根據(jù)SAE（Society of Automotive Engineers）組織發(fā)布的ARP4754［32］構(gòu)建的。其中的系統(tǒng)級(jí)功能危險(xiǎn)性評(píng)估（System Function Hazard Assessment，SFHA）確定可能的功能失效狀態(tài)，根據(jù)失效狀態(tài)影響的嚴(yán)重程度對(duì)其進(jìn)行分類，并對(duì)由此產(chǎn)生的安全性需求進(jìn)行確定。在初步系統(tǒng)安全性評(píng)估（Preliminary System Safety Assessment，PSSA）階段將上層安全性需求（研制保證等級(jí)等）進(jìn)行分配。

邀請(qǐng)n位專家依據(jù)評(píng)價(jià)表對(duì)m個(gè)功能進(jìn)行評(píng)價(jià)，得到功能在p個(gè)方面的具體評(píng)價(jià)值之后，再引入客觀賦權(quán)的熵權(quán)法［33］對(duì)各功能的評(píng)價(jià)指標(biāo)的權(quán)重進(jìn)行計(jì)算。

首先計(jì)算各位專家對(duì)u功能a方面的平均評(píng)價(jià)值，u為

式 中：qa，u，v為第v位專家對(duì)于u功能a維度的評(píng)價(jià)值（評(píng)價(jià)維度總數(shù)為p，功能總數(shù)為m）。

進(jìn)一步可計(jì)算某一指標(biāo)的信息熵值為

式中：ea為a維度的信息熵值。

繼續(xù)可計(jì)算出各指標(biāo)的權(quán)重wa為

則最終功能安全關(guān)鍵度gu為

在功能實(shí)現(xiàn)時(shí)，網(wǎng)絡(luò)資源依賴各端系統(tǒng)之間進(jìn)行任務(wù)通信，根據(jù)功能與端系統(tǒng)非對(duì)稱依賴關(guān)系可建立功能-端系統(tǒng)依賴矩陣c（其中cu，i為u功能對(duì)端系統(tǒng)Ni的依賴關(guān)系），那么為實(shí)現(xiàn)某功能的端系統(tǒng)Ni（節(jié)點(diǎn)）的安全關(guān)鍵度zi為

對(duì)任務(wù)而言，依據(jù)其出發(fā)節(jié)點(diǎn)與接收節(jié)點(diǎn)（端系統(tǒng)），任務(wù)Fk的安全關(guān)鍵度wk可表示為

式中：Dk、Rk分別為任務(wù)Fk的發(fā)送端與接收端。

2.2.2 鏈路安全關(guān)鍵度

任務(wù)在機(jī)載TSN 中傳輸時(shí)會(huì)經(jīng)規(guī)劃好的路徑由發(fā)送端向接收端按照固定周期傳輸數(shù)據(jù)幀，在此過(guò)程中，任務(wù)安全關(guān)鍵度會(huì)累積在流經(jīng)的各鏈路上，將si，j作為鏈路Li，j上的安全關(guān)鍵度，H為度量鏈路安全關(guān)鍵度的時(shí)間范圍，設(shè)總待調(diào)度任務(wù)數(shù)量為φ，則可將其表示為

2.3 鏈路安全關(guān)鍵度均衡調(diào)度方法

在處理不同周期的任務(wù)調(diào)度時(shí)，為保證調(diào)度的完整與正確，提出超周期（Hyper Period）概念，H=lcm{pk|Fk∈F}，lcm 為最小公倍數(shù)函數(shù)，計(jì)算式中各任務(wù)周期pk的公倍數(shù)，pk、H取值為實(shí)數(shù)。將H作為一個(gè)調(diào)度周期，在此周期內(nèi)將所有F中的傳輸任務(wù)調(diào)度完成，即一直循環(huán)下去，保證網(wǎng)絡(luò)的正常傳輸。機(jī)載時(shí)間敏感網(wǎng)絡(luò)的調(diào)度結(jié)果分為兩部分：

1）用布爾變量rk，i，j表示任務(wù)Fk是否經(jīng)過(guò)Li，j鏈路（布爾變量Boolean Variable 具有2 種邏輯狀態(tài)的變量，包含2 個(gè)值：1 與0，當(dāng)值為1 時(shí)表示任務(wù)Fk經(jīng)過(guò)Li，j鏈路），即可將任務(wù)的傳輸路徑進(jìn)行表示；

2）變量tk，i表示任務(wù)Fk從節(jié)點(diǎn)Ni發(fā)送時(shí)，第1 次傳輸開始時(shí)的傳輸偏移，可對(duì)任務(wù)在網(wǎng)絡(luò)中傳輸?shù)臓顟B(tài)在時(shí)間維度上進(jìn)行表達(dá)。其取值范圍為0 到周期長(zhǎng)pk之間的整數(shù)。任務(wù)Fk第1 幀最終在到達(dá)接收端的時(shí)刻(rk，i，j=1，Nr=Rs)為：tk，r+ηk+δi，r+εi+d。其 中δi，j、εi、d分別為鏈路延遲、節(jié)點(diǎn)延遲與時(shí)間同步最大誤差。任務(wù)調(diào)度的最終結(jié)果是為所有任務(wù)找到滿足約束并使優(yōu)化目標(biāo)最大化的傳輸路徑與其在路徑各節(jié)點(diǎn)上的傳輸時(shí)刻（即傳輸偏移）。

2.3.1 任務(wù)路徑相關(guān)約束

由于安全關(guān)鍵度是任務(wù)的一種屬性，任務(wù)傳輸路徑的選擇就與其積累到鏈路上的安全關(guān)鍵度結(jié)果相關(guān)，設(shè)置如下的路徑基礎(chǔ)約束。

1）約束1：可選路徑約束。

任務(wù)的傳輸是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的，任務(wù)的傳輸路徑只能在網(wǎng)絡(luò)拓?fù)渲幸汛嬖诘逆溄又羞x擇。即：當(dāng)網(wǎng)絡(luò)拓?fù)渲袃晒?jié)點(diǎn)Ni與Nj間無(wú)直接鏈接時(shí)，任務(wù)路徑不能直接由Ni到Nj，將其表示為

2）約束2：任務(wù)發(fā)送/接收約束。

在約束1 基礎(chǔ)上繼續(xù)分析，任務(wù)最基礎(chǔ)的需求是將任務(wù)所包含的幀由發(fā)送節(jié)點(diǎn)發(fā)出且由接收節(jié)點(diǎn)接收。將此約束表示為

3）約束3：路徑連續(xù)性約束。

為保障任務(wù)路徑的正確與完整，加入以下限制：任務(wù)Fk的完整傳輸路徑應(yīng)由發(fā)送節(jié)點(diǎn)Sk在鏈接集L中鏈接首尾相接直至接收節(jié)點(diǎn)Rk；且在此傳輸過(guò)程中不能有環(huán)形鏈路出現(xiàn)，即同一任務(wù)的路徑中經(jīng)過(guò)同一節(jié)點(diǎn)數(shù)目不大于一次，表示為

2.3.2 任務(wù)傳輸偏移相關(guān)約束

任務(wù)的傳輸偏移是實(shí)現(xiàn)TT 任務(wù)在TSN 中基于TAS 機(jī)制進(jìn)行門控的重要信息，需要保證其正確配置，利用約束規(guī)劃的方法進(jìn)行求解時(shí)需要以下對(duì)傳輸偏移的約束。

1）約束4：釋放/截止約束

此約束對(duì)所有任務(wù)Fk∈F限制傳輸偏移進(jìn)行基本的數(shù)值限定，此值應(yīng)在相對(duì)釋放時(shí)間與相對(duì)截止時(shí)間之間，進(jìn)一步分析傳輸偏移的上限，每個(gè)任務(wù)均需滿足相應(yīng)的時(shí)延要求需要對(duì)接收節(jié)點(diǎn)的接收時(shí)間加入考慮，表示為

2）約束5：傳輸順序約束。

由于TSN 交換機(jī)依據(jù)存儲(chǔ)轉(zhuǎn)發(fā)實(shí)現(xiàn)幀傳輸，為保證幀傳輸?shù)倪B續(xù)性需要對(duì)任務(wù)Fk路徑上的相鄰兩鏈路的傳輸偏移進(jìn)行限定：

3）約束6：資源約束。

此約束的出發(fā)點(diǎn)為網(wǎng)絡(luò)鏈路資源的有限性，某鏈路上同一時(shí)刻不能有幀之間的爭(zhēng)搶，安排幀之間相錯(cuò)的角度處理此約束，即兩任務(wù)若通過(guò)同一鏈路，在此鏈路上兩任務(wù)的所有幀之間均需與對(duì)方相錯(cuò)，表示為

式中：Fk、Fs為可能通過(guò)同一鏈路的兩任務(wù)；x與y為兩任務(wù)之間相對(duì)的發(fā)送次數(shù)，由于在一個(gè)超周期內(nèi)要發(fā)送數(shù)次，需要保證兩任務(wù)的每次發(fā)送均無(wú)資源沖突。

4）約束7：幀隔離約束。

Vlk 等［34］和Craciunas 等［35］學(xué)者指出：若有幀在傳輸過(guò)程中丟失，那么分配給此幀的時(shí)隙可能由于TSN 隊(duì)列的FIFO（First In First Out）屬性，被TSN 交換機(jī)用于隊(duì)列中其之后的幀傳輸，造成網(wǎng)絡(luò)中TT 流量傳輸混亂，無(wú)法保證時(shí)間觸發(fā)機(jī)制生效，如圖2 所示。為避免此問(wèn)題，加入幀隔離約束對(duì)發(fā)送至同一交換機(jī)接收端的2 個(gè)任務(wù)的傳輸偏移進(jìn)行限制，對(duì)這2 個(gè)任務(wù)的幀進(jìn)行隔離，表示為

圖2 幀隔離約束示意圖Fig.2 Diagram of frame isolation constraint

與式（11）相似，F(xiàn)k，F(xiàn)s為可能通過(guò)同一鏈路的兩任務(wù)，x與y為兩任務(wù)之間相對(duì)的發(fā)送次數(shù)，此約束也需要保證兩任務(wù)在超周期內(nèi)的每次傳輸時(shí)均進(jìn)行了幀隔離措施。

2.3.3 安全關(guān)鍵度均衡

鏈路安全平均值計(jì)算式為

為了避免安全關(guān)鍵度集中，盡量平衡不同鏈路失效時(shí)對(duì)整個(gè)網(wǎng)絡(luò)的影響，引入鏈路安全關(guān)鍵度的方差var(s)，約束規(guī)劃的最終優(yōu)化目標(biāo)為

3 約束規(guī)劃方法

約束規(guī)劃［36］（Constraint Programming）是一種通過(guò)對(duì)全局單一資源約束的高效過(guò)濾方法，在調(diào)度、優(yōu)化問(wèn)題中廣泛使用。其中用區(qū)間變量（Interval Variables）的形式表示相關(guān)待調(diào)度任務(wù)，相應(yīng)的約束與優(yōu)化目標(biāo)也需要進(jìn)行規(guī)范。

3.1 基于區(qū)間變量約束

區(qū)間變量具有4 個(gè)維度的參數(shù)，分別為區(qū)間變量是否存在、區(qū)間變量的開始時(shí)間、完成時(shí)間和其兩者的差值，用約束規(guī)劃中特有的方式PresenceOf、StartOf、EndOf、LengthOf、Alternative、StartBeforeStart 和NoOverlap 等表示。因此可用區(qū)間變量與輔助區(qū)間變量Ψk，i、ζk，i將 約束1～約束7 與優(yōu)化目標(biāo)進(jìn)行基于區(qū)間變量的實(shí)現(xiàn)。

3.1.1 任務(wù)路徑的區(qū)間變量約束

約束1～約束3可利用區(qū)間變量實(shí)現(xiàn)為式（18）～式（20）：

1）約束1：可選路徑約束。

2）約束2：任務(wù)發(fā)送/接收約束。

3）約束3：路徑連續(xù)性約束。

3.1.2 任務(wù)傳輸偏移的區(qū)間變量約束

約束4～約束7可利用區(qū)間變量實(shí)現(xiàn)為式（21）～式（24）：

1）約束4：釋放/截止約束。

2）約束5：傳輸順序約束。

3）約束6：資源約束。

4）約束7：幀隔離約束。

約束5 是通過(guò)約束StartBeforeStart（I1，I2，t）實(shí)現(xiàn)的，它限制了區(qū)間變量I2和區(qū)間變量I1的開始時(shí)間的差值至少是t個(gè)時(shí)間單位，若任一個(gè)區(qū)間變量不存在，則滿足約束。約束6 通過(guò)NoOverlap 約束，其定義為其中的區(qū)間變量組之間無(wú)交疊。

3.1.3 基于區(qū)間變量的優(yōu)化目標(biāo)

優(yōu)化目標(biāo)可格式化為

3.2 Benders 分解

Benders 分解自提出以來(lái)已被廣泛應(yīng)用［37］，此方法可將復(fù)雜規(guī)劃問(wèn)題分解為主問(wèn)題與子問(wèn)題。前文描述約束規(guī)劃模型同時(shí)考慮了任務(wù)路徑與任務(wù)的傳輸偏移，在此依據(jù)Benders 分解將此問(wèn)題分為2 個(gè)階段：首先求解任務(wù)路徑問(wèn)題，然后再對(duì)傳輸偏移進(jìn)行求解。如圖3 所示，先為路徑問(wèn)題建立模型，其中包含約束1～約束3 與可能的調(diào)度狀態(tài)約束，調(diào)度狀態(tài)約束可標(biāo)記某一種求解路徑方案不可行。如果路徑模型無(wú)可行解，直接結(jié)束并提示無(wú)法解決此問(wèn)題；若其有可行解，此時(shí)任務(wù)路徑已經(jīng)變?yōu)橐阎?，進(jìn)而構(gòu)建由約束4～約束7 組成的調(diào)度子問(wèn)題若找到可行解即結(jié)束，若沒(méi)有找到可行解，則添加一個(gè)調(diào)度狀態(tài)約束，并再次重復(fù)前述流程。

圖3 Benders 分解流程Fig.3 Benders decomposition process

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)主要關(guān)注不同的調(diào)度方法的鏈路安全關(guān)鍵度集中上的調(diào)度差異，采用約束規(guī)劃方法，將其與同樣基于約束規(guī)劃的負(fù)載均衡（Load Balancing，LB）、最短路徑（Short Path，SP）的無(wú)等待調(diào)度2 種調(diào)度方法進(jìn)行對(duì)比。實(shí)驗(yàn)采用圖4 中典型的機(jī)載網(wǎng)絡(luò)拓?fù)洌ˋIRBUS A380），其中有9 個(gè)交換機(jī)（節(jié)點(diǎn)編號(hào)1～9）、18 個(gè)終端（節(jié)點(diǎn)編號(hào)10～27），共27 節(jié)點(diǎn)；隨機(jī)生成發(fā)送、接收端；根據(jù)機(jī)載網(wǎng)絡(luò)任務(wù)情況［26，38］設(shè)置調(diào)度任務(wù)的周期pk在300 μs、800 μs、1 000 μs、1 500 μs中選取，設(shè)置傳輸持續(xù)時(shí)間ηk有：ηk∈［1，10］，鏈路傳播延遲統(tǒng)一設(shè)置為0.1，交換機(jī)的結(jié)構(gòu)切換延遲設(shè)置為0.5 μs。

圖4 實(shí)驗(yàn)所用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.4 Network topology used in the experiment

本文采用采用支持Benders 分解的IBM ILOG CPLEX Optimization studio［39-40］實(shí) 現(xiàn)（軟件版本為22.1），文獻(xiàn)［39-40］對(duì)此平臺(tái)特性進(jìn)行了詳細(xì)介紹。

實(shí)驗(yàn)中使用的任務(wù)安全關(guān)鍵度基于此拓?fù)渚W(wǎng)絡(luò)中的功能安全關(guān)鍵度，如表1 所示，實(shí)驗(yàn)選取專家數(shù)n=5，評(píng)價(jià)方面數(shù)量p=3，3 個(gè)方面分別為對(duì)飛機(jī)影響、對(duì)機(jī)組影響和對(duì)乘客影響。本實(shí)驗(yàn)案例中5 位專家對(duì)這3 個(gè)方面按照表2 的評(píng)分標(biāo)準(zhǔn)進(jìn)行打分。最終得到的數(shù)據(jù)如表3 所示。

表1 航電功能安全關(guān)鍵度Table 1 Safety criticality of avionics function

表2 安全關(guān)鍵評(píng)價(jià)表Table 2 Safety criticality evaluation

表3 功能安全關(guān)鍵度專家打分結(jié)果Table 3 Expert scores of functional safety criticality

參考相關(guān)分析［41-42］，將功能安全關(guān)鍵度分為3 個(gè)評(píng)價(jià)指標(biāo)進(jìn)行量化：飛機(jī)影響（A）、機(jī)組影響（B）及乘客影響（C）。將重要程度劃分為4 個(gè)等級(jí)，并為各個(gè)等級(jí)指定量化范圍。

進(jìn)一步依據(jù)熵權(quán)法對(duì)航電功能安全關(guān)鍵度計(jì)算，其中涉及的數(shù)值、具體功能對(duì)應(yīng)關(guān)系［43］如表1 所示。在本實(shí)驗(yàn)中采取50 條隨機(jī)節(jié)點(diǎn)任務(wù)集，根據(jù)端系統(tǒng)與任務(wù)的對(duì)應(yīng)關(guān)系即可得到任務(wù)安全關(guān)鍵度。

4.2 實(shí)驗(yàn)結(jié)果與分析

將得到的安全關(guān)鍵度，在上文所提到的實(shí)驗(yàn)平臺(tái)中進(jìn)行不同調(diào)度方法的調(diào)度結(jié)果求解，并將最終的調(diào)度結(jié)果進(jìn)行整理。圖5 和圖6 為3 種不同調(diào)度方法調(diào)度結(jié)果分別在任務(wù)數(shù)為50和100 的2 種場(chǎng)景下的鏈路安全關(guān)鍵度（Link Safety Criticality，LSC）分布情況。表4 為計(jì)算指標(biāo)結(jié)果。

表4 不同方法調(diào)度結(jié)果Table 4 Scheduling results of different methods

圖5 鏈路安全關(guān)鍵度分布情況（任務(wù)數(shù)為50）Fig.5 Distribution of link safety criticality（number of tasks：50）

圖6 鏈路安全關(guān)鍵度分布情況（任務(wù)數(shù)為100）Fig.6 Distribution of link safety criticality（number of tasks：100）

對(duì)比任務(wù)數(shù)為50 的圖5 不難看出，LB 方法將鏈路L3，5與鏈路L5，7上 的LSC 向L4，6上集中，造成L4，6上 的LSC 高 至15，為全方法最高值，而SP 則是將原本在L4，6與L6，8上的LSC 集中在L1，3、L3，5與L5，7之上，造成LSC 較高的鏈 路較多。LSCB 將L4，6上 的LSC 向L3，5上進(jìn)行轉(zhuǎn)移，使LSC 集中問(wèn)題得到緩解；同時(shí)也將L1，2、L4，6、L5，7等鏈路上的LSC 指標(biāo)進(jìn)行降低。在時(shí)延指標(biāo)中各調(diào)度方法的任務(wù)時(shí)延均值較低，且將調(diào)度最大值維持在可接受水平。

從任務(wù)數(shù)為100 的圖6 可以看出LSCB 方法與LB 方法和SP 方法相比，調(diào)度結(jié)果有一定優(yōu)勢(shì)，但由于實(shí)驗(yàn)任務(wù)集的任務(wù)需要在節(jié)點(diǎn)3、4 和節(jié)點(diǎn)5、6 兩側(cè)相互傳輸?shù)娜蝿?wù)量相對(duì)固定，在L3，5和L4，6上的安全關(guān)鍵度之和一定程度上已固定（如一任務(wù)從節(jié)點(diǎn)17 向節(jié)點(diǎn)21 發(fā)送，勢(shì)必要經(jīng)過(guò)L3，5和L4，6其中的一條），兩鏈路上的LSC 只能相互均衡，無(wú)法向全局拓?fù)渲衅渌溌肪?。但LSC 在L1，9、L2，9、L3，9、L4，9上均衡了更多來(lái)自于L1，3與L2，4的LSC，使全局的集中度更低。因此，LSCB 方法有著更好的鏈路安全關(guān)鍵度均衡能力。

在任務(wù)數(shù)為50 的場(chǎng)景中，LSCB 調(diào)度方法對(duì)鏈路安全關(guān)鍵度的均衡作用相較于LB 方法和SP 方法分別提升了7.1%和25%。在任務(wù)數(shù)為100 的場(chǎng)景中分別提升了17%和18%。結(jié)合2 個(gè)實(shí)驗(yàn)場(chǎng)景可知，LSCB 方法的鏈路安全關(guān)鍵度的均衡能力最好，LB 方法次之，SP 方法最差。由于LB 方法對(duì)負(fù)載的均衡能力，也使其在一定程度上具備鏈路風(fēng)險(xiǎn)均衡能力，但是當(dāng)任務(wù)數(shù)增加時(shí)，由于其并未在約束與優(yōu)化目標(biāo)中考量緩解LSC 集中現(xiàn)象，導(dǎo)致其均衡能力有限；SP 方法的任務(wù)傳輸、接收節(jié)點(diǎn)與拓?fù)湓谝欢ǔ潭壬暇蜎Q定了其發(fā)送路徑，無(wú)法對(duì)LSC 的集中進(jìn)行緩解。實(shí)驗(yàn)表明，LSCB 仍有一定的均衡能力，可以作為機(jī)載TSN 等高安全需求場(chǎng)景下利用任務(wù)調(diào)度來(lái)均衡安全關(guān)鍵度的一種方法。

5 結(jié)語(yǔ)

本文主要針對(duì)機(jī)載TSN 網(wǎng)絡(luò)在任務(wù)傳輸時(shí)出現(xiàn)的風(fēng)險(xiǎn)匯集現(xiàn)象進(jìn)行了研究，提出了一種優(yōu)化鏈路安全關(guān)鍵均衡的調(diào)度方法LSCB。

1）對(duì)功能安全關(guān)鍵度進(jìn)行量化，配合熵權(quán)法對(duì)不同維度賦權(quán)，并得到鏈路安全關(guān)鍵度計(jì)算方法。

2）基于機(jī)載TSN 鏈路安全調(diào)度對(duì)任務(wù)傳輸偏移與任務(wù)傳輸路徑進(jìn)行模型構(gòu)建。

3）基于約束規(guī)劃的方法對(duì)調(diào)度模型中約束進(jìn)行標(biāo)準(zhǔn)化改寫，并將LSCB 與LB、SP 調(diào)度方法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明：相較于其他2 種調(diào)度方法，LSCB 方法對(duì)于鏈路安全關(guān)鍵度集中有一定的緩解作用（7.1%～25%）；通過(guò)具體分析可知，隨著任務(wù)數(shù)的增多，LSCB 方法相較于LB 方法在均衡作用上的優(yōu)勢(shì)更加明顯；而在任務(wù)數(shù)較多的場(chǎng)景下在拓?fù)渲袝?huì)由于某部分的替代路徑不足而無(wú)法進(jìn)一步均衡LSC。

目前該方法配合的求解方法為約束規(guī)劃，并不能達(dá)到特別高的求解效率，下一步計(jì)劃將更高效的尋優(yōu)方法與其匹配，以提高調(diào)度速度與質(zhì)量。