《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 其他 > 業(yè)界動(dòng)態(tài) > 一種優(yōu)化的光纖通道仲裁環(huán)帶寬分配算法

一種優(yōu)化的光纖通道仲裁環(huán)帶寬分配算法

2008-07-08
作者:廖志華, 韓傳久

??? 摘 要: 依據(jù)實(shí)時(shí)系統(tǒng)中的周期任務(wù)模型,,研究了一種帶寬分配" title="帶寬分配">帶寬分配算法實(shí)現(xiàn)合理的帶寬分配,,以保證各節(jié)點(diǎn)的消息均能實(shí)時(shí)傳輸,并用粒子群算法" title="粒子群算法">粒子群算法對(duì)其進(jìn)行了實(shí)現(xiàn)。
??? 關(guān)鍵詞: 仲裁環(huán)? 實(shí)時(shí)傳輸? 公平算法? 帶寬分配? 粒子群算法

?

??? 光纖通道" title="光纖通道">光纖通道(Fibre Channel)協(xié)議是由ANSI(American Nation Standards Institute)的X3T11小組制定的一種高速串行通信協(xié)議標(biāo)準(zhǔn),。光纖通道仲裁環(huán)(FC-AL)提供了在共享式網(wǎng)絡(luò)中把多個(gè)節(jié)點(diǎn)連接在一起的方法,是光纖通道的一種重要的拓?fù)浣Y(jié)構(gòu),,并以其相對(duì)低廉的價(jià)格獲得了廣泛的應(yīng)用,。在實(shí)時(shí)通信領(lǐng)域中,要求網(wǎng)絡(luò)能夠提供在實(shí)時(shí)約束下的消息傳輸,。因此改善FC-AL的實(shí)時(shí)性" title="實(shí)時(shí)性">實(shí)時(shí)性能,,是目前研究的重點(diǎn)。
??? 粒子群優(yōu)化算法PSO(Particle Swarm Optimization)是一種新興的進(jìn)化計(jì)算技術(shù),,具有有效的搜索和優(yōu)化能力,。它的優(yōu)點(diǎn)在于流程簡(jiǎn)單易實(shí)現(xiàn),算法參數(shù)簡(jiǎn)潔,,無(wú)需復(fù)雜的調(diào)整,。因此在近幾年,粒子群算法得到迅速發(fā)展,,已廣泛應(yīng)用于函數(shù)優(yōu)化,、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用的領(lǐng)域,。
??? 在實(shí)時(shí)通信領(lǐng)域中,,要求網(wǎng)絡(luò)提供嚴(yán)格實(shí)時(shí)約束下的消息傳輸,強(qiáng)調(diào)對(duì)每個(gè)特定消息的延時(shí)控制,,網(wǎng)絡(luò)帶寬在各節(jié)點(diǎn)之間的分配直接影響到網(wǎng)絡(luò)的實(shí)時(shí)特性,,網(wǎng)絡(luò)的可達(dá)負(fù)載率UA(當(dāng)網(wǎng)絡(luò)負(fù)載率低于這個(gè)值時(shí),網(wǎng)絡(luò)中所有的消息的實(shí)時(shí)性都能得到滿足)是評(píng)判網(wǎng)絡(luò)實(shí)時(shí)性能的標(biāo)準(zhǔn)之一,。參考文獻(xiàn)[1-5]在這方面都做了有益的研究,,但由于各種原因,,在網(wǎng)絡(luò)的可達(dá)負(fù)載率方面效果都不太理想。本文對(duì)光纖通道仲裁環(huán)帶寬分配算法進(jìn)行了研究,,提出了保證環(huán)路上各節(jié)點(diǎn)消息實(shí)時(shí)傳輸?shù)膸挻_定方法,,并證明了即使在最差的情況下,保證消息集嚴(yán)格實(shí)時(shí)的網(wǎng)絡(luò)可達(dá)負(fù)載率幾乎可以達(dá)到100%,。在此基礎(chǔ)上,,利用優(yōu)化設(shè)計(jì)的思想將問(wèn)題轉(zhuǎn)換為多約束條件的函數(shù)優(yōu)化問(wèn)題,并用粒子群算法對(duì)其進(jìn)行優(yōu)化計(jì)算,,使之成為提高網(wǎng)絡(luò)實(shí)時(shí)性能的新思路,。
1 FC-AL的網(wǎng)絡(luò)模型[6-7]
??? 光纖通道的環(huán)路仲裁協(xié)議與令牌環(huán)訪問(wèn)協(xié)議一樣,屬于公共信道多址接入?yún)f(xié)議,,環(huán)路上的各節(jié)點(diǎn)共享環(huán)路帶寬,。當(dāng)前環(huán)路上有消息需發(fā)送的所有節(jié)點(diǎn)組成一個(gè)訪問(wèn)窗,窗內(nèi)優(yōu)先級(jí)最高的節(jié)點(diǎn)最先贏得仲裁,,贏得仲裁的節(jié)點(diǎn)向環(huán)路發(fā)送一個(gè)數(shù)據(jù)包,,如果此節(jié)點(diǎn)還有消息需要發(fā)送,即使它擁有較高的優(yōu)先權(quán),,也必須等到“訪問(wèn)窗”中的其他節(jié)點(diǎn)都有機(jī)會(huì)發(fā)送一次后才能申請(qǐng)下一次環(huán)路仲裁,。對(duì)網(wǎng)絡(luò)中的實(shí)時(shí)消息流來(lái)說(shuō),某節(jié)點(diǎn)當(dāng)前到達(dá)的消息,,必須在下一個(gè)消息到來(lái)的時(shí)間間隔之內(nèi)發(fā)送完畢,否則將不能實(shí)時(shí)傳輸,。由于光纖通道幀格式中數(shù)據(jù)域較大(2KB),,在“公平算法”下,如果各節(jié)點(diǎn)都以最大" title="最大">最大數(shù)據(jù)發(fā)送,,則當(dāng)前“訪問(wèn)窗”中其他節(jié)點(diǎn)消息的總發(fā)送時(shí)間,,可能會(huì)造成該節(jié)點(diǎn)消息不能實(shí)時(shí)傳輸。根據(jù)參考文獻(xiàn)[4]的思想,,可以對(duì)各節(jié)點(diǎn)在贏得仲裁后發(fā)送的數(shù)據(jù)包大小(packet size)加以限制,,即對(duì)其在一個(gè)“訪問(wèn)窗”中的消息發(fā)送長(zhǎng)度加以限制,從而防止節(jié)點(diǎn)占有環(huán)路使用權(quán)的時(shí)間過(guò)長(zhǎng),,以至影響其他消息的實(shí)時(shí)傳輸,。
1.1 消息模型
??? 消息模型采用實(shí)時(shí)通信中的周期任務(wù)模型,假設(shè)網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn),,每個(gè)節(jié)點(diǎn)各有一個(gè)實(shí)時(shí)消息流需要在網(wǎng)絡(luò)中傳輸,,因而有n個(gè)消息流S1,S2,…,Sn,,由它們組成一個(gè)消息集合M,,即:
??? M={S1,S2,…,Sn}???????????????????????????????????????? ?(1)
??? 每個(gè)消息流均可表示為一個(gè)二維數(shù)組,對(duì)于Si,,有:
??? Si=(Ci,Pi)????????????????????????????????????????????? ? (2)
??? 消息流負(fù)載率Ui定義為:
??? Ui=Ci/Pi????????????????????????????????????????????????????? ????? (3)
式中,Pi表示消息產(chǎn)生的周期,,對(duì)非周期性消息,表示消息產(chǎn)生的最小時(shí)間間隔,。Ci表示消息的長(zhǎng)度,,即該消息的傳輸時(shí)間,內(nèi)容包括網(wǎng)絡(luò)協(xié)議規(guī)定的分隔符,、幀頭信息,、信息域和校驗(yàn)碼等幀的全部信息。
??? 網(wǎng)絡(luò)總的負(fù)載率為:

???

1.2 帶寬計(jì)算方法及性能分析
1.2.1 實(shí)時(shí)限制條件
??? 若fi為節(jié)點(diǎn)i在一次“訪問(wèn)窗”內(nèi)分配的網(wǎng)絡(luò)帶寬,,則一個(gè)訪問(wèn)窗的最大帶寬(傳輸時(shí)間上限)為:

???

??? 對(duì)特定消息流,,如果所采用的帶寬分配方法既能滿足協(xié)議限制條件又能滿足時(shí)限限制條件,則在該帶寬分配方法下,,對(duì)特定消息流可實(shí)現(xiàn)實(shí)時(shí)傳輸,。
??? (1)協(xié)議限制條件
??? 在一個(gè)采用公平算法的訪問(wèn)窗口中,用于發(fā)送消息的總帶寬應(yīng)滿足:

???

式中,,Pmin=min(P1,P2,…Pn),δ表示建立一個(gè)訪問(wèn)窗需要的其他開(kāi)銷,。
??? (2)時(shí)限限制條件
??? 對(duì)于任意時(shí)間間隔t,用Xi(t)表示節(jié)點(diǎn)發(fā)送消息的最小時(shí)間量,,根據(jù)FC-AL的在最差情況下實(shí)時(shí)消息的調(diào)度原則[5],,有:

???

式中,θ=min(fi,t-[t/(Fmax+?啄)]×(Fmax+δ)), [·]取整符號(hào),。
??? 消息集合M中每個(gè)消息在其最大允許時(shí)間內(nèi),,應(yīng)有足夠發(fā)送該消息的時(shí)間,因此對(duì)于任意消息流Si,,應(yīng)有:
??? Xi(Pi)≥Ci ? i=1,2,…n??????????????????????????????????? (8)
1.2.2 帶寬分配方法
??? 通過(guò)以上分析,,可以采用如下方法確定各個(gè)節(jié)點(diǎn)在一次訪問(wèn)窗內(nèi)所分配的帶寬fi
??? mi×(Fmax+δ)+(Fmax+δ)≤Pi??????????????????????????????? (9)

式中,表示向上取整,,亦即節(jié)點(diǎn)在隨后的mi次贏得仲裁后,,可將一個(gè)消息流Ci全部發(fā)送完,其中每個(gè)訪問(wèn)窗內(nèi)發(fā)送的信息段為cij(j=1,2,…,mi),。需要指出的是,,盡管節(jié)點(diǎn)i在一個(gè)訪問(wèn)窗內(nèi)發(fā)送cij時(shí)分配的帶寬(“用時(shí)”)為fi,但由于在該訪問(wèn)窗內(nèi)需要等待其他節(jié)點(diǎn)發(fā)送信息(等待時(shí)間為Fmax-fi),,因此,,發(fā)送cij的實(shí)際最大“耗時(shí)”為Fmax。根據(jù)最差情況下實(shí)時(shí)消息的調(diào)度原則,,節(jié)點(diǎn)i沒(méi)能進(jìn)入第一個(gè)訪問(wèn)窗,,所以還必須等待一個(gè)訪問(wèn)窗的時(shí)間,,最大為Fmax+δ。
1.2.3 實(shí)時(shí)性能分析
??? 定理1 如果各節(jié)點(diǎn)以(9)式提供的方法分配帶寬,,則M中所有消息實(shí)時(shí)性均能得到保證,,即對(duì)所有消息都能滿足協(xié)議限制條件和時(shí)限限制條件。
??? 證明:
??? (1)因?yàn)閒i≤Ci,,則mi≥1,,又mi×(Fmax+δ)+(Fmax+δ)≤Pi2(Fmax+δ)≤mi×Fmax+Fmax≤Pi
??? 則(6)式也成立。

??? (2)因?yàn)閙i×(Fmax+δ)+(Fmax+δ)≤Pi,,其中,,即:

???

??? 即(8)式也成立。
??? 通過(guò)證明,,可知定理1成立,。
??? 定理1說(shuō)明了只要按(9)式分配帶寬,就能滿足消息實(shí)時(shí)傳輸?shù)膬蓚€(gè)限制條件,,而不需對(duì)網(wǎng)絡(luò)負(fù)載率加以限制,,因此,可以將網(wǎng)絡(luò)的可達(dá)負(fù)載率看成UA≈100%,。
2 粒子群算法
2.1 粒子群算法
??? 粒子群優(yōu)化算法PSO是Kennedy和Eberha于1995年提出的一種集群優(yōu)化算法,,同遺傳算法相似,是一種基于迭代的優(yōu)化工具,。PSO算法采用的是速度-位置搜索模型,,每個(gè)粒子代表一個(gè)候選解,解的優(yōu)劣程度由適應(yīng)度函數(shù)來(lái)決定,。xi=(xi1,xi2,…xin)表示第i個(gè)粒子在n維空間的位置,。速度vi=(vi1,vi2,…vin)表示第i個(gè)粒子在搜索空間單位迭代的位移。PSO算法隨機(jī)初始化一群粒子,,然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中,,粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己,。一個(gè)是粒子本身所找到的最優(yōu)解,即個(gè)體極值pbest,;另一個(gè)是整個(gè)種群目前找到的最優(yōu)解,,即全局極值gbest。粒子在找到上述兩個(gè)最優(yōu)值后,,根據(jù)以下公式更新其速度和位置:

???

式中,,rand()是(0,1)區(qū)間上服從均勻分布的隨機(jī)數(shù);c1,、c2稱為學(xué)習(xí)因子,,通常c1=c2=2,;w是慣性權(quán)重,取值在0.4~0.9之間,,一般的做法是將w初始取為:

???

式中,,iter為當(dāng)前的迭代次數(shù),itermax為最大的迭代次數(shù),。為了防止粒子遠(yuǎn)離搜索空間,,粒子的每一維速度都被限制在[-vmax,vmax]之間。假設(shè)搜索空間為[-xmax,xmax],,通常:

???

2.2 利用粒子群算法求解帶寬
??? 這里利用粒子群算法求解FC-AL的帶寬分配問(wèn)題,。因?yàn)樵诎l(fā)送的每幀數(shù)據(jù)中都包含有固定的控制信息,幀長(zhǎng)越短,,其控制比特占的比例越大,,而使得帶寬利用率下降,在這種帶寬分配方法中,,應(yīng)該在滿足消息的時(shí)限要求的同時(shí),,使各節(jié)點(diǎn)所獲得的帶寬盡可能地大。綜合節(jié)點(diǎn)優(yōu)先級(jí)和鏈路利用率兩方面因素,,可將適應(yīng)度函數(shù)設(shè)為:

???

式中,(α12,…αn)表示各個(gè)節(jié)點(diǎn)優(yōu)先級(jí)對(duì)應(yīng)權(quán)值,。
??? 根據(jù)上面對(duì)消息實(shí)時(shí)傳輸所需條件的討論,將每個(gè)fi看成一個(gè)“粒子”,,通過(guò)設(shè)立目標(biāo)函數(shù)和約束條件,,可將FC-AL帶寬分配問(wèn)題轉(zhuǎn)換成如下的優(yōu)化問(wèn)題:

???

2.3 PSO求解的算法流程
??? (1)初始化粒子群,包括種群規(guī)模,,每個(gè)粒子的位置和速度,。
??? (2)計(jì)算每個(gè)fi
??? (3)對(duì)每個(gè)fi,,比較它的適應(yīng)值和個(gè)體最優(yōu)值pbesti,,如果較好則替換pbesti
??? (4)對(duì)每個(gè)fi,,比較它的適應(yīng)值和全局最優(yōu)值gbesti,,如果較好則替換gbesti
??? (5)根據(jù)公式(10),、(11)更新粒子的速度和位置,。
??? (6)如果滿足結(jié)束條件(誤差足夠好或達(dá)到最大循環(huán)次數(shù))則退出,否則回到(2),。
3 仿真實(shí)例
??? 端到端延遲是構(gòu)成仲裁環(huán)節(jié)點(diǎn)間的信息交互的一個(gè)重要組成部分,,如果不能滿足端到端延遲,則無(wú)法保證消息的實(shí)時(shí)性,。為了滿足消息傳輸?shù)膶?shí)時(shí)性要求,,需對(duì)信息包進(jìn)行拆分,,這必然會(huì)引起一些控制信息的增加,鏈路利用率會(huì)有所下降,。通過(guò)試驗(yàn)將本文方法(方法A)與耗盡型(方法B)和比例型(方法C)方法[1]進(jìn)行了對(duì)比,。表1給出了實(shí)驗(yàn)中的一組消息集,由仲裁環(huán)1Gbps的標(biāo)準(zhǔn)速率將消息周期轉(zhuǎn)換為對(duì)應(yīng)的消息長(zhǎng)度,在方法A中取(α12,…α10)=(10,,9,,…1),種群大小為30,,最大迭代次數(shù)為10 000,。表2為A、B,、C三種方法的帶寬分配結(jié)果,。圖1、圖2,、圖3和表3為三種方法下的仿真結(jié)果比較,,主要比較了三種方法下消息的平均延遲。由圖可知,,方法A的端到端延遲明顯比其他兩種方法小,。由表3可以看出,本文提出的帶寬分配方法在保證實(shí)時(shí)性上明顯好于其他兩種方法,,而由此帶來(lái)的鏈路利用率的損失并不大,。仿真結(jié)果表明,本文方法可以很好地滿足網(wǎng)絡(luò)的實(shí)時(shí)性要求,。

?

????? ??????

?

?????????? ?

?

?????????????????? ?圖1 方法A端到端延遲曲線??????????????????????????? 圖2 方法B端到端延遲曲線

?

?

圖3 方法C端到端延遲曲線

?


??? 光纖通道仲裁環(huán)節(jié)點(diǎn)帶寬分配,,是以保證網(wǎng)絡(luò)消息的實(shí)時(shí)傳輸為目標(biāo)的。本文從FC-AL的網(wǎng)絡(luò)特性出發(fā),,根據(jù)協(xié)議規(guī)定的公平訪問(wèn)機(jī)制,,提出了一種能保證消息實(shí)時(shí)傳輸?shù)膸挿峙浼s束條件,并通過(guò)粒子群算法對(duì)帶寬進(jìn)行優(yōu)化求解,。通過(guò)實(shí)驗(yàn)證明,,該算法在滿足節(jié)點(diǎn)消息傳輸?shù)膶?shí)時(shí)性要求上具有良好效果。
參考文獻(xiàn)
[1] ?AGRAWAL G, CHEN Biao, ZHAO Wei. Guaranteeing synchronous message deadlines with the timed token medium access control protocol[A].IEEE Transactions on Computer,,March,1994:327-339.
[2] ?XIONG Hua Gang, LUO Zhi Qiang,, ZHANG Qi Shan.Bandwidth allocation for real time communication with?LTPB protocol[A]. New York:IEEE Aerospace and Electronics Conference[C].IEEE,,1997:920-92.
[3] ?ZHOU Qiang, ZHANG Yan Zhong,,LUO Zhi Giang. An optimal bandwidth allocation scheme and real—time performance analysis for LTPB network[A].IEEE Aerospace ?and Electronics Conference[C]. IEEE,2000:180-186.
[4] ?KOH J, KIM T, SHIN H. Scheduling real-time messages in a fibre channel arbitrated loop[J]. IFAC Control Engineering Practice,1998,6(1):119-127.
[5] ?林強(qiáng),熊華鋼,張其善. 強(qiáng)實(shí)時(shí)條件下光纖通道仲裁環(huán)帶寬分配方法[J]. 北京航空航天大學(xué)學(xué)報(bào),,2005,31(4):443-446.
[6] ?T11.3 task group of technical committee T11. fibre channelframing and signaling rev1.90[S]. 2003.
[7] ?T11.3 task group of technical committee T11, fibre channel arbitrate loop rev7.0[S]. 2001.

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點(diǎn),。轉(zhuǎn)載的所有的文章,、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無(wú)法一一聯(lián)系確認(rèn)版權(quán)者,。如涉及作品內(nèi)容、版權(quán)和其它問(wèn)題,,請(qǐng)及時(shí)通過(guò)電子郵件或電話通知我們,,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失,。聯(lián)系電話:010-82306118,;郵箱:[email protected]