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.

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