مطالعه مقایسه ای در الگوریتم های هیوریستیک : الگوریتم ژنتیک و الگوریتم توزیع حاشیه ای تک متغیره در سیستم های ارتباطی فضایی تسهیم شده

A performance comparison of genetic algorithm (GA) and the univariate marginal distribution algorithm (UMDA) as decoders in multiple input multiple output (MIMO) communication system is presented in this paper. While the optimal maximum likelihood (ML) decoder using an exhaustive search method is prohibitively complex, simulation results show that the GA and UMDA optimized MIMO detection algorithms result in near optimal bit error rate (BER) performance with significantly reduced computational complexity. The results also suggest that the heuristic based MIMO detection outperforms the vertical bell labs layered space time (VBLAST) detector without severely increasing the detection complexity. The performance of UMDA is found to be superior to that of GA in terms of computational complexity and the BER performance.

Recent advances in wireless communication lead to the multiple input multiple output (MIMO) communication systems employing simultaneous use of antenna arrays at both the transmitter and the receiver (Barbarossa, 2005 and Tse and Viswanath, 2005). The MIMO architecture exploits multipath propagation to improve the link capacity by establishing multiple parallel channels operating simultaneously in the same frequency band and at the same transmitted power. In contrast to the logarithmic bandwidth efficiency growth obtained with single antenna systems, the capacity growth for MIMO systems is linearly related with the number of antennas. An information theoretic analysis on the capacity of MIMO systems was presented in Telatar (1999) assuming flat, quasi-static and spatially independent Rayleigh fading environment with known channel state information at the receiver. The study concluded that the capacity of multiple antenna channels increases linearly with the smaller of the number of transmit and the receive antennas. The received signal at a particular receive antenna of a MIMO system is a superimposed representation of the signals transmitted from the multiple transmit antennas. If the MIMO system has N transmit antennas and uses a signal constellation XX of size B=2bB=2b for b bits per symbol, the exhaustive search by maximum likelihood (ML) detection has a computational complexity O(BN)O(BN); hard to implement when B and N are large. Various linear and non-linear suboptimal MIMO detectors are proposed and are well documented in the literature such as zero-forcing (ZF) (Schneider, 1979), minimum mean square error (MMSE) (Honig et al., 1995) and vertical bell labs space time (VBLAST) detector (Golden et al., 1999). These schemes are computationally less expensive but with fairly degraded performance as compared to the ML decoder. The sphere decoder (SD) that searches for optimum solution in the vicinity of the received signal vector is discussed in Fincke and Pohst (1985), Damen et al. (2000), Hochwald and Brink (2003). The average complexity of the SD in general is exponential in the problem dimensions N, but could be dominated by the polynomial terms when N is small and the corresponding signal to noise ratio (SNR) is chosen sufficiently large (Hassibi and Vikalo, 2005). A performance comparison between two classes of search algorithms namely the evolutionary algorithms (EAs) and the estimation of distribution algorithms (EDAs) is provided in this paper. The algorithms are applied to improve the performance of non-linear MIMO detectors without significantly increasing the computational complexity. EAs are one of the most successful meta-heuristic techniques for solving optimization problems taking their inspiration from natural selection and survival of fittest in the biological world. Genetic algorithm (GA) is one important member of this class of optimization algorithms that will be applied to decode the composite received signal in a MIMO system. GA operates on an initially generated subset of the search space and subsequently weeds out the poor solutions based on competitive selection. The population size should be carefully selected because it directly effects the computation time and the optimality achieved. This is followed by the processes of recombination and mutation to generate a new set of probable solutions (offspring) replacing the discarded poor parents. The new set of offspring is biased and directs the search mechanism towards the regions of the search space for which good solutions are already observed. This improves the quality of the output generated after each iteration of the search method. While searching for the optimal solution in time sensitive applications the EAs are desired to achieve satisfactory performance within a reduced number of iterations. Unlike EAs the EDAs do not use crossover or mutation operators, considered primary tools for GA based optimization. Instead, EDAs explicitly extract global statistical information from the selected solutions and subsequently build a probability model of promising solutions based on the extracted information. New solutions are sampled from the model thus built. In this paper univariate marginal distribution algorithm (UMDA) from the family of EDAs is chosen and the performance of the algorithm is analyzed as a MIMO decoder. A comparison of the BER performance of UMDA with the BER performance of GA is also provided in the simulation results. The rest of the paper is organized as follows. Section 2 provides the spatial multiplexed system model and sets-up the MIMO detection problem for flat, quasi-static and spatially independent Rayleigh fading environment. A brief overview of existing MIMO detectors is given in Section 3. Sections 4 and 5 detail the MIMO detection based on GA and UMDA, respectively. BER performance analysis of the proposed detectors is discussed in Section 6 followed by the conclusion.

In this paper a simulation based performance analysis of GA and UMDA while operating as symbol detectors in multiple antenna communication system is presented. The optimization methods show promising results when employed as decoders in higher order MIMO systems with relatively complex configurations. A major gain is achieved in the reduction of computational complexity by the heuristic algorithms when compared with the traditional ML detection. Although VBLAST decoder has less complexity as compared to the reported heuristic algorithms but the degradation in its BER performance quite obvious. The results also show that a trade off can be made between complexity and optimality in order to incorporate the proposed decoders in practical MIMO systems. Significant performance gain is shown by the proposed methods over the VBLAST detector. The simulation results also suggest that the performance of UMDA, as a MIMO detector, is superior as compared to GA in terms of computational complexity. The UMDA based decoder achieves better BER performance when operating with same computational complexity as that of a GA based decoder. The heuristic algorithms in their simplest and original form have shown a potential in solving the MIMO detection problem. Therefore improved results may be achieved by further tuning of the algorithmic parameters and with the confinement of the search around the initial solution.