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

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

作　　者：彭莱[1] 王超[1] 安建伟[1] 吴华怡[1] 

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

出　　处：《计算机应用研究》2010年第2期632-635,共4页Application Research of Computers

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

摘　　要：根据无线信号传播方式的特殊性,重新定义了无线组播路由中的代价和时延函数,基于图论中最小连通支配集(MCDS)理论,提出的基于图论中点着色思想的时延定界组播转发结构的构建方法,通过求解MCDS来实现构建最小代价组播路由结构的目的,提出了组播路由时延定界的概念,并在该约束下构建MCDS。理论推导证明了该算法的正确性,与同类算法相比,较低的近似比证明了该算法的有效性,同时具有O(n)的时间复杂度和O(n)的消息复杂度,进一步证明了其高效性,具有适应于灵活多变的Ad hoc网络的优势。On the basis of particularity of the propagation method of wireless signal, this paper redefined the cost and delay function in wireless muhicast 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 muhicast 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.

关 键 词：AD HOC网络 组播 时延 最小连通支配集 

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