Page Content

Sachin Agarwal's Publications

Reliable Wireless Broadcasting with Near-Zero Feedback
Citation key	XAST-RWBNZF-10
Author	Xiao, Weiyao and Agarwal, Sachin and Starobinski, David and Trachtenberg, Ari
Title of Book	Proceedings of IEEE INFOCOM 2010
Pages	1–5
Year	2010
ISBN	978-1-4244-5836-3
ISSN	0743-166X
DOI	http://dx.doi.org/10.1109/INFCOM.2010.5462188
Location	San Diego, CA, USA
Month	March
Abstract	We examine the problem of minimizing feedback in reliable wireless broadcasting, by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves to estimating the maximum number of packets dropped among many receivers. With rateless codes, this corresponds to the number of redundant transmissions needed at the source for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. We show that FSLF has the desirable property of becoming more accurate with increasing numbers of receivers, while maintaining a fixed overhead. Our protocols are channel agnostic, in that they do not require a-priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which provide about a 30\% latency and energy consumption savings over standard Rateless Deluge.