Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> An adaptive coding scheme for digital communication over time-varying channels is presented. The scheme is based on a finite-state Markov channel model. Emphasis is on the adaptation of the error protection to the actual channel state. The throughput gains that are achieved by the adaptive scheme relative to the conventional nonadaptive coding methods are demonstrated by several examples. Of special interest is the use of punctured convolutional codes with maximum-likelihood Viterbi algorithm to enable adaptive encoding and decoding without modifying the basic structure of the encoder and the decoder. > <s> BIB001 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> We consider the problem of buffer and channel adaptive transmission over fading channels. In the model, data packets arrive stochastically into a finite-length buffer which transmits them over a time-varying correlated fading channel. We assume that knowledge of the buffer occupancy and the fading state is available at the transmitter. The objective is to vary the transmission power and rate according to the buffer and channel conditions so that the long-term system throughput is maximized under some average transmission power constraint. Here, maximizing the system throughput is equivalent to minimizing packet loss due to both buffer overflow and transmission error. We formulate this optimization problem as a Markov decision process (MDP) and use dynamic programming techniques to obtain the solution. Next, we look at the effects of error and delay in the channel state information and propose an optimal adaptive policy that is obtained by formulating a partially observable Markov decision process (POMDP). Simulation results are given to show the performance of the policies over fading channels with perfect and imperfect channel state information. <s> BIB002 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> We investigate joint source-channel decoding for vector quantization over the finite-state Markov channel. In particular, we consider the decoding problem in which the channel state information is not available to the decoder. Based on hidden Markov modeling of the channel output, two decoding strategies are proposed. The first one is a soft-decoder which estimates the source reconstruction vectors directly from the observed channel output samples. The second one is a hard-decoder based on joint MAP estimation of channel symbols and channel states. Application of these decoders to wireless channels with multipath fading is also investigated. Simulation results are provided for a flat fading wireless channel and a Gauss-Markov source. <s> BIB003 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> We consider transmission control (rate and power) strategies for transferring a fixed-size file (finite number of bits) over fading channels under constraints on both transmit energy and transmission delay. The goal is to maximize the probability of successfully transferring the entire file over a time-varying wireless channel modeled as a finite-state Markov process. We study two implementations regarding the delay constraints: an average delay constraint and a strict delay constraint. We also investigate the performance degradation caused by the imperfect (delayed or erroneous) channel knowledge. The resulting optimal policies are shown to be a function of the channel-state information (CSI), the residual battery energy, and the number of residual information bits in the transmit buffer. It is observed that the probability of successful file transfer increases significantly when the CSI is exploited opportunistically. When the perfect instantaneous CSI is available at the transmitter, the faster channel variations increase the success probability under delay constraints. In addition, when considering the power expenditure in the pilot for channel estimation, the optimal policy shows that the transmitter should use the pilot only if there is sufficient energy left for packet transfer; otherwise, a channel-independent policy should be used. <s> BIB004 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> Conventional adaptive transmission schemes perform poorly in wireless correlated slow-fading channels. In this paper, a joint adaptive packet size and modulation (APSM) scheme combined with selective repeat automatic repeat request (SR-ARQ) is proposed. We apply a multi-state Markov system model for analyzing the performance of APSM/SR-ARQ systems and optimizing the selection of modulation levels and packet sizes in correlated fading channels, which is also described by a finite-state Markov chain. A general closed-form expression of the average throughput for APSM/SR-ARQ is presented. Numerical results show that our adaptive scheme combined with SR-ARQ can obtain a good performance in correlated fading channels. <s> BIB005 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> 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. <s> BIB006 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> 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. <s> BIB007 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> 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 <s> BIB008 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> We present a computationally efficient algorithm that minimizes the transmission energy and latency associated with transmitting a file across a Gilbert Elliott fading channel. We formulate the optimal tradeoff between transmission energy and latency as a partially observed Markov decision process problem (POMDP). The channel state is not directly observed and hence transmission decisions must be based on ACK/NAK information provided over a feedback channel. The key idea is to reformulate the resulting POMDP as a Markovian search problem, with optimal transmission control policies that are threshold in nature. Threshold policies are computationally inexpensive to implement. Our analysis shows that for different parameter values of the Gilbert Elliott fading channel, the optimal transmission policy, while threshold in structure, exhibits vastly different behaviour - from persistent retransmission to back-off and wait. Numerical examples demonstrate the performance improvements that can be obtained using the optimal threshold policies as compared to existing heuristic algorithms. <s> BIB009 </s> Finite-state Markov modeling of fading channels - a survey of principles and applications <s> APPLICATION FOUR: ADAPTIVE TRANSMISSION <s> In this paper, Rayleigh fading channel with an OFDMA system is modeled as a finite-state Markov channel (FSMC) by partitioning the received signal envelope into several intervals. With the aid of sub-band formation and property of lumpability, the size of feedback information can be reduced. This approach involves reducing an exponentially increased states of Markov channel to multiple lumpable Markov channels. The corresponding state transition probabilities and steady-state probabilities are used to predict channel states information in multiple symbol durations ahead. Some simulation examples are presented to illustrate the capability of the lumpable FSMC in channel prediction. <s> BIB010
Adaptive transmission is particularly important for efficient transmission of data packets in wireless networks. As the name suggests, in the adaptive scheme the transmitter adapts its coding strategy based on some side information about the quality of the fading channel (and possibly based on available traffic and data buffer resources). The objective is often to devise an efficient adaptive scheme that maximizes the rate of reliable data transmission or the probability of successful file transfer at a tolerable cost, such as transmission delay or power. The side information for adaptive transmission is often provided by the receiver via a feedback link. For example, side information can be the fading level, which is obtained at the receiver by doing extra processing/measurements such as channel estimation. Alternatively, the receiver can send back the success or failure in packet decoding, such as acknowledgments (ACK) or negative acknowledgments (NAK) in the automatic repeat request (ARQ) protocol. In loose terms, in poor channel conditions the transmitter should send data at lower rates by either changing the coding rate or by reducing the modulation dimensionality. In better fading channel conditions, the transmitter may transmit at higher rates. The treatment of the fading channel as an FSMC is attractive from a practical viewpoint. First, the receiver may need to estimate few states for the fading level and send them back to the transmitter. This can greatly reduce the bandwidth required for the feedback link. Second, only a finite number of transmission strategies need to be devised. This simplifies the implementation of the adaptive transmitter. The application of FSMC models for adaptive transmission in correlated fading channels can be traced back to the early work of BIB001 . More recently, the adaptive transmission problem has been cast into the Markov decision process (MDP) framework BIB006 - BIB007 .The MDP framework facilitates solving decision problems in which a scheduler (such as the transmitter) tries to maximize a reward (such as packet throughput), while minimizing some cost (such as transmission delay or power). An MDP has the following elements: a set of system states, a set of actions, and a set of rewards. In the context of adaptive transmission, system state can include the state of transmission buffer, the state of incoming traffic, and the state of fading channel. The required action is to choose a suitable coding rate or transmission power. The reward can be defined as a weighted sum of throughput, delay, and/or power (with appropriate signs used). The MDP setting is more suitable for the slow-fading regime, where the channel state can be accurately estimated at the receiver and be sent back to the transmitter infrequently. However, in faster fading conditions, channel estimation at the receiver becomes imperfect and noisy. In addition, imperfect states should ideally be sent back before the channel changes state, which requires a large feedback bandwidth. In situations where the state of the channel is not directly observable or hidden, a partially observable MDP (POMDP) setting is more suitable for this purpose BIB002 , BIB004 - BIB008 . Partial observations can be either noisy and delayed channel state feedback, or ACKs/NAKs in the ARQ protocol. However, it should be noted that the solution to POMDP is often computationally intractable and hence, practical and suboptimal solutions have been considered in BIB009 and BIB008 . Among other adaptive transmission studies, BIB005 studied adaptive packet size and modulation scheme in a variation of the ARQ protocol in fading channels modeled as FSMCs. The authors in BIB010 used FSMC models for channel prediction in orthogonal frequency division multiple access (OFDMA) systems. Finally, other applications of FSMC models include joint source and channel decoding for vector quantization over FSMC models and their applications to the TV-FFC BIB003 .