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

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