《计算机应用研究》|Application Research of Computers

无线网络中最小权虚拟骨干网连通部分的新方法

New method of connecting minimum-weighted virtual backbone in wireless network

免费全文下载 (已被下载 次)  
获取PDF全文
作者 覃斌,梁家荣,易梦
机构 1.广西大学 计算机与电子信息学院,南宁 530004;2.广西多媒体通信与网络技术重点实验室,南宁 530004
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2021)01-053-0264-05
DOI 10.19734/j.issn.1001-3695.2019.10.0628
摘要 无线网络中的虚拟骨干(VB)是一些无线节点的子集,因此只有VB中的节点负责路由相关任务,并且VB总权值越小会导致开销越少。在一个点赋权的无线网络中,不单要考虑VB中节点数的多少,更重要的是要考虑其总权值的大小。通常,一个赋权无线网络被模型化为一个点赋权单位圆盘图(UDG),相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集(MWCDS)问题进行研究。求MWCDS是一个NP-难问题。为降低点赋权UDG中MWCDS问题的近似比,在连通部分提出一种新方法——基于度的点赋权Steiner树算法。结合目前最好的结果,对于UDG中的MWCDS问题将得到一个(3.32+ε)-近似算法。同样地,对于UDG中的最小权顶点覆盖(MWCVC)问题也将得到一个(3.32+ε)-近似算法。证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的。
关键词 Steiner树; 虚拟骨干; 单位圆盘图; 无线网络
基金项目 国家自然科学基金资助项目(61862003)
广西自然科学基金资助项目(2018GXNSFDA281052,2017GXNSFAA198276,2017GXNSFAA198263)
本文URL http://www.arocmag.com/article/01-2021-01-053.html
英文标题 New method of connecting minimum-weighted virtual backbone in wireless network
作者英文名 Qin Bin, Liang Jiarong, Yi Meng
机构英文名 1.School of Computer & Electronics Information,Guangxi University,Nanning 530004,China;2.Guangxi Key Laboratory of Multimedia Communications & Network Technology,Nanning 530004,China
英文摘要 The virtual backbone(VB) in wireless networks is a subset of some wireless nodes, such that only VB nodes are responsible for routing related tasks. The smaller the weight of VB, the less the overhead. In a node-weighted wireless network, not only the number of nodes in VB should be considered, but also the total weight should be considered. Frequently, a weighted wireless network is modeled as a node-weighted unit disk graph(UDG). Correspondingly, the minimum-weighted VB problem in the weighted wireless network is abstracted as the minimum-weighted connected dominating set(MWCDS) problem in the node-weighted UDG. Finding MWCDS is a NP-hard problem. To reduce the approximate ratio of the connected part of the MWCDS problem in node-weighted UDG, this paper proposed a new method—degree-based node-weighted Steiner tree algorithm in the connected part. Combining the best results at present, it will obtain a(3.32+ε) -approximation algorithm for MWCDS problem in UDG. Similarly, it will also obtain a(3.32+ε) -approximation algorithm for MWCVC problem in UDG. It is proved that the method of reducing the approximate ratio of the MWCDS problem in node-weighted UDG is feasible by improving the approximate ratio of connected parts.
英文关键词 Steiner tree; virtual backbone(VB); unit disk graph(UDG); wireless network
参考文献 查看稿件参考文献
 
收稿日期 2019/10/21
修回日期 2019/12/19
页码 264-268,272
中图分类号 TP393
文献标志码 A