基于二維裝箱問題的TTE調度表生成算法

郭袁賈

(中國航天科工集團第二研究院 七〇六所，北京 100854)

0 引 言

自時間觸發(fā)以太網(wǎng)(time-triggered Ethernet，TTE)[1-4]概念提出以來，關于調度表生成的研究就一直在持續(xù)，調度表生成問題被認為是NP困難問題[5]，目前沒有算法可以求解出這個問題的精確最優(yōu)解，因此大多數(shù)算法都致力于生成工程上可用的調度表。傳統(tǒng)的調度表生成算法是例如文獻[6]和文獻[7]中提出的利用SMT求解器進行求解的方法。這之后出現(xiàn)了一些利用啟發(fā)式算法對調度表進行求解的方法，例如文獻[8]中使用了粒子群模擬退火算法，文獻[9]中使用了模糊粒子群優(yōu)化算法，文獻[10]中使用了遺傳算法。這些啟發(fā)式算法提高了全局尋優(yōu)效率，但是當通信任務較多時會導致算法運算時間快速增加，為了解決這個問題，文獻[11]和文獻[12]中提出了二維裝箱算法和啟發(fā)式算法結合的方法?；旌隙S裝箱算法雖然降低了調度表生成的運算時間，但是仍然存在以下問題：①采用了固定的時隙來傳輸數(shù)據(jù)幀，雖然這樣可以簡化問題，但是實際工程應用中通信任務數(shù)據(jù)幀通常是不一致的；②無法滿足通訊任務動態(tài)添加，調度表動態(tài)更新的需求，這導致當前的算法無法滿足實際工程應用中復雜多變的實際需求。為了解決上述問題，基于二維裝箱問題提出了一種調度表生成算法。

1 問題抽象建模

1.1 網(wǎng)絡模型

本文參考了文獻[5]中的模型，主要關注全雙工鏈路下數(shù)據(jù)幀的傳輸，參考了文獻[11]中設計的較為復雜的樹形網(wǎng)絡拓撲結構，如圖1所示。圖中具有18個終端節(jié)點和14個交換機節(jié)點。其中粗實線表示節(jié)點之間物理鏈路連接，帶箭頭的細實線表示一段鏈路上數(shù)據(jù)幀的傳輸方向，虛線表示一個終端節(jié)點到另外一個終端節(jié)點的通訊任務經(jīng)過的鏈路路徑。

圖1 網(wǎng)絡模型拓撲結構

對網(wǎng)絡模型進行如下定義：

集合V(Vertex)表示網(wǎng)絡拓撲中所有的節(jié)點，其中每個節(jié)點有一個唯一的標識i，因此網(wǎng)絡拓撲中的節(jié)點可以表示為Vi。

集合S(Switch)表示網(wǎng)絡拓撲中所有的交換機節(jié)點，其中每一個交換機有一個唯一的編號j，因此每個交換機可以表示為Sj，例如圖中V9和S9表示同一個網(wǎng)絡節(jié)點。

集合E(endsystem)表示網(wǎng)絡拓撲中所有的終端節(jié)點，其中每一個終端節(jié)點都有一個唯一的編號k，因此每個終端節(jié)點可以表示為Ek，例如圖中V18和E3表示同一個網(wǎng)絡節(jié)點。

集合L(Link)表示網(wǎng)絡拓撲中所有物理連接鏈路，其中節(jié)點Vi和節(jié)點Vj之間的鏈路可以表示為Lvivj，由于本文考慮全雙工通信鏈路，因此Lvivj和Lvjvi認為是不同的鏈路。

集合VL(VirtualLink)表示網(wǎng)絡中由一個節(jié)點鏈接到另外一個節(jié)點的通信鏈路，可以表示為VLvivj，其中VLvivj由集合L中的元素組成，同時可以表示為集合V中元素序列的形式。例如圖1中由節(jié)點V18到V31的虛擬鏈路可以表示為VLv18v31=Lv18v8+Lv8v1+Lv1v0+Lv0v4+Lv4v11+Lv11v12+Lv12v31，同時可以表示為VLv18v31=V18V8V1V0V4V11V12V31。

集合T(Task)表示網(wǎng)絡中所有由終端節(jié)點發(fā)送到除自身以外節(jié)點的通訊任務定義為Tvivj={id，source，desti，period，length，VLvivj}，其中id表示通訊任務的標識符，scycle表示發(fā)送數(shù)據(jù)幀的節(jié)點，desti表示接收數(shù)據(jù)幀的節(jié)點，period表示通訊任務的周期，length表示任務數(shù)據(jù)幀長度，VLvivj表示通訊任務的虛擬鏈路路徑。例如圖1中由節(jié)點V31到節(jié)點V16存在一條周期為3 ms，數(shù)據(jù)幀長度為256字節(jié)的通訊任務，則可以表示為Tv31v16={1，31，16，3 ms，256 Byte，VLv31v16}，其中VLv31v16=Lv31v12+Lv12v11+Lv11v4+Lv4v0+Lv0v1+Lv1v7+Lv7v6+Lv6v16。

1.2 裝箱問題模型

假設從時間軸上看某一條物理鏈路上數(shù)據(jù)幀的傳輸情況，假設有兩個通訊任務在物理鏈路上傳輸，一個通訊任務每次傳輸?shù)臄?shù)據(jù)幀很短但是周期較小，另外一個通訊任務周期長但是每次都要傳輸很長的數(shù)據(jù)幀。如圖2(a)所示，任務1在時間軸上經(jīng)常開始占用鏈路傳輸，但是每次只占用一小段時間，任務2每次發(fā)送需要占用很長時間，但是從時間軸上看，每隔很長時間才開始占用一次。

現(xiàn)在根據(jù)基本周期對時間軸進行折疊，如圖2(b)所示，進一步把折疊的時間軸看作一個“箱子”如圖2(c)所示，當鏈路中需要傳輸不同周期的通訊任務時，可以定義基本周期為所有周期的最大公約數(shù)，這樣可以保證每個通訊任務在基本周期內最多傳輸一次，集群周期可以定義為所有周期的最小公倍數(shù)，這樣可以保證每個通訊任務在集群周期中都至少傳輸一次并且傳輸次數(shù)在每個集群周期中相同。

圖2 裝箱問題抽象過程

箱子的寬度和鏈路的數(shù)據(jù)傳輸速率有關，這里假設網(wǎng)絡中所有的鏈路具有相同的數(shù)據(jù)傳輸速率，都為Bwidth。根據(jù)基本周期，集群周期和鏈路數(shù)據(jù)傳輸速率可以計算出“箱子”的高度和寬度如式(1)、式(2)所示，其中GCD(greatest common divisor)表示最大公約數(shù)，LCM(least common multiple)表示最小公倍數(shù)

(1)

(2)

最后，每個通訊任務可以看作一個有寬度有高度的“二維物品”，可以看出周期越小的通訊任務高度越高，而數(shù)據(jù)幀長度越長的通訊任務寬度越寬。因此把每一個通訊任務Tvivj抽象為一個“二維物品”O(jiān)vivj，將所有二維物品的集合表示為O(object)。并且可以計算每一個物品的寬度和高度，如式(3)和式(4)所示

Ovivj.width=Tvivj.length

(3)

(4)

2 二維裝箱算法

2.1 通訊任務預處理階段

改進前的算法利用交換機節(jié)點手動劃分了“同步傳輸域”，之后定義不同“同步傳輸域”的通訊任務可以進行整合同時傳輸。這樣的定義雖然可以簡化問題，但是在實際網(wǎng)絡環(huán)境中跨越多個“同步傳輸域”的通訊任務往往也滿足同步傳輸?shù)臈l件，因此會造成一定程度的時間資源的浪費，本文在進行裝箱算法之前特別設計了預處理階段，根據(jù)虛擬鏈路對通訊任務進行整合，并且只有整合后可以提高時間資源利用率的通訊任務才進行整合，這樣進一步提高了時間資源利用率也避免了手動劃分“同步傳輸域”的步驟。

以太網(wǎng)使用的物理鏈路支持全雙工通信，因此接收和發(fā)送可以同時進行傳輸，并且虛擬鏈路不重合的通訊任務也可以同步傳輸。之前把通訊任務Tvivj抽象為Ovivj，這意味著在實際裝箱的過程中，有的物品可以和其它的物品重疊，如圖3(a)所示。

圖3 通訊任務預處理

假設現(xiàn)有兩個通訊任務Tvivj和Tvmvn，它們的虛擬鏈路路徑可以表示為VLvivj=Lvivk+…+Lvpvj，VLvmvn=Lvmvx+…+Lvyvn。當對于Tvivj中所有L都不等于Tvmvn中的L，則認為Tvivj和Tvmvn可以同步傳輸，這也表示Ovivj和Ovmvn可以重疊。

當Ovivj和Ovmvn可以重疊時，可以把Ovivn和Ovmvn合并為一個物品。此時存在3種情況如圖3(b)、圖3(c)、圖3(d)所示。當一個物品可以被另外一個物品包含時如圖3(b)所示，可以認為大物品的寬度和高度就是新整合物品的寬度和高度。當兩個物品完全重合時如圖3(c)所示，可以把兩個物品認為是一個物品。圖3(d)是最常見的情況，當兩個物品只能部分重疊時，這時需要對節(jié)省的空間和浪費的空間進行計算，當節(jié)省空間大于浪費空間時可以進行物品整合，否則不對物品進行整合。整合后的物品依然可以和其它物品繼續(xù)整合，不過此時要求整合物品中的原始物品通訊鏈路兩兩不重合。

2.2 裝箱算法階段

經(jīng)過通訊任務預處理階段，所有物品認為只能互相不重疊地進行裝箱。

為了規(guī)范裝箱的過程并且簡化裝箱算法的實現(xiàn)，本文定義了集合P表示目前箱子中的“可用裝箱點”，如圖4(a)所示，當箱子為空時，只存在一個裝箱點P0(0,0)，當裝入一個物品時只能選擇現(xiàn)有的裝箱點進行放置，因此放入第一個物品會消耗“可用裝箱點”P0(0,0)，同時會產(chǎn)生兩個新的裝箱點如圖4(b)所示P1(Ovivj.width,0)和P2(0,Ovivj.height)。同理可知，當放入第2個物品時只能選擇現(xiàn)有的裝箱點P1或者P2，如圖4(c)和圖4(d)所示，此時會消耗一個“可用裝箱點”，同時根據(jù)放入物品的寬度和高度可以計算出新增加的“可用裝箱點”。

圖4 裝箱點

為了簡化“可用裝箱點”的生成位置，可以把物品按照高度和寬度進行排序，此時后放入的物品高度和寬度必然小于等于之前放入的物品。如圖5(a)和圖5(b)所示，此時就自然避免了圖4(c)和圖4(d)中出現(xiàn)的情況，這樣可以保證每放入一個物品都只會消耗一個“可用裝箱點”同時會產(chǎn)生至多兩個新的“可用裝箱點”，當后放入的物品寬度或者高度與前一個物品相同時只會消耗一個“可用裝箱點”同時產(chǎn)生一個新“可用裝箱點”，如圖5(c)和圖5(d)所示。

圖5 排序后物品裝箱

在算法的實現(xiàn)過程中，使用一個數(shù)組型數(shù)據(jù)結構就可以方便的存儲“可用裝箱點”信息，只需要改變數(shù)組中“可用裝箱點”的選取策略就可以改變裝箱算法的裝箱策略。此外，保存運行裝箱算法過程中產(chǎn)生的“可用裝箱點”有利于新通訊任務的動態(tài)添加，如果在之前的“可用裝箱點”記錄中可以找到合適的裝箱位置，則新通訊任務的添加不需要重新運行裝箱算法也不需要修改已有的調度表，只需要對新通訊任務對應的調度表表項進行添加即可。同時也可以簡化調度表分發(fā)的過程，此時由于其它調度表項都不變，因此可以只發(fā)送新通訊任務的調度表表項到對應的交換機節(jié)點即可。

綜上所述，裝箱算法流程如圖6所示。

圖6 裝箱算法階段流程

2.3 調度表表項計算階段

改進前的算法沒有對最后如何生成實際可用的調度表進行詳細論述，裝箱算法對鏈路的時間資源進行了抽象和分配，可以保證數(shù)據(jù)幀沒有沖突的傳輸，但是在實際網(wǎng)絡環(huán)境中，鏈路存在傳輸時延和傳播時延，交換機存在轉發(fā)時延，這些因素在實際使用中必須要考慮進去，并經(jīng)過計算才可以得到實際的數(shù)據(jù)幀發(fā)送時間點和接收時間點。

圖7(a)是整合后的物品的裝箱結果示意圖，整合后的物品只能不重疊地進行裝箱。在通訊任務預處理階段將可以同步傳輸?shù)娜蝿照蠟橐粋€物品，整合的物品在計算調度表時需要恢復成原始物品，圖7(b)是整合物品恢復成原始物品后的裝箱結果示意圖，例如圖7(a)中的整合物品C在圖7(b)中被還原為原始物品③和⑦。圖7(c)是物品還原到每個基本周期傳輸?shù)氖疽鈭D，這個過程與時間軸折疊抽象為箱子的過程正好相反，“箱子”是由多個基本周期組合而成的，此時需要將通訊任務根據(jù)裝箱結果分散到基本周期中。圖7(d)是數(shù)據(jù)幀在鏈路上傳輸，這里是忽略了傳輸時延和轉發(fā)實驗的傳輸，當考慮時延影響時，數(shù)據(jù)幀在鏈路上的傳輸如圖7(e)所示，例如數(shù)據(jù)幀從鏈路1傳輸?shù)芥溌?有時延并且采用存儲轉發(fā)策略，因此鏈路2開始發(fā)送數(shù)據(jù)幀的時間會比鏈路1延后，之后通過的鏈路同理。

圖7 調度表表項計算階段

綜上所述可以對裝箱算法的結果進行解析和計算然后得到數(shù)據(jù)幀在每條鏈路上的發(fā)送時間點和接收時間點，之后根據(jù)全局時鐘精度加上發(fā)送窗口和接收窗口就可以得到實際應用中可用的時間調度表表項。

2.4 動態(tài)添加通訊任務

當需要在已經(jīng)計算好的時間調度表中加入新的通訊任務時，如果之前使用的是例如文獻[8]或者文獻[9]中的啟發(fā)式算法，這時就需要把新的通訊任務加入通訊約束之后重新運行算法才可以得到新的調度表，這樣無法滿足實際應用中復雜多變的實際需求。本文設計的三階段裝箱算法可以在一定程度上滿足動態(tài)添加通訊任務然后生成對應的調度表項。

在第二階段裝箱算法中保存了整合后的物品信息以及當前的“可用裝箱點”信息，因此當有新的通訊任務請求計算調度表時，可以直接與當前整合后的物品進行整合性判斷，如果可以與當前的某個物品整合，那么直接根據(jù)當前整合物品的裝箱結果就可以計算得到該通訊任務對應的調度表。如果該任務與當前所有物品都無法進行整合就讀取“可用裝箱點”信息，如果有可以容納該通訊任務的裝箱點，那么根據(jù)裝箱結果也可以計算得到該通訊任務的調度表信息。最后如果當前添加的通訊任務既無法與當前物品整合也無法找到“可用裝箱點”，此時才把該通訊任務加入通訊任務約束并重新運行裝箱算法，得到所有物品新的裝箱結果并重新計算所有物品的調度表。

3 仿真實驗及討論

3.1 仿真實驗網(wǎng)絡設置

本文進行實驗時選用了文獻[11]中設計的較為復雜的網(wǎng)絡拓撲結構，如圖1所示。本文在裝有Matlab2016的Windows10上進行仿真實驗，處理器為Intel(R)Core(TM)i5-4210U CPU@ 1.70 GHz 2.40 GHz。

本文關注支持全雙工通信的以太網(wǎng)鏈路，但是現(xiàn)有的裝箱算法關注于單工模式傳輸。為了與之前研究保持實驗條件一致，本實驗中也假設網(wǎng)絡中所有鏈路處于單工模式，即在物品整合過程中認為鏈路Lvivj和Lvjvi是同一條鏈路不能同步傳輸。

為了簡化仿真實驗，本文假設網(wǎng)絡拓撲中所有鏈路的傳輸速率都為100 Mbit/s，由于本次實驗關注于時間資源的占用情況，因此忽略網(wǎng)絡鏈路中的傳輸時延、傳輸時延、交換機中的轉發(fā)時延，這些時延只會影響調度表的發(fā)送時間點和接收時間點而不會影響鏈路的時間資源占用情況。

3.2 隨機通訊任務設置

本文設計的算法支持每個通訊任務具有不同的數(shù)據(jù)幀長度，但是之前的裝箱算法為了簡化模型認為每個通訊任務都在固定的時間間隙傳輸，因此本文實驗中也保持每個數(shù)據(jù)幀的長度相同，這里假設每個數(shù)據(jù)幀長度為64個字節(jié)。

本文設計了隨機通訊任務來檢驗算法的時間資源占用情況。這里只考慮終端節(jié)點之間的通訊，不考慮交換機節(jié)點主動向終端節(jié)點發(fā)送數(shù)據(jù)，也不考慮交換機之間的通訊。隨機選取集合E中的一個節(jié)點Ei，再隨機選取一個不同的節(jié)點Ej，因此Ei到Ej通訊任務可以定義為Tvivj={id，source，desti，period，length，VLvivj}。其中id為生成隨機任務時初始化的標識，一般從0開始遞增，source為集合E中隨機選取的一個節(jié)點，desti為集合E中與source不同的節(jié)點。period為{N1*1 ms,N2*2 ms,N3*3 ms,N4*5 ms,N5*7 ms,N6*9 ms,N7*10 ms}中隨機選取一個值，其中N1到N7為大于等于1小于等于10的整數(shù)。Length固定為64字節(jié)。VLvivj為根據(jù)圖1所示拓撲計算得到的虛擬鏈路路徑。

重復從集合E中選取兩個不同節(jié)點并計算虛擬鏈路的步驟，這樣可以得到多個網(wǎng)絡中的隨機通訊任務。

3.3 實驗結果及討論

仿真實驗使用的指標是文獻[9]中定義的時間資源占用率，由于通訊任務已經(jīng)抽象為了“二維物品”所以這里使用“箱子”的空間占用率代表時間資源占用率(Occupancy)，占用率計算公式如下

本仿真實驗利用3.2中介紹的隨機通訊任務生成方法分別對網(wǎng)絡中同時存在50個通訊任務、100個通訊任務等情況進行了仿真實驗。其中每種情況重復了10次隨機實驗以消除隨機誤差。實驗結果見表1。

表1 鏈路時間資源占用率/%

將隨機實驗的平均值繪制為折線如圖8所示。

由折線圖可知當網(wǎng)絡中同時傳輸?shù)耐ㄓ嵢蝿諗?shù)量增加時，網(wǎng)絡的時間資源占用率也在增加，這和實際網(wǎng)絡中數(shù)據(jù)幀的傳輸現(xiàn)象相符的。由于實驗中通訊任務的周期是隨機數(shù)，數(shù)據(jù)幀的發(fā)送節(jié)點和接收節(jié)點都是隨機選取的，因此網(wǎng)絡中雖然同時存在的通訊任務數(shù)量相同但是時間資源占用率卻不同，例如網(wǎng)絡中只存在10個通訊任務時，第2次實驗和第8次實驗時間資源占用率差別較大，這是因為第8次通訊任務隨機生成的周期都較小，并且為了和改進前算法的實驗條件保持一致，本實驗中固定所有通訊任務數(shù)據(jù)幀長都為64字節(jié)，這意味著小周期任務占用時間資源多，因此導致總時間資源占用率變大。

從圖8可以看出，當網(wǎng)絡中通訊任務數(shù)量較少時，改進前后的算法占用率基本相同沒有占用過多的時間資源。當網(wǎng)絡中同時傳輸?shù)娜蝿赵蕉鄷r，改進后的算法對時間資源占用率相比改進前的算法越低。當網(wǎng)絡中同時存在550個通訊任務時，改進后的算法比改進前降低了占用率27.2%，當然，在實際的工程應用中一般不會給時間觸發(fā)數(shù)據(jù)預分配這么多的鏈路資源，因此實際使用中也可能不能降低那么多。根據(jù)隨機實驗可知，當給時間觸發(fā)數(shù)據(jù)分配30%鏈路資源時，改進后的算法能夠降低時間資源占用率11%左右，體現(xiàn)了改進算法的在降低時間資源占用率方面優(yōu)于之前的算法。

圖8 不同任務數(shù)量下鏈路資源占用率

4 結束語

本文基于二維裝箱問題對時間觸發(fā)以太網(wǎng)調度表生成問題進行了抽象，把網(wǎng)絡中需要分配時間資源的通訊任務抽象為具有高度和寬度的“二維物品”，并根據(jù)網(wǎng)絡傳輸?shù)奶匦詫Α岸S物品”進行了預處理，之后提出了便于快速實現(xiàn)的裝箱規(guī)則，最后根據(jù)網(wǎng)絡中的時延計算得到實際的調度表發(fā)送時間點和接收時間點。本文設計的算法對通訊任務重新進行了抽象定義，使得通訊任務可以使用不同的數(shù)據(jù)幀長度，彌補了之前算法使用固定時隙傳輸?shù)娜秉c。此外本文設計的三階段裝箱算法可以支持在已經(jīng)生成的調度表中動態(tài)添加通訊任務，彌補了之前靜態(tài)調度表生成算法的不足，提高了時間觸發(fā)以太網(wǎng)在實際應用中的靈活性。

仿真實驗結果表明，本文提出的算法在網(wǎng)絡中同時存在較多通訊任務時可以有效降低鏈路的時間資源占用率。