Problems on Geometric Graphs with Applications to Wireless Networks

Abstract

It is hard to imagine the modern world without wireless communication. Wireless networks are, however, challenging inasmuch as they are useful. Because of their complexity, wireless networks have introduced a myriad of new problems into the field of algorithms. To tackle the new computational challenges, specific models have been devised to suit wireless networks. Most remarkably, wireless networks can be modelled as geometric graphs. This allows us to address problems in wireless networks using tools from the fields of graph theory, graph algorithms, and computational geometry. Our results have applications to routing, coverage detection, data collection, and fault recovery, among other issues in this area.

To be more specific, we investigate three major problems: a geometric approach to fault recovery; the distributed computation of Voronoi diagrams; and finding Hamiltonian cycles in hexagonal networks. Our geometric approach to fault recovery has been experimentally proved superior to an existing combinatorial approach. The distributed algorithm we propose for computing Voronoi diagrams of networks is the first non-trivial algorithm that has been proved to perform this task correctly; its efficiency has been demonstrated through simulations. Regarding the Hamiltonian cycle problem of hexagonal networks, we have advanced this topic by providing conditions for the existence of such a cycle, in addition to new insight on its complexity for the "solid" hexagonal grid case. Although we present satisfying solutions to several of the addressed problems, plenty is left to be done. In this regard, we identify a set of open problems that will be subject of research for years to come.