传感器网络中最小 k-连通 m-控制集问题的近似算法?

摘要：

在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小 k-连通 m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小 k-连通 m-控制集问题,给出了一个构造最小 k-连通 m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性.

关键词：最小k-连通m-控制集、极大独立集、双向圆盘图、无线传感器网络

分类号：O221.7(运筹学)

在线出版日期：2012-11-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：633-640