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

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.

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

最小生成树(MST)是一个广泛研究的问题，对于通信网络的设计具有重要意义。然而，实际容迟容断网络(DTN)中，由于延迟、可靠性、吞吐率等性能要求，结点的度数及直径都受到了一定的限制，传统的MST算法无法直接应用到上述受限制的情形。针对这个问题，本项目主要研究了度及直径受限的MST理论、算法及其在DTN网络中的应用。. 具体研究内容包括：. 1）应用图论及组合优化理论，研究了度及直径受限的约束最小生成树理论，并构建了相应的智能算法；. 2）应用优化理论，设计了适合于DTN网络特性的数据分发策略。. 主要成果包括：. 1）分析研究了现有MST理论, 将度及直径受限最小生成树问题转化为线性规划问题，应用随机舍入技术设计了多项式时间求解算法，分析了算法可达到的理论界；分析了现有智能算法的性能、优点、缺点等，提出了约束生成树的改进prufer树编码表示、设计了改进的遗传算法，针对存储与传输过程中数据碎片问题，提出了贪婪双向收集器算法，提高了数据存储与收集的效率。. 2）应用上述成果，设计了车载DTN网络中的路由协议和路由算法。具体地，针对车载DTN网络中链接会频繁断开，导致数据的传输范围及距离都受到了限制(即度与直径都受到限制) 的问题，设计了基于最短路径预测的路由协议，缓解了现有DTN的网络拥塞问题，使拥塞率降低大约10%，改进了现有DTN网络协议的性能。.项目研究成果可以进一步推动最小生成树理论的发展及其在通信网络中的应用。