.png){kind=icon}
返回
A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TMC.2010.55.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A Virtual Backbone (VB) of a wireless network is a subset of nodes such that only VB nodes are responsible for routing-related tasks. Since a smaller VB causes less overhead, size is the primary quality factor of VB. Frequently, Unit Disk Graphs (UDGs) are used to model 2D homogeneous wireless networks, and the problem of finding minimum VBs in the networks is abstracted as Minimum Connected Dominating Set (MCDS) problem in UDGs. In some applications, the altitude of nodes can be hugely different and UDG cannot abstract the networks accurately. Then, Unit Ball Graph (UBG) can replace UDG. In this paper, we study how to construct quality CDSs in UBGs in distributed environments. We first give an improved upper bound of the number of independent nodes in a UBG, and use this result to analyze the Performance Ratio (PR) of our new centralized algorithm C-CDS-UBG, which computes CDSs in UBGs. Next, we propose a distributed algorithm D-CDS-UBG originated from C-CDS-UBG and analyze its message and time complexities. Our theoretical analysis shows that the PR of D-CDS-UBG is 14.937, which is better than current best, 22. Our simulations also show that D-CDS-UBG outperforms the competitor, on average.
Keyword:
Wireless networks
connected dominating sets
virtual backbones
unit ball graphs
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
9.2
论文数:
5.9K
被引数:
1.8W
机构
引用论文
分享收藏分享收藏A DESIGN CONCEPT FOR RELIABLE MOBILE RADIO NETWORKS WITH FREQUENCY HOPPING SIGNALING.png)
PROCEEDINGS OF THE IEEE
OAAI
PROCEEDINGS OF THE IEEEIF25.9
OAAI分享收藏
查看更多内容