A Novel Per-Hop Per-Packet Delay Tomography in Wireless Ad Hoc Networks

Authors(2) :-S. Ulaganathan, G. Raja Raja Cholan

Packet delivery delay is one of the most important performance metrics in multi-hop wireless ad-hoc networks. Though numerous research efforts have been spent on measuring and optimizing the end-to-end delay performance, there frequently lack precise and lightweight methods for decomposing the end-to-end delay into the per-hop delay for every packet. The per-hop per-packet delay is able to deeply improve the network visibility and create probable network management and measurement. This thesis proposes Domo, an accurate and lightweight delay tomography method for decomposing the packet end-to-end delay into every hop. The basic idea is to formulate the problem into a set of optimization problems by carefully considering the constraints among various timing quantities. At the network side, Domo attaches a small overhead to each packet for constructing constraints for the optimization problems. At the PC side, Domo employs semi definite relaxation and several other methods to efficiently solve the optimization problems. This thesis implements Domo and evaluates its performance extensively using large-scale simulations. Results show that Domo significantly outperforms two existing methods, nearly tripling the accuracy of the state-of-the-art.

Authors and Affiliations

S. Ulaganathan
Department of Computer Science, Prist University, Vallam, Thanjavur, Tamil Nadu, India
G. Raja Raja Cholan
Department of Computer Science, Prist University, Vallam, Thanjavur, Tamil Nadu, India

Wireless ad-hoc Network, Network Measurement, Delay Tomography.

  1. J. Schiller, Mobile communication. Addison-Wesley Verlag, 2000.
  2. S. Toumpis and D. Toumpakaris, "Wireless ad hoc networks and related topologies: applications and research challenges," e & i Electro technique und Information’s technique, vol. Volume 123, pp. 232-241, 2006.
  3. M. GŁnes, B. Blywis, and F. Juraschek, "Concept and design of the hybrid distributed embedded systems testbed," August 2008.
  4. Perkins and C. E., Ad hoc networking. Addison-Wesley Verlag, 2001.
  5. "The official bluetooth."
  6. L. Mo, Y. He, Y. Liu, J. Zhao, S. Tang, X. Li, and G. Dai, "Canopy Closure Estimates with GreenOrbs: Sustainable Sensing in the Forest," in Proceedings of SenSys, 2009.
  7. M. Ceriotti, L. Mottola, G. P. Picco, A. L. Murphy, S. Guna, M. Corra, M. Pozzi, D. Zonta, and P. Zanon, "Monitoring heritage buildings with wireless sensor networks: The torre aquila deployment," in Proceedings of IPSN, 2009.
  8. X. Mao, X. Miao, Y. He, T. Zhu, J. Wang, W. Dong, X. Li, and Y. Liu, "Citysee: Urban CO2 monitoring with sensors," in Proceedings of INFOCOM, 2012.
  9. O. Chipara, C. Lu, T. C. Bailey, and G. catalin Roman, "Reliable clinical monitoring using wireless sensor networks: Experiences in a step-down hospital unit," in Proceedings of SenSys, 2010.
  10. M. Patel and J. Wang, "Applications, challenges, and prospective in emerging body area networking technologies," IEEE Wireless Communications, vol. 17, no. 1, pp. 80-88, 2010.
  11. M. Keller, L. Thiele, and J. Beutel, "Reconstruction of the correct temporal order of sensor network data," in Proceedings of IPSN, 2011.
  12. J. Wang, W. Dong, Z. Cao, and Y. Liu, "On the delay performance analysis in a large-scale wireless sensor network," in Proceedings of RTSS, 2012.
  13. Y. Gu and T. He, "Data forwarding in extremely low dutycycle sensor networks with unreliable communication links," in Proceedings of SenSys, 2007.
  14. L. Ma, T. He, K. K. Leung, D. Towsley, and A. Swami, "Efficient identification of additive link metrics via network tomography," in Proceedings of ICDCS, 2013.
  15. P. Sommer and B. Kusy, "Minerva: distributed tracing and debugging in wireless sensor networks," in Proceedings of ACM SenSys, 2013.
  16. R. R. Kompella, K. Levchenko, A. C. Snoeren, and G. Varghese, "Every microsecond counts: tracking fine-grain latencies with a lossy difference aggregator," in Proceedings of ACM SIGCOMM, 2009.
  17. M. Lee, N. Duffield, and R. R. Kompella, "Not all microseconds are equal: fine-grained per-flow measurements with reference latency interpolation," in Proceedings of ACM SIGCOMM, 2010.
  18. M. Lee, S. Goldberg, R. R. Kompella, and G. Varghese, "Fine-grained latency and loss measurements in the presence of reordering," in Proceedings of the ACM SIGMETRICS, 2011.
  19. K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, and C. Diot, "Measurement and analysis of single-hop delay on an IP backbone network," IEEE J. Sel. Areas Commun., vol. 21, no. 6, pp. 908-921, Aug. 2003.
  20. M. Keller, J. Beutel, and L. Thiele, "How was your journey? Uncovering routing dynamics in deployed sensor networks with multi-hop network tomography," in Proc. ACM SenSys, 2012, pp. 15-28.
  21. V. Sundaram and P. Eugster, "Lightweight message tracing for debugging wireless sensor networks," in Proc. IEEE/IFIP DSN, Jun. 2013, pp. 1-12.
  22. O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis, "Collection tree protocol," in Proc. ACM SenSys, 2009, pp. 1-14.
  23. Y. Gao et al., "Pathfinder: Robust path reconstruction in large scale sensor networks with lossy links," in Proc. IEEE ICNP, Oct. 2013, pp. 1-10.
  24. Z. Liu, Z. Li, M. Li, W. Xing, and D. Lu, "Path reconstruction in dynamic wireless sensor networks using compressive sensing," IEEE/ACM Trans. Netw., vol. 24, no. 4, pp. 1948-1960, Aug. 2016.
  25. X. Lu, D. Dong, X. Liao, and S. Li, "PathZip: Packet path tracing in wireless sensor networks," in Proc. MASS, 2012, pp. 380-388

Publication Details

Published in : Volume 2 | Issue 4 | July-August 2017
Date of Publication : 2017-08-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 718-728
Manuscript Number : CSEIT11724103
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

S. Ulaganathan, G. Raja Raja Cholan, "A Novel Per-Hop Per-Packet Delay Tomography in Wireless Ad Hoc Networks", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 4, pp.718-728, July-August-2017.
Journal URL : http://ijsrcseit.com/CSEIT11724103

Article Preview