Name
Title | ||
|---|---|---|
Energy-efficient initialization protocols for single-hop radio networks with no collision detection |
Abstract | ||
|---|---|---|
A radio network ($RN$, for short) is a distributed system consisting of $n$ radio stations. We assume that the stations are small, bulk-produced, hand-held devices running on batteries and cannot be distinguished by serial or manufacturing number. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy-efficient. The initialization problem is to assign each of the $n$ stations in the RN a unique ID. The initialization problem is nontrivial since the stations are assumed to be indistinguishable. The problem is fundamental, since practically all communication protocols for $RN$s proceed under the assumption that the RN has been initialized in advance. The main contribution of this work is to propose energy-efficient randomized initialization protocols for single-hop $RN$s lacking collision detection capabilities. First, we show that if the number $n$ of stations is known beforehand, the single-channel $RN$ can be initialized by a protocol that terminates, with probability exceeding $1 - {\frac{1}{n}}$, in $O(n)$ time slots, with no station being awake for more than $O(\log \log n)$ time slots. We then go on to address the multichannel case and show that if $k$, $(k \geq 1)$, channels are available, an n-station $RN$ can be initialized, with probability exceeding $1 - {\frac{1}{n}}$, in $O({n\over k}+\log n)$ time slots, with no station being awake for more than $O(\log\log n)$ time slots. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/71.877942 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | Field | DocType |
protocols,radio networks,energy-efficient initialization protocols,initialization problem,protocols,single-hop radio networks | Log-log plot,Binary logarithm,Wireless network,Collision detection,Computer science,Efficient energy use,Communication channel,Real-time computing,Initialization,Communications protocol,Distributed computing | Journal |
Volume | Issue | ISSN |
11 | 8 | 1045-9219 |
Citations | PageRank | References |
28 | 3.13 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Koji Nakano | 1 | 1165 | 118.13 |
| Stephen Olariu | 2 | 125 | 8.24 |