卫星网络实时分组调度问题研究

《卫星网络实时分组调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2扬州大学硕士学位论文座地面站对太空中的100多颗进行调度管理【2】。地面站不仅投资巨大，其运营费用也极其高昂。如，欧洲的伽利略计划总投资大约为21．5亿欧元，而每年的运营管理费用高达2．2亿欧元【31。1．1．2卫星系统调度卫星系统运行管理的一个最主要任务是在地面站一卫星间进行数据通信的调度，即给定一组通信请求(每个请求有开始时间、结束时限和通信量)、一组地面站和地面站所能看见的卫星时段，寻找能够满足最多通信请求的调度。在九十年代，这一问题是手动解决的。随着卫星系统逐渐普及，在2000年以后这一问题逐渐吸引了众多研究者的兴趣。在早期，调度周期是7天，即所谓

2、的7天调度【4】。文献[4]将这一问题称作SRS(SatelliteRangeScheduling)，并利用整数规划技术为SRS调度进行建模，并实现了自动调度。通过设计一个两阶段的调度算法将调度周期缩短至1天。而后，[2]进一步将SRS问题细分为两个子问题，SiRRS(Single—ResourceRangeScheduling)和MuRRS(Multi-ResourceRangeSchedu]ing)。并通过将单处理机调度问题——lI，，I∑u，多项式归约到SiRRS，以此来证明了SRS问题是NP—hard的。并通过实验分析，指出即使对SiRRS性能较好的

3、算法也不一定适用于MuRRS，但遗传算法对于MuRRS有较好的性能。[5]总结了SRS求解算法的演进，分析了近年来该问题的变化，指出随着通信请求的增多MuRRS将越发地难以调度。[6]给出了一组SRS的测试问题集。[7—8]对SRS问题搜索算法性能差异的机理进行分析，指出搜索平台是导致搜索算法难以收敛到最优解的关键，并由此阐明在搜索算法的设计中采用一些随机技术至关重要。[9]阐述图的仁着色问题和MuRRS的相似性，并将仁着色问题求解的两种启发策略用于了MuRRS，并实验验证了该算法。[10]报告了伽利略系统中的通信任务调度的优化算法，采用了一种非标准的拉格朗

4、日松驰启发获得了近优解。[11]研究NASA的DSN(DeepSpaceNetwork)的通信任务调度，不同于MuRRS该研究考虑了多个优化目标。[12一13]分别设计了遗传算法和蚁群算法求解SRS调度。[14—19]研究了EOS(EarthOrbitingSatellite)调度问题，EOS调度与SRS的差异仅在于EOS主要是调度下行的通信量，本质上与SRS是同一种调度问题。1．1．3星座网络的发展在前面的背景介绍中我们已经对星座网络有了一定的了解，通过介绍，我们了解到星座网络以其独特的组织使其具有覆盖范围大、重访周期短等优点成为目前卫星研究中比较流行的一

5、个科目，这也使得星座网络区别于最初的单颗卫星成为现在卫星系统的一种主流。近年来，随着星间链路(ISL)技术的成熟【20】及星上处理能力的增强，卫星系统的服务不再是简单的“弯管”模式，星座网络成为卫星系统发展的重要趋势口M31，并在二代通信卫星系统中得到广泛应用。[24]讨论了二代通信卫星技术，提出了一种环形拓扑卫星网络。[25—27]研究了基于IP的卫星组网技术：其中，[26]对采用ATM的星座网络进行了综曹双卫星网络实时分组调度问题研究3述；[27]对IP／ATM的卫星网络技术进行了详细论证。[25]提出了将MPLS技术用于卫星组网中，将MPLS的ingr

6、ess、egress和核心路由器映射到卫星网络的实体上，并对MPLS卫星网络的路由计算量进行了分析。[28-29]研究了星间链路的资源分配问题。[28]为加权公平的按需资源分配问题建立优化模型，并给出了相应的求解算法；[29]从控制论的角度将带宽请求看成一种时滞系统，对卫星链路的带宽分配进行了研究。[30—33]研究了卫星网络的路由问题。[30]利用随机规划研究了路由策略和网络拓扑的关系；[31]给出了的路由算法能找到最小传播延迟的路径；[32]研究了网孔(Mesh)拓扑的LEO卫星网络的路由策略，提出RPW、OPW和SHW三种分组转发策略，实验结果表明SH

7、W策略比RPW和OPW策略表现要好。[33]通过以总带宽最小为优化目标求解矩形边Steiner树来解决卫星网络的多播路由问题。随着卫星网络研究的深化，利用ISL的卫星组网技术逐渐成熟，并在GPS和伽利略等系统中得到了应用。传统的卫星系统调度仅仅局限于目标星和地面站之间进行，且目标星和地面站之间的调度只能在地面站的可视时间段内进行，这大大降低了卫星系统的传输调度效率。星座网络的发展使得这一问题得到很好的解决，星座网络使得各目标星之间能够相互传输调度，调度不再仅仅局限于目标星和地面站之间，因此星座网络的发展使得卫星系统的调度效率得到了极大的改善，也因此导致传统的

8、调度模型不再适应于最新的星座网络，必须建立一种新型的