Performance of Some Metaheuristic Algorithms for Multiuser Detection in TTCM-Assisted Rank-Deficient SDMA-OFDM System

Multiinput-Multioutput Orthogonal Frequency Division Multiplexing (MIMO-OFDM) [1] is considered as candidates for future 4G broadband wireless services. Among various topics related to MIMO-OFDM technologies, Space Division Multiple Access (SDMA) [2] based OFDM communication invoking Multiuser Detection (MUD) techniques has recently attracted intensive research interests. In SDMA MIMO systems the different users transmitted signals are separated at the base-station (BS) using their unique, user-specific spatial signature, which is constituted by the -element vector of their channel transfer function between the user's single transmit antenna and the different receiver antenna elements at the BS, upon assuming flat fading channel conditions in each of the OFDM subcarriers. A variety of MUDs [3, 4] have been proposed for separating different users at the BS on a per-subcarrier basis. The most popular among them is constituted by the Minimum Mean Squared Error (MMSE) MUD and was found to give poor performance. ML detection gives the best performance having dramatically increased computational complexity. By incorporating Forward Error Correction (FEC) schemes such as Turbo Trellis Coded Modulationb (TTCM) [5], the achievable performance can be further improved.

In the existing literature, although there are a number of papers dealing with optimization-based approaches for MIMO-MUD, metaheuristic approaches still remain largely unexplored. Metaheuristics are general high-level procedures that coordinate simple heuristics and rules to find good (often optimal) approximate solutions to computationally difficult combinatorial optimization problems [6]. In the context of SDMA multiuser MIMO OFDM systems, none of the known classic multi user detectors allow the number of transmitters ( ) to be higher than the number of receivers, which is often referred to as an overloaded scenario, owing to the constraint imposed by the rank of the MIMO channel matrix. Against this background, in this paper we propose two computationally efficient metaheuristic algorithms based on ABC [7‐11] and PSO [12‐15] for multiuser detection in SDMA-OFDM systems, which provide an effective solution to the multiuser MIMO detection problem in the above-mentioned high-throughput rank-deficient scenario. Both ABC and PSO are efficient stochastic optimization tools with the capability of avoiding local minima, a feature not present in gradient search-based nonlinear optimization methods. The methods proposed approach the optimum performance of the ML detector. Finally, the computational complexity of the proposed schemes is significantly lower than that of the optimum ML system, especially in high-throughput scenarios.

Our major contributions in this paper are (i) the development of two relatively accurate, computationally efficient metaheuristic algorithm suitable for multi user detection in SDMA-OFDM system; (ii) a thorough analysis of the performance of the proposed algorithms under both fully loaded and overloaded scenario; (iii) computational complexity comparison of the proposed algorithms with existing MUDs such as ML and MMSE. From the analysis it is found that the ABC- and PSO-based methods outperform the existing MMSE- and GA-based MUDs. The structure of this paper is as follows. Section 2 provides a description of the related works. The SDMA MIMO system model is described in Section 3, while the proposed MUDs based on ABC and PSO are explained in Section 4. Our simulation results are provided in Section 5, while the associated complexity issues are discussed in Section 6. Our final conclusions are summarized in Section 7.

Multi User Detection in SDMA-OFDM has drawn significant research interest in recent years. Among the various MUDs, Least Square (LS) and MMSE exhibit the lowest complexity, but they suffer from performance loss. The nonlinear MUDs such as SIC and PIC [16] are prone to error propagation. ML detector was found to give best performance at the cost of dramatically increased computational complexity. The performance of numerous known classic MUD techniques such as Vertical Bell Labs Layered Space-Time architecture (V-BLAST) [17] and the QR Decomposition combined with the M-algorithm (QRD-M) [18] will fail in the overloaded scenario where the number of users exceeds the number of receivers. Damen et al. [19] proposed a powerful sphere decoding (SD) algorithm which was suitable for overloaded MIMO MUD. The derivatives of SD such as Optimized Hierarchy Reduced Search Algorithm (OHRSA) [20] were proposed which are capable of achieving ML performance at a lower complexity. Other MUD techniques based on minimum bit error rate (MBER) are also proposed. GA-based MUD has been proposed by Juntti et al. [21] and Wang et al. [22] where the analysis was based on the Additive White Gaussian Noise (AWGN) channel. Its employment in Rayleigh fading channels was considered by Yen and Hanzo in [23]. In 2004, Jiang and Hanzo proposed GA-assisted TTCM-S DMA-OFDM [24].

Inspired by the work of Hanzo we propose ABC and PSO-based stochastic optimization algorithms and show that they have better computational efficiency, convergence characteristics, and BER performance than MMSE and GA algorithm for the multi user detection problem in SDMA-OFDM system.

Figure 1 shows the MIMO OFDM system model in which there are mobile users each having single transmit antenna and the Base station receiver has receiving antennas. The OFDM signal at the transmitter is obtained by Inverse Fast Fourier Transform (IFFT), and Fast Fourier Transform (FFT) is done to detect the signal at the receiver. The th subcarrier of th OFDM symbol of th receive antenna is given by

where is the transmitted data symbol, is the additive white Gaussian noise at the th receive antenna. is the frequency domain channel coefficient between th transmitting antenna and th receiving antenna. We can write (1) in matrix form as

where is dimensional received signal, is dimensional channel matrix, is dimensional transmitted signal, and is a dimensional noise vector. Transmitted symbols of each user are estimated by using MMSE-based MUD. It is done by linearly combining the signal from each received antenna with the weight matrix resulting in

MMSE-based weight matrix is given by

where is the noise variance.

The OFDM modem used in our simulations employed 128 subcarriers. The half-rate TTCM code employed two Recursive Systematic Convolutional (RSC) component codes having a constraint-length of , and the standard 124-bit turbo code interleaver was also used. The octally represented RSC generator polynomial of (7 5) was used. The Minimum Mean Square Error (MMSE) algorithm was used for creating the ABCs initial population. Simulations were carried out on a PC with 2.99 GHz dual core AMD opteron processor and 2.5 GB RAM using Matlab 7.2.0.232(R2006a).

In this section, we characterize the achievable performance of the proposed TCM-assisted concatenated MMSE-ABC/PSO multiuser detected SDMA-OFDM system. The various parameters used in the ABC and PSO MUDs are summarized in Table 1. The channel is assumed to be OFDM symbol-invariant, in which the taps of the impulse response are assumed to be constant for the duration of one OFDM symbol, but they are faded at the beginning of each OFDM symbol. The simulation results were obtained using a 4QAM scheme. The Bit Error Rate (BER) performance of the TTCM-assisted MMSE-ABC/PSO-SDMA-OFDM system employing a 4QAM scheme is given in Figure 3, where six users are supported with the aid of six receiver antenna elements. The performance of the TCM-aided MMSE-detected SDMA-OFDM system, the TCM-assisted optimum ML-detected system, is also provided for reference. It is observed from Figure 3 that the BER performance of the TTCM-assisted MMSE-SDMA-OFDM system was significantly improved with the aid of the ABC and PSO having a sufficiently large food source (population) size or a larger number of iterations . This improvement was achieved, since a larger food source may contain a higher variety of symbol individuals. Similarly, a larger number of iterations imply that, again, a more diverse set of individuals may be evaluated, thus extending the ABC and PSOs search space, which may be expected to increase the chance of finding a lower-BER solution. The proposed TTCM-assisted MMSE-ABC-SDMA-OFDM technique, results in 1.5 dB degraded performance at 10⁻⁴ BER in comparison with ML. However, in comparison to MMSE, it shows 4 dB better performance, and with GA it shows 1 dB better performance. Also the proposed MMSE-PSO-SDMA technique results in 2 dB degraded performance at 10⁻⁴ BER in comparison with ML. It shows 3 dB better performance in comparison to MMSE. In comparison with MMSE-GA-SDMA-OFDM technique it shows 0.5 dB better performance.

In Figure 4 we provide the BER performance recorded in the overloaded scenario, where transmit antennas and receiver antennas were employed. In overloaded scenarios, the weight matrix calculated by the MMSE algorithm becomes a singular matrix, which will lead to a theoretically unresolvable detection problem. By contrast, the system aided by the ABC/PSO was capable of attaining an undistinguishable performance from that of the optimum ML detected arrangement in the overloaded scenario of Figure 4. Again a 1 dB and 0.5 dB gain were obtained, when comparing ABC-MUD and PSO-MUD, respectively, with GA-MUD at BER.

Figures 5 and 6 show the simulation results for MIMO OFDM systems with different QAM constellations, that is, 16-QAM and 64-QAM. High-order constellations assure more transmitted bits per symbol. In the case of high-order constellations, the points must be closer together and are thus more susceptible to noise and other corruption, which results in a higher BER, and so high-order QAM can deliver more less reliable data than lower-order QAM. From Figures 5 and 6, it is clear that the proposed schemes outperform the existing GA-based suboptimal method.

As an investigation on the ABCs convergence characteristics, in Figure 7 the performance of the rank deficient TTCM-aided MMSE-ABC-SDMA-OFDM system is illustrated, at a fixed value of 2 dB. More specifically, in Figure 7 the population size was varied with the number of iterations fixed at , while in Figure 8 the effect of a different number of iterations was evaluated at a fixed population size of . Explicitly, as or increases, a consistently reduced BER is observed, which approaches the optimum ML performance. The convergence of the proposed algorithm in different conditions is illustrated in Figure 9. From Figure 9 it can be concluded that as the population size increases, the algorithm produces better results. However, after a sufficient value for colony size, any increment in the value does not improve the performance of the ABC algorithm significantly.

We will quantify the complexity imposed in terms of the number of metric computations required by the process as follows. ML MUD requires number of metric computations for finding the optimum solution, namely, the most likely transmitted -user vector, where denotes the number of bits per symbol. In the case of our proposed ABC and PSO MUDs, maximum of ( ) metric evaluations are required, since number of -symbol vectors are evaluated during each of the number of iterations. In Figure 10, we compare both the ML- and the ABC/PSO-aided schemes in terms of their complexity, that is, the number of metric computations. As shown in Figure 10, the ML-aided system imposes an exponentially increasing complexity on the order of , when the number of users increases, while the complexity of the ABC- and PSO-aided systems required for maintaining a near-optimum performance increases only slowly. CPU time required for various MUD algorithms is illustrated in Table 2. We can see that the proposed algorithms (ABC and PSO) converge to a better solution in minimum time.

In order to characterize the advantage of the ABC-MUD scheme in terms of the performance-versus-complexity tradeoff, in Table 3 we summarize the computational complexity imposed by the different MUDs assuming an value of 3 dB, where the associated complexity was quantified in terms of the number of complex additions and multiplications imposed by the different MUDs on a per-user basis. As observed in Table 3, the complexity of the ML MUD is significantly higher than that of the MMSE MUD or the ABC MUD, especially in highly rank-deficient scenarios. By contrast, the ABC MUD reduced the BER by up to five orders of magnitude in comparison to the MMSE MUD at a moderate complexity.

In this paper, we have proposed two algorithms to solve multi user detection problem in SDMA-OFDM system using ABC and PSO methods. ABC and PSO having the advantages of simple mathematical model, lesser implementation complexity, resistance to being trapped in local minima, and convergence to reasonable solution in lesser iterations makes them suitable candidates for real-time wireless communications systems. The performance analysis of these algorithms shows a significant improvement in the BER performance and in convergence characteristics compared to the GA-based algorithm, a metaheuristic method already available in the literature. These algorithms show promising results when compared to the optimal ML and traditional MMSE detectors. ABC- and PSO-optimized MIMO symbol detection mechanisms approach near-optimal performance with significant reduction in computational complexity, especially for complex systems with multiple transmitting antennas, where conventional ML detector is computationally expensive and impractical to deploy. For example, a complexity reduction in excess of a factor of 100 can be achieved by the proposed systems for , as evidenced by Figure 10. Although MMSE detector offers a reduced complexity, its BER performance is inferior to the proposed detectors. Furthermore, the proposed techniques are capable of achieving an excellent performance even in the so-called overloaded systems, where the number of transmit antennas is higher than the number of receiver antennas.