大规模无线传感器网络(ε,δ)−近似计数算法

doi:10.3969/j.issn.1000-436X.2013.06.021

摘要/Abstract

摘要：

研究了大规模无线传感器网络中的近似计数问题，提出2个基于数字二叉树（DBT,digital binary tree）协议的近似计数算法DBT-ACA和DBT-BACA算法能够以O(log logn)的时间复杂性返回(ε,δ)-精度保证的近似计数结果。DBT-BACA采用了二分搜索、逐层转发和延迟响应等技术，有效地减少了查询时间和数据通信量。理论分析和实验结果表明，提出的算法在近似结果的精准度、时间效率和能量开销等方面均优于现有的近似计数算法。

关键词: 无线传感器网络, 数据聚集, 近似算法, 数字二叉树

Abstract:

The problem of approximate counting for large scale wireless sensor networks was studied.Two approximate counting algorithms,DBT-ACA and DBT-BACA,based on DBT (digital binary tree) protocol were also proposed.The algorithms presented could attain the counting result in O(log logn)time while meeting the(ε,δ)accuracy requirement.DBT-BACA exploits binary search,level-by-level forwarding and delay response technique to effectively reduce the query delay and transmission cost.Theoretical analysis and experimental results show that the proposed algorithms out-perform existing approaches in terms of estimation accuracy,time efficiency and energy cost.

Key words: wireless sensor networks, data aggregation, approximate algorithms, digital binary tree

朱敬华,管学敏. 大规模无线传感器网络(ε,δ)−近似计数算法[J]. 通信学报, 2013, 34(6): 174-183.

Jing-hua ZHU,Xue-min GUAN. (ε,δ)-approximate counting algorithm for large scale wireless sensor networks[J]. Journal on Communications, 2013, 34(6): 174-183.

图/表 13

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

参考文献 18

[1]	XU N . A survey of sensor network applications[J]. IEEE Communications Magazine, 2002,40: 120-135.
[2]	MADDEN S , FRANKLIN M J , HELLERSTEIN J M , et al. TAG: a tiny aggregation service for ad-hoc sensor networks[A]. Proc of the 5th Symp on Operating System Design and Implementation[C]. New York,USA, 2002. 131-146.
[3]	ABHINV K , VISHAL M , DAN R . Count torrent: ubiquitous access to query aggregates in dynamic and mobile sensor networks[A]. Proc of the 5th International Conference on Embedded Networked Sensor Systems (Sensys 07)[C]. New York:ACM Press,USA, 2007. 137-152.
[4]	CONSIDINE J , LI F , KOLLIOS G , et al. Approximate aggregation techniques for sensor databases[A]. Proc of the 20th Int'l Conf on Data Engineering[C]. Washington: IEEE Computer Society Press,USA, 2004. 449-460.
[5]	NATH S , GIBBONS P B , SESHAN S , et al. Synopsis diffusion for robust aggregation in sensor networks[A]. Proc of the ACM Conf on Embedded Networked Sensor Systemsl[C]. New York: ACM Press,USA, 2004. 250-262.
[6]	HARTL G , LI B C . Infer: a bayesian inference approach towards energy efficient data collection in dense sensor networks[A]. Proc of the 25th IEEE Int'l Conf on Distributed Computing Systems[C]. Washington:IEEE Computer Society Press,USA, 2005. 371-380.
[7]	DELIGIANNAKIS A , KOTIDIS Y , ROSSOPOULOS N . Processing approximate aggregation queries in wireless senor networks[J]. Information Systems, 2006,31(8): 770-792.
[8]	DELIGIANNAKIS A , KOTIDIS Y , ROUSSOPOULOS Y N . Hierarchical in-network data aggregation with quality guarantees[A]. Proc of the Int'l Conf on Extending Database Technology[C]. Washington:IEEE Computer Society Press,USA, 2004. 658-675.
[9]	CORMODE G , GAROFALAKIS M N , MUTHUKRISHNAN S , et al. Holistic aggregates in a networked world: distributed tracking of approximate quantiles[A]. Proc of the 2005 ACM SIGMOD Int'l Conf on Management of Data[C]. New York: ACM Press,USA, 2005. 25-36.
[10]	CHU D , DESHPANDE A , HELLERSTEIN J M , et al. Approximate data collection in sensor networks using probabilistic models[A]. Proc of the 22nd Int'l Conf on Data Engineering[C]. Washington: IEEE Computer Society Press,USA, 2006. 48-59.
[11]	SILBERSTEIN A , PUGGIONI G , GELFAND A , et al. Suppression and failures in sensor networks: a Bayesian approach[A]. Proc of the 33rd Int'l Conf on Very Larger Data Base[C]. New York: ACM Press,USA, 2007. 842-853.
[3]	HAAS P J , SWAMI A N . Sequential sampling procedures for query size estimation[A]. Proc of the 1992 ACM SIGMOD Int'l Conf on Manage-ment of Data[C]. New York: ACM Press,USA, 1992. 341-350.
[13]	LARSON P , LEHNER W , ZHOU J R , et al. Cardinality estimation using sample views with quality assurance[A]. Proc of the 2007 ACM SIGMOD Int'l Conf on Management of Data[C]. New York: ACM Press,USA, 2007. 175-186.
[14]	CEMULLA R , LEHNER W , HAAS P J . Maintaining bernoulli sample over evolving multisets[A]. Proc of the 26th ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems[C]. New York:ACM Press,USA, 2007. 93-102.
[15]	BENJAMIN A , GAUTAM D , DIMITRIOS G , et al. Approximating aggregation queries in peer-to-peer networks[A]. Proc of the 22nd Int'l Conf on Data Engineering[C]. Washington: IEEE Computer Society Press,USA, 2006. 642-654.
[16]	BAYER K , HAAS P J , REINWALD B . On synopses for distinct-value estimation under multiset operations[A]. Proc of the 2007 ACM SIG-MOD Int'l Conf on Management of Data[C]. New York,USA, 2007. 199-210.
[17]	CHENG S Y , LI J Z . (ε,δ)-approximate aggregation algorithm in wire-less sensor networks[J]. Journal of Software, 2010,21(8): 1936-1953.
[18]	TIMUR F , DON T . Multicast Session Membership Size Estimation[R]. Technical Report, 1998.

[1]	赵越, 李赞, 李冰, 郝本建. TDoA定位盲区分析与节点部署策略研究[J]. 通信学报, 2023, 44(1): 1-13.
[2]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.
[3]	杜秀娟, 王丽娟, 刘静萍, 金龙. 基于归零神经动力学的水下无线传感器网络节点测距定位方法[J]. 通信学报, 2022, 43(10): 177-185.
[4]	孙爱晶, 李世昌, 张艺才. 基于PSO优化模糊C均值的WSN分簇路由算法[J]. 通信学报, 2021, 42(3): 91-99.
[5]	韩珍珍,赵国锋,徐川,周文涛,周洋洋. 基于时延的LEO卫星网络SDN控制器动态放置方法[J]. 通信学报, 2020, 41(3): 126-135.
[6]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[7]	郝晓辰,姚宁,解力霞,王姣姣,王立元. 联合功率与信道的WSN生命期优化博弈算法[J]. 通信学报, 2019, 40(4): 62-70.
[8]	刘琳岚,高声荣,舒坚. 基于随机森林的链路质量预测[J]. 通信学报, 2019, 40(4): 202-211.
[9]	武小年,张楚芸,张润莲,孙亚平. WSN中基于改进粒子群优化算法的分簇路由协议[J]. 通信学报, 2019, 40(12): 114-123.
[10]	刘浩然,赵赫瑶,邓玉静,王星淇,尹荣荣. 基于非合作博弈的无线传感器网络覆盖控制算法[J]. 通信学报, 2019, 40(1): 71-78.
[11]	乐燕芬,汤卓,盛存宝,施伟斌. 基于多分布密度位置指纹的高效室内定位算法研究[J]. 通信学报, 2019, 40(1): 172-179.
[12]	舒坚,刘满兰,尚亚青,陈宇斌,刘琳岚. 基于高斯过程回归的链路质量预测模型[J]. 通信学报, 2018, 39(7): 148-156.
[13]	郝晓辰,王立元,刘金硕,解力霞,张文焕. WSN中基于双群体差分进化的资源分配优化算法[J]. 通信学报, 2018, 39(4): 68-75.
[14]	蒋婵,李陶深,梁俊斌. 移动低占空比无线传感器网络中低时延的数据持续性提高算法[J]. 通信学报, 2018, 39(3): 53-62.
[15]	王继红,石文孝. 认知无线传感器网络分簇路由协议综述[J]. 通信学报, 2018, 39(11): 156-169.