Sensor network is a new computing paradigm that has many potential applications. Although much work has been done in this area, a great deal of effort has been put in simulation and experimental study. Some researchers proposed algorithms for sensor networks, but unfortunately many of them are based on the same assumptions as in traditional distributed computer systems including mobile ad-hoc networks. Sensor networks, however, are very different from the computing systems we have built before in terms of energy concerns, large scale, unreliable communication, etc. Thus, most of the algorithm design foundations are not suitable for sensor networks. We have two observations for a sensor network. First, a sensor network is composed of fragile nodes with limited computation capability, operated on limited battery power, and connected via lossy wireless networks. Therefore, due to the energy consumption of transmitting information to a single point, the imprecise knowledge of the network, and the dynamic status of the network, it is prohibitive to run centralized algorithms on a sensor network; instead, a localized algorithm is preferable. Second, since a sensor network consists of a large number of nodes, algorithm analysis is also different from that of traditional computer systems. Communication complexity is important because communication captures the energy consumption. In additon, analysis should not rely on the specific location of each node, but be based on the random distribution of the sensors. The random analysis, instead of the fixed graph structure, should be used for performance evaluation. Intellectual merit: We propose to address those theoretical challenges by examining the computational limitations and capabilities, algorithm design, and performance analysis for sensor networks based on localized diffusion-like operation and random analysis. Specifically, we look into three sensor network problems: clock synchronization, robot navigation and task assignment, and information diffusion in a mobile sensor network. The first problem is a classic topic for distributed systems, which has attracted much attention for the past several decades. By solving it, it can help us to understand the fundamental limitations and capabilities of a sensor network. The second application addresses one of the most important aspects of a sensor network: data dissemination. We design localized, fault-tolerant, and very simple algorithms for the above two problems. The third one estimates the speed for information diffusion in a random network, which is very important in analyzing the performance for a localized algorithm. The analysis techniques will benefit the algorithm design and analysis for other problems in sensor network applications and infrastructure design. We believe our effort is a first step toward understanding sensor networks, and exploring how to design and analyze algorithms for sensor networks. Much theoretical work has done on general networks, but most relies on the assumptions that are not appropriate for sensor networks. Localized and fault-tolerant algorithm design and analysis are very important and promising for the future prevalence of sensor network deployment. This research will help to solve and answer the fundamental problems and limits in sensor networks, for example, clock synchronization, data dissemination, information diffusion, and so on. Broader impact: The project will integrate research and education by introducing sensor network and more advanced algorithm design techniques to the students. It will help to supplement one undergraduate network course and design two graduate level courses. Results from the project will be disseminated via conferences, journals, and the Internet. Furthermore, this project will stimulate the collaboration with people from various disciplines, e.g., networking, computational geometry, online algorithm, matrix analysis, robotics, and so forth.
