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.

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