The Critical Neighbourhood Range for Asymptotic Overlay Connectivity in Ad Hoc Networks

We first motivate the use of ad hoc overlays. In particular, we argue that overlay routing could play a role in the spreading of ad hoc networks. We then define a simple criterion for neighbourhood: two overlay nodes are neighbours if and only if there exists a path between them of at most R hops, and R is called the (overlay) neighbourhood range. A small R may result in a disconnected overlay, while an unnecessarily large R would generate extra control traffic. We are interested in the minimum R ensuring overlay connectivity, the so-called critical R. We study conditions on R to achieve asymptotic connectivity of the overlay almost surely, i.e. connectivity with probability 1 when the number of nodes in the underlying ad hoc network tends to infinity (so-called dense networks) or when the size of the field tends to infinity (socalled sparse networks), under the hypothesis that the underlying ad hoc network is itself asymptotically almost surely connected. For dense networks, we derive a necessary and sufficient condition on R, and for sparse networks we derive distinct necessary and sufficient conditions that are however asymptotically tight. These conditions, though asymptotic, shed some light on the relation linking the critical R to the number of nodes n, the field size the radio transmission range r and the overlay density D (i.e., the proportion of overlay nodes). These conditions can be considered as approximations when the number of nodes (resp. the field) is large enough. Since r is considered as a function of n or l , we are able to study the impact of topology control mechanisms, by showing how the shape of this function impacts the critical R.