Localized Algorithm Design and Analysis

本地化算法设计与分析

• 批准号: 0514985
• 负责人: Qun Li
• 金额: $ 10万
• 依托单位: College of William and Mary
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514985&HistoricalAwards=false
• 关键词: Localized; Algorithm; Design; 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.

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