移动Ad Hoc网络由于抗毁性和分布式等特点，得到了越来越广泛的应用，不断有新的MAC协议被提出，以适应不同的应用环境。动态时隙混合类协议（HTDMA）[1]一般先通过碰撞回避[2]、虚拟载波监听[3]等方式探测网络的局部拓扑信息，据此接入新节点，同时保留现有节点的传输安排，这种方式降低了大量的竞争开销，更易为Ad Hoc网络提供QoS保障。国内外已提出多种动态时隙混合类TDMA协议。在参考文献[4]中提出一种集总式消除冲突的HTDMA协议——CCS-QR协议，它在一个控制时隙内将多个发射节点的接入请求集中处理，从而预约多个数据分组，之后再根据酬金类优先级算法和接入顺序分配数据时隙。它具有平均时延小、吞吐量稳定等优点，很适合为实时业务提供QoS保障，但却不能完全支持分布式运行。这类问题还广泛存在于非耦合式HTDMA协议中[5]。

1 分布式运行约束条件
    在CCS-QR协议中,控制时隙只完成虚拟载波监听，并不为节点分配数据时隙,这种完全解耦的业务关系，减少了很多控制开销。但其带来另一个问题是，如果不提前发送时隙分配表，在数据时隙内由各节点根据优先级确定发送次序，则节点之间就不能相互协调地发送数据分组，就会引发冲突。
    CCS-QR协议的数据时隙如图1所示，结合图2，例如在第1个数据时隙内，两跳范围内业务①②③会同时发送，而相互冲突导致失败。原因是分布式网络结构下，节点覆盖范围有限，无法得到所有节点的业务信息，所以每个节点所维持的预约序列都不相同[6]。

   式(4)中的第一个约束条件表示一个时帧内节点至少分配一个时隙，第二个约束条件表示相距一跳的节点不能分配同一时隙，第三个约束条件表示两个节点与同一节点相距一跳时不能分配同一时隙。以上说明，如果要满足目标函数，无冲突发送数据，则必须保证相距两跳范围内的节点分配不同的时隙。
2 分布式队列运行机制与分析
    本文针对解耦关系的HTDMA，提出一种自协调分布式运行解决方案。下面对图2所示的网络模型和CCS-QR协议[4]进行分析和说明。
    在图2中，网络由14个节点组成，实线表示两个节点在对方覆盖范围内，箭头表示两个节点已在信令时隙完成数据时隙的预约，序号表示节点发送RTS/CTS分组的顺序，为了简化模型，省略了CCS-QR协议里优先级的表达。
2.1业务管理树算法原理
    定义1：各个发射节点将所有两跳范围内的发送业务排成预约队列，称为不完全队列,用Ci={ci-a,ci-b…ci}表示，Li为不完全队列的长度。
    定义2：根据协议安排，把控制时隙里允许接入的最大业务量按照优先级或接入次序进行排队，称之为完全队列，用Call={c1,c2…cn}表示，Lall为完全队列的长度。
    定义3：设Ci为节点i的不完全队列，Ni为节点i在Ci中的序号，每当Ci中的一个节点发送了相应的数据业务，有Li=Li-1，则称使Li=Ni-1的节点为节点i的业务触发节点，其相应的数据业务称为触发业务，将此时节点i的业务称为待发业务。
    定义4：将所有发送业务按照预约顺序的方向排成队列，该队列会从触发业务和待发业务处产生树形结构，称它为业务管理树，其模型如图3。业务管理树的长度Lall等于所有业务发送完毕所需时隙的个数。

    当某个业务同时作为两个预约队列中不同节点的触发业务时，业务树将产生分支结构，分支点位于当前业务之后，即某两个待发业务之前；当不同分支的两个节点同时作为某个业务的触发业务时，业务树将产生汇聚结构，汇聚点位于当前业务之前。
    业务树出现分支意味着将有多个子序列同时发送数据，而业务树的汇聚表示在某个节点接入信道前，其预约队列中同时有多个节点发送了数据。
    前面已经通过数学模型论证，协议只需要将发射节点两跳范围之内的业务进行协调就可以防止此类冲突的发生。而两跳之内的节点必处于同一业务树分支当中，业务树中不同分支上的节点至少相距两跳以上，不在同一分支的节点可以同时隙发送业务,发送次序为Li。
2.2 算法描述

    一个业务管理树运行过程面向业务序列，而不是节点。具体工作过程为：
    (1)收集发射状态（Collection  Phase）：在控制时隙，通过对所有RTS分组和对应CTS分组的监听，接收节点将所有相邻发射节点纳入自身队列，发射节点也将相应接收节点的所有相邻发射节点纳入自身队列。大多数HTDMA协议都能满足此条件。
    (2)接入顺序表达（Sequence Phase）：此阶段，依据协议里优先级设置和节点的接入次序为每项业务分配权重，即发送次序，并由此产生一个相同的完全队列，包含所有业务信息。
　(3)队列形成（Establishing Phase）：在此阶段，节点依据已得到两跳范围内其他节点的发射状态来形成不完全预约队列，这个队列只关心发送次序在自己之前的业务。
　(4)确认发送次序（Approval Phase）：根据业务管理树算法，得到不完全队列的补集，并将自身不完全队列接入自己的触发节点，业务将在不同分支间并行传输，而业务在不完全队列中的次序即为发送次序。
2.3 算例分析
　经过队列调整后，各节点的预约队列分别如表1所示。在此为了便于说明，队列中业务序列按其序号排列。

 3.1 吞吐量分析
    图6显示了不同网络负载下三种协议的吞吐量变化曲线。从图中可以看出,CSMA/CA协议网络吞吐量较低，这是由于竞争接入产生冲突所导致；而CCT—QR协议基于预留方式分配资源，产生的冲突很小，且控制开销不大，所以网络吞吐量较高；DCT—QR协议由于消除了CCT—QR协议数据时隙内的冲突，所以吞吐量更高且更稳定。但由于接入容量有限，所以在网络载荷增多的情况下，吞吐量会出现饱和。

    本文提出了解决Ad Hoc网络非耦合HTDMA协议分布式运行冲突的自协调式的业务管理树算法，通过举例分析和仿真实验可以看出，该算法能够达到预期效果。但这种算法在复杂网络环境下，会增加分组时延，这将是下一步研究工作的重点。
参考文献
[1] Li Wei, Wei Jibo, Wang Shan. An evolutionai-dynamic TDMA slot assignment protocol for Ad Hoc networks[C]. IEEE Communications Society subject matter experts for  publication in the WCNC 2007 proceedings,2007:138-142.
[2] 严少虎，卓永宁，吴诗其,等． IEEE 802. 11 DCF 中带优先级的退避算法[J]．电子与信息学报，2005，27(8):1315-1319．
[3] KAYNIA M, JINDAL N. Improving the performance of wireless Ad Hoc networks through MAC layer design[C]. IEEE transactions on wireless communication:January 2011.
[4] 杨海东，李建海，邓勇.采用集总式冲突消除算法的Ad Hoc网络MAC协议[J]. 系统工程与电子技术, 2009,31(5):1241-1245.
[5] 叶林容，余敬东．基于TDMA的Ad Hoc网络MAC协议研究[D]. 成都：电子科技大学,2011．
[6] FULLERTON P S. Dynamic control slot scheduling algorithm for TDMA based mobile Ad Hoc networks[C]. Military Communications Conference, 2008:1-7.