3.2 五步预留协议（FPRP）

考虑移动MANET中TDMA广播传输时间安排问题。可以利用MANET的多跳网络拓扑进行带宽的空间复用。不同的节点只要相距得足够远，而且不会相互干扰，则可以同时使用相同的带宽。给节点分配发送时隙的问题称为传输时间安排。考虑使用全向天线的单信道MANET中安排广播发送传输时间的问题。广播是指当一个节点发送的时候，该节点周围一跳远范围内的所有相邻节点都接收这个广播分组。广播传输时间安排在网络控制/网络组织期间非常有用，因为在这段时间网络节点必须互相协调控制操作。此时，无冲突广播传输时间安排要求任何两个同时发送的节点之间的距离必须至少等于三跳。

五步预留协议（the Five-Phase Reservation Protocol，FPRP）是一个单信道、基于TDMA的广播传输时间安排协议。FPRP协议使用竞争机制，网络节点使用竞争机制与其他节点互相竞争以获取TDMA广播时隙。FPRP协议不存在“隐含终端”问题，能够快速而高效地做出预留，碰撞概率可以忽略不计。FPRP协议是全分布式协议，可以并行操作，因此具有可扩展性。FPRP协议采用多跳随机贝叶斯（Bayesian）算法来计算竞争概率，使预留过程收敛更快。

FPRP协议允许MANET的节点预留TDMA广播时隙和做出广播传输时间安排，将信道访问和图形添色功能结合起来同时执行，同时无需任何集中机制，也不会限制可扩展性。在提供足够精确的时间同步信号的条件下，FPRP协议要求最小的节点计算能力，易于实现，节点能够区别出一个分组到达还是多个分组到达。FPRP协议在由相同节点构成的网状拓扑网络中表现很好，能够准确估计网络中的节点密度，并将其嵌入到协议中。仿真实验结果表明FPRP协议能够以低得合理的开销做出性能优良的传输时间安排，网络规模和节点移动对FPRP协议的影响不大。因此，FPRP协议非常适用于大规模MANET。

3.2.1 FPRP协议

1.概述

FPRP是一个基于竞争的协议，使用五步预留过程来建立TDMA时隙分配，得到的TDMA时隙分配无碰撞概率高。FPRP是全分布式协议，在整个网络范围内按并行方式运行。所谓并行运行，是指FPRP协议允许在网络内的各个部分同时做出多个预留。对于一个给定节点的预留过程只涉及该节点两跳半径覆盖范围内的节点，所以该过程是一个本地过程，不必与更远的节点进行协调。通过保持预留过程局部化以及在全网范围内同时进行预留，FPRP协议对网络规模表现不敏感。因此FPRP协议适用于规模很大的网络以及规模大小动态变化的网络。当网络发生分割后，FPRP协议也工作得很有效。节点不需要事先掌握有关网络的信息，即不需要知道有关网络成员、网络成员的相邻节点集、以及网络规模大小。这就使得FPRP协议在迅速变化的网络拓扑面前表现出强壮性。FPRP协议不需要媒介访问控制或者网络探测等其他协议的支持。FPRP协议将信道访问和节点广播传输时间安排（即图形添色）两个任务联合在一起，并同时执行。节点使用FPRP协议来检测其相邻区域，并做出几乎没有碰撞的预留。FPRP协议要求网络中所使用的每条链是双向链，但是对网络拓扑没有任何限制。可以用一张非定向图表示网络拓扑。

无线环境中的一个主要难点就是“隐含终端”问题。由于无线传输距离有限，两个节点可能相隔得足够远，以至于不能够相互直接检测到对方的发送（它们互为“隐含”），但是它们的发送可能在它们之间的另一个节点上发生碰撞。即使是IEEE 802.11 MAC中使用的四方握手方法也不能够彻底防止碰撞。大多数在发送方检测隐含节点的MAC协议要求知道两跳范围内的情况。在FPRP协议中，在发生碰撞的节点上检测两个隐含节点之间的碰撞，直到碰撞节点直接通知两个发送节点发生碰撞后才会停止碰撞。这就确保在TDMA广播传输时间安排中不会出现隐含节点引起的碰撞问题。

2.假设条件

对运行FPRP协议的网络做出如下假设：

（1）节点保持精确定时。全网统一时间对网络中每一个节点都有效，而且足够稳定，以便进行全网范围内的时隙同步；

（2）两个节点之间的链路是无噪声对称信道，即两个节点相互正常通话，或者根本不会相互干扰。分组碰撞是接收误码的唯一原因；

（3）在运行FPRP协议期间，网络拓扑不会发生变化。其基本原理是与计算一个新的传输时间安排所需要的时间相比较，网络拓扑变化相对较慢。而且，节点可能到处移动，但是与做出传输时间安排所需要的时间相比较，节点的移动速度相对较慢。因此，一旦计算出一个TDMA传输时间安排，那么在网络拓扑变化迫使做出另一个传输时间安排（或者更新）之前，这个TDMA传输时间安排还是能够使用一段时间；

（4）当多个分组传输到达同一个节点的时候，所有这些分组都被损坏；

（5）一个节点若是处在接收方式，则能够知道发送出来的是零个分组、一个分组、还是多个分组；

（6）每个节点都有一个唯一的身份识别码ID。

其中有些假设条件非常苛刻，代表理想情况。

3.FPRP协议的详细描述

FPRP协议的帧结构如图3-1所示。预留帧（Reservation Frame，RF）紧随在信息时段之前，信息时段由若干个信息帧（Information Frame，IF）组成。在一个IF帧内有 N 个信息时隙（Information Slot，IS）。在一个RF帧内也有N个预留时隙（Reservation Slot，RS）。每个RS时隙对应于预留一个相应的IS时隙。一个节点若需要预留一个IS时隙，则在相应的RS时隙内竞争。在一个RF帧内产生一个TDMA传输时间安排，然后在随后的每个IF帧内使用这个TDMA传输时间安排，直到重新产生新的TDMA传输时间安排的下一个RF帧为止，依次循环重复下去。

一个RS时隙由M个预留周期（Reservation Cycle，RC）组成（对于一个给定网络，必须试探性地确定参数M的取值）。每个RC预留周期由一个五步对话构成，FPRP协议的名称来源于这个五步对话。在一个RS预留时隙内，在竞争节点与其相邻节点之间进行五步对话交互，完成一个预留。

也就是说，一个节点若需要做出一个预留，则首先发送一个申请，其相邻节点接收到申请后回送一个反馈。如果这次申请成功（即这次申请没有与其他申请发生碰撞），那么该节点就预留这个时隙。将这个预留信息发送给该节点两跳范围内的所有节点。这些相邻节点认可这个预留，不会再去竞争这个时隙。如果这次申请不成功，那么该节点就会按照某种概率在随后的RC预留周期中去竞争这个RS预留时隙，直到自己竞争成功，或者其一跳或者两跳范围内的另一个节点竞争成功为止。结果，该节点在相应信息时隙内进行如下三种操作中的一种：发送（Transmit，T）、接收（Receive，R）、或者被堵塞（Be Blocked，B）。五步对话确保：①如果两个申请发生碰撞，那么这两个申请全都不能够做出预留；②一个节点一旦做出一个预留，那么在其相邻区域中高概率地专门使用该时隙。FPRP协议允许在全网范围内对一个时隙进行有效的空间复用。

一个节点保持全网统一的时间，并且知道何时启动五步对话交互过程。一个节点能够发送或者能够接收，但是不能够同时进行发送和接收。假设网络中的每个节点都参与预留过程。

一个预留过程包含如下五个步骤：

① 预留申请阶段（Request Phase，RR）。节点在这个阶段为其所需的预留做出申请。

② 碰撞报告阶段（Collision Report Phase，CR）。节点在这个阶段报告在阶段①发生的碰撞。

③ 预留确认阶段（Reservation Confirmation Phase，RC）。节点在这个阶段对它们的预留申请做出确认（在这个阶段建立一个预留）。

④ 预留应答阶段（Reservation Acknowledgement Phase，RA）。在阶段③旁听到一个RC的节点在这个阶段应答一个RA分组。这个RA分组还起着将这个最新预留通知给所有两跳远以内节点的作用。

⑤ 打包和撤销阶段（Packing and Elimination，P/E）。在这个阶段，发送两种类型的分组：一种是打包分组，用于在一个给定的时隙内使广播传输模式更加密集；另一种是撤销分组，用于撤销相邻广播节点之间可能的死锁（Deadlock，DL）。

下面详细介绍每个阶段的操作。

1）预留申请阶段

在这个阶段，一个节点若需要做出一个预留，则以概率p发送一个预留申请分组（Reservation Request Packet，RR）。发送RR分组的节点称为申请节点（Requesting Node，RN）。稍后讨论概率p的计算。没有发送RR分组的节点在预留申请阶段处于接收工作方式，可能从其相邻节点接收到零个、一个或者多个RR分组。若接收到多个RR分组，则假定全部RR分组都被损坏，该节点检测到一个碰撞。节点不必知道在一次碰撞中有多少分组被损坏。

2）碰撞报告阶段

某个节点若在预留申请阶段接收到多个RR分组，则发送一个碰撞报告分组（Collision Report Packet，CR）以表示在该节点处已发生和检测到一个碰撞。否则，该节点就处于静默状态。RN节点通过在这个阶段接收到的任何CR分组来确定其发送的RR分组是否已经与其他RR分组发生碰撞。RN节点若是没有接收到CR分组，则假定其发送的RR分组已经被其每个相邻节点所正确接收，然后变成一个发送节点（Transmission Node，TN），继续执行下一步并在第三步做出一个预留，然后在随后的信息时隙内进行发送，直到第四步或者第五步结束为止。

一个CR分组就是一种否定应答（Negative Acknowledgment，NACK）形式。接收到一个或者多个CR分组表示一次预留申请失败；只有没有接收到CR分组才表示一次预留申请成功。应该明白：如果两个RN节点互为隐含节点，那么这两个RN节点发送的RR分组将在其之间的中间节点上发生碰撞，并且这两个RN节点都将接收到CR分组，从而不会做出任何预留。RR-CR分组交互排除了“隐含终端”问题。

3）预留确认阶段

一个发送节点TN在预留确认阶段发送一个预留确认分组（Reservation Confirmation Packet，RC）。其一跳范围内的每个节点接收到这个RC分组后，知道这个时隙已经被预留。这些相邻节点在相应信息时隙内接收这个TN节点的发送。

4）预留应答阶段

在第四步，节点通过发送一个预留应答分组（Reservation Acknowledgment Packet，RA）对刚刚接收到的一个RC分组进行认可应答。由此通知发送节点TN：其预留已经建立。一个发送节点TN若是没有连接任何其他节点，则不会接收到任何RA分组，从而意识到自己是一个孤立节点，因而不再把自己作为一个发送节点TN。从而防止已经脱网的孤立节点进行发送和浪费其能量。没有这一步，已经脱网的孤立RN节点永远也接收不到CR分组，然后总是变成和保持为一个发送节点TN。

发送一个RA分组也起着通知发送节点TN两跳范围以内的节点这个预留已经成功。这些节点把这个时隙标注为已经被预留，停止竞争这个时隙；这些节点在这个时隙内被堵塞（Blocked，B）。

将发射机死锁定义为这样一种情况：两个或者更多的发送节点TN是相邻节点，这些节点被称为一个“死锁节点集合”。卷入到死锁中的发送节点没有一个公共的共享相邻节点，这个共享相邻节点本身不是发送节点TN。死锁在第一步开始形成。因为节点在第一步发送的时候不能接收，所以它们不能直接检测到碰撞。为了避免死锁，各个发送节点必须依赖一个已经存在的公共相邻节点在第二步发送一个碰撞报告CR分组。如果不存在这样的相邻节点（没有碰撞报告CR分组），那么每个发送节点在第二步都将声称自己预留申请成功，成为发送节点TN，因此形成一个死锁。有下列两种类型的死锁节点集合：①脱网死锁（死锁节点集合不存在连接任何其他非死锁节点的节点）；②非脱网死锁（死锁节点集合中有些节点连接到一个相邻的非死锁节点）。

第四步也用来解决脱网死锁问题。在脱网死锁情况下，由于没有发送RA分组的节点，也没有接收到RA分组的节点，因而所有节点放弃其发送，因此死锁问题得到解决。稍后介绍非脱网死锁的概率解决方法。

5）打包和撤销阶段

在这个阶段，一个发送节点TN自最近P/E阶段以来已经做出了其预留，与该TN节点相距两跳远的每一个节点都发送一个打包分组（Packing Packet，PP）。三跳远的、接收到PP分组的节点从而获悉一个最新的预留成功。结果，这个TN节点的有些相邻节点不会再竞争这个时隙。这个TN节点可以利用这个时隙，对其竞争概率作相应调整。这样能够加速收敛，同时提高了与拥有预留这个时隙的其他节点相隔三跳远的节点的成功概率。因此两个发送节点TN之间最多相距三跳远。这样更好，因为当发送节点TN相距只有三跳远的时候，允许更多的节点发送，被堵塞的节点较少。这常常被称为“最大封装（Maximal Packing）”。鼓励采用最大封装，FPRP协议的时隙使用效率更高。

在第五步，每个发送节点TN以0.5概率发送一个撤销分组（Elimination Packet，EP）。这考虑到另一个发送节点TN可能是一个潜在的相邻节点，以便解决非脱网死锁问题。一个发送节点TN若是没有发送，但是在第五步接收到一个EP分组，则知道存在一个死锁。在死锁情况下，该发送节点TN将该时隙重新标注为被其他发送节点TN（发送EP分组的TN节点）所预留，然后在该时隙内进行接收，而不是发送。该发送节点TN将在其他时隙内重新竞争，不必将这个重新标注事件通知其相邻节点。

为了进一步降低死锁的概率，可以进一步发送EP分组。一个发送节点TN在获得一个预留之后，在每个操作循环过程的第一步的相同预留时隙内发送一个EP分组。这个EP分组不会干扰任何RR分组（在做出预留之后，两跳范围内的每个节点都不会在这个相同时隙内竞争，所以该发送节点TN发送的EP分组不会与RR分组发生碰撞）。第一步的EP分组作用完全与第五步EP分组的相同。因此，常常执行这个撤销过程，仿真实验结果表明DL概率最终必然等于0。

第五步只有在做出一个成功预留之后才起作用。由于基于竞争的协议（比如时隙化ALOHA）的吞吐量比每个时隙一个分组低得多，所以每隔若干个预留循环过程就安排一次第五步操作较为合适。因此，一个典型的操作顺序就是一次、两次、或者三次的前四个步骤的循环过程，然后是第五步。第五步使用多少次可以通过试探法来确定。

五步预留协议试图通过一种高效、强壮方法使碰撞概率最小。在何时发送一个分组（即在哪个步骤），也就隐含了这个分组的含义。因此，一个分组只需由一个逻辑比特组成。一个分组可能与其他分组发生碰撞，但是在FPRP协议的上下文中总是可以推导出正确语义。根据各种分组的缺少/存在/碰撞（0/1/e）做出推断。一个分组除了需要一个逻辑比特外，不需要任何其他信息。这个逻辑比特必须足够长，以便接收机能够区别出0、1、e。若分组很小，则预留循环过程就非常紧凑。碰撞总是发生在距离发送节点一跳远的节点上，FPRP协议利用了这个事实。由在其上发生碰撞的节点来检测碰撞（不像CSMA/CA协议，发送节点检测在接收节点发生的碰撞），然后将碰撞通知发送节点，发送节点起着本地网络中心的作用。发送节点收集碰撞信息，并做出最终决策。在一个预留成功以前，不必向一跳远以外的节点派发信息，或者从这些节点收集信息，这使预留过程简化了很多。

五步预留协议有很多要素类似于其他现有MAC协议。前四个步骤类似于IEEE 802.11 MAC协议的RTS-CTS控制分组交互。第五步的撤销机制类似于HIPERLAN中采用的机制。每个撤销分组就是一个撤销一个比特的过程。识别0/1/e的能力是很多载波侦听协议的基本能力。在第一步，有必要区别0、1、e。在其他操作步骤，只需要确认是否为0。主要区别就是FPRP协议是一个同步协议，要求很严格的定时。

4.举例

现在举例说明在一个由10个节点组成的级联网络中进行FPRP协议五步操作的运行过程，如图3-2所示。

之前没有进行任何预留。说明一个五步操作过程、以及每个操作步骤中每个节点的发送情况。第一步，节点1、3、7发送预留申请分组RR。节点1和3发送的RR分组在节点2上发生碰撞，但是节点7发送的RR分组却成功到达其相邻节点（节点6和8）。第二步，节点2报告其上所发生的这个碰撞。节点1和3接收到节点2发送来的碰撞报告分组CR后立即意识到发生了碰撞，因而不再继续发送。节点4接收到第一步发送出来的一个RR分组，但是在第三步却没有接收到任何信息，则知道节点3发送的RR分组与另外某个节点发送的RR分组发生了碰撞。节点7没有接收到其相邻节点发送的任何碰撞报告分组CR，因而假设没有发生碰撞。所以，在第三步，节点7发送一个预留确认分组RC，通知节点6和8自己已经确认其预留。在第四步，节点6和8做出应答，回送预留应答分组RA。节点6和8回送的预留应答分组RA同时也通知与节点7相隔两跳远的节点5和9：已经成功完成一个预留，禁止节点5和9在随后的操作过程中再去竞争这个时隙。在第五步，节点7发送一个撤销分组EP。注意：在这个例子中没有死锁问题，所以这个撤销分组EP没有任何撤销对象。在实际中，在一个级联网络中，每条链路都是一座“桥梁”，所以很可能发生死锁。撤销过程在这类网络中非常重要。同时，在第五步，节点5和9发送打包分组PP，将这个最新成功预留通知节点7，因此允许节点4和10竞争。节点4和10通过调整自己的竞争概率在随后的操作过程中很可能竞争成功。

上面的例子清楚说明了FPRP协议的工作机理。然而，一个实际的MANET几乎不会呈现线性拓扑结构，很可能是“网状”结构。图3-3表示一个由16个节点组成的网状拓扑网络。使用这个例子的目的就是强调FPRP协议是并行操作协议。每个节点并行运行FPRP算法，能够在同一个网络中的不同区域同时做出多个预留。图3-3表明FPRP协议前四步的操作。在第一步（图3-3（a）），5个节点（1、4、5、11、15）发送预留申请分组RR。其中，节点4和5发送的预留申请分组RR在节点6上发生碰撞，节点6在下一步操作（图3-3（b））发送一个唯一的碰撞报告分组CR。这个碰撞报告分组CR拒绝节点4和5的预留申请。其余三个预留申请节点RN（1、11、15）因为没有接收到任何碰撞报告分组CR，所以在第三步操作中确认其预留，然后成为发送节点TN（图3-3（c））。在前三步操作中，使用圆表示各种分组的传输范围。从中可以看到：这些发送节点TN的传输范围不会重叠，即不会发生碰撞。在第四步操作（图3-3（d）），进一步将预留延伸到两跳范围内的所有节点。图3-3（d）中的封闭区域表示受到第四步操作发送影响的所有节点。

在图3-3所示的例子中，经过一个五步预留操作过程之后，节点1、11、15建立三个预留。这些节点相互之间的距离至少为三跳，不会相互干扰。在一个规模更大的网络中，在一个五步预留操作过程中会有更多节点做出预留，做出预留的节点数量与网络规模大小成正比。

将FPRP协议的操作概述如下：前四步操作用于建立预留和解决隐含终端问题；第五步预留操作执行打包和解决死锁问题，以便提高同一个时隙的空间复用效率和排除相邻节点之间可能存在的非脱网死锁。

5.FPRP协议的正确性

一次广播发送的分组只有被所有相邻节点正确接收的时候才算成功。一个节点不能同时接收多个发送节点发送的分组，也不能同时既发送分组又接收分组。一个节点接收到的一个分组只有是其正确地接收到的唯一一个分组，并且该节点没有同时进行发送的时候，才认为该节点成功地接收这个分组。把发生在一个没有进行发送的节点上的分组碰撞称为一类碰撞，而把发生在一个正在进行发送的节点上的分组碰撞称为二类碰撞。隐含节点问题是一类碰撞的一个特例。发送节点TN之间没有公共相邻节点的二类碰撞完全等同于死锁。

命题1：不可能发生一类碰撞。

证明：当有多个预留申请分组RR同时传输到达同一个节点的时候，如果该节点此时没在发送，那么该节点检测到碰撞，然后发送一个碰撞报告分组CR。所有相邻的预留申请节点RN都接收到这个碰撞报告分组CR，其中没有一个RN节点预留成功。如果某个发送节点TN是第一个成功做出预留的节点，那么两跳范围内的所有节点就会得到这个成功预留的通知（在第三步预留操作中对于一跳范围内的相邻节点，在第四步预留操作中对于两跳范围内的相邻节点）。这些相邻节点承认这个预留，并且不会在随后再去竞争这个时隙。所以一旦建立一个这样的预留，这个预留在其相邻区域内就是唯一的一个预留。可以得出结论：不存在两个发送在第三个节点上产生碰撞，即一类碰撞不可能发生。

命题2：二类碰撞的发生概率非常小。

证明：FPRP协议发生二类碰撞的概率非常小。节点不能同时进行发送和接收。碰撞检测机制依靠接收到两个预留申请分组RR的另外一个节点。在很多情况下，当两个相邻的预留申请节点RN发生碰撞（二类碰撞）的时候，各自发送的RR分组在其他某个节点（该节点已检测出一类碰撞）上发生碰撞。两个RN节点将接收到CR分组，预留申请失败。因此，总是能够解决伴随着一类碰撞的二类碰撞。在网状拓扑结构网络中，经常是两个相邻节点共享多个相邻节点，二类碰撞总是能够得到解决，此时不会发生死锁问题。

但是，如果两个相邻节点同时提出预留申请、并且没有公共相邻节点，那么这两个发送节点均不能发现碰撞，预留申请失败。如果其中一个发送节点TN是脱网节点，那么这个发送节点TN不会有非发送节点TN的相邻节点，在第四步预留操作中不会接收到预留应答分组RA，因而放弃其发送，死锁问题得到解决。对于不能按照这种方式解决的死锁问题，所有发送节点TN都预留同一个时隙。仿真实验表明，涉及两个以上节点的死锁非常少。很可能在一座“桥”上形成一个死锁（注：一座桥就是两个较大节点组之间的一条链路，这两个节点组在本地没有其他方式连接着。桥两端节点之间没有任何公共相邻节点）。当形成这样一个死锁的时候，相邻发送节点TN就会使用撤销分组尽力解决死锁问题。经过随后每一个撤销操作步骤（以及在第一步操作中的嵌入式撤销操作）后，死锁概率降低一半。仿真实验结果表明很可能在撤销操作过程（尤其是第一步操作中的嵌入式撤销过程）中解决死锁问题。基于这些结果，得到结论：二类碰撞的概率非常小，并且不会严重影响FPRP协议的性能。

6.图形添色与时隙分配

图形添色问题相当于TDMA广播时隙分配问题。图形添色问题包括给网络中的节点分配颜色，要求两跳远范围内任意两个节点不会分得相同的颜色。图形添色问题可以转换成如下的标准图形添色问题。给定一个图形G（V, E）（V是节点集，E是边集），如果把相隔两跳远的每个节点对连接起来，那么得到一张新图G′。图G′叫做源图G的“平方”（Square）。问题现在变成如何给图 G′添色，以便相邻节点之间不会分配到相同颜色。使用最少颜色给一张图添色的问题是全NP问题。RAND协议以一种贪婪方式随意地给节点添色。事实上，RAND算法已经用在很多信道分配方案中，其性能得到充分研究和证明。所以这里使用RAND算法作为一个基准点。把FPRP协议当作一个纯粹的图形添色协议（即给每个节点分配一个时隙或者一种颜色的协议），评估FPRP协议的性能。比较FPRP协议和RAND协议的性能。

随机拓扑的网络构建如下。对于一个具有N个节点的网络，N个节点分布在一个 N× N个单元的区域内。使用X、Y坐标统一分配方法，任意安排节点的位置。因此，网络的平均密度为每平方单元1个节点。单个节点的传输距离R的典型值选为1.5个单元。这样构建网络的目的就是为了能够独立改变网络的大小和单个节点的传输距离R（跟节点密度有关）。网络中每个节点的传输距离相同，建立的每条链路是双向链路。一个节点的平均密度大约等于7。将所构建的网络转变成一张非定向图G(V, E)，采用FPRP协议和RAND协议来给该图添色。在FPRP协议中，每个节点获得一种颜色之后，则停止竞争。在每个预留操作循环过程中，有些节点获得相应的颜色。重复运行预留操作循环过程，直到FPRP协议收敛为止，比如相同的颜色不能分配给图中任何其他的节点。按照同样方式分配下一种颜色。FPRP协议在每个节点都获得一种颜色之后停止运行。所需要的颜色种类数目就是添色（传输时间安排）质量的测量。

对大小从N=100到N=500的各种网络进行测试。对于所有这些网络，均使用R=1.5的传输距离。仿真结果见表3-1。DLB就是密度较低范围。构建一个100 个节点的网络，传输距离 R为1.0～3.0。随着相邻节点数量的增大，所使用颜色种类也相应增加，其结果见表3-2。FPRP协议和RAND协议的总体性能大致相当，只是比密度较低范围稍高一些。两个协议实质上都是随机添色过程，其运行也有些相似。值得注意的是：RAND算法采用集中方式解决问题，并且要求掌握全网范围内的信息，诸如节点已经分配了什么颜色（分配版本也有用，全网范围内的信息可以逐渐获得）；而FPRP协议是全分布式的、并行的，不需要任何事先的信息。这就使得FPRP协议更为适用，更能够在大规模移动Ad Hoc网络中实现。

3.2.2 基于竞争的访问

1.Rivest随机贝叶斯算法

FPRP协议需要合适的竞争策略。理论上，因为每个节点在一个预留帧内只发送一个分组，所以可以使用任何时隙化ALOHA策略作为竞争协议，竞争过程总是平稳的。但是，一个性能良好的竞争策略应该使预留过程快速收敛。绝大多数ALOHA协议都是为具有中心基站的网络开发的。MANET却与此不同。MANET是一种多跳网络，没有任何基站，网络中的每个节点都有可能是一个分组的源节点或者目的节点。对Rivest的随机贝叶斯广播算法进行修改，作为FPRP协议需要的竞争协议。

在Rivest的随机贝叶斯算法中，每个网络节点均要估计竞争节点的数量n，调整其竞争概率p:=1/n。在每个竞争时隙之后，节点根据其接收到的反馈信息更新其估计值n：

success or idle //成功或者空闲

n:=n−1

collision //碰撞

n:=n+(e−2)-1

将这个协议设计成既支持稳定的吞吐量，又具有最小时延。原始的Rivest随机贝叶斯算法在单跳ALOHA网络中表现得非常好。FPRP协议所处理的情况却不同，表现如下：①节点只关心其两跳范围内的竞争节点；②网络一般具有随机形状，每个网络节点具有不同数量的相邻节点；③每个网络节点在一个时隙内只发送一个分组；④在竞争某个特定时隙的过程中，如果一个节点竞争成功，那么该节点两跳范围内的所有其他节点不会再竞争这个时隙，但是将在其他时隙内重新进行竞争。为此，把Rivest算法转变成多跳随机贝叶斯算法，介绍如下。

2.多跳随机贝叶斯算法

一个节点估计其两跳范围内的竞争节点的数量n，计算其相应的竞争概率。将这些竞争节点称为“相邻竞争节点”。一个节点根据其接收到的信息更新其估计：

（1）成功（success）。一个节点A总是知道其两跳范围内的一个成功预留。若在节点A的一跳远处成功做出一个预留，那么节点A在第三步操作中将会得到相应通知（例如在图3-2中，节点6和8得到节点7成功预留的通知）；若在节点A的两跳远处成功做出一个预留，那么节点A在第四步操作中将会得到相应通知（图3-2中的节点5和9）。一个节点在打包阶段获悉三跳远处的一个最新成功预留（图3-2中的节点4和10）。

（2）空闲（idle）。如果在一个节点的两跳范围内没有竞争节点，那么该节点接收不到任何信息，因此假设该时隙是空闲时隙。空闲时隙总是能够检测出来的。

（3）碰撞（collision）。碰撞检测复杂得多。节点知道其一跳远处的竞争失败节点。一个节点若是接收到多个预留申请分组RR（图3-2中的节点2），则表示直接检测到一个碰撞。一个节点若是在FPRP协议的第一步操作中接收到一个预留申请分组RR，但是在第三步操作中没有接收到预留确认分组RC（图3-2中的节点4），则推断其一跳远处有一个竞争节点发送的预留申请分组RR已经发生了碰撞。一个节点若是在第一步操作中没有接收到预留申请分组RR，但是在第二步操作中接收到一个碰撞报告分组CR，则获悉其两跳远处的两个节点正在竞争，并且它们发送的预留申请分组RR在其中间的某个相邻节点上发生了碰撞。并不是总能够将两跳远处的碰撞检测出来。在图3-2所示的网络例子中，节点5不知道节点3在竞争、而且与节点1发生碰撞。当其中一个竞争节点相隔两跳远、同时其他竞争节点相隔三跳远或者四跳远的时候，就会发生检测不出两跳远处碰撞的情况。

一个节点若是获悉其两跳远范围内的一个成功预留，则停止在这个时隙的竞争，但是将继续在其他时隙竞争，从而引起相邻区内竞争节点数量的变化。为了维护稳定的吞吐量（成功率），节点必须维持两个估计：一个是两跳远范围内的竞争节点的数量 nc；另一个是两跳远范围内的需要预留、但是由于附近一个成功预留而不能在当前时隙中竞争的节点的数量 nb。采用一些参考常数来估计一个成功预留对附近竞争节点数量的影响。将一个成功预留对其相邻节点的的影响模拟如下：对于相隔一个成功预留一跳远的一个节点，停止在当前时隙竞争的那部分相邻竞争节点数量为 R1；对于相隔一个成功预留两跳远的一个节点，停止在当前时隙竞争的那部分相邻竞争节点数量为 R2；而对于相隔一个成功预留三跳远的一个节点，停止在当前时隙竞争的那部分相邻竞争节点数量为R3。随机贝叶斯算法变成：

（1）在一个预留时隙的开头，一个节点将其nc和nb复位如下：

nc:=nc+nb；nb:=0

（对于第一个预留时隙，nc:=nc0，这里nc0为预先确定的常数。）

（2）每当执行完一轮FPRP协议预留操作之后，若接收到：

            Idle //空闲
            nc:=nc-1
            collision //碰撞
            nc:=nc+(e-2)-1
            success if the success is some x hops away, where x is：//如果一个成功预留相隔x跳远，那么x等于
            zero://x=0, 节点本身就是一个成功预留节点
            done
            one： //x=1，节点不再在相同时隙内竞争
            nc:=nc-1
            nb:=nb+nc*R1
            nc:=nc*(1-R1)
            two：//x=2，节点不再在相同时隙内竞争
            nc:=nc-1
            nb:=nb+nc*R2
            nc:=nc*(1-R2)
            three：//x=3
            nb:=nb+nc*R3
            nc:=nc*(1-R3)

（3）然后，节点计算竞争概率 p:=1/nc。如果该节点能够在一轮FPRP协议预留操作过程中竞争，那么该节点就以概率p进行竞争。

需要指出的是：这只是一个启发式方案，不是最佳方案。即使是一个节点知道其两跳远范围内的活动竞争节点的确切数量nc，那么该节点的竞争概率p:=1/nc只有在其两跳远范围内的每个节点都以这个概率进行竞争的条件下才是最佳的。常常是，不同的节点有不同的 nc，每个节点基于其自己的nc来计算自己的竞争概率。R1、R2、R3可以通过Monte Carlo仿真来评估；或者在有些情况下，可以通过分析计算得到。但是，因为在一个相邻区域内竞争节点的数量不会增加，所以在竞争过程中的稳定性不是问题。

3.仿真结果

使用前面描述的图形添色过程来实现和测试上面描述的多跳随机贝叶斯算法，仿真网络与FPRP和RAND对比实验使用的仿真网络相同。通过Monte Carlo仿真来评估参数R1、R2、R3。在仿真中，R1=0.80，R2=0.60，R3=0.33。覆盖全部颜色所需要的FPRP协议五步预留操作循环次数表示FPRP协议做出预留的速度。网络节点数量N从100个到400个可变，传输距离均等于R=1.5。仿真100次，求仿真结果的平均值，如图3-4（a）和图3-4（b）所示。多跳随机贝叶斯算法平稳而快速地收敛。当网络从100个节点增大到400个节点的时候，所采用的FPRP协议预留操作循环次数（图3-4（a））稍有增加。更进一步的观察表明：FPRP协议预留操作循环次数随着网络规模的扩大而按照对数函数增加。总的FPRP协议预留操作循环次数就是对传输时间安排开销的测量，对于100、200、300、400个节点的网络分别为89、116、130、145次。由于呈对数增加的开销，FPRP协议具有可扩充性，适用于大规模网络。图3-4（b）表示每个时隙的发送节点数量，这个性能参数随着网络规模的扩大而相应增大。当运用网络规模标准化发送节点数量时，图3-4（b）中的所有曲线表现得极为相互一致。这就意味着这个传输时间安排的带宽效率（传输时间安排的质量）不会随着网络规模的变化而变化。

在仿真中，使用一个协调器来全程监视添色过程，以便确定所有节点都被添色完毕的时间。但是，在实际网络中使用这种协调器是不可行的。一旦已知网络拓扑（节点密度和传输距离），那么根据仿真预测必需多少个FPRP协议预留操作循环是可能的。给节点分配发送时隙所需要的平均FPRP协议预留操作循环次数位于4.2（N=100）和6.9（N=400）之间。从实验中发现：如果使用8个FPRP协议预留操作循环来分配所有21种颜色，那么每个网络节点获得其中一种颜色的概率大于0.99。可以将这些参数嵌入到FPRP协议中，使得FPRP协议的运行不需要协调。从网络节点观点来看，节点知道有多少颜色可以使用、哪个FPRP协议预留操作循环对应哪种颜色。节点简单地使用FPRP协议获取一种颜色。仿真实验也表明几乎从不发生非脱网死锁情况。绝大多数死锁都是通过撤销过程得到解决，剩余的碰撞概率大约等于0.001。FPRP协议的碰撞概率非常小，而且这个极小的碰撞概率对FPRP协议的性能不会产生重大影响。

3.2.3 节点移动的影响

1.节点移动

节点移动从两个方面影响FPRP协议。一方面是影响FPRP协议本身的操作。另一方面是影响FPRP协议做出的传输时间安排。从协议角度来看，对节点移动性的强适应能力或者要求协议具有一定的冗余度，以便在发生网络拓扑变化的时候协议还能正常发挥作用；或者要求协议的操作在没有采取特殊处理措施的条件下不会受到网络拓扑变化的重大影响。将对协议造成负面影响的节点移动的持续时间称为“敏感窗口”。敏感窗口越大，协议对节点移动性的适应能力越弱。对于需要收集全网拓扑信息的协议，敏感窗口非常大，所以协议在面临节点移动时很脆弱。FPRP协议的五步对话没有明确仔细考虑节点移动。FPRP协议的敏感窗口非常小，所以FPRP协议在面临节点移动时的适应能力相对较强。如果一个节点移动进入一个相邻区域，该相邻区域内正在进行一轮五步预留操作，那么该节点有可能失去碰撞检测的机会（注意：碰撞检测是在五步预留操作过程的前两个步骤中完成），并且在相应时隙内可能遭遇一次碰撞。但是，在一个预留操作循环中，节点移动产生的影响不会扩散和累积。在一个预留操作循环中，在作出传输时间安排的同时，完成探测相邻区域内的网络拓扑，这个网络拓扑信息不会传递到下一个预留操作循环中。在一个预留操作循环中探测到的网络拓扑信息总是最新的，没有过时的信息。连续的预留操作循环在碰撞检测方面各自独立，结果，FPRP协议的易受影响时间简单地等于一个预留操作循环的时间长度，所以FPRP协议的敏感窗口非常小。大多数节点在一个预留操作循环期间几乎不会移动，网络主要是静态的。因为相同的原因，参数 nb、nc的随机贝叶斯估计也不会受到节点移动的重大影响。据推测，FPRP协议产生由网络拓扑决定的传输时间安排，是移动性适应能力极强的协议之一。其他在计算节点传输时间安排之前需要全网或者相邻区域的网络拓扑信息和（或者）传输时间安排信息的协议，其敏感窗口大得多，对节点移动性的适应能力很弱。

一旦计算出一个由网络拓扑决定的传输时间安排，那么在更新该传输时间安排或者重新作出传输时间安排之前，该传输时间安排常常遭受网络拓扑变化的损坏。这个过程叫着传输时间安排的“老化”。可以用概率Pcrpt(ξ, t)来测量一个传输时间安排的移动性适应能力，Pcrpt(ξ, t)等于已安排在一个时隙内的发送在移动强度ξ条件下经过一定时间t之后被损坏的概率。因为每次发送都是一次广播，所以，如果发送节点一跳远范围内的任何一个节点不能正确接收广播分组，则认为这个发送被损坏。一般情况下，Pcrpt(ξ, t)随着节点移动强度(ξ )增大和观测时间（t）延长而增大。如果t等于一个信息时段的时间长度，那么每隔t秒产生一个传输时间安排，Pcrpt(ξ, t)等于一个发送在被重新安排之前被损坏的概率。Pcrpt(ξ, 0)等于一个已被安排的发送在FPRP协议完成其操作之后立即被损坏的概率，因此概率Pcrpt(ξ, 0)就是对FPRP协议强壮性（即对节点移动的适应能力）的测量。显然，传输时间安排更新越频繁，节点移动的影响就越小。这就是降低传输时间安排开销和降低损坏概率之间的折中。因为在大规模MANET中，FPRP协议产生广播传输时间安排非常快，所以较为频繁地执行FPRP协议。采用FPRP协议能够维持一个低损坏概率，同时又保持低开销的传输时间安排。

传输时间安排的“老化”过程是传输时间安排本身的一种特性，采用某种贪婪算法（greedy algorithm）产生的每个传输时间安排同样易受节点移动的影响。这是因为在时隙分配中，提高对节点移动的适应能力是以牺牲带宽效率为代价。因为使用贪婪算法时最前面几个时隙被过分使用，因此最前面几个时隙比后面的时隙更易于被损坏（图3-4（b）），所以可以采用贪婪算法平衡不同时隙内的发送节点数量。

2.仿真结果

仿真网络100个节点（N=100），开始的时候，每个节点随机分布在一个10 × 10封闭区域内。每个节点的传输距离R=1.5个单位长度。假设传输距离为1km，传输速率为1Mb/s。节点随机移动，节点移动到达边界线时调转方向重新朝网络区域内移动。

使用两种不同的移动模型，一种是布朗移动模型（Brownian Motion Model，BM），另一种是随机恒定速度移动模型（Randomized Constant Speed Movement Model，RCS）。在布朗移动模型下，每个节点在X和Y两个方向以每δ 秒h步的速度各自独立随机移动。组合效果就是一个节点每δ 秒以相同的概率从四个可能的方向（NE，NW，SE，SW）中随机选择一个方向，然后移动 步。移动速度 。比如一支具有数百辆坦克的大规模坦克部队朝同一个方向运动。坦克之间的相对运动类似于布朗运动。FPRP协议的最小时间单位就是一步操作的时间，δ等于一步操作的持续时间。估计δ=40μs，其中包括发送时间、传播时间、以及收发信机在发送方式和接收方式之间切换所需的时间。使用固定的运动模式和时间单元δ，则可以由节点移动速度S唯一地确定节点的移动。在RCS模型下，每个节点以恒定速度S朝随机选择的方向运动。一旦移动方向被确定，节点移动就是确定的。这类似于暂停时间等于0的随机点模型（Random Waypoint Model）。随机点模型对时隙分配算法性能的影响要比布朗移动模型严重得多。随机点模型对在一个大工作区域内移动的一组自治车辆进行模拟。对于BM和RCS模型，可以用移动速度S描述移动强度ξ，设ξ=S。图3-4（c）表示在BM移动模型下的仿真结果，图3-4（d）表示在RCS移动模型下的仿真结果。

从仿真结果中可以看到，FPRP协议本身的极强节点移动适应能力的移动范围很宽，而与所使用的移动模型无关。可以根据概率Pcrpt(ξ, 0)理解这个结果，Pcrpt(ξ, 0)等于一个传输时间安排产生之后一个时隙立即被损坏的概率。在两种移动模型（图3-4（c）和图3-4（d））下，Pcrpt(ξ, 0)对节点移动的敏感性相对较弱。而且，当网络变得较不稳定的时候，传输时间安排的效率（等于所分配的时隙数量）以及传输时间安排的开销（等于所使用的FPRP协议预留操作循环次数）大都保持不变。所分配的时隙平均等于16个，平均执行89个FPRP协议预留操作循环周期。这是因为FPRP协议有一个长度仅为200μs的敏感窗口（一个五步预留操作循环周期的时间），在89个循环中完成整个传输时间安排过程。在最糟糕情况下，第一个预留时隙到传输时间安排操作结束时已经“老化”了18ms（89个预留操作循环周期的时间）。如果重新安排和固定预留操作循环次数，那么估计只需150个预留操作循环周期（即30ms）。网络在30ms期间主要是静态的，节点移动对FPRP协议本身不会有多大影响。可以频繁执行FPRP协议，例如1s执行一次，以便保持传输时间安排足够新颖，同时又不会增加太多的开销（总带宽的3%）。

传输时间安排对移动模型的依赖性很强。在节点以恒定速度随机移动条件下传输时间安排被损坏的概率很可能高于在节点按照布朗移动条件下传输时间安排被损坏的概率。在RCS模型下，节点以10m/s的速度移动，经过0.5s和1s后，Pcrpt(ξ, t)大约分别等于0.02和0.03；而在BM模型下，节点同样以10m/s的速度移动，经过0.5s和1s后，Pcrpt(ξ, t)却小于0.002。当增大观测时间t时，在RCS模型下，传输时间安排损坏概率Pcrpt(ξ, t)增大得更快，很快增大得不能让人接受。在这种情况下，反复做出传输时间安排较为重要。RCS模型代表这种最坏情况，强制每秒钟更新一次传输时间安排。

3.2.4 时间同步问题

TDMA系统需要某种机制来维护时隙同步，以及提供足够的时隙间的保护时间，以便容忍发射机/接收机间相对位置不同带来的消息传播时延的不同。因为MANET没有中心基站，所以各个节点不能像蜂窝系统那样同步到一个公共引导信号上。但是，对于有些低比特速率到中等比特速率的无线网络，仍能能够实现时隙定时。

采用GPS提供的时间信号，军用级GPS在100ns RMS内实现时间同步，商用级GPS的同步时间是军用级GPS的若干倍。即使怀疑GPS的精确度，如果假设节点间的距离小于1km，那么对于9.6kb/s的低速系统，所需要的时隙间的保护时间（测量单位是比特）比1个比特时间小得多。因此，若只考虑保护时间，则很容易高效实现FPRP协议（注意：五步预留过程的每一步只需要发送一个逻辑比特）。如果比特速率增大到20Mb/s（比如无线ATM和未来的军用系统），那么保护时间增大到约60～70bit，但是在一个时隙内只发送一个逻辑比特却代价高得多。

关键的问题不是GPS的精确度，而是必须考虑信号传播时延之间的可能差异。保护时间相对于电台收发方式转换时间小得多。例如，IEEE 802.11规范要求电台收发方式转换时间为19ms，若采用20Mb/s的传输速率，那么19ms可以传输380bit（约等于保护时间的5倍）。随着技术的进步和发展，今后电台收发方式转换时间有可能接近保护时间。

尽管GPS能够提供全网精确定时，但是这种紧凑性的全网同步并不是绝对必需的。只要定时足够紧凑，满足相邻区域内的“相对”同步要求（相邻节点之间同步），则允许网络不同区域存在定时上的一定漂移。将这种同步称为“本地同步”，本地同步不同于“全网同步”。同步信号或者时间参考的漂移不是协议可实现性或者协议可扩展性的瓶颈。因此，节点间相互本地同步，节点在没有GPS定时信号的条件下进行操作是可行的。

3.2.5 干扰考虑

前面假定两个相邻节点间的通信链路是“无噪声对称信道”。实际情况并不是这样。各个发送节点互相干扰。将所有不需要的信号归入噪声。按照信噪比（Signal-to-Noise Ratio，SNR）测量信道质量。在FPRP协议中，节点可以测量SNR或者其与输入扩频码的相关能力，据此确定链路的质量，或者区分接收节点的空闲、成功、碰撞三种事件。

在FPRP协议中，为了实现较大的碰撞（干扰）检测范围，第一、二、四步操作采用的发射功率高于第三步操作采用的发射功率。在第一、二步操作中，检测出和报告可能发生的碰撞，RR的传输范围大于实际数据分组的传输范围，导致较多的申请节点申请失败。第三步操作的RC分组只采用正常功率（与实际数据分组的发送功率相同）发送。第四步操作又采用较高的功率发送RA分组，以便使较多相邻节点得到最近成功预留的通知，从而减少干扰。这对于有些确保有效防止同频干扰的电台技术可能是必需的。

在图3-3中，网络拓扑是理想拓扑，相当于数据分组发送功率的网络拓扑（与第三步的网络拓扑相同）。第一、二、四步的“干扰检测拓扑”稍微有点密（即平均节点密度较高），因而产生一张需要较多颜色（时隙）进行添色（安排传输时间）的图，也就是网络总吞吐量下降（由于发送节点之间的距离稍大一些），这对于确保没有同频干扰的发送是必需的。

3.2.6 FPRP协议的应用

迄今为止还没有给出节点为什么要竞争时隙的理由。这依赖网络特性及其高层协议。FPRP协议只提供节点做出TDMA广播时隙预留的方法。节点能够依据其自身的传输载荷来做出自己的预留。由此作出的TDMA传输时间安排可以用来发送用户产生的分组。也可以使用FPRP协议为网络控制信息发送做出广播预留。当进行网络控制操作或者网络重组的时候，广播传输时间安排非常有用。因为一个节点能够预留一个TDMA时隙，参与网络组织/控制操作过程，所以FPRP协议非常适合于支持分布式网络控制协议。FPRP协议特别适用于作为MANET中的初始信令信道，网络节点需要在这个信道上探测其相邻区域，以及交换连接和控制信息。FPRP协议不要求节点事先掌握有关网络的情况，因而适合充当“集合点”角色。在FPRP协议支持下，即使是不同种类的网络节点也能够相互结合在一起。

在MANET中，使用FPRP协议反复重新做出传输时间安排很方便。每当执行一次FPRP协议，丢弃现有的传输时间安排，接着从头开始重新做出一个传输时间安排。事实上，这不是唯一的解决方法。在有些情况下，逐渐地更新广播传输时间安排是可能的，比如只修改移动部分的传输时间安排。

可以将FPRP协议用于需要无冲突广播TDMA时间安排传输数据和控制的许多场合。FPRP协议的开销高于CSMA/CA协议，但是FPRP协议是一个非常值得努力实现和使用的协议。一旦FPRP协议作出传输时间安排，则在网络拓扑发生变化之前可以多次使用这个传输时间安排，而不需要像CSMA/CA协议那样针对每个分组进行信道获取操作。TDMA传输时间安排对于话音和多媒体传输更加重要，此时必须考虑时延和时延抖动。在MANET中，分组丢失的原因很多（节点移动、传输误码、链路中断、多址访问干扰等等），因此链路层和/或者传输层的可靠性机制对于保证所需的可靠性等级仍然是必需的。