Optimising expanding ring search for multi-hop wireless networks

Abstract

Expanding ring search (ERS) is a widely used technique to reduce broadcast overhead in multi-hop wireless networks (e.g., ad-hoc and sensor networks). ERS works by searching successively larger areas in the network centred around the source of broadcast. Network-wide broadcast is initiated only if L successive searches fail. This paper explores if there exists an optimal L that would minimise the broadcast cost of ERS. A theoretical model is developed to analyse the expected broadcast cost as a function of L. Using this model, we show that an optimal L exists for any random network topology. The analytical results are validated through extensive numerical experiments that consider a large number of random network topologies of varying sizes and hop lengths. By tuning the parameter L to the optimum value, broadcast cost can be reduced up to 52% depending on the topology.