Reliable Data Dissemination

Weiyao Xiao (PhD ’10)
Prof. David Starobinski, Prof. Ari Trachtenberg, Dr. Sachin Agarwal (Deutsche Telekom)

Funding: NSF and Deutsche Telekom

Background: Commercial providers are increasingly permitting third-parties to develop and implement their own applications on wireless devices, ranging from sensors to 3G cellular phones. Accordingly, reliable data dissemination is quickly emerging as a key enabling technology, providing fundamental services such as over-the-air programming and security patching. The commonly high density of wireless devices hampers efficient accomplishment of this task, however.

Description: In the project, we address the scalability of reliable data dissemination in two ways: (i) we develop and analyze policies harnessing the multi-channel transceiving capabilities of single radio wireless devices, and (ii) we rigorously address the problem of quantifying forward error correction (FEC) redundancy to eliminate control traffic (e.g., Acknowledgments) with high probability.

Results: We first analyze the performance limits of data dissemination in multi-channel,single radio networks. For arbitrary topology networks, we model this problem as a stochastic shortest path optimization and provide approaches to compute the optimal control policy achieving minimum average delay, in a finite number of steps. Due to the prohibitive computational complexity of the optimal solution, we develop asymptotically optimal polices for practical networks with high node density. Our analysis and simulations reveal that a single radio in each receiver suffices to achieve performance gain directly proportional to the number of channels available. Next, pairing rateless coding with extreme value theory, we quantify FEC redundancy by analyzing the cumulative distribution function (CDF) of the data dissemination completion time. We precisely characterize this CDF and demonstrate the existence of a phase transition associated with it. Further, we analyze heterogeneous packet loss models, by establishing a connection to the multi-set coupon collector problem. Finally, we address the problem of performing online FEC estimation under unknown channel statistics. Leveraging properties of extreme value estimators, we design novel techniques that extrapolate over limited information. We demonstrate the benefit of accurately quantifying FEC redundancy through real experiments, which reveal drastic reduction in control traffic, energy consumption and overall delay. In summary, this work contributes to the design and analysis of rapid and energy-efficient data dissemination protocols for large scale wireless networks, thereby facilitating their deployment.

Publications:

http://people.bu.edu/staro/Infocom_QE_Final.pdf
http://people.bu.edu/staro/JSAC_EVT_Final.pdf
http://people.bu.edu/staro/ToN-Weiyao-Final.pdf
http://people.bu.edu/staro/Infocom-FEC-2009.pdf
http://people.bu.edu/staro/camera-info07.pdf
http://people.bu.edu/staro/p0501-xiao.pdf

Website: http://nislab.bu.edu