Show simple item record

dc.contributor.authorNunez Rodriguez, Yurai
dc.contributor.otherQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))en
dc.date2009-11-25 21:04:37.0en
dc.date.accessioned2009-11-26T22:49:00Z
dc.date.available2009-11-26T22:49:00Z
dc.date.issued2009-11-26T22:49:00Z
dc.identifier.urihttp://hdl.handle.net/1974/5335
dc.descriptionThesis (Ph.D, Computing) -- Queen's University, 2009-11-25 21:04:37.0en
dc.description.abstractIt 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.en
dc.format.extent878283 bytes
dc.format.mimetypeapplication/pdf
dc.languageenen
dc.language.isoenen
dc.relation.ispartofseriesCanadian thesesen
dc.rightsThis 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.en
dc.subjectWireless Networken
dc.subjectGeometric Graphen
dc.subjectComputational Geometryen
dc.subjectAlgorithmen
dc.subjectDistributed Algorithmen
dc.titleProblems on Geometric Graphs with Applications to Wireless Networksen
dc.typeThesisen
dc.description.degreePh.Den
dc.contributor.supervisorMeijer, Henken
dc.contributor.supervisorRappaport, Daviden
dc.contributor.departmentComputingen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record