An optimal scheduling algorithm in spatial TDMA mobile ad hoc network

Spatial TDMA (STDMA) is a “conflict-free” MAC protocol so that concurrent communication among the connected nodes. Therefore it can enable high spectral utilization, if optimal scheduling algorithm is achieved. As directional antenna technology developed, point to point transmission to other node could generate higher data transmission rate at the same time, lower interference with other nodes than omnidirectional antenna. Therefore an optimal scheduling algorithm needs to design to allocate the right slot to the right node in order to achieve high efficiency spatial reuse. To achieve this aim, we propose a new optimal scheduling algorithm: Max Spatial Reuse Scheduling Algorithm (MARSA). By using of directional antenna, it allows 1-hop distance neighbor node communication with other node in same slot unless one node connect to two node. Thus this concurrent scheduling algorithm allows more node communication with other nodes in one slot. Our method based on communication graph can be achieved with low complexity.