Trajectory approximation for resource constrained mobile sensor networks

Ghulam Murtaza, Salil S. Kanhere, Aleksandar Ignjatovic, Raja Jurdak, Sanjay Jha

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationDCOSS 2014
Subtitle of host publicationProceedings of the IEEE International Conference on Distributed Computing in Sensor Systems
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages8
ISBN (Electronic)9781479946181
ISBN (Print)9781479946198
Publication statusPublished - 2014
Externally publishedYes
Event9th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2014 - Marina Del Rey, CA, United States
Duration: 26 May 201428 May 2014


Other9th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2014
CountryUnited States
CityMarina Del Rey, CA


  • Animal Habitat monitoring
  • Flying Foxes
  • GPS
  • trajectory approximation

Fingerprint Dive into the research topics of 'Trajectory approximation for resource constrained mobile sensor networks'. Together they form a unique fingerprint.

Cite this