Bhaskar Krishnamachari - US grants

Structural Health Monitoring (SHM) is a highly interdisciplinary area of research focused on developing techniques to detect damage in structures such as buildings, bridges, aircraft, ships and spacecraft. Most SHM research to date has focused either on global damage assessment techniques using low-resolution measurements of a structure's response to ambient excitation, or on limited local independent damage detection mechanisms.

This proposal advocates a paradigm shift in SHM, using decentralized local excitation and high-resolution measurements of response to these excitations, detected and collaboratively analyzed through a spatially
dense wireless network of devices. This shift promises simpler and more accurate techniques to identify and even localize damage within the structure.

The goal of the proposed research is the design of a networked computer system, with distributed actuation and sensing, for SHM. The term "networked SHM" denotes the class of monitoring systems that will
be enabled by this research. By combining local excitation with high-resolution sensing, networked SHM is quite distinct from other sensor network applications being examined today. Networked SHM promises a future where, for example, buildings are constructed using concrete mixed with several tens of thousands of embedded sensor devices as well as low-power local exciters. The network of sensors will be able to continuously monitor the structure, trigger alarms that identify the onset of damage, precisely pinpoint the location of damage and also provide a long-term history of ambient stresses imposed on the building.

Wireless sensor networks promise a revolution in information technology, by providing a high-resolution interface between the physical and virtual worlds. This research project aims to create a mathematical foundation for analyzing and designing data gathering protocols in these systems.

This project develops mathematical models of sensor network applications, environmental conditions, and protocol parameters, in order to quantify and bound the performance of protocols with respect to key metrics such as energy efficiency and response latency. It complements other ongoing efforts in the research community to design and evaluate these protocols via simulations and experimental studies. The mathematical models of protocols developed in this project will provide wireless sensor network designers with practical guidelines and insights on selecting and optimizing protocols for different applications, and making them adaptive. Fundamental performance bounds will reveal whether there is room for improvement, and in some cases even suggest new efficient protocol designs.

The research is being carried out in close collaboration with wireless sensor network systems and applications researchers in academia and industry, to ensure that the analysis is informed by and has a significant impact on the design of real-world systems. Such wireless sensor networks are envisioned to be used in domains ranging widely from environmental, industrial and structural monitoring to security applications.

The research is tightly coupled with an educational program that includes integration of the research activities into the undergraduate graduate networks curriculum at the University of Southern California, as well as outreach to public high school students in Los Angeles.

Networked embedded systems such as wireless sensor networks (WSNs) have the potential for revolutionizing data collection and analysis in physical sciences and other fields by allowing intelligent dense monitoring of the environment. State-of-the-art research in WSNs treats the problem of designing sensor network applications primarily as one of manual customization of low-level network protocols. The design complexity and required expertise make this approach insufficient for increasingly complex, compute-intensive distributed sensor systems.

There is a clear need for a new top-down methodology that automates a bulk of the low-level implementation aspects of design and allows the end user to focus on high level algorithm design and optimization.

Intellectual Merit:
* Development of models and methodologies for design automation of compute-intensive sensor networks, with a focus on two WSN applications: (i) networked structural health monitoring (SHM) where a large-scale network of thousands of sensor and actuator devices embedded into a building or bridge is deployed to continuously monitor the structure, trigger alarms that identify the onset of damage, precisely pinpoint the location of damage and also provide a long-term history of ambient stresses imposed on the building, (ii) networked micro-climate monitoring (MCM) where a network of multi-modal sensors is deployed to provide information about climatic variables such as temperature, light, humidity, etc., in the operational environment (e.g. a wildlife reserve).
*Application representation: A suitable model of computation (MoC), will be defined to capture the structure of computation and communication in the algorithms.
*Virtual architectures: The virtual architecture (abstract machine model) for the target sensor networks will include a network model, a set of computation and communication primitives, cost functions, and middleware services.
*Algorithms for design automation: Algorithms will be developed and middleware services used for in-network processing, such that the desired performance is achieved..
*Demonstration: The design automation methodology will be validated and demonstrated for the two target applications through simulation.

Broader Impacts:
*The target applications are of great benefit to society: SHM networks will improve the safety of our civil infrastructure including roads, bridges and buildings; while the MCM networks will advance our scientific knowledge of the complex ecological interactions between organisms
and their environment.
*More broadly, the proposed methodology will facilitate the rapid design and synthesis for a
wide range of compute-intensive sensor network applications.
*The results of the proposed work will be disseminated
on a timely basis to the research community and to industrial partners.
*This project will build on their existing collaboration which includes co-advising of PhD
students, and joint publications.
*The proposed research will also provide educational material for an advanced graduate
course on sensor networks at USC.

Abstract:

Large scale sensor networks can often be viewed as distributed databases in which information querying is a fundamental operation.

This project aims to research a framework for efficient information discovery in sensor networks, based on a new paradigm called "active query forwarding". The basic principle of this approach is to consider queries as active entities which move efficiently through the network in search of desired information.

A multi-part methodology is employed in the project. Algorithms are designed for query guidance, semantics, adaptation, and optimization; these are then evaluated through both mathematical analysis and computational simulations. Important elements of the active querying framework are further validated on real experimental platforms.

The expected results consist of: (1) a scalable querying framework, (2) its constituent mechanisms, and (3) the related evaluation and validation studies. Together, these provide a fundamental building block for information management in next-generation sensor networks. Utilizing such building blocks efficiently can potentially improve sensor network lifetimes by orders-of-magnitude over existing approaches, without sacrificing information quality. The techniques developed in this project are useful for a wide range of large-scale sensor network applications, from industrial process control to structural health monitoring.

The results of the project are to be disseminated widely and in a timely manner through high quality publications, talks, and interactions with several industrial teams. The project is also closely integrated with the undergraduate and graduate networks curriculum at the University of Southern California, including new courses on sensor and ad-hoc networks and the training of several M.S./Ph.D. students.

Proposal Number: 0627028
Investigators: Viktor Prasanna (PI), Bhaskar Krishnamachari (Co-PI)
Institution: University of Southern California
Title: NeTS-NOSS: A Middleware Framework for Rapid Composition and Deployment of Compute-Intensive Networked Embedded Systems


Abstract

Wireless sensor networks (WSN) have the potential to revolutionize data collection and analysis in physical sciences and other fields by allowing intelligent dense monitoring of the environment. The primary focus of WSN research till now has been the design and implementation of the basic sensor node hardware and low-level protocols such as those for localization, time synchronization, medium access, routing, etc. However, the composition and deployment of a complex networked sensing application is still a daunting task for the non-expert end user.

This project involves the design and evaluation of reusable middleware functions that provide easy-to-program abstractions of the underlying hardware and network services, allowing rapid composition and deployment of sensor network applications. The topics addressed by our research include the development and evaluation of suitable topological abstractions, task mapping and migration techniques, communication and computational primitives, and realistic performance models to evaluate designs.

We expect the middleware techniques developed in this project to significantly enhance the state of the art in the design of sensor networks for complex applications. The abstractions and tools we develop will help establish a paradigm shift from the current dependence on application-specific customized solutions to a generalized automated approach that facilitates rapid design and ease of deployment for a wide range of applications.

The outcomes of the research will be disseminated in a timely basis through publications, presentations, and collaborations to the academic research community as well as to industry. The project will also have a significant educational impact, by supporting graduate student research, and providing material for a course on wireless sensor networks taught at USC.

The explosive growth of mobile devices coupled with near universal connectivity creates new opportunities for community based mobile social networking applications.
In this class of applications each user in a community contributes their knowledge about their surrounding environments and the collective knowledge is used by the group members for a personal or social benefit. The foundational underpinning of all mobile social networks is a participant's desire to take advantage of the collective knowledge gained from other users in the community. However, as security concerns grow there is a desire to protect one's own privacy. Thus all mobile social networks have a fundamental tension between privacy and information utility. This tension can be well formulated as a game theory problem where a self-interested agent's behavior alters dynamically based on the behavior of other agents in the system. This research will investigate the existence and efficiency of Nash equilibria and also design mechanisms that can maximize application performance while satisfying the privacy concerns of users. In particular, this research is conducted in the context of two specific case studies: one pertaining to a mobile device-based real time vehicular traffic information application and another pertaining to a community based mobile application for enhancing personal safety. This research will provide an important proof-of-concept that a rigorous game-theoretic analysis and design
methodology can lead to practical systems to provide appropriate tradeoffs between privacy and user service. The lessons learned in this project will be broadly useful to the development of next-generation social participation-based applications for mobile devices.

While it has been shown theoretically that stochastic network
optimization techniques utilizing queue backpressure can result in
high performance cross-layer protocols, there has been limited prior
work on translating them into practice. In this exploratory research
project, we develop and demonstrate a novel cross-layer backpressure
protocol stack for wireless sensor networks, building on our
implementation of the backpressure collection protocol (BCP). The
possible gains of this highly agile approach to cross-layer wireless
networking are substantial and include increased throughput even in
the presence of mobility, handling of bursty external interference
events with reduced losses, and reduced protocol implementation
complexity. We incorporate techniques for MAC-layer backoff
prioritization, transport layer utility optimization, mechanisms to
handle various kinds of network dynamics, and interoperability with
asynchronous low power sleep schedules. Protocol implementation code
developed in the project will be released publicly as open-source. It
is expected that the successful completion of this project will
provide an important proof-of-concept that stochastic optimization
theory-driven protocols can be successful in practice.

This project explores the interplay between the topology/geometry of networks and their traffic load pattern with the ultimate objective of deriving new load-balancing algorithms based on curvature control. The phenomenon that is observed in reality is the strong concentration of the traffic on some small subsets of links/nodes. This can be seen in the Internet (?backbone?), in the power grid (?line overload?), in vehicular traffic, in metabolic exchange in living organisms, etc. This phenomenon?the emergence of the centroid?cannot be completely accounted for by the local heavy-tailed paradigm, but strong evidence is provided here that this is a general feature dictated by the large-scale hyperbolic structure of the underlying network. Here, hyperbolic is a metaphor to refer to the fact that such networks as the Internet Service Provider (ISP) behave like negatively curved Riemannian manifolds, of which the saddle is the most intuitive visualization. Behavior refers to the geodesic flow, which carries the traffic and controls its stability or instability (e.g., fluttering) under such perturbation as outage or power depletion.

The first part of the proposed research will be devoted to refining criteria for real networks to be identifiable with negatively curved Riemannian manifolds. After developing intuitive criteria based on angle deficit/excess and clustering coefficient, the Gromov Thin Triangle Condition (TTC) and Four-Point Condition (FPC) will be scaled by the size of the graph to become relevant to real networks, which, no matter how awesome their sizes, are nevertheless finite. This leads to the new concept of scale-specific Gromov hyperbolic graphs, of which the Rocketfuel data base already provides an example. Such real-life networks as those provided by Bell Labs, sensor networks, air traffic control, even metabolic and nervous system networks will be used as testbeds. Next, the first step towards congestion analysis is the development of a network-specific concept of centroid or center of mass, already known in the mathematical community in its Riemannian manifold version. While in simulation the centroid has appeared to coincide with the point of maximum traffic, an important research milestone will be the theoretical justification of this fact. At the other end of the curvature spectrum, there is strong evidence that traffic on uniformly positively curved networks is balanced, provided the Dijkstra routing algorithm incorporates a randomization of the equal cost paths.

The preceding leads to the culmination of the research: by reassigning link weights so that the resulting network is positively curved, the routing based on the modified network would balance the load. Provided that the Euler characteristic of the network reveals no obstructions, the reassignment is carried over by the so-called Yamabe flow algorithm, which has a decentralized structure and hence would mesh with such network algorithms as flooding. Finally, the algorithm will be given an adaptive control structure, meaning that once it reaches positive curvature, it will continuously update the link weights as necessitated by network outages, flash points, etc.

The intellectual merit of the proposed research is that it will take coarse geometry?which has over the past few years silently pervaded such diverse fields as wired and wireless networks, autonomous agents, cooperative control, even biochemistry?along its scale-specific reformulation relevant to complex real-life networks, which do not quite fit the mathematical idealization of Gromov hyperbolic graphs. Certainly, the most transformative part of the research is the load-balancing based on routing on a modified positively curved network. The latter will bring to the real world such curvature smoothing algorithms as the Yamabe flow, which was instrumental in the proof of one of the most celebrated mathematical puzzles of all times?the Poincar´e conjecture.

The broader impact of the proposed activity is that it will foster a well-focused, application-driven multidisciplinary collaboration between the Department of Electrical Engineering, the Computer Engineering group, and the most theoretical geometry/topology group of the Department of Mathematics. Joint seminars, group meetings, new course development, etc. will create a new breed of engineering students, knowledgeable in coarse geometry, which has so far not been part of the traditional engineering curriculum. Extensive collaboration with Bell Labs will be maintained throughout the project

The research objective of this award is to test the hypothesis that interactive, sensor monitoring and online control can significantly reduce the energy consumption of buildings (by 20 percent or more) while maintaining occupant comfort. Through simulations and experimentation, inputs from a wide range of modalities and platforms in a heterogeneous sensor system (including wired and wireless sensors; mobile and static sensors; automatic and human-input-based sensors) will be integrated and fused in order to measure and track indoor climate, energy usage, as well as occupant location, activities, and preferences with much higher accuracy and lower cost compared to homogeneous systems. The research will encompass mathematical and empirical analysis and evaluation of efficient online stochastic algorithms based on multi-armed bandit theory that take the integrated sensor measurements as input to learn over time how to automatically operate building controls, so as to minimize energy consumption while maintaining occupant comfort, and quantify the gains in energy consumption obtained in typical environments.

If successful, the research will establish a framework, where humans and building systems interact ubiquitously in real time through an integrated mobile sensor and control system for energy awareness and learning and energy efficiency in buildings. The results will be disseminated through and contribute to the civil and environmental engineering, electrical engineering and computer science curricula, multiple conference talks, and publications. A public outreach and energy education program is planned to raise public awareness on energy efficiency in buildings. Targeting K-12 classrooms, this program aims to attract minority students to the engineering profession in the greater Los Angeles area. An interactive game, focusing on teaching K-12 students how they can conserve energy in their daily life by modifying their behavior and habits will be prototyped and tested.

This research focuses on the problem of information acquisition in the context of spectrum sensing and utilization where a (set of) decision maker(s), by carefully controlling a sequence of actions with uncertain outcomes, dynamically refines his/her belief about stochastically time-varying parameters of interest such as spectrum availability and quality, in order to communicate over that spectrum as efficiently as possible.

The research represents a new theoretical framework for stochastic learning and decision-making in such settings termed Information Acquisition and Utilization Problems (IAUP). Motivated by a synthesis of the researchers' prior works on adaptive sampling, active hypothesis testing, and restless multi-armed bandits, this framework is particularly apt for problems of spectrum sensing and access for several reasons. First, unlike more general stochastic control frameworks such as partially observable Markov decision problems (POMDP's), the IAUP is a purely informational problem in that the actions of the decision maker change only its information state, but not the state of the underlying environment (spectrum quality). Second, in an IAUP there is a conceptual distinction between two kinds of actions: those taken to obtain/refine the information state, and those taken to utilize the current information state, potentially allowing for tractable solutions in many cases where a separation theorem can be proved between these two sets. Finally, an IAUP can explicitly capture the tradeoff between the cost of spectrum sensing and the accuracy and completeness of the information that can be obtained.

Recent developments in the automotive industry point to a new emerging domain of vehicular wireless networks, in which vehicles equipped with radios can communicate a wide range of information to each other and the wider Internet, including traffic and safety updates as well as infotainment content. The primary goal of this project is to develop a hybrid network architecture for such vehicular networks which combines both the existing cellular infrastructure as well as new vehicle-to-vehicle (V2V) communication capabilities. The hypothesis is that such a hybrid network architecture will improve cost, capacity and robustness, compared to either a purely centralized cellular-based approach or a purely distributed V2V approach. Under a hybrid architecture, the project aims to design information-centric protocols for information dissemination, aggregation, and storage, that can exploit the spatio-temporally localized nature of vehicular applications. Further, through mathematical analysis, computer simulations, as well as experimental implementation on a research fleet of vehicles, this project aims to evaluate the performance of these protocols.

This project will be a unique academia-industry collaborative project between researchers at the University of Southern California and General Motors. While the focus will very much be on basic research disseminated to the academic community through publications, the close interaction with a prominent industry partner will enable the research to have a strong impact on real-world vehicular networks. Material from this research project will be incorporated into graduate courses at USC. The aimed-for advance in information technology for the automotive domain could have significant social impact by enabling improvements in traffic safety, efficiency, user comfort and productivity.

While there are a variety of throughput-optimal wireless network protocols, more challenging is the problem of making the protocol optimal relative to such conflicting objectives as queue occupancy (related to latency) and routing cost (related to power management), while holding throughput-optimality. The first step in that direction is the design of a protocol mimicking heat diffusion, as the celebrated Dirichlet principle of heat calculus already endows the routing with minimum routing cost property. The next step requires a significant departure from heat diffusion in order to make the protocol Pareto-optimal relative to routing cost and queue occupancy, while enforcing interference restrictions, link directionality and capacity. From this point onwards, the research effort will be conducted along two different lines of investigation. First, since the classical heat calculus had to be modified in a nontrivial way to make it an implementable wireless network protocol, there is a need to understand the ?heat equation? in the context of directed graphs, subject to interference restrictions and capacity constraints. Classical heat calculus involves the classical Laplacian, which is a linear operator, while here the central mathematical object of concern of this new "heat calculus" is a nonlinear Laplacian in the fluid limit, which describes the rate-level, rather than packet-level, behavior of the stochastic wireless network. The second line of investigation is dedicated to finding the network invariant that could anticipate the potential for large queue occupancy and/or large routing cost. We will develop the Ollivier-Ricci curvature as a computationally implementable network parameter inversely proportional to queue occupancy and routing cost, even under directionality and other network constraints. Also, the Ollivier-Ricci curvature will be investigated as a predictor of the size of the capacity region. Finally, the research will culminate with some Ricci flow technique to optimize the network for maximum Ollivier-Ricci curvature, hence attaining the largest capacity region.

The framework of this proposal is applicable to a wide family of stochastic problems with interdependent resources, where the resources are a collection of interdependent servers that can only be accessed under certain constraints, and the consumers are of random service time with asynchronous completion. This general model describes a wide variety of problems including queuing networks, product assembly systems, memory or processor managements, call centers, agent allocations, data switches, healthcare systems, and transmission planning or storage allocation in power systems just to name a few. Specifically, the research will strive to achieve cross-fertilization among this broad set of problems with classical thermodynamics and Ohm?s law in circuit theory that open a new way to analyze and optimize these complicated problems.

The University of Southern California plans to work together with Arizona State University, University of Arizona, Southern Illinois University and University of Connecticut to form a new NSF Industry University Cooperative Research Center (IUCRC) for Networked Embedded, Smart and Trusted Things (NESTT). The vision of the NESTT center is to contribute to the development of an equitable, safe and secure connected world, focusing on creating holistic Internet of things (IoT) solutions by integrating technology disciplines with expertise in other areas such as law, business, and humanities.

This planning grant's objective is to organize workshops and a planning meeting with industry partners to form the research agenda for NESTT and to explore industry commitment to the proposed center. At these workshops and the planning meeting, USC faculty will present and discuss their research pertaining to IoT, spanning a range of technology horizontals, including networking, distributed edge and cloud computing, blockchain, formal methods, machine learning, data analytics and security, as well as application verticals, including transportation, energy, smart buildings, and smart cities, and interdisciplinary collaborations with non-engineering experts from business, policy, and education.

The proposed NESTT center aims to undertake cutting edge fundamental and applied research that will lower the barriers to the adoption of IoT technologies through holistic multidisciplinary design and innovation in diverse domains such as smart cities, transportation, and energy. These research activities would lead to broader economic, societal and environmental benefits and contribute to new scientific discoveries. The planning effort will also seek effective ways for the proposed center to broaden the participation of underrepresented students in STEM disciplines.

Information about the NESTT IUCRC planning meeting and associated workshops will be posted online at USC under the auspices of the USC Viterbi Center for Cyber-Physical Systems and the Internet of Things (website: http://cci.usc.edu/).

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.