基于动态优先级表的TDMA时隙分配

2013-10-31刘庆刚

通信技术 2013年7期

刘庆刚

(海司信息化部，北京 100841)

0 引言

移动Ad Hoc网络由于其自组织，无中心，分布式[1]等特点现在越来越受到人们的关注，其广泛应用于抢险救灾、临时会议、应急通信等领域。网络在通信过程中各节点既有通信终端的功能，又有路由功能[2-3]。基于TDMA的信道接入策略具有分组无冲突、最大分组时延有限等优点，因此在Ad Hoc网络的组网协议中大多采用基于TDMA的组网协议。

文献[4]提出了一种基于固定TDMA的无冲突动态时隙分配算法，即P_TDMA算法。该算法综合了固定时隙资源分配和动态使用空闲时隙资源的优点，能保证业务传输的最小时延。但是P_TDMA算法没有考虑各节点产生业务不均衡的情况，该算法决定竞争时隙资源成败的唯一依据就是节点的优先级，而不能结合节点本身业务量的大小，因此不能充分利用时隙资源。文献[5]基于P_TDMA算法提出了一种改进型动态TDMA算法，即EP_TDMA算法，该算法事先给出一个固定的优先级表，该表在整个通信过程中保持不变，所以对于节点竞争时隙资源来说存在一定的不公平性。

由于以上原因本文提出了另一种基于固定TDMA的无冲突动态时隙分配算法,即基于动态优先级表的时隙分配算法，起名为DP_TDMA算法。

1 动态优先级表的TDMA时隙分配算法

1.1 优先级表介绍

这里给出一种8节点网络的优先级表。

如表1所示，优先级表中每行和每列的元素都不相同。其中列元素不相同是为了节点竞争时隙时避免冲突；行元素不同是为了保证竞争时隙的公平性。若节点时隙需求情况存在很大差异，采用固定优先级表将存在一定的弊端。例如，若网络中只有节点3可以让出自己的主时隙(与节点号相同的时隙)供其余节点竞争使用，那么由于节点4在3号时隙处始终具有最低优先权，因此将永远竞争不到时隙，存在一定的不公平性。鉴于以上原因，本文提出了基于动态优先级表的时隙分配策略。

表1 8节点优先级表

1.2 DP_TDMA算法介绍

假设网络中有 N个节点，编号为0～N-1，则DP_TDMA算法的时帧结构如图1所示。

图1 DP_TDMA算法时帧结构

1.2.1 声明阶段

声明阶段的主要作用是网内节点根据本地待发送的业务量通知邻居节点自己对时隙资源的需求情况。根据节点的业务量、业务的优先级把节点对时隙的需求分为三种情况，分别为节点不需要使用时隙资源、需要使用一个时隙资源和需要使用多个时隙资源。

1.2.2 回复阶段

经过声明阶段后，各节点收到了邻节点时隙的需求情况信息，接下来的回复阶段各节点将收到的信息组成一个分组，在此称为回复分组。回复阶段各节点在自己对应的时隙依次发送回复分组，发送完成后各节点对自己一跳邻域内节点的时隙需求情况扩展到了两跳范围内。

1.2.3 竞争阶段

基于动态优先级表的竞争策略的基本思想:在时隙竞争过程中决定时隙竞争获胜方的唯一因素是节点在优先级表中的优先级，由于优先级表中的所有列元素不同，因此每次竞争只可能有一个赢家；在算法的运行过程中优先级表是变化的，变化的时间间隔可以根据具体的情况而定，如可以根据时隙的个数而定，也可以根据具体的时间间隔而定。

1.2.4 数据发送阶段

经过竞争阶段后各节点获知自己可以用来发送数据的时隙。由于竞争阶段采用的是无冲突的竞争算法，因此发送过程中不存在冲突，不发送数据的节点处于接收状态。

2 DP_TDMA算法仿真及性能分析

DP_TDMA算法的仿真采用OPNET仿真软件[6]。

2.1 具体仿真实例时隙结构

图2为仿真中采用的固定TDMA时帧结构，各节点在与自己节点号相同的时隙内发送数据。

图2 固定TDMA时隙结构

图3为仿真中采用的动态TDMA时帧结构，其中声明阶段和回复阶段的时隙长度为2 ms，各节点在声明阶段和回复阶段固定使用各个时隙，数据发送阶段的时隙长度为32 ms，各节点动态使用该阶段的时隙。

图3 动态TDMA时隙结构

2.2 仿真结果及性能分析

2.21 固定优先级表的情况

优先级表采用表1。表2所示为仿真阶段所有节点的业务类型情况，由该表可知所有节点每隔0.2s产生一个数据包，产生数据包的时间范围为0～60s。

表2 8节点均衡全饱和业务

从图4可以看出，当网络中的节点业务量均匀时采用固定TDMA的时隙分配算法在网络吞吐量和端到端时延方面取得了较好的结果。

图4 固定TDMA与动态TDMA吞吐量对比

原因分析:由于全网节点都达到了饱和业务量，因此节点都需要使用主时隙发送数据。对于固定TDMA来说，所有的时隙用来发送数据，无浪费的时隙资源；但是对于动态TDMA来说由于算法的前两个阶段用于节点使用时隙需求的交互，在节点都达到饱和传输时，时隙分配的结果是各个节点只能使用自己的主时隙，因此这种情况下前两个阶段相对于同等业务情况下的固定TDMA算法来说浪费了时隙资源，所以在各节点饱和传输的情况下动态TDMA算法相对于固定 TDMA算法来说性能较为拙劣。表3所示为仿真阶段所有节点的业务类型情况，由该表可知0～3号节点每隔0.2s产生一个数据包，达到饱和传输状态，4～7号节点每隔0.6 s产生一个数据包，没有达到饱和传输状态，产生数据包的时间范围为0～60s。

表3 8节点非均衡全饱和业务

由图 5可以看出当节点业务量不均衡时动态TDMA时隙分配算法在吞吐量方面较固定 TDMA时隙分配算法取得了较好的结果。

图5 固定TDMA与动态TDMA吞吐量对比

结果分析:由于网络节点中0、1、2、3号节点业务量处于饱和状态，若只使用主时隙发送数据将造成数据包的积压；节点4、5、6、7每隔0.6 s产生一个数据包，时间间隔较长不会造成数据包的积压。对于固定TDMA时隙分配算法而言，虽然0、1、2、3号节点存在数据包的积压，4、5、6、7号节点存在主时隙空闲的情况，但是业务量大的节点不能使用业务量小的节点空闲出来的时隙，造成时隙资源的浪费；对于动态TDMA而言业务量大的节点可以占用业务量小的节点的主时隙，充分利用了时隙资源，因此在节点业务量不均衡的情况下就吞吐量而言动态TDMA算法效果较好。

总结:由以上的仿真结果可知，对于节点业务量不均衡的网络而言采用动态TDMA时隙分配算法将取得较好的结果。

2.2.2 采用动态优先级表的情况

接下来的仿真中采用动态优先级表代替之前的固定优先级表。表4所示为仿真阶段所有节点的业务类型情况，由该表可知所有节点的业务量均不相同，这样是为了充分保证产生数据包的随机性，产生数据包的时间范围为0s到仿真结束的时间段内。

表4 8节点非均衡业务量

由图6可见，采用动态优先级表的动态TDMA时隙分配算法在吞吐量方面取得了较好的结果。

图6 采用动态优先级表和固定态优先级表的动态TDMA算法吞吐量比较

结果分析:采用固定优先级表行和列的所有元素均不相同，取一个固定优先级表1加以详细分析。

从表1可以看出，虽然各个节点对所有时隙的优先权综合考虑的情况下看似是公平的，但是存在这种情况，即有的节点时隙可能存在长期空出的情况。举例说明如下:比如0号时隙长期空出，若此时1、2号节点需要长期竞争0号时隙，根据以上优先级表可以看出，在节点1、2业务量相当的情况下，1号节点将在竞争中长期处于优胜的地位，这样对于业务量相当的2号节点来说是不公平的，可以称这种情况为同等业务量情况下个别节点的时隙垄断。当加入动态优先级表以后各节点对各时隙的优先级处于不断地变化之中，打破了节点对时隙的垄断，增进了公平，进而增加了网络的吞吐量。