作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (10): 91-93. doi: 10.3969/j.issn.1000-3428.2010.10.030

• 网络与通信 • 上一篇    下一篇

Ad hoc网络时延受限的Steiner树启发式算法

林 琳,王安平,周贤伟,刘臻臻   

  1. (北京科技大学信息工程学院通信工程系,北京 100083)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-05-20 发布日期:2010-05-20

Heuristic Algorithm of Delay-constrained Steiner Tree in Ad hoc Network

LIN Lin, WANG An-ping, ZHOU Xian-wei, LIU Zhen-zhen   

  1. (Department of Communication Engineering, School of Information Engineering, University of Science and Technology Beijing, Beijing 100083)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-05-20 Published:2010-05-20

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

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

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

中图分类号: