Ad hoc网络中基于MCDS构建延迟定界组播转发结构*

根据无线信号传播方式的特殊性，重新定义了无线组播路由中的代价和时延函数，基于图论中最小连通支配集（MCDS）理论，提出的基于图论中点着色思想的时延定界组播转发结构的构建方法，通过求解MCDS来实现构建最小代价组播路由结构的目的，提出了组播路由时延定界的概念，并在该约束下构建MCDS。理论推导证明了该算法的正确性，与同类算法相比，较低的近似比证明了该算法的有效性，同时具有O(n)的时间复杂度和O(n)的消息复杂度，进一步证明了其高效性，具有适应于灵活多变的Ad hoc网络的优势。

Construction of delay definition multicast forwarding backbone for Ad hoc network based on MCDS

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.