论文部分内容阅读
近年来,随着星间链路(ISL)技术的成熟以及星上处理能力的增强,卫星系统的服务不再是简单的“弯管”模式,星座网络成为卫星系统发展的重要趋势。然而,随着太空中卫星的日益增多,卫星系统的运行管理变得困难。地面站不仅投资巨大,运营费用也极其高昂。因此,如何对星座网络进行优化、减少日益庞大的星座网络对地面信关站的需求成为了一项重要的课题。在二代卫星系统中,利用星座网络的星间链路可以有效减少星座系统对地面站资源的需求。在星间链路及组网技术的支持下,星座系统只需选取部分地面可观测的卫星建立星-地链接。这种与地面站有直接链路的卫星被称作网关卫星,而其他卫星的信息传输可以通过网关卫星进行中继,这样不仅可以突破卫星服务必须地面可见的限制,还可以节省大量的地面站资源。网关卫星选择问题是指如何在地面可见卫星集合中选取一个子集作为网关卫星。本文采用一种受限的支配集模型对网关卫星的选择进行建模。并讨论了网关卫星选择问题的复杂性。由于卫星网络拓扑结构具有高度的动态性和时变性,所以收敛慢的启发算法不能应用于网关卫星选择问题。我们重点研究了网关卫星选择问题的近似算法,以及其子问题的有效算法。主要研究内容如下:1、星座网络中,为了既能获得较好的星-地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题。采用一种受限的支配集模型对网关卫星选择问题进行建模。2、通过将3-SAT问题多项式时间规约到网关卫星选择问题,证明了该问题是NP完全的。3、定义了网关卫星选择问题的一个子问题——2限制-网关卫星选择问题,并给出该问题的多项式时间算法——匹配算法。4、分析了传统的贪心算法不适用网关卫星选择问题的原因,同时设计了网关卫星选择问题的贪心算法。理论分析表明,若每颗卫星最多支持k条星间链路,那么贪心选择算法是H(k+1)近似的,这里H表示调和函数。5、基于2限制-网关卫星选择问题的匹配算法对贪心算法进行了改进,改进后的贪心算法性能有所提升。6、对三种算法进行仿真,将仿真得出的数据用图表的形式进行分析。实验结果表明:(1)贪心算法在星座规模中等时性能接近最优解:在星座规模相对较大时性能接近H(k+1)的近似界。在平均情况下,采用贪心算法进行网关卫星选择能节省20%左右的星-地链路资源。(2)验证了匹配算法的性能。(3)改进后的贪心算法较改进前有2%左右的性能提升。改进的贪心算法进行网关卫星选择能够进一步节约星-地链路资源。(4)卫星网络拓扑结构相对简单时,改进的贪心算法的性能优势会更明显。