Distributed Fountain Codes for Networked Storage
Authors:
- 3 August 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 5 (15206149)
Abstract
We investigate the problem of constructing fountain codes for distributed storage in sensor networks. Specifically, we assume that there are n storage nodes with limited memory and k < n data nodes generating the data by sensing the environment. We want a data collector who can appear anywhere in the network, to query any k + epsi storage nodes and be able to retrieve almost all the data packets. We demonstrate how it is possible to solve this problem by using a specific kind of fountain code that requires only linear communication and decoding complexity. Further, for a grid topology, we propose a randomized algorithm that constructs the fountain code over a network using only geographical knowledge and local decisions. A key step in the analysis of our algorithm is a novel result concerning random walks on finite grids with trapsKeywords
This publication has 6 references indexed in Scilit:
- Decentralized erasure codes for distributed networked storageIEEE Transactions on Information Theory, 2006
- Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes2005
- LT codes2003
- Next century challenges1999
- Random Walks and Random Environments1996
- Random walks on random lattices1986