Selective Subcarrier Pairing and Power Allocation for Decode-and-Forward OFDM Relay Systems with Perfect and Partial CSI by Hamidreza Boostanimehr B.Sc., Sharif University of Technology, Tehran, Iran, 2008 A THESIS SUBMITTED IN PARTIAL FULFILLMENT 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 (Vancouver) August 2010 c Hamidreza Boostanimehr 2010 Abstract This thesis investigates a decode-and-forward two-hop relaying system consisting of one source, one relay and one destination, in which orthogonal frequency division multiplexing is used. The relay forwards the message received from the source on a subset of available subcarriers in the second time slot. Firstly, a subcarrier pairing and selection algorithm is proposed, assuming that perfect channel state information (CSI) is available at all nodes, then, power is allocated to both the source and relay stations under individual power constraints in order to maximize the capacity. Secondly, subcarrier selection and pairing, and power allocation (PA) under partial CSI assumption along with individual power constraints are addressed. The result is a novel distributed algorithm with low complexity maximizing the expected value of capacity at the source and relay nodes. Finally, the simulation results show that selective relaying combined with subcarrier pairing and PA improves the system capacity to a considerable extent in both perfect and partial CSI cases. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . ix Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . x Dedication xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Statement of Co-Authorship . . . . . . . . . . . . . . . . . . . . . xii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Fundamental Relaying Methods . . . . . . . . . . . . . . . . . 3 1.2 Resource Allocation in Cooperative Communication . . . . . 4 1.2.1 Resource Allocation with Perfect CSI . . . . . . . . . 5 1.2.2 Resource Allocation with Partial CSI . . . . . . . . . . 6 iii Table of Contents 1.3 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Related Publications . . . . . . . . . . . . . . . . . . . . . . . 9 2 System Model and Problem Formulation . . . . . . . . . . . 11 2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Problem Formulation: Perfect CSI . . . . . . . . . . . . . . . 13 2.3 Problem Formulation: Partial CSI . . . . . . . . . . . . . . . 14 3 Perfect CSI: Capacity Maximization . . . . . . . . . . . . . . 19 3.1 Subcarrier Selection and Pairing . . . . . . . . . . . . . . . . 20 3.2 Power Allocation . . . . . . . . . . . . . . . . . . . . . . . . . 22 4 Partial CSI: Expected Value of Capacity Maximization 5 Numerical Results . . 27 . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.1 Convergence Results . . . . . . . . . . . . . . . . . . . . . . . 37 5.2 Subcarrier Pairing and Selection Performance . . . . . . . . . 42 5.3 Power Allocation Performance 6 Conclusions and Future Work . . . . . . . . . . . . . . . . . 45 . . . . . . . . . . . . . . . . . . 50 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 iv Table of Contents Appendices A Convexity of C¯1 and C¯2 . . . . . . . . . . . . . . . . . . . . . . 57 B L-superadditivity of C¯2 . . . . . . . . . . . . . . . . . . . . . . . 58 v List of Tables 5.1 Relaying subcarriers ratio (Perfect CSI) . . . . . . . . . . . . . 37 5.2 Relaying Subcarriers Ratio (Partial CSI) . . . . . . . . . . . . 37 vi List of Figures 1.1 A simplified cooperation model. . . . . . . . . . . . . . . . . . 3 2.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.1 Convergence of the PA technique, perfect CSI . . . . . . . . . 38 5.2 Convergence of the source optimization problem, partial CSI . 40 5.3 Convergence of the relay optimization problem, partial CSI . . 41 5.4 Performance of the subcarrier pairing and selection processes, perfect CSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.5 Performance of the subcarrier pairing and selection processes, partial CSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.6 Performance of the PA scheme for equal power budgets, perfect CSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.7 Performance of the PA scheme for equal power budgets, partial CSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.8 Performance of the PA scheme for reduced relay power budget, perfect CSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 vii List of Figures 5.9 Performance of PA scheme for reduced relay power budget, partial CSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 viii List of Abbreviations AF Amplify-and-forward CSI Channel state information DF Decode-and-forward FDMA Frequency division multiple access KKT Karush-Kuhn-Tucker MIMO Multiple input multiple output MRC Maximum ratio combining OFDM Orthogonal frequency division multiplexing PA Power allocation PDF Probability distribution unction RV Random variable SNR Signal to noise ratio SQP Sequential quadratic programming TDMA Time division multiple access ix Acknowledgements First and foremost, I would like to thank my supervisor, Prof. Vijay K. Bhargava, for the guidance and support that he has provided. This thesis would not have been possible without his suggestions, advice and constant encouragement. Furthermore, I would like to extend my utmost gratitude to my lab mates for creating a friendly environment, in which I could carry out my research project. Finally, heartfelt and deep thanks go to my family, who have always encouraged me and given their unconditional support throughout my studies at the University of British Columbia. Without their support, I could not have completed this thesis. x Dedication To my parents... xi Statement of Co-Authorship Dr. F. Gagnon and Mr. O. Duval has co-authored the paper entitled ”Selective Subcarrier Pairing and Power Allocation for Decode-and-Forward OFDM Relay Systems”. Mr. Duval and I identified the research problem, and I formulated it in consultation with my graduate supervisor Prof. Vijay K. Bhargava. I, myself, performed all mathematical derivations. Mr. Duval and Dr. Gagnon checked the mathematical derivations. Computer simulations and analysis of the results were totally carried out by me. Mr. Duval helped me in organizing and writing the paper. xii Chapter 1 Introduction During the last few years, wireless communication has become a ubiquitous technology in our daily lives. Voice communication is not the basic concern anymore, and demand for higher data rates is growing every day. High data rate applications such as wireless broadband Internet, online gaming, video streaming and many other applications have come to view recently. Considering the well-known impairments in wireless channels, fulfilling the required data rates for applications mentioned above is only possible by the deployment of multiple input multiple output (MIMO) techniques. However, installing multiple antennas at transmitters and/or receivers results in infeasible size expansion of the devices, which is not practical in many wireless applications. Examples of such applications are wireless sensor networks and ad-hoc networks. Cooperative communication has been introduced as a new communication paradigm to achieve MIMO gains without introducing large devices because of installing multiple antennas. In contrast with traditional point-topoint communication, in cooperative networks, individual users cooperate with each other by relaying all or part of each other’s messages to a receiver. 1 Chapter 1. Introduction In other words, a virtual multiple antenna system is created by taking advantage of antennas belonging to different users. On the other hand, eliminating the need for installing multiple antennas significantly reduces the cost and complexity of the system. From a historical point of view, cooperative communication was introduced by Van Der Meulen in [1], and later was improved in [2] by Cover and El Gamal, where the information theoretic properties of the relay channel are examined. The latter addressed the capacity of a three-node network consisting of a source, a relay, and a destination. Many ideas that appeared later in the literature on cooperative communication were first initialized in [2]. Then, the idea of cooperation was abandoned until the practical issues of wireless cooperation were solved. However, cooperative communication recently has attracted a considerable amount of research attention due to its promising potential to enhance the performance of wireless communication systems [3, 4]. Nowadays, relayed transmission techniques are being used to improve coverage, enhance capacity and combat shadowing in wireless communication networks, such as cellular or mesh networks [5]. Cooperative techniques also exploit cooperative diversity by means of providing several copies of a signal that have experienced independent channel gains [6], [7]. Furthermore, early research in cooperative communication has shown that energy efficient transmitters operating in relay networks help extending battery life [8]. 2 1.1. Fundamental Relaying Methods 1.1 Fundamental Relaying Methods To clarify the main concepts, consider the example wireless network in Fig. 1.1, which is composed of three terminals: source, relay and destination. In this cooperative network, two orthogonal phases are considered, either in time division multiple access (TDMA) or frequency division multiple access (FDMA), in order to avoid interference [9]: • In phase 1, the source transmits its message, and due to the broadcast nature of the wireless channels, both the relay and source receive the message. • In phase 2, the relay retransmits or forwards the whole or part of the message sent by the source to the destination. Figure 1.1: A simplified cooperation model. Two fundamental relaying methods have been defined in [6]: amplifyand-forward (AF), and decode-and-forward (DF). In AF mode, during the phase 2, the relay retransmits an amplified version of the transmitted signal without reading its content. As a result, the relay amplifies it own receiver 3 1.2. Resource Allocation in Cooperative Communication noise, too. Then, the receiver combines the signals received from both the source and relay (e.g., using maximum ratio combining (MRC)), and decodes the original message. On the other hand, in DF mode, the relay reads the message completely, re-encodes a new one and transmits it to the destination. Decoding at the relay may occur in different forms. For instance, the relay may fully decode the incoming message and re-encodes a new one, or may decode the message in symbol-by-symbol fashion knowing that the destination performs the full decoding. These choices enable the trade off between performance and complexity at the relay terminal [6]. In this thesis, only DF relaying systems are addressed. 1.2 Resource Allocation in Cooperative Communication Like all wireless systems, resources such as bandwidth, time and power are valuable and should therefore be allocated optimally in cooperative systems. In recent years, several researchers have studied cooperative communication optimization problems where a centralized control unit with perfect knowledge of channel state information (CSI) allocates power to the source and relay in order to fulfill an objective under a certain set of constraints. Meanwhile, some researchers were interested in solving resource allocation problems assuming partial CSI, in which some statistical knowledge of channel 4 1.2. Resource Allocation in Cooperative Communication gains, e.g., mean value of channel power gains is available. This scenario is more practical considering the extensive feedback needed to inform all the nodes of all channel gains. In the following two sections, necessary definitions and related works in terms of resource allocation problems considering both perfect and partial CSI cases are reviewed. 1.2.1 Resource Allocation with Perfect CSI Several researchers were interested in aggregate capacity maximization objectives under sum power constraints, in which the source and relay share a certain power budget [10–13]. In this class of problems, power is distributed between the source and relay such that the instantaneous bit rate between the source and destination is maximized. Outage probability minimization objectives relied on similar sum power constraints have also been addressed in the literature [14, 15]. In other words, first the probability that the instantaneous bit rate drops below a pre-determined threshold is calculated, then the optimization problem is formulated in order to minimize the probability of this event. Sum power constraints make the resource allocation optimization problems more tractable and easier to solve mathematically. However, individual power constraints represent practical systems more accurately, because geographically separated nodes have independent power sources. Current research [16–18] has considered individual power constraints for capacity maximization problems. 5 1.2. Resource Allocation in Cooperative Communication Another dimension of the problem is frequency selective fading channels: early power allocation (PA) problems [14, 15] considered flat fading channels for AF [10] and DF [11] relaying schemes. Frequency selective channels under orthogonal frequency division multiplexing (OFDM) modulation, which consider constant channel gains in narrow subcarriers, have been studied in [12–14, 16–18]. In cooperative PA for OFDM modulated transmitters, many researchers decide to relay on all subcarriers [12, 13], but it may occur that either the source-relay or the relay-destination wireless subchannel is in a deep fade. In these situations, it is reasonable to relay only on some subcarriers and directly transmit on the rest. This selective relaying strategy offers better capacity performance in general [16–18]. Moreover, the relay, that received a message on a particular subcarrier, has an opportunity to forward the re-encoded message on a different subcarrier. This subcarrier pairing technique improves capacity in systems under sum power constraints [11, 12], but is only mentioned as a potential benefit for individual power constrained problems [16]. 1.2.2 Resource Allocation with Partial CSI As mentioned earlier in this chapter, assuming that either the source or the relay does not have access to all the channel gain information eliminates the need for extensive feedback and heavy signalling overhead, which in turn reduces the system complexity and cost. However, due to the absence of some information during the resource allocation process, performance of these 6 1.2. Resource Allocation in Cooperative Communication systems are worse than systems in which perfect CSI is available. Therefore, there exists a trade off between the performance and complexity. Similar to the perfect CSI case, resource allocation with partial CSI is viewed through different angles in the literature. In [11], first the expected value of the signal-to-noise ratio (SNR) from viewpoint of the source is calculated, assuming that the relay-destination channel has Rayleigh probability distribution function (PDF). Then, the source distributes the power such that this expected value of SNR is maximized. Another approach for PA based on symbol error rate analysis is proposed in [19] for DF relaying systems. Optimal PA assuming partial CSI has been obtained in [14], [20] and [21] to minimize the outage probability. The authors in [22] assumed that fading distribution and path loss information is available across all the nodes and proposed a PA scheme to minimize high SNR approximations of outage probability. However, all the references mentioned in this paragraph considered sum power constraint, which is not as realistic as individual power constraints. In [23] a distributed game-theoretical framework over multiuser cooperative communication networks is proposed to achieve optimal relay selection and PA without knowledge of CSI. 7 1.3. Thesis Contributions 1.3 Thesis Contributions In this thesis, a two-hop DF relaying system consisting of one source, one relay and one destination operating under OFDM modulation is considered. The channel is assumed to suffer from Rayleigh fading. We investigate PA with selective subcarrier pairing in an optimal manner, and individual power constraints at the source and relay transmitters. Two different scenarios are considered, maximizing aggregate capacity assuming perfect CSI, and maximizing expected value of capacity assuming partial CSI: • Maximizing Capacity with Perfect CSI: In this scenario, first the subcarrier pairing and selection problem is solved using a unified solution based on Hungarian method. Then, the PA optimization problem is formulated in a standard convex programming format. Finally, the power is allocated using convex optimization techniques. Our contribution in this scenario is proposing a semi-distributed algorithm, and a general improvement of capacity performance under more realistic power constraints when compared to recent work. • Maximizing the Expected Value of Capacity assuming Partial CSI: In Partial CSI case, first the expressions for expected values of capacity at both the source and relay are calculated. Then, based on the obtained expressions, a fully distributed algorithm is proposed to cover the subcarrier selection, subcarrier pairing, and PA to the both transmitters. Our contribution regarding the partial CSI case is formulating 8 1.4. Thesis Organization the problem in a more realistic way and proposing a novel, practical, distributed and with low complexity solution. 1.4 Thesis Organization The rest of the thesis is organized as follows. In Chapter 2, the system model is defined, and the optimization problems considering perfect and partial CSI are formulated. The optimal subcarrier pairing, subcarrier selection and PA for the perfect CSI case is proposed In Chapter 3 to maximize capacity under individual power constraints. In Chapter 4, building upon the solutions obtained in the previous chapter, the partial CSI case is treated, where the expected value of capacity is maximized by optimally selecting and pairing the relaying subcarriers, and allocating power to the source and relay. Simulation results, which depict the excellence of our proposed schemes, are presented in Chapter 5. Finally, Chapter 6 concludes the thesis and presents possible directions for future work. 1.5 Related Publications • H. Boostanimehr, O. Duval, V. K. Bhargava, F. Gagnon: Selective Subcarrier Pairing and Power Allocation for Decode-and-Forward OFDM Relay Systems. In Proceedings of IEEE ICC, pages 1-5, May 2010. • H. Boostanimehr, V. K. Bhargava, Selective Subcarrier Pairing and 9 1.5. Related Publications Power Allocation for DF OFDM Relay Systems with Perfect and Partial CSI. Submitted to IEEE Transactions on Wireless Communications. 10 Chapter 2 System Model and Problem Formulation 2.1 System Model In a wireless OFDM network operating on frequency selective channels, a source wishes to send data to a destination, using the assistance of a relay, as shown in Fig. 2.1. The channel’s bandwidth is divided into N = NF F T subcarriers, and a transmission period lasts for two time slots. We define the power gain of the ith subcarrier’s channel between the source and destination as ci = |hsd,i |2 /σd2 , the source and relay as ai = |hsr,i |2 /σr2 , and the relay and destination as bi = |hrd,i |2 /σd2 , where hi s are channel gains, and σr2 and σd2 are noise variances at the relay and destination, respectively. We assume these channel gains do not vary during a period of two time slots. In the first time slot, data is broadcasted by the source to the relay and (1) destination on all subcarriers, with power pS . In the second time slot, on the M subcarriers that have been selected for relaying, the relay decodes, permutes and retransmits data with power pR . On the remaining N-M sub11 2.1. System Model Source Relay Destination R t 1,2 p(1) S R t N-1,1 pR M tR N,N N N-M p(2) S T NR Figure 2.1: System model (2) carriers, the source transmits new data with power pS . Therefore, the relay might use a different subcarrier than the one used by the source for a given message. We define an NF F T × NF F T relay pairing matrix as TR with elements tR i,j . The permutations occur from subcarrier i in the 1st time slot to subcarrier j in the 2nd time slot if they are paired, which is denoted by element tR i,j = 1. Similarly, the non-relay pairing NF F T × NF F T matrix TN R has elements R tN i,j = 1, if the subcarrier j is used to transmit a new message from the NR source. All other elements tR i,j = 0 and ti,j = 0. Then, after a two time slot period, the destination exploits maximum ratio combining to retrieve the relayed messages. Now, we formulate the optimization problem for two different cases: A. perfect CSI. B. partial CSI. 12 2.2. Problem Formulation: Perfect CSI 2.2 Problem Formulation: Perfect CSI The capacity on the relaying pairs and non-relaying pairs under perfect CSI assumption will be [6]: 1 (1) (1) min log(1 + ai pS,i ), log(1 + ci pS,i + bj pR,j ) , 2 1 1 (1) (2) CN R (i, j) = log(1 + ci pS,i ) + log(1 + cj pS,j ). 2 2 CR (i, j) = (2.1) (2.2) Our objective is to solve the following optimization problem which involves joint optimization of subcarrier pairing, subcarrier selection, allocating power to the source in the 1st time slot, and allocating power to the relay and source in the 2nd time slot: NF F T NF F T minimize NR {tR i,j · CR (i, j) + ti,j · CN R (i, j)} (2.3) − (2) (1) pS , pS , pR , TR , TN R i=1 j=1 NF F T NR (tR i,j + ti,j ) = 1, ∀j ∈ {1, 2, . . . , NF F T }, subject to (s.t.) i=1 (2.4) NF F T NR (tR i,j + ti,j ) = 1, ∀i ∈ {1, 2, . . . , NF F T }, (2.5) j=1 NR tR i,j , ti,j ∈ {0, 1}, ∀i, j ∈ {1, 2, . . . , NF F T }, (1) (2) pS , pS , pR (1) 0, (2.6) (2.7) (2) 1T pS = PS , 1T pS = PS , 1T pR = PR . (2.8) 13 2.3. Problem Formulation: Partial CSI In the above problem, constraint (2.4), (2.5) and (2.6) guarantee that a given subcarrier in the 2nd time slot can only be used for relaying or direct transmission, and each subcarrier in the 2nd time slot is only matched with one subcarrier in the 1st time slot. Constraint (2.7) guarantees that powers are greater than zero, and finally, constraint (2.8) is individual power constraints for each node in each time slot. This problem is covered in Chapter 3. 2.3 Problem Formulation: Partial CSI In perfect CSI case, all the nodes need to know all the instantaneous channel gains which leads to a centralized solution involving a great amount of feedback and increasing the complexity of the system. However, it is realistic to assume that the source can obtain source-relay and source-destination channel gains through channel estimation techniques, while, the relay-destination channel information is a random variable (RV) to the source with a known PDF [11]. Likewise, the relay can obtain source-relay and relay-destination channel gains, while, source-destination channel information is an RV with a known PDF. If we denote the SNR of ith source-relay subcarrier in the 1st time slot by (1) Γai = ai .pS,i , relay-destination subcarrier in the 2nd time slot by Γbi = bi .pR,i , (1) source-destination subcarrier in the 1st time slot by Γ(1) ci = ci .pS,i , and source(2) destination subcarrier in the 2nd time slot by Γ(2) ci = ci .pS,i , then the source can maximize the expected value of capacity assuming Γbi s as exponentially 14 2.3. Problem Formulation: Partial CSI distributed RVs with mean value of Ωrdi = b¯i .pR,i , because, the channel gains were assumed to be Rayleigh distributed RVs [24]. Likewise, the relay maximizes the expected value of capacity treating Γ(1) ci s as exponentially (1) distributed RVs with mean value of Ωsdi = c¯i .pS,i . Expected value of the relaying capacity is formulated as follows: 1 C¯1 (i, j) = EΓbj log 1 + min{Γai , Γ(1) ci + Γ b j } 2 1 C¯2 (i, j) = EΓ(1) log 1 + min{Γai , Γ(1) ci + Γ b j } 2 ci , (2.9) , (2.10) where EX [·] denotes the expected value with respect to X, and indices 1 and 2 correspond to the source’s and relay’s point of views, respectively. To obtain the above expected value, we define two new RVs: X1 (i, j) = min Γai , Γ(1) ci + Γbj , where Γbj is an RV, (2.11) (1) X2 (i, j) = min Γai , Γ(1) ci + Γbj , where Γci is an RV. (2.12) The PDF of X1 has been obtained in [11] as follows: 1 − fX1 (i,j) (x) = e Ωrdj (1) x−Γc i Ωrd j U (x − Γ(1) ci ) − U (x − Γai ) +e − (1) Γai −Γc i Ωrd j δ(x − Γai ), (2.13) where U (·) is the unit step function and δ(·) is the unit impulse function. 15 2.3. Problem Formulation: Partial CSI Similarly, the PDF of X2 is calculated as: 1 − fX2 (i,j) (x) = e Ωsdi x−Γb j Ωsd i U (x − Γbj ) − U (x − Γai ) − +e Γai −Γb j Ωsd i δ(x − Γai ). (2.14) Then, according to the definition of expected value, C¯1 (i, j) = x)fX1 (i,j) (x)dx and C¯2 (i, j) = 1 2 1 2 log(1 + log(1 + x)fX2 (i,j) (x)dx which are calculated in the following: (1) 1 g1 (pS,i ) C¯1 (i, j) = 2 log(1 + ci p(1) S,i ) , ci ≤ ai (2.15) , ci > ai , (1) , bj pR,j ≤ ai pS,i 1 g2 (pR,j ) C¯2 (i, j) = (1) 2 log(1 + ai p(1) S,i ) , bj pR,j > ai pS,i , (2.16) where, (1) (1) g1 (pS,i ) (1) (1) 1 + ci pS,i 1 + ai pS,i 1 + ci pS,i = exp( ¯ ) Ei(− ¯ ) − Ei(− ¯ ) bpR,j bpR,j bpR,j (1) + log(1 + ci pS,i ), (2.17) 16 2.3. Problem Formulation: Partial CSI (1) 1 + ai pS,i 1 + bj pR,j 1 + bj pR,j ) Ei(− ) − Ei(− ) g2 (pR,j ) = exp( (1) (1) (1) c¯pS,i c¯pS,i c¯pS,i + log(1 + bj pR,j ), (2.18) in which Ei(·) is the exponential integral and defined as Ei(x) = exp(t) x dt −∞ t [25]. Now we formulate the problem at both the source and relay for the purpose of finding the best subcarrier selection, subcarrier pairing and powers such that the expected value of capacity is maximized in a distributed fashion. The source encounters the following problem: NF F T NF F T minimize (1) (2) pS , pS , TR , TN R s.t. − i=1 NR ¯ {tR i,j · C1 (i, j) + ti,j · CN R (i, j)} (2.19) j=1 (2.4), (2.5), (2.6), (1) (2) pS , pS , (1) 0, (2.20) (2) 1T pS = PS , 1T pS = PS , (2.21) 17 2.3. Problem Formulation: Partial CSI and, the relay has to solve the following: minimize R pR , T , T NF F T NF F T − NR s.t. i=1 ¯ {tR i,j · C2 (i, j)} (2.22) j=1 (2.4), (2.5), (2.6), pR 0, 1T pR (2.23) PR , (1) bj pR,j < ai pS,i , ∀(i, j) ∈ {(i, j)|tR i,j = 1}, (2.24) (2.25) where the constraint (2.25) is added at the relay, because, according to (2.16), C¯2 (i, j) is not defined otherwise. And, power constraint 1T pR = PR is changed to 1T pR PR , due to the existence of cases in which not all the power budget at the relay needs to be used. Inspecting two above problems suggests that they are highly coupled through TR and TN R , as they appear in both optimization problems. This will avoid designing a distributed algorithm. To overcome this drawback, further manipulations are needed which will be discussed in Chapter 4. 18 Chapter 3 Perfect CSI: Capacity Maximization In this chapter we intend to solve the following problem as derived in Section 2.2: NF F T NF F T minimize (1) NR {tR i,j · CR (i, j) + ti,j · CN R (i, j)} (3.1) − (2) pS , pS , pR , TR , TN R i=1 j=1 NF F T NR (tR i,j + ti,j ) = 1, ∀j ∈ {1, 2, . . . , NF F T }, s.t. i=1 NF F T NR (tR i,j + ti,j ) = 1, ∀i ∈ {1, 2, . . . , NF F T }, j=1 NR tR i,j , ti,j ∈ {0, 1}, ∀i, j ∈ {1, 2, . . . , NF F T }, (1) (2) pS , pS , pR (1) 0, (2) 1T pS = PS , 1T pS = PS , 1T pR = PR , which is divided into two parts, the second one being PA, but we first discuss subcarrier pairing and selection in the Section 3.1. 19 3.1. Subcarrier Selection and Pairing 3.1 Subcarrier Selection and Pairing The subcarrier pairing and selection is equivalent to determining the optimal TR and TN R matrices, which is an integer programming problem that often proves to be unsolvable or very complex in practical applications. In this paper, an algorithm based on Hungarian method is proposed in order to treat this issue. Subcarrier pairing algorithms are investigated in [12], [13] where the proposed solutions are based on ordering the subcarrier gains: the best sourcerelay gain is paired with the best relay-destination. For instance, [12] orders source-relay subcarriers according to ai − ci and relay-destination subcarriers according to bj . These subcarrier pairing algorithms are optimal when subcarrier selection is not available, i.e., when relaying occurs on all the subcarriers. This fact can be verified by a simple counter example. In terms of subcarrier selection, [11] and [12] introduced a straightforward algorithm for DF relaying systems for which a particular pair is used for relaying if ai , bj > ci . Otherwise, the direct link offers a better capacity. However, this algorithm is based upon a sum power constraint; and as discussed earlier, individual power constraints are more realistic to depict practical applications. To overcome the two shortcomings mentioned above, we present a unified algorithm based on the Hungarian method to deal with the subcarrier pairing 20 3.1. Subcarrier Selection and Pairing and selection problems jointly. First we define the following matrices: D(i, j) = F(i, j) = CR (i, j) , CR (i, j) > CN R (i, j) (3.2) CN R (i, j) , otherwise, 1 , CR (i, j) > CN R (i, j) (3.3) −1 , otherwise. Here, D is an NF F T × NF F T matrix. The element (i, j) of this matrix is CR (i, j), if cooperation on the subcarrier pair (i, j) offers a better capacity than direct transmission on the same subcarrier pair. Otherwise, the direct capacity is nominated for D(i, j). Additionally, Matrix F is a flag matrix which manifests which elements of D are obtained from cooperation, and which ones from direct transmission. The integer programming problem is then reduced to an assignment problem [26] on D. In other words, NF F T elements of D must be selected such that, first of all, only one element from each row and column is selected, and secondly, the summation of the selected elements is maximized. This procedure can be efficiently solved by applying the Hungarian method [27] on D, which gives T = TR + TN R . Then, the TR and TN R matrices can easily be extracted from matrix T using the pre-calculated flag matrix F. The subcarrier pairing and selection method described above has a useful property that will be used in Section 3.2: Proposition 1: A pair (i, j) selected for relaying has ai > ci . 21 3.2. Power Allocation Proof : If a pair (i, j) is selected by Hungarian, it immediately follows that CR (i, j) ≥ CN R (i, j). Therefore: 1 (1) (1) log 1 + min ai pS,i , ci pS,i + bj pR,j > 2 1 1 (1) (2) log 1 + ci pS,i + log 1 + cj pS,j . (3.4) 2 2 The second term in the right hand side in (3.4) is always positive, and does not affect the inequality. And, if the inequality holds, it means that it is held for both terms in the min function. So, we have 1 2 1 2 (1) log 1 + ai pS,i > (1) log 1 + ci pS,i and it suggests ai > ci . After subcarrier pairing and selection, the second part of the problem defined in Section 2.2 is PA. 3.2 Power Allocation Once the subcarrier pairing and selection problem is solved using techniques developed in Section 3.1, we use the resulting TR and TN R matrices to define two sets of (i, j) index pairs as follows: (2) (3.5) (2) (3.6) SR = {(i, j)|tR i,j = 1} : {(i, j)|pR,j ≥ 0, pS,j = 0}, R SN R = {(i, j)|tN i,j = 1} : {(i, j)|pR,j = 0, pS,j ≥ 0}, 22 3.2. Power Allocation where SR is the set containing subcarrier pairs intended to be used for relaying, and SN R is the set of subcarrier pairs on which direct transmission is performed in two successive time slots. Now the problem can be reformulated as follows: minimize (1) − (1) (2) pS , pS , pR (1) min{log(1 + ai pS,i ), log(1 + ci pS,i + bj pR,j )} (3.7) (i,j)∈SR (1) (2) {log(1 + ci pS,i ) + log(1 + cj pS,j )} − (i,j)∈SN R (1) s.t. (2) pS , pS , pR 0, (2) (1) 1T pS = PS , 1T pS = PS , 1T pR = PR . (2) (2) The objective function in (3.7) is separable in pS , and also pS is not coupled by constraints. Thus, we can break problem (3.7) into two sub-problems: Sub-Problem 1: Cooperative water-filling (Source PA in the 1st time slot): minimize (1) (1) − pS , pR (1) min{log(1 + ai pS,i ), log(1 + ci pS,i + bj pR,j )} (3.8) (i,j)∈SR (1) − {log(1 + ci pS,i )} (i,j)∈SN R s.t. (1) pS , pR 0, (1) 1T PS = PS , 1T PR = PR . 23 3.2. Power Allocation Sub-Problem 2: Classical water-filling (Source PA in the 2nd time slot): minimize (2) pS s.t. (2) − log(1 + cj pS,j ) (3.9) (i,j)∈SN R (2) pS 0, (2) 1T pS = PS . Using the Karush-Kuhn-Tucker (KKT) conditions [28], the solution of classical water-filling sub-problem is as follows: (2) pS,j = 0 max 0, (2) , (i, j) ∈ SR 1 (2) νS − 1 cj (3.10) , (i, j) ∈ SN R , (2) where the constant νS is chosen such that the constraint 1T pS = PS is satisfied. For solving the cooperative water-filling sub-problem, we first investigate 24 3.2. Power Allocation its convexity by introducing new variable w. minimize (1) pS , pR s.t. − (1) log(1 + wi ) − (i,j)∈SR log(1 + ci pS,i ) (3.11) (i,j)∈SN R (1) wi ≤ ai pS,i , (i, j) ∈ SR , (1) wi ≤ ci pS,i + bj pR,i , (i, j) ∈ SR , wi ≥ 0, (i, j) ∈ SR , (1) pS,i ≥ 0, (i, j) ∈ SN R , (1) 1T pS = PS , 1T pR = PR . The cooperative water-filling sub-problem is equivalent to (3.11), and the convexity of (3.11) is obvious, because, the objective function is a summation over convex functions, and constraints are all affine and linear [28]. Now we solve the problem in two steps: Step 1 : We set the source powers to be constant and optimize the relay power by writing the KKT conditions: pR,j = min max 0, ν1R − 0 (1) ci pS,i +1 bj (1) i , aib−c pS,i j , (i, j) ∈ SR (3.12) , (i, j) ∈ SN R , in which, the constant νR is chosen such that the constraint 1T pR = PR is satisfied. As stated earlier in proposition 1, if a pair (i, j) is in the set SR , then ai − ci > 0. And in turn, ai −ci bj (1) pS,i is a positive constant. 25 3.2. Power Allocation Step 2: We set the relay powers to be constant and optimize the source power by writing the KKT conditions: (1) pS,i = min max 0, max 0, 1 (1) νS − 1 (1) νS − 1 ai j , aib−c pR,j i 1 ci , (i, j) ∈ SR (3.13) , (i, j) ∈ SN R , (1) (1) in which, the constant νS is chosen such that the constraint 1T pS = PS is satisfied. Again, according to proposition 1, bj aj −cj pR,j is a positive constant. Finally, these two steps can be conducted alternatively until convergence is reached. As a result of the optimization problem being convex, setting one variable to be constant and optimizing with respect to the other one, and then doing the reverse is guaranteed to converge. Furthermore, simulation results show that this process converges quickly to an optimal point, and we will discuss it further in Chapter 5. 26 Chapter 4 Partial CSI: Expected Value of Capacity Maximization In this chapter, according to the problem formulation for the partial CSI case accomplished in Section 2.3, we are to solve the following optimization problems: NF F T NF F T minimize (1) (2) pS , pS , TR , TN R − i=1 NR ¯ {tR i,j · C1 (i, j) + ti,j · CN R (i, j)} (4.1) j=1 NF F T NR (tR i,j + ti,j ) = 1, ∀j ∈ {1, 2, . . . , NF F T }, s.t. i=1 NF F T NR (tR i,j + ti,j ) = 1, ∀i ∈ {1, 2, . . . , NF F T }, j=1 NR tR i,j , ti,j ∈ {0, 1}, ∀i, j ∈ {1, 2, . . . , NF F T }, (1) (2) pS , pS , (1) 0, (2) 1T pS = PS , 1T pS = PS , 27 Chapter 4. Partial CSI: Expected Value of Capacity Maximization and, minimize R pR , T , T NF F T NF F T − NR i=1 ¯ {tR i,j · C2 (i, j)} (4.2) j=1 NF F T NR (tR i,j + ti,j ) = 1, ∀j ∈ {1, 2, . . . , NF F T }, s.t. i=1 NF F T NR (tR i,j + ti,j ) = 1, ∀i ∈ {1, 2, . . . , NF F T }, j=1 NR tR i,j , ti,j ∈ {0, 1}, ∀i, j ∈ {1, 2, . . . , NF F T }, pR 1T pR 0, PR , (1) bj pR,j < ai pS,i , ∀(i, j) ∈ {(i, j)|tR i,j = 1}, where the optimization problem (4.1) is expected value of capacity maximization from viewpoint of the source, and (4.2) is expected value of capacity maximization from relay’s viewpoint. Similar to the perfect CSI case, determining the subcarrier selection and pairing pattern, or in other words, finding optimal TR and TN R matrices is an untractable integer programming problem. In order to overcome this shortcoming, we first select subcarriers which are suitable to be used for relaying, then we allocate the power at the source for the 1st time slot. The next step is finding the best subcarrier pairing at the relay, and then optimizing the relay power in the 2nd time slot. Finally, the source allocates power to subcarriers that are not being used by the relay in the 2nd time slot. 28 Chapter 4. Partial CSI: Expected Value of Capacity Maximization Examining equations (2.15) and (2.17), it immediately follows that the expected value of capacity at source can be broken into two parts. One part is the capacity that could be obtained by transmitting on the direct link, which is simply 1 2 (1) log(1 + ci pS,i ). And, the second part is the cooperation improvement (CImp (i, j)) to the objective value as follows: (1) (1) (1) 1 + ci pS,i 1 + ai pS,i 1 + ci pS,i 1 ) Ei(− ¯ ) − Ei(− ¯ ) . (4.3) CImp (i, j) = exp( ¯ 2 bpR,j bpR,j bpR,j Obviously, if ai > ci and PR,j > 0, then CImp (i, j) > 0, and the resulting expected value will be greater than the capacity that could be obtained by only transmitting on the direct link. On the other hand, if ai ≤ ci , then CImp (i, j) = 0, and cooperation does not improve the capacity. Therefore, the metric for selecting a subcarrier for relaying is simply using subcarriers with ai > ci for relaying. This metric is optimum considering the information available at the source. In contrast with the subcarrier selection process, subcarrier pairing can not be done by the source, since it does not have the necessary information on channel gains between the relay and destination. Thus, subcarrier pairing is treated at the relay in the 2nd time slot. This will be seen later in this chapter. Meanwhile, to be able to remove TR and TN R from (4.1), the source assumes an initial subcarrier pairing pattern and power values at the relay. Without loss of generality, the source may assume that the relay node will forward a given message on the same subcarrier as it received the message 29 Chapter 4. Partial CSI: Expected Value of Capacity Maximization on. To mathematically formulate this, we constitute the following three sets: SR = {(i, j)|ai > ci , j = i}, (4.4) (1) (4.5) (2) (4.6) SN R = {i|ai ≤ ci }, SN R = {j|pR,j = 0}, (1) where SR is the set of subcarrier pairs for relayed transmission, SN R is the set (2) of subcarriers for direct transmission in the 1st time slot, and SN R is the set (1) (2) of subcarriers for direct transmission in the 2nd time slot (SN R and SN R are not set of subcarrier pairs, but single subcarriers in each time slot). More(2) over, SN R will be available after the relay determines the subcarrier pairing pattern. Now, similar to Section 3.2 for perfect CSI case, the optimization problem (4.1) can be broken into two parts: Sub-Problem 1: Cooperative sub-problem (Source PA in the 1st time slot): minimize (1) pS s.t. (1) C¯2 (i, j) − − (1) (4.7) (1) i∈SN R (i,j)∈SR pS {log(1 + ci pS,i )} 0, (1) 1 T P S = PS . Sub-Problem 2: Classical water-filling (Source PA in the 2nd time slot) 30 Chapter 4. Partial CSI: Expected Value of Capacity Maximization which is exactly the same as (3.9): minimize (2) pS s.t. (2) − log(1 + cj pS,j ) (4.8) (2) j∈SN R (2) pS 0, (2) 1T pS = PS . However, sub-problem 2 cannot be treated here, because, first, the relay needs to determine which subcarriers are used for relaying in the 2nd time slot. Therefore, we come back to this problem after treating the optimization problem (4.2) at relay. Before solving the Cooperative sub-problem, we examine the convexity of this problem. The constraints are obviously constructing a convex feasible set. The convexity of the right hand side term of the objective function is also trivial. And, it is shown in Appendix A that − C¯1 (i, j) is also convex. Therefore, the whole problem is convex. Nevertheless, finding a closed form solution by writing KKT conditions proved to be impossible. Therefore, this problem can be solved by many well-known iterative algorithms such as Gradient Descent, Interior Point [28] or Sequential Quadratic Programming (SQP) [29] methods. In this thesis we chose to adopt SQP method, due to its robustness and fast convergence rate. It will be seen in Chapter 5 that the algorithm converges to the global optimal point in few steps. Once the source allocated the power, it puts a tag on messages sent 31 Chapter 4. Partial CSI: Expected Value of Capacity Maximization over subcarriers which are used for relaying, so that the relay distinguishes relaying subcarriers. Also, as a result of the relay knowing the source-relay (1) channel gains, it is able to calculate the updated pS very easily. After these steps, the relay is ready to address the optimization problem (4.2). Again, TR needs to be found to avoid an untractable integer programming. One approach to finding TR is to perform the Hungarian method on the following matrix: D(i, j) = C¯2 (i, j) , if i was selected for relayed transmission by the source, 0 , if i was selected for direct transmission by the source. (4.9) This procedure gives the optimal TR . However, C¯2 (i, j) has the property of L(1) superadditivity with respect to ai pS,i and bj pR,j , i.e., Γ(1) ai and Γbj . It has been shown in [30] that if the objective function is L-superadditive, then subcarrier pairing based on ordering the subcarrier SNRs is optimal and equivalent to the Hungarian method. Here, we order the subcarriers in the 1st time slot (1) according to ai pS,i and the 2nd time slot based on bj pR,j , then the best sourcerelay subcarrier is paired with the best relay-destination subcarrier, and so on. The L-supperadditivity of C¯2 (i, j) is shown in Appendix B. Furthermore, we observed that subcarrier pairing based on ordering is identical to the Hungarian method in our simulations. 32 Chapter 4. Partial CSI: Expected Value of Capacity Maximization (2) After finding TR , SR and SN R sets are updated as follows: SR = {(i, j)|tR i,j = 1}, (4.10) (2) (4.11) SN R = {j|sum[TR (:, j) = 0]}, and the optimization problem (4.2) will be in the following form: minimize pR s.t. C¯2 (i, j) − (4.12) (i,j)∈SR pR 1T pR 0, PR , (1) bj pR,j < ai pS,i , ∀(i, j) ∈ SR , (1) where pS,i s are considered to be fixed. The constraints of the above problem are all affine and linear, and the convexity of the objective function is shown in Appendix A. So, this problem also can be solved by SQP method, due to its robustness and fast convergence. Finally, similar to the source, the relay needs to put another tag on transmitted messages so that the destination retrieves the subcarrier pairing pattern and exploits maximum ratio combining. When subcarriers on which the relay transmits in the 2nd time slot are determined, the source continues sending information on the rest with op(2) timized power pS obtained by solving the classical water-filling problem 33 Chapter 4. Partial CSI: Expected Value of Capacity Maximization (4.8), for which the solution is identical to (3.10). However, the relay needs (2) to inform the source of the updated SN R . This can be done through a light feedback message, or, if channel gains do not vary for more than two time slots, the source gains the knowledge of free subcarriers by listening to the relay in the first round of two time slots. At last, when the period of first two time slots is over, the source optimizes its power according to the new (2) SR and SN R sets and pR . In other words, assuming initial relaying pattern and relay powers at the source is not necessary anymore. 34 Chapter 5 Numerical Results We demonstrate the performance of our selective DF subcarrier pairing and PA techniques for perfect and partial CSI cases through simulation. As it will be seen later in this chapter, the distance and the relay power budgets play a major role in subcarrier selection and pairing, and PA procedures, so we performed simulations for different relay power budgets and positions. It is assumed that all the three nodes are located on a line. The distance between the source and destination (d0 ) is always 1000 m, and location of the relay is indicated by dr , d0 where dr is the source-relay distance. We consider an OFDM modulation with NF F T = 16, subcarrier separation of 10 KHz, and σr2 = σd2 = 4.47 × 10−17 . We consider frequency-selective channels of which the impulse response in the time domain is defined as [16]: L−1 hn · δ(t − nT ), h(t) = (5.1) n=0 where hn is the complex amplitude of path n, and L is the number of channel taps or different paths. We assume that the complex amplitudes of each tap 35 Chapter 5. Numerical Results hn is picked from a Rayleigh fading channel with the following distribution [16]: hn ∼ CN 0, 1 , L(1 + d)α (5.2) where the path loss exponent α = 3, distance d m, and the number of taps L = 4. Therefore, the power delay profile (P(t)) can be defined as: L−1 |hn |2 · δ(t − nT ), P(t) = (5.3) n=0 where | · | is the magnitude of the complex argument. Thus, the Fourier Transform of the power delay profile with NF F T subcarriers generates |hi |2 (power gains) in the frequency domain, where i indicates the index of subcarriers. Finally, given |hi |2 , σr2 , σd2 , NF F T and subcarrier separation, the channel gains to noise power ratios ai , bi and ci are calculated as described in Chapter 2. The source power budget is then selected such that for all subcarriers we have the average SNR of 0 dB at the destination. Moreover, average percentage of relaying subcarriers in different scenarios proved to be useful in analyzing the numerical results. These ratios are shown in Tables 5.1 and 5.2 for perfect and partial CSI cases, respectively. Here, β indicates random relative source-relay distance, taken from a uniform distribution, i.e., β ∼ U [0, 1]. According to these two tables, the ratio of relaying subcarriers increases when the relay is close to the source, and vice versa. This conclusion is compatible with intuition, because when the relay is close to the source, it is more likely that the source-relay channel gains are 36 5.1. Convergence Results stronger than source-destination. Table 5.1: Relaying subcarriers ratio (Perfect CSI) Relay Power Budget PS 0.1 · PS 0.04 · PS % Relaying Subcarriers dr = 0.5d0 dr = βd0 92.75 67.5 74.44 49.94 57.31 40.44 Table 5.2: Relaying Subcarriers Ratio (Partial CSI) % Relaying Subcarriers dr = 0.25d0 dr = 0.5d0 dr = 0.75d0 dr = βd0 98.75 94.5 72.5 81.75 5.1 Convergence Results We study the convergence of the iterative process described in Chapter 3 for perfect CSI case in Fig. 5.1. Analyzing the results in Fig. 5.1, we first find out that the iterative process converges to the optimal solution in every considered scenario, and even first step is very close to the optimal. An important observation is that the convergence time increases when the ratio of relaying subcarriers is close to 50%. This is a situation where the number of subcarrier pairing and selection combinations is large, and it takes more trials to reach the optimal solution. 37 5.1. Convergence Results Percentage of relative error wrt optimal capacity 0.25 PR=PS, d=0.5 PR=0.1*PS, d=0.5 PR=0.04*PS, d=0.5 PR=PS, d=random PR=0.1*PS, d=random PR=0.04*PS, d=random 0.2 0.15 0.1 0.05 0 1 2 3 4 5 6 7 Number of iterations 8 9 10 Figure 5.1: Convergence of the PA technique, perfect CSI Convergence of problems (4.7) and (4.12) (i.e., the source PA in the 1st time slot and the relay PA) which are derived under partial CSI assumption in Chapter 4 is shown in Figures 5.2 and 5.3, respectively. Two different relay power budgets of PR = PS and PR = 0.1 · PS are shown in Fig. 5.2, since the source optimization problem does not depend on the power budgets. However, in Fig. 5.3, only reduced power budget is shown for the relay problem to avoid repetitive figures, because, equal power budget also results in very similar results. Comparing these two figures, it is disclosed that when the relay is close to the source, the source’s optimization problem converges faster. However, for the relay it is the opposite, when the relay is far from the source, the relay’s optimization problem converges in less iterations. As 38 5.1. Convergence Results for the relay, when it is far from the source, less subcarriers are selected for relaying, which in turn, reduces the number of parameters in the optimization problem. Therefore, the solution converges faster. On the other hand, source has to allocate power to both the relaying and non-relaying subcarriers, or in other words, the number of variables does not change. These two groups of subcarriers have different objective functions, therefore, when the relay is far from the source, the number of relaying and non-relaying subcarriers become comparable, and the dynamic nature of the optimization solution becomes more complex. Eventually, it takes more iterations to get to the optimal point. Overall, as it can be observed in Figures 5.2 and 5.3, the SQP method used to solve these optimization problems converges very fast for all considered scenarios. 39 5.1. Convergence Results Percentage of relative error wrt optimal value 7 PR=PS or 0.1*PS, d=0.25 PR=PS or 0.1*PS, d=0.5 PR=PS or 0.1*PS, d=0.75 6 5 4 3 2 1 0 1 2 3 4 5 6 7 Number of iterations 8 9 10 Figure 5.2: Convergence of the source optimization problem, partial CSI 40 5.1. Convergence Results Percentage of relative error wrt optimal value 8 PR=0.1*PS, d=0.25 PR=0.1*PS, d=0.5 PR=0.1*PS, d=0.75 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 Number of iterations 8 9 10 Figure 5.3: Convergence of the relay optimization problem, partial CSI 41 5.2. Subcarrier Pairing and Selection Performance 5.2 Subcarrier Pairing and Selection Performance We consider the performance of the subcarrier pairing and selection part of the process described in Section 3.1 and Chapter 4. We performed simulations for a power budget of PR = PS , with several positions for the relay. The resulting average capacity for scenarios where subcarrier pairing and selection are activated or not are shown in Figures 5.4 and 5.5, for perfect and partial CSI cases, respectively. The PA procedure is activated for all the scenarios, and the shown values are obtained by averaging the capacity over 10,000 channel realizations. Analyzing the results in Fig. 5.4 (perfect CSI case), we observe that any scenario without considering subcarrier selection worsens capacity for some positions of the relay. And also, subcarrier selection has a higher effect on the capacity than subcarrier pairing. On the other hand, investigating the results for partial CSI in Fig. 5.5, subcarrier pairing is more effective than subcarrier selection when the relay is closer to the source, and, subcarrier selection becomes dominant when the relay goes towards the destination. This is because, when the relay is close to the source, most of the subcarriers are used for relaying, whether subcarrier selection is activated or not. In contrast, when the relay is far from the source, more options for direct transmission rise and subcarrier selection becomes dominant. Overall, it appears clearly that subcarrier pairing and selection using the methods described in Section 42 5.2. Subcarrier Pairing and Selection Performance 3.1 and Chapter 4 improve capacity for every considered relay position, in both perfect and partial CSI cases. 3 Capacity (B/s/Hz) 2.5 2 1.5 Selection, Pairing Selection, No Pairing Always Relay, Pairing Always Relay, No Pairing 1 0.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Normalized distance between source and relay 0.8 0.9 Figure 5.4: Performance of the subcarrier pairing and selection processes, perfect CSI 43 5.2. Subcarrier Pairing and Selection Performance 3 Capacity (B/s/Hz) 2.5 2 1.5 1 Selection, Pairing Selection, No Pairing Always Relay, Pairing Always Relay, No Pairing 0.5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Normalized distance between source and relay 0.8 0.9 Figure 5.5: Performance of the subcarrier pairing and selection processes, partial CSI 44 5.3. Power Allocation Performance 5.3 Power Allocation Performance We study the performance of the proposed PA schemes for both perfect and partial CSI cases. We consider different PA scenarios and relay power budgets for several relay positions. In Figures 5.6 and 5.8, average capacity in perfect CSI case is shown for two different relay power budgets: PR = PS and PR = 0.1 · PS . As for the partial CSI case, average capacity for PR = PS relay power budget is shown in Fig. 5.7, and for PR = 0.1 · PS is displayed in Fig. 5.9. Here, the subcarrier selection and pairing are always performed, and the displayed values are average capacities over 10,000 different channel realizations. We analyze these figures in terms of similarities and differences between perfect and partial CSI cases. Firstly, we classify the similarities: • Performance: It is observed that our PA techniques in both perfect and partial CSI cases improve capacity for any considered relay position and relay power budget scenario. • Location of the Peak Capacity: When the relay has equal power budget to the source, the peak occurs at the midpoint between the source and relay. When the relay power ratio is less, the peak capacity moves towards the destination, because the maximal capacity occurs when the source-relay and relay-destination links have the same level of SNR. • Capacity Close to the Destination: The capacity obtained for both relay power budgets assuming perfect CSI when the relay is close to the 45 5.3. Power Allocation Performance 2.8 2.6 Capacity (B/s/Hz) 2.4 2.2 2 1.8 1.6 Optimal Source and Relay Uniform Relay Uniform PS(2) Uniform PS(1) and PS(2) Uniform PS and PR 1.4 1.2 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Normalized distance between source and relay 0.8 0.9 Figure 5.6: Performance of the PA scheme for equal power budgets, perfect CSI destination is similar, because the min function in (2.1) is dominated by the source-relay link. Equivalently, the same thing happens assuming partial CSI case. This is because, min function keeps its role after calculating the expected value of the capacity. • Capacity Elsewhere: The capacity obtained in the equal power scenario is much higher compared to the reduced relay power for both cases, because, more power is available at the relay, which in turn, results in higher SNRs and capacities. Now, we categorize the differences between perfect and partial CSI cases: • The capacity obtained by assuming perfect CSI is higher than partial 46 5.3. Power Allocation Performance 2.8 2.6 2.4 Capacity (B/s/Hz) 2.2 2 1.8 1.6 1.4 Optimal Source & Relay Uniform PS(2) Uniform PS(1) & PS(2) Uniform Relay Uniform PS & PR 1.2 1 0.8 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Normalized distance between source and relay 0.8 0.9 Figure 5.7: Performance of the PA scheme for equal power budgets, partial CSI CSI in equivalent scenarios. This is obviously due to the fact that the source and relay in partial CSI case, do not have access to the full channel gain information. • In terms of perfect CSI case, it can be seen that uniform relay curves offer better performances than all uniform source power curves for most considered positions of the relay. This is because, the source PA has an impact on both direct and relay links, which is not the case for the relay PA. In contrast with perfect CSI case, in partial CSI case, the relay PA affects the capacity more than the source PA, especially when the relay is closer to the source than the destination. The reason is 47 5.3. Power Allocation Performance 2.4 Optimal Source & Relay Uniform Relay Uniform PS(2) Uniform PS(1) & PS(2) Uniform PS & PR 2.2 Capacity (B/s/Hz) 2 1.8 1.6 1.4 1.2 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Normalized distance between source and relay 0.8 0.9 Figure 5.8: Performance of the PA scheme for reduced relay power budget, perfect CSI that, when the relay is close to the destination, most of the subcarriers are used to perform relaying. Therefore, optimizing the relay power significantly improves the capacity. (2) (2) • Impact of pS : In partial CSI case, pS does not play a considerable role, especially when the relay is closer to the source than the destination. As stated in the previous item, this is because a low percentage of subcarriers are used for direct link in the 2nd time slot. However, in perfect CSI case, the effect is considerable. All in all, regarding perfect (2) CSI case, recent research in the field does not contain pS allocation, (2) thus, available solutions must obtain similar results to the uniform pS 48 5.3. Power Allocation Performance 2 1.8 Capacity (B/s/Hz) 1.6 1.4 1.2 1 Optimal Source & Relay Uniform PS(2) Uniform PS(1) & PS(2) Uniform Relay Uniform PS & PR 0.8 0.6 0.4 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Normalized distance between source and relay 0.8 0.9 Figure 5.9: Performance of PA scheme for reduced relay power budget, partial CSI curves, and in terms of partial CSI, due to the novelty of the problem formulation, similar works do not exist in the literature. 49 Chapter 6 Conclusions and Future Work 6.1 Conclusions In this thesis, we have presented selective subcarrier pairing algorithms with PA for OFDM cooperative wireless links assuming perfect and partial CSI, under individual power constraints. In perfect CSI case, we have analytically demonstrated that our semi-distributed method maximizes instantaneous rate, for several individual power budgets and relay location scenarios. Numerical results show that our method outperforms systems using similar solutions available in the most recent research in the field. Additionally, adding a unified subcarrier pairing and selection process based on the Hungarian method to our iterative PA solution greatly improves capacity performance, without considerably increasing the convergence time. Regarding partial CSI, the source or relay may not know the channel gains fully. Therefore, we have formulated the problem in order to maximize the expected value of capacity at the source and relay. The proposed algorithm is distributed, in which the source and relay operate separately with low signalling overhead. Moreover, subcarrier selection process is based on com- 50 6.2. Future Work parison of channel gains, while subcarrier pairing is based on ordering the subcarrier SNRs, both having low complexities. Finally, simulation results prove the effectiveness of this distributed algorithm. 6.2 Future Work There are several possible extensions of the work presented in this thesis and these are listed below: • In this thesis, we have investigated a two-hop relaying system consisting of one source, one relay and one destination. Considering more than one relay assisting the source is a topic for future work. • The second area for further development is assuming multiple antennas at all the three nodes. Then, besides subcarriers, different antennas must be selected and paired with each other, too. Furthermore, power should be distributed optimally among the antennas. • This thesis only addressed DF cooperative systems. Investigating AF cooperative systems and developing similar solutions can be another venue for future work. • Robustness of the algorithms developed in this thesis in the presence of erroneous channel estimations is also a possible direction. 51 Bibliography [1] Edward C. van der Meulen. Three-terminal communication channels. Adv. Appl. Prob., 3(1):120–154, 1971. [2] T. Cover and A. El Gamal. Capacity theorems for the relay channel. IEEE Trans. Inf. Theory, 25(5):572–584, Sep. 1979. [3] O. Oyman, N.J. Laneman, and S. Sandhu. Multihop relaying for broadband wireless mesh networks: From theory to practice. IEEE Commun. Mag., 45(11):116 –122, Nov. 2007. [4] D. Soldani and S. Dixit. Wireless relays for broadband access [radio communications series]. IEEE Commun. Mag., 46(3):58 –66, Mar. 2008. [5] R. Pabst, B.H. Walke, D.C. Schultz, P. Herhold, H. Yanikomeroglu, S. Mukherjee, H. Viswanathan, M. Lott, W. Zirwas, M. Dohler, H. Aghvami, D.D. Falconer, and G.P. Fettweis. Relay-based deployment concepts for wireless and mobile broadband radio. IEEE Commun. Mag., 42(9):80–89, Sep. 2004. [6] J. N. Laneman, D. N. C. Tse, and G. W. Wornell. Cooperative diversity 52 Bibliography in wireless networks: efficient protocols and outage behavior. IEEE Trans. Inf. Theory, 50(12):3062–3080, Dec. 2004. [7] R. U. Nabar, H. Bolcskei, and F. W. Kneubuhler. Fading relay channels: performance limits and space-time signal design. IEEE Jour. on Selected Areas in Commun., 22(6):1099–1109, Aug. 2004. [8] J. N. Laneman and G. W. Wornell. Energy-efficient antenna sharing and relaying for wireless networks. In Proc. IEEE WCNC, pages 7–12, Sep. 2000. [9] K. J. Ray Liu, Ahmed K. Sadek, Weifeng Su, and Andres Kwasinski. Cooperative Communications and Networking. Cambridge University Press, 2009. [10] Zhang Jingmei, Zhang Qi, Shao Chunju, Wang Ying, Zhang Ping, and Zhang Zhang. Adaptive optimal transmit power allocation for two-hop non-regenerative wireless relaying system. In Proc. IEEE VTC, pages 1213–1217, May 2004. [11] Zhang Qi, Zhang Jingmei, Shao Chunju, Wang Ying, Zhang Ping, and Hu Rong. Power allocation for regenerative relay channel with Rayleigh fading. In Proc. IEEE VTC, pages 1167–1171, May 2004. [12] Wang Ying, Qu Xin-chun, Wu Tong, and Liu Bao-ling. Power allocation and subcarrier pairing algorithm for regenerative OFDM relay system. In Proc. IEEE VTC, pages 2727–2731, Apr. 2007. 53 Bibliography [13] Yong Li, Wenbo Wang, Jia Kong, Wei Hong, Xing Zhang, and Mugen Peng. Power allocation and subcarrier pairing in OFDM-based relaying networks. In Proc. IEEE ICC, pages 2602–2606, May 2008. [14] M. O. Hasna and M.-S. Alouini. Optimal power allocation for relayed transmissions over Rayleigh-fading channels. IEEE Trans. Wireless Commun., 3(6):1999–2004, Nov. 2004. [15] M. O. Hasna and M.-S. Alouini. Optimal power allocation for relayed transmissions over Rayleigh fading channels. In Proc. IEEE VTC, volume 4, pages 2461–2465, Apr. 2003. [16] I. Hammerstrom and A. Wittneben. On the optimal power allocation for nonregenerative OFDM relay links. In Proc. IEEE ICC, pages 4463– 4468, Jun. 2006. [17] J. Louveaux, R. T. Duran, and L. Vandendorpe. Efficient algorithm for optimal power allocation in OFDM transmission with relaying. In Proc. IEEE ICASSP, pages 3257–3260, Apr. 2008. [18] L. Vandendorpe, R.T. Duran, J. Louveaux, and A. Zaidi. Power allocation for OFDM transmission with DF relaying. In Proc. IEEE ICC, pages 3795–3800, May 2008. [19] Weifeng Su, A. K. Sadek, and K. J. R. Liu. SER performance analysis and optimum power allocation for decode-and-forward cooperation pro- 54 Bibliography tocol in wireless networks. In Proc. IEEE WCNC, pages 984–989, Mar. 2005. [20] J. Luo, R. S. Blum, L. Cimini, L. Greenstein, and A. Haimovich. Power allocation in a transmit diversity system with mean channel gain information. IEEE Commun. Letter, 9(7):616–618, Jul. 2005. [21] Xitirnin Deng and A. M. Haimovich. Power allocation for cooperative relaying in wireless networks. IEEE Commun. Letter, 9(11):994–996, Nov. 2005. [22] Ramesh Annavajjala, Pamela C. Cosman, and Laurence B. Milstein. Statistical channel knowledge-based optimum power allocation for relaying protocols in the high SNR regime. IEEE Jour. on Selected Areas in Commun., 25(2):292–305, Feb. 2007. [23] Beibei Wang, Zhu Han, and K.J.R. Liu. Distributed relay selection and power control for multiuser cooperative communication networks using stackelberg game. Mobile Computing, IEEE Transactions on, 8(7):975 –990, july 2009. [24] Theodore S. Rappaport. Wireless Communications: Principles and Practice. Prentice Hall, Inc., second edition, 2002. [25] Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, ninth dover printing, tenth gpo printing edition, 1964. 55 [26] Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali. Linear Programming and Network Flows. John Wiley & Sons, Inc., second edition, 1990. [27] H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83–97, 1955. [28] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Mar. 2004. [29] Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, Aug. 2000. [30] A. Hottinen and T. Heikkinen. Optimal subchannel assignment in a two-hop OFDM relay. In Proc. IEEE SPAWC, pages 1–5, Jun. 2007. [31] H. Hindi. A tutorial on convex optimization. In Proc. 2004 Amer. Contr. Conf., pages 3252–3265, Jun. 2004. [32] Henry W. Block, William S. Griffith, and Thomas H. Savits. superadditive structure functions. L- Adv. Appl. Prob., 21(4):919–929, 1989. 56 Appendix A Convexity of C¯1 and C¯2 (1) (1) As stated in Section 3.2, − log 1 + min{ai pS,i , ci pS,i + bj pR,j } is jointly con(1) vex in pS,i and pR,j . Using the following theorem we can show the convexity of −C¯1 (i, j) and −C¯2 (i, j) [31]: Theorem: If f (x, y) is convex in x, then Eu [f (x, u)] (Expected value of f (x, u) with respect to u) is also convex in x. Here, −C¯1 (i, j) and −C¯1 (i, j) are defined as follows: (1) (1) −C¯1 (i, j) = EΓbj − log 1 + min{ai pS,i , ci pS,i + Γbj } (1) −C¯2 (i, j) = EΓ(1) − log 1 + min{ai pS,i , Γ(1) ci + bj pR,j } ci , (A.1) , (A.2) (1) which are convex in pS,i and pR,j , respectively, according to the above theorem. Therefore, the − C¯1 (i, j) and − C¯1 (i, j) are also convex, because, they are in the form of summation over convex functions. 57 Appendix B L-superadditivity of C¯2 First we define L-superadditivity, and mention a useful remark on the definition, both taken from [32]: Definition 1: A function h(x, y) is called L-superadditive if for all x1 ≤ x2 and y1 ≤ y2 in its domain of definition, h(x2 , y2 ) + h(x1 , y1 ) − h(x1 , y2 ) − h(x2 , y1 ) ≥ 0. (B.1) Remark 1.1: If h(x, y) is continuous, then h(x, y) is L-superadditive if and only if the following inequality holds for almost all (x, y): ∂ 2 h(x, y) ≥ 0. ∂x∂y (B.2) We claim that C¯2 (i, j) is L-superadditive with respect to (Γai , Γbj ). Proof: 1 C¯2 (i, j) = EΓ(1) log 1 + min{Γai , Γ(1) ci + Γ b j } 2 ci , (B.3) 58 Bibliography and ∂ C¯2 (i, j) 1 = ∂Γai 2 1 EΓ(1) 1+Γ ai ci 0 , Γai < Γ(1) ci + Γ b j , Γai ≥ Γ(1) ci , + Γ bj and ∂ 2 C¯2 (i, j) = 0, ∂Γai ∂Γbj (B.4) which according to Remark 1.1 completes the proof. 59
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Selective subcarrier pairing and power allocation for...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Selective subcarrier pairing and power allocation for decode-and-forward OFDM relay systems with perfect… Boostanimehr, Hamidreza 2010
pdf
Page Metadata
Item Metadata
Title | Selective subcarrier pairing and power allocation for decode-and-forward OFDM relay systems with perfect and partial CSI |
Creator |
Boostanimehr, Hamidreza |
Publisher | University of British Columbia |
Date Issued | 2010 |
Description | This thesis investigates a decode-and-forward two-hop relaying system consisting of one source, one relay and one destination, in which orthogonal frequency division multiplexing is used. The relay forwards the message received from the source on a subset of available subcarriers in the second time slot. Firstly, a subcarrier pairing and selection algorithm is proposed, assuming that perfect channel state information (CSI) is available at all nodes, then, power is allocated to both the source and relay stations under individual power constraints in order to maximize the capacity. Secondly, subcarrier selection and pairing, and power allocation (PA) under partial CSI assumption along with individual power constraints are addressed. The result is a novel distributed algorithm with low complexity maximizing the expected value of capacity at the source and relay nodes. Finally, the simulation results show that selective relaying combined with subcarrier pairing and PA improves the system capacity to a considerable extent in both perfect and partial CSI cases. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-09-01 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0064887 |
URI | http://hdl.handle.net/2429/28119 |
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 | 2010-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2010_fall_boostanimehr_hamidreza.pdf [ 437.2kB ]
- Metadata
- JSON: 24-1.0064887.json
- JSON-LD: 24-1.0064887-ld.json
- RDF/XML (Pretty): 24-1.0064887-rdf.xml
- RDF/JSON: 24-1.0064887-rdf.json
- Turtle: 24-1.0064887-turtle.txt
- N-Triples: 24-1.0064887-rdf-ntriples.txt
- Original Record: 24-1.0064887-source.json
- Full Text
- 24-1.0064887-fulltext.txt
- Citation
- 24-1.0064887.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-0064887/manifest