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

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

作　　者：覃斌 梁家荣[1,2] 易梦 Qin Bin;Liang Jiarong;Yi Meng(School of Computer&Electronics Information,Guangxi University,Nanning 530004,China;Guangxi Key Laboratory of Multimedia Communications&Network Technology,Nanning 530004,China)

机构地区：[1]广西大学计算机与电子信息学院,南宁530004 [2]广西多媒体通信与网络技术重点实验室,南宁530004

出　　处：《计算机应用研究》2021年第1期264-268,272,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(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问题的近似比降低的方法是可行的。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 net-work,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).Corespondingly,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+ε)-approx imation algo-rithm 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 MW CDS problem in node-weighted UDG is feasi-ble by improving the approximate ratio of connected parts.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]