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

发布时间：2024-03-23 11:26

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

【文章页数】：7 页

【部分图文】：

图1在单位球图中的菱形十二面体

在文献[16]的基础上,Butenko等[17]证明了在任意连通的单位球图上有α(G)≤11opt+1。随后,Kim等[13]采用数学归纳法优化了文献[18]中的结论,得到一个新的关于MIS的算法近似比,为10.917,这是目前已知最优的结论。本节提出了用菱形十二面体进行单....

图2半径为1的单位球

引理3假设G=(V,E)是一个连通的单位球图,Gˉ=(Vˉ,Eˉ)是另一个连通的球图,其有着与G相同的中心,但是每个球的半径为1.5。令I={e1,e2,…,eopt}是图G的一个MCDS,A表示图Gˉ中被以中心为ei的球所覆盖的区域,则有A≤14.1....

图3半径为1.5的单位球图

图2半径为1的单位球证明:假设Di-和Dj-表示两个互相连通且中心为ei和ej、半径为1.5的球,则有d(ei,ej)≤1。本文首先考虑d(ei,ej)=1的情况,令Vi表示Di-的体积,Vji表示Dj--Di-的体积,则

图4菱形十二面体

α(S)≤14.137?2+6.806?8(opt-1)0.707?1≤9.626?4opt+10.366?8注意到,当G的独立集中的一个节点u位于某个单位球的表面时,该节点对应在Gˉ中就是以u为中心、半径0.5的球。在这种情况下,以u为中心、半径为0.5的球为内切球....

本文编号：3935851