Course Readings:

The text:

F. Zhao and L. Guibas. Wireless Sensor Networks: An Information Processing Approach. Elsevier/Morgan-Kaufmann, 2004

Additional Readings:

Week 1

Monday, 24 September 2007. Introduction

• Read chapter 1 of the text.
• Overview papers:
  • D. Culler, D. Estrin, M.Srivastava. Overview of Sensor Networks, IEEE Computer Magazine, Aug. 2004.
  • David E. Culler, Wei Hong. Wireless Sensor Networks. Communications ACM, 47 (6): 30-33, July 2004.
  • David E. Culler and Hans Mulder. Smart Sensors to Network the World. Scientific American, June 2004.

Wednesday, 26 September 2007. Wireless Links and Communication Modelseless Links and Communication Models

• Relevant papers:
  • Dongjin Son, Bhaskar Krishnamachari, John Heidemann, Experimental Analysis of Concurrent Packet Transmissions in Low-Power Wireless Networks, ACM Sensys, November 2006.
  • Marco Zuniga, Bhaskar Krishnamachari, An Analysis of Unreliability and Asymmetry in Low-Power Wireless Links, ACM Transactions on Sensor Networks, 2007.
  • Massimo Franceschetti, Lorna Booth, Matthew Cook, Ronald Meester, and Jehoshua Bruck, Continuum Percolation with Unreliable and Spread out Connections, Journal of Statistical Physics, v. 118, N. 3-4, February 2005, pp. 721-734.
  • Alec Woo, Terence Tong, David E. Culler, Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks. ACM SenSys, 2003, pp.14-27.
  • D. Kotz, C.  Newport, C. Elliott, The Mistaken Axioms of Wireless-Network Research, Dartmouth College Computer Science Technical Report, TR2003-67, 2003.
  • Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip Levis, Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks. Technical Report SING-06-00. Stanford, 2006.
  • Thomas Moscibroda, The Worst-Case Capacity of Wireless Sensor Networks. ACM IPSN, 2007, pp.1-10.
  • Paolo Santi. Topology Control in Wireless Ad Hoc and Sensor Networks. ACM Comput. Surv. 37, 2 (Jun. 2005), pp. 164-194.

Week 2

Monday, 01 October 2007. Networking Sensors I: Geographic Routing eless Links and Communication Models

• Read chapter 3 of the text.
• Relevant papers:
  • E. Kranakis, H. Singh and J. Urrutia, Compass Routing on Geometric Networks. Proc. 11-th Canadian Conference on Computational Geometry, Vancouver, August, 1999.
  • Karp, B. and Kung, H.T., Greedy Perimeter Stateless Routing for Wireless Networks.Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254.
  • Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Asymptotically Optimal Geometric Mobile Ad-Hoc Routing.6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, Georgia, September 2002.
    
  • Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA, June 2003.
    
  • Fabian Kuhn, Roger Wattenhofer, Yan Zhang, and Aaron Zollinger. Geometric Ad-Hoc Routing: Of Theory and Practice. 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003.

Wednesday, 03 October 2007. Networking Sensors II: More on Geographic Routing eless Links and Communication

• Read chapter 3 of the text.
• Relevant papers:
  • Y. -J. Kim, R. Govindan, B. Karp, S. Shenker, On the Pitfalls of Geographic Routing, Proc. of the 3rd International Workshop on DIALM-Principles of Mobile Computing, September 2005.
  • Y.-J. Kim, R. Govindan, B. Karp, S. Shenker, Geographic Routing Made Practical, Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI) , pp. 217--230, May 2005.
  • Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Shenker, Lazy Cross-Link Removal for Geographic Routing, Proceedings of the ACM Sensys, November 2006.
  • Rao, A., Ratnasamy, S., Papadimitriou, C., Shenker, S., and Stoica, I.. Geographic Routing Without Location Information. In Proceedings of the 9th Annual international Conference on Mobile Computing and Networking (San Diego, CA, USA, September 14 - 19, 2003). MobiCom '03. ACM Press, New York, NY, 96-108.
    
  • Ben Leong, Barbara Liskov, and Robert Morris, Geographic Routing without Planarization. Proceedings of the 3rd Symposium on Network Systems Design and Implementation (NSDI 2006). San Jose, CA, May 2006.

Week 3

Monday, 08 October 2007. Programming Sensor Networks: nesC, TinyOS, TOSSIM [Kusy]

• Read chapter 7 of the text.
• Relevant papers:
  • J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, K. Pister, System Architecture Directions for Network Sensors, ASPLOS 2000, , Cambridge, November 2000.
  • D. E. Culler, J. Hill, P. Buonadonna, R. Szewczyk, A. Woo, A Network-Centric Approach to Embedded Software for Tiny Devices, EMSOFT 2001, Oct 2001.
  • D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler, The nesC Language: A Holistic Approach to Networked Embedded Systems, Proceedings of the Programming Language Design and Implementation (PLDI), June 2003.
  • P. Levis, N. Lee, M. Welsh, and D. Culler, TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications. Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2003.
  • David Gay, Philip Levis, and David Culler, Software Design Patterns for TinyOS, Proceedings of ACM SIGPLAN/SIGBED 2005 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'05), Chicago, June 2005.

Wednesday, 10 October 2007. Networking Sensors III: Landmark Methods eless Links and Communicati

• Read .
• Relevant papers:
  • Q. Fang, J. Gao, L. J. Guibas, V. de Silva, L. Zhang. GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks, 24th Conference of the IEEE Communications Society (InfoCom), 2005.
  • S. Funke, L. Guibas, A. Nguyen, and Y. Wang. Distance-Sensitive Information Brokerage in Sensor Networks, Proc. Int. Conference on Distributed Computing in Sensor Systems (DCOSS), pp 234-251, 2006.
  • R. Fonseca, S. Ratnasamy, J. Zhao, C. Tien Ee, D. Culler, S. Shenker and I. Stoica. Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets. Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI), Boston, 2005.
    
  • Jehoshua Bruck, Jie Gao, Anxiao Jiang, MAP: Medial Axis Based Geometric Routing in Sensor Networks, Proc. of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom’05), 88-102, August, 2005. Journal version invited to Wireless Networks (WINET) special issue from MobiCom'05.

Week 4

Monday, 15 October 2007. Information Discovery: Directed Diffusion and GHTs

• Read chapters 3, 4 of the text.
• Relevant papers:
  • Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J., and Silva, F. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Trans. Netw. 11, 1 (Feb. 2003), 2-16.
  • Ratnasamy, S., Karp, B., Shenker, S., Estrin, D., Govindan, R., Yin, L., and Yu, F. Data-Centric Storage in Sensornets with GHT, a Geographic Hash Table. Mob. Netw. Appl. 8, 4 (Aug. 2003), 427-442.

Wednesday, 17 October 2007. Double Rulings, Location Services, Q-Digests

• Read chapters 3, 4 of the text.
• Relevant papers:
  • Rik Sarkar, Xianjin Zhu, Jie Gao, Double Rulings for Information Brokerage in Sensor Networks, The 12th Annual ACM Conference on Mobile Computing and Networking (MobiCom'06), 286-297, September, 2006.
  • Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger, and Robert Morris, A Scalable Location Service for Geographic Ad Hoc Routing, ACM Conference on Mobile Computing and Networking (MobiCom'00), Boston, Massachusetts.
  • Nisheeth Shrivastava, Chiranjeeb Buragohain, Divy Agrawal, Subhash Suri. Medians and Beyond: New Aggregation Techniques for Sensor Networks. ACM SenSys '04, Nov. 3-5, Baltimore, MD.

Week 5

Monday, 22 October 2007. Information Aggregation, Sensor Data Bases; TinyDB

• Read chapter 6 of the text.
• Relevant papers:
  • Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks. SIGOPS Oper. Syst. Rev. 36, SI (Dec. 2002), 131-146.
  • Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. The Design of an Acquisitional Query Processor for Sensor Networks. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pp 491-502.
  • Joseph M. Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek. Beyond Average: Towards Sophisticated Sensing with Queries. In Proceedings of the 2nd International Conference on Information Processing in Sensor Networks (IPSN), Palo Alto, California, USA, April 22-23, 2003, pp 63-79.
  • Madden, S. R., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2005. TinyDB: an Acquisitional Query Processing System for Sensor Networks. ACM Trans. Database Syst. 30, 1 (Mar. 2005), 122-173.
  • Deepak Ganesan, Deborah Estrin, and John Heidemann, DIMENSIONS: Why do we need a new Data Handling architecture for Sensor Networks?, Proceedings of the ACM Workshop on Hot Topics in Networks, pp. 143-148. Princeton, NJ, USA, ACM. October, 2002.
  • Deepak Ganesan, Ben Greenstein, Denis Perelyubskiy, Deborah Estrin and John Heidemann, An Evaluation of Multi-resolution Storage for Sensor Networks In Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003).

Wednesday, 24 October 2007. Distributed Probabilistic Reasoning, Regression

• Relevant papers:
  • A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, W.Hong. Model-Driven Data Acquisition in Sensor Networks. In the 30th International Conference on Very Large Data Bases (VLDB 2004), Toronto, Canada, August 2004.
  • A. Deshpande, C. Guestrin, W. Hong, S. Madden. Exploiting Correlated Attributes in Acquisitional Query Processing. In the 21st International Conference on Data Engineering (ICDE 2005), Tokyo, Japan, April 2005.
  • Carlos Guestrin, Peter Bodik, Romain Thibaux, Mark Paskin, Samuel Madden. Distributed Regression: an Efficient Framework for Modeling Sensor Network Data. In Information Processing in Sensor Networks (IPSN 2004), Berkeley, April 2004.
  • Mark Paskin, Carlos Guestrin and Jim McFadden. A Robust Architecture for Distributed Inference in Sensor Networks. In the Fourth International Conference on Information Processing in Sensor Networks (IPSN'05), April 2005.

Week 6

Monday, 29 October 2007. Synopsis Diffusion and Other Order-and-Duplicate Insenstive Aggregation Schemes [Skraba]

• Relevant papers:
  • Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, and Zachary Anderson, Synopsis Diffusion for Robust Aggregation in Sensor Networks. ACM Sensys (2004) .
  • Suman Nath, Phillip B. Gibbons, Srinivasan Seshan, and Zachary Anderson, Synopsis Diffusion for Robust Aggregation in Sensor Networks. Technical Report IRP-TR-04-13 Intel Research Pittsburgh, PA, April 2004 .
  • P. Flajolet and G. N. Martin, Probabilistic counting algorithms for database applications. Journal of Computer and System Sciences 31, (1985), 189-209 .
  • R. Morris Counting large numbers of events in small registers Communications of the ACM 21,10 (Oct. 1978), 840-842.
  • Edith Cohen, Size-estimation framework with applications to transitive closure and reachability Journal of Computer and System Sciences 55 ,3, (Dec. 1997) 441-453 .
  • N. Alon, Y. Matias, and M. Szegedy The space complexity of approximating the frequency moments J. of Computer and System Sciences 58, (1999), 137-147.
  • Z. Bar-Yossef, R. Kumar, and D. Sivakumar Sampling algorithms: lower bounds and applications ACM STOC (2001).

Wednesday, 31 October 2007. Gossiping; Coding

• Relevant papers:
  • Lin Xiao, Stephen Boyd, Fast Linear Iterations for Distributed Averaging, Systems and Control Letters, 2004.
  • Lin Xiao, Stephen Boyd and Sanjay Lall, A Scheme for Robust Distributed Sensor Fusion Based on Average Consensus, IPSN'05, 2005.
  • S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, Gossip Algorithms: Design, Analysis and Applications, INFOCOM'05.
  • A. G. Dimakis, V. Prabhakaran and K. Ramchandran, Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes, Symposium on Information Processing in Sensor Networks (IPSN'05), April, 2005.
  • R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, Network Information Flow, IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000.
  • C. Fragouli, J. Le Boudec, Jorg Widmer, Network coding: an instant primer.

Week 7

Monday, 5 November 2007. Localization I

• Read chapter, 4 of the text.
• Relevant papers:
  • A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. Proc. MobiCom 2001.
  • Andreas Savvides, and Mani B. Strivastava. Distributed Fine-Grained Localization in Ad-Hoc Networks. IEEE Transactions of Mobile Computing,  to appear, 2003.
  • Tolga Eren, David Goldenberg,  Walter Whitley, Yang Richard Yang, A. Stephen Morse, Brian D.O. Anderson and Peter N. Belhumeur, Rigidity, Computation, and Randomization of Network Localization. In Proceedings of IEEE INFOCOM, Hong Kong, China, April 2004.
  • D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, Proc. ACM SenSys 2004.
  • Yi Shang, Wheeler Ruml, Ying Zhang, and Markus P.J. Fromherz, Localization from Mere Connectivity, MobiHoc 2003.

Wednesday, 7 November2007. Localization II

• Read chapter, 4 of the text.
• Relevant papers:
  • He, T., Huang, C., Blum, B. M., Stankovic, J. A., and Abdelzaher, T. Range-free localization schemes for large scale sensor networks. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (San Diego, CA, USA, September 14 - 19, 2003). MobiCom '03.
  • Koen Langendoen, Niels Reijers. Distributed localization in wireless sensor networks: a quantitative comparison. Computer Networks 43 (2003) 499–518.

Week 8

Monday, 12 November 2007. Midterm

Wednesday, 14 November 2007. Time Synchronization [Kusy]

• Read chapter, 4 of the text.
• Relevant papers:
  • J. Elson and K. Romer, Wireless sensor networks: a new regime for time synchronization, HotNets-I 2002, Princeton, October 2002.
  • J. Elson, L. Girod, and D. Estrin, Fine-grained network time synchronization using reference broadcasts, OSDI 2002, Boston, December 2002.
  • S. Ganeriwal, R. Kumar, and M. B. Srivastava, Timing-sync protocol for sensor networks, SenSys 2003, November 2003.
  • M. Maroti, B. Kusy, G. Simon, and A. Ledeczi, The flooding time synchronization protocol, SenSys 2004, Baltimore, November 2004.
  • Simon, G., Maróti, M., Lédeczi, Á., Balogh, G., Kusy, B., Nádas, A., Pap, G., Sallai, J., and Frampton, K., Sensor Network-Based Countersniper System, SenSys 2004, Baltimore, November 2004.

Week 9

Monday, 26 November 2007. Sensor Tasking and Control

• Read chapter, 5 of the text.
• Relevant papers:
  • Andreas Krause and Carlos Guestrin; Near-Optimal Nonmyopic Value of Information in Graphical Models; 21st Conference on Uncertainty in Artificial Intelligence (UAI 2005), Edinburgh, July 2005.
  • Carlos Guestrin, Andreas Krause and Ajit Singh; Near-Optimal Sensor Placements in Gaussian Processes; 22nd International Conference on Machine Learning (ICML 2005), Bonn, August 2005.
  • Andreas Krause, Carlos Guestrin, Anupam Gupta, Jon Kleinberg; Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost; Fifth International Conference on Information Processing in Sensor Networks (IPSN'06), April 2006.
  • Andreas Krause and Carlos Guestrin; Near-optimal Observation Selection Using Submodular Functions; survey paper for the Nectar track in the 22nd Conference on Artificial Intelligence (AAAI), Vancouver, July 2007.
  • Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen and Natalie Glance; Cost-Effective Outbreak Detection in Networks; 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), San Jose, August 2007.

Wednesday, 28 November 2007. State Estimation and Tracking

• Read chapter, 4 of the text.
• Relevant papers:
  • S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. MIT Press, Cambridge, MA, 2005.
  • Maurice Chu, Horst Haussecker, and Feng Zhao, Scalable Information-Driven Sensor Querying and Routing for ad hoc Heterogeneous Sensor Networks. Int'l J. High Performance Computing Applications, 16(3):90-110.
  • F. Zhao, J. Liu, J. Liu, L. Guibas, and J. Reich, Collaborative Signal and Information processing: an Information-Directed Approach, Proceedings of the IEEE, 91, 8, pp. 1199- 1209, 2003.
  • Q. Fang, F. Zhao, and L. Guibas, Lightweight Sensing and Communication Protocols for Target Enumeration and Aggregation, the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc), 2003, pp. 165-176.
  • J. Shin, L. Guibas and F. Zhao, Distributed Algorithm for Managing Multi-Target Identities in Wireless Ad-hoc Sensor Networks. 2nd Int'l Workshop on Information Processing in Sensor Networks (IPSN) 2003, pp. 223-238.