[摘 要]随着航天技术的发展,卫星网络已成为网络研究领域的热点。一直以来,卫星通信网的资源优化都是卫星系统中的一个重要环节。本文在研究卫星通信网络特点的基础上,通过建立数学模型,并利用遗传算法求解模型,实现了在满足地面用户提交的任务的约束情况下,将子任务合理的进行安排调度,以达到完成所有用户提交任务总时间最短的目的,同时兼顾资源的合理利用问题。
[关键词]卫星通信网资源优化遗传算法
[中图分类号]TN927.2[文献标识码]A[文章编号]1007-9416(2009)11-0091-02
1 问题提出
空天信息网是由各种卫星和航天器组成的动态网络。卫星上的各种功能设备以及一些逻辑资源构成了整个网络的计算资源、通信资源、存储资源、侦察资源等可共享资源。地面用户终端根据实际情况会对这些不同类型的资源提出请求。那么如何合理分配使用这些资源,使整个网络运行达到最佳状态就是一个十分重要的问题。
比如,在整个空天网中,经常会有这样的情况出现:地面用户发出多个资源请求,请求可以有很多种类(比如通信带宽,cpu计算处理资源等),这个时候就形成这样一个问题:怎样将多个用户请求较为合理的分配到各个卫星上执行,使得每一个卫星上的资源能够得到充分利用,并且能够使得完成所有任务的时间最短。
在对资源进行优化组合时,我们可以考虑带宽资源,cpu资源,内存等等。对于不同的资源我们这里假设它们是相互独立的,也就说资源之间没有相互依赖关系。那么就可以在各自的求解空间内分别求解。事实上,我们并不关心具体是什么样的资源,各类资源在我们分配时是没有什么具体区别的,是一类对象而已。我们关心的是这类资源在各个卫星上的总量,剩余量,利用率,用户的请求量等等。
2 问题描述和数学模型的建立
我们把上面的问题描述为:在个卫星组成的空天网络系统中,每个卫星都有类资源,有独立资源请求共个,现在我们需要从这个卫星中选择个能够满足各个资源要求的卫星,也就是怎样把这个用户的资源请求合理分配到各个卫星去执行。一般的>>。考虑执行如下步骤:
(1)确定请求资源类别和资源的特性;
(2)判断请求优先级,统计资源请求时间等策略相关指标。
(3)使用调度算法选择用户需要的资源,判断是否有可用的空闲资源:
如果有可用空闲资源,将资源分配给用户并监控;
如果没有,确定用户需要等待的时间;
(4)请求时间结束回收资源。
如图1所示。
资源一共有类(存储资源、计算资源等),或者我们可以说资源维数为,每个卫星可以有其中某些资源,则每个卫星有多维资源:
,
那么整个网络或者说系统的总资源为:
,
这里,表示第类资源的总和。
在已经对多个任务进行合理的分割子任务之后,确定了各个子任务所需的资源类型以及时间,并且要注意满足各个子任务之间的相互依赖关系。需要解决的问题是如何将每个子任务合理的分配到各个卫星上面,让各个卫星资源负载均衡,并且完成时间尽可能的短。
首要的目标函数就是使得完成所有请求的执行时间最短。即
Max
St.,,
这里是指完成第i个任务的第j个子任务的时间,是指发出资源请求的第i类资源的第j个分量。
同时,我们也要求某些资源都能得到充分利用的同时,不使其它的资源空闲,即各个资源均衡使用,还有各个处理节点也就是各个卫星的剩余资源(分配不了的资源)同时满足请求需要的资源量。
设卫星中第种资源的所有工作时间为,卫星中第种资源的所有工作时间为,要想达到同类资源负载均衡,需要满足:
()
上面公式的具体意义就是要将同类资源之间的工作量差异减到最小值,使整个系统的负载均衡。
3 模型求解
事实上,我们上面所描述的优化问题是一个NP难题,不可能找到多项式时间最优算法,只能退而求其次去寻找有效的次最优算法。在解决资源优化配置问题时目前使用最多的方法有贪婪算法、规划论和遗传算法。但是对于一个给定的问题往往有好几种度量标准,而贪婪算法只能从中选择出一个最优度量标准,所以只能获得该度量意义下的最优解而不是该问题的最优解,并且要选择出最优度量标准不是一件容易的事情。规划论通过建立可控变量与目标系统之间的关系对可控变量进行优化,往往因为模型复杂而不能获得解。遗传算法(Genetic Algorithm,简称GA)由于简单和解决问题的有效能力而被广泛应用到众多的领域。
GA作为基于“适者生存”的一种高度并行、随机和自适应优化算法,它将问题的求解表示成“染色体”的适者生存过程。通过将染色体种群(Population)的一代代不断进化,包括选择(reproduction)、交叉(crossover)和变异(mutation)等操作,最终收敛到“最适合环境”的个体,从而求得问题的最优解或满意解。
下面是遗传算法的标准算法框图2。
将遗传算法应用于卫星网络,需要改进遗传算法的部分步骤,使得基本遗传算法更加适合当前资源优化问题。其遗传算法步骤如下:
(1)编码和解码:采用十进制编码。将资源组合优化的一系列参数用一串代码来加以表示。将任务根据先后顺序编码,组成一个长度为的编码,通过算法找到较优的染色体之后,将代码串表示成实际问题的相应结果作为解码过程。我们采用整数形式编码解向量。问题模型中,共有m种资源可供调用。解以整数向量形式表示,其中的取值范围为[0,]。
(2)产生初始种群
(3)确定适应度函数:适应度是个体对生存环境的适应程度,设计一个适应度函数用以判断个体的适应程度。适应度高的个体将获得更多的生存机会。本文中所设计的染色体的适应度函数值如下:
,,
其中为当前代中当前染色体所代表的可行解中第i个卫星完成最后一个任务的结束时间。S为卫星个数,j为种群规模,M种群进化代数。
(4)产生新种群:根据适应度值大小按照一定的规则从群体中选取优良的染色体,使它们成为新一代的染色体群体。在选择操作上,通过精英策略适当的选取若干个最优解保留到下一代中。剩下的个体通过赌轮盘法选择到子代中。
(5)交叉操作:在新种群中按照改进的POX交叉方法对选中染色体执行交叉操作。
(6)变异操作:对新种群按照变异概率对选中染色体执行变异操作,使其避免陷入局部最优解,防止早熟收敛。
(7)循环步骤4、5、6回到步骤4对经过步骤5和步骤6产生的新种群重复进行选择、交叉和变异操作,即重复执行步骤4、5、6
(8)得到结果:经过一定代数后,选择最好的染色体作为优化问题的最优解。
再根据前面的解码算法将染色体还原成具体的调度结果。
4 结语
本文讨论了卫星网络中资源优化问题,在深入研究问题背景和内容的基础上建立了该问题数学模型并结合卫星网络的特点,对遗传算法进行改进。在此基础上设计了求解问题的遗传算法步骤。
[参考文献]
[1] B.Clifford Neuman,Santosh Rao.Resource Mangement for Distributed Parallel Systems. Proceedings of the 2nd International Symposium on High Performance Distributed Computing, Spokane. 1993.
[2] 王大震,王淑静,宋瀚涛,潘浩.成本/时间综合优化网络资源调度策略及价格算法.北京理工大学学报.2004
[3] 姜思杰,徐晓飞,李全龙.一类资源负荷均衡问题的双最小平衡调度算法.高技术通讯.2002.
[4] 赵林亮,姜月秋,张臻杰,王光兴. Ad hoc网络中资源管理的研究.小型微型计算机系统.2005.
[5] 卢金.基于遗传算法的光传送网络空闲资源优化设计.吉林大学硕士学位论文.
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文