约束最小生成树及其在容迟容断网络中的应用

项目名称： 约束最小生成树及其在容迟容断网络中的应用

项目编号： No.11426163

项目类型： 专项基金项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 宋庆凤

作者单位： 天津城建大学

项目金额： 3万元

中文摘要： 最小生成树是一个广泛研究的问题，对于通信网络的设计具有重要意义。然而在实际网络中，由于网络的延迟、可靠性、吞吐率等性能要求，结点的度数及直径都受到了一定的限制，传统的最小生成树算法无法直接应用到上述受限制的情形。针对这个问题，本项目拟研究度及直径受限最小生成树理论、算法及其在容迟容断网络（DTN）中的应用。具体研究内容包括：1）应用图论及组合优化理论，研究约束最小生成树多项式算法可达到的松弛度上界，并构建相应的多项式算法；2）应用优化理论，设计适合于DTN网络特性的数据分发策略。项目研究成果将进一步推动最小生成树理论的发展及其在通信网络中的应用，提高DTN网络的性能，促进DTN网络在我国的发展。

中文关键词： 约束最小生成树；智能算法；容迟容断网络；近似算法；数据分发

英文摘要： Minimum spanning tree is a well studied problem, and is of great significance to the design of the communication networks. However, in the actual networks, because of the network latency, reliability, throughput and other performance requirements, the degrees and diameter of the node are restricted, and accordingly the traditional minimum spanning tree algorithm cannot be applied to the above restricted conditions directly.To deal with this problem, our project will study the theory and algorithm of the minimum spanning tree with constrained degrees and diameters, and their application in Delay/Disruption Tolerant Networks (DTN). Specifically, 1) we will study the theoretical relaxation bound of the constrained minimum spanning tree based on graph theory and combination optimization theory, and construct the corresponding polynomial algorithm; 2) then, design data distribution strategy for DTN networks based on optimization theory. The research results of our project can help promote the development of the minimum spanning tree theory and its application in communication network, improve the performance of DTN networks, and promote the development of DTN networks in our country.

英文关键词： Constrained minimum spanning tree；Intelligent algorithm；Delay/Disruption tolerant network；Approximation algorithm；Data distribution