HUANG Xiaowei and SHENG Xinqing

Institute of Radio Frequency Technology and Software, School of Integrated Circuits and Electronics, Beijing Institute of Technology, Beijing 100081, China

Abstract: This paper presents a novel method for fast calculation of radar echo in near-field regions after the equivalent source has been computed by method of moments (MoM).An easy-to-access near-field database (NFDB)is established, which is built on the auxiliary tetrahedral meshes surrounding the nearfield regions of interest.The near-fields calculation (NFC)of arbitrary observation points can be expressed explicitly via the NFDB.An efficient matrix compression scheme named random sampling-based butterfly factorization (RS-BF)is proposed to speed up the construction of NFDB.With this approach, each group of O(N)elements in the database can be calculated through one fast matrix-vector multiplication operation that has a computational complexity below O(Nlog2N).The proposed method can avoid time-consuming point-by-point NFC of the traditional methods.Several numerical examples are presented to demonstrate the accuracy and efficiency of this method.In particular, the echo simulation of a missile-target encounter example is presented to illustrate its capability for practical applications.

Keywords: radar echo simulation, near-field database (NFDB),butterfly factorization (BF).

1.Introduction

The simulation of radar echo in near-field regions has always been a topic of interest and is widely used in electromagnetic (EM)compatibility analysis, radio fuse simulations, bio-electromagnetic safety assessment, and a number of other areas [1-5].The essence of radar nearfield echo simulation is to calculate the EM scattering field of objects in near-field regions.Compared to the measurement of the radar echo, numerical simulation is a power tool to handle such problem due to its low cost and flexibility.Over the past decades, many numerical methods have been developed for radar echo simulation [6].Among them, surface integral equations (SIE)are commonly used, where equivalent currents are defined on the surface of the objects and method of moments (MoM)[7,8] is employed to obtain the final solutions.

In this paper, we restrict our attention to the post-processing stage.To be specific, we consider the fast calculation of the EM near-fields that are produced by the available equivalent currents.According to the SIE formula, calculating near-field for each observation point requires integrations over all meshes on the surface.Generally, the computational cost is trial if there are only a few observation points.However, in many practical applications, both the number of source points and observation points are very large.Besides, there are many cases where the positions of the observation points are not fixed but vary with time or change in a wide space.Consequently, the conventional method for the calculation of near-fields will be very time-consuming.

In this paper, we propose a novel method for radar echo simulation in near-field regions based on a fast-constructed database.Different from the previous point-by-point calculation methods, we first construct an easy-to-access near-field database (NFDB)off-line, and then the nearfields of any observation points distributing in the space of interest could be obtained quickly through the access of NFDB.This method is more flexible for those applications that the positions of observation points vary with time.In addition, we also propose a method for efficiently building the NFDB.Inspired by the butterfly factorization (BF)[9-13] implementation on compressing the matrix resulting from discretization of the integral equation (IE)operator, we propose a random samplingbased (RS)butterfly decomposition to speed up the construction of NFDB.The RS-BF is an efficient tool for matrix compression and matrix-vector multiplication operation.Compared to previous work about butterfly al-gorithms, the algorithm proposed here is more convenient to be executed in parallel.With this approach, each group ofO(N)elements in the database can be calculated through a fast matrix-vector multiplication operation that has a computational complexity belowO(Nlog2N).

The rest of this paper is organized as follows.In Section 2, the background of near-fields calculation (NFC)is introduced.Then a detailed description of the proposed method is given in Section 3.In Section 4, several numerical examples are presented to demonstrate the performance of this method.Especially, we present an echo simulation of a missile-target encounter to show the practical applications of the proposed method.Conclusions are made in Section 5.

2.Background

Without loss of generality, consider the electric NFC of an arbitrarily shaped perfect electrical conductor (PEC)object immersed in free space, illuminated by incident wavesEincandHinc.The formulation of the electric nearfield can be derived as

wherez0denotes the wave impedance in free space,?and ?′denote the differential operator applied to the observation pointrand source pointr′, respectively,is the Green’s function withR=|r-r′|and wavenumberk0=2π/λ0,J(r′)is the equivalent electric current distributed on the surfaceS′of the object.

Generally,J(r′)is discretized by Rao-Wilton-Glisson(RWG)[14] basis functions on the triangular surface elements as

whereJjis the expansion coefficient,fj(r′)is thejth RWG function, andNis the number of basis functions.The evaluation of the expansion coefficients can be obtained according to any solution technologies of matrix equations [15].Substituting (2)into (1)yields

whereTjis a pair of triangles on which thejth RWG is defined.

The near-field problem to be studied in this paper is described as follows.Suppose that the coefficients in (2)are already available, the goal is to quickly solve the nearfields of a set of observation pointsri(i=1,2,···,Nob).The number of the observation pointsNobhas the same scale as the current coefficients, i.e.,Nob∝O(N), and the coordinates are not fixed but vary in a spatial range.According to (1), the above problem can be written as a matrix equation of the following form:

It is shown in (4)that the traditional method which needs to evaluate every element ofZis inefficient, particularly whenNandNobbecome very large.Besides,there will be many repeated jobs of the whole processes once the positions of the observation points change.These limitations motivate us to develop a method with fast speed and data reuse property.

3.NFC using database

3.1 Overall framework

The flow chart of calculating the near-fields using database is shown in Fig.1, including the following steps:

Step 1Surround the near-field space of interest and then mesh it with auxiliary tetrahedrons.The meshes can be generated by the exiting computer-aided design software.In this paper, software CATIA V5 is adopted.The average mesh size can be set as 0.05 λ0-0.1 λ0.

Step 2Build the bounding box for all tetrahedrons,then split these tetrahedrons into two almost equal-size son groups along the longest axis of box.This operation is done recursively until each group involves only one tetrahedron.All the tetrahedron groups form a binary tree.The nodes of tree, together with the tetrahedrons’ edges and vertices are renumbered by the global indexes and put into the database.

Step 3Compute the tangential near-fields at the midpoints of all tetrahedrons’ edges using

whereBdenotes the expansion coefficients with each column corresponding to different radar parameters such as incident angles and polarizations,Zthas entries as follows:

Step 4For each observation point, traverse the tetrahedron binary tree to find which tetrahedron it belongs to.

Step 5Compute the near-field of each observation point using edge-element interpolation.

As shown in Fig.1, Steps 1-3 are the database construction processes, which can be finished off-line.After the construction, NFDB comprises three parts, i.e., geometric information, radar parameters, and tangential fields.Steps 4-5 are the database access processes, which can be implemented on-the-fly.More details of the important steps will be further explained in the following.

Fig.1 NFC via the database

3.2 RS-BF

The key step in constructing the database is to calculateEt=Zt·B.From (7)we find elements ofZthave integral expressions involving Green’s function, which is very similar to the impedance matrix of the discretization of IE, and the latter has been confirmed in the exiting literature that BF can be applied for accelerating the matrixvector multiplication efficiently [9-13].Therefore, one can believe that BF could also be used to compressZtand speed up the calculation ofZt·B.

Inspired by the randomized matrix decomposition algorithms presented in recent years [16,17], we propose the RS-BF, which is purely algebraic and can approximate the original matrix using only partial matrix elements.The RS-BF is implemented after the hierarchal matrix partition.First, a so-called cluster tree for the observation points and source points should be created separately.To be specific, the observation (source)points are divided into two almost equal number subgroups recursively.This operation is repeated recursively until the smallest groups contain approximatelyO(1)points, resulting in a complete binary cluster treeTI(TJ)[18], the depth of which is denoted byLH.The next procedure is to build the block cluster tree.From root to leaves, two clusters with the same level can form an admissible block if they are wellseparable [19].Otherwise, this operation should be done in the next level if clusters still have sons.Finally, the block cluster is obtained whose leaves can be mapped to a hierarchical matrix structure, as is shown in Fig.2.

Fig.2 Cluster tree and the hierarchical matrix structure

Once the hierarchical structure has been constructed,we can fill the matrix in a compressed form.For those inadmissible blocks (see the blocks marked withFin Fig.2), the entries of the submatrix are directly calculated; while for those admissible ones (blocks marked withR), RS-BF can be used.

Fig.3 Process of the BF

RS-BF fills these interaction pairs with low-rank factorization from out-to-inner, as shown in Algorithm 1.Consequently, the full matrixcan be approximated byL-block sparse matrices

whereRi(i=0,···,L+1)is block-sparse matrix.

Algorithm 1RS-BF

Input:relative tolerances ε, sampling factor χ, index setsO,S, levelsL

Output:=RL+1·RL·····R1·R0

In Algorithm 1, symbol “A?” denotes the pseudo-inverse, R sp(X,n)denotes the operation of samplingnelements randomly from index setX(in this paper, the uniform sampling is used), #Xdenotes the number of elements in setX, and S kt(A,ε)represents the column skeletonization of matrixAwith relative tolerance ε.In this paper, the rank revealing QR (RRQR)is employed to obtain the skeleton index sets [20].From Algorithm 1 we can see the RS-BF can maintain a fast speed because of the random sampling and skeletonization.Besides, the factorization processes start from levels at both ends level=0 and level=L+1 to the middle level, which can be efficiently implemented in parallel.These characteristics make RS-BF different from existing methods [9-13],though the similar structure can be obtained as shown in Fig.3(b).

3.3 Edge-element interpolation

Interpolation is another key step that ensures fast NFC of unfixed-position observation points.Inspired by the discretization of the finite element method (FEM), edge-element interpolation is adopted to calculate the near-field inside the tetrahedral meshes.As can be seen in Fig.4, the near-field of each observation point can be interpolated by

Fig.4 Tetrahedral and edge-element interpolation

whereNk(ri)is the vector basis function for edgek, andEtkis the tangential field component along the edge-center of the tetrahedron surrounding it.The detailed formulations refer to [21].

With the aid of the edge-element interpolation, the access of the NFDB can be done by Algorithm 2.

Algorithm 2Fast access of NFDB

Input:ri(i=1,2,···,Nob), tetrahedron treeTtet, incident state numbern

Output:E(ri)

3.4 Complexity analysis

In this section, we will derive the memory and computa-tional complexities of the proposed method.LetNDBdenote the number of not repeated edges of tetrahedral meshes,Ndenote the number of source coefficients and supporting thatNDBis proportional toN.

Note that the observation and source cluster trees that make up the hierarchical matrix of NFC are not the selfinteraction.This means that the structure of the matrix partition is not symmetrical.Therefore, there is no uniform formula for the complexity estimations.Nevertheless, the upper bound and lower bound can be derived.Consider a special case that the tetrahedrons are distributed close to the surface of the object, thenTIandTJwill become almost the same.In this case, the storage and computational complexity of the proposed method during database construction would beO(Nlog2N)[9,12].This is the upper bound.Another special case is that the roots of both observation and source cluster trees satisfy the admissible condition.In this case, the whole matrix forms one admissible block compressed by BF.The complexity would beO(NlogN).This is the lower bound.In practice, the complexity belowO(Nlog2N)can be observed with both storage and CPU time cost.As for the complexity of the database access phase, Algorithm 2 is very similar to the binary search, which has a CPU complexityO(NlogN).

4.Numerical results

In this section several numerical examples will be presented to study the performance of the proposed method.All the numerical examples are performed on a server with four fourteen-core 64-bit Intel Xeon E7-4 850 CPUs and 1 TB of RAM.The sampling factor of RS-BF is set as 1.2 and tolerance is set as 1 0-3.Without loss of generality,suppose the radar parameters are fixed and the coefficient matrix in (6)only has one column, then NFDB involves only one group of data.

4.1 Accuracy and efficiency

First, we show the NFC of a PEC sphere to verify the efficiency and accuracy of the proposed method.Our new approach will be compared with the conventional method via performing integrations over the entire surface.The sphere is illuminated by the plane wave ofx-polarized and propagating along -z-direction at frequencyf=c/λ0, whereais a coefficient controlling the size of the sphere.As illustrated in Fig.5, the radius of the sphere isaλ0, and the mesh size of the sphere is λ010.The observation points are uniformly distributed in a square area with an average distance λ020.This square area has a side length 2aλ0with a distanced=raway from the sphere.To calculate the near-fields of these points, we surround this area with a box of dimension 2aλ0×2aλ0×λ0and discretize it with tetrahedral meshes of average size λ0/10.Increasingafrom 1 to 8, the resulting parameters are listed in Table 1.

Fig.5 NFC of a sphere model

Table 1 Parameters corresponding to the increasing size of the sphere

NFC through NFDB involves two phases, i.e., database construction and access.Fig.6 shows the CPU-times of both phases and their complexity estimations, compared to the conventional method.As can be seen in Fig.6,the CPU time for NFC by the conventional method scales asO(N2), which is time-consuming and undesirable.In contrast, the proposed method has anO(NlogN)DB access complexity and a slightly lower thanO(Nlog2N)DB construction complexity.Since the time cost of DB access is much shorter than that of DB construction, the total CPU time in Fig.6 also shows a complexity belowO(Nlog2N).Generally, the computation of the construction of the database can be finished off-line.Therefore,the near-field of arbitrary observation point can be obtained almost instantaneously.

Fig.6 Computational complexity of the proposed method and the conventional method

The storage requirements of the proposed method are listed in Table 2, where the peak memory of equivalent currents solutions is also listed.Table 2 shows that the proposed method will not increase the peak memory.After the database is constructed, only a small amount of memory is needed for the storage of the database.

Table 2 Memory requirements of the proposed method at different stages MB

Finally, the near-field distributions under the parameters of the last group in Table 1 are plotted in Fig.7,where excellent agreement can be seen.The relative error based onL2norm between two figures is 0.95%.

Fig.7 Electric near-field of a 16 λ 0 size sphere calculated at 738 848 observation points by the proposed method and the conventional method

4.2 Application

In this section, we present the simulation of the radio-fuse echo of the missile-target encounter process to show the capability of the proposed method.During the encounter process, the radio-fuse works in the near-field space of the target, and the relative position of the missile-target can be obtained through the radar echo.Generally, the missile moves with high speed and the rendezvous time is as short as the order of tens of milliseconds.Therefore,fast calculation of the near-fields is required.

As can be seen from Fig.8, a missile-like object is approaching an aircraft model with a relative speedvmt.The possible encounter space is highlighted with shadow.In this area, the missile can approach the target from any path (see Path 1, Path 2, and Path 3 for example).In Fig.8 we remark the miss point of Path1 wheredmissdenotes the miss distance.The size of the aircraft is21m×14m×3m, discretized by triangular meshes of average size λ0/10, resulting in 451 302 source points.The incident electric field isz-polarized and propagating along the ydirection at frequencyf=600MHz.The size of the encounter space is 4 0m×15m, discretized by tetrahedral meshes of average size λ0/10, resulting in 2 798 704 auxiliary mesh edges.Each path has 1 000 equally spaced observation points.

Fig.8 Missile-target encounter model

The VV- and HH-polarized electric near-fields of these paths with respect to the miss distancedmiss=8m,10m,12mare plotted in Fig.9, in which the results of the conventional method are compared with those of the proposed method and good agreement can be observed.The results show that the position with the largest amplitude will shift with the change of miss distance.In addition,because the aircraft is an extended target, the maximum value will not appear at the miss point.These feature points can be used to characterize the radar returns, and in turn, the miss distance can be estimated by the curve fitting.This example will take 2 294 s of time and 4 074 MB of memory to finish the NFDB construction.After that, it only takes 2.6 ms for each observation point to search andfinish the near-field interpolation.In contrast, with the conventional method, the time cost for each point is 300 ms approximately.

Fig.9 VV- and HH-polarized electric near-fields at points along the three paths

In practical applications, we may need to consider different incidents and scattering directions, polarizations,missile trajectories and other parameters at the same time.On this occasion, the conventional method will be extremely time-consuming and unacceptable, while the results mentioned above demonstrate high efficiency and practicality of the proposed method, by which we can obtain the near-field patterns of each path efficiently and design the optimum burst point of fuse.

5.Conclusions

In this paper, a novel fast method for radar echo simulation in near-field regions is presented.An easy-to-access NFDB is first set up, then the near-fields of arbitrary observation points can be obtained quickly by accessing the database.To speed up the construction of the database,we propose an efficient, low complexity and highly parallel algorithm named RS-BF to compress the discretization of the integral operators.A computational complexity belowO(Nlog2N)can be observed.The proposed algorithms with fast construction and fast access of the database could bring a novel and efficient approach to calculate the near-fields, particularly for cases with varying position of observation points.Numerical results have demonstrated the accuracy and efficiency of the proposed approach.Furthermore, the proposed fast method shows strong capability to solve practical problems.