Efficient Time-Based Topology-Dependent Scheduling for Radio Packet Networks

Abstract

In Radio Packet Network (RPN), unconstrained transmission may lead to collision of two or more packets. Time Division Multiple Access (TDMA) protocol is a common used protocol to schedule collision-free transmission for such networks. TDMA transmission allows a number of users to access a single radio channel without interference by allocating unique time slots to each user. In TDMA network, time is divided into frames and a frame consists of time slots. For networks where each node is a neighbor for all the other nodes, each node should assign a different time slot in TDMA frame to transmit in it to have collision-free transmission. Typically, those time slots are ended by \emph{guard times} for propagation delays. Those guard times are fixed for all time slots regardless the actual needed propagation delays.

In this paper, we propose a topology-dependent algorithm that automatically schedules collision-free channel access and specify the time instant when a node is to send a packet. We use variable guard times, instead of the fixed ones, calculated using the actual needed propagation delays between sources and destinations. We show that with such scheduling algorithm, a 90% saving in the original guard times could be achieved that increases the network utilization by about 10%. Also UMIACS-TR-2002-57