| 基于相邻矩阵快速构建虚拟主干网的近似算法 |
| |
| 引用本文： | 贺毅朝,田海燕,张新禄,高锁刚.基于相邻矩阵快速构建虚拟主干网的近似算法[J].计算机科学,2012,39(3):83-87. |
| |
| 作者姓名： | 贺毅朝 田海燕 张新禄 高锁刚 |
| |
| 作者单位： | (石家庄经济学院信息工程学院 石家庄050031) (河北师范大学数学与信息科学学院 石家庄050016)(计算数学与应用河北省重点实验室 石家庄050016) |
| |
| 基金项目： | 国家自然科学基金(10971052);河北省教育厅青年基金(2010260);河北省科学技术研究与发展指导计划项目(07216926)资助 |
| |
| 摘 要： | 在无线Ad-hoc网络中,基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用。首先证明了相邻矩阵理论的一个有关结论,然后利用此结论以及极大独立集和极小支配集的关系,提出了一种基于相邻矩阵快速构建无线Ad-hoc网络最小连通支配集的近似算法,并给出了算法的正确性证明、复杂性分析和近似比分析。仿真试验结果表明,利用该算法可以快速高效地构建Ad-hoc网络的虚拟主干网。
|
| 关 键 词： | Ad-hoc网络 极大独立集 相邻矩阵 贪心策略 连通支配集 |
Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone |
| |
| HE Yi-chao,TIAN Hai-yan,ZHANG Xin-lu,GAO Suo-gang.Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone[J].Computer Science,2012,39(3):83-87. |
| |
| Authors: | HE Yi-chao TIAN Hai-yan ZHANG Xin-lu GAO Suo-gang |
| |
| Affiliation: | 2(School of Information Engineering,Shijiazhuang University of Economics,Shijiazhuang 050031,China)1(College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050016,China)2(Hebei Key Laboratory of Computational Mathematics and Application,Shijiazhuang 050016,China)3 |
| |
| Abstract: | 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. hhe 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. |
| |
| Keywords: | Ad-hoc networks Maximal independent set Adjacent matrix Greedy strategy Connected dominating set |
| 本文献已被 CNKI 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
