On the route discovery rate of flooding in large wireless networks

In this paper, we derive the rate of route discovery process for finding a randomly chosen destination in large wireless networks. The well-known protocol for route discovery is flooding in which each node simply rebroadcasts the route request packet once. Rate of route discovery process is defined as the inverse of time between transmitting two successive route request packets which shows how fast a node can request a route to its destination. Discovery time is another parameter of interest. For a single node discovering routes to its destination, at most the rate of È (1/3√n) is feasible when n identical nodes are optimally placed in network area and the discovery time is of order È(3√n). Achievability of such rate is obtained through optimal placement and hierarchical scheduling of nodes transmissions.