Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks

F.N. Abu-Khzam, C. Markarian, F. Meyer auf der Heide, M. Schubert, ArXiv:1510.01866 (2015).

Download
No fulltext has been uploaded.
Preprint | English
Author
; ; ;
Abstract
We consider the problem of dominating set-based virtual backbone used for routing in asymmetric wireless ad-hoc networks. These networks have non-uniform transmission ranges and are modeled using the well-established disk graphs. 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. Distributed algorithms for this problem are of practical significance due to the dynamic nature of ad-hoc networks. We present a first distributed approximation algorithm, with a constant approximation factor and O(Diam) running time, where Diam is the diameter of the graph. Moreover we present a simple heuristic algorithm and conduct an extensive simulation study showing that our heuristic outperforms previously known approaches for the problem.
Publishing Year
Journal Title
arXiv:1510.01866
LibreCat-ID

Cite this

Abu-Khzam FN, Markarian C, Meyer auf der Heide F, Schubert M. Approximation and Heuristic Algorithms for Computing Backbones in  Asymmetric Ad-Hoc Networks. arXiv:151001866. 2015.
Abu-Khzam, F. N., Markarian, C., Meyer auf der Heide, F., & Schubert, M. (2015). Approximation and Heuristic Algorithms for Computing Backbones in  Asymmetric Ad-Hoc Networks. ArXiv:1510.01866.
@article{Abu-Khzam_Markarian_Meyer auf der Heide_Schubert_2015, title={Approximation and Heuristic Algorithms for Computing Backbones in  Asymmetric Ad-Hoc Networks}, journal={arXiv:1510.01866}, author={Abu-Khzam, Faisal N. and Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael}, year={2015} }
Abu-Khzam, Faisal N. , Christine Markarian, Friedhelm Meyer auf der Heide, and Michael Schubert. “Approximation and Heuristic Algorithms for Computing Backbones in  Asymmetric Ad-Hoc Networks.” ArXiv:1510.01866, 2015.
F. N. Abu-Khzam, C. Markarian, F. Meyer auf der Heide, and M. Schubert, “Approximation and Heuristic Algorithms for Computing Backbones in  Asymmetric Ad-Hoc Networks,” arXiv:1510.01866. 2015.
Abu-Khzam, Faisal N., et al. “Approximation and Heuristic Algorithms for Computing Backbones in  Asymmetric Ad-Hoc Networks.” ArXiv:1510.01866, 2015.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1510.01866

Search this title in

Google Scholar