DIMACS Summer School on Foundations of Wireless Networks and Applications

August 7 - 18, 2000
DIMACS Center, CoRE Building, Busch Campus, Rutgers University, Piscataway, NJ

1.

Algorithmic Issues in Wireless Communications
Matthew Andrews, Bell Labs

In this tutorial we shall examine a number of algorithmic
problems that arise in wireless networks.  Given the fact that
wireless spectrum is a scarce resource, it is essential that we use it
efficiently.  The type of problems that we must address depend on
whether the network is a voice or data network and on whether it is a
TDMA or CDMA network.  For example, in a TDMA network we are most
concerned with the assignment of time slots and frequencies whereas in
a CDMA network we are most concerned with the best way to assign power
among the users.

During the tutorial we shall address both short time-scale issues
(such as the best way to assign resources to a voice call and data
burst) and long time-scale issues (such as the best way to assign
frequencies to the basestations in a wireless network).



2.

Personal Area Networking over Bluetooth
Pravin Bhagwat, AT&T Research 

Bluetooth is a promising new technology that is aimed at supporting wireless
connectivity among  cell phones, headsets, PDAs, digital cameras, and laptop
computers. Initially, the technology will be used as replacement for
point-to-point cables, but solutions for forming personal area network of
Bluetooth devices will evolve in the near future. This tutorial is aimed at
computer professionals, academics, network architects, and application
developers who want to develop deeper understanding of  this new technology.
The tutorial will also illustrate in what ways low cost, low power, and form
factor features of Bluetooth are different from other short range wireless
technologies, such as 802.11 and HomeRF. 

The tutorial will first provide the
necessary background in radio communication, signal processing, and low
power circuit design and then explain the design choices made in Bluetooth
1.0 specifications. A detailed discussion of  radio, baseband, link manager,
L2CAP, RFCOMM, and SDP layers will be presented next. 

In principle, using
Bluetooth radio modules it is possible to form an ad hoc network of devices,
but the techniques for forming such networks have not been fully explored
yet. The last quarter of the tutorial will be devoted to the review of the
initial results in this area (namely, the techniques for characterizing
Bluetooth scatternets, algorithms for self-organization, and methods for
routing packets over Bluetooth scatternets). The tutorial will conclude with
a discussion of open problems.

Outline

Review of basic concepts (RF, signal processing) and technology
trends (low cost, low power, small form factor)

Overview of Bluetooth 1.0 specifications  

Multi-hop networking over Bluetooth scatternets
 
TCP/IP over Bluetooth 

Future directions and open problems
 

Intended Audience	

The tutorial is intended for researcfers and practitioners who want to learn
more about Bluetooth 1.0 standard. Computer professionals who want to
develop better understanding of technology trends and identify new market
opportunities in the space of short range wireless networking will also
benefit from this tutorial. Basic understanding of layered network
architecture is expected. No background in analog radio, signal processing,
or wireless communication is required. Researchers who want to identify open
research problems in the area of personal area networking will also find
this tutorial very useful.



3.

Scheduling and Medium Access Issues in Wireless Packet Networks
Vaduvur Bharghavan, University of Illinois at Urbana-CHampaign

In this tutorial, I will first briefly survey the literature on
medium access protocols for shared channel multi-hop wireless
networks. I will describe some of the key features of the
IEEE 802.11 MAC protocol and discuss its performance and
implications on higher layers.

I will then introduce the problem of packet scheduling in wireless
channels and briefly survey the recent literature on this problem.
I will conclude with a detailed discussion of fairness models for
medium access and scheduling in shared channel multi-hop wireless
networks.



4.

Optimization for GSM Wireless Networks
Chandra Chekuri and Lisa Zhang,  Bell Labs

A GSM network is a TDMA (time division multiple access)
wireless system coupled with frequency reuse.  Two common performance
measures of a wireless system is coverage and capacity.  The former
measures the area where the signal quality is good and the latter
measures the number of calls that can simultaneously operate in the
system.  To optimize these two quantities, we adjust antenna
parameters and create a suitable frequency plan.  The former is a
large-scale non-linear optimization problem and the latter is a
combinatorial problem that resembles coloring. We present graphs that
show the improvements due to our optimization.



5.

Zygmunt Haas 
Cornell University
Mobile Ad-Hoc Networks

Ad-hoc Networks are network architectures that can be rapidly 
deployed and that do not rely on preexisting communication
infrastructure. Due to mobility, the topology of a mobile ad-hoc 
network is continuously changing. Thus, a self-reconfiguration 
capability is required. Furthermore, because of the large span 
of the networks, multi-hop routing is usually employed. Finally, 
due to lack of centralized entities all algorithms are distributed. 
Challenges in design of ad-hoc networks stem from the two main 
facts: the topology is unstable and there is no centrally available 
information. This tutorial addresses four areas in the design of
ad-hoc networks: Medium Access Control Schemes, Routing Protocols,
Mobility Management Algorithms, and Application of the Ad-Hoc
Technology.
	
The goal of the tutorial is to comprehensively expose the 
state-of-the-art in ad-hoc networking. It is a focused course
with the emphasis on the applicability of the ad-hoc technology
to current and future systems in both, the commercial and
the military markets.

INTENDED AUDIENCE:
The tutorial is targeted towards broad audience, both from the 
academic and the industrial environments. It will provide the 
attendees with a focused view on what are the issues, the 
solutions, and the techniques in design of ad-hoc networks.



6.

Zygmunt Haas 
Cornell University
Wireless Networks: from Cellular to Ad-Hoc

This tutorial addresses the basic networking concepts of mobile 
wireless networks, exposing both the theoretical and practical 
aspects of mobile communication. As an introduction, basic enabling 
technology will be presented, such as the cellular principle and 
multiple access technologies (e.g., CDMA). Following this 
introduction to mobile radio, we will investigate the underlying 
techniques used in design and operation of cellular networks, 
including handoff schemes, channel assignment and power control 
algorithms, common-air protocols (e.g., IS-54/136, IS-95, GSM, CDPD,
etc), and microcellular architectures. Some more advanced concepts, 
such as macrodiversity and multi-tier wireless networks, will be 
discussed as well. Next, we will address the subject of user mobility 
support in the wireless environment. In particular, call processing 
functions, which include roaming, routing, and registration will be 
explained. As an example, the comparison of the Cellular Digital 
Packet Data (CDPD) and the Internet Mobility Support will be 
presented. We will conclude the course with a view to the future by 
introducing the concept of Ad-Hoc Networks. In particular, we will 
elaborate on the MAC and the routing protocols that are proposed for
the ad-hoc networking environment.

OUTLINE:
	
1. Introduction to Mobile and Wireless Systems - 0.5 hour
2. Enabling Technologies 
 (FDMA, TDMA, CDMA, TDD/FDD, the cellular principle) - 1 hour
3. Techniques in Cellular Radio Networks (channel assignment 
algorithms, handoff schemes, diversity techniques,
sectorization/cell splitting, micro/pico-cellular) - 1.5 hour
4. Radio Propagation Impairments (incl. short- and long-term 
fading) - 0.5 hour
5. Some Common Air Interfaces (AMPS, IS-54/136, IS-95, GSM, CDPD) 
- 1.75 hour
6. Mobility Management in Wireless Networks (call processing and 
signaling) - 1 hour
7. Cellular Digital Packet Data (CDPD) and Mobility in the Internet 
- 0.5 hour
8. Ad-Hoc Networking Principles (incl. MAC and Routing protocols)
- 1 hour
9. Summary and Concluding Remarks - 0.25 hour
10. References

INTENDED AUDIENCE:
The tutorial is targeted towards a broad audience, both from the 
academic and the industrial environments. It is designed to 
provide the attendees with a focused view on what are the issues, 
the solutions, and the techniques used in today's and future
wireless networks.




7.

Rittwik Jana, AT&T Labs - Research
Wireless Application Protocols

The talk will cover the following topics:

1. WAP Market Overview
2. Market development and forecasts
3. Messages for Operators
4. Messages for Content providers
5. Messages for suppliers
6. Users and Applications
7. WAP business models
8. WAP technology



8.

Thyagarajan Nandagopal, University of Illinois at Urbana-Champaign
Fair Scheduling in Wireless Networks

In wireline networks, fair queueing has long been a popular paradigm 
for providing fairness and bounded delay link access. However, adapting 
fair queueing to the wireless domain is non-trivial because of the unique 
problems in wireless channels, such as location-dependent and bursty 
errors, and channel contention.  Consequently, the fair queueing algorithms 
proposed in literature for wireline networks do not apply directly to wireless
networks. In this tutorial, I will survey the state-of-the art techniques for 
enabling fair queueing in wireless (cellular) data networks. 

I will also present a wireless fair service model that captures the 
scheduling requirements of wireless fair scheduling algorithms, and compare 
the various algorithms in recent literature in terms of this fair service 
model.

INTENDED AUDIENCE:

The tutorial is targeted towards an audience with a basic knowledge of 
traditional fair queueing (or processor-sharing) algorithms. The aim is 
to provide the attendees with a clear view of the issues and solutions 
in the design of wireless fair queueing algorithms.



9.

Chris Rose, Rutgers University
A Theoretical Tour of Wireless Communications

This half day tutorial offers a conceptual and theoretical development of 
wireless communications networks.  In a possibly misguided attempt to 
out-Feynman Feynman we will start from basic principles and seek to understand
the various physical considerations which go into wireless network design.
Topics covered will include communications theory, wireless channels, spectrum
allocation and wireless network architectures.  We will also present a 
speculative new architecture for wireless data networks inspired by 
information theory and the recognition that data can often tolerate delay.

We will then move up the "protocol stack" and consider mobility management 
issues for both traditional wireless systems and our proposed new architecture.
The overall intent for this tutorial is that participants understand the 
fundamental considerations of wireless systems and for those with the 
inclination, be confident of their ability to dig deeper into the theoretical 
terrain.



10.

Algorithmics issues in scheduling data delivery
Nicolas Schabanel, DIMACS - AT&T Research

Data delivery technics evolve with technology. With the generalization of
naturally broadcasting medium, new scheduling issues have araised. New
solutions and technics allow to reduce the delivery delays for broad
audience. This tutorial will review and discuss these technics from the
theoretical models of the problems to the algorithmic solutions.

Intended audience: This tutorial is targeted towards a broad audience,
both from academic and practisionners. It is designed to provide the
attendees with focused view on the models, issues, solutions designed for
data delivery in next generation networks.



11.

Christian Scheideler, Paderborn University
Models and Techniques for Communication in Power-Controlled Mobile 
Ad-Hoc Networks

A mobile ad-hoc network is a collection of wireless mobile
hosts forming a temporary network without the aid of any established
infrastructure or centralized administration.  This type of network is
of great importance in situations where it is very difficult to
provide the necessary infrastructure, but it is a challenging task to
enable a fast and reliable communication within such a network. In
this talk, I will concentrate on models and results for so-called
power-controlled mobile ad-hoc networks: networks where the mobile
hosts are able to change their transmission power.
I will distinguish between the cases that the mobile stations
use or do not use SDMA (space division multiple access) to transmit
messages. The results I will present for these models will center
around connectivity and routing problems.



12.

Mani Srivastava, University of California - Los Angelos
Energy Efficient Wireless Systems

Energy efficiency directly affects battery life and portability,
and is perhaps the single most important design metric in 
mobile and wireless systems. It is becoming even more important 
with a variety of embedded devices, such as sensors, becoming 
wirelessly networked. The mismatch between the slow improvements
in batteries on the one hand, and increasing user expectations 
and shrinking form factors in wireless devices on the other hand,
makes energy efficient wireless system design particularly
challenging.

Wireless systems, where the energy consumption for "communication"
is dictated by the link budget, require going beyond low-power 
implementation techniques developed for "computing" systems. Higher 
layers of the system also need to be power aware and energy efficient.
A comprehensive discussion of battery technology, sources of power 
consumption in computing and communication, and generic low-power 
hardware and software implementation techniques will be followed in
the tutorial by a presentation of techniques such as low-power 
network protocols that are specific to wireless and mobile systems. 
Commercial trends such as low-power "mobile" processors and power 
management APIs, and latest research will also be described. 


Outline:

  1. Introduction
      - overview of the field, commercial and technology trends
      - sources of power consumption
      - battery technology
  2. Generic low-power design techniques
      - voltage scaling, dynamic voltage/frequency
      - software: estimation, scheduling, data structures
  3. Power consumption in radios
      - sources of power consumption, link budget
      - techniques for lower-power and power-aware radios
  4. Low-power network protocols
      - energy efficient link layer
      - low-power MAC protocols
      - power-aware routing
      - power-aware transport protocols
  5. Application and OS level techniques
      - CPU and subsystem shutdown, predictive shutdown
      - scheduling with dynamic voltage/frequency CPUs
      - explicit management of power by applications
      - power-efficient encryption
  6. Commercial and research trends
      - new "low-power" processors for mobile applications
      - APIs for OS level power management
      - ultra low-power wireless sensor networks
      - ambient power havesting and scavenging 



13.

Vinay Vaishampayan, AT&T Labs - Research
Multiple Description Data Compression

Packet loss is a problem for voice and video communications over a
packet network, especially when no QoS guarantees are available. This
problem is especially severe when the data is highly compressed and the
packet size is large. Multiple description systems are a class of data
compression systems designed for unreliable channels such as the
packet loss channel.

This tutorial will trace the multiple description problem from its information
theoretic origins in the late 1970's to recent design work along with
applications to voice and video communications on lossy packet networks.
Research work in this area has drawn from diverse areas--information theory,
quantization theory, discrete mathematics and geometry. Key theoretical
developments will be highlighted.



14.

Roy Yates, Rutgers University
Trends in Wireless Data

This tutorial introduces wide area and local area wireless systems. 
With an emphasis on suitability for Internet access, radio access 
technologies, includingCDMA, TDMA, and frequency hopping, will be 
introduced and characterized. Fundamental bit rate and coverage 
tradeoffs  of current second generation and proposed third generation 
systems will motivate research directions for next generation wireless 
data systems.

Other Workshops

DIMACS Homepage