The RCap: an architecture for robust beamforming and high resolution DOA tracking

Proceedings of ICSP2000 THE RCAP: A CONCEPT FOR ROBUST BEAMFORMING AND HIGH RESOLUTION DOA TRACKING A. Pdrez-Neira, R. Yillarino, MA. Lagunas Signal and Communications Theory Dept. Universitat Politkcnica de Catalunya, Campus Nord D5 Jordi Girona, 1-3,08034, Barcelona, SPAIN e-mail: { anuska,[email protected]} Abstract Motivated by the objective of finding a reduced complexity implementation of the EM (Estimate and Maximize) algorithm, the authors move the concept of altemating projection (AP), reported in 1988 by I. Ziskind and M.Wax, to a specific architecture for array processing in communications. Direction of Arrivals (DOA’s) are estimated by scanning the scenario with a dedicated beamvector, proving that low-resolution procedures with constraints, working in parallel, may enhance the performance of high resolution methods. Since no inverse is involved the method is robust and copes with full coherent sources (specular multipath) and fast updates. The procedure is proved to be useful for adaptive beamforming in either point-to-point or mobile communications. Preserving the EM performance the array processing architecture offers a wide range of possibilities in updating and framing taking the best of hardware resources. 1. INTRODUCTION Either as a smart companion of high selective apertures or as a single advanced front-end, antenna arrays show an extraordinary potential for future communication. At the same time, this potential has to face the inappropriate use, design, testing and implementation procedures that produce unaffordable complexity and developing cost. Another issue which is mandatory to take in mind is up to what degree the array front-end may affect or modify the converters, mixers, LNA (Low Noise Amplifiers) and IF (Intermediate Frequency) amplifiers, baseband processing and the communication detector and decoder. In general, whenever the array is adaptive it has to be required that under detectable conditions the adaptive processor has to be switched off, allowing for quiescent performance, and avoiding hard degradation at the detector level. High resolution DOA estimation methods have been traditionally associated with algorithms rather than with a processing scheme or architecture. This paper combines both and describes a processing algorithm and architecture, based in the EM architecture [l-41 and in the AP algorithm [6-81, which does not degrade the expectations of adaptive arrays. In all respects, the proposed architecture presents relatively low cost, easy developing and testing, with robustness to mismatch and channelization components. To guarantee robustness the basic procedures or processing tools reduce to phased array techniques for beamforming and DOA estimation, and to using Kahnan filters to optimize tracking. In fact the main issue remains at the architecture level since a parallel processing plus blocking provides an architecture of single source-single processor which achieves unexpected degrees of performance. Since no inverse is involved the method is robust to coherent scenarios. The work is encompassed as an EM implementation since this was the original motivation of the authors when looking for an architecture that used phased arrays techniques. Phased arrays are, at the end, the only ones that are fully accepted by microwave and antenna engineers, due to their fitness to the above mentioned guidelines. The problems faced hereafter are the DOA estimation and dedicated beamforming design. The structure of the paper is the following: in section II the problem is stated and in section Ill the architecture of the parallel Reduced Complexity Array Processing (RCAP) is described. Section N devotes RCAP to the case of dedicated beamforming: the procedure allows attenuation control of interference, direct control of number of degrees of freedom (allowing sidelobe shape control) and framing control of updates and iterations. Finally, some key simulations are reported in order to show the resulting performance in both cases. 0-7803-5747-7/00/$10.00(92000 IEEE. 2. PROBLEM STATEMENT We address a digital wireless system employing adaptive arrays for the location of P moving sources using an array of Q identical radio receivers. The P sources are narrow-band and can operate simultaneously in the same bandwidth. No restriction is imposed on the signals’ cross-correlation. The signal received by the qth sensor at time n, Xq (n) , is a superposition of the P source signals collected in vector e(n). The Q sensor signals are gathered in the so-called snapshot vector x(n) where the columns of matrix A(n) are the spatial signature a,>(n) of each source p. For the case of point sources in the far-field that impinge on a linear array, each element q of vector ap (n) is x(n) = A(n) e(n) + v(17) (1) being d, the gth sensor location (normalized to the central frequency of the array) and angle 8, (n) the Direction of Arrival or DOA of source p. The problem of interest in this paper is the estimation of the P DOA’s and the dedicated beamforming design. The basic concept that initially motivated this work was the Estimate and Maximize (EM) algorithm [l-21. Facing the problem of reducing the complexity of the two steps, yet preserving the outstanding performance of the EM algorithm, is when concepts of single source processing and blocking come to the scene. The EM algorithm, assuming an uncorrelated stationary source signal and noise process in a time invariant medium, iterates between the E-step and the M-step. The E-step uses the incomplete or observed data x(n) and the current parameter estimate to estimate the log-likelihood of the complete data, producing decoupled signal vectors yp (n) (each vector yp has only contribution of source p and part of the measurement noise): thus, x(n) = cyp (n) . The M-step then maximizes the estimated log-likelihood function of the complete data and obtains in parallel P DOA estimates. Focussing the EM algorithm and looking for complexity reduction, the E-step is viewed as passing from a multiple source problem to a single source one. In other words, given P sources the E-step can be reduced to P blocking processors, blocking P-1 sources each. Following this philosophy, but P p4 implementing the E-step and M-step by a single constrained beamforming, the parallel Reduced Complexity Array Processing (RCAP) architecture is proposed in next section looking for a new trade-off between robustness, complexity and accuracy. In contrast to the AP or EM works, which are all restricted to estimation-only usage, next sections provide further discussions on the computational and implementation aspects. 3. PARALLEL REDUCED COMPLEXITY ARRAY PROCESSING @CAP) As figure 1 shows the proposed architecture consists of two fundamental blocks. In the frst place, the location stage yields a frst estimate of the sources’ position. Inspired in the EM algorithm, it implements the idea of dcaomposing the multiple source scenario in a set of one-source-problems, To make the system work properly in mobile scenarios, a tracker based on the Kalman filter is attached at the output of the location stage. The tracker filters the noise out of the sequence of estimates provided by the previous block and yields a more realistic and better trajectory of the source. Moreover, it provides the location stage with a prediction of the sources’ position for the next iteration. Locoflon staQe Jracklng .. .. B(n I ‘I+#-- n-11 Figure 1. Description of the RCAP architecture. This section is devoted to the main contribution of this work: the location stage. For most of the communication applications we do not need to know precisely the interference location to reduce its effects, only attenuation around 15 to 25 dB’s uses to be enough for most of the communication applications. This can be achieved from a null nearby the actual location and do not need high accuracy DOA estimation to obtain the primary goal of preserving the BER (Bit Error Rate). In fact, some base-stations at the mobile receive the interference in a solid angle: again, a null of the array response inside this solid angle is adequate in most of the cases. These comments are just to show that most of the accuracy that location methods as the formal EM provide is not necessary in many cases to cover successfully the application. Furthermore, this accuracy introduces a substantial loss of robustness and adds complexity to the resulting system. The RCAP turns to a filter bank philosophy in order to estimate in a parallel way the sources' DOA's. Each source branch performs a constrained Phased Array scanning. To be more specific, let's concentrate on a DOA tracking application and imagine that at time n we have a prior estimate of the P DOA angles of the sources 6:) (p=1 ... P). Regardless how close these estimates are to the actual ones, we proceed with updating 0, by blocking steering vectors coming from 6y) (i#p). In order to do so, the scanning beamvector b, is designed following (3) b; (a(@ n(6,(""),. . .,n(@") ,+. e, a(@))) = (1 0 9 0) *(m+1) U' (3.a) This constrained phased array formulated in (4) is used to compute the notch periodogram Then, the new localization estimate for source p, 6Ft1), is associated with the angular position that maximizes the spatial power density, @,(e), that is associated with the notch periodogram, .R,(B), 8:+') = arg mag@,, (e) where R, corresponds to the sample covariance matrix of N snapshots x(n) (n=l..N) and is calculated as Just as the EM, the RCAP procedure iterates until the parameter vector converges to a stationary value, which is rendered as output to the tracking stage: 0, (n) in figure 1. The procedure can be iterated as much as the designer likes in order to further improve the estimates. Since these iterations are done at the DSP level and off-line (i.e. between successive updates of the covariance matrix), they do not overload the mainframe hardware of the RCAP. Also, in order to take advantage of these iterations the scanning grid for a(e) has to be very dense. Another possibility, highly recommended, is to concentrate scanning in a range around previous estimate mainly after the acquisition phase. Note that updates and iterations offer and attractive framing in order to take advantage of the DSP and mainframe hardware to support the RCAP. It is worth remarking that the DOA is estimated from the spatial power density @3,(0) and produces less biased estimates than those obtained by maximizing the spatial power Q,(Q). The reason is that the spatial bandwidth of the beamformer may introduce substantial power leakage from sources or directional noise impinging on the aperture from other directions than the desired one; the power density of (6) takes into account this leakage by normalizing the spatial power by the noise bandwidth bHb. Note also that if the constraint matrix c:) in (4) just contained the scanning direction a(@, then the L. beamvector would be the phased array b = I' lla(e)112 which imposes 0 dB gain in the scanning direction and minimizes the non-directional spatial noise. Note that excluding the data covariance matrix, R, , from the objective (i.e. we use the beamvector norm instead of bHR,b as objective in the constrained minimization of (3.b)), there is no inverse covariance neither SVD like procedures. In consequence, two crucial factors characterize this beamforming or DOA estimation tool: First specular or diffuse multipath are just additional sources that do not degrade the procedure. Second, fast times to upgrade the beamformer or the estimate are allowed. As an example even with onIy 10 snapshots the procedure works properly in a tracking scenario. No other method using covariance inverse or SVD may produce valuable results with such a small number of snapshots. In order to gain more insight into the similarities between the RCAP procedure and the EM, we reformulate the beamvector equated in (4) by applying in (7) the inversion formula for 2x2 block matrices in terms of a projection operator and the scanning direction a(@ (7) Matrix P," projects onto the subspace orthogonal to the one generated by the signals that interfere source p. Then the spatial power density function of (6) resembles the one obtained by the M-step of the EM algorithm. In that case, the new angular estimate of source p was obtained from the spatial density obtained from the power density function the E-step and corresponds to the sample covariance matrix of the estimated complete data set for source p, yp. Notice that expression (6) can be interpreted in the same terms as in the EM algorithm. That is, as an scanning applied to the covariance matrix of some complete data related to source p. Up to now the RCAP procedure has been designed based on heuristics, however it has also an interpretation under a deterministic maximum likelihood perspective. Note that the spatial power density formulated in (6) tallies with the likelihood measure used by the AP algorithm to compute the ML estimate of the DOA's [6]. Since the basis of RCAP and AP are the same, the major difference is the way RCAP implements the AP concept. Instead of using the pure algebraic approach, RCAP reduces the alternating projection to the phased array beamforming design under directional constraints. In other words RCAP is the phased array implementation of the AP algorithm. Both, AP and RCAP, maximize at each iteration the log-likelihood function with respect to a single DOA while all the others are held fixed. Intuitively, the algorithm climbs the peak of the likelihood function along lines parallel to the axes, as shown schematically in figure 2. Since a sequential maximization is performed at every iteration, the .value of the maximization function cannot decrease. As a result, the algorithm is bound to converge to a local maximum. Next we discuss the convenience of introducing Kalman trackers in the RCAP. Figure 2. Conceptual evolution of AP and RCAP over likelihood function. 3.1. The Kalman tracker The main advantage of the RCAP in front of the AP is that the RCAP is not only a low computational algorithm that is based on phased array techniques, but also an architecture that allows the introduction of Kalman filters for the tracking of sources in mobile scenarios. Once having an stable estimate at each branch of this latter block, an angular tracker is used in the scheme of figure 1. The system obtains a double benefit from this subsystem. First, it yields a clean trajectory of the target even in case of eventual signal fadings of bounded time duration. Second, it provides a prediction of the position at the next iteration, making possible to reduce the angular interval in which the power density is computed and therefore reducing the computational load of the algorithm. Since the case of multiple sources is no longer needed by the proposed RCAP architecture, the Kalman filter just concentrates on the estimation of the elevation angle and velocity of a single source. There is no problem to extend the filter to be described herein to the case when azimuths angle and velocity also are parts of the state vector. Further references on the topic can be found in [lo-1 11. It is important to remark that the use of phased array framework to obtain the measured angle makes easy the compatibility with the tracker since measurement noise and source maneuvering have a direct impact on the measurement system. This is not longer the case when more complicated and nonlinear procedures like Music are implemented to find the DOA estimates. Up to now the RCAP has been described as an adequate combination of a set of simple and robust mathematical tools, yielding an architecture for communication systems with DOA detection and tracking capabilities. Additionally, the flexibility of the scheme also allows to easily introduce a set of refinements related to beamforming procedures. Next section is devoted to them. 4. THE RCAP FOR ROBUST BEAMFORMING For space communications, as well as for GPS receivers, the desired direction a&) is known up to some degree, enough to receive, in absence of interferences and multipath, adequate levels of BbNo. The purpose is to keep the EbNo close to a given value (12 dB for BPSK) when multipath and cochannel interferences are present. Within this context, the main purpose of the array is to maintain this specification in a hostile scenario. From now on we consider that the desired source is the one that comes from the known direction 81, thus 8d=8l. Under the deterministic signal model, the maximum likelihood estimation of the signal waveform for source 1 is ~,(n) = aH(e,) P; (aH(el) Ppa(e,>)-' x(n) (8) which is precisely the output of the RCAP beamformer b, formulated in (7), a,(n)=bf(O) x(n), when it steers the DOA of source 1 and perfectly cancels the remaining ones. This reflection motivates the use of the constrained phased array concept to estimate the desired signal waveform. The first task is the finding of the other sources' DOA's. In order to accomplish this aim the iterations for every updates of R, are as follows: First, a phased array with directional constraints is designed in order to find the maximum of the spatial density with the desired source from a(€),) blocked. The whole array manifold is thus scanned by beamvector b,, which is designed in accordance to b, (e)[a(O) a(O, 11 = [I o]~ (9.a) The requested direction of the second source present is then obtained by solving . After 0, is found, the beamvector bd that measures the desired signal can be designed taking (8) into account and considering that only two sources are present in the scenario. Once 82 is found, the procedure iterates in the same way the scanning for another direction 83. At first glance, it can be thought that the algorithm should be repeated until consuming all degrees of freedom (i.e. number of sensors). Then, the beamvector bd that measures the desired signal zl can be designed taking (4) into account. Though it is true that this yields a maximal flat density power estimate, acting this way implies that the spatial response of bd is deformed, and that the measure is corrupted by an excessive leakage due to spatial noise. This fact could even be tolerated if the system acts as a receiving device. However, it cannot be accepted if it plays the role of an emitter because it would radiate excessive power in directions different from the desired one. This fact justifies the existence of an optimum numBer .of consumed degrees of freedom. Thopgh there exists formal approximations to thepoblqm [5], a practical criterion can be based in monitonng the flatness of Cl(€)), or waiting until its maximum value lies under a certain threshold. In the simulations carried out to show the performance of the system, the number of degrees of freedom has simply been limited to P, the number of sources in the scene (one desired source and P-1 interference), an intuitively satisfying value. As a result, the procedure yields a beamformer that renders a power measure with a variation of only decimals of dB over the actual value. In accordance with (4), bd is then b, =A (AHA)-' f, (11) where the constraint matrix is now A and fd is the restriction vector that sets 0 dB gain in the desired DOA, 81. and cancels the rest of the P-1 interference directions: fd = [I Note also that no difference is motivated by multipath since it would produce the same effects in the procedure than non-coherent co-channel interference. Additionally, the updates for R, can be performed at any rate since there is no need to invert the date covariance matrix. Finally, as next subsection presents, practical values of attenuation can be set instead of a perfect zero in order to achieve the target BER 0. v.01. 4.1, Optimum Constraint Vector The beamvector designed in equation (1 1) that estimates the power impinging from the desired direction, bd, can be interpreted as a linear combination of beamvectors bi (i=l ..P) weighted by the coefficients of the constraint vector fd (see equation 12). Each of these beamvectors sets 0 dB gain in direction Bi and cancels its spatial response in the rest of angles obtained by the procedure. bd(fd)=A (AHA)-' fd =Bfd =[b, b,.**b,]fd If fd = [1 O...O] then bd is just the first column of matrix B, thus estimating the power impinging from, the desired direction 01. If the interference DOA's are exactly known, bd minimizes the Signal to Interference Ratio or SIR. However this criterion is not fulfilled if there are estimate errors. Additionally, the more sources are present, the higher the leakage in the resulting beamforming bd and the worse the Signal to Noise ratio or SNR. An alternative is to let the constraint vector be fd = [1 a, aP,] and design the attenuation coefficients (i=l..P-1) different from zero tradingoff between attenuation deep, robustness and performance depending on the application we are dealing with. A less udhoc solution 'is the one formulated in (13), where the beamvector bd(fdo) minimizes the Signal to Noise and Interference Ratio or SNIR (12) (13) (B~R,~ B)-' 1 iH (B~R, B)-' 1 fdo = where 1=[1 0 ... 0IT. This section has shown some of the refinements suitable to be implemented in RCAP. As next section shows the resulting performance in the simulations does not claim for further complexity in GPS or ground segment space communications. One remark should be made before proceeding to the simulation section. In some applications, like radar and point to point communications the beamvector obtained by the described procedure may have an inadequate spatial response. In such situations, or whenever a shape control is desired, the additional constraint can be included in the same manner as it is described in [I21 for the GSLC. 5. SIMULATIONS In order to validate the proposed architecture, 2 groups of simulations have been conducted. The first group deals with the location and tracking stages simultaneously and illustrate the performance of the whole system. Next, the second set of simulations show the behavior of the beamforming procedure of section IV. In the first group of simulations the tracking subsystem is tested, simultaneously illustrating the performance of the whole system. Figure 3 shows the case of two moving and coherent sources tracked by the RCAP. In this simulation a circular array is used and the sources are tracked in both in azimuth and elevation velocity. For source 1, the actual azimuth and elevation velocities (in "/snap) are -0.09 and -0.02 respectively. The estimated values after a few snapshots are: -0.092 and -0.021. For source 2, the actual azimuth and elevation velocities (in "/snap) are 0.1 and -0.032 respectively. The estimated values after a few snapshots are: 0.0999 and -0.0316. As an example figure 4 plots the elevation estimation. In the second group of simulations the beamforming procedure of section 4 is shown, specifically when a shape control is desired. . Figure 5,6 and 7 show a simulation carried out in a scenario with 3 sources impinging from elevation angles 0", 59", -48" the desired source is at the broadside. Coherent multipath also impinges on the aperture from -4", 35" 37" and 39" as a cluster source. The received powers are 10 dB for the desired source, 20 dB. for the mainlobe coherent interference and 10 dB for the rest of signals (including specular multipath). The array that has been used is formed by 15 sensors. Figure 5 plots the quiescent spatial response and indicates the location and power of all the impinging signals. Figure 6 depicts the spatial response of the final designed beamvector bd. The reader can appreciate that all the interference have been eliminated with a pre-designed level of 30 dB. This beamvector measures the desired signal with 10.13 dB. (10 dB actual) in correspondence withsa flat periodogram shown in Fig. 7. The iterations were stopped when 7 degrees of freedom were consumed. When a shape control is desired, the additional constraint can be included in the same manner it is described in [12] for the GSLC. Figure 8 represents the corresponding quiescent, a Chebyshev weighting with bandwidth equal to 16" a constant sidelobe level of -10 dB, where the coherent mainlobe interference has been removed in order to better appreciate the shape control. The resulting beamformer is also depicted in Figure 9. Note that 30 db. of nulling for interference has been set and, regardless the number of degrees of freedom consumed are the same that in the scenario of Figure 5 (one above the optimum), the beamformer does not degrade the design as announced previously. The desired signal level neasured was 10.06 dB versus an actual level of 10. slownesslazimuth plane 901 12060 0 270 South .- North Figure 3. Polar plot of two moving sources tracked by the RCAP system. The azimuth and polar traces are shown. In the scenario, two fully coherent sources of 15 dB each are present. A 13 circular array is used. The covariance matrix is updated every 10 snapshots and 2 iterations are carried out at each update. 2D elevation traces Oiiiescent I -50 0 50 100 Elevanon in degrees Figure 5. Quiescent spatial response and location and power of all the impinging signals. Beam response Bloclan~ G directions 20 k? I -50 0 50 100 Elevanon in degrees Figure 6. Spatial response of the final designed beamvector Peondooram resoonse Elockino 6 dirnclions I O' 50 100 150 200 scans 10 snapsholdscan Figure 4. Elevation estimation .... -1.. ............. .: ....... k? 30 0 50 100 Elevation in degrees Figure 7. Periodogram: complete flat response * 612 Quiescent Elevation in clegraos Figure 8. Chebyshev weighting for the 15 sensor ULA. Quiescent spatial response and location and power of all the impinging signals. Beam reSDonsa 131ocklno 6 directions I 50 0 50 100 Elevation In (lagreus Figure 9. Chebyshev weighting for the 15 sensor ULA. Adapted RCAP beamformer. 6. REFERENCES [ 11 M.Feder, E.Weinstein, "Parameter Estimation of Superimposed Signals Using the EM Algorithm," IEEE Truns. on ASSP, vol. 36, no.4, April 1988, pp. 477-489 [2] M.I.Miller, D.R.Fuhrmann, "MaximumLikelihood Narrow-Band Direction Finding and EM algorithm," ZEEE Truns. 011 ASSP, vol. 38, no.9, September 1990. [3] J.-K. Hwang, Y.-C. Chen, "A combined detection-estimation algorithm for the harmonicretrieval problem", Signal Processing, vol. 30, no.2, January 1993, pp. 177-197. [4] D. Kraus, D.Maiwald, J.F. Biihme, "Maximum Likelihood source location estimation via EM algorithm," Signal Processing, 1992, pp. 649-652. [5] H.-TLi, P.M.Djuric, "An iterative MMSE procedure for parameter estimation of damped sinusoidal signals," Signal Processing 5 1, (1996), [6] I.Ziskind, M.Wax, "Maximum Likelihood localization of multiple souce by alternating projection," IEEE Trans. Acoust. Speech Signal Process., vol. 36, no. 10, October 1988, pp. 15531560. [7] D.E.N. Davies. "Independent angular steering of each zero of the directional pattern of a linear array". IEEE Trans. Antennas and Propagation, [8] R.Bose, B.D.Steinberg, A.Freedman, "Sequence clean: a deconvolution technique for reducing sidelobe artifacts in microwave images of contiguous targets," 13th annual Benjamin Franklin Symposium on New hontiers in Antenna and Microwave Technology, Mayo 1995, pp. 98-101. 191 A. PBrez-Neira, M.A.Lagunas, J.Bas, "Fuzzy Logic for robust detection in wireless communications," PIMRC'97, pp. 1145-49, Helsinki, September97. [lo] B.O. Anderson, J.B. Moore, Optimal Filtering , Prentice-Hall, Electrical Engineering Series, pp. 54-59. [ll] A. PBrez-Neira, M.A. Lagunas, "High performance DOA trackers derived from parallel low resolution. detectors," SSAP Workshop, Greece'96, pp.558-561. [12] L.J. Griffiths, K.M. Buckley, "Quiescent pattern control in linearly constrained adaptive arrays," IEEE Trans. on ASSP, vol. ASSP-35, no.7, pp.917-926, July 1987. pp. 105-120. 1967, pp 296-298. . 613