HTDMA协议自协调分布式运行机制研究*

魏小龙,李建海,杨海东

（空军工程大学 工程学院，陕西 西安710038）

移动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]。

构建此问题的数学模型可以得到分布式Ad Hoc网络正常通信的制约条件。根据图2，可以用一个N×N的二维矩阵C=Cij来表示网络拓扑结构,其中N=|V|为网络中节点个数：

假设一个时帧划分为M个时隙，一个时帧内每个节点至少分配到一个时隙，用M×N二维矩阵X=Xmi来表示时隙分配方案，其中

综上可以将时隙分配问题规划为一个数学模型：

目标函数为：min M and max ρ

约束条件为：

式(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所示。在此为了便于说明，队列中业务序列按其序号排列。

根据业务树算法，在各预约队列中，只有当序列中排在前面的所有节点都发送了数据，当前节点才能发送数据。得到整个系统的业务发送次序如图2箭头表示信道使用权的传递方向。

表1 图2中各发射节点所维护的预约队列

因此，对于图2的模型，分布式队列的路径可以用图 4(a)、(b)所示的业务树来表示。

对照图2可以看出，在图4中的业务树中，不同分支上的业务可以在同时隙发送，而不引起分组碰撞。如图4(a)中的业务②和业务③，以及图4(b)中的业务④和业务③。

对照图1，从图5新业务的发送次序上看，在两组两跳节点间，数据发送无冲突，空间可复用。可见，通过业务树管理算法，节点能够依据自身在队列中的次序依次接入信道。这种机制完全可以代替预约时隙表，可以在不增加任何协议开销的情况下，实现节点的自协调、无冲突的分布式传输。

3 仿真实验

为了进一步验证业务树算法在改善分布式网络性能中起到的作用，通过网络仿真软件OPNET，对该算法使用前后 CCT—QR协议/DCT—QR协议（Distributed CCT—QR）的丢包率和吞吐量进行了仿真和对比。

仿真网络环境参数和协议参数见表2。

表2 仿真参数表

3.1 吞吐量分析

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

3.2 丢包率分析

图7显示了两种协议的数据包丢失情况。当网络负载并不高时，CCT—QR协议和改进后的DCT—QR协议的丢包率相当。但当输入量达到一定值时(480 packet/s)，分布式运行机制就会体现出它的作用，它消除了业务密集后带来的分组碰撞，降低了原协议的丢包率，但当业务量超过控制时隙容量时，丢包率将无可避免地增加。

本文提出了解决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.