数据链时隙分配算法设计与仿真

杨 恩， 张有光， 唐积强

（北京航空航天大学 电子信息工程学院，北京 100191）

0 引言

数据链是采用网络通信技术和应用协议,实现机载、陆地和舰船系统之间的高效的数据信息交换的通信系统[1]。现代空空通信环境下，节点之间的信息交互较多，网络通信业务需求较大，实时性要求强。基于自组织时分多址技术（STDMA）的数据链系统[2]是以时隙为基本单位，将时间轴划分为若干个时隙，由多个时隙组成时帧，网络中的每个作战单元在每个时帧中都占有时隙，为信息交互提供了实时性保证。

现通过使用OPNET软件对自组织预约STDMA算法[3]进行仿真，对仿真结果进行分析，提出了改进的动态自组织时隙分配算法（DSTDMA），该算法可以有效的保证网络的实时性要求，能够更好的适应网络规模的变化。

1 预约STDMA算法简介

预约 STDMA算法由固定分配和预约分配两种方式组成，其帧结构组成如图1所示，每个超帧有n个时帧组成，每个时帧由m个时隙组成[4]。在该算法中，每个时帧由固定时隙和可预约时隙组成。固定时隙固定分配给网络内的节点，其余节点不能使用；预约时隙可以由网络内的时隙共同竞争使用。

图1 时帧结构

该算法提出了动态的时隙预约思想，为网络内的数据包通信提供了QoS保证机制，并且提供了完成的网络调整的机制，整个算法具有较高的稳定性。

在网络规模稳定的情况下，该算法能够获得更好的稳定执行效果，但是当节点较少时，由于整个时帧长度已经固定为m，将会导致部分时隙的浪费，并且当网络规模不断增加之后，由于网络的时隙数有限，将导致网络所有空闲时隙都被分配出去，无法为新节点分配时隙，节点不能加入网络。

在针对STDMA算法的在以上环境下的不适应性，所以提出一种可以动态调整时帧长度的时隙分配算法（DSTDMA），在网络规模变化较快环境下，算法能够更好的利用时隙，减小数据包时延，并且具有良好的可扩展性。

2 DSTDMA算法简介

2.1 时帧结构

DSTDMA算法的帧长度为2的幂次方，在网络运行的整个期间，时帧的长度可变，其帧结构如图2所示。当网络内节点较少时，网络内的帧长度较小，每个节点占用一个时隙，当节点数增加之后，由于原来的时隙数无法满足当前的节点数，则帧长度进行加倍，为新入网节点分配时隙。下面将具体的介绍整个算法的流程。

图2 时隙分配算法的时帧结构

2.2 时隙分配

新的节点在加入网络时，需要获取网络中的可用时隙，来进行数据包的发送，其主要过程为如下几个步骤：

（1）发送入网申请

当一个新的节点加入网络之前，节点不知道网络内的任何时隙分配信息，首先需要侦听网络的帧长度，确定0号时隙的位置，发送入网申请信息。

（2）获取时隙分配信息

当网络内的节点接收到新节点的入网申请之后，各个节点在自己占有的时隙发送其时隙占用情况以及其邻居节点的时隙占用情况。新节点记录下其所有邻居节点发送来的时隙分配信息，首先将自己的时帧长度设置成与获取到的最大时帧长度相等。

（3）选择时隙

节点根据上一个阶段所记录的时隙信息，按照下面三个步骤进行时隙的选择。

①选择空闲时隙。节点根据在上一阶段获取的各个邻居的时隙信息情况，选择没有被任何节点占用的时隙；

社会发展至今，包容度越来越高。“双十一”呼啸而至，码商百舸争流，无论是否买家，都应该放下一切与这个时代不再契合的观念，用自身的体验来打量“双十一”，寻找它的意义。

②释放节点多占的时隙。当新节点在查找获得的时隙信息之后，发现没有空余时隙，那么新节点将查找所获得的时隙信息中，是否存在一个节点占有多个时隙的情况，如果存在一个节点占有了多个时隙，那么将从占有时隙做多的节点所占有的时隙中，选择一个时隙，作为新节点的时隙；

③调整帧长。当新节点查找时隙信息时，如果没有能够满足上面两个情况，新节点将主动将时帧长度加倍，由于每个帧中的第一个时隙是预留时隙，所以，帧长加倍之后，新节点可以占用后面半个帧中的第一个时隙。时帧长度加倍之后，后半帧的时隙占用除了后半帧中第一帧外，其余各个时隙均与前半帧相同。

（4）更新时隙信息

完成了上面三个阶段之后，一个新节点就加入到了网路之中。新节点将其选择的时隙信息在一下个0号时隙进行播报，网络内节点接收到新的时隙分配信息之后，将自己所记录的时隙表进行更新；并且将更新后的时隙信息再次进行播报，使得其邻居节点也更新时隙表信息，保证新入网节点两跳范围内实现无冲突的时隙分配。

3 OPNET仿真建模

OPNET软件作为一种主流网络仿真软件，为通信网络和分布式系统的建模提供了全面的模拟仿真开发环境。OPNET采用三层建模机制：进程模型、节点模型、网络模型。三层模型与实际的协议、设备、网络完全对应，能够全面的反映出网络的相关特性[5]。

3.1 进程模型

进程模型使用有限状态机来描述进程的逻辑行为，它位于OPNET三层模型中的最底层。DSTDMA状态机设计共由8个状态构成。

①init状态机完成算法的初始化过程，设置节点的时隙长度，业务信息，节点类型等；

②listen、backoff、wait状态机完成发送入网申请，以及根据获得的时隙信息，进行时隙的选择；

③control状态完成网络内节点的时隙信息发送和时隙分配调整过程。

3.2 节点模型

OPNET中节点模型定义了每一个节点的行为，一个节点通常由多个模块组成，节点的行为有组成它的模块所决定，每个模块完成节点的一部分行为。DSTDMA的节点模型包含三层，最上层为sink模块和src模块，用来产生数据包和处理、销毁本节点接收的数据包；中间是mac模块，算法的核心模块，完成整个时隙分配算法；最下层是OPNET软件提供的无线收发机模块，用来完成数据的收发。

4 仿真结果分析

4.1 仿真场景

对预约STDMA算法和DSTDMA算法分别进行了建模分析，下面给出仿真分析的网络场景模型。在高动态空空数据链网络中，节点具有通信距离远，运行时间较长等，网络内节点数目有限等特点。整个场景的由 16个节点组成，网络中时隙长度为50 ms，仿真时间为1 h。

4.2 结果分析

仿真过程中，网络内各个节点发送的数据包大小为200 bit，下面三幅图（图3、图4和图5）给出了在不同业务量下，两种算法的时延性能曲线。

由这三组结果可以得出以下结论：

①算法有效性：通过仿真，验证了DSTDMA算法的有效性，网络中各个节点能够按照算法组成网络，并完成时隙分配过程，实现无冲突的数据包发送，显示出了算法的可实现性；

②实时性：由三组仿真结果可以看出，DSTDMA算法有效的减小数据链的数据包端到端传输时延。从上面三幅曲线中,可以看出,在网络形成初期,由于节点数量较少,数据传播时延较小,随着节点不断加入网络之后,数据时延开始增加，最终全网的时延保持稳定。当业务量升至每秒1个数据包的情况下,DSTDMA算法的时延性能明显优于STDMA算法，平均数据时延稳定在1 s，这主要是由于DSTDMA算法采用了监听的方式完成整个时隙分配的过程，减少了网络为节点入网过程所预留的控制数据交互的时隙，有效提高了时隙的利用率，降低了数据包时延；

图3 1 packets/s

图4 0.5 packets/s

图5 0.2 packets/s

③可扩展性：DSTDMA算法的帧长度可以动态变化，随着网络规模的不断变化，帧长度进行自适应调整，以容纳下新加入的节点，与 STDMA算法相比，提高了网络的可扩展性。

5 结语

通过对STDMA算法的分析，提出了一种可变帧长的动态自组织时隙分配算法，在网络环境变化较快的情况下，能够容纳更多节点，网络规模具有更好的可扩展性；同时，算法提高了网络数据包的端到端时延，有效提高了高动态环境下的信息通信。最后，通过OPNET软件对其进行建模分析，对算法的实时性和可扩展性进行了仿真论证。

[1] 孙义明，杨丽萍.信息化战争中的战术数据链[M].北京：北京邮电大学出版社，2005：5-17.

[2] 张军,张其善,邓秋林.S-TDMA 数据链系统时隙预约选择算法分析[J].北京航空航天大学学报,2001(05)：514-517.

[3] 张昱晖,张有光,唐积强.一种新型 STDMA 数据链系统时隙分配模型[J].通信技术,2009,42(06)：59-61.

[4] 李楠,陈颖,夏毅强.VDL4：一种新型航空VHF 数据链[J].电讯技术,2003(06)：90-94.

[5] 陈敏.1OPNET网络仿真[M].北京：清华大学出版社,2004.