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

摘要：

在无线Ad-hoc网络中,基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用.首先证明了相邻矩阵理论的一个有关结论,然后利用此结论以及极大独立集和极小支配集的关系,提出了一种基于相邻矩阵快速构建无线Ad-hoc网络最小连通支配集的近似算法,并给出了算法的正确性证明、复杂性分析和近似比分析.仿真试验结果表明,利用该算法可以快速高效地构建Ad-hoc网络的虚拟主干网.

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

所属期刊栏目：39

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2012-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：83-87