CS 788.11K: Wireless Ad Hoc/Sensor Networks

Autumn 2003

Time:               MWF 12:30 pm
Place: DL 266
Instructor:        Steve Lai

COURSE DESCRIPTION

This is a research-oriented course intended for students with potential research interest in wireless ad hoc and sensor networks.  Topics will include IEEE 802.11 and various issues in ad hoc/sensor networks, including power management, timing synchronization, MAC, routing, reliable transport, coverage and connectivity, topology maintenance, location discovery, tracking.  Students are expected to read a bunch of articles, made one or two presentations, participate in discussions, and complete a research project.

Prerequisites: CIS 677 or consent of instructor  

---

Tentative Topics/Schedule

Week 1-2 (Sept 24, 26, 29; Oct 1, 3, 6, 8):

Topics: IEEE 802.11, Ad Hoc Networks, Power Saving, Timing Synchronization

• M. Gast, 802.11 Wireless Networks, O’Reilly & Associates, Inc.
• L. Huang, T.H. Lai, On the scalability of IEEE 802.11 ad hoc networks, MobiHoc 2002.
• Y.-C. Tseng, C.-S. Hsu, and T.-Y. Hsieh, Power-saving protocols for IEEE 802.11-based multi-hop ad hoc network, INFOCOM 2002.
• R. Zheng, J.C. Hou, L. Sha, Asynchronous wakeup for ad hoc networks, MobiHoc 2003.
• P. Nuggehalli, V. Srinivasan, C. Chiasserini, Energy-efficient caching strategies in ad hoc wireless networks,  MobiHoc 2003
• J.R. Jiang, Y.C. Tseng, C.S. Hsu, T.H. Lai, Quorum-Based Asynchronous Power-Saving Protocols for IEEE 802.11Ad Hoc Networks, ICPP 2003 (Best paper award).
• Week 3 (Oct 10, 13): Coverage and Connectivity Issues in Sensor Networks

• S. Shakkottai, R. Srikant and N. Shroff, Unreliable Sensor Grids: Coverage, Connectivity and Diameter, INFOCOM 2003.
• Piyush Gupta and P. R. Kumar, Critical Power for Asymptotic Connectivity in Wireless Networks,'' pp. 547-566, in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming. Edited by W.M. McEneany, G. Yin, and Q. Zhang, Birkhauser, Boston, 1998. ISBN 0-8176-4078-9.
• Piyush Gupta and P. R. Kumar, ``The Capacity of Wireless Networks,'' IEEE Transactions on Information Theory, vol. IT-46, no. 2, pp. 388-404, March 2000.
• Feng Xue and P. R. Kumar, ``The number of neighbors needed for connectivity of wireless networks.'' To appear in Wireless Networks.
• Josep Díaz, Jordi Petit, Maria J. Serna: Random Geometric Problems on [0, 1]². RANDOM 1998: 294-306.
• Olivier Dousse, Patrick Thiran, Martin Hasler: Connectivity in ad-hoc and hybrid networks. INFOCOM 2002.
• O. Dousse, Francois Baccelli, P. Thiran "Impact of Interferences on Connectivity in Ad Hoc Networks," INFOCOM 2003.

Topics for other weeks:

Topology

• Xiang-Yang Li, Peng-Jun Wan, Yu Wang, Chih-Wei Yi, Fault tolerant deployment and topology control in wireless networks, MobiHoc 2003.
• Lichun Bao, J. J. Garcia-Luna-Aceves, Topology management in ad hoc networks,
• Douglas M. Blough, Mauro Leoncini, Giovanni Resta, Paolo Santi, The lit K-neigh protocol for symmetric topology control in ad hoc networks, MobiHoc 2003.
• Himanshu Gupta, Samir R. Das, Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, MobiHoc 2003.
• Yi Shang, Wheeler Ruml, Ying Zhang, Markus P. J. Fromherz, Localization from mere connectivity, MobiHoc 2003.
• Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris.  "Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks."  Proc. 7th ACM International Conference on Mobile Computing and Networking (MobiCom '01), Rome, Italy, July 2001, pages 85-96.

Routing

• Henri Dubois-Ferriere, Matthias Grossglauser, Martin Vetterli, Age matters: efficient route discovery in mobile ad hoc networks using encounter ages

, MobiHoc 2003.

• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, MobiHoc 2003.
• Chao Gui, Prasant Mohapatra, SHORT: self-healing and optimizing routing techniques for mobile ad hoc networks,  MobiHoc 2003.
• Jiejun Kong, Xiaoyan Hong, ANODR: anonymous on demand routing with untraceable routes for mobile ad-hoc networks,  MobiHoc 2003.
• Venugopalan Ramasubramanian, Zygmunt J. Haas, Emin Gün Sirer, SHARP: a hybrid adaptive routing protocol for mobile ad hoc networks, MobiHoc 2003.
• E.M. Royer and C-K. Toh. "A review of current routing protocols for ad-hoc mobile wireless networks."  IEEE Personal Communications, April 1999.
• Yan Yu, Ramesh Govindan and Deborah Estrin.  "Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks."  UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023, May 2001.
• Karp, B., and Kung. H. T.  "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks." MobiCom 2000).
• Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicker, "Modelling Data-Centric Routing in Wireless Sensor Networks." IEEE Infocom 2002.

Mobility

• Pubudu N. Pathirana, Andrey V. Savkin, Sanjay Jha, Mobility modelling and trajectory prediction for cellular networks with mobile base stations, MobiHoc 2003.
  
• Rajiv Gandhi, Srinivasan Parthasarathy, Arunesh Mishra, Minimizing broadcast latency and redundancy in ad hoc networks, MobiHoc 2003.
  
• Tara Small, Zygmunt J. Haas, The shared wireless infostation model: a new ad hoc networking paradigm (or where there is a whale, there is a way), MobiHoc 2003.
  
• Narayanan Sadagopan, Fan Bai, Bhaskar Krishnamachari, Ahmed Helmy, PATHS: analysis of PATH duration statistics and their impact on reactive MANET routing protocols, MobiHoc 2003.
  
  

Transport

• Yogesh Sankarasubramaniam, Özgür B. Akan, Ian F. Akyildiz, ESRT: event-to-sink reliable transport in wireless sensor networks, MobiHoc 2003.

 MAC and Directional Antenna

• Christina Peraki, Sergio D. Servetto, On the maximum stable throughput problem in random networks with directional antennas, MobiHoc 2003.
• Siuli Roy, Dola Saha, S. Bandyopadhyay, Tetsuro Ueda, Shinsuke Tanaka, A network-aware MAC and routing protocol for effective load balancing in ad hoc wireless networks with directional antenna, MobiHoc 2003.
• Thanasis Korakis, Gentian Jakllari, Leandros Tassiulas, A MAC protocol for full exploitation of directional antennas in ad-hoc wireless networks,  MobiHoc 2003.
  

Location, Tracking, Network Discovery  

• Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan.  "The Cricket Location-Support System."  Mobicom, 2000.
• Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan.  "The Cricket Location-Support System."  Mobicom, 2000.
• Jeffrey Hightower, Gaetano Borriello. "Location systems for ubiquitous computing." IEEE Computer, Vol. 34, No. 8, August 2001 pp 57-66.
• Jeffrey Hightower and Gaetano Borriello, A Survey and Taxonomy of Location Systems for Ubiquitous Computing, University of Washington, CSE, Technical Report UW-CSE 01-08-03, August 24, 2001.
• Andreas Savvides, Chih-Chieh Han and Mani B. Strivastava. "Dynamic fine-grained localization in ad-hoc networks of sensors." 7-th annual international conference on Mobile computing and networking (MobiCom) 2001, July 16 - 21, 2001, Rome Italy.  Pages 166-179.
• Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger, Robert Morris.  "A scalable location service for geographic ad hoc routing."  ACM Mobicom 2000, Boston, MA, pages 120-130.
• John Byers and Gabriel Nasser.  "Utility-based decision making in wireless sensor networks."  MobiHoc 2000.
• Feng Zhao, Jaewon Shin, James Reich.  "Information-Driven Dynamic Sensor Collaboration for Target Tracking", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.
• D.B. Reid. "An Algorithm for Tracking Multiple Targets." IEEE Trans. on Automatic Control, 24:6, 1979.
• Leonidas Guibas. "Sensing, Tracking and Reasoning with Relations", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.
• Joe C. Chen, Kung Yao, and Ralph E. Hudson, "Source localization and beamforming", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.
• Dan Li, Kerry Wong, Yu Hen Hu, Akbar Sayeed. "Detection, Classification and Tracking of Targets in Distributed Sensor Networks", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.

RENERAL READING

• Mark Weiser, The Computer for the Twenty-First Century, Scientific American, pp. 94-10, September 1991.
• J. M. Kahn, R. H. Katz, K. S. J. Pister, Next Century Challenges: Mobile Networking for “Smart Dust”, Mobicom 1999.
• D. Estrin, D. Culler, K. Pister, G. Sukhatme, Connecting the physical world with pervasive networks, IEEE Pervasive Computing, Vol. 1, No.1, 2002.
• D. Estrin, Ramesh Govindan, John Heidemann, and Satish Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks, Mobicom 1999.
• I. F. Akyildiz, W. Su, et al., Wireless Sensor Networks: A Survey, Computer Networks (Elsevier) 38 (2002) 393-422.
• Imrich Chlamtac, Marco Conti, etc., Mobile Ad Hoc Networking:  imperatives and challenges, Ad Hoc Networks (Elsevier) 1 (2003) 13-64.

Grading Plan:

The final grade will be based on:

30% Homework

30% Presentation: each student is responsible for presenting paper(s) and leading a discussion on a selected topic.
40% Project: each student will work on a project involving analysis, simulation, or implementation, and prepare a final project report.

---