Abhinav Kamra
Jon Feldman
Abstract
Sensor networks are especially useful in catastrophic or emergency scenarios such as floods, fires, terrorist attacks or earthquakes where human participation may be too dangerous. However, such disaster scenarios pose an interesting design challenge since the sensor nodes used to collect and communicate data may themselves fail suddenly and unpredictably, resulting in the loss of valuable data. Furthermore, because these networks are often expected to be deployed in response to a disaster, or because of sudden configuration changes due to failure, these networks are often expected to operate in a "zero-configuration" paradigm, where data collection and transmission must be initiated immediately, before the nodes have a chance to assess the current network topology. In this paper, we design and analyze techniques to increase "persistence" of sensed data, so that data is more likely to reach a data sink, even as network nodes fail. This is done by replicating data compactly at neighboring nodes using novel "Growth Codes" that increase in efficiency as data accumulates at the sink. We show that Growth Codes preserve more data in the presence of node failures than previously proposed erasure resilient techniques.
- Crossbow micaz motes.Google Scholar
- TinyOS Homepage.Google Scholar
- S. Katti, D. Katabi, W. Hu, H. Rahul and M. Medard. The Importance of Being Opportunistic: Practical Network Coding For Wireless Environments. In Allerton Annual Conference on Communication, Control and Computing, 2005.Google Scholar
- A. Albanese, J. Blömer, J. Edmonds, M. Luby, M. Sudan. Priority Encoding Transmission. In IEEE Transactions on Information Theory, volume 42, 1996. Google ScholarDigital Library
- A. G. Dimakis, V. Prabhakaran and K. Ramchandran. Ubiquitous Acess to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes. In Information Processing in Sensor Networks, 2005. Google ScholarDigital Library
- A. Kamra, J. Feldman, V. Misra and D. Rubenstein. Data Persistence for Zero-Configuration Sensor Networks. In Technical Report, Department of Computer Science, Columbia University, Feb. 2006.Google Scholar
- A. Manjeshwar and D.P. Agrawal. Teen: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. In Parallel and Distributed Processing Symposium, 2001. Google ScholarDigital Library
- A. Scaglione and S. D. Servetto. On the interdependence of routing and data compression in multi-hop sensor networks. In ACM Conference on Mobile Computing and Networking, 2002. Google ScholarDigital Library
- C. Gkantsidis and P. Rodriguez. Network Coding for Large Scale Content Distribution. In Proceedings of INFOCOM, 2005.Google ScholarCross Ref
- C. Intanagonwiwat, R. Govindan and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In ACM Conference on Mobile Computing and Networking, 2000. Google ScholarDigital Library
- C. Y. Wan, S. B. Eisenman, A. T. Campbell, J. Crowcroft. Siphon: Overload Traffic Management using Multi-Radio Virtual Sinks. In ACM Conference on Embedded Networked Sensor Systems, 2005. Google ScholarDigital Library
- D. Marco, D. Neuhoff. Reliability vs. Efficiency in Distributed Source Coding for Field-Gathering. In Information Processing in Sensor Networks, 2004. Google ScholarDigital Library
- I. F. Akyildiz, M. C. Vuran, O. B. Akan. On Exploiting Spatial and Temporal Correlation in Wireless Sensor Networks. In Proceedings of WiOpt 2004: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pages 71--80, Mar. 2004.Google Scholar
- J. Byers, J. Considine, M. Mitzenmacher and S. Rost. Informed Content Delivery Across Adaptive Overlay Networks. In Proceedings of SIGCOMM, 2002. Google ScholarDigital Library
- J. Considine. Generating good degree distributions for sparse parity check codes using oracles. In Technical Report, BUCS-TR 2001-019, Boston University, 2001.Google Scholar
- J. W. Byers, M. Luby, M. Mitzenmacher, A. Rege. A Digital Fountain Approach to Reliable Distribution of Bulk Data. In Proceedings of SIGCOMM, 1998. Google ScholarDigital Library
- Lin and Costello. Error Control Coding: Fundamentals and Applications. 1983.Google Scholar
- M. Luby. LT Codes. In Symposium on Foundations of Computer Science, 2002. Google ScholarDigital Library
- M. Li, D. Ganesan and P. Shenoy. PRESTO: Feedback-Driven Data Management in Sensor Networks. In ACM/USENIX Symposium on Networked Systems Design and Implementation, 2006. Google ScholarDigital Library
- M. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. Spielman. Efficient Erasure Correcting Codes. In IEEE Transactions on Information Theory, volume 47, pages 569--584, 2001. Google ScholarDigital Library
- M. O. Rabin. Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance. In Journal of the ACM, volume 36, pages 335--348, 1989. Google ScholarDigital Library
- M. Perillo, Z. Ignjatovic and W. Heinzelman. An Energy Conservation Method for Wireless Sensor Networks Employing a Blue Noise Spatial Sampling Technique. In Information Processing in Sensor Networks, pages 116--123, 2003. Google ScholarDigital Library
- M. Sartipi and F. Fekri. Source and Channel Coding in Wireless Sensor Networks using LDPC Codes. In EEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004.Google ScholarCross Ref
- N. Cai, S. Y. R. Li and R. W. Yeung. Linear Network Coding. In IEEE Transactions on Information Theory, volume 49, pages 371--381, 2003. Google ScholarDigital Library
- P. Desnoyers, D. Ganesan and P. Shenoy. TSAR: A Two Tier Storage Architecture Using Interval Skip Graphs. In ACM Conference on Embedded Networked Sensor Systems, 2005. Google ScholarDigital Library
- P. J. M. Havinga, G. J. M. Smit and M. Bos. Energy Efficient Adaptive Wireless Network Design. In The Fifth Symposium on Computers and Communications, 2000. Google ScholarDigital Library
- R. Ahlswede, N. Cai, S. Y. R. Li and R. W. Yeung. Network Information Flow. In IEEE Transactions on Information Theory, volume 46, pages 1004--1016, 2000. Google ScholarDigital Library
- R. Chandra, C. Fetzer and K. Hogstedt. A Mesh-based Robust Topology Discovery Algorithm for Hybrid Wireless Networks. In Proceedings of AD-HOC Networks and Wireless, Sept. 2002.Google Scholar
- R. Koetter and M. Medard. An Algebraic Approach to Network Coding. In ACM/IEEE Transactions on Networking, volume 11, pages 782--795, 2003. Google ScholarDigital Library
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge International Series on Parallel Computation. Google ScholarDigital Library
- S. Acedanski, S. Deb, M. Medard and R. Koetter. How Good is Random Linear Coding Based Distributed Networked Storage. In Workshop on Network Coding, Theory and Applications, 2005.Google Scholar
- S. Pattem, B. Krishnamachari and R. Govindan. The Impact of Spatial Correlation on Routing with Compression in Wireless Sensor Networks. In Information Processing in Sensor Networks, pages 28--35, 2004. Google ScholarDigital Library
- S. S. Pradhan, J. Kusuma and K. Ramchandran. Distributed compression in a dense microsensor network. In IEEE Signal Processing Magazine, volume 19, pages 51--60, Mar. 2002.Google Scholar
- T. Arici, B. Gedik, Y. Altunbasak and L. Liu. PINCO: a Pipelined In-Network COmpression Scheme for Data Collection in Wireless Sensor Networks. In International Conference on Computer Communications and Networks, 2003.Google ScholarCross Ref
- T. Ho, M. Médard, M. Effros and D. Karger. On Randomized Network Coding. In Allerton Annual Conference on Communication, Control and Computing, Oct. 2003.Google Scholar
- W. Heinzelman, A. Chandrakasan and H. Balakrishnan. Energy-Efficient Communication Protocols for Wireless Microsensor Networks. In Hawaii International Conference on Systems Sciences, 2000. Google ScholarDigital Library
Index Terms
- Growth codes: maximizing sensor network data persistence
Recommendations
Growth codes: maximizing sensor network data persistence
SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsSensor networks are especially useful in catastrophic or emergency scenarios such as floods, fires, terrorist attacks or earthquakes where human participation may be too dangerous. However, such disaster scenarios pose an interesting design challenge ...
Key pre-distribution schemes to support various architectural deployment models in WSN
The tremendous applications of wireless sensor technology for day to day activities are rapidly increasing. They have the ability to make the environment smart and prolific. As vulnerabilities on wireless sensor networks are increasing, ensuring secure ...
Maximizing growth codes utility in large-scale wireless sensor networks
Euro-Par'10: Proceedings of the 16th international Euro-Par conference on Parallel processing: Part IIThe goal of Growth Codes proposed by Karma et.al. is to increase the "persistence" of sensed data, so as to promise that data is more likely to reach a data sink. In many "zero-configuration" sensor networks, where the network topology would change very ...
Comments