(PDF) Genetic algorithm assisted multiuser detection for asynchronous multicarrier CDMA

Genetic Algorithm Assisted Multiuser Detection for Asynchronous Multicarrier CDMA Hua Wei and Lajos Hanzo1 Dept. of ECS, University of Southampton, SO17 1BJ, UK. Tel: +44-23-8059-3125, Fax: +44-23-8059-4508 Email:lh1 @ecs.soton.ac.uk, http://www-mobile.ecs.soton.ac.uk Abstract In this contribution a novel genetic algorithm (GA) based multiuser detection (MUD) aided multicarrier code-division multiple-access (MC CDMA) scheme was investigated in the context of frequency-selective Rayleigh fading channels. We considered four different detection strategies in our performance comparisons. Furthermore, turbo coding was invoked for the sake of performance enhancement and –surprisingly– for further complexity reduction. The simulation results showed that the GA assisted MUD was capable of significantly reducing the complexity of Verdu’s optimum MUD without significantly degrading the achievable performance. 1. INTRODUCTION Multicarrier CDMA (MC-CDMA) [1–3] is a novel transmission technique, which combines DS-CDMA and Orthogonal Frequency Division Multiplexing (OFDM) [4–7]. In MC-CDMA systems, instead of applying spreading sequences in the time domain for spreading each bit, we employ spreading sequences in the frequency domain. Hence, we are capable of achieving frequency diversity gain at the cost of a reduced spreading gain. Numerous Multiuser Detection (MUD) schemes have been proposed in the literature [8–10]. For example, the Minimum Mean Square Error (MMSE) MUD has been described in [3, 8], while an Interference Cancellation (IC) based MUD has been proposed in [3, 9]. In [11], the Maximum Likehood (ML) MUD designed for MC-CDMA had been considered. In this specific MUD, the receiver constructs all the possible combinations of the transmitted signal and employs the estimated channel transfer function for generating all the possible received signals, in order to find the one, which has the smallest Euclidean distance from the received signal. Hence, the ML detection based MUD designed for MC-CDMA is capable of achieving the optimum performance. However, it requires the calculation of 2K number of possible received signal combinations in conjunction with Binary Phase Shift Keying (BPSK) modulation. In other words, the ML detection based MUD’s complexity will increase exponentially with the number of users K. Hence the complexity imposed will become excessive, when the number of users K is high. Therefore, in this treatise we will invoke Genetic Algorithms (GA) [12, 13] for reducing the complexity of the ML detection based MUD employed in MC-CDMA systems. The GA-based MUD was first proposed by Juntti The financial support of the Mobile VCE, UK; EPSRC, UK and that of the European Union is gratefully ackowledged. 0-7803-8521-7/04/$20.00 © 2004 IEEE et al. [14] for a synchronous DS-CDMA system communicating over an Additive White Gaussian Noise (AWGN) channel. Yen et al. [3] [15–17] further improved the performance of the GA-based MUD, demonstrating that the performance of the GA-based MUD approaches the single-user performance bound at a significantly lower computational complexity, than that of Verdu’s optimum MUD [18]. Again, in this treatise we will employ a GA assisted MUD scheme as a suboptimal MUD technique applicable to asynchronous MC-CDMA systems communicating over broadband frequency selective fading channels. We assume that each subcarrier obeys independent Rayleigh fading. More explicitly, we will investigate the performance of this specific GA-assisted MUD as a function of the affordable detection complexity. This contribution is organized as follows. Section 2 outlines the receiver model. Section 3 characterizes the achievable performance of the GA assisted MUD. Finally, Section 4 offers our conclusions and outlines our future work. 2. GA ASSISTED MUD AIDED ASYNCHRONOUS MC-CDMA SYSTEM z1,1 b̂1 Tb 0 c1,1 (t − τ1 ) b̂2 zK,1 e−jω1 t Tb Assisted cK,1 (t − τK ) Multiuser GA− 0 r(t) Detection z1,M Tb 0 c1,M (t − τ1 ) e−jωM t zK,M Tb b̂K 0 cK,M (t − τK ) Figure 1: Schematic of the GA assisted MUD aided asynchronous MC-CDMA base station receiver. When communicating over asynchronous environments, the received signal of MC-CDMA can be expressed as: ∞ K 2Ebk (i) rm (t) = ck,m (t − iTb − τk )γk,m bk e(jwm t+φk,m ) M i=−∞ k=1 +n(t), 1914 where τk is the kth user’s delay. Without loss of generality, we assume that we have 0 ≤ τ1 < τ2 · · · < τK < Tb , where (i) Ebk is the kth user’s signal energy per bit, bk ∈ (1, −1), k = 1, . . . , K denotes the ith transmitted bit of the kth user, while the kth user’s signature waveform is ck,m (t), k = 1, . . . , K, m = 1, . . . , M on the mth subcarrier, which again has a length of N chips, and can be written as: (m) Rjk [1] = ck,m (t) = n=0 (n) ρkj = (i) = = [z1,m , . . . , zK,m ] Rm [1]Wm Ab(i−1) + Rm [0]Wm Ab(i) + RTm [1]Wm Ab(i+1) + nm , (4) where we have Cm = [c1,m (t), . . . , cK,m (t)] jφ1,m jφK,m Wm = diag[γ ] 1,m e , . . . , γK,m e b1 A = diag[ 2E ,..., M b = [b1 , . . . , bK ]T n = [n1 , . . . , nK ]T . 2EbK ] M (5) where i is the time instant index and the zero-mean Gaussian noise vector nm has the crosscorrelation matrix of:  2 T σ R [1], if j = i + 1;    2 if j = i; σ R[0], T (6) E[n[i]n [j]] = if j = i − 1; σ 2 R[1],    0, otherwise. The partial crosscorrelation matrix Rm [1] and the crosscorrelation matrix Rm [0] of the spreading codes, when communicating over an asynchronous channel, are defined as [18]:   if j = k;  1, (m) (m) ρjk , if j < k; (7) Rjk [0] =   ρ(m) , if j > k, kj 0-7803-8521-7/04/$20.00 © 2004 IEEE (9) cj,m (t)ck,m (t − τ + Tb )dt. (10) τ 0 According to Equation 4, the noise sample vector nm can also be expressed as : nm = (i) Zm − Rm [1]Wm Ab(i−1) −Rm [0]Wm Ab(i) − RTm [1]Wm Ab(i+1) . (11) Hence, the objective function of the optimum ML detector on the mth subcarrier can be expressed as: Ωm (b(i) ) = arg{ min b(i−1) ,b(i) ,b(i+1) E[nm · nm T ]}. (12) Hence, according to Equation 12, the GA’s objective metric for the mth subcarrier, which we have to maximize, can be expressed as: (i) exp{− Zm − Rm [1]Wm Ab(i−1) − Rm [0]Wm Ab(i) − RTm [1]Wm Ab(i+1) 2 }, (13) where · denotes the Eucledian norm of a complex quantity expressed for the arbitrary variable v = a + jb as v = √ a2 + b2 . Therefore, when combining the signals of the M subcarriers, the modified objective function becomes: Ωm (b(i) ) = According to [18], the received signal vector Zm recorded at the output of the bank of matched filters on the mth subcarrier can be expressed as [18]: Zm cj,m (t)ck,m (t − τ )dt τ (m) Each user’s signal sk,m (t) transmitted on the mth subcarrier is assumed to propagate over an independent non-dispersive single-path Rayleigh fading channel and the fading envelope of each path is statistically independent for all the users. Hence, the single-tap narrowband Channel Impulse Response (CIR) of the kth user on the mth subcarrier can be expressed as γk,m ejφk,m , where the amplitude γk,m is a Rayleigh distributed random variable, while the phase φk,m is uniformly distributed between [0, 2π). Figure 1 shows the schematic of the GA assisted MUD aided asynchronous MC-CDMA base station receiver. As seen in Figure 1, the output of the kth user’s matched filter corresponding to the mth subcarrier sampled at the end of the ith symbol interval is given as: ∞ (i) (3) zk,m = r(t)ck,m (t − iTb − τk )dt. −∞ (8) Tb m = 1, . . . , M, k = 1, . . . , K, (1) where Tc is the chip duration, N is the number of chips per bit associated with each subcarrier and we have Tb /Tc = N . Again, the total processing gain is N M , while p(t) is the rectangular chip waveform employed, which can be expressed as: 1 0 ≤ t < Tc p(t) = (2) 0 otherwise. if j ≥ k; if j < k. (m) (m) ρjk = ck,m p(t − nTc ), 0, (m) ρkj , where the coefficients ρkj and ρkj on the mth subcarrier are the pair of crosscorrelations of the spreading codes recorded in the asynchronous CDMA environment, which can be written as [18]: (m) N −1 Ω(b(i) ) = exp{− M m=1 (i−1) Z(i) m − Rm [1]Wm Ab −Rm [0]Wm Ab(i) − RTm [1]Wm Ab(i+1) 2 }. (14) Therefore, for the sake of achieving the optimum performance, we have to maximize the metric Ω of Equation 14. More explicitly, the optimum decision concerning the K-dimensional Current Estimated Bit (CEB) vector b(i) will maximize the crosscorrelation metric in Equation 14, provided that the Kdimensional Start Estimated Bit (SEB) vector b(i−1) and the K-dimensional End Estimated Bit (EEB) vector b(i+1) are perfectly known to the receiver. However, in practice the receiver is oblivious of the K-dimensional EEB vectors b(i+1) during the detection of b(i) , unless these are estimated based on pilot bits or training bits. Furthermore, the K-dimensional SEB vector b(i−1) is never perfectly known by the receiver, as a consequence of channel errors. Hence we have to invoke appropriate strategies for finding reasonable choices of (b(i−1) , b(i) , b(i+1) ) for the maximization of Equation 14. In the next subsection, we will describe four related strategies in detail. 2.1. Edge-bit Generation In the context of all these four edge-bit selection strategies we will employ the hard decision bit vector b̂(i−1) as the bit vector b(i−1) in order to reduce the search space of the GA, although this is a suboptimum strategy. Nevertheless, in a low-BER 1915 scenario we may assume that the vector b̂(i−1) is close to a perfect estimate. Let us now describe the four different edgebit selection strategies in detail. According to the first strategy (S1), the SEB vector b(i−1) will be set to the hard decision vector b̂(i−1) . Hence, in Equation 14 b̂(i−1) will replace the vector b(i−1) and hence we will maximize the following function: Ω(b(i) , b̂(i+1) ) = exp{− M m=1 is toggled according to the mutation probability used. Hence, (i) the initial generation for the vector bp (0) can be created according to: (i) b(i) p (0) = MUTATION[bM RC ]. Therefore, the objective function to be maximized for the strategies S3 and S4 can be expressed as: (i−1) Z(i) m − Rm [1]Wm Ab̂ −Rm [0]Wm Ab(i) − −RTm [1]Wm Ab(i+1) 2 }, Ω(b(i) ) = (i+1) (0) = MUTATION[b̂M RC ] b(i+1) p (15) (16) p = 1, . . . , P ; (17) Initialisation (i−1) S1, S2, S3 and S4: b̂p,SEB (0) = b̂(i−1) (21) = M U T AT ION [b̃M RC ] S1: (i+1) b̃p,EEB (0) = M U T AT ION [b̃M RC ] (i+1) S2: b̃p,EEB (0) (19) (i+1) b(i+1) = b̂M RC . S1: (i) b̃p (0) S2: b̃p(i) (0) The philosophical difference between Equations 16, 17 and Equations 18, 19 is that the MRC output biM RC used in Equation 16 for initialization has been replaced by biGA , which is a randomly initalised K-bit vector, subjected to no mutation. ¿From Equation 15 we can observe that it requires a GA assisted search for the best individual in a space of 22K elements, which requires a larger population size P and a higher number of generation Y , than that necessitated by the search space of 2K elements required by the synchronous system which only has to consider a K-bit vector. According to the third strategy S3, we will reduce the size of the search space having 22K elements to a search space of 2K elements. This is achieved by invoking a hard decision both for the vector b(i+1) and for the vector b(i−1) . Explicitly, according to strategy S3, the vectors b(i+1) and b(i−1) are given by: (20) (i+1) y = 0 (18) b(i−1) = b̂(i−1) , (i−1) Z(i) m − Rm [1]Wm Ab̂ Start where the subscript p indicates the individuals’ index in the population of the GA, and (0) refers to the initial generation of the GA. According to the second strategy S2, we also employ Equation 15 as the function to be maximized. However, in order to obtain a higher grade of diversity for the individuals of the GA invoked for finding the most likely K-dimensional vector b(i) , we randomly initialized the K-dimensional vector b(i) and hence the initial population associated with the 0th generation can be expressed as: (i+1) (0) = MUTATION[b̂M RC ]. b(i+1) p M m=1 (i) (i) b(i) p (0) = b̂GA , exp{− −Rm [0]Wm Ab(i) − RTm [1]Wm Ab̂M RC 2 }. (24) while the GA’s initial population is given by: b(i) p (0) = MUTATION[b̂M RC ], (23) (i) (i+1) (i) = b̃GA (i+1) = M U T AT ION [b̃M RC ] (i) S3: b̃p (0) = (i+1) S3: b̃p,EEB (0) S4: b̃p(i) (0) = M U T AT ION [b̃M RC ] (i+1) S4: b̃p,EEB (0) = b̂M RC = (i) b̃GA (i+1) b̂M RC (i) (i+1) Fitness Value Evaluation y = 1 Is Decision taken y = Y ? End Create Mating Pool Uniform Crossover Binary Mutation (i) Furthermore, we randomly initialize the population bp (0) us- ing no mutation, which can be expressed as: (i) b(i) p (0) = bGA . Finally, according to our fourth strategy S4, the vectors b(i+1) and b(i−1) are set to the same value as in the context of strategy S3 expressed in Equation 20 and 21. However, as in the context of the synchronous MC-CDMA system, we adopted biased initialization for creating the individuals of the initial population, where each bit of the MRC’s output vector 0-7803-8521-7/04/$20.00 © 2004 IEEE Fitness Value Evaluation (22) Elitism y = y+1 Figure 2: A flowchart depicting the structure of a genetic algorithm assisted MUD aided MC-CDMA base station receiver. 1916 To elaborate a little further, Figure 2 shows the flowchart of the GA assisted MUD, which follows the philosophy of [3, 15, 16]. Having described the four different edge-bit generation strategies, let us now investigate their performance in the next section. 10-1 BER 3. PERFORMANCE OF GA ASSISTED MUD AIDED ASYNCHRONOUS MC-CDMA Parameters Modulation scheme Spreading code Number of subcarriers M subcarrier spreading gain N Total spreading gain M N GA’s selection method GA’s mutation method GA’s crossover method GA’s mutation probability pm GA’s crossover probability pc Mating pool size T Elitism Incest Prevention Value BPSK WALSH 4 8 32 Fitness-proportionate Standard binary mutation Uniform crossover 0. 1 1 5 Yes Yes Table 1: The basic simulation parameters used by the GA assisted MUD aided MC-CDMA system 10 K=15 0 10-1 -2 BER 10 10 K=15 100 10 -2 10-3 10 single user S1 P=60 S2 P=60 S3 P=60 S4 P=60 -4 1 2 3 4 8 7 6 5 The Number of generations Y 9 10 11 12 Figure 4: The GA assisted MC-CDMA MUD’s BER performance as a function of the number of generations Y . Four different GA-aided edge-bit detection strategies were adopted for approaching the optimum MUD’s performance and the number of users supported was K = 15. The population size was P = 40. ¿From Figure 5 we can observe that the GA assisted MUD is capable of reducing the complexity imposed by a factor of 6 × 1010 in comparison to that of Verdu’s optimum MUD, when the number of users K is 15, suggesting that the GA assisted MUD has the potential of significantly reducing the complexity of the optimum MUD. Finally, Figure 6 portrays the achievable BER performance in conjunction with R = 21 turbo codes. From this figure, we can observe that the system required a complexity on the order of O(P · Y ) = O(200) for approaching a near-single-user performance. -3 10 4. CONCLUSIONS AND FUTURE WORK -4 -5 10 In conclusion, the GA assisted MUD is capable of significantly reducing the detection complexity in comparison to Verdu’s optimum MUD. Our future work will comparatively study the performance versus complexity trade-offs of GA versus MAlgorithm [19] based MUDs. single user S1 P=60 Y=10 S2 P=60 Y=10 S3 P=60 Y=10 S4 P=60 Y=10 0 5 10 Eb/N0 [dB] 15 20 Figure 3: The GA assisted MC-CDMA MUD’s BER performance. Four different GA-aided edge-bit detection strategies were adopted for approaching the optimum MUD’s performance and the number of users supported was K = 15. The population size was P = 60 and the number of generations was Y = 10. From Figure 3 we can observe that strategy S4 is capable of achieving a better performance than the other strategies. By studying this figure, we can infer that the biased initialization strategies, namely S1 and S4 outperformed the random initialization strategies of S2 and S3. Figure 4 shows the performance of the GA assisted MUD as a function of the number of generations Y . From this figure, we may conclude that strategy S4 converges fastest to the single-user performance. 0-7803-8521-7/04/$20.00 © 2004 IEEE 1917 5. REFERENCES [1] R. Prasad and S. Hara, “Overview of multicarrier CDMA,” IEEE Communications Magazine, pp. 126–133, December 1997. [2] R. Prasad and S. Hara, “Overview of multi-carrier CDMA,” in Proceedings of the IEEE International Symposium on Spread Spectrum Techniques and Applications (ISSSTA), (Mainz, Germany), pp. 107–114, 22–25 September 1996. [3] L. Hanzo, L. L. Yang, E. L. Kuan, and K. Yen, Single- and Multi-Carrier DS-CDMA. John Wiley and IEEE Press, 2003, 1060 pages. [4] L. Hanzo, M. Münster, B. J. Choi, and T. Keller, OFDM and MC-CDMA. John Wiley and IEEE Press, 2003. 100 1010 10 9 K=15 -1 10-2 10 BER Factor of complexity reduction 1011 8 10 7 10-4 10 10 6 10 10 12 14 18 16 Number of users K 10 20 -3 single user P=20 Y=10 P=30 Y=10 P=40 Y= 5 P=50 Y= 6 -5 0 10 5 15 Eb/N0 [dB] 3K Figure 5: The complexity reduction factor of P2×Y was defined as the ratio of the number of objective function computations required for approaching the single-user bound at a BER of 10−3 , in comparison to Verdu’s optimum MUD when communicating over an asynchronous environment, where P is the population size, and Y is the number of generations, while K is the number of users supported. Figure 6: BER performance of the S4 GA-assisted MUD designed for asynchronous MC-CDMA assisted by R = 21 rate, constraint length v = 4 turbo coding using 4 iterations, when the number of users supported was K = 15. The number of generations was Y = 5, 6 or 10 and the population size was P = 20, 30, 40 and 50. [5] L. Hanzo, W. Webb, and T. Keller, Single- and Multicarrier Quadrature Amplitude Modulation. John Wiley & Sons, Ltd, 1994. [15] K. Yen and L. Hanzo, “Hybrid Genetic Algorithm Based Multiuser Detection Schemes for Synchronous CDMA Systems,” in Proceedings 51st IEEE Vehicular Technology Conference, (Tokyo, Japan), pp. 1400–1404, 18 May 2000. [6] J. Bingham, “Multicarrier modulation for data transmission: An idea whose time has come,” IEEE Communications Magazine, pp. 5–14, May 1990. [7] S. Weinstein and P. Ebert, “Data Transmission by frequency-division multiplexing using the discrete Fourier transform,” IEEE Transcations on Communications Technology, vol. 19, pp. 628–634, Oct 1971. [8] S. L. Miller and B. J. Rainbolt, “MMSE Detection of Multicarrier CDMA,” IEEE Journal on Selected Areas in Communications, vol. 18, pp. 2356–2362, Nov 2000. [9] P. Zong, K. Wang, and Y. Bar-Ness, “Partial Sampling MMSE Interference Suppression in Asynchronous MultiCarirrer CDMA System,” IEEE Journal on Selected Areas in Communications, vol. 19, pp. 1605–1613, August 2001. [10] X. Gui and T. S. Ng, “Performance of Asynchronous Orthogonal Multicarrier CDMA System in Freqencey Selective Fading Channel,” IEEE Transactions on Communications, vol. 47, pp. 1084–1091, July 1999. [16] K. Yen and L. Hanzo, “Genetic algorithm assisted joint multiuser symbol detection and fading channel estimation for synchronous CDMA systems,” IEEE Journal on Selected Areas in Communications, vol. 19, pp. 985 –998, June 2001. [17] K. Yen and L. Hanzo, “Genetic Algorithm Assisted Multiuser Detection in Asynchronous CDMA Communications,” in Proceedings of the IEEE International Conference on Communications, vol. 3, pp. 826 –830, 2001. [18] S. Verdú, Multiuser Detection. Cambridge Press, 1998. [19] L. Wei, L. K. Rasmussen, and R. Wyrwas, “Near Optimum Tree-Search Detection Schemes for Bit-Synchronous Multiuser CDMA Systems over Gaussian and Two-Path Rayleigh-Fading Channels,” IEEE Transactions on Communications, vol. 45, pp. 691–700, June 1997. [11] M. Schnell and S. Kaiser, “Diversity Considerations for MC-CDMA Systems in Mobile Communications,” in Proceedings of IEEE ISSSTA 1996, pp. 131–135, 1996. [12] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. ISBN 0201157675, MA USA: Addison-Wesley, August 2001. [13] M. Mitchell, An Introduction to Genetic Algorithms. Cambrdige, Massachusetts: MIT Press, 1996. [14] M. J. Juntti, “Genetic Algorithms for Multiuser Detection in Synchronous CDMA,” IEEE International Symposium on Information Theory, p. 492, 1997. 0-7803-8521-7/04/$20.00 © 2004 IEEE 1918