More Web Proxy on the site http://driver.im/

research-article

Decentralized coding algorithms for distributed storage in wireless sensor networks

Authors:

Emina SoljaninAuthors Info & Claims

IEEE Journal on Selected Areas in Communications, Volume 28, Issue 2

Pages 261 - 267

Published: 01 February 2010 Publication History

Abstract

We consider large-scale wireless sensor 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 so that the original k source packets can be recovered, locally and in a computationally simple way from any k(1 + Ɛ) nodes for some small Ɛ > 0. We develop decentralized Fountain codes based algorithms to solve this problem. Unlike all previously developed schemes, our algorithms are 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.

References

[1]

C. Raghavendra, K. Sivalingam, and T. Znati, Wireless Sensor Networks. Norwell, MA, USA: Kluwer Academic Publishers, 2004.

Digital Library

[2]

H. Weatherspoon and J. D. Kubiatowics, "Erasure coding vs. replication: a quantitive comparision," in Proc. 1st International Workshop on Peer-to-Peer Systems (IPTPS '02), Cambridge, MA, USA, Springer LNCS, pp. 328-337, March 78 2002.

Digital Library

[3]

A. G. Dimakis, V. Prabhakaran, and K. Ramchandran, "Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes," in Proc. 4th IEEE Symposium on Information Processing in Sensor Networks (IPSN '05), Los Angeles, CA, USA, pp. 111-117, April 2005.

Digital Library

[4]

A. G. Dimakis, V. Prabhakaran, and K. Ramchandran, "Decentralized erasure codes for distributed networked storage," IEEE Trans. Inf. Theory, vol. 52, pp. 2809-2816, 2006.

[5]

M. Pitkanen, R. Moussa, M. Swany, and T. Niemi, "Erasure codes for increasing the availability of grid data storage," in Proc. Advanced International Conference on Telecommunications and International Conference on Internet and Web Applications and Services (AICT/ICIW), pp. 185-185, 2006.

Digital Library

[6]

C. Huang and L. Xu, "Star: An efficient coding scheme for correcting triple storage node failures," in Proc. 4th Usenix Conference on File and Storage Technol. (FAST'05), San Francisco, USA, pp. 15-15, 2005.

Digital Library

[7]

J. S. Plank, "Erasure codes for storage applications," in (Tutorial) Proc. 4th Usenix Conference on File and Storage Technol. (FAST'05), San Francisco, USA, 2005.

[8]

J. S. Plank and M. G. Thomason, "An exploration of nonasymptotic low-density, parity check erasure codes for wide-area storage applications," Parallel Processing Letters, vol. 17, pp. 103-123, March 2007.

[9]

A. G. Dimakis, V. Prabhakaran, and K. Ramchandran, "Distributed fountain codes for networked storage," in Proc. 31st IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'06), Toulouse, France, May, 2006.

[10]

Y. Lin, B. Liang, and B. Li, "Data persistence in large-scale sensor networks with decentralized fountain codes," in Proc. IEEE INFOCOM'07, Anchorage, AK, USA, pp. 1658-1666, May, 2007.

[11]

A. Kamra, V. Misra, J. Feldman, and D. Rubenstein, "Growth codes: Maximizing sensor network data persistence," in Proc. ACM Sigcom'06, Pisa, Italy, September, 2006.

Digital Library

[12]

Y. Lin, B. Li, and B. Liang, "Differentiated data persistence with priority random linear code," in Proc. 27th Int. Conf. on Distributed Computing Systems (ICDCS'07), Toronto, Canada, June, 2007.

Digital Library

[13]

A. Jiang, "Network coding for joint storage and transmission with minimum cost," in Proc. IEEE International Symposium on Information Theory (ISIT '06), Seattle, WA, USA, pp. 1359-1363, July, 2006.

[14]

D. Wang, Q. Zhang, and J. Liu, "Partial network coding: thoery and application for continuous sensor data collection," in Proc. IEEE 14th international workshop on quality of service (IWQoS), 2006.

[15]

S. Acedanski, S. Deb, M. Médard, and R. Koetter, "How good is random linear coding based distributed networked storage?," in Proc. 2nd Workshop on Network Coding (NetCod'05), Pisa, Italy, April, 2005.

[16]

A. G. Dimakis, P. B. Godfrey, M. Wainwright, and K. Ramchandran, "Network coding for distributed storage systems," in Proc. IEEE INFOCOM' 07, Anchorage, AK, USA, pp. 2000-2008, May, 2007.

[17]

D. Munaretto, J. Widmer, M. Rossi, and M. Zorzi, "Network coding strategies for data persistence in static and mobile sensor networks," in Proc. Int. Workshop on Wireless Networks: Communication, Cooperation and Competition (WCN3'07), Limassol, Cyprus, April 2007.

[18]

E. N. Gilbert, "Random plane networks," J. Soc. Indust. Appl. Math., vol. 9, pp. 533-543, 1961.

[19]

M. Penrose, Random Geometric Graphs. New York: Oxford University Press, 2003.

[20]

M. Luby, "LT codes," in 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, Canada, Nov., 2002.

Digital Library

[21]

A. Shokrollahi, "Raptor codes," IEEE Trans. Inf. Theory, vol. 52, pp. 2551-2567, 2006.

Digital Library

[22]

D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs. http://statwww.berkeley.edu/users/aldous/RWG/book.html.

[23]

S. Ross, Stochastic Processes. New York: Wiley, second ed., 1995.

[24]

C. Avin and G. Ercal, "On the cover time of random geometric graphs," in Proc. 32nd International Colloquium of Automata, Languages and Programming (ICALP'05), Lisboa, Portugal, pp. 677-689, July, 2005.

Digital Library

[25]

R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

Cited By

Yang SHareedy ACalderbank RDolecek L(2020)Topology-Aware Cooperative Data Protection in Blockchain-Based Decentralized Storage Networks2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9174443(622-627)Online publication date: 21-Jun-2020
https://dl.acm.org/doi/10.1109/ISIT44484.2020.9174443
Byers JLuby MMitzenmacher M(2019)A digital fountain retrospectiveACM SIGCOMM Computer Communication Review10.1145/3371934.337196049:5(82-85)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371934.3371960
Meng LShang YJiang WJiang PHu Y(2019)LT Codes and the Minimum Spanning Tree Based Distributed Storage in Wireless Sensor NetworksMobile Networks and Applications10.1007/s11036-018-1173-127:3(1084-1091)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1007/s11036-018-1173-1
Show More Cited By

Decentralized coding algorithms for distributed storage in wireless sensor networks
1. Networks
  1. Network types
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Robust decentralized data storage and retrieval for wireless networks

In this paper we study the problem of distributed data storage using Rateless codes for large-scale resource-constrained wireless networks. We focus on building a robust storage system using Fountain codes from physically decentralized sources. Fountain ...
Relay Node Placement in Wireless Sensor Networks

A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy ...
Sensor scheduling for p-percent coverage in wireless sensor networks

We study sensor scheduling problems of p-percent coverage in this paper and propose two scheduling algorithms to prolong network lifetime due to the fact that for some applications full coverage is not necessary and different subareas of the monitored ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Journal on Selected Areas in Communications

IEEE Journal on Selected Areas in Communications Volume 28, Issue 2

February 2010

168 pages

ISSN:0733-8716

Issue’s Table of Contents

Copyright © 2010.

Publisher

IEEE Press

Publication History

Published: 01 February 2010

Revised: 07 August 2009

Received: 29 January 2009

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang SHareedy ACalderbank RDolecek L(2020)Topology-Aware Cooperative Data Protection in Blockchain-Based Decentralized Storage Networks2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9174443(622-627)Online publication date: 21-Jun-2020
https://dl.acm.org/doi/10.1109/ISIT44484.2020.9174443
Byers JLuby MMitzenmacher M(2019)A digital fountain retrospectiveACM SIGCOMM Computer Communication Review10.1145/3371934.337196049:5(82-85)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371934.3371960
Meng LShang YJiang WJiang PHu Y(2019)LT Codes and the Minimum Spanning Tree Based Distributed Storage in Wireless Sensor NetworksMobile Networks and Applications10.1007/s11036-018-1173-127:3(1084-1091)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1007/s11036-018-1173-1
Al-Awami LHassanein H(2017)Robust decentralized data storage and retrieval for wireless networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.02.004128:C(41-50)Online publication date: 9-Dec-2017
https://dl.acm.org/doi/10.1016/j.comnet.2017.02.004
Al-Awami LHassanein H(2016)Distributed Data Storage Systems for Data Survivability in Wireless Sensor Networks using Decentralized Erasure CodesComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.01.00897:C(113-127)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.01.008
Talari ARahnavard N(2016)CStorageAd Hoc Networks10.1016/j.adhoc.2015.09.00937:P2(475-485)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.adhoc.2015.09.009
Li JYe XXu LLiu H(2015)Collecting all data continuously in wireless sensor networks with a mobile base stationInternational Journal of Computational Science and Engineering10.1504/IJCSE.2015.07264711:3(239-248)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1504/IJCSE.2015.072647
Ye XLi JXu L(2014)Distributed Separate Coding for Continuous Data Collection in Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/262965811:1(1-26)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2629658
Aly S(2012)Distributed data collection and storage algorithms for collaborative learning vision sensor devices with applications to pilgrimageInternational Journal of Sensor Networks10.1504/IJSNET.2012.05044912:3(137-148)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1504/IJSNET.2012.050449
Li JYe XJi Y(2011)A novel network coding scheme for data collection in WSNs with a mobile BSProceedings of the 7th international conference on Databases in Networked Information Systems10.1007/978-3-642-25731-5_23(296-311)Online publication date: 12-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25731-5_23
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents