实时局域网协作对称算法建模及性能分析

【摘要】本文在分析冲突预留技术基础上[3-4]，提出简易协作对称算法SCSA。证明了该算法在有时隙和无时隙网络中对于实时环境的适应性。 1 协作对称算法建模 1.1 SCSA原理 简易协作对称算法SC...

摘要 为提高实时局域网的信道容量和减少各工作站的平均等待时间。以冲突预留技术为基础提出适合实时局域网通信的简易协作对称算法，此算法遵循先进先出原则。并对该算法的稳定性及网络负荷上界进行了分析。结果证明该算法在实时局域网传输中的有效性，并验证了高数据量传输时其性能接近TDMA。

关键词 实时局域网；节点缓冲；界限值

中图分类号TP393.1，TP393.03 文献标识码A 文章编号 1674-6708（2012）64-0192-02

0 引言

实时局域网的首要目标是“实时”，因此无法容忍超过阈值的延迟。现有算法要么增加额外的复杂程度，要么降低信道的利用率。传统的ALOHA和CSMA算法随着试图获得信道节点的增多，冲突数量将上升并导致节点重发，此效应将扩散至几乎所有信道，最终导致整个信道瘫痪，无法传输有效数据包[1-2]。

本文在分析冲突预留技术基础上[3-4]，提出简易协作对称算法SCSA。证明了该算法在有时隙和无时隙网络中对于实时环境的适应性。

1 协作对称算法建模

1.1 SCSA原理

简易协作对称算法SCSA是一种低流量的异步CSMA，当流量增加时，该算法与时分多址TDMA算法类似[5-6]。该算法具有简便性、鲁棒性、稳定性、响应时间有限性等特点。

如果网络中所有节点都监控信道，能够侦测到是否有传输。任一时刻，网络节点存在一条可随实际情况变化的命令，节点得到命令时就播报数据包。

如果在δ时间内一旦侦测到媒介上的冲突（δ与端对端传输延迟时间τ相关，通常不超过2τ），便通过干扰频道或播放特殊频率信号的方式通知其他站点，此节点冲突未解决时所有其他站点都将停止进一步工作。实时指令前的节点在站点间强加一个时间基准（长度为δ的时隙），在此期间，卷入冲突的节点在各自时隙内提出请求。

这个时期将持续Nδ（N为总节点数），直到所有冲突信息实现成功传输。此算法允许数据包长度变化，通过监测是否有载波的方式探测数据包传输的终止，载波消失时传输节点取消数据包传输。所有拥有数据包的节点都希望在当前时隙终止时完成数据包传输。

SCSA采用先入先出模式，高负载条件时，每个节点可以不考虑当前命令直接在各时隙参与传输。稳态工作时所有节点的等待时间分布相同。

1.2 SCSA建模

采用具有变化服务时间的半马尔克夫过程对SCSA进行建模，采用计算密集型先求近似解。

用表示第i个节点，则有

（1≤i

式（1）表明Si节点传输数据包的优先权高于Si+1节点。节点如在预设时间内无信号输出则表明发生冲突，冲突分辨周期CRP为冲突检测与系统同步时间之和，CRP不包括使系统处于同步状态所需的时间。

CRP的第一个时隙为节点的当前顺序头，接下来的第i个时隙属于第i个成员。

如果节点i传输Ti时长的包所需时隙持续时间E为

时隙周期随加入传输队列冲突节点数的变化而变化。CRP只依赖网络中的节点总数和时隙长度δ，因此为固定值。每个时隙只有一个CRP，每个CRP期间参与的节点数越少则通道利用率越低。

现在计算绝对下限，最差情况时一个时隙中只有两个节点，此时的持续时间E为

其中，Tmin为最短数据包长度；Tmin为下一个最短数据包长度。

因此系统容量的绝对下界C1b为

2 稳定性分析

针对实时通信局域网，稳定性需满足输出为输入的非减函数和最大平均等待时间为有限值两个条件。

为保证等待时间有限，则要求系统利用率小于1。可得

将式式（37）对Q进行归一化处理，可得数据包到达率的约束条件为

式（9）和式（10）相比，前者更严格的将范围限制在0~1范围内。

事实上，式（6）将在式（7）起作用前不成立，因此导致式（7）并不是真正的界限。

3 容量高负荷上界

随着越来越多的数据包到达节点，获取时隙的时间变长。因为CRP为固定值，时隙长度的增加会提高系统的利用率，系统容量被高负荷系统容量Ch1限制，Ch1为

为给到达率相等的所有节点设置一个上限，使用相同模型重新定义服务时间r为

如果只有一个节点试图获得数据则要求系统模型中时隙持续时间为1，否则持续时间大于1。如果队列中剩下N个客户，则为它们服务所需时间为

当所有节点到达率相等时，实际的系统利用率和平均等待时间将介于求得的上限值和下限值之间。

当节点数为32，δ=0.01时，SCSA的性能界限如图1所示。图2为节点数和δ与图1相同时，系统数据包在节点处平均等待时间的上限和下限，λ为总平均到达率的函数。仿真表明随着系统负载的增加，节点平均到达率相同时，曲线渐渐接近于容量上限而不是下限。验证了算法性能接近TDMA。

当节点数为16、32、48和64，δ=0.1时的系统利用率见图3。由图知：当λ＜0.08时（归一化），最坏情况的平均等待时间为4个数据包的传输时间，且该系统容量的退化情况不会低于0.85。

4 结论

对不要求完全同步网络的冲突保留算法进行变换提出简单的协作对称算法SCSA。分析了SCSA在节点处有/无缓冲能力的情况。此算法遵守先进先出原则，在高通信量传输时性能接近TDMA。此算法数据包的传输时间变化较小，结合强加的延时上限，使得SCSA算法在实时通信方面尽显优势。

参考文献

[1]L.Kleinrock，S.S.Lain, Packet Switching in a Multi-Access Broad-cast Channel: Performance Evaluation[J].IEEETransactions on Communications，1975，COM 23：410-423.

[2]何伟,南敬昌,潘峰.改进的动态p-坚持CSMA协议[J].计算机工程，2010，36(21)：118-120.

[3]R. H. Sherman, M.G.Gable, G.McClure.Concepts, Strategies for Local Data Network Architectures[J].Data Communications，1978，7(7):39-49.

[4]Leonard Kleinrock and Simon Lam.Packet switching in a multiaccess broadcast channel: performance evaluation[J].IEEE munications.1975, COM-23(4)：410-423.

[5]丁心泉, 吴介一.RLAN:一种面积CIMS的实时局域网[J].小型微型计算机系统，1997，18(8)：19-22.

[6]马锦荣.一种短距离无线传输的CSMA/CA协议实现方法[J].单片机与嵌入式系统应用，2010(5)：18-19.