DisCoMath Seminar: Energy-Efficient Initialization in Single-Hop Radio Networks
DisCoMath Seminar
Energy-Efficient Initialization in Single-Hop Radio Networks
Dominick Banasik
Computer Science MS Student
Rochester Institute of Technology
Register for Zoom Here
Abstract:
Initialization is the problem of assigning unique, consecutive identifiers to every processor in a radio network. This is of particular interest in single-hop networks because once initialized, the processors can communicate without collisions. Nakano and Olariu (2000) introduced an energy-efficient initialization algorithm for single-hop radio networks with sender-side feedback, in which no node is awake for more than O(log log n) timesteps. We study the problem of partial initialization, in which we aim to initialize a constant fraction of the nodes, in the more challenging setting with no sender-side feedback. We present an algorithm for solving partial initialization energy in radio networks with no collision detection or sender-side feedback with probability at least 1 - exp(-n^{1 - epsilon}). Our algorithm runs in linear time and has an energy complexity of O(log* n). As a consequence of solving partial initialization, we can solve initialization without sender-side feedback while maintaining the O(log log n) energy bound.
Intended Audience:
All are Welcome!
To request an interpreter, please visit myaccess.rit.edu
Event Snapshot
When and Where
Who
This is an RIT Only Event
Interpreter Requested?
No