Progressive decentralized TDMA based MAC: Joint optimization of slot allocation and frame lengths

The TDMA based MAC scheduling is considered appropriate for many applications in which deterministic medium access schedule plays a crucial role. The existing plentiful literature on the TDMA based scheduling focus on the conflict-free slot allocation where the scheduling problem is broken into two disjoint problems: first find conflict free slot allocation, minimizing the number of slots used, and subsequently select frame sizes in which to use the assigned slots. In this paper, we show that such a sequential approach could lead to suboptimal performance when analyzed from the perspective of slot or channel reuse, which is the prime objective of the spatial reuse TDMA schemes. To his end, we formulate the channel scheduling as an optimization problem that aims to maximize the slot reuse factor whereby we jointly optimize the slots assignment and the frame lengths. The problem being inherently NP-hard, to solve it we propose a greedy heuristic based algorithm by which nodes complete slot assignment in a progressive decentralized way. We show that under the proposed algorithm, all nodes are guaranteed to find a conflict-free transmission schedule. Besides, we provide upper bound on the convergence time of the algorithm for a single node, and for the whole network. Finally, with simulation examples, we show that the proposed algorithm when compared with other TDMA scheduling schemes could give better performance in terms of slot reuse factor.