Yao Graphs in Ad Hoc Networks
Wireless nodes are often powered by batteries and have limited memory resources. These characteristics make it critical to compute and maintain, at each node, only a subset of neighbors that the node communicates with. The collection of nodes and their neighbors define a graph called topology graph. An important topology graphs is the Yao graph, which can be constructed and updated efficiently in a dynamic environment. Let P be a set of points in the plane representing wireless devices. The Yao graph Yk(P), for k > 2, is defined as follows. At each point u 2 P, any k equal-separated rays originated at u define k cones; the Yao graph Yk contains edges connecting u to a nearest neighbor in each nonempty cone, for a total of at most k edges incident to u. It is a standing open problem to determine whether the Yao graph Yk is a t-spanner, for some constant t > 0 and k < 6: for any pair of vertices u, v 2 P, the shortest path in Yk from u to v is no longer than t times the Euclidean distance between u and v. We make progress towards resolving this problem by showing that Y4 is a (12 + 10p2)-spanner for sets of points in convex position. For a fixed vertex pair u, v 2 P, our method constructs a path of Yao edges confined to the smallest square square passing through u and v, and defines a relationship between the length of this path and the boundary of the square. We also show that a related Yao-based graph, called Yao-Yao, is a spanner for point sets of bounded aspect ratio.
Delaunay Triangulation in Ad Hoc Networks
In this research we experimentally try to determine whether a particular conjecture concerning the Delaunay triangulation of a random point set is true or false. It has been shown in past research that a lower bound value for the stretch factor for a Delaunay triangulation is approximately π/2. The conjecture we set out to disprove is whether the Delaunay triangulation is a π/2 spanner. We also specialize this conjecture for points in convex position and show that, for two points that lie on the convex hull of the Delaunay triangulation, the shortest path connecting these points is less than or equal to the direct distance between those same two points times π/2.