Spring 2006 CSE370 Wireless and Mobile Networking

 

Locations and Hours:

Monday and Friday, 12:50pm-2:10pm @ Melville LBR N4072

Instructors: 

Instructor: Prof. Jie Gao, 1415 Computer Science Building. Email: jgao at cs dot sunysb dot edu. Office hour: Friday 2:10pm - 4pm or by appointment.

Announcements:

Course Description:

This course is a 3-credit undergraduate course on wireless and mobile networking.

Prerequisites:

CSE 310, Data Communication and Networks (or an equivalent course). Review materials from CSE 310: CSMA/CD, Ethernet LAN, Routing protocols, IP, TCP.

Course Materials:

  • Textbook: Jochen Schiller, Mobile Communications, 2/e, Addison-Wesley, 2003 (required)
  • Kurose and Ross, Computer Networking: A Top-Down Approach, Addison-Wesley (optional, same text used in CSE 310).
  • Principles of Wireless Networks, Pahlavan and Krishnamurthy, Prentice Hall, 2002 (optional, in CS library reserve).
  • Papers from literature and handouts distributed in class, posted in this web page, or kept in library reserve.

Grading and Requirements:

Grading includes Midterm: 25%, Final: 25%, Homework: 25%, Project: 25%. Late homework gets 25% penalty per day. Project will include substantial programming and is to be done in groups of 2 students. Project will be discussed at the beginning of March.

Tentative Syllabus:

Introductory topics (0.5 week)

·   Challenges of wireless and mobile networking

·   Essential backgrounds

Characteristics of Wireless Transmissions (2 weeks)

·   Signal propagation, path loss and fading

·   Multiplexing

·   Modulation

Medium Access Control (MAC) (2 weeks)

·   Notions of SDMA, FDMA, TDMA

·   Pure random access protocols -- Aloha and related protocols

·   CSMA-based protocols

Wireless LAN and PAN (2 weeks)

·   Infrastructure and ad hoc networks

·   IEEE 802.11 standard

·   Bluetooth

Mobile Infrastructure-based Networks (2 weeks)

·   Location/mobility management

·   Mobile IP

Ad Hoc Networks (2 weeks)

·   Dynamic routing protocols 

·   Location-based protocols

·   Emerging topics: sensor networking

Mobile Transport Layer (1.5 week)

·   TCP over wireless

·   Performance issues

Cellular Network Fundamentals (1.5 weeks)

·   Capacity issues

·   Channel assignment algorithms

Syllabus:

 

Lecture Topics

Required readings

Slides

1/27

Introduction

Chap 1

 

1/30

Characteristics of Wireless Transmissions Signal propagation, path loss and fading

Chap 2.1-2.4

Lecture 2

2/3

Multiplexing, spread spectrum

Chap 2.5, 2.7

Lecture 3

2/6

Modulation

Chap 2.6

Lecture 4 Homework 1 out

2/10

Cellular systems, Medium Access Control (MAC), SDMA, FDMA, TDMA, Aloha, Slotted Aloha

Chap 2.8, 3.2-3.4.3, Aloha papers

Lecture 5

2/13

TDMA, CSMA

Chap 3.2, 3.4

Lecture 6

2/17

CDMA, Intro to networking layer

Chap 3.5, 7.1-7.3.3

Lecture 7

2/20

Wireless LAN and PAN, 802.11

Chap 7.3.4-7.4

Lecture 8

Homework 1 due Homework 2 out

2/24

Ad hoc network routing, DSR

Chap 8.3, DSR paper

Lecture 9

2/27

DSDV, AODV

DSDV, AODV paper

Lecture 10

3/3

Geographical routing

GPSR paper

Lecture 11

3/6

Discussion on projects and Review session for midterm

 

Lecture 12

Homework 2 due

3/10

In-class Midterm

 

 

3/13

Location management in cellular networks

Intro of [BD99]

Lecture 13

3/17

Location management in ad hoc networks

GLS paper

Lecture 14

3/20

Mobile IP

Chap 8.1

Lecture 15

3/24

Mobile Transport Layer

Chap 9.1-9.2, Nitin Vaidya's tutorial on TCP over Wireless Networks

Lecture 16

3/27

Mobile TCP

 

Lecture 17

Homework 3 out

3/31

Sensor networks overview

[Estrin99][Culler04]

 

4/3

Localization I

[Savvides01][Savvides03]

Lecture 19

4/7

Localization II

[Howard01][Moore04]

Lecture 20

4/17

Routing with virtual coordinates

[Rao03][Newsome03]

Lecture 21 Homework 3 due

4/21

Topology control I

 

Lecture 22

4/24

Topology control II

[Wattenhofer01]

Lecture 23

4/28

No class

 

 

5/1

Review session

 

Lecture 24

5/5

Final project presentation

 

 

5/12

Final Exam 2-4:30pm

 

 

Reading list:

The original papers about Aloha, Slotted Aloha:

1.        The Throughput of Packet Broadcasting Channels, Norman Abramson, IEEE Transactions on Communications, Vol. COM-25, No. 1, 117-128, January, 1977.

2.        Development of the ALOHANET, Norman Abramson, IEEE Transactions on Information Theory, Vol IT-21, No. 2, 119-123, March, 1985.

Routing in ad hoc networks

1.        DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. in Ad Hoc Networking, edited by Charles E. Perkins, Chapter 5, pp. 139-172, Addison-Wesley, 2001.

2.        Charles E. Perkins and Elizabeth M. Royer. "Ad hoc On-Demand Distance Vector Routing." Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100.

3.        Charles Perkins and Pravin Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications, 234—244, 1994.

4.        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 webpage.

Location management

1.        [BD99] Amiya Bhattacharya and Sajal K. Das, LeZi-Update: An Information-Theoretic Approach to Track Mobile Users in PCS Networks, Mobicom’99.

2.        GLS paper: Jinyang Li, John Jonnotti, Douglas De Couto, David R. Karger and Robert Morris, A scalable location service for geographic ad hoc routing, Mobicom’00.

Sensor networks applications

1.        [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).

2.        [Culler04] D. Culler, D. Estrin, M.Srivastava. Overview of Sensor Networks, IEEE Computer, Aug. 2004.

Localization

1.        [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.

2.        [Savvides03] A. Savvides, H. Park, and M. B. Strivastava. The n-hop multilateration primitive for node localization problems, Mobile Networks and Applications, Volume 8, Issue 4, 443-451, 2003.

3.        [Howard01] A. Howard, M. J. Mataric, and G. Sukhatme, Relaxation on a Mesh: a Formalism for Generalized Localization, IEEE/RSJ Internaltionsl Conference on Intelligent Robots and Systems, October, 2001.

4.        [Moore04] D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, Proc. ACM SenSys 2004.

Virtual coordinate for routing

1.        [Rao03] Ananth Rao, Christos Papadimitriou, Scott Shenker, and Ion Stoica, Geographical routing without location information, Proc. MobiCom'03, pages 96 - 108, 2003.

2.        [Newsome03] James Newsome, Dawn Song, GEM: Graph EMbedding for Routing and Data-Centric Storage in Sensor Networks Without Geographic Information, Proc. Sensys'03.

Topology control

 

1.        [Wattenhofer01] Roger Wattenhofer, Li Li, Paramvir Bahl, and Yi-Min Wang, Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks, Infocom’01.

Programming projects:

The programming project can be done in groups of 2 students. Each group will turn in a report on the basic algorithm, implementation and performance evaluation. The project can be selected from the following topics. You are welcome to discuss with me about your ideas.

1.        Power management in sensor networks.

Suppose there is a group of static sensors deployed in a squared region. Each sensor has a fixed coverage modeled by a disk of radius 1. All the sensors collectively cover the whole region. In other words, each point of the region is covered by at least one sensor. The battery power of each sensor is limited. So you would like to turn off a sensor to save power. The goal is to design a power management algorithm for the sensors that decides which and when a sensor turns itself off and goes to sleep. The major considerations include:

a)        The region is reasonably covered. It is preferred that each point is covered by at least one sensor at any time. But you can relax the coverage condition for simplicity of the algorithm.

b)        The sensors are load balanced. If a sensor gets used too much, it may run out of battery and die.

c)        We prefer to have a distributed algorithm. Any work that uses global scheduling of the sensors need to address how to implement the global scheduling in a distributed way.

You can make also assumptions such as the nodes are synchronized and they know their locations. There can be many approaches to this problem, such as:

a)        Assume the sensors are synchronized. Design a scheduling schedule that turns sensors on and off.

b)        Use a random schedule (with the idea from Aloha). Each sensor has its own sleeping schedule. A sensor may wake up and communicates to the neighboring nodes and decide on its own sleeping schedule. Intuitively, if a sensor finds many awake sensors in its neighborhood, it would like to go back to sleep sooner. Otherwise, it may stay longer until new sensors wake up. You can also design a handoff scheme where a sensor informs others to stay on if it goes to sleep.

You are required to design a scheduling scheme, implement it (in ns-2, for example) and evaluate its performance. It is a project with open ends. So use your intelligence and think out of the box. J

2.        Routing in ad hoc mobile networks.

Node mobility makes routing in ad hoc networks a challenging problem. Networks of a set of mobile nodes have constantly changing topologies. The explicit maintenance of the network topology may create heavy overhead, as in DSDV. However, without the knowledge of network structure as in on-demand protocols (DSR, AODV) route discovery may have to rely on network-wide flooding. The challenge of designing efficient routing protocols is to decide on which information is maintained by the network so as to facilitate route discovery. Geographical routing algorithms, for example, choose to keep the geographical locations of the nodes.

Mobility, however, is not necessary a bad thing. From an information theoretic point of view, mobility helps to improve the network capacity. A node holding a packet for another node may physically move to the destination to deliver the packet. For many application scenarios, we can explicitly use node mobility to help routing.

This project is to explore how to use node mobility to help routing. The requirement is to

a)        Identify a realistic application scenario. Identify the mobility model, traffic patterns and quality of service requirement. For an example, consider vehicles moving on highways. The mobility model is simple. An ad hoc network on vehicles can be used for real-time traffic monitoring and route suggestions etc. These applications often have a high requirement on delay. Cars can have GPS so they know their location information. Motion trajectories for other nodes can not be controlled. In another example, for a group of collaborative autonomous robots, we can explicitly ask a robot to move towards the destination for message delivery. Motion trajectories can be complicated. Contention needs to be handled (multiple nodes may want the same robot to deliver messages for them).

b)        Design a routing algorithm that uses mobility information to help message delivery. For example, the basic geographical forwarding chooses the neighbor closest to the destination. In a mobility-aware algorithm, one can choose a neighbor whose moving direction is towards the destination.

c)        Compare the performance of mobility-aware algorithm with the original algorithm.

Last updated: 3/13/06