Abstract: Aiming at delay-constrained Steiner tree problem in Ad hoc network, this paper designs a distributed rapid heuristic algorithm DCST. The algorithm builds a delay-constrained Steiner tree through labeling on the nodes and changing the adjacent relationship between nodes based on the labels. Under the premise of time synchronization of nodes in Ad hoc network, the time complexity of the algorithm is O(n). Compared with some traditional Steiner tree algorithms, the algorithm has distinct advantages.

Key words: Ad hoc network, Steiner tree, distributed algorithm, time complexity

摘要： 针对Ad hoc网络时延受限的Steiner树问题，设计一个分布式的快速启发式算法DCST，该算法通过对网络中节点进行标号，并根据标号修改节点间的关联关系，建立一棵时延受限的Steiner树。在网络节点保持时间同步的前提下，算法的时间复杂度为O(n)。与现有经典的Steiner树算法相比，该算法具有明显优势。

关键词: Ad hoc 网络, Steiner树, 分布式算法, 时间复杂度

CLC Number: 

• TP393