On Practical Construction of Quality Fault-Tolerant Virtual Backbone in Homogeneous Wireless Networks
| Autor: | Yingshu Li, Yao-Lin Jiang, Sung-Sik Kwon, Donghyun Kim, Bei Liu, Wei Wang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Computer Networks and Communications Wireless network Unit disk graph Computer science Approximation algorithm 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Range (mathematics) 010201 computation theory & mathematics Dominating set Bounded function 0202 electrical engineering electronic engineering information engineering Electrical and Electronic Engineering Constant (mathematics) Wireless sensor network Software |
| Zdroj: | IEEE/ACM Transactions on Networking. 26:412-421 |
| ISSN: | 1558-2566 1063-6692 |
| DOI: | 10.1109/tnet.2017.2780262 |
| Popis: | Over years, many efforts are made for the problem of constructing quality fault-tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g., with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum $k$ -connected $m$ -dominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers $k$ and $m$ satisfying $m \geq k \geq 1$ and $k \leq 3$ . This paper introduces an approximation algorithm for the problem with $m \geq k \geq 1$ . This algorithm is simple to implement; it connects the components by adding a bounded number of paths, which first computes a 1-connected $m$ -dominating set $D$ and repeats the following steps: (a) search the separators arbitrarily in $(i-1,m)$ -CDS with $i = 2, 3, \cdots, k$ , (b) add a bounded number of paths connecting the components separated by separators in $(i-1,m)$ -CDS to improve the connectivity of $(i-1,m)$ -CDS, until it becomes $k$ -connected, and (c) remove redundant paths if there exist at every iteration. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant, for any fixed $k$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|