无线传感器网络中基于预测的分位数过滤器用于Top-k查询处理

# 无线传感器网络中基于预测的分位数过滤器用于Top-k查询处理 ## 1 引言 随着对物理世界认知的提升以及电子和无线通信等技术的飞速发展，无线传感器网络已广泛应用于军事、医疗、环境监测等众多领域。其光明的前景吸引了众多学者的关注。在无线传感器网络中，传感器节点由电池供电，能量有限。而且，各类传感器会产生大量密集的数据。然而，用户通常只对其中最大或最小的 k 个对象感兴趣。因此，Top-k 查询处理在许多应用中至关重要。 Top-k 查询是一种聚合查询技术，在不确定数据库和关系数据库中已较为成熟。但在无线传感器网络中，它与 SUM、AVG 等一般查询不同。传感器节点无法确定其数据是否会包含在最终结果中，这需要基站收集所有传感器节点的数据后才能决定。这种集中式查询处理方式会产生大量通信成本，浪费大量能量。所以，如何以节能的方式处理 Top-k 查询是无线传感器网络中的一个重要课题，其目标是在最小化能耗的同时为用户提供 Top-k 结果。 目前，基于过滤器的监测方法是处理无线传感器网络中 Top-k 查询的主流。QF（分位数过滤器，QF）是现有算法中一种节能的方法，它基于传感器值的分位数。其基本思想是从所有子节点中选择一个分位数作为阈值，并将该阈值安装在子传感器节点上。然后，每个子节点将大于该分位数的数据发送给父节点，避免了冗余数据的传输。然而，QF 中阈值的获取依赖于子节点和父节点之间的交互，会消耗更多不必要的通信能量。 为了解决这个问题，我们提出了一种名为 QFBP（基于预测值的分位数过滤器，QFBP）的新型 Top-k 监测方法，它通过时间序列模型进行预测来获取阈值。我们采用 ARIMA（自回归积分滑动平均模型）时间序列模型进行预测，因为它方便且更适合传感器数据。该算法通过预测阈值降低了通信和传输的能耗。我们通过大量实验将其与 QF 算法进行了比较，实验结果表明，QFBP 在节能和正确性方面都优于现有的 QF 算法。 ## 2 相关工作 ### 2.1 集中式方法 一种简单的监测 Top-k 查询的实现方式是集中式方法，即基站定期收集所有传感器节点的读数后计算 Top-k 结果集。然而，无线传感器网络是一个分布式网络，由大量能量有限的传感器节点组成，通信成本是主要的能耗来源。大量传感数据的传输以及这些传感器节点之间的交互会消耗额外的能量。 ### 2.2 现有算法 - **TAG 算法**：为了降低数据收集期间的通信成本，Madden 等人引入了一种名为 TAG（Tiny 聚合，TAG）的网络内聚合技术。在 TAG 算法中，数据由节点从低级向高级传输。如果点集的长度小于 k，节点将所有点转发给父节点；否则，转发 k 个值最高的点。最后，基站根据从所有传感器节点收集的这些点计算最终结果。该算法避免了无效数据的传输，但仍然会产生不必要的能耗，并非真正的节能算法。 - **FILA 算法**：Wu 等人提出了基于过滤的监测方法 FILA（基于过滤器的监测方法，FILA）。其基本思想是在每个传感器节点上安装一个过滤器，过滤掉对最终结果没有贡献的不必要数据。重新评估和过滤器设置是确保算法正确性和有效性的两个关键方面。但是，当节点上的传感值变化较大时，基站需要频繁更新相关节点的过滤器，这会导致大量的更新成本，使算法性能变差。 - **DAFM 算法**：基于 FILA，Mai 等人提出了 DAFM（分布式自适应过滤监测，DAFM）算法，旨在降低重新评估过程中发送探测消息的通信成本，并降低 FILA 中更新过滤器时的传输成本。 - **QF 算法**：Chen 等人提出的分位数过滤器将传感值及其传感器视为一个点。Top-k 查询是返回 k 个传感值最高的点。其基本思想是基于一个阈值过滤掉冗余数据，该阈值是所有子节点点集的一个值。但子节点和父节点之间的频繁交互会在获取阈值时产生更多的能量消耗。 - **XP 聚合框架**：Liu 等人开发了一种新的交叉剪枝（XP）聚合框架，用于无线传感器网络中的 Top-k 查询。该框架中有一个簇树路由结构，用于在本地聚合更多对象，并采用广播 - 过滤方法。此外，它还提供了一种网络内聚合技术，用于过滤掉冗余值，增强了网络内过滤的有效性。 - **POT 算法**：Cho 等人提出的 POT 算法（部分有序树，POT）考虑了空间相关性，以维护 k 个传感值最高的传感器节点。 - **MOTE 方法**：Abbasi 等人提出的 MOTE（基于模型的优化技术，MOTE）方法基于模型优化为节点分配过滤器。然而，为 Top-k 集获取最优过滤器设置是一个 NP 难问题。 近年来，一些研究人员将时间序列模型引入无线传感器网络。例如，Tulone 等人和 Liu 等人将时间序列预测模型应用于无线传感器网络的数据收集。其基本思想是在基站和每个节点上构建相同的模型。基站预测节点的值，直到产生异常读数，节点才将传感读数发送给基站。当读数不能被模型正确预测时，重新学习模型以适应变化。主要区别在于，前者基于 AR（自回归模型），而后者采用 ARIMA 模型。虽然时间序列已应用于无线传感器网络，但它们仅用于最小化数据收集的能耗，尚未应用于 Top-k 查询处理。在本文中，我们基于分位数过滤方法，提出了一种新的 Top-k 监测算法 QFBP，结合时间序列预测模型，尤其是 ARIMA 模型，以降低获取阈值时的通信成本，有效减少能耗。 ## 3 Top-k 和基于分位数过滤器的算法 ### 3.1 预备知识 无线传感器网络的系统架构由许多传感器节点组成。网络中的每个节点通过与其他节点协作将传感值传输到基站。基站能量充足，而传感器节点由电池供电，能量有限。当基站超出传感器节点的无线电覆盖范围时，数据通过其他节点进行多跳传输到基站；否则，数据直接发送到基站。我们将数据传输路径视为一个路由树。 在无线传感器网络中，我们将节点的 ID 和其传感值视为一个点。假设 P(vi) 是传感器 vi 产生的点集，那么 P = ∪_N_{i = 1}P(vi) 是整个传感器网络的点集。Top-k 查询是返回 P 中产生读数最高的 k（1 ≤ k ≤ N）个点。如果结果长度大于 k，则根据传感属性选择其中 k 个作为结果。 ### 3.2 QF 概述 #### 3.2.1 QF 算法 QF 算法主要有三个阶段： 1. 每个传感器节点按传感值降序排列其点后，将其分位数过滤值发送给父节点。 2. 父节点从接收到的分位数中选择一个作为过滤器，即阈值 Qfilter，然后将该过滤器广播给所有子节点。 3. 子节点将值不小于 Qfilter 的点发送给父节点。 下面说明阈值 Qfilte