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

• 作者: 张新禄 田海燕 贺毅朝 高锁刚
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: Ad-hoc网络 极大独立集 相邻矩阵 贪心策略 连通支配集
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 83-87
• 分类号: TP301.6
• 字数: 7282字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.03.018

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贺毅朝	石家庄经济学院信息工程学院	53	677	14.0	25.0
2	田海燕	河北师范大学数学与信息科学学院	5	31	2.0	5.0
4	高锁刚	河北师范大学数学与信息科学学院	12	48	2.0	6.0
5	张新禄	河北师范大学数学与信息科学学院	14	108	5.0	10.0