无线自组网络中的消息最优的连通控制集

• 作者: 唐天兵 朱继生 梁家荣
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 极大独立集 连通控制集 消息最优 最小连通控制集 虚拟骨干网
• 年，卷（期）: 2021,（1）
• 所属期刊栏目: 网络与安全
• 页码范围: 122-125
• 页数: 4页
• 分类号: TP393
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2021.01.022

摘要

在无线自组网中,提出了一种虚拟骨干网连通控制集(connected dominating set).然而,寻找最小连通控制集(minimum connected dominating set)是一个NP困难的问题.在很多文献中已经提出了计算最小连通控制集的近似算法,这些算法大都存在近似比很差、时间复杂度和消息复杂度高等问题.近年来,提出了一些新的构造连通控制集的分布式启发式算法.这些新的启发式算法基于生成树的构造,这使得在迁移和拓扑更改的情况下维护连通控制集的通信开销非常昂贵,会对整个网络的性能及生存时间产生影响.因此消息最优的连通控制集也就被提出.在保证构建消息最优的连通控制集的情况下,通过建立一种新的求解极大独立集的模型,考虑到圆不能密铺会造成一定的误差,通过使用正六边形来代替R为0.5的圆,从而求得了一个更为精确的三跳内极大独立集,改善了文献[16]中的结果,得到了更小的连通控集近似比,其值为143opt+33.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐天兵		41	144	7.0	10.0
2	梁家荣		185	1065	17.0	23.0
3	朱继生		1	0	0.0	0.0