Path Properties and Improvements of Sweep Circle Traversals

The rotational sweep algorithm (RS) solves the beaconless recovery problem in local minimum situations, which occur during Greedy routing. It routes a data packet around a void region using only two additional messages per hop, while guaranteeing packet delivery. In this context we present three related contributions: (1) When a sweep circle (SC) is used for RS, the resulting path coincides with the corresponding partial Delaunay triangulation Face traversal. Hence, SC traversals use edges of an Euclidean spanner and are therefore potentially very short. (2) We contrast this result by giving examples where RS performs particularly bad, when considering the Hop instead of the Euclidean metric. (3) To cope with this discrepancy, we devise a beaconless algorithm that helps to cut short in such situations and thereby helps to avoid unnecessary routing steps.