張卓政，王亞平

(1.上海航天控制技術研究所·上?！?01109; 2.上?？臻g推進研究所·上?！?01112)

0 引 言

MIL-STD -1553B是一種軍用電子總線標準，最初被用于飛機內部時分指令、響應式多路數(shù)據(jù)傳輸，具有可確定性、傳輸可靠的特點。經(jīng)過40多年的發(fā)展，由于具備良好的開放性和適應性, MIL-STD -1553B目前在國外已被廣泛應用于航天、航空、航海等領域。國外衛(wèi)星、主要運載火箭、國內新一代運載火箭等都普遍采用了該總線作為數(shù)據(jù)傳輸及共享的通道[1-2]。

作為運載火箭的核心系統(tǒng),控制系統(tǒng)越來越多地采用了1553B總線作為系統(tǒng)的控制和測試總線[3]。控制和測試信息大多以周期性總線消息的方式在總線上時分復用多路傳輸，總線消息周期調度表的設計優(yōu)化對于運載火箭飛行控制的實時性和可靠性而言至關重要。國內外研究人員從不同角度對1553B總線消息周期調度的實現(xiàn)和算法開展了一定研究。在對周期性消息的相位選擇上,文獻[4-5]每次總是優(yōu)先考慮當前負載的最小周期，以降低總線平均延遲和均衡總線負載；文獻[6]更進一步從消息集角度按周期從小到大、首先刻度較短周期的消息以實現(xiàn)相位均衡；文獻[7-8]借鑒單處理器中周期任務的調度方法，來處理1553B總線上的周期消息，將總線消息進行分片傳輸以避免搶占問題。但是，上述文獻對總線負載均衡和最大傳輸時間進行的綜合考慮不多，并且沒有考慮最優(yōu)化設計。因此，本文針對以上問題，采用遺傳算法對總線負載和傳輸時間開展了優(yōu)化設計研究。

1 1553總線和總線消息

1553B總線的傳輸速率為1Mbit/s，總線系統(tǒng)由4部分組成，即總線控制器(BC)、遠程終端(RT)、總線監(jiān)視器(BM)、傳輸介質。BC是指在數(shù)據(jù)總線上被指定執(zhí)行、啟動或開啟信息傳輸任務的唯一終端；BM是被指定執(zhí)行接收總線上傳輸?shù)男畔⒑吞崛〗?jīng)選擇的信息以備后用的終端,它不參與總線的事務處理；所有不作為總線控制器和監(jiān)視器的終端即為RT,其作為各個分系統(tǒng)與總線的接口，在數(shù)量最多時可達31個。

1553B總線標準定義的消息傳輸格式有BC到RT、RT到BC、RT到RT、系統(tǒng)控制方式、廣播方式等共10種，一條1553B消息由3部分組成:命令字、狀態(tài)字和數(shù)據(jù)字。每類字的一個字長為20位,有效信息為16 位,每個字的前3位為單字的同步字頭。命令字只能由BC發(fā)出，狀態(tài)字只能由RT發(fā)出，一條消息的數(shù)據(jù)字最長不超過32個。以RT到BC消息為例：BC向RT發(fā)出1個發(fā)送命令字，該RT在核實命令字后，應發(fā)回1個狀態(tài)字給BC，繼之以規(guī)定數(shù)目的數(shù)據(jù)字。

典型的采用了1553B總線進行設計的運載火箭信息的綜合設計方案如圖1所示[1]。

圖1 運載火箭總線控制系統(tǒng)的拓撲結構示意圖Fig.1 Topology diagram of bus control system of launch vehicle

1553B總線命令/響應式的工作方式和箭載計算機信息集中、功能強大的特點，決定了作為總線上唯一的通信控制器，箭載計算機將統(tǒng)一組織總線消息在各單機之間進行傳輸，以實現(xiàn)控制系統(tǒng)的信息通訊。1553B協(xié)議對于物理層和數(shù)據(jù)鏈路層做出了嚴格的規(guī)范，而其對應用層的總線消息組織調度則依賴于用戶的合理編排。在全箭信息一體化系統(tǒng)中，數(shù)據(jù)總線上傳輸?shù)臄?shù)據(jù)信息在傳輸速度上要受到與該數(shù)據(jù)有關的任務計算時間的限制，這決定了不同類型的數(shù)據(jù)傳輸需要不同的重復周期。例如，典型的姿態(tài)控制周期為20ms，遙測數(shù)據(jù)發(fā)送周期為1000ms。最慢的重復周期(最小的更新速率)常被稱為大周期Tmax，表征了所有周期消息中允許延遲的最大值；最快的重復周期通常被稱為小周期Tmin，表征了所有周期消息中允許延遲的最小值，一般有Tmax=Nmax·Tmin。對于箭上總線傳輸?shù)娜我粋€周期消息τi,一般有Ti=λi·Tmin，λi為周期特征量，λi∈{1，2，…，Nmax}。總線消息周期循環(huán)傳輸示意圖如圖2所示。

圖2 總線消息周期循環(huán)傳輸示意圖Fig.2 Schematic diagram of cyclic transmission of bus messages

在一個大周期內，有Nmax個小周期，所有的周期性消息傳輸至少在某個小周期內出現(xiàn)1次，較快重復周期的消息傳輸則可在多個小周期內出現(xiàn)。作為總線控制器，依據(jù)所處飛行段的不同，箭機將組織所有周期消息在Tmax內完成1次輪詢，在時間刻度上形成1個被稱為消息調度表的掃描表，并進行周期性地執(zhí)行。對于運載火箭上的1553B總線應用而言，消息調度一般采用靜態(tài)調度方法，即總線控制器(BC)按照預先離線設定的消息調度表逐一組織消息傳輸。采用靜態(tài)調度方法的優(yōu)勢是可在飛行時免去執(zhí)行消息的調度算法，其設計過程簡單，消息傳輸?shù)臅r延具有確定性。

2 總線消息周期調度表的數(shù)學建模

2.1 1553B總線周期消息傳輸?shù)奶匦?/h3>

通過研究1553B總線通信模式和運載火箭消息傳輸?shù)囊?，可以?553B總線的周期消息傳輸提取出如下特點：

(1)各總線消息按串行方式傳輸。1553B總線屬于共享式總線，由BC集中控制消息的調度和管理，RT被動響應。與CSMA/CD等必須競爭協(xié)議不同，1553B總線消息按調度表、分時獲得總線使用權，傳輸時間取決于消息的長度；

(2)周期性總線消息傳輸是硬實時任務，基于時間觸發(fā)，截止期就是消息的周期；

(3)消息傳輸為非搶占式調度，傳輸一旦開始便不可中斷；

(4)各個周期性總線消息之間彼此獨立，無相互依賴，且具有相同的優(yōu)先級；

(5)由于是靜態(tài)調度，各個總線消息周期不變，相互之間的傳輸順序在一個大周期內可保持不變；

(6)不考慮消息傳輸過程中的丟包等異常問題。

2.2 1553B總線消息周期調度表的數(shù)學模型

對總線消息傳輸任務進行數(shù)學建模，所有周期性總線消息傳輸任務構成1個任務集，則有

τ={τ1，τ2，…，τn}

一般地，傳輸任務按周期從小到大排列。

對于第i個周期消息傳輸任務，可以用3個元素表征其任務性質：

τi={Ci，λi，Pi}

其中，Ci為消息傳輸時間，包含了命令字、狀態(tài)字、數(shù)據(jù)字、消息響應、消息間隔時間；λi為周期消息的周期特征量，λi∈{1，2，…，Nmax}；Pi為相位，即周期消息首次在某個小周期中傳輸?shù)男蛱枴?/p>

2.3 數(shù)學模型的約束條件

對于已建立的數(shù)學描述，存在一定的約束條件：

(1)在每個小周期內，各個周期性消息傳輸時間的總和必須小于小周期本身的時間長度，即有：

(2)對任一個周期消息傳輸任務，其相位為不大于其周期特征量的正整數(shù)，即有：

Pi≤λi

(3)規(guī)定每個小周期內各個周期性消息的相對次序。

對于1553B總線而言，雖然總線消息沒有優(yōu)先級之分，不可搶占，但是由于消息傳輸由總線控制器按靜態(tài)調度表進行控制，所以總是能夠通過調度表的設計實現(xiàn)控制，即將周期小的消息優(yōu)先傳輸，將周期大的消息滯后傳輸，這在一定程度上體現(xiàn)了消息傳輸?shù)膬?yōu)先級；周期相同的消息，對于火箭控制的重要性等級相同，可以按照控制回路(從傳感器到執(zhí)行器)順序或按照消息長度(從小到大)順序進行傳輸。

2.4 消息調度優(yōu)化設計的目標

對于第i個周期的消息傳輸任務τi={Ci，λi，Pi}，消息傳輸時間Ci和周期特征量λi都是由運載火箭控制系統(tǒng)的特點和控制模式?jīng)Q定的。對于特定的運載火箭，其值一般是固定的。消息調度優(yōu)化設計的任務就是要尋找一種方案，合理分配各個周期性總線消息的相位構成整數(shù)向量P={P1,P2,…，Pn}，使得周期消息傳輸在一個大周期的各個小周期內盡可能均衡地分布。

各個小周期的負載率為：

其中，Mk為在第k個小周期內消息傳輸?shù)膫€數(shù)。對于航天領域，要求典型的總線負載率小于60%，即σk≤60%。

將任務分解為優(yōu)化指標：

(1)在一個大周期內，負載率最大值M=max(σk)盡可能小；

(2)在一個大周期內，負載率差距D=max(σk)-min(σk)盡可能??；

算法的目標則是尋找最優(yōu)的解向量P={Ps}，以實現(xiàn)上述優(yōu)化指標。

3 消息調度優(yōu)化算法設計

3.1 可調度性分析

LIU和Layland[9]對可搶優(yōu)的單處理器周期實時任務調度，提出了單調速率( rate monotonic, RM ) 算法和最小截止期優(yōu)先( earliest dead-line first, EDF) 算法。這2種算法是后續(xù)各種調度算法的基礎，并且證明了單調速率調度(RM)算法在靜態(tài)調度算法中是最優(yōu)的。網(wǎng)絡化控制系統(tǒng)所應用的靜態(tài)信息調度方式，具有不可搶優(yōu)的特點，ZHANG[10]給出了非搶優(yōu)RM調度算法可進行調度的充分非必要條件，由如下定理所述：

一組N個互相獨立、非搶優(yōu)的實時周期任務，任務優(yōu)先級按照標值遞減順序排列(即下標i為1的信息優(yōu)先級最高，下標i為N的信息優(yōu)先級最低)。在RM調度算法下，其可調度條件為，對于所有的i=1,2,…,N，都滿足下列不等式：

顯然，定理可用于1553B總線控制系統(tǒng)周期消息可調度問題的判定。需要指出的是：由于是充分條件，不滿足定理條件的不一定不可調度。不滿足定理條件的消息傳輸任務仍然可以通過調整傳輸時間和周期來滿足定理條件，可調度是可尋優(yōu)的先決條件。

3.2 必要性

總線消息周期調度優(yōu)化問題，實際是已知消息傳輸時間Ci和周期特征量λi，對各周期消息相位合理調度，尋找最優(yōu)的解向量P={Ps}的組合優(yōu)化問題。隨著未來單機設備的增多和對總線消息傳輸需求的增加，周期消息傳輸任務必將更加繁重。對于各周期消息的傳輸調度，可以用窮舉法將所有的可行解列出，但是利用此種方法在龐大的搜索空間中尋找最優(yōu)解顯然是不合適的。遺傳算法[11]是一種借鑒了生物界優(yōu)勝劣汰/適者生存法則的、可自然選擇和自然遺傳的、高度并行/隨機/自適應的搜索方法。遺傳算法尋優(yōu)的機理是：從隨機生成的初始種群開始平行進行，采用基于適應度的策略選擇優(yōu)良個體作為父代；通過父代個體的復制、交叉、變異操作，進化生成子代；當?shù)鷥?yōu)化過程結束時，適應度最優(yōu)的個體所對應的變量值即為優(yōu)化問題的最優(yōu)解。

3.3 算法設計

(1)編碼策略

周期消息傳輸任務τi在周期調度表中第1次出現(xiàn)的位置由相位Pi表征，Pi的值介于1與λi之間，其同時也決定了該周期消息在周期調度表中出現(xiàn)的全部位置。所有周期消息傳輸任務的相位構成的序列就是消息調度的1個可行解。故遺傳算法中個體的基因采用整數(shù)向量編碼方式，取值為Pj={Pj1,Pj2,…，Pjn}。對于每一個個體，若其滿足σk≤60%，則可將其稱為有效染色體。1組有效個體則構成了有效的種群。

(2)適應度函數(shù)

根據(jù)優(yōu)化指標來構造適應度函數(shù)，可用于評價個體的優(yōu)劣，通常可將最小問題轉化為最大問題，且適應度函數(shù)一般要求非負。對應優(yōu)化的3個指標，按一定的權重對其進行分配。于是，適應度函數(shù)有：

F(Pi)=U-rm×M-rd×D-rv×ρ

其中U為足夠大的常數(shù)，以保證適應度函數(shù)非負，rm、rd、rv為權重，且有rm+rd+rv=1。

(3)遺傳操作

選擇操作：首先對種群計算適應度，采用“精英保留”策略對當前種群中適應度最好的2個個體不采取任何操作，而直接將其保留至下一代。經(jīng)典遺傳算法的選擇操作依概率而隨機進行，而由交叉、變異操作導致的劣質個體無法避免，不能防止適應度函數(shù)值較高的個體丟失，存在導致群體評價降低的可能?！熬⒈Ａ簟辈呗跃哂懈玫慕研?，提高了最優(yōu)解產(chǎn)生的效率。對于“精英”以外的個體均要按概率進行交叉或變異，同時每個個體具有1個選擇概率。針對總線消息調度優(yōu)化問題，經(jīng)實際測試發(fā)現(xiàn)，種群中個體的適應度函數(shù)值相差不大，直接采用適應度函數(shù)值進行選擇的方法選擇壓力太小。因此，應采用基于線性排序的選擇方法。

設定VNUM為種群大小，Pos為個體在種群中的序位，SP為選擇壓力，線性排序個體的選擇度按下式計算：

得到選擇度后，采用輪盤賭選擇方法選擇個體。

交叉操作：所謂交叉是指把2個父代個體的部分結構進行替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉概率pc越大，生成新個體的速率越快，進而可能引起遺傳模式的破壞，適應度較高的個體結構會很快丟失；反之，pc越小，算法搜索效率越低，甚至會出現(xiàn)進化停滯。

由于個體基因采用了整數(shù)向量編碼，所以交叉操作對2個父代均勻離散重組，對父個體等概率隨機交換變量值、形成新的個體。

變異操作：變異的基本內容是個體某些基因座上的基因值變動。對于個體Pj={Pj1,Pj2,…，Pjn}，第i個基因座Pji的可選變異值介于1和λi之間。同交叉概率類似，變異概率py越大，個體更新越快；然而，與單純的隨機搜索算法近似，py越小，則算法搜索越緩慢。

對交叉概率和變異概率的選擇，需要根據(jù)具體優(yōu)化的問題試驗選擇、確定合適的值。無論是由交叉或是變異操作生成的新個體，都必須滿足有效個體的限制，這是可行解的最基本的要求。

(4)種群迭代

經(jīng)過遺傳操作的個體集合成下一代新的種群，開始新一輪的迭代。當個體的適應度函數(shù)滿足收斂條件或是迭代次數(shù)達到上限時，計算將終止。優(yōu)化算法的流程如圖3所示。

圖3 總線消息優(yōu)化算法的流程圖Fig.3 Flow chart of bus message optimization algorithm

4 消息調度優(yōu)化算例與驗證

針對某總線控制運載火箭一級飛行段的典型消息傳輸任務采用“精英保留”遺傳算法進行操作，共有20條周期性消息傳輸任務。如表1所示。

表1 消息傳輸任務表Tab.1 Message Transmission TaskTable

經(jīng)驗證，滿足可調度定理的條件。

算法參數(shù)如下：

種群個體數(shù)：30；

迭代次數(shù)：90；

優(yōu)化權重：rm=0.28，rd=0.41，rv=0.31；

交叉概率：0.62；

變異概率：0.48。

仿真計算結果如圖4、圖5所示。由圖4可知，經(jīng)過10代種群遺傳操作后，種群的適應度最大值趨于最優(yōu)結果。圖5給出了優(yōu)化結束后前20個Tmin中消息的調度結果，可見每個Tmin中的消

息負載趨于均衡，算法合理有效。

圖4 優(yōu)化迭代過程中每一代適應度最大值的變化趨勢Fig.4 Trend of maximum fitness of each generation in optimization iteration

圖5 前20個Tmin中的消息調度表Fig.5 Message schedule in Top 20 Tmin

5 結 論

本文在對運載火箭控制系統(tǒng)的1553B總線消息傳輸?shù)奶攸c進行深入分析的基礎上，對總線周期性消息周期調度表進行了數(shù)學建模，提出了基于遺傳算法的、總線消息周期調度表的優(yōu)化設計方法，并結合某運載火箭一級飛行段控制系統(tǒng)的總線消息傳輸任務進行了數(shù)學仿真，驗證了該優(yōu)化設計能夠有效提升總線負載的均衡度，提高了總線傳輸?shù)目煽啃浴?/p>