6717587
Capacity of memoryless channels and block-fading channels with designable cardinality-constrained channel state feedback
A coding theorem is proved for memoryless channels when the channel state feedback of finite cardinality can be designed. Channel state information is estimated at the receiver and a function of the estimated channel state is causally fed back to the transmitter. The feedback link is assumed to be noiseless with a finite feedback alphabet, or equivalently, finite feedback rate. It is shown that the capacity can be achieved with a memoryless deterministic feedback and with a memoryless device which select transmitted symbols from a codeword of expanded alphabet according to current feedback. To characterize the capacity, we investigate the optimization of transmission and channel state feedback strategies. The optimization is performed for both channel capacity and error exponents. We show that the design of the optimal feedback scheme is identical to the design of scalar quantizer with modified distortion measures. We illustrate the optimization using Rayleigh block-fading channels. It is shown that the optimal transmission strategy has a general form of temporal water-filling in important cases. Furthermore, while feedback enhances the forward channel capacity more effectively in low-signal-to noise ratio (SNR) region compared with that of high-SNR region, the enhancement in error exponent is significant in both high- and low-SNR regions. This indicates that significant gain due to finite-rate channel state feedback is expected in practical systems in both SNR regions.
25530597
Optimal space-time scheduling for block fading channels with partial power feedbacks
The multi-user multiple-input-multiple-output (MIMO) space-time scheduling problem is the prime focus of the paper. Using multiple transmit (nT) and receive antennas (nR), it is well known that the link-level throughput will be increased linearly with respect to min[nT, nR] without increasing the bandwidth and power budget. However, optimizing the link-level performance of the MIMO system does not always imply achieving scheduling-level optimization. Therefore, the design optimization across the link layer and the scheduling layer is very important to fully exploit the temporal and spatial dimensions of the communication channel. In this paper, we address the design of the optimal space-time scheduler for the multi-user MIMO system based on an information theoretical approach. Since full knowledge of channel matrix at the transmitter requires a feedback channel capacity not scalable with respect to nT (number of transmit antennas at mobiles) and nR (number of receive antennas at base station), we will assume two partial feedback models.
29049246
Iterative detection for BLAST systems with an arbitrary number of receive antennas
Turbo-coded Vertical Bell Labs Layered Space-Time Architecture (V-BLAST) is a multiple-antenna system employing turbo codes and bit-interleaving to offer flexible rates and high-speed wireless data communications. The conventional detection techniques based on one-shot demodulation and decoding algorithms may suffer poor performance or simply fail when there are fewer receive antennas than transmit antennas or when the multiple-input-multiple-output (MIMO) channel exhibits strong spatial correlations. We propose employing an iterative demodulation and decoding algorithm that solves these problems and greatly extends the applicability of V-BLAST. Simulations demonstrate that iterative V-BLAST offers the best-known performance in a wide range of settings. Through complexity analysis, we show that (a) the incremental computing complexity is small, although additional memory is required, compared with the conventional one-shot maximum likelihood (ML) decoding method, and (b) an iterative algorithm employing generalized sphere decoding will be a low-complexity, memory-reduced, and high-performance solution. We also give extensions to the technique beyond simple V-BLAST. In addition, when feedback from the receiver to the transmitter is available, we illustrate how to adapt code rate, modulation, and the power distribution to take advantage of the channel knowledge. With a combination of the “best in class” receiver performance and the ability to decode V-BLAST transmissions with fewer receive antennas than transmit antennas, the techniques described here can be viewed as key “technology enablers” for BLAST/MIMO in next-generation systems.
5528420
Automatic time-bound analysis for a higher-order language
Analysis of program running time is important for several applications, including reactive systems, interactive environments, compiler optimizations and performance evaluation. Automatic and efficient prediction of accurate time bounds is particularly important, and being able to do so for high-level languages is particularly desirable. This paper presents a general approach for automatic and accurate time-bound analysis for a functional high-level language, that combines methods and techniques studied in theory, languages, and systems. The approach consists of transformations for building time-bound functions in the presence of partially known input structures, symbolic evaluation of the time-bound function based on input parameters, optimizations to make the analysis efficient as well as accurate, and measurements of primitive parameters, all at the source-language level. To handle higher-order functions, special transformations are needed to build lambda expressions for computing running times, to optimize the construction of the time lambda expressions, and to optimize the symbolic evaluation. It took us several tries to obtain the simple and concise transformations for handling lambda expressions. We describe analysis and transformation algorithms and explain how they work. We have implemented this approach and performed a large number of experiments analyzing Scheme programs. The measured worst-case times are closely bounded by the calculated bounds. We describe our prototype system, ALPA, as well as the analysis and measurement results.
29553031
S-Club: an overlay based efficient service discovery mechanism in CROWN grid
Information service plays a key role in grid system, handles resource discovery and management process. Employing existing information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based on existing GIS mesh network of CROWN is built, so that GISs are organized as service clubs. Each club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in RLDS as the information service in CROWN grid and the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves search performance and outperforms existing approaches
1463365
Approximating optimal spare capacity allocation by successive survivable routing
The design of survivable mesh based communication networks has received considerable attention in recent years. One task is to route backup paths and allocate spare capacity in the network to guarantee seamless communications services survivable to a set of failure scenarios. This is a complex multi-constraint optimization problem, called the spare capacity allocation (SCA) problem. This paper unravels the SCA problem structure using a matrix-based model, and develops a fast and efficient approximation algorithm, termed successive survivable routing (SSR). First, per-flow spare capacity sharing is captured by a spare provision matrix (SPM) method. The SPM matrix has a dimension the number of failure scenarios by the number of links. It is used by each demand to route the backup path and share spare capacity with other backup paths. Next, based on a special link metric calculated from SPM, SSR iteratively routes/updates backup paths in order to minimize the cost of total spare capacity. A backup path can be further updated as long as it is not carrying any traffic. Furthermore, the SPM method and SSR algorithm are generalized from protecting all single link failures to any arbitrary link failures such as those generated by Shared Risk Link Groups or all single node failures. Numerical results comparing several SCA algorithms show that SSR has the best trade-off between solution optimality and computation speed.
15370058
Evolutionary programming made faster
Evolutionary programming (EP) has been applied with success to many numerical and combinatorial optimization problems in recent years. EP has rather slow convergence rates, however, on some function optimization problems. In the paper, a "fast EP" (FEP) is proposed which uses a Cauchy instead of Gaussian mutation as the primary search operator. The relationship between FEP and classical EP (CEP) is similar to that between fast simulated annealing and the classical version. Both analytical and empirical studies have been carried out to evaluate the performance of FEP and CEP for different function optimization problems. The paper shows that FEP is very good at search in a large neighborhood while CEP is better at search in a small local neighborhood. For a suite of 23 benchmark problems, FEP performs much better than CEP for multimodal functions with many local minima while being comparable to CEP in performance for unimodal and multimodal functions with only a few local minima. The paper also shows the relationship between the search step size and the probability of finding a global optimum and thus explains why FEP performs better than CEP on some functions but not on others. In addition, the importance of the neighborhood size and its relationship to the probability of finding a near-optimum is investigated. Based on these analyses, an improved FEP (IFEP) is proposed and tested empirically. This technique mixes different search operators (mutations). The experimental results show that IFEP performs better than or as well as the better of FEP and CEP for most benchmark problems tested.
6591453
Opportunistic fair scheduling over multiple wireless channels
Emerging spread spectrum high-speed data networks utilize multiple channels via orthogonal codes or frequency-hopping patterns such that multiple users can transmit concurrently. In this paper, we develop a framework for opportunistic scheduling over multiple wireless channels. With a realistic channel model, any subset of users can be selected for data transmission at any time, albeit with different throughputs and system resource requirements. We first transform selection of the best users and rates from a complex general optimization problem into a decoupled and tractable formulation: a multiuser scheduling problem that maximizes total system throughput and a control-update problem that ensures long-term deterministic or probabilistic fairness constraints. We then design and evaluate practical schedulers that approximate these objectives.