基于遺傳算法的運(yùn)載火箭總線消息調(diào)度優(yōu)化設(shè)計(jì)*

張卓政，王亞平

(1.上海航天控制技術(shù)研究所·上?！?01109; 2.上?？臻g推進(jìn)研究所·上海·201112)

0 引 言

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

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

1 1553總線和總線消息

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

1553B總線標(biāo)準(zhǔn)定義的消息傳輸格式有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在核實(shí)命令字后，應(yīng)發(fā)回1個狀態(tài)字給BC，繼之以規(guī)定數(shù)目的數(shù)據(jù)字。

典型的采用了1553B總線進(jìn)行設(shè)計(jì)的運(yùn)載火箭信息的綜合設(shè)計(jì)方案如圖1所示[1]。

圖1 運(yùn)載火箭總線控制系統(tǒng)的拓?fù)浣Y(jié)構(gòu)示意圖Fig.1 Topology diagram of bus control system of launch vehicle

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

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

2 總線消息周期調(diào)度表的數(shù)學(xué)建模

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

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

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

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

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

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

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

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

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

對總線消息傳輸任務(wù)進(jìn)行數(shù)學(xué)建模，所有周期性總線消息傳輸任務(wù)構(gòu)成1個任務(wù)集，則有

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

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

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

τi={Ci，λi，Pi}

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

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

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

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

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

Pi≤λi

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

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

2.4 消息調(diào)度優(yōu)化設(shè)計(jì)的目標(biāo)

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

各個小周期的負(fù)載率為：

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

將任務(wù)分解為優(yōu)化指標(biāo)：

(1)在一個大周期內(nèi)，負(fù)載率最大值M=max(σk)盡可能?。?/p>

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

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

3 消息調(diào)度優(yōu)化算法設(shè)計(jì)

3.1 可調(diào)度性分析

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

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

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

3.2 必要性

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

3.3 算法設(shè)計(jì)

(1)編碼策略

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

(2)適應(yīng)度函數(shù)

根據(jù)優(yōu)化指標(biāo)來構(gòu)造適應(yīng)度函數(shù)，可用于評價個體的優(yōu)劣，通?？蓪⒆钚栴}轉(zhuǎn)化為最大問題，且適應(yīng)度函數(shù)一般要求非負(fù)。對應(yīng)優(yōu)化的3個指標(biāo)，按一定的權(quán)重對其進(jìn)行分配。于是，適應(yīng)度函數(shù)有：

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

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

(3)遺傳操作

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

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

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

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

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

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

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

(4)種群迭代

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

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

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

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

表1 消息傳輸任務(wù)表Tab.1 Message Transmission TaskTable

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

算法參數(shù)如下：

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

迭代次數(shù)：90；

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

交叉概率：0.62；

變異概率：0.48。

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

息負(fù)載趨于均衡，算法合理有效。

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

圖5 前20個Tmin中的消息調(diào)度表Fig.5 Message schedule in Top 20 Tmin

5 結(jié) 論

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