摘 要： 依据实时系统中的周期任务模型，研究了一种带宽分配" title="带宽分配">带宽分配算法实现合理的带宽分配，以保证各节点的消息均能实时传输，并用粒子群算法" title="粒子群算法">粒子群算法对其进行了实现。
    关键词： 仲裁环  实时传输  公平算法  带宽分配  粒子群算法

    光纤通道" title="光纤通道">光纤通道(Fibre Channel)协议是由ANSI(American Nation Standards Institute)的X3T11小组制定的一种高速串行通信协议标准。光纤通道仲裁环（FC-AL）提供了在共享式网络中把多个节点连接在一起的方法，是光纤通道的一种重要的拓扑结构，并以其相对低廉的价格获得了广泛的应用。在实时通信领域中，要求网络能够提供在实时约束下的消息传输。因此改善FC-AL的实时性" title="实时性">实时性能，是目前研究的重点。
    粒子群优化算法PSO（Particle Swarm Optimization）是一种新兴的进化计算技术，具有有效的搜索和优化能力。它的优点在于流程简单易实现，算法参数简洁，无需复杂的调整。因此在近几年，粒子群算法得到迅速发展，已广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用的领域。
    在实时通信领域中，要求网络提供严格实时约束下的消息传输，强调对每个特定消息的延时控制，网络带宽在各节点之间的分配直接影响到网络的实时特性，网络的可达负载率U_A（当网络负载率低于这个值时，网络中所有的消息的实时性都能得到满足）是评判网络实时性能的标准之一。参考文献[1-5]在这方面都做了有益的研究，但由于各种原因，在网络的可达负载率方面效果都不太理想。本文对光纤通道仲裁环带宽分配算法进行了研究，提出了保证环路上各节点消息实时传输的带宽确定方法，并证明了即使在最差的情况下，保证消息集严格实时的网络可达负载率几乎可以达到100％。在此基础上，利用优化设计的思想将问题转换为多约束条件的函数优化问题，并用粒子群算法对其进行优化计算，使之成为提高网络实时性能的新思路。
1 FC-AL的网络模型[6-7]
    光纤通道的环路仲裁协议与令牌环访问协议一样，属于公共信道多址接入协议，环路上的各节点共享环路带宽。当前环路上有消息需发送的所有节点组成一个访问窗，窗内优先级最高的节点最先赢得仲裁，赢得仲裁的节点向环路发送一个数据包，如果此节点还有消息需要发送，即使它拥有较高的优先权，也必须等到“访问窗”中的其他节点都有机会发送一次后才能申请下一次环路仲裁。对网络中的实时消息流来说，某节点当前到达的消息，必须在下一个消息到来的时间间隔之内发送完毕，否则将不能实时传输。由于光纤通道帧格式中数据域较大（2KB），在“公平算法”下，如果各节点都以最大" title="最大">最大数据发送，则当前“访问窗”中其他节点消息的总发送时间，可能会造成该节点消息不能实时传输。根据参考文献[4]的思想，可以对各节点在赢得仲裁后发送的数据包大小(packet size)加以限制，即对其在一个“访问窗”中的消息发送长度加以限制，从而防止节点占有环路使用权的时间过长，以至影响其他消息的实时传输。
1.1 消息模型
    消息模型采用实时通信中的周期任务模型，假设网络中有n个节点，每个节点各有一个实时消息流需要在网络中传输，因而有n个消息流S₁，S₂,…,S_n，由它们组成一个消息集合M，即:
    M={S₁,S₂,…，S_n}                                          (1)
    每个消息流均可表示为一个二维数组，对于S_i，有:
    S_i=(C_i,P_i)                                                (2)
    消息流负载率U_i定义为:
    U_i=C_i/P_i                                                            (3)
式中,P_i表示消息产生的周期，对非周期性消息，表示消息产生的最小时间间隔。C_i表示消息的长度，即该消息的传输时间，内容包括网络协议规定的分隔符、帧头信息、信息域和校验码等帧的全部信息。
    网络总的负载率为:

1.2 带宽计算方法及性能分析
1.2.1 实时限制条件
    若f_i为节点i在一次“访问窗”内分配的网络带宽，则一个访问窗的最大带宽（传输时间上限）为：

    对特定消息流，如果所采用的带宽分配方法既能满足协议限制条件又能满足时限限制条件，则在该带宽分配方法下，对特定消息流可实现实时传输。
    (1)协议限制条件
    在一个采用公平算法的访问窗口中，用于发送消息的总带宽应满足:

式中，P_min=min(P₁,P₂,…P_n),δ表示建立一个访问窗需要的其他开销。
    (2)时限限制条件
    对于任意时间间隔t，用X_i(t)表示节点发送消息的最小时间量，根据FC-AL的在最差情况下实时消息的调度原则^[5]，有：

式中，θ=min(f_i,t-[t/(F_max+?啄)]×(F_max+δ)), [·]取整符号。
    消息集合M中每个消息在其最大允许时间内，应有足够发送该消息的时间，因此对于任意消息流S_i，应有:
    X_i(P_i)≥C_i   i=1,2,…n                                    (8)
1.2.2 带宽分配方法
    通过以上分析，可以采用如下方法确定各个节点在一次访问窗内所分配的带宽f_i：
    m_i×(F_max+δ)+(F_max+δ)≤P_i                                (9)

式中，表示向上取整，亦即节点在随后的m_i次赢得仲裁后，可将一个消息流C_i全部发送完，其中每个访问窗内发送的信息段为c_ij(j=1,2,…,m_i)。需要指出的是，尽管节点i在一个访问窗内发送c_ij时分配的带宽（“用时”）为f_i，但由于在该访问窗内需要等待其他节点发送信息（等待时间为F_max-f_i），因此，发送c_ij的实际最大“耗时”为F_max。根据最差情况下实时消息的调度原则，节点i没能进入第一个访问窗，所以还必须等待一个访问窗的时间，最大为F_max+δ。
1.2.3 实时性能分析
    定理1 如果各节点以（9）式提供的方法分配带宽，则M中所有消息实时性均能得到保证，即对所有消息都能满足协议限制条件和时限限制条件。
    证明:
    (1)因为f_i≤C_i，则m_i≥1，又m_i×(F_max+δ)+(F_max+δ)≤P_i2(F_max+δ)≤m_i×F_max+F_max≤P_i
    则(6)式也成立。

    (2)因为m_i×(F_max+δ)+(F_max+δ)≤P_i，其中，即：

    即（8）式也成立。
    通过证明，可知定理1成立。
    定理1说明了只要按（9）式分配带宽，就能满足消息实时传输的两个限制条件，而不需对网络负载率加以限制，因此，可以将网络的可达负载率看成UA≈100%。
2 粒子群算法
2.1 粒子群算法
    粒子群优化算法PSO是Kennedy和Eberha于1995年提出的一种集群优化算法，同遗传算法相似，是一种基于迭代的优化工具。PSO算法采用的是速度－位置搜索模型，每个粒子代表一个候选解，解的优劣程度由适应度函数来决定。x_i=(x_i1,x_i2,…x_in)表示第i个粒子在n维空间的位置。速度v_i=(v_i1,v_i2,…v_in)表示第i个粒子在搜索空间单位迭代的位移。PSO算法随机初始化一群粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。一个是粒子本身所找到的最优解，即个体极值pbest；另一个是整个种群目前找到的最优解，即全局极值gbest。粒子在找到上述两个最优值后，根据以下公式更新其速度和位置：

式中，rand()是(0，1)区间上服从均匀分布的随机数;c1、c2称为学习因子，通常c1=c2=2；w是惯性权重，取值在0.4～0.9之间，一般的做法是将w初始取为：

式中，iter为当前的迭代次数，iter_max为最大的迭代次数。为了防止粒子远离搜索空间，粒子的每一维速度都被限制在[-vmax,vmax]之间。假设搜索空间为[-xmax,xmax]，通常：

2.2 利用粒子群算法求解带宽
    这里利用粒子群算法求解FC-AL的带宽分配问题。因为在发送的每帧数据中都包含有固定的控制信息，帧长越短，其控制比特占的比例越大，而使得带宽利用率下降，在这种带宽分配方法中，应该在满足消息的时限要求的同时，使各节点所获得的带宽尽可能地大。综合节点优先级和链路利用率两方面因素，可将适应度函数设为：

式中,(α₁,α₂,…α_n)表示各个节点优先级对应权值。
    根据上面对消息实时传输所需条件的讨论，将每个fi看成一个“粒子”，通过设立目标函数和约束条件，可将FC-AL带宽分配问题转换成如下的优化问题：

2.3 PSO求解的算法流程
    (1)初始化粒子群，包括种群规模，每个粒子的位置和速度。
    (2)计算每个f_i。
    (3)对每个f_i，比较它的适应值和个体最优值pbest_i，如果较好则替换pbest_i。
    (4)对每个f_i，比较它的适应值和全局最优值gbest_i，如果较好则替换gbest_i。
    (5)根据公式(10)、(11)更新粒子的速度和位置。
    (6)如果满足结束条件(误差足够好或达到最大循环次数)则退出，否则回到(2)。
3 仿真实例
    端到端延迟是构成仲裁环节点间的信息交互的一个重要组成部分，如果不能满足端到端延迟，则无法保证消息的实时性。为了满足消息传输的实时性要求，需对信息包进行拆分，这必然会引起一些控制信息的增加，链路利用率会有所下降。通过试验将本文方法（方法A）与耗尽型（方法B）和比例型（方法C）方法^[1]进行了对比。表1给出了实验中的一组消息集，由仲裁环1Gbps的标准速率将消息周期转换为对应的消息长度,在方法A中取(α₁,α₂,…α₁₀)=（10，9，…1），种群大小为30，最大迭代次数为10 000。表2为A、B、C三种方法的带宽分配结果。图1、图2、图3和表3为三种方法下的仿真结果比较，主要比较了三种方法下消息的平均延迟。由图可知，方法A的端到端延迟明显比其他两种方法小。由表3可以看出，本文提出的带宽分配方法在保证实时性上明显好于其他两种方法，而由此带来的链路利用率的损失并不大。仿真结果表明，本文方法可以很好地满足网络的实时性要求。

                    图1 方法A端到端延迟曲线                            图2 方法B端到端延迟曲线

    光纤通道仲裁环节点带宽分配，是以保证网络消息的实时传输为目标的。本文从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.