Trajectory Data Reduction in Wireless Sensor Networks

##plugins.themes.academic_pro.article.sidebar##

Published Jul 1, 2010
https://doi.org/10.47164/ijngc.v1i1.4
Download
PDF
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 1, Issue 1, Inaugural Issue 2010

##plugins.themes.academic_pro.article.main##

Oliviu Ghica
Northwestern University
Goce Trajcevski
Northwestern University
Ouri Wolfson
University of Illinois at Chicago
Ugo Buy
University of Illinois at Chicago
Peter Scheuermann
Northwestern University
Fan Zhou
Northwestern University
Dennis Vaccaro
Northrop Grumman Corp.

Abstract

This work addresses the problem of balancing the trade-off between the energy cost due to communication and the accuracy of the tracking-based trajectories detection and representation in Wireless Sensor Networks (WSNs) settings. We consider some of the approaches used by the Moving Objects Databases (MOD) and Computational Geometry (CG) communities, and we demonstrate that with appropriate adaptation, they can yield significant benefits in terms of energy savings and, consequently, lifetime of a given WSN. Towards that, we developed distributed variations of three approaches for spatio-temporal data reduction − two heuristics (Dead-Reckoning and the Douglas-Peuker algorithm), and a variant of a CG-based optimal algorithm for polyline reduction. In addition, we examine different policies for managing the buffer used by the individual tracking nodes for storing the partial trajectory data. Lastly, we investigated the potential benefits of combining the different data-reduction approaches into " hybrid " ones during tracking of a particular object's trajectory. Our experiments demonstrate that the proposed methodologies can significantly reduce the network-wide energy expenses due to communication and increase the network lifetime.

##plugins.themes.academic_pro.article.details##

How to Cite
Oliviu Ghica, Goce Trajcevski, Ouri Wolfson, Ugo Buy, Peter Scheuermann, Fan Zhou, & Dennis Vaccaro. (2010). Trajectory Data Reduction in Wireless Sensor Networks. International Journal of Next-Generation Computing, 1(1), 28–51. https://doi.org/10.47164/ijngc.v1i1.4
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. www.openstreetmap.org.
  2. Abam, M. A., de Berg, M., Hachenberger, P., and Zarei, A. 2007. Streaming algorithms for line simplification. In Symposium on Computational Geometry.
  3. Akkaya, K. and Younis, M. 2005. A survey on routing protocols for wireless sensor networks. Ad Hoc Networks 3, 3.
  4. Alaybeyogly, A., Erciyes, K., Kantarci, A., and Dagdeviren, O. 2010. Tracking fast moving targets in wireless sensor networks. IETE Technical Review 27, 1.
  5. Bai, F., Sadagopan, N., and Helmy, A. 2003. Important: A framework to systematically analyze the impact of mobility on performance of routing protocols for adhoc networks. In INFOCOM.
  6. Bhattacharya, S., Xing, G., Lu, C., Roman, G.-C., Chipara, O., and Harris, B. 2005. Dynamic wake-up and topology maintenance protocols with spatiotemporal guarantees. In IPSN.
  7. Bose, P., Chen, D. Z., Deascu, O., Goodrich, M. T., and Snoeyink, J. 2002. Efficiently approximating polygonal paths and three and higher dimensions. Algorithmica 33, 4.
  8. Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. 2006. Randomized gossip algorithms. IEEE Transactions on Information Theory 52, 6, 2508–2530.
  9. Camp, T., Boleng, J., and Davies, V. 2002. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing 2, 5.
  10. Cao, H., Wolfson, O., and Trajcevski, G. 2006. Spatio-temporal data reduction with deterministic error bounds. VLDB Journal 15, 3.
  11. Cao, Q., Abdelzaher, T., He, T., and Stankovic, J. 2005. Towards optimal sleep scheduling in sensor networks for rare-event detection. In IPSN.
  12. Cao, Q., Yan, T., Stankovic, J., and Abdelzaher, T. 2005. Analysis of target detection performance for wireless sensor networks. In DCOSS. 276–292.
  13. Chan, W. and Chin, F. 1996. Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal on Computational Geometry and Applications 6, 1.
  14. Chen, W., Hou, J., and Sha, L. 2003. Dynamic clustering for acoustic target tracking in wireless sensor networks. In IEEE International Conference on Network Protocols (ICNP'03).
  15. Dietrich, I. and Dressler, F. 2009. On the lifetime of wireless sensor networks. TOSN 5, 1.
  16. Dodge, S., Weibel, R., and Forootan, E. 2009. Revealing the physics of movement: Comparing the similarity of movement characteristics of different types of moving objects. Computers, Environments and Urban Systems. doi:10.1016/j.compenvurbsys.2009.07.008.
  17. Douglas, D. and Peuker, T. 1973. Algorithms for the reduction of the number of points required to represent a digitised line or its caricature. The Canadian Cartographer 10, 2.
  18. Gedik, B. and Liu, L. 2006. Mobieyes: A distributed location monitoring service using moving location queries. IEEE Transactions on Mobile Computing 5, 10.
  19. Ghica, O., Trajcevski, G., Scheuermann, P., Bischoff, Z., and Valtchanov, N. 2008. Sidnet-swans: A simulator and integrated development platform for sensor networks applications. In SenSys.
  20. Hartung, C., Han, R., Seielstad, C., and Holbrook, S. 2006. Firewxnet: a multi-tiered portable wireless system for monitoring weather conditions in wildland fire environments. In MobiSys.
  21. He, G. and Hou, J. C. 2005. Tracking targets with quality in wireless sensor networks. In 13th IEEE International Conference on Network Protocols (ICNP).
  22. He, T., Vicaire, P., Yan, T., Luo, L., Gu, L., Zhou, G., Stoleru, R., Cao, Q., Stankovic, J. A., and Abdelzaher, T. F. 2006. Achieving real-time target tracking usingwireless sensor networks. In IEEE Real Time Technology and Applications Symposium.
  23. Hershberger, J. and Snoeyink, J. 1992. Speeding up the douglas-peuker line-simplification algorithm. In Proceedings of the 5th International Symposium on Spatial Data Handling.
  24. Imai, H. and Iri, M. 1988. Polygonal approximations of a curve-formulations and algorithms. In Computational Morphology. Elsevier Science Publishers, New York, N.Y., 71–86.
  25. Jeong, J., Guo, S., He, T., and Du, D. 2008. Apl: Autonomous passive localization for wireless sensors deployed in road networks. In INFOCOM.
  26. Jeong, J., Hwang, T., He, T., and Du, D. H.-C. 2007. Mcta: Target tracking algorithm based on minimal contour in wireless sensor networks. In INFOCOM.
  27. Kim, S., Pakzad, S., Culler, D. E., Demmel, J., Fenves, G., Glaser, S., and Turon, M. 2007. Health monitoring of civil infrastructures using wireless sensor networks. In IPSN. 254–263.
  28. Krishnamachari, B., Estrin, D., and Wicker, S. 2002. Impact of data aggregation in wireless sensor networks. In Proc. International Workshop on Distributed Event-Based Systems (DEBS).
  29. Lange, R., Farrell, T., Durr, F., and Rothermel, K. 2009. Remote real-time trajectory simplification. In PerCom.
  30. Lazos, L., Poovendran, R., and Ritcey, J. A. 2009. Analytic evaluation of target detection in heterogeneous wireless sensor networks. TOSN 5, 2.
  31. Lee, S., Muhammad, R. M., and Kim, C. 2007. A leader election algorithm within candidates on ad hoc mobile networks. In ICESS.
  32. Liang, B. and Haas, Z. J. 2003. Predictive distance-based mobility management for multidimensional pcs networks. IEEE/ACM Trans. Netw. 11, 5, 718–732.
  33. Madden, S., Franklin, M., Hellerstein, J., and Hong, W. 2002. Tag: a tiny aggregation service for ad hoc sensor network. In Proc. Fifth Symp. on Operating Systems Design and Implementation, USENIX OSDI.
  34. Madden, S., Franklin, M., Hellerstein, J., and Hong, W. 2005. Tinydb: An acquisitional query processing system for sensor networks. ACM TODS 30, 1.
  35. Manjhi, A., Nath, S., and Gibbons, P. B. 2005. Tributaries and deltas: Efficient and robust aggregation in sensor network streams. In SIGMOD Conference.
  36. Mao, G. and (ed.s), B. F. 2009. Localization Algorithms and Strategies for Wireless Sensor Networks. IGI Global – Invormation Science Publishing.
  37. Mueller, J. 1968. An introduction to the hydraulic and topographic sinuosity indexes1. 371.
  38. Niculesu, D. and Nath, B. 2003. Trajectory based forwarding and its applications. In MOBICOM.
  39. Pattem, S., Krishnamachari, B., and Govindan, R. 2008. The impact of spatial correlation on routing with compression in wireless sensor networks. TOSN 4, 4.
  40. Pattem, S., Poduri, S., and Krishnamachari, B. 2003. Energy-quality tradeoffs for target tracking in wireless sensor networks. In IPSN.
  41. Poduri, S., Pattem, S., Krishnamachari, B., and Sukhatme, G. S. 2009. Using local geometry for tunable topology control in sensor networks. IEEE Trans. Mob. Comput. 8, 2.
  42. Santi, P. 2005. Topology Control in Ad Hoc and Sensor Networks. John Wiley & Sons.
  43. Shrivastava, N., Buragohian, C., Agrawal, A., and Suri, S. 2004. Medians and beyond: New aggregation techniques for sensor networks. In ACM Conference on Embedded Networked Sensor Systems (SenSys).
  44. Singh, S.,Woo, M., and Raghavendra, C. 1998. Power-aware routing in mobile ad hoc networks. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom).
  45. Song, W., Wang, Y., Li, X., and Frieder, O. 2004. Localized algorithms for energy efficient topology in wireless ad hoc networks. In MobiHoc (Anchorage, AK).
  46. Sundararaman, B., Buy, U., and Kshemkalyani, A. D. 2005. Clock synchronization for wireless sensor networks: a survey. Ad Hoc Networks 3, 3, 281–323.
  47. Szewczyk, R., Mainwaring, A. M., Polastre, J., Anderson, J., and Culler, D. E. 2004. An analysis of a large scale habitat monitoring application. In SenSys.
  48. Tanin, E., Chen, S., Tatemura, J., and Hsiung, W.-P. 2008. Monitoring moving objects using low frequency snapshots in sensor networks. In MDM.
  49. Trajcevski, G., Cao, H., Wolfson, O., Scheuermann, P., and Vaccaro, D. 2006. On-line data reduction and the quality of history in moving objects databases. In MobiDE.
  50. Wang, H., Yao, K., and Estrin, D. 2005. Information-theoretic approaches for sensor selection and placement for target localization and tracking in sensor networks. Journal of Communications and Networks 7, 4.
  51. Werner-Allen, G., Lorincz, K., Welsh, M., Marcillo, O., Johnson, J., Ruiz, M., and Lees, J. 2006. Deploying a wireless sensor network on an active volcano. IEEE Internet Computing 10, 2.
  52. Wolfson, O., Sistla, A. P., Chamberlain, S., and Yesha, Y. 1999. Updating and querying databases that track mobile units. Distributed and Parallel Databases 7.
  53. Wu, S. and Candan, K. S. 2007. Power-aware single- and multipath geographic routing in sensor networks. Ad Hoc Networks 5, 7.
  54. Xu, Y. and Lee, W.-C. 2007. Compressing moving object trajectory in wireless sensor networks. IJDSN 3, 2.
  55. Yang, L., Feng, C., Rozenblit, J. W., and Qiao, H. 2006. Adaptive tracking in distributed wireless sensor networks. In ECBS.
  56. Zhang, Q., Sobelman, G. E., and He, T. 2009. Gradient-based target localization in robotic sensor networks. Pervasive and Mobile Computing 5, 1.
  57. Zhang, W. and Cao, G. 2004. Dctc: Dynamic convoy tree-based collaboration for target tracking in sensor networks. IEEE Transcations on Wireless Communication.
  58. Zhong, Z., Zhu, T., Wang, D., and He, T. 2009. Tracking with unreliable node sequences. In INFOCOM. 1215–1223.