Flooding strategy for target discovery in wireless networks

Abstract

In this paper, we address a fundamental problem concerning the best flooding strategy to minimize cost and latency for target discovery in wireless networks. Should we flood the network only once to search for the target, or should we apply a so-called "expansion ring" mechanism to reduce the cost? If the "expansion ring" mechanism is better in terms of the average cost, how many rings should there be and what should be the radius of each ring? We separate wireless networks based on network scale and flooding control methods and explore these questions. We prove that when using a geography-based flooding control method, the number of flooding attempts should be one. When using a hop-based flooding control method, we prove that two-tier and three-tier schemes can reduce the cost of flooding compared to a single attempt. We provide a general formula to determine good parameters for the two-tier and threetier hop-based flooding schemes. Through simulations, we show that choosing flooding parameters according to our techniques gives performance close to that of ideal flooding schemes. Also, we present some preliminary results on flooding strategy with caching and show that a properly chosen searching radius can save much more query overhead than a simple radius selection scheme.