IMA "Hot Topics" Workshop: Wireless Networks

August 8-10 2001

Material from Taks

Rajeev Agrawal (Motorola)

Scheduling in Multimedia Wireless Networks

Wireless systems in the future will have to provide multimedia services where different users have different physical-layer and network-layer QoS requirements. We investigate the use of power control, processing gain, and scheduling in CDMA systems to accommodate these diverse service requirements. First, we derive the time-sharing capacity region for any channel state which is given in terms of the convex hull of the set of user bit rates that can be supported simultaneously subject to physical-layer QoS requirements. Therefore by choosing any bit rate vector in the time-sharing capacity region, we automatically satisfy the physical-layer QoS requirements. Thus, it is the control knob used by the scheduler to satisfy the network layer QoS requirements. We consider the problem of scheduling on fading channels where the channel state varies with time. We design a class of scheduling policies that guarantees system stability. We use simulation to compare the performance of various policies in this class. Specially, we show that the new "Minimum Draining Time" policy has certain desirable qualities vis-a-vis the "Cone" policy and "Modified Cone" policy. All three are special cases of the class of policies for which we show stability.

Venkat Anantharam (EECS Department University of California, Berkeley) ananth@robotics.EECS.Berkeley.EDU

A New Look at the Generalized Distributive Law

(Joint work with Payam Pakzad).

The "Generalized Distributive Law" provides an algorithm for solving the problem of marginalizing a function of several variables over certain subsets of those variables. It has been recognized as underlying a number of important algorithms that are widely used in physical layer communications, such as the BCJR algorithm, the Viterbi algorithm, certain fast transforms, etc.. Convergence of the algorithm to the correct answer is known if a certain "junction tree" condition holds, and it is generally necessary to force this condition by grouping variables, which results in a provably convergent algorithm of higher complexity. However, it is also the practice in several important applications to avoid such grouping of variables, thus using lower complexity versions of this algorithm even though no one knows the conditions for convergence to the correct answer. This is the case, for instance, in some popular decoding algorithms for turbo codes and low density parity check codes.

We decided to take a fresh look at the problem that the GDL attempts to solve by reformulating the marginalization problem in a broader context. In the process we have developed a parallel theory to the existing one which includes the current one as a special case. It is of particular interest that our theory offers a novel way to force (an analog of) the "junction tree" condition and appears to be able to do so without taking such a big complexity hit. Thus our theory leads to new algorithms which are provably convergent. Also, in some of the examples we have examined, such algorithms seem to offer significant improvements over the provably convergent algorithms that would be derived using the current theory.

Developing more convincing examples (if such exist !) is ongoing work. In this talk our theory will be presented together with such examples as we currently have.

Randall A. Berry (Department of Electrical and Computer Engineering, Northwestern University)  rberry@ece.nwu.edu

Power and Quality of Service Trade-offs in Wireless Networks

In wireless networks, physical layer quantities, such as the transmission rate and power, can be dynamically controlled in response to changing channel conditions and user demands. Such techniques can impact not only physical layer performance but also various "network" level quality of service metrics. We will discuss some models which take into account both physical layer concerns as well as some higher layer service metrics. Initially we consider a single user communicating over a wireless channel; the emphasis here is on understanding how to allocate physical layer resources in response to channel fading. Assume arriving data for the user is buffered until it is transmitted and the user's quality of service is related to the buffer delay. In this setting we study the trade-off between the user's average transmission power and the resulting quality of service. Our focus is on understanding these trade-offs in various asymptotic regimes. We also discuss some multi-user situations, where the allocation of resources between users becomes important.

Covering, Percolation, and Wireless Networks

In this talk we show a connection between covering algorithms and continuum percolation, and present a new stochastic model of wireless communication networks.

We consider "clustered" wireless networks, abstracted as a set of disks (wireless gateways) that cover a set of random points (wireless clients) in the plane.

We extend Continuum Percolation Theory to describe the covering process that forms the wireless network, and look at the percolation properties of this extended model.

In this way, we describe the global connectivity state of the network, for different classes of covering algorithms.

Finally, some open problems and possible extensions of the theory will be presented.

Piyush Gupta (Lucent Technologies - Bell Laboratories)  pgupta@research.bell-labs.com

Towards an Information Theory of Large Wireless Networks

Last few decades have seen widespread deployment of cellular voice and data wireless networks and satellite communication systems. These applications have motivated researchers to extend Shannon's information theory for single-user channel to some involving communication among multiple users; a few such examples are multiple-access channel, broadcast channel, and interference channel. Both the above applications as well as the channels used for analyzing them involve mainly single-hop wireless communication.

More recently, there has been considerable interest in another type of wireless networks, namely, multi-hop or ad hoc wireless networks. These networks consist of a group of nodes that communicate with each other over a wireless channel without any centralized control. Examples are in networking mobile computer users on a campus, Bluetooth, HomeRF, and automated transportation systems.

This is joint work with Prof. P. R. Kumar.

Window Flow Control for a Wireless Packet Data Network

In this talk, we develop a new window control algorithm suitable for a transport-layer protocol for a data stream that includes a final, lossy wireless channel. We use a simple queueing model with feedback, with a queue for the base station, which is served by a 2 state Markov wireless channel to the wireless client, and then fed back to the server. We derive the optimal window size, as a function of measurable packet statistics.

Babak Hassibi (Caltech) hassibi@systems.caltech.edu

Space-Time Processing for Wireless Communications    pdf

The use of multiple antennas can, in theory, significantly boost channel capacity as well as lower the probability of error of a wireless communications link. The main signal processing challenge in multi-antenna communications is to devise practical space-time transmission schemes that are simple, yet efficient: simple so that all the processing can be done in real-time, and efficient so that the high rates promised by theory can be attained. In this talk I will describe several recent advances in the design of space-time codes for both quasi-static (as in fixed wireless) and rapidly fading (as in mobile wireless) channels, as well as some new work in the development of efficient (polynomial-time) maximum-likelihood decoding algorithms. I will also attempt to figure out what this all means for wireless networks.

James P. Hughes (Storage Technology Corporation)

Expensive Cryptographic Operations by Wireless Devices

Wireless devices are very power conscious. As these devices get more interconnected, the number or asymmetric cryptographic operations, (key exchanges, signature generation, signature checking, etc) will grow exponentially. This talk will discuss expected applications, performance implications and the status of various candidate algorithms.

P.R. Kumar (Franklin W. Woeltge Professor of Electrical and Computer Engineering, and Research Professor, Coordinated Science Lab, University of Illinois-Urbana Champaign)  prkumar@control.csl.uiuc.edu

Wireless Networks: Analysis, Protocols and Architecture    pdf

Under some models the traffic carrying capacity of wireless networks scales as the reciprocal of the square root of the number of nodes. We present a brief synopsis of this proof.

Wireless networks present issues and problems not arising in wired networks. This necessitates the development of several protocols. We present three such protocols; for power control (COMPOW), media access (SEEDEX), and for routing (STARA).

(Joint Work with Gupta, Kawadia, Narayanaswamy, Rozovsky, and Sreenivas).

Alexander Stolyar (Bell Labs, Lucent Technologies)  stolyar@research.bell-labs.com

QoS Scheduling of Multiple Users Sharing a Time-Varying Wireless Medium

We start with the following model motivated primarily by the problem of Quality-of-Service (QoS) scheduling in wireless systems, like CDMA HDR. Multiple data flows (users) share a channel with capacity that varies in time randomly and 'asynchronously' with respect to different users. The problem: How to schedule transmissions so that the maximal number of flows can be served at a desired QoS level.

We identify two classes of scheduling disciplines which are 'throughput optimal', i.e. have the maximum possible stability region. We demonstrate that using these disciplines with the appropriate choice of parameters allows to efficiently control QoS.

Then, to explain "nice behavior" of throughput optimal disciplines, we consider a heavy traffic regime in a more general model which we call a "generalized switch." This model includes as special cases the model of multiuser data scheduling in a multiantenna system, the input-queued cross-bar switch model, and a discrete time version of a parallel server queueing system. We show that, under a non-restrictive in applications 'complete resource pooling' condition, a simple `MaxWeight' discipline minimizes the system workload and induces a 'state space collapse' - in the limit the vector of queue lengths is always proportional to some fixed vector.

Leandros Tassiulas (Department of Electrical and Computer Engineering, University of Maryland), leandros@isr.umd.edu

Quality of Service Provisioning in Wireless Networks

Scheduling algorithms that provide guaranteed service rates in wireless ad-hoc networks will be presented in this talk. Providing quality of service guarantees is a goal that attracted a lot of efforts over the last decade. Starting with fair-queueing, a wide variety of switch scheduling algorithms were proposed that can support quite stringent quality of service requirements in wireline networks. Little has been done in this respect in wireless networks. The interdependence of different links at the access layer in combination with mobility makes the problem fairly challenging and the available results are mostly on stability guarantees. An algorithm for providing rate guarantees in a wireless ad-hoc network will be presented here. The algorithm is a combination of a "fair-queueing like" token allocation mechanism at the node level and a matching selection algorithm at the link level. The algorithm guarantees max-min fairness in rate allocation at the network level irrespectively of the traffic load of the diffreent flows. When the flows have unequal priorities, different operating regimes can be achieved by appopriate selection of a set of weights.

(Joint work with S. Sarkar).

Mitchell Trott (ArrayComm, Inc.)  mitch@arraycomm.com  http://www.arraycomm.com

Least-squares Beamforming in Wireless Networks

Beamforming methods based on linear least squares have been widely proposed for use with wireless systems employing multiple antennas. Such methods have been suggested for both reception and transmission. We survey the existing research in this area, focusing particularly on the interaction of power control, receive beamforming, and transmit beamforming in cellular networks. We show that transmit beamforming based on least-squares receive processing can have surprising behavior in a network.

In practical systems least-squares solutions are based on limited training data. Are the basic characteristics of beamformers based on perfect training (i.e., MMSE beamformers) preserved in the face of finite training data? We use results developed the 1970s for maximum likelihood spectral estimation to provide a partial answer to this question for transmit beamforming.

David Tse (U.C. Berkeley, EECS)  dtse@eecs.berkeley.edu

A central feature of mobile wireless networks is the random fading of the channel strengths of the underlying communication links. Channel fading has traditionally been viewed as a form of unreliability that has to be compensated for. In this talk, we argue a different point of view, that channel fading is a form of randomization that can be taken advantage of in the design of wireless networks. This viewpoint is particularly relevant in a network with multiple users, each having independent fading channels.

We first motivate this notion of multiuser diversity from information theoretic considerations. We discuss how this concept is used in the design of the downlink packet scheduling algorithm for Qualcomm's HDR wireless data system. We then show how multiple transmit antennas can be used to randomize the channel and increase the multiuser diversity gain in environments with limited fading. Finally, we explain how the idea of multiuser diversity can be used to greatly increase the throughput of mobile ad-hoc networks for delay tolerant applications.

Joint works with P. Viswanath, R. Laroia and M. Grossglauser.

Phil Whiting (Mathematical Sciences Research Center, Lucent Technologies - Bell Laboratories)  pawhiting@lucent.com

Dynamic Rate Control Algorithms for HDR Throughput Optimization

The relative delay tolerance of data applications, together with the bursty traffic characteristics, opens up the possibility for scheduling transmissions so as to optimize throughput. A particularly attractive approach, in fading environments, is to exploit the variations in the channel conditions, and transmit to the user with the currently `best' channel. We show that the `best' user may be identified as the maximum-rate user when the feasible rates are weighed with some appropriately determined coefficients. Interpreting the coefficients as shadow prices, or reward values, the optimal strategy may thus be viewed as a revenue-based policy, which always assigns the transmission slot to the user yielding the maximum revenue.

Calculating the optimal revenue vector directly is a formidable task, requiring detailed information on the channel statistics. Instead, we present adaptive algorithms for determining the optimal revenue vector on-line in an iterative fashion, without the need for explicit knowledge of the channel behavior. Starting from an arbitrary initial vector, the algorithms iteratively adjust the reward values to compensate for observed deviations from the target throughput ratios.

Numerical experiments are presented which demonstrate long-run convergence of the algorithms and the transient performance is also examined. Generalisations of the approach beyond the one-user-at-a-time case are also discussed.

Material from Taks

Wireless Networks

2001-2002 IMA Thematic Year on Mathematics in the Geosciences