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.
Schiller, J. Mobile Communications. Addison-Wesley,
2003.
Vaidya, Nitin H. Wireless Networks, draft.
Balakrishnan, Hari A Graduate Course in Computer Networks, draft.
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.
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.
Brenner, P. A Technical Tutorial on the IEEE 802.11 protocol.
BreezeCOM Wireless Communications, 1997.
http://sss-mag.com/pdf/802_11tut.pdf
Bharghavan, V., Demers, A., Shenker S., and Zhang L. MACAW: A Media Access Protocol for Wireless LANs. ACM SIGCOMM Computer Communication Review, 24(4):212-225, 1994.
Whitehouse, K., Woo, A., Jiang, F., Polastre, J., and Culler, D.
Exploiting the capture effect for collision detection and recovery.
IEEE Workshop on Embedded Networked Sensors (EmNetS-II),
pages 45-52, May 2005.
Demirbas, M, Soysal, O, and Hussain, M. Single hop collaborative
feedback primitives for wireless sensor networks. IEEE INFOCOM
2008: the 27th Conference on Computer Communications,
miniconference, pages 2047-2055, Phoenix, AZ, April 2008.
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.
Gallager, R. A perspective on multiaccess channels. IEEE
Transactions on Information Theory, 31(2):124-142, 1985.
Komlos, J. and Greenberg, A. An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Transactions on Information Theory, 31(2):302-306, 1985.
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.
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
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.
Now we begin studying network-layer issues, focusing first on basic communication problems like network-wide broadcast and point-to-point communication.
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
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
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.
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
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
These papers show how to implement various kinds of global services, which may in turn be useful in implementing applications.
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.
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
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.
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
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.
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.
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.
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.
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
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.
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.
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
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.
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
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