Indiana University-Purdue University Indianapolis (IUPUI) / Indoor tracking is a challenging problem. The level of accepted error is on a much smaller scale than that of its outdoor counterpart. While the global positioning system has become omnipresent, and a widely accepted outdoor tracking system it has limitations in indoor environments due to loss or degradation of signal. Many attempts have been made to address this challenge, but currently none have proven to be the de-facto standard. In this thesis, we introduce the concept of opportunistic tracking in which tracking takes place with whatever sensing infrastructure is present – static or mobile, within a given indoor environment. In this approach many of the challenges (e.g., high cost, infeasible infrastructure deployment, etc.) that prohibit usage of existing systems in typical application domains (e.g., asset tracking, emergency rescue) are eliminated. Challenges do still exist when it comes to provide an accurate positional estimate of an entities location in an indoor environment, namely: sensor classification, sensor selection, and multi-sensor data fusion. We propose an enhanced tracking framework that through the infusion of QoS-based selection criteria of trust and reliability we can improve the overall accuracy of the tracking estimate. This improvement is predicated on the introduction of learning techniques to classify sensors that are dynamically discovered as part of this opportunistic tracking approach. This classification allows for sensors to be properly identified and evaluated based upon their specific behavioral characteristics through performance evaluation. This in-depth evaluation of sensors provides the basis for improving the sensor selection process. A side effect of obtaining this improved accuracy is the cost, found in the form of system runtime. This thesis provides a solution for this tradeoff between accuracy and cost through an optimization function that analyzes this tradeoff in an effort to find the optimal subset of sensors to fulfill the goal of tracking an object as it moves indoors. We demonstrate that through this improved sensor classification, selection, data fusion, and tradeoff optimization we can provide an improvement, in terms of accuracy, over other existing indoor tracking systems.

In this thesis we consider two combinatorial optimization problems that relate to the field of persistent monitoring. In the first part, we extend the classic problem of finding the maximum weight Hamiltonian cycle in a graph to the case where the objective is a submodular function of the edges. We consider a greedy algorithm and a 2-matching based algorithm, and we show that they have approximation factors of 1/2+κ and max{2/(3(2+κ)),(2/3)(1-κ)} respectively, where κ is the curvature of the submodular function. Both algorithms require a number of calls to the submodular function that is cubic to the number of vertices in the graph. We then present a method to solve a multi-objective optimization consisting of both additive edge costs and submodular edge rewards. We provide simulation results to empirically evaluate the performance of the algorithms. Finally, we demonstrate an application in monitoring an environment using an autonomous mobile sensor, where the sensing reward is related to the entropy reduction of a given a set of measurements. In the second part, we study the problem of selecting sensors to obtain the most accurate state estimate of a linear system. The estimator is taken to be a Kalman filter and we attempt to optimize the a posteriori error covariance. For a finite time horizon, we show that, under certain restrictive conditions, the problem can be phrased as a submodular function optimization and that a greedy approach yields a 1-1/(e^(1-1/e))-approximation. Next, for an infinite time horizon, we characterize the exact conditions for the existence of a schedule with bounded estimation error covariance. We then present a scheduling algorithm that guarantees that the error covariance will be bounded and that the error will die out exponentially for any detectable LTI system. Simulations are provided to compare the performance of the algorithm against other known techniques.

In this thesis we consider two combinatorial optimization problems that relate to the field of persistent monitoring. In the first part, we extend the classic problem of finding the maximum weight Hamiltonian cycle in a graph to the case where the objective is a submodular function of the edges. We consider a greedy algorithm and a 2-matching based algorithm, and we show that they have approximation factors of 1/2+κ and max{2/(3(2+κ)),(2/3)(1-κ)} respectively, where κ is the curvature of the submodular function. Both algorithms require a number of calls to the submodular function that is cubic to the number of vertices in the graph. We then present a method to solve a multi-objective optimization consisting of both additive edge costs and submodular edge rewards. We provide simulation results to empirically evaluate the performance of the algorithms. Finally, we demonstrate an application in monitoring an environment using an autonomous mobile sensor, where the sensing reward is related to the entropy reduction of a given a set of measurements. In the second part, we study the problem of selecting sensors to obtain the most accurate state estimate of a linear system. The estimator is taken to be a Kalman filter and we attempt to optimize the a posteriori error covariance. For a finite time horizon, we show that, under certain restrictive conditions, the problem can be phrased as a submodular function optimization and that a greedy approach yields a 1-1/(e^(1-1/e))-approximation. Next, for an infinite time horizon, we characterize the exact conditions for the existence of a schedule with bounded estimation error covariance. We then present a scheduling algorithm that guarantees that the error covariance will be bounded and that the error will die out exponentially for any detectable LTI system. Simulations are provided to compare the performance of the algorithm against other known techniques.

An unknown input observer provides perfect asymptotic tracking of the state of a system affected by unknown inputs. Such an observer exists (possibly requiring a delay in estimation) if and only if the system satisfies a property known as strong detectability. In this thesis, we consider the problem of selecting (at design-time) a minimum cost subset of sensors from a given set to make a given system strongly detectable. We show this problem is NP-hard even when the system is stable. Furthermore, we show it is not possible to approximate the minimum cost within a factor of log(n) in polynomial-time (unless P=NP). However, we prove if a given system (with a selected set of sensors) is already strongly detectable, finding the smallest set of additional sensors to install to obtain a zero-delay observer can be done in polynomial time. Next we consider the problem of attacking a set of deployed sensors to remove the property of strong detectability. We show finding the smallest number of sensors to remove is NP-hard. Lastly through simulations, we analyze two greedy approaches for approximating the strong detectability sensor selection problem.

Optimum Sensor Localization/Selection in A Diagnostic/Prognostic Architecture Guangfan Zhang 107 Pages Directed by Dr. George J. Vachtsevanos This research addresses the problem of sensor localization/selection for fault diagnostic purposes in Prognostics and Health Management (PHM)/Condition-Based Maintenance (CBM) systems. The performance of PHM/CBM systems relies not only on the diagnostic/prognostic algorithms used, but also on the types, location, and number of sensors selected. Most of the research reported in the area of sensor localization/selection for fault diagnosis focuses on qualitative analysis and lacks a uniform figure of merit. Moreover, sensor localization/selection is mainly studied as an open-loop problem without considering the performance feedback from the on-line diagnostic/prognostic system. In this research, a novel approach for sensor localization/selection is proposed in an integrated diagnostic/prognostic architecture to achieve maximum diagnostic performance. First, a fault detectability metric is defined quantitatively. A novel graph-based approach, the Quantified-Directed Model, is called upon to model fault propagation in complex systems and an appropriate figure-of-merit is defined to maximize fault detectability and minimize the required number of sensors while achieving optimum performance. Secondly, the proposed sensor localization/selection strategy is integrated into a diagnostic/prognostic system architecture while exhibiting attributes of flexibility and scalability. Moreover, the performance is validated and verified in the integrated diagnostic/prognostic architecture, and the performance of the integrated diagnostic/prognostic architecture acts as useful feedback for further optimizing the sensors considered. The approach is tested and validated through a five-tank simulation system. This research has led to the following major contributions: ??generalized methodology for sensor localization/selection for fault diagnostic purposes. ??quantitative definition of fault detection ability of a sensor, a novel Quantified-Directed Model (QDG) method for fault propagation modeling purposes, and a generalized figure of merit to maximize fault detectability and minimize the required number of sensors while achieving optimum diagnostic performance at the system level. ??novel, integrated architecture for a diagnostic/prognostic system. ??lidation of the proposed sensor localization/selection approach in the integrated diagnostic/prognostic architecture.

Context information on a smart phone can be used to tailor applications for specific situations (e.g. provide tailored routing advice based on location, gas prices and traffic). However, typical context-aware smart phone applications use very limited context information such as user identity, location and time. In the future, smart phones will need to decide from a wide range of sensors to gather information from in order to best accommodate user needs and preferences in a given context. In this thesis, we present a model for active sensor selection within decision-making processes, in which observational features are selected based on longer-term impact on the decisions made by the smart phone. This thesis formulates the problem as a partially observable Markov decision process (POMDP), and proposes a non-myopic solution to the problem using a state of the art approximate planning algorithm Symbolic Perseus. We have tested our method on a 3 small example domains, comparing different policy types, discount factors and cost settings. The experimental results proved that the proposed approach delivers a better policy in the situation of costly sensors, while at the same time provides the advantage of faster policy computation with less memory usage.

Context information on a smart phone can be used to tailor applications for specific situations (e.g. provide tailored routing advice based on location, gas prices and traffic). However, typical context-aware smart phone applications use very limited context information such as user identity, location and time. In the future, smart phones will need to decide from a wide range of sensors to gather information from in order to best accommodate user needs and preferences in a given context. In this thesis, we present a model for active sensor selection within decision-making processes, in which observational features are selected based on longer-term impact on the decisions made by the smart phone. This thesis formulates the problem as a partially observable Markov decision process (POMDP), and proposes a non-myopic solution to the problem using a state of the art approximate planning algorithm Symbolic Perseus. We have tested our method on a 3 small example domains, comparing different policy types, discount factors and cost settings. The experimental results proved that the proposed approach delivers a better policy in the situation of costly sensors, while at the same time provides the advantage of faster policy computation with less memory usage.

abstract: Modern measurement schemes for linear dynamical systems are typically designed so that different sensors can be scheduled to be used at each time step. To determine which sensors to use, various metrics have been suggested. One possible such metric is the observability of the system. Observability is a binary condition determining whether a finite number of measurements suffice to recover the initial state. However to employ observability for sensor scheduling, the binary definition needs to be expanded so that one can measure how observable a system is with a particular measurement scheme, i.e. one needs a metric of observability. Most methods utilizing an observability metric are about sensor selection and not for sensor scheduling. In this dissertation we present a new approach to utilize the observability for sensor scheduling by employing the condition number of the observability matrix as the metric and using column subset selection to create an algorithm to choose which sensors to use at each time step. To this end we use a rank revealing QR factorization algorithm to select sensors. Several numerical experiments are used to demonstrate the performance of the proposed scheme. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics 2015

In recent years, advances in information technology have led to an increasing number of devices (or things) being connected to the internet; the resulting data can be used by applications to acquire new knowledge. The Internet of Things (IoT) (a network of computing devices that have the ability to interact with their environment without requiring user interaction) and big data (a field that deals with the exponentially increasing rate of data creation, which is a challenge for the cloud in its current state and for standard data analysis technologies) have become hot topics. With all this data being produced, new applications such as predictive maintenance are possible. One such application is monitoring a fleet of vehicles in real-time to predict their remaining useful life, which could help companies lower their fleet management costs by reducing their fleet's average vehicle downtime. Consensus self-organized models (COSMO) approach is an example of a predictive maintenance system for a fleet of public transport buses, which attempts to diagnose faulty buses that deviate from the rest of the bus fleet. The present work proposes a novel IoT-based architecture for predictive maintenance that consists of three primary nodes: namely, the vehicle node (VN), the server leader node (SLN), and the root node (RN). The VN represents the vehicle and performs lightweight data acquisition, data analytics, and data storage. The VN is connected to the fleet via its wireless internet connection. The SLN is responsible for managing a region of vehicles, and it performs more heavy-duty data storage, fleet-wide analytics, and networking. The RN is the central point of administration for the entire system. It controls the entire fleet and provides the application interface to the fleet system. A minimally viable prototype (MVP) of the proposed architecture was implemented and deployed to a garage of the Soci\'et\'e de Transport de l'Outaouais (STO), Gatineau, Canada. The VN in the MVP was implemented using a Raspberry Pi, which acquired sensor data from a STO hybrid bus by reading from a J1939 network, the SLN was implemented using a laptop, and the RN was deployed using meshcentral.com. The goal of the MVP was to perform predictive maintenance for the STO to help reduce their fleet management costs. The present work also proposes a fleet-wide unsupervised dynamic sensor selection algorithm, which attempts to improve the sensor selection performed by the COSMO approach. I named this algorithm the improved consensus self-organized models (ICOSMO) approach. To analyze the performance of ICOSMO, a fleet simulation was implemented. The J1939 data gathered from a STO hybrid bus, which was acquired using the MVP, was used to generate synthetic data to simulate vehicles, faults, and repairs. The deviation detection of the COSMO and ICOSMO approach was applied to the synthetic sensor data. The simulation results were used to compare the performance of the COSMO and ICOSMO approach. Results revealed that in general ICOSMO improved the accuracy of COSMO when COSMO was not performing optimally; that is, in the following situations: a) when the histogram distance chosen by COSMO was a poor choice, b) in an environment with relatively high sensor white noise, and c) when COSMO selected poor sensors. On average ICOSMO only rarely reduced the accuracy of COSMO, which is promising since it suggests deploying ICOSMO as a predictive maintenance system should perform just as well or better than COSMO . More experiments are required to better understand the performance of ICOSMO. The goal is to eventually deploy ICOSMO to the MVP.

The Internet of Things (IoT) is a foundational building block for the upcoming information revolution. Particularly, the IoT bridges the cyber domain to anything within our physical world which enables unprecedented monitoring, connectivity, and smart control. The utilization of Unmanned Aerial Vehicles (UAVs) can offer an extra level of flexibility which results in more advanced and efficient connectivity and data aggregation. In the first part of the thesis, we focus on the optimal IoT devices placement and, the spectral and energy budgets management for accurate source estimation. Practical aspects such as measurement accuracy, communication quality, and energy harvesting are considered. The problem is formed such that a set of cheap and expensive sensors are placed to minimize the estimation error under limited system cost. The IoT revolution relies on aggregating big data from massive numbers of devices that are widely scattered in our environment. These devices are expected to be of low- complexity, low-cost, and limited power supply, which impose stringent constraints on the network operation. Aerial data transmission offers strong line-of-sight links and flexible/instant deployment. The UAV-enabled IoT networks can, for instance, offer solutions to avoid and manage natural disasters such as forest fire. We investigate in this thesis the aerial data aggregation for field estimation, wildfire detection, and connection coverage enhancement via UAVs. To accomplish the network task, the field of interest is divided into several subregions over which the UAVs hover to collect samples from the underlying nodes. To this end, we formulate and solve optimization problems to minimize total hovering and traveling times. This goal is fulfilled by optimizing the UAV hovering locations, the hovering time at each location, and the trajectory traversed between hovering locations. Finally, we propose the utilization of the tethered UAV (T-UAV) to assist the terrestrial network, where the tether provides power supply and connects the T-UAV to the core network through a high capacity link. The T-UAV however has limited mobility due to the limited tether length. A stochastic geometry-based analysis is provided for the optimal coverage probability of T-UAV-assisted cellular networks.