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.

传感器网络是发展最快的网络技术之一。然而，与此同时，它们也带来了新的挑战。一方面，传感器被赋予了雄心勃勃的任务，即使用不断变化和地理分布的数据计算全局属性。另一方面，传感器在存储空间、计算能力和通信带宽方面受到很大限制。为了实现它们的目标，传感器需要新的理论基础来集成存储、计算和通信，并使传感器能够将各种资源聚集在一起，并将它们汇集到其任务中。该项目旨在创建一个正式的框架，用于集成传感器的存储、计算和通信。提出的研究将三种理论（草图，属性测试和网络编码）融合到一个协同设计中，大大提高了通信吞吐量，同时允许廉价的计算和减少存储空间。具体来说，提出的研究包括两个组成部分：网络草图：一种新的传感器架构，用于按需在网络中压缩数据。这种方法可以对多个传感器的空间相关数据进行（有损）压缩；通过降低数据分辨率来管理网络拥塞，而不是放弃一些测量；并自然地将无线网络编码与绘图相结合，以提高无线网络的吞吐量。-时间相干属性测试：一种新的计算模型，将属性测试理论扩展到时间相关数据流。这种新模式可以量化重复检查特定属性的复杂性，并减少传感器网络的计算需求。