Srirangarajan, Seshan2010-06-302010-06-302008-08http://purl.umn.edu/91548University of Minnesota Ph.D. dissertation. August 2008. Major: Electrical Engineering. Advisor: Tewfik, Ahmed H. 1 computer file (PDF); xiv, 115 pages.Ranging and positioning in wireless sensor networks refers to the ability to determine the positions of all nodes in a sensor network using the known positions of a few nodes called reference nodes and pairwise distance or range estimates between neighboring nodes. This is also known as the sensor network localization problem. In this thesis we first present two time-of arrival based localization algorithms for indoor quasi-static environments based on statistical modeling of the ultra-wideband multipath channel. A model of the multipath channel in the form of the signal return and noise characterization is derived, and utilized to distinguish signal components from noise. The first localization algorithm uses multiple (ranging) signal receptions at each reference node, to differentiate between line-of-sight and non-line-of-sight components, and to accurately estimate the position of the line-of-sight component in the received multipath signal. The second localization algorithm employs a time-of-arrival based algorithm to obtain pseudo range estimates which are then used in a spatial domain quasi-maximum likelihood method for location estimation. Furthermore, the associated range estimation error does not increase with increase in the transmitter-receiver range. We next present a distributed solution of the sensor network localization problem based on second-order cone programming relaxation. This algorithm is independent of the ranging technique being used and is computationally more efficient than most contemporary approaches, and scalable to networks with thousands of nodes. We show that the nodes can estimate their positions based on local information. Unlike previous approaches, we also consider the effect of inaccurate reference node positions. In the presence of reference node position errors, the localization is performed in three steps. First, the unlocalized nodes estimate their positions using information from their neighbors. In the second step, the reference nodes refine their positions using relative distance information exchanged with their neighbors and finally, the previously unlocalized nodes refine their position estimates. We demonstrate the convergence of the algorithm numerically. The simulation results, shown for both uniform and irregular network topologies, illustrate the robustness of the algorithm to reference node position and distance estimation errors. We also present the prototype implementation of a directional beacon based positioning algorithm using radio frequency signals. This algorithm allows each unlocalized node to compute its position with respect to a set of reference nodes which are equipped with rotating directional antenna. The directional beacon based algorithm eliminates the need for strict synchronization between the reference nodes and the unlocalized node. In contrast to time-of-arrival based positioning algorithms that rely on signal propagation time and bandwidth, the directional beacon based algorithm depends on the width of the antenna beampattern and the rotational speed of the directional antenna. We will show that these parameters can be optimized in a low cost solution while providing good position estimates. The system implementation is based on the GNU Radio software platform and the Universal Software Radio Peripheral as the hardware component. To deal with obstructed line-of-sight scenarios, we do not rely purely on the received signal strength and instead formulate a least squares problem to estimate the line-of-sight component in a multipath environment. These signal processing techniques yield a more accurate estimation of the bearing of the unlocalized node with respect to each of the reference nodes. We demonstrate the ability to obtain unlocalized node position estimates with sub-meter accuracy by transmitting a narrowband signal of 1 KHz bandwidth in the 2.4 GHz band. Finally, event detection scenarios in sensor networks are considered. The goal in these network deployments is to detect certain critical or emergency conditions with minimum possible delay. We propose a heuristic based sensor selection and a sequential detection procedure that significantly improves the detection speed, measured in terms of the number of measurements needed for detection. In the proposed model, the fusion center selects one sensor at a time for measurement while maximizing a greedy heuristic. Instead of collecting a fixed number of measurements, the fusion center collects one measurement at each time step, until by some sequential decision rule the collection stops and a decision is made. The sequential detection procedure significantly outperforms a non-sequential (or fixed sample size) detector in that it always needs fewer measurements on average to achieve the same detection performance. In addition, we derive a simplified heuristic under the Gaussian probabilistic model. It is seen that the simplified heuristic performs as good as or slightly better than the greedy heuristic. The greedy heuristic based sensor selection provides a general framework for probabilistic models where a simplified heuristic is difficult to obtain. (Abstract shortened by UMI.)en-USPositioningLocalizationRangingUltrawidebandSOCP relaxationWireless sensor networksElectrical EngineeringThesis or Dissertation