Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks

DOI10.1007/S00224-017-9836-ZzbMATH Open1419.05161arXiv1510.01866OpenAlexW2962976294MaRDI QIDQ2322692FDOQ2322692

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

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1510.01866

Recommendations

• A distributed approximation algorithm for strongly connected dominating-absorbent sets in asymmetric wireless ad-hoc networks
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks
• Distributed Computing - IWDC 2003

zbMATH Keywords

distributed algorithmsdominating setsvirtual backbonedisk graphsad-hoc networks

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Cites Work

• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• Unit disk graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Algorithmic construction of sets for k -restrictions
• The online set cover problem
• Approximation algorithms for connected dominating sets
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Leveraging Linial’s Locality Limit
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
• A distributed approximation algorithm for strongly connected dominating-absorbent sets in asymmetric wireless ad-hoc networks

Cited In (2)

• A distributed approximation algorithm for strongly connected dominating-absorbent sets in asymmetric wireless ad-hoc networks
• On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks

This page was built for publication: Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322692)