SenseCode: Network coding for reliable sensor networks

Abstract

Designing a communication protocol for sensor networks often involves obtaining the right trade-off between energy efficiency and end-to-end packet error rate. In this article, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks—and, to the best of our knowledge, the first such implemented protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information into the network, thereby decreasing end-to-end packet error rate in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it reduces end-to-end packet error rate in highly dynamic environments, while consuming a comparable amount of network resources. We have implemented SenseCode as a TinyOS module and evaluate it through extensive TOSSIM simulations.

References

1. Adjih, C., Cho, S. Y., and Jacquet, P. 2007. Near optimal broadcast with network coding in large sensor networks. CoRR abs/0708.0975.
2. Ahlswede, R., Cai, N., Li, S.-Y. R., and Yeung, R. W. 2000. Network information flow. IEEE Trans. Inf. Theory 46, 4, 1204--1216.
3. Biswas, S. and Morris, R. 2005. ExOR: opportunistic multi-hop routing for wireless networks. SIGCOMM Comput. Comm. Rev. 35, 4, 133--144.
4. Chachulski, S., Jennings, M., Katti, S., and Katabi, D. 2007. Trading structure for randomness in wireless opportunistic routing. SIGCOMM Comput. Comm. Rev. 37, 4, 169--180.
5. Chou, P. A., Wu, Y., and Jain, K. 2003. Practical network coding. In Proceedings of the 42th Allerton Conference on Communication, Control, and Computing.
6. De, S., Qiao, C., and Wu, H. 2003. Meshed multipath routing with selective forwarding: An efficient strategy in sensor networks. Comput. Netw. 43, 4, 481--497.
7. Dimakis, A. G., Prabhakaran, V., and Ramchandran, K. 2005. Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. 111--117.
8. Fragouli, C., Widmer, J., And Le Boudec, J.-Y. 2006. Network coding: An instant primer. ACM SIGCOMM Comput. Comm. Rev. 36, 1, 63--68.
9. Ganesan, D., Govindan, R., Shenker, S., and Estrin, D. 2001. Highly-resilient, energy-efficient multipath routing for wireless sensor networks. ACM SIGMOBILE Mobile Comput. Comm. Rev. 5, 4, 11--25.
10. Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and Levis, P. 2009. Collection tree protocol. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. 1--14.
11. Guo, Z., Xie, P., Cui, J.-H., and Wang, B. 2006. On applying network coding to underwater sensor networks. In Proceedings of the 1st ACM International Workshop on Underwater Networks. 109--112.
12. Ho, T. and Lun, D. S. 2008. Network Coding: An Introduction. Cambridge University Press, Cambridge, U.K.
13. Horn, R. A. and Johnson, C. R. 1990. Matrix Analysis. Cambridge University Press, Cambridge, U.K.
14. Jafarisiavoshani, M., Keller, L., Fragouli, C., and Argyraki, K. 2009. Compressed network coding vectors. In Proceedings of the IEEE International Symposium on Information Theory. 109--113.
15. Kamra, A., Misra, V., Feldman, J., and Rubenstein, D. 2006. Growth codes: Maximizing sensor network data persistence. ACM SIGCOMM Comput. Commun. Rev. 36, 4, 255--266.
16. Karande, S., Misra, K., and Radha, H. 2008. Natural growth codes: Partial recovery under random network coding. In Proceedings of the 42nd Annual Conference on Information Sciences and Systems. 540--544.
17. Katti, S., Katabi, D., Balakrishnan, H., and Medard, M. 2008. Symbol-level network coding for wireless mesh networks. SIGCOMM Comput. Comm. Rev. 38, 4, 401--412.
18. Koetter, R. and Kschischang, F. R. 2008. Coding for errors and erasures in random network coding. IEEE Trans. Inform. Theory 54, 8, 3579--3591.
19. Le Boudec, J.-Y. 2010. Performance Evaluation of Computer and Communication Systems. EPFL Press, Lausanne, Switzerland.
20. Lee, H. J., Cerpa, A., and Levis, P. 2007. Improving wireless simulation through noise modeling. In Proceedings of the 6th International Symposium on Information Processing in Sensor Networks. 21--30.
21. Levis, P., Lee, N., Welsh, M., and Culler, D. 2003. Tossim: Accurate and scalable simulation of entire TinyOS applications. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. 126--137.
22. Levis, P., Madden, S., Polastre, J., Szewczyk, R., Whitehouse, K., Woo, A., Gay, D., Hill, J., Welsh, M., Brewer, E., and Culler, D. 2005. TinyOS: An operating system for sensor networks. In Ambient Intelligence, W. Werner, J. M. Rabaey, and E. Aarts, Eds, vol. 35, Springer, Berlin, 115--148.
23. Li, S.-Y., R., Yeung, R. W., and Cai, N. 2003. Linear network coding. IEEE Trans. Inf. Theory 49, 2, 371--381
24. Li, Z. and Li, B. 2006. Improving throughput in multihop wireless networks. IEEE Trans. Veh. Technol. 55, 3, 762--773.
25. MacWilliams, F. J. and Sloane, N. J. A. 1983. The Theory Of Error Correcting Codes. North Holland, Amsterdam, Netherlands.
26. Nath, S., Gibbons, P. B., Seshan, S., and Anderson, Z. 2008. Synopsis diffusion for robust aggregation in sensor networks. ACM Trans. Sen. Netw. 4, 2, 1--40.
27. Petrović, D., Ramchandran, K., and Rabaey, J. 2006. Overcoming untuned radios in wireless sensor networks with network coding. IEEE/ACM Trans. Networking 14, SI, 2649--2657.
28. Pottié, G. and Kaiser, W. 2000. Wireless integrated network. sensors. Comm. ACM 43, 5, 51--58.
29. Pottie, G. and Kaiser, W. 2005. Principles Of Embedded Networked Systems. Cambridge University Press, Cambridge, U.K.
30. Sartipi, M. and Fekri, F. 2004. Source and channel coding in wireless sensor networks using idpc codes. In Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks. 309--316.
31. Silva, D. and Kschichang, F. R. 2007. Using rank-metric codes for error correction in random network coding. In Proceedings of the IEEE International Symposium on Information Theory. 796--800.
32. Texas Insruments. 2007. CC2420 RF Transceiver Datasheet. http://www.ti.com/lit/gpn/cc2420.
33. Toledo, A. L. and Wang, X. 2006. Efficient multipath in sensor networks using diffusion and network coding. In Proceedings of the 40th Annual Conference on Conference on Information Sciences and Systems. 87--92.
34. Wood, A. and Stankovic, J. 2008. Rateless erasure codes for bulk transfer in asymmetric wireless sensor networks. In Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems. 449--450.
35. Wu, Y., Chou, P. A., and Kung, S. Y. 2005. Minimum-energy multicast in mobile ad-hoc networks using network coding. IEEE Trans. Comm. 53, 11, 1906--1918.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

• Networks

  • Network protocols

    • Network protocol design