王 彤

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

0 引言

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

1 FlexRay通信模式

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

1.1 靜態(tài)段

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

1.2 動(dòng)態(tài)段

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

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

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

蟻群算法是一種通過模擬螞蟻覓食從而找到最優(yōu)路徑的方法[2]。傳統(tǒng)蟻群算法沒有考慮到帶寬、時(shí)延等約束條件，在解決本文的問題上具有一定局限性，而改進(jìn)后的蟻群算法將信息素的更新應(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é)點(diǎn)和網(wǎng)絡(luò)中鏈路的集合;delay(PT)表示網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路延遲；bandwidth(PT)表示帶寬限制；packet_loss(PT)表示網(wǎng)絡(luò)丟包限制。

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

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

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

2.3.1 算法描述

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

1) 路徑選擇

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

(4)

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

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

2) 局部更新

由于信息素的揮發(fā)，當(dāng)所有螞蟻在走完一步或者遍歷完n個(gè)節(jié)點(diǎn)，即在一個(gè)循環(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為信息素強(qiáng)度，反映算法的收斂速度，Lk表示第k只螞蟻在本循環(huán)中所有節(jié)點(diǎn)和邊的和。

3) 全局更新

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

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

(8)

(9)

2.3.2 算法步驟

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

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

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

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

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

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

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

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

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

2.4 網(wǎng)絡(luò)負(fù)載均衡蟻群算法—?jiǎng)討B(tài)調(diào)度算法

在一個(gè)特定的時(shí)間片內(nèi)，流經(jīng)某網(wǎng)關(guān)控制節(jié)點(diǎn)的流量不規(guī)律，網(wǎng)絡(luò)中資源相對短缺的位置通常會(huì)發(fā)生擁塞。不均衡的資源分布會(huì)增加或調(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ò)擁塞，不能達(dá)到網(wǎng)絡(luò)資源的優(yōu)化配置。

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

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

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

3 算法仿真與性能分析

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

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

圖1 網(wǎng)絡(luò)拓?fù)鋱D

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

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

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

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

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

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

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

4 結(jié)束語

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