In this work we develop a new theory to analyse the process of routing in large-scale ad-hoc wireless networks. We use a path integral formulation to examine the properties of the paths generated by different routing strategies in these kinds of networks. Using this theoretical framework, we calculate the statistical distribution of the distances between any source to any destination in the network, hence we are able to deduce a length parameter that is unique for each routing strategy. This parameter, defined as the effective radius, effectively encodes the routing information required by a node. Analysing the afore- mentioned statistical distribution for different routing strategies, we obtain a threefold result for practical Large-Scale Wireless Ad-Hoc Networks: 1) We obtain the distribution of the lengths of all the paths in a network for any given routing strategy, 2) We are able to identify "good" routing strategies depending on the evolution of its effective radius as the number of nodes, N , increases to infinity, 3) For any routing strategy with finit e effective radius, we demonstrate that, in a large-scale network, is equivalent to a random routing strategy and that its transport capacity scales asp Nbit-meters per second, thus retrieving the scaling law that Gupta and Kumar (2000) obtained as the limit for single-route large-scale wireless networks.
In this paper we study the lengths of the routes in ad hoc networks. We propose a simplified theoretical model having as objective to estimate the path length for the routing protocols that are using flooding during their path discovery phase. We show how to evaluate the average gain in the hop number that one can obtain by using a simple reduction strategy. We prove the gain to be linear under very general conditions and show how it can be computed practically. The probability distribution is found for the link distance between two randomly positioned mobile radios in a wireless network for two representative deployment scenarios: (1) the mobile locations are uniformly distributed over a rectangular area and (2) the x and y coordinates of the mobile locations have Gaussian distributions. It is shown that the shapes of the link distance distributions for these scenarios are very similar when the width of the rectangular area in the first scenario is taken to be about three times the standard deviation of the location distribution in the second scenario. Thus the choice of mobile location distribution is not critical, but can be selected for the convenience of other aspects of the analysis or simulation of the mobile system.