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

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

作　　者：林琳[1] 王安平[1] 周贤伟[1] 刘臻臻[1] 

机构地区：[1]北京科技大学信息工程学院通信工程系,北京100083

出　　处：《计算机工程》2010年第10期91-93,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60773074);国家"863"计划基金资助项目(2007AA01Z213;2009AA01Z209)

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

关 键 词：Ad HOC网络 STEINER树 分布式算法 时间复杂度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]