A Better Wake-up in Radio Networks.pdf

A Better Wake-up in Radio Networks Bogdan S. Chlebus ? Dariusz R. Kowalski ? June 4, 2004 Abstract We present an improved algorithm to wake up a multi-hop ad-hoc radio network. The goal is to have all the nodes activated, when some of them may wake up spontaneously at arbitrary times and the remaining nodes need to be awoken by the already active ones. The best previously known wake- up algorithm was given by Chrobak, Ga?sieniec and Kowalski [11], and operated in time O(n5/3 log n), where n is the number of nodes. We give an algorithm with the running time O(n3/2 log n). This also yields better algorithms for other synchronization-type primitives, like leader election and local- clocks synchronization, each with a time performance that differs from that of wake-up by an extra factor of O(log n) only, and improves the best previously known method for the problem by a factor of n1/6. A wake-up algorithm is a schedule of transmissions for each node. It can be represented as a collection of binary sequences. Useful properties of such collections have been abstracted to define a (radio) synchronizer. It has been known that good radio synchronizers exist and previous algorithms [17, 11] relied on this. We show how to construct such synchronizers in polynomial time, from suitable constructible expanders. As an application, we obtain a wake-up protocol for a multiple-access channel that activates the network in time O(k2 polylog n), where k is the number of stations that wake up spontaneously, and which can be found in time polynomial in n. We extend the notion of synchronizers to universal synchronizers. We show that there exist universal synchronizers with parameters that guarantee time O(n3/2 log n) of wake-up. 1 Introduction Radio network is defined by a property that messages arriving simultaneously at a node cannot be received due to mutual interference. Such networks have been typically considered in a fully synchronous mode, when all the nodes are active, their loca