{'fraction_non_alphanumeric': 0.04742482752635918, 'fraction_numerical': 0.016054150214778497, 'mean_word_length': 4.111554668440896, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
SWAN: Swarm-Based Low-Complexity Scheme for PAPR Reduction

Cyclically shifted partial transmit sequences (CS-PTS) has conventionally been used in SISO systems for PAPR reduction of OFDM signals. Compared to other techniques, CS-PTS attains superior performance. Nevertheless, due to the exhaustive search requirement, it demands excessive computational complexity. In this paper, we adapt CS-PTS to operate in a MIMO framework, where singular value decomposition (SVD) precoding is employed. We also propose SWAN, a novel optimization method based on swarm intelligence to circumvent the exhaustive search. SWAN not only provides a significant reduction in computational complexity, but it also attains a fair balance between optimality and complexity. Through simulations, we show that SWAN achieves near-optimal performance at a much lower complexity than other competing approaches.


I. INTRODUCTION
The adoption of orthogonal frequency division multiplexing (OFDM) by various communication standards (e.g., WiFi, ISDB-T, LTE, 3GPP Rel. 15/16) stems from its capability to provide high data rates, augmented spectral efficiency, and robustness to multi-path fading [1]. However, OFDM signals suffer from a high peak-to-average power ratio (PAPR) [2] caused by the constructive combination of modulated subcarriers. OFDM signals with high PAPR are power-inefficient [3] and prone to distortion due to the non-linearity of radio frequency (RF) amplifiers. Distortionless amplification can be achieved by reducing the signal power (i.e., back-off mechanism), thus forcing the amplifier to operate in the linear amplification region. However, this procedure compromises the RF amplifier energy efficiency. Therefore, it is essential to develop new approaches without resorting to back-off mechanisms.
Literature review: To reduce the PAPR, several approaches have been proposed. Clipping [3]- [6] limits the signal amplitude to a maximum threshold, thus preventing large peaks but causing distortion and bit error rate (BER) degradation [7]. Companding [8]- [10] consists of compression at the transmitter (to avoid distortion) and signal expanding at the receiver (to restore the amplitude). However, the latter process also magnifies small-valued noise, thus causing BER degradation. Besides, tone reservation (TR) [11], [12] and tone injection (TI) [12]- [14] are techniques that can reduce the PAPR without affecting the BER performance. TR uses a subset of subcarriers for exclusively canceling large signal peaks. TI expands the conventional PSK/QAM constellations such that each symbol can be mapped into one of several possible representations, and the best symbol mapping that minimizes the PAPR is chosen for transmission.
Another subgroup of techniques suppresses the large peaks by applying phase rotations (at the transmitter) and phase de-rotation (at the receiver), which has the advantage of preserving the BER performance. The most representative techniques of this kind are selected mapping (SLM) [15], [16] and partial transmit sequences (PTS) [17], [18]. In SLM, each modulated subcarrier is altered by a phase rotation whereas, in PTS, the modulated subcarriers are divided into disjoint partitions, and each partition is affected by the same phase rotation. While SLM relies on the design of codebooks, PTS focuses on finding the optimal phase rotations from a set of admissible values. The performance of both approaches are similar, and their computational complexities are high. Cyclically shifted partial transmit sequences (CS-PTS) [19]- [22] has not received much attention despite being superior to PTS and SLM. CS-PTS leverages the idea of PTS but incorporates additional time-domain cyclic shifting, which provides another degree of freedom that enables per-subcarrier phase rotation. This improves PAPR reduction but causes substantial complexity increase as more parameters have to be optimized (e.g., phase rotations and time shifts).
Contributions: To address the high search complexity of CS-PTS, we propose SWAN, a swarm-based optimization approach. SWAN controls the number of evaluations of potential solutions, thus maintaining the search complexity affordable with negligible impact on the optimality. Swarm-based approaches are characterized by exploration and exploitation. Exploration is the capability of effectively sampling the search space without inspecting every possibility exhaustively. Exploitation is the ability to capitalize on information obtained in previous iterations to produce more suitable solutions. Cuckoo search algorithm (CSA) [23] is a swarm-based approach inspired in the parasitic breeding behavior of some birds. It was shown though extensive experimentation that CSA outperforms other methods such as genetic algorithms (GA) [24] and particle swarm optimization (PSO) [25]. CSA has remarkable exploration capability, which is attributed to the usage of Levy flights. Nevertheless, the exploitation property of CSA is limited. We found that by improving the exploitation capability, the convergence rate of CSA could be substantially accelerated. Our proposed approach SWAN is an improvement to CSA, wherein we incorporate four additional mechanisms to (i) boost the exploitation capability of CSA and (ii) achieve Weighting and shifting Baseband processing Figure 1: CS-PTS for a SVD-MIMO system a fair balance between exploration and exploitation. The following summarizes our contributions: • CS-PTS has only been used in SISO systems [19]- [22]. We are the first to adapt CS-PTS to operate in MIMO systems with singular valued decomposition (SVD) precoding. • We generalize the application of PTS and SLM to SVD-MIMO systems. • We propose a novel swarm-based approach, SWAN, which finds near-optimal solutions (i.e., low-PAPR signals) at enhanced convergence rate and affordable complexity.
II. GENERALIZING CS-PTS FROM SISO TO SVD-MIMO Fig. 1 shows the implementation of CS-PTS for a SVD-MIMO system with N c subcarriers and N tx antennas at the transmitter, which we adapt from SISO CS-PTS [19]. Let denote the data symbols (e.g., PSK/QAM) at the i-th antenna, where each has a duration of ∆T . Upon serialto-parallel conversion, we obtain the symbols C Nrx×Ntx denote the channel between the transmitter and receiver in the k-th subcarrier (for k = 1, · · · , N c ). Using SVD decomposition 1 , the channel matrix can be factorized The right-hand matrix V k is used for precoding (at the transmitter) whereas U k is used for decoding (at the receiver). Thus, the precoded symbols at the k-th subcarrier are computed asX k = V k X k = X (1) [k], · · · ,X (Ntx) [k] T .
Upon performing precoding on all subcarriers, we definȇ The IFFT is applied to every 1 We assume that the channel matrix is known. Therefore, SVD precoding and decoding can achieve the MIMO channel capacity [26]. As a result, one data stream per singular value can be transmitted without causing interference.X where the PAPR at the i-th antenna is computed as Each phase rotation γ m is constrained to the set U = e j 2π U u | u = 0, · · · , U − 1 , where U represents the number of admissible phase rotations. Similarly, every time shift δ m is restricted to the set D = Nc D d | d = 0, · · · , D − 1 , where D represents the number of possible time shifts. The signal to be transmitted via the i-th antenna (prior to appending the cyclic where L is the oversampling factor. Due to time-frequency duality, cyclic time-domain shifting produces linear variation in the phase response. By cyclically delayingx m , phase variation per subcarrier can be achieved. Thus, every subcarrier k in the same m-th partition will be rotated by an additional phase rotation θ Nc δ m . The combined effect of both phase rotations and time shifts at subcarrier k of the m-th partition is γ m + θ

III. THE PROPOSED SWAN
CSA is inspired by the reproduction strategy of some cuckoo bird species that engage in brood parasitism to ensure their survival [23]. These birds deceive other species (host birds) by laying their eggs in their nests. This tactic relieves cuckoo birds from offspring feeding. As a result, more time can be devoted to food foraging and reproduction, thus improving the chances of survival of the species [23]. Sometimes, host birds are able to identify the cuckoo eggs and either abandon the nest or eject the parasite eggs. Features: CSA captures the core reproduction strategy of cuckoo birds, which is succinctly described in the following.
• The initial population of N cuckoo birds is equal to the number of host nests. • Each nest is a potential solution, and the suitability of each is defined by its fitness value. • The terms egg and nest are used interchangeably. • The nests with the highest quality (i.e., highest fitness) will carry over the next generation of birds. • Host birds discover the parasite eggs with a probability p a . Drawbacks: CSA has an affordable computational complexity and remarkable exploration capability. However, CSA does not exploit the known solutions properly. By balancing exploration and exploitation, the search performance can be improved thereby attaining faster convergence. To achieve this balance, we integrate four low-complexity mechanisms, thus resulting into SWAN. Although SWAN reckons with additional features, the complexity remains affordable since the proposed improvements are applied to only a limited number of potential solutions. Algorithm 1 describes SWAN in detail. The devised mechanisms are described in the following. Mechanism 1 (Update of the best solution): This mechanism is explained in lines 20 ∼ 24 of Algorithm 1. It deals with the appropriate placement of the best nest in the search space. In CSA, the nest with the highest fitness in each generation is used as a reference for generating Levy flights for the rest of the nests. However, the best nest is not updated until the next iteration (or generation). Thus, SWAN replaces the best nest with a more suitable one if a higher fitness is obtained. Specifically, the nests are generated according to where z T is the best solution at iteration t, which is used as a reference for deriving new candidate solutions z T are drawn from a Levy distribution function [23]. In (2), α is a scaling factor, n denotes the dimensions of the solution, and represents element-wise multiplication. Mechanism 2 (Best triad mating): In CSA, birds display limited social interaction. However, SWAN fosters collaborative information sharing, which improves convergence. We introduce the idea of best triad mating, which exploits information available at the best three solutions, intending to intensify the Algorithm 1 SWAN algorithm for PAPR reduction 1: N : number of host nest: initial population of cuckoo birds 2: pa : fraction of the total nests that represents the worst solutions 3: n : number of dimensions 4: τ : counter of evaluations 5: N G : number of nests in the neighborhood of the best nest 6: N H : number of nests to be mutated 7: begin 8: Define the objective function f : X n → R 9: Generate N host nests in Ω = {z i ∈ X n | i = 1, · · · , N } 10: Evaluate the fitness Fz i of each nest z i 11: while ∼ stopcriterion do 12: Find the current fittest nest z i in Ω 13: Choose randomly another nest z i from Ω avoiding z best 14: Generate a new nest z j via a Levy flight from z i 15: Evaluate the fitness Fz j 16: if (Fz j > Fz i ) then 17: Replace z i by the new solution z j 18: end if 19: Generate a new nest z k via a Levy flight from z best 20: Evaluate the fitness Fz k 21: if (Fz k > F best ) then 22: Replace z best by the new solution z k 23: end if 24: Update the counter τ 25: Let Ω Q = {q 1 , q 2 , q 3 } be defined by the three nests with the highest fitness in Ω, such that Ω Q ⊂ Ω, Ω P ⊂ Ω, Ω Q ∪ Ω P = Ω, Ω Q ∩ Ω P = ∅, Ω P = {p i ∈ X n | i = 1, · · · , N − 3}.

26:
Let the triangular region H be defined by q 1 , q 2 and q 3 27: Compute the parameters Γ and ε of H 28: Compute the parameter Γ * 29: Define Ω R = {r 1 , r 2 , r 3 } containing three potentially fitter nests obtained via Gaussian random walks using Γ * as a reference 30: Define Ω S = Ω Q ∪ Ω R and sort the elements, Fs i ≥ Fs i+1 31: Replace Ω Q by the first 3 elements of Ω S 32: Update the set Ω, such that Ω = Ω P ∪ Ω Q 33: Update the counter τ 34: Build the subset Ω A = {a i ∈ X n | i = 1, · · · , N A } consisting of potentially N A worst nests in Ω, such that

35:
Build a subset Ω C = {c i ∈ X n | i = 1, · · · , N A } consisting of N A potentially fitter nests than those contained in Ω A 36: Build the set Ω D = Ω A ∪ Ω C consisting of 2N A elements 37: Sort Replace the elements of Ω A by the first N A elements of Ω D , such that Ω A = {d i ∈ X n | i = 1, · · · , N A } 39: Update the set Ω, such that Ω A ∪ Ω B = Ω 40: Update the counter τ 41: Find the current best nest z best 42: Build Ω G = {g i ∈ X n | i = 1, · · · , N G } with N G new nests generated in the neighborhood of z best using uniform random walks 43: Select randomly N G nests from Ω avoiding z best and replace them by the newly generated eggs in Ω G 44: Update the counter τ 45: Build the set Ω H = {h i ∈ X n | i = 1, · · · , N H } containing the Ω H least fit nests and apply mutation 46: Keep the current best solutions for the next generation 47: Update the counter τ 48: end while 49: end search in a smaller space within which (with high probability) a better solution may lie. The procedure consists of five steps that have been summarized in lines 26 ∼ 34 of Algorithm 1.
Step 2.1: Let Ω Q = {q 1 , q 2 , q 3 } be a subset of Ω containing the fittest three nests (sorted in descending order of their fitness values). Further, let Ω P be a subset of Ω representing the complement of Ω Q . Using the elements in Ω Q , we define H (with point-to-point distances q 1 −q 2 , q 2 −q 3 , q 3 −q 1 ) as shown in Fig. 2. These three solutions {q 1 , q 2 , q 3 } achieve the highest fitness in the generation t. However, potentially fitter solutions might lie in a neighboring area to them.
Step 2.2: We calculate Γ and ε (shown in Fig. 2) as follows Essentially, q 1 , q 2 and q 3 delimit a triangular region H with sides q 1 −q 2 , q 2 −q 3 , q 3 −q 1 . Thus, Γ is the in-center of the circle C inscribed in H whereas ε is the in-radius of C.
Step 2.3: Let F q1 , F q2 , F q3 be the fitness values of q 1 , q 2 , q 3 , respectively. We compute the weighted reference Γ * via When F 1 ≥ F 2 + F 3 , q 1 has a weight higher than Γ. This indicates a higher fitness of q 1 compared to the other two solutions. Thus, Γ * will lean towards q 1 .
Step 2.5: Let Ω S be defined as Ω S = Ω Q ∪Ω R , thus consisting of {q 1 , q 2 , q 3 } and the newly generated {r 1 , r 2 , r 3 }. Let the elements of Ω S be sorted in descending order of fitness, such that F si ≥ F si+1 for all s i ∈ Ω S . Now, we redefine Ω Q such that it contains the three best solutions of Ω S , i.e. Ω Q = {s 1 , s 2 , s 3 }. Finally, we let Ω be the union of Ω Q and  , Ω = Ω Q ∪ Ω P (note that the cardinality of Ω has not changed). Mechanism 3 (Exploitation of the best nest): While each nest in CSA accommodates only one egg, we allow SWAN to accommodate more than one egg per nest as described in lines 42 ∼ 44 of Algorithm 1. Specifically, this mechanism intensifies the exploitation of the best known solution as follows. A random integer N G = {0, 1, 2, 3} is drawn with equal probability. N G is the number of solutions randomly selected from Ω which are to be replaced by new solutions Ω G = {g 1 , · · · , g N G }. By means of n-dimensional uniform random walks w uni = [w uni [1], · · · , w uni [n]] T , additional N G solutions are generated as shown in (5) (for = 1, · · · , N G ), where Ψ 1 = [ψ 1 [1], · · · , ψ 1 [n]] T is a vector whose elements are obtained from a normalized Gaussian probability density function.
where h w = [h w [1], · · · , h w [n]] T represents the nests with the lowest fitness at iteration t. The elements of Ψ 2 = [ψ 2 [1], · · · , ψ 2 [n]] T are obtained from a random variable uniformly distributed in the range [1,2] whereas the elements of Ψ 3 = [ψ 3 [1], · · · , ψ 3 [n]] T are 1 or -1 with equal probability. Remark: CSA is initialized with a set of N nests (or   solutions). However, within each generation, 2N solutions are generated from which only N are carried over to the next generation. SWAN is also initialized with N eggs and within a generation 2N +N ν eggs are generated. Nevertheless, only N are preserved as shown in Fig. 3. The difference, N ν = 3 + N G + N H , is due to the proposed mechanisms.
Adaptation of SWAN to CS-PTS in SVD-MIMO: In general, swarm-based approaches cannot be applied straightforwardly. Adjustments are necessary to take into consideration the underlying nature of the problem. In CS-PTS for SVD-MIMO, the number of dimensions is n = 2M , i.e., M phase rotations and M time shifts. Without loss of optimality, one phase rotation and one time shift can be fixed since the PAPR changes based on relative phase differences. As a result, the unknown parameters are {γ opt m } M −1 m=1 and {δ opt m } M −1 m=1 . Any candidate solution at iteration t has the structure z We define the function f : X n → R that takes an ndimensional input and maps it to a real value, which is the maximum PAPR across all the N tx transmit antennas, i.e., f (z) = max 1≤i≤Ntx PAPR i (z). As observed in (1), the evaluation of each candidate solution requires M − 1 complex operations due to weighting by γ m whereas timeshifting by δ m can be accomplished by varying the summation index only. Therefore, most of the computational complexity is due to complex multiplications by γ m . We avoid part of these operations by dividing SWAN into two stages (see Fig. 4). To decrease the number of complex multiplications, we create ρ 1 intermediate nodes which only bear the effect of the phase rotations γ m . From each intermediate node, ρ 2 solutions bearing the added effect of time-shifting are generated, amounting a total of ρ = ρ 1 ρ 2 candidates. By adopting the described structure, the complex multiplications we incur into are associated only to ρ 1 candidate solutions. Finally, the fitness function F z of a candidate solution z is defined as F z = 1 1+f (z) . IV. COMPUTATIONAL COMPLEXITY Table I shows the complexity of SLM, PTS, and CS-PTS when exhaustive search is employed. The codebook size used by SLM is V , whereas the number of partitions used by either PTS or CS-PTS is M . Also, U and D represent the number of admissible phase rotations and time shifts, respectively. As observed, CS-PTS has the highest number of solution patterns (due to the increased dimensionality, i.e., phase rotations and time shifts), which justifies the importance of SWAN. As shown in Table II, when employing SWAN in CS-PTS, the exponential complexity is eliminated and instead it is controlled by ρ 1 and ρ 2 . Since we compare the performance of SWAN against the benchmarks CSA, PSO and GA in Section V, we also show their complexity in Table III, where ρ represents the number of generated candidate solutions. Upon comparing Table II  and Table III, we conclude that the average cost per generated solution of SWAN is approximately half of that required by CSA. This is a consequence of adding the four mechanisms described in Section III, which require low-complexity opera-   tions and, on average, reduce the cost. Complexity is a critical factor when selecting an approach for practicality reasons. Nevertheless, convergence also plays an important role in guaranteeing high performance. For instance, although GA may be a preferred choice over CSA and PSO due to its low cost per generation, we corroborate in the next section that GA performs worst in terms of convergence (i.e., for a given number of generations the performance of GA is subpar compared to CSA and PSO, thus exhibiting its lower convergence per iteration).

V. NUMERICAL EXPERIMENTS
In this section, we evaluate the probability that the PAPR exceeds a threshold PAPR 0 , denoted by P (PAPR > PAPR 0 ). We evaluate several techniques under various configurations. For a fair comparison, we also adapt SLM and PTS to operate in SVD-MIMO mode. In the sequel, we assume that the data symbols are randomly obtained from a 64-QAM constellation, the oversampling factor is L = 4, and the number of subcarriers is N c = 256. We also assume the Rayleigh fading channel model [32], [33] with N p = 16 paths. Fig. 5 shows the PAPR for a varying number of transmit and receive antennas (N tx × N rx ) when PAPR reduction is not considered. As the number of antennas increases, the minmax PAPR (evaluated via (1)) increases as well. This is an expect outcome since a given solution needs to minimize the maximum PAPR over multiple antennas. In the following scenarios (i.e., Fig. 6 to Fig. 10), we evaluate a variety of PAPR reduction techniques when considering a 4 × 4 MIMO system with SVD precoding. Fig. 6 shows P (PAPR > PAPR 0 ) using SLM with different V = {4, 16, 64, 256, 1024, 4096}, which are pseudorandomly generated with phase rotations from e 0 , e π . Although CSA is computationally more complex than PSO and GA (as seen in Table III), we consider CSA as the benchmark approach due to its higher performance in terms of optimality. With almost half of the complexity of CSA (compare Table II and  Table III), SWAN consistently outperforms CSA under the same number of iterations. Also, the results shown under Optimal are obtained after evaluating (4 × 8) 3 = 32, 768 solution candidates. We realize that by only evaluating ρ = 4320 patterns, SWAN is at most 0.1 dB apart from Optimal with a probability of 10 −4 . Fig. 10 shows that CSA outperforms PSO and GA, and has higher convergence rate. Noteworthily, under the same ρ value, SWAN always outperforms CSA, PSO, and GA. Although SWAN and GA have comparable complexities, SWAN outperforms GA by 0.15 dB at P (PAPR > PAPR 0 ) = 10 −4 , and this result is prevailing under all the evaluated values of ρ = {270, 1080, 4320}.

VI. CONCLUSIONS
In this paper, we adapted CS-PTS to operate in MIMO systems with SVD precoding. Leveraging on this system, we formulated a min-max problem to reduce the PAPR across multiple transmit antennas. Given the high computational complexity of the resulting problem, we proposed a swarmbased approach called SWAN to design the parameters (i.e., phase rotations and time shifts) that minimize the maximum PAPR. Through extensive simulations, we showed that SWAN outperforms other competing approaches such as CSA, GA, and PSO in terms of convergence and complexity. Our results confirmed that even with a low complexity requirement, SWAN attains near-optimality. We conclude that SWAN is an attractive technique for systems with limited capabilities. In particular, through SWAN, computationally-constrained systems can explore the solution space in a smarter fashion, thus providing a better trade-off between complexity and optimality compared to straightforward approaches such as exhaustive search.