Startseite > Publikationen > Publikationen

Publikationen

Markarian, Christine;Schubert, Michael;Meyer auf der Heide, Friedhelm:

Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.

In: Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, LNCS, 5. - 6. Sep. 2013, Springer-Verlag, to appear

Abstract

Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc networks. Such backbones receive and transmit messages from/to every node in the network. Existing distributed algorithms only consider undirected graphs, which model symmetric networks with uniform transmission ranges. We are particularly interested in the well-established disk graphs, which model asymmetric networks with non-uniform transmission ranges. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the subgraph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. We introduce the first distributed algorithm for this problem in disk graphs. The algorithm gives an $O(k^4)$-approximation ratio and has a runtime bound of $O(Diam)$ where $Diam$ is the diameter of the graph and $k$ denotes the transmission ratio $r_{max}/r_{min}$ with $r_{max}$ and $r_{min}$ being the maximum and minimum transmission range, respectively. Moreover, we apply our algorithm on the subgraph of disk graphs consisting of only bidirectional edges. Our algorithm gives an $O(\ln k)$-approximation and a runtime bound of $O(k^8 \log^*n)$, which, for bounded $k$, is an optimal approximation for the problem, following Lenzen and Wattenhofer's $\Omega(\log^*n)$ runtime lower bound for distributed constant approximation in disk graphs.

Bibtex

@inproceedings{hniid=7885,
author = {Markarian, Christine and Schubert, Michael and Meyer auf der Heide, Friedhelm},
title = {Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks},
booktitle = {Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013},
series = {LNCS},
publisher = {Springer-Verlag},
month = {5~-~6~} # sep,
year = {2013},
note = {to appear},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/7885