On the capacity of multihop wireless networks: Fundamental limitations and efficient algorithms
Riedi, Rudolf H.
Doctor of Philosophy
Wireless networks are rapidly becoming a major component of the modern communications infrastructure competing with wireline networking. The and of this thesis is to study the capacity, fundamental limitations, and the throughput of a number of protocols in multihop wireless networks. To this end, we introduce novel frameworks and powerful tools for analyzing throughput and the effect of various network protocols. In the first part of the thesis, we study broadcast in wireless networks in several complementary directions. We start by proposing three novel broadcast schemes for ad hoc networks which combine low overhead with robustness and are provably efficient. Next, we study the dynamics of broadcast flooding under a realistic MAC model in large wireless networks. We find conditions on survivability and coverage of flooding, and prove that flooding disseminates the information in almost constant speed. Then, we introduce and compute the broadcast capacity for multihop wireless networks. We show that the broadcast capacity is proportional to the wireless channel bandwidth. Moreover, we demonstrate that only the broadcasts schemes with efficient backbone can achieve a throughput close to the broadcast capacity. By applying these results, we are able to analytically evaluate the throughput and the effect of broadcast applications in arbitrary wireless networks. In the second part of the thesis, we generalize our study from broadcast to unicast and multicast in wireless networks. We introduce novel analytical tools for analyzing the capacity of arbitrary wireless networks. We provide some tight and sensitive bounds on the network capacity for unicast and nnilticast applications which depend on topology and traffic pattern of the network. Furthermore, we add another dimension to our work by allowing network coding among the nodes. We investigate the benefit of network coding for some popular scenarios in wireless networks, and demonstrate that the network coding gain is limited by a constant factor. We identify wireless channel interference, network topology, and traffic pattern as the determining parameters on the capacity of wireless networks. Finally, we discuss how the relevant results of this thesis can be used for design and development of wireless networks in some particular network scenarios.