Training a wireless sensor network

ABSTRACT

The networks considered in this paper consist of tiny energy-constrained commodity sensors massively deployed, along with one or more sink nodes providing interface to the outside world. Our contribution is to propose a scalable energy-efficient training protocol for nodes that are initially anonymous, asynchronous and unaware of their location. Our training protocol imposes a flexible and intuitive coordinate system onto the deployment area and partitions the anonymous nodes into clusters where data can be gathered from the environment and synthesized under local control. An important by-product of the training protocol is a simple and natural data fusion protocol as well as an energy-efficient protocol for routing data from clusters to the sink node. Being energy-efficient, our training protocol can be run on either a scheduled or ad-hoc basis to provide robustness and dynamic reconfiguration. We also outline a way of making the training protocol secure by using a parameterized variant of frequency hopping.

REFERENCES

• 1: Jon Agre , Loren Clare, An Integrated Architecture for Cooperative Sensing Networks, Computer, v.33 n.5, p.106-108, May 2000 [doi>10.1109/2.841788]
• 2: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 3: Ross J. Anderson, Security Engineering: A Guide to Building Dependable Distributed Systems, John Wiley & Sons, Inc., New York, NY, 2001
• 4: {4} R. Anderson and M. Kuhn, Tamper resistance - a cautionary note, in: Proc. 2nd USENIX Workshop on Electronic Commerce, Berkeley, CA (1996), pp. 1-11. IEEE Wireless Communications 9(1) (2002) 40-48.
• 5: {5} S. Bandyopadhyay and E. Coyle, An efficient hierarchical clustering algorithm for wireless sensor networks, in: Proc. INFOCOM'2003, San Francisco, CA (April 2003).
• 6: {6} D. Braginsky and D. Estrin, Rumor routing algorithm for sensor networks, in: Proc. Internat. Conf. on Distributed Computing Systems (ICDCS-22) (November 2001).
• 7: {7} N. Bulusu, J. Heidemann and D. Estrin, GPS-less low cost outdoor localization for very small devices, IEEE Personal Communications 7(5) (2000) 28-34.
• 8: {8} N. Bulusu, J. Heidemann and D. Estrin, Scalable coordination for wireless sensor networks: self-configuration localization systems, in: Proc. 6th Internat. Sympos. on Communication Theory and Applications (ISCTA-2001) (July 2001).
• 9: Srdjan Čapkun , Maher Hamdi , Jean-Pierre Hubaux, GPS-free Positioning in Mobile Ad Hoc Networks, Cluster Computing, v.5 n.2, p.157-167, April 2002 [doi>10.1023/A:1013933626682]
• 10: {10} D.W. Carman, P.S. Kruus and B.J. Matt, Constraints and approaches for distributed sensor network security, Technical Report 00-010, NAI Labs (2000).
• 11: Daniel Coore , Radhika Nagpal , Ron Weiss, Paradigms for Structure in an Amorphous Computer, Massachusetts Institute of Technology, Cambridge, MA, 1997
• 12: {12} L. Doherty, H.S.J. Pister and L.E. Ghaoui, Convex position estimation in wireless sensor networks, in: Proc. INFOCOM'2001, Anchorage, AK (April 2001).
• 13: {13} A. Ephremides, J. Wieselthier and D. Baker, A design concept for reliable mobile radio networks with frequency hopping signaling, Proceedings of the IEEE 75(1) (1987) 56-73.
• 14: Deepak Ganesan , Ramesh Govindan , Scott Shenker , Deborah Estrin, Highly-resilient, energy-efficient multipath routing in wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.4, October 2001 [doi>10.1145/509506.509514]
• 15: {15} S. Ghiasi, A. Srivastava, X. Yang and M. Sarrafzadeh, Optimal energyaware clustering in sensor networks, Sensors 2 (2002) 258-269.
• 16: Locating Tiny Sensors in Time and Space: A Case Study, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.214, September 16-18, 2002
• 17: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 18: {18} http://www.darpa.mil/mto/mems/
• 19: {19} http://www.stanford.edu/class/ee321/ho/MEMS-14sensors.pdf
• 20: {20} http://www.xs4all.nl/~ganswijk/chipdir/m/sensor. htm
• 21: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 22: K. Jones , A. Wadaa , S. Olariu , L. Wilson , M. Eltoweissy, Towards a new paradigm for securing wireless sensor networks, Proceedings of the 2003 workshop on New security paradigms, August 18-21, 2003, Ascona, Switzerland [doi>10.1145/986655.986672]
• 23: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 24: Joanna Kulik , Wendi Heinzelman , Hari Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, v.8 n.2/3, p.169-185, March-May 2002 [doi>10.1023/A:1013715909417]
• 25: {25} K. Langendoen and N. Reijers, Distributed localization in wireless sensor networks, a quantitative comparison, Manuscript (May 2003).
• 26: Koji Nakano , Stephan Olariu, Randomized initialization protocols for radio networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 27: Koji Nikano , Stephan Olariu, Uniform Leader Election Protocols for Radio Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.5, p.516-526, May 2002 [doi>10.1109/TPDS.2002.1003864]
• 28: National Research Council Staff, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Academy Press, Washington, DC, 2001
• 29: {29} D. Niculescu and B. Nath, Ad-hoc positioning system, in: Proc. IEEE GLOBECOM, San Antonio, TX (November 2001) pp. 2926-2931.
• 30: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 31: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 32: Paul Saffo, Sensors: the next wave of innovation, Communications of the ACM, v.40 n.2, p.92-97, Feb. 1997 [doi>10.1145/253671.253734]
• 33: Chris Savarese , Jan M. Rabaey , Koen Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.317-327, June 10-15, 2002
• 34: {34} R.C. Shah and J. Rabaey, Energy aware routing for low energy ad hoc sensor networks, in: Proc. IEEE WCNC, Orlando, FL (March 2002).
• 35: {35} C.-C. Shen, C. Srisathapornphat and C. Jaikaeo, Sensor information networking architecture and applications, IEEE Personal Communications (August 2001) 52-59.
• 36: Eugene Shih , Seong-Hwan Cho , Nathan Ickes , Rex Min , Amit Sinha , Alice Wang , Anantha Chandrakasan, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.272-287, July 2001, Rome, Italy [doi>10.1145/381677.381703]
• 37: {37} K. Sohrabi, J. Gao, V. Ailawadhi and G. Pottie, Protocols for selforganization of a wireless sensor network, IEEE Personal Communications (October 2000) 16-27.
• 38: Sameer Tilak , Nael B. Abu-Ghazaleh , Wendi Heinzelman, A taxonomy of wireless micro-sensor network models, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.2, p.28-36, April 2002 [doi>10.1145/565702.565708]
• 39: {39} A. Wadaa, S. Olariu, L. Wilson, K. Jones and Q. Xu, On training wireless sensor networks, in: Proc. 3rd International Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN'03), Nice, France (April 2003).
• 40: Brett Warneke , Matt Last , Brian Liebowitz , Kristofer S. J. Pister, Smart Dust: Communicating with a Cubic-Millimeter Computer, Computer, v.34 n.1, p.44-51, January 2001 [doi>10.1109/2.963443]
• 41: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 42: Anthony D. Wood , John A. Stankovic, Denial of Service in Sensor Networks, Computer, v.35 n.10, p.54-62, October 2002 [doi>10.1109/MC.2002.1039518]
• 43: {43} W. Ye, J. Heidemann and D. Estrin, An energy-efficient MAC protocol for wireless sensor networks, in: Proc. INFOCOM 2002, New York (June 2002).
• 44: Victor V. Zhirnov , Daniel J. C. Herr, New Frontiers: Self-Assembly and Nanoelectronics, Computer, v.34 n.1, p.34-43, January 2001
• 45: {45} J. Zyren, T. Godfrey and D. Eaton, Does frequency hopping enhance security? http://www.packetnexus.com/docs/ 20010419frequency_Hopping.pdf

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Performance

Keywords:
clustering, dynamic coordinate system, energy-efficient protocols, security, self-organization, training, wireless sensor networks