无线传感器网络技术书-无线传感器及元器件：网络、设计与应用

无线传感器网络极大地扩展了人类对物理世界的感知，并在许多方面得到了广泛应用，因此引起了学术界的广泛关注。 无线传感器网络的数据采集和查询处理是它们提供的基础和重要服务。 然而，无线传感器网络能量受限、自组织、可靠性差等特点，导致其在支持数据采集和查询处理方面存在诸多困难。 首先，节点供电能量有限成为阻碍无线传感器网络应用的严重问题。 在大型网络中，通常存在远距离的数据传输和庞大的数据流量。 这两个因素极大地加剧了很多应用中部分节点的能耗率，从而严重影响了网络的生命周期。 因此，如何延长数据采集和查询处理过程中的网络生命周期成为首要挑战。 其次，用户感兴趣的检测目标不同于传感器节点的感知对象，可能对隐藏在原始数据中的有用信息和知识感兴趣。 在这种情况下，不需要将所有原始数据上传到汇聚节点的网内处理成为节省能源消耗的重要途径。 然而，由于节点的计算和存储能力有限，如何在资源受限的情况下使网络能够支持新的查询成为第二个挑战。 最后，由于WSN具有很强的动态特性，其数据传输路由及其支持的应用的可靠性与其他无线网络相比较低。 如何保证查询处理和数据传输的顺利进行成为第三个挑战。 针对以上三个挑战，本文考虑了与数据采集和查询处理相关的优化问题，提出了相应的优化策略和算法，并从理论和实验的角度分析和验证了所提策略和算法的有效性。 本文取得如下研究成果。

首先，针对网络中的数据收集和多对多数据聚合两种应用，提出了最大化网络生命周期的优化策略。 (1) 首次研究了数据采集传感器网络的生命周期最大化问题，生命周期定义为第一个节点能量耗尽之前数据采集的轮数。 证明问题是NP完全的，并提出近似优化算法。 提出了一种改进的策略来减少整数规划的巨大计算开销和存储空间。 最后通过大量实验验证了算法的有效性。 (2) 我们研究了如何获得节能聚合策略来优化传感器网络中的多对多聚合。 即在网络中，多个节点提供自己的数据无线传感器网络技术书无线传感器网络技术书，同时多个节点需要某一部分数据的聚合值。 当同时考虑路由和聚合选择时，证明问题是NP完全的。 在提出的三种逼近算法中，两种算法针对特殊情况，一种算法针对问题的一般情况。 核心思想是对Steiner树问题使用近似算法。 所有算法都被证明具有常数或多项式逼近比。

其次，针对无线传感器网络中的两种新查询，极值区域查询和概率Skyline查询，分别提出了查询处理和优化算法。 (1) 研究了一种更一般的极值查询——极值区域查询，即给定一个查询半径R，极值区域查询将返回所有圆盘形区域值的最大值/最小值半径为 R ，其中盘子的值定义为该区域内所有传感器读数的某种聚合。 针对此类查询，提出了分布式算法EXQ，不仅有效降低了查询处理过程中的能耗，而且使得各个传感器的能耗更加均衡，从而延长了网络的寿命。 从理论上和实验上比较了EXQ和集中式算法的能量开销和能量消耗分布。 (2)研究如何以最大概率计算出天际线，称为Pr-Skyline问题。 为此，首先给出了Pr-Skyline问题的定义，并证明了它是NP完全的和多项式时间不可近似的。 尽管如此，所提出的SKY-SEARCH算法结合多种剪枝策略仍然可以保证大数据量下的高平均计算效率，并且基于过滤器的分布式优化策略显着减少了查询过程。 节点所需的传输开销和存储空间。 大量实验验证了SKY-SEARCH算法和分布式优化策略的执行效率和可扩展性。

最后针对低任务周期模式下查询处理和多查询调度中的关键节点（切点）的寻找提出了相关算法和优化策略。 (1) 提出了一种高效的分布式切点检测算法CVD，该算法同时遍历拓扑图上的每个节点，并基于区间编码对生成树上的边进行着色。 这种并发模式极大地降低了查询处理过程中的时间延迟，并提出了优化策略以进一步降低能量开销和时间延迟。 证明了CVD的正确性，并从理论和实验的角度分析了CVD的性能。 仿真实验和真实实验均表明，与其他算法相比，CVD算法具有更低的能耗、更短的时延和更好的可靠性。 (2) 为了缓解低占空比模式下的网络传输拥塞，减少数据丢失，需要对每次查询进行调度，在时间和空间两个维度上平衡各节点的传输负载。 这部分工作从而定义了负载均衡（LB）问题，并证明了它在无限网络拓扑的情况下是NP完全的。 提出了两种时间调度算法并分析了它们的性能。 然后提出了一种基于该算法的查询调度协议。 仿真结果表明，该算法在大多数情况下显着提高了网络性能。 展开▼