Theta-graphs that efficiently support local routing

Thumbnail Image

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-05-20

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

16

Series

Abstract

Consider a connected weighted graph G(V, E), where the nodes V are points (x, y) on a plane, and the edges E have weight equal to the Euclidean distance between their endpoints. The graph G is a t-spanner, if there is a path between any pair of nodes (u, w), with length at most t times their Euclidean distance. Spanners have applications in computational geometry and networking. One way to create spanners is to construct a Θk-graph, where the plane is divided into k cones around each node. This thesis is a literature review of suggested routing strategies for Θk-graphs, and the effects of the parameter k for effective routing. The goal of this thesis is to compare the strengths and weaknesses between these strategies, and to recommend best practices for constructing and routing Θk-graphs. The mathematical properties Θk-graphs and their variations have been studied for different values of k. Generally, a larger value of k creates a denser graph, but one that also guarantees the existence of a shorter path. The upper bounds for these path lengths are often proven in literature by showing that a particular routing strategy can find them. These strategies are often specialized for that particular type of graph and combine multiple simpler strategies into one. This thesis concludes that while common routing strategies usually have shortcomings when routing sparser Θk-graphs, hybrid strategies can be used on them. For routing Θk-graphs when k is large, θ-routing is suggested.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Kisfaludi-Bak, Sandor

Keywords

geometric spanner, t-spanner, Θ-graph, geometric routing, local routing

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202406184581

Collections

[kand] Perustieteiden korkeakoulu / SCI