Link16时隙固定分配算法的时延分析

(空军工程大学 电讯工程学院，西安 710077)

1 引 言

数据链是链接数字化战场上的各种传感器、指挥中心、武器平台和作战部队的一种信息处理、交换和分发系统。在数据链系统中，各种信息按照规定的格式，实时、自动、保密地进行传输和交换，从而实现信息资源共享，最大限度地提高作战效能。

时分多址(TDMA)作为一种有效的多址接入方式在数据链中得到广泛应用。TDMA系统中主要的时隙分配算法有固定分配、竞争分配、预约分配和动态再分配[1]。固定分配，也称为静态分配或预分配，指在通信前根据对用户业务量的统计，给每个用户一次性分配一定量的时隙资源。用户在每帧中分配给自己的专用时隙上无冲突的发送信息，在其它时隙中接收有用信息。固定分配的优点在于实现比较简单，并且可以保证每个用户之间的“公平性”(每个用户都分配了固定专用的时隙资源)以及报文的平均时延。因此，固定分配在数据链中得到了广泛应用。例如，数据链Link16的多址接入方式采用TDMA，其最常用的时隙分配算法就是固定分配，只有在时隙容量不足或特殊条件下才使用竞争分配或动态再分配[2]。

2 固定分配算法建模分析

2.1 模型建立

在Link16中，将一天24 h划分为112.5个时元，每时元持续时间为12.8 min。每时元再划分为64个时帧，帧长为12 s。时帧中总共包含m=1 536个时隙，每个时隙宽度为τ=7.812 5 ms。在一个时帧中，时隙被编入3个时隙组，即A组、B组、C组。每组共包含512个时隙，编号为0～511。时帧结构如图1所示[3]。

图1 时帧结构示意图Fig.1 Structure of time frame

Link16的J系列消息总共有91类消息，但每个用户在作战过程中不一定收发所有类型的消息，而是只能或只需处理特定类型的消息。为此，把J系列消息按照功能进行分组，这些分组称为网络参与组(NPG)。因此，首先将系统的时隙资源分配给各NPG，不同的NPG分配到不同的时隙数量。NPG再将时隙分配给各用户，用以发送和接收该NPG上的消息。

时隙以时隙块的形式进行分配。采用二叉树法划分时隙块，这样时隙块中的时隙等间隔地分布在整个时帧之中。

时隙块的表示方法为：时隙组-起始时隙号-重现率。例如，时隙块A-2-11表示属于时隙组A，起始时隙是2，重复率为11(每个时帧中含有211-6=32个时隙，在时隙组A中时隙间隔为16个时隙)，时隙编号可用(2+16n)来表示，即包含时隙：A-2，A-18，A-34，…，A-498。

表1 4种消息封装结构及特性Table 1 Four data packing formats and their features

在Link16中，根据支持的消息类型、吞吐量需求和抗干扰性能需求，用户端机可以产生4种消息封装结构，它们是由抖动(STDP、P2SP中有抖动，P2DP、P4SP中没有抖动)、粗精同步头、报头、消息本体(含有消息字，每个消息字包含70 bit的用户数据)和传输保护段构成的，如表1和图2所示。

图2 时隙结构示意图Fig.2 Structure of timeslot

2.2 模型分析与求解

2.2.1 指标分析

时延指报文从源节点发送到目的节点所需要的延迟时间。该指标体现了系统传输信息的时效性。

按照发生的顺序，时延主要包括4个部分：

(1)处理时延：指当报文在源节点产生到该报文进入到发送队列之间的时间差；

(2)等待时延：指当报文进入到发送队列到该报文开始被传输之间的时间差。在这个时延阶段，该报文首先要等待比其先到发送队列的报文传输完毕，然后再等待时帧内可用的服务时隙的到来；

(3)传输时延：指当报文开始被传输第一个比特到传输完最后一个比特之间的时间差；

(4)传播时延：指报文最后一个比特被传输完到该比特被目的节点接收之间的时间差。

处理时延和传输时延主要与硬件性能及一些设置相关，传播时延是物理距离的函数，所以三者基本上都是固定值。而等待时延与选择的时隙分配方式有密切关系，并且是影响消息响应时间的主要因素[4]。因而，在接下来的分析求解过程中，主要讨论用户报文的平均等待时延。

2.2.2分析与求解

由于各用户的报文平均到达率λi和服务速率μCi都不相同，故各用户的平均等待时延各不相同。设用户i的报文的平均等待时延为Ti，那么Ti由两部分组成：

(1)报文的平均排队时延Wi，包括等待比其先到发送队列的报文传输完毕的时延和正在接受服务的报文的剩余服务时间；

(2)报文等待时帧内服务时隙的平均时延。

由排队论中的P-K(Pollaczek-Khinchin)公式知[5-8]，用户i的报文的平均排队时延为

(1)

(2)

ρi为其排队系统的负荷率，即报文的平均到达率和服务速率之比，所以：

(3)

因此，可求得报文的排队时延为

(4)

综上所述，可求得用户i的平均等待时延为

(5)

利用Little定理，可求得用户i的发送队列中的平均报文数为

(6)

3 数值计算与仿真

3.1 数值计算

因此，可求得该用户的平均等待时延为

利用Little定理，该用户的发送队列中的平均报文数为

由Link16的时隙结构可知，在一个时隙内既包含了传输时间也包含了传播时间，即两者之和小于7.812 5 ms，而数据链的处理时延一般都比较小。因此通过数值计算可知，它们都远远小于等待时延，即用户报文的总时延主要是由等待时延部分构成，等待时延是影响消息响应时间的主要因素。

3.2 仿真结果与分析

通过对前面建立的固定分配算法模型进行仿真，可以得到用户i报文的平均等待时延Ti和队列中的平均报文数Ni随着负荷率ρi的变化规律，分别如图4和图5所示。

图4 平均等待时延与负荷率的关系Fig.4 Average waiting time delay vs load rate

图5 平均报文数与负荷率的关系Fig.5 Average message number vs load rate

由图4可以看出：

(1)当负荷率ρi在(0，1)范围内增大时，Ti随之增大。当负荷率ρi趋于1时，Ti将趋于无穷大。因此，在进行时隙固定分配时，应根据网络规划等要求使数据链工作在合适的负荷率。如果选取的负荷率过小，就会造成时隙资源的浪费，降低系统的吞吐量；相反，如果选取的负荷率过大(接近于1)，那么吞吐量接近饱和，造成时延急剧恶化，此时无法满足系统规定的消息响应时间的通信要求；

(2)比较图4中的3条曲线可知，在负荷率ρi相同的情况下，Ti随着分配给用户的时隙数ni的增大而减小。因此，采用时隙固定分配算法时，系统必须根据事先对用户业务量的统计，给用户分配足够的时隙来降低时延，从而确保达到系统规定的消息响应时间的要求；

(3)当给用户分配定量时隙之后，如果用户的业务量突然增大，即负荷率增大，由图可知时延也将随之增大，从而可能无法满足系统规定的消息响应时间的要求，此时应当视消息发送失败。由此可以看出，固定分配算法适用于用户业务量比较稳定的情况，这样负荷率能够在维持在一个合适的小范围内。如果用户业务量不稳定或者时隙资源不够分配，那么将会使时延增大，无法满足系统规定的消息响应时间等要求，这体现了固定分配算法不够灵活。

由图5可以看出：用户的发送队列中的报文数随着负荷率ρi的增大而增大，即ρi反映了排队系统的繁忙程度。但实际上用户的缓存器容量是有限的，如果发送队列中的报文过多而超过了缓存器容量，那么将会出现丢弃报文的情况。

4 结束语

时隙分配是数据链网络规划管理的一个重要部分，它影响到网络能否高效、可靠地运行，必须针对不同的应用场合选取合适的时隙分配算法，从而达到提高网络性能的目的。本文通过运用排队论理论，建立了Link16的时隙固定分配算法的排队模型，并对其时延特性进行了具体的分析和求解。数值计算和仿真结果表明，时隙固定分配算法适用于用户业务量比较稳定且时隙资源充足的情况，必须选取合适的负荷率，才能够满足系统规定的消息响应时间的要求，使系统达到良好的吞吐量。本文为研究其它时隙分配算法提供了对比和参考。

参考文献：

[1] 梁爽.地空数据链中越区切换和时隙动态分配的应用与研究[D].西安：空军工程大学，2005.

LIANG Shuang. Application and Study of Handover and Timeslot Allocation in Ground to Air Data Link[D].Xi′an: Air Force Engineering University, 2005. (in Chinese)

[2] 骆光明，杨斌，邱致和，等.数据链[M].北京：国防工业出版社，2008.

LUO Guang-ming,YANG Bin,QIU Zhi-he,et al.Data Link[M].Beijing: National Defense Industry Press,2008.(in Chinese)

[3] 梅文华，蔡善法.JTIDS/Link16数据链[M].北京：高等教育出版社，2004.

MEI Wen-hua,CAI Shan-fa. JTIDS/Link16 Data Link[M].Beijing: Higher Education Press, 2004. (in Chinese)

[4] 侯新宇.数据链时隙动态分配及其网络规划技术研究[D].成都：电子科技大学，2008.

HOU Xin-yu. Reseach on Dynamic Timeslot Allocation and Network Layout Technique for Data Link[D].Chengdu: University of Electronic Science and Technology of China, 2008. (in Chinese)

[5] 李建东，盛敏.通信网络基础[M].北京：高等教育出版社，2004.

LI Jian-dong,SHENG Ming. Base of Communication Network[M].Beijing: Higher Education Press, 2004. (in Chinese)

[6] 仝海波，梁俊，吕娜.战术数据链时延特性的仿真分析[J].电光与控制，2009,16(8):53-55,64.

TONG Hai-bo,LIANG Jun,LV Na. Simulation and Analysis on Delay Performance of Tactical Data Link[J].Electronics Optics and Control, 2009,16(8): 53-55,64. (in Chinese)

[7] 汪荣鑫.随机过程[M].西安：西安交通大学出版社，2006.

WANG Rong-xin.Stochastic Process [M].Xi′an: Xi′an Jiaotong University Press, 2006. (in Chinese)

[8] 张军，李忠孝.自组织时分多址甚高频数据链的延时分析[J].北京航空航天大学学报，2004,30(3):222-226.

ZHANG Jun,LI Zhong-xiao. Delay Analysis of Self-Organized TDMA VHF Datalink[J].Journal of Beijing University of Aeronautics and Astronautics, 2004,30(3):222-226.(in Chinese)