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. / Thesis (Ph.D, Computing) -- Queen's University, 2009-11-25 21:04:37.0
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OKQ.1974/5335 |
| Date | 26 November 2009 |
| Creators | NUNEZ RODRIGUEZ, YURAI |
| Contributors | Queen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.)) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | 878283 bytes, application/pdf |
| Rights | 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. |
| Relation | Canadian theses |
Page generated in 0.002 seconds