CMPSCI
791L
Sensor
Networks, Part 2 – Spring 2004
Instructors: Professors Jim
Kurose, Prashant Shenoy and Victor Lesser
Dates: February 13 –
Time and Place: Friday’s,
Part 1 is found here http://www-net.cs.umass.edu/cs791_sensornets/,
also please check out its introduction.
Schedule
number: 60595
This course
continues the CMPSCI Sensor
Networks seminar from the Fall 2003 semester.
Sensor networks are
a sensing, computing and communication infrastructure that allows us to
instrument, observe, and respond to phenomena in the natural environment, and
in our physical and cyber infrastructure. The sensors themselves can range from
small passive microsensors (e.g, "smart dust") to larger scale,
controllable weather-sensing platforms. Their computation and communication
infrastructure will be radically different from that found in today's
Internet-based systems, reflecting the device- and application-driven nature of
these systems. In this seminar, we will continue our journey of last semester
to survey the current sensor networks literature, focusing on the data-centric,
computational, and communication challenges posed by these systems. Throughout
the semester, we'll look to identify open research challenges and directions.
This course can be
taken for 1 credit. Prerequisites include previous courses in computer networks
and operating systems at the undergraduate level. Approval of one of the
instructors is required to register for this seminar.
The following
reading list is under construction, and will no doubt continue to evolve as the
semester progresses ...
CLASS
STRUCTURE
In the interest of
facilitating exciting discussion among the participants, each class will be
structured in three segments as follows:
1. 25-30 minute presentation of the paper (or
papers). The presenter is responsible for staying within this time limit.
2. 5 minute critique of the paper by the
presenter. What were the main contributions of the paper? How do they relate to
the contributions of related papers? What are the most promising areas of
follow-on work in this area?
3. 15-20 minutes for discussion.
The last class
(scheduled for May 14) will be optional since it is scheduled during reading
period.
PRESENTATION
WEEK
1: APPLICATION-DRIVEN ROUTING (
Slides (PDF, PPT);
Presenter: David Yates; Virtual
red team: Peter Desnoyers, Jim Kurose
Bhaskar Krishnamachari and John Heidemann. Application-specific Modelling of Information Routing in Sensor Networks. Technical Report ISI-TR-576, USC/Information Sciences Institute, August 2003.
http://ceng.usc.edu/~bkrishna/research/papers/KrishnamachariHeidemann_ApplicationModeling.pdf
WEEK
2: QUERY PROCESSING I (
Slides (PDF, PPT);
Presenter: Weifeng Chen; Virtual
red team: Bing Wang, David Yates
Samuel R. Madden, Michael J. Franklin, Joseph M.
Hellerstein, and Wei Hong. The Design of an Acquisitional Query Processor
for Sensor Networks. ACM SIGMOD, June 2003,
http://db.cs.berkeley.edu/papers/sigmod03-acqp.pdf
WEEK
3: QUERY PROCESSING II (
Slides(PDF, PPT); Presenter:
Peter Desnoyers; Virtual red team: Huan
Li, Bing Wang
Joseph M. Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek. Beyond Average: Towards Sophisticated Sensing with Queries. Second International Workshop on Information Processing in Sensor Networks (IPSN '03), March 2003.
http://www.cs.berkeley.edu/~madden/beyond_average_ipsn.pdf
WEEK
4: QUERY PROCESSING III (
Slides(PDF,
PPT);
Presenter: Wei Wei; Virtual red
team: Bing Wang, Weifeng Chen
Yong Yao, J. E. Gehrke, "Query Processing in Sensor
Networks". First Biennial Conference on Innovative Data Systems Research
(CIDR 2003)
http://www-db.cs.wisc.edu/cidr/program/p21.pdf
Yong Yao, J. E. Gehrke, "The Cougar Approach to
In-Network Query Processing in Sensor Networks". ACM SIGMOD Record, Volume
31, Number
http://www.cs.cornell.edu/johannes/papers/2002/sigmod-record2002.pdf
WEEK
5: REAL-TIME COMMUNICATION I (
Slides(PDF, PPT);
Presenter: Bing Wang; Virtual red
team: David Yates, Huan Li
"RAP: A Real-Time Communication Architecture for
Large-Scale Wireless Sensor Networks", Chenyang Lu, Brian M. Blum, Tarek
F. Abdelzaher, John A. Stankovic, and Tian He, IEEE Real-Time and Embedded
Technology and Applications Symposium (RTAS 2002), San Jose, CA, September
2002.
http://www.cs.virginia.edu/~stankovic/psfiles/rtas02-rap.pdf
WEEK
6: REAL-TIME COMMUNICATION II (
Slides(PDF,
PPT);
Presenter: Huan Li; Virtual red
team: Bing Wang, Wei Wei
"An Implicit Prioritized Access Protocol for Wireless Sensor Networks", M. Caccamo, L. Y. Zhang, L. Sha and G. Buttazzo, IEEE Real-Time Systems Symposium, December 2002.
http://pertsserver.cs.uiuc.edu/~mcaccamo/papers/rtss02.ps
WEEK
7: CACHING AND REPLICATION I (
Slides (PDF, PPT);
Presenter: David Yates; Virtual
red team: Sudarshan Vasudevan, Ellen Zhang
C. Olston, J. Jiang, and J. Widom. Adaptive Filters for Continuous Queries over Distributed Data Streams (Extended version). Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 563-574, San Diego, California, June 2003.
http://www-2.cs.cmu.edu/~olston/publications/af-sigmod03.pdf
C. Olston and J. Widom. Best-Effort Cache Synchronization with Source Cooperation (Extended version). Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 73-84, Madison, Wisconsin, June 2002.
http://www-2.cs.cmu.edu/~olston/publications/bes-sigmod.pdf
WEEK
8: CACHING AND REPLICATION II (
Slides (PDF, PPT);
Presenter: David Yates; Virtual
red team: Sudarshan Vasudevan, Ellen Zhang
A. Deshpande, S. Nath, P. Gibbons, S. Seshan.
Cache-and-Query for Wide Area Sensor Databases. Proceedings of the ACM SIGMOD,
http://www.cs.berkeley.edu/~amol/papers/iris-sigmod.pdf
WEEK
9: TOPOLOGY CONTROL I (
Slides (PDF, PPT);
Presenter: Sudarshan Vasudevan;
Virtual red team: Ellen Zhang, Weifeng Chen
"Topology Control of Multihop Wireless Networks using Transmit Power Adjustment", Ram Ramanathan and Regina-Rosales Hain. IEEE Infocom 2000.
http://nesl.ee.ucla.edu/pw/ee206a/Ramanathan_Infocom00.pdf
"Energy-Efficient Link Assessment in Wireless Sensor Networks". A. Keshavarzian, Elif Uysal-Biyikoglu, Falk Herrman, Arati Manjeshwar. IEEE Infocom 2004.
http://simula.stanford.edu/papers/wireless/sensor/WSN2.pdf
WEEK
10: TOPOLOGY CONTROL II (
Slides (PDF, PPT); Presenter: Ellen Zhang; Virtual red team: Wei Wei, Huan Li
"Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks" - R. Wattenhofer, Li Li, Victor Bahl and Yi-Min Wang. IEEE Infocom 2001.
http://distcomp.ethz.ch/publications/INFOCOM01b.pdf
"Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-hop Networks" (2001) L. Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, Roger Wattenhofer. ACM PODC 2001.
http://www.bell-labs.com/user/erranlli/liliPODC01.pdf
WEEK
11: ROUTING IN SENSOR NETWORKS (
Slides (Part1-PDF, Part1-PPT, Part2-PDF, Part3-PDF, Part3-PPT);
Presenter: Chun Zhang; Virtual red team: Daniel Figueiredo, Huan Li,
Vicky Manfredi
"Geographic Routing Without Location Information". Ananth Rao, Sylvia Ratnasamy, Christos Padamitriou, Scott Shenker and Ion Stoica. ACM Mobicom 2003.
http://www.cs.ucla.edu/classes/fall03/cs218/paper/p96-rao.pdf
"Age Matters: Efficient
Route Discovery in
http://www.sigmobile.org/mobihoc/2003/papers/p257-dubois.pdf
WEEK
12: TIME SYNCHRONIZATION (
Slides (PDF, PPT);
Presenter: Daniel Figueiredo;
Virtual red team: Vicky Manfredi, David Yates
"Fine-Grained
Network Time Synchronization using Reference Broadcasts", Jeremy Elson, Lewis Girod and Deborah Estrin,
Fifth Symposium on Operating Systems Design and Implementation (OSDI) 2002.
http://lecs.cs.ucla.edu/Publications/papers/broadcast-osdi.pdf
"Global Clock Synchronization in Sensor Networks", Qun Li, Daniela Rus, IEEE Infocom 2004.
http://www.cs.dartmouth.edu/~liqun/paper/info04.pdf
WEEK
13: SEMINAR WRAP-UP (
Your favorite m
papers (and why);
Your least favorite n papers (and
why); and
Future directions in Sensor Networks.
Please email these to Dan and I in advance so that we can tally and summarize the results. We will also deal with logistics such as course evaluations, etc. Finally, we should also ask the obvious question ... What next?
- Should we consider organizing a seminar for the Fall?
- What would topics of interest be for a Fall seminar?
- Should we stay with the 1-credit format, or is a 3-credit format
- preferred?
- Plus ... Anything else you think is important to discuss!
BACKGROUND
INTRODUCTION
AND APPLICATIONS
Joseph M. Hellerstein, Samuel Madden, and Wei Hong. The
Sensor Spectrum: Technology, Trends, and Requirements. ACM SIGMOD Record,
December 2003.
http://www.cs.berkeley.edu/~madden/sensorspectrum.pdf
"Smart Kindergarten: Sensor-based Wireless Networks for
Smart Developmental Problem-solving Environments", Mani Srivastava,
Richard Muntz, and Miodrag Potkonjak. In Seventh Annual International
Conference on
http://www.cs.washington.edu/education/courses/590es/01au/papers/5.pdf
"Lightweight Sensing and Communication Protocols for Target Enumeration and Aggregation", Qing Fang, Feng Zhao, Leonidas Guibas, MobiHoc 2003.
http://www2.parc.com/spl/projects/cosense/pub/mobihoc03.pdf
REAL-TIME
COMMUNICATION
"Real-Time Communication and Coordination in Embedded
Sensor Networks", John A. Stankovic, Tarek Abdelzaher, Chenyang Lu, Lui
Sha, Jennifer Hou, Proceedings of the IEEE, 91(7): 1002-1022, July 2003.
http://www.cs.virginia.edu/~zaher/sensornet-ieee.ps
DATA-CENTRIC
/ APPLICATION-DRIVEN ROUTING AND QUERY PROCESSING
"Directed Diffusion: A Scalable
and Robust Communication Paradigm for Sensor Networks."
Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin, In Proceedings of the Sixth Annual
International Conference on Mobile Computing and Networks (MobiCOM 2000),
August 2000, Boston, Massachusetts.
http://www.isi.edu/div7/publication_files/directed_diffusion_scalable.pdf
P. Bonnet, J. Gehrke and P. Seshadri, "Towards sensor
database systems". In Second International Conference on
http://www.cs.cornell.edu/johannes/papers/2001/MDM2001-sensor.pdf
Bhaskar Krishnamachari, Deborah Estrin and Stephen Wicker,
"Modelling Data-Centric Routing
in Wireless Sensor Networks," USC Computer Engineering
Technical Report CENG 02-14, 2002.
http://ceng.usc.edu/~bkrishna/anr/techreports/Bhaskar-DataCentric.pdf
B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and Issues in Data Stream Systems.
Proceedings of the Twenty-First ACM SIGACT-SIGMOD-SIGART Symposium on Principles
of Database Systems, pages 1-16, Madison, Wisconsin, June 2002.
http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=2002-19&format=pdf&compression=
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.
http://www.cs.berkeley.edu/~madden/madden_tag.pdf
Samuel R. Madden, Mehul A. Shah, Joseph M. Hellerstein, and
Vijayshankar Raman. Continuously Adaptive Continuous Queries over Streams.
Proceedings of the Twenty-First ACM SIGACT-SIGMOD-SIGART Symposium on Principles
of Database Systems,
http://www.cs.berkeley.edu/~madden/madden_cacq_final.pdf
Suman Nath and Phillip B. Gibbons, “Synopsis Diffusion for Robust
Aggregation in Sensor Networks,” Intel Research Technical Report IRP-TR-03-08,
August 2003.
http://www.cs.cmu.edu/~sknath/ITR-03-08.pdf
John Heidemann, Fabio Silva, and Deborah Estrin. Matching Data Dissemination
Algorithms to Application Requirements. In Proceedings of the
ACM SenSys Conference, pp. 218-229.
http://lecs.cs.ucla.edu/publications/papers/p128-heidemann.pdf
Narayanan Sadagopan, Bhaskar Krishnamachari, Ahmed Helmy,
"Active Query Forwarding in Sensor Networks (ACQUIRE)," USC Computer
Engineering Technical Report,
http://nile.usc.edu/~helmy/career/acquire-elsevier-sub-2.pdf
POSITION,
LOCALIZATION AND TIME
"Recursive Position Estimation in Sensor Networks", J. Albowitz, A. Chen, L. Zhang, ICNP, 2001.
http://irl.cs.ucla.edu/papers/grab-icnp01.pdf
"Localization from Mere Connectivity", Yi Shang,
Wheeler Ruml, Ying Zhang, Markus Fromherz, MobiHoc 2003.
http://www2.parc.com/spl/projects/ldc/publications/nest-mobihoc03.pdf
"Optimal and
Global Time Synchronization in Sensornets", Richard Karp, Jeremy Elson, Deborah Estrin, and Scott Shenker, UCLA CENS
Technical Report #12 , April 11 2003.
http://www.eecs.harvard.edu/~mdw/course/cs263/fa03/papers/timesync-techrept03.pdf
ROUTING
IN SENSOR NETWORKS
Finn, G.G., "Routing and addressing problems in large metropolitan-scale internetworks," ISI/RR-87-180, ISI, Mar 1987.
(Large = 73 MB) http://www.isi.edu/div7/people/finn.home/routing_and_addressing_problems_in_large_metropolitan-scale_internetworks.BW.pdf
B. Karp and H. Kung, "GPSR: Greedy Perimeter Stateless
Routing for Wireless Networks." ACM International Conference on
http://www.eecs.harvard.edu/~htk/publication/2000-mobi-karp-kung.pdf
Larry Hughes, Omid Banyasad and Evan Hughes, "Cartesian
routing". In Computer Networks: The International Journal of Computer
and Telecommunications Networking, 34(3), pp. 455-466, September 2000.
http://www.dal.ca/~lhughes2/cartnet/article.pdf
Matthias Grossglauser and Martin Vetterli, "Locating
Nodes with EASE: Mobility Diffusion of Last Encounters in Ad Hoc Networks."
IEEE Infocom 2003.
http://www.terminodes.org/getDoc.php?docid=200&docnum=1
CACHING,
REPLICATION, AND SCALE
C. Olston and J.
Widom, “Offering a Precision-Performance Tradeoff for Aggregation Queries over
Replicated Data.” In Twenty-Sixth International Conference on Very Large Data
Bases, pp. 144-155,
http://hake.stanford.edu/~olston/publications/trapp-vldb.pdf
C. Olston, B.T.
Loo, and J. Widom, “Adaptive Precision Setting for Cached Approximate Values.” In
ACM SIGMOD International Conference on Management of Data, pp. 355-366, Santa
Barbara, CA, May 2001.
http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=2001-18&format=pdf&compression=
B. Xu, O. Wolfson, S. Chamberlain,
http://www.cs.uic.edu/~wolfson/mobile_ps/winet02.ps
Sagnik Bhattacharya, Hyung Kim,
Shashi Prabh and Tarek Abdelzaher. Energy-Conserving Data Placement and
Asynchronous Multicast in Wireless Sensor Networks. Proceedings of USENIX
MobiSys,
http://www.cs.virginia.edu/~zaher/mobysis-sagnik.pdf
Praveen Yalagandula and Mike Dahlin, A Scalable
Distributed Information Management System The University of
http://www.cs.utexas.edu/users/dahlin/papers/yalagandulaDahlin-SDIMS-Sep2003.pdf