Details

Autor(en) / Beteiligte

• Abu-Khzam, Faisal N.
• Markarian, Christine
• Heide, Friedhelm Meyer auf der
• Schubert, Michael

Titel

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

Ist Teil von

• Theory of computing systems, 2018-11, Vol.62 (8), p.1673-1689

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2018

Quelle

Business Source Ultimate

Beschreibungen/Notizen

• 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 directed 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. Due to the dynamic nature of ad-hoc networks, distributed algorithms for this problem are of practical significance. Hence, we seek algorithms that do not require centralized computation and yet yield good approximation factors and/or behave well in practice. We present a first distributed approximation algorithm for this problem. The algorithm achieves a constant approximation ratio if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded and takes O ( D i a m ) rounds, where D i a m is the diameter of the graph. Moreover, we present a simple distributed heuristic algorithm and conduct an extensive simulation study showing that our heuristic outperforms previously known approaches for the problem.