2.3 基于控制分组握手的访问控制协议

2.3.1 MACA协议

具碰撞回避的多址访问（Multiple Access with Collision Avoidance，MACA）协议使用控制分组握手诊断来减轻隐含终端干扰和使显现终端个数最少。MACA协议采用两种固定长度的短分组，即请求发送（Request to Send，RTS）和允许发送（Clear to Send，CTS）。节点A需要对节点B发送的时候，首先给节点B发送一个RTS分组，RTS分组包含发送数据的长度。节点B若接收到RTS分组、并且当前不在退避之中，则立即应答CTS分组，CTS分组也包含发送数据的长度。节点A接收到CTS分组后，立即发送其数据。旁听到RTS分组的任何节点推迟其全部发送，直到有关CTS分组完成为止（包括CTS分组发送时间和接收节点从RTS分组接收方式转换到CTS分组发送方式所需时间）。旁听到CTS分组的任何节点推迟其发送，推迟时间长度等于预定数据发送所需时间（其中包括RTS分组和CTS分组）。

采用这种算法，任一节点旁听到RTS分组后将其发送推迟足够长时间，这样发送节点A才能够正确接收回送的CTS分组。旁听到CTS分组后的所有节点避开与节点A发送来的数据碰撞。因为CTS是从接收节点发出的，所以对称性确保能够与节点A发送来的数据碰撞的每个节点均处在CTS分组的覆盖范围内（区域内其他发送导致CTS分组可能不会被其覆盖范围内的所有节点所接收到）。注意：能够旁听到RTS分组但是旁听不到CTS分组的节点处在发送节点的传输覆盖范围内，但是不在接收节点的传输覆盖范围内，可以在发送完CTS分组之后开始发送，不会引起碰撞，这是因为这些节点不在接收节点（不会碰撞数据发送）的传输覆盖范围内。

在图2-1所示的隐含终端情况下，节点C接收不到节点A发送的RTS分组、但是能够接收到节点B发送的CTS分组，因此在节点A发送数据期间停止发送。在图2-2所示的显现终端情况下，节点C接收不到节点A发送的CTS分组、但是能够接收到节点B发送的RTS分组，因此可以在节点B发送数据期间自由发送。这正是所需要的操作。

因此，与载波侦听协议对比之下，RTS-CTS分组交互能够使邻近节点避免在接收节点（注意：不是在发送节点）发生碰撞。RTS分组的作用是得到接收节点的CTS分组，其他节点接收到CTS分组表示这些节点处在CTS分组的传输覆盖范围内、因此可能与随后的发送发生碰撞。这主要依赖对称性：如果一个节点不能接收到节点B发送的CTS分组，那就假定该节点不会对节点B的接收产生碰撞。

如果节点A接收不到节点B回送的CTS分组，那么节点A最终发生超时（即停止等待CTS分组），假定发生了碰撞，然后安排重传RTS分组。MACA协议采用二进制指数退避算法选择重传时间。

1.MACA协议的规则

控制规则和退避规则控制载波捕捉和数据发送。延迟规则控制碰撞回避。假设：节点A需要给节点B发送数据分组，节点C只能接收到节点A的发送，节点D只能接收到节点B的发送。

MACA协议的运行分成5种状态：空闲状态（IDLE）、竞争状态（CONTEND）、CTS分组等待状态（Wait for CTS，WFCTS）、数据等待状态（Wait for Data，WFData）、静默状态（QUIET）。MACA协议运行过程可以处在其中任何一种状态。控制状态转移的控制规则如下：

（1）当节点A处在空闲状态、并且需要给节点B发送数据分组的时候，节点A设置一个随机定时器，进入竞争状态。

（2）当节点B处在空闲状态、并且接收到节点A发送的RTS分组的时候，节点B给节点A回送一个CTS分组，CTS分组包含节点A和B的身份识别码ID、以及所允许发送的字节数。节点B设置一个定时器，进入数据等待状态（WFData）。

（3）当节点A处在CTS分组等待状态（WFCTS）、并且接收到节点B发送的CTS分组的时候，节点A将随机定时器清零，给节点B发送一个数据分组，然后将状态复位到空闲状态。

（4）当节点B处在WFData状态、并且接收到节点A发送的一个数据分组的时候，节点B清零定时器，然后将状态复位到空闲状态。

（5）节点A若处在竞争状态下接收到RTS分组，则清零定时器，给相应发送节点回送CTS分组，进入数据等待状态。

MACA协议的延迟规则如下：

（1）当节点C接收到节点A发送给节点B的RTS分组的时候，节点C从其当前状态进入静默状态，设置一个定时器，定时时间足够让节点A接收到节点B回送的CTS分组。

（2）当节点D接收到节点B回送给节点A的CTS分组的时候，节点D从其当前状态进入静默状态，设置一个定时器，定时时间足够让节点B接收到节点A发送的数据分组。

MACA协议的超时规则如下：

（1）当节点A处在竞争状态、并且定时器定时结束的时候，节点A发送一个RTS分组，RTS分组包含节点A和B的身份识别码ID，以及请求发送的字节数。然后节点A设置一个定时器，进入WFCTS状态。

（2）当定时器定时结束的时候，节点从任何其他状态进入空闲状态。

优先级按照延迟规则、控制规则、超时规则顺序依次降低。

2.举例

图2-5表示MACA协议的操作过程。节点B希望发送分组给节点A。节点B首先发送一个RTS控制分组，RTS分组到达节点A、C和D[见图2-5（a）]。然后节点A通过发送一个CTS控制分组来做出响应[见图2-5（b）]。此时，节点B可以自由地发送其数据分组[见图2-5（c）]。

2.3.2 MACAW协议

MACAW协议是MACA协议的改进版，增加了两个新的控制分组RRTS和DS。MACAW协议通过以下措施强化MACA协议：应用载波侦听来避免RTS控制分组之间的碰撞，使用正确应答ACK分组来辅助丢失分组的迅速恢复。为了防止正确应答ACK分组的碰撞，源节点发送一个数据发送（Data Sending，DS）控制分组来提醒显现节点正确应答ACK分组即将发送。

1.退避算法

MACA协议采用二进制指数退避（Binary Exponential Backoff，BEB）算法。BEB算法是在每次碰撞之后将退避时间加倍，在每次成功完成RTS-CTS分组交付之后采用最小退避时间。这种方法不能提供网络中的准确公平等级。例如，如图2-6（a）所示，节点P1和P2相互处在对方的传输覆盖范围内，节点B处在节点P1和P2的传输覆盖范围内。节点P1和节点P2各自产生足够多的UDP分组，完全占用信道的容量。实验结果如表2-2所示。采用BEB退避算法的时候，最后只有一个节点（节点P1）占用信道发送UDP分组，而另一个节点（节点P2）则被完全退避（即退避计数器设在BOmax）。在类似于图2-6（a）所示的网络拓扑（多个节点向同一个节点发送）中，如果所有发送节点的退避计数器均较大，但是其中只有一个发送节点的退避计数器相对较大，那么每次碰撞后退避计数器较小的节点很可能首先重发，赢得碰撞，因此将其退避计数器设为BOmin。每次碰撞后重复发生这种现象，退避节点变得越来越难以赢得碰撞。如果没有最大退避，那么最终只有一个节点始终占用信道。一个节点的退避计数器比其他节点小得多，总是产生上述不公平信道访问，原本指望这个最小退避计数器应该反映相应节点周围的竞争程度，对于所有节点都是这样。每个节点根据自己在网络中遇到的情况独自进行自己的拥塞计算，不共享拥塞信息，导致不同节点对拥塞程度具有不同看法。

为了纠正这种信道的不公平访问，对BEB算法加以修改：在分组头中增加一个退避计数器域，用于记录退避计数器的当前计数值。一个节点只要接收到一个分组，就将该分组分组头中退避计数器域中的数值复制作为自己的退避计数器计数值。因此，在一个相邻区域内，每当成功完成一次发送后，相邻区域内的所有节点具有相同的退避计数值。采用这种算法得到的实验结果见表2-2的右边一列，两个UDP分组流的吞吐量非常接近。因此，媒介访问协议直接分发拥塞信息能够公平分配资源。

BEB退避算法调整退避时间很迅速：每当检测到一次碰撞就立即增大退避时间和进入退避，每当成功完成一次发送就立即将退避计数器设为BOmin。因此，BEB退避算法的退避计数器变化大。比如，在图2-6（a）中，每当成功完成一次发送后所有节点具有相同的最小退避时间值，然后必须重复一轮竞争来增大退避时间。

为了防止BEB退避时间变化大的问题，采用一种较平缓的调整算法：每当发生一次碰撞，将退避间隔时间调整为原退避间隔时间的1.5倍，Finc(x)=MIN[1.5x，BOmax]；每当成功完成一次发送，将退避间隔时间调整为原退避间隔时间减一，Finc(x)=MAX[x−1，BOmin]。这种退避时间算法叫做倍数递增和线性递减（Multiplicative Increase and Linear Decrease，MILD）算法。在竞争激烈的时候，MILD算法仍然相当快地增大退避时间。但是，每当成功完成一次发送后，MILD算法不会将退避时间复位到BOmin，因此不需要重复一次碰撞来增大退避时间。如图2-6（b）所示，6个节点P1、P2、P3、P4、P5、P6均在给一个公共节点B发送UDP数据分组，每个UDP分组流的速率是每秒32个UDP分组。采用BEB复制算法和MILD算法在图2-6（b）所示网络中作对比实验，得到表2-3所示的实验结果。MILD算法的吞吐量明显高于BEB复制算法。

由于多址访问的随机性，碰撞是不可避免的。MACAW协议采用退避算法，将RTS分组发送延迟随机个时隙，以便降低碰撞概率和解决发生的碰撞。根据退避计数器计算随机时延，因此，退避时间值应该反映媒介的竞争程度。

MACAW协议的目标是实现高总吞吐量和各个流公平共享吞吐量，其退避算法对此起着关键作用。对于高效退避算法，退避计数器必须精确反映媒介的竞争程度。前面已经介绍了对退避算法的改进，将BEB算法改为MILD算法，以便对竞争程度实现较为平稳的估计。对于公平的退避算法，所有竞争节点应该使用同一个退避计数器。前面介绍了一种退避拷贝机制，用于确保所有竞争节点使用同一个退避计数器。

2.基本的消息交换

1）ACK分组

许多在移动装置上的应用（比如，电子邮件）都要求数据的可靠交付。在传输层，采用TCP给应用提供可靠交付。在MACA协议中，当数据分组遇到碰撞或者受到噪声破坏的时候，传输错误必须由传输层来恢复。这必需相当长的等待时间，因为TCP协议实现中采用的最小超时时间（比如0.5s）同时用于本地数据发送和远程数据发送。

但是，采用链路层恢复却能够快得多，因为超时周期可以调整，以便适应传输媒介最短时间。因此，对基本的RTS-CTS-DATA消息交换序列进行修改，使其包含一个应答分组ACK，接收节点接收到发送节点发送的一个数据分组后立即给发送节点回送一个ACK分组。如果发送节点没有接收到ACK分组，那么安排数据分组重传。如果数据分组实际上已经被接收节点正确接收到，但是ACK分组却没有被发送节点接收到，那么当发送节点发送一个用于数据分组重传的RTS分组的时候，接收节点可以用相应ACK分组响应、而不用CTS分组响应。发送节点发送完一个RTS分组后没有在超时时间内接收到CTS分组或者ACK分组，则增大其退避时间；发送节点接收到ACK分组则减小其退避时间。如果RTS-CTS分组交付成功完成，但是没有接收到ACK分组，那么退避时间保持不变。

在两个节点点对点的网络中实验ACK分组的作用效能，信道上存在断断续续的噪声。按照给定概率模拟噪声，每个分组（不论大小如何）不会被其目的节点毫无误码的接收到。表2-4给出TCP吞吐量实验结果。对于RTS-CTS-DATA消息交换序列，吞吐量随着噪声的增大而急剧下降，这是因为TCP层慢恢复的缘故。当采用ACK分组后，TCP吞吐量的下降要平稳得多。ACK分组带来的开销大约等于9%（噪声条件下每秒36.76个分组，无噪声条件下每秒40.41个分组）；若分组丢失率等于1×10−3，两种算法在相同条件下必然得到完全相同的结果。假定断断续续噪声很可能出现，并且对网络吞吐量有不利影响，那么应该采用RTS-CTS-DATA-ACK消息交换序列进行所有的可靠数据传输。

2）DS分组

在分析显现终端的配置结构中（见图2-1），即使节点C处在发送节点B的传输覆盖范围内、但是处在接收节点A的传输覆盖范围之外，节点C也应该自由进行发送，接收节点A是跟节点C发送有关系的唯一节点。但是，只有当节点C能够接收到CTS分组的时候，节点C的发送才具有有益作用。当节点B正在发送的时候，节点C不能接收到任何应答，因此启动发送没有任何有益作用。只有当发送节点B不必接收CTS分组之后的分组的时候，节点C的发送才不会对发送节点B产生不利影响。而且，当节点C初始化发送、但是却没有得到任何响应的时候，迅速增大节点C的退避时间。采用单向发送，唯一有关的碰撞在接收节点；但是，采用双向的RTS-CTS-DATA消息交互，碰撞跟发送节点和接收节点均有关。

因此，当节点B正在发送数据的时候，节点C应该推迟其发送。因为节点C只能接收到RTS分组、但是接收不到CTS分组，所以节点C无法知道RTS-CTS分组交互是否成功，所以也就不知道节点B是否正在发送数据。

有两种方法解决这个问题。可以采用载波侦听避免发送无用的RTS分组。一个节点在没有检测到载波后的一个时隙时间内不能进行发送（如果需要发送，则必须推迟发送），让空中信道保持一个时隙的空闲是为了确保显现终端不会干扰回送的ACK分组。这实质上就是CSMA/CA协议。另外一种解决方法（MACAW协议采用的方法）不需要载波侦听硬件。一个节点在发送一个数据分组之前，首先发送一个30B的DS分组。每个节点接收到DS分组后就知道RTS-CTS分组交互已经成功完成、并且即将发送一个数据分组，推迟其发送，直到ACK分组传输时隙结束之后为止。

增加一个DS分组会带来什么效果？见图2-6（c）。节点P1是节点P2发送给B2的分组流（S2）的显现终端，节点P2是节点P1发送给B1的分组流（S1）的显现终端。表2-5给出图2-6（c）所示网络仿真实验得到的吞吐量。假定不采用DS分组，有一个远端节点（表2-5中的节点P2）首次竞争失败，然后继续进行无效重传。关键的原因在于没有采用DS分组，竞争失败节点（P2）无法知道下一次竞争（即，ACK分组之后，下一个RTS分组之前的时间）何时开始，因此不能完成对信道的有效访问。由于数据分组比控制分组大许多，所以一个正在进行中的通信流占用绝大部分时间进行数据发送。因此，竞争失败节点（P2）若必须随机选择重传次数，则常常在数据分组发送期间结束其RTS分组发送，而这种发送总是产生分组碰撞。因此，为了有效完成RTS-CTS分组交互，远端节点必须在竞争期间发送其RTS分组，这就要求知道数据发送何时开始、何时结束。对“同步”信息的需求非常关键；在图2-6（c）中，同步信息由DS分组提供（DS分组将有关随后是否有数据分组及其长度告诉其他节点）。

3）RRTS分组

考虑如图2-6（d）所示的网络配置，这是一种对称配置，除了流的方向相反之外，图2-6（d）的网络配置与图2-6（c）完全相同。每个数据流均能够完全占用信道。表2-6 给出图2-6（d）的实验结果（吞吐量），第二列表示采用RTS-CTS-DS-DATA-ACK消息交换序列的吞吐量。B1-P1流（S1）几乎不能获得信道的访问，而B2-P2流（S2）接受所请求的全部吞吐量。只有一个流（S2）初次竞争成功。之后，由于数据分组相对大于控制分组，所以节点B1大部分时间用于初始化数据发送而发送RTS分组，接收节点P1根据节点B2对节点P2的数据发送而一再推迟自己的发送，因而不能响应节点B1的RTS分组。节点B1成功初始化数据发送的唯一方法是其发送的RTS分组在节点B2完成一个数据分组发送与节点P2完成下一个CTS分组应答之间的短暂空闲时间内成功到达接收节点P1。

采用RTS-CTS-DS-DATA-ACK消息交换序列的关键问题仍然是缺乏同步信息。节点B1在非常短的时间内与节点B2竞争，但是却无法知道这个短竞争周期的起始点和结束点。DS分组不能解决这个问题，因为节点B1接收不到B2-P2流的消息交换，B2接收不到B1-P1流的消息交换。采用RTS-CTS-DS-DATA-ACK消息交换序列的第二个问题是节点B1接收不到节点P1的响应而不断增大自己的退避时间。

解决上述两个问题的方法是让节点P1代表节点B1进行竞争。一个节点（P1）只要接收到发送给自己的RTS分组、但是却不能对其作出响应（由于退避的缘故）的时候，则在下一个竞争周期内进行竞争，给RTS分组发送节点（B1）发送一个RTS分组的请求分组（Request for Request to Send，RRTS）。如果在退避期间接收到同一个发送节点的多个RTS分组，那么只需响应接收到的第一个RTS分组。节点（B1）接收到RRTS分组后立即用一个RTS分组响应，然后开始正常的消息交换。旁听到RRTS分组的节点推迟两个时隙时间，这个时间足够旁听一个RTS-CTS分组交付是否成功完成。表2-6第三列给出采用RRTS分组后的吞吐量。从表2-6中可以看到，RRTS分组能够使各个流公平访问传输信道。

但是，RRTS分组并没有解决其中的所有问题。考虑如图2-6（e）所示的网络配置。表2-7给出图2-6（e）所示网络在采用RRTS分组的吞吐量实验结果。B1-P1流被完全拒绝访问信道，而B2-P2流获得全部信道利用率。这是因为节点B1大部分时间在初始化数据发送而发送RTS分组，节点P1由于节点P2的发送而接收不到节点B1发送的RTS分组（两个发送在P1上发生碰撞）。节点B1能够成功初始化数据发送的唯一时间机会是其发送的RTS分组在节点P2完成一个数据分组发送后与发送下一个RTS分组之间的极短暂空闲时间内成功到达接收节点P1。其原因仍然是缺乏同步信息。节点B1无法知道短暂竞争周期的起始点。RRTS分组与此无关，因为节点P1接收不到输入的RTS分组。MACAW协议没有解决这个问题。

3.MACAW协议的规则

1）消息交换规则与控制规则

按照控制规则、延迟规则、超时规则描述MACAW协议。

MACAW协议的运行分成8种状态：空闲状态（IDLE）、竞争状态（CONTEND）、CTS分组等待状态（Wait for CTS，WFCTS）、竞争等待状态（Wait for Contend，WFContend）、数据发送分组等待状态（Wait for DataSend，WFDS）、数据等待状态（Wait for Data，WFData）、ACK等待状态（Wait for ACK，WFACK）、静默状态（QUIET）。

MACAW协议的控制规则如下：

（1）当节点A处在空闲状态、并且需要给节点B发送数据分组的时候，节点A设置一个随机定时器，进入竞争状态。

（2）当节点B处在空闲状态、并且接收到节点A发送的RTS分组的时候，节点B给节点A回送一个CTS分组，然后设置一个定时器，进入数据发送分组等待状态（WFDS）。

（3）当节点A处在CTS分组等待状态、并且接收到节点B发送的CTS分组的时候，节点A将随机定时器清零，依次给节点B发送一个DS分组和一个数据分组，然后进入ACK等待状态（WFACK），设置一个定时器。

（4）当节点B处在WFDS状态、并且接收到节点A发送的DS分组的时候，节点B进入数据等待状态（WFData），设置一个定时器。

（5）当节点B处在WFData状态、并且接收到节点A发送的一个数据分组的时候，节点B清零定时器，给节点A回送一个ACK分组，然后进入空闲状态。

（6）当节点A处在WFACK状态、并且接收到节点B发送的ACK分组的时候，节点A将状态复位到空闲状态，清零定时器。

（7）当节点B处在空闲状态、并且接收到一个RTS分组（这个RTS分组用于发送最近已经应答过的一个数据分组）的时候，节点B发送ACK分组、而不发送CTS分组。

（8）节点A若在竞争状态下接收到一个RTS分组，则给相应发送节点回送CTS分组，进入WFDS状态，设置定时器。

（9）节点C若在静默状态下接收到一个RTS分组，则进入竞争等待状态（WFContend）。

（10）如果一个节点在空闲状态下接收到一个RRTS分组，那么该节点给相应发送节点回送RTS分组，进入WFCTS状态，设置定时器。

MACAW协议的延迟规则如下：

（1）当节点C接收到节点A发送给节点B的RTS分组的时候，节点C从其当前状态进入静默状态，设置一个定时器，定时时间足够让节点A接收到节点B回送的CTS分组。

（2）当节点C接收到节点A发送给节点B的DS分组的时候，节点C从其当前状态进入静默状态，设置一个定时器，定时时间足够让节点A发送一个数据分组和接收到节点B回送的ACK分组。

（3）当节点D接收到节点B回送给节点A的CTS分组的时候，节点D从其当前状态进入静默状态，设置一个定时器，定时时间足够让节点B接收到节点A发送的数据分组。

（4）当节点B接收到节点D发送的RRTS分组的时候，节点B从其当前状态进入静默状态，设置一个定时器，定时时间足够完成一个RTS-CTS分组交互。

MACAW协议的超时规则如下：

（1）当一个节点处在WFContend状态下、并且定时器定时结束的时候，该节点设置一个随机定时器，进入竞争状态（CONTEND）。

（2）当一个节点处在CONTEND状态下、并且定时器定时结束的时候，该节点或者可以发送一个RTS分组、执行发送节点初始化的数据发送（节点A），或者可以发送一个RRTS分组、执行接收节点初始化的数据发送（节点D），具体选择取决于该节点是从空闲状态进入CONTEND状态、还是从WFContend状态进入CONTEND状态。

对于发送节点初始化的数据发送，节点A发送一个RTS分组，RTS分组包含节点A和B的身份识别码ID、以及请求发送的字节数。然后节点A进入WFCTS状态，设置一个定时器。对于接收节点初始化的数据发送，节点D发送一个RRTS分组，然后进入空闲状态。

（3）据上所述，当定时器定时结束的时候，节点进入空闲状态，清零定时器。

2）退避规则与复制规则

每个节点维护下列变量：

（1）my_backoff：本节点的退避时间值。

（2）对于每个远端节点的每个状态：

① local_backoff：远端节点估计的本节点的退避时间值。

② remote_backoff：所估计的远端节点的退避时间值。

③ exchange_seq_number(ESN)：与远端节点交换分组时使用的序列号。

④ retry_count：重传次数。

当一个远端节点P接收到节点Q对节点R发送的一个分组（不是RTS分组）的时候，节点P更新其有关节点Q和R的竞争程度估计，用该分组中的local_backoff和remote_backoff进行刷新。此外，假定节点Q处在节点P的附近，因此节点Q的退避时间大致反映了相邻区域内的竞争程度，所以节点P将节点Q的退避时间值作为自己的退避时间值。忽略RTS分组是因为RTS分组携带的退避时间值可能不正确。更精确的描述如下：

            packet(local_backoff,remote_backoff,ESN)
                if packet == RTS,ignore
                else
                    Q’s backoff = local_backoff；
                if(remote_backoff != I_DONT_KNOW)
                    R’s backoff = remote_backoff；
                my_backoff = local_backoff；

当远端节点P接收到远端节点Q发送给自己的一个分组的时候，如果exchange_seq_number已经增大，那么或者这个分组正在初始化一个新的发送，或者已经成功完成一个握手。在其中任何一种情况下，该分组携带的退避时间值应该是正确的。因此，节点P更新节点Q和自己的退避时间值，将ESN增大，复位retry_count。节点P的local_backoff是一个在试图与节点Q交互的时候临时使用的变量；一旦成功完成一次握手，临时变量local_backoff的取值与节点P的my_backoff同步。

另一方面，如果远端节点P接收到的这个分组是一个旧分组的重传分组，那么节点P假定在节点Q发生了碰撞，因而增大节点Q的退避时间。由于节点P和Q的退避时间总值应该相等、与在哪个节点上发生了碰撞无关，所以节点P将自己的退避时间值更新为节点P的退避时间总值与节点P估计的节点Q的退避时间之差。

            packet(local_backoff,remote_backoff,ESN)
                if (ESN > ESN for Q)
                    Q’S backoff = local_backoff；
                    if(remote_backoff != I_DONT_KNOW)
                        P’s local_backoff = remote_backoff；
                        my_backoff = remote_backoff；
                    else
                        P’s local_backoff = my_backoff；
                P’s ESN for Q = ESN+1；
                    P’s retry_count with Q = 1；
                else /*该分组是一个重传分组*/
                    Q’s backoff = local_backoff + retry_count * ALPHA；
                    if(remote_backoff != I_DONT_KNOW)
                        P’s local_backoff = (local_backoff+remote_backoff) - Q’s backoff；
                    else
                        P’s local_backoff = my_backoff；
                    retry_count++；

当远端节点P给节点Q发送一个分组的时候，节点P将该分组中的参数local_backoff、remote_backoff、ESN设置如下：

            if(packet = RTS)/*或者应该在一个新分组开始的时候*/
                local_backoff(used in communicating with Q) = my_backoff；
            remote_backoff = Q’s backoff(or I_DONT_KNOW)；
            local_backoff = local_backoff used with Q；
            send packet with local_backoff,remote_backoff,ESN；

当远端节点P给节点Q发送一个分组出现超时的时候：

            Q’s backoff += retry_count * ALPHA；
            if reached max_retry_count，
                P’s local_backoff used with Q = MAX_BACKOFF；
                Q’s backoff = I_DONT_KNOW；

2.3.3 FAMA协议

信道获取多址访问（Floor Acquisition Multiple Access，FAMA）协议要求需要发送一个或者多个分组的节点在发送之前首先获取信道。获取信道的方法是采用RTS-CTS控制分组交互，RTS、CTS、数据分组均在同一个信道上传输。尽管可能存在多个RTS分组和CTS分组碰撞的问题，但是数据分组发送总是无碰撞的。

一个节点（源节点）为了获取信道，采取载波侦听或者分组侦听发送一个RTS分组：前者相当于采用CSMA协议发送RTS分组，后者相当于使用ALOHA协议发送RTS分组。接收节点成功接收到RTS分组后，给源节点回送一个CTS分组。源节点成功接收到RTS分组后，知道自己已经获得到达接收节点的信道。获得信道后，信道占有节点或者其任何接收节点就能够在该信道上无碰撞地发送数据分组和应答。在信道占有节点及其通信节点之间，可以在FAMA协议上面实现任何可靠链路控制协议，其实现方法是：强迫没有获得信道的节点等待一段预先确定的最小时间（至少等于最大传播时延的两倍），然后才能够竞争获取信道。

为了确保在互为隐含的竞争发送节点（已经提出了信道申请，即发送了一个RTS分组）之间强迫执行信道获取操作成功，保证接收节点回送的CTS分组持续足够长时间（或者重复次数足够多），以便阻止任何没有接收到RTS分组的隐含发送节点得到应答。

一个节点有数据需要发送、但是却没有获得信道或者检测出信道正被其他节点所占用时，必须重新安排其信道获取操作。此时，可以采用不同的持续策略或者退避策略。由于非持续CSMA协议在重载荷下的吞吐量比p-持续CSMA协议高得多，且在轻载荷下的吞吐量只是稍低于后者，所以在FAM A中考虑使用非持续协议。

1.FAMA-NCS规程

非持续载波侦听信道获取（争夺）多址访问协议（Floor Acquisition Multiple Access with Non-persistent Carrier Sensing，FAMA-NCS）是FAMA协议的一个衍生版，综合了非持续载波侦听机制和RTS-CTS分组交互机制。FAMA-NCS是基于RTS-CTS分组交互的信道访问控制协议，特别适用于Ad Hoc网络。FAMA-NCS协议类似于IEEE 802.11 MAC协议。FAMA-NCS的目的是有数据需要发送的节点在发送数据分组之前必须获取接收节点附近的信道控制权，以确保数据分组不会在接收节点碰撞任何其他分组。

在FAMA-NCS协议中，一个CTS分组的时间长度大于一个RTS分组时间长度、最大信道往返时间、发送到接收的转换时间、处理时间的之和；而为了避免一个节点在另一个节点已经开始接收RTS分组之前就已经完全旁听到这个RTS分组，要求一个RTS分组的时间长度大于最大信道传播时延、发送到接收的转换时间、处理时延之和。CTS分组与RTS分组的这种大小关系表明在信道上CTS分组优于RTS分组，起支配作用。一旦一个节点已经开始发送CTS分组，那么该节点传输覆盖范围内同时（即在开始发送该CTS分组之后的一个信道传播时延内）发送RTS分组的任何其他节点将至少接收到该CTS分组（起到干扰信号的作用）的一部分，然后退出发送方式，进行退避，因而随后发送的数据分组不会遇到碰撞。主导CTS分组起到忙音的作用，提供干扰信号阻止CTS分组发送节点传输覆盖范围内可能的干扰发射机进行发送。

图2-7所示是CTS分组主导协议操作的一个详细例子。节点B正在发送CTS分组，而节点A试图发送RTS分组且获得信道。由于节点A和B均使用载波侦听，所以节点A必须在节点B开始发送其CTS分组后的τ 秒内发送其RTS分组；否则，其中一个节点将检测到载波而进行退避。图2-7（a）表示节点B发送的CTS分组正好在节点A开始发送其RTS分组的时候到达节点A。由于节点B发送的CTS分组大于RTS分组与发送至接收转换时间之和，所以节点A能够听到信号重叠产生的噪声（即干扰），然后进行退避。图2-7（b）表示另外一种情况：节点A可以在节点B开始发送其CTS分组前的τ 秒内发送其RTS分组；否则（即节点A提前发送其RTS分组的时间更早（大于τ 秒）），节点A将干扰发送给节点B的RTS分组，节点B接收不到RTS分组、因而不发送CTS分组。在这种情况下，节点B发送的CTS分组将在节点A发送完RTS分组后的2τ秒到达节点A。同样由于节点B发送的CTS分组大于RTS分组与发送至接收转换时间之和，所以节点A能够接收到CTS分组的尾部（一片噪声），然后进行退避。

图2-8所示的是FAMA-NCS协议规范的详细说明。FAMA-NCS协议规范假定电台转换时间（发送至接收转换时间，接收至发送转换时间）大于任意两个节点（相互处在对方的传输覆盖范围内）之间的最大来回传输时间。

一个刚被初始化的节点必须等待一段时间，该时间长度等于在信道上发送一个最大数据分组所需时间与该信道上一个最大来回传输时间之和。从而允许跟数据分组接收过程有关的任何相邻节点成功完成该数据分组的接收。初始化时间保证相邻节点能够知道正在进行的本地传输。如果在初始化期间没有检测到载波，那么相邻节点转移到被动（PASSIVE）状态；否则（即检测到载波），相邻节点转移到远端（REMOTE）状态。如果一个节点被适当初始化（即，没有分组需要发送，信道侦听为空闲），那么该节点只能处在PASSIVE状态。在所有其他状态，节点必须对信道接收一段足够长时间，以便让有关相邻节点在转移到PASSIVE状态之前完成数据的接收。

一个节点在PASSIVE状态下而检测到信道上的载波后转移到REMOTE状态；或者一个节点在PASSIVE状态下接收到一个需要发送的分组后发送一个RTS分组，然后转移到RTS状态。发送节点等待足够长的时间，以便目的节点应答CTS分组。如果在允许的超时时间内没有接收到CTS分组，那么发送节点转移到退避（BACKOFF）状态。如果发送节点发送完RTS分组后接收到信道噪声，那么假定与相邻节点的主CTS分组发生了碰撞，等待足够长的时间以便接收最大长度数据分组。否则，发送节点接收到CTS分组后发送其数据分组。由于CTS分组可能在发送节点被破坏，所以目的节点一旦发送完CTS分组后，只需要等待一个最大来回传输时间，侦听源节点开始发送数据分组。如果源节点没有开始发送数据分组，那么目的节点或者转移到BACKOFF状态（假定传输被搁置），或者转移到PASSIVE状态。

在BACKOFF状态，如果在整个退避期间没有检测到载波，那么节点发送一个RTS分组，然后转移到RTS状态。否则，即在退避期间检测到载波，节点转移到REMOTE状态。

对于处在REMOTE状态下的节点，FAMA-NCS协议根据信道旁听结果强迫各个被动节点（即处于PASSIVE状态的节点）等待长度不等的时间（这些被动节点与当前发送周期没有直接关系）。任何一个被动节点检测到载波后转移到REMOTE状态，在信道空闲后按照如下方法确定等待周期：

（1）该节点旁听到发送给另一个节点的RTS分组后，必须等待足够长的时间，以便目的节点回送CTS分组和发送节点接收该CTS分组、以及发送节点开始发送数据分组。

（2）该节点接收到另一个节点发送的CTS分组后，必须等待足够长的时间，以便允许这个节点接收其数据分组。

（3）旁听到一个数据分组后，等待时间为强迫性FAMA等待周期。

（4）接收到信道噪声（控制分组碰撞）后，等待周期必须足够长，以便允许其他节点有时间接收一个最大数据分组。

当所有节点处在PASSIVE状态或者BACKOFF状态的时候，信道变成空闲状态。接收到新的分组、以及重传已经被退避的分组重新驱动信道访问。

为了提高信道效率，一个节点成功获得信道后可以连续发送多个数据分组，连续发送的分组个数受上限限制。为了在隐含终端环境中能够成功连续发送多个分组，目的节点必须通知其相邻节点自己有多个数据分组即将传输到达，要求相邻节点继续推迟其发送。FAMA-NCS协议采用如下一种简单握手机制来支持连续发送多个数据分组：

在数据分组分组头中设置一个“MORE”比特标志：“1”表示连续发送多个数据分组，“0”表示发送一个数据分组。如果发送节点需要连续发送多个数据分组，那么发送节点将数据分组分组头中的MORE标志置“1”。目的节点接收到该数据分组，知道其MORE标志置“1”，因而在一个最大分组长度之后回送一个CTS分组，最大分组长度包括所收到数据分组的发送时间。CTS分组用于通知目的节点的所有相邻节点：它们可能干扰下一个数据分组，因而必须继续推迟其发送。此外，REMOTE状态下的节点在旁听到一个MORE标志置“1”的数据分组后必须延长其等待周期，以便有额外的时间让发送节点接收目的节点回送的CTS分组，同时CTS分组还起到通知发送节点的作用：目的节点能够接收下一个数据分组。

2.FAMA-NPS规程

FAMA协议的另一个版本是非持续性分组侦听FAMA-NPS协议（Non-Persistent Packet Sensing）。FAMA-NPS协议没有采用载波侦听，基本上是MACA协议的改进版，详情见图2-9。

若在隐含终端条件下采用分组侦听的FAMA协议，则CTS分组必须发送多次，这就意味着只是在全连通网络中才能够有效支持信道获取。而FAMA-NPS协议假定用于全连通网络、一个CTS分组只发送一次。RTS分组和CTS分组的持续时间相同，大于一个最大来回时间。

一个节点需要发送一个数据分组、且又不要求接收一个CTS分组或者一个数据分组的时候首先给目的节点发送一个RTS分组。一个节点正在处理一个正确RTS分组的时候，推迟其任何RTS分组的发送，推迟时间由正被处理的这个RTS分组确定；如果这个RTS分组是发送给这个节点的，那么该节点回送一个CTS分组，等待足够长时间，以便发送节点发送的一个数据分组完整传输到达本节点；接着等待一段随机时间，之后再发送RTS分组。

FAMA-NPS协议的一个重要特点是节点发送前不需要侦听信道。节点只是在接收和认识到一个完整的RTS分组或者CTS分组之后才推迟其发送。如果没有恰当的预防措施，数据分组可能与RTS分组碰撞。

3.FAMA-NCS的正确性

FAMA-NCS要正确获取信道，就必须确保每个新分组或者重传分组在准备好之后在有限时间内被发送到信道上以及确保每个数据分组不能与任何其他分组发送碰撞。

定理2-1的证明采用如下假设条件（在其他假设条件下，采用类似方法也能得到类似结果）：

● 相互处在对方传输覆盖范围内的任意两个节点之间的最大传播时延τ<∞；

● 发送至信道上且不会与其他发送碰撞的分组无误码交付概率p>0；

● 节点给一个预定目的节点发送一个RTS分组且接收到该目的节点回送的不会与任何其他发送碰撞的CTS分组的概率大于0；

● 所有节点正确执行FAMA-NCS；

● 一个RTS分组的发送时间γ <∞，一个CTS分组的发送时间γ ′<∞，一个数据分组的最大传输时间δ <∞，最大发送至接收硬件转换时间2τ<ε<∞，接收至发送硬件转换时间为0；

● 信道上不存在捕获效应和衰落；

● 在一个特定接收机上的重叠发送导致该接收机无法识别任何分组。

定理2-1：若γ >τ，γ +2τ +ε <γ ′<∞，则FAMA-NCS在隐含终端条件下提供正确的信道获取能力。

证明：图2-10给出一对源节点S与目的节点R的各种隐含终端情况。节点L是S的相邻节点，是R的隐含节点，会在S上产生干扰。节点K是L的相邻节点，是S的隐含节点，会在L上产生干扰，会阻止L遵从S与R的分组交互。类似地，节点X是R的相邻节点，是S的隐含节点，会在R上产生干扰。节点Y是X的相邻节点，是R的隐含节点，会在X上产生干扰，会阻止X遵从R与S的分组交互。必须证明：若S给R发送一个数据分组，则不论是否存在其他干扰节点的发送，该数据分组均不会与其他发送碰撞。

S要能够将数据分组发送给R，首先必须接收到R回送的CTS分组。不失一般性，假定S在时刻t0给R发送一个RT S分组。

由于信道的最小传播时延大于0，所以S的任何相邻节点（比如节点L）必须在时刻 0Lt >t0开始接收S的RT S分组。若L正确接收到S的RT S分组，则L必须在接收RT S分组结束之时开始退避一段时间（大于2τ +γ ′），即L在时刻 0Lt 后退避γ +2τ +γ ′。若L接收到S的RTS分组有误码，或者K的发送在L上干扰了S的RTS分组，则L必须从载波侦听结束时刻开始退避一段时间（大于2τ +δ）。L必须退避的最小时间符合载波侦听结束时刻与S的RTS分组结束时刻一致。因此，L必须在时刻后退避γ +2τ +δ 秒。S在时刻t0给R发送一个RTS分组强迫S的所有相邻节点（R除外）退避到时刻t1>t0+γ +2τ +γ ′。

若R接收到的RTS分组有误码或者被R的其他相邻节点（S的隐含节点，比如X）的发送所碰撞，则R不能回送CTS分组，S也就不能发送数据。

假定R在时刻t2正确接收到S的RTS分组。若R回送的CTS分组到达S时有误码或者遭遇S的相邻节点（隐含节点，比如L）的发送的碰撞，则S不能发送数据分组。

在下面的证明中假定S发送的RT S分组在一个最大传播时延内被R所正确接收。因此，R必须在时刻t2≤t0+γ+τ开始给S回送CTS分组（假定处理时延为0）。R回送完CTS后，CTS同样在一个最大传播时延内到达S。因此，S必须在时刻t3≤t2+γ′+τ=t0+γ+γ′+2τ接收到R回送的完整CTS分组。

由于t1>t3，所以S任何可能的干扰相邻节点（比如L）必须退避足够长时间，以便S能够无碰撞地接收到R回送的CTS分组。

S必须在R开始回送CTS之后的τ内开始对其接收，必须在时刻t4≤t2+γ′+τ接收到R回送的完整CTS分组和发送其数据分组。R必须在时刻t5≤t4+δ+τ≤t2+γ′+2τ+δ接收完S的数据分组。

此外，R传输覆盖范围内的任意节点X（S除外）必须在时刻 开始接收R回送的CTS分组。若X正确接收到R回送的CTS分组，则R在完成接收CTS分组时刻后必须退避一段时间（大于2τ +δ），因此X从时刻开始退避γ ′+2τ +δ 秒。反之，若R回送的CTS分组到达X时有误码或者遭遇R的某个相邻隐含节点（比如Y）的发送的碰撞，则X必须从载波侦听结束时刻开始退避一段时间（大于2τ +δ）。X的最小退避时间符合X载波侦听结束时刻等于X接收到R回送的完整CTS分组时刻。因此，X在 后必须退避γ ′+2τ +δ 秒。R在时刻t2给S回送CTS分组迫使X和R的所有相邻节点（S除外）退避至时刻t6>t2+γ ′+2τ +δ。

由于t6>t5，所以X和R任何其他可能的干扰相邻节点必须退避足够长时间，以便R能够无碰撞地接收到S发送来的数据分组。因此，FAMA-NCS允许节点在成功完成RTS-CTS分组交互后发送数据分组，并且数据分组不会与其他发送碰撞。

ε>2τ不是FAMA协议正确性的必要条件，但是起到简化上述公式的作用，并且与IEEE 802.11规范一致。理论上，为了使主CTS技术适用于任意ε≥0，只要求数据分组发送节点正确接收到回送的CTS后退避2τ 秒，并且要求将退避节点（以便于数据分组的交付）的退避时延增大2τ 秒。

定理2-1说明：若一个RTS分组的持续时间大于最大传播时延，一个CTS分组的持续时间大于一个RTS分组发送时间、最大往返传播时延、最大发送至接收硬件转换时间之和，则FAMA-NCS提供正确的信道获取能力。

4.FAMA-NPS的正确性

以图2-11进行描述。在FAMA-NPS中，节点在推迟其发送之前必须解析分组，并且一个节点的发送需要τ 秒才能够到达所有其他节点。因此，一个节点（比如C）在另一个节点（比如A）完成其RTS分组发送（用于请求与另一个节点B通信）之后最多还需要τ 秒才可能开始发送自己的RTS分组。此外，C开始发送的RTS分组也需要τ 秒才可能到达A。所以从A发送完毕RTS分组时刻至C开始发送RTS分组时刻之间的最大时间为2τ 秒。若B离A非常近，则B成功接收到A的RTS分组并对其处理完毕之后很快（所需时间ε <<τ）就会回送CTS分组；A在ε 秒内接收到B的CTS分组，然后完成对其处理，接着就可以立即开始对B发送数据分组。若γ≤2τ，则ε→0，因此A有可能在其RTS分组发送完毕之后的2τ 秒内成功接收到B回送的CTS分组和对B发送数据分组；数据分组与C发送的RTS分组碰撞，因此C发送的RTS分组在A的RTS分组发送完毕之后的2τ 秒内不会到达A。

定理2-2：若2τ<γ<∞，则FAMA-NPS确保数据分组不会与任何其他发送碰撞。

证明：考虑一个全连通网络，其中节点A给节点B发送数据，干扰节点C。需要证明：B回送给A的CTS分组在A上与C发送的RTS分组碰撞。不是一般性，假定A和B是相邻节点，如图2-12所示。A给B无干扰发送完RTS分组后，B在随后的ε 秒内接收到A的RTS分组，接着立即回送CTS分组。A在B停止其发送后的ε 秒内接收到B的CTS分组。C若要能够在A开始发送其RTS分组后开始发送自己的RTS分组，那么就必须在A完成其RTS分组发送之后（正好在解析A的RTS分组之前）的最多τ秒内进行发送。C的RTS分组最多需要τ 秒（A完成其RTS分组之后的2τ）到达A、并且必定与B的CTS分组碰撞（即使因γ >2τ 而ε =0），从而导致A和B之间的RTS-CTS交互失败，A退避后重新尝试发送。因此，若γ >2τ，且其他任意节点在A的RTS分组发送完毕之后的τ 内开始发送RTS分组，则A不能发送数据分组；若此前没有其他节点发送RTS分组，则每个节点必须最多τ 秒内解析A的RTS分组。定理2-2成立。

下面举例说明基于RTS-CTS分组交互的MAC协议以及在隐含终端下没有载波侦听不能有效支持获取信道，这是因为必须重传若干次CTS分组才能确保数据分组不会与其他分组发送碰撞。假定RTS和CTS的分组长度相同。

假定S给R发送一个RTS分组，R正确接收到S的RTS分组后立即给S回送CTS分组。图2-13表示R的相邻节点不认识CTS分组的两种情形：第一种情形是X相邻区域内的节点X给R发送RTS分组，从而阻碍自己及R相邻区域内所有其他节点认识第一个CTS分组和第二个CTS分组；第二种情形是X相邻区域内一个节点（既不是R也不是S）发送RTS分组，导致X接收不到R的CTS分组，从而X可以发送自己的RTS分组而堵塞其他CTS分组。不论哪种情形，若R没有重传足够多的CTS分组，则至少X不认识CTS分组，因而可以发送RTS分组，导致在R上碰撞S发送的数据分组。

为了解决第一种情形的竞争问题，接收节点R至少需要重传3个独立的CTS分组。这是必要的，因为节点认为在没有成功接收到任何发送分组之前或者没有检测到信道上的发送信息时信道是空闲的，因而可以进行发送。因此，X正好可以在快要接收完R的CTS分组前的极短时间内发送自己的RTS分组，也可以在R开始发送下一个CTS分组后发送自己的RTS分组。X等待R回送自己RTS的CTS分组，而不会解析R回送给S的CTS分组，进一步推迟发送。

在第二种情形中，R至少必须发送5个CTS分组。X的相邻节点发送RTS分组而碰撞第一个CTS分组和第二个CTS分组，导致X接收不到CTS分组，因而X发送RTS分组而碰撞第三个CTS分组和第四个CTS分组。X接收到第五个CTS分组，从而迫使X推迟其发送。

网络规模越大，任意接收节点R必须重传的CTS分组就越多，以确保R的相邻节点能够意识到R即将接收数据分组，因此这种分组交付方法效率低。

5.吞吐量对比分析

1）假设条件与使用符号

下面从理论上近似分析FAMA-NCS、ALOHA、CSMA、MACA（即FAMA-NPS）在全连通网络和无线局域网（存在隐含终端）中的吞吐量。

假定无穷个节点组成一个泊松源，泊松源以每单位时间λ个分组的总平均产生率向信道上发送RTS分组（FAMA）、数据分组或重传数据分组（CSMA）。任意节点能够侦听任意其他节点的发送。

假定每个节点任何时候最多只有一个数据块需要发送。在所分析的各种MAC协议中，每个节点将整个数据块或者作为一个数据分组（CSMA、MACA）来发送，或者作为多个数据分组（FAMA-NCS）来发送。一个数据块平均持续δ 秒，一个RTS分组持续γ 秒，一个CTS持续γ ′秒。相互处在对方传输覆盖范围内且能够相互通信的任意两个节点之间的最大传播时延为τ 秒。可能在信道上发生碰撞（FAMA-NCS协议的RTS分组，CSMA的数据分组）。假定一个节点必须重传一个分组时，该节点随机退避一段时间（其平均值比δ大得多）后再重传该分组。平均信道利用率S为

式中，B表示信道忙的平均持续时间，等于信道正在被使用的时间；表示信道空闲的平均持续时间，等于信道连续两次忙期间之间的时间；表示信道成功忙于发送用户数据的时间。

假定不存在信道误码，因此分组碰撞是唯一误码源，节点能够检测全部分组碰撞。假定时间上相互重叠在一起的两个或者更多发送必须重传，分组正好在τ 秒传播到达所有节点。为了减少使用的变量，分组时间中包含转换时间（ε），ε 包含传播时延。

这个分析模型只是实际情况的大致近似。实际情况是，有限个节点访问信道，节点排队缓存多个分组等待发送，各个节点的发送和重传（RTS分组或数据分组）是相关的（比如：在有限时间内，一个RTS分组发送失败后紧接着发送另一个RTS分组）。这个分析模型有助于理解侦听信道活动类型的益处，有助于认识FAMA协议性能和信道速率和传播时延对信道获取技术的影响。

对于非持续性CSMA，假定使用一个独立的理想应答信道，所有应答都是可靠发送的，节点据此能知道自己的发送分组何时已被正确接收。因此，只需要非持续性CSMA的吞吐量的上限。

为了便于以数据依据比较各种MAC协议的吞吐量，图中给出了平均吞吐量与流量载荷之间的变化曲线，利用δ=1和以下变量对所获得的S结果规格化：

a=τ/δ（规格化传播时延）

G=λ×δ（流量载荷，采用数据分组进行规格化）

2）全连通网络的吞吐量

（1）FAMA-NCS的吞吐量

FAMA-NCS的发送周期如图2-14所示。一个FAMA-NCS发送周期从源节点RTS分组发送时刻t0开始，发送脆弱周期τ秒，其间可能碰撞其他节点发送的RT S分组，导致发送失败。脆弱周期结束后，若没有其他节点发送，则所有其他节点侦听信道为忙而推迟发送，因此RT S分组发送成功。根据FAMA-NCS协议，RTS分组发送成功后，紧接着是接收节点回送CTS分组，然后是源节点发送数据分组。由于强迫等待时间和空闲周期，一个FAMA-NCS忙周期正好等于一个成功发送周期或者一个失败发送周期，之后均为一个空闲周期。

定理2-3：FAMA-NCS的吞吐量为

证明：一次成功发送周期包含一个RTS分组及其到达预定接收节点的传播时延、一个CTS分组及其到达源节点的传播时延、一个数据分组及其到达预定接收节点的传播时延。因此，一次成功发送周期T等于

由于FAMA-NCS保证在RTS分组成功之后发送的数据分组不会与任何其他分组碰撞，所以一个失败发送周期包含在时刻t0发送到信道上的一个RTS分组，以及之后其他节点在Y秒时间内发送的一个或者多个RTS分组，0≤Y≤τ，再加上一个最终传播时延。因此，正如非持续CSMA一样，平均失败发送周期TFAIL=γ +τ +。Y的累积分布函数就是时间τ−y内无RTS分组到达的概率，即FY(y)=e−λ(τ−y)，y≤τ。因此，Y的均值Y=τ−(1−e−λτ)/λ。

由于在所有其他网络节点检测载波信号之前存在τ秒的信道时延，所以RT S分组的成功率P S等于τ秒内无RT S分组到达的概率。在这τ秒的脆弱期间，所有节点检测信道载波信号，推迟其发送。因此，假定RTS分组到达信道上为参数λ 的泊松分布，于是得到

一个FAMA-NCS忙周期的成功概率为e−λτ。一个成功的FAMA-NCS忙周期的长度等于(γ+τ)+(δ+γ′+2τ)，其中(γ+τ)包含一个RT S分组的持续时间和一个传播时延，(δ+γ′+2τ)包含相应CTS分组和数据分组的持续时间及其传播时延。同理，如图2-14 所示，一个失败的FAMA-NCS忙周期的长度等于γ+τ+Y。因此，假定在一个成功FAMA-NCS忙周期中y=0，于是得到FAMA-NCS忙周期的平均长度B为

平均利用率等于在一个成功FAMA-NCS忙周期中有用数据的平均发送时间。于是得到

根据FAMA-NCS的定义，节点每次发送之后、以及在转移到状态PASSIVE或BACKOFF之前均要等待固定时间2τ秒（见图2-8）。因此，平均空闲周期为

将式（2-7）、式（2-8）和式（2-9）代入式（2-3），得到式（2-4）。

（2）FAMA-NPS的吞吐量

FAMA-NPS的发送周期如图2-15所示，其中γ>2τ。采用FAMA-NPS的节点在发送之后没有强制性等待时间（参考MACAW及图2-15～图2-12），所以RTS分组和CTS分组说明节点的退避时间长度。MACA在发送RTS分组之前没有使用载波侦听，一个节点即使接收到或者正在接收而没有接收完另一个RTS分组也可以开始发送RTS分组（或者CTS分组），这种操作类似于ALOHA操作。但是，节点认识到另一个节点的无误码RTS分组后推迟自己的发送，推迟时间等于一次成功发送的剩余发送时间。推迟时间结束后，在重新发送之前等待一段随机时间。随机等待时间强迫一次成功发送之后需要一个空闲周期。失败发送周期包含在失败发送周期中（或者在失败发送周期附近）的任何发送尝试，因此一个失败发送周期之后也是一个空闲周期。一个FAMA-NPS忙周期等于一个成功发送周期或者一个失败发送周期。

定理2-4：FAMA-NPS的吞吐量为

其中，。

证明：一次成功发送包含一个RTS分组、一个CTS分组、一个数据分组、信道传播时延τ 秒。因此一次成功发送周期T由式（2-5）给出。

如上所述，一个忙周期由一个发送周期组成。假定每个分组需τ秒到达所有节点，γ>2τ，则根据定理2-2，RTS分组和CTS分组不会碰撞数据分组。一个失败发送周期只有碰撞的RTS分组和CTS分组组成。一个失败周期存在两种情形：一是启动忙周期的RTS分组碰撞其他节点发送的一个或者多个RT S分组；二是预定接收节点成功接收到RT S分组，但是在RTS分组的τ秒传播时延期间、以及在识别这个RTS分组之前，至少一个其他节点有数据分组需要发送而发送自己的RTS分组，结果碰撞本忙周期的第一个RTS分组的CTS响应分组。对于这两种情形，失败发送周期的平均长度都是不受限制的。对于第一种情形，失败发送周期 TFRTS只包含多个RTS分组。对于第二种情形，失败周期的平均长度TFCTS包含一个RTS分组、第一个RTS分组结束后τ秒间隔内RTS分组平均到达时间τ′、失败RTS分组的周期（其平均值等于TFRTS）或者开始发送CTS分组后无RTS分组到达时CTS分组清除信道所需要的时间。

图2-16比较详细描述了FAMA-NPS的RTS分组发送失败周期。图中所示发送周期包含四个发送失败的RT S分组，时间周期f1、f2、f3表示这四个RT S分组的到达间隔时间。平均失败发送周期正好与纯ALOHA协议相同，包含L个RTS分组到达间隔时间（L不确定且呈几何分布，到达间隔时间平均长 f 秒（两个失败RT S分组之间的平均到达时间））、一个RT S分组的持续时间γ，以及传播时延τ秒之和。根据文献[17]（推导出纯ALOHA的L和 f 是λ的函数），当忙周期的第一个RTS分组碰撞其他RTS分组时，一个失败发送周期的平均长度TFRTS为

当一个失败CTS分组已经清除信道时该CTS分组发送失败周期结束的概率等于一旦开始发送该CTS分组后无其他RTS分组到达的概率，即等于随后γ 秒（CTS分组的持续时间）无RTS分组到达的概率（假定γ +τ秒（RTS分组结束时刻与其相应CTS分组结束时刻之间的时间）内至少有一个RTS分组到达）。于是

由于RTS分组到达过程是泊松过程，所以任意给定时间间隔内的到达时间是独立的、均匀分布的。这就意味着，平均地，τ′=τ/2。因此，一个CTS分组发送失败周期的平均长度TFCTS为

一次成功发送的概率 PS等于在信道上发送数据分组的概率。而只有当RTS分组及其CTS分组发送无碰撞时才能够在信道上发送数据分组。如果在开始发送RTS分组前/后γ秒内没有发送其他RTS分组，那么信道是干净的（没有传输其他分组）。由于RTS分组需要τ秒才能到达所有节点，所以若是在RTS分组之后τ秒内没有发送RTS分组，则是在干净信道上回送CTS分组。于是

RTS分组发送失败的概率等于正在发送另一个RTS分组期间而该RTS分组到达的概率，即PFRTS=1−e−2 λγ。

CTS分组发送失败的概率等于一个RTS分组发送成功而在该RTS分组发送结束后的τ 秒内至少发送一个RTS分组（因此碰撞成功发送的RTS分组的CTS分组）的概率，即PFCTS=e−2 λγ(1−e−λτ)。

一个FAMA-NPS忙周期只等于一个成功发送周期或者失败发送周期（两种的一种），即

将PS、PFRTS、PFCTS、T、TFRTS、TFCTS代入式（2-15），得到

由于对信道的所有发送（包括重传）都是从RTS分组开始的，所以FAMA-NPS的平均空闲周期I等于RTS分组的平均到达间隔时间，即等于1/λ。。于是

将代入式（2-3），得到式（2-10）。

（3）吞吐量的对比

下面比较FAMA-NCS、非持续CSMA、FAMA-NPS在全连通网络中的吞吐量。传输速率1M b/s，短数据分组53B（AT M信元的长度），长数据分组400B，最大网络直径1英里，单向传播时延约5μs，最小RTS分组20B（包含源节点和接收节点的IP地址、CRC、成帧字节）。图2-17给出了各种MAC协议吞吐量与网络载荷之间的变化关系。从图2-17所示结果可以看到使用载波侦听作为信道获取策略的一个组成部分非常重要，FAMA-NCS的吞吐量比FAMA-NPS（即MACA）和时隙化FAMA-NPS高得多。当b=γ/δ取小值时，FAMA-NCS效果更好（见图2-18）。显然，在低速或高速信道上使用MACA（或者其衍生版），每次成功完成RTS-CTS交互后，传输单个短数据分组，其效率很低。

3）无线局域网的吞吐量

采用Tobagi和Kleinrock在文献[2]中使用的模型分析研究FAMA-NCS在无线局域网中的性能。该模型包含前面的假设条件，系统由大量终端组成。所有终端在视距范围内且处于基站传输覆盖范围内，可能互为隐含终端，在单信道上与单个基站直接通信。将所有终端分成N个独立组。相同组内的所有终端能够相互通信和与基站通信。任意两个不同组的终端互为隐含终端。所有流量都是从终端传递至基站，每个组i由大量终端组成，共同形成一个独立的、总平均每秒

λi个信道请求的泊松源。因此，。

定理2-5：对于N个独立全分布式隐含节点组的系统，FAMA-NCS的吞吐量为

其中 。

证明：基站的时间由忙周期和空闲周期序列组成。由于FAMA-NCS提供正确的信道获取能力，所以只可能在RTS分组之间发生碰撞。因此，由于成功发送的RTS分组根本不会与任何其他RTS分组重叠在一起，所有组能够检测到成功发送周期，并且一个成功发送周期强制要求2τ 秒空闲时间，所以一个忙周期等于一个失败发送周期或者等于一个成功发送周期。

组i中任意节点s发送的RTS分组若没有遭遇其他组发送的RTS分组的碰撞，则发送成功。组i内所有其他节点在节点s开始发送RTS分组之后τ秒都能够检测到该RTS分组，因此该RTS分组的脆弱周期为τ秒，RTS分组在其组i内成功发送的概率为e− iλτ。由于隐含组中节点接收不到s发送的RTS分组，且所有发送需要τ秒才能到达基站，所以RTS分组关于其他组在基站的脆弱周期为γ秒，组i中节点s发送的RTS分组关于组j的成功概率为 (2 )e− jλ γ。因为所有组相互独立，所以组i发送的RTS分组在基站的成功概率为

因此，任意组成功发送RTS分组的概率为

任意给定组发送的RTS分组关于其他组在基站的成功概率为

一个成功发送周期T秒，由式（2-5）给出。有两种类型的失败发送周期。若在一个发送周期中只有一个组发送RTS分组，则其在基站的平均持续时间等于TF1=γ +，其中等于全连通网络的。由于一个给定组中的节点接收不到其他组发送的RTS分组而可以在一个失败发送周期（并不涉及组i）结束后随时发送，所以TF1不等于全连通网络的TFAIL。，为了简单起见，使用如下不等式：

如果在一个失败发送周期中多个组发送RTS分组，那么失败发送周期包含多个相互重叠的发送周期，每个发送周期平均长TF1秒。由于各个组相互隐含、相互独立，所以可以按照N个节点的ALOHA信道来计算失败发送周期的平均长度：节点i相当于组i，具有总速率λi，平均失败发送周期包含L个到达间隔时间和一个RTS分组的持续时间γ，L是几何分布的不确定数，到达间隔时间平均长 f 秒（两个失败到达之间的平均时间）。根据文献[17]（推导出纯ALOHA的L和 f 是λ的函数），当发送周期的第一个RTS分组碰撞其他RTS分组的时候，失败发送周期的平均长度TFRTS等于

为了使用前面的结果，假定N非常大。因此，用不等式（2-22）的上限替代公式（2-23）中的γ，得到失败发送周期的平均长度近似值

于是，平均忙周期为

将式（2-21）、式（2-22）、式（2-23）代入式（2-24），得到

平均空闲周期等于每次成功数据分组发送之后的2τ 秒与所有组的RTS分组平均到达间隔时间之和，即

平均信道利用时间等于一个成功忙周期中有用数据的发送时间，即

将式（2-26）、式（2-27）、式（2-28）代入式（2-3），得到式（2-18）。

当N→∞时，FAMA-NCS在无线局域网中的吞吐量为

式（2-4）和上述结果说明：随着关于任意给定组的隐含终端的增多，FAMA-NCS的性能随着下降至RTS分组的脆弱周期2 倍于RTS分组的长度（而不是2 倍于传播时延），这正好是FAMA-NPS在全连通网络中的性能；但是由于γ<<δ，FAMA-NCS的性能远优于CSMA的性能（一个分组的脆弱周期2倍于该分组的长度，正好是ALOHA信道的性能）。

为了使上述结果更形象，比较FAMA-NCS、CSMA在无线局域网（具有相互隐含的独立组，一个中心站）的吞吐量。图2-19（a）比较了ALOHA、时隙化ALOHA、非持续CSMA（NP-CSMA）、FAMA-NCS的吞吐量与独立组数量（N）之间的变化关系。结果表明：FAMA-NCS在隐含终端下的吞吐量正是FAMA-NPS在全连通网络中的吞吐量，这正是所需要的结果。

下面介绍FAMA-NCS在互补节点组对配置中的吞吐量。其中一部分节点（比率α）是剩余节点的隐含节点。采用2个独立组（N=2），节点组大小可变，其中一个节点组大小S1=α×S，另一个节点组大小 S2=（1−α）×S。RTS分组总平均到达率 G=5.0，相当于α=1/2时最大吞吐量的到达率。图2-19（b）给出了最大可得吞吐量与α之间的变化关系。从图2-19（b）可看到：存在隐含终端时，FAMA-NCS吞吐量下降明显小于CSMA。

2.3.4 IEEE 802.11 MAC协议

IEEE 802.11 MAC协议包含两种方式：一是分布式协调功能（Distributed Coordination Function，DCF）方式，二是集中协调功能（Point Coordination Function，PCF）方式。分布式基本无线媒介访问控制（Distrbuted Foundation Wireless Medium Access Control，DFWMAC）是具有DCF方式的IEEE 802.11 MAC协议。DCF的基础就是载波侦听多址访问与碰撞回避（Carrier-Sense Multiple Access with Collision Avoidance，CSMA/CA）协议。

CSMA/CA协议可以看作是CSMA协议和MACA协议的组合协议，意在解决隐含终端问题。CSMA/CA协议采用RTS-CTS-DATA-ACK交互方式传输数据。在CSMA/CA协议中，发送节点必须首先发送一个请求发送（Request to Send，RTS）分组。RTS分组包含接收节点的身份识别码，因此只有该RTS分组指定的接收节点才能够用允许发送（Clear to Send，CTS）分组来应答该RTS分组。其他移动节点接收到RTS分组或者CTS分组则推迟其发送，推迟的时间由RTS-CTS握手控制分组中的网络分配矢量（Network Allocation Vector，NAV）来确定（见图2-20）。每个网络节点维护一个NAV。NAV包含其他节点发送而导致传输媒介忙的持续时间信息。因此，隐含节点的数量得到一定程度的减少。

DFWMAC协议中的每个分组之间有一个间隔时间，这个间隔时间叫做帧间隔（Inter-Frame Space，IFS）。有四种IFS：短IFS（Short Inter-Frame Space，SIFS），集中协调功能IFS（Point Coordination Function Inter-Frame Space，PIFS），分布式协调功能IFS（Distributed Coordination Function Inter-Frame Space，DIFS），扩展IFS（Extended Inter-Frame Space，EIFS），每种IFS都有其使用场合。只有媒介空闲的时间长度大于IFS的时候，移动节点才会认为媒介是空闲的。只要移动节点认为媒介空闲，那么该节点就可以进行发送。

一个节点在发送一个RTS分组之前，必须首先侦听媒介一个DIFS时间。如果信道侦听结果为空闲，那么该节点就可以开始发送RTS分组。接收节点接收到RTS分组之后，首先侦听媒介一个SIFS时间，如果信道侦听结果为空闲，则回送一个CTS分组。如果信道空闲时间长度达到SIFS，那么发送节点发送一个数据分组，接收节点接收到数据分组之后用ACK分组作出应答，如图2-21所示。

如果一个移动节点已经发送了一个RTS分组或者一个数据分组，但是却没有接收到CTS应答分组或者ACK应答分组，那么该节点启动退避进程。在退避过程中，该移动节点首先产生一个退避时间，其值等于若干个时隙，均匀分布在[0，CW]上，CW为当前竞争窗口参数。只有当媒介空闲的时候，移动节点才会递减退避时间。注意：为了识别空闲媒介，移动节点必须侦听到媒介的空闲时间等于DIFS。当信道变成空闲的时间大于DIFS的时候，移动节点递减退避时间；而当信道重新变成忙的时候，移动节点停止递减退避时间。重复进行这个过程，直到退避时间减到零时为止。然后移动节点在下一个时隙初始化发送，而无需等待一个DIFS时间。

竞争窗口最初从最小值CWmin开始。每碰撞一次，竞争窗口增大一倍，达到最大值CWmax后则停止继续增大。一旦传输成功，将竞争窗口复位到最小值CWmin。

NAV不同于退避时间，总是递减的，而且与媒介状态无关，这是因为NAV等待数据分组传输所需要的时间。获得NAV的移动节点就在NAV所需要的这段时间停止其发送，从而节省了电池的使用寿命。DFWMAC协议设置一个较短的SIFS间隔用来传输随后的分组，因此，已经获得信道使用的移动节点具有优先权。已经发送了RTS分组的移动节点对信道侦听一段较短的时间，比其他节点更有可能获得信道的使用。

但是，CSMA/CA协议没有彻底解决隐含节点问题。例如，在图2-22中，当节点C（是发送节点A的隐含节点）在节点A和节点B之间的握手协议完成之后进入双方的通信区域、并且开始发送数据的时候，那么就会在有效的接收节点上发生碰撞。

CSMA/CA协议导致更多的移动节点不能发送，从而加重显现节点问题。显现节点问题使得传输控制协议（Transmission Control Protocol，TCP）在DFWMAC协议作用下的性能不理想。特别地，在一个相同区域内只能存在一个TCP连接。

IEEE 802.11 MAC伪码如图2-23所示。IEEE 802.11 MAC协议的详细描述详见本章参考文献[14，15]。

2.3.5 MACA-BI协议

应邀式多址访问与碰撞回避协议MACA（MACA by Invitation，MACA-BI）是接收节点初始化竞争类MAC协议，意在减少发送节点初始化竞争类MAC协议（例如MACA、MACAW、FAMA、IEEE802.11等）交互的控制分组数量，从而提高系统吞吐量。

MACA-BI协议将MACA协议的控制分组握手对话过程反过来：接收节点通过给发送节点发送一个准备接收（Ready to Receive，RTR）控制分组来初始化分组传输，发送节点使用数据分组传输来响应这个轮询分组（即RTR控制分组）。因此，MACA-BI采用双方交互（RTR-DATA）传输数据，而不是采用三方交互（RTS-CTS-DATA）传输数据。

在MACA-BI中，由于发送节点在接收到请求之前不能发送数据，因此接收节点必须有某种流量预测算法，以便知道何时向发送节点请求数据。流量预测算法的效率决定系统吞吐量。例如，可以让数据分组携带有关发送节点分组队列长度和数据到达率等信息，要求每个节点维护一张其相邻节点及其传输特征的表格，与相邻节点共享这张表格的信息。接收节点接收到数据分组后就能够预测相应发送节点中缓存的数据量，从而进一步发送RTR分组。此外，当发送节点输入数据缓存器发生益出时，发送节点发送RTS分组，此时系统从MACA-BI协议回复到MACA协议。

MACA-BI协议适用于可预测流量模式的网络，效率高。但是，对于突发流量，MACA-BI协议的性能下降为MACA协议的性能。

MACA-BI协议不能预防数据分组碰撞问题。例如在图2-24（a）中，节点A和D在时刻t0分别给节点B和E发送RTR分组，从而激励发送节点（B和E）在时刻t1发送数据分组，而只要其中一个发送节点（B或者E）将数据分组发送给节点C，则会在节点C上发生碰撞，导致节点C接收不到数据分组。又如在图2-24（b）中，节点A在时刻t0给节点B发送一个RTR分组，节点B因此而在时刻t1开始给节点A发送数据分组。为了提供良好的吞吐量，必须有t1>γ，γ是RTR分组的持续时间长度。节点C在时刻t2开始给节点D发送RTR分组。由于载波侦听，t2必须在t1的τ秒（最大传播时延）内。节点D接收到节点C的RTR分组后，利用数据做出应答，该数据必须在时刻t3到达节点C。由于最大传播时延τ，所以t3≤t2+γ+2τ≤t1+γ+3τ必须成立。如果数据分组的持续时间大于γ+3τ秒，那么节点B和D发送的数据分组在节点C上发生碰撞。实际上，为了提供良好的吞吐量，数据分组比RTR分组大得多，这就说明MACA-BI协议不能防止数据分组碰撞。