The wake-up problem in multihop radio networks

Marek Chrobak, Leszek Ga̧sieniec, Dariusz R. Kowalski

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

We study the problem of waking up a collection of n processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up spontaneously or gets activated by receiving a wake-up signal from another node. All active nodes transmit the wake-up signals according to a given protocol W. The running time of W is the number of steps counted from the first spontaneous wake-up until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time O(n 5/3 logn). Our protocol is based on a novel concept of a shift-tolerant selector to which we refer as a (radio) synchronizer. The second protocol is randomized, and its expected running time is O(D log 2 n), where D is the diameter of the network. Subsequently we show how to employ our wake-up protocols to solve two other communication primitives: leader election and clock synchronization.

Original languageEnglish (US)
Pages (from-to)1453-1471
Number of pages19
JournalSIAM Journal on Computing
Volume36
Issue number5
DOIs
StatePublished - 2006
Externally publishedYes

Keywords

  • Broadcasting
  • Gossiping
  • Probabilistic method
  • Radio network
  • Wake-up

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'The wake-up problem in multihop radio networks'. Together they form a unique fingerprint.

Cite this