An optimal topology-transparent scheduling method in multihop packet radio networks

Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time-division multiple-access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and do not adapt to different traffic requirements. Chlamtac and Farago (1994) proposed a topology-transparent algorithm. Following their approach, but with a different design strategy, we propose another algorithm which is optimal in that it maximizes the minimum throughput. We compare our algorithm with that of Chlamtac and Farago's and with the TDMA algorithm, and find that it gives better performance in terms of minimum throughput and minimum and maximum delay times. Our algorithm requires estimated values of the number of nodes and the maximum nodal degree in the network. However, we show that the performance of our algorithm is insensitive to these design parameters.