天基信息网络流问题的算法研究

【摘要】：随着航天技术飞速发展,构建天基信息网络,夺取空间优势成为各国科技和军事发展的重要任务.天基信息网络是一种以各种类型的卫星为网络节点,通过星间链路连接起来的空间无线网络系统,具有覆盖范围广、传输容量大等特点.路由问题和流问题作为天基信息网络信息传输的两种重要方式,日益成为国内外学者研究的课题.本文针对天基信息网络的特点,对其流问题进行了研究.通过对流问题的分类,提出了针对性强、有着重要应用背景和现实意义的三个流问题,并给出了相应的求解算法.本文的主要工作成果有以下几个方面:1、提出了天基信息网络流问题的分类标准,将其细分为静态流问题、动态信息流问题和动态拓扑流问题三种,指出了它们之间的区别与联系,阐述了它们各自所对应的现实应用背景,并将动态拓扑流问题转化成对静态网络问题作敏感度分析.2、根据天基信息网络的Qo S协议模式,阐述了多目标优化问题的实用价值,抽象出带主次双费用的最小双费用流问题模型.并利用原始对偶的思想,为该问题设计出正确高效的求解算法,最后将算法推广到最小多费用流问题上去.3、针对天基信息网络中存在的信息传输时延问题,抽象出连续时间容量网络的模型,提出了最短动态时间流的概念.发现了经典网络和带节点限制网络之间的关系,并分别为这两种网络模型设计出最短动态时间流算法.4、介绍了天基信息网络最大信息流敏感度分析的背景和研究现状,对其中的两个重要子问题——关键卫星问题和最佳添加链路弧问题,分别设计出高效的求解算法.相比按定义求解的自然算法,本文的算法在理论复杂性和实际计算量上都有明显降低.
【关键词】：天基信息网络 流问题 最小双费用流 最短动态时间流 最大流敏感度分析
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TN927.2