skip to main content
Show Results with:

The wake up dominating set problem

Bannoura, Amir et al.

Theoretical computer science -- Elsevier Science -- Volume: 608 P2; (pages 120-134) -- 2015

Online access

  • Title:
    The wake up dominating set problem
  • Author: Bannoura, Amir;
    Ortolf, Christian;
    Reindl, Leonhard;
    Schindelhauer, Christian
  • Found In: Theoretical computer science. Volume 608:Number P2(2015); 20151210; 120-134
  • Journal Title: Theoretical computer science
  • Subjects: Machine theory; Robots; Formal languages; Computer science Mathematics; Automates mathématiques, Théorie des Périodiques; Robots; Langages formels; Formal languages; Machine theory; Robots; Teoretisk databehandling; LCSH: Machine theory; LCSH: Robots; LCSH: Formal languages; LCSH: Computer science Mathematics; Dewey: 004.015105
  • Rights: Licensed
  • Publication Details: Elsevier Science
  • Abstract: AbstractRecently developed wake-up receivers pose a viable alternative for duty-cycling in wireless sensor networks. Here, a special radio signal can wake up close-by nodes. We model the wake-up range by the unit-disk graph. Such wake-up radio signals are very energy expensive and limited in range. Therefore, their number must be minimized.We revisit the Connected Dominating Set (CDS) problem for unit-disk graphs and consider an online variant, where starting from an initial node all nodes need to be woken up, while the online algorithm knows only the nodes woken up so far and has no information about the number and location of the sleeping nodes.We show that in general this problem cannot be solved effectively, since a worst-case setting exists where the competitive ratio, i.e. the number of wake-up signals divided by the size of the minimum CDS, isΘ(n)fornnodes. For dense random uniform placements, this problem can be solved within a constant factor competitive ratio with high probability, i.e.1nc, when the nodes positions are known or at least some rough distance estimator.For a restricted adversary with a reduced wake-up range of1ϵwe present a deterministic wake-up algorithm with a competitive ratio ofO(ϵ12)for the general problem in two dimensions.In the case of random placement without any explicit position information we present anO(logn)-competitive epidemic algorithm to wake up all nodes with high probability. Simulations show that a simplified version of this oblivious online algorithm already produces reasonable results, that allow its application in the real world.
  • Identifier: Journal ISSN: 0304-3975
  • Publication Date: 2015
  • Physical Description: Electronic
  • Shelfmark(s): 8814.556000
  • UIN: ETOCvdc_100045996000.0x000001

Searching Remote Databases, Please Wait