A Study about the Distribution of the Spanning Ratios of Yao Graphs

Authors: Maryam Hsaini, Mostafa Nouri-Baygi

Abstract:

A critical problem in wireless sensor networks is limited battery and memory of nodes. Therefore, each node in the network could maintain only a subset of its neighbors to communicate with. This will increase the battery usage in the network because each packet should take more hops to reach its destination. In order to tackle these problems, spanner graphs are defined. Since each node has a small degree in a spanner graph and the distance in the graph is not much greater than its actual geographical distance, spanner graphs are suitable candidates to be used for the topology of a wireless sensor network. In this paper, we study Yao graphs and their behavior for a randomly selected set of points. We generate several random point sets and compare the properties of their Yao graphs with the complete graph. Based on our data sets, we obtain several charts demonstrating how Yao graphs behave for a set of randomly chosen point set. As the results show, the stretch factor of a Yao graph follows a normal distribution. Furthermore, the stretch factor is in average far less than the worst case stretch factor proved for Yao graphs in previous results. Furthermore, we use Yao graph for a realistic point set and study its stretch factor in real world.

Keywords: Wireless sensor network, spanner graph, Yao Graph.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1474493

References:

[1] Deng, Jing, Yunghsiang Sam Han, Po-Ning Chen, and Pramod K. Varshney,"Optimum transmission range for wireless ad hoc networks," in Wireless Communications and Networking Conference, 2004, pp. 1024-1029.
[2] Nag Anindya, and Rajarshi Roy, "A Review of Energy Optimal Topology Control for Large Wireless Network Using Yao-Graph and Its Variants," International Journal on Smart Sensing & Intelligent Systems, 2014, vol. 7.
[3] Mohammad Ilyas and Imad Mahgoub, Handbook of sensor networks: compact wireless and wired sensing systems: CRC press 2004.
[4] El Molla, M. Nawar, Yao spanners for wireless ad hoc networks. Villanova University, 2009.
[5] Keng, Wah Loon, and Ge Xia," The Yao Graph Y5 is a Spanner” Department of Computer Science, Lafayette College, Easton, USA, 2013.
[6] Barba, Luis, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André Van Renssen, Perouz Taslakian, Sander Verdonschot, and Ge Xia,"New and improved spanning ratios for Yao graphs," in Proceedings of the thirtieth annual symposium on Computational geometry, 2014, p. 30.
[7] L. P. Chew. “There is a planar graph almost as good as the complete graph.” In Proceedings of the 2nd ACM Symposium on Computational Geometry, pages 169–177, 1986.
[8] D. Peleg and J. D. Ullman. “An optimal synchronizer for the hypercube.” In Proceedings of the 8th ACM Symposium on Principles of Distributed Computing, pages 77–85, 1987.
[9] D. Peleg and A. A. Schäffer. “Graph spanners.” Journal of Graph Theory, 13:99–116, 1989.
[10] J. Soares. “Graph spanners: A survey.” Congressus Numerantium, 89:225–238, 1992.
[11] M. Bern and D. Eppstein. “Approximation algorithms for geometric problems.” In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 296–345. PWS Publishing Company, Boston, MA, 1997.
[12] D. Eppstein. “Spanning trees and spanners.” In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425–461. Elsevier Science, Amsterdam, 2000.
[13] J. S. B. Mitchell. “Geometric shortest paths and network optimization.” In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633–701. Elsevier Science, Amsterdam, 2000.
[14] J. Gudmundsson and C. Knauer. “Dilation and detours in geometric networks.” In T. F. Gonzalez, editor, Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC, Boca Raton, FL, 2006.
[15] P. Bose and M. Smid. “On plane geometric spanners: A survey and open problems.” Computational Geometry, 2013, pp. 818-830.