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

摘要

在均质无线自组织网络中,虚拟骨干(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算法的可行性.