一种改进的Ad hoc网络中动态TDMA时隙分配方法

解放军理工大学通信工程学院研三队 王宝康

总参谋部第61研究所 陈 强

1.引言

Ad hoc网络是一种不依赖基础设施的网络，网络中的节点均是有移动主机构成，它们可以在没有提前配置的情况下自由进出网络，这种灵活性促使了相应MAC协议的开发，我们根据他们的发送机制可以将其划分为两大类。

第一类MAC协议是基于竞争的协议，基于载波侦听/冲突避免（CSMA/CA）的IEEE 802.11协议就是常见的第一类协议。虽然它被广泛应用，但是它基于竞争的机制使得预约带宽难以实现。

第二类MAC协议是没有竞争的协议，如时分多址（Time division multiple access）协议，每个节点预先都被安排了一系列时隙用于满足发送要求，同时较好的适合Qos（Quality of service）要求。但是，即便是知道了准确详尽的信息也很难提出一种最优的时隙分配机制。在前期提出的一些协议中，节点依靠提前定义的网络信息逐个进行时隙预约分配，结果是这些协议本身对网络拓扑依赖较大，如果网络拓扑和带宽需求动态变化的话，则会导致无用时隙的急剧增加。

因此，本文提出一种新的TDMA时隙分配协议来克服上述这些缺点，我们的协议不需要提前知道网络的信息，而且根据竞争区域内节点数量和带宽需求的变化动态的改变帧长和发送机制，这里竞争区域指的是对于每个节点，两跳之内的节点的集合。

2.USAP和FPRP简介

USAP，即统一时隙分配协议（Unifying slot assignment protocol）和五阶段预约协议（five-phase reservation protocol）是两种传统的第二类MAC协议。前者由戴维·杨提出，目前在TDMA中大量使用。图1是TDMA在USAP中的形式，它由N个帧组成，每帧由M个时隙组成，M和N都是定值。每个帧的第一个时隙用于描述该传送节点的控制信息包，叫做NMOP(节点管理操作信息包)。这样,统一分配时隙协议USAP允N个节点存在于网络中，每个节点拥有相应的NMOP(节点管理操作信息包)，这N个帧组成一个循环。

节点间通过一系列的信息交换使每个节点了解存在的未分配时隙的状态并在其中为自己分配一个时隙使用。因为每个节点收到一个新节点管理操作信息包NMOP时都会刷新自己的统一时隙分配协议USAP，所以统一时隙分配协议可以反映出网络内节点的存在状况。

图2给出了FPRP协议的帧格式，帧中有一个由一系列信息帧IF（Information frames）组成的预约帧RF（Reservation frames），每个信息帧IF内有N个信息时隙IS（Information slots），每个RF内又有N个预约时隙RS（Reservation slots），每个RS和相应的IS相对应。如果一个节点要预约IS，则首先竞争相应的RS。一个RS由M个预约循环RC（Reservation cycle）组成，每个RC由五个阶段的对话组成，通过这五阶段对话竞争节点和其邻居节点完成预约。

有上述可以看出，无论USAP还是FPRP，网络的主要参数例如节点数N和时隙数M都需提前知道，这在实际的Ad hoc网络中不易实现，因为Ad hoc网络最大的特点就是其动态变化这点，因此有必要提出一种新的TDMA时隙分配协议，能够根据节点数目动态的调整这些参数的方法。

3.E-DTSAP协议

3.1 简介

E-DTSAP协议，即改进的TDMA时隙分配协议（Evolutionary-dynamic TDMA slot assignment protocol），它可以让节点随着网络拓扑结构的变化相应的对时隙进行重新分配。在此协议中，所有节点地位平等，通过这种方式，E-DTSAP允许存在同时预约的现象。如果由于拓扑结构变化使得冲突发生，那么发送者从接收者那里得知消息并停止在此时隙的发送。同时，如果有必要，可以对其他未分配的时隙进行预约。发送完成后，发送者释放被分配的时隙，此时隙又可以被其他节点预约。

图1 USAP下的TDMA时隙示意图[4]

图2 FPRP协议帧格式

图3 E-DTSAP的帧格式

图4 数据包格式

图5 控制包格式

图6 初始状态下时隙分配过程

图7 发送状态下时隙分配过程

图8 吞吐量(T)、发送时延(Delay)与D的关系

3.2 帧格式

如图3所示，在此协议中，帧长被设置为2的幂次数长度，其中第一个时隙预留给新节点用于发送控制报文来完成时隙分配请求，因此，在此时隙内不发送任何数据。M是一个正整数，每个时隙都包含4个子时隙（Minislot），同时，minislot 0和minislot 1又可以进一步被划分为两个控制域，即RTS和CTS。这些控制域用来完成预约未分配时隙和防止隐藏终端冲突。如果一个节点在其分配的时隙内有数据要发送，则首先应当通过minislot 0中的RTS和CTS与对应的接收节点完成握手，当握手过程完成后，节点在相应时隙的DATA子时隙内发送数据包，同时在同一时隙等待数据ACK回应。如果任何节点在时隙的minislot 0时隙都感知信道是空闲的，那么此时隙被标记为未分配时隙，可以被预约。当一个节点想要预约未分配时隙时，首先应当通过RTS的minislot 1向对应的接收节点发送时隙预约请求，如果接受者成功接收到这个请求，它通过同一时隙的CTS域向发送者回复预约认证信息。只有当节点在minislot 1内竞争成功后，DATA子时隙才可以用于发送数据，并且在后继帧中的相同时隙都可以预约给此节点直至包发送完成。

3.3 包格式

在E-DTSAP中有两种数据包，发送包和控制包，不同的方式对应不同的节点运行。在发送状态下，如果有必要，节点发送数据包和控制包通过预约未分配时隙用于重新安排时隙分配，另一方面，新节点在初始状态通过发送控制包以获得足够的信息从而完成时隙分配。数据包的形式如下：

如图4所示，数据包包括数据形式、发送者ID、目的ID、时隙分配信息及发送节点及其邻居最大帧长和数据。

在E-DTSAP中，总共有12种控制包类型，每种包都有不同的作用，如图5：

请求包只有新节点发送，通过向邻居发送此包，新节点请求竞争区域内所有节点的关于帧长和时隙分配的信息；时隙信息包包含所有信息；时隙预约包同样由新节点发送，通过发送此包给邻居，新节点通知其他节点预约的帧长和时隙信息；回复包是为了作为接收时隙预约包的确认；时隙保持包由保持被分配时隙且没有包要发送的节点发送；RTS包由需要发送包的节点通过minislot 0中的RTS域来发送；CTS包由相应的接收节点作为发送包接收请求的回应通过相同子时隙的CTS域发送。当此握手过程完成后，节点在DATA微时隙发送相应的数据包，在ACK微时隙发送相应的ACK包作为接收包的确认信息；当节点需要预约未分配时隙时，在minislot 1的RTS域发送时隙重分配包，同理在相应的接收节点会发送ACK包作为收到包的确认信息。

3.4 时隙分配

传统的第二类MAC协议需要提前知道网络信息，当网路拓扑动态变化时，在初始状态下进行的时隙分配并不是一直保持有效，而E-DTSAP协议中，不仅在初始状态下而且在发送状态下时隙分配都能随网络参数的变化做出相应的调整从而适应网络变化。

如图6中所示，如果一个新节点需要加入网络，它需要知道竞争区域内其他节点的帧长和时隙分配的信息。为了得到这些信息，新节点首先需要侦听信道并且检查从邻居节点发送的数据包，在收集到这些信息后，新节点就知道了竞争区域内一帧中的最大帧长及第一个时隙的位置，然后，新节点在下一帧的第一个时隙广播发送一个请求包并且等待所有接收到此包的邻居节点发送时隙信息包。

在接收时隙信息包之前，新节点应当通过minislot 0的RTS和CTS域来完成握手过程，如果没有冲突发生，在收集到所有邻居的时隙信息包后，新节点开始进行时隙分配过程，如果有冲突，新节点回到载波侦听阶段，此过程一致重复知道新节点从所有邻居那收集到时隙信息包为止。

当新节点开始时隙分配时，它首先将它的帧长设置为竞争区域内最大帧长，这里，F0表示新节点的帧长，由于新节点知道竞争区域内时隙分配的全部信息，因此它可以实现无冲突时隙分配。如果一个邻居的帧长与新节点帧长相同，均为F0，则新节点复制接收到的时隙信息包中的内容，如果F0=αFi，其中Fi为邻居的帧长，α为一个2的幂次数的整数，那么新节点每隔F0/α时隙重复复制时隙分配信息，通过这种方法，新节点将所有来自邻居节点的信息融合起来并且形成自己的时隙分配表。

此时，如果在时隙分配表中有未分配的时隙存在，那么新节点将预约其中的一个给自己使用；如果没有发现未分配的时隙，新节点检查竞争区域内的节点，是否有一个节点占有多个时隙的情况，如果有，则占有时隙较多的那个节点被要求释放一个时隙给新节点使用，如果以上两种情况均未出现，则新节点需将帧长加倍，如前所述，由于第一个节点不分配给任何节点，因此，在加倍后，后半部分的第一个时隙将为空时隙，可以被分配给新节点使用。

在完成时隙分配后，新节点想邻居节点广播分送一个时隙预约包，接收到此包的邻居节点发送相应的回复包。在接收回复包之前，新节点需要与邻居节点通过mi-nislot 0的RTS和CTS域完成握手。如果没有冲突，在收集了所有回复包之后，新节点完成它的时隙分配并准备发送数据；如果存在冲突，新节点回到载波侦听阶段，此过程重复直至新节点完成自己的时隙分配。

如图7所示，在完成时隙分配后，新节点准备在自己的时隙内发送数据，在一个分配时隙的初始，首先应当判断是否存在数据包要发送，如果有数据包需要发送，则应当在minislot 0的RTS和CTS域与接收节点完成握手，当此过程完成后，节点在被分配的时隙内的DATA子时隙发送数据包，接收到数据包的节点在同一时隙的ACK微时隙发送数据ACK包作为回应，如果没有接收到ACK包，则发送者不得不重新进行时隙分配并释放当前时隙。

在未分配时隙初始，发送者估计网络拓扑和自己的带宽需求，如果发现信道是空闲的并且需要预约时隙时，应当通过mi-nislot 1的RTS域发送时隙重分配包，相应的接收者收到此包后在CTS域发送一个ACK作为回应，在接收到ACK后，发送者进行时隙分配并通过DATA子时隙发送数据，否则，发送者返回等待状态并保持原来的时隙分配状态。

4.仿真分析

这里，我们将本协议与传统的第二类MAC协议及802.11协议做了对比，在仿真环境中，我们假设网络中有50个节点，节点通信采用CBR，目的节点在邻居中随机选择，我们观察了平均吞吐量及发送延迟与D的关系，其中D表示的是节点的邻居节点的最大数目。

由图八（1）的结果我们得知，随着D的不断变化，E-DTSAP协议的吞吐量在各个阶段都明显高于其余协议，这与设计目的一致。同时，随着D的增加，平均吞吐量降到一定值（大约0.02），而且E-DTSAP的下降比较平滑，这是因为越来越多的邻居节点将会导致更多的干扰和更少的分配时隙；图八（2）显示出E-DTSAP协议相比其余协议，有最低的发送时延；在随D变化过程中，D越大，将导致更多的干扰和越来越少的分配时隙，因此，发送时延几乎呈线性增长。

5.结束语

本文中，我们提出了一种改进的动态TDMA时隙分配协议，它可以根据竞争区域内节点数目动态改变帧长和发送机制，而且我们的协议不需要提前知道网络的信息，通过与邻居节点的信息进行相互通知和认证来完成时隙预约。它可以很好的适应于实际的Ad hoc网络。

[1]郝莉,陈彦辉,张彪.一种适于Ad hoc网的改进型TDMA协议[J].北京电子科技学院学报,2005.

[2]Wei Li,Ji-Bo Wei,Shan Wang.Dynamic TDMA Slot Assignment Protocol for multihop ad hoc networks,Communication Technology,2006.

[3]C.D.Young.USAP:a unifying dynamic distributed multichannel TDMA slot assignment protocol,in Proc.IEEE MILCOM’96,1996,235-239.

[4]杨棣,梁刚.在Ad hoc网络中的动态TDMA时隙分配[J].电子科技,2009,11.

[5]Chenxi Zhu and M.S.Corson.A Five-Phase Reservation Protocol(FPRP)for Mobile Ad hoc Networks,in Proc.IEEE INFOCOM’98,1998,322-331.

[6]Kanzaki A,et al,Dynamic TDMA Slot Assignment in Ad hoc Networks,in Proc.IEEE AINA’03,2003,300-335.

[7]郑少仁,王海涛,赵志峰等.Ad Hoc网络技术[M].北京:人民邮电出版社,2005.