A framework for frameless TDMA using slot chains

TDMA MAC protocols suffer from two draw-backs that have reduced its practical appeal, especially for infrastructure-less wireless networks: the need for time synchronization, and the use of Jrames. While there has been extensive research towards achieving the required time synchronization, the frames are assumed to be inherent in TDMA. In this paper we present a framework for frameless TDMA based on a new concept we refer to as a slot chain. A slot chain is a series of slots with a starting slot and inter-slot period that is chosen to match a given capacity request. The key challenge in using slot chains instead of frames is ensuring that slot chains representing arbitrary capacity requests are conflict free. We present an algorithm for interleaving slot chains in a conflict-free manner. The algorithm is optimal for a class of requests called geometric and is z-approximate for general requests, where z can be made arbitrarily small. We show that any TDMA MAC protocol can readily replace using frames with using slot chains. Our simulation analysis shows that using slot chains results in much better capacity utilization when traffic is heterogeneous - as much as 100% in some cases.