Back to Course Home Page.
>>
Prof. Nitin Vaidya of the University of Illinois is also preparing notes on (practical aspects of) mobile computing this term. He is allowing us to distribute xerox copies to members of this course; however, they should not be disseminated to others. In return, we should try to provide him with helpful feedback.
Prof. Balakrishnan's course notes for 6.829, lectures 11-14, also provide helpful background.
This section of the course will describe protocols that attempt to coordinate message transmissions over the shared communication medium.
Gallager, R. A perspective on multiaccess channels. IEEE Transactions on Information Theory, 31(2):124-142, 1985. .pdf
Komlos, J. and Greenberg, A. An asymptotically nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Transactions on Information Theory, IT-31, pages 302-306, 1985. .pdf
Brenner, P. A Technical Tutorial on the IEEE 802.11 protocol. BreezeCOM Wireless Communications, 1997. .pdf
The following gives a nice overview of basic issues in wireless networks, plus a specific MAC protocol.
Bharghavan, V., Demers, A., Shenker S., and Zhang L. MACAW: A Media Access Protocol for Wireless LANs. Proceedings of the ACM SIGCOMM'94 Conference on Communications Architectures, Protocols, and Applications, London, U.K., pages 212-225, August/September 1994. .pdf
2. Localization
These algorithms describe how a node can learn its own location, to within some reasonable approximation.
Savvides, A., Han, C.-C., and Strivastava, M. B. Dynamic fine-grained localization in ad-hoc networks of sensors. Mobicom 2001: The Seventh Annual International Conference on Mobile Computing and Networking, Rome, Italy, July, 2001. .pdf
Priyantha, N., Chakraborty, A., and Balakrishnan, H. The Cricket Location-Support System. Mobicom 2000: The Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, August 2000. .pdf
Priyantha, N. B., Balakrishnan, H., Demaine, E., and Teller, S. Mobile-Assisted Localization in Wireless Sensor Networks. IEEE INFOCOM 2005: The 24th Annual Conference, Miami, FL, March 2005. .pdf
Moore, D., Leonard, J., Rus, D., and Teller, S. Robust distributed network localization with noisy range measurements. Proceedings of ACM Sensys'04, Baltimore, Maryland, November, 2004. .pdf
Aspnes, J., Eren, T., Goldenberg, D. K., Morse, A. S., Whiteley, W., Yang, Y. R., Anderson, B. D. O., and Belhumeur, P. N. A theory of network localization. To appear in IEEE Transactions on Mobile Computing, January 2006. .pdf
Connelly, B., Lecture notes on rigidity. .pdf
3. Time synchronization
These papers describe various techniques for providing the nodes with a consistent notion of time.
Elson, J., Girod, L., and Estrin, D. Fine-Grained Network Time Synchronization Using Reference Broadcasts. OSDI'02: 5th Symposium on Operating Systems Design and Implementation, Boston, Massachusetts, December 2002. ..pdf
Karp, R. M., Elson, J., Papadimitriou, C., and Shenker, S. Global Synchronization in Sensornets. Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04), Buenos Aires, Argentina, pages 609-624, April 2004. .pdf
Su, W. and Akyildiz, I.F. Time-diffusion synchronization protocol for wireless sensor networks. IEEE/ACM Transactions on Networking, 13(2): 384-397, 2005. .pdf
Fan, R. and Lynch, N. Gradient clock synchronization. To appear in Distributed Computing. .pdf
Fan, R., Chakraborty, I., and Lynch, N. Clock Synchronization for Wireless Networks. In Teruo Higashino, editor, Principles of Distributed Systems: 8th International Conference, OPODIS 2004, Grenoble, France, December 2004,volume 3544 of Lecture Notes in Computer Science, pages 400-414, 2005. Springer. .ps.gz
Attiya, H., Hay, D., and Welch, J. Optimal Clock Synchronization Under Energy Constraints in Wireless ad hoc Networks. OPODIS 2005: 9th International Conference on Principles of Distributed Systems, Pisa, Italy, December 2005. .pdf
4. Topology control
These papers describe how to reduce transmission power while guaranteeing to maintain network connectivity.
Li, L., Halpern, J., Bahl, V., Wang, M., and Wattenhofer, R. Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. PODC 2001: Proceedings of the Twentieth ACM Symposium on Principles of Distributed Computing, Newport, Rhode Island, August 2001. .pdf
Bahramgiri, M., Hajiaghayi, M. T., and Mirrokni, V. S. Fault-tolerant and Three-Dimensional distributed topology control algorithms in wireless multi-hop networks. Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (IC3N), Miami, Florida, pages 392-398, October 2002. Also, MIT Technical Report MIT-TR-TR-862, Cambridge, MA, 2002. .ps
5. Local infrastructure
These papers describe algorithms that build local structure that can help in building distributed algorithms. (These algorithms may rely on the nodes having good information about the current time and about their own locations. Obtaining this information may require distributed algorithms, as described in the previous items.)
Chockler, G., Demirbas, M., Gilbert, S., Newport, C., and Nolte, T. Consensus and Collision Detectors in Wireless ad hoc Networks. PODC'05: Proceedings of the Twenty-Fourth Annual Symposium on Distributed Computing, Las Vegas, Nevada, July, 2005. .pdf
Chockler, G. and Gilbert, S. Replicated State Machines for Collision-Prone Wireless Networks. Manuscript, 2005. .pdf
The following paper presents another ``middleware'' for wireless networks that uses group services to make programming ad hoc networks easier.
Luo, J. and Hubaux, J.. NASCENT: Network Layer Service for Vicinity Ad-hoc Groups. In Proceedings of the First Annual IEEE Conference on Sensor and Ad Hoc Communications and Networks (SECON 2004), Santa Clara, California, October 2004. .pdf
The following paper presents a "region-based" paradigm for programming sensor networks, which is related to the "virtual infrastructure" approach we will discuss later in the term.
Welsh, M. and Mainland, G. Programming Sensor Networks Using Abstract Regions. In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI'04), March 2004. .pdf
6. Broadcast
Now we begin studying network-layer issues. Network-wide broadcast has been studied quite a bit. Here are a few representative papers.
Bar-Yehuda, R., Goldreich, O., and Itai, A. On the Time Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap Between Determinism and Randomization. Journal of Computer and System Sciences, 45(1):104-126, 1992. .pdf
Bar-Yehuda, R., Goldreich, O., and Itai, A. Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection. Distributed Computing, volume 5, pages 67-71, 1991. .pdf
Kowalski, D. and Pelc, A. Time of Deterministic Broadcasting in Radio Networks with Local Knowledge. SIAM J. on Computing, 33(4): 870-891, 2004. .pdf
Kushelevitz, E. and Mansour, Y. An Omega(D log(N/D)) lower bound for broadcast in radio networks. PODC'93: Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, Ithaca, New York, pages 65-74, August, 1993. .pdf
Gupta, P. and Kumar, P. R. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388-404, 2000. .pdf
Livadas, C. and Lynch, N. A Reliable Broadcast Scheme for Sensor Networks. Technical Report MIT-LCS-TR-915, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2003. .ps
Chockler, G., Demirbas, M., Gilbert, S., and Newport, C. A Middleware Framework for Robust Applications in Wireless Ad Hoc Networks. Allerton Conference 2005: Forty-Third Annual Allerton Conference on Communication, Control, and Computing, September, 2005. .pdf
7. Point-to-point routing
Much work on algorithms for mobile networks has been devoted to message routing.
Brad Karp. Multi-hop Wireless Networks. CMU CS 15-829: Internet Scale Sensor Systems, March 18, 2003. .pdf
The algorithms described in the first two subsections below (DSR, AODV, TORA, etc.) do not rely on any kind of geographic information, whether absolute or relative; they just rely on connectivity information (who are my neighbors). So they seem quite a bit like "traditional" wired routing algorithms.
7.1 Algorithms similar to those used in traditional wired networks
Johnson, D. B. and Maltz. D. A. Dynamic source routing in ad hoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing, pages 153-- 81. Kluwer, 1996. .ps
Perkins, C. and Royer, E. Ad hoc on-demand distance-vector routing. 2nd Workshop on Mobile Computing Systems and Applications (WMCSA'99), New Orleans, Lousiana, pages 90-100, February 1999. .ps
Hu, Y.-C. and Johnson, D. B. Caching strategies in on-demand routing protocols for wireless ad-hoc networks. Mobicom 2000: 6th Intl. Conference on Mobile Computing and Networking, Boston, Massachusetts, pages 231-242, August 2000. .pdf
Chen, X. and Murphy, A. Enabling disconnected transitive communication in mobile ad hoc networks. POMC 2001: Workshop on Principles of Mobile Computing, Newport, Rhode Island, August 2001. .pdf
7.2 Link-reversal routing algorithms
Gafni, E. and Bertsekas, D. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE transactions on communications, January 1981. .pdf
Park, V. and Corson, M. A highly adaptive distributed routing algorithm for mobile ad hoc networks. Proceedings IEEE INFOCOM '97, The Conference on Computer Communications, Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Driving the Information Revolution, Kobe, Japan, pages 1405-1413, April 1997. .pdf
Busch, C., Surapaneni, S., and Tirthapura. S. Analysis of link reversal routing algorithms for mobile ad hoc networks. SPAA 2003: Fifteenth ACM Symposium on Parallelism in Algorithms and Architecturesan Diego, California, June 2003. .pdf
7.3 Location-free routing
These algorithms do not use information about actual locations in Euclidean space. Rather, they try to determine, and use, some other kind of ``distance''.
Rao, A., Papadimitiou, C., Shenker, S., and Stoica, I. Geographical routing without location information. Mobicom 2003: The Ninth Annual International Conference on Mobile Computing and Networking, San Diego, California, pages 96-108, September 2003. .pdf
Fang, Q., Gao, J., Guibas, L., de Silva, V., and Zhang, L. GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks. INFOCOM 2005: 24th Annual Conference, Miami, Florida, March 2005. .pdf
Fonseca, R., Ratnasamy, S., Zhao, J., Ee, C. T., Coller, D., Shenker, S., and Stoica, I. Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets. NSDI 2005: 2nd Symposium on Networked Systems Design and Implementation, Boston, Massachusetts, May 2005. .pdf
Woo, A., Tong, T., and Culler, D. Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks. Proceedings of SenSys'03, Los Angeles, CA, November 2003. .pdf
7.4 Other protocols
Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C., and Jetcheva, J. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. In Mobicom'98: Proceedings of the Fourth Annual International Conference on Mobile Computing and Networking, Dallas Texas, October 1998. .pdf
De Couto, D., Aguayo, D., Bicket, J., and Morris, R. A High-Throughput Path Metric for Multi-Hop Wireless Routing. In Mobicom 2003: The Ninth Annual International Conference on Mobile Computing and Networking, San Diego, California, September 2003. .pdf
Biswas, S. and Morris, R. ExOR: Opportunistic Multi-Hop Routing for Wireless Networks. In Proceedings of the 2005 ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Philadelphia, Pennsylvania, pages 133-143, August 2005. .pdf
Some nice slides about multi-hop wireless appear at: .pdf
8. Location-based communication services
8.1 Location services
A location service maps node ides to their geographic locations. This can be combined with location-based routing (see below). Various algorithms have been proposed.
Awerbuch, B. and Peleg, D. Concurrent online tracking of mobile users. ACM SIGCOMM Computer Communication Review, 21(4):221-233, 1991. .pdf
Li, J., Jannotti, J., DeCouto, D. S. J., Karger, D. R., and Morris, R. A Scalable Location Service for Geographic ad hoc Routing. Mobicom 2000: The Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, pages 120-130, August 2000. .pdf
Abraham, I., Dolev, D., and Malkhi, D. LLS: A Locality Aware Location Service for Mobile ad Hoc Networks. Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, Philadelphia, Pennsylvania, pages 75-84, October 2004. .pdf
8.2 Location-based routing
Ko, Y.-B. and Vaidya, N. Geocasting in mobile ad-hoc networks: location-based multicast algorithms. WMCSA'99: 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, Lousiana, February 1999. .pdf
Ko, Y.-B. and Vaidya, N. Location-aided routing (LAR) in mobile ad hoc networks. Wireless Networks, 6(4):307-321, Springer, July 2000. .pdf
Kranakis, E., Singh, H., and Urrutia, J. Compass routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, BC, Canada, August 1999. .pdf
Karp, B. and Kung, H. T. GPSR: Greedy perimeter stateless routing for wireless networks. Mobicom 2000: The Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, August 2000. .pdf
The following paper is related to routing in geometric networks, and to the geocast/GPSR algorithms. It proves guarantees on "stretch" (how far from optimal is the selected path?). It has a good bibliography on geometric routing.
Abraham, I. and Malkhi, D.. Compact Routing on Euclidean Metrics. 23rd ACM Symposium on Principles of Distributed Computing (PODC 2004), John's, Newfoundland, Canada, July 2004. .pdf
Bose, P., Morin, P., Stojmenovic, I., and Urrutia, J. Routing with Guaranteed Delivery in ad hoc Wireless Networks. Wireless Networks, 7(6):609-617, Springer, November 2001. .pdf
Barriere, L., Fraigniaud, P., and Narayanan, L. Robust Position-Based Routing in Wireless ad Hoc Networks with Unstable Transmission Ranges. In Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2001), Rome, Italy, pages 19-27, July 2001. .pdf
Kuhn, F., Wattenhofer, R., Zhang, Y., and Zollinger, A. Geometric ad-hoc routing: Of theory and practice. PODC'03: Proceedings of the Twenty-Second ACM Symposium on Principle of Distributed Computing, Boston, Massachusetts, pages 63-72, July 2003. .pdf
9. Global infrastructure
This topic includes problems like constructing and maintaining spanning trees and clusters.
Kuhn, F. and Wattenhofer, R.. Constant-Time Distributed Dominating Set Approximation. In Proceedings of the 22nd ACM Symposium on the Principles of Distributed Computing (PODC'03), Boston, Massachusetts, USA, pages 25-32, July 2003. .pdf
Kuhn, F., Moscibroda, T., and Wattenhofer, R. On the Locality of Bounded Growth. In Proceedings of the 24th ACM Symposium on the Principles of Distributed Computing (PODC'05), Las Vegas, Nevada, USA, pages 60-68, July 2005. .pdf
Moscibroda, T. and Wattenhofer, R. Maximal Independent Sets in Radio Networks. Proceedings of the 24th ACM Symposium on the Principles of Distributed Computing (PODC'05), Las Vegas, Nevada, USA, pages 148-157, July 2005. .pdf
Kuhn, F., Moscibroda, T., and Wattenhofer, R. What Cannot Be Computed Locally! Proceedings of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC'04), St. John's, Newfoundland, Canada, pages 300-309, July 2004. .pdf
Wattenhofer, R. Algorithms for Ad Hoc Networks (Case Study Clustering) Slides. .pdf
Elkin, M. Distributed Approximations - A Survey. Distributed Computing, volume 35, pages 40-57, December 2004. .pdf
Kuhn, F., Wattenhofer, R., and Zollinger, A. Ad-hoc networks beyond unit-disk graphs. DIALM-POMC, Joint Workshop on Foundations of Mobile Computing, San Diego, California, pages 69-78, September 2003. .pdf
Mittal, V., Demirbas, M., and A. Arora, A. Loci: Local Clustering in Large Scale Wireless Networks. Technical Report OSU-CISRC-2/03-TR07, The Ohio State University, February 2003. .ps
This classical paper talks about metrics for clustering; the algorithm is centralized.
Awerbuch, B. and D. Peleg, D. Sparse Partitions (Extended Abstract). IEEE Symposium on Foundations of Computer Science, pages 503-513, 1990. .pdf
10. Middleware services
These papers show how to implement various kinds of global services, which may be useful in implementing applications.
Malpani, N., Chen, Y., Vaidya, N., and Welch, J. Distributed token circulation in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 4(2): 154-165, March/April 2005. .pdf
Malpani, N., Welch, J., and Vaidya, N. Leader election algorithms for mobile ad hoc networks. DIAL-M 2000: Fourth International Workshop in Discrete Algorithms and Methods for Mobile Computing and Communications, Boston, Massachusetts, pages 96-103, August 2000. .pdf
Angluin, D., Aspnes, J., Fischer, M. J., and Jiang, H. Self-stabilizing Population Protocols. OPODIS 2005: 9th International Conference on Principles of Distributed Systems, Pisa, Italy, December 2005. .pdf
10.1 Mutual exclusion, resource allocation
Walter, J., Welch, J., and Vaidya, N. A mutual exclusion algorithm for ad hoc mobile networks. Wireless Networks, 7(6):585-600, Springer, November 2001. .pdf
Chen, Y. and Welch, J. Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks. To appear in the Journal of Parallel and Distributed Computing. .ps.
Bulgannawar, S. and Vaidya, N. A distributed k-mutual exclusion algorithm. ICDCS 1995: Proceedings of the 15th International Conference on Distributed Computing Systems, Vancouver, British Columbia, Canada, pages 153-160, May/June 1995, IEEE Computer Society Press. .pdf
Walter, J., Cao, G., and Mohanty, M. A k-mutual exclusion algorithm for wireless ad hoc networks. POMC 2001: Workshop on Principles of Mobile Computing , Newport, Rhode Island, August 2001. .pdf
10.2 Group membership, group communication
Dolev, S., Schiller, E., and Welch, J. Random Walk for Self-Stabilizing Group Communication in Ad-Hoc Networks. SRDS 2002: 21st Symposium on Reliable Distributed Systems, Suita, Japan, pages 70-79, October 2002. IEEE Computer Society. .pdf
11. Virtual node layers
11.1 Compulsory protocols
An important precursor to the virtual nodes work was the "compulsory protocols" work by Hatzis, et al. These protocols rely on mobile nodes that move according to a pre-planned pattern.
Hatzis, K. P., Pentaris, G. P., Spirakis, P., Tampakas, V., and Tan, R. Fundamental control algorithms in mobile networks. SPAA 1999: Eleventh ACM Symposium on Parallel Algorithms and Architectures, Saint-Malo, France, pages 251-260, June 1999. .pdf
Chatzigiannakis, I., Nikoletseas, S., and Spirakis, P. On the average and worst-case efficiency of some new distributed communication and control algorithms for ad-hoc mobile networks. POMC 2001: Workshop on Principles of Mobile Computing, Newport, Rhode Island, August 2001. .pdf
Chatzigiannakis, I., Nikoletseas, S., and Spirakis, P. An efficient communication strategy for ad-hoc mobile networks. DISC 2001: 15th International Symposium on DIStributed Computing, Lisbon, Portugal, October 2001. .pdf
Chatzigiannakis, I., Nikoletseas, S., and Spirakis, P. An efficient routing protocol for hierarchical ad-hoc mobile networks. In Proceedings of the 1st IEEE/ACM International Workshop on Parallel and Distributed Computing Issues in Wireless networks and Mobile Computing (PDCIWNMC'2001), IPDPS 2001 Workshops, Hyatt Regency, San Francisco, April 2001. .pdf
11.2 Virtual nodes
Virtual nodes are explicit active entities that are implemented by the real mobile nodes. They may be stationary or mobile. If they are mobile, they can emulate moving nodes in compulsory protocols.
Dolev, S., Gilbert, S., Lynch, N., Shvartsman, A., and Welch, W. GeoQuorums: Implementing Atomic Memory in Ad Hoc Networks. To appear in special edition of Distributed Computing, (edited by Faith Fich), related to the DISC03 conference. .ps
Dolev, S., Gilbert, S., Lynch, N., Schiller, E., A. Shvartsman, A., and Welch, J. Virtual Mobile Nodes for Mobile ad hoc Networks. In Rachid Guerraoui, editor, 18th International Symposium on Distributed Computing (DISC04), Trippenhuis, Amsterdam, the Netherlands, October 4-7, 2004, volume 3274 of Lecture Notes in Computer Science, Springer-Verlag, December 2004. .ps
Dolev, S., Gilbert, S., Lahiani, L., Lynch, N., and Nolte, T. Timed Virtual Stationary Automata. 9th International Conference on Principles of Distributed Systems (OPODIS 2005), December 12-14, 2005. Also, Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA 02139, August 2005. .ps
Dolev, D., Lahiani, L., Lynch, N., and Nolte, T. Self-Stabilizing Mobile Node Location Management and Message Routing. Seventh International Symposium on Self Stabilizing Systems (SSS 2005), Barcelona, Spain, October 26-27, 2005. Also, Technical Report MIT-LCS-TR-999, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2005. .pdf
Jun Luo, J., Th. Eugster, P., and Hubaux, J.-P. Pilot: Probabilistic Lightweight Group Communication System for Ad-Hoc Networks. IEEE Transactions on Mobile Computing, 3(2):164-179, 2004. .pdf
12. Applications
12.1 Data aggregation
Nath, S., Gibbons, P. Anderson, Z., and Seshan, S. Synopsis Diffusion for Robust Aggregation in Sensor Networks. Proceedings of ACM Sensys'04, Baltimore, Maryland, November, 2004. .pdf
Shrivastava, N. Buragohain, C., Agrawal, D., and Suri, S. Medians and Beyond: New Aggregation Techniques for Sensor Networks. Proceedings of ACM Sensys'04, Nor. 35, Baltimore, Maryland, November, 2004. .pdf
This paper is related to aggregating data in a sensor network. It focuses on reducing the bit complexity.
Patt-Shamir, B. A note on efficient aggregate queries in sensor networks. Proceedings of the 23rd Annual ACM Conference on Principles of Distributed Computing (PODC 2004), St. John's, Newfoundland, Canada, pages 283-289, July 2004. .pdf
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M. J., and Peralta, R. Computation in networks of passively mobile finite-state sensors. Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004), St. John's, Newfoundland, Canada, July 2004. .pdf
Angluin, D., Aspnes, J., Chan, M., Fischer, M. J., Jiang, H., and Peralta, R. Stably computable properties of network graphs. DCOSS'05: International Conference on Distributed Computing in Sensor Systems, Marina del Ray, California, June/July 2005. .pdf
12.2 Implementing atomic memory
Lynch, N. and Shvartsman, A. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. In D. Malkhi, editor, Distributed Computing (Proceedings of the 16th International Symposium on DIStributed Computing (DISC) October 2002, Toulouse, France), volume 2508 of Lecture Notes in Computer Science, pages 173-190, 2002. Springer-Verlag. .pdf
Gilbert, S., Lynch, N., and Shvartsman, A. RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks. Proceedings of the International Conference on Dependable Systems and Networks (DSN), San Francisco, CA, pages 259-268, June 22nd - 25th, 2003. .ps.gz
Dolev, S., Gilbert, S., Lynch, N., Shvartsman, A., and Welch, W. GeoQuorums: Implementing Atomic Memory in Ad Hoc Networks. To appear in special edition of Distributed Computing, (edited by Faith Fich), related to the DISC03 conference. .ps
12.3 Tracking non-cooperating objects (intruders)
Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. A Hierarchy-based Fault-local Stabilizing Algorithm for Tracking in Sensor Networks. In Teruo Higashino, editor, Principles of Distributed Systems: OPODIS 2004: 8th International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004, volume 3544 of Lecture Notes in Computer Science, pages 299-315, 2005. Springer. .pdf
12.4 Robot motion coordination
Walter, J., Welch, J., and Amato, N. Distributed reconfiguration of metamorphic robot chains. Journal on Distributed Computing, 17:171-189, 2004. Springer-Verlag. .pdf
Other papers on this topic include:
Defago, X. and Konagaya, A. Circle formation for oblivious anonymous mobile robots with no common sense of orientation. POMC 2002: Workshop on Principles of Mobile Computing, Toulouse, France, October 2002. .pdf
Flocchini P., Prencipe G., Santoro N. and Widmayer W. Gathering of Autonomous Mobile Robots With Limited Visibility. In Proc. 18th International Symposium on Theoretical Aspects of Computer Science (STACS 2001), Dresden, Germany, pages 247-258, volume 2010 of Lecture Notes in Computer Science, Springer, 2001. .pdf
Li, Q. and Rus, D. Navigation Protocols in Sensor Networks. ACM Transactions on Sensor Networks, 1(1):1-33, August 2005. .pdf
The following uses virtual nodes to address the coordination problem.
Lynch, N., Mitra, S., and Nolte, T. Motion Coordination Using Virtual Nodes. CDC-ECC 2005: Forty-Fourth IEEE Conference on Decision and Control and European Control Conference, Seville, Spain, December 2005. .ps
12.5 Intelligent highways
Sun, Q. and Garcia-Molina, H. Using ad-hoc inter-vehicle network for regional alerts. Technical Report 2004-51, Computer Science Department, Stanford University, 2005. .pdf
Kan, M., Pande, R., Vinograd, P., and Garcia-Molina, H. Event Dissemination in High Mobility Ad-hoc Networks. Submitted for publication, 2005.