Localized Algorithm Design and Analysis

传感器网络是一种新的计算范式，具有许多潜在的应用。虽然在这方面已经做了大量的工作，但在仿真和实验研究方面也投入了大量的精力。一些研究人员提出了传感器网络的算法，但遗憾的是，其中许多算法都是基于与包括移动自组织网络在内的传统分布式计算机系统相同的假设。然而，传感器网络在能耗、大规模、通信不可靠等方面与我们以前构建的计算系统有很大的不同，因此大多数算法设计基础都不适合传感器网络。首先，传感器网络由计算能力有限的脆弱节点组成，依靠有限的电池功率工作，并通过有损无线网络连接。因此，由于向单点传输信息的能量消耗、对网络的不精确了解以及网络的动态状态，在传感器网络上运行集中式算法是不可取的；相反，本地化算法是可取的。其次，由于传感器网络由大量的节点组成，算法分析也不同于传统的计算机系统。通信复杂性很重要，因为通信捕获了能源消耗。此外，分析不应依赖于每个节点的具体位置，而是基于传感器的随机分布。对于传感器网络的性能评估，应该使用随机分析，而不是固定的图结构。智力优势：我们提出了通过考察基于局部扩散类运算和随机分析的传感器网络的计算模拟和能力、算法设计和性能分析来解决这些理论挑战。具体地说，我们研究了三个传感器网络问题：时钟同步、机器人导航和任务分配以及移动传感器网络中的信息扩散。第一个问题是分布式系统的经典问题，在过去的几十年里引起了人们的极大关注。通过解决这个问题，它可以帮助我们了解传感器网络的基本限制和功能。第二个应用涉及传感器网络最重要的方面之一：数据传播。针对上述两个问题，我们设计了局部化的、容错的、非常简单的算法。第三种方法估计信息在随机网络中的扩散速度，这对于分析局部化算法的性能是非常重要的。这些分析技术将有助于传感器网络应用和基础设施设计中其他问题的算法设计和分析。我们相信，我们的努力是理解传感器网络，探索如何设计和分析传感器网络算法的第一步。许多理论工作已经在一般网络上完成，但大多数依赖于不适用于传感器网络的假设。局部化和容错算法的设计和分析对于未来传感器网络部署的普及具有非常重要的意义和前景。这项研究将有助于解决和回答传感器网络中的基本问题和限制，如时钟同步、数据分发、信息扩散等。广泛的影响：该项目将通过向学生介绍传感器网络和更先进的算法设计技术，将研究和教育结合起来。它将有助于补充一门本科网络课程，并设计两门研究生水平的课程。该项目的成果将通过会议、期刊和互联网传播。此外，该项目将促进与来自不同学科的人的合作，例如网络、计算几何、在线算法、矩阵分析、机器人学等。

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 computationallimitations 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.