基于极大独立集的最小连通支配集的分布式算法

• 作者: 周明天 唐勇
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 无线传感器网络 移动自组织网络 广播 极大独立集 最小连通支配集
• 年，卷（期）: 2007,（5）
• 所属期刊栏目: 学术论文
• 页码范围: 868-874
• 页数: 7页
• 分类号: TP393
• 字数: 10115字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2007.05.014

摘要

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周明天	电子科技大学计算机科学与工程学院	315	3725	27.0	49.0
2	唐勇	电子科技大学计算机科学与工程学院	28	1193	10.0	28.0