无线传感器网络中的Skyline查询处理技术

摘要/Abstract

摘要： Skyline查询作为多目标决策的重要手段之一,在无线传感器网络应用中发挥着越来越重要的作用。对无线传感器网络中的Skyline查询处理技术进行了论述。首先讨论集中数据库中的Skyline查询算法。其次,讨论无线传感器网络中Skyline查询的典型应用。进而,根据无线传感器网络能量、存储和处理能力有限等特点,全面论述了无线传感器网络中的Skyline查询方法,并指出了今后的研究方向。

关键词: 无线传感器网络,Skyline查询,过滤,能量高效,数据划分

Abstract: As one of the important means of multi-criteria decision making problems,the skyline query processing technology plays an increasingly important role for applications of the wireless sensor networks．This paper summarized the studies of skyline query processing techniques in wireless sensor networks．Firstly,it described algorithms for answering skyline queries in centralized databases．Secondly,it listed typical applications of the skyline queries in the wireless sensor networks．Thirdly,it thoroughly discussed the skyline query methods of the wireless sensor networks according to limited energy and storage as well as processing abilities．Finally,this paper proposed several directions for further research.

Key words: Wireless sensor networks,Skyline queries,Filtering,Energy-efficient,Data partitioning

王海翔,郑吉平,宋保利. 无线传感器网络中的Skyline查询处理技术[J]. 计算机科学, 2013, 40(8): 14-23. https://doi.org/

WANG Hai-xiang,ZHENG Ji-ping and SONG Bao-li. Skyline Query Processing in Wireless Sensor Networks[J]. Computer Science, 2013, 40(8): 14-23. https://doi.org/

参考文献

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al．Wireless sensor networks:a survey[J]．Computer networks,2002,38(4):393-422
[2] Yao Y,Gehrke J E．The Cougar approach to in-network query processing in sensor networks[J]．SIGMOD Record,2002,31(3):9-18
[3] Madden S,Franklin M,Hellerstein J．TinyDB:An acqusitional query processing system for sensor networks[J]．ACM Trans．Database Syst.,2005,30(1):122-173
[4] Abadi Daniel J,Samuel M,Wolfgang L．REED:Robust,Efficient Filtering and Event Detection in Sensor Networks[C]∥Proceedings of the 31^st VLDB Conference．Trondheim,Norway,2005:769-780
[5] Micro S,Klemens B,Erik B．Processing Continuous Join Queries in Sensor Networks:a Filtering Approach[C]∥Proceedings of the ACM Conference on Management of Data．2010:267-278
[6] Yao Yu-xia,Tang Xue-yan,Lim Ee-peng．Continuous Monito-ring of kNN Queries in Wireless Sensor Networks[C]∥Proceedings of International Conference on Mobile Ad-hoc and Sensor Netwoks.2006:663-674
[7] Wu Min-ji,Xu Jian-liang,Tang Xue-yan,et al．Top-k Monitoring in Wireless Sensor Networks[J]．IEEE Transactions on Know-ledge and Data Engineering,2007,19(7):962-975
[8] Baljeet M,Nascimento Mario A,loanis N．Exact Top-K Queries in Wireless Sensor Networks[J]．IEEE Transactions on Know-ledge and Data Engineering,2011,23(10):1513-1525
[9] Adam S,Rebecca B,Carla E,et al．A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks[C]∥Procee-dings of the 22^nd International Conference on Data Engineering(ICDE’06)．2006:68-78
[10] Alexandru C,Nascimento Mario A,Jorg S．A Framework for Spatio-Temporal Query Processing Over Wireless Sensor Networks[C]∥Proceedings of the First Workshop on Data Mana-gement for Sensor Networks(DMSN’04)．Toronto,Canada,2004:104-110
[11] Kwon Y,Choi J-H,Chung Y-D,et al．In-Network Processing for Skyline Queries in Sensor Networks[C]∥Proceedings of the Institute of Electronics,Information and Communication Engineers (IEICE)．2007:3452-3459
[12] Chen He-kang,Zhou Shui-geng,Guan Ji-hong,et al．TowardsEnergy-Efficient Skyline Monitoring in Wireless Sensor Networks[C]∥4th European Conference,EWSN 2007．2007:101-116
[13] Xin J,Wang G,Chen L,et al．Continuously Maintaining Sliding Window Skylines in a Sensor Network[C]∥Proceeding of the 12^th International Conference on Database Systems for Advanced Applications,DASFAA．2007:509-521
[14] Borzsony S,Kossmann D,Stocker K,et al．The Skyline operator[C]∥Proceedings of the 17th International Conference on Data Engineering．2001:421-430
[15] Ooi B C,Eng P-K,Tan K-L,et al．Efficient Progressive Skyline Computation[C]∥Proceedings of the 27th International Confe-rence on Very Large Data Bases．2001:301-310
[16] Jan C,Parke G,Jarek G,et al．Skyline with Presorting[C]∥Proceeding of the 19th International Conference on Data Engineering．2003:717-719
[17] Godfrey P,Shipley R,Gryz J．Maximal Vector Computation inLarge Data Sets[C]∥VLDB．2005:229-240
[18] Kossmann D,Ramsak F,Rost S．Shooting Stars in the sky:An online algorithm for skyline queries[C]∥Proceeding of the 28nd International Conference on Very Large Data Bases．2002:275-286
[19] Papadias D,Tao Y F,Fu G,et al．Progressive skyline computation in database systems[J]．ACM Transactions on Database Systems,2005,30(01):41-82
[20] Papadias D,Tao Y F,Fu G,et al．An Optimal and Progressive Algorithm for Skyline Queries[C]∥Proceeding of SIGMOD．2003:467-478
[21] Lee K C,Zheng B,Lu H,et al．Approaching the Skyline in Z Order[C]∥Proceeding of VLDB．2007:279-290
[22] Lee K C K,Zheng B,Lee W-C,et al．Z-SKY:An Efficient Skyline Query Processing Framework Based on Z-Order[J]．VLDB Journal,2010,19(2):333-362
[23] Surajit C,Nilesh D,Raghav K．Robust Cardinality and Cost Estimation for the Skyline Operator[C]∥Proceedings of the 22nd International Conference on Data Engineering (ICDE’06)．2006:1-10
[24] Zhang Zhen-jie,Yang Yin,Cai Rui-chu,et al．Kernel-based skyline cardinality estimation[C]∥Proceedings of the 2009ACM SIGMOD International Conference on Management of data (SIGMOD)．2009:509-522
[25] Hose K,Vlachou A．A survey of skyline processing in highly distributed environments[J]．The VLDB Journal,2012,21(3):359-384
[26] Wu Ping,Zhang Cai-jie,Feng Ying,et al．Parallelizing skyline queries for scalable distribution[C]∥Proceedings of EDBT．2006:112-130
[27] Chen Li-jiang,Cui Bin,Lu Hua,et al．iSky:Efficient and Progressive Skyline Computing in a Structured P2P Network[C]∥Proceeding of The 28th International Conference on Distributed Computing Systems．2008:160-167
[28] Wang Shi-yuan,Vu Q H,Ooi B C,et al．Skyframe:a framework for skyline query processing in peer-to-peer systems[J]．The VLDB Journal,2009,18:345-362
[29] Tao Yu-fei,Dimitris P．Maintaining Sliding Window Skylines on Data Streams[J]．IEEE Transactions on Knowledge and Data Engineering,2006,18(3):377-391
[30] Wolf-Tilo B,Ulrich G,Xin Z J．Efficient distributed skylining for web information systems[J]．EDBT,Lecture Notes in Computer Science,2004,2:256-273
[31] Pei Jian,Jiang Bin,Lin Xue-min,et al．Probabilistic skylines on uncertain data[C]∥Proceedings of the 33rd international conference on very large data bases (VLDB’07)．2007:15-26
[32] Lian Xiang,Chen Lei．Reverse skyline search in uncertain databases[J]．ACM Transactions on Database Systems,2010,35(1):49
[33] Khalefa Mohamed E,Mokbel Mohamed F,Levandoski Justin J．Skyline Query Processing for Incomplete Data[C]∥Proceedings of the 2008IEEE 24th International Conference on Data Engineering (ICDE’08)．IEEE Computer Society．Washington,DC,USA,2008:556-565
[34] Sharifzadeh M,Shahabi C．The spatial skyline queries[C]∥Proceeding of the international conference on Very large data bases(VLDB’06)．Seoul,Korea,2006:751-762
[35] Deng K,Zhou X,Shen H T．Multi-source skyline query proces-sing in road networks[C]∥Proceedings of the 23th international conference on data engineering．2007:796-805
[36] Huang Zhi-yong,Christian S J,Lu Hua,et al．Skyline Queries Against Mobile Lightweight Devices in MANETs[C]∥Procee-ding of the 22^nd International Conference on Data Engineering (ICDE’06)．2006:720-730
[37] Su I-F,Chung Yu-chi,Lee Chiang,et al．Efficient skyline query processing in wireless sensor networks[J]．Journal of Parallel and Distributed Computing,2010,70(6):680-698
[38] Liang Wei-fa,Chen Bai-chen,Jeffery X Y．Enery-Efficient Skyline Query Processing and Maintenance in Sensor Networks[C]∥Proceedings of the ACM International and Knowledge Mana-gement(CIKM’08)．2008:1471-1472
[39] Chen Bai-chen,Liang Wei-fa．Progressive Skyline Query Pro-cessing in Wireless Sensor Networks[C]∥Proceeding of the Fifth International Conference on Mobile Ad-hoc and Sensor Networks．2009:17-24
[40] Chen Bai-chen,Liang Wei-fa,Jeffrey X Y．Energy-efficient skyline query optimization in wireless sensor networks[J]．Wireless Networks,2012,18(8):985-1004

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed