计算机应用研究

作者：覃斌,梁家荣,易梦,

单位：1.广西大学计算机与电子信息学院,南宁530004；2.广西多媒体通信与网络技术重点实验室,南宁530004；

关键词：Steiner树,虚拟骨干,单位圆盘图,无线网络,

基金：国家自然科学基金资助项目(61862003)；广西自然科学基金资助项目(2018GXNSFDA281052,2017GXNSFAA198276,2017GXNSFAA198263)；；

无线网络中的虚拟骨干（VB）是一些无线节点的子集，因此只有VB中的节点负责路由相关任务，并且VB总权值越小会导致开销越少。在一个点赋权的无线网络中，不单要考虑VB中节点数的多少，更重要的是要考虑其总权值的大小。通常，一个赋权无线网络被模型化为一个点赋权单位圆盘图（UDG），相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集（MWCDS）问题进行研究。求MWCDS是一个NP-难问题。为降低点赋权UDG中MWCDS问题的近似比，在连通部分提出一种新方法——基于度的点赋权Steiner树算法。结合目前最好的结果，对于UDG中的MWCDS问题将得到一个（3.32+ε）-近似算法。同样地，对于UDG中的最小权顶点覆盖（MWCVC）问题也将得到一个（3.32+ε）-近似算法。证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的。

来源：2021年第1期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第1期