CS735: Sensor Networks and Data Management

10/22 Note updated schedule.

Organizers

Overview

The database seminar this semester will deal with data management for sensor networks and peer-to-peer computing. Due to considerable overlap with material with CS615, the seminar is joined with CS615 "Adaptive Systems" taught by Professor Gun Sirer. This works as follows:

1. You can register for CS615 pass fail, TR 2:55-4:10. Just listen to the lectures and read the papers. If you take the course pass/fail there there are no other requirements (e.g., paper reviews, projects, or examinations).

2. You register for CS735, (M)W 4:40-5:30pm; new in Upson 211.

In CS615, Professor Sirer will give regular lectures of fundamental material related to ad-hoc networking and other systems issues. CS735 is a seminar. Al Demers and Johannes Gehrke will give some of the lectures, but afterwards participants in the course will give the remaining lectures. We will cover some advanced topics, concentrating on data management for sensor networks and data management for peer-to-peer computing with the goal to identify interesting database and data mining research problems in this area.

News

Overview papers and background reading.

Tentative Schedule (will be continued)

Date Topic Lecturer
September 5 Introduction  
September 10 no class  
September 12

Routing

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.

 

 Johannes Gehrke
September 17 No class due to colloquium  
September 19

Routing

Gossip-Based Ad-hoc Routing.
Zygmunt Haas, Joe Halpern, and Li Li.

 Kevin O'Neill
September 24

Routing

Karp, B., and Kung. H. T. (2000).  GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom 2000), 243-254.

P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM'99), pp. 48-55, 1999. ©ACM [conference postscript] [journal postscript]

 Al Demers

Note new (permanent) room: Upson 211.
September 26 no class (School of Engineering faculty event)  
October 1

Routing

L. Li with J. Halpern, V. Bahl, Y.M. Wang and R. Wattenhofer, "Analysis of a Cone-Based Distributed Topology Control Algorithms for Wireless Multi-hop Networks", ACM Symposium on Principle of Distributed Computing (PODC), August 2001.

L. Li with V. Bahl, Y.M. Wang and R. Wattenhofer ,"Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks", IEEE INFOCOM, April 2001.

 Al Demers
October 3

Location

Young-Bae Ko and Nitin H. Vaidya, "Location-Aided Routing(LAR) in Mobile Ad Hoc Networks" In Proceedings of the 4th Annual International Conference on Mobile Computing and Networking (MOBICOM'98), October, 1998.

Adaptive Beacon Placement. Nirupama Bulusu, John Heidemann and Deborah Estrin. In Proceedings of the Twenty First International Conference on Distributed Computing Systems (ICDCS-21), Phoenix, Arizona, April 2001.

Cristian Bucila
October 8 Fall break  
October 10

Power-aware routing

Geography-informed Energy Conservation for Ad-hoc Routing. Ya Xu, John Heidemann, Deborah Estrin. In Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking(ACM MobiCom), Rome, Italy, July 16-21, 2001.

Span: an Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris.
Proc. 7th ACM MOBICOM Rome, Italy. July, 2001. See also http://pdos.lcs.mit.edu/span/

Yong Yao
October 15 MAC Layer

F. A. Tobagi and L. Kleinrock, ``Packet switching in radio channels: part II - The hidden terminal problem in carrier sense multiple-access and the busy-tone solution,'' IEEE Trans. Commun., vol. COM-23, no. 12, pp. 1417-1433, Dec. 1975.

P. Karn, ``MACA - A new channel access method for packet radio,'' in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-140, 1990.

V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, ``MACAW: A media access protocol for wireless LAN's,'' in Proc. ACM SIGCOMM '94, pp. 212-225, 1994.

 Al Demers
October 17   cancelled
October 22   cancelled
October 24 MAC Layer

C. Fullmer and J.J. Garcia-Luna-Aceves, Floor Acquisition Multiple Access for Packet Radio Networks. SIGCOMM 95.

Rodrigo Garces and J.J. Garcia-Luna-Aceves, Floor Acquisition Multiple Access with Collision Resolution. MOBICOM 96.

C. L. Fullmer, J. J. Garcia-Luna-Aceves, ``Solutions to hidden terminal problems in wireless networks,'' in Proc. ACM SIGCOMM '97, pp. 39-49, 1997. Can be found on Fullmer's publication page.

A. C. V. Gummalla and J. O. Limb, ``Design of an Access Mechanism for a High Speed Distributed Wireless LAN,'' IEEE JSAC, vol. 18, no. 9, Sep. 2000.

Shugong Xu and Tarek Saadawi, Does the IEEE 802.11 MAC Protocol Work Well in Multihop Ad Hoc Networks? IEEE Communications Magazine, June 2001, p. 130.

 Dual lecture:

Johannes, then Al
October 24    
October 29 Astrolabe Robbert van Renesse
October 31 MAC Layer

C. Wu and V. O. K. Li, ``Receiver-initiated busy-tone multiple access in packet radio networks,'' in Proc. ACM SIGCOMM '87, pp. 336-342, 1987. To get the paper, go to the Cornell Electronic Library, or click on the following link:

http://delivery.acm.org/10.1145/60000/55518/p336-wu.pdf?CFID=226708&CFTOKEN=22352344 

DBTMA (Dual Busy Tone Multiple Access): http://citeseer.nj.nec.com/deng98dual.html 

 Matt Schultz
November 5   no class
November 7 Sensor failure

Keith Marzullo. Tolerating failures of continuous-valued sensors. ACM TOCS, Volume 8, Number 4. Pages 284 - 304.

 Zhiyuan
November 12 STOC deadline no class
November 14 Matthew Clegg, Keith Marzullo: Predicting Physical Processes in the Presence of Faulty Sensor Readings. 27th International Symposium on Fault-Tolerant Computing (FTCS '97). 373-378 Adina
November 19 Eddies

Joe Hellerstein and Ron Avnur. Eddies: Continuously Adaptive Query Processing (with Ron Avnur). SIGMOD 2000. [PDF] [PS].

 Alin
November 21   Thanksgiving, no class.
November 28 Laurent Amsaleg, Michael J. Franklin, Anthony Tomasic, Tolga Urhan: Scrambling Query Plans to Cope With Unexpected Delays. PDIS 1996: 208-219

Tolga Urhan, Michael J. Franklin, Laurent Amsaleg: Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998: 130-141

 Johannes
December 3
(Last class)		 João Pereira, Françoise Fabret, François Llirbat, Dennis Shasha: Efficient Matching for Web-Based Publish/Subscribe Systems. CoopIS 2000: 162-173

Françoise Fabret, Hans-Arno Jacobsen, François Llirbat, João Pereira, Kenneth A. Ross, Dennis Shasha: Filtering Algorithms and Implementation for Very Fast Publish/Subscribe. SIGMOD Conference 2001

 Indranil Gupta

Questions and comments to johannes@cs.cornell.edu.