Abstract: In this study, a hybrid approach with Ant Colony Optimization (ACO) and Code Filtering System (CFS) is proposed for DS-CDMA multiuser detection. In CFS, the method of Lagrange multipliers is applied to set the threshold in order to make the judgment of the codes of users. Compared with the ACO multiuser detector, the hybrid detector can both filter out the most part of the wrong codes from the output of the ACO multiuser detector and decrease the iteration numbers in the process of hunting the solution. Via computer simulations, it’s shown that the performance of the hybrid detector in reducing bit-error rate and decreasing the computational complexity is much better than that of the ACO multiuser detector and is very close to the performance of the optimum multiuser detector. At the same time, its computational complexity is only 20.7% of the complexity of ACO, which can greatly increase the rate of data processing and enhance the real-time performance of the systems.
INTRODUCTION
Code Division Multiple Access (CDMA) is a new type of technique in mobile communication, which is fit for the demands of a large number of users in the 3G. The demands generally include large system capacity, high baud rate and strong confidential feature. However, it leads to Multiple Access Interference (MAI) due to non-complete-orthogonality among the spreading sequences of different users, which has great influence on the system capacity and decreases the bit error performance of systems. In order to solve the problem of MAI, the method of multiuser detection (MUD) is put forward. In 1986, Verdu first proposed the Optimum Multiuser Detector (OMD) based on Maximum Likelihood Sequence Detection (MLSD) (Verdu, 1986). Although, the OMD can completely eliminate MAI and near-far effect, it has apparent weakness, that is, its computational complexity is equivalent to 2K (K is the number of users), which means that when there are a number of CDMA users, the computational complexity of the system is extremely large and it’s impossible to obtain the results in a short time. Hence, scientists began to find some sub-optimum algorithms, which have been studied and expanded upon a number of works. The sub-optimum detectors can achieve relatively good performance and reduce the computational complexity, such as decorrelator (Paris, 1996) Minimum Mean Square Error (MMSE) detector (Kohli and Mehra, 2007) hopfield neural network detector (Liu et al., 2006) stochastic cellular neural network detector (Wu et al., 2007) non-canonical linearly constrained constant modulus detector (Jiang and Kwak, 2002) Ant Colony Optimization (ACO) multiuser detector (Stuzle and Dorigo, 2002) Population Declining Ant Colony Optimization Detector (PDACO) (Wu et al., 2009) and Mutated Ant Colony Optimization (MACO) detector (Ren et al., 2008) as to balance between system performance and computational complexity.
Among these sub-optimum algorithms, ant colony optimization multiuser detector is applied widely because of fast convergence speed (Yu and Zhang, 2009), little computational complexity and good real-time computation for data processing (Dorigo et al., 2006). However, in the process of the operation, the algorithm often traps into sub-optimum solutions. Although, ACO is much better than conventional detector, it can’t achieve the desired performance for practical application. In fact, we need the approach in which a better solution and a low computation complexity can be obtained. Hence, in this study, a novel hybrid approach with ACO and CFS is brought forward. Different from other sub-optimum detectors, code filtering system can be easily implemented. The two parts of the system include input data and judgment conditions. We can use ACO multiuser detector to obtain a series of sub-optimum solutions as the input data. As for the judgment conditions, according to the theory of OMD proposed by Lupas and Verdu (1989) it can be transformed into an optimization problem with equality constraint. In order to reduce the Bit-Error Rate (BER) of the system, Lagrange multipliers (Scaglione et al., 2000) are applied to solve the optimization problem. The bit-error performance of system mainly lies on the judgment conditions, which can filter out the wrong codes from the input data and correct them without iterations. Besides, the computational complexity is mainly determined by the ACO multiuser detector. Actually the BER performance of input data from ACO doesn’t need to be very good. This can to a great extent decrease the computational complexity of ACO. Therefore, the hybrid approach with ACO and CFS can improve bit-error performance greatly with little computation complexity.
ACO MULTIUSER DETECTOR
Ant colony optimization: The ACO was firstly used to solve the Traveling Salesman Problem (TSP), so we use the TSP as a concrete example to demonstrate the basic principle of ACO.
The problem is that a salesman wants to visit some cities, all of the cities must be visited and each city has to be visited only once. The TSP is used to find a shortest route to visit all of the cities (Dorigo and Gambardella, 1997). The ACO algorithms take inspiration from the foraging strategy of ant species. These ants deposit pheromone on the ground in order to mark some favorable paths that should be followed by other members of the colony. The shorter the path is, the more pheromone the ants deposit. The other member will select the paths on the probability related to the pheromone deposited on the ground.
The main characteristic of ACO is that, after each iteration, the pheromone values are updated by all the M ants that have built the solutions. The pheromone τij(t+1) associated with the edge joining city i and j and at the time t+1, is updated as follows:
| (1) |
| (2) |
where, Δτijk(t, t+1) is the quantity of the pheromone laid on edge (i, j) by ant k from the time t to t+1, ρ is the evaporation rate and m is the number of ants.
In the construction of a solution, ants select the following city to be visited through a stochastic mechanism. When ant k is in city i, the probability that ant k selects the following city j is given as follows:
| (3) |
where, allowedk={0,1,…,n-1} is the serial number of the city permitted to visit by ant k. The parameters α and β control the relative importance of the pheromone versus the heuristic information ηij, which is given by:
| (4) |
where, dij is the distance between city i and j.
ACO multiuser detector: As the speciality of multiuser detection in DS-CDMA system, the ACO algorithms should be adjusted if we want to apply them to the multiuser detection.
Because the K users are independent, without losing generality, we can let each ant travel in the fixed order from the 1st user to the Kth user. In this case, the ants should not decide whether the user has been visited. Hence, the problem of multiuser detection is attributed to TSP. The model of ACO multiuser detection is shown in Fig. 1.
Figure 1a represents the anthill and Fig. 1b represents the place of food. There are K crossings between a and b. The kth crossing represents the kth user (kε[1, K], kεN). Each crossing has two paths which represent two values of each user. The value can only be +1 or -1. The shorter path represents the right value of each user. Hence, finding the right code of each user equals to finding a shortest route in Fig. 1 from a to b.
As there is not any heuristic information, parameters ηij, α and β could be discarded.
| Fig. 1: | The model of ACO multiuser detection |
Because the transmitted information by each user only can be +1 or -1, the probability taking the value of the kth user transmitted decided by the ant m at the time t is given by:
| (5) |
According to the theory of OMD proposed by Verdu, finding the right value from the 1st user to the Kth user equals finding the maximum of the desirability function that is given by:
| (6) |
where, b = [b1, b2 ,…,bK]T is the vector including K elements that represent the value from the 1st user to the Kth user, bkε{-1,+1}. y=[y1, y2 ,…,yK]T is the vector that each element is the output of each user from the corresponding matched filter; A = diag(A1, A2,…, AK) is the diagonal matrix which the diagonal element Ak (kε[1,K], kεN) represents the signal amplitude of the kth user; R= (rij)KxK is the cross-correlation matrix and H= ARA.
Hence, the relation between the quantity of pheromone τij and the desirability function J(b) is given as follows:
| (7) |
where, f is a monotonic increasing function.
Through the rules set above, multiuser detection can be described as a path-choosing problem that can be solved by ACO.
CFS WITH LAGRANGE MULTIPLIERS
Construction of the hybrid detector: The construction of the hybrid detector includes two blocks: sub-optimum algorithm block and CFS block. In the hybrid detector, we use ACO multiuser detector as the sub-optimum detector block to obtain the sub-optimum solution as the input data of the CFS block. The construction of the hybrid detector is shown in Fig. 2.
As shown in Fig. 2, we know that the input data of CFS is the output data from the sub-optimum detector. To select the wrong codes and correct them, we choose Lagrange multipliers to make the judgments.
Assumptions: For a clear and convincing illustration, we need two assumptions:
| • | The average bit-error rate of the output from the sub-optimum detector should be under 0.1. It means that though the output data are not the optimum solution, it’s certain that most codes of input data are correct. For the ACO detector, this assumption is surely satisfied |
| • | The spreading sequences of users have good cross-correlation feature, which means that the cross-correlation matrix R = (rij)KxK satisfies as: |
| Fig. 2: | Construction of the hybrid detector for CDMA multiuser detection |
| (8) |
Basic principles: According to the theory of OMD, the decision of the best solution is based on the value of the desirability function in Eq. 6. The solution whose desirability function has the largest value is the best. Hence, the problem for detection can be attributed to solving the problem of optimization with equality constraints as follows:
| (9) |
The ordinary approach for this type of problem is Lagrange multipliers.
Let:
| (10) |
where, σ is called Lagrange multiplier. To expand Eq. 10, we get:
| (11) |
Make the partial derivation, we have:
| (12) |
We can obtain the correct codes by extracting the solution vector of Eq. 12. However, it’s difficult to solve a system of nonlinear equations, especially impossible when the order of equations is large. So, the approximate approach should be adopted.
Substitute the condition biε{-1,1}, i =1,2,…,K into Eq. 12 and we get the latter part of the equations σ(|bi|-1)|bi|, i = 1,2,…,K is zero regardless what σ really is.
Let:
| (13) |
We know that the output of the group of matched filters is given as Eq. 14:
| (14) |
where, n represents an Additive White Gaussian Noise (AWGN) sequence.
Substitute it to Eq.13. It’s clear that without noise, L(bi) = 0, i = 1,2,…,K. Furthermore, in the condition of AWGN channel, though L(bi), i = 1,2,…,K doesn’t equal to zero strictly, it’s still a number which is close to zero. According to the first assumption, most of the input data which are brought to Eq. 12 are correct.
According to the first assumption, we can see that the probability with more than two wrong codes is quite small and it can be ignored. Hence, it’s reasonable that there are two wrong codes at most in each code set.
There are three situations which are illustrated as follows:
No wrong codes in code set: bi, i = 1,2,…,K are all correct, which means that in the condition of AWGN, L(bi), i = 1,2,…,K are small number close to zero.
One wrong code in code set: Let bk (kε[1, K], kεN) be the wrong code (that’s to say, -bk is the correct code), the other codes are correct. In the condition of AWGN, L(bi), i = 1,2,…,K doesn’t equal to zero strictly, but according to the second assumption, substitute Eq. 8 to 13, the equalities are given as follows:
| (15) |
where, i = 1,2,…,K, i≠k.
| (16) |
from Eq. 15, 16 and 8, we can see that:
| (17) |
where, i=1,2,…,K, i≠k.
Hence, we can judge the wrong codes through calculating the value of |L(bi)|,. The large ones represent wrong codes and the small ones represent right codes.
Two wrong codes in code set: Let, bk1, bk2 (k1, k2ε[1, K], k1, k2εN, k1εk2) are wrong codes, the other codes are correct. According to the second situation, the values of |L(bk1)| and |L(bk2)| are quite larger than the others.
From above, we might calculate the value of each L(bi) if the input data are given and then set a value of threshold c. If the value of L(bi) is greater than c, the code bi is considered to be the wrong code; or else, it’s considered to be a correct one. However, in practice, it’s not enough due to the interference of noise. A pointed pulse of noise added to judgment function L(bi) may break through the judgment threshold c, which leads to the right code being considered the wrong one. To solve the problem, a new judgment condition is needed.
Assume bk (kε[1, K], kεN) is the wrong code, the other codes are all correct and bk= -1. Thus, the correct code -bk = 1. In the condition without noise, we have:
| (18) |
We can see that the judgment function L(bk) and the code bk are same sign. Hence, a new judgment condition can be given as follows:
| (19) |
To make the threshold selection more convenient, it’s better to enlarge the absolute value of judgment function. In this paper, the adjusted absolute value of judgment function is given as follows:
| (20) |
where, a is a constant which is greater than 1.
Hybrid approach with ACO and CFS for CDMA detection: As illustrated above, the hybrid approach with ACO and CFS is represented by the following steps:
| Step 1: | Initialize the parameters, including PN code of each user, cross-correlation matrix R = (rij)KxK, amplitude matrix A = diag(A1, A2,…, AK) and the input data created by ACO multiuser detector |
| Step 2: | Set a threshold c as the judgment condition |
| Step 3: | Calculate the value of L’(bi), i = 1,2,…,K and compare to the threshold c. If the value of L’(bi) is larger than c, the corresponding code bi is considered wrong, turn to step 4; or else, bi is considered correct and turn to step 5 directly |
| Step 4: | Judge the sign of L(bi)bi, i = 1,2,…,K, if the sign is positive, the corresponding code bi is considered wrong, let bi = -bi; or else, bi is considered correct |
| Step 5: | Let i = i+1. If i<K, return to STEP 3; or else, stop the algorithm |
For the hybrid detector, it’s important to set the threshold to make the judgment. If the threshold is set too little, the absolute values of some right codes’ judgment functions may be greater than the judgment threshold because of the interference of the channel noise and the corresponding right codes will be regarded as the wrong codes. On the contrary, if the threshold is set too large, some wrong codes may not be filtered out. The relationship between the judgment threshold and the bit-error rate of the hybrid detector is shown in Fig. 3, which is in the condition of SNR = 0 dB.
| Fig. 3: | Bit-error rate vs. judgment threshold |
RESULTS AND DISCUSSION
Here, the simulation results are presented in order to emphasize the improvement effects in bit-error performance and computational complexity by the hybrid detector and make the comparison with the other detectors.
In order to evaluate the performance of the hybrid detector with ACO and CFS, a CDMA system using it is designed as Fig. 4.
First, the bit-error performance is discussed. In our computer simulation, as shown in Fig. 2, the sub-optimum algorithm is applied by Simple Ant-Colony Optimization (SACO), which there is only one ant in the colony for path searching and the code filtering system is applied by Lagrange multipliers. Based on the system described in Fig. 4, the performance of Conventional Detector (CD), Optimum Multiuser Detector (OMD), simple ACO detector (SACO), population declining ACO detector (PDACO) (Wu et al., 2009) and the hybrid detector with SACO and CFS with Lagrange multipliers (SACO-LAG) is compared. Considering the high real-time requirement, the iteration number of SACO is set as 10 and SACO in SACO-LAG is only iterated twice.
As shown in Table 1, the value of best judgment threshold is covered from 70 to 80 in this situation and descends with the increase of SNR. Hence, it’s possible to set the range of best judgment threshold by estimating the system signal-noise ratio. Furthermore, it’s shown in Fig. 5 that the BER with SACO-LAG is nearly the same with the BER with SACO itself in the condition of low signal-noise rate, such as -10 to -6 dB. But in the condition of high signal-noise rate (above -4 dB), the system performance by SACO-LAG is much better than SACO. That’s to say, CFS with Lagrange multipliers is fit for high SNR conditions.
| Fig. 4: | The block diagram of the hybrid detector system with ACO and CFS |
| Fig. 5: | Bit-error rate vs. signal-noise ratio |
| Table 1: | The relationship between SNR and best judgment threshold |
In the process of simulation, the number of users K = 10 and each user is distributed a list of 15 bit m sequence as the spreading sequences. The BER versus Signal-Noise Ratio (SNR) curves with equal energy of each user, are shown in Fig. 5. Among them, the curve of SACO-LAG is depicted by setting the best judgment threshold with different SNR conditions shown in Table 1. It’s shown that the BER of the SACO-LAG is much lower than that of the CD, DEC and the SACO with the increase of the signal-noise ratio and is close to the BER of the OMD.
Second, the near-far effect problem is discussed. The BER curves of the first user are compared when its energy is increasing with the energy of the other users unchanged and the results are shown in Fig. 6 when the SNR of the first user is 0 dB.
| Fig. 6: | Bit-error rate vs. near-far ratio |
During the simulation, the judgment threshold of SACO-LAG is set as 75. As shown in Fig. 6, the improvement of BER changes obviously when the E1/Ei =0 dB by the SACO-LAG, which is much better than the other detectors except the OMD. However, in the other conditions, the near-far effect by the SACO-LAG has not been improved much because of the choice of the judgment threshold. It’s effective under the condition of E1/Ei = 0 dB, but the same threshold doesn’t make the BER performance better under the other conditions. Therefore, it’s necessary to set the judgment threshold automatically with the change of the power of each user’s signal.
Third, we discuss the computational complexity of the detectors. The computational complexity of a detector can be measured as the number of multiplications and additions in the process of calculation. The computational complexity CD, SACO, PDACO, SACO-LAG and OMD are compared in Table 2, where the number of users is K and each detects only one bit.
In Table 2, N is the length of the m sequences. In this study, K is set to 10 and N is set to 15. So, the computation complexity of SACO-LAG is 20.7% of the complexity of SACO and only 1.9% of PDACO because of the decreasing the number of iterations and it will be much less than that of OMD when K is even larger.
| Table 2: | Computational complexity comparison |
CONCLUSION
In this study, we have proposed a hybrid approach with ACO and CFS (SACO-LAG) for DS-CDMA multiuser detection. The hybrid multiuser detector can use Lagrange multipliers to filter out the wrong codes from the output of ACO detector. Hence, the performance of the hybrid detector is superior to that of the single ACO detector. Since, CFS is a filtering module that is independent of the former detection algorithm, CFS can be combined with many sub-optimum algorithms, such as ACO, to improve the performance of them. Simulation results showed that the hybrid approach with ACO and CFS has much better bit-error performance than the single ACO algorithm and is very close to the performance of OMD. Furthermore, the computational complexity of SACO-LAG is much less than that of the other detectors.