臺灣博碩士論文加值系統

近年來無線感測網路技術日益進步，帶動許多新應用之蓬勃發展，例如物件追蹤，軍事監控，居家安全等等。由於這些應用產生大量與位置相關的資料，因此許多研究針對這類型的資料加以分析，期能擷取出有用的資訊。自然界中許多之現象顯示大多數的生物都具有群聚的特性，許多生物也有規律性的遷移行為，例如大象會群聚在一起，並沿著特定的路徑移動等等，這兩個特性都是生物學重要的研究領域。此論文研究是關於利用無線感測網路以進行物件追蹤的應用，主旨在利用資料探勘之技術於分析物件的群聚特性，以及尋找其移動的模型，並且更進一步利用探勘所得之資訊於物件追蹤機制之設計，藉以減少資料傳輸，達到節能的目的。
本論文首先研究的課題是在無線感測網路的環境下，探勘物件之群組關係以及群組物件移動之特性，我們考慮無線感測網路資源之限制-主要是電力資源有限的限制，提出一個分散式群聚關係探勘之演算法，此演算法為一兩階段探勘的架構，主要特點如下：(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.

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 A Distributed Framework of Mining Group Movement Patterns Efficiently . . 2
1.2.2 Exploring Group Movement Patterns for Data Aggregation in Tracking Applications
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Exploring Group Movements Patterns for Data Compression in a Batch-based
TrackingNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 A Distributed Framework of Mining Group Movement Patterns Efficiently 6
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Hierarchical Network Structure andLocationModel . . . . . . . . . . . . . . 11
2.2.3 Movement Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Learning of Object Movement Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Probabilistic Suffix Tree (PST) . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Probabilistic Suffix Tree with Spatial Correlation (PSTspa) . . . . . . . . . . . 18
2.4 Design of the Distributed Mining Algorithm . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.1 Similarity Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.2 The GMPMine Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.3 The Cluster Ensembling (CE) Algorithm . . . . . . . . . . . . . . . . . . . . 29
2.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.1 Discrimination Ability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.2 Impact of Lmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.5.3 Impact of the Moving Distance (d) . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5.4 Influenceof theSizeofSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5.5 PST Storage Cost and Prediction Hit Rate on Real Trajectory Datasets . . . . . 41
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3 Exploring Group Movement Patterns for Data Aggregation in Tracking Applications 44
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.1 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3 Design of the Update-based TrackingNetwork . . . . . . . . . . . . . . . . . . . . . 50
3.3.1 Group Data Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.2 PSTPrediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.3 The Multi-layer Tracking Algorithm . . . . . . . . . . . . . . . . . . . . . . . 55
3.4 Design of the In-network Data Aggregation . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.1 In-network Tracking Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4.2 Energy Cost Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.1 Efficiency of the Update-based Tracking Network and Impact of Network Structure
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.2 ImpactofAccuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.5.3 Efficiency of In-network Data Aggregation . . . . . . . . . . . . . . . . . . . 65
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Exploring Group Movements Patterns for Data Compression in a Batch-based Tracking
Network 68
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3 The Two-phase and Two-dimensional CompressionAlgorithm . . . . . . . . . . . . . 71
4.3.1 Sequence Merge Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.2 Entropy Reduction Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.3 Segmentation, Alignment, andPackaging . . . . . . . . . . . . . . . . . . . . 90
4.4 Experiment and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.1 Compressibility Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.4.2 Impact of the Group Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.4.3 Impact of the Batch Period . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.4.4 ImpactofAccuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.4.5 Effectiveness of the ReplaceAlgorithm . . . . . . . . . . . . . . . . . . . . . 97
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5 Conclusions 99
Bibliography 100

[1] African elephant. Available at http://www.defenders.org/wildlife_and_habitat/wildlife/elephant.php.
[2] Mica2 sensor board. Available at http://www.xbow.com. [3] Stargate:a platform x project. Available at http://platformx.sourceforge.net.
[4] New nand flash application trends in 2007. Available at http://www.dramexchange.com/weeklyresearch/post/1/500.aspx, Jan. 2007.
[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.
[6] R. Agrawal and R. Srikant. Mining sequential patterns. In Proc. 11th Int’l Conf. on Data Engineering, pages 3–14, 1995.
[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.
[11] R. Avogadri and G. Valentini. Fuzzy ensemble clustering based on random projections for DNA microarray data analysis. Artifical Intelligenc Med, pages 1866–1881, Sep. 2008.
[12] H. Ayad, O. A. Basir, andM. Kamel. A probabilisticmodel using information theoretic measures for cluster ensembles. In proc. 5th Int’l Wksp. on Multiple Classifier Systems, pages 144–153, Jun. 2004.
[13] B., D. Estrin, and S. B. Wicker. The impact of data aggregation in wireless sensor networks. In Proc. 22nd Conf. Distributed Computing Systems, pages 241–245, Jul. 2002.
[14] S. Baek, G. de Veciana, and X. Su. Minimizing energy consumption in large-scale sensor networks through distributed data compression and hierarchical aggregation. IEEE J. on Selected Areas in Communications, 22(6):1130–1140, Aug. 2004.
[15] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. Lai. Deploying wireless sensors to achieve bothcoverage and connectivity. In Proc. ACM Annual Int’l Symp. on Mobile Ad-Hoc Networking andComputing, pages 131–142, May 2006.
[16] G. Bejerano and G. Yona. Variations on probabilistic suffix trees: statistical modeling and theprediction of protein families. Bioinformatics, 17(1):23–43, 2001.
[17] D. Bolier. SIM : a c++ library for discrete event simulation. Available athttp://www.cs.vu.nl/ eliens/sim, Oct. 1995.
[18] D. Bollegala, Y. Matsuo, and M. Ishizuka. Measuring semantic similarity between words usingweb search engines. In Proc. 16th Int’l World Wide Web Conf., pages 757–766, 2007.
[19] M. Cardei, M. T. Thai, Y. Li, and W. Wu. Energy-efficient target coverage in wireless sensornetworks. In Proc. 24th IEEE Int’l Conf. Computer Communications, 2005.
[20] Y. C. Chang, D. J. Lee, Y. Hong, J. K. Archibald, and D. Liang. A robust color image quantizationalgorithm based on knowledge reuse of k-means clustering ensemble. J. of Multimedia,3(2):20–27, Jun. 2008.
[21] L. Chen, M. Tamer Özsu, and V. Oria. Robust and fast similarity search for moving objecttrajectories. In Proc. ACM SIGMOD Int’l Conf. on Management of Data, pages 491–502, 2005.
[22] M.-S. Chen, J. S. Park, and P. S. Yu. Efficient data mining for path traversal patterns. Knowledgeand Data Engineering, 10(2):209–221, 1998.
[23] C.-P. Cheng, G.-T. Lau, J. Pan, K.-H. Law, and A. Jones. Domain-specific ontology mapping bycorpus-based semantic similarity. In Proc. Scientific Foundations Wksp. of End-to-End ServiceUtility, Mar. 2007.
[24] K. W. Church and P. Hanks. Word association norms, mutual information, and lexicography.Computational Linguistics, 16(1):22–29, 1990.
[25] D. Culler, D. Estrin, and M. Srivastava. Overview of sensor networks. IEEE Computer, SpecialIssue in Sensor Networks, 37(8):41–49, Aug. 2004.
[26] A. Deligiannakis, Y. Kotidis, and N. Roussopoulos. Hierarchical in-network data aggregationwith quality guarantees. In Proc. 9th Int’l Conf. on Extending Database Technology, volume2992, pages 658–675, Mar. 2004.
[27] Y. Diao, D. Ganesan, G. Mathur, and P. J. Shenoy. Rethinking data management for storagecentricsensor networks. In Proc. 3d Biennial Conf. on Innovative Data Systems Research, pages22–31, Nov. 2007.
[28] S. Dubnov, G. Assayag, O. Lartillot, and G. Bejerano. Using machine-learning methods formusical style modeling. IEEE Computer Magazine, 36(10):73–80, Oct. 2003.
[29] P. Dutta, D. Culler, and S. Shenker. Procrastination might lead to a longer and more useful life.In Proc. 6thWksp. on Hot Topics in Networks, Nov. 2007.
[30] X. Z. Fern and C. E. Brodley. Random projection for high dimensional data clustering: A clusterensemble approach. In Proc. 20th Int’l Conf. on Machine Learning, pages 1186–193, Jun. 2003.
[31] A. L. N. Fred and A. K. Jain. Combining multiple clusterings using evidence accumulation.IEEE Trans. on Pattern Analysis and Machine Intelligence, 27(6):835–850, Jun. 2005.
[32] D. Ganesan, B. Greenstein, D. Estrin, J. heidemann, and R. Govindan. Multiresolution storageand search in sensor networks. ACM Trans. on Storage, 1(3):277–315, Aug. 2005.
[33] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In Proc. 13thACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, pages 330–339, 2007.
[34] J. D. Gibson. The Mobile Communications Handbook, Second Edition. CRC Press, 1998.
[35] B. Gloss, M. Scharf, and D. Neubauer. Location-dependent parameterization of a random directionmobility model. In Proc. IEEE 63rd Conf. on Vehicular Technology, volume 3, pages1068–1072, 2006.
[36] J.-W. Han, J. Pei, B. Mortazavi-Asl, Q.-M. Chen, U. Dayal, and M.-C. Hsu. Freespan: frequentpattern-projected sequential pattern mining. In Proc. 6th ACMSIGKDD Int’l Con. on KnowledgeDiscovery and Data Mining, pages 355–359, 2000.
[37] E. Hartuv and R. Shamir. A clustering algorithm based on graph connectivity. InformationProcessing Letters, 76(4-6):175–181, 2000.
[38] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocolfor wireless microsensor networks. In Proc. 33rd Annual Hawaii Int’l Conf. on SystemSciences, pages 3005–3014, Jan. 2000.
[39] J. Hightower and G. Borriello. Location systems for ubiquitous computing. Computer, 34(8):57–66, Aug. 2001.
[40] B. Hoffmeister and T. Zeugmann. Text mining using markov chains of variable length. LectureNotes in Artificial Intelligence, pages 1–24, 2006.
[41] X. Hong, M. Gerla, G. Pei, and C. Chiang. A group mobility model for ad hoc wireless networks.In Proc. 9th ACM/IEEE Int’l Symp. on Modeling, Analysis and Simulation of Wirelessand Mobile Systems, pages 53–60, Aug. 1999.
[42] J.-L. Huang and M.-S. Chen. On the effect of group mobility to data replication in ad hocnetworks. IEEE Trans. on Mobile Computing, 5(5), May 2006.
[43] J. Jeong, T. Hwang, T. He, and D. Du. Mcta: Target tracking algorithm based on minimal contourin wireless sensor networks. In Proc. 26th IEEE Int’l Conf. on Computer Communications, pages2371–2375, May 2007.
[44] G. Karpis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregulargraphs. SIAM J. of Scientific Computing, 20(1):359âA˘ S¸–392, 1998.
[45] D. Katsaros and Y. Manolopoulos. A suffix tree based prediction scheme for pervasive computingenvironments. In Panhellenic Conf. on Informatics, pages 267–277, Nov. 2005.
[46] H. T. Kung and D. Vlah. Efficient location tracking using sensor networks. In Proc. Conf. IEEEWireless Communications and Networking, volume 3, pages 1954–1961, Mar. 2003.
[47] C. Largeron-Leténo. Prediction suffix trees for supervised classification of sequences. PatternRecognition Letters, 24(16):3153–3164, 2003.
[48] J.-G. Lee, J. Han, andK.-Y. Whang. Trajectory clustering: a partition-and-group framework. InProc. ACM SIGMOD Int’l Conf. on Management of Data, pages 593–604, 2007.
[49] D.Li, K. D. Wong,Y. H. Hu, andA. M. Sayeed. Detection, classification, and tracking of targets.IEEE Signal Processing Magazine, 19(2):17–30, Mar. 2002.
[50] Y. Li, J. Han, and J. Yang. Clustering moving objects. In Proc. 10th ACM SIGKDD int’l conf.on Knowledge discovery and data mining, pages 617–622, 2004.
[51] C.-Y. Lin,W.-C. Peng, and Y.-C. Tseng. Efficient in-network moving object tracking in wirelesssensor networks. IEEE Trans. on Mobile Computing, 5(8):1044–1056, Aug. 2006.
[52] C.-Y. Lin and Y.-C. Tseng. Structures for in-network moving object tracking in wireless sensornetworks. In Proc. 1st Int’l Conf. on Broadband Networks, pages 718–727, Oct. 2004.
[53] X. Liu, A. Krishnan, and A. Mondry. An entropy-based gene selection method for cancer classificationusing microarray data. BMC Bioinformatics, 6(76), Mar. 2005.
[54] G. Mathur, P. Desnoyers, D. Ganesan, and P. Shenoy. Ultra-low power data storage for sensornetworks. In Proc. 5th Int’l Conf. on Information Processing in Sensor Networks, pages 374–381, Apr. 2006.
[55] N. Meratnia and R. A. de By. A new perspective on trajectory compression techniques. In Proc.ISPRS Commission II and IV, WG II/5, II/6, IV/1 and IV/2 Joint Wksp. on Spatial, Temporal andMulti-dimensional Data Modelling and Analysis, Oct. 2003.
[56] M. Morzy. Prediction of moving object location based on frequent trajectories. In Proc. 21thInt’l Symp. on Computer and Information Sciences, pages 583–592, Nov. 2006.
[57] M. Morzy. Mining frequent trajectories of moving objects for location prediction. In Proc. 5thInt’l Conf. on Machine Learning and Data Mining in Pattern Recognition, pages 667–680, Jul.2007.
[58] M. Nanni and D. Pedreschi. Time-focused clustering of trajectories of moving objects. J. IntelligentInformation Systems, 27(3):267–289, 2006.
[59] F. Osterlind and A. Dunkels. Approaching the maximum 802.15.4 multi-hop throughput. InProc. 5th Wksp. on Embedded Networked Sensors, 2008.
[60] P. Sun, S. Chawla, and B. Arunsalam. Mining for outliers in sequential databases. In Proc. 6thSIAM Int’l Conf. on Data Mining, Apr. 2006.
[61] S. Pandey, S. Dong, P. Agrawal, and K. Sivalingam. A hybrid approach to optimize node placementsin hierarchical heterogeneous networks. In Proc. IEEE Conf. onWireless Communicationsand Networking Conference, pages 3918–3923, Mar. 2007.
[62] W.-C. Peng and M.-S. Chen. Developing data allocation schemes by incremental mining ofuser moving patterns in a mobile computing system. IEEE Trans. on Knowledge and DataEngineering, 15(1):70–85, Jan.-Feb. 2003.
[63] W.-C. Peng, Y.-Z. Ko, and W.-C. Lee. On mining moving patterns for object tracking sensornetworks. In Proc. 7th Int’l Conf. on Mobile Data Management, 2006.
[64] M. A. Perillo and W. Heinzelman. Optimal sensor management under energy and reliabilityconstraints. In Proc. IEEE Int’l Conf. Wireless Communications and Networking, volume 3,pages 1621–1626, Mar. 2003.
[65] J. P. W. Pluim, J. B. A. Maintz, and M. A. Viergever. Mutual information based registration ofmedical images: a survey. IEEE Trans. on Medical Imaging, 22(8):986–1004, Aug. 2003.
[66] S. S. Pradhan, J. Kusuma, and K. Ramchandran. Distributed compression in a dense microsensornetwork. IEEE Signal Processing Magazine, 19(2):51–60, Mar. 2002.
[67] D. Ron, Y. Singer, and N. Tishby. Learning probabilistic automata with variable memory length.In Proc. 7th Annual Conf. on Computational Learning Theory, Jul. 1994.
[68] C. Roux and R. T. F. Bernard. Home range size, spatial distribution and habitat use of elephantsin two enclosed game reserves in the eastern cape province, south africa. African J. of Ecology,Oct. 2007.
[69] C. M. Sadler and M. Martonosi. Data compression algorithms for energy-constrained devicesin delay tolerant networks. In Proc. ACM Conf. on Embedded Networked Sensor Systems, Nov.2006.
[70] S. Santini and K. Romer. An adaptive strategy for quality-based data reduction in wireless sensornetworks. In Proc. 3rd Int’l Conf. on Networked Sensing Systems, pages 29–36, Jun. 2006.
[71] G. Saporta and G. Youness. Comparing two partitions: some proposals and experiments. InProc. Computational Statistics, Aug. 2002.
[72] A. Scaglione and S. D. Servetto. On the interdependence of routing and data compression inmulti-hop sensor networks. In Proc. 8th Annual Int’l Conf. onMobile computing and networking,pages 140–147, 2002.
[73] C. E. Shannon. A mathematical theory of communication. J. Bell System Technical, 27:379–423,623–656, 1948.
[74] G. Shannon, B. Page, K. Duffy, and R. Slotow. African elephant home range and habitat selectionin pongola game reserve, south africa. African Zoology, 41(1):37–44, Apr. 2006.
[75] A. Silberstein. Push and pull in sensor network query processing. In Proc. Southeast Wksp. onData and Information Management, Mar. 2006.
[76] M. Stoer and F. Wagner. A simple min-cut algorithm. J. of the ACM, 44(4):585–591, Jul. 1997.
[77] A. Strehl and J. Ghosh. Cluster ensembles - a knowledge reuse framework for combining partitionings.In Proc. Conf. on Artificial Intelligence, pages 93âA˘ S¸–98, Jul. 2002.
[78] J. Tang, B. Hao, and A. Sen. Relay node placement in large scale wireless sensor networks. J.of Computer Communications, Special Issue on Sensor Networks, 29(4):490–501, 2006.
[79] Y. Theodoridis. The r-tree portal. Available at http://www.rtreeportal.org, Dec. 2005.
[80] A. Topchy, A. K. Jain, and W. Punch. A mixture model for clustering ensembles. In Proc. Int’lSIAM Conf. on Data Mining, pages 379–390, 2004.
[81] V. S. Tseng and K.W. Lin. Mining temporal moving patterns in object tracking sensor networks.In Proc. Int’l Wksp. on Ubiquitous Data Management, 2005.
[82] V. S. Tseng and K. W. Lin. Energy efficient strategies for object tracking in sensor networks: Adata mining approach. J. Systems and Software, 80(10):1678–1698, 2007.
[83] N. A. Vasanthi and S. Annadurai. Energy saving schedule for target tracking sensor networksto maximize the network lifetime. In Proc. 1st Int’l Conf. Communication System Software andMiddleware, pages 1–8, Jan. 2006.
[84] G.Wang, H.Wang, J. Cao, andM. Guo. Energy-efficient dual prediction-based data gathering forenvironmental monitoring applications. In Proc. IEEEWireless Communication and NetworkingConf., Mar. 2007.
[85] X. Wang, L. Ding, D. Bi, and S. Wang. Energy-efficient optimization of reorganization-enabledwireless sensor networks. Sensors, 7:1793–1816, 2007.
[86] Y. Wang, E.-P. Lim, and S.-Y. Hwang. Efficient mining of group patterns from user movementdata. Data Knowledge Engineering, 57(3):240–282, 2006.
[87] Y. Wang, P. Zhang, T. Liu, C. Sadler, and M. Martonosi. CRAWDADtrace princeton/zebranet/movement/baseoututm2 (v. 2007-02-14). Available athttp://crawdad.cs.dartmouth.edu/princeton/zebranet/movement/baseoutUTM2, feb 2007.
[88] S. Watanabe. Pattern recognition as a quest for minimum entropy. Pattern Recog., 13(5):381–387, 1981.
[89] G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectivityconfiguration for energy conservation in sensor networks. ACM Trans. Sensor Networks,1(1):36–72, Jan. 2005.
[90] Y. Xu, J. Winter, and W.-C. Lee. Dual prediction-based reporting for object tracking sensornetworks. In Proc. 1st Annual Int’l Conf. on Mobile and Ubiquitous Systems: Networking andServices, pages 154–163, Aug. 2004.
[91] Y. Xu, J.Winter, andW.-C. Lee. Prediction-based strategies for energy saving in object trackingsensor networks. In Proc. IEEE Int’l Conf. on Mobile Data Management, pages 346–357, 2004.
[92] Y.-G. Xu and W.-C. Lee. Compressing moving object trajectory in wireless sensor networks.Int’l J. of Distributed Sensor Networks, 3(2):151–174, Apr. 2007.
[93] Y. Xue, Y. Cui, and K. Nahrstedt. Maximizing lifetime for data aggregation in wireless sensornetworks. Mobile Networks and Applications, 10(6):853–864, 2005.
[94] Y. and K. Chakrabarty. Sensor deployment and target localization based on virtual forces. InProc. 22nd Annual Join Conf. IEEE Computer and Communications Societies, volume 2, pages1293–1303, Apr. 2003.
[95] H. Yang and B. Sikdar. A protocol for tracking mobile targets using sensor networks. In Proc.IEEE Int’l Wksp. on Sensor Network Protocols and Applications, pages 71–81, May 2003.
[96] J. Yang andM. Hu. Trajpattern: Mining sequential patterns from imprecise trajectories of mobileobjects. In Proc. 10th Int’l Conf. on Extending Database Technology, pages 664–681,Mar. 2006.
[97] J. Yang and W. Wang. CLUSEQ: Efficient and effective sequence clustering. In Proc. 19th Int’lConf. on Data Engineering, pages 101–112, Mar. 2003.
[98] L. Yang, C. Feng, J. W. Rozenblit, and H. Qiao. Adaptive tracking in distributed wireless sensornetworks. In Proc. 13th Annual IEEE Int’l Symp. and Wksp. on Engineering of Computer BasedSystems, pages 103–111, Mar. 2006.
[99] J. Yick, B. Mukherjee, and D. Ghosal. Analysis of a prediction-based mobility adaptive trackingalgorithm. In Proc. 2nd Int’l Conf. on Broadband Networks, pages 753–760, Oct. 2005.
[100] M. Younis and K. Akkaya. Strategies and techniques for node placement in wireless sensornetworks: A survey. Ad Hoc Netw., 6(4):621–655, 2008.
[101] L. Yuan and H. K. Kesavan. Minimum entropy and information measurement. IEEE Tran. onSystem, Man, and Cybernetics, 28(3), Aug. 1998.
[102] H. Zhang and J. C. Hou. Maintaining sensing coverage and connectivity in large sensor networks.J. on Wireless Ad Hoc and Sensor Networks, 1(1-2):89–123, Jan. 2005.
[103] W. Zhang and G. Cao. DCTC: Dynamic convoy tree-based collaboration for target tracking insensor networks. IEEE Trans. on Wireless Communications, 3(5):1689–1701, Sep. 2004.
[104] L. Zhong, R. Shah, C. Guo, and J. Rabaey. An ultra-low power and distributed access protocolfor broadband wireless sensor networks. IEEE Broadband Wireless Summit, May 2001.
[105] Z. Zhou, S. Das, and H. Gupta. Connected k-coverage problem in sensor networks. In Proc.13th Int’l Conf. Computer Communications and Networks, pages 373–378, Oct. 2004.