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