| An intrinsic characteristic of wireless networks is the lack of a rigid infrastructure. While this does in the first place create many design challenges that need to be overcome, it also gives rise to numerous opportunities that one can exploit in order to improve the performance of the underlying network. The goal of this thesis is to investigate two specific issues that arise from this lack of infrastructure.; We first tackle a very basic problem that literally originates from the wireless nature of the communications between nodes. In particular, the absence of wires to specify ahead of time which nodes are connected to which, presents both an opportunity and a challenge. As a result, we first consider the very basic task of topology formation, which can in broad terms be described as choosing which nodes should establish logical "wires" between them, i.e., which nodes should connect to each other. We approach this problem from an algorithmic perspective, and by using a specific wireless technology, namely Bluetooth, we investigate the implications that deciding which wires/links to enable has on our ability to create large-scale ad hoc networks using this technology. We show that simply deciding whether a connected topology is feasible is itself an NP-hard problem. We then develop several algorithms that either guarantee a connected topology under certain simplifying assumptions, or if unable to guarantee a connected topology, actually succeed at establishing one most of the time. We compare these algorithms to several others that are available in the literature, and conclude that for large topologies, i.e., for a large number of nodes, they all face similar issues that stem from the design choices Bluetooth made. This investigation provided insight into issues associated with the use of wireless communications in building large ad hoc networks, and in particular the impact that specific communication layer design choices can have on upper layers, including the network layer. We concluded that while Bluetooth might be a suitable wireless technology for small networks, it is unlikely to succeed in building large ad hoc networks.; The second area we focus on is one that explores how to best take advantage of a natural strength of wireless communications, namely the availability of multiple transmission paths between senders and receivers. We ask why, how, when, and to what extent can these multiple paths be exploited in order to improve performance. We propose simple open-loop path diversity techniques that rely on minimal knowledge of the channel characteristics, and significantly improve performance in settings where retransmissions are either impractical or detrimental to application quality, i.e., as with real-time applications. Our main contribution is in showing that how to achieve the best possible performance often relies on somewhat counterintuitive uses of the available channels, and in introducing the concept of "equivalent" channels to broadly characterize the channel scenarios in which diversity yields meaningful benefits. We explore how those benefits evolve as the underlying system parameters change, investigate the robustness of those benefits to changes in channel characteristics, and develop simple heuristics for quickly identifying how to use the available channels. Additionally, we present experimental results which evaluate the magnitude of these benefits in a realistic IEEE 802.11 setting. |
