Fountain Codes Based Distributed Storage Algorithms for Large-Scale Wireless Sensor Networks
Authors:
- Salah A. AlySASalah A. Aly
- Zhenning KongZKZhenning Kong
- Emina SoljaninESEmina Soljanin
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 171-182
Abstract
We consider large-scale networks with n nodes, out of which k are in possession, (e.g., have sensed or collected in some other way) k information packets. In the scenarios in which network nodes are vulnerable because of, for example, limited energy or a hostile environment, it is desirable to disseminate the acquired information throughout the network so that each of the n nodes stores one (possibly coded) packet and the original k source packets can be recovered later in a computationally simple way from any (1 + isin)k nodes for some small isin > 0. We developed two distributed algorithms for solving this problem based on simple random walks and Fountain codes. Unlike all previously developed schemes, our solution is truly distributed, that is, nodes do not know n, k or connectivity in the network, except in their own neighborhoods, and they do not maintain any routing tables. In the first algorithm, all the sensors have the knowledge of n and k. In the second algorithm, each sensor estimates these parameters through the random walk dissemination. We present analysis of the communication/transmission and encoding/decoding complexity of these two algorithms, and provide extensive simulation results as well.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Fountain Codes Based Distributed Storage Algorithms for Large-Scale Wireless Sensor Networks2008
- Differentiated Data Persistence with Priority Random Linear Codes2007
- Data Persistence in Large-Scale Sensor Networks with Decentralized Fountain Codes2007
- Growth codes2006
- Decentralized erasure codes for distributed networked storageIEEE Transactions on Information Theory, 2006
- Erasure Codes for Increasing the Availability of Grid Data Storage2006
- Data persistence in sensor networksACM SIGMETRICS Performance Evaluation Review, 2005
- On the Cover Time of Random Geometric Graphs2005
- Randomized Algorithms1995
- Random Plane NetworksJournal of the Society for Industrial and Applied Mathematics, 1961