簡易檢索 / 詳目顯示

回結果列表
研究生： 謝明樺
Hsieh, Ming-Hua
論文名稱： 感測網路中運用資料探勘技術之節能追蹤方法之研究
A Study on Energy-Efficient Tracking Schemes Using Data Mining Techniques in Sensor Networks
指導教授： 曾新穆
Tseng, Vincent
共同指導教授: 林威成
Lin, Kawuu
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2011
畢業學年度： 100
語文別： 英文
論文頁數： 131
中文關鍵詞： 感測網路 、物體追蹤 、排程監控 、資料探勘 、移動樣式 、節能策略 、追蹤規劃
外文關鍵詞： sensor networks, object tracking, schedule monitoring, data mining, movement pattern, energy-efficient strategy, tracking scheme
相關次數： 點閱：121  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近年來，感測網路隨著無線通訊以及嵌入式技術的快速發展，已經衍生出許多有趣的應用。在眾多的感測網路應用中，於感測網路下進行物體追蹤，則引起了廣泛的關注。由於感測節點的電量有所限制，因此，如何使感測網路的物體追蹤盡可能節省能量，已經成為一個值得研究的議題。本研究發展多種節能策略，在不同網路情境下，應用於感測網路的物體追蹤。經由蒐集的物體移動紀錄，找出相關的移動樣式以及行為樣式，並且利用這些樣式設計出一系列的節能追蹤規劃。
    針對感測網路物體追蹤，利用預測物體的未來移動以達到節能的規劃，主要適用於當感測網路中移動物體個數少的情境下。本研究目的之一，就是提出一個不需要定義時序切割單位的無縫式時序移動樣式。透過整合發現的無縫式時序移動樣式以及速度樣式，我們也建構一個創新的綜合預測型追蹤規劃。經由各種不同的參數實驗評估，我們提出的綜合預測型追蹤規劃比以往的預測型追蹤方法更為節能以及達到較低的遺失比率。
    當感測網路中移動物體數量龐大的時候，由於喚醒感測節點的通訊費用增加，因此預測型追蹤規劃的總耗能也會呈倍數成長。針對感測網路龐大的工作量，偵測型追蹤規劃採用排程監控方式，以節省大量的通訊成本。本研究第二個目的，就是設計一套自動化感測節點排程規劃。我們也提出一個感測節點連續拜訪區間的概念，在此連續拜訪區間，可以經由探勘每個感測節點的拜訪時間資訊得到。利用找出來的連續拜訪區間去設計適合的排程監控。模擬測試資料集評估的結果，也證實我們提出的自動化感測節點排程監控，可以比以往的偵測型追蹤規劃節省較多能量;而且其遺失比率也遠低於預測型的追蹤規劃。
    對於大工作量的感測網路，於本研究提出的自動化感測節點排程監控雖然可以比既有的追蹤規劃節省更多能量。然而，在大規模的感測網路情境下，自動化感測節點排程監控的總耗能，還是高於預測型的追蹤規劃。上述的情況，促使我們融合自動化感測節點排程監控以及預測型追蹤規劃兩者的優點，去設計一個互助型追蹤規劃，使得不管於各種網路情境底下，皆能做到能量保存以及低遺失比率。首先，我們提出了感應效益時段的概念去設計具有能量高效率的排程監控。此外，區域移動樣式以及種子式散播復歸模式也被提出用以建構二階段式復歸機制。我們將既有的物體追蹤規劃，以及我們提出的三種追蹤規劃，在模擬測試資料集以及真實的行動資料集進行總耗能以及遺失比率的量測。結果也顯示出本研究所提出的三種應用於感測網路下物體的追蹤規劃，都可以於其適合的網路情境下，展現出優於其他方法的效益。

    In recent years, the rapid growth of wireless communication and embedded micro-sensing technologies facilitates a lot of interesting applications of sensor networks. Among the numerous applications of sensor networks, object tracking in sensor networks (OTSNs) has attracted the extensive attention. Due to the limited power of sensor nodes, conserving as much energy as possible for OTSNs has thereby become an issue worth exploring. The goal of this study is to develop various energy-efficient strategies for OTSNs under different network scenarios. A series of tracking schemes with energy-efficient property were designed by utilizing the discovered movement patterns and behavior patterns mined from the collection of the movement logs of objects.
    The tracking schemes based on the prediction of future movements of objects for OTSNs are mainly applied to the sensor networks, where the number of moving object is few. One of the goals in this study is to propose a seamless temporal movement pattern without giving the interval unit. We also integrate the velocity-based movement patterns with the discovered seamless temporal movement patterns to construct a novel Hybrid Prediction-based Tracking Scheme (HPTS). Through the evaluations under various parameters, the experimental results show that the proposed HPTS can save more energy and achieve a lower missing rate than the previous prediction-based tracking approaches.
    As the number of moving objects in sensor networks is huge, the total energy consumption of the prediction-based schemes suffers from multiple growths with the increase in the communication cost for awaking sensor nodes. For the huge workload of sensor networks, the detection-based tracking schemes adopt the schedule monitoring for saving a great amount of communication cost. The second goal in this study is to design an Autonomous Node Schedule Scheme (ANSS). We also propose a concept of continuously-visited period of sensor node, which can be mined from the visited temporal information of each sensor node. The discovered continuously-visited periods are utilized to design the adaptive schedule monitoring. The evaluations of the simulated datasets have also proven that our proposed ANSS can save more energy than the previous detection-based tracking schemes and achieve a much lower missing rate than the prediction-based tracking schemes.
    As to the heavy workload of sensor networks, the proposed ANSS in this study can save more energy than the existing tracking schemes. However, the total energy consumption of the ANSS is higher than the prediction-based tracking schemes in the large size of sensor networks. The above situations motivate us to fuse the advantages of the ANSS and HPTS to design a Cooperative Tracking Scheme (CTS) for the energy conservation and a low missing rate under various network scenarios. First, we propose a concept of sensing-beneficial period to design an energy-efficient schedule monitoring scheme. Furthermore, the region-based movement patterns and seeding-based flooding are also proposed to construct a Two-Stage Recovery Mechanism. We compare our proposed three tracking schemes with the existing ones to investigate the total energy consumption and missing rate over the simulated and real datasets. The experimental results show that our proposed three tracking schemes for OTSNs can deliver a better performance than other approaches in their appropriate network scenario.

    中文摘要 III ABSTRACT V 誌謝 VIII Content IX List of Tables XII List of Figures XIII Chapter 1 Introduction 1 1.1 Motivation 3 1.2 Overview of the Dissertation 6 1.2.1 Framework of Hybrid Prediction-based Tracking Scheme (HPTS) 8 1.2.2 Framework of Autonomous Node Scheduling Scheme (ANSS) 9 1.2.3 Framework of Cooperative Tracking Scheme (CTS) 10 1.3 Organization of the Dissertation 10 Chapter 2 Background and Related Work 12 2.1 Introduction 12 2.2 Scheduling Mechanism for Sensor Networks 13 2.3 Data Mining Techniques 17 2.3.1 Association Rule Mining (ARM) 18 2.3.2 Sequential Pattern Mining 18 2.3.3 Clustering Technique 19 2.4 Energy-Efficient Strategies for OTSNs 21 Chapter 3 Hybrid Prediction-based Tracking Scheme (HPTS) 24 3.1 Introduction 24 3.2 Problem Statement 26 3.3 System Framework 28 3.4 Proposed Methods 30 3.4.1 Formulation of Data Mining Problem 31 3.4.2 Seamless Temporal Movement Patten Mining Algorithm (STMP-Mine) 33 3.4.3 Seamless Temporal Movement Rules 38 3.5 Proposed Prediction Strategies for Object Tracking 39 3.6 Experimental Results 41 3.6.1 Simulation Model 42 3.6.2 Performance of Prediction Strategies 43 3.6.3 Comparisons of Various Prediction Methods 46 3.6.4 Effects of Varying the Object Velocity 48 3.7 Summary 50 Chapter 4 Autonomous Node Scheduling Scheme (ANSS) 52 4.1 Introduction 52 4.2 Problem Statement 54 4.3 System Framework 56 4.3.1 Log Collection 57 4.3.2 Data Mining Phase 58 4.3.3 Autonomous Scheduling Phase 59 4.4 Proposed Methods 59 4.4.1 Problem Formulations 59 4.4.2 Continuously-visited Time Period Mining (CvTP-Mine) 62 4.5 Autonomous Node Scheduling Scheme 63 4.5.1 Proposed Scheduling Strategies 64 4.5.2 An Illustrative Example 67 4.6 Experimental Evaluations 68 4.6.1 Simulation Model 68 4.6.2 Effects of Varying Parameters for Mining and Top-k of IPSN 70 4.6.3 Performance Study of Different Schemes 74 4.6.4 Summary of Experimental Results 80 4.7 Summary 81 Chapter 5 Cooperative Tracking Scheme (CTS) 83 5.1 Introduction 83 5.2 Motivations 86 5.3 System Framework 88 5.3.1 Data Mining Phase 90 5.3.2 Tracking Phase 91 5.4 Proposed Methods 91 5.4.1 Sensing-Beneficial Period Mining (SBP-Mine) 93 5.4.2 Energy-Efficient Schedule Monitoring Mechanism 95 5.4.3 Weighted-ordering Clustering Approach 96 5.4.4 Two-Stage Recovery Mechanism 98 5.5 Experimental Evaluation 100 5.5.1 Performance Study for Large-Scale Sensor Networks 102 5.5.2 Performance Study for Light Workload of Sensor Networks 107 5.5.3 Performance Study for Small Size of Sensor Networks 111 5.5.4 Study on Real Dataset 115 5.6 Summary 118 Chapter 6 Conclusions and Future Work 120 6.1 Conclusions 120 6.2 Future Work 123 References 124 Publications 130

    [1] R. Agrawal, T. Imieliński and A. Swami, “Mining Association Rule between Sets of Items in Large Databases,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 207-216, May 1993.
    [2] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases,” Proceedings of the 20th International Conference on Very Large Data Bases, pp. 478-499, Sept. 1994.
    [3] R. Agrawal and R. Srikant, “Mining Sequential Patterns,” Proceedings of the 11th International Conference on Data Engineering, pp. 3-14, Mar. 1995.
    [4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks, vol. 38, no. 4, pp. 393-422, Mar. 2002.
    [5] A. Ben-Dor and Z. Yakhini, “Clustering Gene Expression Patterns,” Journal of Computational Biology, vol. 6, no. 3, pp. 281-297, Jul. 1999.
    [6] F. Bonchi, F. Giannotti, A. Mazzanti, and D. Pedreschi, “Examiner: Optimized level-wise frequent pattern mining with monotone constraints,” Proceedings of the 3rd IEEE International Conference on Data Mining, pp. 11–18, Nov. 2003
    [7] J. Borges and M. Levene, “Data Mining of User Navigation Patterns,” Lecture Notes in Computer Science, vol. 1836, pp. 92-112, 2000.
    [8] Q. Cao, T. Abdelzaher, T. He and J. Stankovic, “Towards Optimal Sleep Scheduling in Sensor Network for Rare-Event Detection,” Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, pp. 20–27, Apr. 2005.
    [9] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton and J. Zhao, “Habitat Monitoring: Application Driver for Wireless Communications Technology,” Proceedings of the 1st ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, pp. 20-41, Apr. 2001.
    [10] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 85-96, July 2001.
    [11] M.-S. Chen, J. S. Park and P. S. Yu, “Efficient Data Mining for Path Traversal Patterns,” IEEE Transactions on Knowledge and Data Engineering, vol. 10, no. 2, pp. 209-221, Mar. 1998.
    [12] C. H. Cheong and M. H. Wong, “Mining Popular Paths in a Transportation Database System with Privacy Protection,” Proceedings of the 22nd International Conference on Data Engineering Workshops, pp. 122, Apr. 2006.
    [13] CRAWDAD Project. http://crawdad.cs.dartmouth.edu/index.php.
    [14] A. M. Denton, C. A. Besemann and D. H. Dorr, “Pattern-Based Time-Series Subsequence Clustering Using Radial Distribution Functions”, Knowledge and Information Systems, vol. 18, no. 1, pp. 1-27, Jan. 2009.
    [15] N. Eagle and A. Pentland, "Reality Mining: Sensing Complex Social Systems", Personal and Ubiquitous Computing, vol. 10, no, 4, pp.255-268, Mar. 2006.
    [16] M. Ester, H.-P. Kriegel, J. Sander and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining, pp. 226-231, Aug. 1996.
    [17] S. Goel and T. Imielinski, “Prediction-based Monitoring in Sensor Networks: Taking Lessons from MPEG,” ACM Computer Communication Review, vol. 31, no. 5, pp. 82-98, Oct. 2001.
    [18] L. Gu and J. A. Stankovic, “Radio-Triggered Wake-Up Capability for Sensor Networks," Real-Time Systems, vol.29, no. 2-3, pp.157-182, Mar. 2005.
    [19] J. Han and Y. Fu, “Discovery of Multiple-Level Association Rules in Large Database,” Proceedings of the 21st Int'l International Conference on Very Large Data Bases, pp. 420-431, Sept. 1995.
    [20] J. Han, J. Pei and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 1-12, May 2000.
    [21] T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, G. Zhou, J. Hui, and B. Krogh, “Vigilnet: an integrated sensor network system for energy-efficient surveillance,” ACM Transaction on Sensor Networks, vol.2, no.1, pp. 1-38, Feb. 2006 .
    [22] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” Proceedings of the 33rd Hawaii International Conference on System Sciences, pp. 3005-3014, Jan. 2000.
    [23] C.-F. Huang and Y.-C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, pp. 115-121, Sep. 2003.
    [24] Jorjeta G. Jetcheva, Yih-Chun Hu, Santashil PalChaudhuri, Amit Kumar Saha, and David B. Johnson, “Design and Evaluation of a Metropolitan Area Multitier Wireless Ad Hoc Network Architecture,” Proceedings of the 5th IEEE Workshop on Mobile Computing Systems & Applications, pp. 32-43, Oct. 2003.
    [25] L. Kaufman and P. J. Rousseeuw, “Finding Groups in Data: An Introduction to Cluster Analysis,” John Wiley & Sons, Mar. 1990.
    [26] H. T. Kung and D. Vlah, “Efficient Location Tracking Using Sensor Networks,” Proceedings of IEEE Conference on Wireless Communications and Networking, pp. 1954-1961, Mar. 2003.
    [27] C. Y. Lin, W. C. Peng, and Y. C. Tseng, “Efficient In-Network Moving Object Tracking in Wireless Sensor Networks,” IEEE Transaction on Mobile Computing, vol. 5, no. 8, pp. 1044-1056, Aug. 2006.
    [28] Kawuu Lin, Ming-Hua Hsieh, and Vincent S. Tseng. “A Novel Prediction-based Strategy for Object Tracking in Sensor Networks by Mining Seamless Temporal Movement Patterns,” Expert Systems with Applications, vol. 37, no. 4, pp. 2799-2807, 2010
    [29] G. Lu, B. Krishnamachari and C. Raghavendra, “An Adaptive Energy-Efficient and Low-Latency MAC for Data Gathering in Wireless Sensor Networks,” Proceedings of the 18th IEEE International Parallel and Distributed Processing Symposium, pp. 224-231, Apr. 2004.
    [30] M. Mani, “Understanding the Semantics of Sensor Data,” ACM SIGMOD Record, vol. 32, no. 4, pp. 28-34, Dec. 2003.
    [31] M. Maroti, B. Kusy, G. Simon, and A. Ledeczi, “The flooding time synchronization protocol,” Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems, pp. 39-49, Nov. 2004.
    [32] M. J. Miller and N. H. Vaidya, “Power save mechanisms for multi-hop wireless networks,” Proceedings of the 1st International Conference on Broadband Networks, pp. 518-526, Oct. 2004.
    [33] J. S. Park, M.-S. Chan and P. S. Yu, “An Effective Hash Based Algorithm for Mining Association Rules,” Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 175-186, May 1995.
    [34] J. Pei, J. Han, B. Mortazavi-Asl and H. Zhu, “Mining Access Patterns Efficiently from Web Logs,” Proceedings of the 4th Pacific Asia Conference on Knowledge Discovery and Data Mining, pp. 396-407, Apr. 2000.
    [35] W. C. Peng, Y. Z. Ko, and W. C. Lee, “On Mining Moving Patterns for Object Tracking Sensor Networks,” Proceedings of the 7th IEEE International Conference on Mobile Data Management, pp. 41-44, May 2006.
    [36] Michal Piorkowski, Natasa Sarafijanovoc-Djukic and Matthias Grossglauser, “A Parsimonious Model of Mobile Partitioned Networks with Clustering,” Proceedings of the 1st International Conference on COMmunication Systems and NETworkS, pp.1-10, Jan. 2009.
    [37] G. J. Pottie and W. J. Kaiser, “Wireless Integrated Network Sensors,” Communications of the ACM, vol. 43, no. 5, pp. 51–58, 2000.
    [38] V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava, “Energy Aware Wireless Microsensor Networks,” IEEE Signal Processing Magazine, vol. 19, no. 2, pp. 40-50, Mar. 2002.
    [39] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. B. Srivastava, “Topology management for sensor networks: exploiting latency and density,” Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 135-145, June 2002.
    [40] E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan, ”Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks,” Proceedings of the 7th ACM International Conference on Mobile Computing and Networking, pp. 272–287, July 2001.
    [41] Zhong Su, Qiang Yang, Ye Lu, and Hongjiang Zhang, “WhatNext: a prediction system for Web requests using n-gram sequence models,” Proceedings of the 1st Web Information Systems Engineering, pp. 214-221, June 2000.
    [42] D. Tian and N. D. Georganas. “A coverage-preserving node scheduling scheme for large wireless sensor networks,” Proceedings of the 1st ACM International Workshop on Wireless sensor networks and applications, pp. 32–41, Sep. 2002.
    [43] D. Tian and N. D. Georganas, “A node scheduling scheme for energy conservation in large wireless sensor networks,” Wireless Communications and Mobile Computing, vol. 3, no. 2, pp. 271–290, 2003.
    [44] H. W. Tsai, C. P. Chu, and T. S. Chen, “Mobile object tracking in wireless sensor networks,” Computing Communication, vol. 30, no. 8, pp. 1811-1825, June 2007.
    [45] V. S. Tseng and C. Kao, “Efficiently Mining Gene Expression Data via a Novel Parameterless Clustering Method,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 2, no. 4, pp. 355-365, Oct. 2005.
    [46] V. S. Tseng, K. W. Lin, “Mining Temporal Moving Patterns in Object Tracking Sensor Networks,” Proceedings of the International Workshop on Ubiquitous Data Management, pp. 105-112, Apr. 2005.
    [47] V. S. Tseng and K. W. Lin, “Energy Efficient Strategies for Object Tracking in Sensor Networks: A Data Mining Approach,” Journal of Systems and Software, vol. 80, no. 10, pp. 1678-1698, Oct. 2007.
    [48] V. S. Tseng, K. W. Lin, and Ming-Hua Hsieh, “Energy Efficient Object Tracking in Sensor Networks by Mining Temporal Moving Patterns,” Proceedings of the 2008 IEEE International Conference on Sensor Networks, Ubiquitous and Trustworthy Computing, pp. 170-176, June 2008.
    [49] V. S. Tseng, Ming-Hua Hsieh, and K. W. Lin, “Mining Region-Based Movement Patterns for Energy-Efficient Object Tracking in Sensor Networks, ” Proceedings of the 8th IEEE International Conference on Intelligent System Design and Applications, pp. 188-196, Nov. 2008.
    [50] V. S. Tseng and C. F. Tsui, “Mining Multi-Level and Location-Aware Associated Service Patterns in Mobile Environments,” IEEE Transactions on Systems, Man, and Cybernetics: Part B, vol. 34, no. 6, pp. 2480-2485, Dec. 2004.
    [51] WINS project, Rockwell Science Center. Available: http://wins.rsc.rockwell.co.
    [52] A. Woo and D. Culler, “A transmission control scheme for media access in sensor networks,” Proceedings of 7th ACM Annual International Conference on Mobile Computing and Networking, pp. 221–235, July 2001.
    [53] Y. Xu, J. Heidemann, and D. Estrin, “Adaptive Energy-Conserving Routing for Multihop Ad hoc Networks,” Technical Report 527, USC/ISI, Oct.2000.
    [54] Y. Xu and W. C. Lee, “On Localized Prediction for Power Efficient Object Tracking in Sensor Networks,” Proceedings of International Workshop on Mobile Distributed Computing, pp. 434-439, May 2003.
    [55] Y. Xu, J. Winter, and W. C. Lee, “Prediction-Based Strategies for Energy Saving in Object Tracking Sensor Networks,” Proceedings of the 5th IEEE International Conference on Mobile Data Management, pp. 346-357, Jan. 2004.
    [56] F. Ye, G. Zhong, S. Lu, and L. Zhang, “PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks,” Proceedings of the 23rd International Conference on Distributed Computing Systems, pp. 28-37, May, 2003.
    [57] W. Ye, J. Heidemann, and D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” Proceedings of the 21st IEEE Infocom, pp. 1567-1576, 2002.
    [58] W. Ye, J. Heidmann, and D. Estrin, “Medium Access Control with Coordinated Adaptive Sleeping for Wireless Sensor Networks," ACM/IEEE Transaction on Networking, vol. 12, no. 3, pp. 493-506, June 2004.

    下載圖示 校內：2013-11-18公開
    校外：2013-11-18公開
    QR CODE