Trajectory approximation for resource constrained mobile sensor networks

Low-power compact sensor nodes are being increasingly used to collect trajectory data from moving objects such as wildlife. The size of this data can easily overwhelm the data storage available on these nodes. Moreover, the transmission of this extensive data over the wireless channel may prove to be difficult. The memory and energy constraints of these platforms underscores the need for lightweight online trajectory compression albeit without seriously affecting the accuracy of the mobility data. In this paper, we present a novel online Polygon Based Approximation (PBA) algorithm that uses regular polygons, the size of which is determined by the allowed spatial error, as the smallest spatial unit for approximating the raw GPS samples. PBA only stores the first GPS sample as a reference. Each subsequent point is approximated to the centre of the polygon containing the point. Furthermore, a coding scheme is proposed that encodes the relative position (distance and direction) of each polygon with respect to the preceding polygon in the trajectory. The resulting trajectory is thus a series of bit codes, that have pair-wise dependencies at the reference point. It is thus possible to easily reconstruct an approximation of the original trajectory by decoding the chain of codes starting with the first reference point. Encoding a single GPS sample is an O (1) operation, with an overall complexity of O (n). Moreover, PBA only requires the storage of two raw GPS samples in memory at any given time. The low complexity and small memory footprint of PBA make it particularly attractive for low-power sensor nodes. PBA is evaluated using GPS traces that capture the actual mobility of flying foxes in the wild. Our results demonstrate that PBA can achieve up to nine-fold memory savings as compared to Douglas-Peucker line simplification heuristic. While we present PBA in the context of low-power devices, it can be equally useful for other GPS-enabled devices such smartphones and car navigation units.