3.4 混合时分多址访问（HTDMA）协议

混合时分多址访问（Hybrid TDMA，HTDMA）协议是竞争协议（载波侦听多址访问与碰撞回避CSMA/CA协议、虚拟载波侦听RTS/CTS协议）和分配协议（TDMA）的混合协议，是增强型TDMA（Evolutionay TDMA，E-TDMA）协议的衍生版。

3.4.1 HTDMA传输时间安排的基本设计考虑

无线信道很容易支持广播通信。当一个节点使用全向天线发送一个分组时，该分组很容易到达其无线电波传输覆盖范围内的每一个节点。如果这个分组是到达某个接收节点的唯一一个分组，那么这次发送就是成功的，而且接收节点本身在这同一时间是不能发送的。若采用TDMA访问技术，则一个节点不能既发送分组，同时又接收另外的分组，而且在一个时间内不能接收两个或者两个以上的分组。从发送节点一方来看，如果不考虑俘获效应，那么发送节点正在向其某个一跳相邻节点发送分组的时候，同时也正在阻止其所有其他一跳相邻节点从其他节点接收信息；从接收节点一方来看，成功接收分组意味着禁止其所有一跳相邻节点尤其是预定发送节点发送分组。在多跳网络中，像这样的时间安排必须慎重对待，因为两跳远的、不能相互直接通信的节点之间可能发生碰撞（“隐含节点”碰撞）。

依据分组的预定接收节点数目，传输分成单目标传输、多目标传输、广播传输，这三种传输类型表示的接收节点数目分别为发送节点周围一跳远范围内的一个、多个、全部相邻节点。多目标传输可以被看成为通用情况，它是一个子集，子集中的元素就是作为接收节点的位于发送节点周围一跳范围内的各个相邻节点。单目标传输、广播传输都是多目标传输（通用传输）的特例。单目标传输就是只有一个元素的子集，广播传输就是包含所有元素的子集。在实际MANET中出现的传输要求常常是单目标、多目标、广播三种传输的混合体，多数数据传输很可能是单目标传输和多目标传输，而把广播传输用于网络控制和网络管理。不同的节点对带宽的要求可能是差距很大的。一个节点应该能够保留不同的带宽数量，可以使用不同的传输类型。

对于移动网络，带宽效率最佳的时间安排可能不是最好的。带宽效率最佳的时间安排的空间复用程度最高，但是冗余度最低。因此带宽效率最佳的时间安排是非常脆弱的，而且很容易被干扰而变坏。当节点移动的时候，网络拓扑发生变化，时间安排中可能发生碰撞，即使在当初做出这种时间安排的时候不会产生碰撞。时间安排还需要容纳带宽要求方面的变化。当原传输会晤结束、而新传输会晤开始的时候，应该迅速将带宽从结束的会晤中释放出来，并分配给新的会晤。所有这些变化，包括网络拓扑和网络传输两个方面，都要求能够频繁修改传输时间安排。这就被称着为时间安排“维护”。因为需要非常频繁地维护时间安排，所以时间安排维护必须是低开销而高效的。与其他类型的网络相比，MANET在带宽和计算能力方面都是有限的。要求用来做出和维护传输时间安排的通信开销和计算开销需要尽可能的低。简单的方法是，在网络发生变化的时候将原先的传输时间安排彻底推翻，然后重新做出一个新的传输时间安排，这种方法显然是不适合的。尽管一个新的传输时间安排反映了最新的网络拓扑和带宽要求，而且安排得很有效率，但是做出这种传输时间安排很可能是开销非常高，而且有点多余，特别是当现有传输时间安排中一小部分过时而其余仍然有效的时候。比较合适的解决办法是，现有的传输时间安排尽可能多地被保留。只有由于节点移动或者带宽要求变化而变得过时了的那部分传输时间安排才会被修改。如果两次更新之间的间隔足够短，那么只有一小部分现有的传输时间安排必须被修改。与重新做出整个传输时间安排的方法相比较，这种方法更为经济。由于MANET的动态特性，所以优先考虑分布式协议。这对于强调网络效率和强壮性是非常重要的。传输时间安排过程不该依赖于某个特定的节点。一个实际网络在大小和拓扑方面的动态性可能是非常强的。在一个大区域内，当节点移动到一起或者疏散开来的时候，节点密度的变化可能非常剧烈。网络可能被分割，当网络发生分割的时候，每个分隔出来的部分应该作为一个较小的网络而自行运行工作。这就要求协议是可扩展的。例如，网络作为一个大网络或者作为一个小网络时，应该能够运行得同样良好。

为了快速做出或者更新传输时间安排，我们应该利用本地传输特性。从一个节点传输到该节点的一跳相邻节点，要影响该节点两跳远以内的节点。节点知道其两跳远以内所有节点的传输情况就足够做出没有冲突的传输时间安排。相互分隔远的节点可以单独做出其传输时间安排。这就使得可能在本地的基础上来设计做出传输时间安排的协议。联合竞争和预留的混合协议使用竞争来做出预留，因此排除了节点轮流等待预留时隙的需求。因为竞争只涉及附近的节点，所以这类混合些协议是可扩展的。当网络很大、传输时间安排必须频繁更新的时候，竞争是有用的。在这些苛求的要求下，迅速做出无碰撞的传输时间安排比花费时间做出一个高效率的传输时间安排更为重要。

HTDMA的目的不是做出带宽效率最佳的传输时间安排，而是基于局部网络信息，按照全分布式、并行方式尽可能快地做出和维护没有碰撞的传输时间安排。

3.4.2 HTDMA时间安排协议

HTDMA协议允许节点在网络结构和带宽需求发生变化的时候为这些节点分配TDMA传输时隙。HTDMA协议同时做出两个TDMA时间安排，每个时间安排用于不同的目的和同一个信道的不同部分。第一个时间安排是竞争时间安排，由一个相对较长的时隙组成，分成四个时间片：第一个时间片是随机等待时间，用于避免许多节点在同一时刻同时进行发送；第二个时间片是时隙请求时间，用于发送RTS时隙请求分组；第三个时间片是时隙应答时间，用于传输CTS时隙应答分组；第四个时间片用于广播传输时间安排更新，本时间片不是必需的。竞争时间安排用于各个节点竞争所需的若干个时隙，所以被称着竞争时间安排（contend_schedule）。第二个时间安排用于用户信息的传输，所以被称着用户信息时间安排（UserInfo_schedule），由N个长度均等于 Tslot的时隙组成。这里的所有预留都是一跳预留。在用户信息时间安排中，一个节点能够按需地向其相邻节点中的单个、多个、所有目标发送信息而预留不等的带宽数量（时隙个数）。用户信息时间安排和竞争时间安排都反映了网络的拓扑结构。而且，当网络拓扑和带宽需求变化的时候，这些时间安排相应地被做出调整，以便维护没有碰撞的传输。

使用HTDMA协议的时候，所有网络节点平等参与传输时间安排的制定过程。做出传输时间安排的过程同时在整个网络中进行。节点不用按照某种顺序等待为其传输而做出时间安排。节点通过竞争许可方式来决定哪些节点能够预留传输时隙，很多节点能够同时获得这种许可并且做出其传输时间安排。这就降低了开销，同时提高了强壮性。每个节点负责其自己的传输时间安排。一个节点能够预留一个没有碰撞的时隙，用于向其一组相邻节点进行发送。如果由于网络中某些拓扑变化而使得另一个发送引起其中某个接收节点开始遭受碰撞，那么该发送节点就能够从这个接收节点获知这种碰撞情况，然后停止在该时隙内的发送。如果需要的话，该发送节点能够预留另一个时隙。发送完成之后，发送节点释放该时隙，该时隙可以被预留为另一个发送。节点只需要与其一跳相邻节点交换信息。

1.HTDMA时隙状态定义

关于HTDMA，节点ni在给定时隙s内的活动表示为（state(s)，target(s)），这里state表示该节点在时隙s内的活动，target表示由该节点的一跳相邻节点组成的子集，该节点向该子集发送信息或者从该节点子集中接收信息。在无碰撞TDMA传输要求的限制下，节点ni在时隙s内的活动可以被分成以下几种状态：

（1）向一个相邻节点子集R发送：（state(s)=Trans，target(s)=R）。如果这个发送是广播，那么target(s)=Broadcast；

（2）从一个相邻节点接收nj：（state(s)=Recv，target(s)=nj）。对于这种情况|target(s)|=1；

如果一个节点在时隙s内既没有发送，也没有接收，那么该节点就处于以下状态中的某一种：（1）由于至少一个相邻节点在接收另一个节点的信息而且没有一个相邻节点发送的发送阻塞：（state(s)=Block_t）；

（2）由于至少一个相邻节点在向另一个节点发送而且没有一个相邻节点接收的接收阻塞：（state(s)=Block_r）；

（3）由于至少一个相邻节点正在接收的发送阻塞和由于至少一个相邻节点正在发送的接收阻塞：（state(s)=Block_tr）；

（4）希望从某个相邻节点接收的时候，却正在经历碰撞：（state(s)=Collision）；

（5）空闲，时隙s内没有任何相邻节点发送或者接收：（state(s)=Idle）。

注意target域只是为Trans和Recv两种状态定义的。对于其他的状态，target域是没有意义的。处在非发送中的任何时隙都被称着被动时隙。

每个节点维护一张时隙状态列表，该表纪录了该节点的所有相邻节点以及所有相邻节点的相邻节点的时隙状态。每个节点根据其时隙状态列表为高层服务做出时隙分配。

2.HTDMA的帧结构

HTDMA协议将信道分成两个组成部分：①竞争时段，HTDMA协议在该时段竞争所需时隙和更新传输时间安排；②用户信息时段，在该时段内传输用户数据。这两个时段交替工作。HTDMA协议的帧结构如图3-11所示。信息时段由N个信息帧（N个时隙传输N个分组）组成。在N个时隙中，其中连续K（K<N）个时隙可以重新组成一个大的时隙，用于传输一个大分组。在一个用户信息时隙内，一个节点按照用户信息时间安排向其相邻节点发送或者接收一个分组（或者一个分组的一部分）。一个节点在用户信息时间安排中需要多少个时隙、在一个时隙内的传输需要选址那些相邻节点取决于该节点正在进行的传输的类型和数量，并且可能是时变的。HTDMA协议通过周期性地更新用户信息时间安排来满足这些传输要求。用户信息时间安排在竞争时段内被更新。在一个竞争时段内完成两个功能：时隙竞争功能和时隙分配功能。

在竞争时段内，节点通过使用RTS/CTS控制分组交互，完成对自己所需时隙及其数量的竞争和分配。在竞争时段内，每个节点在启动RTS/CTS控制分组交互进程之前，首先必须等待一段随机确定的时间，以便减少碰撞的机会。

3.HTDMA的详细操作

在HTDMA协议中，每个节点均做出和维护其自己的传输时间安排，以便于与其相邻节点共同协调工作。整个网络的传输时间安排就是所有节点的传输时间安排的简单组合。单个节点不需要全网络范围内的全网信息，比如网络大小、所有网络节点及其传输时间安排。节点只与其一跳相邻节点直接发生关系。对于一个给定的节点，两跳远以外的其他节点如果与该节点同时在一个相同的时隙内同时发送，那么有可能产生干扰，但是这种干扰或者碰撞发生在一跳远范围内的相邻节点中。节点知道其一跳远范围内的相邻节点的传输时间安排，因而间接知道其两跳远范围内的相邻节点的传输时间安排。这种方法是能够避免碰撞的。例如，假设节点n1和n2分别为节点n0的一跳相邻节点和两跳相邻节点。如果节点n2预留一个时隙用于向节点n1发送，那么由于节点n0获悉节点n1在该时隙上接收节点n2发送的信息，所以节点n0间接知道节点n2的发送情况。因此节点n0将避免在这个相同时隙内发送，以避免碰撞。两跳远范围内的相邻节点的发送信息被嵌入在一跳远范围内的相邻节点的传输时间安排内，两跳远范围以外的节点不必直接进行发送信息交互。一个节点不必也不需要两跳远范围以外的节点的任何信息。节点周期性地在竞争时段内交换其传输时间安排。节点将其相邻节点信息保存在一张相邻节点列表NB里。节点通过跟踪其相邻节点及其传输时间安排，就知道哪些时隙正在使用、哪些时隙可以使用，并运用这些信息预留其新的时隙。很多节点能够同时预留其发送时隙。

当传输时间安排被更新的时候，它们总是在现有的传输时间安排的基础上被更新。一个预留只有在发送完成之后或者遭遇碰撞的时候才会被释放，一个预留不会为了提供一个新的预留而被释放。只有在不会与前面已建立的所有预留产生碰撞的时候，才能够做出一个新的预留。最后得到的传输时间安排随着网络拓扑变化、传输方式的变化而变化。

1）时隙的分配

节点接收到高层的时隙请求服务的时候，根据其时隙状态列表，初步为其做出时间安排（即选出时隙），并把其封装到RTS控制分组中，然后把RTS控制分组广播出去，等待该RTS控制分组的预定接收节点回送的CTS控制分组。接收方接收到RTS控制分组之后，根据自己的时隙状态列表，对该RTS控制分组中提出的时隙请求进行确认：①如果完全认可时隙请求，则根据认可的时隙请求修改自己的时隙状态列表，接着做出时隙请求认可应答；②如果部分认可，则根据部分认可的时隙请求修改自己的时隙状态列表，接着做出时隙请求部分认可应答；③如果完全拒绝时隙请求，则做出时隙请求拒绝应答；④如果没有接收到时隙请求RTS控制分组，则不会做出任何响应。RTS控制分组发送节点根据其预定接收节点回送的CTS控制分组应答进行处理：①如果是时隙请求认可应答，则正式确定前面初步做出的时间安排，更新其时隙状态列表，再把这个更新广播出去，本次时隙请求/本跳时隙请求成功完成；②如果是时隙请求部分认可，则根据认可部分重新做出时间安排，更新其时隙状态列表，再把这个更新广播出去，然后通知上层本次时隙请求只能得到部分满足；③如果是时隙请求拒绝应答，则仍然需要重新做出时间安排（否定前面初步做出的传输时间安排），更新其时隙状态列表，再把这个更新广播出去，然后通知上层本次时隙请求完全失败，结束本次时隙请求操作；④如果在规定的超时时间内没有接收到预定接收节点回送的CTS控制分组应答，则认为本次时隙请求遇到碰撞，仍然需要重新做出时间安排（否定前面初步做出的传输时间安排），更新其时隙状态列表，再把这个更新广播出去，从而本次时隙请求失败，然后等待在下一个周期内重新进行时隙请求，重复进行的次数规定为R次（R<∞）。

在控制分组、自组织包、用户数据分组中都安排有时隙信息。一个节点每当接收到一个这样的分组的时候，也就接收到相应节点发送来的传输时间安排的部分信息或者全部信息，该节点基于所收到的这些信息对自己的传输时间安排做出调整，更新其时隙状态列表。如果时隙状态列表中某个相邻节点的内容有一段时间没有被更新，那么该节点就被认为已经移动离开了（或者关机了），其内容被删除。当一个节点接收到其他节点的传输时间安排的时候，在前面描述的一个时隙的可能的状态中，最为重要的状态就是Trans和Recv两种状态。

一个节点停止在某个时隙的发送就是释放它以前已经预留而不再需要的某个时隙。一个节点在以下条件下可以释放用户信息时间安排中的某个（或者某几个）信息时隙：①该节点向预定接收节点的发送已经完成；②该节点已经获知其发送正在与某个接收节点发生碰撞（通过接收到该节点广播出来的传输时间安排而获知）。为了释放时隙 s，节点只需简单地依据其相邻节点的状态将该时隙的状态从Trans状态改变到被动状态中的某一种状态，然后把这种更新了的传输时间安排向外广播出去，其相邻节点也就被通知了这种更新。与这个发送所对应的一个接收节点接收到这个广播后，就知道发送节点已经释放了该时隙，因此停止在该时隙的接收。一个被释放的时隙可以被预留为后面的另一个发送。

预留一个新时隙比释放一个时隙复杂，需要更加细心，因为这个预留可能产生碰撞。一个节点接收到其所有一跳相邻节点广播出来的传输时间更新信息后，也就知道了它们的传输时间安排，然后可以基于这些最新的信息选择其新的传输时隙。如果需要的话，该节点可以根据其传输要求（比如单目标传输、多目标传输、广播传输），在用户信息时间安排中预留信息时隙。如果节点ni希望预留一个时隙用于向相邻节点nj发送，那么当接收节点nj处于Idle或者Block_t状态、并且发送节点ni本身处于Idle或者Block_r状态的时候，那么发送节点ni选择时隙s。如果有多个时隙符合这个规则，那么发送节点从中任意选择一个时隙。节点将其新的预留合并到其传输时间安排里，然后将这个更新了的传输时间安排广播到其相邻节点。接收节点接收到这个新传输时间安排后，将其相应时隙的状态改变为Recv状态。这样就建立了一个预留。随后发送节点就可以在该时隙上发送信息帧，直到发送节点释放该节点为止。

2）时隙的竞争

在前面的时隙分配过程中，提到了RTS、CTS两个控制分组。这两个控制分组均携带有时间安排（时隙预留）信息，其作用有两个方面：一方面是用于发送节点和接收节点相互进行时隙分配的协商和调整；另一方面是用于与发送节点周围的所有相邻节点、接收节点周围的所有相邻节点竞争时隙。竞争的作用就是发送节点与其周围一跳和两跳远范围内的所有相邻节点竞争时隙的发送权，接收节点与其周围一跳和两跳远范围内的所有相邻节点竞争时隙的接收权。

一个节点（发送节点）在竞争时段经过一段随机确定的等待时间之后，如果CSMA侦听到信道此时没有发送，则向外发送一个RTS控制分组。在发送节点周围的所有节点经过CSMA侦听到已经存在发送之后，将停止其发送（如果有发送，则退避到下一个竞争时段），接收到该RTS控制分组之后，重新安排其传输时间，更新其时隙状态列表。

RTS控制分组的预定接收节点接收到RTS控制分组后，根据其时隙状态列表，生成CTS时隙请求应答分组，再把该CTS控制分组广播出去。接收节点周围的所有相邻节点接收到该CTS控制分组之后，重新安排其传输时间，更新其时隙状态列表。如图3-12所示。

3.4.3 HTDMA的碰撞分析

当节点ni希望选找一个时隙来给一个接收节点集 R（R⊆NB）发送的时候，如果该节点知道其所有一跳相邻节点的当前传输时间安排，那么该节点在如下条件下就能够挑选一个时隙s：当该节点处于Idle状态或者Block_r状态时，并且每个节点nj∈R的状态或者为Idle或者为Block_t。接收节点能够成功接收，因为对于它们在这个相同的时隙内没有其他一跳相邻节点正在发送（否则的话，这些节点的状态或者为Recv、或者为Block_r、或者为Block_tr）。这个发送也能够到达该发送节点的其他一跳相邻节点（NB∩），但是这个发送不会干扰这些节点。如果产生这样的干扰，那么这些节点中至少有一个节点nj∈NB∩正在从其他源接收（Recv），节点ni的状态应该是Block_t（或者Block_tr）。但是，节点ni处于Idle状态或者Block_r状态，因此产生一个碰撞。所以，如果节点ni知道其所有一跳相邻节点的最新传输时间安排，那么该节点就能够挑选一个时隙用来向这些相邻节点中的一个（或者多个、或者全部）发送。这个发送不会与正在进行中的发送产生碰撞。

当节点开始移动的时候，在这些传输时间安排中就可能产生碰撞，即使在开始做出的传输时间安排是没有碰撞的。但是，用了HTDMA协议，这些碰撞就不会持续太久。对于在同一个时隙s内的两个发送（ni→nj）和（nk→nl），如果节点ni朝着接近节点nl的方向移动，然后成为了其一跳远范围内的节点，那么在节点nl上产生碰撞，如图3-13所示。现在两个分组，一个来自节点ni，另一个来自节点nk，在同一个时隙s内到达节点nl，那么节点nl开始经历一个碰撞。当发生这种情况的时候，节点nl不能接收到事先安排和预定好的当前这个分组，所以节点nl判定发生了碰撞，因而将自己信息时段中的时隙s的状态改变为碰撞（Collision）。当节点nl在下一个竞争时段中广播自己新的传输时间安排的时候，节点ni和节点nk都从节点nl接收到这个最新的传输时间安排。（对于节点ni，节点nl是一个新的相邻节点，并且被加入到节点ni的相邻节点列表NB。）当这两个节点基于这个新近接收到的信息更新其自己的传输时间安排的时候，节点nk停止发送，因为节点nk的接收节点正在一个碰撞中。在时隙s中，如果节点nj没有碰撞，那么节点ni可能继续向节点nj发送，方法就是在下一个竞争时段解决节点nl的碰撞问题。所以一次碰撞持续的最长时间为一个竞争时段与一个信息时段之和。

当一个节点由于碰撞丢失一个时隙的时候，该节点会在下一个竞争时段中努力预留另一个时隙，或者通知碰撞源停止在该时隙的发送。为了缩短碰撞的持续时间，需要经常更新传输时间安排。当一个节点加电开机的时候，如果其附近已经有正在工作的其他节点，那么该节点通过接收这些节点向外广播的传输时间安排，就能够知道这些相邻节点的传输时间安排，并且建立其自己的相邻节点列表NB。传输时间安排的更新速度决定HTDMA协议处理网络移动性的好坏程度。

通过维护一跳相邻节点列表NB，HTDMA协议在MAC层提供了一种相邻节点选找机制，从而有可能简化某些情况下的路由算法。例如，节点ni需要一条到达节点nj的路由，节点nj是节点ni的一个两跳远范围内的相邻节点，并且通过节点ni的一个一跳相邻节点nk可达，所以节点ni能够直接使用路由ni→nk→nj。这样就不需要针对节点nj进行路由寻找。

由于HTDMA协议的本地特性，所以HTDMA协议对网络大小反应迟钝，也不会受到网络分割的影响。HTDMA适用于大型的、同类的、大小变化的网络。