Stochastic Optimization Algorithms for Adaptive Modulation in Software Defined Radio by Anup Misra B.Eng., The University of Victoria, 2003 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Applied Science in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA October 2007 © Anup Misra 2007 Abstract Adaptive modulation has been actively researched as a means to increase spectral efficiency of wireless communications systems. In general, analytic closed form models have been derived for the performance of the communications system as a function of the control parameters. However, in systems where general error correction coding is employed, it may be difficult to derive closed form performance functions of the communications systems. In addition, in closed form optimization, real time adaptation is not possible. Systems designed with deterministic state optimization are developed offline for a certain set of parameters and hardwired into mobile devices. In this thesis we present stochastic learning algorithms for adaptive modulation design. The algorithms presented allow for adaptive modulation system design independent of error correction coding and modulation constellation requirements. In real time, the performance of the system is measured and stochastic approximation techniques are used to learn the optimal transmission parameters of the system. The technique is applied to Software Defined Radio (SDR) platforms, an emerging wireless technology which is currently being researched as a means of designing intelligent communications devices. The fundamental property that sets SDR apart from i ii traditional radios is that the communications parameters are controlled in software, allowing for real-time control of physical layer communications. Our treatment begins by modeling the time evolution of the adaptive modulation process as a general state space Markov chain. We show the existence and uniqueness of the invariant measure and model performance functions as expectations with respect to the invariant measure. We consider constrained and unconstrained throughput optimization. We show that the cost functions considered are convex. Next we present stochastic approximation algorithms that are used to estimate the gradient of the cost function given only noisy estimates. We conclude by presenting simulation results obtained by the presented method. The learning based method is able to achieve the maximum throughput as dictated by exhaustive Monte Carlo simulation of the communications system, which provide an upper bound on performance. In addition, the learning algorithm is able to optimize communications under various error correction schemes. The tracking abilities of the algorithm are also demonstrated. We see that the proposed method is able to track optimal throughput settings as constraints are changed in time. Table of Contents Abstract ^i Table of Contents ^ iii List of Figures ^ vi Acknowledgments ^ viii 1 2 Introduction ^ 1 1.1 Motivation ^ 3 1.2 Contributions of the Thesis 4 1.3 Organization ^ Adaptive Modulation 2.1 ^ ^ 5 6 Wireless Channel Fundamentals ^ 6 2.1.1^Multi-path fading ^ 8 2.1.2^Statistical Properties of Fading Channels ^ 9 2.2 Adaptive Modulation ^ 10 2.3 Software Defined Radio ^ 12 2.4 Cognitive Radio ^ 14 iii iv 3 4 Stochastic Optimization ^ 3.1 Convex Optimization ^ 15 3.2 Markovian Stochastic Processes ^ 19 3.2.1^Markov Chain Monte Carlo ^ 22 3.3 Optimization with Noisy Function Estimates ^ 23 3.4 Stochastic Approximation ^ 25 Current Research Work in Adaptive Modulation ^ 29 4.1 Theory of Adaptive Modulation ^ 29 4.1.1^Closed-form Optimization ^ 30 4.1.2^Statistical Approaches to Adaptive Modulation Design 37 Adaptive Learning Approaches 39 4.2 5 15 ^ Stochastic Optimization in Adaptive Modulation ^ 41 5.1 42 Stochastic Dynamical Model for Adaptive Modulation ^ 5.1.1^Markovian Dynamical Formulation of Adaptive Modulation Problem ^ 46 5.1.2^Constrained and Unconstrained Performance Metrics for Adaptive Modulation ^ 48 5.1.3^Convexity of Throughput and Quasiconvexity of Error Rate Constraint ^ 5.2 50 Primal Dual Stochastic Gradient Approximation for Adaptive Modulation ^ 53 5.2.1^Gradient Estimation and SPSA Algorithm ^ 54 5.2.2^System Initialization ^ 56 V 6 Results and Simulation Techniques ^ 6.1 Packet Level Simulation ^ 6.1.1 Performance Results ^ 6.2 Bit Level Simulation 6.2.1 Simulation results 57 57 58 ^60 ^60 6.2.2 Uncoded Transmission ^ 60 6.2.3 Convolutional Coding ^ 64 6.2.4 Turbo Coding ^ 66 7 Conclusions and Future Work ^ 69 Bibliography ^ 70 List of Figures 5.1 System block diagram for adaptive transmission ^ 42 5.2 Rayleigh fading realization simulation block diagram [44] ^ 44 5.3 Rate region thresholds ^ 45 5.4 Effective system model for stochastic learning algorithm ^ 53 6.1 Increase in average throughput for Gilbert-Elliot Channel ^ 58 6.2 Increase in average throughput for Gilbert-Elliot Channel ^ 59 6.3 Average throughput versus SNR for fixed and adaptive modulation policies without coding ^61 6.4 Average throughput versus SNR for fixed and adaptive modulation policies with no coding in Rayleigh fading with packet error rate constraint 62 6.5 Tracking of adaptive modulation system under 16dB average SNR where PER constraint is adjusted at iteration 100 from 1% to 8% . . 63 6.6 Average throughput versus SNR for fixed and adaptive modulation policies with convolutional coding in Rayleigh fading ^ 64 6.7 Average throughput versus SNR of adaptive modulation learning process under convolutional coding with 10dB average received SNR and constrained PER of 1% vi 65 vii 6.8 Tracking of adaptive modulation system under 16dB average SNR where PER constraint is adjusted at iteration 75 from 1% to 5% . . ^66 6.9 Average throughput versus SNR for fixed and adaptive modulation policies with turbo coding in Rayleigh fading ^ 67 6.10 Average throughput versus iteration number of adaptive modulation training under turbo coding with 15dB average received SNR ^ 68 Acknowledgments Firstly, I would like to thank Dr. Vikram Krishnamurthy for all of his guidance and support as I worked towards the completion of this thesis. I would also like to thank Dr. Robert Schober. Without his input and detailed review this work would not be of the same quality. I must also thank the University of British Columbia for the honor of the UGF. In addition, I would like to thanks Dr. Vijay Bhargava for helping guide me along my path through UBC and beyond. viii Chapter 1 Introduction The demand for high-speed wireless connectivity has exploded. Technologies such as wireless local area networks (LANs) and Third Generation (3G) wireless networks have become cornerstones for delivering rich multimedia content to end users. As the demand for high-speed wireless connectivity grows, future wireless networks will support even higher data rates. Unfortunately, bandwidth is a finite resource. As users demand higher data rates, wireless communications systems must employ new strategies to exploit the already crowded wireless channel in the most efficient way possible. Adaptive modulation is one such technique that has garnered much attention. As we look to the future, the emergence of Software Defined Radios (SDR) has changed the possibilities for modulation and protocol development. A software defined radio is a device that provides software control over modulation techniques [7]. SDRs are extremely agile and are able to implement dynamic physical layer transmission parameters in real-time [5]. Initiatives such as the Joint Tactical Radio Service and the XG standards are pushing the development of SDR technology. 1 1.1 INTRODUCTION^ 2 Adaptive modulation is an important element in maximizing spectral efficiency for SDRs. However, new approaches can be taken in order to capitalize on the newly available flexibility. Built on the foundation of SDR, Cognitive Radio [17, 15] has emerged as a research area of much interest. The aim is to use the flexibility and adaptability of SDR to design 'intelligent re-configurable' communications devices, those which are able to sense their operating environment and adapt accordingly. Adaptive modulation is one such form of adaptability in the face of time varying conditions. In wireless communications systems employing adaptive modulation, the transmitter is able to vary the transmit power, constellation size, data rate, error coding rate and scheme in response to a flat fading channel. In this fashion, the transmitter is able to maximize power and bandwidth efficiency while meeting certain constraints [12]. Adaptive modulation has been actively researched as a key component in many proposed wireless standards [22]. The design of adaptive modulation systems relies upon finding an optimal modulation policy. The policy is a mapping of channel quality measurements to the modulation scheme to be engaged at the transmitter. The policy is optimal in the sense that it optimizes some performance metric of the communications system. The metric of interest varies depending on the specific application. For example, the optimal choice may be to maximize spectral efficiency (bps/Hz) for a certain target bit error rate (BER) or to maximize overall throughput where the average BER is not a concern. 1.1 INTRODUCTION^ 3 1.1 Motivation Research into the design of adaptive modulation systems has relied primarily on analytical approaches [9] [13] [12]. Thereby an analytical model of the input/output characteristics of the communication system is derived as a function of the modulation policy used. In some cases functional approximations are used where the exact relationship is not convenient for analysis. It is then possible to find an optimal set of parameters that define the modulation policy to maximize the spectral efficiency or overall throughput. Techniques such as Lagrange optimization have been used to solve for the modulation policy [9]. This is a powerful approach that finds optimal solutions to a large class of adaptive modulation systems. We propose re-enforcement learning based adaptive modulation techniques that will allow an SDR to take full advantage of its inherent adaptability. Learning based solutions are ideally suited for the flexible nature of SDR modulation control. We consider a radio that may be preprogrammed with a set of modulation and coding schemes. These may include various constellation types, forward error correction codes and different decoding algorithms. In real-time the radio is capable of sensing its transmission performance and updating its internal modulation parameters in order to improve communications given the set of all operation modes. The learning based approach is motivated by the fact that, in certain cases, it may be difficult to define the input/output characteristics of the system given a broad set of communications options [19, 31]. For example, the inclusion of convolutional or turbo error correction codes may complicate the task of deriving analytical expressions for the error rate performance as a function of signal to noise ratio. In addition, real-time changes to the communications constraints, an attractive option in SDR, may not be 1.2 INTRODUCTION^ 4 possible. We aim to develop algorithms that allow devices to intelligently select transmission parameters in order to efficiently use the radio spectrum given limited information of the communications system. Technologies such as Cognitive Radio are utilizing SDR as a platform for the advancement of research into intelligent communications devices [15]. In this work, we present real-time machine learning algorithms that assess the performance of the current system and iteratively tune communications parameters in order to optimize system performance. 1.2 Contributions of the Thesis • We model the adaptive modulation communication system by a general state space Markovian stochastic process. We consider packetized transmission with arbitrary error correction coding. We show the Harris recurrence of the Markov Chain, the existence of a unique invariant distribution and pose the optimization of the feedback signal as a stochastic optimization problem. • We show that the cost functions presented are convex and exhibit global convergence to the optimal value under certain assumptions. • A re-enforcement learning based algorithm is used for the optimization of the cost function. The optimization is simulation based where stochastic approximates of the gradient of the cost function are used to iteratively update the control parameter. Gradient estimation is performed using sample-path techniques. The optimization is performed online with no training data required. 1.3 INTRODUCTION^ 5 • Experimental simulations were run to test the ability of the proposed algorithm to learn the optimal modulation policy. We provide results for various error correction codes used and comparison to analytic design techniques. 1.3 Organization The remainder of the thesis is organization as follows. In Chapter 2 the theory behind fading in wireless communications is discussed along with the advantages offered by adaptive communications. The opportunities made possible by SDR are also explored along with advances in intelligent agents in communications research. Chapter 3 reviews some of the basic principles of optimization theory, stochastic optimization, stochastic processes and simulation. The theory is used later on to develop stochastic optimization algorithms for adaptive modulation. Chapter 4 outlines current approaches to adaptive modulation system design. Here we outline the general mathematical optimization problem as well look at well studied solutions to those problems. Chapter 5 contains the novel work presented. We derive the adaptive modulation system as a controlled stochastic process and provide mathematical details on the modeling and optimization of the system. In Chapter 6 simulation results of the designed algorithms are presented. Chapter 2 Adaptive Modulation In this chapter we discuss the general problem of adaptive modulation design from wireless communications fundamentals. We begin by presenting basic properties of the radio communications channel that adaptive transmissions aim to exploit. We present some basic communications theory on fading channels and adaptive signaling. In addition, background information on the development of SDR and an extension, Cognitive Radio, are discussed to better frame the task of developing learning based algorithms for reconfigurable devices. 2.1 Wireless Channel Fundamentals Wireless communications is the research of transmitting information over electromagnetic waves. Antennas are able to transmit and receive the signals and our goal is communicate the largest amount of data while using the fewest resources possible, in this case spectrum bandwidth and transmit power. The main obstacle to communication in wireless settings is the wireless channel. The simplest model for the wireless 6 2.1 ADAPTIVE MODULATION ^ 7 channel is the free space propagation model. Derived from Maxwell's equations, this model has all electro-magnetic waves emanating from a point source in all directions losing energy in accordance to a 1/(distance) 2 rule. However, this simple model is rarely sufficient to capture the dynamics of realworld channels. Properties such as refraction, scattering and diffraction produce multiple received copies of the transmitted signal that leads to distortions such as fading and shadowing. In land-mobile communications the base station antenna is usually geographically fixed and the device is free to move. As the user moves these disruptive phenomena will vary and produce irregular received information. Wireless communications research has looked at many techniques to overcome the disruptive nature of the wireless transmission channel. This thesis deals with efficient use of spectrum in response to fading. In general, fading is a phenomenon where the quality of the transmission channel varies with time and position. When using a fixed rate communications system engineers must design the system to be robust enough to transmit during most times of poor channel condition. Unfortunately, this may be wasteful. Fixed rate transmission systems may transmit at times of extremely poor channel quality where the probability of successful transmission is very low, therefore wasting power. Conversely, in times of high channel quality, the channel may bear the opportunity for highly reliable communications at much higher data rate. The transmitter may take advantage of the fluctuations if they are slow and can be effectively tracked. Adaptive modulation is a technique where the transmitter may adapt it communications parameters in order to minimize wastage and maximize data rate. If the transmitter where presented information about the channel, it may pick a transmis- 2.1 ADAPTIVE MODULATION^ 8 sion mode that will perform reliably and transmit as much data as possible. In this thesis we analyze how the transmitter may 'pick' the best transmission mode given information about the channel. To design such systems we must first understand the fluctuations of the channel quality. We refer the reader to [27, 14, 28] for a more in depth treatment of the subject. 2.1.1 Multi-path fading One of the fundamental problems of wireless communications is that the line-ofsight link between transmitter and receiver may be obstructed. In fact, in many urban settings, the received signal may undergo numerous scatterings off surrounding buildings or diffraction around buildings or objects. All of these scattered carriers meet at the receiver and sum to create a new effective received signal. Now consider the case where the receiver is moving. In this situation there is a continuous change in the lengths of the paths between the transmitter and receiver. Therefore the relative phase of the two attenuated signals is constantly changing in time. As the mobile receiver moves it may encounter constructive interference at some locations and destructive interference at others. For practical mobile environments there may be many reflected and scattered copies of the signal received. Of course, there will be many propagation paths and the received signal would be a combination of all these paths. The net effect is that the received signal envelope will vary in a complicated fashion in practice. In settings such as urban areas, there are numerous obstructions between the transmitter and receiver. Additionally the specific obstructions will change with time as the user moves about. 2.1 ADAPTIVE MODULATION^ 9 Fading is essentially a spatial property of a received signal in an environment. We see its effects in the time domain as a mobile receiver moves in the environment. The variations can be related to the motion of the receiver as the Doppler shift. The Doppler shift results in an apparent shift in frequency due to the motion of the mobile. The apparent shift in frequency of the received signal, v, is given by v v--= — cos a A (2.1) where v is the speed of the receiver, A is the wave length and a is the angle between the direction of motion and the location of the transmitter. 2.1.2 Statistical Properties of Fading Channels The received signal is a amalgamation of multiple reflected, scattered and refracted copies. The modeling of individual scattered signal levels is practically impossible given the range of materials that the signals may reflect off of, the geometry of surrounding reflectors and movement of antennas. In addition there are many random parameters involved in fully characterizing the received signal: noise, user movement, objects moving in the area. In general, the properties of a radio communication channel can only be characterized by statistics of the observed variations. A model used for the fading process in Rayleigh fading. The autocorrelation of the fading process h is modeled by Rh(r) = J0(2 7rfdTsT )^ (2.2) 10 2.2 ADAPTIVE MODULATION^ where fd T8 is the normalized Doppler spread, J0 is the Bessel function of the first kind and 7 is the time offset. In flat fading, the multi-path structure of the channel is such that the spectral characteristics of the transmitted signal are preserved at the receiver. However the strength of the received signal changes with time due to fluctuations of the gain of the channel due to multi-path effects. The variation of the channel can be modeled as Rayleigh or Rician fading. A signal undergoes flat fading if Bs << Bc and if Ts UT where Bs is the bandwidth of transmitted modulation, Ts = llBs is the symbol period, Bc is the coherence bandwidth and UT is the rms delay spread. The bandwidth of the signal is much less than the coherence bandwidth of the channel. If the channel gain changes over time a change of amplitude occurs in the received signal. Another statistical model for channel effects is the First Order Markov Chain Model [40] [41]. In this model a slowly varying flat fading channel can be modeled as a Markovian stochastic process. Throughout this work we consider communications in slowly varying flat fading channels. 2.2 Adaptive Modulation Communications systems that employ adaptive transmission modes aim to use the channel in the most spectrally efficient manner possible. Spectral efficiency is defined as the data rate per unit bandwidth used. The transmitter is able to take advantage of favorable channel conditions by transmitting at high data rates and gracefully 2.2 ADAPTIVE MODULATION^ 11 decrease the data rate during periods of poor channel quality. In this fashion, the amount of data that can be reliably transmitted is maximized. The basic premise of adaptive modulation is the real-time balancing of the link budget in flat fading channels through adaptive variation of the transmitted power level, symbol transmission rate, constellation size, BER, coding scheme/rate or any combination thereof. Adaptive modulation relies on accurate channel information and reliable feedback path. The design of adaptive modulation systems relies upon finding an optimal modulation policy. The policy is a mapping of channel quality measurements made at the receiver to the modulation scheme to be picked at the transmitter. The optimal policy is the mapping that maximizes some desirable performance metric. This metric of interest varies depending on the specific application. For example, the optimal or `best' choice may be to maximize spectral efficiency (bps/Hz) for a certain target bit error rate (BER). We may be interested in maximizing throughput where the average BER is not a concern. Experiments have been conducted to measure the increase in performance of adaptive transmission schemes compared to fixed transmission systems. [12] has shown that adaptive modulation greatly increase the data throughput of wireless communications system compared to fixed schemes. We consider a few basic means by which the transmission rate may be varied. The first is variation of the signaling rate by changing the modulation constellation used. For this study we consider M-ary Quadrature Amplitude Modulation as the transmission constellation. MQAM is a digital modulation technique where M bits of information may be mapped to one of 2m possible transmission symbols. Low rate 2.3 ADAPTIVE MODULATION^ 12 transmission schemes offer robust communications as opposed to more sensitive high rate constellations. The transmission rate and communications quality may also be affect by the error correction coding used. For this study we consider convolutional codes [42] as well as turbo codes [16]. We consider these codes due to their importance in the development of current and future standards. These are the basic tool of digital communications we are interested in the properties of the devices that will employ them. Software Defined Radio is an emerging technologies that offers new capabilities for communications protocol design. 2.3 Software Defined Radio A Software Defined Radio is a device where all of the communications actions are accomplished in software. Aspects such as the protocol or system that the device operates under can be reprogrammed. Even physical layer parameters such as modulation scheme, constellation options and coding may be influenced on the fly. Traditional communications devices have their parameters set in hardware at the time of device creation. In general, they cannot be modified afterwards. The SDR framework has many advantages over traditional systems. SDR based systems are much more flexible in terms of communications standards that may be used. The heart of the SDR is a general purpose processor. Functions such as error coding, modulation and detection con be programmed onto the device. In addition, the wireless device may be reprogrammed on the fly. The network that the device logs onto may change over the operation of the 2.3 ADAPTIVE MODULATION^ 13 user. For example one radio may join an analog cellular network, a digital Personal Communications Service (PCS) network or become a cordless phone or even a pager. This level of flexibility is not possible in current fixed wireless device design. Speakeasy is a military SDR system under development [39]. The goal is a standardized, modular system for SDR development. It is static SDR system where any number of communication standards can be preprogrammed and switched between during operation. The project addresses three key difficulties with battlefield communications devices [3]. They are: • inadequate interoperability • poor interference tolerance, especially mutual interference due to nearby radios • speed/flexibility of deployment and other miscellaneous practical usage issues SDR technology will aid in overcoming these practical challenges. There are also interesting application of SDR for dynamic physical layer operation, a feature capitalized on by our proposed learning algorithm. In [25] [24], the authors develop an automatic modulation scheme recognition system that is robust and realtime. The technique is based in pattern recognition theories. The system they have developed is capable of differentiating analog from digital modulation and then from there determining the exact modulation scheme used. The system relies on signal characteristics that can be quantified and exploited. For example, when trying to differentiate between AM and FM it is possible to measure the variance of the received signal envelope to determine the underlying modulation scheme. 2.4 ADAPTIVE MODULATION^ 14 The authors provide an example where the increased flexibility of SDRs may be leveraged to design new and exciting applications. In [5], the authors also research applications of devices that offer complete software control over modulation options. We are interested in this flexibility of SDR that allows convenient application of re-enforcement learning algorithms. 2.4 Cognitive Radio Cognitive Radio technology is a revolution in the design of wireless communications protocols. Cognitive radios take SDR one step further [10] [17] [18]. The idea is to allow a highly flexible radio to sense its environment and intelligently adapt its communications parameters in order to maximize performance. Radios compete, and cooperate, for radio resources. A cognitive radio may adjust its carrier frequency, modulation scheme, power level, protocol or any other communication parameters. The goal is the most efficient use of the channel at all times. A major focus is using CR to take advantage of unused spectrum between regulated bands. There is much opportunity for a class of learning based algorithms to allow radios to jump in and out of these gaps with minimal impact to resident communications networks. The goal is highly efficient spectrum usage and robust communications. The solution is seen as developing intelligent devices that are able to learn the optimal actions to take while interacting with their environment. In [15], the author has outlined a mathematical framework for estimation and cooperation in CR networks. The author re-iterates the importance of re-enforcement learning based solutions in highly dimensional problems. Chapter 3 Stochastic Optimization Our aim in this thesis is to design real-time learning based adaptive modulation algorithms As we have seen, technology such as SDR allow for the real-time adaptability needed to pursue such approaches. In this chapter, we review some of the fundamental mathematics that will be applied to adaptive modulation design. The techniques used for optimization are stochastic optimization algorithms and more specifically simulation based optimization algorithms. We begin this section with an overview of the basics of convex optimization, present differences between deterministic and stochastic optimization algorithms as well as discuss sample path based stochastic optimization problems. 3.1 Convex Optimization In this section we outline properties of convex functions and optimization problems involving convex functions. 15 3.1 STOCHASTIC OPTIMIZATION ^ 16 A mathematical optimization problem has the form minimize (3.1) fo(x) subject to fi (x) < b i i = 1,^, m^(3.2) The variable x^(x 1 , . , x n ) is known as the optimization variable. The function fo : Rn R is called the cost or objective function. The functions A : IR 7 R are known as the inequality constraint functions where the b i are the constraint bounds for i = 1, , m. The point x* is defined as the optimal value of the optimization problem or equivalently the value of x which has the smallest objective value while obeying all constraints. We assume its domain D nri n_ o dom A and denote the optimal value of the function by p*. We are particularly interested in the classes of problems where the objective and constraint functions are convex. A function is convex if it satisfies the inequality Max +,3y) 5_ Max) + ^ (3.3) for x, y E Rn and a o3 E R with a + = 1 and a > 0, > 0 A fundamental property of convex optimization is that any locally optimum solution must be a global optimum. [6] provides proof of this statement as well as conditions for optimality for differentiable functions A. A more general condition of convexity is known as quasiconvexity. A function f : W1^JR is called quasiconvex if its domain and all sublevel sets Sa = { x E dom flf(x) 5_ al^ (3.4) 3.1 STOCHASTIC OPTIMIZATION^ 17 for a E R are convex. For a function on R, quasiconvexity requires that sublevel set is convex, including open intervals. We may represent the sublevel sets of a quasiconvex function by a set of inequalities of convex functions. We are interested in the family of convex functions cbt : R, indexed by t E R with f(x) t <#. o t < o (3.5) For convex optimization problems with quasiconvex constraint functions the constraints may be substituted with the equivalent convex constraint function with the same 0-sublevel set. When solving convex optimization problems such as (3.2), we can incorporate the constraints into the cost function by considering the Lagrangian function. The Lagrangian L : Rn x Rm R associated with (3.2) is given by m L(x, A) = fo(x) ^ ifi(x) ^ (3.6) i= 1 with dom = D x R' x Ilk. We refer to A, as the Lagrange multiplier associated with constraint i. We define the Lagrage Dual function g : R m R as the minimum value of the Lagrangian over x g(A) = inf L(x, A) = inf (fo (x) + xED^xED fi (x))^(3.7) i=1 The dual function yields lower bounds on the optimal value p* of (3.2). For any A > 0 we have that g(A) 5_ p*^ (3.8) ^ 3.1 STOCHASTIC OPTIMIZATION^ 18 The dual problem is always concave regardless of whether the primal is convex or not. A natural question we may be interested in is what is the best lower for the value p* that can be found as A varies. This leads to what is known as the Lagrange dual problem: maximize g (A)^ (3.9) subject to A > 0^ (3.10) We refer to A* as dual optimal if it is optimal for (3.10). If we denote the optimal value of the Lagrange Dual problem of (3.10) by d* we have the following inequality d* < p*^ (3.11) which holds regardless of convexity of the original problem. This property is called weak duality. If equality holds we have what is called strong duality, or equivalently the duality gap is zero. If the primal problem of (3.2) is convex, we usually have strong duality. There are constraint qualifications that reinforce the strong duality property, for example Slater's condition. A proof for strong duality on constraint qualification can be found in [6, p234]. Let x* and A* be any primal and dual optimal points with zero duality gap. Given that x* minimizes L(x, A*) over x, it follows that m vfo(x.)+E A:vfi(x), 0^(3.12) i=1 ^ 3.2 STOCHASTIC OPTIMIZATION ^ 19 Therefore we have the Karush-Kuhn-Tucker (KKT) optimality conditions i (c) ^f < 0, i^1,... , m A i > 0, i^1, . , m (3.13) fi () = 0, i = 1, . , m VfoW + , AiVfiW = 0 which state that when the primal problem is convex any points ^A) that satisfy the KKT conditions are sufficient for the point to be primal and dual optimal. If a convex optimization problem that is differentiable and meets Slater's condition then the KKT conditions provide necessary and sufficient conditions for optimality. Given the framework discussed so far our ultimate goal is to solve the optimization problem. For this we may apply an iterative optimization method for constrained optimization, analogous to steepest decent optimization. The search direction may computed from the first order KKT conditions as ox = V fo(x (n) ) + E A i(n)vfi(x(ri))^ (3.14) Obi = fi (x ( n ) ) — b i^(3.15) 3.2 Markovian Stochastic Processes In many instances the evolution of a dynamical system can be modeled statistically. Wireless communications systems are no different. Fading processes are an example. 3.2 STOCHASTIC OPTIMIZATION ^ 20 One very powerful probabilistic model is the Markov Chain. The theory of Markov Chains has been widely investigated [23]. Our aim is to model physical processes by Markovian dynamics and apply mathematical findings for the purpose of estimation and optimization. In this section we provide formal definition of a Markovian process as well as outline the fundamental properties of Markov Chains that enable us perform simulation based estimation and optimization applied in following chapters. Let X be a general set and 8(X) denote a countable a-field on X. If P = {P(x, A), x E X, A E 8(X)} such that 1. for each A E 13(X), P(., A) is a non-negative measurable function on X 2. for each x E X, P(x,•) is a probability measure on 13(X) then P is a transition probability kernel. The stochastic process 4) = {43 0 , 43 1 , ...} defined on (52, F), where 52 = fr o X, and F =U,°, ° 0 B(Xi), is called a time-homogeneous Markov chain with transition probability kernel P(x, A) and initial distribution it if the finite dimensional distributions of 1 satisfy PA( 43 0 E Ao, Di E A1,^, Dri E An) ( ( A^• yoe—o^ /1(40)P(Yo, dYi) • • P(Yn-1, An) (3.16) for every 71 E Z + , where 1u is initial measure on B(X) and Pi, is a probability measure on such that pi is the probability of event {(13 E B} for B E ,F; and for measurable A i C Xi , i = 0, , n. Equation (3.16) defines the restriction on P for the process (I) to be a discrete time, general state space Markov Chain. In general it states that the probability 3.2 STOCHASTIC OPTIMIZATION ^ 21 distribution of state .13„ ±i is only dependant on the current state (13„ and no previous history. Given the definition of the Markov chain we seek structure of the probability matrix which exhibit poroperties which aid in estimation and optimization. We define the concept of irreducibility or the fundamental idea that all parts of the state space of the Markov Chain can be reached. If there exists an irreducibility measure c,o on 13(X) such that for every state x co(A) > 0 —÷ L(x, A) > 0^ (3.17) then there exists an essentially unique maximal irreducibility measure 0 on 13(X) such that for every state x we have L(x, A) > 0 whenever 0(A) > 0. For the chain (I), x E X and A E 13(X) we write Q(x, A) := Px {kli E A infinitely often}^(3.18) The set A is called Harris recurrent if Q(x,^= Px (77 = oo) = 1^ (3.19) for x E A. A chain is called Harris recurrent if it is 0-irreducible and every set in 8+ (X) is Harris recurrent. A a-finite measure 7 on 13(X) is said to be invariant if 7 (A)= I (dx)P(x , A) (3.20) 3.2 STOCHASTIC OPTIMIZATION ^ 22 for A E 13(X). It can be shown that if a Markov chain is recurrent it posses a unique invariant distribution [23, p235]. In addition, for all initial states of the chain, the chain is geometrically ergodic and converges to the invariant measure geometrically fast. 3.2.1 Markov Chain Monte Carlo Consider the Markov Chain Z = .1 on state space (X, 13(X)). The transition probability kernel is given by P(x, A) as outlined in Section 3.2. Assume that Z is positively Harris recurrent possessing unique invariant distribution 71 and geometri- cally ergodic [30]. We are interested in estimating real functions c : X —* R of the state variable Zk given by Eir[c(Z k )] = f c(z)7(z)dz (3.21) If it were possible to sample from the distribution it we may estimate the value v of (3.21) via the Strong Law of Large Numbers tells us that the arithmetic mean of an independent sample from it converges to the integral S N(c) = E N k _ l c(zk) --+ E,[c(Z k )], k oo (3.22) However, if we sample according to the irreducible, ergodic Markov Chain Z, although the samples are no longer independent, the ergodic theorem implies the convergence of sample value means [23]. As we will show, when a physical process is modeled as a Markov chain with the requisite recurrence and ergodicity properties we may estimate functions of the form 3.3 STOCHASTIC OPTIMIZATION^ 23 (3.21) by Monte Carlo simulation where the function c takes the physical interpretation of some performance function of the Markov chain. This is especially helpful in cases where the limiting distribution may not be known or the function c itself may not be known yet observable. We will use this property to help find sensitivities of the cost function to aid in optimization. 3.3 Optimization with Noisy Function Estimates The theories of Stochastic optimization aid in the optimization of functions where only noisy estimates of the performance function are available. If the experiment which generates the observed output is repeatable it may be possible to estimate sensitivities of the system due to a parameter of control and perform optimization [ 8 ]. Let 0 E RP be a general parameter that affects the behavior of a system. The state of our system at time t is written X(t, 0) to indicate its dependence on 0. When a sample path of this system is observed, its "performance" is a function of the state history X(t, 0). We use L(9, w) to denote the sample performance function where w denotes a particular sample path. (We can think of 12 as being the set of all possible sample paths and w E C2). For any given B, since X(t, 0) is generally a stochastic process, L(0, w) is a random variable. L(0, w) is the performance under a certain sample path. We are interested in the average performance over all sample paths, that is the expectation over all possible 3.4 STOCHASTIC OPTIMIZATION^ J(9) = E[L (0 , w)}^ 24 (3.23) The expectation is over some measure on a If we observe n separate sample paths w i w n then an estimate of J(9) is given by n 1(0) = n^ . L(9, w i ) (3.24) We wish to pick a 9 that maximizes J(0). In many systems the function J(9) is simply unknown. The idea is to use several sample paths from which we can evaluate L(9, w 1 ) . . . L(9, w7 ,) and produce an estimate J(9) by averaging. To do this, in practice we would set the parameter to some value 90 and observe (.4) 0 in order to get an estimate of J(00), J(00 ) = wo). We can then change the parameter to a new value, 9 1 , obtain a new sample path w 1 and performance measure L(9, w 1 ). The comparison of L(0 0 , w0 ) to L(0 1 , w i ) tells us whether we have a performance improvement or not. Obviously, trying this technique for all values of 9 is impractical. We want to predict the effect of a change from 0 0 to 0 1 without actually trying it. We want to find 1(0) and somehow extract some gradient information. This information can help us find a new 0 1 as we try to maximizes or minimize J(0). 3.4 STOCHASTIC OPTIMIZATION ^ 25 3.4 Stochastic Approximation In this section we discuss stochastic approximation (SA) methods for gradient approximations where noisy estimates of the loss function J are available. We focus our discussion on two main forms of SA, finite difference SA (FDSA) and stochastic perturbation SA (SPSA). We wish in general to approximate the sensitivities of the function J(0). The aim is to approximate the sensitivities without direct gradient information of the cost function available, only measurements of the noisy cost function. One possible method is stochastic approximation (SA). Robbins and Munro [29] introduced SA in the early fifties as a method for optimization when only noisy estimates of the loss function L are available. To motivate our discussion recall the steepest descent algorithm for unconstrained optimization O(k+1) , O(k) + a (k) g (O(k)) (3.25) where the gain a k > 0 and g is defined as OJ g(e) = DB (3.26) at iteration k. Using the given formulation 9 -- 9* as k -* oo given certain conditions. For our purposes, assume J is convex, with unique global optimum 0*. There are cases where we may not have direct information of g, only estimates g. In which case we may consider the iterative optimization algorithm O(k+1) _= 8(k) + ct (k) j•(4i(k)) (3.27) 3.4 STOCHASTIC OPTIMIZATION ^ 26 The key to solving such a recursion is the estimation of :4(O (k) ). One of the best known techniques for gradient estimation is Finite Difference SA (FDSA). FDSA has its roots in the definition of the gradient as a vector of p partial derivatives where the control parameter B E W. The two-sided Kiefer-Wolfowitz FDSA[20] involves the measurements AO (k) + perturbation) with J O ( k) + ,(k)w j(e(k ) _ c ( k)4- 1 ) 40 k)) . 2 c( k) ( (3.28) j( O (k) + c ( k )G )_ j(e( k ) _, (k) ep ) 2c(k) where e i denotes a 1 in the ith component and 0 everywhere else and c (k) > 0 denotes the difference magnitude. Standard conditions on the gain sequences to guarantee a (k) >^c(k) > 0, a (k)^0, c (k) convergence are:^ Ei7o a (k) =- oo and V•00 (k)2 /c(k)2 < z_a k= o a/ oo. The selection of optimal gain sequences is dependent on the specific problem being solved. In general a mix of heuristic, analytic and trail-anderror numerical experimentation will yield satisfactory gains. One drawback of the FDSA method is the approximation of sensitivities for problems with high dimensionality p. The FDSA techniques requires 2p loss function measurements to generate the two-sided estimate .0(9 (k) ). As p increases it may no longer be practically feasible to approximate the gradient. Another approach, first presented by Spall [34, 35, 33], is the so called Simultaneous Perturbation Stochastic Approximation. In SPSA all elements of the test vector O (k) are perturbed by the random vector (k) to produce two measurements 3.4 STOCHASTIC OPTIMIZATION ^ y(( k ) c (k) (k)) 27 of the loss function. For the two sided case we have — j (e (k )± c ( k)A(k) ),_ j( O (k)_ c (k )A (k ) ) 2c(k),64 k) g(e (k (3.29) ) ) j( d( k) ± c ( k) A (k )) _ j (O (k ) _, (k )A (k ) ) 2 c(k ) ,k) ( where the vector A is zero mean. The elements of L\ k) are independent for all k and i, identically distributed for all i at each k, symmetrically distributed about zero and uniformly bounded in magnitude. In addition there is an important condition on the inverse moments namely 1 <C (k) (3.30) 2 + 2r) for some T > 0 and C > 0. This condition is needed to control the variation of the elements of .4(O ( k)). A specific distribution which satisfies the conditions is the symmetric Bernoulli {±1} distribution. Due to the fact that SPSA has all components of the test vector O (k) randomly perturbed, only two loss measurements are required to form gradient estimates independent of p. This gives SPSA potential for large savings in the overall cost of optimization. This potential is realized when the number of iterations needed for effective converge to 0* does not increase so as to cancel the savings gained through measurement savings. Under reasonably general conditions, SPSA and FDSA achieve the same level of statistical accuracy for a given number of iterations considering the measurement savings afforded by the SPSA approach. We know turn our attention to the conditions under which SPSA iterates converge. [34] rigourously details proofs of convergence for the SPSA algorithm. The conditions 3.4 STOCHASTIC OPTIMIZATION ^ 28 place restrictions on the selection of gain sequences and properties of the cost function under investigation. We have the following restrictions on a and c; a (k) > 0, c (k) > 0, a (k) 0, c (k) —+ 0, Er=o a (k) oo and E kci o a (k)2 /C (k)2 < oo. The standard form of the gain sequences is given as a (k) = ^ (k + 1 + A)a (3.31) and C (k) = ^ (k + 1)1' (3.32) with a, a, c, and 'y selected in accordance to the specific problem. Selection of optimal gain coefficients is a heuristic task and one of the drawbacks of SPSA. Experimentation is needed to tune the gain coefficients and find suitable parameters. Chapter 4 Current Research Work in Adaptive Modulation In this chapter we discuss the current approaches to adaptive modulation design. Most research work has looked into deterministic state optimization where the input/output characteristics of the communications system are algebraically modeled. We present the problem formulation as well as how solutions were gained through this approach. 4.1 Theory of Adaptive Modulation The goal of adaptive modulation system design is to determine the optimal policy of rate, power and BER adaptation to maximize spectral efficiency subject to rate, power and quality of service constraints. For any channel state, in this case the channel state is received SNR -y, what is the best choice for rate and power when aiming to satisfy a target BER constraint. In continuous adaptation this boils down 29 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^30 to finding a function that maps SNR -y to the associated rate/power. For the discrete rate case, we must map discrete regions of y to a particular rate. The set of all possible SNR values is divided into N intervals, [-y„ 7, 4.1) 3 (0 < i < N — 1) . When the instantaneous SNR falls into one of these regions we select the corresponding rate. As the system operates we may observe the performance as a function of the rate region threshold boundaries. The optimal rate region boundaries are those that optimize the performance of the system. Rate region boundaries that are aggressive yet still able to maintain constraint conditions. The major approach used in solution of the optimization problem if presented in the first section with other very powerful methods discussed below. 4.1.1 Closed-form Optimization There has been much work in the areas of adaptive modulation dedicated to analytic modeling of the performance of the system as a function of modulation constellation, error correction coding and channel quality. The approaches generally look at modeling observed data with closed form approximation that closely match the data. Given the closed form expression, algebraic optimization algorithms can be applied to find optimal modulation policies. In this section we outline some of the major works in this area. Degrees of Freedom in Adaptive Modulation [9] The authors investigate adaptive modulation techniques with the aim being to optimize spectral efficiency. The parameters of control are data rate and transmit power. The constraints are average power, average/instantaneous BER. We begin 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^31 by discussing the system model used by the authors and then present cost function formulation and solution approach. A discrete time channel model with time varying gain Ai], additive white Gaussian noise n[i] with variance cr 2 is used. Let S be the average transmit power, B be be the average channel power gain. Assume that the received signal bandwidth and be the feedback path is instantaneous and error free. For constant transmit power S the instantaneous received SNR is Sg[i] r[i] = - 0.2 • (4.1) S(-y[i]) is the transmit power at time i an a function of SNR and the received SNR at time i is yiil seT[i]) s,^ • (4.2) This equation represents the ratio of instantaneous power, S, to the average power, S . Using this scheme a scaled version of SNR is measured. Finally, let p(7) be the probability distribution of -y[i]. Note that -y is a stationary stochastic process and therefore p(-y) is independent of i. Assume ideal coherent phase detection. Spectral efficiency equals the average data rate per unit bandwidth. When we send k(y) = log 2 (M(-y)) bits/ symbol, the instantaneous data rate is k(y)/Ts bps, where Ts is symbol time. For continuous rate adaptation R = E[spectral efficiency]^ B 1 1 = E[k(7)-— ] bps/Hz . Ts B = fo k( - (4.3) (4.4) y)p(-y)d-y bps/Hz^ (4.5) 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^32 For discrete rate adaptation we have f =E R^N B - 1^ y, + 1 p(-y)d-y bps/Hz. (4.6) z=0 These equations are our cost/reward functions. The following average power constraint is used l (4.7) c° S(7)P( Y)d7 5 S - The average BER constraint can be expressed as B E R(-y) = E(number of error bits per transmission) E(number of bits per transmission) fc7 BE R(-y)k(7)13(7)d-y RI B (4.8) (4.9) The next step is to derive an equation for the BER as a function of the rate and power for a series of non-binary modulation schemes. The technique is to approximate the true BER expression, which can be very complicated, with simpler expressions. These expressions can be inverted and differentiated with respect to the variable in interest. For example the true BER of MQAM is approximated with s@)] —1.6-y s BERMQAM(-Y) .2 exp 2k( r) 1 - (4.10) — The same technique is used to model MPSK. For all non-binary modulation schemes the authors have developed a generic BER approximation. sw [ ^( BE R(-y) :----- c i exp ^C27 f (k(7)) (4.11) 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^33 where f (k(7)) = 2 c3k(-y) _ e4 (4.12) The method of Lagrange optimization is used to solve the optimization problem. Four scenarios are considered: • Constant rate, average BER • Constant rate, instantaneous BER • Discrete rate, average BER • Discrete rate, instantaneous BER Although continuous rate adaptation is not practically feasible it provides an upper bound to the performance derived from discrete transmission modes. We are particularly interested in the discrete case where the task is to find the optimal rate region boundaries with average error rate constraint. The performance function is given as J(71) 72^'TN 8 (7)) E ki f p(-y)d-y 0<i<N-1 + 1 [ E Ti+1 ki^(BE R(y) — BE R)19 ( -y)d y] - o<i<N -1 + A2 [f oo S(7)p(7)d-y —^(4.13) "YO A suboptimal policy is given in the paper. It is shown that, although suboptimal, the policy works quite well. 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^34 As an important note, the paper shows us that near optimal performance can be obtained by varying either parameter. Therefore, it is best to vary the parameters dictated by implementation issues. Variable-Rate Variable-Power MQAM for Fading Channels [12] In this paper the authors consider adaptive modulation by varying rate and power in MQAM systems, much like the authors previous work. They also consider the effect of errors in channel estimation and feedback delay. The authors touch upon some very important practical considerations common to all adaptive systems. If the channel changes faster than it can be estimated and fed back to the transmitter, adaptive techniques will not perform well. For example, for a target BER of 10', the BER remains at its target level as long as the total delay of the channel estimator and feedback path is less than .001 A/v, where v is the vehicle speed. For a 900 MHz signal, at pedestrian speeds of 3.6 km/h the total delay should not exceed .3 ms, and at vehicle speed of 90 km/h, 13.3 its. This short of a delay can be problematic. A higher BER loosens the constraints. The paper also discusses the rate of adaptation. There are constraints as to how fast we can adapt the transmit parameters. The system model is the same as in [13] [9]. We have channel gain . V g[i], additive white gaussian noise n[i] with noise density N0 /2, average transmit power g, signal bandwidth B, average channel gain g. For constant transmit power S, the instantaneous received SNR is y[i] = S (g[i]) I (N 0 B) . Suppose we adapt the transmit power at time i based on channel estimate g[i] or equivalently -^y[i] = S:g[i]/(N0 B). Denote the transmit power with the adaptive scheme as S(y[i]) and the received 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^35 power at time i as -y[i]S(-5 [i])1 S. 7[i] has distribution p( -y) which is independent of , i. The estimate .g[i] is available at the receiver after a delay of - T seconds, this in- corporates both estimation and feedback delay. The estimation error is defined as e[i] = g[i]/g[i] = -Y[i] I -y[i]. The rate of channel variation will dictate how often the transmitter must adapt its rate/power and will also affect the BER due to estimation error and delay. For Rayleigh fading we use the Jakes model for the autocorrelation of the channel power gain over time A 9 (7) = J <,2 (27m I A) where v is the velocity. - For comparison the authors consider two established power control schemes; channel inversion and truncated channel inversion. The authors show in this paper that their uncoded MQAM scheme has an effective power loss of K with respect to the optimal transmission scheme, independent of the fading distribution. Equivalently, K is the maximum coding gain for their system. To this point there was no restriction placed on the constellation size. For practical systems we must restrict the constellation size to a finite set. The authors study the effects of this on their system. Cross-Layer Combining of Queuing with Adaptive Modulation and Coding over Wireless Links [22] In this work the authors tackle to task of adaptive modulation design for packet based communications. Their approach to designing the adaptive modulator is based on analytic model fitting of experimental packet error rate curves. For example, The 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^36 HIPERLAN/2 standard has published sets of packet error rate models of the form PERn (7) 1 1,^if 0 < 7 < a n exl)( - 9n"-Y) if 7 ^ 7pn (4.14) 7pn where n denotes the mode index, -y is the received SNR and a n , gn and -ypn are mode dependent parameters calculated by fitting the exponential curve to experimental data. Adaptive Coded Modulation for Fading Channels [13] This paper aims to develop a technique of joint adaptive error coding/modulation over flat fading channels. Coset codes are used as a coding scheme and laid on top of the underlying adaptive modulation scheme. The coded Modulation scheme exhibits a coding gain over standard adaptive modulation. The system model used is the same as in [9]. A binary encoder operates on k uncoded message bits to produce k + r = n coded bits, and then the coset (subset) selector uses the coded bits to choose one of the 2 n cosets from the partition of the signal constellation. During a given symbol periods T (-y) the size of each coset is limited to 2 7" —k where n(y) and T(y) are function of the channel SNR. A signal point in the selected coset is chosen using n(y) — k = r uncoded data bits. The selected point in the selected coset is one of M(y) = 2n (7) ±r points in the transmit signal constellation [e.g. MQAM, MPSK]. The idea being that by varying M(y), S(y) and T(-y) we can maintain a fixed distance between points in the received signal constellation. 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^37 The average rate of the adaptive coded scheme is given by 1: T(-y) (log2 M (-y) — r)p(-y)d-y R=L (4.15) where -y, is the minimum cutoff SNR threshold. In the remainder of the paper the authors develop a detailed implementation of an adaptive trellis coded MQAM scheme. Numerical search techniques are used to solve the optimization problem. There is a coding gain in the neighborhood of 3 dB however the tradeoff is complexity. The authors have also pointed towards adaptive turbo coded modulation as an area of promise. 4.1.2 Statistical Approaches to Adaptive Modulation Design Adaptive Modulation and Coding in 3G Wireless Systems [43] This work provides another analysis of adaptive modulation. The authors model the channel variations as a Markov chain and attempt to maximize the expected throughput of the system. In the "threshold" decision rule method of [9], the received SNR's are divide into rate regions where each region is assigned a specific modulation scheme. Then the boundary of the rate regions is optimized to maximize spectral efficiency. The authors present a statistical decision making approach. The authors use a first-order Markov chain to represent the time variations of the average channel SNR. The channel is modeled with fiat-fading and log-normal shadowing. The states represent the SNR of a frame uniformly quantized with a given step size 6 and they form a set S = {So, Si,... , Sm _i} of m states. The strategy is to assign a modulation scheme to each of the states so as to maximize expected 4.1 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^38 throughput. The transition probabilities are found by Monte Carlo simulation of the channel. After simulation, we can calculate the transition probabilities from the data. The transition probabilities tell us the probability of the received SNR going from state i to state j quantized in time over one frame duration. The transition probabilities are denoted P {73, 3 , 0 < i j < m — 1}. The stationary distribution of , the MC is H= {73 , 0 < j < m — 1}. The expected throughput Tip of the ith scheme, A, in state j is Tii E Ni pik ( — Fik ) = E [Ni (1 — Pik )] (4.16) k=0 where Ni is the number of information bits in the current frame and (1 — Fi k) is the probability of correct transmission of the ith scheme when channel is in state k. T forms a matrix where each row corresponds to a particular modulation scheme and the column corresponds to the channel state. Generally there will be many more channel states than modulation schemes. The calculation of each entry requires the evaluation of (4.16). Each entry is the expected value of the expected number of bits transmitted in the frame with the expectation taken with respect to the row of the transition probability matrix corresponding to the current state j. Now for each state we assign the scheme, A, that has the highest expected throughput and select this scheme for the next frame if the channel SNR falls into this state. In other words, assign A to S3 if > Tkj,Vk^i.^ (4.17) The expected throughput in state j is T,. The expected throughput over all states is 4.2 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^39 T = E 31 0 T . - j One of the weaknesses of the model is the need to simulate the transition probabilities. The full-scale system can be difficult to train on the fly if conditions change. The amount of computation required to find the transition probabilities is quite high. To help alleviate the problem the authors look to reduce the complexity of their algorithm by introducing a number of simplifications. As time goes on the performance of the system will get worse and worse until we can update the transition probability matrix. 4.2 Adaptive Learning Approaches Tang et.al [37, 36] have looked into the application of stochastic automata to the adaptive modulation design process. Stochastic automatons are structures which learn adaptive policies by interaction with their environment. They act by adjusting the probabilities associated with a randomized policy by assessing output performance. The Authors have shown that the learning automaton techniques was able to converge to the desired throughput. The authors have also looked into the application of this techniques to adaptive modulation in Orthogonal Frequency Division Multiplexing [38]. In addition, the author's work has looked at the case of multiple radios and mutual interference problems. The interaction and competition of multiple devices is a central idea in the development of Cognitive Radios. Bose et al have looked at the problem of designing adaptive modulation protocols for SDR [5]. The authors have consider a flexible SDR device that has the capabilities 4.2 CURRENT RESEARCH WORK IN ADAPTIVE MODULATION ^40 to adjust physical layer properties on a per packet basis. The solution proposed is to assess the various constraints on communications parameters and at each instant pick from a set of coding and modulation options. The problem is that of a discrete optimization. Chapter 5 Stochastic Optimization Algorithms for Adaptive Modulation In this chapter we present the application of stochastic learning algorithms to the design of adaptive modulation systems. We begin by presenting the system model for adaptive modulation. Next we present stochastic models as well as analysis of various costs functions and their convexity properties. We also present the optimization problem in the context of the stochastic models given. 41 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^42 Error Coding Channel AWGN Gain h k^Wk H Data Detection Performance Measurement Modulation Channel Estimation Modulation Policy Q o Yk Figure 5.1: System block diagram for adaptive transmission 5.1 Stochastic Dynamical Model for Adaptive Modulation Consider the single-transmit single-receive antenna communication system with adaptive modulation shown in Figure 5.1. The system consists of three main stages; transmitter, channel, and receiver. Transmitter: The user transmits a packet of data, ak at time instant k. The data is modulated and encoded using scheme ik to produce the passband signal xk. We assume that a k is independently and identically distributed Bernoulli random vector taking values in the set A = {0, 1}L where L is the number of information bits per packet and p represents the probability of a individual component taking value 1. We also define ik E I, where I is a discrete set of available transmission modes. The resulting signal, x k E X, is transmitted over the channel where X is the set of all 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION^43 possible modulated waveforms. We consider a transmission scheme with variable rates, where forward error correction (FEC) and M-ary Quadrature Amplitude Modulation (MQAM) is employed with a total of R possible rates. Each packet has a fixed number of symbols and the modulation scheme used is fixed within a packet. We assume that each packet contains cyclic redundancy check (CRC) information that will allow the receiver to ascertain the success of transmission. Packet based transmission is an important feature of the presented model. Much research into future wireless standards have been focussed on packet based wireless communications systems especially as data communications has become a essential aspect of user connectivity [11]. Channel: The channel is modeled as a slowly varying, flat Rayleigh fading channel with channel gain h k E 7 1 and autocorrelation R h [T] = J0 (27fd Ts r) where; - fdT3 is the normalized Doppler spread; J0 is the Bessel function of the first kind; and r is the time offset. The received signal is impaired by zero-mean additive white Gaussian noise (AWGN) w k with variance a u2 . For the learning based adaptive modulation algorithm we approximate the fading coefficient by a first order Markov chain such that hk =--- ah k _ i_ + vk, lai < 1 (5.1) where v k is zero-mean Gaussian noise with variance o-, 2, independent of h k _ 1 [2] [40] [41]. It should be noted that, for the results presented in Section 6.2.1, the fading realizations were generated using the modified Jakes method of [44]. The simulation of correlated Rayleigh variates is an important step in generating meaningful simulations of physical layer effects in wireless communications systems. 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^44 In [44], the authors propose a modified method based on Smith's method [32]. The Rayleigh distributed realization is formed by taking the magnitude of a zero-mean complex Gaussian sequence, the real and imaginary parts of which are i.i.d. N 1.I.D. Zero-Mean {A(k]} Gaussian Variates . Multiply by Filter Sequence {F[k]} N-point Complex Inverse DFT {X [k]} k = 0,1,^, N — 1 N Zero-Mean Gaussian Variates {B[k]} {z[n]} I^I Baseband Rayleigh Fading Sequence n = 0, 1,^,N — 1 Multiply by Filter Sequence {F[k]} Figure 5.2: Rayleigh fading realization simulation block diagram [44] Figure 5.2 outlines the process of generating the realizations. A and B are sequences of Gaussian variates. The authors specify the filter sequence F. This particular implementation is more efficient than Smith's original method. As well it offers superior computational efficiency and accuracy as compared to other well-established methods (i.e. filtering of Gaussian noise, Monte Carlo sum of sinusoids). We also consider a block fading model such as [4] where the fading remains constant over the packet interval. The output of the channel in the discrete time baseband formulation is given by yk = h k xk Wk with yk E y. The instantaneous signal to noise ratio (SNR), -yk, is 1 hk 2 = ^ a2 • w where P is the average transmit power. (5.2) 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^45 The receiver outputs the detected data, a k , and calculates the performance func- tion. The performance function is an empirically measured quantity that reflects the success of transmission. For example, as transmission progresses, an average packet error rate (PER) can be measured. We do not consider packet re-transmission for error correction. The receiver attempts to decode the received packet. The detected data, a k is output. In terms of error detection and correction no restriction is placed on the algorithm used to decode the received data. The specific implementation is left to our grey box modeling and handled by the learning algorithm given that the decoding algorithm meets certain conditions outlined in Section 5.1.3. To enable adaptive transmission the receiver transmits channel state information (CSI) to the transmitter in order to select a new modulation and coding scheme (MCS) via a feedback path. We assume ideal channel estimation and an error free, instantaneous feedback path. The MCS used to encode x k , is selected by the modulation policy Q 0 , which maps the measured channel quality at the receiver to a new modulation and coding scheme, ik E I, at the transmitter. Each ik is associated with a particular rate rk in bits per symbol. rR 00 = 0^01 02^0R-2 r ^ 2-1 eR -I Figure 5.3: Rate region thresholds -y is partitioned into R rate regions, each region is assigned a rate in increasing 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^46 order, r 0 < r 1 < ... < rR_ i , as Figure 5.3. The rate region thresholds are parameterized by 0 E 0 where 0 is the set {111 R-1 such that 0 < 02 < . . . < 0R-11. As the system operates, the transmitter is fedback empirical packet error rate information which is used to update Q o and drive the system to maximum performance. As we have discussed, devices such as SDR could possess the ability to update Q o in real-time [5]. This opens many possibilities for online optimization and control of adaptive modulation processes. 5.1.1 Markovian Dynamical Formulation of Adaptive Modulation Problem With the system model in place we turn our attention to the statistical dynamics of the time evolution of the system. The overall system dynamics are given by Ilk = hkxk + Wk ^ xk = ak 0 Qo EYk-ii^ (5.3) (5.4) In (5.4), '0' denotes the error coding and modulation of the user data ak with the selected modulation scheme ik. 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^47 Proposition 1. The stochastic process {Z k } defined by Yk zk = \ ^hk^ (5.5) Xk y ak / on state space i = {Y x x x X x A} is Markovian with transition kernel p o (zk lzk_ i ) ( ^1^ ,^ ^ exp^tYk — hkxk )2) 27ro-wa-v^2-2 •exp (-- 1 (hk — ahk--0 2 ) 2o-,2 •6 (xk — ak Qo ^(5.6) where 6 denotes the Dirac delta function. Moreover, the Markov process {Zk} is geometrically ergodic with unique invariant distribution 70 Proof. We are interested in the conditional probability of zk given the entire history Zk- 1 , Zk- 2 , . . •, Z0 which is P(Yk, hk, Xk 7 ak^hk_i,^ak_i, • • • , yo , h o , x o ,a o ) = P(ykIhk, xk, ak)P(hkihk-i)P(xklak7 hk-1)P(ak) (5.7) Therefore p(zklzk_ i , z k _ 2 ,... , z o ) = p(zkizk-4) ^ (5.8) Using the fact that lal < 1, v k and w k are finite variance, and that a k is i.i.d., it 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^48 follows from [23] that z k is positively Harris recurrent. Hence, it possesses a unique invariant distribution ire. ^ 1=1 Remark: The above proposition states that the state distribution of zk converges geometrically fast in k to Ire. Geometric ergodicity is required for the stochastic optimization algorithm given in the paper to converge. Given the structure derived, we now model our cost functions as expectations with respect to the unique invariant distribution Ir e with the goal of applying Markov Chain Monte Carlo estimation. 5.1.2 Constrained and Unconstrained Performance Metrics for Adaptive Modulation The goal of adaptive modulation is to find the optimal modulation policy Qe so as to maximize a given performance metric. For this study we are interested in two cases; Problem 1: Optimization of the average throughput, Problem 2: Optimization of average throughput under average packet error constraint. In this study, we consider variable rate, fixed power transmission schemes. It has been shown that the gain achieved in spectral efficiency for joint variable rate/power adaptation is marginal compared to fixed power, variable rate transmission [9]. We show that under some empirical assumptions a unique global optimum exists for the optimization problem. Definition 1. Unconstrained Throughput Optimization. Define the instantaneous throughput as F(zk) = r[zk]( 1 — Pe(zk)) ^ (5.9) 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^49 where r (zk ) and P,(zk )^Pe (-yk) represent instantaneous rate and packet error respectively, as a function of the state vector z. The mean system throughput is R-1 f (9) Ero [F(zk)] =^ 10i+1 (1 — Pe,ri (74(7)d'y (5.10) i=0 where, -y is received SNR with probability distribution p(7)• 00 = 0, B R = oo are fixed with 0, < 0, +1 and r, < r i±i for i = 1, 2 ... R — 1. Pe , r , (-y) represents the packet error rate under transmission rate r, as a function of received SNR Aim: Compute the optimal threshold vector 0* where 9* = arg max f (0)^ Bee (5.11) Remark: Since 0 is compact and f(0) is continuous (see (5.10)) the maximum is well defined. Definition 2. Throughput Optimization with Packet Error Rate Constraint. Denote the instantaneous packet error rate as Pe [k]. The mean PER is given by h(0) = Eiro[Pe(zk)] (5.12) Aim: Compute the optimal threshold vector 0* as the solution for the constrained stochastic optimization problem max f (0) s.t. h(0) — W < 0 (5.13) 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^50 where V) is the target packet error rate. In the constrained case for R possible rates we require 6' E lIZ_FF' due to no transmission below threshold 8 1 . Remark: Problems 1 and 2 are stochastic optimization problems because we do not explicitly know ire. We can only observe F(zk ) and Pe [k] and our aim is to solve the optimization problems of (5.11) and (5.13). 5.1.3 Convexity of Throughput and Quasiconvexity of Error Rate Constraint We begin by making certain assumptions on the structure of the packet error rate functions, Pe , r (y). Al) Pe is an exponentially decreasing function of received SNR -y A2) For a given SNR^< Pe ,,,,, (y) Assumption Al has been studied by [22] as an effective means for approximating packet error rates as a function of channel SNR. In addition, [9, 1] have similar studies for bit error rate. [19] has investigated adaptive modulation properties with general approximating expressions for throughput. A2 and is empirically valid. For example, the approximations to packet error rate curves in used in HIPERLAN/2 system design exhibit this property [22]. For our purposes the specific numerical approximations to the packet error rate curves are not needed, only that the assumptions outlined hold. Proposition 2. The function f (0), defined by (5.10), is locally convex on the feasible set e and h(0), defined by (5.12), is quasi-convex with respect to the control variable 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION 51 Proof. The gradient of f is given by f ae i = —r i (1 — Pe ,„(0,))p(0,) + ri _ i (1 — Pe , r ,_ 1 (0,))p(0,) (5.14) Given assumptions Al and A2 the bounded solution 9* to -(21 ae, = 0 is unique. The gradient of f also attains zero magnitude at the unbounded endpoints. The Hessian matrix of dimension R(R-1) x (R-1) follows as^0 for i j, else a2 f^r aPe , r ,; (00^r aPe,ri_i(ei)]^) ei a 30?^ ^aei aPA)^r (1 — Pe,ri( 0i)) ri-1(1 — Pe,,_,(00)1 (5.15) 00i i a < 0 at 9*. By assumption assumption Al, A2 and the fact that r, > r,_ 1 we have that s Therefore f(9) is locally convex around 9*. We restrict the feasible region to the set O which defines the locally convex region around 9*. For h, consider a two rate transmission scheme for simplicity, h(0) is given by h(0) = Pe,ri (/-1 )/3 (7 < 0) + Pe,r2 ( 1)( 1 PeY < 0)) ^ (5.16) where p is the probability distribution of received SNR 7 with Ep (-y) = ,u. From assumption A2 we see have that Pe,r1 Pe,r2 • Remark Note that f possesses a unique global maximum, however f is not convex on the entire domain O. We must restrict the feasible set to O to ensure convexity of the objective function and therefore strong duality of the primal-dual problem. It is an open research question to determine if the quasi-convex optimization problem can 5.1 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^52 be shown to have strong duality on the entire parameter space O. If so the restriction of defining the locally convex region e can be relaxed. Theorem 1. Given that the objective function, f and constraint function, h, are convex and quasi-convex on the set e respectively, the Lagrange dual formulation max() f (9) + A (h (0) — '0) s. t.^A < 0 (5.17) is convex. Proof Noting that quasi-convex constraint function can always be expressed as equiv- alent convex constraint function [6], the Langrangian G : R 2^R given by L(0, A) = f(0) + )0(0) —^ (5.18) is the linear combination of convex functions and hence convex. ^1=1 Theorem 2 (KKT Conditions). Let the set IC, where {0* E O, 3A* < 0, Ve t' + A*Veh = 0, A*Voit = 0}^(5.19) s define the Karush-Kuhn-Tucker points. Given Theorem 1 and assuming f and h are twice differentiable, the point (0*, A * ) E IC is unique. Moreover, 0* meets the second order sufficient condition f (0*) + A*VP(0*) = 0^(5.20) 5.2 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^53 Proof. This theorem follows directly from the findings of optimization theory, see Boyd [6]. Given that the functions f and h are convex strong duality holds. Suppose A* is a dual optimal solution then any primal optimal point is a maximizer of £(e, A*) (see (5.18)). The maximizer of £(O, Al is unique given the convexity of f and h. Since 0 maximizes G(0, )*), its gradient with respect to 0 disappears at 0*. This implies that the KKT conditions are met, hence necessary and sufficient condition for optimality are met. ^ 5.2 Primal Dual Stochastic Gradient Approximation for Adaptive Modulation Empirical PER Figure 5.4: Effective system model for stochastic learning algorithm We now outline simulation based optimization algorithms for solving 5.17. The learning algorithms work on the effective system diagram of Figure 5.4. As the system operates the performance is measured and fed back to the transmitter. Using 5.2 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^54 this information, stochastic estimates to the gradient of the cost function may be computed based on sample path information. In this section we frame the problem as an iterative stochastic optimization and present stochastic approximation techniques for sample path gradient estimation. For the constrained case, if On, ,,,, tfn and tit, represents estimates of 0, A, Vf n and Vh n respectively at iteration n, we have On +i = On + EnjtOgn ( e n) + 5 ri t O h n O n)} (5.21) An+i = mina., — E n (h.„,(f),„) — V)), 0}^(5.22) where E n is a decreasing step size sequence of the form €/n, where c is a constant greater than zero. 5.2.1 Gradient Estimation and SPSA Algorithm One method to estimate V o L, is to compute a finite difference stochastic approximation (FDSA) [34]. In FDSA, each component of 0 is perturbed individually and the associated objective function measurement for each of the R — 1 new Os is obtained. This is the standard Kiefer-Wolfowitz procedure for gradient approximation. The motivation is the definition of the gradient as a vector of n partial derivatives. The drawback of this approach is that the number of measurements needed to compute an approximation to the gradient grows linearly with the length of 0. Therefore it may be time consuming and inefficient in high dimensional problems. Simultaneous Perturbation Stochastic Approximation [34] (SPSA) is another method 5.2 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^55 for gradient approximation. In SPSA an approximation of V e f(0) can be obtained using only two experimental measurements of f (0), denoted by f(e). f may be empirically measured at the receiver after N packets have been transmitted by (9) [k](1 — Pe [k]) (5.23) where r[k] and Pe [k} represent the instantaneous rate and packet error. h (see (5.12)) may be estimated in a similar fashion. As the system operates empirical PER information is stored and fedback to the transmitter in order to facilitate optimization. The SPSA approach has all components of the vector 0 randomly perturbed simultaneously with a random vector A. The two-sided gradient approximation relies on the measurements f(0, bn A n ). The SPSA gradient estimate is given by _ f (On+bnAn) (en 2bnAn,1 — — bnAn) (5.24) (en±bnAn) — (°n — bnAri) 2bnAn,R^- where A n is a multivariate Bernoulli random vector with each element taking on values {±1} with equal probability. The constants b n and e n are appropriately selected according to [35]. A similar expression holds for t h(theta n ). Apart from finite difference methods there are 3 other methods for gradient estimation; pathwise (IPA), score function or weak derivatives. For a Markovian process score function methods have large variance and are not suitable. The weak derivative approach is a topic of future research. Theorem 3. The primal dual SPSA algorithm (5.21), (5.22) and (5.24) converges 5.2 STOCHASTIC OPTIMIZATION IN ADAPTIVE MODULATION ^56 strongly to the global optimum (0*, )*), i.e. (On) : 7-t) ---4 (9 * , A * ) with probability 1^(5.25) For fixed step size the algorithm will converge weakly to the optimum. Proof. Itefni,Itohni < M are bounded which implies uniform integrability. The gain sequences used in the application of the SPSA algorithm are selected in accordance with [35]. ^ We assume that f(0) is thrice differentiable for all values of 0. Further details about sufficient conditions and proof of convergence can be found in [34]. 5.2.2 System Initialization When applying this algorithm in simulation we we must find the bounds which define the feasible set and select an initial starting point for the simulation. Due to the decoupled nature of the optimal values this reduces to a sent of R individual bound estimates. We perform this as a pre-processing step. We must test the channel at several threshold levels and estimate the boundaries of the locally convex set defined by O of Section 5.1.3. Once this is established we may proceed with the simulation. The pre-processing aids in the selection of an initial state for the threshold vector thus reducing initial settling times. The drawback is that there is a large amount of pre-processing that is required before the algorithm can be run. Chapter 6 Results and Simulation Techniques Through the evolution of the research project our aim was to divide the entire adaptive modulation system into smaller parts and test them successively. With each part adding more and more sophistication. In this way we were able to observe the performance of the algorithms and also implement them in a step by step way. This section outlines the progressive, iterative design of the adaptive modulation system. We present results of testing on progressively more sophisticated system models and communications techniques. The performance and the system is compared to analytical analysis and Monte Carlo simulations. 6.1 Packet Level Simulation To begin our testing of the proposed algorithm we make simplifying assumption on the model of the system to test the effectiveness of the algorithm. The rationale behind this decision was to test the algorithm on a considerably simplified system to see whether to not the proposed algorithm was indeed able to learn optimal transmission 57 6.1 RESULTS AND SIMULATION TECHNIQUES^ 58 policies. We first consider the successful transmission of a packet modeled as a Gilbert Elliot channel model. The Gilbert-Elliot channel models the quality of the channel as a two state Markov chain. The possible channel state are 'good' and 'bad'. For the purposes of simulation, in each of the states the probability of packet error set. As the system operates an average packet error rate may be measured. 6.1.1 Performance Results 1.7 0 E 1.5 1,4 _0 1.3 C 2 1.2 I 10^15^20^25 Iteration 35 40 Figure 6.1: Increase in average throughput for Gilbert-Elliot Channel 6.2 RESULTS AND SIMULATION TECHNIQUES^ 59 1. 8 L7 1.2 10^15^20 Iteration 25 40 Figure 6.2: Increase in average throughput for Gilbert-Elliot Channel FIgures 6.1 and 6.2 show the learning characteristics of the packet level simulation. Given initial values for probability of packet error in good and bad channel conditions as well as channel switching probability re-enforcemtn learning was used to optimize the throughput. Each iteration represents transmission of 200 packets. The results indicate that the approach is feasible. Given that the simplifications made to the system are substantial we see that the algorithm is able to perform adequately and optimize the system. 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 60 6.2 Bit Level Simulation 6.2.1 Simulation results In this section, we present Monte Carlo simulations that were conducted to test the effectiveness of the stochastic learning algorithms in the presence and absence of error correction coding. Our aim is to consider the SDR system model given and apply (5.21), (5.22) and (5.24) to three different situations; uncoded, convolutionally coded and turbo coded transmission. For each scenario we consider unconstrained and average packet error rate constrained transmission. In addition, we investigate the tracking capabilities of the stochastic optimization. For all experiments the channel is modeled as a slowly varying Rayleigh fading channel. The channel is simulated using the modified Jakes method of [44]. For algorithm implementation we assume an ideal SDR where the modulation process is fully controlled in software and that general purpose hardware is available for computation. Full software control of the modulation process will allow wireless devices to adapt spectrum to usage to a wide variety of influences such as user needs, application demands or network demands. 6.2.2 Uncoded Transmission We begin by considering MQAM transmission without error correction coding. Figure 6.3 shows the average throughput performance versus average received SNR. We see the performance of fixed rate transmission schemes (dashed lines) as well as the performance of the adaptive modulation system (solid line). The channel is simulated using the powerful modified Jakes method of [44]. Figure 6.4 shows the average throughput under 1% PER constraint. The dashed 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 61 6 5 0 E 4/2 4 co 3 z 2 _c i-6 1) 2 co 1 0 0 5^10^15^20^25^30^35^40 SNR (dB) Figure 6.3: Average throughput versus SNR for fixed and adaptive modulation policies without coding lines represent the throughput for each of the fixed transmission modes. The dashdotted lines represent the average packet error rate for each transmission mode respectively. The solid line displays the throughput achievable using under a 1% packet error rate constraint. Figure 6.5 shows the tracking ability of the algorithm as the PER constraint is adjusted from 1% to 8% PER. The system is initialized with a heuristically decided initial B point. During the first 40 iterations learns the optimal throughput settings. At iteration 100 the PER constraint is adjusted to 8%. Each iteration represents the ^ 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 62 i^i^I^- —0— - QPSK 1^i^x ^• —0— 16QAM 1^1^1^--x-•64QAM i^1^ ---i--- Adaptive 1^1^1^---- • 1% PER i^i^ i 0 QPSK 16QAM x 64QAM Adaptive 1. .0 i^• I^1, 1 . O 0 cuC.) a. 1 9^ \^ 6 :^ ■ ^\: 1. a) 0) ■^A A^o •^0.... . 0 ^.0.^-6 -^o• o•,. 7 ^Ix , - . 0- • • • o^o E. a) 0.05 > . I.^x^\ I^'^\^\. I o.^ 10^15^20^25 Average SNR (dB) \ ^ 30 ^ 35 0 40 Figure 6.4: Average throughput versus SNR for fixed and adaptive modulation policies with no coding in Rayleigh fading with packet error rate constraint transmission of 500 packets. Analytic Analysis For uncoded transmission it is also possible to formulate a tight approximation for the packet error rate for MQAM transmission. For MQAM modulation an approximation of the symbol error rate (P3 ) as a function of received SNR is [26] 4B r 2 sin 2^4B2^sin2 13,(e) = — ^ d3^(6.1) g,T3°113 ^ sin2 + 91 o^sin2^ 7 JO^ ^ 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 2.5 63 - 0.25 Measured Throughput Optimal Throughput 0 E a) - 0.2 cc 0 — - Measured Error Rate^"ci; a PER Constraint 1%->8% 0.15 a. a) 0 = 0 0) a) - 0.1 j;, ^ I^,^i^. • • 1.1^'./' /^•I/ -11^•I t^11 .1 . /^. 1^ t 1^ 0.5 - 0.05 14 /,,f 1,0. . X .1, '77 rn 0^ 0 0 20^40^60^80^100^120^140^160^180^200 Iteration Figure 6.5: Tracking of adaptive modulation system under 16dB average SNR where PER constraint is adjusted at iteration 100 from 1% to 8% where g = 3/[2(M — 1)], B = 1 — 1/M 1 / 2 and M refers to the MQAM constellation size. The PER may be approximated by Pe,MQAM (7) ^ ^ — S ERMQAM(7))L (6.2) where L denotes the number of symbols per packet and log M denotes the bit per symbol. From this finding and (5.11) we arrive at the analytical solution, 0* = 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 64 [15.8, 22.5]dB. The adaptively trained optimum value was found to be 0* --= [16.0, 23.1]dB. The values are consistent considering the assumptions made in deriving the analytic solution. 6.2.3 Convolutional Coding 16QAM, code rate = 1/2 256QAM, code rate = 1/2 + 256QAM, code rate = 3/4 ^ Adaptive Transmission 0 0^ 0 0 0 0 0^0 0 0 0 ^ 5^10^15^20^25^30^35 Average SNR (dB) ^ 40 Figure 6.6: Average throughput versus SNR for fixed and adaptive modulation policies with convolutional coding in Rayleigh fading We now consider convolutionally encoded transmission. Figure 6.6 shows the average throughput performance versus received SNR for unconstrained optimization. We employ a convolutional code with constraint length 7, generator polyno- 6.2 RESULTS AND SIMULATION TECHNIQUES ^ —0— QPSK 0 QPSK 16QAM 5 65 • —0— 16QAM —x— 64QAM - 0.25 Adaptive — - 1% PER x 64QAM Adaptive 0 .0 a) >, 4 0.2 U) Co 0 .0 +3. ci) 3 0 .c 0.15 -6 n a) cr) T E 2 0.1 a) 10^15^20^25 Average SNR (dB) 30 35 Figure 6.7: Average throughput versus SNR of adaptive modulation learning process under convolutional coding with 10dB average received SNR and constrained PER of 1% mial [133,1711 8 . The transmission modes are; (o) code rate=1/2 16QAM , (o) code rate=1/2 256QAM and (+) code rate=3/4 256QAM. As we see there is strong adherence to the optimal transmission mode in each rate region. Figure 6.7 shows the average throughput performance where the PER is constrained to be 1%. Figure 6.8 shows the tracking capabilities of the learning algorithm as the PER constraint is relaxed. ^ 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 66 Measured Throughput Optimal Throughput 2.5 0 E 0 rn 0 - 1. Measured Error Rate - PER Constraint 154->5% - o or) fE a) i i.^,. ^ it ■ .l.^r " I^• I^ 1^ . T r1 -‘,, 1 , ' 4 i -- ■ 4 / \-t 0.05 ' ' 4 ,i -1" ,11, 1 .^,^..^i^, I i II 0.5 Ili^ i ^1 i I I^ •^.^•^, /^/^i^ ^/ ..,^•^ 0 I^' i^I^`•^i^•^V%^1 ii^l! 50^ Iteration 100 ^0 150 Figure 6.8: Tracking of adaptive modulation system under 16dB average SNR where PER constraint is adjusted at iteration 75 from 1% to 5% 6.2.4 Turbo Coding Similar tests were conducted using Turbo Codes. In [21] the authors outline a technique whereby turbo codes may be used in conjunction with high spectral efficiency modulation constellations such as high order MQAM. Figure 6.9 shows the average throughput performance versus received SNR. We consider turbo codes with constraint length 5 in the constituent convolutional encoders. The transmission modes are; (o) code rate=1/2 16QAM , (o) code rate=1/2 256QAM and (+) code rate=3/4 256QAM. As we see there is strong adherence to 6.2 RESULTS AND SIMULATION TECHNIQUES^ 67 16QAM, code rate=1/2 0 256QAM, code rate=1/2 5 + 256QAM, code rate=1/2 ^ Adaptive Transmission 0 U) 4 0 0 ^0 co 5 5 )3 0 rn 0 0 0^0 0 0 0 0 0 2 a) > 0^ rni 5^10^15^20^25 Average SNR (dB) 30 35 40 Figure 6.9: Average throughput versus SNR for fixed and adaptive modulation policies with turbo coding in Rayleigh fading the optimal transmission mode in each rate region. Figure 6.10 shows the learning properties of the algorithm. 6.2 RESULTS AND SIMULATION TECHNIQUES ^ 68 3.5 0 _o E To 2.5 ,(s) ^fm T = .01 0 f m T = .001 ^ Optimal Throughput 0_ _c rn 0 -c a) o 0 1.5 a) 0.5 I^I^I^I^■^,^■^i^i 10^20^30^40^50^60^70^80^90 Iteration 100 Figure 6.10: Average throughput versus iteration number of adaptive modulation training under turbo coding with 15dB average received SNR Chapter 7 Conclusions and Future Work In this thesis we have presented stochastic optimization algorithms for the design of adaptive modulation. Built upon the flexibility offered by SDR technology, our aim was to develop real-time optimization and tracking algorithms that could be applied independently of modulation constellation or error correction coding used. Adaptive modulation has traditionally been solved as an analytical problem closed form problem where input/output models of system performance have been used to optimize performance. However these approaches have been limited to a class of communications systems that can be algebraically modeled or approximated. This may not be true for classes of communications systems that employ certain error correction codes or desire real-time adaptability. We have applied stochastic optimization algorithms to the design of adaptive modulation systems. The time evolution of the system was modeled by a general state space Markov chain parameterized by the control vector. We proved the recurrence of the Markov chain and the existence of the unique invariant distribution. Perfor- 69 7.0 CONCLUSIONS AND FUTURE WORK^ 70 mance functions were modeled as expectation of the state variable with respect to the invariant distribution. We considered unconstrained and constrained throughput performance metrics. In addition, given some assumptions, the performance metrics were shown to be convex with the constraint function being quasiconvex. To perform the optimization stochastic approximation algorithms were applied to help perform simulation-based optimization. Stochastic estimates of the gradient of the performance functions were used in an iterative optimization algorithm. We proved the convergence of such algorithms as well as present simulation results of the algorithms presented. We were able to show that the stochastic optimization design was able to converge to optimal throughput conditions for various error correction coding schemes employed. Future work is needed to model the interaction of multiple SDR radios in competition and cooperation for resources. In the future vision of Cognitive Radio, radio devices will be able to make their own decisions about spectrum usage. Future research would look at modeling the cross-coupled interactions of multiple devices as they each attempt to optimize throughput while meeting performance constraints and limiting interference effects. Bibliography [1] M.-S. Alouini and A.J. Goldsmith. Adaptive modulation over nakagamifading channels. Kluwer J. Wireless Comms, 13, May 2000. [2] K.E. Baddour and N.C. Beaulieu. Autoregresive models for fading channel simulation. Proc. IEEE Globecom, 2, 2001. [3] C. Bergstrom, S. Chuprun, S. Gifford, and G. Maalouli. Software defined radio (SDR) special military applications. volume 1, pages 383-388. MILCOM 2002, Oct 2002. [4] E. Biglieri, G. Caire, and G. Taricco. Limiting performance of block-fading channels with multiple antennas. IEEE Trans. Information Theory, 47(4), May 2001. [5] V. Bose, R. Hu, and R. Morris. Dynamic physical layers for wireless networks using software radio. volume 4, pages 2045-2048. Acoustics, Speech, and Signal Processing, 2001. Proceedings. (ICASSP '01). 2001 IEEE International Conference on, May 2001. [6] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. 71 72 7.0 BIBLIOGRAPHY^ [7] E. Buracchini. The software radio concept. Communications Magazine, IEEE, 38(9), Sep 2000. [8] Christos G. Cassandras and Stephane Lafortune. Introduction to Discrete Event Systems. Springer, 1999. [9] S. T. Chung and A. J. Goldsmith. Degrees of freedom in adapative modulation: A unified view. IEEE Trans. Comms., 49(9), Sept. 2001. [10] Bruce Fette.^SDR technology implementation for the cognitive radio. http://www.gd-decisionsystems.com/radiosystems/brochurespublications.html, May 2003. [11] M. Frodigh, S. Parkvall, C. Roobol, P. Johansson, and P. Larsson. Futuregeneration wireless networks. IEEE Wireless Communications, 8, Oct 2001. [12] A. J. Goldsmith and S. G. Chua. Variable-rate variable-power MQAM for fading channels. IEEE Trans. Wireless Communications, 45(10), Oct. 1997. [13] A. J. Goldsmith and S. G. Chua. Adaptive coded modulation for fading channels. IEEE Trans. Comms., 46(5), May 1998. [14] S. Haykin. Communications Systems, 4th edition. John Wiley and Sons Inc., 2001. [15] S. Haykin. Cognitive radio: brain-empowered wireless communications. Selected Areas in Communications, IEEE Journal on, 23(2), Feb 2005. [16] C. Heegard and S. B. Wicker. Turbo Coding. Boston: Kluwer Academic Press, 1999. 7.0 BIBLIOGRAPHY^ 73 [17] Joseph Mitola III. Cognitive Radio - An Integrated Agent Architecture for Software Defined Radio. PhD thesis, May 2000. [18] Joseph Mitola III. Cognitive INFOSEC. Microwave Symposium Digest, 2003 IEEE MTT-S International, 2:1051-1054, June 2003. [19] Pierre T. Kabamba, Semyon M. Meerkov, and Choon Yik Tang. Optimal, suboptimal, and adaptive threshold policies for power efficiency of wireless networks. Information Threory, IEEE Trans., 51, Apr 2005. [20] J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function. Ann. Math. Stat., 23:462-466, 1952. [21] S. Le Goff, A. Glavieux, and C. Berrou. Turbo-codes and high spectral efficiency modulation. volume 2, pages 645-649. IEEE International Conference on Communications, May 1994. [22] Q. Liu, S. Zhou, and G. B. Giannakis. Cross-layer combining of adaptive modulation and coding with truncated ARQ over wireless links. IEEE Trans. Wireless Communications, 3, Sept. 2004. [23] S.P. Meyn and R.L. Tweedie. Markov Chains and Stochastic Stability. SpringerVerlag, 1993. [24] Keith E. Nolan, Linda Doyle, Donal O'Mahony, and Philip Mackenzie. Modulation scheme recognition techniques for software radio on a general purpose processor platform. First Joint IEVIEE Symposium on Telecommunications Systems Research, Nov 2001. 7.0 BIBLIOGRAPHY^ 74 [25] Keith E. Nolan, Linda Doyle, Donal O'Mahony, and Philip Mackenzie. Signal space based adaptive modulation for software radio. IEEE Wireless Communications and Networking Conference WCNC, March 2002. [26] M.S. Patterh, T.S. Kamal, and B.S. Sohi. Performance of coherent square mqam in wireless frequency non-selective slowly fading channels. volume 2, pages 1358-1360. Communication Technology Proceedings, 2000. WCC - ICCT 2000. International Conference on, Aug 2000. [27] J. Proakis. Digital Communication, 3rd ed. McGraw-Hill, 1995. [28] T. Rappaport. Wireless Communications: Principles and Practice, 2nd ed. Wiley, 1991. [29] H. Robbins and S. Munro. A stochastic approximation method. Ann. Math. Stat, 2:400-407, 1951. [30] C.P. Robert and G. Casella. Monte Carlo Statistical Methods (second edition). New York: Springer-Verlag, 2004. [31] C. B. Schlegel and L. C. Perez. Trellis and Turbo Coding. Wiley-Interscience, IEEE Press, 2004. [32] J. I. Smith. A computer generated multipath fading simulation for mobile radio. IEEE Trans. Veh. Technol., VT24:39-40, Aug 1975. [33] J. C. Spall. Implementation of the simultaneous perturbation algorithm for stochastic optimization. Aerospace and Electronic Systems, IEEE Transactions on, 34(3), July 1998. 7.0 BIBLIOGRAPHY^ 75 [34] J. C. Spa11. Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control. Wiley-Interscience, 2003. [35] J.C. Spall. Adaptive stochastic approximation by the simultaneous perturbation method. Automatic Control, IEEE Transactions on, 45(10), Oct. 2000. [36] C Tang. An intelligent learning scheme for adaptive modulation. Vehicular Technology Conference, 2001. VTC 2001 Fall. IEEE VTS 54th, 1:144-148, 2001. [37] C Tang. Performance of adaptive learning schemes for adaptive modulation. Wireless Personal Multimedia Communications, 2002. The 5th International Symposium on, 3, Oct 2002. [38] C Tang and V. Stolpman. An adaptive learning approach to adaptive OFDM. IEEE Wireless Communications and Networking Conference, 2004, 3, Mar. 2004. [39] Frank M. Torre. Speakeasy-a new direction in tactical communications for the 21st century. volume 1, pages 139-142. Tactical Communications Conference, 1992. Vol. 1 Tactical Communications: 'Technology in Transition'., Proceedings of the, Apr 1992. [40] H.S. Wang and P.0 Chang. On verifying the first-order markovian assumption for a rayleigh fading channel miodel. IEEE Transactions on Vehicular Technology, 45, May 1996. [41] H.S. Wang and N. Moayeri. Finite-state markov channel - a useful model for radio communication channels. IEEE Transactions on Vehicular Technology, 44(1), Feb 1995. 7.0 BIBLIOGRAPHY^ 76 [42] S. B. Wicker. Error Control Systems for Digital Communication and Storage. Englewood Cliffs: Prentice Hall, 1995. [43] J. Yang, N. Tin, and A.K. Khandani. Adaptive modulation and coding in 3g wireless systems. volume 1, pages 544-548. Vehicular Technology Conference, 2002. Proceedings. VTC 2002, Sept 2002. [44] D. Young and N. C. Beaulieu. The generation of correlated rayleigh random variates by inverse discrete fourier transform. IEEE Transactions on Communications, 48, July 2000.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Stochastic optimization algorithms for adaptive modulation...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Stochastic optimization algorithms for adaptive modulation in software defined radio Misra, Anup 2007
pdf
Page Metadata
Item Metadata
Title | Stochastic optimization algorithms for adaptive modulation in software defined radio |
Creator |
Misra, Anup |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | Adaptive modulation has been actively researched as a means to increase spectral efficiency of wireless communications systems. In general, analytic closed form models have been derived for the performance of the communications system as a function of the control parameters. However, in systems where general error correction coding is employed, it may be difficult to derive closed form performance functions of the communications systems. In addition, in closed form optimization, real time adaptation is not possible. Systems designed with deterministic state optimization are developed offline for a certain set of parameters and hardwired into mobile devices. In this thesis we present stochastic learning algorithms for adaptive modulation design. The algorithms presented allow for adaptive modulation system design in-dependent of error correction coding and modulation constellation requirements. In real time, the performance of the system is measured and stochastic approximation techniques are used to learn the optimal transmission parameters of the system. The technique is applied to Software Defined Radio (SDR) platforms, an emerging wireless technology which is currently being researched as a means of designing intelligent communications devices. The fundamental property that sets SDR apart from traditional radios is that the communications parameters are controlled in software, allowing for real-time control of physical layer communications. Our treatment begins by modeling the time evolution of the adaptive modulation process as a general state space Markov chain. We show the existence and uniqueness of the invariant measure and model performance functions as expectations with respect to the invariant measure. We consider constrained and unconstrained throughput optimization. We show that the cost functions considered are convex. Next we present stochastic approximation algorithms that are used to estimate the gradient of the cost function given only noisy estimates. We conclude by presenting simulation results obtained by the presented method. The learning based method is able to achieve the maximum throughput as dictated by exhaustive Monte Carlo simulation of the communications system, which provide an upper bound on performance. In addition, the learning algorithm is able to optimize communications under various error correction schemes. The tracking abilities of the algorithm are also demonstrated. We see that the proposed method is able to track optimal throughput settings as constraints are changed in time. |
Extent | 3183869 bytes |
Subject |
adaptive modulation efficiency software defined radio stochastic |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-02-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0066287 |
URI | http://hdl.handle.net/2429/429 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2008-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2008_spring_misra_anup.pdf [ 3.04MB ]
- Metadata
- JSON: 24-1.0066287.json
- JSON-LD: 24-1.0066287-ld.json
- RDF/XML (Pretty): 24-1.0066287-rdf.xml
- RDF/JSON: 24-1.0066287-rdf.json
- Turtle: 24-1.0066287-turtle.txt
- N-Triples: 24-1.0066287-rdf-ntriples.txt
- Original Record: 24-1.0066287-source.json
- Full Text
- 24-1.0066287-fulltext.txt
- Citation
- 24-1.0066287.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0066287/manifest