探勘應用層語義於移動物件追蹤機制之設計

近年來無線感測網路技術日益進步，帶動許多新應用之蓬勃發展，例如物件追蹤，軍事監控，居家安全等等。由於這些應用產生大量與位置相關的資料，因此許多研究針對這類型的資料加以分析，期能擷取出有用的資訊。自然界中許多之現象顯示大多數的生物都具有群聚的特性，許多生物也有規律性的遷移行為，例如大象會群聚在一起，並沿著特定的路徑移動等等，這兩個特性都是生物學重要的研究領域。此論文研究是關於利用無線感測網路以進行物件追蹤的應用，主旨在利用資料探勘之技術於分析物件的群聚特性，以及尋找其移動的模型，並且更進一步利用探勘所得之資訊於物件追蹤機制之設計，藉以減少資料傳輸，達到節能的目的。本論文首先研究的課題是在無線感測網路的環境下，探勘物件之群組關係以及群組物件移動之特性，我們考慮無線感測網路資源之限制-主要是電力資源有限的限制，提出一個分散式群聚關係探勘之演算法，此演算法為一兩階段探勘的架構，主要特點如下：(1)針對無線感測網路節能的議題，我們以分散式的探勘架構來處理，僅傳輸局部區域分群結果至中央伺服器，以減少資料傳輸；(2)考量群組數目和群組大小之變異性；(3)提供較佳的分群效果和穩定性，及對異常值有較佳之恢復力；(4)分散式的架構為不同的資料來源提供彈性，適合運用於異質追蹤網路環境；(5)以一切割參數集和探索的方式尋找較佳解，折衷權衡分群效果和計算複雜度。在此演算法的第一階段，我們提出一個群組移動模型探勘演算法，稱之為GMPMine。在此演算法中，我們探勘物件移動的軌跡以建立位置預測模型，並基於物件的位置預測模型，提出一個新的相似度比較法，以便對物件進行分群，擷取出局部區域的物件群聚資訊。在第二階段，我們提出分群整合的演算法，稱之為CE，其將各局部區域的分群結果加以整合，以找出較佳的分群結果和提升分群穩定性。和其他集中式分群的不同，在於我們僅將各局部區分群的結果傳回伺服器，進行結合的步驟，比起將所以的資料全部傳回伺服器再進行分析，我們的所提出的分散式的方法不但有效率，實驗結果也顯示我們的方法能有效地將不同移動路徑的物件的群聚關係找出來。在物件追蹤感測網路中，為更新物件位置所產生之資料傳輸，是能源消耗的主因之一，本論文第二部分討論的課題是利用探勘所得之群組移動特性，設計群組物件位置更新之聚集技術，以減少資料傳輸。我們的設計分為兩個方向：一個是介於區域感測網路頭端（clusterhead）和伺服器（sink）間之跨網路層資料聚集技術，另一個是網內群組物件追蹤之協定和網內資料聚集技術。我們提出跨網路層資料聚集技術，其利用物件的群聚關係於物件位置更新，整合多個物件位置更新所需之封包，以群組編號取代多個個別物件的編號，達成減少資料傳輸的目的；另外，我們亦利用GMPMine演算法所得之位置預測模型，預測物件未來可能的位置；當區域感測網路頭端和伺服器都以此預測模型和相同的先前位置資料進行預測時，對於可正確預測之位置，可以避免傳送不必要的封包，進一步減少物件位置更新所需之資料傳輸。無線感測網路的另一個重要課題是感測區域覆蓋（coverage）程度和感測網路效率之權衡（trade-off），許多研究利用個別物件移動的方向、速度和位置等資訊於感測器睡眠機制之設計；然而先前之研究並沒有利用到物件的群聚特性。在本論文中，我們利用物件群聚特性於網內物件追蹤協定和網內資料聚集技術之設計，我們動態的預估群組分散的範圍，並以位置預測模型預測群組物件的中心位置，啟動預測範圍內的感測器進行偵測和追蹤的工作。根據我們的數學分析和模擬實驗結果顯示，當物件的群組關係存在時，我們的設計比先前的研究，如PES[93]，更為省電。在本論文的第三部分，我們利用探勘所得之資訊於設計一個二階段二維度的壓縮技術，運用此壓縮技術於一個批次式的無線感測網路中，以減少物件位置更新所需傳輸的資料量。此壓縮技術包含兩個階段：位置序列合併階段和熵降低階段。在位置序列合併階段，我們提出Merge演算法來合併和壓縮一群物件的位置資料。在熵降低階段，我們利用位置預測模型來增加資料的不對稱性（skewness），並系統地將之表示成猜對項目的取代（HIR）問題。我們提出Replace演算法來取得HIR問題的最佳解。在此演算法中，我們用資訊理論中熵之特性，策劃設計三個取代規則來降低位置序列的熵，有效率地解決HIR問題。實驗結果顯示我們所提出的二階段二維度的壓縮技術可以有效且有效率地利用群組資訊和群組移動的模型來減少傳輸的資料量，達到省電的目的。在本論文中，我們針對物件追蹤的應用，探勘其應用層語義，並研究無線感測網路節能的課題，利用探勘所得之資訊於移動物件追蹤機制之設計，實驗結果驗證我們所提出之分散式群聚關係探勘演算法能有效地挖掘出物件的群組關係和群組物件的移動模型，實驗結果也顯示利用群聚關係和位置預測模型於資料聚集技術和壓縮技術，可有效地減少傳輸的資料量，達到省電的目的。

關鍵字

無線感測網路；物件追蹤；分散式資料分群技術；相似度測量；移動型樣探勘；群組整合；資料聚集；資料壓縮

並列摘要

Recent advances in technologies of wireless sensor networks (WSNs) have fostered many novel tracking and monitoring applications, which generate large amounts of location data. Many approaches focus on compiling the collected data to extract useful information, such as the repeat patterns of objects of interest. Natural phenomena show that many creatures form large social groups and move in regular patterns. The group relationships together with the movement patterns are important in some biological research domains, such as the study of animals’ social behavior and wildlife migration. However, previous works focus on finding the movement of each single object or all objects. In this dissertation, we formulate the moving object clustering problem to minimize the number of groups such that members in each of the discovered groups are highly related by their movement patterns. First, we propose a new similarity measure, which is based on the objects’ movement patterns, to compute the similarities of moving objects. Then, we propose a distributed and two-phase mining algorithm that finds moving animals belonging to the same group and identify their aggregated movement patterns in a resource-constrained tracking network like WSNs. To address the energy conservation issue in WSNs, the algorithm only transmits the local grouping results to the sink node for further processing, instead of all the raw data about moving objects’ locations. The algorithm also considers the diversity of the number of groups and their sizes because of the inherent variations in the number of groups and their sizes in the tracking applications. The proposed algorithm comprises a local mining phase and a cluster ensembling phase. In the local mining phase, the algorithm finds movement patterns in the local trajectory datasets and identifies the local group relationships of moving objects. In the cluster ensembling phase, the algorithm exploits the information theory to combine the local grouping results to derive the group relationships from a global view. Since the tracking applications generate large amounts of location data, which lead to transmission and storage challenges in WSNs, various data aggregation and data compression algorithms have been proposed to reduce the amount of transmitted data - by extension- to reduce the energy consumption expense for data transmission in WSNs. However, previous works did not address application level semantics, such as the group relationships and movement patterns, in the location datasets. Therefore, we propose an inter-layer tracking algorithm and an in-network tracking protocol to track a group of moving objects efficiently by exploiting the group movement patterns. In the tracking algorithm, we utilize the group relationships in data aggregation to reduce long-distance transmissions. Moreover, we also use the movement patterns as the prediction model to avoid unnecessary transmissions when a location of an object is predictable based on its previous trajectory. In the in-network tracking protocol, we form a sensor group (SG) to track a group of moving objects and to keep most sensors in sleep mode for saving energy. Specifically, with the group information, we dynamically and adaptively adjust the size of an SG to provide coverage for all objects of a group; the group movement patterns enable us to predict the center of a group of moving objects such that we designate the sensor nearest to the center to handle the rest tracking affairs. In addition, we propose a two-phase and two-dimensional compression algorithm that exploits the obtained group movement patterns to reduce the amount of delivered data. The compression algorithm includes a sequence merge phase and an entropy reduction phase. In the sequence merge phase, we propose a Merge algorithm to merge and compress the location data of a group of moving objects. In the entropy reduction phase, we formulate a Hit Item Replacement (HIR) problem and prove the proposed Replace algorithm obtains the optimal solution. In the algorithm, we devise three replacement rules by using properties of information theory to derive the maximum compression ratio effectively and efficiently. The results of experiments show that the proposed distributed and two-phase mining algorithm achieves good grouping quality, and the derived information helps reduce the energy consumption by reducing the long-distance transmissions, in-network data traffic, and the amount of data to be transmitted.

並列關鍵字

Distributed Clustering ； Similarity Measure ； Movement PatternMining ； Cluster Ensembling ； Data Aggregation ； Data Compression ； WSN ； Object Tracking

參考文獻

[5] Z. Abrams, A. Goel, and S. Plotkin. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In Proc. Int’l Conf. Information Processing in Sensor Networks, pages 424–432, Apr. 2004.

[7] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: A survey. Computer Networks, 38(4):393–422, 2002.

[8] J. N. Al-Karaki and A. E. Kamal. Routing techniques in wireless sensor networks: a survey. IEEE Wireless Communications, 11(6):6–28, 2004.

[9] J. N. Al-Karaki, R. Ul-Mustafa, and A. E. Kamal. Data aggregation in wireless sensor networks - exact and approximate algorithms. In Proc. IEEE Wksp. on High Performance Switching and Routing, pages 241–245, Oct. 2004.

[10] A. Apostolico and G. Bejerano. Optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space. In Proc. 4th annual Int’l Conf. on Computational Molecular Biology, pages 25–32, 2000.

國際替代計量

探勘應用層語義於移動物件追蹤機制之設計

全文下載

主題瀏覽