Performance analysis of expanding ring search for multi-hop wireless networks

Expanding ring search (ERS) is a powerful technique used frequently in multi-hop wireless networks for optimising the broadcast cost of searching. How many times to search using ERS, i.e., the search threshold L, is an interesting open question. Various work found in the literature reports an arbitrary value of the search threshold. In this paper, we analyse the impact of L on the performance of ERS by modeling three different regular network topologies - circular, grid, and hexagonal. We have also carried out a pilot study on nonregular (random) topologies. Our analysis of regular topologies suggests that although it is possible to reduce the network-wide broadcast overhead with ERS by carefully selecting parameter L, the overhead reduction is only marginal. We, however, find that for random topologies, ERS may be very effective in reducing broadcast overhead. We also present guidelines for selecting L for both regular and non-regular topologies.