通信网络基础4-3

1、4.3 随机多址接入协议 1随机多址协议又叫做有竞争的多址接入协议。各节点在网络中的地位是等同的，通过竞争获得信道的使用权。 随机多址接入协议可分为：完全随机多址接入协议（ ALOHA 协议）载波侦听型多址接入协议不论是哪种随机多址接入协议，我们主要关心两个方面的问题：稳态情况下系统的通过率和时延性能系统的稳定性 随机多址接入协议ALOHA 协议是 70 年代 Hawaii 大学建立的在多个数据终端到计算中心之间的通信网络中使用的协议。其基本思想是：若一个空闲的节点有一个分组到达，则立即发送该分组，并期望不会和其它节点发生碰撞。 ALOHA 协议为了分析随机多址接入协议的性能，假设系统是由m个

2、发送节点组成的单跳系统，信道是无差错的，分组的到达和传输过程满足如下假定：各节点的到达过程为独立的参数为/m的Poisson过程，系统总的到达率为。在一个时隙或一个分组传输结束后，信道能够立即给出当前传输状态的反馈信息。反馈信息为“0”表明当前时隙或信道无分组传输反馈信息为“1”表明当前时隙或信道仅有一个分组传输（即传输成功）反馈信息为“e”表明当前时隙或信道有多个分组在传输，即发生了碰撞，导致接收端无法正确接收。ALOHA 协议碰撞的节点将在后面的某一个时刻重传被碰撞的分组，直至传输成功。如果一个节点的分组需要重传，则称该节点为等待重传的节点。对于节点的缓存和到达过程作如下假设： 假设A：无

3、缓存情况。在该情况下，每个节点最多容纳一个分组。如果该节点有一个分组在等待传输或正在传输，则新到达的分组被丢弃且不会被传输。在该情况下，所求得的时延是有缓存情况下时延的下界。假设B：系统有无限个节点（m=）。每个新产生的分组到达一个新的节点。这样网络中所有的分组都参与竞争，导致网络的时延增加。因此，在该假设情况下求得的时延是有限节点情况下的时延上界。ALOHA 协议纯ALOHA 协议 纯ALOHA 协议是最基本的 ALOHA 协议。 只要有新的分组到达，就立即被发送并期望不与别的分组发生碰撞。一旦分组发生碰撞，则随机退避一段时间后进行重传。纯ALOHA 协议纯ALOHA 协议如果从数据分组开始

4、发送的时间起点到其传输结束的这段时间内，没有其它数据分组发送，则该分组就不会和其它分组发生碰撞。在什么情况下图中阴影部分表示的数据分组（在t0+t时刻产生的分组）可以不受任何干扰的发送呢？与阴影帧的开始碰撞与阴影帧的结尾碰撞易受破坏区间假设系统中所有分组的长度相等，传输数据分组所需的时间定义为系统的单位时间，为了简化描述，令该值等于t，(下面的分析中令 t 等于1）。我们将时间区间t0，t0+2t称为阴影分组（在t0+t时刻产生的分组）的易受破坏区间。很显然，在纯ALOHA协议中，只有在数据分组的易受破坏区间内没有其它分组到达，则该分组可以成功传输。纯ALOHA 协议为了分析方便，设系统有无穷

5、多个节点（假设 B），假定重传的时延足够随机，重传分组和新到达分组合成的分组流是到达率为G的Poisson到达过程。则在纯ALOHA系统中，一个分组成功传输的概率，就是在其产生时刻前一个时间单位内没有分组发送，并且在该分组产生时刻的后一个时间单位内仅有一个分组（即该分组本身）发送的概率。纯ALOHA 协议纯ALOHA 协议根据泊松公式，在单位时间内，产生k个分组的概率是则根据上面的分析，我们可以得到在纯ALOHA系统中，分组成功传输的概率纯ALOHA 协议系统的通过率（单位时间内一个分组成功传输的概率）对上式求最大值，可得系统的最大通过率为1/2e0.184此时对应的G=0.5可见，效率很低。

6、从前面的描述中可以看到，在纯ALOHA协议中，节点只要有分组就发送，易受破坏区间为两个单位时间。如果我们缩小易受破坏区间，就可以减少分组碰撞的概率，提高系统的利用率。基于这一出发点，提出了时隙 ALOHA 协议。时隙 ALOHA 协议时隙 ALOHA系统将时间轴划分为若干个时隙，所有节点同步，各节点只能在时隙的开始时刻才能够发送分组，时隙宽度等于一个分组的传输时间。当一个分组在某时隙到达后，它将在下一时隙开始传输，并期望不会与其它节点发生碰撞。如果在某时隙内，仅有一个分组到达（包括新到达的分组和重传分组的到达），则该分组会传输成功。如果在某时隙内到达两个或两个以上的分组，则将会发生碰撞。碰撞的

7、分组将在以后的时隙中重传。很显然，此时的易受破坏区间长度减少为一个单位时间（时隙）。 时隙 ALOHA 协议时隙 ALOHA 协议利用前面的假设条件，并假定系统有无穷多个节点(假设B)。显然在一个时隙内到达的分组包括两个部分：新到达的分组重传的分组设新到达的分组是到达率为(分组数/时隙)的Poisson过程。假定重传的时延足够随机化，这样就可以近似地认为重传分组的到达过程和新分组的到达过程之和是到达率为G(G )的Poisson过程。时隙 ALOHA 协议分析则在一个时隙内有一个分组成功传输的概率为G e-G，它被定义为系统的通过率S（或离开系统的速率），即S=G e-G如果分组的长度为一个时

8、隙宽度，则系统的通过率就是指在一个时隙内成功传输所占的比例（或有一个分组成功传输的概率）。其最大通过率为1/e0.368，对应的G =1时隙 ALOHA 协议ALOHA的通过率曲线例4.1 若干个终端用纯 ALOHA 随机接入协议与远端主机通信，信道速率为 2.4kb/s。每个终端平均每3分钟发送一个帧，帧长为 200bit，问系统中最多可容纳多少个终端？若采用时隙 ALOHA 协议，其结果又如何？ALOHA 协议例子时隙 ALOHA 协议设可容纳的终端数为N。每个终端发送数据的速率是 bit/s。由于纯ALOHA系统的最大系统通过率为1/2e，则有若采用时隙ALOHA协议，最大通过率为1/e

9、，则有时隙 ALOHA 协议稳定性分析对于时隙ALOHA系统：当G1时，碰撞较多，从而导致系统性能下降。因此，为了达到最佳的性能，应当将G维持在1附近变化。时隙 ALOHA 协议稳定性分析当系统达到稳态时，应该有新分组的到达率等于系统的离开速率，即有S=图中，哪个平衡点是稳定的，哪个是不稳定的？为了分析系统的动态行为，我们先采用假设A （无缓存的情况）来进行讨论。时隙 ALOHA 的行为可以用离散时间马尔可夫链 来描述，其系统的状态为每个时隙开始时刻等待重传的节点数。时隙 ALOHA 协议稳定性分析qr：在碰撞后等待重传的节点在每一个时隙内重传的概率n：在每个时隙开始时刻等待重传的节点数m：系

10、统中的总用户数qa：每个节点有新分组到达的概率：m 个节点的总到达率( 即每个节点的到达率为/m ) ，其单位为分组数/ 时隙；Qr (i, n) ：n 个等待重传的节点中，有i个节点在当前时隙传输的概率；Qa (i, n) ：在当前时隙中，m-n 个空闲节点中有i个新到达的分组传输的概率。参数定义时隙 ALOHA 协议稳定性分析显然，每个节点有新分组到达的概率qa=1-e-/m 在给定n 的条件下，有Pn,n+i表示时隙开始时刻有n个等待重传的节点，到下一时隙开始点，有n+i个等待重传节点的转移概率。状态转移概率为时隙 ALOHA 协议稳定性分析2i(m-n) i=1 i=0 i= -1 时

11、隙 ALOHA 协议稳定性分析时隙 ALOHA 协议稳定性分析在稳态情况下，对于任一状态n而言，从其它状态转入的频率应当等于从该状态转移出去的频率，即有由于从n 转移到各种可能状态的概率之和为1， 从而有 利用 和状态转移概率Pn,n+i，就可以求出p0和pn。显然，如果重传的概率qr1，将会导致出现大量的碰撞，从而使系统中的节点长时间处于等待重传状态。为了进一步了解系统的动态行为，我们定义系统状态偏移量为： Dn = 当系统状态为n时，在一个时隙内等待重传队列的平均变化量 =（在该时隙内平均到达的新分组数）（在该时隙内平均成功 传输的分组数） = (m-n) qa- Psucc其中 Psuc

12、c = Qa(1,n) Qr(0,n) + Qa(0,n) Qr(1,n) 时隙 ALOHA 协议稳定性分析时隙 ALOHA 协议稳定性分析再定义当系统状态为n 时，一个时隙内平均传输的分组数为G(n) ，则有G(n)= (m-n) qa+ nqr将Qr(i，n)和Qa(i，n)代入Psucc表达式，有时隙 ALOHA 协议稳定性分析分组到达率（(m-n)qa）n 和分组离开率PsuccG (n)两条关系曲线图中的横轴有两个坐标: 一个是系统状态n，另一个是总的分组到达率G(n)=(m-n)qa+nqr。ALOHA动态性能曲线的分析从图中可以看出，Dn(重传队列的平均变化量)就是分组到达率曲线

13、与分组离开率曲线之差。两条曲线有三个交叉点即三个平衡点。在第一个交叉点与第二个交叉点之间的D (n)为负值，即系统的离开率大于分组到达率，因而会导致系统的状态减少。或者说，D(n)的方向为负。因而对第二交叉点的任何负的扰动都将导致系统状态趋于第一个交叉点。在第二个交叉点与第三个交叉点之间的D (n)为正值，即系统的分组到达率大于分组离开率，因而在该区域内的状态变化会导致系统的状态增加。或者说，D(n)的方向为正，对第二个交叉点的任何正的扰动将导致系统状态趋于第三个交叉点。从上面的讨论可以看出第一和第三个交叉点是稳定的平衡点，第二个交叉点是不稳定的平衡点。对于第一个交叉点，有较高的通过率，而第三

14、个交叉点的通过率很低。因此，第一个交叉点是希望的稳定平衡点，而第三个交叉点是不希望的稳定平衡点。重传概率qr对稳定性的影响如果qr增加，则重传时延将会减小。如果图中的横坐标n 保持不变，则G (n)=(m-n)qa+nqr的取值将增加，由G (n)对应的G (n)e-G(n)将下降，即曲线向左压缩，第二个交叉点向左移。这样，退出不稳定性的可能性增加，但到达不希望稳定点的可能性增大。 如果qr减小，则重传时延将会增加。如果图中的横坐标n 保持不变，则G (n)取值下降，G(n)e-G(n)的取值增加，即曲线向右扩展，这时仅有一个稳定点。稳定的时隙 ALOHA 协议伪贝叶斯算法 稳定的多址协议是指

15、对于给定的到达率，多址协议可以保证每个分组的平均时延是有限的。或者说对于给定的到达率，系统是稳定的。使系统稳定的到达率的最小上界称为系统的最大稳定通过率。 伪贝叶斯算法背景Psucc近似等于G(n)e-G(n) ，并且当G(n) =1时，获得最大的系统通过量。如果可以动态的改变qr，使G(n)总是处于1，则系统可以一直获得最大的通过量。由于G(n)是n的函数（n为系统中处于重传状态的分组数），因此只要能正确估计n的值，就可以使G(n)=1 。但由于n是未知的值，所以只能通过反馈信息来估计。假定n可以准确估计且 G(n) =1，则根据Poisson到达的近似，可得成功的概率为1/e0.368,

16、空闲的概率为 1/e 0.368，碰撞的概率为1- 2/e0.264。 因此，在调整重传概率qr时，应使碰撞的概率小于空闲的概率。伪贝叶斯算法伪贝叶斯算法（PseudoBayesian Algorithm）是一种稳定的时隙ALOHA算法。核心思想：尽可能的使G(n) =1 ，从而使系统的通过率达到最大值。伪贝叶斯算法伪贝叶斯算法基本思路假定系统有无穷多个节点（假设B），新到达的分组立即被认为是等待重传的分组（这是与普通时隙ALOHA协议的差别），即所有的分组都以相同的方式处理。根据时隙开始点状态（等待重传的节点数）的估计值 确定重传概率 ，并根据当前时隙的传输状态（空闲、成功或碰撞）来估计下一

17、时隙开始点的状态在理想情况下，假定在时隙开始处有n个等待重传的分组，则当前时隙总的传输速率为G(n)=nqr，其成功传输一个分组的概率是根据G(n)=nqr=1的要求，应有qr=1/n伪贝叶斯算法具体步骤(1)估计当前时隙（第k个时隙）开始点的等待重传的节点数 ，则各个节点在第k个时隙发送的概率 （要求qr1）根据第k个时隙的传输结果，估计第k+1个时隙开始点的等待重传的节点数 ： 第k个时隙空闲或成功第k个时隙碰撞伪贝叶斯算法具体步骤(2)式中加入是考虑新的到达，取max表示对 的估计不会小于新到达分组的贡献。若传输成功，则新的估计要从 中减去1。 若碰撞则新的估计要将 增加(e-2)-1。

18、增加(e-2)-1的目的是适当减少重传的概率，若时隙空闲，将 减去1，这样适当的增加重发的概率，以免有太多的空闲时隙。这样可维持系统的真实状态取值n 和估计值 之间的平衡。也就是说，在空闲和碰撞的情况下，平均队长不应该改变。因为在Poisson近似下，空闲的概率为1/e，碰撞的概率为(e-2)/e，则这两种情况下平均队长的改变为-(1/e)+1/(e-2)(e-2)e)=0。伪贝叶斯算法分析该伪贝叶斯算法对任何1/e的到达率都是稳定的。在 n 较大时, 如有，则有qr=1/n, G(n)=1, 其成功的概率=1/e。 根据式(4-20)的定义，有: D(n)=-(1/e), 当 1/e时，有D

19、(n)0, 此时系统是稳定的。当系统状态估计的初值 与实际系统的n 相差较大时，系统也会进入稳态。当 时， 较小, 系统碰撞概率很大，必然导致 迅速增加，从而有 趋于n。当 时, 较大, 系统空闲概率很大, 成功传输概率很高，必然导致 迅速减少, 从而有 趋于n。载波侦听型多址协议 CSMA 是从 ALOHA 协议演变出的一种改进型协议，它采用了附加的硬件装置，每个节点都能够检测（侦听）到信道上有无分组在传输。如果一个节点有分组要传输，它首先检测信道是否空闲，如果信道有其他分组在传输，则该节点可以等到信道空闲后再传输，这样可以减少要发送的分组与正在传输的分组之间的碰撞，提高系统的利用率。CSM

20、ACSMA 协议可细分为几种不同的实现形式：非坚持型（ Non-persistent）CSMA1-坚持型 CSMAp-坚持型 CSMACSMA所谓非坚持型 CSMA 是指当分组到达时，若信道空闲，则立即发送分组；若信道处于忙状态，则分组的发送将被延迟，且节点不再跟踪信道的状态（即节点暂时不检测信道），延迟结束后节点再次检测信道状态，并重复上述过程，如此循环，直到将该分组发送成功为止。 非坚持型 CSMA所谓 1-坚持型 CSMA 是指当分组到达时，若信道空闲，则立即发送分组；若信道处于忙状态，则该节点一直坚持检测信道状态，直至检测到信道空闲后，立即发送该分组。1-坚持型 CSMA所谓 p-坚持

21、型 CSMA 是指当分组到达时，若信道空闲，则立即发送分组；若信道处于忙状态，则该节点一直检测信道的状态，在检测到信道空闲后，以概率 p发送该分组p-坚持型 CSMA检测时延众所周知，由于电信号在介质中的传播时延，在不同的观察点上监测到同一信道的出现或消失的时刻是不相同的。因此，在 CSMA 多址协议中，影响系统性能的主要参数是（信道）载波的检测时延。它包括两部分：发送节点到检测节点的传播时延和物理层检测时延（即检测节点开始检测到检测节点给出信道是忙或闲所需的时间）。设信道速率为C bit/s，分组长度为 L bit ，则归一化的载波侦听（检测）时延为非时隙 CSMA 多址协议 非时隙 CSM

22、A 协议的工作过程如下：当分组到达时，如果信道空闲，则立即发送该分组；如果信道忙，则分组被延迟一段时间后，重新检测信道。如果信道忙或发送时与其它分组碰撞，则该分组变成等待重传的分组。每个等待重传的分组将重复地尝试重传，重传间隔相互独立且服从指数分布。 非时隙 CSMA控制算法描述 1) 若有分组等待发送，则转到第 2）步，否则处于空闲状态，等待分组到达。 2) 监测信道：若信道空闲，启动发送分组，发完返回第 1）步；若信道忙，放弃监测信道，选择一个随机时延的时间长度t 开始延时（此时节点处于退避状态）。 3) 延时结束，转至第 1）步。非时隙 CSMA非时隙 CSMA显然，若分组的传输时间定义

23、为1个时间单位，则即为。非时隙 CSMA非时隙非坚持型 CSMA 多址协议的主要特点是在发送数据前先监测信道，一旦监测到信道忙时，能主动的退避一段时间（暂时放弃监测信道），其系统通过率为 非时隙CSMA性能分析B：忙碌期，某一个分组在信道中开始出现，直到经信道最大传播时延后信道中该分组的数据信号完全消失为止的一段时间区间。I：空闲期，信道中完全没有数据信号的时间区间。U：在一个忙碌期中用于成功传输分组的时间。在系统稳态时， 吞吐量非时隙 CSMA性能分析 是在一个忙碌期中用于成功传输分组的平均时间，即在一个信道周期内某站发送一个分组前的时间内无其他分组到达的概率，由Poisson公式有而空闲周

24、期即平均到达率为G的poisson流的平均间隔，有随机变量Y：在一个不成功的忙碌期开始(0, )区间内的第一个分组到达时刻与最后一个分组到达时刻之间的间隔，有。y=t1+t2+tn 非时隙 CSMA性能分析可得Y的分布函数平均间隔长度B的平均值为因此有时隙 CSMA 多址协议 时隙 CSMA 协议把时间轴分成宽度为的时隙（注意：时隙 ALOHA 中时隙的宽度为一个分组的长度，这里的时隙宽度为载波检测时间）。如果分组到达一个空闲的时隙，它将在下一个空闲时隙开始传输。如果某节点的分组到达时，信道上有分组正在传输，则该节点变为等待重传的节点，它将在当前分组传输结束后的后续空闲时隙中以概率qr进行传输

25、。时隙 CSMA 协议时隙 CSMA 协议时隙 CSMA 协议我们可以用马尔可夫链来分析时隙CSMA协议的性能。设分组长度为1个单位长度，其总的到达过程是速率为的Poisson过程，网络中有无穷多个节点（假设B）。信道状态 0、1、e的反馈时延最大为。又设系统的状态为每一个空闲时隙结束时刻等待重传的分组数 n ，则相继两个状态转移的时间间隔为或1。定义在一个状态转移间隔内n的平均变化数为 Dn = E状态转移间隔内到达的分组数-Psucc =E状态转移间隔-Psucc 这里 E状态转移间隔 =P(时隙空闲)+(1+)（1-P(时隙空闲)）=+1 - P(时隙空闲)=+1- e-(1-qr)n

26、+1- e-e qr n 时隙空闲对应于间隔内无分组到达，以及n个等待重传的节点没有分组发送。时隙 CSMA 协议时隙 CSMA 协议分组成功传输的条件是：在内有一个分组到达且n个等待重传的节点没有分组发送，或在内没有新分组到达但n个等待重传的节点有一个分组传输。因此有：将Psucc和E状态转移间隔代入Dn表达式中，有：时隙 CSMA 协议当qr较小时,有(1-qr)n-1 (1-qr)n e-qrn，进而有 式中，g(n)=+qrn, 它反映的是在一个状态转移间隔内到达分组数和重传分组数之和，即在一个状态转移间隔内试图进行传输的平均分组数。时隙 CSMA 协议显然，使Dn 为负的条件为上式中

27、分子为每个状态转移区间内平均成功传输的分组数，分母为平均状态转移区间的长度，两者相除为单位时间内的平均离开率（即通过率） 典型随机接入多址协议性能曲线稳定的时隙 CSMA 协议 稳定的时隙 CSMA 多址协议假定所有新进入系统的分组立即变成等待重传的分组。设每个状态转移时刻的等待重传分组数为n。n的估计值为 ，在每个空闲时隙结束时，每个等待重传的分组独立地以概率qr发送，qr是 的函数。稳定的时隙CSMA协议的基本出发点是根据n如何确定qr，使得 ，从而使通过量达到最大。给定n的条件下, 在当前时隙开始发送的平均分组数为g(n)=nqr，根据得稳定的时隙 CSMA协议在给定n 的一个估值 的情

28、况下, 其qr应这样选择: 式中取极小值是为了防止 较小时，导致 太大。更新 的规则如下:可以证明, 只要，则该算法是稳定的。 时隙空闲 成功传输 碰撞 有碰撞检测的载波侦听型多址协议（ CSMA/CD ） 前面讨论的 CSMA 协议由于在发送之前进行载波监听，所以减少了冲突的机会。但由于传播时延的存在，冲突还是不可避免的。只要发生冲突，信道就被浪费一段时间。CSMA/CD比CSMA又增加了一个功能，这就是边发送边监听。只要监听到信道上发生了冲突，则冲突的节点就必须停止发送。这样，信道就很快空闲下来，因而提高了信道的利用率。这种边发送边监听的功能称为冲突检测。CSMA/CDCSMA/CD 的工

29、作过程如下：当一个节点有分组到达时，它首先侦听信道，看信道是否空闲。如果信道空闲，则立即发送分组；如果信道忙，则连续侦听信道，直至信道空闲后立即发送分组。该节点在发送分组的同时，监测信道秒，以便确定本节点的分组是否与其它节点发生碰撞。如果没有发生碰撞，则该节点会无冲突地占用该总线，直至传输结束。如果发生碰撞，则该节点停止发送，随机时延一段时间后重复上述过程。（在实际应用时，发送节点在检测到碰撞以后，还要产生一个阻塞信号来阻塞信道，以防止其它节点没有检测到碰撞而继续传输。）CSMA/CD总的来说，CSMA/CD 接入协议比 CSMA 多址接入协议的控制规则增加了如下三点： “边发边听 ” “强化

30、干扰 ” “碰撞检测窗口 ”CSMA/CD任一发送节点在发送数据帧期间要保持侦听信道的碰撞情况。一旦检测到碰撞发生，应立即中止发送，而不管目前正在发送的帧是否发完。保证尽快确知碰撞发生和尽早关闭碰撞发生后的无用发送，这有利于提高信道利用率边发边听发送节点在检测到碰撞并停止发送后，立即改为发送一小段“强化干扰信号”，以增强碰撞检测效果。可以提高网络中所有节点对于碰撞检测的可信度，保证了分布式控制的一致性强化干扰任一发送节点若能完整的发完一个数据帧，则停顿一段时间（两倍的最大传播时延）并监听信道情况。若在此期间未发生碰撞，则可认为该数据帧已经发送成功。此时间区间称为“碰撞检测窗口”。有利于提高一个

31、数据帧发送成功的可信度。如果接收节点在此窗口内发送应答帧（ACK 或NAK）的话，则可保证应答传输成功。碰撞检测窗口为了简化分析，首先假定一个局域网（LAN）工作在时隙状态下，以每个分组传输的结束时刻作为参考点，将空闲信道分为若干个微时隙，用分组长度进行归一化的微时隙的宽度为。所有节点都同步在微时隙的开始点进行传输。如果在一个微时隙开始点有分组发送，则经过一个微时隙后，所有节点都检测到在该微时隙上是否发生碰撞。如果发生了碰撞，则立即停止发送。 CSMA/CD 协议的性能这里仍然用马尔可夫链的方法分析。分析的方法与时隙 CSMA 协议相同。设网络中有无穷多个节点，每一个空闲时隙结束时的等待重传的分组数为 n ，每个等待重传的节点在每一个空闲时隙后发送的概率为 qr。 CSMA/CD 协议的性能C