Throughput versus routing overhead in large ad hoc networks
Radha Krishna Ganti, Martin Haenggi · International Wireless Internet Conference · 2008
Consider a wireless ad hoc network with n nodes distributed uniformly on [0, 1]2. The transport capacity (TC) of such a wireless network scales like √n. To achieve this, each node should serve about √n distinct information flows. So the routing table of each node should be of the order √n bits. We show that if the size of the routing table is restricted to be of the order O(nH(δ)), the maximum achievable pernode TC is O(nR(δ)) when the source-destination distance is n-δ/2. We show that R(δ) = min {1/2, δ/2 + H(δ)} - 1 is the optimal tradeoff.