不确定数据PT‑TopK查询近似处理系统和方法

摘要

本发明公开一种面向水环境监测网络的不确定数据PT‑TopK查询近似处理系统和方法，通过建立x‑tuple规则元组的不确定元组模型，采用簇内和簇间两个阶段数据减枝与查询处理方法，在不影响最终查询结果的准确度情况下，减少数据通信开销，解决面向水环境监测网络系统的不确定数据查询处理问题；减少数据传输量与网络能耗，提高数据查询结果的可信度，降低水环境监测网络系统中数据管理的开发与部署成本。

主权项

一种不确定数据PT‑TopK查询近似处理方法，不确定数据PT‑TopK查询近似处理系统包括监测节点端部分和用户终端部分；用户终端部分包括用户交互接口、网络初始化模块、查询任务启动模块和查询结果返回接口；监测节点端部分包括簇内查询处理模块、簇间查询处理模块和基站节点查询处理模块；(1)监测节点端部分簇内查询处理模块：簇内成员节点接收从查询启动模块传输的查询任务，根据查询参数概率阈值p和排序数k，在其不确定数据表上执行PT‑Topk查询；采用与其簇头节点两次数据交换策略，簇成员节点将本地不确定数据表上可能成为最终查询结果的数据传输给簇头节点，实现簇内数据修剪；簇间查询处理模块：由于不确定元组的存在概率大于等于不确定元组Top‑k概率，对于排序比较低的不确定元组，即使其存在概率很大，最后得出的Top‑k概率也可能会非常低，甚至不满足概率阈值p的要求；因此，簇头节点接收到所有簇内成员节点传输的数据，根据查询参数概率阈值p和排序数k，簇头节点与Sink基站节点通过行两次数据交换，确定其可能成为最终查询结果的数据传输给Sink基站节点，实现簇间减枝；基站节点查询处理模块：基站节点对数据表T_sink中的所有元组按等级顺序定义的降序顺序排序，根据查询任务的概率阈值p和排序数k，在不确定数据表T_sink上执行PT‑Topk查询，并将查询结果数据进行封装，返回给查询结果返回接口；(2)用户终端部分用户交互接口：以图形化界面的方式，接收用户的查询任务和查询参数，并向查询任务和参数转发至查询任务启动模块；网络初始化模块：利用TEEN网络分簇算法构建层次式聚簇网络拓扑结构，将整个网络分成若干个簇，每个簇只有一个簇头节点，并负责与基站节点进行通信，簇头节点保存本簇内所有节点的信息；簇内节点之间可以相互通信，收集感知器感知的数据，保存在本地存储器中；查询任务启动模块：根据水环境监测任务需求，用户发起查询请求，解析查询任务参数，确定查询任务的发布方式，并对查询数据进行封装；查询结果返回接口：接收查询结果数据包，并根据封装格式，进行解包，得到查询结果以图形化的方式展示给用户；其特征在于，方法包括以下步骤：1)建立水环境监测网络的拓扑结构：水环境监测网络采用层次式聚簇网络拓扑结构，利用TEEN网络分簇算法，将整个网络分成若干个簇，每个簇只有一个簇头节点，并负责与基站节点进行通信，簇头节点保存本簇内所有节点的信息；簇内节点之间可以相互通信，收集感知器感知的数据，保存在本地存储器中；2)每个簇内节点建立x‑tuple规则元组的不确定元组模型：x‑tuple规则元组由若干不确定元组构成，每个元组中都存在一个数据项，数据项是节点感知数据，并且每个数据项都有一个存在概率；x‑tuple规则元组中所有数据项存在概率之和小于等于1；3)簇内节点查询处理：簇内节点接收到查询请求，根据概率阈值p和排序数k在其不确定数据表上执行PT‑Topk查询，当满足查询算法终止执行条件时，将最后查询到的不确定元组传输给簇首节点；簇首节点将收集到的所有不确定元组排序，找出排序最高的不确定元组作为硬阈值，并传输给簇内节点；簇内节点收到硬阈值，并将本地不确定数据表上大于此硬阈值的所有不确定元组传输给簇首节点；4)簇间节点查询处理：簇首节点将收集到的所有不确定元组按降序排序，执行PT‑Topk查询处理算法，计算出查询结果；将查询结果分为两类：受到影响查询结果和不受影响查询结果；查询结果排序最低元组的感知数据项作为查询结果下界，相应的可将查询结果下界分为受到影响查询结果下界和不受影响查询结果下界；在基站，分别计算所有受到影响查询结果下界的最小值和不受影响查询结果下界的最大值；然后比较此最小值和最大值，并将其中较大者记为全局下界，并广播全局下界给簇首节点，簇首节点将全局下界作为硬阈值，将感知数据项大于此硬阈值的不确定元组传输基站；5)基站节点查询处理：基站将收集的不确定元组按降序排序，并执行PT‑Topk查询近似算法，得到最终查询结果；采用数据包对查询结果数据进行封装，通过基站节点返回到用户终端。