一種FlexRay網(wǎng)絡(luò)信息流調(diào)度算法研究

王 彤

(航空工業(yè)西安航空計算技術(shù)研究所，陜西西安710065)

0 引言

FlexRay作為一種靈活的車載網(wǎng)絡(luò)系統(tǒng)，具有高速、可靠、安全等特點[1]。在實時性的安全網(wǎng)絡(luò)中，由于節(jié)點間的信息交換途徑的改變會對網(wǎng)絡(luò)通信效率和網(wǎng)絡(luò)性能產(chǎn)生重要影響，因此車載網(wǎng)絡(luò)的信息流調(diào)度算法是改善網(wǎng)絡(luò)性能的關(guān)鍵，一個好的調(diào)度算法不僅能夠保證網(wǎng)絡(luò)通信的有效性，而且可以合理的分配網(wǎng)絡(luò)資源，更有效的控制由系統(tǒng)引起的時間延遲。基于蟻群算法的資源調(diào)度策略可以縮短整個任務(wù)的完成時間，維持網(wǎng)絡(luò)負載平衡，從而提高網(wǎng)絡(luò)資源的利用率和整體性能，具有可行性。

1 FlexRay通信模式

FlexRay的通信是在周期循環(huán)中進行的。一個通信循環(huán)始終包括靜態(tài)段和網(wǎng)絡(luò)閑置時間，還可能包括動態(tài)段、符號窗口。本文主要研究靜態(tài)段和動態(tài)段。靜態(tài)段和動態(tài)段由時隙構(gòu)成，通過時隙傳輸幀信息，時隙經(jīng)固定的周期而重復。

1.1 靜態(tài)段

FlexRay的靜態(tài)部分是基于TDMA機制，用于確定的周期性數(shù)據(jù)通信。FlexRay將靜態(tài)段分成若干個大小相等的時隙，每個節(jié)點都分配了一定的傳輸時隙，且根據(jù)對帶寬要求分配了所需時隙的大小。

1.2 動態(tài)段

動態(tài)段用于觸發(fā)的實時性非周期性消息的傳輸，其可用帶寬可被動態(tài)分配。如果沒有節(jié)點需要傳輸消息，則節(jié)點等待的時長為一個最小時隙長度；當某個節(jié)點時隙計數(shù)器讀數(shù)增加時，節(jié)點就會檢查對應(yīng)時隙里是否有準備好的消息需要發(fā)送。若有則發(fā)送節(jié)點會將此消息發(fā)送出去，直到這一消息被完全接收之后，動態(tài)段內(nèi)的時隙計數(shù)器的值會加1，這個過程循環(huán)往復，直到結(jié)束。

2 基于蟻群算法的調(diào)度算法

2.1 傳統(tǒng)蟻群算法局限性

蟻群算法是一種通過模擬螞蟻覓食從而找到最優(yōu)路徑的方法[2]。傳統(tǒng)蟻群算法沒有考慮到帶寬、時延等約束條件，在解決本文的問題上具有一定局限性，而改進后的蟻群算法將信息素的更新應(yīng)用到網(wǎng)絡(luò)路由中，使用每輪迭代更新的信息素的濃度增量來反映服務(wù)的質(zhì)量，解決了傳統(tǒng)的蟻群算法在該問題上的不足。

2.2 基于網(wǎng)絡(luò)路由的蟻群算法

網(wǎng)絡(luò)路由優(yōu)化問題[3,4]，即找到一條路徑，滿足丟包率約束和帶寬約束[5,6]。

其中，網(wǎng)絡(luò)延遲、帶寬限制和丟包率約束表示如下：

(1)

bandwidth(PT)=min(bandwidth(e,n∈PT)).

(2)

(3)

上述公式中，PT表示具有處理和轉(zhuǎn)發(fā)功能的網(wǎng)絡(luò)節(jié)點和網(wǎng)絡(luò)中鏈路的集合;delay(PT)表示網(wǎng)絡(luò)節(jié)點和鏈路延遲；bandwidth(PT)表示帶寬限制；packet_loss(PT)表示網(wǎng)絡(luò)丟包限制。

基本算法：首先，在基本蟻群算法的基礎(chǔ)上，根據(jù)上述約束刪除掉不滿足條件的點和邊。其次，在網(wǎng)絡(luò)中找出經(jīng)過所有節(jié)點并滿足約束條件的最優(yōu)路徑，達到保留帶寬和時延最小的水平。最后，根據(jù)螞蟻周游后得到的最優(yōu)路徑集合中的鏈路增加信息素，對其他路徑上的鏈路減少信息素，然后進行下一次迭代，直到迭代次數(shù)的最大值。

2.3 靜態(tài)調(diào)度算法

在這里采取了蟻群優(yōu)化中的一種元啟發(fā)式算法——頻率廣義分配問題進行網(wǎng)絡(luò)資源的分配和調(diào)度。

2.3.1 算法描述

假定整個FlexRay通信系統(tǒng)中共有n個通信節(jié)點(其中，源節(jié)點和目的節(jié)點已經(jīng)確定，并且對于通信網(wǎng)絡(luò)中的每一個節(jié)點都有可分配的時隙)，將FlexRay的一個通信周期分成M個大小相同的時隙。把每個節(jié)點作為一個頂點，當兩個節(jié)點有數(shù)據(jù)交換時，其間存在一條邊，反之則沒有邊。節(jié)點在通信過程中都會被分配一個時隙，被分配了時隙的鏈路才能夠?qū)崿F(xiàn)兩端節(jié)點的通信。設(shè)系統(tǒng)中的螞蟻數(shù)目為m，每個螞蟻代表一個資源調(diào)度方案，以此為網(wǎng)絡(luò)中的每個節(jié)點選擇一個時隙分配。靜態(tài)消息的調(diào)度算法就是尋找到第一個可以用于消息傳輸?shù)臅r隙，并能最大化靜態(tài)段的通信帶寬的利用率。

1) 路徑選擇

概率選擇方式使用近似非確定性樹搜索的概率計算方法：

(4)

其中,τij表示時隙分配給節(jié)點i的信息素量;ηij表示從時隙配給節(jié)點i的啟發(fā)信息；ζ是一個參數(shù)，用來規(guī)定信息素與吸引力之間的相對重要性;allowedk表示螞蟻k給節(jié)點i滿足約束條件的可分配的時隙集合。

當螞蟻k遍歷到節(jié)點i時，從可分配的時隙集合中選取一個時隙分配給節(jié)點i，并修改禁忌表，更新可分配時隙集合，然后依次遍歷下一個節(jié)點，當螞蟻k遍歷完所有節(jié)點后，可形成一個時隙的分配方案，從而能獲得本次遍歷的最短時延的節(jié)點序列。當所有的螞蟻都完成節(jié)點搜索任務(wù)后，即經(jīng)歷一次迭代過程，形成n個時隙分配方案，組成本次迭代可行方案，根據(jù)最小時延原則，從本次迭代產(chǎn)生的最優(yōu)解添加到最小時延集合中，作為當前最優(yōu)解，并更新集合中的最小時延。當達到最大迭代次數(shù)時，選取集合中的最小時延，即為最終解。

2) 局部更新

由于信息素的揮發(fā)，當所有螞蟻在走完一步或者遍歷完n個節(jié)點，即在一個循環(huán)的結(jié)束，要更新殘留信息素。根據(jù)公式：

τi,j(k+1)=(1-ρ)*τij(k)+Δτi,j.

(5)

(6)

其中ρ為信息揮發(fā)系數(shù);Δτi,j(k)為第k只螞蟻在本次循環(huán)中灑在(i，j)上的信息素增量。

(7)

Q為信息素強度，反映算法的收斂速度，Lk表示第k只螞蟻在本循環(huán)中所有節(jié)點和邊的和。

3) 全局更新

針對當前全局最優(yōu)解所屬的邊按下式進行更新：

τi,j(t+n)=ρ*τ(t)+(1-ρ)*Δτ(t).

(8)

(9)

2.3.2 算法步驟

1) 初始化網(wǎng)絡(luò)節(jié)點ECU_i(i=1，2，……)構(gòu)建圖，生成網(wǎng)絡(luò)模型節(jié)點信息。根據(jù)鏈路的信息，求出網(wǎng)絡(luò)拓撲結(jié)構(gòu)的鄰接矩陣；

2) 初始化信息素濃度：初始化路徑(i，j)位置上的信息素濃度與本次迭代在該位置上留下的總的信息素的量。為每條邊的信息素濃度設(shè)置一個初始值；

3) 根據(jù)丟包率、帶寬約束刪除不滿足條件的節(jié)點和鏈路，避免為丟包率過大或者浪費帶寬的鏈路分配時隙，把網(wǎng)絡(luò)過濾成一個新的網(wǎng)絡(luò)；

4) 將m只螞蟻隨機放到n個節(jié)點上，即選擇了第一個可被利用的時隙，將循環(huán)次數(shù)置為0，初始化禁忌表；

5)m只螞蟻按概率函數(shù)公式(8)選擇下一個可用于消息傳輸?shù)臅r隙，完成各自的周游；

6) 當螞蟻k遍歷到節(jié)點ECU_i時，從可分配時隙集合中選取一個時隙分配給ECU_i，修改禁忌表指針，將被分配到時隙的鏈路(i，j)添加到螞蟻的禁忌表之中；

7) 當遍歷完所有節(jié)點，跳轉(zhuǎn)執(zhí)行第8)步；

8) 根據(jù)公式(7)更新信息素；

9) 當循環(huán)次數(shù)到達最大值時，循環(huán)結(jié)束，輸出結(jié)果。

2.4 網(wǎng)絡(luò)負載均衡蟻群算法—動態(tài)調(diào)度算法

在一個特定的時間片內(nèi)，流經(jīng)某網(wǎng)關(guān)控制節(jié)點的流量不規(guī)律，網(wǎng)絡(luò)中資源相對短缺的位置通常會發(fā)生擁塞。不均衡的資源分布會增加或調(diào)換網(wǎng)絡(luò)資源。如果使用2.3節(jié)所提到的靜態(tài)調(diào)度算法，系統(tǒng)易陷入局部最優(yōu)，出現(xiàn)早熟停滯現(xiàn)象，無法應(yīng)對突發(fā)的業(yè)務(wù)量；且易形成網(wǎng)絡(luò)擁塞，不能達到網(wǎng)絡(luò)資源的優(yōu)化配置。

對于網(wǎng)絡(luò)資源中的負載均衡問題，可以使用調(diào)度和負載均衡策略，將負載動態(tài)地分配給多個鏈路。在這里對靜態(tài)調(diào)度算法進行改進，提出一種動態(tài)調(diào)度算法，使用螞蟻數(shù)量代表網(wǎng)絡(luò)資源的流量，通過螞蟻間信息素的相互作用將網(wǎng)絡(luò)流量分給多條可用路徑。以少花費為目標，以當前路徑上的信息素濃度為指標選擇鏈路，避開信息素濃度過高的鏈路，使網(wǎng)絡(luò)達到最大通過量，盡可能減少時延，把高負載鏈路上的流量轉(zhuǎn)移到其他較低負載的鏈路上，減少鏈路上數(shù)據(jù)包的丟失。

假設(shè)每只螞蟻代表在鏈路上傳輸?shù)臄?shù)據(jù)包，每選擇一條鏈路，都會占用一定大小的帶寬。螞蟻在路徑構(gòu)建的每一步，都根據(jù)公式(4)進行時隙分配。每只螞蟻有一個訪問的禁忌表，按照訪問的順序記錄已訪問過的節(jié)點。當所有的螞蟻都構(gòu)建完路徑后，每條邊的信息素根據(jù)公式(5)進行更新。

由公式(7)，螞蟻構(gòu)建的路徑達到最優(yōu)時，該路徑的每條邊上就會獲得更多的信息素。通常而言，當更多螞蟻選擇一條邊時，該邊的時延會越短，那么這條邊將會獲得更多的信息素，在后面的迭代中將會被更多的螞蟻選擇。

3 算法仿真與性能分析

3.1 仿真實驗說明以及參數(shù)設(shè)置

在仿真開始之前，需要對參數(shù)進行初步的設(shè)置。網(wǎng)絡(luò)拓撲圖如圖1。算法設(shè)置參數(shù)m=150，ρ=0.9、ζ=0.2、Q=100。螞蟻從原點1、2、3到目標節(jié)點6 在節(jié)點4處匯合，有四條路徑可選：4→5→6，4→6，4→7→6，4→8→9→6，當螞蟻都選擇4→6時，該條路徑可能會成為網(wǎng)絡(luò)的瓶頸，影響網(wǎng)絡(luò)的性能。

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

用蟻群代表數(shù)據(jù)包所占用的帶寬量，假設(shè)每只螞蟻代表一個基本的網(wǎng)絡(luò)流量單元Bw=0.2Mb，鏈路4→6的最大帶寬容量為7Mb/s，即最多可以通過35只螞蟻，當鏈路上的螞蟻占用帶寬量較多時，不能容納新選擇這條鏈路的螞蟻，就會產(chǎn)生丟棄，即在網(wǎng)絡(luò)中發(fā)送丟包的情況。

螞蟻的數(shù)目是150，代表有30Mb的數(shù)據(jù)包要從源節(jié)點4到達目的節(jié)點6，如果考慮花費，則都選擇最短路徑，這樣會造成網(wǎng)絡(luò)的擁塞，丟包率增加。因此，設(shè)定一個帶寬的限制值，當最優(yōu)路徑到達一定的帶寬利用率時，不再運行螞蟻選擇該路徑，而是將其分配到其他更好的路徑上，提高網(wǎng)絡(luò)資源的利用率。

3.2 網(wǎng)絡(luò)負載均衡性能分析

最短路由4→6上螞蟻的數(shù)量變化圖如圖2。基本的蟻群算法在較短的時間內(nèi)找到了到達終點的最短路徑，同時釋放信息素，導致轉(zhuǎn)移概率的增加，影響到以后的螞蟻，使螞蟻都選擇該最短路徑，雖然在路徑的消耗上進行了優(yōu)化，但是會造成大量數(shù)據(jù)包在最短路徑的擁塞，引起數(shù)據(jù)包丟失。而網(wǎng)絡(luò)負載均衡的蟻群算法可以將最短路徑上的螞蟻控制在一個較低的水平(最大鏈路容量)，降低丟包率，減少網(wǎng)絡(luò)擁塞的發(fā)生，從而提高帶寬利用率。

圖2 最短路由4-6上螞蟻的數(shù)量變化

網(wǎng)絡(luò)負載均衡性能實驗結(jié)果如圖3所示。實驗結(jié)果表明，與基本的蟻群算法不同，網(wǎng)絡(luò)負載均衡的蟻群算法可以使螞蟻即網(wǎng)絡(luò)傳輸中的數(shù)據(jù)包更合理的分配到各個路徑上，而不是把數(shù)據(jù)包越來越多地引入最短路徑，從而達到網(wǎng)絡(luò)負載均衡的目的。改進后的蟻群算法將平均帶寬利用率從原來的31%提高到70%以上，網(wǎng)絡(luò)資源的利用率有了很大的提高；將丟包率維持在一個較低的水平，且在較小范圍內(nèi)變化，使網(wǎng)絡(luò)資源得到合理均衡的分配。從而有效地實現(xiàn)了網(wǎng)絡(luò)負載均衡，進一步提高了網(wǎng)絡(luò)的綜合性能。

圖3 網(wǎng)絡(luò)均衡性能試驗結(jié)果

4 結(jié)束語

本文從FlexRay總線出發(fā)，通過對FlexRay總線及其網(wǎng)絡(luò)性能的分析，運用保留帶寬的思想，研究了基于蟻群算法的靜態(tài)和動態(tài)調(diào)度算法并對其進行仿真，為改善FlexRay網(wǎng)絡(luò)的實時性及性能，提供了理論依據(jù)和參考價值。