空间信息网络时变图模型研究

(3000 Characters)：Space data network(SDN) will be country's infrastructure. The network has some characteristics of intermittently connected links, constrained storage, store-and-forward mechanism and long propagation time delay. It is a temporal network which is not suitable for modeling, analyzing and designing a space data network with static graph theory. Based on this, this project will firstly explore a temporal graph model for data space network, which includes constellation planning with multiple constrains, the rules of end-to-end flow restricted by SDN resource elements, a multidimensional resource dynamic graph model for SDN, the algorithm for solving aforementioned model, and the scheme of transforming a time-variable graph model to a time free graph model. Secondly, this project will also explore optimal searching algorithms of the time-variable graph, which includes a polynomial-time routing algorithm, a routing algorithm based on QoS guarantee, a multi-path routing algorithm, and a polynomial-time algorithm for maximal flow problem. This project will also construct a test bed for demonstration and confirmation of key technologies. What’s more, this research will do contribution for time variable graph model, optimal theory of graph searching, and theoretical and technical supports for the design, control and usage of SDN.

空间信息网络将是国家重要的基础设施。该网络具有链路断续连通、传播时延尺度大、节点存储器有限等特征。无法利用静态图构建网络模型，无法利用成熟的图论理论进行网络的计算、分析与设计。基于此，本课题将探索空间信息网络的时变图模型，研究内容包括：多约束条件下的网络星座规划方案，空间信息网络各资源要素制约端到端流量的规律，构建网络的时变多维资源图模型；研究网络多维资源图模型的简化方法，提出多维资源图模型向时间不关图的转化机制。将探索时变图的优化搜索算法，研究内容包括：多项式时间最短路径路由算法；时延保障的路由算法；多路径路由算法，多项式时间的最大流算法。将构建演示验证平台，验证时变图模型转换机制、时间不关图的性能及多种路由算法的效能。课题成果将必须拓展动态图模型与优化理论，为空间信息网络的设计、管控与使用提供理论及技术支持。

项目面向高轨/低轨卫星、地面站、飞艇等节点构成的时变空间网络，面向资源卫星、飞机、地面移动终端等用户生成的随机业务环境，针对空间信息网络的高效图模型缺失、网络性能分析困难、高效利用空间链路资源的路由算法缺失、以及现有空间信息网络承载能力难以最大化利用等问题，开展了时变图模型、时变网络路由算法及时变网络路由协议演示验证平台等研究工作，取得如下研究成果。1）提出了空间信息网络时变图模型—存储时间聚合图，在动态稀疏链路资源、节点缓存有限等约束条件下，精确高效表征了空间信息网络的拓扑特征。与传统的快照图模型相比，弥补了快照之间关联关系的表征，解决了快照图无法利用断续连通链路资源的问题；与时间扩展图相比，存储时间聚合图的存储量显著下降。2）首次提出缓存受限时变图最大流算法。针对节点缓存有限的约束条件，在存储时间聚合图节点模型上增加了缓存限制，设计了缓存受限的存储时间转移序列的转移规则，给出了时变图最大流算法，与时间扩展图相比，基于存储时间聚合图最大流算法的算法复杂度降低，算法复杂度不随时间序列长度的增加而增加。该算法可用于分析空间信息网络的网络承载能力，为断续连通网络链路资源的最大化利用提供了理论依据。3）提出了基于存储时间聚合图的最短时延路由算法，考虑了节点缓存与业务流流量等约束，支持断续连通网络路由的计算。4）研制了空间信息网络时变图关键技术演示验证平台。设计了链路模拟器，仿真空间信息网络拓扑的时变特征；设计了支持存储时间聚合图路由算法的拓扑发现机制与时变路由表，支持时变网络路由协议的验证。项目研究成果为空间信息网络的表征、网络传输性能的分析、路由计算及业务调度与编排提供了理论支撑。本项目的部分研究成果将用于国家重点研发计划“基于分布式可重构航天遥感技术”项目。