湯 宇，李 峭，賈琪明

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

0 引 言

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

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

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

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

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

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

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

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

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

1.2 網(wǎng)絡(luò)的物理拓撲

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

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

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

圖2 抽象出的拓撲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

其中

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

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

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

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

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

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

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

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

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

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

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

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

具體步驟如下：

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

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

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

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

圖3 模擬退火算法流程

3 案例研究與仿真分析

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

圖4 TTE網(wǎng)絡(luò)拓撲

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

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

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

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

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

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

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

4 結(jié)束語

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

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

［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ò)負載均衡研究 ［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］.計算機工程，2010，36 （16）：71－73.］