TCS / Studies / T-79.194 Seminar on Theoretical Computer Science

T-79.194 Seminar on Theoretical Computer Science (2 cr) P V

Spring 2005 -- Algorithmics of Sensor Networks

This seminar, which is part of the major studies in Theoretical Computer Science, deals with annually varying topics of current interest in the field. The Spring 2005 instantiation of the seminar will be concerned with algorithmic and computation theoretic issues in distributed sensor networks.

[Current] [General] [Arrangements] [Schedule] [Material]

Previous years: [Spring 2004] [Spring 2002] [Spring 2001]

Current

Grade sheet (in Finnish, pdf) available here.
Changes in the schedule:
(i) on Wed 27 April, Maarit Hietalahti replaces Mikko Särelä as the second speaker;
(ii) to replace the cancelled session of 20 Apr, an additional session will be organised on Tuesday 3 May from 12-13 (note date and time!), with a presentation by Antti Rusanen. This exceptional sesssion meets in Room A346.

General

Time, place: Wednesdays 14-16, seminar room TB353.
Coordinator: Prof. Pekka Orponen, room TA348.
Registration by TOPI.
Prerequisites: First two years' mathematics courses. Familiarity with telecommunications technology (e.g. T-110.300) and algorithm design (T-106.410) an asset.
Credits: Seminar presentation plus written summary paper (5-10 pp.) 2 cr. In addition, feedback must be provided for the speakers of at least three other sessions using the respective electronic forms. (Forms will be available via the seminar schedule below.)

Arrangements

Pointers to seminar material will be linked to the schedule below by coordinator.
An electronic copy of the seminar paper must be mailed by the presenter to the coordinator by Monday 12 noon of the presentation week. The paper will then be linked to the schedule below, for distribution to the other seminar participants. If the presenter provides archivable slides, these will also be linked to the schedule after the presentation.

Schedule

19 Jan: Opening, overview, handing out assigments (P.O.)
26 Jan: No seminar
2 Feb: No seminar
9 Feb: Routing 1:
1. Jussi Nikander: Intanagonwiwat et al. (2003)
  Presentation: paper, slides, feedback form
2. Aleksi Ahtiainen: Braginsky & Estrin (2002)
  Presentation: paper, slides, feedback form
23 Feb: Routing 2:
1. Olli Pottonen: Li, Aslam, Rus (2001) & Gandham, Dawande, Prakash (2004)
  Presentation: paper, feedback form
2. Heikki Tikanmäki: Servetto & Barrenechea (2002)
  Presentation: paper, feedback form
2 Mar: Topology control 1:
1. Juho Törmä: Chen et al. (2002)
  Presentation: paper, feedback form
2. Sami Kauppinen: Cerpa & Estrin (2004)
  Presentation: paper, feedback form
9 Mar: Topology control 2:
1. Billy Brumley: Lloyd et al. (2005)
  Presentation: paper, feedback form
2. Antti Hyvärinen: Calinescu et al. (2003)
  Presentation: paper, feedback form
16 Mar: Data gathering & aggregation
1. Juhana Yrjölä: Heinzelman et al. (2000)
  Presentation: paper, slides, feedback form
2. Kimmo Kinnunen: Kalpakis et al. (2003)
  Presentation: paper, feedback form
23 Mar: Sensor deployment & coverage
1. Laura Kneckt: Meguerdichian et al. (2001)
  Presentation: paper, feedback form
2. Lasse Kiviluoto: Cardei & Du (2005)
  Presentation: paper, feedback form
30 Mar: No seminar (Easter break)
6 Apr: Localisation
1. Alexey Kirichenko: Doherty et al. (2001)
  Presentation: paper, slides, feedback form
13 Apr: Distributed algorithms 1
1. Janne Lindqvist: Gallager et al. (1983)
  Presentation: paper, feedback form
20 Apr: Cancelled.
27 Apr: Fault-tolerance & security
1. Lionel Reya: Jacob & Mathai (2004)
  Presentation: paper, feedback form
2. Maarit Hietalahti: Karlof & Wagner
  Presentation: paper, slides, feedback form
Tuesday 3 May, 12-14: Distributed Algorithms 2
1. Antti Rusanen: Rabbat & Nowak (2004)
  Presentation: paper, feedback form

Seminar material

Surveys & overviews

Communications of the ACM 47:6 (June 2004), Special Issue on Wireless Sensor Networks
IEEE Computer 37:8 (August 2004), Special Section on Sensor Networks
IEEE Wireless Communications 11:6 (December 2004), Special Issue on Wireless Sensor Networks
Proceedings of the IEEE 91:8 (August 2003), Special Issue on Sensor Networks and Applications
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey. Computer Networks 38 (2002), 393-422.
J. N. Al-Karaki, A. E. Kamal, Routing techniques in wireless sensor networks: a survey IEEE Wireless Communications 11 (2004), 6-28.
A. Ephremides, Energy concerns in wireless networks. IEEE Wireless Communications 9 (2002), 48-59.
R. Rajaraman, Topology control and routing in ad hoc networks: a survey ACM SIGACT News 33:2 (June 2002), 60-73.

Routing

D. Braginsky, D. Estrin, Rumor routing algorithm for sensor networks. Proc. 1st ACM Intl. Workshop on Wireless Sensor Networks and Applications (WCNA 2002), 22 - 31. ACM, New York NY 2002.
S. Gandham, M. Dawande, R. Prakash, An integral flow-based energy-efficient routing algorithm for wireless sensor networks. Proc. IEEE Wireless Communications and Networking Conference 2004 Vol. 4, 2341-2346.
C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, F. Silva, Directed diffusion for wireless sensor networking. IEEE/ACM Transactions on Networking 11 (2003), 2-16.
Q. Li, J. Aslam, D. Rus, Online power-aware routing in wireless ad-hoc networks. Proc. 7th Ann. Intl. Conf. on Mobile Computing and Networking (ACM Mobicom'01), 97-107. ACM, New York NY, 2001. (Journal version here.)
D. Servetto, G. Barrenechea, Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks. Proc. 1st ACM Intl. Workshop on Wireless Sensor Networks (WSNA'02), ACM, New York NY, 2002.

Topology control

G. Calinescu, S. Kapoor, A. Olshevsky, A. Zelikovsky, Network lifetime and power assignment in ad hoc wireless networks. Proc. 11th Ann. European Symp. on Algorithms (ESA 2003), 114-126. Lecture Notes in Computer Science 2832, Springer-Verlag, Berlin 2003.
A. Cerpa, D. Estrin, ASCENT: Adaptive self-configuring sensor networks topologies. IEEE Transactions on Mobile Computing 3 (2004), 272-285.
B. Chen, K. Jamieson, H. Balakrishnan, R. Morris, SPAN: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. Wireless Networks 8 (2002), 481-494.
E. L. Lloyd, M. V. Marathe, R. Ramanathan, S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks. Mobile Networks and Applications 10 (2005), 19-34.

Data gathering & aggregation

W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. Proc. 33rd Hawaii Intl. Conf. on System Sciences (HICSS'00) Vol. 8. IEEE Computer Society, New York NY, 2000.
K. Kalpakis, K. Dasgupta, P. Namjoshi, Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Computer Networks 42 (2003), 697-716.

Sensor deployment & coverage

M. Cardei, D.-Z. Du, Improving wireless sensor network lifetime through power aware organization. Wireless Networks 11 (2005), to appear.
S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. B. Srivastava, Coverage problems in wireless ad-hoc sensor networks. Proc. 20th Ann. Joint Conf. of IEEE Computer and Communications Societies (INFOCOM 2001) Vol. 3, 1380-1387. IEEE, New York NY, 2001.

Fault tolerance & self-stabilisation

D. Bein, A. K. Datta, A self-stabilizing directed diffusion protocol for sensor networks. Proc. 2004 Intl. Conf. on Parallel Processing Workshops (ICPPW 2004), 69-77. IEEE, New York NY, 2004.
M. Demirbas, A. Arora, M. G .Gouda, A pursuer-evader game for sensor networks. Proc. 6th Intl. Symp. on Self-Stabilizing Systems (SSSS 2003), 1-16. Lecture Notes in Computer Science 2704, Springer-Verlag, Berlin, 2003.
C. Jacob, R. J. Mathai, Fault Tolerance in Sensor Networks. Manuscript, Univ. of Wisconsin, Madison 2004.
F. Koushanfar, M. Potkonjak, A. Sangiovanni-Vincentelli, Fault tolerance techniques for wireless ad hoc sensor networks. Proc. IEEE Sensors 2002 Vol. 2, 1491-1496. IEEE, New York NY, 2002.
H. Zhang, A. Arora, GS³: scalable self-configuration and self-healing in wireless networks. Proc. 21st Ann. ACM Symp. on Principles of Distributed Computing (PODC 2002), 58-67. ACM, New York NY, 2002.

Localisation

P. Biswas, Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization. Proc. 3rd Intl. Symp. on Information Processing in Sensor Networks (IPSN 2004), 46-54. ACM, New York NY, 2004.
L. Doherty, K. S. J. Pister, L. El Ghaoui, Convex position estimation in wireless sensor networks. Proc. 20th Ann. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2001), Vol. 3, 1655 - 1663. IEEE, New York NY, 2001.

Distributed algorithms

R. G. Gallager, P. A. Humblet, P. M. Spira, A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems 5 (1983), 66-77.
A. Kamath, O. Palmon, S. Plotkin, Fast approximation algorithm for minimum cost multicommodity flow. Proc. 6th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), 493-501. SIAM, Philadelphia PA, 1995.
A. Kamath, O. Palmon, S. Plotkin, Simple and fast distributed multicommodity flow algorithm. Manuscript, Stanford University 1995.
M. Rabbat, R. Nowak, Distributed optimization in sensor networks. Proc. 3rd Intl. Symp. on Information Processing in Sensor Networks (IPSN 2004), 20-27. ACM, New York NY, 2004.

Miscellaneous (e.g. security, clustering)

C. Karlof, D. Wagner, Secure routing in wireless sensor networks: attacks and countermeasures. Ad Hoc Networks 1 (2003), 293-315.
V. Mhatre, C. Rosenberg, Design guidelines for wireless sensor networks: communication, clustering and aggregation. Ad Hoc Networks 2 (2004), 45-63.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]

Latest update: 13 June 2005. Pekka Orponen.