关键词:Ad hoc网络; 组播; 时延; 最小连通支配集
Construction of delay definition multicast forwarding backbone forAd hoc network based on MCDS
PENG Lai, WANG Chao, AN Jian-wei, WU Hua-yi
(Dept. of Communication Engineering, School of Information Engineering, University of Science & Technology Beijing, Beijing 100083, China)
Abstract:On the basis of particularity of the propagation method of wireless signal, this paper redefined the cost and delay function in wireless multicast routing. Proposed a vertex-coloring algorithm based method of construction of delay definition multicast forwarding backbone based on minimum connected dominating set (MCDS) theory in graph theory. By solving the MCDS problem, realized the construction of minimum cost multicast routing. And proposed the concept of delay definition in multicast routing. Theoretic analyzed the accuracy of this algorithm of construction and the low approximation ratio prove the algorithm to be more efficient than other conventional algorithm. It is further proven that this algorithm has high efficiency with O(n) time complexity and O(n) message complexity, which make it has more advantages when applied in Ad hoc network with characteristics of flexibility and variability. ......