Algorithms for generic role assignment in wireless sensor networks

ABSTRACT

We consider configuration of wireless sensor networks, where certain functions must be automatically assigned to sensor nodes, such that the properties of a sensor node (e.g., remaining energy, network neighbors) match the requirements of the assigned function. Essentially, sensor nodes take on certain roles in the network as a result of configuration. To help developers with such configuration tasks for a variety of applications, we propose generic role assignment as a programming abstraction, where roles and rules for their assignment can be easily specified using a configuration language. We present such a role specification language and distributed algorithms for role assignment according to such specifications. We evaluate our approach and show that efficient and robust generic role assignment is practically feasible for wireless sensor networks.

REFERENCES

• 1: T. Abdelzaher , B. Blum , Q. Cao , Y. Chen , D. Evans , J. George , S. George , L. Gu , T. He , S. Krishnamurthy , L. Luo , S. Son , J. Stankovic , R. Stoleru , A. Wood, EnviroTrack: Towards an Environmental Computing Paradigm for Distributed Sensor Networks, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.582-589, March 24-26, 2004
• 2: Harold Abelson , Don Allen , Daniel Coore , Chris Hanson , George Homsy , Thomas F. Knight, Jr. , Radhika Nagpal , Erik Rauch , Gerald Jay Sussman , Ron Weiss, Amorphous computing, Communications of the ACM, v.43 n.5, p.74-82, May 2000 [doi>10.1145/332833.332842]
• 3: Rimon Barr , Zygmunt J. Haas, An efficient, unifying approach to simulation using virtual machines, 2004
• 4: B. Bonfils and P. Bonnet. Adaptive and decentralized operator placement for in-network query processing. In IPSN'04, Berkeley, USA, April 2003.
• 5: SmartRF CC1000 Datasheet (rev. 2.2). Chipcon AS, April 2004. www.chipcon.com/files/CC1000_Data_Sheet_2_2.pdf.
• 6: W. B. Heinzelman, A. L. Murphy, H. S. Carvalho, and M. A. Perillo. Middleware to Support Sensor Network Applications. IEEE Network, 18(1):6--14, Jan-Feb 2004.
• 7: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 8: 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]
• 9: Holger Karl , Andreas Willig, Protocols and Architectures for Wireless Sensor Networks, John Wiley & Sons, 2005
• 10: Manish Kochhal , Loren Schwiebert , Sandeep Gupta, Role-based hierarchical self organization for wireless ad hoc sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941364]
• 11: Taek Jin Kwon , Mario Gerla, Efficient flooding with Passive Clustering (PC) in ad hoc networks, ACM SIGCOMM Computer Communication Review, v.32 n.1, p.44-56, January 2002 [doi>10.1145/510726.510730]
• 12: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In NSDI'04, San Francisco, USA, March 2004.
• 13: P. J. Marrón, A. Lachenmann, D. Minder, J. Hähner, R. Sauter, and K. Rothermel. Tinycubus: A flexible and adaptive framework for sensor networks. In EWSN'05, Istanbul, Turkey, January 2005.
• 14: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 15: K. Römer, C. Frank, P. J. Marrón, and C. Becker. Generic role assignment for wireless sensor networks. In 11th ACM SIGOPS European Workshop, pages 7--12, Leuven, Belgium, September 2004.
• 16: S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In ICC'01, Helsinki, Finland, June 2001.
• 17: K. Sohrabi, V. Ailawadhi, J. Gao, and G. Pottie. Protocols for Self Organization of a Wireless Sensor Network. Personal Communication Magazine, 7:16--27, 2000.
• 18: Lakshminarayanan Subramanian , Randy H. Katz, An architecture for building self-configurable systems, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 19: D. Tian and N. D. Georganas. A node scheduling scheme for energy conservation in large wireless sensor networks. Wireless Communications and Mobile Computing, 3(2):271--290, 2003.
• 20: A. Ulbrich, T. Weis, G. Mühl, and K. Geihs. Application Development for Actuator and Sensor Networks. In GI Workshop on Sensor Networks, ETH Zurich, Switzerland, March 2005.
• 21: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958512]
• 22: M. Welsh and G. Mainland. Programming sensor networks using abstract regions. In NSDI'04, San Francisco, USA, March 2004.
• 23: G. Werner-Allen, J. Johnson, M. Ruiz, J. Lees, and M. Welsh. Monitoring volcanic eruptions with a wireless sensor network. In EWSN'05, Istanbul, Turkey, January 2005.
• 24: Kamin Whitehouse , Cory Sharp , Eric Brewer , David Culler, Hood: a neighborhood abstraction for sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990079]
• 25: S. Wolfram. Cellular Automata and Complexity. Addison-Wesley, 1994.
• 26: 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]
• 27: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 28: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. In INFOCOM'02, New York, USA, June 2002.
• 29: BTnodes. www.btnode.ethz.ch.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.m Miscellaneous

General Terms:
Algorithms, Languages, Performance

Keywords:
configuration, programming, sensor networks