Search

This paper deals with the management of multimode sensors such as multifunction radars. We consider the problems of multitarget radar scheduling formulated as multivariate partially observed Markov decision process (POMDPs). The aim is to compute the scheduling policy to determine which target to choose and how long to continue with this choice so as to minimize a cost function. We give sufficient conditions on the cost function, dynamics of the Markov chain target and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to the multivariate TP2 ordering. This implies that the optimal parameterized policy can be estimated efficiently. We then present stochastic approximation algorithms for estimating the best multilinear threshold policy.

Incremental-redundancy hybrid automatic repeat- request (IR-HARQ) schemes are proposed in several wireless standards for increased throughput-efficiency and greater reliability. We investigate transmit power and modulation order adaptation strategies for the IR-HARQ schemes over correlated Rayleigh fading channels using semi-Markov decision process-based model. In order to jointly analyze physical layer and link layer, transmitter model incorporates a finite-size buffer that receives randomly varying traffic from a higher layer application. It is assumed that channel variations can be modeled with a first-order Markov chain. We show that the optimal transmission power and rate adaptation laws under buffering delay and packet overflow constraints can be obtained using the framework of semi-Markov decision process. We discuss three different adaptation models for the IR-HARQ schemes and compare their performances with the non-adaptive scheme. It is shown that unique optimal policy exists for each case and it can be computed using linear programming approach. This optimal policy is then applied for realistic channel fading and incoming traffic samples to evaluate its performance for both hard-decision and soft-decision decoding. Simulation results in general point out that substantial power savings can be achieved using adaptation and also if the transmission-delay requirements are relaxed.

We present a general framework for the computation of the optimal scheduling policies for delay and overflow-constrained joint rate and power adaptations for type-I hybrid automatic-repeat-request systems. This framework can be applied to adaptive resource-allocation problems on correlated flat-fading or frequency-selective fading channels for bursty nonconstant packet arrivals. It is shown that the optimal-rate and powercontrol laws can be obtained by solving the formulated Markov decision process problems. We consider two cases for packet scheduling over wireless channels that are of significant practical importance. In the first case, we assume that the transmitter perfectly knows the channel-state information (CSI) at the beginning of the transmission. The transmitter is also provided with the decoding result for the previous transmission in terms of observation feedback at the end of the transmission. Second, we consider the scheduling problem when the transmitter does not know the CSI at the time of transmission, but it makes the transmission decision based on the history of previous transmissions and corresponding outcomes. In both cases, our objective is to minimize transmission power, and the optimal policies are computed under two different buffer-cost constraints, namely, the average buffer delay and the average packet overflow rate. The results of this paper are of importance for the development of modern wireless standards that support heterogeneous multimedia and Internet traffic with certain application-dependent-delay and packet-dropping requirements.

We consider the optimal sensor scheduling problem formulated as a partially observed Markov decision process (POMDP). Due to operational constraints, at each time instant, the scheduler can dynamically select one out of a finite number of sensors and record a noisy measurement of an underlying Markov chain. The aim is to compute the optimal measurement scheduling policy, so as to minimize a cost function comprising of estimation errors and measurement costs. The formulation results in a nonstandard POMDP that is nonlinear in the information state. We give sufficient conditions on the cost function, dynamics of the Markov chain and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to a monotone likelihood ratio (MLR) ordering. As a result, the computational complexity of implementing the optimal scheduling policy is inexpensive. We then present stochastic approximation algorithms for estimating the best linear MLR order threshold policy.

This paper addresses the optimal power and rate allocation control in multiple-input multiple-output (MIMO) wireless systems over Markovian fading channels. The problem is posed as an infinite horizon average-cost constrained Markov decision process (CMDP) with the goal of minimizing the average transmission power subject to delay constraints. By using a Lagrangian formulation of the CMDP, we use the concepts of stochastic dominance, submodularity, and multimodularity to prove that the optimal randomized policies are monotone. Three important structural results on the nature of the optimal randomized policies are derived. First, we show that the action space can be exponentially reduced by decomposing the rate allocation problem into bit-loading problem across individual antennas and the total rate allocation based on the current buffer occupancy and channel state. Second, we show that the optimal rate allocation policy is a randomized mixture of two pure policies that are monotonically increasing in the buffer occupancy. Finally, we show that the optimal power allocation is piecewise linear in the delay constraint. These three structural results can be exploited to devise efficient online reinforcement learning algorithms for optimal rate allocation.

We present transmission scheduling algorithms for maximizing the lifetime of a sensor network. In each data collection, only one group of sensors are scheduled to transmit their measurements directly to an access point (AP) through a fading channel, causing a reduction in battery energy levels of these sensors. We formulate the problem of dynamically choosing which group of sensors should communicate with the AP to maximize network lifetime as a stochastic shortest path Markov decision process. We consider three types of channel information structure: global channel state information (CSI), channel statistics, and local CSI. For optimal scheduling using global CSI (i.e., the scheduler has the information of all sensors' instantaneous channel realizations), we propose an algorithm that obtains the optimal stationary scheduling policy with computational complexity reduced from exponential to polynomial in network size when the network is dense. Due to the large implementation overhead in acquiring global CSI, we consider scheduling algorithms that use channel statistics (i.e., each sensor only knows its own channel distribution) or local CSI (i.e., each sensor knows its own instantaneous channel realization). The optimal scheduling using channel statistics is formulated as a shortest path multiarmed bandit problem, which has an indexable optimal policy. We derive a closed-form expression for the Gittins index. We further show that the Gittins index is simply the residual energy when the channel fading is identically (but not necessarily independently) distributed across sensors, i.e., the optimal scheduling policy in this case is to choose the sensor with the most residual energy. Finally, we study an asymptotically optimal scheduling protocol using local CSI. This protocol has a distributed implementation yet achieves a comparable performance as the optimal scheduling using global CSI

This paper presents novel Q-learning based stochastic control algorithms for rate and power control in V-BLAST transmission systems. The algorithms exploit the supermodularity and monotonic structure results derived in the companion paper. Rate and power control problem is posed as a stochastic optimization problem with the goal of minimizing the average transmission power under the constraint on the average delay that can be interpreted as the quality of service requirement of a given application. Standard Q-learning algorithm is modified to handle the constraints so that it can adaptively learn structured optimal policy for unknown channel/traffic statistics. We discuss the convergence of the proposed algorithms and explore their properties in simulations. To address the issue of unknown transmission costs in an unknown time-varying environment, we propose the variant of Q-learning algorithm in which power costs are estimated in online fashion, and we show that this algorithm converges to the optimal solution as long as the power cost estimates are asymptotically unbiased

We address the issue of optimal coding rate scheduling for adaptive type-I hybrid automatic repeat request wireless systems. In this scheme, the coding rate is varied depending on channel, buffer and incoming traffic conditions. In general, we consider the hidden Markov model for both time-varying flat fading channel and bursty correlated incoming traffic. It is shown that the appropriate framework for computing the optimal coding rate allocation policies is partially observable Markov decision process (POMDP). In this framework, the optimal coding rate allocation policy maximizes the reward function, which is a weighted sum of throughput and buffer occupancy with appropriate sign. Since polynomial amount of space is needed to calculate the optimal policy even for a simple POMDP problem, we investigate maximum-likelihood, voting and Q-MDP policy heuristic approaches for the purpose of efficient and real-time solution. Our results show that three heuristics perform close to completely observable system state case if the fading and/or traffic state mixing rate is slow. On the other hand, when the channel fading is fast, Q-MDP heuristic is the most throughput-efficient among considered heuristics. Also, its performance is close to the optimal coding rate allocation policy of fully observable system state case. We also explore the performances of the proposed heuristics in the bursty correlated traffic case and show that maximum-likelihood and voting heuristics consistently outperform the non-adaptive case

We address the issue of optimal packet scheduling over correlated fading channels which trades off between minimization of three goals: average transmission power, average delay and average packet dropping probability. We show that the problem forms a weakly communicating Markov decision process and formulate the problem as both unconstrained and constrained problem. Relative value iteration (RVI) algorithm is used to find optimal deterministic policy for unconstrained problem, while optimal randomized policy for constrained problem is obtained using linear programming (LP) technique. Whereas with RVI only a finite number of scheduling policies can be obtained over the feasible delay region, LP can produce policies for all feasible delays with a fixed dropping probability and is computationally faster than the RVI. We show the structure of optimal deterministic policy in terms of the channel and buffer state and form a simple log functional suboptimal scheduler that approximately follows the optimal structure. Performance results are given for both constant and bursty Poisson arrivals, and the proposed suboptimal scheduler is compared with the optimal and channel threshold scheduler. Our suboptimal scheduler performs close to the optimal scheduler for every feasible delay and is robust to different channel parameters, number of actions and incoming traffic distributions.

The problem of adopting space-time block coding (STBC) in the uplink of direct sequence code division multiple access (DS-CDMA) systems is addressed. A novel system architecture is proposed for space-time (ST)-coded uplink transmissions over multipath fading channels with multiple user interference (MUI)-free reception. This proposed system is a combination of single-carrier time-reversal zero-padding (SC-TR-ZP)-based STBC with chip-interleaved block-spread (CIBS)-CDMA. Simulation results show that a substantial performance improvement can be achieved by adopting ST coding compared to the original CIBS-CDMA scheme without ST coding. Optimal maximum likelihood sequence estimation (MLSE) may be computationally prohibitive for long channels and/or with high-level modulation. Hence, the performance of different decision feedback sequence estimation (DFSE) schemes is investigated for the proposed ST-coded uplink system. In the case of whitened DFSE (WDFSE), a linear prediction (LP)-based approach is adapted for designing a whitening prefilter. Furthermore, a new scheme, which is a combination of linear equalization (LE) and modified unwhitened DFSE (MUDFSE) is proposed. The proposed combined LE-MUDFSE (Comb. LE-MUDFSE) scheme is very attractive as error-floor behavior appearing in other unwhitened DFSE schemes is eliminated. The simulation results indicate that a substantial performance improvement over the minimum mean-square error (MMSE) equalizer can be achieved by using either Comb. LE-MUDFSE scheme or WDFSE scheme.

This letter considers a multiple-access fading channel with opportunistic transmission of the users, i.e., only the user with the highest received power is allowed to transmit at a certain time slot. The transmit power randomization, independent of the channel estimates, is used in order to increase the fading rate, decrease the latency, and shape the distribution of the received powers. We derive the optimal distribution of the received powers that maximizes the throughput of the system, and measure possible gains compared with the long-term average throughput of the opportunistic transmission in a Rayleigh fading channel. The issue of unequal fading distributions of different users is also addressed.

The usage of multichannel receivers that are followed by diversity combining can significantly improve the performance of wireless communications links. In this paper, we investigate in some detail three popular techniques for diversity combining, namely maximal ratio combining (MRC), equal gain combining, and selection combining. The main goal is to investigate under which circumstances it can be guaranteed that a certain technique does indeed decrease the probability of error of a multichannel receiver. The analyzed fading model is quite general with the only assumption that fading gains are scaled exchangeable random variables. The crucial mathematical tool used to produce the results of this paper is the powerful theory of stochastic majorization. Among other results, it was shown that the average bit-error probability of the MRC receiver with equally distributed average powers always decreases with the addition of a new diversity branch if the total power is fixed.

Spectral efficiency presents the ultimate limit on data rate per unit bandwidth of a certain communication system. For direct-sequence code-division multiple access systems, the spectral efficiency has been derived in case of synchronous reception for optimal and linear multiuser receivers, flat-fading and nonfading environments, as well as single and multicell cellular networks. The most pervasive model employed in all these analyses is the large system random signature model. For the decision feedback receivers, previous research handled only the nonfading case while the case of fading channels remained unknown. This paper analyzes the spectral efficiency of the popular conventional decision feedback receiver (CDFR) in flat- and frequency-selective fading channels with and without power ordering. Results show that in the case of power ordering before cancellation and very large system loads, the spectral efficiency of this receiver in fading channels can be even larger than in the case of channels with no fading. We also discuss and identify optimal power control laws for the CDFR with and without power ordering. The power control law which equalizes single-user capacities in the case of power ordering is also discussed.

The sum capacity of optimally allocated spreading sequences with and without power control is studied for synchronous code-division multiple-access channels subject to frequency flat fading. Continuing upon the recently derived characterization of sum capacity for asymmetric received powers with no power control at the transmitter, we present an asymptotic analysis of the sum capacity in the wideband limit of a large number of users and evaluate possible gains compared with the random spread sequences. Next, we discuss group orthogonal optimal sequence allocation and analyze its potential to decrease the complexity of the receiver while achieving the sum capacity of optimally allocated equal-energy sequences. For the power controlled case, we give a general characterization of sum capacity and identify the optimal power-control law and sequence allocation that achieves this capacity. These results are also analyzed in the asymptotic limit of a large number of users.

For original paper see A. A. Alsugair and R. S. Cheng, ibid., vol. 41, p. 1072-1082 (July, 1995). We show that the signature sequences set that maximizes the lower bound on symmetric capacity derived in the above paper also maximizes the sum capacity of the Gaussian synchronous code-division multiple-access (CDMA) channel. This is done by relying on the equivalence of the eigenvalues of energy-weighted correlation matrices. This result establishes the missing link between the above paper and the sum capacity maximization result by Viswanath et al. (1999).

We present the spectral efficiency analysis of the recently proposed feedback receiver for two sets of orthogonal sequences (TSOS) scheme which is capable of supporting higher number of users than the spreading gain of the DS/CDMA system. The added complexity is minimal compared to the conventional matched filter. We show that in the case of coded system, spectral efficiency of this scheme is close to that of a Gaussian multiple access channel if the incomplete group of orthogonal sequences is detected first. We also discuss the choice of orthogonal sequences that maximizes the spectral efficiency. This analysis is extended for the case of flat fading channels.

We consider opportunistic spectrum access (OSA) which allows secondary users to identify and exploit instantaneous spectrum opportunities resulting from the bursty traffic of primary users. Within the framework of partially observable Markov decision process (POMDP), we develop decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. The focus of this paper is the tradeoff between optimality and complexity of obtaining OSA protocols. We first analyze the computational complexity of designing OSA protocols within the POMDP framework and demonstrate that the complexity grows exponentially with the horizon length (i.e, the spectrum access time of secondary users). By exploiting the underlying structure of the problem, we aim to develop a quantitative characterization of the fundamental tradeoff between optimality and complexity so that a systematic way of balancing these two can be obtained. Specifically, by exploiting the mixing time of the underlying Markov process of spectrum occupancy, we develop a truncated MDP formulation of OSA and reduce the computational complexity from growing exponentially to linearly with the horizon length. More importantly, this truncated MDP formulation provides a systematical way of trading off performance with complexity by choosing an appropriate truncation parameter.

The problem of transmission scheduling over a correlated time-varying wireless channel is formulated as a Constrained Markov Decision Process. The model includes a transmission buffer and finite state Markov model for time-varying radio channel and incoming traffic. The resulting cross-layer optimization problem is formulated to minimize the transmission cost under the constraint on a buffer cost such as the transmission delay. Under the assumptions on submodularity and convexity of the cost function it is shown that the optimal randomized policy is monotonically increasing with the increase of the buffer state. Furthermore, the influence of the channel and traffic correlation matrices on the optimal transmission cost is investigated. It is shown that comparison between optimal transmission costs of two different channels can be performed by considering the stochastic dominance relation of their conditional probability distributions. As an example of this result, channels with smaller scattering and the same mean can achieve smaller average transmission cost for the same average buffer cost.

This paper addresses learning based adaptive resource allocation for wireless MIMO channels with Markovian fading. The problem is posed as constrained Markov decision process with the goal of minimizing the average transmission cost (such as the transmission power) with the constraint on the average holding cost (such as the transmitter delay). Standard Q-learning algorithm is employed to adaptively find the optimal policy for unknown channel/traffic statistics, its convergence properties discussed and shown that it can relatively quickly compute the optimal policy even for rather large state spaces. In order to further improve the convergence rate of the standard Q- learning, we establish several structural results on the optimal policies. We show that the optimal transmission policy is monotonic in the buffer occupancy. This permits us to utilize the supermodularity of the Q-factors and form a structured Q-learning algorithm that increases the convergence rate with respect to the standard Q-learning algorithm.

The problem of transmission adaptation over a correlated time-varying wireless channel is formulated as a Constrained Markov Decision Process. The model includes a transmission buffer and finite state Markov model for time-varying radio channel and incoming traffic. This crosslayer optimization problem is formulated as to minimize the transmission cost (e.g. power or bit-error-rate) under the constraint on a buffer cost such as the transmission delay. Under the assumptions on submodularity and convexity of the cost function it is shown that the optimal randomized policy is monotonically increasing with the increase of the buffer state.

This paper addresses the problem of dynamic control for power and rate allocation in V-BLAST wireless systems over Markovian fading channels. The problem is posed as a controlled Markov decision process problem with the goal of minimizing the average transmission power with the constraint on the average delay that can be interpreted as the Quality of Service (QoS) requirement of a given application. Several structural results on the nature of the optimal randomized policies and costs are derived. In particular, it is shown that number of actions to be considered can be reduced by dividing the rate allocation problem into bit-loading problem across individual antennas and the total rate allocation based on the current buffer and channel state. Further, optimal rate allocation policies are shown to be a mixture of two pure policies that are non-decreasing in the buffer state. These results can be utilized to devise an efficient online learning algorithm for optimal rate allocation policies1.

We investigate transmit power adaptation strategy for IR-HARQ scheme over correlated fading channels. In order to jointly analyze physical and link layers, the transmitter model incorporates a finite-size buffer that receives randomly varying traffic from a higher layer application. It is assumed that channel variations can be modeled with first order Markov chain. We show that the optimal power adaptation law under buffer delay and packet overflow constraints can be obtained using the framework of semi-Markov decision processes. The optimal policy is computed using the linear programming approach. Simulation results show that substantial power savings can be achieved if the transmission delay requirements are relaxed.

The usage of multichannel receivers that are followed by diversity combining can significantly improve the performance of wireless communications links. In this paper we investigate in some detail two popular techniques for diversity combining, namely maximal ratio combining (MRC) and equal gain combining (EGC). The main goal is to investigate under which circumstances it can be guaranteed that a certain technique does indeed decrease the probability of error of a multichannel receiver. The analyzed fading model is quite general with the only assumption that fading gains are scaled exchangeable random variables. The crucial mathematical tool used to produce the results of this paper is the powerful theory of stochastic majorization. Among other results, it was shown that the average bit error probability of the MRC receiver with equally distributed average powers always decreases with the addition of a new diversity branch if the total power is fixed.

We present a general Markov decision process based framework for the identification of optimal delay-constrained rate adaptation for MQAM systems and power adaptation for type-I hybrid ARQ systems. This framework can be applied to adaptive resource allocation over correlated fading channels. It is shown that the optimal rate and power control can be obtained by solving the appropriately formulated Markov decision processes using linear programming techniques. In the case of adaptive MQAM systems, the optimal rate allocation policy is dependent on the current buffer occupancy and the channel state. For hybrid ARQ systems the power control law can be formulated as being dependent on the current buffer occupancy and the history record of channel and action observations. The results of this paper are of importance for the development of modern wireless standards that support delay sensitive multimedia traffic.

In this paper, we consider the application of space- time (ST) block coding in the uplink of DS-CDMA systems. A novel system architecture, which is the combination of single- carrier time-reversal zero-padded (SC-TR-ZP) based ST block coding with chip-interleaved block-spread (CIBS)-CDMA, is proposed for frequency-selective uplink transmissions. Moreover, several decision feedback sequence estimation (DFSE) schemes are proposed for ST coded CIBS-CDMA systems. The simulation results demonstrate a significant improvement in the performance of the proposed system compared to CIBS-CDMA without ST coding. The simulation results also indicate that a substantial per- formance improvement can be achieved either using multistage modified unwhitened DFSE (MMUDFSE) or whitened DFSE (WDFSE) scheme over the linear MMSE equalizer. Furthermore, a low-complexity linear prediction (LP) based approach can be adapted to compute the whitening prefilter required in WDFSE to transform the system model into its minimum phase equivalent.

This paper explores optimal and suboptimal power and bit loading algorithms for a multicarrier system. Specifically, we study the trade-offs between the total transmit power of an orthogonal frequency division multiplexing (OFDM) system and the buffering delay of the packets in a transmission buffer. The loading framework is formulated as a Markov decision process (MDP) and an optimal loading policy which minimizes the transmit power while meeting a target delay constraint is obtained via equivalent linear programming (LP) methodology. The complexity of finding the optimal loading policy and its' implementation issues are described. Since finding the optimal policies becomes complex and practically un-realizable for large number of carriers in the system, we offer a sub-optimal power and bit loading algorithm using the results of the single carrier system's power and rate adaptation policy and a greedy approach. Selected numerical examples show that the sub-optimal algorithm, which has reduced complexity, has performance close to the optimal one

This paper explores optimal and suboptimal packet schedulers for time-varying flat fading channels that trade-off between minimization of the average delay and the average transmitted power. Both uncorrelated and correlated block fading channels are investigated. Extending a previous work, we formulate the trade-off as a unconstrained Markov decision processes and find the stationary deterministic optimal policy using both relative value iteration and policy iteration algorithm. As well, we present constrained Markov decision processes formulation of the problem and linear programming algorithm to solve it and show that optimal schedulers are randomized in this case. In order to alleviate the computational complexity needed, to determine the optimal scheduling policy we propose a suboptimal log-scheduling policy that has performance close to that of the optimal scheduler. The proposed policy is also robust to different channel models. It is demonstrated that log-policy is favorable to the water-filling policy for very slow fading channels.

The spectral efficiency presents the ultimate limit on the data rate per unit bandwidth of a certain communication system. For the DS-CDMA systems spectral efficiency has been derived for optimal and linear multiuser receivers in the case of synchronous reception, fading and non-fading environment as well as single and multi-cell cellular networks. The most pervasive model employed in all these analyses is the large system random signature model. For the decision feedback receivers the previous research handled only the non-fading case while the case of fading channels remained unknown. This paper analyses the spectral efficiency of the decision feedback receiver in a fading channel with and without power ordering. The results show that in the case of power ordering before cancellation the multiuser diversity effect previously encountered by S. Shamai (Shitz) and Verdu (see IEEE Trans. on Inform. Theory, vol.47, p.1302-27, May 2001) occurs. Multiuser diversity is the effect where the spectral efficiency of a certain multiple-access system improves in fading channels due to the multiplicity of users that share the system and provide the necessary power diversity. Also, analyzed in this paper is the case of imperfectly estimated channel gains in fading environments or the case of imperfect power control. The spectral efficiency loss incurred by this estimation error is analyzed in the case of the conventional decision feedback receiver.

Using a result from extreme value theory, we characterize the sum capacity of optimally allocated sequences in flat fading channels in a large system model, i.e., when both the number of users and the processing gain increase without bounds while their ratio remains fixed. Thus we are able to evaluate explicitly possible gains of using optimal sequences compared to random sequences. Since optimization of sequences requires perfect knowledge of channel state information at the transmitter, there is usually no need to constrain the problem of finding optimal sequences while not simultaneously allowing power control, as was done by P. Viswanath and V. Anantharam (see IEEE Trans. on Inform. Theory, vol.45, p.1984-92, 1999). Therefore, we address the problem of joint power control law/signature optimization, and show that it can be solved as a determinant optimization problem (see Witshenusen, H.S., SIAM J. Appl. Math,. p.515-22, 1975). The sum capacity of optimal signature sequences with power control is derived for the general case and then extended for the asymptotic large system model.

This paper analyzes two different low-complexity multiuser detection schemes for the oversaturated synchronous CDMA systems, ie, systems which can accommodate more users than the processing gain of the system. The first scheme is multistage iterative alternative detection of the users of the two groups combined with interference cancellation. The bit-error rate performance analysis of this scheme using Gaussian approximation is also derived and it is shown that this scheme is the realization of the space altering generalized expectation maximization algorithm known in signal processing literature. As an improvement for the shortcomings of the first scheme in near-far situations, a group orthogonal sequence allocation scheme is introduced. It is demonstrated that it can lead to efficient optimal multiuser detection. It is also shown that if all groups of sequences attain the Welch bound for the sum of squared sequence correlation coefficients then the optimal joint multiuser detection maximizes the sum capacity of the channel.