基于二維裝箱問(wèn)題的TTE調(diào)度表生成算法

郭袁賈

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

0 引 言

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

1 問(wèn)題抽象建模

1.1 網(wǎng)絡(luò)模型

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

圖1 網(wǎng)絡(luò)模型拓?fù)浣Y(jié)構(gòu)

對(duì)網(wǎng)絡(luò)模型進(jìn)行如下定義：

集合V(Vertex)表示網(wǎng)絡(luò)拓?fù)渲兴械墓?jié)點(diǎn)，其中每個(gè)節(jié)點(diǎn)有一個(gè)唯一的標(biāo)識(shí)i，因此網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)可以表示為Vi。

集合S(Switch)表示網(wǎng)絡(luò)拓?fù)渲兴械慕粨Q機(jī)節(jié)點(diǎn)，其中每一個(gè)交換機(jī)有一個(gè)唯一的編號(hào)j，因此每個(gè)交換機(jī)可以表示為Sj，例如圖中V9和S9表示同一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。

集合E(endsystem)表示網(wǎng)絡(luò)拓?fù)渲兴械慕K端節(jié)點(diǎn)，其中每一個(gè)終端節(jié)點(diǎn)都有一個(gè)唯一的編號(hào)k，因此每個(gè)終端節(jié)點(diǎn)可以表示為Ek，例如圖中V18和E3表示同一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。

集合L(Link)表示網(wǎng)絡(luò)拓?fù)渲兴形锢磉B接鏈路，其中節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vj之間的鏈路可以表示為L(zhǎng)vivj，由于本文考慮全雙工通信鏈路，因此Lvivj和Lvjvi認(rèn)為是不同的鏈路。

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

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

1.2 裝箱問(wèn)題模型

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

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

圖2 裝箱問(wèn)題抽象過(guò)程

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

(1)

(2)

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

Ovivj.width=Tvivj.length

(3)

(4)

2 二維裝箱算法

2.1 通訊任務(wù)預(yù)處理階段

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

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

圖3 通訊任務(wù)預(yù)處理

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

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

2.2 裝箱算法階段

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

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

圖4 裝箱點(diǎn)

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

圖5 排序后物品裝箱

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

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

圖6 裝箱算法階段流程

2.3 調(diào)度表表項(xiàng)計(jì)算階段

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

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

圖7 調(diào)度表表項(xiàng)計(jì)算階段

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

2.4 動(dòng)態(tài)添加通訊任務(wù)

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

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

3 仿真實(shí)驗(yàn)及討論

3.1 仿真實(shí)驗(yàn)網(wǎng)絡(luò)設(shè)置

本文進(jìn)行實(shí)驗(yàn)時(shí)選用了文獻(xiàn)[11]中設(shè)計(jì)的較為復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖1所示。本文在裝有Matlab2016的Windows10上進(jìn)行仿真實(shí)驗(yàn)，處理器為Intel(R)Core(TM)i5-4210U CPU@ 1.70 GHz 2.40 GHz。

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

為了簡(jiǎn)化仿真實(shí)驗(yàn)，本文假設(shè)網(wǎng)絡(luò)拓?fù)渲兴墟溌返膫鬏斔俾识紴?00 Mbit/s，由于本次實(shí)驗(yàn)關(guān)注于時(shí)間資源的占用情況，因此忽略網(wǎng)絡(luò)鏈路中的傳輸時(shí)延、傳輸時(shí)延、交換機(jī)中的轉(zhuǎn)發(fā)時(shí)延，這些時(shí)延只會(huì)影響調(diào)度表的發(fā)送時(shí)間點(diǎn)和接收時(shí)間點(diǎn)而不會(huì)影響鏈路的時(shí)間資源占用情況。

3.2 隨機(jī)通訊任務(wù)設(shè)置

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

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

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

3.3 實(shí)驗(yàn)結(jié)果及討論

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

本仿真實(shí)驗(yàn)利用3.2中介紹的隨機(jī)通訊任務(wù)生成方法分別對(duì)網(wǎng)絡(luò)中同時(shí)存在50個(gè)通訊任務(wù)、100個(gè)通訊任務(wù)等情況進(jìn)行了仿真實(shí)驗(yàn)。其中每種情況重復(fù)了10次隨機(jī)實(shí)驗(yàn)以消除隨機(jī)誤差。實(shí)驗(yàn)結(jié)果見表1。

表1 鏈路時(shí)間資源占用率/%

將隨機(jī)實(shí)驗(yàn)的平均值繪制為折線如圖8所示。

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

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

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

4 結(jié)束語(yǔ)

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

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