Performance trade-offs in large wireless networks

Recent technological advances have spurred interest in large wireless networks without fixed infrastructure. This work uses a random network model and characterizes the fundamental performance limits of such large wireless networks in terms of the scaling of optimal performance with the number of nodes in the network. The performance metrics include throughput (communication rate), delay, and energy consumption. It is shown that cooperation between nodes, by relaying data for each other, results in the best possible performance, although performance inevitably degrades as the number of nodes in the network increase.; Gupta and Kumar (2000) showed that in static networks, the highest achievable throughput is of order 1/nlogn . This work shows that for any lower throughput, the optimal delay is of order n times the throughput. This work also establishes the optimal trade-offs between throughput, delay, and energy consumption for static networks. Grossglauser and Tse (2001) showed that a constant throughput scaling is achievable in a network with mobile nodes, however, the corresponding delay was not known. This work models the mobility of nodes as a random walk on the discrete torus and shows that the corresponding delay is of order n log n. The optimal throughput-delay tradeoff for mobile networks is also established. For any throughput of order 1/nlogn or lower, the throughput-delay trade-off is the same as in static networks. Somewhat surprisingly, this trade-off reveals that any throughput higher than that achievable in static networks is accompanied by a delay of order n log n. The effect of restricted mobility on throughput and delay is also investigated. The techniques used to establish these results belong to several areas such as analysis of algorithms, probabilistic analysis, Markov chains., queuing theory, and random walks.