期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

无线传感器网络中能量高效的Top-k监测算法 被引量：7

Energy Efficient Top-k Monitoring Algorithm in Wireless Sensor Networks
在线阅读 下载PDF
导出
摘要 传感器节点由于电源能量耗尽的原因经常失效或废弃,因此研究无线传感网的高能效查询处理算法具有重要意义.Top-k监测返回k个最大(或最小)的感知值及相应的位置信息,可以帮助用户检测异常事件并定位发生异常事件的位置,对于用户具有重要的实际意义.已有的Top-k查询处理算法致力于返回精确或近似的查询结果,通信能量开销较高.以最小化网内通信开销的期望为优化目标,提出了基于过滤器的Top-k监测算法.首先,提出了过滤器的健壮性并给出了通信开销模型;其次,根据期望的均值内涵和感知数据的时空相关性,给出了过滤器失败概率的计算公式;最后,以最小化通信开销的期望为优化目标,证明了健壮的过滤器的最优阈值,并提出了基于过滤器的Top-k监测算法(filter based Top-k monitoring algorithm,FTM).理论分析和实验结果验证了该算法的正确性以及低能耗性. Due to the battery energy exhausted, sensor node becomes invalid and gets out of use, hence researching on energy efficiency query processing algorithms plays a significant role in the area of sensor networks. The results returned by the Top-k queries provide k largest （or smallest） sensed values and their locations, which are very useful for detecting abnormal events happened in the monitored region. Existing algorithms focus on returning either exact results or approximate results, which brings about higher communication consumption. To overcome the shortcomings of the existing Top-k queries and improve the energy efficiency, filter based Top-k monitoring algorithm is proposed in this paper, which aims at minimizing the expectation of communication overhead. Firstly, the robustness of filters guaranteeing the correctness and high energy efficiency is proposed, and then the communication overhead model is presented. Based on the essence of expectation and sensed data correlation, the probability of filter failure is derived. Finally, minimizing the expectation of communication overhead as an optimization objective, optimal filter threshold is proved and filter based Top-k monitoring algorithm （FTM） is proposed. Real dataset based experiments are carried out to evaluate the efficiency and effectiveness of the proposed algorithm. The theoretical analysis and performance evaluation demonstrate the accuracy and energy efficiency of the proposed algorithm.
作者 毕冉 李建中
机构地区 哈尔滨工业大学计算机科学与技术学院
出处 《计算机研究与发展》 EI CSCD 北大核心 2014年第11期2361-2373,共13页 Journal of Computer Research and Development
基金 国家"九七三"重点基础研究发展计划基金项目(2012CB316200) 国家自然科学基金项目(61190115 61033015 60933001) 国家自然科学基金国际(地区)合作与交流项目(60831160525) 中央高校基本科研业务费专项基金项目(HIT.NSRIF.201180)
关键词 无线传感器网络 最小化通信能量 Top-k监测算法 滤波器 阈值 wireless sensor networks （WSNs） minimizing communication energy Top-k monitoringalgorithm filter threshold
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献27

  • 1Bocca M, Toivola J, Eriksson L M, et al. Structural health monitoring in wireless sensor networks by the embedded goertzel algorithm [C] //Proc of the 2nd Int Conf on Cyber Physical Systems (ICCPS). Alamitos, CA: IEEE Ccrnputer Society, 2011: 206-214.
  • 2Zeinalipour Yazti D, Vagena Z, Gunopulos D, et ai. The threshold join algorithm for top k queries ir distributed sensor networks [C] //Proe of the 2nd Int Workshop on Data Management for Sensor Networks. New York: ACM, 2005: 61-66.
  • 3Chaudhuri S, Gravano L, Marian A. Optimizing top k selection queries over multimedia repositories [J]. IEEE Trans on Knowledge and Data Engineering, 2004, 16 (8) : 992-1009.
  • 4Michel S, Triantafillou P, Weikum G. KI.EE: A framework for distributed top-k query algorithms [C] //Proc of the 31st Int Conf on Very Large Databases. New York: ACM, 2005: 637-648.
  • 5Babcock B, Olston C. Distributed top-k monitoring [C] // Proc of 2003 ACM SIGMOD Int Conf on Management of Data. NewYork: ACM, 2003:28-39.
  • 6Considine J, Li Feifei, Kollios G, et al. Approximate aggregation techniques for sensor databases [C] //Proc of IEEE ICDE 2004. Piscataway, NJ: IEEE, 2004:449-460.
  • 7Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware [J]. Journal of Computer and System Sciences, 2003, 66(4): 614-656.
  • 8Silberstein A S, Braynard R, Ellis C, et al. A sampling- based approach to optimizing top-k queries in sensor networks [C] //Proc of IEEE ICDE 2006. Piscataway, NJ: IEEE, 2006:68-78.
  • 9Liu Yu, Li Jianzhong, Gao Hong, et al. Enabling e-approximate querying in sensor networks [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 169-180.
  • 10Cheng Siyao, Li Jianzhong. Sampling based ( e, 8)- approximate aggregation algorithm in sensor networks [C] // Proc of IEEE ICDCS 2009. Piscataway, NJ: IEEE, 2009: 273-280.

二级参考文献16

  • 1ZEINALIPOUR-YAZTI D, VAGENA Z, GUNOPULOS D, et al. The threshold join algorithm for Top-k queries in distributed sensor networks[A]. ACM International Conference Proceeding Series[C]. 2005.61-66.
  • 2BABOCK B, OLSSTON C. Distributed Top-k monitoring[A]. SIGMOD[C]. 2003.28-39.
  • 3CHAUDHURI S, GRAVANO L, MARIAN A. Optimizing Top-k selection queries over multimedia repositories[J]. IEEE Transactions on Knowledge and Data Engineering, 2004,16(8): 992-1009.
  • 4SEBASTIAN M, PETER T, GERHARD W. KLEE: a framework for distributed Top-k query algorithm[A]. VLDB[C]. 2005.637-648.
  • 5ADAM S, REBECCA B, CARLA S E, et al. A sampling-based approach to optimizing Top-k queries in sensor networks[A]. ICDE[C]. 2006.68-78.
  • 6RONALD E AMNON L, MONI N. Optimal aggregation algorithm for middleware[A]. PODS [C]. 2001. 102-113.
  • 7THEOBALD M, WEIKUM G; SCHENKEL R. Top-k query evaluation with probabilistic guarantees[A]. VLDB[C]. 2004. 648-659.
  • 8ARAI B, DAS G, GUNOPULOS D, et al. Anytime measuers for Top-k algorithms[A]. VLDB[C]. 2007.648-659.
  • 9GUNTAER U, BALKE W T, KIEBLING W. Optimizing multi-feature queries for image databases[A]. VLDB[C]. 2000. 419-428.
  • 10CAO E WANG Z. Efficient Top-k query calculation in distributed netwrks[A]. PODC[C]. 2004. 206-215.

共引文献5

同被引文献52

  • 1崔莉,鞠海玲,苗勇,李天璞,刘巍,赵泽.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):163-174. 被引量：730
  • 2曹冬磊,曹建农,金蓓弘.一种无线传感器网络中事件区域检测的容错算法[J].计算机学报,2007,30(10):1770-1776. 被引量：29
  • 3XING Xiaofei, WANG Guojun, LI Jie. Collaborative target tracking in wireless sensor networks [J].Ad- hoc and Sensor Networks, 2014, 23(8): 117-135.
  • 4YANG Changlin, CHIN Kwanwu. Novel algorithm for complete targets coverage in energy harvesting wireless sensor networks [J].IEEE Communications Letters, 2014, 18(1): 118-121.
  • 5AMMARI H M, DAS S K. Centralized and clustered k-coverage protocols for wireless sensor networks [J]. IEEE Transactions on Computers, 2012, 61(1): 118- 132.
  • 6SEOK J H, LEE J Y, KIM W, et al. A bipopulation- based evolutionary algorithm for solving full area cov- erage problems[J].IEEE Sensors Journal, 2014, 13 (12) :4796-4807.
  • 7YANG Changlin, CHIN K W. Novel algorithms for complete targets coverage in energy harvesting wireless sensor networks [J]. IEEE Communications Letters, 2014, 18(1): 118-121.
  • 8MINI S, UDGATE S, SABAT S. Sensor deployment and scheduling for target coverage problem in wireless sensor networks [J]. IEEE Sensors Journal, 2014, 14 (3) : 636-644.
  • 9CHENG T M, SAVKIN A V. A distributed self- deployment algorithm for the coverage of mobile wire- less sensor networks [J]. IEEE Communications Let- ters, 2009, 13(11): 877-879.
  • 10SUN Zeyu, LI Heng, CHEN Heng, et al. Optimiza- tion coverage of wireless sensor networks based on en- ergy saving[J]. International Journal of Future Gen- eration Communication and Networking, 2014, 7 (4) : 35-48.

引证文献7

二级引证文献84

计算机研究与发展
2014年 第11期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部