Distributed topology organization and transmission scheduling in wireless ad hoc networks

A wireless ad hoc network is a set of nodes that form an all-wireless infrastructure without the aid of any centralized administration. In this dissertation, we study two fundamental distributed resource allocation problems that arise in the ad hoc network setting: topology organization and transmission scheduling.; Topology organization is studied in the first part of the dissertation. We consider ad hoc networks where multiple channels are available and defined by distinct frequency hopping sequences. To address these issues, we first devise a symmetric technique where two nodes use a randomized schedule to synchronize and establish a link in minimum time. This method forms the basis of a distributed topology construction protocol that starts with a set of non-synchronized nodes and quickly forms a multi-channel ad hoc network satisfying certain connectivity or throughput requirements.; The second part of this dissertation introduces a novel distributed transmission scheduling framework for provision of Quality of Service (QoS) guarantees in wireless ad hoc networks.; We first relax on network-wide slot synchronization and study asynchronous TDMA ad hoc networks. We then introduce an asynchronous TDMA architecture for reaching global QoS objectives using only local information. The QoS objective is a set of link rates to be realized by a slotted network TDMA schedule where at each slot, several transmissions occur such that no conflicts occur at the intended receivers.; Both Constant Bit Rate (CBR) and Available Bit Rate (ABR) services are considered. We show that CBR service can be provided using simple admission control rules and QoS routing mechanisms, similar to wireline networks; for ABR service, we introduce an asynchronous distributed algorithm for computing session max-min fair rates. The session rates computed by the end-to-end bandwidth allocation algorithm are translated to link demands that must be enforced using a TDMA schedule. We solve this dynamic link scheduling problem for the special case of tree topologies and provide upper bounds on convergence delay.; An important feature of both our topology organization and transmission scheduling techniques is that they are amenable to distributed implementation on existing wireless technologies. To this end, we present an implementation and performance evaluation over Bluetooth, a wireless technology that enables ad hoc networking applications. (Abstract shortened by UMI.)...