无线网络连通支配集分布式构造

• 作者: 孔维祎 孙坤 武舒 郑建超
• 来源期刊: 曲阜师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 连通支配集 近似算法 时间复杂度 消息复杂度
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 54-59
• 页数: 6页
• 分类号: TN925.93
• 字数: 5047字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2019.3.054

摘要

针对在无线网络中构造连通支配集问题,提出了一种基于圆盘图模型构造连通支配集的分布式算法PS-CDS,算法分为2部分,首先由PS-CDS-1算法构造极大独立集,然后通过PS-CDS-2算法向极大独立集中添加连通节点得到连通支配集.所提出的算法包括功率分配方案,选择能完成邻域广播的最小发送功率.算法的时间复杂度为O(n),消息复杂度为O(nm),近似比为R2Τ/R2min(2opt+1)-2.将PS-CDS算法与其他连通支配集算法进行实验比较,结果表明PS-CDS算法所生成的连通支配集规模最小.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙坤	曲阜师范大学信息科学与工程学院	5	0	0.0	0.0
2	武舒	曲阜师范大学信息科学与工程学院	3	0	0.0	0.0
3	郑建超	中山大学电子与信息工程学院	1	0	0.0	0.0