基于TDMA支持实时应用的多跳时隙预留协议

陶 洋 ，乔会学，谭 鹏，罗启涵

(重庆邮电大学通信与信息工程学院，重庆400065)

AdHoc网络的分布式和自组织特性使得它的媒体接入控制(MAC)协议设计极具挑战性，时分多址接入(TDMA)技术在自由竞争的基础上通过对无线信道资源进行时隙划分，可以高效地利用有限的无线信道资源，目前，已经有许多基于TDMA的分布式MAC方案［1-3］。例如，五阶段预留协议(FPRP)需要5个阶段预留过程来完成TDMA时隙的分配［4］;E-TDMA协议需要节点为一跳范围内的邻居节点预留无冲突时隙，并利用预留时隙向邻居节点单播、多播、广播数据包［5］。在分布式分组预留多址接入(D-PRMA)协议中，节点分为传输语音和数据的节点，同时一个时隙被分为多个微时隙。但是，这些协议都不支持超过两跳的多跳实时数据包传输，同时，D-PRMA没有考虑节点的移动性，FPRP和E-TDMA只是限制性地考虑了节点移动性，FPRP假定节点在网络拓扑不发生变化的网络中移动，且要求节点移动速度非常慢，E-TDMA假定网络没有被分隔，如果在一个节点的通信范围内没有其他节点，该节点将会随机选择一个新的目的节点，并且强制性地移向这个节点。这在实际应用中很不实用，因此，本文提出一种MANET中支持实时应用的基于TDMA的时隙预留协议(TMSR)，TMSR为多跳数据包传输进行信道资源预留，同时，当一个节点丢失时，TMSR通过快速故障点检测和高效的资源释放机制来支持节点移动性。

1 TMSR协议

TMSR超帧结构，如图1所示，关于超帧的基本概念请参考文献［6］，在TMSR协议中，信道时间被分成多个超帧，每个超帧由3个主要部分组成，分别是beacon期(BP)、数据传输期(DTP)和时隙预留期(SRP)，每个超帧以BP开始，一个BP由m个竞争时隙和n个beacon时隙组成，节点加入网络，首先通过竞争时隙获得一个beacon时隙，一个竞争时隙包括1 byte的前同步码、6 byte的节点MAC地址、1 byte的beacon时隙索引(BSI)和4 byte的前向错误控制(FEC)域，其中，BSI是在BP期为节点分配的时隙号，如果一个节点被分配了beacon时隙，那么节点将在每个超级帧中传输其beacon。一个beacon时隙包括1 byte的前同步码，6 byte的节点MAC地址，112 byte(7 byte×16 neighbors)的一跳范围内邻居节点列表、32 byte的资源映射表和4 byte的前向错误控制(FEC)域，其中，节点一跳范围内的邻居节点列表由6 byte的节点MAC地址和1 byte的BSI组成，资源映射表显示DTP中处于激活的每个时隙的预留状态。节点根据它在beacon时隙监听的邻居节点的beacons更新它的邻居表和资源映射表。在节点被成功分配了beacon时隙后，当有数据需要传输时，节点首先在BP和DTP没有预留的时隙中，通过载波监听多路访问(CSMA)方式执行多跳信道时隙预留过程。如果在BP和DTP没有可用的时隙，节点将会在RRP中执行多跳时隙预留过程，最后，如果多跳信道预留过程完成，节点将会通过DTP预留的时隙进行数据传输。

图1 TMSR协议超帧结构图［6］

1.1 BP创建和beacon时隙分配过程

首先，本文假定每个节点保持全球时隙同步，因此，所有节点都知道每个超帧的起始时刻，节点为了能够被分配一个beacon时隙，首先将扫描至少一个超帧的beacons，如果在扫描过程中，没有接收到beacon，那么该节点将创建一个新的BP，并且发送第一个时隙中不是beacon时隙的其他beacon。然而，如果节点接收到来自邻近节点的beacon，它将启动beacon时隙分配过程，图2演示了节点E在竞争时隙数为2的条件下beacon时隙的分配过程。例如，假定有两个现存节点，节点C的BSI为3，节点B的BSI为4，初始时刻，因为节点B与节点E相距两跳，所以节点E不知道节点B的存在，但是通过所有节点的beacons广播(包含一跳范围内邻居列表)，节点E能够知道节点B的存在。其中斜体字母表示距离节点E两跳的节点。节点E在收到来自节点C的beacon后，发送一个BSI请求的原始beacon，节点从n个beacon时隙中随机地选择它的初始BSI，本例中，假定节点E选择的BSI为5，其中，原始beacon包括节点的MAC地址和BSI，原始beacon通过在竞争时隙中随机获得的时隙进行传输，如果节点E的邻居节点C能够成功地接收到来自节点E的原始beacon，那么节点C将发送它一跳邻居节点表中包含节点E的beacon，因此，当节点E监听到来自节点C的beacon，并且在多个超帧中，节点E的MAC地址被包含在节点C的beacon中，那么节点E将正式地发送它在第5个时隙中的beacon。

1.2 beacon 冲突

在TMSR协议中，多个节点周期性地发送beacon，当这些节点处于活动状态后，节点在beacon时隙分配过程中本地、独立地选择BSI，因为是本地分配的BSI，所以可能存在多个节点拥有相同的BSI，在静态网络环境，这种情况是没有影响的，但是，当具有相同BSI的多个节点定期或非定期地移动到网络中某个位置时，可能会产生beacon冲突。TMSR提出一个简单的规则来解决这个问题，节点通过利用来自邻居节点的beacon来检测beacon冲突，如果在多个超帧中，节点接收到来自邻居节点的beacon中都没有自身的MAC地址，节点就认为有一个或多个其他节点使用了与自己相同的BSI，因此，这个节点就会暂停它的beacon传输，并且如果该节点检测到它的beacon与其他节点的beacon产生重复的冲突，该节点将再次执行beacon时隙分配过程。尽管它的beacon传输被终止，但是，只要该节点能够接收到与既定流(如音、视频)相关的节点的beacon，该节点将继续进行数据传输，如果在beacon时隙分配过程中，该节点在多个超帧中都没有接收到与既定流相关的beacon，该节点将会释放与丢失节点相关的时隙。

图2 节点的信标时隙分配过程

1.3 多跳信道时隙预留

在TMSR中，节点在传输数据时，先进行多跳信道时隙预留，引入两个控制包，分别是预留请求(SREQ)和预留响应(SRES)，同时引入了专用术语，如表1所示。

如果源节点需要预定到目的节点的时隙，它将广播初始跃点计数设置为0的SREQ包，SREQ包的转发信息包括源节点地址、目的节点地址、预约尺寸和跃点计数。当节点接收到新的SREQ包时，将检测接收到的SREQ包中的跃点计数是否比跳数最大值小，如果不满足此条件，节点将丢弃接收到的SREQ包。如果满足此条件，节点将创建包含到源节点路径信息的反向路径表，反向路径表由源节点地址、目的节点地址和SRES包单播到的下一跳节点地址组成，在创建了反向路径表之后，中间节点转发SREQ包给它的邻居节点，同时对跃点计数加1。同时，中间节点和目的节点可能收到同一媒体流的SREQ包的多个副本，这些节点选择第一个到达节点的MAC地址作为目的节点，这些节点将以反向路径发送SRES包给最先到达的节点。在TMSR协议中，实际上多跳信道时隙预留在传输RRES包的反向路径上执行。

表1 专用术语对照表

下面通过一个例子对多跳信道时隙预留术语进行说明，图3中，考虑了这样一个场景，目的节点d，源节点s和中间节点i，其中1≤i≤n，n表示与特定流相关的中间节点数目，如果节点接收到一个目的节点地址是自己的MAC地址的REQ包，该节点将创建一个反向路径表，同时由于所有的节点不仅知道自己的资源映射表，而且通过beacon还知道一跳范围内邻居节点的资源映射表，所以，目的节点d将在中间节点i和目的节点d的资源映射表中搜索和预留常用的非预约时隙，对于被目的节点预留的时隙，中间节点i将变成TN，目的节点变成RN，在TMSR中，它们被叫做一对预留对。作为TN预留的时隙包括源节点地址、目的节点地址、TN的MAC地址和单播的数据包的下一跳地址等信息，同时，作为RN预留的时隙包括源节点地址、目的节点地址、将要转发数据包节点的MAC地址和RN的MAC地址等信息。在成功预留时隙后，目的节点将向源节点发送SRES包。其中SRES包包含由源节点地址、目的节点地址、选定的时隙索引和单播SRES包的下一跳节点地址组成的前向转发信息。

图3 多跳信道时隙预留术语示意图

算法1是针对源节点/中间节点的多跳信道时隙预留，算法描述(伪代码)具体如下:

//其前提要求:

a1:当中间节点1接收到来自节点2的RRES包时，中间节点1将检测在其与源节点S之间是否有常用的非预留时隙。

a2:当中间节点i-1接收到来自中间节点i的RRES包时，中间节点i-1将检查其与节点i-2之间是否有常用的非预留时隙。

a1，a2={AVAILABLE or NOT_AVAILABLE}

1:if i=1 then

2:根据选定的时隙索引，源节点将为它与作为TN的中间节点1之间的通信预留时隙。

3:源节点s在预留时隙内开始发送数据。

4:else if i=2 then

5:根据选定的时隙索引，中间节点1将为它与作为TN的中间节点2之间的通信预留时隙。

6:if a1=AVAILABLE then

7:中间节点1为源节点与作为RN的自己之间的通信预留时隙。

8:中间节点1向源节点s发送带有选定时隙索引的RRES包。

9:else

10:不做任何操作

11:end if

12:else if2 ＜i＜n，then

13:根据选定的时隙索引，中间节点i-1为其与中间节点i之间的通信预留时隙，自己作为TN。

14:if a2=AVAILABLE then

15:中间节点i-1为其与中间节点i-2之间的通信预留时隙

自己作为RN.

16:中间节点i-1向中间节点i-2发送带有选定时隙索引的RRES包。

17:else

18:不做任何操作

19:end if

20:end if

算法1中，展示了中间节点或源节点接收到来自中间节点i的SRES包时执行多跳信道时隙预留过程。当中间节点或源节点接收到下一跳节点地址是自己MAC地址的SRES包时调用算法1，算法中，当中间节点作为RN预留时隙时，中间节点将优先预留接收到的SRES包中选定时隙索引左边的时隙，这样使SRES包在通过多跳链路的超帧中变得连续有序。

图4中，演示了在有1个源节点、2个中间节点和1个目的节点的场景中多跳信道时隙预留过程。

图4 TMSR协议多跳时隙预留过程示意图

1.4 故障节点检测

TMSR故障点检测的基本思想是利用beacon，当节点接收到来自一跳范围内邻居节点的beacon时，它将创建邻居列表，并且将邻居的资源映射表保存到内存中，当有节点移开时，节点将根据检测阈值来决定是否继续维持关于离开节点的数据流。如果节点通过检测阈值决定不再维持丢失节点的流，那么该节点将释放所有与丢失节点相关的预约时隙，而其他与丢失节点相关的节点将会在达到生存期后释放它们的预约时隙，在没有任何包传输的情况下，信道时隙释放过程依次蔓延到整个网络，在节点释放预留时隙过程中，如果流的源节点地址是自己的MAC地址时，该节点将再次发送SREQ包。

2 性能仿真

2.1 TMSR协议的实现

通过NS2实现TMSR协议，一个超帧由272个时隙组成，包括6个竞争时隙、90个beacon时隙、160个数据时隙和16个信道资源预留时隙，假设每20 ms产生一个语音包，超帧中预留空间大小至少为4，表1列出了TMSR的仿真参数。

2.2 仿真场景

假设网络中有25个节点随机分布在1 km×1 km的方形区域内，节点的传输范围是150 m，考虑了10种不同的网络拓扑，每个场景有两个不同的流量模式，仿真结果取它们的平均值，其中节点按照随机行走移动模型在网络内移动，考虑了速度为v1=0 m/s，v2=4 m/s，v3=8 m/s三个移动场景，其中v1=0 m/s表示静态网络，v2=4 m/s，v3=8 m/s表示节点以在0～v之间的速度在网络内移动。为了性能评价，考虑了以下性能参数，一个是平均端到端时延，其中端到端时延是目的节点接收到包的时间与源节点发送包的时间的差值，另一个是平均吞吐量，其中吞吐量是成功接收到的包的数量与网络中传输的包的数量的比值。

表1 仿真参数

2.3 仿真结果

首先讨论单跳场景的仿真结果，为了验证TMSR协议的性能，对使用TMSR协议和使用E-TDMA协议的单跳场景的仿真结果进行比较，然后，对使用TMRR协议的多跳场景的仿真结果进行分析，因为E-TDMA不支持多跳场景，所以没有考虑在多跳场景中使用E-TDMA协议的情况。

图5和图6是在不同流量负载和节点移动速度下，TMSR协议和E-TDMA协议的平均端到端时延和平均吞吐量仿真图。当网络流量负载比较轻时，这两个协议都传输了几乎所有的包，在静态网络环境中，初始时，TMSR的平均端到端时延略高于E-TDMA的平均端到端时延，直到传输的数据包达到105个时，这种情况才发送改变，这是因为所有的TMSR节点经历了BP和SRP这两个阶段的固定时间延迟，此外，在执行时隙预留的过程中，目的节点随机选择DTP的后半部分作为预约点，因此，根据目的节点选择哪部分作为预留点，也会造成不同的额外时延。尽管TMSR起始阶段经历了一段时延，但是随着数据流量的增加，TMSR在包吞吐量和时延方面的性能都优于ETDMA。

图7是多跳场景中TMSR协议的平均端到端时延仿真图，在多跳场景中，本文评估了在流量恒定时，由于节点移动而引起TMSR协议性能的变化，仿真开始时，由于许多节点同时预留信道时隙，所以使得TMSR的平均端到端时延显著增加，而随着TMSR网络趋于稳定，平均端到端时延开始下降。在饱和点，语音包的平均端到端时延小于250 ms，满足表2中所列出的实时业务多跳端到端时延要求。

图5 单跳场景下平均端到端时延

图6 单跳场景下平均吞吐量

图7 多跳条件下平均端到端时延

表2 多跳端到端时延要求

3 结论

为了支持实时应用，本文提出了一种新的MANET中的TMSR MAC协议，尽管节点由于BP和SRP都经历了固定的时延，但是，TMSR节点的平均端到端时延都满足节点在静态和移动环境中多跳端到端时延要求，因此，提出的TMSR协议可以应用在MANET中以支持实时应用。

［1］JURDAK R，LOPES C V，BALDI P.A survey，classification，and comparative analysis of medium access control protocols for Ad Hoc networks［J］.IEEE Communications Surveys and Tutorials，2004，6(1):2-16.

［2］BRATEN L E，VOLDHAUG J E，OVSTHUYS K.Medium access for a military narrowband wireless ad-hoc network;requirements and initial approaches［C］//Proc.MILCOM 2008.San Diego:IEEE Press，2008:1-7.

［3］DJUKIC P，MOHAPATRA P.Soft-TDMAC:a software TDMA-based MAC over commodity 802.11 hardware［C］//Proc.INFOCOM 2009，［S.l.］:IEEE Press，2009:1836-1844.

［4］ZHU C，CORSON M S.A five-phase reservation protocol(FPRP)for Mobile Ad Hoc networks［C］//Proc.17th Annual Joint Conf.IEEE Comp.and Commun.Societies.［S.l.］:IEEE Press，1998:322-331.

［5］ZHU C，CORSON M S.An evolutionary-TDMA scheduling protocol(ETDMA)for mobile ad hoc networks［R］.［S.l.］:The University of Maryland，2000.

［6］WiMedia Alliance.Distributed Medium Access Control(MAC)for Wireless Networks［EB/OL］.［2013-07-12］.http://www.wimedia.org/en/docs/091819r01aWM_BOD-only-Specification_1.5.pdf.

［7］DJUKIC P，MOHAPATRA P.Soft-tdmac:a software-based 802.11overlay tdma mac with microsecond synchronization［J］.IEEE Trans.Mobile Computing，2012，11(3):478-491.

［8］陶洋，张询.MANET中的高准确度地址冲突检测算法［J］.计算机工程，2009，35(5):94-96.