Exploring Application Level Semantics for Tracking Moving Objects
Date Issued
2009
Date
2009
Author(s)
Tsai, Hsiao-Ping
Abstract
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.
Subjects
Distributed Clustering
Similarity Measure
Movement PatternMining
Cluster Ensembling
Data Aggregation
Data Compression
WSN
Object Tracking
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D87921024-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):f744b533b2d59fb1628914b7177658ff