查询驱动模式下两层传感器网络Top-k查询汇聚算法研究

doi:10.3969/j.issn.0372-2112.2014.10.032

电子学报 ›› 2014, Vol. 42 ›› Issue (10): 2075-2080.DOI: 10.3969/j.issn.0372-2112.2014.10.032

查询驱动模式下两层传感器网络Top-k查询汇聚算法研究

梁俊斌¹, 马行坡², 奎晓燕³

1. 广西大学计算机与电子信息学院, 广西南宁 530004;
2. 信阳师范学院计算机与信息技术学院, 河南信阳 464000;
3. 中南大学信息科学与工程学院, 湖南长沙 410083

收稿日期:2013-10-23 修回日期:2014-05-28 出版日期:2014-10-25
- 通讯作者:
- 奎晓燕
- 作者简介:
- 梁俊斌 男,1979年生于广西南宁,2010年获得中南大学计算机应用技术专业博士学位.目前为广西大学计算机与电子信息学院副教授,研究方向为无线传感器网络. E-mail:liangjb2002@163.com;马行坡 男,1980年生于河南郑州.2013年获得中南大学计算机应用技术专业博士学位.目前为信阳师范学院计算机与信息技术学院讲师,研究方向为无线传感器网络、智能信息系统. E-mail:maxingpo@csu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61103245); 广西自然科学基金 (No.2012GXNSFBA053163)

Research on Data Aggregation Algorithms for Top-k Queries in Query-Driven-Based Two-Tiered Sensor Networks

LIANG Jun-bin¹, MA Xing-po², KUI Xiao-yan³

1. School of Computer and Electronic Information, Guangxi University, Nanning, Guangxi 530004, China;
2. School of Computer and Information Technology, Xinyang Normal University, Xinyang, Henan 464000, China;
3. School of Information Science and Engineering, Central South University, Changsha, Hunan 410083, China

Received:2013-10-23 Revised:2014-05-28 Online:2014-10-25 Published:2014-10-25
- Supported by:
- National Natural Science Foundation of China (No.61103245); Natural Science Foundation of Guangxi Zhuang Autonomous Region, China (No.2012GXNSFBA053163)

摘要/Abstract

摘要：

在两层传感器网络中,查询驱动模式是将查询请求在下层传感器网络层进行分布式处理的一种查询处理模式.在传感器节点产生数据的频率较高而用户发出查询请求的频率较低的情况下,查询驱动模式能够大大减少数据传输量,降低节点的能量消耗.在这种模式下,如何有效支持局部区域性Top-k查询是一个很有挑战性的问题.针对这一问题,本文首先构造了一种新的数据汇聚树(DAT),接着在DAT的基础上提出了一种支持区域性Top-k查询的数据汇聚方案.理论分析和仿真实验表明,与已有算法相比,本文提出的方案更加高效.

关键词: 查询驱动, 数据汇聚, Top-k, 两层无线传感器网络

Abstract:

In two-tiered wireless sensor networks, a query-driven mode means that queries are processed in a distributed way at the sensor network level of the tiered architecture.When the data generating rates of the sensor nodes are high and the query frequencies are low, using query-driven mode can deeply shrink the amount of data flow and decrease the energy consumption of the sensor nodes.Under such mode, how to support region-based Top-k queries efficiently is a challenging problem.To solve this problem, firstly, a novel data aggregation tree named DAT is constructed.Then, a novel data aggregation scheme for region-based Top-k queries is proposed based on DAT.Theory analysis and simulation results show that, compared with existing schemes, our proposed scheme performs much better in efficiency.

Key words: query driven, data aggregation, Top-k, two-tiered sensor networks

中图分类号:

TP301

梁俊斌, 马行坡, 奎晓燕. 查询驱动模式下两层传感器网络Top-k查询汇聚算法研究[J]. 电子学报, 2014, 42(10): 2075-2080.

LIANG Jun-bin, MA Xing-po, KUI Xiao-yan . Research on Data Aggregation Algorithms for Top-k Queries in Query-Driven-Based Two-Tiered Sensor Networks[J]. Acta Electronica Sinica, 2014, 42(10): 2075-2080.

参考文献

[1] R Zhang,J Shi,Y Z Liu,et al.Verifiable fine-grained Top-k queries in tiered sensor network[A].Proc of IEEE INFOCOM[C].San Diego CA:IEEE,2010.1-9.
[2] W F Liang,B C Chen,J X Yu.Top-k query evaluation in sensor networks under query response time constraint[J].Information Sciences,2011,181(4):869-882.
[3] Q H Pan,M L Li,M Y Wu,W Shu.Optimization of accurate Top-k query in sensor networks with cached data[A].Proc of IEEE WCNC[C].Kowloon:IEEE,2007.4233-4238.
[4] F Chen,A Liu.Safe Q:Secure and efficient query processing in sensor networks[A].Proc of IEEE INFOCOM[C].San Diego CA:IEEE,2010.2642-2650.
[5] S Madden,M Franklin,J Hellerstein,W Hong.The design of an acquisitional query processor for sensor networks[A].Proc of SIGMOD[C].New York:ACM,2003.491-502.
[6] Z Ye,AA Abouzeid,J Ai.Optimal policies for distributed data aggregation in wireless sensor networks[A].Proc of IEEE INFOCOM[C].Anchorage,AK:IEEE,2007.1676-1684.
[7] J Gao,L Guibas,N Milosavljevic,J Hershberger.Sparse data aggregation in sensor networks[A].Proc of IPSN[C].New York:ACM,2007.430-439.
[8] W S Jung,K W Lim,Y B Ko,S J Park.A hybrid approach for clustering-based data aggregation in wireless sensor networks[A].Proc of ICDS[C].Cancun:IEEE,2009.112-117.
[9] R J Barton,R Zheng.Order-optimal data aggregation in wireless sensor networks using cooperative time-reversal communication[A].Proc of CISS[C].Princeton,NJ:IEEE,2006.1050-1055.
[10] 梁俊斌,王建新,陈建二.在传感器网络中构造延迟限定的最大化生命周期树[J].电子学报,2010,38 (2):345-351. Liang Jun-bin,Wang Jian-xin,Chen Jian-er.On the construction of a delay-constrained maximum lifetime tree in wireless sensor networks[J].Acta Electronica Sinica,2010,38(2):345-351.(in Chinese)
[11] 奎晓燕,杜华坤,梁俊斌.无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法[J].电子学报,2013,41(8):1521-1528. Kui Xiao-yan,Du Hua-kun,Liang Jun-bin.An energy-balanced connected dominating sets for data gathering in wireless sensor networks[J].Acta Electronica Sinica,2013,41(8):1521-1528.(in Chinese)
[12] L Shan,Jk Wang,W Wei.An energy-efficient data aggregation routing algorithm in wireless sensor networks[J].Information Technology Journal,2012,11(10):1463-1469.
[13] D J Luo,X J Zhu,X B Wu,G H Chen.Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks[A].Proc of IEEE INFOCOM[C].Shanghai:IEEE,2011.1566-1574.
[14] Y Wu,S Fahmy,N B Shroff.On the construction of a maximum lifetime data gathering tree in sensor networks:NP-completeness and approximation algorithm[A].Proc of IEEE INFOCOM[C].Phoenix,AZ:IEEE,2008.1-9.
[15] C L Liu,G H Cao.Distributed monitoring and aggregation in wireless sensor networks[A].Proc of IEEE INFOCOM[C].San Diego CA:IEEE,2010.1-9.
[16] T Kuo,M Tsai.On the construction of data aggregation tree with minimum energy cost in wireless sensor networks:NP-completeness and approximation[A].Proc of IEEE INFOCOM[C].Orlando,FL:IEEE,2012.2591-2595.
[17] M J Wu,J L Xu,X Y Tang.Processing precision-constrained approximate queries in wireless sensor networks[A].Proc of MDM[C].Nara,Japan:IEEE Computer Society,2006.31.
[18] 毕冉,李建中,程思瑶.无线传感器网络(ε,δ)-近似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].Journal on Communications,2011,32(8):45-54.(in Chinese)
[19] M J .Wu,J L Xu,X Y Tang,W C Lee.Top-k monitoring in wireless sensor networks[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(7):962-976.
[20] H T Mai,Y W Lee,K Y Lee,et al.Distributed adaptive Top-k monitoring in wireless sensor networks[J].Journal of Systems and Software,2011,84(2):314-327.
[21] S J Tang,X F Mao,X Y Li.Efficient and fast distributed Top-k query protocol in wireless sensor networks[A].Proc of ICNP[C].Vancouver,BC:IEEE,2011.99-108.
[22] B Malhotra,M A Nascimento,I Nikolaidis.Exact Top-k queries in wireless sensor networks[J].IEEE Transactions on Knowledge and Data Engineering,2011,23(10):1513-1525.
[23] J Cheng,H B Jiang,J C Liu,W Y Liu,C G Wang.On efficient processing of continuous historical Top-k queries in sensor networks[J].IEEE Transactions on Vehicular technology,2011,60(5):2363-2367.
[24] B C Chen,W F Liang,J X Yu.Online time interval Top-k queries in wireless sensor networks[A].Proc of MDM[C].Kansas City,MO,USA:IEEE,2010.177-182.

查询驱动模式下两层传感器网络Top-k查询汇聚算法研究

Research on Data Aggregation Algorithms for Top-k Queries in Query-Driven-Based Two-Tiered Sensor Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	王新军, 闫实, 彭朝晖, 李庆忠. Extractor：支持查询重构的高效数据库关键词检索系统[J]. 电子学报, 2014, 42(2): 209-216.
[2]	徐猛, 崔立真, 李庆忠. 基于扩展图规划的Top-K服务组合方法研究[J]. 电子学报, 2012, 40(7): 1404-1409.
[3]	林亚平;王雷;陈宇;张锦;陈治平;童调生. 传感器网络中一种分布式数据汇聚层次路由算法[J]. 电子学报, 2004, 32(11): 1801-1805.