We first identify an inherent trade-off between the degree of topology control and fraction of feasible allocations that can be captured by the local conditions. We show that tree topologies can be maximally utilized in this respect and that a converging distributed link scheduling algorithm exists in this case.

Decoupling end-to-end bandwidth allocation from link scheduling allows support of various end-to-end QoS objectives. Focusing on Available Bit Rate (ABR) service, we design an asynchronous distributed algorithm for sharing bandwidth to the sessions in a maxmin fair (MMF) manner.

Finally, we present the implementation of this framework over Bluetooth, an existing wireless technology that enables the formation of ad hoc networks. This implementation is free of the usual restrictive assumptions of previous TDMA approaches: it does not require any a-priori knowledge on the number of nodes in the network nor even network-wide slot synchronization.

First we introduce a fluid model of the system where the conflict avoidance requirements of neighboring links are relaxed while the aspect of local channel sharing is captured. In that model we propose an algorithm where the nodes asynchronously re-adjust the rates allocated to their adjacent links based only on local information. We prove that from any initial condition the algorithm finds the max-min fair rate allocation in the fluid model. Hence if the iteration is performed constantly the rate allocation will track the optimal even in regimes of constant topology changes.

Then we consider the slotted system and propose a modification method that applies directly on the slotted schedule, emulating the effect of the rate re-adjusment iteration of the fluid model. Through extensive experiments in networks with fixed and time varying topologies we show that the latter algorithm achieves balanced rate allocation in the actual slotted system that are very close to the max-min fair rates. The experiments show also that the algorithm is very robust on topology variations, with very good tracking properties of the max-min fair rate allocation.

The problem is investigated for the case of Bluetooth, a newpromising TDMA wireless technology that enables the formation ofad hoc networks called scatternets. A scatternet does not supporta global slot synchronization mechanism. Instead, nodes aregrouped in multiple channels called piconets and each piconet usesa different time slot reference provided by a node designated asmaster. Traffic forwarding between piconets is performed in a timedivision fashion by bridge nodes that are aware of the timereferences of the piconets they participate in. Due to theinherent lack of global synchronicity, slots are wasted whenbridges switch piconet time references. This translates to abandwidth loss compared to an ideally synchronized scatternet.While the existence of this asynchronicity overhead has beenreported in previous work, there has been no effort to minimize itor even evaluate its possible extent. Nevertheless, these issuesare very important for the deployment of practical TDMA-based adhoc networks.

We consider a scatternet that allocates bandwidth to its linksusing an asynchronous periodic conflict-free TDMA schedule. Inthis setting the asynchronicity overhead is manifested as anincrease in the minimum period required to realize a demandallocation when compared to a perfectly synchronized system.

We first derive a general upper bound on the overhead of anyscatternet and demand allocation. Then we consider the problem ofminimizing the overhead given a scatternet configuration anddemand allocation on its links. We cast this as a combinatorialoptimization problem and propose two algorithms for its solution.The first algorithm reaches the optimal solution using exhaustivesearch. However this approach can be computationally prohibitivefor large problem sizes. To this end, we introduce a secondpractical heuristic algorithm of polynomial complexity. Usingsimulations, the heuristic is shown to perform very well forproblem sizes where the optimal can be computed. For large problemsizes we use the heuristic to investigate the effect of thevarious system parameters on the generated overhead and evaluateits performance with respect to the derived general upper bound.

Bluetooth is a promising new wireless technology that enables portable devices to form short-range wireless ad hoc networks and is based on a frequency hopping physical layer. This fact implies that hosts are not able to communicate unless they have previously discovered each other by synchronizing their frequency hopping patterns. Thus, even if all nodes are within direct communication range of each other, only those nodes which are synchronized with the transmitter can hear the transmission.

To support any-to-any communication, nodes must be synchronized so that the pairs of nodes (which can communicate with each other) together form a connected graph.

Using Bluetooth as an example, this paper first provides deeper insights into the issue to link establishment in frequency hopping wireless systems. It then introduces the Bluetooth Topology Costruction Protocol (BTCP), an asynchronous distributed protocol for constructing scatternets which starts with nodes that have no knowledge of their surroundings and terminates with the formation of a connected network satisfying all connectivity constraints posed by the Bluetooth technology.

To the best of our knowledge, the work presented in this paper is the first attempt at building Bluetooth scatternets using distributed logic and is quite "practical" in the sense that it can be implemented using the communication primitives offered by the Bluetooth 1.0 specifications.

This thesis attempts to address the scalability issue by introducing a framework and strategiesto quantify the concept of destination caching. The observation that a source host can augmentits cache's routing table by using the caches of other closely situated hosts forms the basisof our approach. We propose algorithms that determine a host's cached information by takinginto account the host's memory capacity, the network size and the number and identity of thedestinations this host needs to cache information about.

Mainly two classes of algorithms are introduced. The class of "Best State/Best Cost" algorithms(BSBC) tries to minimize the flooding cost per route discovery by keeping the most "expensive"destinations in each host's cache. However it does not impose any flooding constraints for thenon-cached destinations. The second class of LEADERS algorithms adopts a different view by relaxingon the flooding cost optimality and taking into account a maximum flooding constraint for each node.In this way, the worst flooding case is controlled since any node is guaranteed to find informationabout any destination within a pre-specified maximum distance.