无线传感器网络(ε,δ)-近似Top-k查询处理算法

毕冉; 李建中; 程思瑶

您当前的位置：

首页 >

文章列表页 >

无线传感器网络(ε,δ)-近似Top-k查询处理算法

学术论文 | 更新时间：2024-10-14

- 无线传感器网络(ε,δ)-近似Top-k查询处理算法
- (ε,δ)-approximate Top-k query processing algorithm in wireless sensor networks
- 通信学报 2011年32卷第8期页码：45-54
- 作者机构：
  
  哈尔滨工业大学计算机科学与技术学院
- 作者简介：
- 基金信息：
- DOI：
  中图分类号： TN929.5;TP212.9
- 纸质出版日期：2011
- 稿件说明：
移动端阅览
毕冉, 李建中, 程思瑶. 无线传感器网络(ε,δ)-近似Top-k查询处理算法[J]. 通信学报, 2011,32(8):45-54.

BI Ran, LI Jian-zhong, CHENG Si-yao. (ε,δ)-approximate Top-k query processing algorithm in wireless sensor networks[J]. 2011, 32(8): 45-54.
毕冉, 李建中, 程思瑶. 无线传感器网络(ε,δ)-近似Top-k查询处理算法[J]. 通信学报, 2011,32(8):45-54. DOI：

BI Ran, LI Jian-zhong, CHENG Si-yao. (ε,δ)-approximate Top-k query processing algorithm in wireless sensor networks[J]. 2011, 32(8): 45-54. DOI：

摘要

提出一种适合于任意数据分布的基于抽样的(ε

δ)–近似Top-k查询处理算法。其中

ε≥0和0≤δ<1分别是相对误差界和失败概率界。理论分析表明

对于任意ε≥0和0≤δ<1

该算法返回的查询结果的相对误差界大于ε/(1+ε)的概率小于δ。于是

该算法可以达到任意精度。同时

还给出了支持近似Top-k查询的优化的抽样算法

并通过节点上的数据过滤技术来减少通信能量的消耗。理论分析和仿真结果表明

提出的算法能量消耗低并且计算复杂度低。

Abstract

A sampling based approximate Top-k algorithm was proposed that is adaptive for any data distribution.δ≥0 and 0≤δ<1 are respectively relative error bound and failure probability bound.The theoretical analysis demonstrates that for any δ≥0 and 0≤δ<1 the probability that the relative error bound of the results returned by this algorithm is larger than ε/（1+ε） is less than δ.So the proposed algorithm can reach arbitrary precision.Furthermore

an optimal sampling algorithm was proposed that supported the approximate Top-k query

and through the technique of data filtering the en-ergy consumption of communication was reduced.Theoretical analysis and simulation show that the proposed algorithm is efficient and consumes little energy.

关键词

Keywords

references

浏览量

250

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于非合作博弈的无线传感器网络覆盖控制算法

无线传感器网络隐私保护数据聚集技术

无线传感器网络中新的最小暴露路径问题及其求解算法

基于Voronoi图和定位集的故障诊断和修复策略

基于CS的机载分簇型WSN数据采集方法