资源负载均衡

文章编号:1001-2486(2011)02-0095-05一种航天侦察任务-资源匹配的负载均衡方法谈群1,彭黎1,李志猛1,祁炜2(1.
国防科技大学信息系统工程重点实验室,湖南长沙410073;2.
空军雷达学院陆基预警监视装备系,湖北武汉430019)摘要:当前航天侦察任务预处理方法一般仅从任务需求的角度考虑资源分配问题,容易导致负载不均衡,对此提出了一种综合考虑任务需求与资源负载的任务-资源匹配方法.
分析了资源负载均衡需要考虑的任务要素以及相应的描述方法,提出用任务执行概率度量卫星资源负载状况,基于任务流模型给出了单任务执行概率的估算公式,并给出了一种简易的多任务执行概率求解算法.
综合考虑任务的任务量、优先级、执行效果与执行概率,提出了航天侦察任务-资源匹配的负载均衡模型,并给出了一种启发式求解算法,模拟实验表明负载均衡方法可以有效提高卫星资源利用率以及侦察效益.
关键词:航天侦察;卫星资源分配;负载均衡;任务流中图分类号:V19文献标识码:AALoadBalancingMethodforMatchingReconnaissanceTasksandSatelliteResourcesTANQun1,PENGLi1,LIZhimeng1,QIWei2(1.
ScienceandTechnologyonInformationSystemsEngineeringLaboratory,NationalUniv.
ofDefenseTechnology,Changsha410073,China;2.
DepartmentofLandbasedEarlywarningSurveillanceEquipment,AirForceRadarAcademy,Wuhan430019,China)Abstract:Incurrentspacebasedreconnaissancetaskpretreatmentprocess,resourceallocationgenerallyliesontaskrequirements,whichmayleadtoloadimbalance.
Inlightofthis,amatchingmethodthatconsidersbothtaskrequirementsandresourceloadwaspresented.
Forthesakeofloadbalancing,thekeytaskelementsandtheirdescriptionmethodwereanalyzed.
Basedonthetaskflowmodel,formulaandalgorithmforcalculatingtheprobabilityoftheexecutedtaskwereavailable,thentheexecutionprobabilitywereusedtomeasuretheloadstatusofsatelliteresources.
Finally,theresearchputforwardaloadbalancingmodelandacorrespondingheuristicalgorithmformatchingreconnaissancetasksandsatelliteresources,whichtakesintoconsiderationtheworkload,priority,qualityoftasksandexecutionprobability.
Simulationresultsshowthattheproposedloadbalancingmethodcaneffectivelyimprovetheutilizationofsatelliteresourcesandreconnaissancebenefit.
Keywords:spacebasedreconnaissance;satelliteresourceallocation;loadbalancing;taskflow航天侦察以其独特的时空范围、精度、可靠性等不可替代的优势在现代战场上扮演着重要的角色,航天侦察卫星包括可见光成像侦察卫星、红外成像侦察卫星、雷达成像侦察卫星、电子侦察卫星等多种类型.
在航天侦察任务的处理过程中,由用户提出成像需求请求,卫星应用管理中心接收任务需求后,首先进行任务与资源的数据预处理,完成任务的资源过滤与资源分配,然后根据观测需求的属性信息、卫星的状态信息和各种约束条件生成卫星侦察任务调度计划.
Kaslow[1]、Whitefield[2]研究了卫星资源计划与调度方法,根据信息需求类型、质量要求、侦察对象特点、卫星运行状态等为航天侦察任务指定最优的卫星资源.
龚卓君[3]研究了基于多Agent协商的卫星资源分配技术,仅从任务的角度考虑卫星资源是否能执行任务,在满足各种约束的条件下,依据一定的准则为任务分配卫星资源.
李菊芳[4]、陈浩[5]研究了多星任务调度方法,基本思想是先将每个任务分配给一个卫星资源,对每个卫星资源进行单星调度,综合多颗卫星的调度结果优化原始任务分配方案.
这些方法在分配资源时都没有考虑卫星负载状况,容易导致资源负载不均衡,影响任务完成率.
此外,从资源利用的角度收稿日期:2010-10-20基金项目:国家部委基金资助项目(9140A22010609KG01)作者简介:谈群(1982—),男,博士生.
第33卷第2期国防科技大学学报Vol.
33No.
22011年4月JOURNALOFNATIONALUNIVERSITYOFDEFENSETECHNOLOGYApr.
2011来看,在完成尽可能多、尽可能重要的观测任务的同时,单个卫星所消耗的载荷能力越少越好,卫星间的负载分配越平均越好,研究任务-资源匹配的负载均衡方法可以促进卫星资源得到充分、均衡的利用.
负载均衡技术随着网络的发展而出现[6],有效解决了一些网站由于迅猛增加的访问量造成服务能力跟不上的问题.
负载均衡技术可分为静态和动态两类[7],本文在航天侦察任务-资源匹配问题中借鉴动态负载均衡的思想,重点解决了卫星资源负载状况度量的问题,预测侦察任务及各类卫星资源能力随时间动态变化的情况,将部分任务分配给在相应任务时间区间内较空闲的卫星资源,从而提高资源利用率及任务成功率.
1航天侦察任务关键要素分析一般来说,用户的卫星成像侦察任务需求包括优先级、时间属性、侦察对象、信息质量要求等内容,为了进行负载均衡,需要重点考虑任务在特定时间内占用的卫星资源数量,同时还要考虑任务的优先级以及任务由不同类型卫星资源执行的效果差别.
任务量是指任务占用的卫星资源数量,以任务占用的资源相对于元任务的倍数来衡量,最小值为1.
其中,元任务是指卫星一个侦察动作可以完成的任务,但由于幅宽不同,不同类型卫星资源的元任务是不一样的,可能某类卫星一次就可以完成的任务其他卫星却需要多次才能完成.
为了不同的需要,提出相对任务量与绝对任务量两个概念,相对任务量是指任务针对某一类卫星资源的任务量,绝对任务量是指所有任务按照统一标准计算得到的任务量,相对任务量用于计算卫星资源的负载状况,绝对任务量用于计算完成任务的收益.
任务量由任务的作用对象及信息质量决定.
任务执行效果由任务对象的特点、信息质量要求及卫星资源的能力决定,记任务i由第j类卫星资源执行的效果为ui(j).
为了便于横向比较完成任务的收益,任务执行效果取相对值,设对于任务i,第l类卫星资源执行效果最好,其执行效果取1,不能执行i任务的效果取0,其他类型卫星资源执行的相对效果为efij=ui(j)ui(l)(1)根据上述分析,将航天侦察任务描述为一个四元组ST=,其中pri为优先级,STT=[ts,te)为时间区间,STL=(λi,λi1,…,λik),λi为绝对任务量,λi1,…,λik为相对任务量,STE=(efi1,…,efik)为执行效果.
2任务-资源匹配的负载均衡模型及求解算法负载均衡技术的一个关键问题是服务器的负载状况度量,卫星任务调度是周期性进行的,在调度之前,卫星资源在本周期内不同时间段的负载状况都是未知的,本节通过估算一个任务分配给一类卫星资源后的执行概率来度量这类卫星资源在那段时间内的负载状况,进而提出负载均衡模型及求解算法.
21任务执行概率一个任务的执行概率不仅与其自身分配的卫星资源有关,还受到其他任务的分配结果影响,由于要尝试很多种不同的分配方案,这种不确定的任务集合无法输入到任务调度系统中得到任务的执行结果,因此很难精确计算.
作者在文献[8]中提出了天基信息系统任务流建模方法,这里给出一种基于任务流模型的任务执行概率估算方法.
设在分配方案为X的情况下,task1,task2,…,taskm(m≤n)为分配给第j类卫星资源的任务,这些任务形成一个任务流,记为TFj={task1,task2,…,taskm}=,[Ts,Te]表示任务流的起止时间,fjr(t)表示优先级为r级的任务流强度函数,其表达式为fjr(t)=∑mi=1Θ(t,Ti)·Φ(prii,r)·λijL(Ti)(2)其中L(Ti)表示时间区间Ti的长度,Θ(t,Ti)=1t∈Ti0tT{iΦ(prii,r)=1prii=r0prii≠{r对任意时间区间[t1,t2][Ts,Te],∫t2t1fjr(t)dt表示在该时间区间内任务优先级为r的任务量.
令gj(t)表示在[Ts,Te]时间段内第j类卫星资源的能力曲线,卫星不过顶时,能力为0,gj(t)是周期函数,∫t2t1gj(t)dt表示第j类卫星资源在[t1,t2]内最多可以完成的任务量.
以图1为例,[ts,te)为taski的时间区间,f(t)是与taski优先级相同的任务构成的任务流强度函数,虚线·69·国防科技大学学报2011年所示g(t)是剩下可用于执行优先级不高于taski的任务的卫星资源能力曲线,s3是f(t)超出g(t)那部分的面积,表示超载的任务,s2是g(t)超出f(t)那部分的面积,表示空闲的资源,s1是二者重合的面积.
图1任务流强度与卫星资源能力Fig.
1Taskflowintensityandsatelliteresourcecapability假设如果两个优先级、任务时间相同的任务都匹配给同一类资源,则这两个任务的执行概率相同.
通过合理的任务调度,一定比例的空闲的资源可以执行超载的任务,称这个比例为灵活度,记为δ.
任务taski执行概率的估算公式为proi=min{1,(s1+δ·s2)(s1+s3)}(3)式(3)给出了计算单任务执行概率的方法,对于多个任务task1,task2,…,taskm的执行概率,按优先级从高到低顺序计算,算法如图2所示.
g(t)←gj(t);forr=9to1docst←0;fori=1tomdoifprii==rthencalculateproiusingformula(3);cst+=λij·proi;endifendforg(t)←(1-cst∫TeTsg(t)dt)·g(t);endfor图2多任务执行概率求解算法Fig.
2Multitaskexecutionprobabilityalgorithmcapability22任务-资源匹配的负载均衡模型任务-资源匹配就是为每个任务合理分配卫星资源,有些非常重要的任务需要多类卫星共同完成,有些任务受条件限制只能由某一类卫星完成,本文不考虑这些任务.
因此,这里负载均衡的目标就是为每个任务分配一类卫星资源,使总侦察效益最大.
设有n个侦察任务,k类卫星资源,负载均衡模型描述为maxZ=∑ni=1∑kj=1λi·priiα·efij·pro(X)i·xij∑kj=1xij=1,i=1,…,nxij=0or1(4)其中:λi表示任务的绝对任务量;prii表示任务的优先级;efij表示第j类卫星资源执行任务i预期的效果;pro(X)i表示在分配方案为X的情况下,任务i的执行概率;xij=1表示分配第j类卫星资源执行第i个任务;α为优先级的修正系数,因为优先级仅仅是重要性的排序,序号不具有物理意义,因此需要引入一个修正系数.
同时可以求出分配方案X的资源利用率:U=∑ni=1λi·pro(X)i∫TeTsg(t)dt(5)23求解负载均衡模型的启发式算法负载均衡模型的求解是一个NP问题,当任务与卫星资源的规模达到一定程度时,很难在有效时间内找到最优解,用近似算法找到一个较优的可行解是合理的解决办法,本文提出一种启发式算法.
用启发式算法求解负载均衡模型的关键在于计算调整一个任务的卫星资源类型可以取得的收益.
调整一个任务会影响此任务的执行效果、执行概率以及其他与此任务时间有重叠的任务的执行概率,如果重新计算每个任务的执行概率,再按照式(4)计算总收益,会使求解速度非常慢,事实上这里可以采取简化的计算方法,对最终的优化效果影响很小,但可以大幅度提高求解速度.
例如,任务taski从A类卫星资源调整到B类卫星资源,调整前,两类卫星资源对应的任务流强度函数分别为fA(t),fB(t),将其他优先级与taski相同、与AB两类卫星资源匹配的任务时间属于Ti的部分看作两个虚拟任务taskA=prii,Ti,λA,ef{}A与taskB=prii,Ti,λB,ef{}B,其中λA=∫TifA(t)dt-λi,λB=∫TifB(t)dt,这样就大大减少了相关任务的数量,将调整前后的匹配方案分别记为X、X′,按照式(4)此次调整的收益·79·第2期谈群,等:一种航天侦察任务-资源匹配的负载均衡方法近似为wi(A,B)=λA·priαi·efA·pro(X′)A+λB·priαi·efB·pro(X′)B+λi·priαi·efiB·pro(X′)i-λA·priαi·efA·pro(X)A-λB·priαi·efB·pro(X)B-λi·priαi·efiA·pro(X)i(6)每次调整只考虑本优先级的任务,因此priαi可以省略.
每个任务只作一次调整,因此efiA=1,两个虚拟任务的执行效果近似取1.
按照计算执行概率的假设,pro(X)A=pro(X)i,pro(X′)B=pro(X′)i,执行概率均按照式(3)计算.
因此,式(6)可以简化为wi(A,B)=λA·pro(X′)A+(λB+λi·efiB)·pro(X′)i-λB·pro(X)B-∫TifA(t)dt·pro(X)i(7)fori=1tondoforj=1tokdoifefij==1thenxi←j;assignsatellitewithbesteffectendifendforendforforr=9to1dofori=1tondoifprii==rthenforj=1tokdocalculatewi(xi,j)usingformula(7);endforendifendfordosearchmaximalwi(xi,j);ifmaximalwi(xi,j)>0thenxi←j;adjusttaskwithmaximalwi(xi,j)Updatew(x,j)ofrelatedtasks;endifuntilmaximalwi(xi,j)≤0endfor图3负载均衡模型的启发式算法Fig.
3Heuristicalgorithmforloadbalancingmodel求解负载均衡模型的基本思路是首先为每个任务分配执行效果最好的卫星资源,然后按照优先级由高到低的顺序调整任务的卫星资源,在同一个优先级内,按照调整收益由大到小的顺序调整任务的卫星资源,直到调整收益都不大于0,具体算法如图3所示.
算法的主体部分是为任务分配更优的卫星资源,经过分析,每个任务至多调整一次,每次调整需要搜索最大调整收益并更新相关任务的调整收益,这两个操作的时间复杂度分别为O(log2n)与O(n),因此算法总的时间复杂度为O(n2),在模拟实验中,300个任务仿真1000次花费时间小于30s,验证了算法的有效性.
3模拟实验实验在VisualStudio环境下编程实现,程序量约600行,任务与卫星数据均随机产生.
任务数量tasknum分两种情况:平时,任务较少,到达过程较平稳,时间约束相对较松,数量设为200个,用泊松分布模拟;应急情况,任务较多,到达过程不平稳,时间约束更严格,数量设为300个,用负二项分布模拟.
卫星资源有5类,卫星数量satnum分六种状态,平时情况,当前10颗,中期20颗,远期30颗,应急情况各比平时增加50%.
参数取值为α=05,δ=03,每种情况运行1000次.
任务-资源匹配时,首先为每个任务分配执行效果最好的资源,然后按照本文的负载均衡方法进行优化,统计优化前后的匹配结果.
优化前后各优先级任务的平均执行概率如图4所示,从图中可以看出,大多数情况下,优化后任务的执行概率提高了.
在卫星资源较少时(如情况1、4),优先级高的任务执行概率提高幅度非常大,但低优先级任务的执行概率略有下降,这符合卫星资源紧缺时首先保障重要任务的原则.
随着卫星资源的增加,高优先级任务执行概率的增幅放缓,低优先级任务的执行概率逐渐不再降低甚至全部都有提高(如情况3).
按照式(4)、(5)分别求出各种情况下的总侦察效益与资源利用率,分别如图5、6所示.
从图中可以看出各种情况下总侦察效益都有一定提高.
对比平时与应急情况,平时优化效果更好,总侦察效益都提高了12%以上,资源利用率也提高更多,说明平时调整空间更大.
对比不同卫星资源数量,卫星资源丰富时总侦察效益提高的绝对值更大,资源利用率提高也更显著,说明卫星资源越丰富,优化效果越好.
·89·国防科技大学学报2011年图4各优先级任务平均执行概率Fig.
4Averageexecutionprobabilityoftaskswithdifferentpriorities图5总侦察效益Fig.
5Totalreconnaissancebenefit图6资源利用率Fig.
6Utilizationofsatelliteresources4结束语本文根据任务流模型提出了预先估计各类卫星资源在不同时间段负载情况的方法,在此基础上建立了考虑资源负载的任务-资源匹配模型,给出了模型求解的一种启发式算法.
模拟实验结果表明,相对于给每个任务分配执行效果最好的卫星资源,负载均衡方法可以有效提升任务执行概率,在卫星资源较少时,优先级高的任务执行概率显著提高,最大幅度接近30%,随着卫星资源的增加,低优先级任务的执行概率逐渐得到提高,总侦察效益与卫星资源利用率也得到了较大提高,平时都在12%以上,但应急条件下优化效果大约只有平时的一半.
参考文献:[1]KaslowD.
PlanningandSchedulingofEarthObservingSatellites[C]IEEEAerospaceConference,2007:1-12.
[2]WhitefieldD,GopalR.
CapacityEnhancementwithDynamicResourceManagementforNextGenerationSatelliteSystems[C]IEEEMILCOM,2005,2:761-767.
[3]龚卓君.
卫星应用任务分解技术研究[D].
长沙:国防科技大学,2009.
[4]李菊芳,白保存,陈英武,等.
多星成像调度问题基于分解的优化算法[J].
系统工程理论与实践,2009(8):134-143.
[5]陈浩,李军,唐宇,等.
基于动态罚函数遗传算法的电磁探测卫星多星规划方法[J].
国防科技大学学报,2009,31(2):44-50.
[6]薛军,李增智,王云岚.
负载均衡技术的发展[J].
小型微型计算机系统,2003,24(12):2101-2103.
[7]杨际祥,谭国真,王荣生.
并行与分布式计算动态负载均衡策略综述[J].
电子学报,2010(5):1122-1130.
[8]QiuDS,TanQ,PengL,etal.
AModelingMethodofSpacebasedInformationSystemTaskflowBasedonScenario[C]InternationalColloquiumonComputing,Communication,Control,andManagement,2010:712-717.
·99·第2期谈群,等:一种航天侦察任务-资源匹配的负载均衡方法