无线传感器网络中最优路由树的构造算法研究

Data gathering is a basic operation for wireless sensor network applications. How to design an efficient data gathering tree to prolong network lifetime is a critical problem in wireless sensor networks. However, finding the optimal routing tree has been proved to be NP-hard. Currently, most algorithms for this problem are heuristic algorithms, and have no (or rather weak) worst-case theoretical guarantee. Consequently, these algorithms can only be evaluated by experiments (or simulations), making it difficult to further understand and solve the problem. This project aims to propose algorithms for finding the optimal routing tree. Specifically, we will consider the problem in wireless sensor networks with aggregation capabilities, in wireless sensor networks without aggregation capabilities, and in wireless sensor networks powered by new energy sources. For each type of sensor networks, we will prove stronger inapproximability results, propose approximation algorithms with lower time complexity and higher approximation ratio matching the theoretical upper bound, and design exact algorithms with lower (exponential) running time. We will evaluate the proposed algorithms by both theoretical analysis and real-world experiments. This research project will improve the understanding of routing tree construction problem, and provide theoretical guidance in designing the routing structure in practical wireless sensor networks. We plan to publish 6-8 papers in international conferences and journals, and at least four of them are ranked B in CCF recommended conferences and journals.

数据收集是传感网应用的一项基本操作。如何为数据收集设计高效的路由树来延长传感网生存时间是一个关键问题。然而，最优路由树问题已被证明是NP难问题。目前，针对此问题的算法以启发式算法为主，缺少最坏情况下的理论保证或理论保证较弱，研究者只能通过(模拟)实验对算法进行评估，制约了对路由树问题的进一步理解和解决。本项目研究最优路由树的构造算法与理论，具体包含数据融合传感网的最优路由树问题、非数据融合传感网的最优路由树问题和新型能源传感网的最优路由树问题。对每个问题，分析最优路由树问题的不可近似比，提出时间复杂度更低、近似比接近理论上界的近似算法，并设计具有更低(指数)时间复杂度的精确算法。我们将结合理论推导和实验论证的方法来验证算法的性能。本项目的研究成果将加深对路由树构造问题的理解，为路由结构设计提供理论指导。力争在国际期刊或会议上发表高质量论文6-8篇，其中至少包含4篇CCF B类以上论文。

本项目对无线传感器网络的最优路由树问题从难度分析、近似算法设计和精确算法设计三个方面开展了研究。突出创新之处包括：(1)提出了一种能够与理论不可近似比匹配的近似算法，不但证明了不可近似比已不可改进，而且提出的近似算法在应用到传统的度限制生成树和最小度生成树问题中时，具有更低的时间复杂度；(2)提出了最坏情况下时间复杂度为O*(2^n)的精确算法，回答了一个长期悬而未决的难题；(3)提出了在实际网络中运行速度更快的精确算法，能够为中等规模无线传感器网络寻找到最优路由树；(4)将最优路由树的研究成果应用到了软件定义网络及内容中心网络中，证明了一系列难度结论。本项目的研究推动了对最优路由树问题的理解，具有重要的理论意义和应用价值。