无线传感器网络中分布式近似计算方法的研究

摘要

随着微电子技术、嵌入式技术、集成电路以及无线通信技术的日益成熟,无线传感器网络开始进入了人们的生活,并为人类低成本地观察、认知复杂物理世界提供了一条有效途径。目前,传感器网络已广泛应用于环境监测、医疗卫生、国防军事等各大领域。在构成传感网的诸多要素之中,传感器节点采集的感知数据是其核心部分之一,几乎传感网的所有应用都是建立在感知数据的计算(包含查询、分析、挖掘等)基础之上的。由于传感网中感知数据的规模庞大,将其传送至Sink节点再进行计算势必将消耗大量能量,故分布式的网内计算方法对传感网来说十分重要。并且,由于传感器节点在感知、计算、通信、存储及能源等方面的能力均十分有限,故在许多情况下,传感网无法给出精确的查询分析结果。此时,正如智者亚里士多德所述,我们不必纠结于无法获得的精确结果,具有一定误差保证的近似结果亦是可接受的。综上,在传感网的研究中,设计低能耗的、分布式的、具有一定误差保证的感知数据近似计算方法具有极其重要的意义。本文开展了这方面的研究,主要研究成果如下:
　　首先,本文研究了静态传感器网络中的-近似聚集算法。聚集操作是传感网中的一种十分重要的操作。由于精确聚集算法的能量开销很大,因而,近年来人们开展了对近似聚集算法的研究。然而,现有的网内近似聚集算法均具有固定的误差界,并且很难调节,所以一旦用户所需要的误差小于已有聚集算法所能保证的误差界时,这些算法将失效。为了解决该问题,使得近似聚集结果能够满足用户任意的精度需求,本文开展了传感器网络中的-近似聚集算法的研究,并基于均衡抽样技术,提出了静态传感器网络中的-近似聚集算法。在该研究中,我们首先针对聚集和、平均值、无重复计数值等3种聚集操作,给出了根据来确定优化的样本容量的数学方法。其次,我们提出了一种分布式的均衡抽样算法,用以完成样本数据的抽取,并且我们对该算法的计算与通信复杂性进行了分析。第三,我们给出了估计聚集和、平均值、无重复计数值的数学方法,根据这些数学方法,提出了一种静态传感器网络中的-近似聚集算法,并证明了该算法能够满足用户的任意精确度需求。第四,鉴于和感知数据的变化会影响最终的聚集结果,我们提出了两种样本数据信息的维护更新算法,分别用于处理和网络中感知数据发生变化的情况。最后,通过模拟实验验证了本部分提出的算法的有效性。
　　其次,本文研究了动态传感器网络中的-近似聚集算法。虽然第一部分所给出的算法能够满足用户任意的精确需求,并在静态网络中具有较高性能,但是该算法需要Sink节点频繁地统计各个簇及全网内处于活动状态的节点的数量,考虑到动态传感网中活动节点数目是不断变化的,故该算法不适合应用于动态传感网之中。进而,本文开展了动态传感网中的-近似聚集算法的研究,并基于Bernoulli抽样技术,提出了4种-近似聚集算法。在该研究中,我们首先针对活动节点计数值、感知数据聚集和、平均值等3种聚集操作,给出了跟据来确定优化的抽样概率的数学方法。其次,我们给出了适应动态网络环境的、分布式的Bernoulli抽样方法,用以获取样本数据,并对该算法计算与通信复杂度进行了分析。第三,我们给出了估计活动节点计数值、感知数据聚集和与平均值的数学方法。第四,在上述数学方法基础上,我们给出了4种基于Bernoulli抽样的-近似聚集算法,分别用以处理Snapshot查询与连续查询。我们证明了上述4种算法能够满足用户任意的精度需求,并且能够适应动态的网络环境。最后,通过详尽的模拟实验验证了本部分提出的算法的性能。
　　第三,本文研究了传感器网络中的地理位置敏感的极值点查询算法。在传感网收集的大量数据中,感知数据的极值点(例如,感知数据的最大值)及其所出现的地理位置有助于用户识别与定位异常区域,对于用户来说十分重要。虽然传统的top-k查询亦能够返回最大的k个感知值及其发生位置,但是由于在传统top-k查询处理过程中未考虑感知数据的空间相关性,所以其返回的结果(包括感知值及其位置)往往集中于一个小区域,为用户提供的异常信息也极其有限。并且,由于传统top-k查询结果包含着大量的冗余数据,从而使得传输上述结果的能量消耗过大。鉴于上述原因,本文提出了一种新的查询,称之为地理位置敏感的极值点查询(Location Aware Peak Value Query),简记为LAP-(D,k)查询,并对LAP-(D,k)查询处理算法进行了研究。在该研究中,我们首先对LAP-(D,k)查询处理问题进行了严格定义,并证明了该问题是NP-难的。其次,我们分别给出了两种分布式近似算法用以解决LAP-(D,k)查询处理问题。第三,我们证明了这两种算法均具有常数近似比,同时,我们亦对上述两种算法的计算和通信复杂度进行了详细的分析。最后,通过真实和模拟实验验证了本部分提出的算法在精确性及能量消耗方面均具有较高的性能。
　　第四,本文研究了传感器网络中物理过程近似逼近算法。目前,几乎所有的感知数据计算技术均是建立在等频数据采集之上的,并且假设通过等频数据采集而获得的感知数据能够精准地反映物理过程的变化情况。但是,现实中物理过程往往是连续变化的,而等频数据采集仅是对连续变化物理过程的离散化,故等频数据采集存在着关键点丢失和曲线失真等问题。鉴于上述原因,本文开展了传感网中物理过程近似逼近算法的研究。在该研究中,我们首次提出了面向物理可高精度逼近的数据采集问题,并分别基于Hermit插值和三次样条插值技术提出了两种面向物理可高精度逼近的数据采集算法。上述算法可根据真实物理过程的变化情况及用户的误差需求,自适应地调整传感器节点的数据采集频率。其次,我们对上述算法的性能进行了分析与比较,包括算法输出的曲线光滑程度、在计算一阶、二阶导数时的误差、算法的数据采集次数及复杂性等。第三,我们改进了传统意义上的感知数据的概念,在本文中,感知数据不再是离散的数据点,而是多条连续的分段曲线,称之为近似物理过程曲线,该曲线可以更好地表达物理过程连续变化等诸多特性。第四,我们提出了近似物理过程曲线的分布式聚集算法,并对算法精度及其优化策略进行了分析。最后,通过真实与模拟实验验证了本部分提出的算法的性能。

目录

无线传感器网络中分布式近似计算方法的研究

RESEARCH ON DISTRIBUTEDAPPROXIMATE COMPUTATIONALGORITHMS IN WIRELESS SENSORNETWORKS

摘要

Abstract

目 录

Contents

第 1 章 绪论

1.1 研究的目的和意义

1.2 无线传感器网络简介

1.2.1 什么是无线传感器网络

1.2.2 无线传感器网络的特点与挑战

1.2.3 无线传感器网络领域的研究现状与热点问题

1.3 无线传感网中感知数据的获取与计算技术简介

1.3.1 无线传感网中感知数据获取与计算技术的研究现状

1.3.2 无线传感网中感知数据获取与计算技术所面临的新挑战

1.4 本文研究的问题与成果

1.4.1 本文研究的问题

1.4.2 本文主要贡献

1.5 本文的章节安排

第 2 章 静态传感器网络中基于均衡抽样的(,)-近似聚集算法

2.1 引言

2.2 问题定义

2.3 数学基础

2.3.1 聚集和的估计器

2.3.2 平均值的估计器

2.3.3 无重复计数值的估计器

2.4 分布式均衡抽样算法

2.4.1 样本容量的确定

2.4.2 均衡抽样算法

2.5 近似聚集算法

2.6 样本信息维护算法

2.6.1 和变化时样本数据信息维护算法

2.6.2 感知数据变化时样本信息维护算法

2.7 实验结果

2.7.1 基于抽样技术算法的特有性能

2.7.2 查询处理过程中的能量消耗

2.8 相关工作

2.9 本章小节

第 3 章 动态传感器网络中基于Bernoulli抽样的(,)-近似聚集算法

3.1 引言

3.2 预备知识

3.2.1 问题定义

3.2.2 Bernoulli抽样

3.3 数学基础

3.3.1 计数值及聚集和的估计器

3.3.2 平均值估计器

3.4 Bernoulli抽样算法

3.4.1 抽样概率的确定

3.4.2 Bernoulli抽样算法

3.5 基于Bernoulli抽样的(, )-聚集算法

3.5.1 Snapshot查询处理算法

3.5.2 连续查询处理算法

3.5.3 基于多抽样概率的(,)-近似聚集算法

3.6 实验结果

3.6.1 大规模传感网中算法的性能

3.6.2 中等规模传感网中算法的性能

3.7 本章小节

第 4 章 传感器网络中地理位置敏感的近似极值点查询算法

4.1 引言

4.2 问题定义

4.3 贪心算法

4.3.1 集中式贪心算法

4.3.2 分布式贪心算法

4.3.3 算法复杂性

4.4 基于区域划分的分布式算法

4.4.1 基于区域划分的分布式算法

4.4.2 RrDk的计算方法

4.4.3 算法复杂性

4.5 实验结果

4.5.1 “Top-k”与“LAP-(D,k)”的比较

4.5.2 不同算法在计算“LAP-(D,k)”时的性能

4.6 相关工作

4.7 本章小结

第 5 章 传感器网络中物理过程近似逼近算法

5.1 引言

5.2 问题定义

5.3 面向物理过程可高精度逼近的变频数据采集算法

5.3.1 基于Hermit插值的变频数据采集算法

5.3.2 基于三次样条插值的变频数据采集算法

5.4 近似物理过程曲线聚集算法

5.4.1 问题的定义

5.4.2 近似物理过程曲线聚集算法

5.4.3 聚集算法的优化策略

5.5 实验结果

5.5.1 变频数据采集算法的性能

5.5.2 近似物理过程曲线聚集算法的性能

5.6 相关工作

5.7 本章小节

结论

参考文献

攻读博士学位期间发表的论文及其他成果

哈尔滨工业大学学位论文原创性声明及使用授权说明

致谢

个人简历