一种改进的First-fit载波分配算法

尹　译　梁　俊　宋爱民　肖　楠　王　轶

(空军工程大学信息与导航学院　陕西 西安 710077)



一种改进的First-fit载波分配算法

尹译梁俊宋爱民肖楠王轶

(空军工程大学信息与导航学院陕西 西安 710077)

摘要针对MF-TDMA卫星网络中利用First-fit算法进行载波分配时出现的时隙碎片问题，构建出支持时隙调整的载波时隙管理模型，并在模型基础上提出一种改进的支持时隙调整的First-fit载波分配算法。在该算法中，载波在首次分配失败后将对空闲时隙进行位置调整，构建与业务相匹配的时隙组，最终实现接纳业务的目的。仿真结果表明，该算法能有效提升载波剩余容量利用率，降低新到达业务的被拒绝率。

关键词卫星网络载波分配装箱问题利用率时隙组

AN IMPROVED FIRST-FIT CARRIER ALLOCATION ALGORITHM

Yin YiLiang JunSong AiminXiao NanWang Yi

(School of Information and Navigation, Air Force Engineering University, Xi’an 710077，Shaanxi,China)

AbstractCarrier allocation with traditional First-fit algorithm will easily produce slot fragments in MF-TDMA satellite communication network when system accepts new services. To solve this problem, we built a carrier slots administration model supporting slots adjustment. Based on this model, we presented an improved First-fit algorithm which allows the adjustment of slots. In this improved algorithm, carrier will adjust the positions of idle slots after the failure in first allocation, and the system will try to build a new slots group matching the services, and finally achieves the goal of service admission. Simulation result indicated that the adjustment-allowed algorithm could efficiently raise the use ratio of carriers’ residual capacity and decreased the rejecting possibility of newly-arrived services.

KeywordsSatellite networkCarrier allocationBin packing problemUse ratioSlots group

0引言

随着卫星通信技术的不断发展，业务传输质量与有限通信资源的矛盾日益突出。作为解决该矛盾的关键技术之一，卫星资源管理技术在DVB、IP和ATM卫星通信系统中均得到广泛应用。卫星资源管理主要研究如何充分地利用现有通信资源，为用户提供尽可能高的服务质量。目前卫星资源管理技术的研究热点主要集中在带宽分配上，文献[1]提出了一种比例公平注水迭代算法，能够最大程度保证用户间的公平性，但是带宽利用率偏低。文献[2]针对动态带宽分配问题，利用流量预测对带宽需求进行估计，提升了链路使用效率。文献[3]在带宽分配中引入经济学中效用的概念，建立起基于效用函数的带宽动态分配模型，求解出最大效用的带宽分配方案，改善了DVB-RCS卫星网中吞吐量偏低的问题。文献[4]提出了一种基于令牌桶的改进带宽分配算法，将用户按照优先级和权值进行划分，实现了按照用户重要性对带宽的二次分配。

在MF-TDMA卫星通信体制中，带宽分配实质上可划分为载波分配和时隙分配两步进行[5]。某条载波被分配给业务的条件是空闲容量必须与业务需求相匹配，否则系统将为业务选择其余载波。为解决如何分配载波的问题，文献[6]将载波分配抽象为一维装箱问题[7]，提出了一种First-fit载波分配算法。但是该算法在分配后存在时隙碎片的问题，阻碍了载波剩余容量利用率的提高。为解决时隙碎片问题，本文对First-fit载波分配算法进行了改进，构建出支持载波内时隙调整的管理模型，并在该模型的基础上设计了支持时隙调整的First-fit载波分配算法，允许系统在载波内进行业务时隙位置的调整，使载波能够容纳更多业务，提高了载波的利用率。

1时隙碎片问题

在MF-TDMA卫星网络中，时隙分配分解为两步完成：第一步为业务分配载波；第二步在载波内进行具体时隙划分。在第一步中，载波被分配给业务的前提是载波中空闲时隙的数目、位置能分别满足业务对时延和时延抖动要求。用户业务类型不同，对时隙数量和分布均匀性的要求也不同，例如高速数据传输仅需要满足时隙数目要求，而语音、视频等对时延敏感的业务还关注时隙分布均匀程度。由于载波中空闲时隙分布呈现随机性，剩余时隙的均匀性可能难以满足新到达业务对时延抖动的要求[5]。因此在设计载波分配算法时，需要同时考虑时隙数目和分布两个因素的约束。

装箱模型是统筹学中的典型NP-Hard问题[8]，其主要解决的问题是如何利用最少的箱子装下大小不同的货物，这与载波分配问题在本质上是相同的。文献[6]中提出将载波分配转化为带时隙均匀性约束的一维装箱问题，并利用装箱问题中的First-fit算法[9]进行解决。 First-fit算法是一维装箱问题中的经典算法，其基本思想是：对箱子依次进行编号，始终将新到达的货物装入编号最小且能够容纳其的箱子中，若已有非空箱子都无法容纳货物，则启用新箱子装载货物。First-Fit载波分配算法遵从上述思想，将载波、业务分别抽象为箱子和货物，结合业务的具体需求判别和选择承载载波，具体过程如图1所示。

图1　传统First-Fit载波分配算法示意图

上述载波分配算法根据业务所需时隙数目对所有已用载波依次进行遍历。若找到时隙数目符合要求的载波，则进一步考察载波中空闲时隙分布均匀性是否能满足业务要求，在判定时隙分布均匀性符合要求后，系统选择该载波承载业务。若所有载波都不能同时满足时隙数目和均匀性要求时，系统判定对已有的载波进行分配失败，将启用新的空载波传输业务。该算法存在的主要问题是在剩余时隙数目足够的条件下，部分载波的时隙分布均匀性达不到业务要求导致分配失败，遗留下大量空闲的“时隙碎片”，不利于载波利用率的提高。

为消除空闲的时隙碎片，必须在载波中调整时隙碎片的位置，以适应新到达业务的需求，这是本文改进算法的出发点。为实现上述时隙调整过程，首先需构建一种支持时隙调整的管理模型，对载波空闲时隙的数目和分布进行建模管理，以明确当前载波所能提供的时隙资源现状。然后在载波分配过程中设计合理的调整机制以改变空余时隙的分布状态，使其尽量能与业务需求相匹配，以期望利用最少的载波容纳下最多的业务。

2时隙管理模型设计

时隙管理模型是进行时隙分配的前提，其任务是描述载波中时隙可用状态及分布，并将结果传递给资源管理器，由资源管理器决定具体为连接请求分配哪些时隙。传统的时隙管理方式是按帧中顺序对时隙进行编号，并以帧为基本单位[5]对时隙进行统计和分配，实现起来简单方便。这种离散的时隙管理模型虽然能够清晰标识出空闲时隙，但是在时隙分布均匀程度的表示和带宽分配的灵活性上遇到困难，不利于时隙调整的必要性判断和执行方案的制定。本文设计一种基于时隙组的管理模型，从时隙管理的基本单位出发解决了上述问题。

以帧中包含n个时隙的载波为例，首先按传统的编号方式对连续m帧的时隙进行编号s1,s2,…，sn×m，对于编号为k的时隙，根据如下过程生成在矩阵中对应的位置(i,j)：

(1)

j=mod(k,t)

(2)

(3)

(4)

(z=1,2,…)

将满足上述条件的等距时隙构建为时隙组，作为资源管理的基本单位。由于时隙组内的时隙遵从相对均匀分布，占用时隙组的业务将获得良好的时延性能[10]，能有效避免出现大的时延抖动。考虑到α、β取值的特殊性，构建过程中可能会出现时隙重复划分的现象，例如某方阵中对角线时隙组和第一列时隙组均包含s11，而星上资源管理器不可能将s11同时分配给两个连接请求。为避免该问题，约定以下时隙组构建规则：

① 时隙不能同时划分给多个时隙组；

② 模型初始化过程中，时隙组的成员时隙必须来源于同一列；

③ 同列的时隙组成员间必须具有相等列间距；

④ 在满足②、③的基础上，允许时隙组进行合并或等分；

⑤ 时隙组与业务必须确定单对单的服务关系，否则将对时隙组进行拆分。

上述准则可保证构建完毕后每列剩余时隙仍可构成时隙组，同时允许时隙组根据业务需求对时隙组进行合并或拆分。下面对如何确定时隙组包含时隙数量进行讨论。

传统时隙管理模型将时隙作为提供带宽的基本单位，分配给业务的带宽必须是基本带宽的整数倍。以文献[11]中MF-TDMA系统参数为例，管理模型的单位带宽：

(5)

当系统进行带宽分配时，单个业务连接获得带宽：

B=M×64 kbps

(6)

(7)

如表1所示(假定矩阵中每帧组成一行)。

表1　基于时隙组的管理模型单位带宽

表1中随着矩阵包含帧数越大，载波提供的单位带宽越小。一方面，相比于式(6)中缺乏灵活性的整数倍带宽分配，基于时隙组的管理模型中单位带宽较小，允许系统每隔n帧分配一个时隙，提高了时隙分配的“精度”，使系统更加自由地分配和调整业务占用时隙位置成为可能。例如某业务需要192 kbps带宽，其在两种管理模型下的实现如图2所示。

图2　业务在两种管理模型下的实现

图2中，传统管理模型需要在每帧中寻找3个空闲时隙提供给业务，否则将选择其他载波。而在基于时隙组的管理模型中，由于系统以时隙组为单位进行时隙管理，只需在矩阵中提供任意包含12个时隙的时隙组(图中分配编号为1、2、3、4的时隙组)，仍然能满足业务的带宽需求，提高了时隙分配的灵活性。

另一方面，在不同的资源管理模型下，相同连接请求所需的时隙数目是不同的，其中传统资源管理模型所需的时隙为：

(8)

而基于时隙组的管理模型为：

(9)

对比式(8)、式(9)，可以证明降低单位带宽确实能避免资源浪费，提高时隙的利用率。

对于GEO卫星网络而言，地面用户在计算时隙组大小N′后，向星上资源管理器提出带宽申请[12]，卫星将结合业务时隙均匀性要求和现有空余时隙组分布判断载波分配的结果并传回地面。由于星地时延的存在，申请到返回结果的时延将略大于270 ms。

3支持时隙调整的First-fit载波分配算法

根据接入业务对时隙分布均匀性要求不同，可将业务划分为严格要求、有限要求和无要求三类。严格均匀性要求业务是指部分高质量传输服务，对时延抖动要求十分苛刻，分配的时隙组必须遵从完全均匀分布。有限均匀性要求业务的传输质量、时延抖动要求都有所降低，时隙的分布只需满足近似均匀即可。无均匀性要求业务只对时隙数目有要求，在分配时不考虑时隙是否均匀分布。

载波中时隙位置的调整必然带来时隙间相对位置的变动，根据调整行为发生的位置以及对业务产生影响大小，定义以下四种时隙调整行为。

1) 时隙组调整时隙组调整是指由于某些时隙组构建的需要，将现有时隙组进行整体性移动，如图3所示，时隙组内成员的相对位置不变，不会影响业务时隙的均匀性分布。此类位置调整对业务无任何显著影响，适用于所有类型的业务。

图3　时隙组调整

2) 时隙组内调整为新业务构建时隙组时，某些条件下必须对时隙组内部进行位置调整，如图4所示，导致时隙组内部分布均匀性发生变化。为衡量原业务对上述调整的容忍程度，设定参数qmax衡量单个时隙允许调整的最大位移：

qmax=λ·l

(10)

其中l表示在调整前时隙组内时隙间距；λ表示业务对调整容忍程度，根据业务的不同存在差异，一般条件下严格均匀性要求业务λ=0，有限均匀性要求业务取值为0<λ≤0.3，无均匀性要求业务λ=∞。业务的qmax越大，表明时隙调整对其影响越小。

图4　时隙组内调整

3) 载波间迁移时隙位置调整中允许改变承载业务的载波，即业务由原载波迁移到另一目标载波，如图5所示。对业务进行载波间迁移需满足以下两个条件：(1)原载波在构建新时隙组时需要使用业务已占用的时隙。(2)目标载波存在满足相应需求的空闲时隙组以接纳业务。若无法同时满足上述条件，则时隙调整失败，不能在原载波中构建新时隙组。在业务载波间迁移时，由于目标载波的时隙组分布均匀性存在差异，可能伴随着1)和2)的发生，系统在业务迁移前必须考虑式(10)的约束是否得到满足。在调整后，业务将在新的载波上继续运行，对业务的影响与2)相同。

图5　载波间迁移

4) 无序调整无序调整是指破坏已有业务时隙组，将业务无序分布到新的空闲时隙组中。这类时隙调整不关注时隙的均匀性，只要求新的时隙组能够接纳业务，对时隙组的选择存在随意性，仅适用于无均匀性要求业务。

在时隙数目达到要求的条件下，系统的时隙调整行为允许载波重新整合自身的空闲时隙，构建出满足新业务需求的时隙组。将上述时隙调整行为引入First-Fit载波分配算法中进行改进，利用载波时隙的“可调整”特性提高载波中时隙利用率，改进算法的具体过程如图6所示。

图6　支持时隙调整的First-fit载波分配算法示意图

在上述载波分配过程中，在剩余时隙组与业务需求的匹配失败后，系统将进入时隙调整阶段，以生成与新业务相匹配的时隙组为目标执行调整。若成功生成目标时隙组，进行业务分配并结束，否则将继续与其余载波进行匹配比较。当遍历完所有载波仍未完成分配，则启用新的空载波承载业务。

4仿真与性能分析

为验证支持时隙调整的First-Fit载波分配算法的对载波利用率的改进效果，构建基于STK/MATLAB软件的网络仿真环境，以模拟业务到达后被载波接纳的情况。其中STK模拟卫星的轨道位置、传输时延和信噪比等参数，MATLAB计算业务时隙需求和载波剩余容量。

1) 仿真参数设置

假定MF-TDMA卫星系统包含16条载波，载波中每帧包含64个时隙。一共设置8个业务源，通过地面信关站进行集中的时隙申请，网络拓扑结构如图7所示。卫星选取同步轨道卫星(双向时延270 ms)，信道中信噪比设置为18~20 dB，保证信关站与卫星之间能够顺利完成信息交互。

图7　仿真网络拓扑图

在用户端的设置如下：业务到达的过程服从泊松分布，且以概率P=0.5出现对时隙均匀性的要求；每个业务请求的时隙数目在[0,16]上呈均匀分布，调整容忍程度λ=0.25。为了简化仿真过程，规定业务在被载波接纳后不会结束服务，意味着被业务占据的时隙在仿真中不会释放。

2) 性能指标的选择

为合理检验算法载波分配过程中载波利用率的改进，需分别从载波时隙和业务接纳的角度进行考察。选取载波平均利用率α用于衡量载波时隙的使用情况，其定义为：

(11)

选取业务拒绝率β衡量算法对新到业务的接纳能力，其定义为：

(12)

3) 仿真过程与分析

为对照检验改进算法性能的提升，在仿真中设置实验组A和对照组B，分别采用支持时隙调整的First-fit载波分配算法和传统的First-fit载波分配算法，其余仿真环境与前述1)中配置相同。

仿真中对每项到达业务的状态进行监测，确定其是否被系统接纳，并据此计算出相应α和β值变化。当系统不再接纳业务时表明系统容量已经饱和，中止仿真并记录结果。仿真结果如图8、图9所示。

图8　两种算法的载波利用率α

图9　两种算法的业务拒绝率β

图8中在业务申请数较少时，载波中时隙资源相对充足，曲线只随业务的时隙需求变化，无时隙碎片产生，两种算法的载波利用率曲线重叠。随着业务申请的增加，传统的First-fit载波分配算法的载波利用率将低于改进的分配算法，这是因为在高业务到达率的条件下，空闲时隙的非均匀分布会导致时隙碎片的产生，传统First-fit载波分配算法无法处理这些碎片，造成资源浪费；而引入调整机制的改进算法中，系统能主动对载波内空闲时隙的位置进行调整，以构建出能够接纳业务的新时隙组，减少了时隙碎片的产生，改善了载波的利用效率。

在图9中，First-Fit载波分配算法存在较高的业务拒绝率，而改进后载波分配算法的业务拒绝率要显著低于原算法。这种差异的原因在于两种算法拒绝接纳业务的条件不同，原算法在寻找能够接纳业务的时隙组失败后就拒绝接纳；而改进算法在无法找到时隙组时会尝试构建新时隙组，在寻找和构建均失败后才进行拒绝，这样后者能够显著提升载波接纳业务的能力，降低业务被拒绝的概率。

5结语

针对MF-TDMA卫星网络中利用First-fit算法进行载波分配时出现的时隙碎片问题，本文构建出支持时隙调整的载波时隙管理模型，并在模型基础上提出一种改进的支持时隙调整的First-fit载波分配算法。在该算法中，系统以匹配新业务为目标进行载波调整，尽量使业务选择利用率已经较高的载波，最大程度上对剩余空闲时隙进行了利用，在考虑时隙数目和位置的基础上，提高了原算法的载波利用率，降低了新业务的被拒绝概率。但是，本文在设计和仿真中未考虑载波的调整运算的复杂性对系统性能带来的影响，有待于在以后的研究中进行完善。

参考文献

[1] Morell A, Seco-Granados G, Vazquesz-Castro M. Cross-layer design of dynamic bandwidth allocation in DVB-RCS [J].IEEE Systems Journal, 2008,2(1):62-73.

[2] 秦勇,张军,张涛.基于带宽按需分配的DVB-RCS宽带卫星MAC协议[J].宇航学报,2010,31(3):838-844.

[3] 高鑫,王祖林.基于效用最大化的DVB-RCS跨层动态带宽分配[J].宇航学报,2011,32(4):857-862.

[4] 张文波,谭小波.一种改进的无线通信网络带宽分配方法[J].宇航学报,2012,33(12):1762-1767.

[5] 董启甲,张军,张涛,等.高效MF-TDMA系统时隙分配策略[J].航空学报, 2009,30(9):1718-1725.

[6] Park J M, Savagaonkar Y, Chong E K P, et al. Allocation of Qos connections in MF-TDMA satellite systems: a two-phase approach [J]. IEEE Transactions on Vehicular Technology,2005,54(1):177-190.

[7] 刘林浩,杨鼎强,王晨.一种带脆度的尺寸可变装箱问题[J].计算机工程与应用,2013,49(12):263-266.

[8] Poothokaran D, Shimakawa Y. A study on evaluation of multi-objective Bin Packing Problems[C]//Computers and Industrial Engineering(CIE), 2010 40thInternational Conference on. IEEE, 2010:1-6.

[9] 张雪,倪桂强,金凤林,等. MF-TDMA信道分配研究[J].计算机与数字工程,2010,38(11):58-60.

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

[11] Celandroni N, Secchi R .Suitability of DAMA and contention-based satellite access schemes for tcp traffic in mobile DVB-RCS[J]. IEEE Transactions on Vehicular Technology,2009,58(4):1836-1845.

[12] 秦勇,张军,张涛.DVB-RCS卫星系统无线资源管理体系架构[J].计算机工程与应用,2010,46(20):71-74.

中图分类号TN927.23

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.027

收稿日期：2014-09-09。陕西省自然科学基金面上项目(2012JM 8004)。尹译，硕士生，主研领域：卫星资源管理。梁俊，教授。宋爱民，高级实验师。肖楠，博士生。王轶，讲师。