计算机科学 ›› 2012, Vol. 39 ›› Issue (3): 83-87.
• 计算机网络与信息安全 • 上一篇 下一篇
贺毅朝,田海燕,张新禄,高锁刚
出版日期:
发布日期:
Online:
Published:
摘要: 在无线Ad-hoc网络中,基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用。首先证明了相部矩阵理论的一个有关结论,然后利用此结论以及极大独立集和极小支配集的关系,提出了一种基于相部矩阵快速构建无线Ad-hoc网络最小连通支配集的近似算法,并给出了算法的正确性证明、复杂性分析和近似比分析。仿真试验结果表明,利用该算法可以快速高效地构建Ad-hoc网络的虚拟主干网。
关键词: Ad-hoc网络,极大独立集,相部矩阵,贪心策略,连通支配集
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.
Key words: Ad-hoc networks, Maximal independent set, Adjacent matrix, Greedy strategy, Connected dominating set
贺毅朝,田海燕,张新禄,高锁刚. 基于相邻矩阵快速构建虚拟主干网的近似算法[J]. 计算机科学, 2012, 39(3): 83-87. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2012/V39/I3/83
Cited