湯 宇，李 峭，賈琪明

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

0 引 言

在實(shí)時(shí)分布式系統(tǒng)中，采用時(shí)間觸發(fā)通信 （time－triggered，TT）可以避免數(shù)據(jù)幀爭(zhēng)用物理鏈路，保證數(shù)據(jù)交換的嚴(yán)格的實(shí)時(shí)性，提高了離線任務(wù)負(fù)載均衡分配的效果。

時(shí)間觸 發(fā) 以 太 網(wǎng) （time－triggered Ethernet，TTE）［1，2］在交換式網(wǎng)絡(luò)的環(huán)境下實(shí)現(xiàn)了可以精確到亞微秒量級(jí)的分布式時(shí)鐘同步，為時(shí)間觸發(fā)通信的調(diào)度提供了必要條件。

TTE調(diào)度表設(shè)計(jì)需要考慮的因素包括網(wǎng)絡(luò)的物理拓?fù)?、虛擬鏈路拓?fù)?，以及時(shí)鐘同步拓?fù)?，并且與分布式綜合應(yīng)用的處理和通信任務(wù)的分配有關(guān)，這具體體現(xiàn)于：

（1）總線形網(wǎng)絡(luò) （如：SAE AS6003標(biāo)準(zhǔn)［3］定義的TTP）的時(shí)間觸發(fā)調(diào)度面對(duì)的是共享介質(zhì)的局域網(wǎng)，只需要一套公共的調(diào)度表；而對(duì)于TTE這種交換式網(wǎng)絡(luò)，交換機(jī)端口之間是空分隔離的，不同網(wǎng)段可以同時(shí)傳輸不同的數(shù)據(jù)包；

（2）在傳統(tǒng)的分布式任務(wù)分配中，采用分步驟的分配方法，通常先分配處理任務(wù)，然后再依據(jù)分配的結(jié)果對(duì)通信任務(wù)的調(diào)度，通信任務(wù)之間被認(rèn)為是異步的；而在TTE網(wǎng)絡(luò)中，為了實(shí)現(xiàn)分布式時(shí)鐘精確同步下更深層次的應(yīng)用綜合，需要考慮處理任務(wù)和通信任務(wù)之間的同步配合關(guān)系，它們的分配與設(shè)計(jì)的優(yōu)化相關(guān)聯(lián)。

本文針對(duì)以TTE網(wǎng)絡(luò)為互連基礎(chǔ)設(shè)施的分布式綜合系統(tǒng)，提出了一種將各個(gè)任務(wù)的多種設(shè)計(jì)約束轉(zhuǎn)化定義為代價(jià)函數(shù)，并通過建立處理任務(wù)間的通信關(guān)系矩陣，將通信任務(wù)作為處理任務(wù)的參數(shù)，由此給出處理任務(wù)和通信任務(wù)統(tǒng)一地映射到嵌入式資源的方法，其目的在于優(yōu)化整網(wǎng)的任務(wù)分配關(guān)系，提高整網(wǎng)中的節(jié)點(diǎn)和鏈路上的負(fù)載均衡程度，完成離線時(shí)刻調(diào)度表生成的預(yù)設(shè)計(jì)過程。

1 網(wǎng)絡(luò)與任務(wù)模型的模型

1.1 時(shí)間觸發(fā)以太網(wǎng)簡(jiǎn)介

時(shí)間觸發(fā)以太網(wǎng)，采用時(shí)間觸發(fā)代替事件觸發(fā)的方式將通信任務(wù)通過合理的調(diào)度定時(shí)觸發(fā)發(fā)送，可避免數(shù)據(jù)幀爭(zhēng)用物理鏈路，保證實(shí)時(shí)性。其相應(yīng)的規(guī)范由TTTech公司發(fā)布，并在2011年形成SAE AS6802標(biāo)準(zhǔn)［4］。時(shí)間觸發(fā)通信可以支持遠(yuǎn)程任務(wù)之間同步處理，有望實(shí)現(xiàn)分布式綜合模塊化 （distributed integrated modular architecture，DIMA）的體系結(jié)構(gòu)，并應(yīng)用于航空、航天等嵌入式平臺(tái)，例如：美國(guó)Orion載人飛船［5］采用1000BASE－CX物理層和雙冗余配置的TTE網(wǎng)絡(luò)綜合互連方案，考慮了抗惡劣環(huán)境的高完整性。

1.2 網(wǎng)絡(luò)的物理拓?fù)?/h3>

在綜合化航空電子系統(tǒng)中，采用交換機(jī)骨干網(wǎng)絡(luò)將具有處理資源的嵌入式主機(jī)通過全雙工的方式接入到交換網(wǎng)絡(luò)中，處理任務(wù)不受限于主機(jī)的物理邊界，在一定的約束下，軟件構(gòu)件可以在不同的標(biāo)準(zhǔn)化處理模塊中運(yùn)行。具體到DIMA架構(gòu)［6，7］下，異構(gòu)的處理主機(jī)，如：LRM集群或具有開放資源的LRU可以通過TTE網(wǎng)絡(luò)互連進(jìn)行綜合化分區(qū)管理下的同步并行處理。圖1所示的是DIMA架構(gòu)下的航空電子互連的簡(jiǎn)單的例子。

圖1 DIMA架構(gòu)下的航空電子互聯(lián)

為了求解任務(wù)分配問題，將功能分區(qū)相同的處理主機(jī)及其直接接入的交換結(jié)構(gòu)抽象為一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，而節(jié)點(diǎn)之間的鏈路則由交換機(jī)之間的骨干鏈路所構(gòu)成。例如：對(duì)于圖1所示的航空電子系統(tǒng)，將執(zhí)行相同功能的ES3、ES4連同它們之間的交換機(jī)抽象為一個(gè)處理集群，抽象后所形成的拓?fù)浣Y(jié)構(gòu)如圖2所示。

圖2 抽象出的拓?fù)浣Y(jié)構(gòu)

根據(jù)功能抽象后，用有向圖G＝ （V，E）來表示處理節(jié)點(diǎn)之間的通信關(guān)系，如圖2所示。其中V為網(wǎng)絡(luò)節(jié)點(diǎn)集合，在TTE網(wǎng)絡(luò)中為交換結(jié)構(gòu)和與之相連接的處理機(jī)的合集，V＝ （v1，v2，…，vN），N為節(jié)點(diǎn)數(shù)量。E為連接節(jié)點(diǎn)的鏈路的集合，Q為鏈路數(shù)量，節(jié)點(diǎn)vi到節(jié)點(diǎn)vj（vi∈V，vj∈V）的鏈路e（e∈E）可以表示為eij。

采用連接矩陣A＝ （aij）N×N定義節(jié)點(diǎn)之間的聯(lián)通關(guān)系，其中aij為

其中aij＝1表示節(jié)點(diǎn)vi有到節(jié)點(diǎn)vj（vi∈V，vj∈V）有鏈路連接，aij＝0則表示沒有連接。

1.3 處理任務(wù)與通信任務(wù)

考慮到處理任務(wù)有可能分解到不同的綜合化處理機(jī)運(yùn)行，根據(jù)可以并發(fā)執(zhí)行的部分，首先對(duì)待分配的處理任務(wù)進(jìn)行分解，作為簡(jiǎn)化的假設(shè)，忽略分解后帶來的額外開銷。同時(shí)，對(duì)于任務(wù)之間由于應(yīng)用需求而帶來的依賴關(guān)系，通過將具有依賴性的關(guān)系的部分融合在一起。

分解后的處理任務(wù)集合用P表示，P＝ （p1，p2，…，pM），M為處理任務(wù)的數(shù)量，用μk表示處理任務(wù)pk在節(jié)點(diǎn)上所需要占用的資源量。

通信任務(wù)則對(duì)應(yīng)著一個(gè)處理任務(wù)到另一個(gè)處理任務(wù)的應(yīng)用層 “端到端”的有向流量。因而通信任務(wù)集合用C表示，那么對(duì)于任意c∈C，可以用三元組 （sk，tk，λk）表示，sk表示通信任務(wù)的發(fā)出任務(wù)，tk表示通信任務(wù)的接收任務(wù)，λk表示通信任務(wù)在的流量。

在TTE網(wǎng)絡(luò)中，時(shí)間觸發(fā)通信任務(wù)具有精確的時(shí)間確定性，使得處理任務(wù)和通信任務(wù)之間具有了明確的關(guān)聯(lián)性。因而，可以建立處理任務(wù)間的通信關(guān)系矩陣B＝ （bij）N×N，其中bij為

通過建立處理任務(wù)間的通信關(guān)系矩陣，就可以將通信任務(wù)轉(zhuǎn)化為處理任務(wù)的一個(gè)參數(shù)，從而能夠統(tǒng)一地完成處理任務(wù)和通信任務(wù)的分配，達(dá)到更好的優(yōu)化效果。

2 任務(wù)分配的優(yōu)化

2.1 目標(biāo)函數(shù)的確定

由于TTE網(wǎng)絡(luò)［1，3］通信本身所具有的時(shí)間確定性，并且在TTE網(wǎng)絡(luò)中，節(jié)點(diǎn)和鏈路上的負(fù)載均衡可以顯著降低離線調(diào)度表生成的不可行的概率，同時(shí)也能保證整個(gè)網(wǎng)絡(luò)中的各個(gè)部分都能有足夠的空閑時(shí)間片剩余，以保證RC和BE任務(wù)的正常傳輸。因而本文使用TTE網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路上的負(fù)載均衡程度來衡量任務(wù)分配方法的性能。

由于在給定的分配方案下，由于各個(gè)任務(wù)的粒度不同，使得各節(jié)點(diǎn)和鏈路上負(fù)載不可能完全一致，但可以通過定義如下的指標(biāo)進(jìn)行衡量

其中

由于上述定義的二次的指標(biāo)與統(tǒng)計(jì)中方差的定義類似，所以這里也稱之為衡量負(fù)載均衡的 “方差”。本文以TTE網(wǎng)絡(luò)中處理任務(wù)和通信任務(wù)的方差之和作為目標(biāo)函數(shù)，目標(biāo)函數(shù)越小，則說明其負(fù)載均衡度越好

解集X＝ （x1，x2，…，xM），xk≤N，xk∈N＋，分別表示各個(gè)處理任務(wù)pk分配到第xk個(gè)節(jié)點(diǎn)上。

由于各個(gè)節(jié)點(diǎn)的處理能力以及各鏈路的帶寬都是有限的，在分配時(shí)要考慮到各節(jié)點(diǎn)和鏈路的約束條件，因而本文采用懲罰函數(shù)的方法對(duì)非可行解進(jìn)行處理，即在目標(biāo)函數(shù)中加入懲罰函數(shù)，將有約束極值問題轉(zhuǎn)化為帶有罰函數(shù)的極值問題

式中：hk——節(jié)點(diǎn)vk在解集X 中所使用的資源量，hmaxk——節(jié)點(diǎn)vk所能處理的最大資源量，dk——鏈路ek在解集X中所使用的帶寬，dmaxk——鏈路ek的最大帶寬。M為一個(gè)比目標(biāo)函數(shù)值大很多的正整數(shù)。在滿足各節(jié)點(diǎn)和鏈路的約束條件的情況下，hk－h(huán)maxk≤0，dk－dmaxk≤0恒成立，G（X）＝f（X）＋M×0，為可行解所得的函數(shù)值，從而起到剔除的作用。在實(shí)際問題中，某些處理任務(wù)只能在特定的一個(gè)或者幾個(gè)處理器中處理，例如：某些信號(hào)處理只能在接近傳感器的前端進(jìn)行，這也可以使用罰函數(shù)表示這種選擇特定處理節(jié)點(diǎn)的強(qiáng)約束關(guān)系。

2.2 通信任務(wù)路徑選擇

由于TTE網(wǎng)絡(luò)拓?fù)渌哂械娜我庑?，在各個(gè)節(jié)點(diǎn)間會(huì)存在多條可行的通信任務(wù)路徑。在通信任務(wù)路徑的選擇過程中，若選擇最短通路 （采用圖論中的Dijkstra算法［8］得出）則會(huì)導(dǎo)致某些鏈路上的負(fù)載過大，影響鏈路的負(fù)載均衡；若選擇負(fù)載最低的通路則會(huì)導(dǎo)致轉(zhuǎn)跳次數(shù)較多，增大整網(wǎng)的負(fù)載。同時(shí)，由于通信任務(wù)路徑選擇需要在每次目標(biāo)函數(shù)的計(jì)算過程中都進(jìn)行一次，因而，提出了一種快速的通信任務(wù)路徑選擇方法，具體步驟如下：

步驟1 將發(fā)出節(jié)點(diǎn)和接受節(jié)點(diǎn)間有鏈路直接相連的通信任務(wù)的路徑確定為相連的鏈路。

步驟2 把剩余的任務(wù)按照最少轉(zhuǎn)跳數(shù)tmin和所占帶寬d的乘積的大小進(jìn)行排序，從而得到剩余任務(wù)對(duì)于整網(wǎng)負(fù)載的影響程度的排序。

步驟3 按照影響程度從大到小依次確定任務(wù)的路徑，任務(wù)的路徑為在所有轉(zhuǎn)跳數(shù)為tmin或tmin＋1的路徑中，所經(jīng)過的鏈路上的負(fù)載之和最小的路徑。

這種通信任務(wù)路徑選擇方法均衡地考慮了轉(zhuǎn)跳次數(shù)和鏈路的負(fù)載均衡，解決了兩者之間的矛盾；算法的復(fù)雜程度較低，可以較快地得到通信任務(wù)路徑，非常適合于在TTE網(wǎng)絡(luò)拓?fù)渲惺褂谩?/p>

2.3 優(yōu)化問題的求解

在約束和目標(biāo)函數(shù)較為復(fù)雜的情況下，任意拓?fù)浣Y(jié)構(gòu)下任務(wù)與資源映射的組合優(yōu)化問題很難采用解析方法，可以采用啟發(fā)式算法，在有限的計(jì)算時(shí)間內(nèi)尋找次優(yōu)解。選用了模擬退火算法［9］，利用它較強(qiáng)的局部搜索能力求解任務(wù)均衡分配方案。

具體步驟如下：

步驟1 獲取TTE網(wǎng)絡(luò)的基本信息。包括網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、處理與通信任務(wù)的相關(guān)參數(shù)以及網(wǎng)絡(luò)節(jié)點(diǎn)及鏈路的約束條件。

步驟2 依據(jù)由于TTE網(wǎng)絡(luò)通信本身所具有的時(shí)間確定性，對(duì)通信任務(wù)進(jìn)行優(yōu)化處理，將通信任務(wù)轉(zhuǎn)化為處理任務(wù)的參數(shù)，以達(dá)到兩者同時(shí)進(jìn)行分配的效果。

步驟3 設(shè)定控制參數(shù)，即調(diào)整模擬退火法的冷卻進(jìn)度表。包括控制參數(shù) “溫度系數(shù)”的初值t0及其衰減函數(shù)α，以及馬爾科夫長(zhǎng)度。

步驟4 使用模擬退火算法進(jìn)行求解，其運(yùn)算過程如圖3所示，包含內(nèi)、外兩層循環(huán)，內(nèi)循環(huán)模擬升溫過程，外循環(huán)模擬冷卻過程，升溫時(shí)在當(dāng)前解X的鄰域通過搜索能夠改進(jìn)目標(biāo)函數(shù)值的解，為了能夠擺脫局部極值，當(dāng)改進(jìn)量ΔG暫時(shí)沒有優(yōu)勢(shì)時(shí)，以概率exp（－ΔG（X）／T）接受新解X←X（b），冷卻時(shí)進(jìn)行終止條件的判斷。

圖3 模擬退火算法流程

3 案例研究與仿真分析

在擁有4臺(tái)節(jié)點(diǎn)的TTE網(wǎng)絡(luò)仿真環(huán)境下對(duì)16個(gè)處理任務(wù)和64個(gè)通信任務(wù)進(jìn)行分布式任務(wù)均衡分配。在本例中，暫不考慮處理任務(wù)的約束關(guān)系，各處理任務(wù)的負(fù)載見表1，TTE網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)淙鐖D4所示，各處理任務(wù)間的應(yīng)用層 “端到端”的有向流量，即通信任務(wù)見表2（其中0已省略）。

圖4 TTE網(wǎng)絡(luò)拓?fù)?/p>

表1 處理任務(wù)的負(fù)載

表2 處理任務(wù)間的有向流量

利用編程仿真的方法分別對(duì)本文提出的處理任務(wù)和通信任務(wù)統(tǒng)一地映射的分配方法進(jìn)行仿真。作為比較組，采用分步分配［10，11］的方法，即先進(jìn)行處理任務(wù)分配，然后在此基礎(chǔ)上進(jìn)行通信任務(wù)分配。對(duì)于這個(gè)例子，仍然采用式（1）的算法，只不過在分配處理任務(wù)時(shí)，不考慮通信任務(wù)間的負(fù)載均衡情況，式 （1）中的f（X）＝σ2v，而在分配通信任務(wù)時(shí)，則不考慮處理任務(wù)間的負(fù)載均衡情況，f（X）＝σ2E。相當(dāng)于分別用本算法的特例分兩步解決任務(wù)分配問題，從而得到表3及圖5中的數(shù)據(jù)。

表3 各節(jié)點(diǎn)的分配結(jié)果

圖5 各鏈路的分配結(jié)果

由上述數(shù)據(jù)可以算出，使用統(tǒng)一分配的算法得到的目標(biāo)函數(shù)值為9.9475，而使用分步分配的算法得到的目標(biāo)函數(shù)值為174.9875。這說明使用統(tǒng)一分配算法在時(shí)間觸發(fā)以太網(wǎng)任務(wù)分配上遠(yuǎn)遠(yuǎn)優(yōu)于通常所使用的分步式分配方法。

這主要是因?yàn)閭鹘y(tǒng)的分步式分配方法雖然在分配處理任務(wù)的過程中取得了很好的效果，但是在分配通信任務(wù)時(shí)，由于處理任務(wù)的影響而無法達(dá)到很好的效果。而統(tǒng)一分配算法則利用了TTE網(wǎng)絡(luò)通信所具有的時(shí)間確定性機(jī)制，將不同處理資源上的處理任務(wù)通過通信互連的關(guān)系聯(lián)系起來，在整體上取得優(yōu)化的效果。

4 結(jié)束語

本文以采用TTE網(wǎng)絡(luò)的分布式綜合化系統(tǒng)為研究背景。提出了一種將信息處理和通信任務(wù)統(tǒng)一處理的任務(wù)均衡分配方法。案例研究表明，該方法充分發(fā)揮了TTE網(wǎng)絡(luò)通信本身所具有的時(shí)間確定性，將處理任務(wù)和通信任務(wù)統(tǒng)一地進(jìn)行分配，相較于傳統(tǒng)分配方法，提高了網(wǎng)絡(luò)的整體負(fù)載均衡程度，可以有效改善網(wǎng)絡(luò)的性能。

由于分布式任務(wù)均衡分配的復(fù)雜性，本文在處理任務(wù)間的依賴性關(guān)系及任務(wù)路徑分析等方面采取了簡(jiǎn)化的手段進(jìn)行處理，因此對(duì)此類問題如何進(jìn)行優(yōu)化分配還需要進(jìn)一步深入探討。

［1］Steiner W.TTEthernet specification ［S］.Austria：TTTech Computertechnik AG，2008.

［2］Jakovljevic M.Deterministic Ethernet：SAE AS6802 “Time－Triggered Ethernet” ［EB／OL］. ［2013－08－19］.SAE AS－2D2“Deterministic Ethernet and Unified Networking”Committee，http：／／www.sae.org／servlets／works／committeeHome.do？comtID＝TEAAS2D.

［3］SAE AS6003.TTP communication protocol［S］.

［4］SAE AS6802.Time－triggered Ethernet ［S］.

［5］McCabe Mary，Baggerman Clint，Verma Dinesh.Avionics architecture interface considerations between constellation vehicles［C］／／IEEE Digital Avionics Systems Conf，2009：25－29.

［6］Wolfig R，Jakovljevic M.Distributed IMA and DO－297：Architectural，communication and certification attributes ［C］／／27th Digital Avionics Systems Confe－rence，2008：26－30.

［7］RTCA DO－297.Integrated modular avionics （IMA）development guidance and certification considerations ［S］.

［8］Zhu Y，Liu X，Yu X.An optimal path algorithm of high security based on Dijkstra algorithm ［C］／／International Conference on Sensor Network Security Technology and Privacy Communication System.IEEE，2013：93－96.

［9］Matusiak M，de Koster R，Kroon L，et al.A fast simulated annealing method for batching precedence－constrained customer orders in a warehouse ［J］.European Journal of Operational Research，2013.

［10］LIU Yang，TONG Xiaonian.Research on network loading balance based on genetic simulated annealing algorithm ［J］.Computer ＆ Digital Engineering，2008，36 （9）：16－18 （in Chinese）.［劉陽，童小念.基于遺傳模擬退火算法的網(wǎng)絡(luò)負(fù)載均衡研究 ［J］.計(jì)算機(jī)與數(shù)字工程，2008，36 （9）：16－18.］

［11］HU Rong，YANG Chun.Energy－balanced multi－h(huán)op routing scheme based on simulated annealing algorithm ［J］.Computer Engineering，2010，36 （16）：71－73 （in Chinese）. ［胡榮，楊春.基于模擬退火算法的能耗均衡多跳路由方案 ［J］.計(jì)算機(jī)工程，2010，36 （16）：71－73.］