Programming ad-hoc networks of mobile and resource-constrained devices

ABSTRACT

Ad-hoc networks of mobile devices such as smart phones and PDAs represent a new and exciting distributed system architecture. Building distributed applications on such an architecture poses new design challenges in programming models, languages, compilers, and runtime systems. This paper discusses SpatialViews, a high-level language designed for programming mobile devices connected through a wireless ad-hoc network. SpatialViews allows specification of virtual networks with nodes providing desired services and residing in interesting spaces. These nodes are discovered dynamically with user-specified time constraints and quality of result (QoR). The programming model supports "best-effort" semantics, i.e., different executions of the same program may result in "correct" answers of different quality. It is the responsibility of the compiler and runtime system to produce a high-quality answer for the particular network and resource conditions encountered during program execution. Four applications, which exercise different features of the SpatialViews language, are presented to demonstrate the expressiveness of the language and the efficiency of the compiler generated code. The applications are an application that collects and aggregates sensor data in network, an application that performs dynamic service installation, a mobile camera application that supports computation offloading for image understanding, and an augmented-reality (AR) Pacman game. The efficiency of the compiler generated code is verified through simulation and physical measurements. The reported results show that SpatialViews is an expressive and effective language for ad-hoc networks. In addition, compiler optimizations can significantly improve response times and energy consumption.

REFERENCES

• 1: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.186-201, December 12-15, 1999, Charleston, South Carolina, United States
• 2: Eric Allen , David Chase , Victor Luchangco , Jan-Willem Maessen , Guy L. Steele, Jr., Object-oriented units of measurement, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 3: Randy Allen and Ken Kennedy. Optimizing compilers for modern architectures. Morgan Kaufmann, 2001.
• 4: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 5: Brian Blum , Prashant Nagaraddi , Anthony Wood , Tarek Abdelzaher , Sang Son , Jack Stankovic, An entity maintenance and connection service for sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.201-214, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066122]
• 6: Cristian Borcea , Chalermek Intanagonwiwat , Porlin Kang , Ulrich Kremer , Liviu Iftode, Spatial Programming Using Smart Messages: Design and Implementation, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.690-699, March 24-26, 2004
• 7: Athanassios Boulis , Chih-Chieh Han , Mani B. Srivastava, Design and implementation of a framework for efficient and programmable sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.187-200, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066121]
• 8: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 9: William Joseph Butera , V. Michael Bove, Jr., Programming a paintable computer, 2002
• 10: Luca Cardelli, A language with distributed scope, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.286-297, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199516]
• 11: Adrian David Cheok, Siew Wan Fong, Kok Hwee Goh, Xubo Yang, Wei Liu, and Farzam Farbiz. Human pacman:a mobile entertainment system with ubiquitous computing and tangible interaction over a wide outdoor area. In Fifth International Symposium on Human Computer Interaction with Mobile Devices and Services, 2003.
• 12: S. Dashtinezhad, T. Nadeem, B. Dorohonceanu, C. Borcea, P. Kang, and L. Iftode. TrafficView: A driver assistant device for traffic monitoring based on car-to-car communication. In IEEE Semiannual Vehicular Technology, Milan, Italy, May 2004.
• 13: eDonkey. homepage. http://www.edonkey2000.com.
• 14: 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
• 15: Robert S. Gray , George Cybenko, Agent tcl: a flexible and secure mobile-agent system, 1998
• 16: Robert S. Gray , George Cybenko , David Kotz , Ronald A. Peterson , Daniela Rus, D'Agents: applications and performance of a mobile-agent system, Software—Practice & Experience, v.32 n.6, p.543-573, May 2002 [doi>10.1002/spe.449]
• 17: 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
• 18: Qingfeng Huang , Chenyang Lu , Gruia-Catalin Roman, Spatiotemporal multicast in 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.958516]
• 19: The IEEE Mobile Ad-hoc Networks (manet) Working Group. homepage. http://www.ietf.org/html.charters/manet-charter.html.
• 20: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.77-93, November 08-11, 1987, Austin, Texas, United States
• 21: David B Johnson and David A Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 22: P. Kang, C. Borcea, G. Xu, A. Saxena, U. Kremer, and L. Iftode. Smart messages: A distributed computing platform for networks of embedded systems. The Computer Journal, Special Issue on Mobile and Pervasive Computing, 47(4), January 2004.
• 23: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 24: Kazaa. homepage. http://www.kazaa.com.
• 25: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 26: U. Kremer, Y. Ni, and A. Stere. Spatial Views language specification, version 1.0. Technical Report DCS-TR-563, Department of Computer Science, Rutgers University, November 2004.
• 27: Danny B. Lange , Oshima Mitsuru, Programming and Deploying Java Mobile Agents Aglets, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 28: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 29: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 30: Ting Liu , Margaret Martonosi, Impala: a middleware system for managing autonomic, parallel sensor systems, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 31: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 32: Mutella. homepage. http://mutella.sourceforge.net.
• 33: Radhika Nagpal, Programmable self-assembly using biologically-inspired multiagent control, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544839]
• 34: Julio C. Navas , Tomasz Imielinski, GeoCast—geographic addressing and routing, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.66-76, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262132]
• 35: Yang Ni, Ulrich Kremer, and Liviu Iftode. Spatial Views: Space-aware programming for networks of embedded systems. In The 16th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2003), October 2003.
• 36: Yang Ni , Ulrich Kremer , Liviu Iftode, A programming language for ad-hoc networks of mobile devices, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-12, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066662]
• 37: Pac-Manhattan. homepage. http://pacmanhattan.com.
• 38: Charles. E. Perkins. Ad hoc networking. Addison-Wesley, 2001.
• 39: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 40: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 41: Sun Microsystems, Inc. Java 2 Platform, Micro Edition (J2ME). http://java.sun.com/j2me.
• 42: Sun Microsystems, Inc. The K virtual machine. a white paper available at http://java.sun.com/products/cldc/wp/.
• 43: Jim Waldo, The Jini architecture for network-centric computing, Communications of the ACM, v.42 n.7, p.76-82, July 1999 [doi>10.1145/306549.306582]
• 44: Matt Welsh and Geoff Mainland. Programming sensor networks using abstract regions. In NSDI 2004, March 2004.
• 45: D. Wetheral. Lessons from a Capsule-based system. In SOSP, 1999.
• 46: James E. White. Telescript technology: mobile agents, 1996. General Magic, Inc. White Paper.
• 47: 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]
• 48: Gang Xu, Cristian Borcea, and Liviu Iftode. Toward a security architecture for smart messages: Challenges, solutions, and open issues. In Proceedings of the First International Workshop on Mobile Distributed Computing, May 2003.
• 49: Peng Zhou , Tamer Nadeem , Porlin Kang , Cristian Borcea , Liviu Iftode, EZCab: A Cab Booking Application Using Short-Range Wireless Communication, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.27-38, March 08-12, 2005 [doi>10.1109/PERCOM.2005.21]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

General Terms:
Design, Languages

Keywords:
MANET, ad-hoc networks, location-awareness, quality of result, service discovery