Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications

ABSTRACT

We present Disco, an asynchronous neighbor discovery and rendezvous protocol that allows two or more nodes to operate their radios at low duty cycles (e.g. 1%) and yet still discover and communicate with one another during infrequent, opportunistic encounters without requiring any prior synchronization information. The key challenge is to operate the radio at a low duty cycle but still ensure that discovery is fast, reliable, and predictable over a range of operating conditions. Disco nodes pick a pair of prime numbers such that the sum of their reciprocals is equal to the desired radio duty cycle. Each node increments a local counter with a globallyfixed period. If a node's local counter value is divisible by either of its primes, then the node turns on its radio for one period. This protocol ensures that two nodes will have some overlapping radio on-time within a bounded number of periods, even if nodes independently set their own duty cycle. Once a neighbor is discovered, and its wakeup schedule known, rendezvous is just a matter of being awake during the neighbor's next wakeup period,for synchronous rendezvous, or during an overlapping wake period, for asynchronous rendezvous.

REFERENCES

• 1: G. Borriello, W. Brunette, M. Hall, C. Hartung, and C. Tangney. Reminding about tagged objects using passive rfids. In Ubicomp, pages 36--53, 2004.
• 2: Michael Buettner , Gary V. Yee , Eric Anderson , Richard Han, X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182838]
• 3: Kameswari Chebrolu , Bhaskaran Raman , Nilesh Mishra , Phani Kumar Valiveti , Raj Kumar, Brimon: a sensor network system for railway bridge monitoring, Proceeding of the 6th international conference on Mobile systems, applications, and services, June 17-20, 2008, Breckenridge, CO, USA [doi>10.1145/1378600.1378603]
• 4: Tanzeem Khalid Choudhury , Alex P. Pentland, Sensing and modeling human networks, Massachusetts Institute of Technology, 2004
• 5: P. Dutta, D. Culler, and S. Shenker. Procrastination Might Lead to a Longer and More Useful Life. In The 6th Workshop on Hot Topics in Networks (HotNets VI), 2007.
• 6: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 7: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless 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.990096]
• 8: T. Herman, S. V. Pemmaraju, L. Pilard, and M. Mjelde. Temporal partition in sensor networks. In SSS'07: 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 325--339, 2007.
• 9: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 10: Jyh-How Huang , Saqib Amjad , Shivakant Mishra, CenWits: a sensor-based loosely coupled search and rescue system using witnesses, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098938]
• 11: Jehn-Ruey Jiang , Yu-Chee Tseng , Chih-Shun Hsu , Ten-Hwang Lai, Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.169-181, February 2005 [doi>10.1145/1046430.1046443]
• 12: J. Leguay, T. Friedman, and V. Conan. Evaluating mobility pattern space routing. In INFOCOM'06: Proceedings of the 25th IEEE Conference on Computer Communications, 2006.
• 13: Y. Li, W. Ye, and J. Heidemann. Energy and latency control in low duty cycle MAC protocols. In IEEE WCNC'05: Proceedings of the IEEE Wireless Communications and Networking Conference, 2005.
• 14: Ting Liu , Christopher M. Sadler , Pei Zhang , Margaret Martonosi, Implementing software on resource-constrained mobile sensors: experiences with Impala and ZebraNet, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990095]
• 15: Mateusz Malinowski , Matthew Moskwa , Mark Feldmeier , Mathew Laibowitz , Joseph A. Paradiso, CargoNet: a low-cost micropower sensor node exploiting quasi-passive wakeup for adaptive asychronous monitoring of exceptional events, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322278]
• 16: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 17: Michael J. McGlynn , Steven A. Borbash, Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501435]
• 18: I. Niven, H. S. Zuckerman, and H. L. Mongomery. An Introduction to the Theory of Numbers. John Wiley & Sons, 1991.
• 19: S. Patel, K. Lorincz, R. Hughes, N. Huggins, J. H. Growdon, M. Welsh, and P. Bonato. Analysis of feature space for monitoring persons with parkinson's disease with application to a wireless wearable sensor system. In Proceedings of the 29th IEEE EMBS Annual International Conference, Aug. 2007.
• 20: 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]
• 21: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 22: Hoi-Sheung Wilson So , Giang Nguyen , Jean Walrand, Practical synchronization techniques for multi-channel MAC, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161105]
• 23: Jacob Sorber , Alexander Kostadinov , Matthew Garber , Matthew Brennan , Mark D. Corner , Emery D. Berger, Eon: a language and runtime system for perpetual systems, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322279]
• 24: Jay Taneja , Jaein Jeong , David Culler, Design, Modeling, and Capacity Planning for Micro-solar Power Sensor Networks, Proceedings of the 7th international conference on Information processing in sensor networks, p.407-418, April 22-24, 2008 [doi>10.1109/IPSN.2008.67]
• 25: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]
• 26: Y.-C. Tseng, C.-S. Hsu, and T.-Y. Hsieh. Power-saving protocols for IEEE 802.11-based multi-hop ad hoc networks. In INFOCOM'02: Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Comm. Soc., 2002.
• 27: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 28: Tim Wark , Wen Hu , Pavan Sikka , Lasse Klingbeil , Peter Corke , Chris Crossman , Greg Bishop-Hurley, A model-based routing protocol for a mobile, delay tolerant network, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322326]
• 29: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. In INFOCOM'02: Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies, June 2002.
• 30: Rong Zheng , Jennifer C. Hou , Lui Sha, Asynchronous wakeup for ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778420]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
neighbor discovery, protocol, rendezvous, wireless