计算机科学 ›› 2017, Vol. 44 ›› Issue (10): 177-181.doi: 10.11896/j.issn.1002-137X.2017.10.033

• 软件与数据库技术 • 上一篇    下一篇

无线传感器网络中基于聚簇结构的Skyline查询方法

李青,肖迎元,王晓晔,李玉坤   

  1. 天津理工大学计算机与通信工程学院 天津300384天津市智能计算及软件新技术重点实验室 天津300384,天津理工大学计算机与通信工程学院 天津300384天津市智能计算及软件新技术重点实验室 天津300384,天津理工大学计算机与通信工程学院 天津300384天津市智能计算及软件新技术重点实验室 天津300384,天津理工大学计算机与通信工程学院 天津300384天津市智能计算及软件新技术重点实验室 天津300384
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金重大研究计划(91646117),国家自然科学基金(61170174),天津市自然科学基金(17JCYBJC15200),天津市科技特派员项目(16JCTPJC53600)资助

Clustering Architecture-based Skyline Query Processing in Wireless Sensor Networks

LI Qing, XIAO Ying-yuan, WANG Xiao-ye and LI Yu-kun   

  • Online:2018-12-01 Published:2018-12-01

摘要: 现有的基于单服务器的Skyline查询算法已经不能很好地应用于无线传感器网络这类分布式多跳自组织网络中。基于聚簇结构的Skyline查询算法就是针对 这类特定的网络结构而提出的。该算法采用基于聚簇的路由结构,为了减少Skyline查询处理过程中传感器节点的通信开销,挑选具有最大支配力的数据元组作为全局过滤元组来过滤不满足Skyline条件的数据。同时,在Skyline查询处理过程中引入滑动窗口机制,该机制也能有效地降低通信开销。大量的仿真实验结果显示,所提Skyline查询算法在确保能耗的基础上仍然具有很好的性能。

关键词: Skyline查询,聚簇结构,滑动窗口

Abstract: Obviously,the existing Skyline query algorithm based on single server can not be applied to the kind of distributed multi-hop ad hoc networks,such as wireless sensor networks.In this paper,we proposed a clustering based Skyline query method for the specific networks.Clustering architecture-based routing is adopted,which selects the maxi-mum rule power data tuple as global filter to filter the data that do not satisfy the Skyline condition,in order to reduce the communication overhead of sensor nodes in the Skyline query processing.Meanwhile,the sliding window mechanism is introduced into the Skyline query processing,and the mechanism can also effectively reduce the communication overhead.A large number of experimental results show that the proposed Skyline query algorithm has good performance of energy consumption.

Key words: Skyline query processing,Clustering architecture,Sliding window

[1] 颜振亚,郑宝玉.无线传感器网络[M].北京:清华大学出版社,2005.
[2] XIAO Y Y,CHEN Y G.Efficient distributed skyline queries for mobile applications[J].Journal of Computer Science and Technology,2010,5(3):523-536.
[3] WANG H X,ZHENG J P,SONG B L.Skyline Query Processing in Wireless Sensor Networks[J].Journal of Computer Science,2013,40(8):14-23.(in Chinese) 王海翔,郑吉平,宋保利.无线传感器网络中的Skyline查询处理技术[J].计算机科学,2013,40(8):14-23.
[4] HOSE K,VLACHOU A.A survey of skyline processing in high-ly distributed environments[J].Vldb Journal,2012,21(3):359-384.
[5] VLACHOU A,DOULKERIDIS C,KOTIDIS Y,et al.SKYPE-ER:Efficient Subspace Skyline Computation over Distributed Data[C]∥ 2014 IEEE 30th International Conference on Data Engineering.IEEE,2007:416-425.
[6] WU P,ZHANG C,FENG Y,et al.Parallelizing Skyline Queries for Scalable Distribution[C]∥International Conference on Advances in Database Technology-edbt.2006:112-130.
[7] WANG S,VU Q H,OOI B C,et al.Skyframe:A framework for skyline query processing in peer-to-peer systems[J].Vldb Journal,2009,18(1):345-362.
[8] BALKE W T,GNTZER U,ZHENG J X.Efficient Distributed Skylining for Web Information Systems[J].Lecture Notes in Computer Science,2004,2992:256-273.
[9] HUANG Z,JENSEN C S,LU H,et al.Skyline queries against mobile lightweight devices in MANETs[C]∥ International Conference on Data Engineering.2006:66.
[10] CHEN H,ZHOU S,GUAN J.Towards Energy-Efficient Sky-line Monitoring in Wireless Sensor Networks[C]∥ Wireless Sensor Networks,European Conference(Ewsn 2007).Delft,the Netherlands,2007:101-116.
[11] KWON Y,CHOI J H,CHUNG Y D,et al.In-Network Proces-sing for Skyline Queries in Sensor Networks [J].Ieice Transactions on Communications,2007,90(12):3452-3459.
[12] TAO Y,PAPADIAS D.Maintaining sliding window skylines on data streams[J].IEEE Transactions on Knowledge & Data Engineering,2006,18(3):377-391.
[13] XIN J,WANG G,CHEN L,et al.Continuously MaintainingSliding Window Skylines in a Sensor Network[C]∥Internatio-nal Conference on Database Systems for Advanced Applications(DASFAA 2007).Bangkok,Thailand,2007:509-521.
[14] XIN J C,WANG G R.Continuous Skyline Nodes Query Processing over Wireless Sensor Networks[C]∥ NDBL 2012.2012:2415-2430.(in Chinese) 信俊昌,王国仁.无线传感器网络中Skyline节点连续查询算法[C]∥中国数据库学术会议.2012:2415-2430.
[15] LI H,YOO J.An efficient scheme for continuous skyline query processing over dynamic data set[C]∥ International Conference on Big Data and Smart Computing.2014:54-59.
[16] SU I F,CHUNG Y C,LEE C,et al.Efficient skyline query processing in wireless sensor networks[J].Journal of Parallel & Distributed Computing,2010,70(6):680-698.
[17] KARP B,KUNG H T.GPSR:greedy perimeter stateless routing for wireless networks[C]∥International Conference on Mobile Computing and Networking.ACM,2000:243-254.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .