Secure Initialization in Single-Hop Radio Networks
Miroslaw Kutylowski, Wojciech Rutkowski
We consider single-hop radio networks, where collisions in the shared
channel cannot be detected (no-CD model). A radio channel can be
accessed by an adversary trying to degrade functionality of the network,
so we are interested in algorithms that work in the presence of an
adversary, who knows the algorithm executed and may try make it faulty
by injecting own messages. We also focus on algorithms that are time and
energy efficient.
We propose a randomized initialization algorithm for a single-hop no-CD
radio network. The algorithm has time complexity O(N) and energy cost
O(sqrt(log N)). This is not much worse than the best fragile algorithms
constructed so far (O( N) in time complexity and O(log log N) energy
cost). Our algorithm succeeds with probability
1-2^{-Omega(sqrt(log N))}
in presence of an adversary, who has energy cost Theta(log N).