基于相邻矩阵快速构建虚拟主干网的近似算法  

Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone

作　　者：贺毅朝[1] 田海燕[2,3] 张新禄[2] 高锁刚[2] 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031 [2]河北师范大学数学与信息科学学院,石家庄050016 [3]计算数学与应用河北省重点实验室,石家庄050016

出　　处：《计算机科学》2012年第3期83-87,共5页Computer Science

基　　金：国家自然科学基金(10971052);河北省教育厅青年基金(2010260);河北省科学技术研究与发展指导计划项目(07216926)资助

摘　　要：在无线Ad-hoc网络中,基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用。首先证明了相邻矩阵理论的一个有关结论,然后利用此结论以及极大独立集和极小支配集的关系,提出了一种基于相邻矩阵快速构建无线Ad-hoc网络最小连通支配集的近似算法,并给出了算法的正确性证明、复杂性分析和近似比分析。仿真试验结果表明,利用该算法可以快速高效地构建Ad-hoc网络的虚拟主干网。In Ad-hoc networks,a minimum connected dominating set （MCDS） can be used as a virtual backbone to improve the performance of source allocation and prolong the system lifetime. In this paper, we firstly proved a useful theorem about adjacent matrix. Secondly, using the theorem and the relationship between maximum independent set and minimum dominating set, we proposed a fast approximation algorithm based on adjacent matrix for constructing MCDS in Ad-hoc networks. The correctness, complexity and approximation rate of the proposed algorithm were analyzed respectively. Simulation results show that new algorithm can efficiently and fast construct virtual backbone in Ad-hoc networks.

关 键 词：AD-HOC网络 极大独立集 相邻矩阵 贪心策略 连通支配集 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]