The objective of this project is to develop efficient distributed algorithms for joint information processing, optimization and coordination of static, pervasive sensor nodes and mobile, autonomous agents that altogether monitor and act on the environment. The application scenarios include tracking, searching and planning mobile agents with the underlying sensor network as a supporting communication infrastructure, and online resource management and allocation guided by real-time sensor detections.
This project focuses on three research problems: distributed min-cost bipartite matching, kinetic minimum Steiner tree, and facility location for mobile nodes, by using two non-trivial technical approaches, namely, embedding of the network metric into tree metrics, and distributed primal dual framework. There are two central intellectual questions investigated in this project.
1) How to make use of the sensor data to best serve user requests? This involves developing communication efficient schemes for sensors detecting interesting local events and the mobile users seeking such information to find each other.
2) How to best make use of the continuity and coherence in mobility, either in the presence of mobility enabled sensor data (e.g., detections of continuously moving targets), as well as the locations of mobile users? The project provides solutions that adapt to the system configuration with low update cost, avoiding drastic sudden changes or any level of reconstruction.
This project helps to extend the current Internet to the physical world, encouraging seamless integrations of sensing and control of the physical environment. The PI integrates the research agenda with new and existing curriculum development for both undergraduate and graduate education, and continues her efforts in improving female presence in computer science and exposure of research for high school students.
This project developed efficient distributed algorithms for integrating static, pervasive sensor nodes and mobile, autonomous agents that altogether monitor and act on the environment. The outcome of the project can be described as two aspects: First, how to enable smooth, efficient information flow between mobile agents and static sensor nodes using efficient, distributed data structures; Second, how to manage and analyze information flow in such a hybrid setting. For the first aspect, we have obtained two main breakthrough results. The first one is to use a distributed algorithm to embed the sensor network metric onto a topological tree metric [Gao etal 09]. The use of this tree embedding allows the sensors to efficient aggregate data that can be made available to the mobile agents, which helps with matching mobile agents with spontaneously emerging events [Gao etal 09]; or maintaining spanning tree among the mobile agents [Zhou Gao 10]. It also allows low-stretch routing in the sensor network that is resilient to node/link failures when two or more trees are used [Gao, Zhou 11]. In a different setting but with a similar idea, we use a triangulation of the sensor network to guide routing in a complex environment with the given homotopy (getting around holes in a specific way) [Huang etal 14]. We developed the first algorithm that is distribtued and achieves constant stretch in this setting. The second one examined the classical capacitated clustering problem for both base stations/agents/centers and terminals nodes that are possibly in motion. This is a fundamental clustering problem that appears in a variety of applications such as data mule management etc. We make use of the geometric structure of this problem to develop efficient algorithms that are orders of magnitude faster than state of the art solutions. For the second aspect, we initiated the study of information dissemination through physical contacts enabled by real world mobilities. By studing multiple data sets from different cities, we discovered that the physical contacts have a number of properties similar to the social contact patterns such as the small world phoenomena. This also motivated us to study contagions in complex networks. In particular, we look at complex contagions which requires multiple reinforcement from neighbors and we are the first to analyze the behaviors in small world graph models and preferential attachment models [Ghasemiesfeh etal 13]. In conclusion, the mobility element introduced to static sensor network setup substantially enriched the capability of such networks. Novel methods to fully integrate the operation of the mobile and static nodes can substantially increase our capacity of monitoring, understanding and acting on the environment. For the broader impact, the project has made contributions toward excellence in both research and education. The results are obtained by using ideas from discrete geometry, algorithm design and computational geometry. Our work finds non-trivial applications in the area of computer networking and provides better solutions to many network related problems. We believe that the mathematical field gains from such applications not only additional motivations to the mathematical ideas but also new research problems and directions. The outreach activities include student mentoring, course development, workshop organization and activities that encourage women participation in computer science. The award supported a number of Ph.D students and provided training in mathematical and algorithmic knowledge as well as programming and implementation skills. Three Ph.D students received their degrees with partial support from this project. Three female Ph.D students have been involved in this project.
