Improving an over-the-air programming protocol for wireless sensor networks based on small world concepts

ABSTRACT

Reprogramming is an important and challenging problem in wireless sensor networks because it is often necessary to in-network sensor processing. Thus, over-the-air programming is a fundamental service that relies upon reliable broadcast for efficient distribution. In this work we use small world features to improve the over-the-air programming. The small world based protocol takes into account the communication workflow of sensor networks to create shortcuts toward the sink, thus improving the reprogramming process. The endpoints of these shortcuts are nodes with more powerful hardware, resulting in a heterogeneous wireless sensor network. We then evaluate the behavior of the small world based protocol regarding the number of transmitted messages, energy consumption and time to reconfigure the network.

REFERENCES

• 1: Akyildiz, I.F.; Weilian Su; Sankarasubramaniam, Y.; Cayirci, E., "A survey on sensor networks," Communications Magazine, IEEE , vol.40, no.8, pp. 102--114, Aug 2002 URL: http://www.ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1024422&isnumber=22021
• 2: A. Boukerche. Algorithms and Protocols for Wireless Sensor Networks. Wiley-IEEE Press, 2008.
• 3: D. Cavalcanti, D. Agrawal, and J. K. D. Sadok. Exploiting the small-world effect to increase connectivity in wireless ad hoc networks. In 11th International Conference on Telecommunications (ICT'04), volume 3124 of Lecture Notes in Computer Science, pages 388--393, Fortaleza, Brazil, August 2004. Springer Berlin/Heidelberg.
• 4: R. Chitradurga and A. Helmy. Analysis of wired short cuts in wireless sensor networks. In IEEE/ACS International Conference on Pervasive Services (ICPS'04), pages 167--176, Beirut, Lebanon, July 2004. IEEE Computer Society.
• 5: I. Crossbow Technology. Mote in-network programming user reference. www.tinyos.net/tinyos-1.x/doc/Xnp.pdf, 2003.
• 6: E. D. C. Group. Sinalgo - simulator for network algorithms. http://dcg.ethz.ch/projects/sinalgo/, 2008.
• 7: D. L. Guidoni, R. A. Mini, and A. A. Loureiro. On the design of heterogeneous sensor networks based on small world concepts. In MSWiM '08: Proceedings of the 11th international symposium on Modeling, analysis and simulation of wireless and mobile systems, pages 309--314, New York, NY, USA, 2008. ACM.
• 8: D. L. Guidoni, R. A. F. Mini, and A. A. F. Loureiro. Creating small-world models in wireless sensor networks. In 19th International Symposium on Personal, Indoor and Mobile Radio Communications. (PIMRC'08), pages 1--6, September 2008.
• 9: P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions on information theory, 46(2):388--404, 2000.
• 10: A. Helmy. Small worlds in wireless networks. IEEE Communications Letters, 7(10):490--492, October 2003.
• 11: J. W. Hui and D. Culler. The dynamic behavior of a data dissemination protocol for network programming at scale. In SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 81--94, New York, NY, USA, 2004. ACM.
• 12: J. Kleinberg. The convergence of social and technological networks. Commun. ACM, 51(11):66--72, 2008.
• 13: S. S. Kulkarni and L. Wang. Mnp: Multihop network reprogramming service for sensor networks. Distributed Computing Systems, International Conference on, 0:7--16, 2005.
• 14: E. F. Nakamura, A. A. F. Loureiro, and A. C. Frery. Information fusion for wireless sensor networks: Methods, models, and classifications. ACM Computing Surveys, 39(3):9/1 - 9/55, April 2007.
• 15: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 16: R. Panta, S. Bagchi, I. Khalil, and L. Montestruque. Single versus multi-hop wireless reprogramming in sensor networks. In TridentCom '08: Proceedings of the 4th International Conference on Testbeds and research infrastructures for the development of networks & communities, pages 1--7, ICST, Brussels, Belgium, Belgium, 2008. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering).
• 17: G. Sharma and R. Mazumdar. A case for hybrid sensor networks. IEEE/ACM Transactions on Networking, 16(5):1121--1132, October 2008.
• 18: T. Stathopoulos, J. Heidemann, and D. Estrin. A remote code update mechanism for wireless sensor networks. Technical report, 2003.
• 19: Q. Wang, Y. Zhu, and L. Cheng. Reprogramming wireless sensor networks: challenges and approaches. IEEE Network, 20(3):48--55, 2006.
• 20: D. J. Watts. A twenty-first century science. Nature, 445(2):489, 2007.
• 21: D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, 393(6684):440--442, 1998.
• 22: M. Yarvis, N. Kushalnagar, H. Singh, A. Rangarajan, Y. Liu, and S. Singh. Exploiting heterogeneity in sensor networks. In Proceedings IEEE INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, volume 2, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms

Keywords:
over-the-air programming, small world, wireless sensor networks