conference paper
A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks
Christine
Markarian
author 37612
Friedhelm
Meyer auf der Heide
author 15523
Michael
Schubert
author
63
department
SFB 901
project
SFB 901 - Subprojekt A1
project
SFB 901 - Project Area A
project
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 Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk graphs.
https://ris.uni-paderborn.de/download/563/1278/563-978-3-642-45346-5_16.pdf
application/pdf
2013
Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)10.1007/978-3-642-45346-5_16
217-227
Markarian, Christine, et al. “A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.” <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>, 2013, pp. 217–27, doi:<a href="https://doi.org/10.1007/978-3-642-45346-5_16">10.1007/978-3-642-45346-5_16</a>.
Markarian, C., Meyer auf der Heide, F., & Schubert, M. (2013). A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks. In <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i> (pp. 217–227). <a href="https://doi.org/10.1007/978-3-642-45346-5_16">https://doi.org/10.1007/978-3-642-45346-5_16</a>
@inproceedings{Markarian_Meyer auf der Heide_Schubert_2013, series={LNCS}, title={A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks}, DOI={<a href="https://doi.org/10.1007/978-3-642-45346-5_16">10.1007/978-3-642-45346-5_16</a>}, booktitle={Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)}, author={Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael}, year={2013}, pages={217–227}, collection={LNCS} }
C. Markarian, F. Meyer auf der Heide, M. Schubert, in: Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 217–227.
Markarian, Christine, Friedhelm Meyer auf der Heide, and Michael Schubert. “A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.” In <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>, 217–27. LNCS, 2013. <a href="https://doi.org/10.1007/978-3-642-45346-5_16">https://doi.org/10.1007/978-3-642-45346-5_16</a>.
Markarian C, Meyer auf der Heide F, Schubert M. A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks. In: <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>. LNCS. ; 2013:217-227. doi:<a href="https://doi.org/10.1007/978-3-642-45346-5_16">10.1007/978-3-642-45346-5_16</a>
C. Markarian, F. Meyer auf der Heide, and M. Schubert, “A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks,” in <i>Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)</i>, 2013, pp. 217–227.
5632017-10-17T12:42:42Z2020-05-07T05:27:15Z