TDMA 多跳网络多接口多信道设计资源优化分配方法*

王亚茜，毛建兵，田 爽，张 浪

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引言

多跳无线Ad Hoc 网络具备无中心、自组织的特点，无需架设固定的基础设施，可以快速铺开，自行完成网络的组建，具备较强的机动性、灵活性和抗毁性，可以广泛应用于战场通信、应急救灾通信等场景。

根据节点工作信道数的不同，无线Ad Hoc 网络MAC 协议可以分为单信道MAC 协议和多信道MAC 协议。随着无线Ad Hoc 网络用户容量、信息吞吐量等需求的不断提升，采用单信道设计越来越难以满足无线Ad Hoc 网络大规模、多样化业务互联的应用需求，而采用多信道是解决以上需求与性能之间矛盾的重要手段之一。但是，多信道的使用将带来更高的频谱占用消耗，不适用于无线频谱资源稀缺的场景。

多信道Ad Hoc 网络MAC 协议按节点配置接口数目的不同，可以分为单接口多信道MAC 协议和多接口多信道网络MAC 协议。单接口多信道MAC协议有基于跳频的多信道MAC 协议（Slotted Seeded Channel Hopping，SSCH）[1]和基于时隙划分的MAC 协议（Multi-channel MAC，MMAC）[2]等。采用多接口多信道技术，可以使得相邻节点选用不同的信道，从两个方面提高网络的理论吞吐量。一方面，多信道多接口可以使一个节点同时进行收发工作，而不是时分复用，以加倍节点的吞吐量；另一方面，利用多接口多信道可以通过给相邻节点分配不同的发送或接收信道，避免相邻节点的共信道干扰，消除隐藏节点和暴露节点问题，进而提高网络的吞吐量。多接口的使用虽然能提高多信道资源的利用率，但也会对硬件设计带来更高的要求，且成本较高。多接口多信道MAC 协议有动态信道分配（Dynamic Channel Assignment，DCA）协议[3]和基于主信道分配的MAC（Primary Channel Assignment based MAC，PCAM)协议[4]等。

信道资源调度控制是MAC 层设计的主要功能之一。目前，信道资源调度技术主要分为两类：一类是基于竞争的信道调度，如典型的带有冲突避免的载波侦听多路访问（Carrier Sense Multiple Access With Collision Avoidance，CSMA/CA）；另一类是基于分配的信道调度，如时分复用多址接入（Time Division Multiple Access，TDMA）。基于竞争的信道调度实现简单、可靠性高、扩展性好、便于分布式实现，也有研究将CSMA/CA 扩展应用到多接口多信道的无线Mesh 网络当中[5]。但是，基于CSMA/CA 的调度存在隐藏终端和暴露终端的问题，在多跳Ad Hoc 网络应用中因为其保守的设计而降低了网络吞吐量。基于TDMA 的信道调度在理想实现的条件下不会发生MAC 层冲突，因为每个节点所分配的时隙不会和它的干扰节点冲突。在业务流稳定的网络中，TDMA 调度能够获得更高的网络通信容量。此外，TDMA 方式采用的时分结构适合于有时延限制的传输，相关的接入公平性、流量控制及预留带宽等QoS 目标也更容易实现。目前，TDMA 作为一种有效的多址接入方式，广泛应用于无线Ad Hoc 网络中。

但是，TDMA 调度算法设计面临着诸多挑战，尤其是对多接口多信道的无线Ad Hoc 网络，尚无统一的协议标准。本文针对多接口多信道无线Ad Hoc 网络，提出一种基于TDMA 的分布式信道资源动态分配调度方法，适用于无线Ad Hoc 网络无中心、拓扑动态变化的情形。通过对信道资源采用面向节点和面向链路两者相结合的混合分配机制，在广播和单播数据传输的资源使用上更有针对性，提高了资源利用效率，以适应无线Ad Hoc 网络日益增大的网络规模和吞吐量需求。此外，作为多接口多信道网络的特例，算法设计同样支持接口数退化为一的单接口条件和信道数退化为一的单信道条件。

1 TDMA 信道帧结构

TDMA 信道帧结构如图1 所示，将时间按相等的帧长划分为一个个信道帧，每个信道帧又划分为L+M 个时隙，每个时隙根据信道的不同划分为多个时频资源。后面在不引起歧义的情况下，也将时频资源称之为时隙。

网络中的节点工作在一组正交的信道C0～Cn上，将这组正交的信道称之为信道集，信道C0同时兼任控制信道。信道帧中时隙由Beacon 信令时隙和Data 数据时隙组成。Beacon 时隙工作在信道C0上，Data 时隙工作在信道C0～Cn上。

接口使用方面，在Beacon 时隙所处时段节点一个接口固定工作在控制信道上，执行Beacon 时隙收发。该接口其余时段以及剩余接口可根据需要调度工作在任一信道上，执行Data 时隙收发。

网络中的节点唯一无冲突地预分配一个Beacon时隙，用于监听所有邻居和时隙的分配情况，同时用于分配Data 时隙进行数据发送和Data 时隙使用结束后的释放等。

图1 TDMA 信道帧结构

Data 时隙通过本节点占用的Beacon 时隙与邻居进行协商申请动态分配，并可在两跳外复用同一时隙。Data 时隙分配支持面向节点和面向链路的按需分配使用方式，用于节点通信有效载荷的发送，并在使用结束后被释放。

2 信道资源动态分配机制

2.1 分配策略

节点可以采用两种方式向其邻居节点传输数据分组。第一种方式为面向节点分配资源，并采用一个发射机向其所有的邻居广播传输一次。第二种方式为面向链路分配资源，传输节点只可向一个特定的邻居进行通信，其他节点可能无法保证其正确接收数据。面向节点的资源分配和传输特别适合于如地址解析和群组通告信息传输之类的广播应用，而面向链路的资源分配和传输则更有助于支持大数据量的点对点单播业务流的传输。在两跳邻域内，单一的面向节点分配策略只允许有一个激活的无线发射机，而单一的面向链路或两者混合的分配策略则可以激活多个发射机。如图2 所示，当节点1 在信道C1发送时，它的邻居节点需要做好接收准备，因此不允许节点1 两跳邻域内有节点在任何信道上以面向节点的方式激活发射机进行发送，但允许其两跳邻域内节点8、9 在另一信道C2上以面向链路的方式激活发射机进行发送。此外，当节点8 发送时，它的接收节点是节点7，与其他邻居节点无关，因此节点9 可以使用与之相同的信道在同一时间向别的节点进行发送。所以，本文的分配策略采取面向节点的分配+面向链路的分配两者相结合的混合分配策略，以分布式按需分配算法来实现TDMA 多跳网络应用中共存共享的广播和单播两类业务。

图2 面向节点和面向链路混合分配传输

2.2 分配原则

MAC 层信道资源管理区分统计节点广播以及到不同目的节点的单播业务量，节点根据统计的业务量大小或是QoS 业务流显示指定的带宽需求，对Data 时隙进行按需动态分配。

信道资源动态分配遵循以下原则：

（1）节点不能选择本节点或目的节点接口已使用的时隙；

（2）节点需要有空闲的接口调度工作在相应分配的时隙上进行发送或是接收；

（3）对特定时隙，节点不能选择目的节点和自己正在该时隙使用的信道集里的频率；

（4）对特定时隙，节点不能选择所有一跳邻居节点正在该时隙接收使用的信道集；

（5）对特定时隙，节点不能选择目的节点的所有一跳邻居节点正在该时隙发送使用的信道集。

（6）冲突避免原则如下：①对于不同的分配策略，遵循面向节点的时隙分配优先级高于面向链路的时隙分配的原则；②相同分配策略的时隙冲突采用hash 函数协调分配资源，以帧号/时隙号/频率号/节点ID 作为输入参数进行hash 计算，以hash 值最大/最小者取得竞争获胜，使不同的时频资源分配产生变化，提高信道资源使用的公平性。

针对单播方式的业务传输，算法为其分配面向链路的资源，目的节点为特定的接收节点；对于广播方式的业务传输，算法为其分配面向节点的资源，目的节点为其所有的一跳邻居节点。无论是面向链路还是面向节点的资源分配策略，算法设计都只需要遵从上述动态分配原则，即可同时实现两者混合的分配策略，只是两者对原则（1）、原则（3）和原则（5）中的目的节点定义不同而已。

2.3 资源申请流程

（1）在N-1 时帧，根据本节点到各个目的节点的业务速率和队列堆积情况，估计需要的Data 时隙数。广播业务作为一种到达特殊目的节点的业务，按相同的算法估计需要的时隙数。

（2）选择本节点、目的节点均有空闲的时隙，空闲定义等同于2.2 中原则（1）～原则（5）；广播发送节点需选择本节点、所有一跳邻居节点均有空闲的时隙。

（3）在N时帧将选择的时隙封装人Beacon 分组时隙申请域，发Beacon 通告。

（4）一跳邻居节点收齐N时帧Beacon 通告后进行冲突处理，并更新本地资源状态表。

（5）一跳邻居节点在N+1 时帧Beacon 分组中通告对申请的应答。

（6）本节点收齐N+1 时帧Beacon 通告后确认本节点对时隙的占用/退避情况，并更新本地的资源分配表。

（7）节点在N+2 时帧开始按照新的资源分配表占用相应时隙。

2.4 冲突调解流程

通过Beacon 时隙对Data 时隙进行申请时，因为Data 时隙采用“申请—应答—占用/退避”的过程进行分配，故这类冲突可通过应答阶段予以解决。冲突可以分为两种情况：一是时隙冲突，二是接口冲突。可以通过Beacon 分组的设计和一定的冲突调解算法进行完全的调解。

节点每帧发起或收到网络中其他节点发起的资源申请，节点每帧对每个时隙均动态记录以下4 个表项信息。

（1）本节点发送申请记录表ST，如表1 所示。

表1 本节点发送申请记录表ST

若本节点在某时隙、某信道发起申请，则该时隙、信道对应的表项标志置起。

（2）邻节点发送（目的节点为本节点）申请记录表NT1，如表2 所示。

表2 邻节点发送申请记录表NT1

本节点收到邻节点Beacon 消息中若邻节点发起发送申请且目的节点为本节点，则将该邻节点的节点号记录入其申请占用的时隙、信道对应的NT1表项中，同时该时隙、信道对应的NT1 表项的“申请邻居总数”加1。

（3）邻节点发送（目的节点不为本节点）申请记录表NT2。NT2 表与NT1 表类似，区别仅在于其记录目的节点不为本节点的邻节点发送申请。

（4）处理结果表PR，如表3 所示。

表3 处理结果表PR

本节点完成冲突处理后，若本节点在某时隙、信道收，则该时隙、信道对应的PR 表项的“本节点收状态标志”置起，同时在“本节点处理结果”记录源节点号。若本节点在某时隙、信道不收，“本节点收状态标志”不置起，“本节点处理结果”记录0。

节点根据上述表项记录的信息进行冲突处理，图3 为冲突处理的算法设计。

（1）初始化时隙号i=0；

（2）若i＜M（其中M为一个信道帧中的时隙数），则执行（3），否则冲突调解结束；

（3）初始化信道号j=0；

（4）若j＜C（其中C为信道数），则执行（5）；否则，i=i+1，并重新执行（2）；

图3 冲突处理算法设计

（5）若本节点在时隙i接口有剩余，则执行（6），否则处理结果表信道j至信道C-1 对应本节点收状态标志不置起，本节点处理结果置0，i=i+1，并重新执行（2）；

（6）若本节点在时隙i、信道j申请发送，执行（7），否则执行（8）；

（7）将本节点记录入时隙i的NT1 表中信道j对应表项，同时申请邻居总数相应加1，其中NT1 表包括邻节点发送且目的节点为本节点的申请记录；

（8）若时隙i的NT1 表中信道j对应申请邻居总数大于0，则执行（9），否则PR 表信道j对应本节点收状态标志不置起，本节点处理结果置0，j=j+1，并重新执行（4）；

（9）对NT1 和NT2 表中记录的所有邻节点的节点ID 计算hash 值，其中NT2 表包括邻节点发送且目的节点不为本节点的申请记录；对计算的hash值进行排序，将hash 值最大的节点ID 记录到处理结果表的本节点处理结果；

（10）若hash 值最大的节点为NT1 表中记录的节点且不为本节点，则执行（11），否则PR 表信道j 对应本节点收状态标志不置起，j=j+1，并重新执行（4）；

（11）PR 表信道j对应本节点收状态标志置起，本节点时隙i接口剩余数减1，j=j+1，并重新执行（4）。

2.5 资源释放流程

Data 时隙资源的释放分为主动释放和被动释放两种。

2.5.1 主动释放

主动释放分为3 种情形。

情形1：本节点空闲时隙释放，发起方为本节点，主动释放本节点占用的多余时隙，邻节点收到释放通告后，也将时隙的占用记录清除。流程如下：

（1）在N-1 时帧若节点存在需释放的空闲时隙，则选择待释放的时隙，更新本地维护的本节点时隙占用记录；

（2）在N时帧将选择释放的时隙封装入Beacon 分组时隙释放域，发Beacon 通告。

（3）邻节点收Beacon 通告，解析Beacon 分组中的时隙释放信息，更新本地维护的邻节点时隙占用记录。

情形2：邻居丢失时隙释放，节点标记某个邻节点占用了某些时隙，但该邻节点可能因为各种原因从本节点的邻居表中删除，此时本节点需要初始化本节点维护的该邻节点的资源占用记录，完成相应资源的释放。邻居丢失时隙释放发起方为本节点，主动释放丢失邻居占用的时隙，流程如下：

（1）在N时帧比较与N-1 时帧的邻居表，若发现某邻居丢失，设置等待超时时间为M个时帧。

（2）等待M个时帧，若该邻居未恢复，进入步骤（3），否则退出。

（3）释放标记邻节点占用的时隙。

情形3：本节点时隙内部协调，节点需要申请新的时隙进行业务发送，但节点到该业务的目的节点A 的可用时隙或接口资源已耗尽，而节点已占用的时隙数又高于两跳邻域内节点的平均时隙数时，根据节点当前已占用时隙情况，可释放部分用于向其他目的节点传输占用的资源，释放后的这些资源可用于节点向目的节点A 发送业务。本节点时隙内部协调发起方为本节点，本质上这些资源还是由本节点继续占用，只是从本节点的一个目的节点释放给另一个目的节点，因此只需再次对这些资源进行时隙申请通告。通告新的目的节点，这样旧的目的节点及其一跳邻居知晓旧的目的节点不再在这些时隙上接收，新的目的节点及其一跳邻居知晓新的目的节点将在这些时隙上接收，流程如下。

（1）在N-1 时帧选择要协调目的节点的时隙。

（2）在N时帧将选择协调时隙的相关信息封装入Beacon 分组时隙申请域，发送Beacon 通告。

（3）后续流程同2.3 资源申请流程（4）～（7）。

2.5.2 被动释放

被动释放发生在节点需要申请新的时隙进行业务发送，但节点到该业务的目的节点的时隙或接口资源已耗尽时，若节点占用的时隙数低于两跳邻域内节点的平均时隙数，则节点可以发起时隙释放申请，收到释放申请的节点被动释放相应时隙。被动释放流程发起方为本节点，邻节点收到释放通告后，被动释放占用的相应时隙。流程如下：

（1）选择要申请释放的时隙。

（2）将选择申请释放的时隙相关信息封装入Beacon 分组的时隙释放申请域，发送Beacon 通告。节点在发出释放申请的同时，也相当于发起了占用这些时隙的通告，称为时隙释放/占用。

（3）邻节点收到Beacon 通告，解析Beacon 分组中的时隙释放申请域，一方面要进行资源释放相关的操作，另一方面要进行时隙冲突检查和调解。

（4）如果邻节点在步骤（3）发现冲突，将冲突信息封装入Beacon 分组中的时隙申请应答域，发Beacon 通告。

（5）两跳邻节点收Beacon 通告，解析时隙申请应答域中通告的冲突信息，如有需要则进行退避。

3 仿真验证

利用MATLAB 平台对所设计的多接口多信道的信道资源动态分配方法对信道利用率、空间复用率、信道成功接入率、信道冲突概率以及网络一跳吞吐量等多个方面进行算法仿真分析，并对比本文提出方法所采取的混合分配策略与传统单一的面向节点或面向链路的分配策略相互之间的性能差异。

为了比较本文采取的混合分配策略与单一的面向节点或面向链路的分配策略相互之间的性能差异，在动态场景下对3 种策略进行仿真比较。为方便描述，3 种分配策略分别将其简称为策略A、策略B 和策略C，如表4 所示。

表4 动态分配策略简称

仿真参数设定如表5 所示。节点单播业务的目的接收节点随机在其一跳邻居中产生，广播业务的目的节点为其所有一跳邻居。

表5 网络仿真参数设定

初始仿真场景的网络拓扑形态如图4 所示。仿真过程中节点位置按照随机确定的方向不断移动，移动速率大小在范围60～100 km/h 内随机选取。仿真结果如图5 所示。

图4 仿真场景网络拓扑

图5 3 种分配策略仿真结果对比

对比结果可以看出，采用策略C，无论是在系统成功接入率、节点成功接入率，还是信道冲突概率方面，性能都优于另外两种分配策略。表6 给出了动态场景下仿真不同分配策略获得的关于平均系统成功接入率、平均节点成功接入率、平均信道冲突概率的统计平均值，也可得出相同的结论。

表6 不同策略部分指标对比

从图5 的仿真结果中看到，在信道利用率、空间复用率以及一跳吞吐量方面，策略B 面向链路的分配策略要高于策略C，这是因为策略B 将广播业务全部转化为单播业务进行发送，而面向链路的资源分配占用比面向节点的资源分配更高效，因此其信道利用率和空间复用率更高，且策略B 中节点每次数据发送都计入一跳吞吐量，使得其一跳吞吐量随之较高。实际应用中，广播业务被转化为到每个邻居节点的单播发送，其实际传输效率非常低，因此尽管策略B 有更高的一跳传输吞吐量，但其在广播/单播业务混合传输时的实际业务传输能力则较低。

4 结语

本文针对多接口多信道的无线Ad Hoc 网络，提出了一种基于TDMA 的分布式信道资源动态分配调度方法。提出的信道资源动态分配方法支持网络节点接口数及信道数的弹性可变，适用于无线Ad Hoc网络灵活多样的组网场景需求。从仿真结果来看，采用的信道资源面向节点和面向链路两者相结合的混合分配机制，在广播和单播数据分类传输的资源使用上更有针对性，提高了信道资源的利用效率。