Fast Approximate Algorithms for Wireless Sensor Networks

无线传感器网络的快速近似算法

• 批准号: 0728645
• 负责人: Piotr Indyk
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728645&HistoricalAwards=false
• 关键词: Fast; Approximate; Algorithms; Wireless; Sensor

Sensor networks are one of the fastest growing network technologies. At the same time, however, they present new challenges. On the one hand, the sensors are given ambitious tasks of computing global properties using constantly changing and geographically distributed data. On the other hand, the sensors are significantly limited in their storage space, computation power, and communication bandwidth. To achieve their goals, sensornets need new theoretical foundations that integrate storage, computation, and communication, and enable the sensornet to pull its various resources together and funnel them toward its tasks.This project aims to create a formal framework for integrating storage, computation, and communication in sensornets. The proposed research assimilates three theories (sketching, property testing and network coding), into a synergetic design that greatly improves the communication throughput, while allowing for cheap computation and reduced storage space. Specifically, the proposed research consists of two components:- Network Sketching: a new architecture for sensornets that performs on-demand in-network compression of the data.This approach enables (lossy) compression of spatially correlated data at multiple sensors; manages network congestion by reducing data resolution as opposed to dropping some of the measurements; and naturally combines wireless network coding with sketching to boost the throughput of the wireless network.- Temporally Coherent Property Testing: a new computational model that extends the theory of property testing to a stream of temporally correlated data.This new paradigm enables quantifying the complexity of repeatedly checking for a particular property, and reduces the computational needs of sensor networks.

传感器网络是增长最快的网络技术之一。 但是，与此同时，他们提出了新的挑战。一方面，使用不断变化和地理分布的数据来赋予传感器的雄心勃勃的任务。另一方面，传感器的存储空间，计算能力和通信带宽受到显着限制。 为了实现他们的目标，Sensornet需要新的理论基础来集成存储，计算和通信，并使Sensornet能够将其各种资源汇总在一起，并将其汇入其任务。该项目旨在创建一个正式的框架，以集成存储，计算和在SensOrnet中进行通信。 拟议的研究将三种理论（素描，属性测试和网络编码）吸收为协同设计，可大大改善通信吞吐量，同时允许廉价计算和减少存储空间。具体而言，所提出的研究由两个组成部分组成： - 网络草图：SensOrnets的新架构，用于对数据进行按需网络内压缩。这种方法启用（损失）在多个传感器处的空间相关数据的压缩；通过减少数据解决方案而不是丢弃一些测量值来管理网络拥塞。自然地将无线网络编码与草图结合起来，以增强无线网络的吞吐量。-时间相干性属性测试：一种新的计算模型，将属性测试的理论扩展到时间相关的数据流，启用此新范式可以量化反复检查特定属性的复杂性，并降低传感器网络的计算需求。