计算机应用 ›› 2014, Vol. 34 ›› Issue (2): 313-317.

• 网络与通信 • 上一篇    下一篇

无线传感器网络不重复记录求和近似算法

刘彩苹1,蔡玉武1,毛建旭2,蔡玉文3   

  1. 1. 湖南大学 信息科学与工程学院,长沙 410082
    2. 湖南大学 电气与信息工程学院,长沙 410082;
    3. 中南民族大学 生物医学工程学院,武汉 430000
  • 收稿日期:2013-07-16 修回日期:2013-09-17 出版日期:2014-02-01 发布日期:2014-03-01
  • 通讯作者: 蔡玉武
  • 作者简介:刘彩苹(1978-),女,湖南邵阳人,讲师,主要研究方向:无线传感器网络、数据挖掘;蔡玉武(1990-),男,湖南娄底人,硕士研究生,主要研究方向:无线传感器网络、数据挖掘;毛建旭(1974-),男,江西安义人,副教授,主要研究方向:无线传感器网络、数字图像处理、模式识别;蔡玉文(1988-),男,湖南娄底人,硕士研究生,主要研究方向:生物医学工程医学传感器。
  • 基金资助:
    国家自然科学基金资助项目;湖南省自然科学基金资助项目;湖南大学青年教师成长计划项目

Approximate summation algorithm of distinct records for wireless sensor network

LIU Caiping1,CAI Yuwu1,MAO Jianxu2,CAI Yuwen3   

  1. 1. School of Information Science and Engineering, Hunan University,Changsha Hunan 410082,China;
    2. College of Electrical and Information Engineering, Hunan University,Changsha Hunan 410082,China;
    3. College of Biomedical Engineering,South-Central University for Nationalities,Wuhan Hubei 430000,China
  • Received:2013-07-16 Revised:2013-09-17 Online:2014-02-01 Published:2014-03-01
  • Contact: CAI Yuwu

摘要: 针对现有的求和算法基本上都是对副本敏感的算法,提出一种对副本不敏感的求和近似算法FM-S。网络中各节点由FM-S和服从二项分布的随机数样本对节点记录进行哈希转换以填充一个长度为L的二进制求和序列,并且每个节点会把生成的序列转发给路由树中的父亲节点,根节点将接收到全网的求和序列,最终根据此序列可计算出网络中不重复记录求和的近似值。实验结果显示该算法是一种分布式、低功耗、容错性高、扩展性和健壮性强的聚集查询算法。

关键词: 无线传感器网络, 分布式算法, 求和查询, 近似算法, 聚集查询

Abstract: Since the existing summation aggregation algorithms are almost duplicate-sensitive, an approximate algorithm Flajolet-Martin SUM (FM-S) of distinct summation query for Wireless Sensor Network (WSN) was proposed. In FM-S, each node in WSN combined the FM-S algorithm and the random number sample of binomial distribution to do hash conversion so as to fill a summation sequence of length L, and each node forwarded the generated sequence to the father node in routing tree. Then the root node received the summation sequence of whole network. Finally, according to the sequence of root node, the approximation summation value of distinct records in sensor networks could be obtained. The experimental results show that the distributed algorithm is of low power consumption, high fault tolerance, robustness and scalability.

Key words: Wireless Sensor Network (WSN), distributed algorithm, summation query, approximate algorithm, aggregate algorithm

中图分类号: