均衡负荷

2024-10-23

均衡负荷（精选5篇）

均衡负荷篇1

1 概述

目前华为MSC Pool的负载均衡的原则 (NNSF分发) 一般是根据设计话务量来设置, 使Pool内各MSC达到话务量均衡的效果, 但由于现网设计容量属于商务购买的软件容量, 与安装配备的硬件容量往往存在不匹配的情况, 因此单纯按设计容量来设置NNSF分发, 容易导致Pool内各MSC的CPU负荷均衡性指标不理想。因此, 需要在满足节假日或其他造成话务量激增的重大事件中有一定容量冗余的前提下, 优先保证CPU负荷均衡性, 同时要满足MSC POOL内100%容灾率的条件, 计算出相对安全高效的NNSF分发值。

2 原理介绍

2.1 均衡性原理。

POOL中的NNSF实体 (RAN节点) 根据MSC Pool内各有效MSC的用户容量比例对用户进行分发, 由于POOL内各个局点话务模型都相同, 那么局点的用户数决定了这个局点的资源负荷, 用户数不同则资源负荷不同。判断负荷均衡的标准就是POOL内各个局点NNSF分发比例值是否合理。

2.2 均衡性定义。

均衡系数是体现MSCPOOL均衡性的一个量化指标, 它指MSCPOOL内各个局点的各种容量利用率和指标偏离平均值的离散程度, 其计算公式如下:

均衡系数 , 其中, Xi是POOL内各个局点的容量利用率或者指标, 是POOL内各个局点的容量利用率或者指标平均值, n是POOL内局点个数。以CPU负荷为例, Xi为单个局点各个CCU/CSU模块的均值, 则是根据Xi再次求均值所得。

一般均衡系数基线值为0.03。

2.3 容灾性定义。

POOL的容灾性是通过容灾率来进行量化表征。容灾率是体现MSCPOOL容灾能力的一个量化指标, 它指MSCPOOL内一个容量最大的MSCServer故障情况下, 剩下所有MSCServer的设计总容量与MSCPOOL实际容量的比值, 其计算公式如下:

3 均衡性优化过程

下面通过一个均衡性优化的实例对该算法进行详细说明。该实例中的Pool1内共7个MSC_server, 原均衡性评估如表1。

可见, 以均衡系数基线值为0.03, POOL1各个局点忙时话务量容量利用率均衡, 而用户数容量利用率和CCU (CSU) 模块的CPU占用率都不均衡。

3.1 NNSF用户分发值计算过程。

需要改善POOL1内各MSC间CPU负荷不均衡的现状, 必须调整NNSF用户分发比例, 其计算过程如下:a.根据话务模型不变的前提下, CPU占用率和用户数 (分发值) 之间近似线性的关系, 即最优分发值一=现有分发值× (各局点CPU占用率均值-CPU空载负荷) / (局点当前CPU占用率-CPU空载负荷) , 算出在此分发值下各个局点的分发比例。其中CPU空载负荷为5%。b.验证在最优分发值一下各局点的话务量、用户数比例是否超过扩容基线0.7, 基线的限制是为了保证在节假日等大话务量的冗余, 基线定为70%则该局点在节假日下能满足话务量 (1-70%) /70%=42.9%的增长。

话务容量利用率冗余=预测话务容量利用率-扩容基线-0.01 (冗余为负值, 则代表局点话务量未超过扩容基线, 冗余为正值, 则代表局点话务量超过扩容基线) 。分摊话务量比例=各局点分发值/ (所有局点分发值的总和-容量超标的局点分发值) , 仅对话务量未超过基线的局点需要计算。对于预测话务容量利用率超过基线的局点, 最终分摊话务量=设计话务量× (扩容基线-0.01) 。

其中, 预测话务量=POOL内总话务量×调整后的分发比例, 预测用户数=POOL内总用户数×调整后的分发比例,

对于预测话务容量利用率未超过基线的局点, 最终分摊话务量=预测话务量+∑局点n超出部分话务量×分摊话务量比例:

超出部分话务量=预测话务量×话务容量利用率冗余

从上面计算看出, POOL1中硬件用户数容量充足, 因而只需要根据话务量容量进一步调整NNSF分发值。c.最终分发值计算:调整后最终的分发比例=最终分摊后话务量/POOL忙时总话务量, 调整后分发值二=调整前分发值×调整后分发比例/调整前分发比例, 取整操作:对调整分发值进行十位数取整, 计算调整前后总和差值, 如果差值超过调整前总和, 则差值在最高CPU值的局点分发值中依次按步长为10递减。反之, 差值小于调整前总和, 则差值在最低CPU值局点分发值中按步长为10递增见表4。d.得到的新分发值需验证容灾率的满足情况, 容灾率满足要求即目标NNSF值可作为优化值输出, 不满足则在最新分发值基础上以10为步长微调分发值, 降低话务量 (用户数) 利用率超过1局点的分发比例, 为保持总的分发值一致, 需要同时相应地增加CPU负荷较低局的分发值。单个网元故障后话务量容灾率: (话务量利用率不能超过1, 超过1代表有呼损) 。单个网元故障后用户数容灾率: (用户数利用率不能超过1, 超过1代表有呼损) 。容灾下的分发值=扣除最大局点分发值后各局点的分发值 (见表5) 。e.根据新分发值下各局点目标用户数与现有用户数情况对比, 得到各个局点需要调整的用户数 (见表6) 。

3.2 优化效果验证。

在扩容基线定为70%的情况下进行首次优化操作, POOL1各局点忙时CPU均值差值缩小, CPU均衡系数从0.0623 (均衡度93.77%) 提升到0.0349 (均衡度96.51%) 。将扩容基线放宽为80%下进行第二次优化操作, POOL1各局点忙时CPU均值趋于一致, CPU均衡系数从0.0351 (均衡度96.49%) 提升到0.0176 (均衡度98.24%) 。

结束语

由于各局点硬件配置、设计容量的不一致, 导致MIP中话务量、用户数和CPU负荷和均衡性难以全部满足。目前现网的NNSF用户分发值都是按照设计话务量来确定, 因此各局的话务量均衡性都合格, 但是CPU负荷的均衡性稍差, 因此文章最后给出两点建议:

建议一.由于CPU负荷关系到网元运行的稳定性, 因此对于各局点CPU负荷存在明显不均的情况建议进行优化。

注:目标用户数=调整后分发比例×POOL忙时总用户数

建议二.如果需要优先保证CPU负荷均衡性, 则需要对话务容量利用率较高的局点进行软、硬件的扩容, 达到话务容量利用率的均衡。

均衡负荷篇2

任务分配是各类系统提高效率的基础和关键, 受到机械工程、计算科学和运筹学的广泛关注。任务分配问题既是一类典型的组合优化问题又是一类常见的NP-Complete问题, 近年来出现的一些启发式算法 (如模拟退火、遗传算法及蚁群算法等) 为解决此类NP-Complete问题提供了新的途径。以下将免疫算法 (Immune Algorithm, IA) 引入到考虑任务协作的面向负荷均衡的任务组合优化分配中, 这种基于群体的随机搜索算法能有效克服其他智能算法的早熟现象、群体多样性不足及搜索速度慢等问题。通过免疫选择、免疫自调节、疫苗接种等免疫机制, 提高搜索效率, 加快全局收敛的速度, 在合理的时间内得到协作任务分配的优化解。

2 基于IA的协作任务优化分配算法

免疫算法是模仿生物免疫系统处理机理和基因进化机理, 通过人工方式构造的一类全局寻优搜索算法。尽管免疫系统具有许多优良的计算性能, 但现有免疫算法模型仍存在一些问题, 主要在抗体的评价形式、抗体的促进和抑制以及记忆库的使用上。抗体评价主要依据抗体与抗原的亲和度, 促进高亲和度抗体和抑制低亲和度抗体, 往往易陷入局部优化, 导致“早熟”。并且, 记忆库仅在产生初始种群时被使用, 在算法以后的过程中仅更新记忆库而不再利用它, 这没有起到加速收敛的效果。葛红等对免疫算法进行了改进, 根据期望繁殖率对抗体降序排列, 然后一次性消除期望繁殖率低的抗体, 试验表明收敛速度有所提高, 但这会使不少较优抗体被一块消除, 不利于有效提高收敛速度。针对现有免疫算法的不足, 提出了基于动态任务资源匹配矩阵的免疫算法, 其主要流程见图1。

免疫进化时首先进行抗原识别, 分析问题及解的特性并进行抗体编码, 本文采用K进制编码, 对参与协同工作的工作中心资源按1, 2, …, K进行编码, 抗体长度为任务数N。若抗体第i个基因位对应的值为p, 则表示任务i被分配到工作中心p进行生产加工。此编码直观, 易于操作, 且不需解码。

免疫进化过程中, 首先根据任务资源匹配初始矩阵随机产生规模为popsize的初始抗体群体antiby (t) 。抗体群体根据抗体繁殖率进行免疫选择, 高繁殖率的抗体 (优化解) 被促进, 低繁殖率的抗体 (非优解) 被抑制。通过促进/抑制抗体的进化, 既突出适者生存, 又防止个别个体绝对占优, 实现免疫系统的动态平衡自调节功能。在这些必要、有效的抗体群体基础上进行免疫操作。经过免疫操作进行免疫进化后, 将会产生免疫接种抗体种群antiby_v、交叉克隆的抗体种群antiby_c、亲和突变的抗体种群antiby_m, 以及募集的新的抗体种群antiby_n, 将这些免疫种群与记忆的较优抗体种群antiby_o合并, 生成下一代免疫进化的抗体种群antiby (t+1) 。再在此进化基础上循环进化, 直到满足进化的终止条件, 输出免疫进化的结果。

2.1 抗体的评价与选择

免疫进化过程中, 需要对各抗体进行评价。如果以抗体的适应度为评价指标, 当群体中的某个抗体占据了相当规模, 而又不是最优解时就极易导致过早收敛。采用抗体浓度来抑制规模较大又不是最优解的抗体, 并以信息熵作为衡量相似度的指标, 以期望繁殖率作为评价抗体的标准。抗体v的繁殖率ev计算如下:

undefined

undefinedlogP′pi

式中, fit (v) :抗体v的适应度;F (v) :将抗体v作为分配方案代入目标函数时对应的函数值;cv:抗体浓度;λac:亲和度阀值;αxv, w:抗体v与抗体w之间的亲和度;H (2) :抗体v和抗体w的信息熵, 两抗体所有基因都相同时, H (2) =0;N:抗体的基因长度, 即为待分配任务数;Hi (2) :两个抗体第i个基因位的信息熵;Ki':第i个基因位可选字符个数, 其代表满足任务特性约束, 可完成第i个任务的工作中心个数。

由式1显见, 抗体的期望繁殖率刻画了适应度、亲和度和浓度的关系, 综合考虑了抗体与抗原之间的关系 (即抗体的适应度) 、抗体与抗体之间的关系 (通过抗体的亲和度来评价抗体间的相似程度, 抗体的浓度来表示抗体与其相似的抗体的规模) 。

免疫选择是指在抗体群中依据抗体的期望繁殖率选择抗体。从免疫机理的角度, 免疫选择反映了抗体选择的不确定性以及抗体的抑制与促进机制。本文中按照比例选择规则选择抗体种群中的抗体。在免疫种群G中抗体si被选择的概率如式2:

undefined

2.2 疫苗的抽取与接种

有效的疫苗对算法的收敛性和有效性具有重要的正面作用, 本算法从动态任务资源匹配矩阵中抽取疫苗, 每代进化过程任务资源匹配矩阵是动态更新的, 通过该方式来获得有效的疫苗, 在深层次上隐含了疫苗也是随抗体进化而不断进化的思想, 更加符合生物的进化规律。通过式3计算免疫进化过程中每代对应的任务资源匹配矩阵, 其中Ppi表示第i个基因位出现p的概率;gv (i) 表示个体第i个基因位的编码值。根据任务资源匹配矩阵中Ppi值, 当某等位基因上的概率Ppi最大且大于某个设定阀值时, 将其作为该等位基因上的疫苗, 最终提取的疫苗如式4所示。

undefined

疫苗接种进行特异性免疫 (Specific Immunity) , 有导向性地产生特异性抗体, 利用待求解问题的先验知识有效地加速算法的收敛。针对每代进化得到的抗体种群, 以事先设定的免疫概率, 随机选择父代群体中要进行接种的抗体g1。对选中的抗体g1, 将疫苗Y的基因码依次接入, 通过置换抗体相应基因位置上的码值产生新的免疫抗体g2, 最终形成免疫种群antiby_v。疫苗接种的一个示例如图2所示。

2.3 抗体交叉与变异

交叉是在肯定基因位进化的基础上, 通过基因重新组合产生新的抗体, 使子代能够继承父代的优良基因, 优秀抗体的基因模式得以迅速繁殖并在种群中扩散, 使进化向最优方向进行。当交叉由于基因的局部相似而无法产生新的抗体时, 通过变异可避免寻优过程陷入局部最优, 改善种群的多样性, 引导进化探索新的搜索空间。

本文算法的交叉/变异操作采用两点交叉/变异。对于交叉操作, 根据交叉概率, 随机的从免疫种群中选取两个抗体g1和g2作为父代, 在g1中随机选取两个非零且不相等的基因位x1和x2, 从而得到交叉区间 [min (x1, x2) , max (x1, x2) ], 在g2上找到对应的交叉区间, 将这两个区间内基因互换, 就产生了两个新的子代抗体g3和 g4, 这些子代抗体最终组成一个交叉种群antiby_c。对于变异操作, 根据变异概率, 随机从免疫种群中选择抗体g1。在g1中随机选取两个非零且不相等的基因位x1和x2, 得到变异区间[min (x1, x2) , max (x1, x2) ], 对该区间上每一个基因位, 根据动态任务资源匹配矩阵相应的选择概率, 重新组合该区间上的基因, 从而形成新的抗体g2, 这些抗体最终组成变异种群antiby_m。

2.4 算法的特点分析

在本文算法中, 免疫选择将进化群体中较好的候选解确定性地选择参与进化, 提供开拓更好候选解的机会。免疫记忆不仅为问题的解决提供高效求解的机会, 而且为算法的局部搜索提供必要的准备。这一操作与抗体交叉操作及亲和突变操作共同作用, 增强算法局部搜索能力, 使算法有更多机会探测更好的候选解。浓度抑制可确保种群中相同或相似的抗体不会大量繁殖, 其作用不仅在于保存好、中、差的抗体, 而且减轻了免疫选择算子选择存活抗体时的选择压力。免疫选择的作用在于:不仅给适应度高的抗体提供更多选择机会, 而且也给适应度及浓度皆低的抗体提供生存机会, 使得存活的抗体种群具有多样性, 这一机制主要反映了抗体促进和抑制机理以及抗体选择的随机性。本文在抗体种群初始化与募集新成员时, 采用基于动态任务资源匹配矩阵的抗体产生方法, 通过该方法产生的抗体能够微调群体多样性及增强全局搜索能力, 而且由于考虑了动态的任务资源匹配概率, 能够加快算法的寻优速度, 同时使算法随时有自我抗体被引入而具有开放式特点。这些算子相互作用, 使算法具有如下特点:

1) 抗体的选择受适应度与浓度的制约, 是确定性和随机性的统一。

2) 抗体交叉与变异体现了邻域搜索及并行搜索的特性。

3) 搜索过程中处于开采、探测、选择、自我调节的协调合作过程, 体现了体液免疫应答中抗体学习抗原的行为特性。

4) 搜索过程处于开放, 随时有自我抗体被加入进化群体, 以增强群体多样性, 提供产生更好解的机会的同时能够加快算法的寻优速度。

3 仿真

算法仿真环境为Windows XP操作系统, 3.0GHz CPU, 1G内存。仿真工具采用Matlab7.0。基于动态任务资源匹配矩阵的免疫算法参数选取为:进化代数100, 种群规模50, 种群中交叉产生的个体比率为0.4, 变异产生的个体比率为0.2, 接种疫苗的个体比率为0.2, 募集的新个体比率为0.1, 记忆的优良个体比率为0.1, 优异基因抽取阀值为0.85, 亲和度阀值为0.85。

在算法运行初期, 会出现优异的基因未能达到抽取的阀值, 导致在接种操作时无疫苗使用, 而能够体现基因特异性信息的任务资源匹配矩阵随着抗体种群的进化而不断进化, 因此, 此时采用依据动态任务资源匹配矩阵产生新的抗体种群是疫苗接种种群的最佳替代, 可有效避免无疫苗可用而引起的算法的寻优效率降低的缺点。对本文第一节中的示例问题进行仿真, 该问题中所有工作中心的初始负荷为0, 其免疫进化过程如图3所示。

至图3中标识了每代最优任务分配方案对应的目标函数值、协作成本函数值及平方和函数值, 分别对应目标函数值及目标函数中第一、二部分的函数值。其中目标函数值与协作成本函数值共用图中左侧纵坐标轴, 平方和函数值使用右侧纵坐标轴。从图中可见, 算法进化第44代取得最优分配方案。由于该问题中设定K′i=K, 决定了工作中心之间具有互换性, 因此算法进化过程中将寻找到多个最优分配方案, 并且当K′i=K且初始负荷为0, 多个最优方案中的任何一个方案对于该问题都是无差别的。表1给出了最优任务分配方案。

图4标识了该最优分配方案对应的各工作中心的能力、负荷、利用率、最高利用率、平均利用率及最低利用率状态。综合图3与图4可见, 本文提出的算法实现了平衡各工作中心的负荷的同时最小化企业的协作成本。

在实际的企业运作中由于有新项目订单情况, 存在为新增加任务进行分配的问题, 解决该问题有两种方式:一是将新任务与原任务作为一个整体重新进行任务分配;二是在保持原任务分配方案不变的前提下, 对新增加的任务再分配。现假设企业有新项目订单到达, 需对新增任务进行分配。图5给出了新增任务的任务关联图, 新增任务的任务资源匹配初始矩阵如表5所示。

第一种方式采用本算法重新计算即可, 但在实际生产中由于产生的分配方案将作为计划调度等系统的重要数据输入, 该种方式不但涉及到任务重分配计算成本, 而且还将涉及到重计划/调度等成本。故在实际应用中, 该方式较第二种方式虽然可能获得相对较高质量的解, 但仍较少采用。下文给出了在保证原分配方案不变的基础上, 运用提出的免疫算法对新增任务进行分配, 即动态的任务再分配。由表5可知, 此时问题的初始状态为K′i≠K, 且由于是在已有任务分配的基础上进行任务分配, 所以各工作中心的初始负荷不为0。因此, 对新增任务进行再分配, 不仅可以验证该算法在处理新增任务分配问题的灵活性, 同时还可以将其作为一个当K′i≠K且初始负荷不为0的新的任务分配问题 (K′i≠K、初始负荷不为0, 更能代表企业实际运作中的多工作中心任务分配问题) , 说明算法在解决实际的多工作中心任务分配问题的实用性。

表3给出了新增任务在表1给出的任务分配方案的基础上, 进行任务再分配获得的新增任务的优化分配方案。图8给出了任务再分配后新的优化方案对应的工作中心负荷状态。从图6中可以看出, 该任务再分配结果可以满足实际的生产需要, 同时验证了提出的算法在解决多工作中心任务组合优化分配问题的有效性。

4 结束语

从多工作中心协同工作的角度, 研究了面向负荷均衡的任务分配问题, 提出了用于解决该问题并支持任务重/再分配的免疫算法。运用免疫算法在求解多工作中心任务组合优化分配的过程中, 引入动态任务资源匹配矩阵的概念, 提高了算法的搜索效率。仿真实验表明该算法的有效性和实用性特点。

参考文献

[1]Kyung-Hyun Choi, Dong-Soo Kim, Yang-Hoi Doh.Multi-agent-based task assign-ment system for virtual enterprises[J].Roboticsand Computer-Integrated Managacturing.2007, 2:1-6.

[2]柴永生, 孙树栋, 余建军等.基于免疫遗传算法的车间动态调度[J].机械工程学报.2005, 41 (10) :23-27.

[3]张维存, 郑丕谔, 吴晓丹.基于主-从遗传算法求解柔性调度问题[J].计算机集成制造系统.2006, 12 (8) :1241-1245.

[4]Tung-Kuan Liu, Jinn-Tsong Tsai, Jyh-Horng Chou.Improve genetic algorithm for job-shop scheduling problem[J].The InternationalJournal of Advanced Manufacturing Technology.2006, 27:1021～1029.

[5]Jie Gao, Mitsuo Gen, Linyan Sun.Sched-uling jobs and maintenances in flexible job shop witha hybrid genetic algorthm[J].Journal of IntelligentManufacturing.2006, 17:493～507.

[6]黄席樾, 张著洪, 何传江等.现代智能算法理论及应用[M].1版.北京:科学出版社, 2005.

[7]蔡自兴, 龚涛.免疫算法研究的进展[J].控制与决策.2004, 19 (8) :841-846.

[8]葛红, 毛宗源.免疫算法的改进[J].计算机工程于应用.2002, 38 (14) :47-49.

均衡负荷篇3

侦察卫星等地球低轨道卫星每天获取的大量数据都需要通过地面站及数据接收天线(简称“数传资源”)传输到地面以供用户分析使用,由此产生的卫星数传调度问题就是在一定的规划调度周期TimeLine内,由m个不完全相同的数传资源R={R1,R2,…,Rm}执行n个相互独立的数传任务T={T1,T2,…,Tn},以满足数传任务的调度收益最大等目标。其中,每个任务Tj(j=1,2,…,n)具有优先级Tprij和任务最短持续时间Tdurj,以及由任务最早开始时间Tstj和最迟结束时间Tetj决定的任务执行时间窗口[Tstj,Tetj],任务Tj的可用数传资源集R(Tj)⊆R,显然R(Tj)≠∅,当任务要求频段Tbj与资源Ri(i=1,2,…,m)的频段Rbi一致时,两者之间具有可见时间窗口TWij=[TWstij,TWetij],其中Ri∈R(Tj)。

卫星数传调度问题研究中,李云峰建立了基于数传任务框架的卫星数传调度模型[1],先后提出基于试探性启发式调度算法、综合优先度调度算法和混合遗传算法[2,3,4]。Sylvain Damiani等将卫星数据下载调度作为一个独立于卫星侦察调度的决策问题, 建立了动态规划模型, 并用贪婪算法求解[5]。针对Gooly首先提出的SRS(satellite range scheduling)问题[6],L.Barbulescu证明了具有多资源的SRS问题是NP-hard问题[7],并证明了在大规模SRS问题中,遗传算法比传统启发式算法更具优势。针对COSMO-SkyMed星座中的SRS问题, Bianchessi等提出了具有前向搜索和反向回溯能力的构造算法[8]。N.Zufferey等借鉴图着色技术的基本思想,设计了禁忌搜索和适应存储两种算法求解多资源的SRS问题[9]。以上学者的研究,主要侧重于任务调度收益建模,强调的是任务调度完成的数量及价值收益,没有考虑执行任务的资源负荷均衡问题。实际上,一个合理的调度方案必须考虑到资源负荷的均衡性,否则就可能造成某些资源长期处于高负荷工作状态,而某些资源则总处于低负荷工作状态,资源负荷均衡性较差,显然不利于资源利用及人员配备。

通过对数传资源负荷进行定义与分析,建立基于资源负荷均衡的卫星数传调度模型,并提出基于蚁群算法[10]的模型求解算法, 在满足调度收益目标的情况下, 提高资源负荷均衡度,使调度方案更具合理性和可操作性。蚁群算法已在混合车间调度问题[11]、排列流水调度问题[12]、资源受限项目调度问题[13]中得到深入研究,并开始应用于航天调度领域[14,15],但是相关的算法只针对特定的问题。

2 模型建立与调度方案评价

2.1 数传资源负荷

引入0-1决策变量xij,任务Tj在资源Ri上执行数传时xij=1,否则xij=0。因此,可构造调度方案决策矩阵Xm×n.引入具有起止时间Dstij,Detij的时间窗口变量Dij=[Dstij,Detij],构造卫星数传调度方案矩阵Dm×n,Dij(i=1,2,…,m;j=1,2,…,n)表示数传任务Tj在数传资源Ri上的数传执行时间窗口,其长度为|Dij|=Detij-Dstij.当Dij⊆TWij时,任务Tj在资源Ri上执行数传,否则不执行数传,|Dij|=0。

时间窗口限制是卫星数传调度问题中的一个重要特征,数传任务的完成与时间窗口密切相关,因此,可以把时间作为资源负荷的度量依据。定义数传资源负荷为所有数传任务在某个数传资源上的数传时间之和。根据定义,资源Ri的负荷为 $C_{i}^{S c h e} (X, D) = \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}$ ,所有资源的负荷为 $C_{R}^{S c h e} (X, D) = \sum_{i = 1}^{m} C_{i}^{S c h e} (X, D) ‚ C_{R}^{S c h e} (X, D)$ 是上限为 $C_{R}^{\max} = \sum_{j = 1}^{n} Τ_{j}^{d u r}$ 的非常数,其均值满足 $\min_{1 \leq i \leq m} {C_{i}^{S c h e} (X, D)} \leq C_{R}^{S c h e} (X, D) / m \leq \max_{1 \leq i \leq m} {C_{i}^{S c h e} (X, D)}$ 。显然, 只要使得各资源负荷CSchei(X,D)之间的差值尽可能小, 资源负荷的均衡度就越高, 各资源负荷就越接近于CScheR(X,D)/m.由于资源负荷均值有界, 即CScheR(X,D)/m≤CmaxR/m,所以数传资源负荷均衡的调度问题必然收敛。

2.2 资源负荷均衡调度模型

卫星数传调度问题的主要优化目标是调度收益,一般情况下, 其调度收益取决于成功完成任务的数量、任务的优先级大小以及任务执行时间,因此可确定调度收益目标函数为成功调度任务数传时间优先级加权和最大。根据对数传资源负荷的定义与分析,在满足任务调度收益目标的情况下, 数传资源负荷越均衡, 其调度方案越合理, 因此可确定数传资源负荷差值最小为资源负荷均衡目标函数,建立如式(1)所示的基于资源负荷均衡的数传调度模型。

O1:

$\max \sum_{i = 1}^{m} \sum_{j = 1}^{n} Τ_{j}^{p r i} \cdot | D_{i j} | \cdot x_{i j}$

O2:

$\min {\frac{\sum_{i = 1}^{m} (\sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j} - \frac{\sum_{i = 1}^{m} \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}}{m})^{2}}{m}}^{1 / 2}$

s.t.

i=1,2,…,m

j=1,2,…,n

C1: xij=1, Tbj=Rbi

C2: xij=1, Dij⊆TWij

C3: $\forall j, x_{i j} = 1, Τ_{j}^{d u r} \leq \sum_{i = 1}^{m} | D_{i j} |$

C4: $\forall i, x_{i j} = 1, 0 < \sum_{j = 1}^{n} | D_{i j} |$

C5: ∀j, xij=1, Tstj≥min(Dst1j,Dst1j,…,Dstmj)

C6: ∀i, xij=1, Tetj≤max(Det1j,Det1j,…,Detmj)

C7: ∀i, xij=1, Di1∩Di2∩…∩Dmn=∅

C8: ∀j, xij=1, D1j∩D2j∩…∩Dmn=∅ (1)

其中,O1表示数传调度收益目标函数,其值越大越好;O2表示资源负荷均衡目标函数,其值越小越好。约束C1表示数传任务与数传资源天线频段必须一致;约束C2表示数传任务只能在与数传资源的可见时间窗口内执行;约束C3表示一个数传任务成功完成必须满足其最短持续时间要求;约束C4表示为了达到资源均衡调度,一个数传资源至少为一个数传任务提供服务;约束C5、C6分别表示任务调度必须满足最早开始时间和最迟结束时间要求;约束C7表示同一时刻一个数传资源只能为一个数传任务提供服务;约束C8表示同一时刻,一个数传任务只能在一个数传资源上执行。另外,数传资源在为不同任务提供数传服务时,还要满足设备状态切换时间要求。

2.3 调度方案评价

为了评估基于资源负荷均衡的数传调度模型所取得的调度方案,需要将调度模型中的两个目标函数的量纲相互统一,因此定义数传时间优先级加权满足度和数传资源负荷均衡度两个调度方案评估指标,分别评估调度方案的调度收益和资源负荷均衡度,然后基于这两个指标来设计调度方案的效能评估函数。

①数传时间优先级加权满足度

数传时间优先级加权满足度是成功调度数传任务的最短持续时间优先级加权和与所有任务最短持续时间优先级加权和的比值,由于分母为常量,分子为目标函数,所以该指标值越大目标函数O1值也越大。

$E Ι_{Τ} (X, D) = \frac{\sum_{i = 1}^{m} \sum_{j = 1}^{n} Τ_{j}^{p r i} \cdot | D_{i j} | \cdot x_{i j}}{\sum_{j = 1}^{n} Τ_{j}^{p r i} \cdot Τ_{j}^{d u r}} (2)$

②数传资源负荷均衡度

数传资源负荷均衡度是1减去资源负荷均方差与资源负荷均值的比值,由于资源负荷均值有界,当资源负荷均方差越小的时候,负荷均衡度越高,该指标值越大,其目标函数O2值越小。

$\begin{array}{l} E Ι_{R} (X, D) = 1 - \\ \frac{{(\sum_{i = 1}^{m} (\sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j} - (\sum_{i = 1}^{m} \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}) / m)^{2}) / m}^{1 / 2}}{(\sum_{i = 1}^{m} \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}) / m} \end{array} (3)$

③效能评估函数

数传时间优先级加权满足度和数传资源负荷均衡度两个评估指标分别反映了调度收益和资源均衡度两个目标函数的优化程度,由于需要对调度模型中的两个目标函数同时优化,在此定义如式(4)所示调度方案的效能评估函数,并以效能函数值的大小作为调度方案评估依据。

$\max E (X, D) = {E Ι_{Τ} (X, D)}^{γ} \cdot {E Ι_{R} (X, D)}^{λ} (4)$

式中,γ≥0表示调度收益评价指标(数传时间优先级加权满足度)的重要系数,λ≥0表示资源负荷均衡评价指标(数传资源负荷均衡度)重要系数。

3 蚁群解构造及算法流程

3.1 矩阵解构造图

J.Montgomery研究发现,在组合优化问题中,解的表示与信息素分布模型对于蚁群优化算法的应用至关重要[16,17,18]。针对卫星数传调度问题,构造矩阵解构造图模型G=(N,E),其中:N={Nij|i=1,2,…,m;j=1,2,…,n}为图G中结点集合,Nij表示任务Tj在资源Ri上执行调度;E={(Nij,Nkl)|i,k=1,2,…,m;j,l=1,2,…,n},其中(i≠k)||(j≠l)为图G中各结点之间的连接边或弧。

信息素分布于图G中各结点上,τij表示在结点Nij上的信息素浓度,是任务Tj在资源Ri上执行数传的期望。ηij表示人工蚂蚁经过结点Nij时,任务Tj在资源Ri上执行数传的启发式信息,可取如式(5)所示的数传时间满足度δ作为启发式信息,则可定义ηij如式(6):

$\begin{array}{l} δ = \frac{\min (Τ_{j}^{e t}, Τ W_{i j}^{e t}) - \max (Τ_{j}^{s t}, Τ W_{i j}^{s t})}{Τ_{j}^{d u r}} (5) \\ η_{i j} = {\begin{matrix} \min {1.0, δ}, & 0 < | Τ W_{i j} | \\ 0, & o t h e r w i s e \end{matrix} (6) \end{array}$

3.2 解构造过程

规模大小为Amax的蚁群中的每只蚂蚁在调度可行解构造过程中,首先从某个虚拟结点N0出发,根据图中结点上的信息素和问题启发式信息进行列选择,按照式(7)、式(8)选择图G=(N,E)中某列πT(j),这相当于首先确定当前调度的任务。信息素相对重要系数α>0和启发式信息相对重要系数β≥0表明蚂蚁在解构造过程中对两种信息的偏好程度。

$\begin{array}{l} π^{Τ} (j) = {\begin{matrix} \arg \max_{j \in Τ_{a l l o w e d}} {[\sum_{i = 1}^{m} τ_{i j}]^{α} \cdot [η_{i j}^{*}]^{β}}, & q \leq q_{0} \\ S_{Τ}, & o t h e r w i s e \end{matrix} (7) \\ p_{j}^{Τ} = {\begin{matrix} \frac{[\sum_{i = 1}^{m} τ_{i j}]^{α} \cdot [η_{i j}^{*}]^{β}}{\sum_{l \in Τ_{a l l o w e d}} [\sum_{i = 1}^{m} τ_{i l}]^{α} \cdot [η_{i l}^{*}]^{β}}, & j \in Τ_{a l l o w e d} \\ 0, & o t h e r w i s e \end{matrix} (8) \end{array}$

其中, $\sum_{i = 1}^{m} τ_{i j}$ 表示调度任务Tj时的可用资源期望。 $η_{i j}^{*} = (1 - \frac{\sum_{i = 1}^{m} η_{i j}}{m}) + \frac{Τ_{j}^{p r i} \cdot Τ_{j}^{d u r}}{\sum_{l \in Τ_{a l l o w e d}} Τ_{l}^{p r i} \cdot Τ_{l}^{d u r}} ‚ (1 - \frac{\sum_{i = 1}^{m} η_{i j}}{m})$ 表示优先调度平均数传时间满足度较小的任务,而 $\frac{Τ_{j}^{p r i} \cdot Τ_{j}^{d u r}}{\sum_{l \in Τ_{a l l o w e d}} Τ_{l}^{p r i} \cdot Τ_{l}^{d u r}}$ 表示当前任务调度收益的相对大小。

q∈[0,1]为均匀分布的随机数,q0∈[0,1]是蚂蚁在解构造过程中的知识利用与随机搜索的相对重要性。当q≤q0时,蚂蚁在调度任务选择时倾向于的知识利用,选择 $[\sum_{i = 1}^{m} τ_{i j}]^{α} \cdot [η_{i j}^{*}]^{β}$ 最大的列为πT(j),否则在ST中以概率pTj选择πT(j)。

为避免列搜索空间过大,假设虚拟结点N0是从调度周期开始时刻确定列搜索空间,如果两个列所代表任务Tp,Tq(p,q=1,2,…,n;p≠q)的任务需求时间窗口相交,由式(9)判定,这两个任务调度的先后顺序可能对列结点遍历时的资源分配产生影响,所以将与当前列所代表任务时间窗口相交的任务集合作为列搜索空间Tallowed.

$\frac{\max {Τ_{p}^{e t}, Τ_{q}^{e t}} - \min {Τ_{p}^{s t}, Τ_{q}^{s t}}}{| Τ_{p}^{e t} - Τ_{p}^{s t} | + | Τ_{q}^{e t} - Τ_{q}^{s t} |} < 1 (9)$

确定当前列πT(j)之后,再按照式(10)、式(11)遍历此列中的各结点,相当于资源分配。

$\begin{array}{l} π_{j}^{R} (i) = {\begin{matrix} \arg \max_{i \in R_{a l l o w e d}} {[τ_{i j}]^{α} \cdot [η_{i j}]^{β}}, & q \leq q_{0} \\ S_{R}, & o t h e r w i s e \end{matrix} (10) \\ p_{i j}^{R} = {\begin{matrix} \frac{[τ_{i j}^{*}]^{α} \cdot [η_{i j}]^{β}}{\sum_{k \in R_{a l l o w e d}} [τ_{k j}^{*}]^{α} \cdot [η_{k j}]^{β}}, & i \in R_{a l l o w e d} \\ 0, & o t h e r w i s e \end{matrix} (11) \end{array}$

其中,Rallowed=R(Tj)-Tabuj(R),Rallowed⊆R,Tabuj(R)为已经为任务Tj分配了时间窗口的资源。当q≤q0时, 蚂蚁倾向于任务资源分配的知识利用, 选择[τij]α·[ηij]β最大的结点为πRj(i),否则在SR中以概率pRij确定πRj(i)。在确定调度任务及可用数传资源之后, 按照式(1)中的约束条件为任务分配数传时间窗口, 直到满足数传任务的最短持续时间或者无数传资源可用。然后重复进行列选择和列结点遍历, 并进行数传任务的资源与时间窗口分配, 直到所有列中的结点都被遍历之后, 完成可行调度解构造。

3.3 信息素更新规则

蚂蚁在当前算法迭代t的解构造过程中,为了减小蚁群中其他蚂蚁走相同路径的可能性,按式(12)进行局部信息素更新,其中局部信息素挥发系数ρl∈(0,1),τ0是路径上初始信息素大小。

$τ_{i j} (t) = (1 - ρ_{l}) τ_{i j} (t) + ρ_{l} \cdot τ_{0} (12)$

全局信息素更新在算法迭代t中蚁群都完成调度可行解构造之后,采用效能函数式(4)对蚁群中各蚂蚁所构造的解进行评价,并获得历史最优解,将历史最优解作为全局信息素更新依据。设全局信息素挥发系数ρg∈(0,1),全局信息素更新规则由式(13)确定:

$τ_{i j} (t + 1) = (1 - ρ_{g}) τ_{i j} (t) + ρ_{g} \cdot (Δ τ_{i j}^{g b} + Δ τ_{i j}) (13)$

Δτgbij表示蚂蚁在历史最优解的解构造路径上在结点Nij上遗留的信息素,由式(14)决定。

$\begin{array}{l} Δ τ_{i j}^{g b} = \\ {\begin{matrix} (\frac{γ}{γ + λ} \cdot E Ι_{Τ}^{g b} + \frac{λ}{γ + λ} \cdot E Ι_{R}^{g b}) \cdot \frac{| D_{i j} |}{Τ_{j}^{d u r}}, & x_{i j} = 1 \\ 0, & o t h e r w i s e \end{matrix} \end{array} (14)$

其中,EIgbT,EIgbR分别为历史最优解的数传时间优先级加权满足度和数传资源负荷均衡度指标的评估值。γ/(γ+λ)为调度收益目标的相对重要系数,λ/(γ+λ)表示资源负荷均衡目标的相对重要系数,|Dij|/Tdurj表示每个结点上的遗留信息素大小与数传执行时间所占任务最短持续时间的比例相关。

Δτij为每次算法迭代中,蚁群在结点Nij上遗留的局部信息素之和,由式(15)决定:

$Δ τ_{i j} = \sum_{k = 1}^{A_{\max}} Δ τ_{i j}^{k} = \sum_{k = 1}^{A_{\max}} ρ_{l} \cdot τ_{0} (15)$

为避免τij过大或者过小,使算法过早陷入局部最优,其大小必须限制在[τmin,τmax]范围内,如式(16)。

$τ_{i j} (t) = {\begin{matrix} τ_{\max}, & τ_{i j} (t) \geq τ_{\max} \\ τ_{i j} (t), & τ_{\min} < τ_{i j} (t) < τ_{\max} \\ τ_{\min}, & τ_{i j} (t) \leq τ_{\min} \end{matrix} (16)$

3.4 算法基本流程

基于资源负荷均衡的卫星数传调度蚁群优化算法基本流程如下:

步骤1 根据问题实例确定任务和资源规模,并问题实例映射为矩阵解构造图G=(N,E)中,并完成图中结点上的初始信息素τ0设置,以及τmin,τmax设置;

步骤2 设置算法基本参数,包括α,β,q0,蚁群规模Amax,算法最大迭代次数NCmax,以及算法终止条件,同时确定γ,λ的值;

步骤3 算法运行

3.1 初始化蚁群,将任务集合加入每只蚂蚁k(k=1,2,…,Amax)的任务调度禁忌表Tabuk,并从初始结点出发;

3.2 根据式(9)确定调度任务的搜索领域,按照式(7)、式(8)选择要执行调度的任务;

3.3 确定调度任务后,根据式(10)、式(11)确定该任务的资源分配序列;

3.4 根据式(1)中的调度约束限制,结合已构造的解,按照任务资源分配顺序表进行资源及时间窗口分配,当任务满足调度要求或者可用资源分配完毕之后,记录该任务所构造的解;

3.5 根据当前任务解按式(12)进行局部信息素更新,并从Tabuk中删除;

3.6 转入3.2进行下一调度任务的选择和解构造,当Tabuk为空时,蚂蚁k完成调度可行解构造;

3.7 当蚁群中所有蚂蚁都完成调度可行解构造之后,根据调度方案效能函数式(4)评价每只蚂蚁所构造的解,记录效能评价值最高的解;

步骤4 以历史最优解为全局信息更新依据,按照式(13)进行全局信息素更新;

步骤5 循环算法迭代,直到满足算法终止条件或者最大迭代次数限制;

步骤6 按照式(2)、式(3)进行最优解的指标评价,记录并输出全局最优解。

4 算例仿真

4.1 算例设计

设一个包括12颗卫星、 4个地面站的调度场景, 其中每颗卫星和每个地面站都具有1根同频段数传天线。场景调度周期为2008-8-8 0:00:00至2008-8-9 0:00:00,根据金光提出的冲突评估方法[19],计算得到场景冲突统计结果如表1所示,可以看出该场景具有较强的“可见时间窗口”冲突。地面站和卫星的基本参数分别列于表2和表3。

根据STK工具生成的场景预报流数据,并依据一定规则生成数传任务共计103个,任务最短时间优先级加权和为360208秒。

任务生成规则:

① 将每颗卫星存在重叠的可见时间窗口依次合并为一个时间窗口。

② 针对每个长度大于5分钟的合并后的时间窗口,生成一个0-1之间的随机数q.

③ 如果0≤q<0.3,则以时间窗口内的两个时间点作为任务的最早开始时间和最迟结束时间,任务最短持续时间为时间区间长度,并满足大于5分钟的要求。该类任务调度时的时间窗口约束更为严格,调度相对困难。

④ 如果0.3≤q≤1.0,则以时间窗口的起止时间作为任务的最早开始时间和最迟结束时间,任务的最短持续时间在5分钟到时间窗口长度之间抽样生成。该类任务的开始时间具有一定的灵活性,调度成功的可能性更大。

⑤ 为每个任务随机生成一个1-10之间的整数作任务优先级,以表明任务的重要程度及价值,并假设值越大优先级越高。

4.2 仿真结果分析

通过大量试验,确定算法参数为:α=1.0,β=0.5,q0=0.25,Amax=8,NCmax=100,ρg=0.75,ρl=0.25,τ0=0.5, τmin=0.01, τmax=10.0。为充分验证算法模型的正确性和有效性, 当γ=0.0,λ=1.0时, 只考虑调度收益(scheduling profits)目标函数O1, 将算法模型称为“SPACO”;当γ=1.0,λ=0.0时,只考虑负荷均衡(load balance)目标函数,将算法模型称为LBACO;当γ>0.0,λ>0.0时,综合考虑目标函数O1和O2的多目标(multi objective)蚁群算法模型称为“MOACO”,现在取值为γ=2.0,λ=0.5。在算法参数设置不变的条件下, 对SPACO、 LBACO、 MOACO分别运行10次, 取效能函数值表现最优的方案, 进行数传时间优先级加权满足度和数传资源负荷均衡度指标评估,结果见表4。

表4中, GA是文献[3]中提出的一种基于遗传算法的卫星数传混合调度算法,并采用与文献中相同的参数设置。TSP是文献[4]中提出的一种基于卫星数传任务综合优先度的启发式算法。MPA是STK/Scheduler中采用的一种多次扫描算法,通过计算每一种方案的FOM(figure of merit)值,对每一种方案进行比较评价,最后挑选出FOM值最大的调度方案作为最终的调度方案。PBS是基于优先级的调度算法,其基本思想是优先调度任务优先级高的任务。FCFS为先到先服务调度算法,基本思想是优先调度开始时间较早的任务。

从表4可以看出,MOACO、LBACO、SPACO所取得的调度方案两个评估指标值均高于现有算法,说明基于数传资源负荷均衡的调度模型是正确的,算法的解寻优效果较好。当只考虑资源负荷均衡目标时, LBACO取得高达99.85%的资源负荷均衡度, 远远高于没有考虑资源负荷均衡的其他算法模型。当同时考虑数传资源负荷均衡和数传时间优先级加权时, MOACO不仅达到了SPACO所求得的93.21%的数传时间优先级加权满足度,而且数传资源负荷均衡度比SPACO高3.62%,说明算法均有良好的目标优化和平衡能力。

图1是仿真中不同算法模型求得的最优方案的数传资源负荷(数传执行时间)分布情况,可以看出,资源负荷均衡度指标客观的反映了数传资源负荷的分布状况,与表4中的数传资源负荷均衡度指标评估值相一致。说明在算法在解构造过程中,考虑了资源负荷均衡性,避免了资源负荷出现较大差异。

图2是MOACO所求调度方案的数传资源负荷均衡度指标和数传时间优先级加权满足度指标随算法迭代进化曲线图,可知算法具有良好的收敛性能,并能同时优化两个调度目标。在试验过程中还发现,本文提出的蚁群算法运算速度明显快于文献[3]提出的遗传算法。

5 结论

合理的卫星数传调度方案应该在确保任务调度收益最大的同时考虑数传资源的负荷均衡,以减少因为资源负荷不均而造成的资源利用与人力分配之间的矛盾。通过分析定义数传资源负荷,建立了卫星数传资源负荷均衡调度模型,提出了基于数传时间优先级加权满足度和数传资源负荷均衡度指标的调度方案效能评价函数。在矩阵解构造图的基础上,提出了具有调度任务确定和资源分配两个决策阶段的蚁群解构造过程,以及基于效能评价函数的全局信息素更新规则。算例仿真表明,本文提出的调度模型和蚁群算法综合考虑了任务调度收益和资源负荷均衡两个优化目标,能够在保证任务调度收益的同时,提高数传资源负荷均衡度,所取得的调度方案获得了较好的数传时间优先级满足度和数传资源负荷均衡度指标评价值。

均衡负荷篇4

随着移动互联网应用的爆发性增长, 用户对手机上网、视频点播、收发邮件、下载等业务由接受转为依赖, 移动运营商必须提供更大的带宽和容量来满足用户的需求。随着4G用户的逐渐增长, 热点区域的单载波已经不能保证用户的需求, 双载波的部署显得越发重要。目前, 双载波的部署采用负荷均衡的方式, 根据服务小区和其邻区负荷状态合理平衡小区间、频率间和无线接入技术之间的负荷, 达到负荷分担, 充分利用现有频率资源, 提高系统吞吐量, 提升用户感知的目的。

二、TD-LTE双载波以及负荷均衡工作原理

双载波是为提高单个基站容量, 通过使用两个频段, 共用天馈、共用RRU并配合相关负载切换来实现不增加站点, 提升小区容量来保障下载速率。移动性负载均衡 (Mobility Load Balancing) 是通过判断本小区的负载高低, 进行小区间负载信息交互, 将负载从较为繁忙的小区转移到剩余资源较多的小区。这样既协调了异频小区之间的负载分布, 实现了网络资源利用最大化, 又也可将小区的一部分负载转移到其它制式小区, 降低E-UTRAN系统拥塞率, 有利于提升业务的接入成功率, 改善用户的业务感受。因此, 移动性负载平衡可以分为异频负载平衡和异系统负载分担。

TD-LTE采用同RRU下的双小区、双载波技术, 本质上就是两个各采用20M的LTE小区覆盖同一或部分重叠区域, 并使用负载均衡算法在同系统两小区之间进行业务均衡, 以满足在某种场景下的使用, 提升系统吞吐率及用户使用感知。

三、TD-LTE双载波组网分析

3.1双载波分层组网结构

双载波分层组网主要分为同频段双载波和异频段双载波组网两个方式:

同频段双载波分层组网主要适用于人口密度比较大且比较均匀的闹市区, 单载波组网容量受限场景, 两个20M小区配置使用相同的功率配置, 覆盖完全相同的地理位置。目前主要针对中国移动的室分E频段和密集城区D频段间的负荷均衡。这种组网方式下, 小区1 (F1频点) 和小区2 (F2频点) 都进行连续覆盖, 对于小区边缘F1和F2频点都将受到基本等同的同频干扰。两个小区可以采用共RRU共天馈方式也可以采用不同天线, 建议进行共站同覆盖两个小区间的负荷均衡, 不考虑非同覆盖相邻小区间的负荷均衡。

异频段双载波分层组网主要适用于人口密度大, 但业务分布不均匀的区域。两个频段小区 (各20M) 部分同覆盖, 高频段做热点小区, 吸收容量, 低频段小区做覆盖小区, 两者的发射功率可以相同, 也可以不同。目前主要针对中国移动FD共BBU情形下, F频段进行连续覆盖, D进行热点区域覆盖的负荷均衡。如在这种组网方式下, 小区边缘主要存在F频段的同频干扰, 对于D频点, 只在同一基站内不同小区覆盖区域间存在少量重叠。F和D共BBU, 分RRU, 两个频点小区可以采用同一天馈, 也可以采用不同天馈, 共天馈时F和D时隙配置无要求, 不共天馈时, 当时隙配置不一致时天线需要满足一定的空间隔离度。

3.2双载波分层组网功能分析

分层组网的目的是提升系统容量, 在负荷均衡算法中要首先保证KPI指标, 任何算法以不影响KPI指标为前提, 主要考虑的指标包括开机附着成功率、切换成功率、接入成功率、掉线率等。在此基础上可以考虑以下算法的实现:

(1) 基于硬件负荷 (CPU占用率) 和业务负荷 (PRB利用率) 对同覆盖或部分同覆盖的两个小区进行负荷均衡控制, 以实现两个小区的负荷平衡和整体吞吐量最优;

(2) 基于小区选择的均衡策略, 同频通过调整q-Rx Lev Min与q-Offset Cell参数, 使得用户初始接入时选择驻留到高负荷小区的负荷均衡过程;

(3) 基于静态参数配置实现空闲态用户的分布策略, 同频双载波小区可以通过调整q-Rx Lev Min与q-OffsetCell重选参数, 对同覆盖小区的空闲态用户进行重选的负荷均衡过程, 异频双载波小区通过设置频率优先级、重选参数门限的配置使得空闲用户按照期望的分布比例驻留到D、F频段, 设置D频段为高优先级, F频段低优先级的策略, 首先需要分别得出测试区域D、F频段RSRP覆盖的CDF分布图, 根据CDF的统计结果设置参数, 一般期望中心用户驻留在D频段, 边缘用户驻留在F频段;

(4) 基于快速切换的均衡策略, 通过快速切换 (不需要测量上报) 方式对同覆盖或部分同覆盖小区的激活态用户进行负荷调整, 负荷调整过程中选择用户需要同时兼顾电平、业务、质量的综合考虑;

(5) 开启负荷调整的判断条件, 同覆盖或部分同覆盖小区中的一个小区达到高负荷门限, 同时高负荷小区和低负荷小区的负荷差值达到一定门限则触发负荷调整过程;或者考虑相对门限, 即两个小区的负荷差异达到门限值, 启动负荷均衡调整过程, 如果两个小区的负荷都达到高负荷状态, 则不进行负荷调整。但要防止小区间乒乓切换, 可以基于A3测量的同、异频切换算法, 防止终端发生乒乓切换。

四、TD-LTE双载波应用举例

4.1室分同频双载波应用举例

同基站邻区和服务小区的负荷由同一个CC板进行计算, 因此邻区的负荷获取不是问题, 可以采用基于快速切换的均衡策略。本次应用选择室分基站的双载波小区负荷均进行测试验证。

4.2室分同频双载波测试步骤

分别选择E频段的某室内小区配置双载波, 测试步骤如下:

(1) 选择某E频段的室内LTE小区, 中心频点为2330MHZ;

(2) 新建该小区的另一个中心频点为2350MHZ, 即该小区配置双载波, 此时记2330MHZ频点的小区为1小区, 2350MHZ频点的小区为2小区;

(3) 首先关闭2小区, 关闭负荷均衡功能, 使用6个UE同时接入1小区进行下载业务, 并记录每个UE的RSRP、SINR及下载速率, 统计此条件下小区的下行总吞吐量及UE平均下载速率;

(4) 打开2小区, 开启双载波负荷均衡功能, 在步骤3的条件下 (所有UE的下载任务未中断) , 通过设置PBR参数、负荷均衡门限等, 观察这些之前接入1小区做业务的UE是否会通过负荷均衡迁移至2小区;

(5) 如果步骤4中有部分UE成功从1小区迁移至2小区, 说明该功能生效, 此时分别记录各个UE所在的小区、RSRP、SINR及下载速率, 并统计小区的下行总吞吐量及UE平均下载速率;

(6) 对比步骤3和步骤5的小区下行总吞吐量及UE平均下载速率;

(7) 终端分别附着在两个小区下, 使用后台信令跟踪, 通过信令分析以及通话成功率确定CSFB功能是否正常启用, 并测试统计相关指标。

4.3室分同频双载波测试结论

单用户保障速率为4M情况下小区的负荷均衡测试结果如表1所示。

结论:根据上述测试结果, 开启双载波负荷均衡算法功能后, 当小区达到负荷均衡执行门限后, 部分UE (本次6个UE成功迁移3个) 会从负荷高的小区迁移至负荷低的小区, 同基站双载波负荷均衡算法功能生效。通过同基站负荷均衡前后下行吞吐量的比较可知, 双载波小区总的吞吐量由100.3M提升至195M, UE平均下载速率由16.72M提升至32.5M, 提升效果显著。开通RRU双载波后, 在4G异频双载波下, 进行语音业务, RRC_CONN_REL消息中会包含2G频点信息, 且RRC手机终端用户均能正常使用CSFB功能, 进行语音业务。

五、TD-LTE双载波后续演进-聚合载波技术

LTE载波聚合 (CA) 技术的核心思路是:将多个连续或离散载波聚合在一起, 形成一个更宽频谱。这种技术的应用既满足了LTE-Advanced在带宽方面的需求, 又可以提高频谱碎片的利用率, 用以提升用户的数据传输速率, 并减少延迟。虽然目前的LTE移动终端能够支持多个LTE射频信道, 但是每次只能通过一个信道进行下载;而LTE载波聚合可以实现同时在两个或多个LTE射频信道上的下载, 它有助于充分利用芯片组的额定LTE数据速率组。

摘要：随着4G用户的逐渐增长, 热点区域的TD-LTE单载波将无法满足用户大带宽和高容量的需求。在不增加硬件的条件下, 开通双载波功能, 使用负载均衡切换, 可以充分利用现有频率资源, 将单载波上的用户进行分流, 达到提升系统吞吐量、小区容量和用户感知的目的。

均衡负荷篇5

IMS(IP Multimedia Subsystem)是IP多媒体子系统的简称,是第三代合作伙伴计划(The 3rd Generation Partnership Project,3GPP)在通用移动通信系统(Universal Mobile Telecommunication System,UMTS)R5标准版本中正式提出的,其目的是将核心网络统一到全IP的网络结构上,并实现固定网络和移动通信网络的融合,是下一代网络(Next Generation Network,NGN)的发展方向[1,2]。IMS被看作是更“软”的软交换系统,软交换实现了承载和控制的有效分离,IMS技术进一步分解了控制层功能,网络架构因此变得更加灵活、开放,是独立于接入技术的提供IP多媒体业务的体系架构,被公认为是固定与移动网络融合的基础。IMS具有如下技术特点:基于会话初始协议(Session Initiation Protocol,SIP)的会话控制,水平体系架构,与接入无关,业务与控制分离,提供丰富而动态的组合业务[3,4]。

在NGN的框架中,终端和接入网络是各种各样的,而其核心网络只有一个,即IMS,它的核心特点是采用SIP协议和与接入的无关性。为顺应网络IP化的趋势,IMS系统采用SIP协议作为唯一的会话控制协议。IP技术是互联网的主导技术,在互联网上的应用已经非常成熟,其优点是可以快捷灵活地提供各种信息类服务,并且有较好的业务开放性和可开发性。但是IP技术固有的缺点则不能忽视,其在数据传输的安全性和计费控制方面无法适应IMS业务的要求。

传统的电信网络采用独立的信令网来完成呼叫的建立、路由和控制等过程,信令网的安全能够保证网络的安全。而且传输采用时分复用(Time Division Multiplexing,TDM)的专线,用户之间采用面向连接的通道进行通信,避免了来自其他终端用户的各种窃听和攻击。而IMS网络与互联网相连接,基于IP协议和开放的网络架构可以将语音、数据、多媒体等多种不同业务,通过采用多种不同的接入方式来共享业务平台,增加了网络的灵活性和终端之间的互通性。正是由于IMS是建立在IP基础之上,也使得IMS的安全性要求比传统运营商在独立网络上运营要高得多,不管是由移动接入还是固定接入,IMS的安全问题都不容忽视。因此,IMS用户终端(User Equipment,UE)接入到IMS核心网需经一系列认证和密钥协商过程,这个过程即用户注册业务[5]。IMS的注册业务主要由呼叫会话控制器(Call Session Control Function,CSCF)、应用服务器(Application Server,AS)、接入网控制器(Access Gateway Control Function,AGCF)和归属用户服务器(Home Subscriber Server,HSS)等网元完成[6,7]。

1 IMS用户注册

IMS用户注册过程包括初始注册、刷新注册和注销,根据用户类型又分为支持3GPP的SIP用户终端发起的注册和AGCF代理注册。AGCF需要代理接入的公共电话交换网(Public Switched Telephone Network,PSTN)等固网用户和不支持3GPP的SIP用户等向IMS注册[8],IMS用户注册网络结构图如图1所示。

SIP用户终端发起的注册和AGCF代理注册流程基本相同,区别在于SIP用户经过代理CSCF(Proxy-CSCF,P-CSCF)注册,而AGCF代理注册直接向查询CSCF(Interrogating-CSCF,I-CSCF)发起注册。

1.1 AGCF代理初始注册

IMS中的位置管理通过用户的注册来完成。注册的目的是让服务CSCF(Serving-CSCF,S-CSCF)能准确地知道用户当前的位置和状态。传统终端接入网关(Access GateWay,AGW)等设备通过PI接口向AGCF注册后,AGCF需要代理这些设备向IMS注册。AGCF代理初始注册过程如图2所示。

AGCF代理初始注册流程简述如下:

(1)AGCF代理传统终端设备向I-CSCF发起注册(REGISTER)消息。

(2)-(3)I-CSCF向HSS查询提供用户服务的S-CSCF。

(4)I-CSCF将REGISTER消息转发给S-CSCF。

(5)-(7)S-CSCF向HSS请求鉴权向量集,并选择1个鉴权向量。

(8)-(9)S-CSCF向I-SCCF返回401未鉴权消息(携带鉴权挑战字),并转给AGCF。

(10)-(11)AGCF根据鉴权挑战字计算挑战结果,并发起带鉴权挑战结果的REGISTER。

(12)-(13)I-CSCF向HSS查询提供用户服务的S-CSCF。

(14)I-CSCF将REGISTER消息转发给S-CSCF。

(15)对挑战响应进行鉴权。

(16)-(17)通知HSS用户已注册,并从HSS获得用户签约数据。

(18)-(19)S-CSCF向I-CSCF发回注册成功200OK响应,并转给AGCF。

1.2 AGCF代理刷新注册

用户注册后,当其需要更新当前的注册或是改变当前的注册状态时,用户可以发起应用层的刷新注册请求,目的为保持用户当前的注册状态,也需要在当前注册的注册时长(EXPIRE)过期之前进行刷新注册。刷新注册时用户在初始注册时已经获取了鉴权挑战字并计算出了挑战结果,故刷新注册携带鉴权挑战结果,S-CSCF直接对刷新注册进行鉴权,然后由S-CSCF更新用户注册时长即可。AGCF代理刷新注册流程如图3所示。

AGCF代理刷新注册流程简述如下:

(1)AGCF代理传统终端设备向I-CSCF发起注册(REGISTER)消息。

(2)-(3)I-CSCF向HSS查询提供用户服务的S-CSCF。

(4)I-CSCF将REGISTER消息转发给S-CSCF。

(5)S-SCCF判断用户已经注册,根据S-CSCF上的用户注册信息直接进行注册鉴权并更新用户注册时长。

(6)-(7)S-CSCF向I-CSCF发回注册成功200OK响应,并转给AGCF。

1.3 AGCF代理注销

IMS用户注销为刷新注册的特例,即注册请求中EXPIRE值为0的刷新注册。AGCF代理注销流程与1.2代理刷新注册相同。

2 存在问题

AGCF在固网设备融合到IMS的过程中具有重要作用。它具有接入网关控制功能,接入传统窄带用户到IMS网络中。AGCF以Mw接口与IMS CSCF设备交互,同时充当MGC功能以PI等接口与住户网关(Residential GateWay,AGW/RGW)等传统固定终端交互。

传统固定终端用户通过AGCF接入IMS网络的流程如下:传统终端AGW等设备通过PI接口向AGCF注册,AGW在AGCF上注册成功后,AGCF代理AGW终端下的用户向IMS网络的CSCF设备发送SIP REGISTER注册请求,注册成功后,CSCF返回200OK应答,200OK里携带了注册有效期EXPIRE。AGCF根据EXPIRE值定时代理AGW用户向CSCF发送刷新注册请求,以保持用户在IMS网络中的注册状态。刷新注册时间在3GPP里有建议,3GPP建议的算法如下:如果EXPIRE>1200,刷新时间为当前时间+EXPIRE-600;如果EXPIRE<=1200,刷新时间[9]为当前时间+EXPIRE/2。

当IMS网络中大量终端同时发送注册请求时,就会形成注册消息流量集中发送,由于IMS核心网无法及时处理这些报文,导致报文反复重传使得整个网络的压力像滚雪球一样越来越大,从而对IMS核心网造成雪崩风暴,业界称其为注册风暴[10]。而AGCF代理注册由于是瞬间集中大批量注册,比普通IMS用户的注册时间更加集中,往往会造成非常严重的注册风暴,给CSCF、AS和HSS等网络设备造成巨大的压力。在实际应用中,由于运营商需要AGCF代理的用户短时间内就在CSCF上注册成功,故AGCF代理初始注册风暴是不可避免的,且初始注册风暴在一段时间内一般只出现1次;而刷新注册风暴则是持续的,这会大大加大IMS核心网的系统负荷。刷新注册风暴的产生主要有以下2个原因:

(1)AGCF重启:初始注册200OK里的EX-PIRE值往往都是相同的,就会导致用户的刷新注册时间也集中在短时间段内。在1个EXPIRE时间周期内,AGCF和CSCF用户刷新注册的工作负荷严重不均衡。

(2)AGCF接入的多个AGW网关不在同一时间注册,这些AGW网关注册的时间恰好间隔1个或多个EXPIRE周期,AGCF代理用户发起初始注册时间是受AGW网关注册时间决定的。因此这种情况也会导致AGCF用户刷新注册集中在EX-PIRE周期的某一短时间段内,从而导致工作负荷不均衡。

3 技术解决方案

3.1 刷新注册负荷均衡算法

根据3GPP建议的刷新注册时间算法,AGCF代理刷新注册的注册风暴是客观存在的,但这是运营商和设备制造商不能忍受的,鉴于以上问题,本文提出一种在IMS网络中,AGCF代理用户刷新注册负荷均衡的方法。AGCF代理用户初始注册成功后,第1次刷新时间不采用3GPP的算法计算,而是利用随机分布算法把刷新时间散列在EXPIRE周期内,从而达到负荷均衡的目的。

AGCF上电时,初始化一个EXPIRE大小的统计数组。数组下标从0到EXPIRE-1,每个数组元素都是1个计数器,记录有多少用户刷新注册时间落在EXPIRE周期内每一秒上。AGCF刷新注册统计数组示意图如图4所示。

AGCF代理用户发起初始注册,初始注册请求中携带相同的EXPIRE协商值,CSCF接受AGCF建议的EXPIRE,并在初始注册200 OK中返回,AGCF收到初始注册的200OK后,在EXPIRE时间段内取1个随机值,判断((当前时间+随机值)MOD EXPIRE)对应的下标数组元素的统计值是否超过了平均值,如果没有超过,就把当前时间+随机值作为此用户的第1次刷新注册时间。如果对应下标数组元素的统计值超过了平均值,则在EXPIRE时间段重新获取1个随机值,并判断对应数组元素的统计值。每个用户最多可以尝试获取5次随机值,如果5次尝试之后还没有找到低于平均值的随机时间点,就用最后1个随机值+当前时间作为第1次刷新时间,同时对应数组下标元素统计值加1。

AGCF只针对第1次刷新注册时间做随机散列,每个用户后续的刷新注册时间按3GPP的建议算法计算。刷新注册负荷均衡算法示意图如图5所示。

结合图5对刷新注册负荷均衡算法说明如下:

(1)从图中初始注册时间点开始,AGCF把图中的Tr时间段作为此用户的第1次刷新散列区间。Tr=EXPIRE-Th-Tt。Th和Tt二个时间段长度可配置,用来防止散列后的刷新时间太早或太迟。

(2)AGCF在Tr时间段随机获取一个时间点Tf,然后以(Tf Mod EXPIRE)为数组下标,判断Array[(Tf Mod EXPIRE)]的统计值是否超过平均值Av。Av=初始注册总数/EXPIRE+5。

(3)如果Array[(Tf Mod EXPIRE)]小于Av,则用Tf作为此用户的第1次刷新时间,并把Array[(Tf Mod EXPIRE)]统计值加1,初始注册总数加1。

(4)如果Array[(Tf Mod EXPIRE)]大等于Av。AGCF返回(2)步重新在Tr时间段内获取一个随机的时间点Tf。如果5次随机时间点都不能满足(3)的条件,则用第5次的随机时间点Tf5作为此用户的第1次刷新时间,并把Array[(Tf5 Mod EXPIRE)]统计值加1,初始注册总数加1。

(5)通过刷新负荷均衡算法计算刷新时间结束。

3.2 改进后的AGCF代理注册流程

图6为根据刷新注册负荷均衡算法设计的AGCF代理注册流程图,具体说明如下:

(1)AGCF上电时初始化刷新注册统计数组。

(2)AGW网关在AGCF上注册成功。

(3)AGCF代理AGW网关下的用户向CSCF发送初始注册请求,请求中携带3GPP协议建议的注册时长,即每个用户的注册消息中携带的EX-PIRE都相同。

(4)CSCF返回200OK注册应答,应答中返回相同的EXPIRE值。

(5)AGCF收到CSCF的200OK后,不采用3GPP协议建议的刷新注册时间,根据3.1节中刷新注册负荷均衡算法计算出用户第一次刷新注册时间。

(6)用户第一次刷新注册时间到达后,AGCF向CSCF发送代理刷新注册请求,请求中携带正常的EXPIRE值。

(7)CSCF返回200OK注册应答,应答中返回相同的EXPIRE值。

(8)AGCF收到CSCF的200 OK后,采用3GPP协议建议的刷新注册时间。

(9)AGCF根据3GPP协议建议的刷新注册时间进行后续代理刷新注册。

(10)CSCF返回200OK注册应答。

4 结束语

文章介绍了IMS固网设备融合组网中AGCF代理注册业务流程及其存在的问题,针对AGCF代理注册引发的刷新注册风暴进行分析,提出了一种代理注册业务负荷均衡算法,根据这种算法可以使AGCF代理注册的刷新注册时间均衡分布,从而避免了AGCF代理注册对IMS核心设备的频繁、持续的网络冲击。文章针对AGCF代理注册业务提出的负荷均衡算法不仅适用于其他代理注册场景,也同样适用于代理订阅业务,为解决IMS系统中代理注册订阅、业务订阅和呼叫转移通知订阅等业务的刷新订阅风暴提供了一种重要技术参考。

摘要：文章介绍了IP多媒体子系统(IP Multimedia Subsystem,IMS)的技术体系架构,分析了IMS系统中接入网控器(AGCF)设备代理大批量用户刷新注册存在的问题,提出了一种IMS设备注册业务负荷均衡的算法,通过这种算法将AGCF代理用户的刷新注册时间均匀分布。实践证明,该设计高效、稳定,可以有效避免大批量代理用户集中刷新注册风暴给AGCF设备及整个IMS系统带来的网络冲击。

关键词：IP多媒体子系统,代理注册,负荷均衡,接入网控器,刷新注册风暴

参考文献

[1]薛晓飞,陈璐,路萍.基于SIP和RTP的VoIP通信[J].指挥信息系统与技术,2012(01):68-71.

[2]王清春,孙宇.下一代网络中的软交换与IMS[J].网络安全技术与应用,2014(08):37-38.

[3]钱蕾,唐海,钟橙.IMS核心网发展策略探析[J].数据通信,2014(02):20-22.

[4]王金柱.IMS过载控制关键技术研究[D].北京:北京邮电大学,2012.

[5]张奇支,黄兴平,范冰冰.IMS中一种快速的用户重注册过程[J].计算机科学,2010(09):117-120.

[6]许盛宏,邓勇,李力卡.IMS网络AGCF高效可靠容灾方案探讨[J].电信技术,2014(S1):208-211.

[7]罗汉斌.IMS网络用户注册流程浅析[J].中国新通讯,2014(09):28-29.

[8]李蕊,崔欣.NGN向AGCF演进方案研究[J].现代电信科技,2013(09):61-65,70.

[9]胡乐明,曹磊,陈洁.IMS技术原理及应用[M].北京:电子工业出版社,2006:98-107.

【均衡负荷】推荐阅读：