University of Minnesota
University of Minnesota
http://www.umn.edu/
IMA Web

Abstracts and Talk Materials:

2005 Summer Program: Wireless Communication

June 22-July 1, 2005

Rajeev Agrawal (Motorola)

Convergence and optimality of channel aware scheduling and resource allocation algorithms

With an abstraction of serving rate-adaptive sources on a broadcast-type wireless channel as a utility maximization problem, it is shown how one can design many intuitive online scheduling policies based upon the feedback that one obtains at the scheduler. Using a stochastic approximation argument it is then shown that the constructed algorithms converge to optimal solutions of the utility maximization problem over different sets which critically depend on the quality of the feedback information.

We then apply the theory developed above to the downlink in a CDMA based wireless network. In terms of operational variables the problem is to select a subset of the users for transmission at each transmission oppurtunity and for each of the users selected, to choose the modulation and coding scheme, transmission power, and number of codes used. We refer to this combination as the physical layer operating point (PLOP). Each PLOP consumes different amounts of code and power resources. Thus, the task is to pick the ``optimal'' PLOP taking into account both system-wide and individual user resource constraints that can arise in a practical system. Using an information theoretic model for the achievable rate per code results in a tractable convex optimization problem. By exploiting the structure of this problem, we give algorithms for finding the optimal solution with geometric convergence. We also use insights obtained from the optimal solution to construct low complexity near optimal algorithms that are easily implementable. Numerical results comparing these algorithms are also given.

Matthew Andrews (Lucent Technologies)

Scheduling high speed data in (adversarial) wireless networks

Wireless networks for transmitting high speed data are becoming increasingly common. Such networks lead to new and interesting scheduling problems, in large part because the quality of a wireless channel constantly changes over time. It is important to schedule in an opportunistic fashion, i.e. we want to transmit data between two users during the times when the associated wireless channel has good quality.

A number of models have been proposed for studying such systems. These differ according to the assumptions made on the arrival process, the assumptions made on the channel conditions, and the metrics that are to be optimized. In this talk we shall survey some of these models and present contrasting scheduling results that arise in each model. We shall concentrate on the case in which the channel conditions are governed by an adversary and present limits on the optimum fairness and quality-of-service that can be achieved in the resulting adversarial environment.

Paul Anghel (University of Minnesota)

On the optimum power allocation in interference-free cooperative systems

We consider an interference-free fixed wireless cooperative system where transmissions from different terminals are orthogonal. In the proposed system the idled terminals help a source by relaying its information signal to the destination. We consider both regenerative and non-regenerative idled terminals (relays). For the inference-free system with non-regenerative relays, we show that maximizing mutual information for each user under total power constraint is a strictly quasi-concave maximization problem whose global optimal solution can be found efficiently. In fact, we provide a simple analytic formula for the optimum power allocation strategy, which is reminiscent of the water-filling principle. We also illustrate how the setup can be extended in order to allow for terminal mobility. For the regenerative system we consider two cases - full collaboration between relays and no-collaboration between relays - and show that in both cases the maximum mutual information under total power constraint can be found in polynomial-time.

Randall A. Berry (Northwestern University) http://www.ece.northwestern.edu/~rberry/

Spectrum Sharing Games

In wireless networks a key consideration is how to mitigate interference among multiple users in a given spectrum band. This is especially true in unlicensed or open bands, where users may be deployed without any centralized frequency planning or control. In this talk, we describe some simple mathematical models for sharing a given spectrum band. We discuss both a case where a spectrum manager controls access and a case where there is no manager and users implement a distributed algorithm to manage access. In the first case, we describe an auction mechanisms where the users bid for spectrum access. We model this auction as a game and characterize the equilibrium. In the second case, we discuss a distributed algorithm, in which users announce "price" signals which indicate the cost of interference to them. We relate this algorithm to a "fictitious" game, which in certain cases is supermodular. This relation is used to characterize the algorithms convergence. Extensions to multi-channel networks will also be discussed, where users can allocate their power over multiple frequency bands, as in a OFDM system.

Sem C. Borst (Lucent Technologies - Bell Laboratories)

Flow-level performance in wireless data networks

Channel-aware scheduling strategies provide an effective mechanism for improving throughput performance in wireless data networks by exploiting channel fluctuations. In the talk, we focus on the flow-level performance of channel-aware scheduling algorithms in a dynamic setting with random finite-size data transfers. We show that in certain cases the flow-level performance may be evaluated by means of a multi-class Processor-Sharing model where the total service rate varies with the total number of users. In addition, we present simple necessary conditions for flow-level stability in the presence of channel variations, and establish that these are also sufficient for a broad class of utility-based scheduling strategies and arbitrary rate statistics. Time permitting, we conclude with a discussion of capacity issues and flow-level performance in wireless networks with multiple interacting base stations.

Robert Buche (North Carolina State University)

Heavy traffic models and control of wireless systems

Heavy traffic methods are useful for wireline queueing analysis and show promise for wireless systems. The main difference compared to the wireline setting is the randomly-varying environment in which wireless systems operate. In the heavy traffic analysis, typically a Brownian driven stochastic differential equation with reflection (SDER) models the queueing dynamics. We will discuss these models and the associated stochastic control problem along with some numerical simulation results. Recently, the importance of modeling long range dependence in wireless systems has been shown. We will give some initial comments on extending the analysis to this case where the SDER is driven by a more general Levy process.

Dov Chelst (DeVry University)

A Charged Van der Waals Equation of State and Order-Decreasing Lattice-Path Mappings

One can successfully modify a standard derivation of a van der Waals equation of state (see Lebowitz and Penrose, Journal of Math. Phys. 1966) to accomodate a system of charged particles. Along the way, significant modifications to the original arguments must be made to accomodate the long-range nature of the Coulomb potential. Particularly, in a one-dimension two-component plasma, a purely combinatorial result regarding lattice path mappings proves useful. I will define the term "order-decreasing mapping", to explain the nature of the combinatorial result and its connection to the original statistical mechanical problem. In addition, I will discuss attempts at generalizing the mathematical result in order to accomodate a wider class of physical systems.

Rong-Rong Chen (University of Utah)

Capacity-approaching LDPC Codes Based on Markov Chain Monte Carlo MIMO Detection

We study joint code design and MIMO (multiple-input multiple-output) detection based on Markov Chain Monte Carlo (MCMC) approach. The MCMC detector is highly effective for large antenna systems because it has a much lower complexity than traditional MIMO detectors including the sphere decoding detector. We apply the extrinsic information transfer (EXIT) technique to find optimal irregular LDPC codes that are matched to the characteristics of the MCMC detector. For a large system of 8 transmit and 8 receive antennas and 16 QAM modulation, the optimized LDPC code achieves within 1.4 dB of the channel capacity. This result improves best published results by 2.3 dB, where 1.3 dB is due to the MCMC detection and 1 dB is due to code optimization.

Rong-Rong Chen (University of Utah)

Capacity-approaching LDPC Codes Based on Markov Chain Monte Carlo MIMO Detection

We study joint code design and MIMO (multiple-input multiple-output) detection based on Markov Chain Monte Carlo (MCMC) approach. The MCMC detector is highly effective for large antenna systems because it has a much lower complexity than traditional MIMO detectors including the sphere decoding detector. We apply the extrinsic information transfer (EXIT) technique to find optimal irregular LDPC codes that are matched to the characteristics of the MCMC detector. For a large system of 8 transmit and 8 receive antennas and 16 QAM modulation, the optimized LDPC code achieves within 1.4 dB of the channel capacity. This result improves best published results by 2.3 dB, where 1.3 dB is due to the MCMC detection and 1 dB is due to code optimization.

Kenneth L. Clarkson (Bell Laboratories)

Optimizing Wireless Networks with Ocelot

Ocelot is a Lucent tool for modeling the performance of cellular networks, and optimizing that predicted performance with respect to antenna parameters, such as azimuth, pilot fraction, and tilt. For Ocelot to be useful, its numerical model must satisfy some stringent requirements: simple enough to compute quickly, smooth enough to optimize effectively, and accurate enough to given meaningful results. As well as an overview of Ocelot, this talk will describe one or two specific aspects of its modeling; for example, Ocelot estimates the effect of dynamic shadow fading on active-set membership using a simple steady-state approximation, where more typically such effects would be modeled by simulation. The applicability of this approximation has been confirmed by computational studies.

Martin Eiger (Telcordia)

Wireless Local Area Network Simulation

We describe a software system that simulates wireless local area networks supporting heterogeneous services and multiple protocols. We present applications of this system in three areas: analysis of voice capacity, maximization of data throughput while protecting voice quality of service, and the design and evaluation of scheduling algorithms in a polling-based system.

Philip Fleming (Motorola, Inc.)

System analysis of wireless packet networks carrying voice over IP

Joint work with Amitava Ghosh and Ivan Vukovic.

This tutorial will cover the system architecture, protocol design and performance characteristics of voice and other quasi-real-time applications such as push-to-talk over wireless packet networks. We address features of the bearer path such as voice coding and IP header compression as well as control plane characteristics such as call set-up and hand-off latency. We will give an overview of the next generation wireless wide area network technologies, HRPD (EV-DO), HSUPA/HSDPA and 802.16e and present analysis and simulation of system behavior for each under moderate and heavy loading conditions using both real- and non-real-time traffic and mixtures. Packet scheduling and media access control will also be discussed in some detail. Toward the end of the tutorial we will discuss open research areas.

Georgios Giannakis (University of Minnesota)

Distributed canonical correlation and distortion-rate analyses for centralized compression-estimation using wireless sensor networks

Wireless sensor networks deployed to perform surveillance and monitoring tasks have to operate under stringent energy and bandwidth limitations. These motivate well distributed compression and estimation scenarios based on reduced dimensionality sensor observations which may have to be severely quantized before transmission to a fusion center. We will show how distributed correlation analysis can be used to compress observations and explore the fundamental performance limits dictated by distortion-rate analysis in this decentralized estimation setup. We will further present interesting tradeoffs that emerge even in distributed mean-location estimation based on severely quantized observations along with their fundamental error-variance limits. Estimators utilizing either independent or colored binary data will be developed and analyzed. Corroborating simulations will provide comparisons with the clairvoyant estimators based on unquantized sensor observations, and include a motivating application with a sensor net employed for habitat monitoring. In the poster session we will also discuss dynamical systems and present (extended) Kalman Filtering ideas based on single-bit observations.
Brief Bio: G. B. Giannakis received his B.Sc. in 1981 from the Ntl. Tech. Univ. of Athens, Greece and his M.Sc. and Ph.D. in Electrical Engineering in 1983 and 1986 from the Univ. of Southern California. Since 1999 he has been a professor with the Department of Electrical and Computer Engineering at the University of Minnesota, where he now holds an Endowed ADC Chair in Wireless Telecommunications. His general interests span the areas of communications and signal processing, estimation and detection theory -- subjects on which he has published more than 200 journal papers, 350 conference papers, and two edited books. Current research focuses on complex-field and space-time coding, multicarrier, ultra-wide band wireless communication systems, cross-layer designs and wireless sensor networks. He is the (co-) recipient of six best paper awards from the IEEE Signal Processing (SP) and Communications Societies (1992, 1998, 2000, 2001, 2003, 2004) and also received the SP Society's Technical Achievement Award in 2000. He is an IEEE Fellow since 1997 and has served the IEEE in various editorial and organizational posts.

Georgios Giannakis (University of Minnesota)

Achieving Wireline Random Access Throughput in Wireless Networking via User Cooperation

Well appreciated at the physical layer, user cooperation is introduced here as a diversity enabler for wireless random access (RA) at the medium access control sub-layer. This is accomplished through a two-phase protocol in which active users start with a low power transmission attempting to reach nearby users, and follow up with a high power transmission in cooperation with the users recruited in the first phase. We show that such a cooperative protocol yields a significant increase in throughput. Specifically, we prove that for networks with a large number of users, the throughput of a cooperative wireless RA network operating over Rayleigh fading links approaches the throughput of a RA network operating over additive white Gaussian noise (AWGN) links. As a result, user cooperation migrates diversity benefits to the wireless RA regime, thus bridging the gap to wireline RA networks, without incurring a bandwidth or energy penalty.

Martin Greiner (Siemens)

Selforganizing control of network structure in wireless communication

Wireless multihop ad hoc communication networks represent an infrastructure-less peer-to-peer generalization of todays cellular networks. Since a central control authority is missing, the complex network has to selforganize itself for various operating tasks. Key is the design of simple, yet robust distributive control rules, which allow the overall network to perform well. Two examples from topology control are given. The first one addresses the connectivity issue, where a selforganizing rule is presented and shown to lead to strong network connectivity almost surely. A generic packet-traffic analysis is used in the second example to first develop a phenomenological description of the end-to-end throughput capacity for fixed network structures and then to sketch further steps towards a selforganizing rule for obtaining throughput-optimized network structures.

Katherine Guo (Bell Laboratories)

Bandwidth Guaranteed Provisioning in Network-Based Mobile VPNs

Provision of VPN services to mobile customers is a revenue generating opportunity for Network Service Providers (NSPs). To provide network-based Mobile-VPN services, the NSPs terminate the VPN sessions from remote mobile users within the NSP network and aggregate VPN traffic destined to the same enterprise intranet onto one or a few VPN sessions from within the network to the enterprise VPN gateway. In between, value-added services are provided for this customer traffic.

We propose the use of a hierarchical network architecture to efficiently realize network-based Mobile VPNs. The hierarchical architecture consists of three main components: a) the Mobile Access Point (MAP), b) the IP Services Gateway (IPSG), and c) the enterprise VPN gateway or the Customer Premise Equipment (CPE). We address the problem of provisioning customers on the IP Service Gateways (IPSGs) in a bandwidth constrained network such that the profit realized by the NSP by delivering Mobile-VPN services is maximized. The parameters considered in the optimization problem include the cost of provisioning customers on the IPSGs, the bandwidth capacity of links on the network, the bandwidth cost and the revenue that a NSP realizes from a customer.

We derive an integer programming formulation for the problem and provide solutions for a few practical cases. The results provide insights into the design of Mobile-VPN service architectures and illustrates the different trade-offs that are involved.

John Hobby (Bell Laboratories)

Optimizing Performance Metrics for Cellular Networks

We have developed an interactive tool for modeling and optimizing various types of cellular networks including CDMA, GSM, UMTS, EV-DO. Modeling network coverage and capacity as smooth, differentiable functions of parameters such as antenna tilts and azimuths facilitates efficient optimization even for large networks.

The model involves explicit probability computations for effects such as shadow fading, and it includes steady-state approximations to dynamic processes such as the effect of the add/drop timer. Reverse-link power control and power amplifier sharing lead to highly-coupled systems that are nontrivial to solve and make the analytical derivative functions especially challenging.

Michael L. Honig (Northwestern University)

Large System Analysis of Multi-Input/Multi-Output Channels

Performance analysis of wireless communication systems is often facilitated through the use of asymptotic methods. Recent examples include large system analysis of Code-Division Multiple Access (CDMA) with random signatures, and multiple antenna systems with random channels. A key feature of this analysis is application of results on eigenvalue distributions and moments of large random matrices. Those results enable the efficient computation of large system performance measures, such as spectral efficiency and probability of error, which are far more difficult to compute for finite-size systems. The large system results typically give an accurate prediction of the performance of finite-size systems, and offer important insights into system behavior. We will present some recent applications of large system analysis to variants of CDMA and Multi-Input/Multi-Output channels with and without feedback for signature optimization, and to least squares filtering for interference suppression.

Yasong Jin (University of Kansas)

Temporal Properties of Congestion Events in Networks with Fractional Brownian Traffic

In packet networks congestion events tend to persist, producing large delays and long bursts of consecutive packet loss resulting in perceived performance degradations. The length and rate of these events have a significant effect on network quality of service (QoS). The packet delay resulting from these congestion events also influences QoS. A technique for predicting these properties of congestion events, such as, the inter-congestion events time and the congestion duration, is developed in the presence of fractional Brownian Motion (fBM) traffic.

Nihar Jindal (University of Minnesota)

High SNR analysis of MIMO broadcast channels

The behavior of the multiple antenna broadcast channel at high SNR is investigated. The sum rate capacity (achievable by dirty paper coding), the sum rate achievable using transmitter beamforming, and an upper bound to the sum rate capacity are studied. Though these three terms are equivalent in the sense of the multiplexing gain, i.e. in terms of first order growth, there is an absolute difference between the corresponding rates. These difference terms are calculated and simple and intuitive geometrical interpretations are given.

Thierry Klein (Lucent Technologies)

End-to-end performance in 3G wireless data networks

We provide an overview of wireless packet data networks and emphasize the importance of end-to-end performance metrics to support user-perceived quality of service guarantees. The following topics are addressed in the tutorial to illustrate various performance-enhancing control mechanisms in wireless packet data networks:
1. Overview of wireless data networks
2. Overview of end-to-end performance issues
3. Opportunistic scheduling algorithms
4. Interactions between scheduling algorithms and TCP
5. TCP-level performance optimizations
6. Quality of service based admission control

Thierry Klein (Lucent Technologies)

Dynamic optimization of future wireless networks

In this tutorial, we discuss the role of network performance optimization, which is required when deploying real-world wireless networks to adjust to complex channel propagation effects, network layout irregularities and inhomogeneous traffic distributions. Traditional and automated optimization procedures are presented, along with a cellular optimization tool to enhance the coverage and the capacity of CDMA networks. The emerging trends in wireless data networks naturally lead to dynamic network optimizations. These trends are highlighted along with some of the critical components and a list of sample optimization problems. The problem of autonomous base station deployment and configuration is presented in more detail.

Thierry Klein (Lucent Technologies)

A distributed architecture for future wireless IP networks

In this tutorial, a possible evolution path for future wireless networks is discussed. In particular, a distributed radio network architecture is presented in which the network controller functionalities are integrated with the base station. We first motivate the migration towards a distributed architecture and present the salient features and the main difficulties in realizing this evolution path. Distributed mobility and radio resource management techniques are then proposed, along with a framework for dimensioning the backhaul network to support the required quality of service performances.

Gerhard Kramer (Lucent Technologies)

Some Information theory and codes for half-duplex relays

A relay channel has a source terminal transmitting a message to a destination terminal with the help of one or more relays. We review a selection of the existing information theory for such channels, with emphasis on half-duplex models. We further consider aspects of code and receiver design, including phase and symbol synchronization.

Vikram Krishnamurthy (University of British Columbia)

Structural results in cross layer optimization of wireless networks

In the first part of the talk, we consider the interaction between the physical and link layers for single user systems. By using a Lagriangian approach to constrained Markov decision processes and stochastic dominance results, we examine the structural effects of buffer size, fading channel dynamics and traffic dynamics on system throughput. Also a channel aware ARQ protocol is proposed that uses a partially observed Markov deicision process to optimize the tradeoff between latency and throughput.

In the second part of the talk, we consider cross layer admission control and vertical handoff between WLAN and CDMA networks for multiuser systems. We present gradient learning based stochastic approximation algorithms to optimize the resulting constrained Markov decision process.

Komandur R. Krishnan (Telcordia) , Arnie Neidhardt (Telcordia)

Power Requirements in CDMA Networks with Multiple Classes of Traffic

We propose methods for calculating downlink power-requirements in a CDMA network that supports multiple classes of traffic. In providing for fluctuations of transmitter-power requirements in response to traffic-rate fluctuations, we make use of the notion of an "effective power" of a transmitter, analogous to the notion of an "effective bandwidth" of a traffic source. The methods consist of "perturbation analysis" by means of an expansion about approximate average values of transmitter-powers.

P. R. Kumar (University of Illinois - Urbana-Champaign)

Capacity, architecture, and protocols for ad hoc wireless networks

Topics

This tutorial is motivated by two considerations.

(i) There has been some progress in recent years in developing a quantitative framework for wireless networks.

(ii) The research community is entering a phase of designing several second generation protocols for wireless networks which aim to not only improve performance, but also to address unmet needs.

Our goal in this tutorial is twofold:

(i) We will provide a clear presentation of the key ideas underlying this emerging theory of wireless networks. The goal is to make the theory accessible to all researchers in the area, to understand the questions addressed, the questions unaddressed, the methods used, and address its shortcomings, as well as its results, i.e., basically to understand it.

(ii) We will provide some candidate second generation protocol designs. In particular we will stress the importance of paying attention to the architecture of the implementation. We will also address some issues related to the emerging topic of cross-layer design. We will also stress the importance of implementing designs.

Harold J. Kushner (Brown University)

Control of multi-node mobile Communications networks with time varying channels via stability methods

Consider a communications network consisting of mobiles, each of which can be scheduled to serve as a receiver and/or transmitter. Data from many external sources arrives at the various mobiles in some random way. Each mobile can serve as a node in the possibly multihop path from source to destination.

At each mobile the data is queued according to the source-destination pair until transmitted. Time is divided into small scheduling intervals. The connecting channels are randomly varying due to the motion of the mobiles and consequent scattering. At the beginning of the intervals, the channels are estimated via pilot signals and this information is used for scheduling.

The issues are the allocation of transmission power and/or time and bandwidth to the various queues at the various mobiles in a queue and channel-state dependent way to assure stability and good operation. Lost packets might or might not have to be retransmitted. The decisions are made at the beginning of the scheduling intervals. In a recent work, stochastic stability methods were used to develop scheduling policies for the simple system where there is a single transmitter communicating with many mobiles. The resulting controls were readily implementable and allowed a range of tradeoffs between current rates and queue lengths, under very weak conditions. Here the basic methods and results are extended to the network case. The choice of Liapunov function allows a choice of the effective performance criteria. All essential factors are incorporated into a "mean rate" function, so that the results cover many different systems.

Because of the non-Markovian nature of the problem, we use the perturbed Stochastic Liapunov function method, which is designed for such problems.

Chulhan Lee (University of Texas - Austin)

Cooperation vs. compression for sensor networks

In a sensor network, nodes share information about their observations, and the amount of shared information can often be substantial. This paper compares two different strategies that exploit this redundant information - compression and cooperation. It finds compression to be the winning strategy when energy savings is the most important objective, but finds cooperation to be the throughput maximizing strategy. A weighted optimization problem is formulated to obtain intermediate schemes that allow a critical level of cooperation in the system, thereafter compressing all other redundant information.

Steven Low (California Institute of Technology)

An optimization model of protocol stack and hetergeneous protocols

Can we integrate the various protocol layers into a single coherent theory by regarding them as carrying out an asynchronous distributed primal-dual computation over the network to implicitly solve a global optimization problem? Different layers iterate on different subsets of the decision variables using local information to achieve individual optimalities, but taken together, these local algorithms attempt to achieve a global objective. Such a theory will expose the interconnection between protocol layers and can be used to study rigorously the performance tradeoff in protocol layering as different ways to distribute a centralized computation. We describe some preliminary work on cross layer interactions involving HTTP, TCP, IP, MAC, and scheduling. All of these instances can be integrated within a utility maximization model. We present equilibrium and stability properties of networks shared by TCP sources that react to different pricing signals where the current utlity maximization model breaks down.

Sean P. Meyn (University of Illinois - Urbana-Champaign)

Characterization and computation of optimal distributions for channel coding

This presentation concerns the structure of optimal codes for stochastic channel models. An investigation of an associated dual convex program reveals that the optimal distribution in channel coding is typically discrete. Based on this observation we construct a new class of algorithms is introduced, based on the cutting-plane method, to generate discrete distributions that are optimal within a prescribed class. This lecture builds upon a tutorial lecture to be presented by Meyn prior to the workshop at IMA.

Sean P. Meyn (University of Illinois - Urbana-Champaign)

Entropy, inference, and channel capacity

The goal of these three lectures is two-fold:

1. We will explore issues surrounding the capacity of non-coherent, memoryless communication channels. It is now known that the capacity-achieving input distribution is typically discrete, with a finite number of mass points. Even for the additive white-noise Gaussian channel, a distribution of this form is very nearly optimal for SNR of unity or below.

2. These concepts generalize to worst-case channel models, and to worst-case hypothesis testing. To see why, we will explore applications and theory of mutual information and relative entropy. In each of the applications considered, a discrete distribution is the optimizer of a linear program over the space of probability measures, or a convex program that admits a linear approximation.

These findings lead to many new applicable techniques, including improved methods for signal constellation design, new methods for computation of optimal input distributions, and a simple and effective approach to robust hypothesis testing.

Eytan Modiano (Massachusetts Institute of Technology)

Cross-layer control in wireless networks with QoS constraints

In this talk we will describe algorithms for resource allocation in wireless networks that attempt to optimize network performance across multiple layers of the protocol stack. In the first part of the talk we will consider the joint problem of flow control, routing, and scheduling in a wireless network subject to Quality of Service requirements. In particular, we will describe a dynamic control strategy that maximizes the sum utility in the network; and can be used to achieve a wide range of fairness objectives. In the second part, we consider a wireless transmitter whose data rate can be controlled by varying the transmission power. For such a system we will describe optimal transmission policies that satisfy delay constraints and also minimize the total transmission energy expenditure.

Vincent Poor (Princeton University)

Energy efficiency in multiple-access wireless networks: Nash equilibria in power control games

The energy efficiency (measured in bits-per-Joule) of multiple-access wireless data networks is considered via the behavior of Nash equilibria in non-cooperative power control games. Particular issues considered include the effects of multiuser detection and multiple antennas on energy efficiency, energy efficient carrier loading in multi-carrier CDMA systems, and the effects of delay constraints on energy efficiency. Some open problems of interest are also discussed.

Alexandre Proutiere (France Telecom)

Random multi-access protocols - A mean field analysis

Joint work with Charles Bordenave (ENS, Paris) and David McDonald (University of Ottawa, Canada).

Although random multi-access protocols, such as the Decentralized Coordination Function (DCF) in IEEE 802.11-based networks, are widely used, their performance remains largely unknown. This is due to the fact that the inherent interactions between competing sources have proven to be extremely complex to model and analyze. A very popular approach to circumvent this difficulty consists in decoupling the source behaviors; i.e. assuming that the evolutions of the back-off processes of the different sources are mutually independent. This assumption allows one to derive explicit estimates of the performance. This approach was applied by Bianchi (IEEE trans. on Wireless Comm. 2000) to analyze the DCF protocol and since then has been widely used to accurately predict the performance of similar protocols. In this work, using mean field techniques, we prove that, for a wide range of random multi-access protocols, the decoupling assumption is asymptotically exact as the number of competing sources grows. In the specific case of the DCF, the mean field analysis provides the transient and the stationary distributions of the backoff processes.

Christian Scheideler (Johns Hopkins University)

Overlay networks for wireless ad hoc networks

In this talk I will give an overview of various techniques to organize Wireless nodes in an overlay network with near-optimal communication Paths between any pair of nodes. Many of these overlay network constructions are based on the theory of graph spanners. Spanners first appeared in computational geometry, were then discovered as an interesting tool for approximating NP-hard problems, and have recently also attracted a lot of attention in the context of routing and topology control in wireless ad hoc networks.

After introducing the concept of graph spanners and giving several Examples relevant for wireless ad hoc networks, I will discuss various distributed, self-stabilizing protocols for maintaining a spanner among the wireless nodes, using a very simple wireless communication model just to provide a proof of concept. Afterwards, I will also discuss a much more realistic wireless communication model that has just recently been published, and I will demonstrate how to design a self-stabilizing overlay network protocol within that model.

Alain B. Tchagang (University of Minnesota)

Particle Filtering in Wireless Communications

With the increase use of wireless communication systems, the demand for fast and reliable filtering algorithm capable of coping with difficult transmission conditions is becoming more and more prevalent. Physical limitations and impairments of wireless channels, including multi-access and co-channel interference, time-variation and frequency selectivity, present a major technical challenge to the reliable transmission over a wireless link. The task can be greatly facilitated by the use of an efficient signal processing technique. In this poster, we present an overview and the application of particle filtering to the problems associated with transmission in wireless communications.

Xiaodong Wang (Columbia University)

Optimization of IEEE 802.11 DCF based on Bayesian estimation of the number of competing terminals

The performance of the Distributed Coordination Function (DCF) of the IEEE 802.11 protocol has been shown to heavily depend on the number of terminals accessing the distributed medium. The DCF uses a carrier sense multiple access scheme with collision avoidance (CSMA/CA) where the backoff parameters are fixed and determined by the standard. While those parameters were chosen to provide a good protocol performance under light loads, they fail to provide an optimum utilization of the channel in many scenarios. In particular, under heavy load scenarios, the utilization of the medium can drop tenfold. Most of the optimization mechanisms proposed in the literature are based on adapting the DCF backoff parameters to the estimate of the number of competing terminals in the network. However, existing estimation algorithms are either inaccurate or too complex. In this paper we propose an enhanced version of the IEEE 802.11 DCF that employs an adaptive estimator of the number of competing terminals based on sequential Monte Carlo methods. The algorithm uses a Bayesian approach, optimizing the backoff parameters of the DCF based on the predictive distribution of the number of competing terminals. We show that our algorithm is simple yet highly accurate even at small time scales. We implement our proposed new DCF in the ns-2 simulator and show that it outperforms existing methods. We also show that its accuracy can be used to improve the results of the protocol even when the nodes are not in saturation mode. Moreover, we show that there exists a Nash equilibrium strategy that prevents rogue nodes from changing their parameters for their own benefits, making the algorithm applicable in a complete distributed fashion without having to modify the standard or the existing base stations.

Wing Shing Wong (Chinese University of Hong Kong)

Mathematical problems in ad hoc wireless networks

In this talk, we discuss selected problems arising from ad hoc wireless networks, problems such as the fairness in routing and distributed state estimation. We show how these problems lead naturally to concepts such as generalized Perron-Frobenius eigenvectors, von Neumann equilibrium, and low data rate distributed controller, as well as to Baynesian decision function and stochastic approximation.

Dapeng Wu (University of Florida)

Effective capacity approach to providing statistical quality-of-service guarantees in wireless networks

The next-generation wireless networks are targeted at supporting various applications such as voice, data, and multimedia with diverse quality of service (QoS) requirements. To provide explicit QoS guarantees such as a data rate, delay bound, and delay-bound violation probability triplet, it is necessary to analyze a QoS provisioning system in terms of these QoS measures. This task requires characterization of the service (channel modeling), and queueing analysis of the system. However, the existing channel models such as finite-state Markov chain models, do not explicitly characterize a wireless channel in terms of these QoS measures. This leads to high complexity in characterizing the relation between the control parameters of QoS provisioning and the calculated QoS measures.

Recognizing that the above difficulty is the lack of a channel model that can easily relate the control parameters of a QoS provisioning system to the QoS measures, we propose and develop a link-layer channel model termed the effective capacity (EC) model. The EC model captures the effect of channel fading on the queueing behavior of the link, using a computationally simple yet accurate model, and thus, is a critical tool for designing efficient QoS provisioning mechanisms. Such an approach to channel modeling and QoS provisioning, is called effective capacity approach. In this poster, I will present our effective capacity approach to channel modeling.

George Yin (Wayne State University) , Qing Zhang (University of Georgia)

Reduction of Complexity for Systems Involving A Discrete-time Markov Chain: Time-scale Separation

Many problems in wireless communications involve a discrete-time Markov chain. Often, the state space of the Markov chain is inevitably large. To reduce the computation complexity becomes a practical concern. This poster presents a brief summary on recent developments for such systems. To achieve the goal of complexity reduction, time-scale separation and singular perturbation techniques are used in the modeling and analysis. Asymptotic expansions of probability vectors and structural properties of the Markov chain are provided together with near optimality in related control problem and Markov decision processes.

Yingqun Yu (University of Minnesota)

High-Throughput Random Access Via PHY-Layer Opportunism and Interference Cancellation

We consider two cross-layer design examples of high-throughput random access schemes via PHY-layer opportunism and interference cancellation. The first example is the so-called channel-aware slotted Aloha, which can exploit fading by effecting decentralized multi-user diversity. For continuous channels with analog amplitude, we prove the optimality of binary scheduling in terms of sum-throughput for homogeneous systems and in terms of sum-log-throughput for heterogeneous systems. For finite state Markov chain (FSMC) channels, we provide a convex formulation of the corresponding throughput optimization problem, and derive a simple binary-like access strategy.

The second example is SICTA, a contention tree algorithm with successive interference cancellation (SIC). The conventional random access algorithms, including tree algorithms (TAs), have relatively low throughput, since collided packets are typically discarded when packet collisions happen. We develop a novel protocol exploiting successive interference cancellation in a tree algorithm, where collided packets are reserved for reuse. We show that SICTA with binary splitting and gated access can achieve a throughput of 0.693, which represents about 40% increase in throughput over the renowned 0.487 first-come-first-serve (FCFS) tree algorithm.

Eric van den Berg (Telcordia)

Reducing energy consumption for power-constrained mobiles

We present a new method to increase the lifetime of energy constrained mobile devices. Each mobile node powers off its radio interface during time periods where it does nog expect to originate, receive or relay traffic. Nodes make autonomous decisions on whether and when to power down and wake up, without signaling messages to/from other nodes. We present results to show that the proposed method can significantly increase the lifetime of energy constrained nodes.