臺灣博碩士論文加值系統

近年來， skyline 查詢一直受到人們的注意。因為它在多個最佳且有矛盾的條件下，可幫助使用者過濾不必要的資料並挑選感興趣的結果，以讓使用者做進一步的決策判斷。先前已有許多的研究提出集中式環境處理 skyline 查詢的方法，然而這些方法是無法適用在本論文所要探討的感測器網路環境。由於感測器供應的電力有限，所以在 skyline 查詢處理上，需有效率地節省感測器網路的電力消耗，以延長使用的壽命。本篇論文，我們提出 skyline query processing in distributed sensor networks (SKYSENSOR) 來有效率地從分散式的感測器網路環境中取回 skyline。SKYSENSOR 首先設計一個叢集式架構，使用多個叢集來把感測資料依感測值分散存放至不同的叢集中。然後，在處理 skyline 查詢時，提供一個修剪策略來有效率地從感測器網路中篩選出 skyline 結果。因此 SKYSENSOR 可以減少感測器網路的資料傳輸花費與找出結果的計算花費，達到節省電力的目的。在最後，我們用實驗結果來證明我們所提出的方法，在各種資料分佈情況下都有良好的表現。

In recent years, the skyline operator has received considerable attention in the database research community. This is mainly due to the importance of various skyline results in applications involving multi-criteria decision making. On recently, skyline queries are considered in distributed computing environments (e.g., P2P networks, mobile ad hoc networks, and sensor networks). In this paper, we exploit the problem of skyline query processing in sensor networks. Many previous studies investigated efficient approaches to answer skyline queries in a centralized manner. However, those approaches cannot be applied directly to the sensor network environment primarily due to limited power and resource of sensor nodes. We proposed a skyline query processing mechanism, SKYSENSOR, that can efficiently retrieve skyline results from a distributed sensor network. Our solution is based on two main ideas: (1) the clustering architecture and (2) the pruning strategy. The clustering architecture partitions sensor readings into several clusters. By using the clustering architecture, we can identify the sensor that stores skyline points that dominate many data points in the early stage of the query processing. Those skyline points can be used to discard unqualified data points from further examination. The pruning strategy can help to control the amount of query forwarding, limiting the number of sensors involved and the amount of messages transmitted in the network. We conduct a comprehensive data set of experiments to reveal that SKYSENSOR significantly outperforms other existing methods while processing skyline query in a sensor network.

Abstract i
Acknowledgements iii
Table of Contents iv
Table of Figures vii
Table of Tables ix
Table of Algorithms x
1 Introduction 1
2 Related Work 11
2.1 Centralized Environment . . . 11
2.2 Distributed Environment . . . 12
2.2.1 MFT-Applied Aggregation Method Based on Cluster . . . 14
2.2.2 MinMax-Threshold Approach . . . 16
2.2.3 Sliding Window Skyline Monitoring Algorithm . . . 19
3 Network Infrastructure 22
3.1 Assumptions . . . 22
3.2 Clustering Architecture . . . 23
3.2.1 Cluster Location Decision . . . 26
3.2.2 Storage Node Selection . . . 27
3.2.3 Storing Range Division . . . 29
3.3 An Example of Network Infrastructure for 3-dimension . . . 31
4 Data Insertion 34
4.1 Update Summary Table . . . 37
4.2 Sorting . . . 37
5 Query Processing 40
5.1 Setting Threshold . . . 41
5.2 Pruning Strategy . . . 43
5.2.1 Pruning Tuple Phase . . . 43
5.2.2 Pruning Storage Node Phase . . . 45
5.2.3 Adjusting Threshold . . . 47
5.3 Skyline Queries Processing in Distributed Sensor Networks . . . 50
5.4 An Example of SKYSENSOR . . . 52
6 Robustness 57
6.1 Allotment Storing Range . . . 57
6.2 Storage Node Replication . . . 58
7 Performance Evaluation 60
7.1 Experimental Settings . . . 60
7.2 On Synthetic Data Sets . . . 61
7.3 Data Insertion Costs . . . 64
7.4 Query Processing Costs . . . 66
7.5 Total Costs . . . 68
7.6 Percentage of Pruned Tuples . . . 69
7.7 Percentage of Storage Nodes Visited . . . 71
7.8 Storage Load of Sensor Node . . . 73
8 Conclusions and Future Work 75
Bibliography 77
Biography 86

[1] B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker, “Difs: A distributed index for features in sensor networks,” in Proceedings of the first IEEE Sensor Network Protocols and Applications, pp. 163–173, May 2003.
[2] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “Tag: a tiny aggregation service for ad-hoc sensor networks,” Proceedings of ACM Special Interest Group on Operating Systems (SIGOPS) Review, vol. 36, pp. 131–146, December 2002.
[3] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “The design of an acquisitional query processor for sensor networks,” in Proceedings of the 2003 ACM Special Interest Group on Management Of Data (SIGMOD) international conference, pp. 491–502. San Diego, California: ACM Press, June 2003.
[4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Proceedings of Computer Networks, vol. 38, no. 4, pp. 393–422, March 2002.
[5] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler1, and J. Anderson, “Wireless sensor networks for habitat monitoring,” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, pp. 88–97, Atlanta, Georgia, September 2002.
[6] F. Zhao1, J. Shin, and J. Reich, “Information-driven dynamic sensor collaboration for tracking applications,” Proceedings of IEEE Signal Processing Magazine, vol. 19, no. 2, pp. 61–72, March 2002.
[7] I. A. Essa, “Ubiquitous sensing for smart and aware environments: Technologies towards the building of an aware home,” Proceedings of IEEE Personal Communications, vol. 7, no. 5, pp. 47–49, October 2000.
[8] Y.-C. Chung, I.-F. Su, and C. Lee, “Supporting multi-dimensional range query for sensor networks,” in Proceedings of the 27th International Conference on Distributed Computing Systems (ICDCS), p. 35. Washington, DC, USA: IEEE Computer Society, 2007.
[9] X. Li, Y. J. Kim, R. Govindan, and W. Hong, “Multi-dimensional range queries in sensor networks,” in Proceedings of the 1st international conference on Embedded networked sensor systems, pp. 63–75. Los Angeles, California: ACM Press, 2003.
[10] J. Y. Lee, Y. H. Lim, Y. D. Chung, and M. H. Kim, “Data storage in sensor networks for multi-dimensional range queries,” in Proceedings of the Second International Conference on Embedded Software and Systems, pp. 420–429, November 2005.
[11] A. Silberstein, R. Braynard, C. Ellis, K. Munagala, and J. Yang, “A sampling-based approach to optimizing top-k queries in sensor networks,” in Proceedings of the 22nd International Conference on Data Engineering (ICDE), p. 68. Atlanta, Georgia: IEEE Computer Society, April 2006.
[12] B. Patt-Shamir and A. Shafrir, “Approximate top-k queries in sensor networks,” in Proceedings of the Colloquia on Structural Information and Communication Complexity (SIROCCO), pp. 319–333, 2006.
[13] M. Wu, J. Xu, X. Tang, and W.-C. Lee, “Monitoring top-k query in wireless sensor networks,” in Proceedings of the 22nd International Conference on Data Engineering (ICDE), p. 143, 2006.
[14] D. Zeinalipour-Yazti and Z. Vagena, “Distributed top-k query processing in wireless sensor networks,” in Proceedings of the Ninth International Conference on Mobile Data Management (MDM 2008), p. 227, 2008.
[15] K. C. K. Lee, W.-C. Lee, B. Zheng, and J. Winter, “Processing multiple aggregation queries in geo-sensor networks,” in Proceedings of the 11th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 20–34, 2006.
[16] N. Trigoni, A. Guitton, and A. Skordylis, “Routing and processing multiple aggregate queries in sensor networks,” in Proceedings of Fourth ACM Conference on Embedded Networked Sensor Systems (SenSys 2006), pp. 391–392, 2006.
[17] Z. Tu and W. Liang, “Energy-efficient aggregate query evaluation in sensor networks,” in Proceedings of International Conference on Mobile Ad-hoc and Sensor Networks (MSN), pp. 31–41, 2005.
[18] H.-Y. Yang, W.-C. Peng, and C.-H. Lo, “Optimizing multiple in-network aggregate queries in wireless sensor networks,” in Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 870–875, 2007.
[19] H. Chen1, S. Zhou1, and J. Guan, “Towards energy-efficient skyline monitoring in wireless sensor networks,” in Proceedings of the 4th European conference on Wireless Sensor Networks (EWSN 2007), pp. 101–116, Delft, The Netherlands, January 2007.
[20] Y. Kwon, J.-H. Choi, Y. D. Chung, and S. Lee, “In-network processing for skyline queries in sensor networks,” Proceedings of the Institute of Electronics, Information and Communication Engineers (IEICE) Transactions, vol. 90-B, no. 12, pp. 3452–3459, 2007.
[21] J. Xin, G. Wang, L. Chen, X. Zhang, and Z. Wang, “Continuously maintaining sliding window skylines in a sensor network,” in Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA), pp. 509–521, 2007.
[22] J. Xin, G.Wang, and X. Zhang, “Energy-efficient skyline queries over sensor network using mapped skyline filters,” in Proceedings of Asia-Pacific Web Conference and International Conference on Web-Age Information Management (APWeb/WAIM), pp. 144–156, 2007.
[23] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator,” in Proceedings of the 17th International Conference on Data Engineering, 2001.
[24] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with pre-sorting,” in Proceedings of the 19th International Conference on Data Engineering (ICDE), pp. 717–719, Bangalore, India, March 2003.
[25] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: An online algorithm for skyline queries,” in Proceedings of 28th International Conference on Very Large Data Bases, pp. 275–286, Hong Kong, China, August 2002.
[26] K. C. K. Lee, B. Zheng, H. Li, andW.-C. Lee, “Approaching the skyline in z order,” in Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB), pp. 279–290, September 2007.
[27] K.-L. Tan, P.-K. Eng, and B. C. Ooi, “Efficient progressive skyline computation,” in Proceedings of the 27th International Conference on Very Large Databases (VLDB), pp. 301–310, Roma, Italy, September 2001.
[28] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries,” in Proceedings of the 2003 ACM Special Interest Group on Management Of Data (SIGMOD) international conference, pp. 467–478. San Diego, California: ACM Press, 2003.
[29] Davis, “Ornamental horticulture in california,” Proceedings of GROWING Points, vol. 3, no. 1, p. 1V8, 1999.
[30] S.-O. Chung, H.-J. Lee, and J.-K. Park, “Precision agriculture in the republic of korea,” in Proceedings of Site Specific Management Center Newsletter, May 2005.
[31] Z. Liu, K. C. Sia, and J. Cho, “Cost-efficient processing of min/max queries over distributed sensors with uncertainty,” in Proceedings of the 20th Annual ACM Symposium on Applied Computing (SAC), pp. 634–641, 2005.
[32] I. Bartolini, P. Ciaccia, and M. Patella, “Salsa: Computing the skyline without scanning the whole sky,” in Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management (CIKM), pp. 405–414, 2006.
[33] Y. Guo, P. Corke, G. Poulton, T. Wark, G. Bishop-Hurley, and D. Swain, “Animal behaviour understanding using wireless sensor networks,” in Proceedings 2006 31st IEEE Conference on Local Computer Networks, pp. 607–614, November 2006.
[34] E. S. Nadimi, H. T. Sogaard, T. Bak, F. W., and Oudshoorn, “Zigbee-based wireless sensor networks for monitoring animal presence and pasture time in a strip of new grass,” Proceedings of Computers and Electronics in Agriculture, vol. 61, no. 2, pp. 79–87, May 2008.
[35] M. KARABULUT, “An examination of relationships between vegetation and rainfall using maximum value composite avhrr-ndvi data,” in Proceedings of Turkish Journal of Botany, pp. 93–101, 2003.
[36] M. Arattano and L. Marchi, “Systems and sensors for debris-flow monitoring and warning,” in Proceedings of Sensors, pp. 2436–2452, 2008.
[37] W.-T. Balke, U. Guntzer, and J. X. Zheng, “Efficient distributed skylining for web information systems,” in Proceedings of the 9th International Conference on Extending Database. Technology (EDBT 2004), pp. 256–273, Heraklio, Greece, March 2004.
[38] Z. Huang, C. S. Jensen, H. Lu, and B. C. Ooi, “Skyline queries against mobile lightweight devices in manets,” in Proceedings of the 22nd International Conference on Data Engineering (ICDE), p. 66. IEEE Computer Society, 2006.
[39] H. Li, Q. Tan, and W.-C. Lee, “Efficient progressive processing of skyline queries in peer-to-peer systems,” in Proceedings of the 1st International Conference on Scalable Information Systems (INFOSCALE). Hong Kong: ACM Press, May 2006.
[40] A. Vlachou1, C. Doulkeridis1, Y. Kotidis, and M. Vazirgiannis1, “Skypeer: Efficient subspace skyline computation over distributed data,” in Proceedings of the 23rd IEEE International Conference on Data Engineering (ICDE), pp. 416–425, Istanbul, Turkey, April 2007.
[41] S. Wang1, B. C. Ooi, A. K. H. Tung, and L. Xu, “Efficient skyline query processing on peer-to-peer networks,” in Proceedings of the 23rd IEEE International Conference on Data Engineering (ICDE), pp. 1126–1135, Istanbul, Turkey, April 2007.
[42] P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi, “Parallelizing skyline queries for scalable distribution,” in Proceedings of the 10th International Conference on Extending Database Technology (EDBT), pp. 112–130, 2006.
[43] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion: A scalable and robust communication paradigm for sensor networks,” in Proceedings of the Annual International Conference on Mobile Computing and Networking (MOBICOM), pp. 56–67, 2000.
[44] S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker, “Ght: A geographic hash table for datacentric storage,” in Proceedings of the First ACM International Workshop on Wire-
less Sensor Networks and Applications (WSNA)), pp. 78–87. ACM Press, 2002.
[45] G. R. Hjaltason and H. Samet, “Distance browsing in spatial databases,” Proceedings of ACM Transactions on Database Systems, vol. 24, no. 2, pp. 265–318, 1999.
[46] Y. Yao and J. Gehrke, “The cougar approach to in-network query processing in sensor networks,” Proceedings of ACM Special Interest Group on Management Of Data (SIGMOD) Record, vol. 31, no. 3, pp. 9–18, 2002.
[47] S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and D. Estrin, “Data-centric storage in sensornets,” Proceedings of ACM Special Interest Group on Data Communication (SIGCOMM) Computer Communication Review, vol. 33, no. 1, pp. 137–142, January 2003.
[48] A. Ghose, J. Grossklags, and J. Chuang, “Resilient data-centric storage in wireless ad-hoc sensor networks,” in Proceedings of the 4th International Conference on Mobile Data Management (MDM’03), pp. 45–62. Springer-Verlag, 2003.
[49] N. Bulusu, J. Heidemann, and D. Estrin, “Gps-less low cost outdoor localization for very small devices,” in Proceedings of IEEE Personal Communications Magazine, pp. 28–34, June 2000.
[50] B. Karp and H. T. Kung, “Gpsr: Greedy perimeter stateless routing for wireless networks,” in Proceedings of the 6th Annual ACM/IEEE Internatiional Conference on Mobile Computing and Networks (MOBICOM), pp. 243–254, Boston, Massachusetts, August 2000.
[51] S. Chaudhuri, N. Dalvi, and R. Kaushik, “Robust cardinality and cost estimation for skyline operator,” in Proceedings of the 22nd International Conference on Data Engineering (ICDE), p. 64, 2006.
[52] B. Silverman, “Density estimation for statistics and data analysis,” in Proceedings of Chemical Rubber Company (CRC) Press, 1986.
[53] Y. Yuan, X. Lin, Q. Liu, W. Wang, J. X. Yu, and Q. Zhang, “Efficient computation of the skyline cube,” in Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), pp.241–252, 2005.
[54] W. Zhang, G. Cao, and T. F. L. Porta, “Data dissemination with ring-based index for wireless sensor networks,” in Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP), pp. 305–314, 2003.
[55] L. P. Cox, M. Castro, and A. I. T. Rowstron, “Pos: A practical order statistics service forwireless sensor networks,” in Proceedings of the 26th International Conference on Distributed Computing Systems (ICDCS), p. 52, July 2006.
[56] G. J. Pottie andW. J. Kaiser., “Wireless integrated network sensors,” Proceedings of Communications of the ACM, vol. 43, no. 5, pp. 51–58, May 2000.