Abstract: 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.