Local Routing in Convex Subdivisions

Prosenjit Bose, Stephane Durocher, Debajyoti Mondal, Maxime Peabody, Matthew Skala, Mohammad Abdul Wahid

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review


In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required Θ(logn) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and the first local geometric memoryless routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions) when the algorithm has knowledge of the incoming port (the preceding node on the route).
BogserieLecture Notes in Computer Science
Sider (fra-til)140
Antal sider151
StatusUdgivet - 2015
Udgivet eksterntJa


Dyk ned i forskningsemnerne om 'Local Routing in Convex Subdivisions'. Sammen danner de et unikt fingeraftryk.