A topology-independent TDMA transmission scheduling algorithm in wireless multihop networks

A new topology-independent transmission scheduling algorithm, called S-PRS scheduling algorithm, for TDMA wireless multihop networks is presented. In the S-PRS scheduling algorithm, each node is assigned a unique transmission scheduling vector that deterministically specifies the slots in which the user is authorized to transmit. We prove that this algorithm is topology transparent, and guarantees that each node has at least one collision-free slot in each frame for any neighbor. This characteristic makes it suitable for a high mobility network environment. The scheduling algorithm proposed can provide much higher throughput and better sharing of channel resources than a simple-PRS (proper robust schedule) algorithm with spatial slot reuse.