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. W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, and J. Lilley. The design and implementation of an intentional naming system. In SOSP, 1999.]]
2. Eric Allen, David Chase, Victor Luchangco, Jan-Willem Maessen, and Guy L. Steele Jr. Object-oriented units of measurement. In OOPSLA, Vancouver, British Columbia, Canada, October 2004.]]
3. Randy Allen and Ken Kennedy. Optimizing compilers for modern architectures. Morgan Kaufmann, 2001.]]
4. T.E. Anderson, D. E. Culler, and D. A. Patterson. A case for networks of workstations: NOW. IEEE Micro, 15(1):54--64, February 1995.]]
5. Brian Blum, Prashant Nagaraddi, Anthony Wood, Tarek Abdelzaher, Sang Son, and Jack Stankovic. An entity maintenance and connection service for sensor networks. In MobiSys, 2003.]]
6. C. Borcea, C. Intanagonwiwat, P. Kang, U. Kremer, and L. Iftode. Spatial programming using Smart Messages: Design and implementation. In International Conference on Distributed Computing Systems (ICDCS'04), Tokyo, Japan, March 2004.]]
7. A. Boulis, C. Han, and Mani Srivastava. Design and implementation of a framework for efficient and programmable sensor networks. In MobiSys, 2003.]]
8. Josh Broch, David~A. Maltz, David~B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In MobiCom, 1998.]]
9. William J. Butera. Programming a paintable computer. PhD thesis, MIT, February 2002.]]
10. Luca Cardelli. A language with distributed scope. In POPL, 1995.]]
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, Phil Levis, Robert von Behren, Matt Welsh, Eric Brewer, and David Culler. The nesC language: A holistic approach to networked embedded systems. In PLDI, 2003.]]
15. Robert S. Gray. Agent Tcl: A flexible and secure mobile-agent system. PhD thesis, Dartmouth College, June 1997.]]
16. Robert S. Gray, George Cybenko, David Kotz, Ronald A. Peterson, and Daniela Rus. D'Agents: Applications and performance of a mobile-agent system. Software: Practice and Experience, May 2002.]]
17. Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister. System architecture directions for network sensors. In ASPLOS, 2000.]]
18. Qingfeng Huang, Chenyang Lu, and Gruia-Catalin Roman. Spatiotemporal multicast in sensor networks. In SenSys, 2003.]]
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, P. Hontalas, P. Laroche, K. Sturdevant, J. Tupman, V. Warren, J. Wedel, H. Younger, and S. Bellenot. Distributed simulation and time warp operating systems. In SOSP, 1987.]]
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 and H.T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In MobiCom, 2000.]]
24. Kazaa. homepage. http://www.kazaa.com.]]
25. Young-Bae Ko and Nitin H. Vaidya. Location-aided routing (lar) in mobile ad hoc networks. In MobiCom, 1998.]]
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 and Mitsuru Ishima. Programming and deploying Java mobile agents with Aglets. Addison-Wesley, 1998.]]
28. Philip Levis and David Culler. Maté: A tiny virtual machine for sensor networks. In ASPLOS, 2002.]]
29. Jinyang Li, John Jannotti, Douglas S. J. De Couto, David~R. Karger, and Robert Morris. A scalable location service for geographic ad hoc routing. In MobiCom, 2000.]]
30. Ting Liu and Margaret Martonosi. Impala: a middleware system for managing autononmic parallel sensor systems. In PPoPP, 2003.]]
31. S. Madden, M. J. Franklin, J. Hellerstein, and W. Hong. TAG:a Tiny AGregation service for ad-hoc sensor networks. In OSDI, 2002.]]
32. Mutella. homepage. http://mutella.sourceforge.net.]]
33. Radhika Nagpal. Programmable self-assembly using biologically-inspired multiagent control. In AAMAS, Bologna, Italy, July 2002.]]
34. J.C. Navas and T. Imielinski. geocast--geographic addressing and routing. In MobiCom, 1997.]]
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, and Liviu Iftode. A programming language for ad-hoc networks of mobile devices. In The 7th Workshop on Languages, Compilers, and Run-time Support for Scalable Systems (LCR 2004), Houston, TX, October 2004.]]
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, and Seth J. Teller. The cricket compass for context-aware mobile applications. In MobiCom, 2001.]]
40. Hanan Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, 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. ACM Communications, July 1999.]]
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, and David Culler. Hood: A neighborhood abstraction for sensor networks. In Mobisys 2004, June 2004.]]
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. P. Zhou, T. Nadeem, P. Kang, C. Borcea, and L. Iftode. EZCab: A cab booking application using short-range wireless communication. In Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom), March 2005.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages