Suboptimal Partial Transmit Sequence-Active Interference Cancellation with Particle Swarm Optimization

Ultrawideband (UWB) communication, a spectrum underlay system, has a very small power spectral density that spans over hundreds of megahertz. While a UWB device must endure interference from the primary narrowband devices, the UWB transmission must not cause interference back to them. There are several works studying the impact of interference if the UWB system is to coexist with other narrowband systems, for example, [1‐4]. These studies indicate performance degradation as a result of mutual interference between UWB and narrowband systems.

Due to the secondary nature of UWB devices, it is their requirement to avoid causing the interference in the first place. One approach is to enhance the UWB device with the "detect-and-avoid" (DAA) [5] capability, sensing any ongoing narrowband transmissions and intelligently keeping away from the overlapped spectrum. If the narrowband transmission is found, the UWB device will adjust its transmission such that the effect of the UWB transmission will be negligible at the primary device receiver. DAA has been an interesting research topic on UWB recently. The strong interest of DAA is attributed to widespread usage of wireless applications sharing the same or overlapped part of the spectrum band. For example, current important narrowband systems that share parts of the UWB spectrum are WiMAX at the 3.5 GHz frequency range and IEEE802.11a at the 5 GHz frequency range. In the future, it seems inevitable for the UWB device to have the DAA feature.

This paper focuses on the avoidance part of DAA for the UWB system that employs OFDM transmission such as WiMedia standard [6]. In [6], tone nulling at the overlapped narrowband spectrum (referred to as an interference band) is suggested as an avoidance technique. Although tone nulling completely removes the interference at the exact center frequency corresponding to the nulled tones, there still exists interference caused by sidelobes of the remaining tones present elsewhere in the interference band [7]. One efficient technique to mitigate sidelobe interference is active interference cancellation (AIC) proposed in [7]. In addition to removing the subcarriers that lie inside the interference band, AIC removes two more subcarriers beside them and replaces the removed tones with the computed "AIC tones". The purpose of placing AIC tones is to generate "negative interference" in order to cancel the sidelobe interference from the remaining subcarriers.

Many extensions and improvements of AIC have been proposed recently. In a subcarrier-based antenna selection system, a new AIC formulation was proposed in [8]. The problem of sidelobe interference coming from a superposition of the transmissions from all antennas necessitates a new AIC for all antennas.

A few AIC algorithms with low complexity were proposed in [9]. The algorithms are based on simplifying matrix computation in the AIC. The complexity saving in [9] comes at a price of degraded interference cancellation performance although it is claimed that the algorithm is still better than the original AIC in the worst case.

The following works attempt to deepen the notch spectrum obtained with AIC. Extended AIC inserts the so-called extended AIC tones between the usual AIC tones, and they generate better negative interference [10]. However, since the extended AIC tones are placed in between the usual subcarrier positions, orthogonality between the subcarriers is lost and the bit error rate (BER) curve shows an error floor. Reference [11] proposes three enhancements of the AIC by cyclic shifting, phase shifting, or joint cyclic and phase shifting the data subcarriers. Doing so leads to modification of the spectrum and yields smaller remaining interference after the AIC operation. The algorithms in [11] increase the cancellation performance of AIC significantly with the drawbacks of high complexity and the requirement of side information. Recently, another technique, so-called partial transmit sequence-AIC (PTS-AIC), was proposed in [12]. It is essentially a novel application of partial transmit sequence that has been applied in OFDM in order to reduce peak-to-average power ratio (PAPR) [13, 14]. Adjacent subblock partitioning and interleaved subblock partitioning were proposed for the PTS-AIC. It was shown that PTS-AIC enhances the performance of AIC and provides more flexibility in parametrizing the algorithm. However, selecting the optimal parameters for PTS-AIC is very complex, especially when a large number of subblocks are used. High complexity comes from the exhaustive search for the optimal weighting factors whose number grows exponentially with the number of subblocks [12].

Particle swarm optimization (PSO) is a heuristic bio-inspired optimization algorithm that is well suited to solve high-dimensional and multimodal optimization problems [15‐18]. The PSO-based CDMA multiuser detection has been reported in [19‐21] where exponential complexity in the number of users has been resolved by the PSO. Power allocation problem in CDMA was solved by the PSO in [22] where a few constraint handlings were investigated and extensive studies on the parameters of PSO were given. PSO was applied in PTS for OFDM PAPR reduction in [23] to achieve much lower complexity. In [24], exponential complexity in the number of sensors was solved by the PSO in a sensor scheduling problem which optimizes a group of sensors for target tracking under the performance and cost constraints. More recently, PSO was exploited in determining linear precoding for a linear MMSE multiuser MIMO receiver, and it was shown to outperform the block diagonalization approach [25].

This paper proposes a PSO as a suboptimal approach to optimize weighting factors for PTS-AIC with the main purpose of reducing complexity. Unlike [23], both continuous and discrete (binary) version [16] of PSO are considered. It is shown that PSO can be applied to PTS-AIC effectively and can approach the performance of optimal PTS-AIC in many cases with much lower complexity. The PSO algorithm allows us to enhance the performance of PTS-AIC by using a larger number of subblocks whose complexity is prohibitive for the optimal exhaustive search.

The paper is organized as follows. Section 2 provides the background on AIC. Section 3 reviews the PTS-AIC as well as two types of subblock partitioning proposed in [12]. Section 4 discusses PSO in both continuous and discrete versions as well as their complexity analysis. Section 5 shows the simulation results and discussion. Conclusion is given in Section 6.

Notations

Bold letters represent matrices or vectors. is a transpose. is a Hermitian transpose. is an absolute value. is the -norm of a vector.

We hereby describe the AIC algorithm in a matrix formulation. Detailed description can be found in the original paper [7].

Some definitions are required as follows. Interference band is the frequency band that overlaps with the narrowband spectrum. Interference tones are the UWB OFDM subcarriers that are present in the interference band. AIC tones obtained by the AIC algorithm are to replace the interference tones and two subcarriers beside the interference tones. Figure 1 shows an example of interference band, interference tones, and AIC tones.

Let , where represents original frequency-domain data symbols and is the number of subcarriers (FFT size). We can write

where is an upsampled symbol vector with an upsampling factor and is an upsampling matrix of size with element .

Suppose the interference tones start from the th to th subcarriers, where is the number of interference tones. Define a nulling matrix which is constructed from an identity matrix, and put zeros at the th to th diagonal elements. The (upsampled) interference generated from the sidelobes of the other subcarriers can be computed as

where is a submatrix of by taking its row corresponding to upsampled spectrum in the interference band, that is, from the th to th rows of . Thus, the size of is . Let a new set of AIC subcarriers be a column vector of length . The AIC subcarriers are computed to generate "negative interference" to cancel , that is,

where is a submatrix of by taking its column corresponding to the positions of AIC tones, that is, from the th to th columns of . The size of is then . Since is not a square matrix, to solve (3), one constructs a least-squares problem which finds that minimizes the squared error [7],

A well-known least-squares solution to (4) is the Moore-Penrose generalized inverse (pseudoinverse) [26], in the form

where is of size and can be precomputed. Then, is inserted at the nulled tone positions. IFFT performs on this new block with the AIC tones in place to construct an OFDM symbol.

Figure 2 illustrates the transmission model for PTS-AIC. First, , a symbol block of length , is partitioned into subblocks of equal size . Each subblock is multiplied by a weighting factor .The weighting factor in this paper is chosen from a usual unit-energy complex PSK constellation of size , for example, when , and when . Then, a symbol block is reconstructed from each subblock as before it is processed with the AIC algorithm. The PTS-AIC algorithm determines an optimum -tuple weighting factor such that the remaining interference power inside the interference band after performing the AIC is minimum, that is,

where is a reconstructed symbol block computed by an -tuple weighting factor and is a set of -tuple weighting factor where its element is chosen from .

The PTS-AIC algorithm is characterized by the parameters and . We can adjust both parameters such that the interference cancellation performance meets the target while the complexity is affordable. As either or increases, the performance improves while the complexity increases. The complexity of PTS-AIC is determined by the number of all possible weighting factors to find , which is . Since the complexity grows exponentially with , one cannot increase the number of subblocks to a very large value to improve the performance, as the number of comparisons is prohibitive.

There are two types of subblock partitioning considered in this paper. The first type is adjacent subblock partitioning in which each subblock is constructed from adjacent subcarriers of the original symbol block. The second type is interleaved subblock partitioning in which each subblock is constructed from the subcarriers of distance in the original symbol block. Both types of partitioning are depicted in Figure 3.

Since PTS-AIC modifies the transmission block by the weighting factors, the receiver must be aware which set of weighting factors is applied so that it can recover the original symbol block. This can be done by sending the index of the optimum weighting factor as side information that amounts to bits. Once the receiver knows the applied weighting factors, multiplication of their complex conjugates to the received signal block after FFT returns the original data block.

Note one major difference between PTS conventionally applied to reduce PAPR and the proposed PTS-AIC. While the conventional PTS measures the PAPR of the (upsampled) time-domain signal after IFFT, the proposed PTS-AIC measures the interference power of the upsampled frequency spectrum before IFFT.

PSO algorithm was described in analogy with an activity of bird flocking or fish schooling [17]. Imagine a group of birds trying to locate a position in the field with the highest concentration of food. Each bird flies over the field and detects the concentration of food at its location. Each bird has an ability to remember its own best location and is aware of the group's best location. Its flying path depends on the previously observed location and is influenced by its own best location and the group's best location. Each bird has a chance to "fly over" the best location previously found and therefore observes the surrounding for a possibly better location. As time passes, most birds will be crowded at the best location they found as a group.

In the optimization problem, each bird is called a particle and its location represents an -dimension solution candidate in the -dimensional solution space. In the context of the PTS-AIC, a particle represents a vector of weighting factors . The location of the particle is reflected in the elements of . The concentration of food corresponds to the remaining interference power of PTS-AIC which is an objective value of the objective function in (6). The best location corresponds to the particle whose objective value is the minimum among other particles.

One round of observations from all particles corresponds to one iteration in the PSO. Suppose is the number of particles and is the number of iterations. The th dimension of the current location of the particle is while that of the particle's best location is . The th dimension of the group's best location is . The PSO is initialized by generating random locations for every particle. In one iteration, each particle evaluates the objective function and replaces its own best and the group's best locations if a better solution is found. The particle's best and the group's best locations will determine the change of location for the next iteration through a velocity variable which indicates the amount and direction (positive or negative) of change in distance from the current location. The update of the location for the next iteration is done by updating the velocity of each dimension

where is the velocity of the th dimension of the th particle at the th iteration. The velocity is initialized to be zero in the first iteration. , and are parameters of the PSO used to adjust the influence to the path of solutions from a particle's best location and the group's best location. are uniform random variables whose values are between 0 and 1 so as to introduce uncertainty of the influence. The update of the location is simply

where the time duration (supposed to be multiplied with the velocity) is assumed to be one. This completes the task for one particle in one iteration. The algorithm is repeated from the point of evaluation of the objective function for all particles and for iterations.

The original PSO algorithm was designed for a problem with continuous parameters. Since the optimization parameters in PTS-AIC are the weighting factors which are discrete, the location of a particle has to be quantized to the nearest point in the constellation set before the objective function is evaluated. This is done after the location update. The number of dimensions of each location in PTS-AIC (for the binary case) is . PSO for PTS-AIC with (binary case) can be described by Algorithm 1.

( ) Initialize parameters . Reset the vectors

     , for particle best and group best locations.

    Reset for particle best and group best objective values.

( ) Generate random locations, . Each location is an

     -dimension binary vector.

( ) Consider the first particle.

( ) Evaluate the objective function (7) with as weighting

    factors and update if necessary.

( ) Update the velocity according to (8) for each dimension.

( ) Update the location according to (9) for each dimension.

( ) Quantize the location to the nearest binary vector.

( ) Repeat from 4: for the next particle until all particles are considered.

( ) Repeat from 3: for iterations.

( ) Return as the solution of a vector of weighting factors.

Another way to tackle discrete parameters is to apply the PSO algorithm modified for binary parameters proposed in [16]. The idea is to work with dummy continuous parameters, transform them to have the range from 0 to 1, and consider the results as probabilities of the optimization parameters taking value 0 or 1. Therefore, there is no need to round off the parameters as in the previous algorithm. The transformation function proposed in [16] is a sigmoid limiting function, , whose domain is and whose range is . is the probability of equal to one, and the location is updated by generating a random number uniformly distributed over and comparing it with . We refer to this discrete version as discrete PSO (DPSO). The only change from Algorithm 1 is at Step ( ), which should be replaced by the location update algorithm according to Algorithm 2.

( ) Compute a probability mass function from

    where is the updated velocity for each dimension.

( ) Update the location by generating a random binary vector

    where each component is generated from the distribution

    computed in Step ( ).

To handle nonbinary parameters for both PSO and DPSO, we can simply extend the dimension of location and velocity vectors and convert the binary tuples into symbols on the constellation. For example, for , the dimension of each vector will be and two dimensions in the location are converted into one QPSK symbol.

Random QPSK symbols are generated to form OFDM data blocks. Each block contains 128 symbols corresponding to the 128-point FFT/IFFT. The subcarrier indices from the 85th to 87th are assumed to be the interference tones. From the AIC algorithm, the 84th to 88th subcarriers are removed and replaced by the AIC tones. The frequency-domain upsampling factor is four. To compute CCDF of the remaining interference power, , 10,000 data blocks are simulated in each case.

The parameters of PSO are set as , and resulting in equal influence from its own particle and from the group. This choice of parameters was recommended in an early work on PSO [15].

Figure 4 compares CCDF of among PSO, DPSO, random and optimal PTS-AIC. Adjacent subblock partitioning is assumed. The parameters for PTS-AIC are , and the parameters for PSO are . Optimal PTS-AIC exhaustively searches for the best weighting factors from the whole solution space of candidates. The optimal PTS-AIC serves as the best performance limit. The performance of the random scheme, which randomly chooses weighting factors and selects the best one, is plotted to illustrate the benefit of using the PSO/DPSO algorithms. For the random scheme, 600 random weighting factors are compared. This amount is equivalent to the number of comparisons in PSO/DPSO .

From the plots, the PSO and DPSO outperform the random scheme, and the DPSO can approach the performance of the optimal PTS-AIC at high interference power. At low interference power, however, the gain of PSO over the random scheme is small. Therefore, DPSO will be applied to the PTS-AIC for the rest of this section. The complexity of DPSO PTS-AIC is only about one percent of the optimal PTS-AIC in terms of the number of comparisons. Table 2 shows the average CPU time per realization of the considered algorithms taking into account all the required operations. It is shown that the PSO/DPSO has lower CPU times than the optimal scheme by almost two orders of magnitude.

To gain further insight on the complexity, Figure 5 shows the plots of average CPU time for optimal PTS-AIC, DPSO, and PSO. The CPU time of the optimal PTS-AIC is plotted versus the number of subblocks while the CPU times of DPSO and PSO are plotted versus the number of particles. Note that the -axis of Figure 5(a) is in a logarithmic scale. Since the curve is a straight line, it reflects an exponential complexity with respect to the number of subblocks in the case of the optimal PTS-AIC. In Figure 5(b), the CPU times of DPSO are slightly larger than those of PSO. From Table 1, given , the complexity is linear with and vice versa. This is reflected in the results in Figure 5(b). For a fixed , the curves are linear in . When is double, the slopes of the curves are also double.

Figure 6 shows the effect of different number of particles, , to the performance of DPSO PTS-AIC. By increasing the number of particles, the performance is improved regardless of the interference power. The performance of interleaved subblock partitioning is more sensitive to the number of particles than that of adjacent subblock partitioning. Nevertheless, increasing the number of particles beyond 30 seem does not to achieve much further gain. Therefore, we limit the maximum number of particles at 30 in the following simulations.

Figure 7 shows the average interference power of DPSO PTS-AIC as a function of the number of iterations, . The average interference power decreases sharply at small 's while it decreases gradually at large 's. The value where the average interference power starts to decrease gradually depends on . When is larger, this value gets larger, since the solution space becomes larger, so it takes more iterations to find a near-optimal solution. Increasing the number of iterations beyond 20 does not significantly improve the performance in our considered cases. Therefore, we limit the maximum number of iterations at 20 in the following simulations.

Figure 8 illustrates for 100 realizations of the optimal PTS-AIC and DPSO PTS-AIC with performing on the same data block for each realization. It is clear that DPSO PTS-AIC does not outperform the optimal PTS-AIC. Since DPSO PTS-AIC is suboptimal, the case can sometimes outperform the case (the particles are newly generated for , so they are different from each other).

Figure 9 shows the CCDF of when . The DPSO PTS-AIC with approaches the optimal PTS-AIC performance in the case of adjacent subblock partitioning. However, in the case of interleaved subblock partitioning, the DPSO PTS-AIC is still much worse than the optimal PTS-AIC.

Figure 10 shows the CCDF of when . The DPSO PTS-AIC with approaches the optimal PTS-AIC performance in both cases of adjacent and interleaved subblock partitionings.

Another potential benefit of PSO is apparent when is very large: the optimal PTS-AIC becomes prohibitive. Figure 11 shows that, at excess interference power, 5-dB gain over the optimal PTS-AIC with is achieved by the DPSO with . Similarly, about 10-dB gain over the optimal PTS-AIC with is achieved by DPSO with . This outcome is attained by the DPSO PTS-AIC with the complexity only about 1% of the optimal PTS-AIC.

We propose a suboptimal algorithm, called particle swarm optimization (PSO), for partial transmit sequence active interference cancellation (PTS-AIC) used for interference avoidance feature for UWB OFDM transmitter, to reduce the computational complexity significantly. The PTS-AIC with PSO becomes more attractive when the number of subblocks and/or the constellation set for the weighting factors are large for PTS-AIC. The discrete version of PSO is a better choice for the suboptimal algorithm compared to the continuous version and is able to approach the performance of the optimal PTS-AIC in many cases at much lower complexity. The benefit that is, brought from PSO to PTS-AIC becomes more attractive when the number of subblocks for PTS-AIC is large and makes PTS-AIC implementable in hardware.