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.
Since ad hoc and sensor networks can be composed of a very large number of devices, the scalability of network protocols is a major design concern. Furthermore, network protocols must be designed to prolong the battery lifetime of the devices. However, most existing routing techniques for ad hoc networks are known not to scale well. On the other hand, the so-called geographical routing algorithms are known to be scalable but their energy efficiency has never been extensively and comparatively studied. In a geographical routing algorithm, data packets are forwarded by a node to its neighbor based on their respective positions. The neighborhood of each node is constituted by the nodes that lie within a certain radio range. Thus, from the perspective of a node forwarding a packet, the next hop depends on the width of the neighborhood it perceives. The analytical framework proposed in this paper allows to analyze the relationship between the energy efficiency of the routing tasks and the extension of the range of the topology knowledge for each node. A wider topology knowledge may improve the energy efficiency of the routing tasks but increases the cost of topology information due to signaling packets needed to acquire this information. The problem of determining the optimal topology knowledge range for each node to make energy efficient geographical routing decisions is tackled by integer linear programming. It is shown that the problem is intrinsically localized, i.e., a limited topology knowledge is sufficient to make energy efficient forwarding decisions. The leading forwarding rules for geographical routing are compared in this framework, and the energy efficiency of each of them is studied. Moreover, a new forwarding scheme, partial topology knowledge forwarding (PTKF), is introduced, and shown to outperform other existing schemes in typical application scenarios. A probe-based distributed protocol for knowledge range adjustment (PRADA) is finally introduced that allows each node to efficiently select online its topology knowledge range. PRADA is shown to rapidly converge to a near-optimal solution.