Feature extraction and selection in the presence of nonlinear dependencies among the data is a fundamental challenge in unsupervised learning. We propose using a Gram-Schmidt (GS) type orthogonalization process over function spaces to detect and map out such dependencies. Specifically, by applying the GS process over some family of functions, we construct a series of covariance matrices that can either be used to identify new large-variance directions, or to remove those dependencies from known directions. In the former case, we provide information-theoretic guarantees in terms of entropy reduction. In the latter, we provide precise conditions by which the chosen function family eliminates existing redundancy in the data. Each approach provides both a feature extraction and a feature selection algorithm. Our feature extraction methods are linear, and can be seen as natural generalization of principal component analysis (PCA). We provide experimental results for synthetic and real-world benchmark datasets which show superior performance over state-of-the-art (linear) feature extraction and selection algorithms. Surprisingly, our linear feature extraction algorithms are comparable and often outperform several important nonlinear feature extraction methods such as autoencoders, kernel PCA, and UMAP. Furthermore, one of our feature selection algorithms strictly generalizes a recent Fourier-based feature selection mechanism (Heidari et al., IEEE Transactions on Information Theory, 2022), yet at significantly reduced complexity.

Multi-core platforms are becoming increasingly prevalent in cyber-physical systems such as automobiles and robots. However, contention for shared resources makes it chal-lenging to guarantee timing predictability. Existing studies have primarily focused on characterizing the extent to which such interference can induce delays (usually from an adversarial perspective). Unfortunately, less is understood on the physical impacts of these timing delays in different cyber-physical plat-forms. In this paper, we fill this gap by providing an empirical examination of the end-to-end effects of performance interference on real-world applications. We analyze the root causes of harmful interference and summarize potential implementation pitfalls. To automate this process, we introduce TimeTrap, a tool that analyzes performance interference in autonomous systems through the lens of control outcome. To understand the extent to which timing interference may cause control deviations, TimeTrap has to strategically leverage different magnitudes of resource contention to trigger targeted deadline miss patterns. Through this exercise, we found that a naive approach that maximizes task latency via performance interference may fail to trigger worst-case outcomes (i.e. physical damages) due to built-in fail-safe mechanisms. As a result, delays have to be induced in a stealthy manner to avoid triggering fail-safes. To achieve this, TimeTrap first employs a system that actively injects fine-grained delays into the target software, adjusting the duration based on measured feedback. Second, TimeTrap leverages predictability in CPS execution patterns and resource usage to automatically tune its aggressor workloads, matching these patterns to achieve targeted interference and execution delays in a victim. We evaluate TimeTrap on two physical-world platforms and six platforms in a hardware-in-the-Ioop simulation environment, including robotic arms, UGVs, UAVs, self-driving cars, and humanoid robots. These studies demonstrate that an interference-based attack surface exists in different stages of the CPS pipeline, from perception to planning and control.

This article introduces the notion of carelessness level into robot action planners such that the safety and efficiency are optimized. The core idea is to make the robot’s plan less sensitive to the behavior of careless humans who may inattentively violate safety constraints and degrade efficiency. More precisely, our planner reduces the opportunities given to the careless humans to put themselves in danger and hamper the efficiency of the robot’s plan. The effectiveness of the proposed planner is demonstrated through simulation studies on a packaging line and on a collaborative assembly line. Results show that the proposed scheme can improve efficiency and safety in both examples.

Industrial automation traditionally relies on local controllers implemented on microcontrollers or programmable logic controllers. With the emergence of edge computing, however, industrial automation evolves into a distributed two-tier computing architecture comprising local controllers and edge servers that communicate over wireless networks. Compared to local controllers, edge servers provide larger computing capacity at the cost of data loss over wireless networks. This article presents switching multitier control (SMC) to exploit edge computing for industrial control. SMC dynamically optimizes control performance by switching between local and edge controllers in response to changing network conditions. SMC employs a data-driven approach to derive switching policies based on classification models trained based on simulations while guaranteeing system stability based on an extended Simplex approach tailored for two-tier platforms. To evaluate the performance of industrial control over edge computing platforms, we have developedWCPS-EC, a real-time hybrid simulator that integrates simulated plants, real computing platforms, and real or simulated wireless networks. In a case study of an industrial robotic control system, SMC significantly outperformed both a local controller and an edge controller in face of varying data loss in a wireless network.

Beacon-based time-of-flight indoor localization systems have shown great promise for applications ranging from indoor navigation to asset tracking. In large-scale deployments, a major practical challenge is determining the placement of a minimal number of beacons that ensures full coverage -- each point in the domain has line-of-sight paths to enough beacons to uniquely localize itself. Three beacons with line-of-sight paths are always enough, but two beacons within line of sight may also work, given a favorable geometry. In this paper, we propose two beacon placement algorithms that leverage the floor plan geometry with provable theoretical guarantees. First, we present a greedy algorithm using properties of sub-modular functions to place O(OPT · ln m) beacons, where m is the number of discrete location points in the region that need to be localized, and OPT is the size of the optimal solution. Second, we present a random sampling algorithm that places O (OPT · log(OPT)) beacons while localizing all targets. We evaluate our algorithms on both real-world and randomly generated floor plans. Our algorithms place on an average 6 ~ 23% and 12% fewer beacons in real-world topologies and randomly generated floor plans respectively, as compared to prior work. We also present a study where we ask users to attempt to place nodes manually and discover that even humans that are well versed on the coverage problem find it hard to balance the trade-off between the number of beacons and area localized.

The Internet-of-Things (IoT) is a large and complex domain. These systems are often constructed using a very diverse set of hardware, software and protocols. This, combined with the ever increasing number of IoT solutions/services that are rushed to market means that most such systems are rife with security holes. Recent incidents (e.g., the Mirai botnet) further highlight such security issues. With emerging technologies such as blockchain and software-defined networks (SDNs), new security solutions are possible in the IoT domain. In this paper we will explore future trends in IoT security: (a) the use of blockchains in IoT security, (b) data provenance for sensor information, (c) reliable and secure transport mechanisms using SDNs (d) scalable authentication and remote attestation mechanisms for IoT devices and (e) threat modeling and risk/maturity assessment frameworks for the domain.

Indoor localization systems typically determine a position using either ranging measurements, inertial sensors, environmental-specific signatures or some combination of all of these methods. Given a floor plan, inertial and signature-based systems can converge on accurate locations by slowly pruning away inconsistent states as a user walks through the space. In contrast, range-based systems are capable of instantly acquiring locations, but they rely on densely deployed beacons and suffer from inaccurate range measurements given non-line-of-sight (NLOS) signals. In order to get the best of both worlds, we present an approach that systematically exploits the geometry information derived from building floor plans to directly improve location acquisition in range-based systems. Our solving approach can disambiguate multiple feasible locations taking into account a mix of LOS and NLOS hypotheses to accurately localize with significantly fewer beacons. We demonstrate our geometry-aware solving approach using a new ultrasonic beacon platform that is able to perform direct time-of-flight ranges on commodity smartphones. The platform uses Bluetooth Low Energy (BLE) for time synchronization and ultrasound for measuring propagation distance. We evaluate our system's accuracy with multiple deployments in a university campus and show that our approach shifts the 80% accuracy point from 4-8m to 1m as compared to solvers that do not use the floor plan information. We are able to detect and remove NLOS signals with 91.5% accuracy.

Recent efforts highlight the promise of data-driven approaches to optimize network decisions. Many such efforts use trace-driven evaluation; i.e., running offline analysis on network traces to estimate the potential benefits of different policies before running them in practice. Unfortunately, such frameworks can have fundamental pitfalls (e.g., skews due to previous policies that were used in the data collection phase and insufficient data for specific subpopulations) that could lead to misleading estimates and ultimately suboptimal decisions. In this paper, we shed light on such pitfalls and identify a promising roadmap to address these pitfalls by leveraging parallels in causal inference, namely the Doubly Robust estimator.

In this paper, we address the problem of range-based beacon placement given a floor plan to support indoor localization systems. Existing approaches for trilateration require three or more beacons to determine a unique position solution. We show that with prior knowledge of the map and a model of beacon coverage, it is possible to uniquely localize with only two beacons. This not only reduces installation cost by requiring fewer nodes, but can also improve robustness. One of the main challenges with respect to beacon placement algorithms is defining a metric for estimating performance. We propose augmenting the commonly used Geometric Dilution of Precision (GDOP) metric to account for indoor spaces. We then use this enhanced GDOP metric as part of a toolchain to compare various beacon placement algorithms in terms of coverage and expected accuracy. When applied to a set of real floor plans, our approach is able to reduce the number of beacons between 22% and 60% (33% on an average) as compared to standard trilateration.

Bitrate adaptation is critical in ensuring good users’ quality-of-experience (QoE) in Internet video delivery system. Several efforts have argued that accurate throughput prediction can dramatically improve (1) initial bitrate selection for low startup delay and high initial resolution; (2) midstream bitrate adaptation for high QoE. However, prior ef- forts did not systematically quantify real-world throughput predictability or develop good prediction algorithms. To bridge this gap, this paper makes three key technical contributions: First, we analyze the throughput characteristics in a dataset with 20M+ sessions. We find: (a) Sessions sharing similar key features (e.g., ISP, region) present similar initial values and dynamical patterns; (b) There is a natural “stateful” dynamical behavior within a given session. Second, building on these insights, we develop CS2P, a better throughput prediction system. CS2P leverages data-driven approach to learn (a) clusters of similar sessions, (b) an initial throughput predictor, and (c) a Hidden-Markov-Model based midstream predictor modeling the stateful evolution of throughput. Third, we develop a prototype system and show by trace-driven simulation and real-world experiments that CS2P outperforms state-of-art by 40% and 50% median pre- diction error respectively for initial and midstream through- put and improves QoE by 14% over buffer-based adaptation algorithm.

In today's large social and technological networks, since it is unfeasible to observe all the nodes, the source of diffusion is determined based on the observations of a subset of nodes. The probability of source localization error depends on the particular choice of observer nodes. We propose a criterion for observer node selection based on the minimal pairwise Chernoff distance between distributions of different source candidates. The proposed approach is optimal for the fastest error decay with vanishing noise. Although suboptimal for non-negligible noise, through simulation, we demonstrate its applicability in achieving low error probability. We also analyze the effect of network topology on the resulting error by bounding the smallest Chernoff distance for some specific networks.

In this paper, we present the design and evaluation of a platform that can be used for time synchronization and indoor positioning of mobile devices. The platform uses the Time-Difference-Of-Arrival (TDOA) of multiple ultrasonic chirps broadcast from a network of beacons placed throughout the environment to find an initial location as well as synchronize a receiver's clock with the infrastructure. These chirps encode identification data and ranging information that can be used to compute the receiver's location. Once the clocks have been synchronized, the system can continue performing localization directly using Time-of-Flight (TOF) ranging as opposed to TDOA. This provides similar position accuracy with fewer beacons (for tens of minutes) until the mobile device clock drifts enough that a TDOA signal is once again required. Our hardware platform uses RF-based time synchronization to distribute clock synchronization from a subset of infrastructure beacons connected to a GPS source. Mobile devices use a novel time synchronization technique leverages the continuously free-running audio sampling subsystem of a smartphone to synchronize with global time. Once synchronized, each device can determine an accurate proximity from as little as one beacon using TOF measurements. This significantly decreases the number of beacons required to cover an indoor space and improves performance in the face of obstructions. We show through experiments that this approach outperforms the Network Time Protocol (NTP) on smartphones by an order of magnitude, providing an average 720μs synchronization accuracy with clock drift rates as low as 2ppm.

The proliferation of Bluetooth Low-Energy (BLE) chipsets on mobile devices has lead to a wide variety of user-installable tags and beacons designed for location-aware applications. In this paper, we present the Acoustic Location Processing System (ALPS), a platform that augments BLE transmitters with ultrasound in a manner that improves ranging accuracy and can help users configure indoor localization systems with minimal effort. A user places three or more beacons in an environment and then walks through a calibration sequence with their mobile device where they touch key points in the environment like the floor and the corners of the room. This process automatically computes the room geometry as well as the precise beacon locations without needing auxiliary measurements. Once configured, the system can track a user's location referenced to a map.

We demonstrate the Acoustic Location Processing System (ALPS), a platform that augments BLE proximity beacons with ultrasonic transmitters in a manner that allows for precise and robust indoor localization. {\em ALPS} uses Time-Difference-Of-Arrival (TDOA) and Time-Of-Flight (TOF) ranging to accurately localize mobile devices such as off-the-shelf smartphones and tablets in 2D space. Users inside the demo area will be able to determine their location and can directly plot it relatively to a map of the area using our app on a smartphone. Once a receiving device has determined its initial position, it can synchronize its audio clock with the transmission infrastructure to perform TOF-based localization, which provides similar position accuracy to TDOA based localization with fewer beacons. Multilateration and trilateration processing for each device's location is offloaded onto a cloud-based solver that can provide localization as a service to ALPS and similar TOF/TDOA based systems.

User-perceived quality-of-experience (QoE) is critical in Internet video applications as it impacts revenues for content providers and delivery systems. Given that there is little support in the network for optimizing such measures, bottlenecks could occur anywhere in the delivery system. Consequently, a robust bitrate adaptation algorithm in client-side players is critical to ensure good user experience. Previous studies have shown key limitations of state-of-art commercial solutions and proposed a range of heuristic fixes. Despite the emergence of several proposals, there is still a distinct lack of consensus on: (1) How best to design this client-side bitrate adaptation logic (e.g., use rate estimates vs. buffer occupancy); (2) How well specific classes of approaches will perform under diverse operating regimes (e.g., high throughput variability); or (3) How do they actually balance different QoE objectives (e.g., startup delay vs. rebuffering). To this end, this paper makes three key technical contributions. First, to bring some rigor to this space, we develop a principled control-theoretic model to reason about a broad spectrum of strategies. Second, we propose a novel model predictive control algorithm that can optimally combine throughput and buffer occupancy information to outperform traditional approaches. Third, we present a practical implementation in a reference video player to validate our approach using realistic trace-driven emulations.

Traffic is not only a source of frustration but also a leading cause of death for people under 35 years of age. Recent research has focused on how driver assistance technologies can be used to mitigate traffic fatalities and create more enjoyable commutes. In this work, we consider cooperative adaptive cruise control (CACC) or platooning, a driver assistance technology that controls the speed of vehicles and inter-vehicle spacing. CACC equipped cars use radar to fine tune inter-vehicle spacing and dedicated short-range communication (DSRC) to collaboratively accelerate and decelerate. Platooning can reduce fuel consumption by over 5% and increases the density of cars on a highway. Previous work on platooning has focused on proving string stability, which guarantees that the error between cars does not grow with the length of a platoon, but little work has considered the impact an attacker can have on a platoon. To design safe distributed controllers and networks it is essential to understand the possible attacks that could be mounted against platoons.

Client-side bitrate adaptation algorithms play a critical role in delivering a good quality of experience for Internet video. Many studies have shown that current solutions perform suboptimally, and despite the proliferation of several proposals in this space, both from commercial providers and researchers, there is still a distinct lack of clarity and consensus w.r.t. several natural questions: (1) What objectives does/should such an algorithm optimize? (2) What environment signals such as buffer occupancy or throughput estimates should an algorithm use in its control loop? (3) How sensitive is an algorithm to operating conditions (e.g., bandwidth stability, buffer size, available bitrates)? This work attempts to bring clarity to this discussion by casting adaptive bitrate streaming as a model-based predictive control problem. We demonstrate the initial promise of shedding light on these questions using this control-theoretic abstraction.

It is often appealing to assume that existing solutions can be directly applied to emerging engineering domains. Unfortunately, careful investigation of the unique challenges presented by new domains exposes its idiosyncrasies, thus often requiring new approaches and solutions. In this paper, we argue that the “smart” grid, replacing its incredibly successful and reliable predecessor, poses a series of new security challenges, among others, that require novel approaches to the field of cyber security. We will call this new field cyber-physical security. The tight coupling between information and communication technologies and physical systems introduces new security concerns, requiring a rethinking of the commonly used objectives and methods. Existing security approaches are either inapplicable, not viable, insufficiently scalable, incompatible, or simply inadequate to address the challenges posed by highly complex environments such as the smart grid. A concerted effort by the entire industry, the research community, and the policy makers is required to achieve the vision of a secure smart grid infrastructure.

This paper presents data centers from a cyber–physical system (CPS) perspective. Current methods for controlling information technology (IT) and cooling technology (CT) in data centers are classified according to the degree to which they take into account both cyber and physical considerations. To evaluate the potential impact of coordinated CPS strategies at the data center level, we introduce a control-oriented model that represents the data center as two coupled networks: a computational network representing the cyber dynamics and a thermal network representing the physical dynamics. These networks are coupled through the influence of the IT on both networks: servers affect both the quality of service (QoS) delivered by the computational network and the generation of heat in the thermal network. Using this model, three control strategies are evaluated with respect to their energy efficiency and computational performance: a baseline strategy that ignores CPS considerations, an uncoordinated strategy that manages the IT and CT independently, and a coordinated strategy that manages the IT and CT together to achieve optimal performance with respect to both QoS and energy efficiency. Simulation results show that the benefits to be realized from coordinating the control of IT and CT depend on the distribution and heterogeneity of the computational and cooling resources throughout the data center. A new cyber–physical index (CPI) is introduced as a measure of this combined distribution of cyber and physical effects in a given data center. We illustrate how the CPI indicates the potential impact of using coordinated CPS control strategies.

We show that distributed detection over random networks, or using a random protocol, e.g., of the gossip type, is asymptotically optimal, if the rate of information flow across the random network is large enough. Asymptotic optimality is in the sense of Chernoff information; in other words, we determine when the exponential rate of decay of the error probability for distributed detection is the best possible and equal to the rate of decay of the best centralized detector. The rate of information flow is defined by |log r|, where r is the second largest eigenvalue of the second moment of the random, consensus weight matrix. We quantify interesting tradeoffs in distributed detection, between the rate of information flow and the achievable detection performance.

This paper concerns the use of large-scale wireless sensor networks to detect and locate leaks of specified gases in the presence of time-varying advection (air currents) and diffusion. We show that when leaks are rare but constant for long periods, Kalman filtering combined with binary hypothesis testing provides an effective alternative to full-scale hypothesis testing covering all possible combinations of leaks and leak intensities. To reduce energy consumption and use of communication bandwidth, a two-tiered strategy is proposed in which a reduced number of sensors (Tier 1) provides coarse-grid sensing. When a leak is detected by the Tier 1 strategy, fine-grained grids of sensors (Tier 2) are activated around the vicinities of the detected leak areas to provide more precise detection and localization. Energy consumption is further reduced by applying an information versus energy-based dynamic sensor selection technique. Details of a laboratory implementation are presented and simulation results illustrate the approach and demonstrate its effectiveness.

This paper considers control and estimation problems where the sensor signals and the actuator signals are transmitted to various subsystems over a network. In contrast to traditional control and estimation problems, here the observation and control packets may be lost or delayed. The unreliability of the underlying communication network is modeled stochastically by assigning probabilities to the successful transmission of packets. This requires a novel theory which generalizes classical control/estimation paradigms. The paper offers the foundations of such a novel theory.

We show that the coarse-grained and fine-grained localization problems for ad hoc sensor networks can be posed and solved as a pattern recognition problem using kernel methods from statistical learning theory. This stems from an observation that the kernel function, which is a similarity measure critical to the effectiveness of a kernel-based learning algorithm, can be naturally defined in terms of the matrix of signal strengths received by the sensors. Thus we work in the natural coordinate system provided by the physical devices. This not only allows us to sidestep the difficult ranging procedure required by many existing localization algorithms in the literature, but also enables us to derive a simple and effective localization algorithm. The algorithm is particularly suitable for networks with densely distributed sensors, most of whose locations are unknown. The computations are initially performed at the base sensors, and the computation cost depends only on the number of base sensors. The localization step for each sensor of unknown location is then performed locally in linear time. We present an analysis of the localization error bounds, and provide an evaluation of our algorithm on both simulated and real sensor networks.

Sensor networks are gaining a central role in the research community. This paper addresses some of the issues arising from the use of sensor networks in control applications. Classical control theory proves to be insufficient in modeling distributed control problems where issues of communication delay, jitter, and time synchronization between components are not negligible. After discussing our hardware and software platform and our target application, we review useful models of computation and then suggest a mixed model for design, analysis, and synthesis of control algorithms within sensor networks. We present a hierarchical model composed of continuous time-trigger components at the low level and discrete event-triggered components at the high level.

We are developing a system for autonomous navigation of unmanned aerial vehicles (UAVs) based on computer vision. A UAV is equipped with on-board cameras and each UAV is provided with noisy estimates of its own state, coming from GPS/INS. The mission of the UAV is low altitude navigation from an initial position to a final position in a partially known 3-D environment while avoiding obstacles and minimizing path length. We use a hierarchical approach to path planning. We distinguish between a global offline computation, based on a coarse known model of the environment and a local online computation, based on the information coming from the vision system. A UAV builds and updates a virtual 3-D model of the surrounding environment by processing image sequences and fusing them with sensor data. Based on such a model the UAV will plan a path from its current position to the terminal point. It will then follow such path, getting more data from the on-board cameras, and refining map and local path in real time.