HIGH PERFORMANCE, LOW COST SUBSPACE DECOMPOSITION AND POLYNOMIAL ROOTING FOR REAL TIME DIRECTION OF ARRIVAL ESTIMATION: ANALYSIS AND IMPLEMENTATION

This thesis develops high performance real-time signal processing modules for direction of arrival (DOA) estimation for localization systems. It proposes highly parallel algorithms for performing subspace decomposition and polynomial rooting, which are otherwise traditionally implemented using sequential algorithms. The proposed algorithms address the emerging need for real-time localization for a wide range of applications. As the antenna array size increases, the complexity of signal processing algorithms increases, making it increasingly difficult to satisfy the real-time constraints. This thesis addresses real-time implementation by proposing parallel algorithms, that maintain considerable improvement over traditional algorithms, especially for systems with larger number of antenna array elements. Singular value decomposition (SVD) and polynomial rooting are two computationally complex steps and act as the bottleneck to achieving real-time performance. The proposed algorithms are suitable for implementation on field programmable gated arrays (FPGAs), single instruction multiple data (SIMD) hardware or application specific integrated chips (ASICs), which offer large number of processing elements that can be exploited for parallel processing. The designs proposed in this thesis are modular, easily expandable and easy to implement. Firstly, this thesis proposes a fast converging SVD algorithm. The proposed method reduces the number of iterations it takes to converge to correct singular values, thus achieving closer to real-time performance. A general algorithm and a modular system design are provided making it easy for designers to replicate and extend the design to larger matrix sizes. Moreover, the method is highly parallel, which can be exploited in various hardware platforms mentioned earlier. A fixed point implementation of proposed SVD algorithm is presented. The FPGA design is pipelined to the maximum extent to increase the maximum achievable frequency of operation. The system was developed with the objective of achieving high throughput. Various modern cores available in FPGAs were used to maximize the performance and details of these modules are presented in detail. Finally, a parallel polynomial rooting technique based on Newton’s method applicable exclusively to root-MUSIC polynomials is proposed. Unique characteristics of root-MUSIC polynomial’s complex dynamics were exploited to derive this polynomial rooting method. The technique exhibits parallelism and converges to the desired root within fixed number of iterations, making this suitable for polynomial rooting of large degree polynomials. We believe this is the first time that complex dynamics of root-MUSIC polynomial were analyzed to propose an algorithm. In all, the thesis addresses two major bottlenecks in a direction of arrival estimation system, by providing simple, high throughput, parallel algorithms.

Direction finding in the presence of a more realistic environment model

Direction-of-arrival (DOA) estimation is susceptible to errors introduced by the presence of real-ground and resonant size scatterers in the vicinity of the antenna array. To compensate for these errors pre-calibration and auto-calibration techniques are presented. The effects of real-ground constituent parameters on the mutual coupling (MC) of wire type antenna arrays for DOA estimation are investigated. This is accomplished by pre-calibration of the antenna array over the real-ground using the finite element method (FEM). The mutual impedance matrix is pre-estimated and used to remove the perturbations in the received terminal voltage. The unperturbed terminal voltage is incorporated in MUSIC algorithm to estimate DOAs. First, MC of quarter wave monopole antenna arrays is investigated. This work augments an existing MC compensation technique for ground-based antennas and proposes reduction in MC for antennas over finite ground as compared to the perfect ground. A factor of 4 decrease in both the real and imaginary parts of the MC is observed when considering a poor ground versus a perfectly conducting one for quarter wave monopoles in the receiving mode. A simulated result to show the compensation of errors direction of arrival (DOA) estimation with actual realization of the environment is also presented. Secondly, investigations for the effects on received MC of λ/2 dipole arrays placed near real-earth are carried out. As a rule of thumb, estimation of mutual coupling can be divided in two regions of antenna height that is very near ground 0

Multi-antenna non-line-of-sight identification techniques for target localization in mobile ad-hoc networks

Target localization has a wide range of military and civilian applications in wireless mobile networks. Examples include battle-field surveillance, emergency 911 (E911), traffc alert, habitat monitoring, resource allocation, routing, and disaster mitigation. Basic localization techniques include time-of-arrival (TOA), direction-of-arrival (DOA) and received-signal strength (RSS) estimation. Techniques that are proposed based on TOA and DOA are very sensitive to the availability of Line-of-sight (LOS) which is the direct path between the transmitter and the receiver. If LOS is not available, TOA and DOA estimation errors create a large localization error. In order to reduce NLOS localization error, NLOS identifcation, mitigation, and localization techniques have been proposed. This research investigates NLOS identifcation for multiple antennas radio systems. The techniques proposed in the literature mainly use one antenna element to enable NLOS identifcation. When a single antenna is utilized, limited features of the wireless channel can be exploited to identify NLOS situations. However, in DOA-based wireless localization systems, multiple antenna elements are available. In addition, multiple antenna technology has been adopted in many widely used wireless systems such as wireless LAN 802.11n and WiMAX 802.16e which are good candidates for localization based services. In this work, the potential of spatial channel information for high performance NLOS identifcation is investigated. Considering narrowband multiple antenna wireless systems, two xvNLOS identifcation techniques are proposed. Here, the implementation of spatial correlation of channel coeffcients across antenna elements as a metric for NLOS identifcation is proposed. In order to obtain the spatial correlation, a new multi-input multi-output (MIMO) channel model based on rough surface theory is proposed. This model can be used to compute the spatial correlation between the antenna pair separated by any distance. In addition, a new NLOS identifcation technique that exploits the statistics of phase difference across two antenna elements is proposed. This technique assumes the phases received across two antenna elements are uncorrelated. This assumption is validated based on the well-known circular and elliptic scattering models. Next, it is proved that the channel Rician K-factor is a function of the phase difference variance. Exploiting Rician K-factor, techniques to identify NLOS scenarios are proposed. Considering wideband multiple antenna wireless systems which use MIMO-orthogonal frequency division multiplexing (OFDM) signaling, space-time-frequency channel correlation is exploited to attain NLOS identifcation in time-varying, frequency-selective and spaceselective radio channels. Novel NLOS identi?cation measures based on space, time and frequency channel correlation are proposed and their performances are evaluated. These measures represent a better NLOS identifcation performance compared to those that only use space, time or frequency.

Multi-node TOA-DOA cooperative LOS-NLOS localization : enabling high accuracy and reliability

This dissertation investigates high performance cooperative localization in wireless environments based on multi-node time-of-arrival (TOA) and direction-of-arrival (DOA) estimations in line-of-sight (LOS) and non-LOS (NLOS) scenarios. Here, two categories of nodes are assumed: base nodes (BNs) and target nodes (TNs). BNs are equipped with antenna arrays and capable of estimating TOA (range) and DOA (angle). TNs are equipped with Omni-directional antennas and communicate with BNs to allow BNs to localize TNs; thus, the proposed localization is maintained by BNs and TNs cooperation. First, a LOS localization method is proposed, which is based on semi-distributed multi-node TOA-DOA fusion. The proposed technique is applicable to mobile ad-hoc networks (MANETs). We assume LOS is available between BNs and TNs. One BN is selected as the reference BN, and other nodes are localized in the coordinates of the reference BN. Each BN can localize TNs located in its coverage area independently. In addition, a TN might be localized by multiple BNs. High performance localization is attainable via multi-node TOA-DOA fusion. The complexity of the semi-distributed multi-node TOA-DOA fusion is low because the total computational load is distributed across all BNs. To evaluate the localization accuracy of the proposed method, we compare the proposed method with global positioning system (GPS) aided TOA (DOA) fusion, which are applicable to MANETs. The comparison criterion is the localization circular error probability (CEP). The results confirm that the proposed method is suitable for moderate scale MANETs, while GPS-aided TOA fusion is suitable for large scale MANETs. Usually, TOA and DOA of TNs are periodically estimated by BNs. Thus, Kalman filter (KF) is integrated with multi-node TOA-DOA fusion to further improve its performance. The integration of KF and multi-node TOA-DOA fusion is compared with extended-KF (EKF) when it is applied to multiple TOA-DOA estimations made by multiple BNs. The comparison depicts that it is stable (no divergence takes place) and its accuracy is slightly lower than that of the EKF, if the EKF converges. However, the EKF may diverge while the integration of KF and multi-node TOA-DOA fusion does not; thus, the reliability of the proposed method is higher. In addition, the computational complexity of the integration of KF and multi-node TOA-DOA fusion is much lower than that of EKF. In wireless environments, LOS might be obstructed. This degrades the localization reliability. Antenna arrays installed at each BN is incorporated to allow each BN to identify NLOS scenarios independently. Here, a single BN measures the phase difference across two antenna elements using a synchronized bi-receiver system, and maps it into wireless channel’s K-factor. The larger K is, the more likely the channel would be a LOS one. Next, the K-factor is incorporated to identify NLOS scenarios. The performance of this system is characterized in terms of probability of LOS and NLOS identification. The latency of the method is small. Finally, a multi-node NLOS identification and localization method is proposed to improve localization reliability. In this case, multiple BNs engage in the process of NLOS identification, shared reflectors determination and localization, and NLOS TN localization. In NLOS scenarios, when there are three or more shared reflectors, those reflectors are localized via DOA fusion, and then a TN is localized via TOA fusion based on the localization of shared reflectors.

Estimation of the degree of polarization through computational sensing

The degree of polarization of a refected field from active laser illumination can be used for object identifcation and classifcation. The goal of this study is to investigate methods for estimating the degree of polarization for refected fields with active laser illumination, which involves the measurement and processing of two orthogonal field components (complex amplitudes), two orthogonal intensity components, and the total field intensity. We propose to replace interferometric optical apparatuses with a computational approach for estimating the degree of polarization from two orthogonal intensity data and total intensity data. Cramer-Rao bounds for each of the three sensing modalities with various noise models are computed. Algebraic estimators and maximum-likelihood (ML) estimators are proposed. Active-set algorithm and expectation-maximization (EM) algorithm are used to compute ML estimates. The performances of the estimators are compared with each other and with their corresponding Cramer-Rao bounds. Estimators for four-channel polarimeter (intensity interferometer) sensing have a better performance than orthogonal intensities estimators and total intensity estimators. Processing the four intensities data from polarimeter, however, requires complicated optical devices, alignment, and four CCD detectors. It only requires one or two detectors and a computer to process orthogonal intensities data and total intensity data, and the bounds and estimator performances demonstrate that reasonable estimates may still be obtained from orthogonal intensities or total intensity data. Computational sensing is a promising way to estimate the degree of polarization.

Automation of shear-wave splitting parameter determination of local earthquakes at Yellowstone : application as indicator of crustal stress and temporal variation

Shear-wave splitting can be a useful technique for determining crustal stress fields in volcanic settings and temporal variations associated with activity. Splitting parameters were determined for a subset of local earthquakes recorded from 2000-2010 at Yellowstone. Analysis was automated using an unsupervised cluster analysis technique to determine optimum splitting parameters from 270 analysis windows for each event. Six stations clearly exhibit preferential fast polarization values sub-orthogonal to the direction of minimum horizontal compression. Yellowstone deformation results in a local crustal stress field differing from the regional field dominated by NE-SW extension, and fast directions reflect this difference rotating around the caldera maintaining perpendicularity to the rim. One station exhibits temporal variations concordant with identified periods of caldera subsidence and uplift. From splitting measurements, we calculated a crustal anisotropy of ~17-23% and crack density ~0.12-0.17 possibly resulting from stress-aligned fluid filled microcracks in the upper crust and an active hydrothermal system.

Development of a physically-based method for delineation of hydrologically homogeneous regions and flood quantile estimation in ungauged basins via the index flood method

Regional flood frequency techniques are commonly used to estimate flood quantiles when flood data is unavailable or the record length at an individual gauging station is insufficient for reliable analyses. These methods compensate for limited or unavailable data by pooling data from nearby gauged sites. This requires the delineation of hydrologically homogeneous regions in which the flood regime is sufficiently similar to allow the spatial transfer of information. It is generally accepted that hydrologic similarity results from similar physiographic characteristics, and thus these characteristics can be used to delineate regions and classify ungauged sites. However, as currently practiced, the delineation is highly subjective and dependent on the similarity measures and classification techniques employed. A standardized procedure for delineation of hydrologically homogeneous regions is presented herein. Key aspects are a new statistical metric to identify physically discordant sites, and the identification of an appropriate set of physically based measures of extreme hydrological similarity. A combination of multivariate statistical techniques applied to multiple flood statistics and basin characteristics for gauging stations in the Southeastern U.S. revealed that basin slope, elevation, and soil drainage largely determine the extreme hydrological behavior of a watershed. Use of these characteristics as similarity measures in the standardized approach for region delineation yields regions which are more homogeneous and more efficient for quantile estimation at ungauged sites than those delineated using alternative physically-based procedures typically employed in practice. The proposed methods and key physical characteristics are also shown to be efficient for region delineation and quantile development in alternative areas composed of watersheds with statistically different physical composition. In addition, the use of aggregated values of key watershed characteristics was found to be sufficient for the regionalization of flood data; the added time and computational effort required to derive spatially distributed watershed variables does not increase the accuracy of quantile estimators for ungauged sites. This dissertation also presents a methodology by which flood quantile estimates in Haiti can be derived using relationships developed for data rich regions of the U.S. As currently practiced, regional flood frequency techniques can only be applied within the predefined area used for model development. However, results presented herein demonstrate that the regional flood distribution can successfully be extrapolated to areas of similar physical composition located beyond the extent of that used for model development provided differences in precipitation are accounted for and the site in question can be appropriately classified within a delineated region.

Calibration of the HAWC Gamma-Ray Observatory

The High-Altitude Water Cherenkov (HAWC) Experiment is a gamma-ray observatory that utilizes water silos as Cherenkov detectors to measure the electromagnetic air showers created by gamma rays. The experiment consists of an array of closely packed water Cherenkov detectors (WCDs), each with four photomultiplier tubes (PMTs). The direction of the gamma ray will be reconstructed using the times when the electromagnetic shower front triggers PMTs in each WCD. To achieve an angular resolution as low as 0.1 degrees, a laser calibration system will be used to measure relative PMT response times. The system will direct 300ps laser pulses into two fiber-optic networks. Each network will use optical fan-outs and switches to direct light to specific WCDs. The first network is used to measure the light transit time out to each pair of detectors, and the second network sends light to each detector, calibrating the response times of the four PMTs within each detector. As the relative PMT response times are dependent on the number of photons in the light pulse, neutral density filters will be used to control the light intensity across five orders of magnitude. This system will run both continuously in a low-rate mode, and in a high-rate mode with many intensity levels. In this thesis, the design of the calibration system and systematic studies verifying its performance are presented.

EVALUATION OF THE EVOLVING STRESS FIELD OF THE YELLOWSTONE VOLCANIC PLATEAU FROM 1988 TO 2010 FROM EARTHQUAKE FIRST MOTIONS INVERSION

Within the Yellowstone National Park, Wyoming, the silicic Yellowstone volcanic field is one of the most active volcanic systems all over the world. Although the last rhyolite eruption occurred around 70,000 years ago, Yellowstone is still believed to be volcanically active, due to high hydrothermal and seismic activity. The earthquake data used in this study cover the period of time between 1988 and 2010. Earthquake relocations and a set of 369 well-constrained, double-couple, focal mechanism solutions were computed. Events were grouped according to location and time to investigate trends in faulting. The majority of the events has oblique, normal-faulting solutions. The overall direction of extension throughout the 0.64 Ma Yellowstone caldera looks nearly ENE, consistently with the direction of alignments of volcanic vents within the caldera, but detailed study revealed spatial and temporal variations. Stress-field solutions for different areas and time periods were calculated from earthquake focal mechanism inversion. A well-resolved rotation of σ3 was found, from NNE-SSW near the Hebgen Lake fault zone, to ENE-WSW near Norris Junction. In particular, the σ3 direction changed throughout the years in the Norris Junction area, from being ENE-WSW, as calculated in the study by Waite and Smith (2004), to NNE-SSW, while the other σ3 directions are mostly unchanged over time. The Yellowstone caldera was subject to periods of net uplift and subsidence over the past century, explained in previous studies as caused by expanding or contracting sills, at different depths. Based on the models used to explain these deformation periods, we investigated the relationship between variability in aseismic deformation and seismic activity and faulting styles. Focal mechanisms and P and T axes were divided into temporal and depth intervals, in order to identify spatial or temporal trends in deformation. The presence of “chocolate tablet” structures, with composite dilational faults, was identified in many stages of the deformation history both in the Norris Geyser Basin area and inside the caldera. Strike-slip component movement was found in a depth interval below a contracting sill, indicating the movement of magma towards the caldera.