??? 摘 要： 依據實時系統中的周期任務模型，研究了一種帶寬分配" title="帶寬分配">帶寬分配算法實現合理的帶寬分配，以保證各節點的消息均能實時傳輸，并用粒子群算法" title="粒子群算法">粒子群算法對其進行了實現。
??? 關鍵詞： 仲裁環? 實時傳輸? 公平算法? 帶寬分配? 粒子群算法
?
??? 光纖通道" title="光纖通道">光纖通道(Fibre Channel)協議是由ANSI(American Nation Standards Institute)的X3T11小組制定的一種高速串行通信協議標準。光纖通道仲裁環（FC-AL）提供了在共享式網絡中把多個節點連接在一起的方法，是光纖通道的一種重要的拓撲結構，并以其相對低廉的價格獲得了廣泛的應用。在實時通信領域中，要求網絡能夠提供在實時約束下的消息傳輸。因此改善FC-AL的實時性" title="實時性">實時性能，是目前研究的重點。
??? 粒子群優化算法PSO（Particle Swarm Optimization）是一種新興的進化計算技術，具有有效的搜索和優化能力。它的優點在于流程簡單易實現，算法參數簡潔，無需復雜的調整。因此在近幾年，粒子群算法得到迅速發展，已廣泛應用于函數優化、神經網絡訓練、模糊系統控制以及其他遺傳算法的應用的領域。
??? 在實時通信領域中，要求網絡提供嚴格實時約束下的消息傳輸，強調對每個特定消息的延時控制，網絡帶寬在各節點之間的分配直接影響到網絡的實時特性，網絡的可達負載率UA（當網絡負載率低于這個值時，網絡中所有的消息的實時性都能得到滿足）是評判網絡實時性能的標準之一。參考文獻[1-5]在這方面都做了有益的研究，但由于各種原因，在網絡的可達負載率方面效果都不太理想。本文對光纖通道仲裁環帶寬分配算法進行了研究，提出了保證環路上各節點消息實時傳輸的帶寬確定方法，并證明了即使在最差的情況下，保證消息集嚴格實時的網絡可達負載率幾乎可以達到100％。在此基礎上，利用優化設計的思想將問題轉換為多約束條件的函數優化問題，并用粒子群算法對其進行優化計算，使之成為提高網絡實時性能的新思路。
1 FC-AL的網絡模型[6-7]
??? 光纖通道的環路仲裁協議與令牌環訪問協議一樣，屬于公共信道多址接入協議，環路上的各節點共享環路帶寬。當前環路上有消息需發送的所有節點組成一個訪問窗，窗內優先級最高的節點最先贏得仲裁，贏得仲裁的節點向環路發送一個數據包，如果此節點還有消息需要發送，即使它擁有較高的優先權，也必須等到“訪問窗”中的其他節點都有機會發送一次后才能申請下一次環路仲裁。對網絡中的實時消息流來說，某節點當前到達的消息，必須在下一個消息到來的時間間隔之內發送完畢，否則將不能實時傳輸。由于光纖通道幀格式中數據域較大（2KB），在“公平算法”下，如果各節點都以最大" title="最大">最大數據發送，則當前“訪問窗”中其他節點消息的總發送時間，可能會造成該節點消息不能實時傳輸。根據參考文獻[4]的思想，可以對各節點在贏得仲裁后發送的數據包大小(packet size)加以限制，即對其在一個“訪問窗”中的消息發送長度加以限制，從而防止節點占有環路使用權的時間過長，以至影響其他消息的實時傳輸。
1.1 消息模型
??? 消息模型采用實時通信中的周期任務模型，假設網絡中有n個節點，每個節點各有一個實時消息流需要在網絡中傳輸，因而有n個消息流S1，S2,…,Sn，由它們組成一個消息集合M，即:
??? M={S1,S2,…，Sn}???????????????????????????????????????? ?(1)
??? 每個消息流均可表示為一個二維數組，對于Si，有:
??? Si=(Ci,Pi)????????????????????????????????????????????? ? (2)
??? 消息流負載率Ui定義為:
??? Ui=Ci/Pi????????????????????????????????????????????????????? ????? (3)
式中,Pi表示消息產生的周期，對非周期性消息，表示消息產生的最小時間間隔。Ci表示消息的長度，即該消息的傳輸時間，內容包括網絡協議規定的分隔符、幀頭信息、信息域和校驗碼等幀的全部信息。
??? 網絡總的負載率為:
??? 
1.2 帶寬計算方法及性能分析
1.2.1 實時限制條件
??? 若fi為節點i在一次“訪問窗”內分配的網絡帶寬，則一個訪問窗的最大帶寬（傳輸時間上限）為：
??? 
??? 對特定消息流，如果所采用的帶寬分配方法既能滿足協議限制條件又能滿足時限限制條件，則在該帶寬分配方法下，對特定消息流可實現實時傳輸。
??? (1)協議限制條件
??? 在一個采用公平算法的訪問窗口中，用于發送消息的總帶寬應滿足:
??? 
式中，Pmin=min(P1,P2,…Pn),δ表示建立一個訪問窗需要的其他開銷。
??? (2)時限限制條件
??? 對于任意時間間隔t，用Xi(t)表示節點發送消息的最小時間量，根據FC-AL的在最差情況下實時消息的調度原則[5]，有：
??? 
式中，θ=min(fi,t-[t/(Fmax+?啄)]×(Fmax+δ)), [·]取整符號。
??? 消息集合M中每個消息在其最大允許時間內，應有足夠發送該消息的時間，因此對于任意消息流Si，應有:
??? Xi(Pi)≥Ci ? i=1,2,…n??????????????????????????????????? (8)
1.2.2 帶寬分配方法
??? 通過以上分析，可以采用如下方法確定各個節點在一次訪問窗內所分配的帶寬fi：
??? mi×(Fmax+δ)+(Fmax+δ)≤Pi??????????????????????????????? (9)
式中，
表示向上取整，亦即節點在隨后的mi次贏得仲裁后，可將一個消息流Ci全部發送完，其中每個訪問窗內發送的信息段為cij(j=1,2,…,mi)。需要指出的是，盡管節點i在一個訪問窗內發送cij時分配的帶寬（“用時”）為fi，但由于在該訪問窗內需要等待其他節點發送信息（等待時間為Fmax-fi），因此，發送cij的實際最大“耗時”為Fmax。根據最差情況下實時消息的調度原則，節點i沒能進入第一個訪問窗，所以還必須等待一個訪問窗的時間，最大為Fmax+δ。
1.2.3 實時性能分析
??? 定理1 如果各節點以（9）式提供的方法分配帶寬，則M中所有消息實時性均能得到保證，即對所有消息都能滿足協議限制條件和時限限制條件。
??? 證明:
??? (1)因為fi≤Ci，則mi≥1，又mi×(Fmax+δ)+(Fmax+δ)≤Pi
2(Fmax+δ)≤mi×Fmax+Fmax≤Pi
??? 則(6)式也成立。
??? (2)因為mi×(Fmax+δ)+(Fmax+δ)≤Pi，其中，
即：
??? 
??? 即（8）式也成立。
??? 通過證明，可知定理1成立。
??? 定理1說明了只要按（9）式分配帶寬，就能滿足消息實時傳輸的兩個限制條件，而不需對網絡負載率加以限制，因此，可以將網絡的可達負載率看成UA≈100%。
2 粒子群算法
2.1 粒子群算法
??? 粒子群優化算法PSO是Kennedy和Eberha于1995年提出的一種集群優化算法，同遺傳算法相似，是一種基于迭代的優化工具。PSO算法采用的是速度－位置搜索模型，每個粒子代表一個候選解，解的優劣程度由適應度函數來決定。xi=(xi1,xi2,…xin)表示第i個粒子在n維空間的位置。速度vi=(vi1,vi2,…vin)表示第i個粒子在搜索空間單位迭代的位移。PSO算法隨機初始化一群粒子，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。一個是粒子本身所找到的最優解，即個體極值pbest；另一個是整個種群目前找到的最優解，即全局極值gbest。粒子在找到上述兩個最優值后，根據以下公式更新其速度和位置：
??? 
式中，rand()是(0，1)區間上服從均勻分布的隨機數;c1、c2稱為學習因子，通常c1=c2=2；w是慣性權重，取值在0.4～0.9之間，一般的做法是將w初始取為：
??? 
式中，iter為當前的迭代次數，itermax為最大的迭代次數。為了防止粒子遠離搜索空間，粒子的每一維速度都被限制在[-vmax,vmax]之間。假設搜索空間為[-xmax,xmax]，通常：
??? 
2.2 利用粒子群算法求解帶寬
??? 這里利用粒子群算法求解FC-AL的帶寬分配問題。因為在發送的每幀數據中都包含有固定的控制信息，幀長越短，其控制比特占的比例越大，而使得帶寬利用率下降，在這種帶寬分配方法中，應該在滿足消息的時限要求的同時，使各節點所獲得的帶寬盡可能地大。綜合節點優先級和鏈路利用率兩方面因素，可將適應度函數設為：
??? 
式中,(α1,α2,…αn)表示各個節點優先級對應權值。
??? 根據上面對消息實時傳輸所需條件的討論，將每個fi看成一個“粒子”，通過設立目標函數和約束條件，可將FC-AL帶寬分配問題轉換成如下的優化問題：
??? 
2.3 PSO求解的算法流程
??? (1)初始化粒子群，包括種群規模，每個粒子的位置和速度。
??? (2)計算每個fi。
??? (3)對每個fi，比較它的適應值和個體最優值pbesti，如果較好則替換pbesti。
??? (4)對每個fi，比較它的適應值和全局最優值gbesti，如果較好則替換gbesti。
??? (5)根據公式(10)、(11)更新粒子的速度和位置。
??? (6)如果滿足結束條件(誤差足夠好或達到最大循環次數)則退出，否則回到(2)。
3 仿真實例
??? 端到端延遲是構成仲裁環節點間的信息交互的一個重要組成部分，如果不能滿足端到端延遲，則無法保證消息的實時性。為了滿足消息傳輸的實時性要求，需對信息包進行拆分，這必然會引起一些控制信息的增加，鏈路利用率會有所下降。通過試驗將本文方法（方法A）與耗盡型（方法B）和比例型（方法C）方法[1]進行了對比。表1給出了實驗中的一組消息集，由仲裁環1Gbps的標準速率將消息周期轉換為對應的消息長度,在方法A中取(α1,α2,…α10)=（10，9，…1），種群大小為30，最大迭代次數為10 000。表2為A、B、C三種方法的帶寬分配結果。圖1、圖2、圖3和表3為三種方法下的仿真結果比較，主要比較了三種方法下消息的平均延遲。由圖可知，方法A的端到端延遲明顯比其他兩種方法小。由表3可以看出，本文提出的帶寬分配方法在保證實時性上明顯好于其他兩種方法，而由此帶來的鏈路利用率的損失并不大。仿真結果表明，本文方法可以很好地滿足網絡的實時性要求。
?
????? 
?????? 
?
????????
?? ? 
?
?????????????????? ?圖1 方法A端到端延遲曲線??????????????????????????? 圖2 方法B端到端延遲曲線
?
?
圖3 方法C端到端延遲曲線
?
??? 光纖通道仲裁環節點帶寬分配，是以保證網絡消息的實時傳輸為目標的。本文從FC-AL的網絡特性出發，根據協議規定的公平訪問機制，提出了一種能保證消息實時傳輸的帶寬分配約束條件，并通過粒子群算法對帶寬進行優化求解。通過實驗證明，該算法在滿足節點消息傳輸的實時性要求上具有良好效果。
參考文獻
[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] ?林強,熊華鋼,張其善. 強實時條件下光纖通道仲裁環帶寬分配方法[J]. 北京航空航天大學學報，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.