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

DOI10.1007/S00224-017-9836-ZMaRDI QIDQ2322692zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A distributed approximation algorithm for strongly connected dominating-absorbent sets in asymmetric wireless ad-hoc networks
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Algorithmic construction of sets for k -restrictions
• Approximation algorithms for connected dominating sets
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• 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
• The online set cover problem
• Unit disk graphs

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)