A new model for scheduling packet radio networks

Abstract

Packet radio networks are modeled as arbitrary graphs by most researchers. We show that an arbitrary graph is an inaccurate model of the radio networks. This is true because there exists a large class of graphs which will not model the radio networks. Radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. Since the radio networks can accurately be modeled only by a restricted class of graphs, the NP-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. We study the broadcast scheduling problem using the restricted class as the model. We show that the problem remains NP-complete even in this restricted domain. We give an O(nlogn) algorithm when all the transceivers are located on a line. We restrict our attention to static allocation in general and TDMA in particular. However, it may be noted that the results presented are also valid for other static allocation schemes.