三维无线自组织网络中最小虚拟骨干的近似算法

• 作者: 易梦 梁家荣 覃斌
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 三维无线自组织网络 虚拟骨干 连通控制集 斯坦纳树 菱形十二面体
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 计算机网络
• 页码范围: 250-256
• 页数: 7页
• 分类号: TP393
• 字数: 7703字
• 语种: 中文
• DOI: 10.11896/jsjkx.190700059

摘要

在均质无线自组织网络中,虚拟骨干(Virtual Backbone,VB)的大小是衡量无线自组织网络质量的一个重要因素,虚拟骨干越小,网络路由开销越少.最小虚拟骨干的求取问题能够抽象为最小连通控制集问题.针对二维无线自组织网络上的单位圆盘图(Unit Disk Graph,UDG)中最小连通控制集问题,目前已有很多研究成果,但是在现实中的某些情况下,单位圆盘图并不能准确地抽象网络.因此,文中提出了在单位球图(Unit Ball Graph,UBG)中构建高质量的连通控制集(Connected Domi-nating Set,CDS)的算法ST-CDS,给出了单位球图中独立节点个数的一个优化上界,并进一步利用该优化上界得到连通控制集的性能比.所提算法主要运用构造最小斯坦纳节点的斯坦纳树(Steiner Tree with Minimum Number of Steiner Nodes)方法来优化节点之间的连通部分.理论分析表明,ST-CDS算法的性能比为11.8080+ln11,是目前已知该方向研究中最好的结果.仿真结果也验证了ST-CDS算法的可行性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	梁家荣		5	0	0.0	0.0
2	易梦	广西大学计算机与电子信息学院	2	0	0.0	0.0
3	覃斌	广西大学计算机与电子信息学院	3	4	1.0	2.0