基于P-Persistent CSMA改进协议的研究

摘要: 　　由CSMA协议派生出几种不同的协议：非坚持CSMA，1—坚持CSMA，Ｐ—坚持CSMA。这些协议被成功应用于对实时性要求不高的网络。为了满足对实时性的要求，埃施朗公司提出一种新的CSMA算法即可预测Ｐ—坚持CSMA协议。本文中我们将通过对这种协议种其它各种CSMA协议进行比较从而对其性能做出评价。 关键词: 　　P—坚持CSMA 可预测性P—坚持CSMA LonTalK Abstract: 　　There are several variants derived from CSMA protocol, such as non-persistent CSMA, 1-persistent CSMA, and p-persistent CSMA etc. These algorithms are successful in time-insensitive network. To meet the real-time requirements, Echelon Corporation proposed a novel CSMA algorithm, the predictive p-persistent CSMA protocol. In this paper, we evaluate the performance of this protocol by the comparison with other p—persistent CSMA protocols. Keywords: 　　p—persistent CSMA Predictive p—persistent CSMA LonTalk 引言 　　CSMA（Carrier Sense Multiple Access），即载波监听多路访问是一种竞争型的介质访问控制协议。它起源于美国夏威夷大学开发的ALOHA网所采用的竞争型协议，并进行了改进，使之具有比ALOHA协议更高的介质利用率。 一、CSMA介质访问控制方法 　　CSMA是一种常用竞争的方法来决定对媒体访问权的协议。在网络中，每个站点都能独立地决定帧的发送，若两个或多个站同时发送帧，就会产生冲突，导致所发送的帧都出错。因此，一个用户发送信息成功与否，在很大程度上取决于监测总线是否空闲的算法，以及当两个不同节点同时发送的分组发生冲突后所使用的中断传输的方法。 采用CSMA的技术要传输数据的站点，首先对媒体上有无载波进行监听，以确定是否有别的站点在传输数据。如果媒体空闲，该站点便可传输数据；否则，该站点将避让一段时间后再做尝试。这就需要有一种退避算法来决定避让的时间，常用的退避算法有三种： 　　（1）非坚持CSMA：一旦监听到信道空闲，立即发送；一旦发现信道忙，不再坚持监听，延时一段时间后再监听。缺点是：不能将信道刚一变成空闲的时刻找出。 定义 表示报文分组在信道上传播时延，T_d表示分组发送时间，G表示信道的负载量。 　　（2）l—坚持CSMA：监听到信道闲，立即发送；监听到信道忙，继续监听，直至出现信道空闲。缺点是：若有两个或更多的节点同时在监听信道，则发送的帧相互冲突，反而不利于吞吐量的提高。 信道的利用率S为 　　(3）P—坚持CSMA：当监听到信道闲时，就以概率P发送数据，而以概率（1－P）延迟一段时间（端到端的传播时延），重新监听信道。缺点是：即使有几个节点要发送数据，因为P值小于1，信道仍然有可能处于空闲状态。 信道的利用率S为 　　则三种介质访问控制方法的信道利用率S与信道负载量G的比较关系可用图1表示 　　由图1可知当网络负荷较低时（G的取值在1附近）信道的利用率S较高。当网络的负荷较高时（G≥4）,有两种情况出现：（1）P取值较大时（例如1和0.5），信道上会产生大量数据包碰撞，许多数据包必须延时重发，从而导致信道的利用率急剧降低，信道的通信能力也会大大降低；（2）P取值较低时或为0时，表面上信道的利用率S不会急剧下降，实际上我们由P取值很小可知，数据包立即发出的概率非常小（例如P=0.01），数据包很大可能会延时重发。综合上述两种情况可知，采用普通的P—persistent CSMA算法，不管P的取值大小或为0，当网络负荷较重时，都会造成大量数据包延时重发，这对实时性要求高的网络尤其是工业控制网是不能忍受的。这就要求我们采用新的MAC层算法。 　　二、可预测的P—坚持CSMA介质访问控制方法 　　但由于现有的MAC层算法，如IEEE802.2,802.3,802.4和802.5不能满足工业控制网使用多种通信介质以及对实时性的要求、在负荷繁重情况下维持性能的要求、以及支持大型网络的需要。因此，Echelon公司的LonTalk协议采用了可预测P-坚持CSMA（Predictive P—Persistent CSMA）算法。 可预测P—坚持CSMA通过对网络负载的预测，实现了对P值的动态调整。当网络空闲或轻载时，所有节点被随机分布在最小16个不同延时的随机时隙（见图2）上发送消息， 　　说明:协议为提高对重要数据包的响应时间可以提供优先机制,在信道上分配优先时隙(图中的虚线框)。 　　这样，在空闲或轻载的网络中，访问的平均延时为8个时隙，等同于P=0.0625（1/16）的P—坚持CSMA。当预测到网络负载要增加时，增加随机时隙的数目，将节点随机地分配在数目增多了的某个随机时隙上。 发送概率P＝l/R，R增加，P值降低，因此可预测P—坚持CSMA在保留P—坚持CSMA优点的前提下，通过对网络负载的事先预测，在网络轻载时，给网上节点分配数目较少的随机时隙，使节点对介质访问的时延最小；网络重载时，通过给网上节点分配数目较多的随机时隙，从而使节点同时发送数据带来的冲突最少，避免了重载下系统处于不稳定状态，保证信道仍能以最大的吞吐量工作，不会因过多的冲突而造成阻塞。 　　由以上可见，由于随机时隙数目的动态调整，实现了概率P值的动态调整。具体实现如下： 　　（1）P值的动态调整取决于随机时隙的动态调整。 　　当网络预测到负载增加时，节点将分布在更多的时隙上发送数据，增加的时隙的数量由参数BL(backlog)决定，参数BL被称作对信道上积压系数的估计，既网络负载，它代表了下一次循环将要发送数据包的节点数，取值范围是1～63，所以随机时隙的数目16*BL,最小16，最大1008。 　　（2）随机时隙的动态调整依赖于节点对网络负载的预测能力。 　　网上每个节点在启动发送数据之前，先预测BL的值，调整随机时隙数，然后在某一随机分配的时隙以概率1/（BL *l6）发送消息包。 BL是对当前网络繁忙程度的估计，每个节点都有一个BL值。节点是这样实现对BL预测的：要发送数据包的节点在它发送的数据包中，包含了要肯定应答接收该消息的节点数目，即发送消息包将产生的应答数信息，所有收到该消息包的节点的BL值通过加上该应答数获得新的BL值，从而使随机时隙的数目得以更新，若该节点有数据要发送，它将以新的概率值P在随机分配的时隙上发送，每个节点在数据包发送结束时，其BL值自动减1。可见，要实现预测，消息服务的类型必须选择应答服务。由于数据包采用典型的应答服务类型，50%或更高的负载可以预测。由此实现了每一个节点在任何时候都能动态地预测有多少节点要发送消息包，并且预测BL值的能力比较高。预测的精度越高，则重载时网络的冲突概率会越小，系统能够保证正常工作，轻载时介质访问时延也会越小。所以，可预测P—坚持CSMA协议能够满足特定环境下的要求。 　　在MAC层中，为提高紧急事件的响应时间，提供一个可选择优先级机制。该机制允许用户为每个需要优先级的节点分配一个特定的优先级时隙（如图1中虚线框所包含部分），在发送过程中，优先级数据报文将在那个时间间隙里将报文发送出去。优先时间间隙从0～127，0表示不需要等待立即发送，1表示等待一个时间间隙……，低优先级的节点需要等待较多的时间间隙，而高优先级的节点需要等待较少的时间间隙。这个时间间隙加在P—概率随机间隙之前（即节点的随机等待时间的随机间隙之前）。非优先级的节点必须等待优先级时隙都完成后，再等待P—概率时间间隙后发送。这样，加入优先级的节点具有更快的响应时间。 　　三、对比实验结果 　　实验表明，36个网络节点互联时，采用一般的P-坚持CMSA算法。当每秒传输的报文达500～1000包时，碰撞率由10%上升到54%，而采用可预测P—坚持CSMA在500包以下时碰撞率很低，在500～1000包时稳定在10%。 　　四、结束语 　　可预测P—坚持CSMA在保留P—坚持CSMA的优点前提下，通过对网络负载的预测从而动态地调整随机时隙数目，因而实现了概率P值的动态调整。这样，网络负载很重时发生冲突概率会减小，系统能够保证正常工作，轻载时介质访问时延也会减小。实际上，这种协议已成功应用于工业控制，楼宇自动化，测控，航空航天等领域。当然，可预测P—坚持CSMA并不能避免冲突的出现，而冲突的存在必然影响到响应时间。因此在对响应时间要求较高的应用中，可采用优先级加以弥补。 　　参考文献 1 Echelon Corporation， LonTalk Protocol Specification. Version 3.0， 1999 2 Echelon Corporation，Getting Started with the LONWORKS System starter kit ，1999 3杨育红 ， LON网络控制技术及应用， 西安电子科技大学出版社，1999 4马 莉 ， 智能控制与Lon网络开发技术， 北京航空航天大学出版社，2002 5冯晓升等译 ， LonWorks 技术—开放的控制网络与应用中的分布系统，2002 　　作者简介： 姓名：黄大君 出生年月：1974 年7月 现在合肥工业大学计算机与信息学院攻读硕士研究生 研究方向：计算机软件与理论 TEL：0551-338488