Reading List on Ad Hoc and Sensor Networks

This web page contains a selection of papers in ad hoc and sensor networking, grouped by topic. It may serve as a reading list for students who are interested in doing research in ad hoc/sensor networks. It may also serve as a bibliography for lecturers who are interested in teaching sensor or ad hoc networks.

The reading list concentrates on algorithmic results. (We are aware that a large majority of papers in ad hoc/sensor networking evaluates protocols/heuristics by simulation; for these papers we refer to other lists/books.) Clearly our selection is highly subjective. If you believe that we missed an important paper, or misinterpreted a paper, please tell us. We�re looking forward to updating our reading list thanks to your valuable input.

Topics

• Link Layer
  • MAC / Coloring
  • Topology Control
  • Interference
  • Deployment / Initialization
  • Spanning Structures
  • Dominating Sets
  • Maximal Independent Sets
  • Radio Networks
• Network Layer
  • Geo-Routing
  • Intriguing Routing Paradigms
  • Data Gathering
• Transport Layer
• Services
  • Location Services
  • Time Synchronization
  • Positioning / Virtual Coordinates
• Theory
  • Model
  • Lower Bounds
  • Information Theoretic Aspects

 

Geo-Routing

[TK84a]	On Transmission Ranges for Randomly Distributed Packet Radio Terminals. H. Takagi and L. Kleinrock. IEEE Transactions on Communications, Vol COM-32, No.3, pp 246-257, 1984. MFR: First proposition for Geometric Routing.
[KSU99]	Compass Routing on Geometric Networks. E. Kranakis, H. Singh, and J. Urrutia. In Proc. of the 11th Canadian Conference on Computational Geometry, Vancouver, British Columbia, Canada, August 1999. Face Routing: First correct algorithm.
[BMSU99]	Routing with Guaranteed Delivery in ad hoc Wireless Networks. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. In Proc. of the 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Seattle, Washington, USA, August 1999. GFG: First average-case efficient algorithm (with simulation).
[KH00]	GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. B. Karp and H. T. Kung In Proc. of the 6th Annual ACM/IEEE Int. Conf. on Mobile Computing and Networking (MOBICOM), Boston, Massachusetts, USA, August 2000. GPSR: Yet another simulation for GFG.
[KWZ02]	Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. F. Kuhn, R. Wattenhofer, and A. Zollinger. In Proc. of the 6th Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, Georgia, USA, September 2002. AFR: First worst-case analysis.
[KWZ03a]	Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. F. Kuhn, R. Wattenhofer, and A. Zollinger. In Proc. of the 4th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA, June 2003. GOAFR: Worst-case optimal and average-case efficient, percolation theory. Easier to read than [KWZZ03].
[KWZZ03]	Geometric Ad-Hoc Routing: Of Theory and Practice. F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003. GOAFR+: Currently best algorithm in theory, other cost metrics.
[KGKS05]	On the Pitfalls of Geographic Face Routing Y-J. Kim, R. Govindan, B. Karp, and S. Shenker. In Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany, September 2005. Experimentation with geographic routing in practical ad hoc networks.

Location Services

[AP91]	Concurrent online tracking of mobile users. B. Awerbuch and D. Peleg SIGCOMM '91: Proceedings of the conference on Communications architecture & protocols, 1991. The original location service.
[LJCK+00]	A Scalable Location Service for Geographic Ad Hoc Routing. J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, and R. Morris In Proc. of the 6th Annual ACM/IEEE Int. Conf. on Mobile Computing and Networking (MOBICOM), Boston, Massachusetts, USA, August 2000. GLS: A datastructure helping GFG or GOAFR to find the destination. More systemsy than [AP91].
[RKY+02]	GHT: a Geographic Hash Table for Data-Centric Storage S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker In Proc. of the First ACM International Workshop on Wireless Sensor Networks (WSNA), Atlanta, Giorgia, USA, September 2004. GHT: Hash data geographically, an idea later used by others [ADM04].
[ADM04]	LLS : a Locality Aware Location Service for Mobile Ad Hoc Networks I. Abraham, D. Dolev, and D. Malkhi In Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004. LLS: A competitive version of [LJCK+00].

Topology Control

[TK84b]	Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. H. Takagi and L. Kleinrock IEEE Transactions on Communications, 32(3):246-257, 1984. Originators of Topology Control.
[WLBW01]	Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang In Proc. of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Anchorage, Alaska, USA, April 2001. CBTC: The Cone-Based Topology Control algorithm. First attempt to have achieve several properties with a local algorithm.
[Raj02]	Topology Control and Routing in Ad hoc Networks: A Survey. R. Rajaraman SIGACT News, 33:60-73, June 2002. A survey on the early work.
[JV02]	A Power Control MAC Protocol for Ad Hoc Networks. E.-S. Jung and N. H. Vaidya In Proc. of the 8th Annual Int. Conf. on Mobile Computing and Networking (MOBICOM), Atlanta, Georga, USA, September 2002. Topology Control works in practice...?!
[LWWF02]	Sparse power efficient topology for wireless networks X.-Y. Li, P.-J. Wan, Y. Wang, and O. Frieder In Proc. of 35th Hawaii International Conference on System Sciences (HICSS), Big Island, Hawaii, USA, January 2002. A topology control structure based on the Yao Graph.
[BLRS03]	The k-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks. D. M. Blough, M. Leoncini, G. Resta, and P. Santi In Proc. of the 4th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA, June 2003. An analysis of the simplest topology control algorithm for random node distribution.
[BLRS03]	On Local Algorithms for Topology Control and Routing in Ad Hoc Networks. L. Jia, R. Rajaraman, and C. Scheideler In Proc. of the 15th Annual ACM Symp. on Parallel Algorithms and Architectures (SPAA), San Diego, California, USA, June 2003. An analysis of [LWWF02].
[WL03]	Localized Construction of Bounded Degree Planar Spanner for Wireless Ad Hoc Networks. Y. Wang and X.-Y. Li In Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA, September 2003. Bringing together many useful properties, e.g. a spanner with constant degree.
[CPS04]	On the Power Assignment Problem in Radio Networks. A. Clementi, P. Penna, and R. Silvestri Mobile Networks and Applications, 9(2):125-140, 2004. Several existence and inapproximability results.
[WZ04]	XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks. R. Wattenhofer and A. Zollinger In Proc. of the 4th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Santa Fe, New Mexico, April 2004. A generalization of the Relative Neighborhood Graph. Simple enough to be implementable.
[LSW04]	Localized Topology Control for Heterogeneous Wireless Ad-hoc Networks. X.-Y. Li, W.-Z. Song, and Y. Wang In Proc. of the 1st IEEE Int. Conf. on Mobile Ad-hoc and Sensor Systems (MASS), Fort Lauderdale, Florida, USA, October 2004. Considers the case where not all nodes have identical transmission radii, in particular mutual inclusion graphs.
[san05]	Topology Control in Wireless Ad Hoc and Sensor Networks. P. Santi A book about topology control.

Deployment / Initialization

[KMW04b]

Initializing Newly Deployed Ad Hoc and Sensor Networks. F. Kuhn, T. Moscibroda, and R. Wattenhofer In Proc. of the 10th Annual Int. Conf. on Mobile Computing and Networking (MOBICOM), Philadelphia, Pennsylvania, USA, September 2004. Introduces the unstructured radio network model that models newly deployed ad hoc and sensor networks. A good clustering can be computed efficiently in this model.

[MvRW06]

Analyzing the Energy-Latency Trade-off during the Deployment of Sensor Networks T. Moscibroda and P. von Rickenbach and R. Wattenhofer In Proc. of the 25st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Barcelona, Spain, 2006 Introduces a framework for analyzing the energy-latency trade-off of different deployment protocols and proposes two energy efficient protocols that provably exhibiting good trade-offs.

Lower Bounds

[Lin92]	Locality in Distributed Graph Algorithms. N. Lineal SIAM Journal on Computing, 21(1):193-201, 1992. The classic paper in locality. Shows, among other things, the non-trivial lower bound of Omega(log* n) for coloring a ring, thus the optimality of [CV86] or [KMW05].
[NS93]	What Can Be Computed Locally? M. Naor and L. Stockmeyer In Proc. of the 25th Annual ACM Symp. on Theory of Computing (STOC), San Diego, California, USA, 1993. Studies problems which can/cannot be locally computed in constant time.
[Pel00]	Distributed Computing: A Locality-Sensitive Approach. D. Peleg SIAM, 2000. Main text book on locality.
[PR00]	A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. D. Peleg and V. Rubinovich SIAM Journal on Computing, 30(5):1427-1442, 2000. Title says it all.
[KMW04a]	What Cannot Be Computed Locally! F. Kuhn, T. Moscibroda, and R. Wattenhofer In Proc. of the 23nd ACM Symp. on Principles of Distributed Computing (PODC), St. John's, Newfoundland, Canada, July 2004. Surprisingly high lower bounds for local algorithms. Results can be applied to many classic problems.
[Elk04a]	Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem. M. Elkin In Proc. of the 36th ACM Symp. on Theory of Computing (STOC), Chicago, Illinois, USA, June 2004. Improving [PR00].

MAC / Coloring

[CV86]	Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. R. Cole and U. Vishkin Information and Control, 70(1):32-53, 1986. An interesting coloring algorithm for rings and other low-degree graphs, shown to be optimal by [L02].
[Bia00]	Performance Analysis of the IEEE 802.11 Distributed Coordination Funcion. G. Bianchi IEEE Journal on Selected Areas in Communications, 2000. Performance evaluation of the 802.11 DCF using Markov Chains.
[ELRS03]	Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. G. Even, Z. Lotker, D. Ron, and S. Smorodinsky SIAM Journal on Computing, 33(1):94-136, 2003. A single non-interfering frequency is enough to decode some sender.
[MW06]	The Complexity of Connectivity in Wireless Networks. T. Moscibroda and R. Wattenhofer In Proc. of the 25st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Barcelona, Spain, 2006 In the worst-case, all commonly used (uniform and linear) power assignment policies inherently result in a disastrous MAC performance.

Dominating Sets

[GK96]	Approximation Algorithms for Connected Dominating Sets. S. Guha and S. Khuller In Proc. of the 4h Annual European Symp. on Algorithms (ESA), Barcelona, Spain, 1996. The optimal algorithm for CDS, not distributed.
[Fei98]	A Threshold of ln n for Approximating Set Cover. U. Feige Journal of the ACM (JACM), 45(4):634-652, 1998. Dominating sets cannot be approximated abritrarily well, unless P=NP (more or less).
[WL99]	On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks. J. Wu and H. Li In Proc. of the 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Seattle, Washington, USA, August 1999. Direct CDS algorithm that does not connect the DS the usual way. Done right it works fine for random UDG graphs. Bad worst-case though.
[GGHZ+01]	Discrete Mobile Centers. J. Gao, L. Guibas, J. Hershberger, L. Zahng, and A. Zhu In Proc. of the 17th Symp. on Computational Geometry (SCG), Medford, Massachusetts, USA, 2001. Fast O(loglog n) DS algorithm for UDGs if nodes know distances to neighbors.
[JRS01]	An Efficient Distributed Algorithm for Constructing Small Dominating Sets. L. Jia, R. Rajaraman, and R. Suel In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing (PODC), Newport, Rhode Island, USA, August 2001. Fast O(log n) distributed approximation for DS for general graphs.
[WAF02]	Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. P. Wan, K Alzoubi, and O. Frieder In Proc. of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), New York, New York, USA, June 2002. Maximal independent set, connected through 2- and 3-hop bridges. For UDGs, this is a constant approximation.
[KW03]	Constant-Time Distributed Dominating Set Approximation. F. Kuhn and R. Wattenhofer In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003. First local algorithm which achieves a non-trivial approximation ratio for general graphs.
[NH04]	A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. T. Nieberg and J.L. Hurink Memorandum 1732, Universiteit Twente, Dep't of Applied Mathematics, 2004. The name says it all. Algorithm is robust and works without geometric representation.
[KMW04b]	Initializing Newly Deployed Ad Hoc and Sensor Networks. F. Kuhn, T. Moscibroda, and R. Wattenhofer In Proc. of the 10th Annual Int. Conf. on Mobile Computing and Networking (MOBICOM), Philadelphia, Pennsylvania, USA, September 2004. Computing a dominating set in the unstructured radio network model.
[MW05a]	Maximizing the Lifetime of Dominating Sets. T. Moscibroda and R. Wattenhofer In Proc. of the 5th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, Colorado, April 2005. Shows that results on the domatic partition problem can be applied to extend the lifetime of a clustering in ad hoc and sensor networks.
[KMW05]	On the Locality of Bounded Growth. F. Kuhn, T. Moscibroda, and R. Wattenhofer In Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005. This paper proves that a MIS (as well as numerous other problems) can be computed in asymptotically optimal time O(log*n) in unit disk graphs and a large class of bounded independence graphs.
[MW05b]	Facility Location: Distributed Aproximation. T. Moscibroda and R. Wattenhofer In Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005. Studies the classic facility location problem in a distributed context and gives provable approximation guarantees. The facility location problem models energy efficient clustering in wireless networks.

Radio Networks

[Rob75]	Aloha Packet System with and without Slots and Capture. L. G. Roberts ACM SIGCOMM, Computer Communication Review, 5(2):28-42, 1975. Unslotted Aloha is only a constant worse than slotted Aloha.
[ABLP91]	A Lower Bound for Radio Broadcast. N. Alon, A. Bar-Noy, N. Linial, D. Peleg Journal of Computer and System Sciences, 43(2):290-298, August 1991. This paper proves a lower bound on radio network broadcast.
[BGI92]	On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap Between Determinism and Randomization. R. Bar-Yehuda, O. Goldreich, and A. Itai Journal of Computer and System Sciences, 45(1):104-126, August 1992. This classic establishes the first results on broadcast in radio networks.
[KM98]	An Ω(Dlog(N/D)) Lower Bound for Broadcast in Radio Networks. E. Kushilevitz and Y. Mansour SIAM Journal on Computing, 27(3):702-712, June 1998. A strong lower bound for broadcast in radio networks.
[GPP00]	The Wakeup Problem in Synchronous Broadcast Systems. L. Gasieniec, A. Pelc, and D. Peleg SIAM Journal on Discrete Mathematics, 14(2):207-222, 2001. Introduces the wake-up problem in radio networks.
[JS02]	Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. T. Jurdzindski and G. Stachowiak In Proc. of the 13th Int. Symp. on Algorithms and Computation (ISAAC), Vancouver, British Columbia, Canada, November 2002. The wake-up problem in single-hop radio networks analyzed in several different models. Among other things this paper shows that nodes need an estimate about the number of nodes in the network to structure the network efficiently.
[KMW04b]	Initializing Newly Deployed Ad Hoc and Sensor Networks. F. Kuhn, T. Moscibroda, and R. Wattenhofer In Proc. of the 10th Annual Int. Conf. on Mobile Computing and Networking (MOBICOM), Philadelphia, Pennsylvania, USA, September 2004. There are more things than broadcast.

Maximal Independent Sets

[Lub86]	A Simple Parallel Algorithm for the Maximal Independent Set Problem. M. Luby SIAM Journal on Computing, 15:1036-1053, 1986. Beautiful local O(log n) algorithm for MIS on general graphs.
[MW05c]	Maximal Independent Sets in Radio Networks. T. Moscibroda and R. Wattenhofer In Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005. Studies the distributed complexity of computing a MIS in the unstructured radio network model (asynchronous wake-up, no collision detection, scarce knowledge about the network topology, etc.).
[KMNW05]	Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer In Proc. of the 19th Int. Symp. on Distributed Computing (DISC), Cracow, Poland, September 2005. Shows that a MIS can be computed deterministically in time O(log*n log Delta) in networks with bounded independence, such as unit disk graphs.

Spanning Structures

[GHS83]	A Distributed Algorithm for Minimum-Weight Spanning Trees. R. G Gallager, P. A. Humblet, and P. M. Spira ACM Transactions on Programming Languages and Systems, 5:66-77, 1983 The classic distributed minimum spanning tree algorithm.
[Awe87]	Optimal Distributed Algorithms for Minimum-Weight Spanning Tree, Counting, Leader Election and related problems. B. Awerbuch In Proc. of the 19th Annual ACM Symp. on Theory of Computing (STOC), New York, New York, USA, May 1987. Improving [GHS83].
[ABP90]	Cost-Sensitive Analysis of Communication Protocols. B. Awerbuch, A. Baratz, and D. Peleg In Proc. of the 9th ACM Symp. on Principles of Distributed Computing (PODC), Quebec City, Quebec, Canada, July 1990. Introduces the Shallow-Light Tree which is a constant approximation for the MST and for the SPT at the same time.
[KRY93]	Balancing Minimum Spanning Trees and Shortest-Path Trees. S. Khuller, B. Raghavachari, and N. Young In Proc. of the 15th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), Austin, Texas, USA, January 1993. Improved version of [ABP90] with new name: Light Approximate Shortest-Path Tree.
[PR00]	See Lower Bounds
[CCPR+01]	On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. A. Clementi, P. Crescenzi, P. Penna, G. Rossi, and P. Vocca In Proc. of the 18th Annual Symp. on Theoretical Aspects of Computer Science (STACS), Dresden, Germany, February 2001. The authors show that the problem is in NP, that there exists no PTAS and give a constant approximation.
[WCLF01]	Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks. P.-J. Wan, G. Calinescu, X.-Y. Li, and O. Frieder In Proc. of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Anchorage, Alaska, USA, April 2001. Analysis of three heuristics.
[Elk04a]	See Lower Bounds
[Elk04b]	A Faster Distributed Protocol for Constructing a Minimum Spanning Tree. M. Elkin In Proc. of the 15th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), New Orleans, Louisiana, USA, January 2004. Title says it all.
[Amb05]	An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. C. Amb�hl In Proc. of the 32nd Int. Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005. Thight analysis for the MST-based approximation algorithm.

Positioning / Virtual Coordinates

[BK98]	Unit Disk Graph Recognition is NP-hard. H. Breu and D. G. Kirkpatrick Computational Geometry: Theory and Applications, 9(1-2):3-24, 1998. Proved that finding a UDG embedding is NP-hard.
[RRPS+04]	Geographic Routing without Location Information. A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica In Proc. of the 9th Annual Int. Conf. on Mobile Computing and Networking (MOBICOM), San Diego, California, USA, September 2003. Proposing Virtual Coordinates for Geo-Routing. (Not really an algorithms paper, though.)
[BW04]	Analyzing Connectivity-Based, Multi-Hop Ad-hoc Positioning. R. Bischoff and R. Wattenhofer In Proc. of the 2nd IEEE Int. Conf. on Pervasive Computing and Communications (PerCom), Orlando, Florida, USA, March 2004. Optimal 1D positioning algorithm, improved 2D.
[LdAP04]	Range-Free Ranking in Sensor Networks and Its Applications to Localization. Z. Lotker, M. M. de Albeniz, and S. Perennes In Proc. of the Ad-Hoc, Mobile, and Wireless Networks: Third International Conference (ADHOC-NOW), Vancouver, British Columbia, Canada, July 2004.
[AGY04]	On the Computational Complexity of Sensor Network Localization. J. Aspnes, D. Goldberg, and Y. R. Yang In Proc. of the 1st Intl. Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), Turku, Finland, July 2004. Proved that even when knowing the exact distances of the edges finding such an embedding of a UDG is hard, thus improving on [BK98].
[MOWW04]	Virtual Coordinates for Ad hoc and Sensor Networks. T. Moscibroda, R. O'Dell, M. Wattenhofer, and R. Wattenhofer In Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004. First algorithm for virtual coordinates with high probability guaranteed upper bound.
[KMW04c]	Unit Disk Graph Approximation. F. Kuhn, T. Moscibroda, and R. Wattenhofer In Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004. Even closely approximating a UDG is hard.
[BGJ05]	Localization and Routing in Sensor Networks by Local Angle Information. J. Bruck, J. Gao, and A. A. Jiang In Proc. of the 6th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), Urbana-Champaign, Illinois, USA, May 2005. Even if angle information is available, quasi UDG embedding is hard; a linear-programming-based heuristic produces good results if angle information is available.

Time Synchronization

[ST87]	Optimal Clock Synchronization. T. K. Srikanth and S. Toueg Journal of the ACM (JACM), 34(3):626-645, 1987. Clock synchronization is easy.
[PSR94]	A Theory of Clock Synchronization. B. Patt-Shamir and S. Rajsbaum In Proc. of the 26th Annual ACM Symp. on Theory of Computing (STOC), Montr�al, Qu�bec, Canada, May 1994. Still easy.
[FL04]	Gradient Clock Synchronization. R. Fan and N. Lynch In Proc. of the 23nd ACM Symp. on Principles of Distributed Computing (PODC), St. John's, Newfoundland, Canada, July 2004. Oops, it might not be so easy after all. In particular a surprising non-trivial lower bound which grows with the diameter of the network is shown.
[MT05]	Gradient Clock Synchronization in Sensor Networks. L. Meier and L. Thiele In Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005. A first follow-up of [FL04].

Models

[SW06]

Algorithmic Models for Sensor Networks. S. Schmid and R. Wattenhofer In Proc. of the 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), Island of Rhodes, Greece, April 2006. Puts into perspective the various connectivity and interference models in use today.

Data Gathering

[NSU97]	Efficient distributed selection with bounded messages. A. Negro, N. Santoro, and J. Urrutia IEEE Transactions on Parallel and Distributed Systems, April 1997. Efficiently computing the median of a set. Not quite as easy as min, max, or average.
[KNR02]	Control Message Aggregation in Group Communication Protocols. S. Khanna, S. Naor, and D. Raz In Proc. of the 29th International Colloquium of Automata, Languagues and Programming (ICALP), Malaga, Spain, July 2002. Data gathering as an online problem.
[GE03]	Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at Bulk. A. Goel and D. Estrin In Proc. of the 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), Baltimore, Maryland, USA, January 2003. Proposes an approximation algorithm yielding an aggregation tree for a class of aggregation functions simultaneously.
[vRW04]	Gathering Correlated Data in Sensor Networks. P. von Rickenbach and R. Wattenhofer In Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004. By considering data correlation explicitly, algorithms for two coding strategies are provided.
[JLNR+05]	Universal Approximations for TSP, Steiner Tree and Set Cover. L. Jia, G. Lin, G. Noubir, R. Rajaraman, R. Sundaram In Proc. of the 37th ACM Symp. on Theory of Computing (STOC), Baltimore, Maryland, USA, May 2005. An instant classic: Among other things, the paper presents a method to compute a fixed Steiner tree which is efficient no matter what subset of nodes are answering a query. Good approximation especially for constant doubling metrics.

Interference

[MSVG02]	Energy, Congestion and Dilation in Radio Networks. F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, and M. Gruenewald In Proc. of the 14th Annual ACM Symp. on Parallel Algorithms and Architectures (SPAA), Winnipeg, Manitoba, Canada, August 2002. This paper shows that you cannot have all three, good energy routes, little interference, and a few hops.
[BvRWZ04]	Does Topology Control Reduce Interference? M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger. In Proc. of the 5th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), Roppongi Hills, Tokyo, Japan, May 2004. Classic topology control algorithms that include the nearest neighbors might not be all that good after all.
[vRSWZ05]	A Robust Interference Model for Wireless Ad-Hoc Networks. P. von Rickenbach, S. Schmid, R. Wattenhofer, and A. Zollinger In Proc. of the 5th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, Colorado, April 2005. A first try to modify the model of [BvRWZ04].
[MW05]	Minimizing Interference in Ad Hoc and Sensor Networks. T. Moscibroda and R. Wattenhofer In Proc. of the 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany, September 2005. Presents a centralized algorithm to reduce average interference.
[MW06]	The Complexity of Connectivity in Wireless Networks. T. Moscibroda and R. Wattenhofer In Proc. of the 25st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Barcelona, Spain, 2006 The first paper studying the interplay between interference and scheduling on the SINR level

Routing

[GB81]	Distributed algorithms for generating loop-free routes in networks with frequently changing topology. E. M. Gafni and D. P. Bertsekas IEEE Transactions on Communication, 29, 1981. An original algorithmic routing idea, which seems more suitable for highly mobile networks.
[Pra99]	Unidirectional Links Prove Costly in Wireless Ad-Hoc Networks. R. Prakash In Proc. of the 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Seattle, Washington, USA, August 1999. Not many people looked at unidirectional links after this paper.
[BST03]	Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks. C. Busch, S. Surapaneni, and S. Tirthapura In Proc. of the 15th Annual ACM Symp. on Parallel Algorithms and Architectures (SPAA), San Diego, California, USA, June 2003. A nice analysis of [GB81].
[AHKR05]	Provably Competitive Adaptive Routing. B. Awerbuch, D. Holmer, R. Kleinberg, and H. Rubens In Proc. of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Miami, USA, March 2005.

Transport Layer

[KKPS00]	Optimization Problems in Congestion Control. R. Karp, E. Koutsoupias, Ch. Papadimitriou, and S. Shenker In Proc. of the 33rd Annual ACM Symp. on Theory of Computing (FOCS), Redondo Beach, California, USA, November 2000. How to guesstimate the available bandwidth efficiently. (Not really Sensor/Ad Hoc Networks though.)
[KKR01]	Dynamic TCP Acknowledgement and Other Stories about e/(e-1). A. Karlin, C. Kenyon, and D. Randall In Proceedings of the 41st Annual Symp. on Foundations of Computer Science (STOC), Heraklion, Crete, Greece, July 2001 How to send ACKs efficiently. (Not really Sensor/Ad Hoc Networks though.)
[KNR02]	Control Message Aggregation in Group Communication Protocols. S. Khanna, S. Naor, and D. Raz In Proc. of the 29th International Colloquium of Automata, Languagues and Programming (ICALP), Malaga, Spain, July 2002. [KKR01] extended for data gathering.

Information Theoretic Aspects

[GK00]

The Capacity of Wireless Networks. P. Gupta and P. R. Kumar IEEE Transactions on Information Theory, 46(2):388-404, 2000. The classic capacity paper which spawned a whole industry of follow-ups. Not really an algorithmic paper, though.

[MW06]

The Complexity of Connectivity in Wireless Networks. T. Moscibroda and R. Wattenhofer In Proc. of the 25st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Barcelona, Spain, 2006 To some extent an algorithmic (worst-case) analogon of [GK00]. It shows that even in worst-case node distributions a strongly connected component can be scheduled efficiently. Hence, in theory, there exists no fundamental scaling problem.

Responsible: P. von Rickenbach © Distributed Computing Group

© 2024 DISCO, TIK, ETH Zurich | Imprint | Last updated: Mon, 31 Aug 2020 21:02.