• Schiller, J., Mobile Communications. Addison-Wesley, 2003.

• Course notes for 6.829 by Prof. Hari Balakrishnan, MIT, lectures 11-14.

• Notes by Prof. Nitin Vaidya (University of Illinois); hard copy distributed in class

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

• 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

• Miu, A., Balakrishnan, H., and Koksal, C. E. Improving Loss Resilience with Multi-Radio Diversity in Wireless Networks. Mobicom 2005: The Eleventh Annual International Conference on Mobile Computing and Networking, Cologne, Germany, September, 2005. .pdf

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

• Eren, T., Goldenberg, D. K., Whiteley, W., Yang, Y. R., Morse, A. S., Anderson, B. D. O., and Belhumeur, P. N. Rigidity, Computation, and Randomization in Network Localization. IEEE Infocom 2004: The 23rd Conference, Hong Kong, March 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. Submitted for publication, 2004. .pdf

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. PODC'04: Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, St. Johns, Newfoundland, Canada, pages 320-327, July 2004. .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. To appear in OPODIS 2005: 9th International Conference on Principles of Distributed Systems, Pisa, Italy, December 2005. .pdf

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-LCS-TR-862, Cambridge, MA, 2002. .pdf, .ps

This section will contain papers that are designed to build up some local structure that can help in building distributed algorithms. Such algorithms have a local flavor; however, they 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

6. Broadcast

Now we begin studying network-layer issues. The broadcast problem studied in these paper is that of ensuring that a certain message is eventually delivered to every node in the network.

• 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

• Kushilevitz, 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. The algorithms in the first two subsections below (DRC, 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). In that sense, they seem quite a bit like "traditional" routing algorithms for wired networks.

7.1 "Classic" Routing Algorithms

• 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, Louisiana, 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

• 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 Architectures, San Diego, California, June 2003. .pdf

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

• 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

  Also, these slides about multi-hop wireless are very good. .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

8.1 Location Services

A location service maps node ids to their geographic locations. This can be combined with lcoation-based routing (see below). Various algorithms have been proposed.

• 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. (The GRID paper.) .pdf

• Awerbuch, B. and Peleg, D. Concurrent online tracking of mobile users. ACM SIGCOMM Computer Communication Review, 21(4):221-233, 1991. .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

These routing algorithms use information about the geographic location of the nodes to determine how to route messages to destinations.

• 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, Louisiana, 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

• 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

• 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

This topic includes problems like constructing and maintaining spanning trees and clusters.

• Wattenhofer, R. Algorithms for Ad Hoc Networks (Case Study Clustering) Slides. .ppt

• Elkin, M. Distributed Approximations - A Survey. Distributed Computing, volume 35, pages 40-57, December 2004. .pdf

• Wattenhofer has his own recommended reading list, conveniently broken down into categories, and major papers in the categories, with a short one sentence appraisal of each paper. It's online at .html

• 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

• 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

These papers show how to implement various kinds of global services, which may be useful in implementing applications.

10.1 Token Circulation, Leader Election

• 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. %was titled Self-stabilizing behavior in networks of nondeterministically %interacting sensors. To appear in OPODIS 2005: 9th International Conference on Principles of Distributed Systems, Pisa, Italy, December 2005. .pdf

• 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

• 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.1 Compulsory Protocols

An important precursor to the virtual nodes work was the "compulsory protocols" 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

Vrtual 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., 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 for Mobile Networks. 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

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

• 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

• 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

• Walter, J., Welch, J., and Amato, N. Distributed reconfiguration of metamorphic robot chains. Journal on Distributed Computing, 17:171-189, 2004. Springer-Verlag. .pdf

• 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

• Lynch, N., Mitra, S., and Nolte, T. Motion Coordination Using Virtual Nodes. To appear in CDC-ECC 2005: Forty-Fourth IEEE Conference on Decision and Control and European Control Conference, Seville, Spain, December 2005. .ps

• Sun and Garcia-Molina, paper on providing alert information for obstacles.