SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Research

A complexity-performance-balanced multiuser detector based on artificial fish swarm algorithm for DS-UWB systems in the AWGN and multipath environments

Zhendong Yin1*, Zhiyuan Zong1, Hongjian Sun2, Zhilu Wu1 and Zhutian Yang1

Author Affiliations

1 School of Electronics and Information Engineering, Harbin Institute of Technology, Harbin, People’s Republic of China

2 Department of Electronic Engineering, King’s College London, London, WC2R 2LS, UK

For all author emails, please log on.

EURASIP Journal on Advances in Signal Processing 2012, 2012:229  doi:10.1186/1687-6180-2012-229


The electronic version of this article is the complete one and can be found online at: http://asp.eurasipjournals.com/content/2012/1/229


Received:21 February 2012
Accepted:12 October 2012
Published:30 October 2012

© 2012 Yin et al.; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

In this article, an efficient multiuser detector based on the artificial fish swarm algorithm (AFSA-MUD) is proposed and investigated for direct-sequence ultrawideband systems under different channels: the additive white Gaussian noise channel and the IEEE 802.15.3a multipath channel. From the literature review, the issues that the computational complexity of classical optimum multiuser detection (OMD) rises exponentially with the number of users and the bit error rate (BER) performance of other sub-optimal multiuser detectors is not satisfactory, still need to be solved. This proposed method can make a good tradeoff between complexity and performance through the various behaviors of artificial fishes in the simplified Euclidean solution space, which is constructed by the solutions of some sub-optimal multiuser detectors. Here, these sub-optimal detectors are minimum mean square error detector, decorrelating detector, and successive interference cancellation detector. As a result of this novel scheme, the convergence speed of AFSA-MUD is greatly accelerated and the number of iterations is also significantly reduced. The experimental results demonstrate that the BER performance and the near–far effect resistance of this proposed algorithm are quite close to those of OMD, while its computational complexity is much lower than the traditional OMD. Moreover, as the number of active users increases, the BER performance of AFSA-MUD is almost the same as that of OMD.

Keywords:
DS-UWB; Multiuser detection (MUD); Artificial fish swarm algorithm (AFSA); Euclidean solution space

1. Introduction

Ultrawideband (UWB) technology is attractive for its multiple-access (MA) applications in wireless communication systems owing to its high ratio of the transmitted signal bandwidth to information signal bandwidth (or pulse repetition frequency) [1]. Similarly, power can spread, because of its information symbols transmitted by short pulses, over the wide frequency band [2]. There are mainly two standard schemes formulated by IEEE 802.15 Task Group 3a, i.e., the multi-band-based orthogonal frequency division multiplexing (MB-OFDM) and single-band-based direct-sequence UWB (DS-UWB) [3]. The former is a carrier-based system that divides the wide bandwidth of UWB into many sub-bands, while the latter is a baseband system modulating its input information symbols with nanosecond pulses, which is different from conventional code division multiple access (CDMA) systems [1,4,5]. Compared with MB-OFDM, DS-UWB scheme has many advantages, which stem from its UWB nature, such as low peak-to-average power ratio, wide bandwidth, good information hidden ability, and less sensitivity to multipath fading [6,7]. Our focus is thus on investigating the detection algorithms in multiuser DS-UWB communication systems.

Actually, the idea of UWB MA systems dates back to the original proposal put forward by Scholtz [8], and with subsequent analyses in [9-12]. However, as in conventional CDMA systems, these proposed UWB MA systems also suffer from the multiple-access interference (MAI) problem, which severely restricts their performance and system capacity. This is due to the crude assumption that the MAI can be modeled as a zero-mean Gaussian random variable (called “Gaussian approximation”) [13] for the conventional single-user matched receiver. Moreover, MAI even causes the near–far effect (NFE) [14], the case that the user with lower received signal power will be swamped by users with higher power. In order to solve these problems, multiuser detection (MUD) technology that can eliminate or weaken the negative effects of MAI was studied in [15-27]. Among them, the optimum multiuser detection (OMD), proposed for CDMA systems by Verdu [15], has the optimal BER performance [16] and the perfect NFE resistant ability [17]. But its computational complexity growing exponentially with the number of active users makes it impractical to use [18]. Yoon and Kohno [19] introduced this OMD algorithm to the UWB MA system; its high computational complexity problem is yet to be solved.

In recent years, many different sub-optimal MUD algorithms have been studied in literatures. In [20], a multiuser frequency-domain (FD) turbo detector was proposed that combines FD turbo equalization schemes with soft interference cancelation, but its BER performance is unsatisfactory. A blind multiuser detector using support vector machine on a chaos-based code CDMA systems was presented in [21], which does not require the knowledge of spreading codes of other users at the cost of training procedure. In [22], a low-complexity approximate SISO multiuser detector based on soft interference cancellation and linear minimum mean square error (MMSE) filtering was developed, but the performance of this detector is unfavorable at low SNR. As the swarm intelligence is one of the latest methods in the field of signal processing [23] (especially for combinatorial optimization problems [24]), several swarm-intelligence-based MUD algorithms have been considered in [25-27]. However, the tradeoff problem between computational complexity and BER performance still exists.

To solve these issues, we investigate a complexity-performance-balanced multiuser detector based on the artificial fish swarm algorithm (AFSA-MUD) for DS-UWB systems. As a kind of swarm intelligence methods, AFSA is selected here for its significant ability to search for the global optimal value and to adapt its searching space automatically [28,29]. And its basic motivation is to find the global optimum by simulating the fish’s behaviors, such as preying, swarming, and searching.

In this proposed AFSA-MUD algorithm, a simplified Euclidean solution searching space is constructed by the use of the solutions of sub-optimal multiuser detectors, which are MMSE detector, decorrelating (DEC) detector, and successive interference cancellation (SIC) detector. Specifically, the center of this space is the result judged in terms of the average value of all these sub-optimal solutions, while its radius is defined as the maximum distance between this center and these sub-optimal solutions. Then, AFSA is applied in this simplified solution space and these sub-optimal solutions are considered as the initial states for the artificial fishes (AFs). Simulation results show that the BER performance and the NFE resistance capability of this proposed algorithm are comparable to those of OMD, and significantly better than those of matched filter (MF), SIC, DEC, and MMSE detectors. Besides, its computational complexity is much lower than that of OMD, indicating a better efficiency.

The remainder of this article is organized as follows. In Section 2, the general multiuser DS-UWB system and some typical MUD algorithms are described, including OMD, MMSE, DEC, and SIC. And in Sections 3 and 4, the basic principles of AFSA and the proposed AFSA-MUD algorithm are discussed, respectively. In Section 5, simulation experiments that compare the performance of different MUD algorithms are made, followed by conclusions given in Section 6.

2. Multiuser DS-UWB system model and some classical MUD algorithms

2.1. Multiuser DS-UWB system model in additive white Gaussian noise and IEEE 802.15.3a channels

First, we consider a K-user synchronous DS-UWB system under the additive white Gaussian noise (AWGN) channel and each user employs the BPSK direct sequence spread spectrum modulation [30]. Then, the kth user’s transmitted signal can be expressed in the following form [31]:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M1">View MathML</a>

(1)

where wtr(t) represents the transmitted pulse waveform generally characterized as the second derivative of Gaussian pulse [6,19] in Equation (2), {bj(k)} are the information symbols for the kth user, {pn(k)} denotes the spreading sequences assigned to this user, Tc is the pulse repetition period (namely the chip period), Tf is the time duration of information symbol that satisfies Tf = NcTc, and Nc is the length of spreading codes.

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M2">View MathML</a>

(2)

where τm is the parameter that determines the width of the pulse.

If these K users are all active, the total received signal composed by different signals of all users is

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M3">View MathML</a>

(3)

where Ak is the amplitude of the kth received signal and n(t) represents the received noise modeled as a normal distribution N(0, σn2) [4].

The AWGN channel, in which the performance of different MUD detectors can be discussed and analyzed easily, is too ideal for practical use. However, the multipath channel is in reality used more often, especially in the indoor environment. In this article, IEEE 802.15.3a channel model discussed in [30,32,33] is chosen for the system in discussion. This channel model is slightly modified from the Saleh–Valenzuela model [34], that is, a lognormal distribution hypothesis for the multipath gain magnitude replaces the Rayleigh distribution hypothesis. This multipath channel model can be defined as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M4">View MathML</a>

(4)

where X is the lognormal shadowing factor, {αm,l} are the multipath gain coefficients, Tl is the delay of the lth cluster, τm,l represents the delay of the mth multipath component (called “ray”) relative to the lth cluster arrival time (Tl), i.e., τ0,l = 0. L and M denote the number of clusters and its rays, respectively. In addition, the amplitude |αm,l| has a lognormal distribution while the phase ∠ αm,l is equal to {0, π} with equiprobability [30].

According to the conclusions in [32], there are four typical multipath channel models of different channel characteristics, namely CM1–CM4. CM1 represents a line-of-sight (LOS) propagation case with 0–4-m propagation distance, while CM2–CM4 denote three different non-LOS propagation cases with different propagation distance or delay spread. The detailed characteristics of these models are summarized in [32].

Therefore, the transmitted signal passed through this multipath channel can be expressed as Equation (5), which is dissimilar with Equation (3)

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M5">View MathML</a>

(5)

where the symbol ⊗ denotes the convolution operation. Furthermore, in this case, the pulse repetition period Tc is chosen large enough to preclude intersymbol and intrasymbol interference [10]. With the help of Rake receivers, the MUD algorithms discussed in the AWGN case can be applied to the multipath case easily.

2.2. Classical multiuser detectors

2.2.1. Single-user MF

Since the MA DS-UWB system is assumed to be synchronous, the output of a bank of single-user MFs is a K-dimensional vector y, and its kth component is the output of the filter matched to Str(k)(t) at the jth symbol duration

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M6">View MathML</a>

(6)

Without loss of generality, we set the case that j = 0 and remove the index j. Thus, Equation (6) turns to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M7">View MathML</a>

(7)

where the first term Akbk is the ideal detection result of the kth user, the second term indicates the MAI to this user, where ρik = ∫ 0TfStr(i)(t)Str(k)(t)dt denotes the normalized correlation coefficient, and the last term nk = ∫ 0Tfn(t)Str(k)(t)dt is the noise interference. Consequently, this K-dimensional detection vector y can be represented in matrix and vector forms

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M8">View MathML</a>

(8)

where R is the normalized cross-correlation matrix with {ρik}(i,k = 1,2,…,K), and

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M9">View MathML</a>

where diag{A1, A2,…,AK} represents a diagonal matrix with diagonal elements A1, A2, …, AK. Furthermore, n is a zero-mean Gaussian random vector with its covariance matrix equal to

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M10">View MathML</a>

(9)

2.2.2. OMD

According to [35], the OMD problem is equivalent to the maximum a posteriori estimation. The criterion of OMD is written as follows

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M11">View MathML</a>

(10)

It is known that the selection of this optimal solution <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M12">View MathML</a> in the K-dimensional Euclidean solution space is generally a non-deterministic polynomial (NP) hard problem [18]. For this reason, the computational complexity of OMD grows exponentially with the number of active users.

2.2.3. MMSE detector

The purpose of MMSE detector is to minimize the mean square error between the transmitted signal and the detected signal transformed by matrix M linearly. This linear transformation can also maximize the signal-to-interference ratio [21,36]. Thus, the MMSE algorithm is equivalent to the choice of the K × K matrix M that achieves

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M13">View MathML</a>

(11)

From [21,36], the optimal matrix M for Equation (11) is

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M14">View MathML</a>

(12)

and the solution of this MMSE detector can be expressed as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M15">View MathML</a>

(13)

2.2.4. DEC detector

Assume the cross-correlation matrix R is invertible, and then the transformation matrix M of the DEC detector is R–1

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M16">View MathML</a>

(14)

where the interference caused by other users is eliminated completely, but that of background noise is amplified.

2.2.5. SIC detector

This method is motivated by a natural and simple idea that if a decision has been made for an interfering user’s information bit, then its interfering signal can be recreated at the receiver and subtracted from the original received signal [37]. Thus, the decision of the kth user is [36]

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M17">View MathML</a>

(15)

where the decisions of users k + 1, k + 2, …, K are assumed to be correct. Since the reliability of this assumption affects performance drastically, the order of demodulating users becomes the problem. Here, we set users in order through Equation (16), which can be estimated easily from the MF outputs [36]

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M18">View MathML</a>

(16)

Notice that all these MUD algorithms introduced above can be applied to the multipath situation easily by Rake receivers with channel estimators [33] (which is outside the scope of this article).

3. The basic principles of AFSA

AFSA is a random-searching optimization algorithm inspired by fish’s behaviors, such as searching for food, swarming, and following others. It is good at avoiding the local optimum and searching for the global optimum owing to its adaptive capacity in the parallel search of solution space through simulating these behaviors in nature [27-29]. In this section, the general AFSA is discussed below.

3.1. Some definitions for AFSA

In the AFSA, let the searching solution space is K-dimensional and there are N AFs in this space. Like other swarm-intelligence methods, AFSA searches this solution space based on the cooperation and competition among its AFs [28]. As is shown in Figure 1, there are some important definitions for AFSA.

thumbnailFigure 1. The local visual range of AF Xi(the two-dimensional case).

The state of each AF can be modeled as a K-dimensional vector:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M19">View MathML</a>

(17)

where xi (i = 1, 2, …, K) is the ith component of X. Moreover, Y = f(X) denotes the food concentration level of this state, where f(.) is also called the fitness function or the objective function for specific issues.

The distance between the states Xi and Xj is formulated as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M20">View MathML</a>

(18)

In addition, Visual denotes the local visual (or search) distance of AFs, δ is the factor of crowdedness that affects the number of AFs in the local space, step is the movement size of AFs, and try_number is the random-searching times in searching behavior described below.

3.2. The behavior descriptions of AFSA

3.2.1. Searching behavior

Suppose that Xi is the current state of a certain AF. This AF then selects a new state Xj within its visual distance randomly. If Yj = f(Xj) > Yi = f(Xi), this AF will move from Xi to Xj as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M21">View MathML</a>

(19)

where the calculation of (XjXi)/||XjXi|| gives the orientation to move. Otherwise, select a new Xj randomly again and determine whether it satisfies the movement condition (Yj > Yi). If no one can satisfy this condition after testing try_number times, this AF will move one step randomly at final as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M22">View MathML</a>

(20)

3.2.2. Swarming behavior

Let Xi is the current state of a certain AF, and nf is the number of companions within its visual range, which is the number of elements in the set of B = {Xj |di,j < Visual}. Then Xc is calculated by Equation (21) as the central state of its companions in its visual range:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M23">View MathML</a>

(21)

Meanwhile, Yc = f(Xc) is the food concentration of this central state. If Yc/nf > δYi and Yc > Yi, which means the food concentration of Xc is sufficient while this area is not crowded, then this AF will move one step to the central state as Equation (22). Otherwise, the searching behavior is executed.

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M24">View MathML</a>

(22)

3.2.3. Following behavior

Assume that Xi is the state of a certain AF at present, and then within the visual scope of Xi, search the state Xmax whose food concentration Ymax is maximum. If the conditions Ymax/nf > δYi and Ymax > Yi satisfy, this AF will move one step to Xmax:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M25">View MathML</a>

(23)

Otherwise, the searching behavior is executed.

3.3. Bulletin board

The bulletin board is designed to prevent the optimization results from degradation, that is, it is used to record and renew the best food concentration and its corresponding state during the iteration of AFSA. After the maximum number of iterations has been achieved, the final records on this bulletin board will be output as the result of AFSA.

3.4. The selection of different behaviors for AFs

As for the optimization problems, such as the maximum problem, the selection of these different behaviors is based on the trial method [38], which simulates the swarming behavior and the following behavior of each AF and the better one of them that can increase the food concentration of this AF will be implemented actually. If none of them can improve the former state of this AF, the searching behavior will be selected. Hence, the whole flowchart of AFSA can be summarized in Figure 2 (the sections in the dashed border are not necessary).

thumbnailFigure 2. The whole flowchart of AFSA.

4. The proposed AFSA-MUD algorithm

4.1. The AFSA for MUD problem

It is clear that OMD is a combinatorial optimization problem, and AFSA has a strong global searching capability to solve this problem. Therefore, here AFSA is applied to the MUD problem with some additional explications in the discrete Euclidean solution space EK, where K is the number of active users

(1) The expression of AF’s state. In this solution space, the state of each AF is encoded by −1 or +1. If there are K active users in this DS-UWB MA system, thus the state is a K-dimensional vector, like X0 = (x1,x2,…,xK)T, where xi ∈ {−1,   +  1} and i = 1,2,…,K.

(2) Initialization. The initial state of each AF is selected randomly in the discrete space with 2K likely solutions.

(3) The distance between different states. In this case, the operator XOR is used to calculate this distance. For example, if Xi = (1,1,–1,1,1) and Xj = (1,–1,1,–1,1), then the distance di,j = Xi XOR Xj = 3.

(4) The food concentration or the fitness function for AFs is the criterion of OMD in Equation (10).

(5) The operations in Equations (19), (22), and (23) are be modified as follows, respectively:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M26">View MathML</a>

(24)

4.2. The improved scheme for the selection of initial states and the simplification of solution space

Since AFSA is a kind of random-searching swarm-intelligence algorithms, its convergence speed and computational complexity mainly depend on its initial states and searching space. This suggests that, in order to enhance the speed of convergence and decrease the computational complexity of AFSA-MUD, the initial states should be selected with a priori knowledge, rather than selected randomly, and the K-dimensional solution space should be simplified.

Hence, a novel AFSA-MUD method is proposed here, whose a priori knowledge is the detection results of some sub-optimal detectors, such as MMSE, DEC, and SIC detectors. Besides, its Euclidean solution space defined by its center and radius is constructed by these sub-optimal results, which is more condensed than the former whole space. As a result, this mechanism cannot only enhance the convergence speed and search accuracy for the global optimum, but also reduce the time or complexity it takes. The details are described as follows.

(1) Initialization. Let the detection results of MMSE, DEC, and SIC detectors be the K-dimensional vectors X1, X2, and X3. Thus, the number of AFs can be set as 3 and their initial states are assigned by X1, X2, and X3, respectively. Notice that this initialization can be expanded to the situation with more than three sub-optimal detectors effortlessly.

(2) The center of the simplified space. Here, the majority voting method is applied, which has widely been used to solve the conflict problem both in engineering and social fields, to the fixing of the center point:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M27">View MathML</a>

(25)

(3) The radius of the simplified space. In this algorithm, the radius is determined by the maximum distance between the center and these initial states (or sub-optimal solutions):

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M28">View MathML</a>

(26)

where dradius denotes the searching radius of AFSA. But in fact, these sub-optimal detectors are not independent of each other absolutely, and their correlation degree can be estimated [39] as

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M29">View MathML</a>

(27)

In [39], n is the total number of classifiers, N is the total number of testing samples, Nf is the number of samples that are misclassified by all classifiers, and Nr means those samples that are classified correctly by all classifiers. But here, n is regarded as the total number of sub-optimal detectors, N is the total number of testing information bits, Nf denotes the number of bits that are detected wrongly by all detectors while Nr is the bits detected correctly by all. Figure 3 depicts the correlation ρ3 of SIC, DEC, and MMSE detectors versus Eb/N0. From it, we can see as the Eb/N0 increases, their correlation degree rises obviously before Eb/N0 = 16 dB (from 0.52 to 0.98), but after that, it stands at nearly 1 all the time. In general, the lower the Eb/N0 is, the more diversity these sub-optimal detectors will have, and also the bigger the space-searching radius is. Furthermore, this correlation degree is quite significant if there are many sub-optimal detectors to choose from.

thumbnailFigure 3. The correlation degree of SIC, DEC, and MMSE detectors.

Considering the analysis above, when the case X1 = X2 = X3 occurs, the radius calculated by Equation (26) is zero, which means the solution space is null. In order to avoid this problem, the radius is set as 1, if X1 = X2 = X3 is satisfied.

To sum up how to determinate the center and the radius of the simplified space, three situations are considered.

i. none of these sub-optimal solutions equals to another (X1X2X3);

ii. two of these solutions are equal, but not three (X1 =X2X3);

iii. all of these solutions are equal (X1 = X2 = X3).

Figure 4 shows these three situations in a two-dimensional solution space, which can be generalized into K-dimensional solution space easily (K > 2).

thumbnailFigure 4. Three situations in a two-dimensional solution space.

4.3. The proposed AFSA-MUD algorithm

In consideration of the statements above, the overall structure of this proposed AFSA-MUD detector is shown in Figure 5. And the implementation of this detector is summarized as follows.

(1) The output of a bank of single-user MF receivers is fed to sub-optimal detectors, such as SIC, DEC, and MMSE.

(2) The detection results of these sub-optimal detectors are used to construct a simplified solution space and initialize the states of AFs.

(3) The AFSA is executed in this space.

thumbnailFigure 5. General schematic diagram of the AFSA-MUD detector.

5. Numerical results

In order to test and verify this proposed AFSA-MUD algorithm, Monte Carlo simulations are utilized and the majority parameters used for these simulations are summarized in Table 1. The performance of MF, SIC, DEC, MMSE, AFSA-MUD, and OMD detectors is compared in both AWGN and multipath channels (only the energy of the first path is received, that is, without Rake diversity combining) as follows, including the BER performance versus Eb/N0, the BER performance versus the number of active users K, and also the NFE resistant capability. Finally, the computational complexity of AFSA-MUD is compared with those of other detectors to demonstrate its efficiency.

Table 1. Simulation parameters

5.1. The BER performance versus Eb/N0 comparison

The BER versus Eb/N0 curves with perfect power control in the AWGN and multipath IEEE 802.15.3a CM2 channels are depicted in Figures 6 and 7, respectively, when there are ten users in the system. Besides, the BER versus Eb/N0 performance curves of AFSA-MUD conditioned in the different multipath channels, which is CM1–CM4, are displayed in Figure 8.

thumbnailFigure 6. BER performance comparison when K = 10 in the AWGN channel.

thumbnailFigure 7. BER performance comparison when K = 10 in the IEEE 802.15.3a CM2 channel.

thumbnailFigure 8. BER performance comparison for AFSA-MUD whenK= 10 in CM1–CM4 channels.

It can be seen from Figure 6 that the BER performance of AFSA-MUD is superior to those of other sub-optimal detectors including MF, SIC, DEC, and MMSE, and it even coincides with that of OMD. The reason is that this proposed AFSA-MUD algorithm can make a search within a simplified solution space constructed by the solutions of these sub-optimal detectors, rather than a random search. Therefore, all these sub-optimal solutions are certainly contained in this searching space. Although all the performances of these algorithms are aggravated in the multipath environment (Figure 7), the BER performance of AFSA-MUD is still close to that of OMD, both of which are the best.

From the simulation results in Figure 8, we can see that, as the communication channel condition deteriorates from CM1 to CM4, the BER performance of AFSA-MUD also deteriorates. In detail, CM1, compared with CM2–CM4, is LOS and its transmission distance is the shortest, so that the power of its received signal is larger than others.

5.2. The BER performance versus K comparison

The BER performance curves of these detectors with different number of active users K are analyzed in this experiment, considering two cases: (i) the AWGN channel with the Eb/N0 set as 5 dB for all detectors; (ii) the multipath CM2 channel with the Eb/N0 set as 10 dB (to distinguish these curves clearly) for all detectors.

Figures 9 and 10 show the results corresponding to Cases one and two, respectively. As a whole, the BER becomes higher when the number of users increases, and the performance of OMD is the best. The reason for the performance gap between AFSA-MUD and OMD is that, as the number of users increases, the simplified solution space also expands, and as a result of this, the parameters (Visual, Try_number, and the iterative times) should be bigger, but in this experiment, they remain unchanged as in Table 1.

thumbnailFigure 9. Case one: BER performance versus K.

thumbnailFigure 10. Case two: BER performance versus K.

In addition, there are some conspicuous differences between these two figures. The performance of SIC is better than that of MF in Figure 9 but worse in Figure 10, which is because the interfering user’s bits estimated in AWGN environment are much more accurate than in multipath environment. That is, SIC cannot improve the BER performance of MF in low Eb/N0 environment. Then, limited by its ability to amplify the interference of background noise, DEC cannot achieve the optimal performance, especially in Case two where its performance is the worst when K = 5, 10.

5.3. The NFE resistant capability comparison

The BER performance of these detectors with imperfect power control, called the NFE, is discussed in this simulation. Also we give two cases: (i) the AWGN channel with the number of users set as 10, when the transmitted energy per information bit of the first user Eb1 keeps the same with its Eb1/N0 = 5 dB while that of other users Eb2–10/N0 varies from 0 to 15 dB synchronously; (ii) the multipath CM2 channel with the number of users set as 10, when Eb1/N0 = 10 dB (to separate these curves clearly) while that of other users Eb2–10/N0 also varies from 0 to 15 dB synchronously. Notice that only the BER of the first user is analyzed and depicted.

From Figure 11 (Case one), it is obvious that DEC, MMSE, AFSA-MUD, and OMD have the stronger NFE resistant ability (no sense with Eb2–10/N0) than MF and SIC detectors. However, in consideration of the BER performance of them, AFSA-MUD and OMD are the best. Furthermore, the BER performance curve of SIC has an inflexion at the point where Eb2–10/N0 = 5 dB, due to its detection method in Equations (15) and (16). On one hand, when the energy of users 2–10 calculated by Equation (16) is smaller than that of user 1, which is Eb2–10/N0 < 5 dB, then the information bits of user 1 will be detected at first, which is the same as MF does. This is the reason that the BER performance of SIC is identical with MF until Eb2–10/N0 = 5 dB. On the other hand, when Eb2–10/N0 > 5 dB, the information bits of users 2–10 will be detected before those of user 1 with more reliability. As a result, after the interfering signal subtracted from the original received signal by Equation (15), the BER performance of SIC is improved, agreeing with those of AFSA-MUD and OMD.

thumbnailFigure 11. Case one: BER performance versus Eb2–10/N0.

Figure 12 shows the almost same conclusion for the NFE resistant ability comparison in the multipath case, except for a little diverse. Due to the effect of multipath, especially when Eb2–10/N0 is larger than 8 dB, the interfering users’ bits are not estimated correctly enough (here, BER > 10–1). From Equation (15), it can be seen that if the estimation of the interfering users’ bits is inaccurate, the interfering signals can be enhanced perversely, resulting in the worse BER performance of SIC even than that of MF, which is different from the AWGN case in Figure 11.

thumbnailFigure 12. Case two: BER performance versus Eb2–10/N0.

5.4. The computational complexity comparison

The total number of calculating the K-dimensional vector inner products (after the output of MFs in Equation 8) for all these detectors at each symbol duration is listed in Table 2, where K is the number of active users in this multiuser system and Li is the upper bound for the radius of solution space in the current information symbol duration ((i – 1)Tf < t < iTf). The detailed derivation of the computational complexity of AFSA-MUD is given in Appendix. Note that in our discussed problem, the communication system is static (i.e., the number of active users is fixed, such as K = 5, 10, 15) so that the matrix inversion in Equations (13) and (14) need not be performed at each symbol period. In other words, the computational complexity of inversion operation is negligible.

Table 2. The computational complexity comparison

As is shown in Table 2, the computational complexity of AFSA-MUD is much lower than that of OMD evidently, because only if Li = K and K is large enough, that <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M31">View MathML</a> is satisfied. However, the case LiK/2 is meaningless for a certain communication system. To make it clear, the computational complexity of all these detectors is compared in Figure 13, when Li/K = 0.1, 0.3, and 0.5.

thumbnailFigure 13. The computational complexity of all detectors.

In addition, the average Li/K versus Eb/N0 curves (K = 10) conditioned on the AWGN case and multipath CM1–CM4 cases are depicted in Figure 14. As it shows, Li/K will decrease when the variable Eb/N0 increases, which also means the upper bound for the radius of solution space has a self-adaption capability in accordance with Eb/N0. Besides, the average ratio Li/K is about 0.2 for CM1–CM4 cases, which implies that AFSA-MUD can save at least 94.4% of the computational complexity of OMD (in Table 2 with K = 10). In AWGN case, AFSA-MUD will save even more than 98.8% of the complexity.

thumbnailFigure 14. The average Li/K versus Eb/N0curves when K = 10.

6. Conclusion

In this article, the focus has been on the MUD technology used in the DS-UWB system. In consideration of the high-computational complexity of OMD, and the low BER performance of sub-optimal multiuser detectors, a complexity-performance balanced MUD algorithm is proposed on the basis of AFSA, named AFSA-MUD. This method executes the different behaviors of AFs in a simplified Euclidean solution space, which is built by the detection results of sub-optimal detectors. Simulation results have indicated that the BER performance and the NFE resistant ability of this novel algorithm are quite close to those of OMD, and they are also superior to those of MF, SIC, DEC, and MMSE; furthermore, it takes much lower computational complexity to achieve this performance.

Appendix

The computational complexity of AFSA-MUD

Let the detection results of SIC, DEC, and MMSE be three K-dimensional vectors:

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M32">View MathML</a>

and in consideration of the parallel execution of these detectors (from Figure 5), the number of calculating the K-vector inner products for this parallel execution is considered K here.

According to Equations (25) and (26), the center of its simplified solution space is

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M33">View MathML</a>

while the radius is dradius. An arbitrary solution in this space is X = (x1, x2, …, xK)T, which satisfies the condition

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M34">View MathML</a>

(28)

where Li is the upper bound for the radius of this solution space in the current information symbol duration ((i – 1)Tf < t < iTf), and it can be determined by the number of discordant components in these three K-dimensional vectors

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M35">View MathML</a>

(29)

Then, the total number of K-vector inner products for AFSA-MUD is equivalent to counting the number of K-vector inner products for all discrete solutions in this space (its radius is Li), and plus the number for the parallel execution of SIC, DEC, and MMSE, that is

<a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M36">View MathML</a>

(30)

where the term <a onClick="popup('http://asp.eurasipjournals.com/content/2012/1/229/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://asp.eurasipjournals.com/content/2012/1/229/mathml/M37">View MathML</a> (i = 0, 1, …, Li) means the number of all solutions that satisfies d(X0, X) = i.

Competing interests

The authors declare that they have no competing interests.

Acknowledgements

This study was supported by “the National Natural Science Foundation of China” (Grant no. 61102084), “the Fundamental Research Funds for the Central Universities in China” (Grant no. HIT.NSRIF.2010092), and “the China Postdoctoral Science Foundation” (Grant no. 2011M500665). Besides, the authors would like to thank the anonymous reviewers for their invaluable comments.

References

  1. B Hu, NC Beaulieu, Precise performance analysis of DS-UWB systems on additive white Gaussian noise channels in the presence of multiuser interference. IET Commun. 1(5), 977–981 (2007). Publisher Full Text OpenURL

  2. M Herceg, T Svedek, T Matic, Pulse interval modulation for ultra-high speed IR-UWB communications systems. EURASIP J. Adv. Signal Process. 2010, 8 (2010) Article ID 658451 OpenURL

  3. J Maunu, T Koivisto, M Laiho, A Paasio, An analog Viterbi decoder array for DS-UWB receiver. Proceedings of IEEE International Conference on Ultra-wideband (Waltham, MA, USA, 2006), pp. 31–36 24–27 Sept OpenURL

  4. Y Zhang, AK Brown, Data rate for DS-UWB communication systems in wireless personal area networks. Proceedings of IEEE International Conference on Ultra-wideband, 1st edn. (Hannover, Germany, 2008), pp. 187–190 10–12 Sept OpenURL

  5. BR Vojcic, RL Pickholtz, Direct-sequence code division multiple access for ultra-wide bandwidth impulse radio. in Proceedings of IEEE Military Communications Conference (MILCOM 03) vol. 2, 898–902 (2003) 13–16 Oct OpenURL

  6. S Tan, A Nallanathan, B Kannan, Performance of DS-UWB multiple-access systems with diversity reception in dense multipath environments. IEEE Trans. Veh. Technol. 55(4), 1269–1280 (2006). Publisher Full Text OpenURL

  7. H Sato, T Ohtsuki, Frequency domain channel estimation and equalisation for direct sequence ultra wideband (DS-UWB) system. IEE Proc. Commun. 153(1), 93–98 (2006). Publisher Full Text OpenURL

  8. RA Scholtz, Multiple access with time-hopping impulse modulation. Proceedings of IEEE Military Communications Conference (MILCOM 93), 2nd edn. (Boston, MA, USA, 1993), pp. 447–450 11–14 Oct OpenURL

  9. MZ Win, RA Scholtz, Ultra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communications. IEEE Trans. Commun. 48(4), 679–689 (2000). Publisher Full Text OpenURL

  10. JD Choi, WE Stark, Performance of ultra-wideband communications with suboptimal receivers in multipath channels. IEEE J. Sel. Areas Commun. 20(9), 1754–1766 (2002). Publisher Full Text OpenURL

  11. AR Forouzan, M Nasiri-Kenari, JA Salehi, Performance analysis of time-hopping spread-spectrum multiple-access systems: uncoded and coded schemes. IEEE Trans. Wirel. Commun. 1(4), 671–681 (2002). Publisher Full Text OpenURL

  12. VS Somayazulu, Multiple access performance in UWB systems using time hopping vs. direct sequence spreading. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC 02), 2nd edn., 522–525 (2002) Mar OpenURL

  13. G Durisi, S Benedetto, Performance evaluation of TH-PPM UWB systems in the presence of multiuser interference. IEEE Commun. Lett. 7(5), 224–226 (2003)

  14. FC Zheng, SK Barton, On the performance of near-far resistant CDMA detectors in the presence of synchronization errors. IEEE Trans. Commun. 43(12), 3037–3045 (1995). Publisher Full Text OpenURL

  15. S Verdu, Optimum multiuser asymptotic efficiency. IEEE Trans. Commun. 4(9), 890–897 (1986)

  16. S Verdu, Minimum probability of error for asynchronous Gaussian multiple-access channels. IEEE Trans. Inf. Theory 32(1), 85–96 (1986). Publisher Full Text OpenURL

  17. R Lupas, S Verdu, Near-far resistance of multiuser detectors in asynchronous channels. IEEE Trans. Commun. 38(4), 496–508 (1990). Publisher Full Text OpenURL

  18. S Verdu, Computational complexity of optimum multiuser detection. Algorithmica 4(1–4), 303–312 (1989)

  19. YC Yoon, R Kohno, Optimum multi-user detection in ultra-wideband (UWB) multiple-access communication systems. Proceedings of IEEE International Conference on Communications(ICC 02), 2nd edn. (New York, NY, USA, 2002), pp. 812–816

  20. P Kaligineedi, VK Bhargava, Frequency-domain turbo equalization and multiuser detection for DS-UWB systems. IEEE Trans. Wirel. Commun. 7(9), 3280–3284 (2008)

  21. JW Kao, SM Berber, Blind multiuser detector for chaos-based CDMA using support vector machine. IEEE Trans. Neural Netw. 21(8), 1221–1231 (2010). PubMed Abstract | Publisher Full Text OpenURL

  22. X Wang, HV Poor, Iterative (Turbo) soft interference cancellation and decoding for coded CDMA. IEEE Trans. Commun. 47(7), 1046–1061 (1999). Publisher Full Text OpenURL

  23. D Merkle, M Middendorf, Swarm intelligence and signal processing. IEEE Signal Process. Mag. 25(6), 152–158 (2008)

  24. MG Hinchey, R Sterritt, C Rouff, Swarms and swarm intelligence. Computer 40(4), 111–113 (2007)

  25. N Zhao, ZL Wu, YQ Zhao, TF Quan, A population declining mutated ant colony optimization multiuser detector for MC-CDMA. IEEE Commun. Lett. 14(6), 497–499 (2010)

  26. H Liu, J Li, A particle swarm optimization-based multiuser detection for receive-diversity-aided STBC systems. IEEE Signal Process. Lett. 15, 29–32 (2008)

  27. M Jiang, C Li, D Yuan, MA Lagunas, Multiuser detection based on wavelet packet modulation and artificial fish swarm algorithm. Proceedings of IET Conference on Wireless, Mobile and Sensor Networks (Shanghai, China, 2007), pp. 117–120 12–14 Dec OpenURL

  28. XZ Gao, Y Wu, K Zenger, X Huang, A knowledge-based artificial fish-swarm algorithm. Proceedings of IEEE 13th International Conference on Computational Science and Engineering (Hong Kong, China, 2010), pp. 327–332 11–13 Dec OpenURL

  29. YM Cheng, L Liang, SC Chi, Determination of the critical slip surface using artificial fish swarms algorithm. J. Geotech. Geoenviron. Eng. 134(2), 244–251 (2008). Publisher Full Text OpenURL

  30. J Ren, MS Lim, A novel equalizer structure for direct sequence ultra wideband (DS-UWB) system. Proceedings of IEEE International Conference on Portable Information Devices (Orlando, FL, USA, 2007), pp. 1–5 25–29 May OpenURL

  31. N Boubaker, KB Letaief, Performance analysis of DS-UWB multiple access under imperfect power control. IEEE Trans. Commun. 52(9), 1459–1463 (2004). Publisher Full Text OpenURL

  32. AF Molisch, JR Foerster, M Pendergrass, Channel models for ultrawideband personal area networks. IEEE Wirel. Commun. 10(6), 14–21 (2003). Publisher Full Text OpenURL

  33. B Mielczarek, MO Wessman, A Svensson, Performance of coherent UWB Rake receivers with channel estimators. Proceedings of IEEE Vehicular Technology Conference, 3rd edn. (Orlando, FL, USA, 2003), pp. 1880–1884 6–9 Oct OpenURL

  34. AAM Saleh, R Valenzuela, A Statistical model for indoor multipath propagation. IEEE J. Sel. Areas Commun. 5(2), 128–137 (1987)

  35. J Luo, KR Pattipati, PK Willett, F Hasegawa, Near-optimal multiuser detection in synchronous CDMA using probabilistic data association. IEEE Commun. Lett. 5(9), 361–363 (2001)

  36. S Verdu, Multiuser Detection (Cambridge University Press, UK, 1998)

  37. Y Wang, MZ Bocus, JP Coon, Iterative successive interference cancellation for quasi-synchronous block spread CDMA based on the orders of the times of arrival. EURASIP J. Adv. Signal Process. 2011, 12 Article ID 918046 BioMed Central Full Text OpenURL

  38. H Ma, Y Wang, An artificial fish swarm algorithm based on chaos search. Proceedings of International Conference on Natural Computation, 4th edn. (Tianjian, China, 2009), pp. 118–121 14–16 Aug OpenURL

  39. K Goebel, W Yan, W Cheetham, A method to calculate classifier correlation for decision fusion. Proceedings of Decision and Control, 135–140 (2002)