Problems on Geometric Graphs with Applications to Wireless Networks
Loading...
Authors
Nunez Rodriguez, Yurai
Date
2009-11-26T22:49:00Z
Type
thesis
Language
eng
Keyword
Wireless Network , Geometric Graph , Computational Geometry , Algorithm , Distributed Algorithm
Alternative Title
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.
Description
Thesis (Ph.D, Computing) -- Queen's University, 2009-11-25 21:04:37.0
Citation
Publisher
License
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.