Forwarding Capacity in Large Wireless Multihop Networks - A Computational Approach

Wireless multihop networks are networks without any fixed infrastructure. This thesis concentrates on a network consisting of a plethora of immobile nodes communicating with each other over a shared wireless channel. The intrinsic nature of the shared wireless channel makes it difficult to efficiently avoid interference between the transmissions, and the exact capacity of such a network is in many respects an open question. At first, we characterize the capacity problem in a massively dense wireless network where a separation of scales emerges, and the problem can be separated into two different subproblems. The two subproblems loosely correspond to routing at the global scale and forwarding at the local scale. We focus on the latter one and study the microscopic level multidirectional forwarding capacity problem that considers an infinitely large network's capability to relay information. Because of the complexity of analyzing a large random network and wireless interference, the main approach is to construct algorithms that produce numerical bounds or estimates for the forwarding capacity, and simulate them for large network realizations. The methods used for studying the forwarding capacity are presented in two parts. The first part considers the instantaneous forwarding capacity. The instantaneous forwarding capacity can be achieved temporarily but cannot be maintained for a longer time period. It is a natural upper bound for the actual forwarding capacity and can be analyzed with more complex ways of modeling interference, such as the SINR-based models, in addition to the simple Boolean interference model. The actual forwarding capacity with multihop traffic under the Boolean interference model is considered in the second part. In this part, the upper bound provided by the instantaneous capacity is tightened for a small number of neighbor nodes, where it is less accurate. We also provide a lower bound that shows a notable improvement compared with previous results for uncoordinated opportunistic forwarding. Finally, an estimate is found for the forwarding capacity. The dependence of the estimate on the directional distribution of the traffic is studied to determine the possible gain from interleaving traffic in different directions compared with time sharing between the directions. Eventually, it is illustrated how the results for the forwarding capacity can be used with the macroscopic level results to obtain the total capacity of a large wireless network. The thesis hence makes it possible to calculate a numerical estimate for the total capacity.