基于贝叶斯决策的自适应p-持续CSMA协议

黄业文，杨荣领，邝神芬

（1.华南理工大学广州学院 广东 广州　510800；2.韶关学院 广东 韶关　512005）

基于贝叶斯决策的自适应p-持续CSMA协议

黄业文1，杨荣领1，邝神芬2

（1.华南理工大学广州学院 广东 广州510800；2.韶关学院 广东 韶关512005）

针对计算机终端中p-持续CSMA协议的信道利用率的问题进行研究，为了能更好的利用信道发送数据，提高信道利用率，采用了基于贝叶斯决策统计理论，通过全概率公式拆分，对p-持续CSMA协议中的参数p进行动态自适应拟合的一种CSMA协议改进方法。用Matlab2010a进行模拟仿真实验，得出改进后的自适应p-持续CSMA协议比静态的p-持续CSMA协议对信道有高20%左右的利用率。

贝叶斯决策；p-持续CSMA；吞吐率；自适应

网络终端信道的分配从上世纪70年代就成为了计算机网络研究的热点，最开始是 Norman Abramson研究的ALOHA系统，经历了纯ALOHA系统，分槽ALOHA系统。之后Kleinrock和Tobagi推广到载波检测协议，研究了持续的和非持续的CSMA协议，又分为1-持续的CSMA协议和p-持续的CSMA协议。后来进一步改进成带冲突检测的CSMA协议。之后更多的工作者研究了p-持续CSMA协议在计算机终端随机竞争接入信道中的应用[1-6]。CSMA协议主要是发送从MAC子层交过来的数据帧，对于怎么样有效地发送数据帧，使得信道能够有较好的利用率，并且尽可能大的提高信道利用率成为了CSMA协议研究的最主要的问题。直至当代，CSMA协议仍然是计算机网络研究的热点，各类文献已经在研究各种实际出现的繁杂情况下的数据帧发送，并且已有了一定的研究结果。本文在一些文献研究的基础上，提出基于贝叶斯决策的自适应p-持续CSMA协议，该协议是通过全概率公式拆分，对p-持续CSMA协议中的数据帧发送概率p利用贝叶斯公式进行拟合的改进[7-8]协议。通过理论分析之后，用Matlab2010a进行模型仿真，仿真结果表明本文基于贝叶斯决策的自适应p-持续CSMA协议比常见的的静态p-持续CSMA协议具有更突出的信道利用率。

1　自适应p-持续CSMA协议模型

在常见的p-持续CSMA协议中[9]，信道以数值p发送上层下交的数据时，p值是静态不变的。这样的系统运行起来比较简单，不用关注系统的拥塞情况，只能按照既定的协议单调地发送数据帧。从而对信道的利用率也不会很高，使得系统一直在忙却处于信道利用率效率较为低下的状态中。相对于一般的静态p-持续CSMA协议[10]，为了提高系统信道利用率，本文利用全概率公式拆分提出基于贝叶斯决策的自适应p-持续CSMA协议模型，该模型的主要特点是：只要发生数据帧传输，数值p随着系统拥塞情况进行动态调整，不管终端是否发生冲突重传。其中数值p由基于贝叶斯决策统计理论的全概率公式拆分计算来确定。这样的模型因为关注到系统的拥塞状况，对拥塞状况来调整终端数据帧的发送频率来避免数据帧发送发生冲突，因此能够使得系统信道能够得到较高的利用率。但是也存在一定的缺陷，为了调整p的取值，需要用到一小部分系统的资源。该模型实质就是损失一部分系统资源来调整p值提高系统信道利用率的模型研究，这也是动态p-持续CSMA协议模型绕不过去的弯。在模型中，发生数据帧传送时，如果信道不空闲，终端继续监测信道直到信道重新处于竞争时隙，此时，终端才开始发送上层移交的数据，终端以概率p发送数据，以概率1-p将数据调整到下一个时隙继续发送，时隙宽度记为δ。如果系统终端顺利发送数据帧，立即调整p值大小，如果终端发送数据帧过程中遭遇冲突，系统同样调整p值大小，将数据帧发送往后延迟随机时间t，t∈（0，T），再次进行监测，竞争信道以等待发送，如此循环。

基于贝叶斯决策的自适应p-持续CSMA协议的随机接入流程如图1所示，发送数据帧是引入随机数j，j与p比较后，j

1）系统信道只有一个，有无穷终端，；

2）数据帧平均到达率λ～N（μ，σ2），其密度函数为φμ，σ（x）；

3）终端在由数据帧发送转为数据帧接收是瞬时的；

4）信道实时监测接收信号；

5）在每个时隙（间隔足够小）内，每一终端有不超过一个数据帧等待竞争信道；

6）系统内站点间的数据传输存在延时，延时假设为τ；

7）系统内包括新到达的数据帧和需要重发的数据帧，各个终端数据帧等待发送的数目服从参数为λ的泊松分布，λ为平均到达率，密度函数为p（k，λ），k∈N；

8）数据帧长度相等，记每帧时为F，F是τ的整数倍；

9）若发送过程中检测到发生冲突，立即停止数据帧传送；

10）数据帧冲突时，终端发送冲突信号的时间J对各个终端一样；

11）只要信道发送数据时数据帧重叠，就需要重新发送数据帧；

12）冲突的检测时间忽略不计；

13）信道是理想信道。

设模型中有上层移送数据待发的终端数记为a，即整个系统要发的帧数为a。a由假设（1）、（2）确定，a为正数。系统终端发送数据帧时，当p最接近时信道利用率达到最大，所以对p进行调整取值时，最优的选择应该是，但是这只是客观存在的一个数值，不可能精确的寻找出来，只能通过模型研究，拟合，寻求尽量接近其理想值的方法。设p0是终端系统即时p值，由假设（2），通过全概率公式计算，对即时p值进行最大概率的估计，得a的初始估计为这个数值作

为贝叶斯公式的先验概率，该a值认为是瞬时λ的最优概率估计，再由假设（2），因为λ>0，λ～N（k，σ2），由3σ原则，可得λ∈（0，2k）取值范围是，从而

图1　基于贝叶斯决策的自适应p-持续CSMA协议流程图Fig.1　Flowchart of dynamic p-persistent CSMA protocol based on Bayesian decision theory

根据模型假设（1）、（2）可得以下计算式子：

由式（1）～（7）可计算出：

将k逐一取值，计算之后得当p=p0时，P（a=k|C）、P（a=k|的最大值，记为

在信道利用率概率最大的意义下，p=p0时进行一次信道竞争后，若系统遭遇传送数据帧重复，p自适应调整为；若系统不发生数据帧重复，p自适应调整为至此完成一个数据帧发送，继续循环下去即为信道吞吐率最大的基于贝叶斯决策的自适应p-坚持CSMA协议模型，该模型较好的解决了关键参数p的选取的问题。参数p的选取基于贝叶斯公式，是由系统拥塞情况调整的，这是本文基于贝叶斯决策的自适应p-坚持CSMA协议算法的改进之处。

对函数f（p0，C），和f（p0，C）的部分计算结果可见表1。在实际应用时，只要对照表1就可以查询到相应的p值。

表1　基于贝叶斯决策的自适应p-持续CSMA协议p值选取表Tab.1　p-value selection table of dynamic p-persistent CSMA protocol based on Bayesian decision theory

2　模型仿真

为了检验模型的信道利用率，利用Matlab2010a进行仿真实验，设信道利用率为S，每帧时平均发送帧数为G，初始发送概率设为p0=1，发送延时τ=512 bytes，数据帧传送帧时F =16τ，冲突反馈时长J=τ。仿真得到的信道利用率S和平均发送帧数G的关系如图2所示。

图2每帧时平均发送帧数G∈（0，1 000），可以看到G值很大时信道利用率仍然在85%左右，这表明模型的吞吐率是较好的。

在p-持续CSMA协议中，分别对p=1，0.5，0.1，0.01，进行了F=16τ，J=τ，τ=512 bytes的模型仿真，其S和G的变化关系如图3所示。

图3可以看到不同的p值发生拥塞的情况不同，p= 1，0.5，0.1，0.01时发生拥塞分别发生在G=10，20，100，1 000，并且在没有发生拥塞时信道的利用率也是比较低效的。在G∈（0，10）的一般取值范围内信道利用率在45%～65%之间。

图2　自适应p-持续CSMA协议S和G变化关系图Fig.2　S and G function diagram of dynamic p-persistent CSMA protocol based on Bayesian decision theory

为了更清楚地对比文中的动态p值协议和一般的静态p值协议的信道利用率吞吐性能，取0≤G≤10，以步长0.1进行仿真，得到p分别为1，0.5，0.1，0.01情形下平均发送帧数G和信道利用率S的函数关系，如图4所示。图4充分体现了本文模型的优越性能。

3　结　论

图2、图3和图4的Matlab2010a仿真实验表明，相对于常见的p-持续CSMA协议，本文基于贝叶斯决策的自适应p-持续CSMA协议使得终端数据发送在整体上有较好的数据帧吞吐性，信道得到较高的利用率。改良后的基于贝叶斯决策的自适应p-持续CSMA协议整体信道利用率高达85%以上，而其他的协议信道利用率或者开始较高但后来随着数据发送量增大立刻急剧降低，例如p=1，p=0.5时，或者开始较低而随着数据发送量增大才会缓慢改善慢慢增大，例如p= 0.1，p=0.01时，这些情况对信道的平均利用率在45～65%之间。本文基于贝叶斯决策的自适应p-持续CSMA协议很好的避免了常见的p-持续CSMA协议中信道利用率较低的缺陷，实际应用时，可将p值先计算出来，存于一个存贮栈中，方便读取，模型的实际应用性较好。

图3　p-持续CSMA协议S和G变化关系图Fig.3　S and G function diagram of p-persistent CSMA protocol

图4　自适应p和固定p的协议S和G变化关系图Fig.4　S and G function diagram about dynamic p-persistent and p-persistent's CSMA protocol

协议模型提出了一种能大幅度提高信道利用率的动态改变p值的新方法，该模型的研究是初步的，下一步将对模型进行完善。模型中的一部分假设是比较理想的，实际情况会复杂的多，例如，信道监测可能受到系统电压变化产生的一些信号影响，信道不是理想信道等等，所以要对协议模型进行进一步的完善，能够让模型越来越适用于复杂的实际。

[1]Gallager R G.A perspective on multiaccess Channels[J]. IEEE Trans.on Information Theory，1985，31（2）:124-142.

[2]Cali F，Conti M，Gregori E.IEEE 802.11 protocol:design and performance evaluation of an adapative backoff mechanism[J]. IEEEJournalonSelectedAreasinCommunications，2000，18（9）:1774-1786.

[3]Breno R，Conti M，Gregori E.Optimal capacity of p-persistent CSMA protocols[J].IEEE Communications Lettes，2003，7 （3）:139-141.

[4]Cali F，Conti M，Gregori E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit[J]. IEEE/ACM Trans.on Networking，2000，8（6）:785-799.

[5]毛秀伟，吴铁军.自适应p-持续CSMA/CD介质访问控制策略[J].通信学报，2003，24（8）:161-167.

[6]何伟，南敬唱，潘峰.改进的动态p-持续CSMA协议[J].计算机工程，2010，36（21）:118-120.

[7]朱金玲.贝叶斯决策分析及改进 [J].江苏统计，2006（6）: 27-28.

[8]翟军昌，车伟伟，刘艳丽，等.基于改进信息增益的垃圾邮件过滤研究[J].电子设计工程，2012（13）:9-11.

[9]吴汶泰，扈维，林胜洁.颁布式单片机网络中CSMA的软件设计与性能分析[J].电子科技，2009（7）:93-95.

[10]Andrew S.Tanenbaum.计算机网络[M].潘爱民，译.4版.北京：清华大学出版社，2004.

Adaptive p-persistent CSMA protocol based on Bayesian decision theory

HUANG Ye-wen1，YANG Rong-ling1，KUANG Shen-fen2
（1.Guangzhou College of South China University of Technology，Guangzhou 510800，China；2.Shaoguan University，Shaoguan 512005，China）

Research on the problem about the channel utilization of p-persistent CSMA protocol in computer terminal.In order to improve the channel utilization，this paper proposes an adaptive p-persistent CSMA protocol based on Bayesian decision theory by calculation of full probability formula.Using Matlab2010a to carry on the simulation experiment，the improved adaptive p-persistent CSMA protocol has a higher utilization ratio than the others of fixed p-CSMA protocol which it rase about 20%.

Bayesian decision theory；p-persistent CSMA；throughput；adaptive

TN911.1

A

1674－6236（2016）01-0073-04

2015-10-08稿件编号：201510030

国家自然科学基金（61305036）；华南理工大学广州学院青年教师科研基金（XQ114004）

黄业文（1979—），男，广西北流人，硕士，讲师。研究方向：数理统计，计算机网络与分布计算。