Interference-Resilient Information Exchange

This paper presents an efficient protocol for reliably exchanging information in a single-hop, multi-channel radio network subject to unpredictable interference. We model the interference by an adversary that can simultaneously disrupt up to t of the C available channels. We assume no shared secret keys or third-party infrastructure. The running time of our protocol depends on the gap between C and t: when the number of channels C =Omega(t^2), the running time is linear; when only C = t+1 channels are available, the running time is exponential. We prove that exponential-time is unavoidable in the latter case. At the core of our protocol lies a combinatorial function, possibly of independent interest, described for the first time in this paper: the multi-selector. A multi-selector generates a sequence of channel assignments for each device such that every sufficiently large subset of devices is partitioned onto distinct channels by at least one of these assignments.

Published in:
Proceedings of the 28th Conference on Computer Communications
Presented at:
IEEE InfoCom 2009, Rio de Janeiro, Brazil, April 19-25, 2009
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa

 Record created 2009-01-23, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)