Decoupling link scheduling constraints in multi-hop packet radio networks
C.G. Prohazka · IEEE Transactions on Computers · 1989
An aspect of the problem of constructing a minimal length link schedule for a PRN (packet radio network) is examined. Specifically, it is assumed that a PRN of unrestricted topology is given, including a set of users, a set of channels, a set of interference links, a frequency band assignment, and an initial link schedule. It is required that any link schedule satisfies two constraints. The first is the transmission/reception constraint, namely that users cannot transmit and receive simultaneously and cannot transmit/receive more than one packet at a time. The second is the interference-free constraint, namely that no user interferes with any other. It is assumed that the initial link schedule satisfies the transmission/reception constraint, but not necessarily the interference-free constraint. Then it is shown that a simple modification of the initial link is needed to satisfy the latter constraint as well, i.e. the two constraints can be decoupled.>