Tuesday and Thursday, 3:50-5:10pm, Stony Brook Union 231.

Instructors: 

Instructor: Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Thursday 5:20-6:30pm or by appointment.

Announcements:

1. We will have project presentation on May 5^th and 7^th. Project report is due May 8^th.
2. No class on April 7^th and 9^th. April 14^th we will have an invited speaker. The class will be moved to CS2311.
3. Project topic is due on 3/10/09. Please email me a paragraph describing your project idea.
4. Homework 1 is out on 2/24/09, due 2 weeks later.
5. Project ideas will be handed out on Tuesday, 2/10/09.
6. Extreme Sensing competition at IPSN’09. Travel fund will be available for class projects to participate. Please let me know if you would like to attend.
7. The first class is on Jan 27th. See you there!

Course Description:

This course is a 3-credit graduate course on the recent progress in wireless sensor networks. A wireless sensor network consists of a large number of autonomous, small-size, inexpensive sensor nodes that can communicate with each other by wireless radios. Networked sensor systems of large scale are becoming available in the foreseeable future, providing economical and practical solutions for data collection and environment monitoring, especially in hostile, inaccessible environments or emergent situations. Sensor networks have the potential to revolutionize the way we observe, interact with and influence the physical world. The major technical challenges of sensor networks include scalable network self-organization, as well as efficient processing of the massive amount of spatially and temporally distributed data, under the constraint of limited computation and communication resources.

This course will focus on the algorithmic issues for wireless sensor networks involved in important networking and data processing functions, such as

• network modeling, connectivity,
• network localization,
• geometric routing,
• information aggregation,
• information storage and query,
• optimization and function evaluation via gossip algorithms,
• mobility.

Algorithms for sensor networks face a number of challenges.

• Sensor nodes typically only have local views and have no knowledge of the global network state, or even the location of itself. Thus localized, distributed algorithms are always preferred if not required;
• Sensor nodes may die. Communication links are not stable. System robustness is an indispensable consideration.
• Sensor data is noisy, due to sensor malfunction or packet loss during communication. Thus data-processing algorithms need to be robust to noises and outliers in the input.
• Sensor nodes have limited resources in terms of energy, computation and communication. Any algorithms for large-scale sensor networks should be simple, distributed and light-weight.

The lectures will be self-contained so no prior knowledge on those topics is required. Prerequisites include undergraduate networking, algorithm and probability courses or consult with the instructor. Previous years’ offerings: Fall 2005, Fall 2006.

Auditors are welcome!

Course Materials:

Most of the materials used in this course are technical papers. See the reading list below. Some recommended textbooks:

• Wireless Sensor Networks: An Information Processing Approach by F. Zhao and L. Guibas, Elsevier/Morgan-Kaufmann, 2004. The book is put on 2-hours reserve in computer science library.
• Networking Wireless Sensors by Bhaskar Krishnamachari, Cambridge University Press, 2005.
• An FDL'ed Textbook on Sensor Networks, by Thomas Haenselmann. The book is available online.

Grading and Requirements:

We expect to have an interactive class. Grading includes class participation (20%), homework (30%) and a final project (50%). There are no exams. Students are required to finish the “required readings” (typically 1-2 papers) before class. Class participation includes class attendance and paper presentation.

Paper presentation: each student will be asked to present at least 1 paper in class. The presentation is 20-30 mins. Students will be evaluated by the audience, in terms of slides quality, presentation clarity and audience engagement. 

For the final projects, students may form a group of two and choose either the theory track or the applied track.  A project on theory track involves identifying a topic of interest, related to one of the topics covered in the class, formulating it into a mathematical problem and solving it. An applied track project will involve identifying a topic of interest, and simulation/implementation of an algorithm and performance evaluation, and a final report on your discovery. Evaluation will be based on the result significance and the final report quality. At the end of the semester students are expected to make a 30 minutes presentation on their projects in class. There will also be a midterm progress check by which the students are expected to find a topic, and make a presentation about preliminary work, and get feedback from the class. 

Possible project ideas will be distributed in class in the first few weeks. You are highly encouraged to discuss with me about your project ideas. In Fall 2005 offering, a number of successful projects have turned into publications in the best networking conferences such as ACM Mobicom and MobiHoc.

Syllabus:

Reading List (To be updated):

Overview

• [Estrin99] D. Estrin, R. Govindan, J. S. Heidemann, and S. Kumar. Next century challenges: Scalable coordination in sensor networks, In Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99).
• [Culler04] D. Culler, D. Estrin, M.Srivastava. Overview of Sensor Networks, IEEE Computer, Aug. 2004
• [Hill04] J. Hill, M. Horton, R. Kling, and L. Krishnamurthy. The Platforms Enabling Wireless Sensor Networks, Communications of the ACM, Volume 47, Issue 6, pp. 41-46, June 2004.
• [TinyOS] http://www.tinyos.net/.

Localization:

• [Savvides01] A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In MobiCom 01: Proceedings of the 7th ACM Annual International Conference on Mobile Computing and Networking, pages 166-179, 2001. The basic trilateration scheme: compute the location of a node by using the distances to at least three anchor nodes.
• [Graver93] J. Graver, B. Servatius, and H. Servatius, Combinatorial Rigidity, Chapter 1, volume 2, Graduate Studies in Mathematics, Amer. Math. Soc., 1993. Introduction to rigidity theory (graph rigidity, generic rigidity, infinitesimal rigidity, etc).
• [Jacobs97] D. J. Jacobs and B. Hendrickson, An Algorithm for two dimensional rigidity percolation: The pebble game. J. Comput. Phys., 137:346-365, 1997. Pebble game algorithm: O(nm) algorithm to test whether a graph is rigid or not.
• [Eren04] 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. The first time that rigidity theory is used for sensor network localization. A greedy algorithm to localize trilateration graphs.
• [Moore04] D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, Proc. ACM SenSys 2004. Anchor-free algorithm by patching up robust quadrilaterals --- the quadrilaterals that are unlikely to have a local flip.
• [Shang03] Yi Shang, Wheeler Ruml, Ying Zhang, Markus P.J. Fromherz, Localization from Mere Connectivity, MobiHoc'03. Multi-dimensional scaling and its application in network localization.
• [Lederer08] Sol Lederer, Yue Wang, Jie Gao, Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape, INFOCOM’08. Use combinatorial Delaunay complex for anchor-free localization. The intuition is that two adjacent Delaunay triangles must be embedded side-by-side.
• [Lee08] HyungJune Lee, Martin Wicke, Branislav Kusy, Leonidas Guibas, Localization of Mobile Users Using Trajectory Matching, ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments, MELT 2008. Fingerprinting approach but uses a short history of the signals from infrastructure nodes.
• [Zhong07] Ziguo Zhong, Tian He, MSP: Multi-Sequence Positioning of Wireless Sensor Nodes, Sensys07. Use simply distance comparisons for localization.

Location-based routing:

• [Bose01] P. Bose, P. Morin, I. Stojmenovic and J. Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, 7(6), 609-616, 2001. One of the first papers on greedy forwarding + face routing to guarantee delivery in ad hoc networks.
• [Karp00] Karp, B. and Kung, H.T., Greedy Perimeter Stateless Routing for Wireless Networks, in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254. GPSR: one of the first on geographical routing.
• [Kuhn03] F. Kuhn, R. Wattenhofer, Y. Zhang, A. Zollinger, Geometric Ad-hoc routing: of theory and practice, in PODC'03. How to find a short path with geographical routing?
• [Gao01] J. Gao, L. Guibas, J. Hershberger, L. Zhang, A. Zhu, Geometric Spanner for Ad hoc Mobile Networks, in MobiHoc'01. Develop a planar subgraph from a unit disk graph that is also a planner spanner, i.e., having paths that are at most a constant factor longer than the shortest path in the original graph.
• [Kim05] Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S., On the Pitfalls of Geographic Face Routing, The third International workshop on foundations of mobile computing (DIAL-M-POMC'05), 2005. Geographical routing in practice fails, because the planar subgraph extraction is not perfect.
• [Frey06] Hannes Frey, Ivan Stojmenovic, On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks, Mobicom’06. An in-depth study of the local rules used in variations of face routing. Conclusion: it is subtle! Please pay attention during implementation.
• [Popa07] Lucian Popa, Afshin Rostamizadeh, Richard Karp, Christos Papadimitriou, Ion Stoica, Balancing Traffic Load in Wireless Networks with Curveball Routing, Mobihoc’07. How to route messages such that the traffic load is balanced for all pairs traffic.
• [Mei08] Alessandro Mei, Julinda Stefa, Routing in Outer Space: Fair Traffic Load in Multi-Hop Wireless Networks, Mobihoc’08. Geographical routing such that the load of the nodes is balanced.

Routing with virtual coordinates:

• [Rao03] Ananth Rao, Christos Papadimitriou, Scott Shenker, and Ion Stoica, Geographical routing without location information, Proc. MobiCom'03, pages 96 - 108, 2003. Generate with rubberband representation virtual coordinates and apply greedy forwarding.
• [Papadimitriou04] David Ratajczak, Christos Papadimitriou, On a conjecture related to geometric routing, ALGOSENSOR, 2004. Can one find a embedding of a given graph such that greedy forwarding always works?
• [Leighton08] T. Leighton and A. Moitra. Some results on greedy embeddings in metric spaces. FOCS08. The Ratajczak-Papadimitriou conjecture is proved.
• [Newsome03] James Newsome, Dawn Song, GEM: Graph EMbedding for Routing and Data-Centric Storage in Sensor Networks Without Geographic Information, Proc. Sensys'03. Virtual coordinates constructed by using a spanning tree.
• [Caesar06] M. Caesar, M. Castro, E. B. Nightingale, G. O'Shea, A. Rowstron, Virtual Ring Routing: Network Routing Inspired by DHTs, Sigcomm’06. Routing with 1D coordinates.
• [Bruck05b] J. Bruck, J. Gao, A. Jiang, MAP: Medial Axis Based Geometric Routing in Sensor Networks, to appear in the 11th Annual International Conference on Mobile Computing and Networking (MobiCom05), August, 2005. Extract a skeleton from the sensor network and use it to guide routing around holes.

Landmark-based routing:

• [Kleinberg04] J. Kleinberg, A. Slivkins, T. Wexler. Triangulation and Embedding using Small Sets of Beacons. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004. Using the distances to landmarks and triangle inequality, one can approximate the distance for most of pairs.
• [Fang05a] Qing Fang, Jie Gao, Leonidas Guibas, Vin de Silva, Li Zhang, GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks, Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM'05), March, 2005. Route around holes. Use combinatorial Delaunay graph to capture the global topology.
• [Fonseca05] Rodrigo Fonseca, Sylvia Ratnasamy, Jerry Zhao, Cheng Tien Ee and David Culler, Scott Shenker, Ion Stoica, Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets, NSDI'05. Landmark-based routing scheme.
• [Mao07] Yun Mao, Feng Wang, Lili Qiu, Simon S. Lam, Jonathan M. Smith, S4: Small State and Small Stretch Routing Protocol for Large Wireless Sensor Networks, NSDI’07. Landmark-based routing with constant stretch, and \sqrt{n} routing table size.
• [Thorup01] Mikkel Thorup, Uri Zwick, Compact Routing Schemes, SPAA'01. The scheme in S4.
• [Nguyen07] An Nguyen, Nikola Milosavljevic, Qing Fang, Jie Gao, Leonidas Guibas, Landmark selection and Greedy Landmark-descent Routing for Sensor Networks, INFOCOM’07. Landmark-selection and a coupled landmark-based routing scheme with bounded stretch.
• [Tsuchiya88] P. F. Tsuchiya. The landmark hierarchy: a new hierarchy for routing in very large networks. In Sigcomm88. Landmark hierarchy for routing.
• [Funke05a] S. Funke, L. Guibas, A. Nguyen, Y. Wang, Distance Sensitive Routing and Information Brokerage in Sensor Networks, DCOSS’06. Improved landmark hierarchy for routing with worse-case guarantee.

Data-centric query:

• [Intanagonwiwat00] Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin, Directed diffusion: A scalable and robust communication paradigm for sensor networks, In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM '00), August 2000, Boston, Massachussetts. The first paper on data-centric routing in sensor networks. Data discovery relies on flooding the network.
• [Ratnasamy02] Sylvia Ratnasamy,  Li Yin,  Fang Yu,  Deborah Estrin,  Ramesh Govindan,  Brad Karp,  Scott Shenker, GHT: A Geographic Hash Table for Data-Centric Storage, In First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA) 2002. Hash data to geographical locations, for storage and retrieval.
• [Braginsky02] David Braginsky, Deborah Estrin, Rumor routing algorithm for sensor networks, 1^st ACM workshop on Wireless Sensor Networks, 2002. The data source sends agents that walk randomly in the network and leave traces. Sink will send queries along some other random walk and hope to encounter the data traces.
• [Sarkar06] Rik Sarkar, Xianjin Zhu, Jie Gao, Double Rulings for Information Brokerage in Sensor Networks, MobiCom06. Hash data to circles.
• [Fang06] Qing Fang, Jie Gao, Leonidas Guibas, Landmark-based Information Storage and Retrieval in Sensor Networks, INFOCOM'06. Landmark-based data-centric routing with GLIDER: use GHT on top level, use double rulings at bottom level.
• [Awerbuch91] Baruch Awerbuch, David Peleg. Concurrent online tracking of mobile users, SIGCOMM'91. Track mobile users. Use hierarchies.
• [Li00] Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger and Robert Morris, A scalable location service for geographic ad hoc routing, MobiCom'00. Hierarchical structure with universal hashing. Application in location service.
• [Abraham04] I. Abraham, D. Dolev, D. Malkhi , LLS : a Locality Aware Location Service for Mobile Ad Hoc Networks, DIALM-POMC 2004. Improve the above algorithm in terms of worst-case bound. 
• For the above two papers [Awerbuch91] and [Li00], you can take a look at the lecture notes here, here and here.
• [Vieira08] Luiz F. M. Vieira, Uichin Lee, Mario Gerla,  Phero-Trail: a Bio-inspired Location Service for Mobile Underwater Sensors, WUWNet'08, Location service for mobile underwater 3D networks.

• [Greenstein03] B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker, DIFS: A distributed index for features in sensor networks. In Proc. of the 1st IEEE workshop on sensor networks protocols and applications, 2003. Hashing scheme that exploits data correlation.
• [Madden02] Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks, OSDI, December 2002. Aggregation with a tree.
• [Hellerstein03] Joseph Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek. Beyond Average: Towards Sophisticated Sensing with Queries. In Proceedings of IPSN, 2003.
• [Nath04] Suman Nath, Phillip B. Gibbons, Zachary Anderson, and Srinivasan Seshan, Synopsis Diffusion for Robust Aggregation in Sensor Networks. In proceedings of ACM SenSys'04. Use multipath routing to improve routing robustness. Order and duplicate insensitive synopsis needs to be used to prevent one data value to be aggregated multiple times.
• [Considine04] Jeffrey Considine, Feifei Li, George Kollios and John Byers, Approximate Aggregation Techniques for Sensor Databases, Proc. ICDE 2004. Independent development of the same idea as above.
• [Broder02] A. Broder and M. Mitzenmacher, Network Applications of Bloom Filters: A Survey, Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, pp. 636-646, 2002. Bloom filters: a classical data structure for the representation of sets. 
• [Shrivastava04] 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. Approximate answer to medians, reduce storage and message size.
• [Kamra07] Abhinav Kamra, Vishal Misra, Dan Rubenstein, CountTorrent: Ubiquitous Access to Query Aggregates in Dynamic and Mobile Sensor Networks, Sensys’07. Use multipath routing and record what value has been aggregated.
• [Manjhi05] Amit Manjhi, Suman Nath, and Phillip B. Gibbons, Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams, ACM SIGMOD 2005. Combine synopsis diffusion with tree-based aggregation.
• [Przydatek03] Bartosz Przydatek, Dawn Song, Adrian Perrig, SIA: Secure Information Aggregation in Sensor Networks, Sensys’03. Secure computation of median and average.

Multi-dimensional range queries:

• [Berg99] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Algorithms and Applications, Chapter 5, Orthogonal Range Searching, Springer, Second edition, 1999.
• [Matousek94] Jirka Matousek, Geometric range searching. Computing Surveys, volume 26, number 4, page. 422-461, 1994.
• [Li03a] X. Li, Y. J. Kim, R. Govindan, W. Hong, Multi-dimensional Range Queries in Sensor Networks, Proc. ACM SenSys 2003.
• [Gao04] J. Gao, L. Guibas, J. Hershberger, L. Zhang, Fractional Cascaded Information in a Sensor Network, IPSN'04.
• [Ganesan02] Deepak Ganesan, Deborah Estrin and John Heidemann, DIMENSIONS: why do we need a new data handling architecture for sensor networks. In Proc. ACM SIGCOMM workshop on hot topics in networks, 2002.

Boundary detection:

• [Funke05] Stefan Funke, Topological Hole Detection in Wireless Sensor Networks and its Applications, The 3rd ACM/SIGMOBILE International Workshop on foundations of Mobile Computing (DIAL-M-POMC) 2005. Detect broken contours caused by network holes.
• [Wang06] Yue Wang, Jie Gao, Joseph S.B. Mitchell, Boundary Recognition in Sensor Networks by Topological Methods, Mobicom06.
• [Kroller06] A. Kröller, S. P. Fekete, D. Pfisterer, S. Fischer, Deterministic boundary recognition and topology extraction for large sensor networks, SODA06.

Coding and applications in wireless communication and storage:

• [Fragouli06] C. Fragouli, J. Le Boudec, Jorg Widmer, Network coding: an instant primer. A (very) short survey of network coding and applications.
• [Katti06] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, XORs in The Air: Practical Wireless Network Coding, Sigcomm’06. Use network coding in wireless networks.
• [Katti07] Sachin Katti, Shyamnath Gollakota, Dina Katabi, Embracing Wireless Interference: Analog Network Coding, SIGCOMM 2007. Wireless interference is in fact network coding with the analog signals. The paper uses wireless interference intentionally to improve system throughput.
• [Katti08] Sachin Katti, Dina Katabi, Hari Balakrishnan, Muriel Medard, Symbol-level Network Coding for Wireless Mesh Networks, SIGCOMM 2008. The scheme in this paper patches up uncorrupted portions of packets delivered by lossy wireless channels.
• [Gollakota08] Shyamnath Gollakota, Dina Katabi, ZigZag Decoding: Combating Hidden Terminals in Wireless Networks, SIGCOMM 2008. Combat hidden terminal problem in wireless networks. When there are collisions.
• [Dubois05] Henri Dubois-Ferriere, Deborah Estrin and Martin Vetterli, Packet Combining in Sensor Networks, Sensys'05.
• [Dimakis05] A. G. Dimakis, V. Prabhakaran and K. Ramchandran, Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes, IPSN'05. Use erasure code to improve data robustness.
• [Kamra06] Abhinav Kamra, Vishal Misra, Jon Feldman, Dan Rubenstein, Growth Codes: Maximizing Sensor Network Data Persistence, SIGCOMM06. There is a sink in the network. However, instead of sending the data directly to the sink, the nodes in the network propagate coded packets (whose code degree --- the number of source data blocks --- grows over time). The sink is able to decode all the data eventually when it receives enough coded packets.
• [Lin07] Yunfeng Lin, Ben Liang, Baochun Li, Data Persistence in Large-scale Sensor Networks with Decentralized Fountain Codes, INFOCOM07. This paper uses random walk and Metropolis algorithm to construct Fountain Codes.
• [Nath09] Suman Nath, Energy Efficient Sensor Data Logging with Amnesic Flash Storage, IPSN’09. Compression schemes with data aging.

Sensor selection:

• [Krause06] Andreas Krause, Carlos Guestrin, Anupam Gupta, Jon Kleinberg, Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost, IPSN’06. Place sensors for the optimal sensing results.
• [Das08] A. Das and D. Kempe. Sensor selection for minimizing worst-case prediction error, IPSN’08. Select a minimum subset of sensors for aggregation that achieves some error given bound.
• [Gandhi07] Sorabh Gandhi, Subhash Suri, Emo Welzl, Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks, Sensys 2007. Use random samples to catch significant events.
• [Shrivastava05] Nisheeth Shrivastava, Subhash Suri, Csaba, Toth, Detecting Cuts in Sensor Networks, IPSN'05. Use a small subset of sensor nodes to detect whether the network is partitioned.
• [Singh07] Jaspreet Singh, Rajesh Kumar, Upamanyu Madhow, Subhash Suri, Richard Cagley, Tracking Multiple Targets Using Binary Proximity Sensors, IPSN'07.
  

Simulators for sensor networks protocols:

• ns-2: network simulator.
• TOSSIM: TinyOS mote simulator.