TECHNICAL FIELD

[001] The present invention relates to sensor arrays used for direction of arrival (DOA) estimation.

BACKGROUND

[002] Sensor arrays are used for direction of arrival

(DOA) estimation m a wide range of applications such as wireless communications, radar, sonar, and passive emitter location. A key performance metric for a sensor array is the ability to resolve two signals coming from different DOAs. The resolution capability of an array depends to a large extent on the size of the array. Large arrays can resolve very closely spaced signals, but they are expensive, both in terms of hardware and computational complexity. One way to reduce the complexity while retaining the resolving capability is to judiciously remove some of the elements from a fully populated array (e.g., an array with element separation ≤λ/2 where λ is the wavelength of the signal to be received by the array) . Such arrays are often referred to as thinned arrays. Other advantages with thinned arrays are reduced mutual coupling, weight, and power consumption.

[003] The price paid for thinning a full array is reduced gain and increased sidelobes, or near-gratmg lobes. A grating lobe is a lobe with the same magnitude as the mam lobe. Grating lobes appear when the array elements are regularly spaced more than 2/2 apart. If the elements in a thinned array are spaced irregularly, "near-grating lobes" with magnitude less than the main lobe will appear. Unlike sidelobes, these lobes cannot be reduced by tapering since they are caused by spatial undersamplmg. If the near-grating lobes are too high they will degrade the resolution capability of the array and may also produce false DOA estimates.

[004] One existing method for designing thinned arrays with high resolution is based on the so called minimum redundancy principle. In this method, the array is designed so that the number of array element pairs that have the same spatial covaπance lag is made as small as possible. Most DOA estimation methods are based on the spatial covaπance matrix which contains estimates of the different spatial covaπance lags. With the minimum redundancy method it is possible to design a thinned array that still has the ability to estimate every spatial covaπance lag. However, the method is based on heuristics and no optimality can be claimed.

[005] Other approaches use the Cramer-Rao Bound (CRB) m the optimization of element positions. The CRB is a lower bound on the estimation accuracy that can be achieved by any estimator. Thus, this is an optimization criterion that is directly connected to the achievable estimation accuracy. The problem with this approach is that the CRB is a local measure that does not take the deteriorating effect of near-grating lobes into account. Therefore, methods based on the CRB tend to produce arrays with high sidelobes .

[006] What is desired is an improved apparatus and method for constructing a sensor array for estimating direction of arrival (DOA) .

SUMMARY

[007] In one aspect, the invention provides a method for constructing a sensor array (e.g., a linear sensor array) , wherein the sensor array has (1) a length, (2) not more than a certain number of array elements, and (3) a grid structure specifying the locations at which an array element may be positioned (these locations may be evenly spaced apart) . In some embodiments, this method includes the following steps: (1) for each sensor array configuration included in a set of sensor array configurations, determining a resolution corresponding to the sensor array configuration, wherein the set of sensor array configurations includes only those sensor array configurations that are possible given the certain number of array elements and the grid structure and the resolution is defined as the smallest angular separation for which the root mean square error (RMSE) of a direction of arrival (DOA) maximum likelihood (ML) estimator is less than or equal to half a DOA separation; (2) determining the sensor array configuration that has the corresponding best resolution; and (3) constructing a sensor array such that the constructed sensor array is configured according to the sensor array configuration that has the corresponding best resolution .

[008] In some embodiments, the locations are evenly spaced apart by an amount equal to or approximately equal to, λ/2 wherein λ is a wavelength value corresponding to the wavelength of a signal to be received by the sensor array.

[009] In some embodiments, the method also includes the step of selecting a signal model, wherein the selecting a signal model step occurs prior to the step of determining the sensor array configuration that has the corresponding best resolution. The step of selecting the signal model may comprise selecting a signal model from a set of signal models including a deterministic signal model and a stochastic signal model. The selection of the signal model is based on an application of a DOA estimator. [0010] The method may also include the step of determining all possible sensor array configurations given the number of array elements and the grid structure, and the set of sensor array configuration includes all sensor array configurations that are possible given the certain number of array elements and the grid structure. [0011] In another aspect, the present invention provides a computer apparatus for constructing a sensor array, the sensor array having (1) a length, (2) not more than a certain number of array elements, and (3) a grid structure specifying the locations at which an array element may be positioned. In some embodiments, the apparatus includes: a data storage system; a data processing system coupled to the data storage system; and computer software stored m the data storage system, wherein the computer software comprises: (i) a resolution determining module configured to, for each sensor array configuration included in a set of sensor array configurations, determine a resolution corresponding to the sensor array configuration, wherein the set of sensor array configurations includes only those sensor array configurations that are possible given the certain number of array elements and the grid structure; and (ii) a best resolution determining module configured to determine the sensor array configuration that has the corresponding best resolution, wherein the resolution is defined as the smallest angular separation for which the root mean square error (RMSE) of a direction of arrival (DOA) maximum likelihood (ML) estimator is less than or equal to half a DOA separation. [0012] In another aspect, the present invention provides a computer program product for constructing a sensor array, the sensor array having (1) a length, (2) not more than a certain number of array elements, and (3) a grid structure specifying the locations at which an array element may be positioned. In some embodiments, the product includes: (i) a computer readable medium; and (ii) computer software stored by the computer readable medium, wherein the computer software comprises: (a) a resolution determining module configured to, for each sensor array configuration included m a set of sensor array configurations, determine a resolution corresponding to the sensor array configuration, wherein the set of sensor array configurations includes only those sensor array configurations that are possible given the certain number of array elements and the grid structure, and (2) a best resolution determining module configured to determine the sensor array configuration that has the corresponding best resolution, wherein the resolution is defined as the smallest angular separation for which the root mean square error (RMSE) of a maximum likelihood (ML) estimator is less than or equal to half a direction of arrival (DOA) separation .

[0013] The above and other aspects and embodiments are described below with reference to the accompanying drawings .

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] The accompanying drawings, which are incorporated herein and form part of the specification, illustrate various embodiments of the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the pertinent art to make and use the invention. In the drawings, like reference numbers may indicate identical or functionally similar elements.

[0015] FIG. 1 is a diagrammatic illustration of a linear sensor array grid structure.

[0016] FIG. 2 is a diagrammatic illustration of a full linear sensor array.

[0017] FIG. 3 is a diagrammatic illustration of a thinned linear sensor array

[0018] FIG. 4 is a flow chart illustrating a process according to some embodiments of the invention.

[0019] FIG. 5 is a diagrammatic illustration of a linear sensor array grid structure according to an embodiment of the invention.

[0020] FIGs. 6A and 6B show two possible thinned arrays that could be constructed based on the grid structure shown m FIG. 5 and setting the total number of array elements for the array equal to 6.

[0021] FIG. 7 is a functional block diagram of an apparatus according to an embodiment of the invention.

[0022] FIG. 8 is a functional block diagram of software according to an embodiment of the invention.

[0023] FIG. 9 illustrates an example histogram.

DETAILED DESCRIPTION

[0024] Referring now to FIG. 1, FIG. 1 is a diagrammatic illustration of a linear array grid structure 100 having a length (L), where L is equal to a multiple (m) of λ/2 (m this example, m = 7) . Grid structure 100 specifies the potential array element locations 104 (e.g., the locations where the array elements may be placed m the linear array) . These locations are identified by an X. In the example shown, structure 100 specifies that: (1) the linear array contains 8 potential array element locations and (2) the distance between any two neighboring potential array element locations is or approximately [0025] The well known "filled" array is defined as an array for which an array element is positioned at each potential array element location. An example well known filled array 200 constructed from grid structure 100 is illustrated in FIG. 2. As shown m FIG. 2, an array element 204 is positioned at each possible array element location. As illustrated in FIG. 2, one can use a filled linear sensor array to determine the angle θ. A thinned array is an array for which there is at least one potential array element location at which no array element is placed. An example thinned array 300 is illustrated m FIG. 3. As illustrated in FIG. 3, one can use a thinned linear sensor array to determine the angle θ.

[0026] As discussed above, a thinned array is less "expensive" than a filled array, but may have less resolution capability than a filled array. However, one aspect the present invention provides a process for creating a thinned linear array with optimal resolution capability. Unlike prior art m this field, the proposed process takes into account the effect of near-gratmg lobes m the beam pattern.

[0027] Referring now to FIG. 4, FIG. 4 is a flow chart illustrating one embodiment of a process 400 for creating a thinned linear sensor array. Process 400 may begin m step 402, where a linear sensor array grid structure is defined. In some embodiments, the linear sensor array grid structure specifies that the linear array contains m potential array element locations. Additionally, m some embodiments, the grid structure specifies that: (1) an array element 204 (e.g., an antenna element) be placed at each end of the array and/or (2) the distance between any two neighboring array elements is λ/2 or approximately λ/2. Referring now to FIG. 5, FIG. 5 illustrates such a grid structure. As shown, the grid structure specifies that an element 204 be placed at each end of the array and that there are 6 locations at which array elements may be placed. The number 6 was chosen solely for simplicity as the grid structure is not limited to any specific number of locations at which array elements may be placed.

[0028] In step 404, the total number of array elements to include in the linear sensor array is selected. Because this is a thinned array, the selected total number of array elements will be at least one less than the total number of elements that can be supported by the linear array grid structure .

[0029] In step 406, the set of some or all possible sensor array configurations that are possible given the defined grid structure and the chosen total number of array elements is determined. For example, if we assume that the defined grid structure is as shown m FIG. 5 and we assume that the total number of array elements is chosen to be 6, then FIGs. 6A and 6B illustrate two of the possible sensor array configurations.

[0030] In step 408, a sensor array configuration is selected from the set and "removed" from the set (e.g., indicated as having been selected) . [0031] In step 410, the resolution of an array corresponding to the selected sensor array configuration is determined. In one embodiment, the resolution is defined as the smallest angular separation for which the root mean square error (RMSE) of a direction of arrival (DOA) maximum likelihood (ML) estimator is less than or equal to half a DOA separation.

[0032] In step 412, a determination is made as to whether the set is "empty" (i.e., whether all sensor array configurations included m the set have been selected) . If the set is not "empty," the process returns to step 408, otherwise it proceeds to step 414.

[0033] In step 414, the sensor array configuration from the set that has the best determined resolution is selected. In step 416, a sensor array is physically constructed such that it is configured according to the sensor array configuration selected in step 414. [0034] As described above, the array with the best resolution can be found by an exhaustive search over some or all of the possible arrays. The number of possible thinned arrays with K array elements picked from a grid of D points is given by (D-2) ' / [ (K-2) ' (D-K) ' ] , if the two end elements are assumed to be fixed at the end points of the grid. Due to symmetry, only half of all these arrays need to be examined. For very large arrays this may become computationally intractable. In this case some discrete optimization algorithm can be used.

[0035] Referring now to FIG. 7, FIG. 7 illustrates an apparatus 700, according to some embodiments, for facilitating the construction of a thinned sensor array. Apparatus 700 is a data processing apparatus (e.g., computer) . As shown m FIG. 7, apparatus 700 includes a data processing system 702 (e.g., one or more microprocessors) , a data storage system 706 (e.g., one or more non-volatile storage devices) and computer software 708 stored on the storage system 706. Configuration parameters 710 may also be stored m storage system 706. [0036] Software 708 is configured such that when processor 702 executes software 708, apparatus 700 performs one or more of the steps described above with reference to the flow chart shown m FIG. 4. For example, software 708, a functional block diagram of which is illustrated m FIG. 8, may include: (1) sensor array configuration determining code 806 (see FIG. 8) configured to determine a set of possible sensor array configurations given a selected number of array elements and a defined grid structure; (2) resolution determining code 802 configured to determine a resolution of a sensor array configuration; and (3) best resolution determining code 804 for determining a sensor array configuration that has the best resolution relative to a set of other sensor array configurations. The resolution determining code 802 may include signal model selection code configured to enable the selection of a signal model that is used to determine the resolution. [0037] As discussed above, m some embodiments, the resolution is defined as the smallest angular separation for which the root mean sguare error (RMSE) of a direction of arrival (DOA) maximum likelihood (ML) estimator is less than or equal to half a DOA separation. That is, the performance criterion used m the proposed method is the ability of the array to resolve two signals when the maximum likelihood (ML) estimator is used for DOA estimation. The ML estimator is an estimator based on fundamental statistical principles and is m general recognized as an estimator with excellent performance. It also known to be at least asymptotically optimal under some conditions .

[0038] The ML estimator requires a statistical model of the received signal samples as a function of the sought parameters. The estimation problem considered herein is to find the DOAs, θ = [θi, Θ ₂ ] , of two source signals s = [sl(t) s2(t) ] contaminated by zero-mean white Gaussian noise n(t) . The complex baseband signals received by a linear array of K sensors can be modeled by the K x I complex vector where Here, a(θ) is the K x I array steering vector that models the array response to a unit waveform from the DOA θ, measured relative to the array boresight. If the signal source and the array are coplanar, θ represents an azimuthal angle. If not, it represents a cone angle. Furthermore, N denotes the number of snapshots, is the complex amplitude at baseband of the m-th impinging wavefront and n(t) is KxI vector representing noise and interference. The noise and interference are assumed to be spatio-temporally white with variance σ ² .

[0039] For simplicity, the sensors are assumed to be omnidirectional with unity gain. Furthermore, it is assumed that the array elements are placed on a regular grid, but that not all grid points need to be occupied by an element. The steering vector then takes the form

[0040] where K are the sensor positions along the array axis. Typically, the grid point separation, Δ, will be ≤λ/2. For the ease of notation, the estimation will be considered in the sequel. [0041] It Is convenient to express the model in (1) in matrix form according to

[ 0042 ] where

[0043] Two different variations of the ML DOA estimator exist. The difference is in the model of the source signal s(t) . The signal samples can be considered as unknown deterministic parameters that need to be estimated along with the DOAs, or they can be modeled as a random process with unknown variance. These two different ML approaches are referred to as the deterministic and stochastic ML estimators, respectively. In the stochastic model, the signals si(t) and S ₂ (t) are assumed to be uncorrelated zero- mean white Gaussian processes with variances Pi and P ₂ , respectively. The array design method is the same for both the deterministic and stochastic ML estimators, but the mathematical details differ. These are treated separately. [0044] Deterministic Maximum Likelihood [0045] The ML estimator under the deterministic signal model is given by

where

[0046] Here, ( ) , and is the sample covariance matrix of the received data. We will also need the ML criterion in the absence of noise. This is given by where u ₀ is the true value of u. Now, let denote the n-th local maximum of V and define the probability

[0047] In order to compute the probabilities P _n , The cumulant generating function, which is the logarithm of the moment generating function, which in turn is related to the Laplace transform of the probability density function, K(s) , of the quadratic form is needed. To this end, perform the following eigendecomposition where the eigenvectors are the columns in E and the eigenvalues are the diagonal element in It is assumed that the eigenvectors and the eigenvalues have been ordered so that Λ = diag where L is the number of nonzero eigenvalues, which are assumed to be distinct. Furthermore, define

where E ₃ is the j-th column of E. The cumulant generating function is then given by

[0048] Its first two derivatives are also needed. These are given by

[0049] The probabilities P _n are then given by the following expressions

where

[0050] In the above expressions, So is the solution to the equation in the interval where and denote the negative and positive eigenvalues .

[0051] Finally, the MSE for the deterministic ML DOA estimate of the k-th signal is given by where is the diagnol element in the matrix

The resolution of a particular array is then defined as the smallest for which

[0052] Stochastic Maximum Likelihood

[0053] The ML estimator under the stochastic signal model is given by

[0054] Here is a vector of the unknown parameters that need to be estimated and where

[0055] The asymptotic criterion function is also needed m the calculations. This is given by where α ₀ is the true value of α. [0056] The probabilities P _n are m this case defined as where is the n-th local minimum of In this case the cumulant generating function of is needed. This, and its first two derivatives, are given by

where are the distinct eigenvalues of

And are the corresponding multiplicities. [0057] The probabilities, P _n can now be computed according to the following expressions

Where

Where S ₀ is the solution to the equation in the interval [0058] Finally, the MSE for the stochastic ML DOA estimate of the signal is given by where is the k-th diagnol element m the matrix

This matrix can be computed from the following expressions

[0059] The resolution of a particular array is then defined as the smallest [0060] Example

[0061] In this example, the stochastic signal model was used to find the array with the best resolution. The example assumes two signals with the same power and signal- to-noise ratio SNR = Pl/σ ² = 7 dB. The number of array snapshots is N = 16 and the DOA of the first signal is u =

0 (i.e., array boresight) . The optimal thinned array with 8 elements picked from a regular grid of 24 points spaced λ/2 apart was found using the above described procedure. In order to compare arrays of the same length, the thinned array end elements are fixed at the grid end points (i.e., at 0 and The number of possible such thinned arrays is 74613 . For this number of arrays it is feasible to perform an exhaustive search for the array the best resolution. The results are summarized m FIG. 9 as a histogram of the obtained resolutions.

[0062] The best resolution is Δu = 0.020 and this was obtained with the array with element positions given by [0 It is interesting to compare the resolution of this optimized array with the resolution of a λ/2 spaced uniform linear array (ULA) with the same number of elements and a λ/2 spaced ULA with the same length as the optimized array. Using the same calculations as in the optimization procedure we find that an 8-element ULA with λ/2 element separation has a resolution of 0.066, while a ULA with the same length but with 24 elements has a resolution of 0.017. Hence, the optimized thinned array has much better resolution than a ULA with the same number of elements, and almost as good resolution as a fully populated array with the same length but with 3 times as many elements .

[0063] While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments.

[0064] Additionally, while the processes described above and illustrated in the drawings are shown as a sequence of steps, this was done solely for the sake of illustration. Accordingly, it is contemplated that some steps may be added, some steps may be omitted, the order of the steps may be re-arranged, and some steps may be performed m parallel .