Compressing Moving Object Trajectory in Wireless Sensor Networks

Abstract

Some object tracking applications can tolerate delays in data collection and processing. Taking advantage of the delay tolerance, we propose an efficient and accurate algorithm for in-network data compression, called delay-tolerant trajectory compression (DTTC). In DTTC, a cluster-based infrastructure is built within the network. Each cluster head compresses an object's movement trajectory detected within its cluster by a compression function. Rather than transmitting all sensor readings to the sink node, the cluster head communicates only the compression parameters, which not only provide the sink node expressive yet traceable models about the object movements, but also significantly reduce the total amount of data communication required for tracking operations. DTTC supports a broad class of movement trajectories using two proposed techniques, DC-compression and SW-compression, and an efficient trajectory segmentation scheme, which are designed for improving the trajectory compression accuracy at less computation cost. Moreover, we analyze the underlying cluster-based infrastructure and mathematically derive the optimum cluster size, aiming at minimizing the total communication cost of the DTTC algorithm. An extensive simulation has been conducted to compare DTTC with competing prediction-based tracking technique, DPR [28]. Simulation results show that DTTC exhibits superior performance in terms of accuracy, communication cost and computation cost and soundly outperforms DPR with all types of movement trajectories.

Keywords:

• Compression
• Segmentation
• Object Tracking
• Wireless Sensor Networks

Acknowledgement

Wang-Chien Lee and Yingqi Xu were supported in part by National Science Foundation grants IIS-0328881 and CNS-0626709.

Notes

¹This paper focuses on exploring energy-efficient data collection schemes for object tracking. Therefore, we only examine the closely related work in the field of data dissemination. However, similar techniques also appear in other sensor network operations, including infrastructure construction and maintenance, query propagation and etc.

²Within each cluster, a smaller-sized tree/cluster can be used for data aggregation [16, 28], which further reduces the total amount of data communication.

³Since MH does not allow movement randomness, to be comparable, we do not consider the bumps in RWP model.

⁴To be consistent and comparable, we use the default reporting duration, i.e., 5s in calculating the distance error, even though the sensor nodes do not report their readings with this duration.