DIMACS Summer School on Foundations of Wireless Networks and Applications

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



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
Contacting the Center
Document last modified on August 2, 2000.