基于哈希算法的动态TDMA时隙分配研究

吉 彬，苏 旸

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

0 引言

Ad Hoc网络是由无线通信设备组成的分布式网络，它不需要基础通信设施的支持，在通信过程中节点既有通信终端的功能,又有路由的功能[1-2]。Ad Hoc网络中无线信道多点共享，时隙资源分配是Ad Hoc网络的关键技术，关系到节点能否充分利用有限的信道资源，实现节点对时隙资源的公平竞争。动态TDMA信道接入协议具有分组无冲突、最大分组时延有界等优点，在无线通信系统中得到了广泛应用。

文献[3]提出了一种基于固定TDMA的无冲突动态时隙分配P_TDMA算法。该算法综合了固定分配和动态接入的优点，具有最小时延保障。但是这种算法没有充分考虑节点业务不均衡的情况，在竞争阶段节点都按优先级高低尽最大可能占有时隙，而不考虑自身的时隙需求，因此该算法不能充分利用时隙资源。文献[4]在P_TDMA的基础上提出了一种改进型EP_TDMA算法，该算法在竞争阶段采用给出的优先级表决定谁是时隙竞争的赢家，由于优先级表固定不变，所以该算法存在一定的不公平性。

鉴于以上原因提出了一种基于固定TDMA的无冲突动态时隙分配HP-TDMA算法。该算法通过声明阶段清晰的时隙需求划分来避免不必要的时隙资源浪费。经过交互信息阶段各节点知悉两跳范围内节点时隙的需求情况。在时隙竞争阶段，根据哈希算法得出各竞争节点对可竞争时隙的优先级顺序表，优先级顺序表决定了节点对时隙的使用权。

1 HP_TDMA算法

1.1 TDMA时帧结构

假定无线网络有N个节点，各节点可以与它的一跳相邻节点直接通信。帧结构分为声明阶段、交互信息阶段、竞争阶段、信息发送阶段。

图1为HP_TDMA时帧结构。各部分分为N个子时隙，对应网络中N个节点。信息发送阶段各子时隙称为各节点的主时隙。

图1 HP_TDMA时帧结构

1.2 声明阶段

声明阶段主要作用是各节点声明自己时隙需求情况，使用时隙需求是基于节点业务量的情况。节点需要使用时隙则发送时隙使用通知分组。声明分组由3部分组成，即类型、节点号和标志位。标志位由2比特组成，标志位为00表示节无需使用时隙；标志位为01表示节点需使用自己的主时隙；标志位为10表示节点需要使用自己的主时隙和竞争额外时隙。

声明阶段通过节点使用时隙3种情况的划分避免节点凭借高优先级占有多个无用时隙资源的情况。

1.3 交互信息阶段

经过声明阶段节点获得相邻节点时隙使用情况，随后对获得的时隙使用信息进行分组。交互信息分组分为分组类型、源节点号、节点状态等部分。节点状态表明节点收集到的在网节点对时隙资源的需求情况。

通过交互信息阶段N个信息分组的发送，节点把一跳范围内各节点对时隙资源的需求情况信息扩展到两跳范围内。两跳范围内各节点可以竞争使用无需时隙资源节点的时隙以及两跳范围外各节点的时隙。在此给出如图2所示的一个网络拓扑实例。

图2 网络拓扑

图2中数字代表节点号，其中1、4节点为只需要使用自己主时隙的节点，6、7节点为不仅需要使用自己主时隙而且需要竞争额外时隙的节点，其余不需要使用时隙。

经交互信息阶段后各节点获得其他节点时隙需求情况如表1所示。

表1 交互信息阶段后节点获知的全网节点时隙需求情况

表1中00表示节点不需要使用时隙；01表示只需使用主时隙；10表示不仅需要使用主时隙，而且需要竞争额外的时隙。

1.4 竞争阶段

此阶段节点拥有一个与其他节点不同的随机种子，这里随机种子为节点号。随机种子与时隙号、时帧号进行串接输入名为 inline_smear的哈希函数生成一个哈希值，该哈希值最终决定谁是时隙竞争的赢家。若出现相同哈希值则取节点号小者为时隙竞争赢家。给出inline_smear函数：

inline_smear函数使输入值变换为一个不相关的哈希值，文献[5]中论述了有关哈希函数计算节点竞争时隙时的公平性。

1.5 信息发送阶段

信息发送阶段，节点在获得的时隙发送业务，无业务发送的节点处于监听状态。

2 算法性能分析

仿真场景如图2所示。在此定义两个参数，一个为总的可用时隙数，一个为时隙利用率。总的可用时隙数为一帧内总共可以发送数据的时隙总数量，若同一时刻多个节点有权发送数据则时隙数为发送数据节点数之和；时隙利用率为实际发送业务的时隙数量与总的可用时隙数的比值。

文献[4]提出的EP_TDMA算法在竞争阶段基于一个固定优先级表来展开对时隙资源的竞争，而HP-TDMA算法基于哈希函数计算节点对时隙资源的竞争结果。现将两种方法的计算结果加以对比，如表2所示。

表2 算法性能对比

由表2可以看出EP_TDMA算法分配时隙资源导致只需使用自己主时隙的节点占用过多时隙。EP_TDMA可用于发送的总的可用时隙数为9个，但有3个是浪费的，利用率为6/9=66.7%。只需使用自己主时隙的节点1和4分别占用了1、6号时隙和2、3、4号时隙，这必将导致网络中部分业务量大的节点因为可用时隙被占用而不能传输业务。然而HP_TDMA算法的动态时隙分配给出了合理分配结果。1、4节点业务量不大，只分配了自己的主时隙。6、7节点因为业务量大分别分配了1、2、6和3、5、7等多个时隙。HP_TDMA算法给出可以利用的总的可用时隙数为8个，这8个时隙都有节点发送数据，利用率为100%。

由图3可以看出只需使用自己主时隙的节点1、4在EP_TDMA算法中分别获得2个和3个时隙，造成时隙资源的浪费，而在HP_TDMA算法中1、4节点只分配到主时隙。

图3 节点可用时隙数分配结果

需使用额外时隙的节点6、7在EP_TDMA算法中共分得4个时隙资源，而在HP_TDMA算法中6、7节点共分得6个时隙资源，在整个时帧过程中EP_ TDMA算法分给所有节点实际使用的时隙数为6个，而HP_TDMA算法分给节点实际使用的时隙数为 8个，可已看出HP_TDMA算法分配的实际使用时隙数为EP_TDMA算法的8/6=1.33倍。因此使用HP_TDMA算法得出的分配结果是优于EP_TDMA算法的。

3 结语

HP_TDMA算法在声明阶段通过清晰的时隙需求划分避免时隙资源的浪费[5-7]，在竞争阶段通过哈希算法公平的进行时隙资源的竞争，为各节点公平的得到自己所需的时隙资源数创造了条件，因此采用基于哈希算法的动态TDMA时隙分配取得了较好的结果。但是，由于该算法每个时帧都要运行哈希函数来计算时隙竞争的赢家，使用HP_TDMA算法相比采用固定优先级表的EP_TDMA算法增加了运算量，在网络运行中将增加节点功耗。因此，HP_TDMA算法还有待做出进一步的研究，以期获得更好的结果。

[1] 陈林星,曾曦,曹毅.移动Ad Hoc网络——自组织分组无线网络技术[M].北京:电子工业出版社,2006.

[2] 张弛.基于TDMA的Ad Hoc网络MAC协议比较[D].西安：西安电子科技大学，2007：1-12.

[3] PENG Gexin, XIE Shengli, CHEN Caiyun. A Collisionavoid Dynamic Slots Assignment Algorithm based on Fixed TDMA[J]. China Information Security,2005(11):115-120.

[4] 聂建耀，许勇.一种应用于Ad Hoc网络的改进型TDMA动态时隙分配算法[J].移动通信，2008(10):83-86.

[5] 李翠然,谢健骊.移动自组网MAC协议的误码性能分析[J]. 通信技术,2010,43(05):140-142.

[6] 夏林英,张亚明,陈绍炜.战术数据链网络同步技术的改进方案[J].信息安全与通信保密,2007(05):74-75.

[7] 彭革新,谢胜利,陈彩云.一种基于固定TDMA的无冲突动态时隙分配算法[J] .信息安全与通信保密, 2005(11):115-120.