CPSC 689 Spring 2009

Reading List for CPSC 689-608, Spring 2009

Acknowledgement: MIT course 6.885, Fall 2008, taught by Prof. Nancy Lynch and Dr. Fabian Kuhn.

If you are behind the TAMU firewall, you can get free access to all papers published by ACM, IEEE and Springer via the TAMU library website. Contact me if you need help with this.

The following book introduces basic concepts of mobile computing:: Schiller, J. Mobile Communications. Addison-Wesley, 2003.
Prof. Nitin Vaidya of the University of Illinois is also preparing notes on (practical aspects of) mobile computing for his spring mobile computing course. He is allowing us to distribute paper copies to students in 6.885; however, you should not disseminate these to others. The target audience for these notes is senior undergraduates and first year graduates with knowledge of basic networking.: Vaidya, Nitin H. Wireless Networks, draft.
Prof. Balakrishnan's course notes for MIT course 6.829, Chapters 4, 11, 12, and 13, may also provide helpful background. We will also provide paper copies of these; again, do not disseminate these.: Balakrishnan, Hari A Graduate Course in Computer Networks, draft.

Part I: Basics

1.1 Physical layer

The reference books describe the physical characteristics of wireless networks.

Schiller, J. Mobile Communications, Chapters 1 and 2.

Vaidya, Nitin H. Wireless Networks, Chapters 1 and 2.

Balakrishnan, Hari A Graduate Course in Computer Networks, Chapter 11.

1.2 MAC layer

This section of the course will describe protocols that attempt to coordinate message transmissions over the shared communication medium. The books provide background and overview:

Schiller, J. Mobile Communications, Chapters 3 and 7.; Vaidya, Nitin H. Wireless Networks, Chapters 3, 4, and 5.; Balakrishnan, Hari A Graduate Course in Computer Networks, Chapter 11.
The following tutorial describes the popular 802.11 protocol, in great detail.

1.3 Time synchronization

These papers describe various techniques for providing nodes in a wireless network with a consistent notion of time.

Elson, J., Girod, L., and Estrin, D. Fine-Grained Network Time Synchronization Using Reference Broadcasts. ACM SIGOPS Operating Systems Review, 36(SI):147-163, 2002.; 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, volume 2976 of Lecture Notes in Computer Science, pages 609-624, 2004. Springer.; Su, W. and Akyildiz, I.F. Time-diffusion synchronization protocol for wireless sensor networks. IEEE/ACM Transactions on Networking, 13(2): 384-397, 2005.; Attiya, H., Hay, D., and Welch, J. Optimal Clock Synchronization Under Energy Constraints in Wireless ad hoc Networks. In Principles of Distributed Systems: 9th International Conference, OPODIS 2005, Pisa, Italy, December 2005, volume 3974 of Lecture Notes in Computer Science, pages 221-234, 2006, Springer.; 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.
The following papers have quite a different flavor. They give bounds on the closeness with which neighboring clocks can be synchronized in a large network.: Fan, R. and Lynch, N. Gradient clock synchronization. Distributed Computing, 18(4):255-266, March, 2006.; Fan, R. Lower Bounds in Distributed Computing. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, February 2008.
http://theory.csail.mit.edu/tds/papers/Fan/phd-thesis.pdf; Lenzen, C., Locher, T., and Wattenhofer, R. Clock synchronization with bounded global and local skew. Proceedings of 2008 Symposium on Foundations of Computer Science, Philadelphia, PA, October 2008.
http://dcg.ethz.ch/publications/focs08full.pdf

1.4 Localization

These algorithms describe how a node can learn its own location, to within some reasonable approximation.

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.
http://delivery.acm.org/10.1145/350000/345917/p32-priyantha.pdf?key1=345917&key2= 9630007121&coll=ACM&dl=ACM&CFID=36861458&CFTOKEN=35932670

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.

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.

Moore, D., Leonard, J., Rus, D., and Teller, S. Robust distributed network localization with noisy range measurements. Proceedings of ACM Sensys'04, Baltimore, Maryland, pages 50-61, November, 2004.
http://delivery.acm.org/10.1145/1040000/1031502/p50-moore.pdf?key1=1031502&key2= 5380007121&coll=GUIDE&dl=GUIDE&CFID=78109815&CFTOKEN=79552248

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. IEEE Transactions on Mobile Computing, 5(12):1663-1678, December, 2006.

Part II: Communication

Now we begin studying network-layer issues, focusing first on basic communication problems like network-wide broadcast and point-to-point communication.

2.1 Network-wide broadcast

The first paper gives a simple fault-tolerant broadcast algorithm, which is similar to some used in practice.

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.
http://theory.csail.mit.edu/tds/papers/Livadas/TR-915.pdf
The following four papers give theoretical upper and lower bound results about network broadcasts, under particular sets of assumptions.: 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.; 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, 5(2):67-71, 1991.; Kowalski, D. and Pelc, A. Time of Deterministic Broadcasting in Radio Networks with Local Knowledge. SIAM J. on Computing, 33(4): 870-891, 2004.; Kushelevitz, E. and Mansour, Y. An Omega(D log(N/D)) lower bound for broadcast in radio networks. SIAM Journal on Computing, 27(3):702-712, June 1998. Earlier version in PODC'93.
http://siamdl.aip.org/getpdf/servlet/GetPDFServlet?filetype= pdf&id=SMJCAT000027000003000702000001&idtype=cvips

2.2 Point-to-point message routing without location information

The following sources give overviews of routing issues in wireless networks:

Karp, B. Multi-hop Wireless Networks. CMU CS 15-829: Internet Scale Sensor Systems, March 18, 2003.
http://theory.csail.mit.edu/classes/6.885/fall08/papers/Karp-slides.pdf; Schiller, J. Mobile Communications, Chapter 8.; Vaidya, Nitin H. Wireless Networks, Chapter 6.
The algorithms described in this subsection do not rely on any kind of geographic information, whether absolute or relative; they just rely on connectivity information (who are my neighbors). In this sense, they are like "traditional" wired 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.
http://theory.csail.mit.edu/classes/6.885/fall08/papers/JohnsonMaltz.pdf; 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.; 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.; 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.
http://theory.csail.mit.edu/classes/6.885/fall08/papers/ChenMurphy-pomc01.pdf
An interesting strategy for routing without location informatino is based on a "link-reversal" strategy first studied in a theoretical paper by Gafni and Bertsekas:: Gafni, E. and Bertsekas, D. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE transactions on communications, January 1981.; 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.; Busch, C., Surapaneni, S., and Tirthapura. S. Analysis of link reversal routing algorithms. SIAM Journal on Computing, 35(2):305-326, October 2005.; Charron-Bost, B., Gaillard, A., Welch, J., and Widder, J. Routing without ordering. manuscript submited for publication, 2008.
The following paper compares some of the algorithms above.: 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.
The following papers also do not depend on information about actual locations in Euclidean space. Rather, they try to determine, and use, some other kind of "distance".: Rao, A., Ratnasamy, S., 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.; 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 Joint Conference of the IEEE Computer and Communications Societies, pages 339-350, Miami, Florida, March 2005.; 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.

2.3 Capacity of wireless networks

A popular topic for theoretical study has been limits on the communication capacity (bandwith) in wireless networks. Here are some representative papers.

Gupta, P. and Kumar, P. R. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388-404, 2000.

Moscibroda, T. and Wattenhofer, R. The complexity of connectivity in wireless networks. 25th Annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM 2006), pages 1-13, Barcelona, Spain, April 2006.

2.4 Location services

Some algorithms for point-to-point communication in mobile networks include a piece that keeps track of node locations, and enables nodes to "look up" the geographical locations of other nodes. This piece is often abstracted into a separate service called a location service. Various algorithms have been proposed, for instance:

Awerbuch, B. and Peleg, D. Online tracking of mobile users. Journal of the ACM, 42(5):1021-1058, 1995.

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.

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.

2.5 Location-based routing

These papers describe strategies for point-to-point message routing that use geographical information.

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.

Ko, Y.-B. and Vaidya, N. Location-aided routing (LAR) in mobile ad hoc networks. Wireless Networks, 6(4):307-321, Springer, July 2000.

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.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.9931

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, pages 243-254, August 2000.

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.

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.

Barriere, L., Fraigniaud, P., and Narayanan, L. Robust Position-Based Routing in Wireless ad hoc Networks with Irregular Transmission Ranges. Wireless Communications and Mobile Computing, 3(2):141-153, 2003. John Wiley & Sons, Inc.

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.

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.

Part III: Building and Maintaining Network Structure

3.1 Topology control

These papers describe how to reduce transmission power while maintaining network connectivity.

Li, L., Halpern, J., Bahl, V., Wang, Y.-M., and Wattenhofer, R. A cone-based distributed topology-control algorithm for wireless multi-hop networks. IEEE/ACM Transactions on Networking, 13(1):147-159, 2005.

Wang, Y. and Li, X.-Y. Localized construction of bounded degree and planar spanner for wireless ad hoc networks. Mobile Networks and Applications, 11(2):161-175, April 2006.
http://www.springerlink.com/content/5358546562233m73/fulltext.pdf

Bahramgiri, M., Hajiaghayi, M. T., and Mirrokni, V. S. Fault-tolerant and three-dimensional distributed topology control algorithms in wireless multi-hop networks. Wireless Networks, 12(2):179-188, 2006. Kluwer.

auf de Heide, F.M., Schindelhauer, C., Volbert, K., and Gruenewald, M. Energy, congestion, and dilation in radio networks. Theory of Computing Systems, 37(3):343-370, May 2004. Springer.

Burkhart, M., von Rickenbach, P., Wattenhofer, R., and Zollinger, A. Does topology control reduce interference? Proceedings of the 5th ACM International Symposium on Mobile ad hoc Networking and Computing (MOBIHOC), Tokyo, Japan, pp. 9-19, 2004.

von Rickenbach, P., Schmid, S., Wattenhofer, R., and Zollinger, A. A robust interference model for wireless ad hoc networks. Proceedings of the International Workshop on Algorithms for Wireless, Mobile, Ad Hoc, and Sensor Networks (WMAN), affiliated with the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05), Workshop 12, Vol. 13, 2005.
http://courses.csail.mit.edu/6.885/fall08/papers/RSWZ.pdf

Moscibroda, T., and Wattenhofer, R. Minimizing interference in ad hoc and sensor networks. Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany, pp. 24-33, 2005.

3.2 Clustering

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

Jia, L, Rajaraman, R., and Suel, T. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193-205, December 2002. Special Issue: Selected papers from PODC'01.; Kuhn, F. and Wattenhofer, R.. Constant-Time Distributed Dominating Set Approximation. Distributed Computing, 17(4):303-310, May 2005.; Kuhn, F., Moscibroda, T., and Wattenhofer, R. The price of being near-sighted. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, Florida, pp. 980-989, 2006.; Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., and Srinivasan, A. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, pp. 717-724, 2003.; Kuhn, F., Moscibroda, T., and Wattenhofer, R. Fault-tolerant clustering in ad hoc and sensor networks. Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS), Lisboa, Portugal, p. 68, 2006.; Kuhn, F. and Moscribroda, T. Distributed approximation of capacitated dominating sets. Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, California, pp. 161-170, 2007.; 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.
http://delivery.acm.org/10.1145/1020000/1011811/p300-kuhn.pdf; Elkin, M. Distributed Approximations - A Survey. SIGACT News, 35,(4):40-57, December 2004.
http://courses.csail.mit.edu/6.885/fall08/papers/elkin.pdf; Kuhn, F. and Wattenhofer, R. On the complexity of distributed graph coloring. Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), Denver, Colorado, pp. 7-15, 2006.
http://delivery.acm.org/10.1145/1150000/1146387/p7-kuhn.pdf
The following are classical papers on clustering algorithms in networks. The Awerbuch and Peleg paper describes metrics for clustering, but their algorithm is centralized.: Luby, M. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036-1055, November 1986.; Awerbuch, B. and D. Peleg, D. Sparse Partitions (Extended Abstract). IEEE Symposium on the 31st Annual Symposium on Foundations of Computer Science (FOCS 1990), pages 503-513, 1990.
http://ieeexplore.ieee.org/iel2/310/2915/00089571.pdf; Linial, N. and Saks, M. Decomposing Graphs into Regions of Small Diameter. Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 320-330, January 1991.

3.3 Unit disk graphs and related models

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.

Schmid, S. and Wattenhofer, R. Algorithmic models for sensor networks. 20th International Parallel and Distributed Processing Symposium (IPDPS), April 2006.

Schneider, J. and Wattenhofer, R. A log-star distributed maximal independent set algorithm for growth bounded graphs. Proceedings of 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, 2008.
http://www.dcg.ethz.ch/publications/podc08SW.pdf

Linial, N. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, February 1992.

Kuhn, F., Nieberg, T., Moscibroda, T., and Wattenhofer, R. Local approximation schemes for ad hoc and sensor networks. Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, Cologne, Germany, pp. 97-103, 2005.
http://delivery.acm.org/10.1145/1090000/1080827/p97-kuhn.pdf

Czygrinow, A. and Hanckowiak, M. Distributed approximation algorithms in unit-disk graphs. Distributed Computing, 20th International Symposium on Distributed Computing (DISC 2006), volume 4167 of Lecture Notes in Computer Science, pages 385-398, 2006. Springer.

3.4 The wakeup problem

Gasieniec, L., Pelc, A., and Peleg, D. The wakeup problem in synchronous broadcast systems. SIAM Journal on Discrete Mathematics, 14(2):207-222, 2001.

Jurdzinski, T. and Stachowiak, G. Probabilistic algorithms for the wakeup problem in single-hop radio networks. Proceedings of the 13th International Symposium on Algorithms and Computation, volume 2518 of Lecture Notes in Computer science, pages 535-549, 2002. Springer.

3.5 Local computations in the radio network model

Kuhn, F., Moscibroda, T., Wattenhofer, R. Initializing newly deployed ad hoc and sensor networks. Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, Philadelphia, Pennsylvania, pages 260-274, 2004.

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.
http://portal.acm.org/citation.cfm?id=1073842

Moscibroda, T. and Wattenhofer, R. Coloring unstructured radio networks. Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Las Vegas, Nevada, pp 39-48, 2005.

Part IV: Middleware

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

4.1 Local infrastructure

These papers describe algorithms that construct and maintain local structure for use in building distributed algorithms. Note that these algorithms may rely on the nodes having good information about the current time and about their own locations. Obtaining this information may require other distributed algorithms, like those in Section 1.

The following paper describes group services, intended to make it easier to program ad hoc networks.

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.
The next one deals with abstract regions.: 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.
http://delivery.acm.org/10.1145/1260000/1251178/p3-welsh.pdf
The following paper, discussed earlier for its treatment of collision detection, describes local consensus services.: Chockler, G., Demirbas, M., Gilbert, S., Lynch, N., Newport, C., and Nolte, T. Consensus and Collision Detectors in Wireless ad hoc Networks. Distributed Computing, 21(1):55-84, June, 2008.
The following papers describe local active state machines, or "virtual nodes". This is related to the "virtual infrastructure" approach that we will discuss later in the term.: Chockler, G. and Gilbert, S. Virtual Infrastructure for Collision-Prone Wireless Networks. Twenty-Seventh Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008), Toronto, Canada, August 2008.
http://groups.csail.mit.edu/tds/papers/Gilbert/PODC08.pdf; 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.
http://www.csl.uiuc.edu/allerton/archives/allerton05/PDFs/Papers/IV_F_1.pdf

4.2 Token circulation, leader election, resource allocation, and group communication

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.

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.
http://delivery.acm.org/10.1145/350000/345871/p96-malpani.pdf

Ingram, R., Shields, P., Walter, J., and Welch, J. An asynchronous leader election algorithm for dynamic networks. IEEE Int'l Parallel and Distributed Processing Symposium, 2009. Full version available as TAMU CSE Department Tech Report 2009-1-1.

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.

Chen, Y. and Welch, J. Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks. Journal of Parallel and Distributed Computing, 65(9):1072-1089, September 2005.

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.

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.
http://theory.csail.mit.edu/classes/6.885/fall08/papers/WalterCM.pdf

Dolev, S., Schiller, E., and Welch, J. Random Walk for Self-Stabilizing Group Communication in Ad-Hoc Networks. IEEE Transactions on Mobile Computing, 5(7):893-905, July 2006.

4.3 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.
http://delivery.acm.org/10.1145/310000/305649/p251-hatzis.pdf

Chatzigiannakis, I., Nikoletseas, S., and Spirakis, P. Distributed Communication Algorithms for ad hoc mobile networks. Journal of Parallel and Distributed Computing, volume 63, pages 8-74, 2003.

Chatzigiannakis, I. and Nikoletseas, S. Design and Analysis of an Efficient Communication Strategy for Hierarchical and Highly Changing Ad-hoc Mobile Networks. ACM/Baltzer Journal of Mobile Networks and Applications (MONET), 9(4):319-332, 2004. Special Issue on Parallel Processing Issues in Mobile Computing.

4.4 Virtual node layers

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. These papers describe entire abstraction layers consisting of virtual nodes and communication services that connect the virtual and ordinary nodes.

Dolev, S., Gilbert, S., Lynch, N., Shvartsman, A., and Welch, W. GeoQuorums: Implementing Atomic Memory in Ad Hoc Networks. Distributed Computing, Special Issue DISC03, 18(2):125-155, 2005.

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.

Chockler, G. and Gilbert, S. Virtual Infrastructure for Collision-Prone Wireless Networks. Twenty-Seventh Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008), Toronto, Canada, August 2008.
http://groups.csail.mit.edu/tds/papers/Gilbert/PODC08.pdf

Seth Gilbert. Virtual Infrastructure for Wireless Ad Hoc Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, 2007.
http://groups.csail.mit.edu/tds/papers/Gilbert/thesis-final-gilbert.pdf

Mike Spindel. Simulation and Evaluation of the Reactive Virtual Node Layer. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 2008.
http://groups.csail.mit.edu/tds/papers/Spindel/thesis.pdf

Dolev, S., Gilbert, S., Lahiani, L., Lynch, N., and Nolte, T. Timed Virtual Stationary Automata for Mobile Networks. Principles of Distributed systems: 9th International Conference on Principles of Distributed Systems (OPODIS 2005), volume 3974 of Lecture Notes in Computer Science, pages 130-145, 2006, Springer. Also, Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA 02139, August 2005.

Dolev, D., Lahiani, L., Lynch, N., and Nolte, T. Self-Stabilizing Mobile Node Location Management and Message Routing. Self-Stabilizing Systems: Seventh International Symposium on Self Stabilizing Systems (SSS 2005), Barcelona, Spain, October 26-27, 2005, volume 3764 of Lecture Notes in Computer Science, pages 96-112, 2005. Springer. Also, Technical Report MIT-LCS-TR-999, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2005.

Tina Nolte. Virtual Stationary Timed Automata for Mobile Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 2008.

Part V: Applications

5.1 Data aggregation

Shrivastava, N. Buragohain, C., Agrawal, D., and Suri, S. Medians and Beyond: New Aggregation Techniques for Sensor Networks. Proceedings of the 2nd ACM International Conference on Embedded Networked Sensor Systems (Sensys'04), Nor. 35, Baltimore, Maryland, pages 239-249, November, 2004.; Nath, S., Gibbons, P. Anderson, Z., and Seshan, S. Synopsis Diffusion for Robust Aggregation in Sensor Networks. ACM Transactions on Sensor Networks, 4(2):1-40, March 2008.
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. Theoretical Computer Science, 370(1-3):254-264, February 2007.; Kuhn, F., Locher, T., and Schmid, S. Distributed computation of the mode. Twenty-Seventh Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008), Toronto, Canada.
http://www.dcg.ethz.ch/publications/podc08.pdf

5.2 Computing properties in mobile networks

Aspnes, J., and Ruppert, E. An Introduction to Population Protocols, chapter of book MiNEMA: State of the Art, to be published by Springer.
http://theory.csail.mit.edu/classes/6.885/fall08/papers/minema-survey-3.pdf

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M. J., and Peralta, R. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, March 2006. Special Issue PODC'04.

Angluin, D., Aspnes, J., Chan, M., Fischer, M. J., Jiang, H., and Peralta, R. Stably computable properties of network graphs. Distributed Computing in Sensor Systems: International Conference on Distributed Computing in Sensor Systems (DCOSS'05), Marina del Ray, California, June/July 2005, volume 3560 of Lecture Notes in Computer Science, pages 63-74, 2006. Springer.

Angluin, D., Aspnes, J., Fischer, M. J., and Jiang, H. Self-stabilizing population protocols. Principles of Distributed Systems: 9th International Conference on Principles of Distributed Systems (OPODIS'05), Pisa, Italy, December 2005, volume 3974 of Lecture Notes in Computer Science, pages 103-117, 2006. Springer.

Angluin, D., Fischer, M.J., and Jiang, H. Stabilizing consensus in mobile networks. Proceedings of 2nd International Conference on Distributed Computing in Sensor Systems (DCOSS'06), San Francisco, California, volume 4026 of Lecture Notes in Computer Science,pages 37-50, Springer-Verlag, June 2006.

Fischer, M. and Jiang, H. Self-stabilizing leader election in networks of finite-state anonymous agents. Principles of Distributed Systems: Proceedings of 10th International Conference on Principles of Distributed Systems (OPODIS'06), Bordeaux, France, volume 4305 of Lecture Notes in Computer Science, pages 395-409, Springer-Verlag, 2006.

Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, November 2007. PODC 2006 special issue.

5.3 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.

Gilbert, S., Lynch, N., and Shvartsman, A. RAMBO: A Robust, Reconfigurable Atomic Memory for Dynamic Networks. Submitted for journal publication.
http://groups.csail.mit.edu/tds/papers/Gilbert/rambo-journal2.pdf

Dolev, S., Gilbert, S., Lynch, N., Shvartsman, A., and Welch, W. GeoQuorums: Implementing Atomic Memory in Ad Hoc Networks. Distributed Computing, Special Issue DISC03, 18(2):125-155, 2005.

5.4 Robot motion coordination

Walter, J., Welch, J., and Amato, N. Distributed reconfiguration of metamorphic robot chains. Distributed Computing, 17(2):171-189, 2004. Springer-Verlag.; Li, Q. and Rus, D. Navigation Protocols in Sensor Networks. ACM Transactions on Sensor Networks, 1(1):3-35, August 2005.; James McLurkin. Analysis and Implementation of Distributed Algorithms for Multi-Robot Systems. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 2008.
http://people.csail.mit.edu/jamesm/McLurkin-PhD-MIT-2008.pdf; Defago, X. and Konagaya, A. Circle formation for oblivious anonymous mobile robots with no common sense of orientation. Proceedings of the Second ACM International Workshop on Principles of Mobile Computing, Toulouse, France, pages 97-104, October 2002.; Flocchini P., Prencipe G., Santoro N. and Widmayer W. Gathering of asynchronous robots with limited visability. Theoretical Computer Science, 337(1-3):147-168, 2005.; Bullo, F., Cortes, J., and Martinez, S. Distributed control of robotic networks: A mathematical approach to motion coordination algorithms. Manuscript preprint, June 2008.
Electronically available at http://coordinationbook.info
The following uses virtual nodes to address the coordination problem.: Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte. Self-Stabilizing Robot Formations over Unreliable Networks. Submitted for journal publication, 2008.
http://courses.csail.mit.edu/6.885/fall08/papers/GLMN-sub; 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.

5.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.
http://infolab.stanford.edu/~qsun/research/alert.pdf

Maihoefer, C., Leinmueller, T., and Schoch, E.. Abiding geocast: time--stable geocast for ad hoc networks. Proc. 2nd ACM International Workshop on Vehicular Ad Hoc Networks pp. 20-29, 2005. http://portal.acm.org/citation.cfm?doid=1080754.1080758

Kan, M., Pande, R., Vinograd, P., and Garcia-Molina, H. Event Dissemination in High Mobility Ad-hoc Networks. Submitted for publication, 2005.
http://courses.csail.mit.edu/6.885/fall08/papers/Kan-etal.pdf

5.6 Aircraft control

Matthew D. Brown. Air Traffic Control Using Virtual Stationary Automata. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2007.
http://groups.csail.mit.edu/tds/papers/Brown/mdbrown-thesis.pdf