Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm

Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm Momin Jamil∗† , Hans-J¨urgen Zepernick∗, and Xin-She Yang‡ Citation details: M. Jamil, H. J. Zepernick, X. S. Yang, Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm, in: Recent Advances in Swarm Intelligence and Evolutionary Computation (Ed. Xin-She Yang), Studies in Computational Intelligence,vol. 585, pp. 179-202 (2015). Abstract The cross-ambiguity function (CAF) relates to the correlation processing of signals in radar, sonar, and communication systems in the presence of delays and Doppler shifts. It is a commonly used tool in the analysis of signals in these systems when both delay and Doppler shifts are present. In this chapter, we aim to tackle the CAF synthesization problem such that the synthesized CAF approximates a desired CAF. A CAF synthesization problem is addressed by jointly designing a pair of waveforms using a metaheuristic approach based on the echolocation of bats. Through four examples, it is shown that such an approach can be used as an effective tool in synthesizing different types of CAFs. 1 Introduction In a conventional matched filter receiver, the internal reference waveform is a du- plicate of the transmitted signal, i.e., the receiver reference waveform is matched to the transmitted signal [34]. However, in radar applications, the appropriate time delay and compression must be taken into account at the receiver side. Therefore, in a conventional matched filter receiver, the receiver waveform is a replica of the transmitted signal with appropriate time delay and time compression. However, a conventional receiver is not able to take care of clutter or jamming suppression. In Momin Jamil∗† ∗† Harman International, Automotive Division, Becker-Goering Str. 16, D-76307 Karlsbad, Germany, e-mail: [email protected] Hans-J¨urgen Zepernick∗ , ∗ Blekinge Institute of Technology, SE-371 79 Karlskrona, Sweden e-mail: [email protected] Xin-She Yang‡ , ‡ Middlesex University, School of Science and Technology, London NW4 4BT, UK e-mail: [email protected] 1 2 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ a radar system, clutter appears as signal echoes with different delays or Doppler shifts compared to the signal of interest. In order to suppress impairments due to clutter and interference, it is desirable to minimize these effects at the receiver side. Accordingly, a joint design of the transmit signal and receive filter is desirable such that the signal-to-clutter-plus-interference ratio (SCIR) of the receiver output is maximized at the time of target detection [29]. As a result, an alternative to con- ventional receivers, known as a general or optimum receiver, was proposed in [34]. This receiver can be used as a trade-off between the signal-to-noise ratio (SNR) for improved SCIR [34]. In an optimum receiver, the internal or reference waveforms (or equivalent filter) may be deliberately mismatched to reduce the sidelobes in the delay-Doppler plane. The aforementioned joint design for clutter/interference suppression has been addressed in [5, 6, 16, 17, 23, 29, 31, 33] and the references therein. However, a joint design of the mismatched filter at the receiver side and the transmit signal leads to a more complex optimization problem that involves either assessing cross- correlation (CC) properties with respect to delay in the case of negligible Doppler shifts or focusing on cross-ambiguity function (CAF) characteristics in the delay- Dopper plane otherwise [6, 27]. A performance measure frequently used to assess waveforms for radar, sonar, and communication applications in the presence of delay and Doppler shifts, known as ambiguity function (AF), was proposed in [39]. An AF is a function of two vari- ables representing correlation properties of a signal in the delay-Doppler plane. It provides a mathematical representation of the response of a matched filter to a re- ceived waveform. The waveform design that would yield an optimum AF has been on the forefront of research for many years. In an ideal case, an AF would have the shape of a spike at the origin and zero elsewhere in the delay-Doppler plane. Al- though such an AF is certainly desirable, in practice, it is not realizable for signals having finite energy. As a result, large efforts have been given to waveform designs that relax the zero sidelobe constraint throughout the delay-Doppler plane to uni- formly low sidelobes, while still maintaining a reasonable large value at the origin. In practice, radar waveforms are often designed by minimizing the sidelobes of an auto-correlation function (ACF), i.e., by basically matching pre-defined specifica- tions only to the zero-Doppler cut of an AF [30]. In [39], the importance of signal designs using waveform synthesis for radar and sonar applications has been stressed. Nevertheless, the search for practical solutions to the synthesis problem still poses a challenge to radar system engineers. A first known mathematical solution to the synthesization problem was presented in [37]. However, this solution has two drawbacks: (i) it requires that the shape of a desired ambiguity function is given in analytical form, (ii) it does not cope with settings where only certain parts of the ambiguity surface are to be approximated, e.g., the clear area in and around a large neighbourhood of the origin. As a consequence, this solution is of limited interest to practical radar applications. In practice, radar engi- neers typically have a general idea about the desirable shape of an AF rather than an exact expression of it as a mathematical function. Furthermore, in many scenarios, it is not even necessary to specify the shape of an AF for the entire delay-Doppler Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 3 plane. In other words, the region where an AF is required to produce small values very much depends on the particular radar application. For example, the Doppler shift may be much smaller compared to the bandwidth of the transmitted waveform which can be in the order of several megahertz. In this case, the AF for Doppler shifts beyond the maximum induced shifts is not required. An alternative approach of constructing a waveform with optimal ambiguity surface in a region around the main lobe of an AF using well-know Hermite waveforms has been presented in [8]. In single-input single-output (SISO) radar systems, the problem becomes to syn- thesize a single radar waveform that approximates a desired auto-ambiguity function (AAF) of pre-defined magnitude over the delay-Doppler plane. On the other hand, multiple-input multiple-output (MIMO) radar systems or communication systems involve pairs of signals rather than a single waveform. Accordingly, the synthesis problem focuses on the CAF between a pair of signals. In the considered context, the CAF describes the receiver response to a mismatched signal as a function of time and Doppler shift. In particular, the continuous-time CAF is defined as Z ∞ χ (τ , fd ) = a(t)b∗ (t + τ ) exp( j2π fd t)dt, (1) −∞ where a(t) and b(t) are arbitrary waveforms as a function of time t, τ is delay, fd denotes √ Doppler frequency/Doppler shift, (·)∗ denotes complex conjugate, and j = −1. In practice, the CAF is applicable for a SISO radar system when a(t) is the transmit signal and b(t) represents the receive filter [28]. Similarly, the CAF is used for a MIMO radar system when both a(t) and b(t) are different transmit signals [25]. In a conventional matched filter receiver, where the receiver reference waveform is matched to the transmitted signal [34], i.e. a(t) = b(t), the CAF becomes an AAF. Let us now consider two signals a(t) and b(t), consisting of a train of N pulses si (t) and s j (t), respectively, as N a(t) = ∑ ai si (t), (2) i=1 N b(t) = ∑ b j s j (t), (3) j=1 where the coefficients ai and bi can be expressed as column vectors of length N as a = (a1 , a2 , . . . , aN )T , (4) b = (b1 , b2 , . . . , bN )T , (5) and sk (t); k = i, j denotes a pulse shaping function. For example, a rectangular pulse shaping function is defined as 1 h t − (k − 1)Tc i sk (t) = √ s , k = 1, 2, . . . , N, (6) Tc Tc 4 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ where Tc denotes the pulse duration and ( 1, 0 ≤ t ≤ Tc , s(t) = (7) 0, elsewhere. Substituting (2), (3), and (6) into (1), the CAF comprising of pulse shaping func- tions with respective shifted pulses and corresponding coefficients ai and b j can be obtained as N N Z ∞ χ (τ , fd ) = ∑ ∑ ai b∗i −∞ si (t)s∗j (t + τ ) exp( j2π fd t)dt, (8) i=1 j=1 where the integral represents the CAF between pairs of pulse shaping functions, i.e., Z ∞ χˆ i, j (τ , fd ) = si (t)s∗j (t + τ ) exp( j2π fd t)dt. (9) −∞ Clearly, synthesizing a CAF such that it matches a desired CAF of pre-defined magnitude over the delay-Doppler plane is a difficult task. As a result, not many methods, other than solutions based on the least-squares approaches exist, see, e.g., [4, 8, 22, 26, 32, 38]. Recently, in [12], an algorithm has been proposed to match a synthesized CAF to a desired CAF of pre-defined magnitude over the delay-Doppler plane. More specifically, this algorithm proposes a joint design of a pair of signals a(t) and b(t), or sequences a and b to tackle the CAF synthesization problem. Fur- thermore, in [15], Jamil et al. proposed a L´evy flight based cuckoo search for a joint sequence design such that their CAF approximates a desired CAF indicating the potential of metaheuristic approaches to solve such challenging sequence design problems. In view of the above, this chapter considers a joint sequence design using the im- proved bat algorithm (IBA) of [14] to address the problem of matching a synthesized CAF to a desired CAF of pre-defined magnitude over the delay-Doppler plane. We hypothesize that a joint design of a pair of sequences a and b such that their CAF ap- proximates a desired CAF is a global optimization problem (GOP). Apparently, this type of problem is a highly multimodal problem without any a priori information about the location of the optimum solution (unimodal) or solutions (multimodal). Traditional optimization methods that require either a good initial guess or gradient information are unsuitable to solve such problems to optimality. Therefore, nature- inspired population methods, mimicking the behaviour of different species of ani- mals, have been proposed to solve such problems [40, 41, 42]. Due to their general applicability and effectiveness, these algorithms have been a popular choice to solve modern optimization problems. These population-based algorithms use population members to explore the problem search space for a possible solution or solutions by maintaining a balance between intensification (exploitation) and diversification (ex- ploration). However, intensification (exploitation) and diversification (exploration) are usually based on a uniform or Gaussian distribution. L´evy flights (LFs) based on Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 5 the L´evy distribution have been proposed as an alternative to achieve exploitation and exploration strategies. The remainder of this chapter is organized as follows. In Section 2, we briefly in- troduce the L´evy probability distribution, and the motivation of using LFs in meta- heuristic algorithms. In Section 3, we present the improved bat algorithm in detail. In Section 4, the formulation and solution to the considered synthesis problem is presented. Numerical results are presented in Section 5. Finally, Section 6 concludes the chapter. 2 L´evy Probability Distribution 2.1 L´evy Distribution A random process is called stable if the sum of a given number of independent random variables, X1 , X2 , . . . , XN , has the same probability density function (PDF) up to location and scale parameters as the individual random variables. A well- known example of a stable random process is a Gaussian process, i.e., the sum of Gaussian random variables also produces a Gaussian distribution which in addition has a finite second moment. A stable random process with infinite second moment produces a so-called α -stable distribution. An α -stable random variable S is defined by its characteristic function as follows [11]: Φα ,β = E exp( jzS) = exp(−β α |z|α )   (10) √ where E[·] denotes the expectation operator, j = −1, z ∈ R, α ∈ (0, 2] and β ≥ 0. The L´evy probability distribution belongs to a special class of symmetric α -stable distributions. According to [11], the PDF of a symmetric α -stable random variable is given by the inverse Fourier transform of (10) as Z ∞ 1 Lα ,β (S) = exp(−β zα ) cos(zS)dz (11) π 0 In (11), the parameters α and β control the shape and the scale of the distribution, respectively. The parameter α takes values in the interval 0 < α ≤ 2 and controls the heaviness of the distribution, i.e., the decay of the tails. The smaller the value of α , the more the accumulation of data in the tails of the distribution. In other words, the random variable values are more likely to be far away from the mean of the distribution. On the other hand, the larger the value of α , the more the accumulation of data near the mean of the distribution. Except for a few special cases, a closed- form expression of integral in (11) is not known for α in general. The integral in (11) becomes a Cauchy distribution and Gaussian distribution for α = 1 and 2, respectively. 6 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 2.2 L´evy Flight Based Metaheuristic Algorithms In recent years, a number of theoretical and empirical studies have tried to explain that foragers such as grey seals [1], microzooplankton [2], [13], reindeer [18], wan- dering albatrosses [35], fish [36], among many others, adapt LF as an optimal search strategy in search of food. However, it should be mentioned that foragers adapt their search strategy based on the density of prey, sometimes switching between LF and Brownian motion (BM). In metaheuristic and stochastic optimization algorithms, random walks play an important and central role in the exploration of the problem search space. The search performed by metaheuristic algorithms (MAs) is carried out in a way that it can accomplish goals of intensively explored areas of the search space with high-quality solutions and move to unexplored areas of the search space when necessary. Intensification and diversification [9, 10] are two key ingredients to achieve these goals. By maintaining a fine balance between these two components define the overall efficiency of MA. In fact, L´evy flights have already been used to enhance metaheuristic algorithms with promising results in the literature, including the cuckoo search and firefly algorithm [15], [40], [41]. An alternative to a uniform or Gaussian distribution to realize randomization in MA is offered by the L´evy distribution. Not only does the power law behavior of a L´evy distribution reduce the probability of returning to previously visited sites in the problem search space, but it also provides an effective and efficient exploration mechanism of the far-off regions of the function landscape. 3 Improved Bat Algorithm The bat algorithm (BA) mimicking the echolocation behavior of certain species of bats was presented in [42] and is based on the following set of rules and assump- tions: 1. All bats know the difference between food/prey, background barriers, and use echolocation to sense the proximate distance from the prey; 2. In search mode, bats fly randomly with a frequency fmin with velocity vi at posi- tion xi . During search mode, bats vary wavelength λ (or frequency f ) and loud- ness A0 . Depending on the proximity from the target, bats can automatically ad- just the wavelength (or frequency) for their emitted pulses and adjust the rate of pulse emission r ∈ [0, 1]; 3. It is further assumed that the loudness varies from a large (positive A0 ) to a min- imum value of Amin ; 4. Ray tracing is not used in estimating the time delay and three dimensional topog- raphy; 5. The frequency f is considered in a range [ fmin , fmax ] corresponding to the range of wavelengths [λmin , λmax ]; 6. For simplicity, frequency is assumed in the range f ∈ [0, fmax ]. Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 7 According to [42], by making use of the above rules and assumptions, the stan- dard bat algorithm (SBA) will always find the global optimum. However, in SBA, the bats rely purely on random walks drawn from a Gaussian distribution, there- fore, speedy convergence may not be guaranteed [42]. To improve the bat algorithm further, Jamil et al. developed the improved bat algorithm (IBA) [14]. In this section, a brief overview of the IBA [14] is presented which constitutes an improved version of SBA [42]. In IBA, the random motion of bats is replaced by LF instead of using a Gaussian distribution. The motivation for this choice is that the power-law behavior of the L´evy distribution will produce some members of the random population in the distant regions of the search space, while other members will be concentrated around the mean of the distribution. The power-law behavior of the L´evy distribution also helps to induce exploration at any stage of the convergence, making sure that the system will be not trapped in local minima. The L´evy distribution also reduces the probability of returning to the previously visited sights, while the number of visitations to new sights is increased [14, 40, 42]. For a comprehensive review of the bat algorithm and its variants, please refer to [43]. 3.1 Motion of the Bats In IBA, the position or location of each bat is given as xti and it flies through the D-dimensional search space or solution space with a velocity vti . The position and velocity for bat i are updated at time t, respectively, as vti = vt−1 i + (xt−1 i − xbest i ) fi , (12) xt+1 i = xt−1 i + vti ∆ t, (13) where ∆ t represents the discrete time step of the iteration. However, in mathemati- cal optimization, emphasis is often given to dimensionless variables, and therefore, ∆ t can be implicitly chosen as 1. Furthermore, the pulse frequency fi for bat i at position xi is given by fi = fmin + ( fmax − fmin )β , (14) and vectors xi and vi represent the position and velocity of bat i. In (14), β ∈ [0, 1] is a random number drawn from a uniform distribution, fmin and fmax denote the minimum and maximum frequency of the emitted pulse [42]. The symbol xbest i in (12) represents the current best solution found by bat i by comparing all the solutions among all the NP bats. In IBA [14], once a best solution is selected among the current best solutions, a new solution for each bat is generated using an LF that is based on a L´evy distribu- tion according to xti = xbest i + γ · Lα (S). (15) 8 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ Here, vector Lα (S) represents a random walk that is generated based on the L´evy distribution for each i (bat) with parameter α . The parameter γ > 0 scales the random step length and is related to the scales of the problem [40, 41, 42]. Specifically, the step size S of the random walk is drawn from a L´evy distribution (with an infinite mean and variance) that is often given in terms of a power-law formula given as [11, 40, 41] 1 Lα (S) ∼ , |S| ≫ 0, (16) Sα +1 where α is the exponent determining the shape of the tail of the distribution. 3.2 Variation of Loudness and Pulse Rates In IBA, we use the originally proposed approach of controlling the exploration and exploitation in bats as proposed in [42], i.e., variation of loudness and pulse rates. In order to switch to the exploitation stage when necessary, each bat i varies its loudness Ai and pulse emission rate ri iteratively as follows: At+1 i = ϒ Ati0 , (17) ri0 [1 − exp(−Γ t)], t rt+1 i = (18) where Ati0 , At+1 t0 t+1 i , ri , and ri , respectively, represent initial loudness, updated loud- ness, initial pulse emission rate, and updated pulse emission rate after each iteration for bat i. Furthermore, ϒ and Γ are constants. 4 Problem Formulation In practice, infinite energy signals do not exist, therefore, ambiguity surfaces that produce a Dirac impulse or a function with ideal delay-Doppler characteristics do not exist. Thus, it is often desirable to design waveforms that exhibit a peak at the origin and produce an almost flat surface in and around a large neighborhood of the origin. The problem of matching a CAF to a desired CAF can be formulated as a mini- mization problem and can be solved by using the cyclic approach proposed in [12]. Accordingly, such an optimization problem can be formulated as Z∞ Z∞ 2 w(τ , fd ) · d(τ , fd ) − bH X(τ , fd )a d τ d fd ,   min C(a, b) = (19) a,b −∞ −∞ Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 9 where w(τ , fd ) is a weighting function that specifies which area of the CAF in the delay-Doppler plane needs to be emphasized and (·)H denotes Hermitian transpose. The modulus of the desired CAF is denoted by d(τ , fd ) which is positive and real- valued, a and b are different sequences. In view of (9), the cross-ambiguity matrix of the pulse shaping functions can be written as χˆ 1,1 (τ , fd ) · · · χˆ 1,N (τ , fd )   X(τ , fd ) =  .. .. .. . (20)   . . . χˆ N,1 (τ , fd ) · · · χˆ N,N (τ , fd ) where χˆ i, j (τ , fd ) denotes the CAF between the i-th and j-th pulse shaping function given by (9). Furthermore, the term under the absolute value operator | · | in (19) represents the CAF in (8) in a more compact form as χ (τ , fd ) = bH X(τ , fd )a. (21) Due to phase incoherencies, the magnitude of the ambiguity function contains all the information about a signal pertinent to system performance [32]. In order to solve the ambiguity function synthesis problem, the indirect approach introduced in [7, 32] can be used. Accordingly, auxiliary phases are introduced to the desired ambiguity function d(τ , fd ) in (19), that is Z∞ Z∞ w(τ , fd ) · d(τ , fd )e jθ (τ , fd ) − bH X(τ , fd )a d τ d fd . (22) 2 ˜ b, θ (τ , fd )) =  C(a, −∞ −∞ Introducing auxiliary phases θ (τ , fd ) makes the integrand in (22) real and positive everywhere. The minimization problem in (22) can then be solved by fixing two arguments of C(·,˜ ·, ·) and minimizing C(·, ˜ ·, ·) with respect to the third variable [12]. First, let us fix a pair of sequences a and b which leads to the auxiliary phase θ (τ , fd ) being expressed as [7, 32] θ (τ , fd ) = arg{bH X(τ , fd )a}. (23) Second, by fixing the auxiliary phases θ (τ , fd ) and sequence b, the criterium ˜ ·, ·) → C(a) C(·, ˜ can be written as [7, 32] Z∞ Z∞ 2 ˜ = aH D1 a − aH D2 b − bH D2 H a + w(τ , fd )d(τ , fd ) d τ d fd  C(a) −∞ −∞ −1 H −1 = (a − D1 D2 b) D1 (a − D1 D2 b) + C, (24) where constant C does not depend on sequence a and therefore can be ignored. It follows from (24) that the minimizer a is given as a = D−1 1 D2 b, (25) 10 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ where D1 ∈ CN×N and D2 ∈ CN×N , respectively, are given as Z∞ Z∞ D1 = w(τ , fd )XH (τ , fd )bbH X(τ , fd )d τ d fd , (26) −∞ −∞ Z∞ Z∞ D2 = w(τ , fd )d(τ , fd )eθ (τ , fd ) XH (τ , fd )d τ d fd . (27) −∞ −∞ Third, by fixing the auxiliary phases θ (τ , fd ) and sequence a, the criterium ˜ ·, ·) → C(b) C(·, ˜ can be formulated as [7, 32] Z∞ Z∞ 2 ˜ = bH D3 b − bH D2 a − aH D2 H b + w(τ , fd )d(τ , fd ) d τ d fd  C(b) −∞ −∞ −1 H H −1 H = (b − D3 D2 a) D3 (b − D3 D2 a) + C, (28) where constant C does not depend on sequence b and therefore can be ignored. Then, in view of (28), the minimizer b can be obtained as b = D−1 H 3 D2 a, (29) where D3 ∈ CN×N is given as Z ∞Z ∞ D3 = w(τ , fd )X(τ , fd )aaH XH (τ , fd )d τ d fd . (30) −∞ −∞ 4.1 Proposed Approach In the proposed approach, the phases of the elements of sequence a ∈ CN×1 and sequence b ∈ CN×1 , respectively, are denoted by column vectors of length N as φa = [φa (1), φa (2), . . . , φa (N)]T , (31) φb = [φb (1), φb (2), . . . , φb (N)]T . (32) In the context of IBA, each element of the column vectors φa and φb in (31) and (32), respectively, is considered as a single bat generated randomly in the interval [0, 2π ]. The population size (bats) is equal to the length N of the sequences. Then, the corresponding sequences a and b, respectively, are given as a = [eφa (1) , eφa (2) , . . . , eφa (N) ]T , (33) φb (1) φb (2) φb (N) T b = [e ,e ,...,e ] . (34) Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 11 Given the above notion of sequence elements being bats, the pseudocode to solve the CAF synthesization problem using IBA can be formulated as in Procedure 1. Procedure 1: Pseudocode of IBA for CAF synthesization. 1. Objective function C( ˜ θ (τ , fd ), a, b) 2. Initialize Ai , fi , and ri . 3. Generate the cross-ambiguity matrix using (20). for all NP bats 4. Generate an initial population of NP bats (solutions) to generate sequences a and b using (33) and (34), respectively, or use initially generated sequences. 5. θ (τ , fd ) = arg{bH X(τ , fd )a} 6. Start with initially generated sequence in Step 4 by applying (25) to generate a. 7. Start with initially generated sequence in Step 4 by applying (29) to generate b. 8. Evaluate the objective function using (22). end 9. Store the best objective function value. 10. Keep the current best sequences a and b. t=1 while (t < MaxGeneration) or (stop criterion) t =t +1 11. Update pulse emission rate and loudness using (17) and (18). 12. Update the velocity and frequency using (12) and (14). 13. θ (τ , fd ) = arg{bH X(τ , fd )a} 14. Start with sequences generated in Step 6 and 7 to generate a′ and b′ by applying (25), (29), and (13). 15. if (rand > r) Start with sequences in Step 10 to generate a′ and b′ by performing LF using (25), (29), and (15). end 16. Apply problem bound constraints, if the sequences generated in Step 14 or Step 15 are outside the interval [0, 2π ]. 17. Re-evaluate the objective function using (22). 18. if (C˜Step 16 ≤ C˜Step 8 | rand < A) Replace the sequences in Step 6 and Step 7 with a′ and b′ . C˜Step 8 ← C˜Step 17 end 19. if C˜Step 17 ≤ C˜Step 9 Replace the sequences in Step 10 with a′ and b′ . C˜Step 9 ← C˜Step 17 end end while 12 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 4.2 Parameter Settings Universal values of the parameters At0 , rt0 , Γ , and ϒ do not exist for the problems that will be discussed in Section 5. This is due to the fact that each problem has a different landscape and dimension. Hence, an effective set of initial values of these parameters require some experimentation. Accordingly, the initial values for these parameters were obtained from trial experiments on the optimization problems that will be considered in Section 5. Different initial values for loudness A and pulse emission rate r were taken in the range [0, 1] with increments of 0.1. For each opti- mization problem, the selected values of At0 , rt0 , Γ , and ϒ produced slightly differ- ent rates of convergence as each optimization problem has a different landscape. In reality, bats increase pulse emission rate ri and decrease loudness Ai after po- tential prey has been detected and their approach towards the prey has commenced. In the context of optimization, prey refers to a solution of the problem. As such, an update of loudness Ai and pulse emission rate ri in (17) and (18), respectively, takes place in the IBA only if a new solution is found. This implies that the virtual bats are moving towards the optimal solution. The above experimental approach was also adapted to select the values of con- stants ϒ and Γ . The best combination of ϒ and Γ was found to be ϒ = Γ = 0.5. The results that will be presented subsequently in Section 5 show that this choice of parameters seems to be appropriate for the optimization problems considered. In summary, the parameter settings listed in Table 1 are used in the simulations. Table 1: Parameter Setting for IBA. Parameter Value Number of Bats (Population Size), NP depending on the length of the sequence to be synthesized Number of Generations, G 200 Initial Loudness, At0 0.1 Initial Pulse Emission Rate, rt0 0.1 Constants, ϒ = Γ 0.5 L´evy Step Length, S 1.5 Minimum Frequency, f min 0 Maximum Frequency, f max depending on the problem domain size 4.3 Calculation of L´evy Step Size A CAF synthesization problem can be considered as multimodal optimization prob- lem without any a priori information regarding the location of an optimal solution. LFs can be used to generate the random step length S of a random walk drawn from Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 13 a L´evy distribution. The choice of α in (16) determines the probability of obtaining a L´evy random number in the tail of the L´evy distribution. Given that each opti- mization problem is unique, i.e., has different dimension and landscape, the task of choosing a favorable value of α that generates a suitable step length S becomes dif- ficult. In particular, the search ability of the algorithm may be severely hampered, if an improper value of α is used to generate S. Given the complex nature of the CAF synthesization problem, it seems that a universal value of α required to generate S for guiding virtual bats in IBA without getting trapped in a local minimum does not exist. Therefore, it is appropriate to carry out a series of experiments in order to find a suitable value of α . For this purpose, four values of α = 1.3, 1.4, 1.5, and 1.6 were selected. For each of these values, 10 independent trials for a fixed number of iterations were performed to minimize (22) for the problems that will be discussed in Section 5. It turned out that α = 1.5 produces the best value of criterium (22) in average over the number of trails. Therefore, this value has been used to generate the random step length S for all problems considered in Section 5. 4.4 Selection of Scaling factor The parameter γ in (15) determines how far the virtual bats in IBA can travel in the search space. An excessively large value of γ causes new solutions to jump outside of the feasible search space and even to fly off to far regions. On the other hand, the search is confined to a rather narrow region, if γ is too small. In the former case, the LF becomes too aggressive, whereas, in the latter case, the LF is not efficient. Therefore, some sort of strategy is needed to scale step length S such that an effi- cient search process is maintained. In order to avoid the particles/bats flying too far, a small value of parameter γ can be more efficient [40, 41]. A small value of γ may apply for unimodal problems. We hypothesize that the location of an optimal solu- tion to a multimodal problem such as CAF synthesization is not known. As such, selecting a small value of γ will hinder the search process. Therefore, in order to select an appropriate value of γ , we have adopted the ex- perimental approach described in Section 4.3 and conducted a series of trials with different values of γ . We have conducted 10 independent trails for a fixed number of iterations that were performed to minimize (22) for Example 2 in Section 5 using γ = 0.01, 0.05, 0.1, 0.5, 0.7 and 0.9. The best peak-to-average power ratio (PAR) for each of these values produced by IBA for each run was recorded. It was found that γ = 0.05 produces the best PAR and hence was subsequently used as a basis for the examples presented in Section 5. 14 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 5 Numerical Results Let us consider sequences of length N = 50 for Examples 1 and 2, sequence length N = 53 for Example 3 and sequence length N = 31 for Example 4. Each element of the considered sequences corresponds to the phase-coded amplitude of a rectangular pulse shape function of duration Tc . Thus, the duration of a sequence is given as T = N · Tc . Furthermore, τ denotes the delay by which a transmitted signal is returned from a target and fd denotes the Doppler frequency induced by a moving target. In the sequel, we utilize normalized delay τ /Tc and normalized Doppler frequency fd · T , respectively. In what follows, we illustrate by way of four examples that IBA is able to jointly design sequences a and b such that a desired CAF is synthesized. 5.1 Example 1 In this example, we aim at synthesizing a CAF with a diagonal ridge while being zero elsewhere. This type of CAF is desirable when a filter bank is too expensive to cope with different Doppler frequencies and tolerance to Doppler shifts is needed. The weighting function is w(τ , fd ) = 1 for all (τ , fd ) in (19) and the sequence a has constant modulus, i.e., each element of a takes on the value of one and hence PAR = 1. The desired CAF is shown in Fig. 1 and the corresponding synthesized CAF obtained by using IBA is shown in Fig. 2. As can be seen from Fig. 2, the CAF synthesized by IBA approximates the desired CAF in Fig. 1. 0 20 −5 10 −10 −15 Doppler 0 −20 −10 −25 −30 −20 −35 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay Fig. 1: Desired CAF with diagonal ridge. Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 15 0 20 −5 10 −10 −15 Doppler 0 −20 −10 −25 −30 −20 −35 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay Fig. 2: Synthesized CAF using IBA for γ = 0.05 (PAR = 1). 5.2 Example 2 The synthesization of an ideal thumbtack CAF, i.e., narrow peak at the origin and zero sidelobes in the rest of the delay-Doppler plane is not possible due to the vol- ume property of CAFs. Therefore, in this example, we aim at synthesizing a CAF with a clear area in and around a large neighbourhood of the origin using the fol- lowing CAF modulus: ( N, for (τ , fd ) = (0, 0), d(τ , fd ) = 0, elsewhere, and weighting function ( 1, for (τ , fd ) ∈ Ωds \Ω∼ds , w(τ , fd ) = 0, elsewhere, where Ωds = {[−10Tc , 10Tc ]× [− T2c , T2c ]} is the selected region of interest of the syn- thesized CAF. In order to compensate for sharp changes in the desired CAF d(τ , fd ) near the origin, the area of the main lobe Ω∼ds = {[−Tc , Tc ]\{0} × [− T1c , T1c ]\{0}} near the origin has to be excluded [12]. Recall that the Doppler shift fd induced on the signal in practice is often much smaller compared to the bandwidth of the transmitted signal. Therefore, the weighting function w(τ , fd ) outside the maximum induced Doppler shift fd can be set to zero. The need of this type of CAF arises in applications such a geolocation of signals, where the CAF is used to calculate the time of difference of arrival and frequency 16 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ difference of arrival of the emitted signal using two receivers [21]. The two collector architecture offers the opportunity to compare the reception of a likely similar radar pulse using cross-correlation concepts with respect to delay. Thus, one collector will see the radar pulse as a(t) and the other collector will see it as b(t + τ ). Also, it is assumed that one collector is moving with some relative velocity to the other collector which supports measuring the frequency of the received pulse at slightly different frequencies [21]. Furthermore, a CAF with a clear area around a large neighbourhood of the origin also arises in situations, when it is not possible to design a sequence or set of se- quences that yield zero sidelobes over the entire delay-Doppler plane. Therefore, it is desirable to design a reference waveform or equivalent filter at the radar receiver end. Such a receiver, is called an optimum receiver [34] in which the internal or ref- erence waveform (or equivalent filter) is deliberately mismatched compared to the transmitted waveform in order to reduce the sidelobes in the delay-Doppler plane. Fig. 3 shows the CAF of sequences a and b generated by IBA with γ = 0.05. The desired sidelobe free area can be observed within the rectangular area close and around the origin. The sidelobe free region in Fig. 3(a) is due to the fact that the amplitude of the generated sequences a or b is not constrained. This may result in sequences with relatively high PAR and relatively low sidelobe levels. The PAR of sequences a and b for the CAF shown in Fig. 3(a) were found to be PARa = 3.9 and PARb = 7.2, respectively. It is noted that low sidelobe levels are desirable in radar applications to avoid masking of main peaks of secondary targets, even if the targets are well separated. Moreover, in case of a multiple target environment, the sum of all sidelobes may build up to a level sufficient to mask even relatively strong targets. The widespread use of solid state power amplifiers and digitization can have a significant impact on the overall performance of radar, sonar, and communication systems. For example, the transmission of a signal or a waveform of arbitrary ampli- tude is not possible due to the limitations of power amplifiers and analog-to-digital converters. As a result, it is often desirable that transmit signals or waveforms have a constant amplitude or a low PAR. One of the possibilities that allows the consid- eration of waveforms with variable amplitude is to work with a pair of waveforms, i.e., the transmitted signal of constant amplitude and the reference signal of arbi- trary amplitude that is used during signal processing at the receiver [19]. Therefore, to constrain the PAR of a transmit waveform with PAR=1, the following additional operation may be employed in the IBA algorithm in Procedure 1 after Step 14 (see also [12]): sn ← exp[ j arg(sn )]. (35) However, inducing such a constraint further complicates the design of waveforms with prescribed ambiguity surfaces. Using (35), somewhat higher sidelobes can be observed in the results shown in Fig. 3(b). The normalized zero-Doppler cut through the CAF for the unconstrained design (PAR > 1) and constrained design (PAR = 1) are shown in Fig. 4. Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 17 0 20 −5 10 −10 −15 Doppler 0 −20 −10 −25 −30 −20 −35 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay (a) 0 20 −5 10 −10 −15 Doppler 0 −20 −10 −25 −30 −20 −35 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay (b) Fig. 3: CAF synthesization without and with PAR constraint (35) for γ = 0.05: (a) Synthesized CAF of random sequences of length N = 50 (PAR = 3.9), (b) Synthe- sized CAF of random sequences of length N = 50 (PAR = 1). 5.3 Example 3 In this example, we aim at synthesizing a CAF for Bj¨orck sequences of length N = 53. In particular, Bj¨orck sequences of length N = P, where P is a prime number and P ≡ 1(mod 4), are defined as 18 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 0 PAR = 3.9 Normalized Ambiguity Cut for fd = 0 PAR = 1.0 −15 −30 −45 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay Fig. 4: Normalized zero-Doppler cut of the CAFs of Fig. 3(a) and (b) without and with constraint (35), respectively.      k 1 B(k) = exp j2πθ , θ = arccos √ , (36) P 1+ P where ( Pk ) denotes the Legendre symbol which is defined as  1,    if k ≡ 0 (mod P), k = 1, if k ≡ m2 (mod P) for m ∈ Z, P  6 m2 (mod P) for m ∈ Z. −1, if k ≡  The synthesized CAFs for the case of Bj¨orck sequences which approximates a desired thumbtack CAF without and with using constraint (35) are shown in Fig. 5(a) and (b), respectively. The normalized zero-Doppler cuts through the CAFs for the unconstrained design (PAR > 1) and the constrained design (PAR = 1) are shown in Fig. 6. A sidelobe level below −45dB respective −30dB can be observed for these cases. 5.4 Example 4 Finally, we synthesize a CAF for the case of Oppermann sequences [20] of length N = 31. The phase ϕk (i) of the i-th element uk (i) of the k-th Oppermann sequence uk = [uk (0), uk (1), · · · uk (N − 1)] of length N is defined as Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 19 0 20 −5 10 −10 −15 Doppler 0 −20 −10 −25 −30 −20 −35 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay (a) 0 20 −5 10 −10 −15 Doppler 0 −20 −10 −25 −30 −20 −35 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay (b) Fig. 5: CAF synthesization without and with (35) for γ = 0.05: (a) Synthesized CAF for Bj¨orck sequence of length N=53 (PAR=4.9), (b) Synthesized CAF for Bj¨orck sequence of length N=53 (PAR = 1). π m ϕk (i) = [k (i + 1) p + (i + 1)n + k(i + 1)N], (37) N where 1 ≤ k ≤ N − 1, 0 ≤ i ≤ N − 1 and integer k is relatively prime to the length N. The parameters m, n and p in (37) take on real values and define a family of Oppermann codes. 20 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 0 PAR = 4.9 Normalized Ambiguity Cut for fd = 0 PAR = 1.0 −15 −30 −45 −50 −40 −30 −20 −10 0 10 20 30 40 50 Delay Fig. 6: Normalized zero-Doppler cut of the CAFs shown in Fig. 5(a) and (b) without and with constraint (35), respectively. The CAF for the case of Oppermann sequences with parameters m, p = 1 and n = 3 is shown in Fig. 7. The synthesized CAF of these Oppermann sequences is shown in Fig. 8, which approximates the desired CAF with a sidelobe free area around the neighbourhood of the origin. Relatively low sidelobe levels can be observed within the rectangular area close and around the origin with improved delay-Doppler characteristics compared to the CAF of the original sequence that is shown in Fig. 7. The zero-Doppler cut of the synthesized Oppermann sequence is shown in Fig. 9 which exhibits a low sidelobe level with respect to delay compared to the original Oppermann sequences. Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 21 20 0 −5 10 −10 Doppler 0 −15 −20 −10 −25 −20 −30 −30 −20 −10 0 10 20 30 Delay Fig. 7: Synthesized CAF of Oppermann sequences with parameters m, p = 1, and n = 3. 20 0 −5 10 −10 Doppler 0 −15 −20 −10 −25 −20 −30 −30 −20 −10 0 10 20 30 Delay Fig. 8: Synthesized CAF of Oppermann sequences with γ = 0.05 and using con- straint (35). 6 Conclusions In this chapter, the problem of synthesizing CAFs using a metaheuristic approach based on the echolocation of bats has been addressed. The fundamental problem in this context is to minimize the integrated square error between a desired CAF and a synthesized CAF. In particular, the IBA has been combined with a cyclic approach 22 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 0 Original Oppermann Seq Synthesized Seq Normalized Ambiguity Cut for fd = 0 −15 −30 −45 −30 −20 −10 0 10 20 30 Delay Fig. 9: Normalized zero-Doppler cuts through the CAFs shown in Fig. 7 and 8. to solve this problem. By using four examples, we have shown that the approach based on echolocation of bats can indeed synthesize CAFs that approximate CAF surfaces having a diagonal ridge and zero value elsewhere as well as CAF surfaces with a clear area around the origin. Our results indicate that the proposed approach is a promising technique for synthesizing CAFs. Further research will focus on more extensive studies of how to synthesize other complex functions and waveforms. References 1. Austin, D., Bowen, W. D., McMillan, J. I.: Intraspecific variation in movement patterns: Mod- elling individaul behaviour in a large marine predator. Oikos 105(1), 15–30, (2004). 2. Bartumeus, F., Peters, F., Pueyo, S., Marrase, C., Catalan, J.: Helical L´evy walks: Adjust- ing searching statistics to resource avaliability in microzooplankton. Proc. National Academy Science, USA, 100(22), 12771–12775, (2003). 3. Benedetto, J. J., Konstantinidis, I., Rangaswam, M.: Phase-coded waveforms and their design – The role of ambiguity function. IEEE Signal Processing Magazine, 26(1), 22–31, (2009). 4. Blau, W.: Synthesis of ambiguity functions for prescribed responses. IEEE Trans. on Aerospace and Electronic Systems, 3(4), 656–663, (1967). 5. Blunt, S. D., Gerlach, K.: Adaptive pulse compression via MMSE estimation. IEEE Trans. on Aerospace and Electronic Systems, 42(2), 572–584, (2006). 6. Delong Jr., D. F., Hofstetter, E. M.: The design of clutter-resistant radar waveforms with lim- ited dynamic range. IEEE Trans. on Information Theory, 15(3), 376–385, (1967). 7. Fienup, J. R.: Phase retrival algorithms: A comparison. Applied Optics, 21(15), 2758–2769, (1982). 8. Gladkova, I., Chebanov, D.: On the synthesis problem for a waveform having a nearly ideal ambiguity function. International Conference on Radar Systems, Toulouse, France, (2004). 9. Glover, F.: Tabu search - Part I. ORSA Journal of Computing, 1(3), 190–206, (1989). Synthesizing Cross-Ambiguity Functions Using the Improved Bat Algorithm 23 10. Glover, F.: Tabu search - Part II. ORSA Journal of Computing, 2(1), 4–32, (1990). 11. Gutowski, M.: L´evy flights as an underlying mechanism for global optimization algorithms. Proc. National Conf. on Evolutionary Computation and Global Optimization, Jastrze¸bia G´ora, Poland, (2001). 12. He, H., Stoica, P., Li, J.: On synthesizing cross ambiguity function. IEEE International Con- ference on Acoustics, Speech and Signal Processing, Prague, Czech Republic, (2011). 13. Humphries, N. E., Querioz, N., Dyer, J. R. M., Pade, N. G., Musyl, M. K., Schaefer, K. M., Fuller, D. W., Brunnschweiler, J. M., Doyle, T. K., Houghton, J. D. R., Hays, G. C., Jones, C. S., Noble, L. R., Wearmouth, V. J., Southall, E. J., Sims, D. W.: Environmental context ex- plains L´evy and Brownian movement patterns of marine predators. Nature, 451(7301), 1066– 1069, (2010). 14. Jamil, M., Yang, X-S., Zepernick, H.-J.: Improved Bat-inspired metaheuristic algorithm with L´evy flights for global optimization problems, Journal of Appied Soft Computing – Under Revision. 15. Jamil, M., Zepernick, H.-J., Yang, X-S.: L´evy flight based cuckoo search algorithm for syn- thesizing cross-ambiguity functions, IEEE Military Communications Conference, 823–828, San Diego, USA, (2013). 16. Kay, S.: Optimal signal design for detection of Gaussian point targets in stationary Gaussian clutter/reverberation. IEEE J. of Selected Topics in Signal Processing, 1(1), 31–41, (2007). 17. Key, E. L.: A method of sidelobe reduction in coded pulse waveform. Tech. Report 209, M.I.T Lincoln Lab., Lexington, Mass., (1959). 18. M˚arell, A. J., Ball, P., Hofgraad, A.: A foraging and movement paths of female reinedeer: Insights from fractal analysis, correlated random walks and L´evy flights. Canadian Journal of Zoology, 80(5), 854–865, (2002). 19. Levanon, N., Mozeson, E.: Radar Signals. John & Wiley, 2004. 20. Oppermann, I., Vucetic, B.S.: Complex spreading sequences with a wide range of correlation properties. IEEE Trans. on Commununications, 45(3), 365–375, (1997). 21. Overfield, J., Biskaduros, Z., Buehrer, R. M.: Geolocation of MIMO signals using the cross ambiguity function and TDOA/FDOA. IEEE International Conference on Communications, 3648–3653, Ottawa, Canada, (2012). 22. Rihaczek, A. W., Mitchell, R. L.: Radar waveforms for suppression of extended clutter. IEEE Trans. on Aerospace and Electronic Systems, 3(3), 510–517, (1967). 23. Rummler, W. D.: A technique for improving the clutter performance of coherent pulse train signals. IEEE Trans. on Aerospace and Electronic Systems, 3(6), 898–906, (1967). 24. Shlesinger, M. F., Zaslavsky, G. M., Frisch, U. (Eds): L´evy flights and related topics in physics. Springer, Heidelberg, (1995). 25. Sharama, R.: Analysis of MIMO radar ambiguity function and implications on clear region. IEEE International Radar Conference, Washington DC, USA, (2010). 26. Siebert, W.: A Radar Detection Philosophy. IRE Trans. on Information. Theory, 2(3), 204– 221, (1956). 27. Spafford, L. J.: Optimum radar signal processing in clutter. IEEE Trans. on Information The- ory, 14(5), 734–743, (1968). 28. Stein, S.: Algorithms for ambiguity function processing. IEEE Trans. on Acoustics, Speech, and Signal Processing, 29(3), 588–599, (1981). 29. Stoica, P., Li, J., Xue, M.: Transmit codes and receive filters for radar. IEEE Signal Processing Magazine, 25(6), 94–109, (2008). 30. Stoica, P., He, H., Li, J.: New algorithms for designing unimodular sequences with good cor- relation properties. IEEE Trans. on Signal Processing, 57(4), 1415–1425, (2009). 31. Stutt, C., Spafford, L. J.: A ‘best’ mismatched filter response for radar clutter discrimination. IEEE Trans. on Information Theory, 14(2), 280–287, (1968). 32. Sussman, S.: Least-square synthesis of the radar ambiguity function. IEEE Trans. on Informa- tion Theory, 8(3), 246–254, (1962). 33. Urkowitz, H.: Some high-velocity clutter effects in matched and mismatched receivers. IEEE Trans. on Aerospace and Electronic Systems, 4(3), 481–485, (1968). 24 Momin Jamil∗† , Hans-J¨urgen Zepernick∗ , and Xin-She Yang‡ 34. Van Tress, H. L.: Optimum signal design and prcoessing for reverberation-limited environ- ment. IEEE Trans. on Military Electronics, 9(3), 212–229, (1965). 35. Viswanathan, G. M., Afanasyev, V., Buldyrev, S. V., Murphy, E. J., Prince, P. A., Stanley, H. E.: L´evy flight search patterns of wandering albatrosses. Nature, 381(6581), 413–415, (1996). 36. Viswanathan, G. M.: Fish in L´evy-flight foraging. Nature 465(7301), 1018–1019, (2010). 37. Wilcox, C. H.: The synthesis problem for radar ambiguity functions. MRC Tech. Summary Report 157, US Army, Univ. of Wisconsin, Madison, Wisconsin, USA, (1960). Reprint: Radar and Sonar, Part 1, The IMA Volumes in Mathematics and its Applications, Springer-Verlag, (1991). 38. Wolf, J. D., Lee, G. M., Suyo, C. E.: Radar waveform synthesis by mean-square optimization techniques. IEEE Trans. on Aerospace and Electronic Systems, 5(4), 611–619, (1969). 39. Woodward, P.M.: Probability and information theory with applications to radar. Pergamon Press, (1953). Reprint: Artech House, London (1980). 40. Yang, X-S., Deb, S.: Cuckoo search via L´evy flights. Congress on Nature and Biological Inspired Computing, 210-214, Coimbatore, India (2009). 41. Yang, X-S.: Firefly algorithm, L´evy flights and global optimization. Research and Develop- ment in Intelligent Systems XXVI (Eds. M Bramer, R. Ellis, M. Petridis), 209-218, Springer (2010). 42. Yang, X-S.: A new metaheuristic bat-inspired algorithm. Nature Inspired Cooperative Strate- gies for Optimization (Eds. J. R Gonzalez et. al), Studies in Computational Intelligence, 65-74, Springer (2010). 43. Yang, X-S., He, X.: Bat algorithm review and applications. Int. J. Bio-Inspired Computation, 5(4), 141–149 (2013).