In the direct sequence/code division multiple access (DS/CDMA) technology, all the users share the entire frequency band available at the same time. This is possible due the spreading sequence with short chip period, which is used in order to spread the user information along all the available bandwidth spectrum, as well as serves as an identification code for each user, providing some level of multiple access interference (MAI) immunity. The application of sequences with low cross correlation allows to support a considerably number of users simultaneously, as well as the possibility of operation in the asynchronous configuration mode, meting the requirements of wireless mobile communication uplink. However, as the system loading1 increases, the utilization of sophisticated detectors become necessary, such as multi user detection (MuD) (Verdú, 1998), in such a way to obtain a reasonable separation among the several user’ signals, each one under an intense multiple access interference level generated by K − 1 interfering users. The best performance is achieved by the optimum multiuser detector (OMuD) or maximum likelihood (ML) detector, which complexity grows exponentially with the number of users, O(2K)O(2K) (Verdú, 1998).
After the Verdú’s revolutionary work, a wide number of suboptimal MuD approaches have been proposed in an attempt to get high performance multiuser receivers with low complexity. Among the suboptimal MuDs, the linear multiuser detectors, such as decorrelator (Verdú, 1986) and Minimum Mean Square Error (MMSE) (Poor & Verdu, 1997), as well as the nonlinear MuDs, such as interference cancelers (Patel & Holtzman, 1994), zero-forcing (Duel-Hallen, 1995), among others have been widely discussed in literature in the past two decades. More recently, a new class of multiuser detection approach has been successfully proposed with increasing gain in complexity-performance trade-off: the heuristic-based multiuser detectors ( Ciriaco et al., 2006, Ergun and Hacioglu, 2000, Hijazi and Natarajan, 2004 and Lim and Venkatesh, 2003).
In the last decade, proposals based on heuristic methods have been reported to solve the MuD problem, getting performance close to the ML performance with polynomial computational complexity (Abrão et al., 2009 and Ergun and Hacioglu, 2000). The use of heuristic search algorithms is motivated by the fact that optimization problems related to wireless communication systems results in non-polynomial (NP-hard) problems, e.g., MuD optimization problem (Verdú, 1989). So, from a practical point-of-view, the challenge is to obtain satisfactory results for these high computational complexity problems in a polynomial time. This requirement comes from the fact that detection stage must be provided in a short time under a limited computational resources in order to met the real time wireless communication applications and services. Meting this requirement the wireless communication system is able to be implemented on modern digital signal processors platforms.
Furthermore, the input parameters optimization of the heuristic-based algorithms is of paramount importance in order to obtain reliable results. Specifically on MuD optimization problem, in Abrão, Oliveira, Angélico, and Jeszensky (2010) a detailed study about the input parameters of the particle swarm heuristic algorithm applied to DS/CDMA multiuser detection problem has been conducted. Hence, present work aims to develop an input parameters analysis for the ant colony optimization (ACO) heuristic-based algorithm applied to DS/CDMA multiuser detection problem.
Previous results shows the heuristic based algorithms application in several wireless communications optimization problems has achieved great success in the performance-complexity tradeoff. In the multiuser detection context, the heuristic based algorithms (Heur-MuD) most commonly used includes the evolutionary programming (EP) based algorithms, specially the genetic algorithms (GA) (Ciriaco et al., 2006 and Ergun and Hacioglu, 2000), particle swarm optimization (PSO) (de Oliveira et al., 2006 and Zhao et al., 2006), ant colony optimization (ACO) (Xu, Yang, & Hanzo, 2007) and the local search method (LS) (Lim and Venkatesh, 2003 and Oliveira et al., 2009).
The first algorithm using the ACO heuristic approximation was proposed in 1991 by Colorni, Dorigo, and Maniezzo (1991), and since that many variant algorithms were described in the literature. The ACO intelligence has achieved great success in solving combinatorial optimization problems that had arisen in many areas. For example in power electronics field, variants of this heuristic method, such as elitist ant system (EAS), rank-based ant system (ASrank) and max–min ant system (MMAS) just to name a few, have been deployed, for instance, in reactive power controls (Abbasy & Hosseini, 2007). Recently, this ant behavior-based technique has been widely applied to multiple access multiuser detection (Hijazi and Natarajan, 2004, Lai and Lain, 2005, Xu et al., 2007 and Zhao et al., 2010).
The computational complexity of DS/CDMA ACO multiuser detection was analyzed in Hijazi and Natarajan (2004), noting that with a few iterations the ACO-MuD algorithm was able to reach the near-optimal performance spending only a small fraction (≈5%) of computational effort necessary to perform an exhaustive search. In Hijazi and Natarajan (2005), a similar performance is reached considering different received powers for the users. Also, the lower computational complexity for the ACO algorithm regarding to genetic algorithm has been evidenced. Besides, under the same channel and system operation conditions the authors have been shows the the worse performance of the GA-MuD regarding that obtained with ACO-MuD.
In a more complex system and environment, Lain and Lai (2007) have explored the joint receiver diversity and ACO multiuser detection techniques. In that work, authors have been shown the near-far robustness effect achieved by ACO algorithm, differently from GA algorithm, which performance is degraded under severe NFR condition. Furthermore, Xu et al. (2007) analyzes the ACO-MuD applied to multi carrier DS/CDMA systems (MC-DS/CDMA). ACO-MuD in this context is able to reach the optimal performance, regardless the adopted number of carriers. Under this promising performance, the authors have carried out complexity analysis and verified that the ACO-MuD complexity seems the conventional detector, even under a system loading of 100%.
An heuristic ACO-based multiuser detector for space–time block coding (STBC) systems with receiver diversity was proposed in Hongwu (2009). This STBC ACO-MuD applies the Pareto-optimally (PO) concept in the pheromone updating step, selecting only the ants with the best results in that iteration. Numerical results have indicated a very close performance to the optimal one; importantly, authors have demonstrated a very low computational complexity for the STBC ACO-MuD. Furthermore, the proposed ACO-MuD presented a performance much better than GA-MuD at the same operation system and channel conditions; also, the STBC ACO-MuD does not present the bit error rate saturation (BER-floor), a degradation performance effect that occurring at high SNR region.
This work is divided in seven parts. Besides this introductory section, the adopted system model is described in Section 2. In Section 3, the ACO-based heuristic algorithm applied to MuD detection is minutely exploited, while in Section 4, an input parameters optimization methodology was proposed for the algorithm, considering different channel conditions. An analysis on the number of iterations (Golub & Loan, 1996) computed by the ACO-MuD algorithm is carried out in Section 5. The numerical results for the performance of ACO-MuD detector are presented in Section 6. Finally, the main conclusions of this work are offered in Section 7.
