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

项目名称： 空间信息网络时变图模型研究

项目编号： No.91338115

项目类型： 重大研究计划

立项/批准年度： 2014

项目学科： 无线电电子学、电信技术

项目作者： 李红艳

作者单位： 西安电子科技大学

项目金额： 80万元

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

中文关键词： 时变图模型；路由算法；最大流算法；；

英文摘要： (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,

英文关键词： time-varying graph model；routing algorithm；the maximum flow of the network；；