Ein Reaktiver Algorithmus für Geografisches Clustering
- Beaconlose geografische Routingverfahren für Unit-Disk Graphen basieren auf einer beaconlosen Strategie und bieten einen Ansatz zur Verbesserung von lokalen Routingverfahren für Quasi-Unit-Disk Graphen. Der Großteil der lokalen geografischen Routingverfahren für Quasi-Unit-Disk Graphen benötigt 2-lokale Nachbarschaftsinformation und verursacht einen Nachrichtenoverhead. Der in dieser Arbeit entwickelte Beaconlose Clustering Algorithmus zeigt, dass sich Nachrichtenoverhead und Energieverbrauch eines bestehenden nicht beaconlosen Verfahrens mittels beaconloser Strategie optimieren lassen. Der Beaconlose Clustering Algorithmus basiert auf einem geografischen Clustering und konstruiert eine lokale Sicht auf einen ausgedünnten Graphen mit einer konstanten Anzahl von Knoten pro Flächeneinheit. Neben der detaillierten Beschreibung des Algorithmus beinhaltet diese Arbeit einen Korrektheitsbeweis und eine Implementierung mit anschließender Simulation zur Untersuchung der Verbesserung des bestehenden Verfahrens.
- Existing algorithms using a beaconless strategy for geographic routing in Unit-Disk Graphs offer an approach for improving non-beaconless routing algorithms for Quasi-Unit-Disk Graphs. The majority of the aforementioned non-beaconlessrnrouting algorithms for Quasi-Unit-Disk Graphs are based on collecting 2-hop neighbourhood information. As shown by the Beaconless Clustering Algorithm developed in this thesis, a beaconless strategy can be used to enhance an existing non-beaconless algorithm by reducing message overhead and power consumption. The Beaconless Clustering algorithm is based on geographic clustering and constructs a sparse graph with constant number of vertices per unit area. The thesis at hand contains a detailed description of the algorithm, a proof of correctness and a simulation for presenting reachable improvements.