MF-TDMA卫星通信系统信道分配时间优化方法

许 楠，郝学坤，许 众

(1.中国电子科技集团公司第五十四研究所，河北石家庄 050081;2.沈阳理工大学，辽宁沈阳 110159)

0 引言

多频时分多址(MF-TDMA)将频率分割为多个子信道，在每路载波上划分时隙，每个用户在一定的频率上占用指定的时隙。这种技术同时具有FDMA和TDMA 2种体制的优点，扩展了网络规模，能够灵活分配信道的时隙资源，保证信道的利用率，因此广泛应用于卫星通信系统中。

MF-TDMA卫星通信系统对信道时隙资源的分配采取申请/分配机制。各终端站根据其业务的特性与变化情况，周期性地向中心站发送时隙申请信息。中心站接收后，执行时隙分配算法，从信道中搜索合适的时隙进行分配，形成时隙分配表，下发至每一个终端站。各站在接收到时隙分配表后，进行解析，获得本站的时隙分配情况，在相应的时隙内进行业务数据的传输。

因此，MF-TDMA卫星通信系统具有非常强的实时性。如何高效快速地进行信道分配，使整个通信系统能够公平、高效的进行业务传输一直是卫星通信领域研究的课题。

1 周期轮询法

1.1 分配约束条件

MF-TDMA系统的信道可以抽象理解为一个二维矩阵，其中行表示不同频率的载波，列表示一帧内划分的时隙。分配过程可以看作是:在一定的约束条件下，将终端站的时隙申请，以尽快的速度分配到信道矩阵最合适的空闲时隙当中去。约束条件主要有以下3个方面:

①为同一终端站分配的时隙数量不能超过一个载波的时隙容量;

②为同一终端站分配的时隙资源，在时间上不能冲突;

③同一个时隙资源不能同时分配给2个业务申请。

1.2 分配过程分析

目前最常见的信道分配算法是周期轮询法。该方法的分配过程是当中心站接收到各终端站的时隙申请信息后，按照申请业务的优先级，将其从高到低进行排序。然后按照顺序依次提取业务申请，找到对应的载波，从头至尾进行一次轮询，检测时隙是否空闲。如果空闲，该时隙是否与申请冲突，如果未发生冲突，直接将该申请分配，提取下一个申请;如果发生冲突，继续检测下一个时隙，直至整个载波全部轮询完毕，则该申请无法被分配，直接放弃，提取下一个申请，从载波的起始位置继续重复这一轮询过程。

图1 周期轮询法的流程图

1.3 数学模型

MF-TDMA系统一帧的分配时间用T来表示，则:

式中，m表示一帧内分配的时隙个数;i表示分配过程中搜索到的空闲时隙个数;tu表示搜索判断一个时隙是否空闲的时间;j表示搜索的已分配时隙的个数;k表示检测冲突时的已分配载波数量;t'u表示检测一个已分配时隙是否与申请冲突的时间。

不同tu之间的差值忽略不计，统一表示为t，同理t'u统一表示为t'，则式(1)可以表示为:

式中，t和t'受系统硬件条件的限制，一般来说是固定不可变的。真正决定分配时间的是m、i、j、k，即分配的申请个数、冲突出现的次数、对已分配时隙检测的次数和已分配的载波数等因素。

1.4 算法的性能分析

周期轮询算法的优点是过程简单容易实现，能够保证优先分配优先级较高的业务时隙申请;缺点是分配的效率低下。这是因为该方法对每一个时隙申请，都采取同样的轮询操作。在轮询的过程中，对空闲时隙和已分配时隙不加以区分，而是统一进行查询比对，大量时间消耗在对已分配时隙的检测比对上，即i*t所占T的比例很大。特别是当信道分配的末期，已分配时隙占信道时隙的大多数，此时进行分配，绝大部分分配时间都消耗在对已分配时隙的检测上面。

2 时隙列表法

2.1 算法的优化目标

对于MF-TDMA系统来说，时隙分配的计算时间是一个非常重要的性能指标，它直接影响申请的响应时间，是通信业务正常传输的保证。

在时隙分配的初始阶段，空闲时隙占信道的大多数，对其搜索是很容易的，可以快速完成。此时对已分配时隙的检测非常少，对时间的消耗也不多。随着信道中的时隙逐渐被分配，空闲时隙数量越来越少，对其搜索也越来越困难，在搜索的过程中，对已分配时隙的检测占绝大多数。尤其是在信道分配过程的最后阶段，为了分配一个时隙申请，要将几乎信道中所有的时隙都检测一遍。

由式(2)可以看到，周期轮询法在分配的后期很大一部分时间用来检测已分配时隙，即i*t。搜索的目的是要找到合适的空闲时隙，这一部分时间消耗对于分配的结果来说是毫无意义的，因此要尽量减小i*t。由于t是由系统所决定的，不可改变，只能减小搜索的次数i，尽量减少对已分配时隙的处理，甚至完全不再搜索已分配时隙。

2.2 原理

能够解决这一问题的是时隙列表法。这种方法是通过创建和维护一个时隙列表，达到分配过程中“屏蔽”已分配时隙的目的。

如图2所示，当信道分配进行到一定程度时，对空闲时隙的搜索变得困难，通过对信道进行一次轮询，统计空闲可分配的时隙，创建一个列表，用以存放这些空闲时隙的信息，包括位置、大小和是否连续等。接下来的分配，中心站提取时隙申请后，不再直接对信道进行轮询，而是在时隙列表中提取信息，在信道中直接寻找对应的空闲时隙，然后进行冲突检测等操作。一旦分配成功，立即在时隙列表中将该空闲时隙的信息释放。随着分配到进行，时隙列表不断地被释放，其大小始终与信道中的空闲时隙数量是一致的。分配结束时，由时隙列表的大小可以直接得出该次时隙分配的信道利用率。这一方法借助时隙列表将繁琐的轮询搜索过程简化为直接一步提取查找，对信道中已分配的时隙不再进行空闲检测，达到了“屏蔽”的目的，能够有效缩短分配时间。

图2 时隙列表法的流程图

该方法的本质是将信道中的空闲时隙通过一次提取出来，重新组成新的信道矩阵，继续进行分配。但是经过时隙列表提取后，信道的规模大大减小，并且全部是空闲时隙，等同于在全新的信道内继续进行分配，因此搜索分配的效率大大提升，分配的时间将会得到大幅度缩减。

当然该方法只有在信道分配过程中才会有明显效果。当信道内存在大量空闲时隙时，容易搜索，使用时隙列表法和直接搜索的差别不大，时隙列表的创建和维护反而耗费了一定时间。当分配进行到一定阶段，大部分时隙已被占用时，直接搜索的效率大大降低，时隙列表法才能发挥最大的效用。

2.3 具体实现

当信道开始分配时，可以使用周期轮询法，在时隙分配一定数量后，对信道进行轮询生成时隙列表;也可以直接对信道进行一次轮询，不断提取时隙申请进行分配，如果发生冲突不能分配，将空闲时隙记录在时隙列表中，这样经过一次轮询，不仅生成了时隙列表，并且分配了大量的时隙申请，减少了轮询的次数m，最大限度地缩短了分配的时间。

具体的实现步骤:

①通过对信道进行一次轮询，分配时隙申请的同时，根据信道内空闲时隙的分布情况创建时隙列表;

②提取时隙申请，在时隙列表中提取空闲时隙的信息，根据其在信道中进行冲突的检测;

③如果没有发生冲突，直接将申请分配到信道中相应的空闲时隙中，同时在时隙列表中释放该时隙，提取下一申请重复②;

④如果发生冲突，继续在时隙列表中提取空闲时隙;

⑤信道搜索完毕后，仍无法分配，放弃该时隙申请，提取下一申请重复②;

⑥时隙申请全部提取或者信道全部被占用，释放时隙列表，分配过程结束。

3 仿真优化

针对MF-TDMA系统，对时隙分配的过程和时隙列表法进行模拟和仿真。仿真的具体条件设定如下:

① 网络中的终端站规模【8，256】递增;

②信道矩阵包含8个载波，一帧内包含128个时隙;

③时隙申请为8*128的矩阵，发出申请的终端站随机分布;

④每次分配前信道清零。

3.1 信道分配的过程分析

在信道分配的不同时期，分配相同数量的时隙申请，耗费的时间是不相同的。

图3中的4条曲线分别表示分配的起始、进行和结束的不同阶段，分配32个时隙申请所耗费的时间。

图3 不同阶段分配相等数量时隙耗费的时间

由仿真的结果，可以看到在分配过程的不同时期，分配同等数量的申请，分配的效率差别很大。在分配的初期，信道内空闲时隙较多，分配的效率很高;随着分配的进行，空闲时隙的搜索愈加困难，分配的效率越来越低。因此需要针对分配的不同时期，采取相应的策略以优化分配的时间。

此外，在网络规模较小时，时隙分配的时间会相对长一些，这是因为此时发出时隙申请的终端站分布较为集中，出现时隙冲突的概率较大，因此搜索的空闲时隙和检测冲突的次数较多，从而导致分配的时间较长。

3.2 时隙列表法

图4中的第1条曲线是原始的周期轮询法;第2条曲线是首先使用原始轮询法，在信道被分配50%的时候，采用时隙列表法;最后一条曲线，是在分配初始阶段，采取一次轮询分配多个申请，然后采用时隙列表法。

图4 时隙列表法的比较

由仿真的结果可以看到，时隙列表法可以大幅度缩短时隙分配的时间。而在信道绝大部分时隙为空闲的时候，一次轮询分配多个申请和时隙列表法相结合，可以极大地增强时隙列表法的优化效果。

时隙列表法是对空闲时隙的搜索操作进行简化，优化了分配时间，对分配的结果没有任何的影响，3种方法最终的信道利用率都是一致的。

4 结束语

通过对MF-TDMA系统时隙资源分配的周期轮询法进行分析，提出时隙列表法，通过一次轮询分配时隙并生成时隙列表，在列表中进行接下来的分配，避免了对已分配时隙的反复轮询，简化了分配操作，通过仿真分析，表明这一方法可以有效地缩短MFTDMA系统的时隙分配时间。

［1］PARK J M，CHONG E K P，SIEGEL H J.Allocation of QoS Connections in MF-TDMA Satellite Systems:A Two-Phase Approach［J］.IEEE Transactions on Vehicular Technology，2005，54(1):177-190.

［2］刘丽宏，孙晨华.MF-TDMA系统时隙分配算法的研究［C］∥第23届全国通信与信息技术发展研讨会，2006:313-316.

［3］董启甲，张军，张涛.星上MF-TDMA系统信道管理方法［J］.电子与信息学报，2009(10):2378-2384.

［4］董启甲，张军，张涛，等.高效MF-TDMA系统时隙分配策略［J］.航空学报，2009(9):1718-1726.

［5］郝学坤，孙晨华，李文铎.MF-TDMA卫星通信系统技术体制研究［J］.无线电通信技术，2006，32(5):224-228.

［6］刘丽宏，李维，刘海建.TDMA帧结构研究［J］.无线电通信技术，2007，33(4):5-7.