Geometric ad-hoc routing

TLDR

A persistent gap between theory and practice exists in ad‑hoc routing. This paper proposes a new geometric routing algorithm that is both highly efficient on average‑case networks and asymptotically worst‑case optimal, thereby narrowing that gap. The algorithm operates without a minimum node‑distance assumption and classifies routing cost metrics into two fundamentally different categories. It successfully removes the previously required minimum node‑distance assumption, enabling practical deployment.

Abstract

All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentamentally different classes of cost metrics for routing in ad-hoc networks.