分布式最小连通支配集启发式算法

摘要：

针对Ad Hoc 网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀.

关键词：有效度、支配节点、极大独立集、最小连通支配集

所属期刊栏目：35

分类号：TP393.07(计算技术、计算机技术)

资助基金：现代通信国家重点实验室基金资助项目9140c110206070 c11;杭州电子科技大学校科学研究基金资助项目KYF071506005

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

页数：共3页

页码：92-94