Broadcast scheduling in multi-hop packet radio networks

Packet radio networks (PRN) are an important component of modern wireless and mobile communication systems. However, multi-hopping and the unpredictable operational environment of PRNs pose considerable technical challenges in the implementation of appropriate packet radio networks. One of the most difficult of these challenges resides in the design of a channel access control protocol to meet application requirements while maintaining acceptable performance even in extreme cases. Many algorithms for medium access control of a multiple access channel are known. Unfortunately, none of these existing methods are well suited to the environment of large broadcast multi-hop PRNs. This situation requires the development of new methods.; The focus of this research is on the development and evaluation of broadcast scheduling techniques in multi-hop PRNs. Of particular concern are on-line algorithms and adaptive protocols. (1) The on-line algorithms that we develop accommodate topological changes by adapting the existing schedule, rather than completely rebuilding the schedule. As such, these algorithms provide rapid responses to environmental changes. In addition, these algorithms are theoretically strong in the sense that they have constant performance ratios in unit disk graphs—a reasonable and widely assumed model for packet radio network topologies—and have running times that are polynomial in the size of the neighborhood where the change occurs. More significantly, our experiments establish that the algorithms have good practical performances compared to the performances of the best off-line algorithms. (2) The fully distributed protocol for adaptive broadcast scheduling that we describe is comprehensive in: having each station determine its own slot(s) in the schedule; allowing multiple stations to simultaneously run the scheduler portion of the protocol; allowing stations in non-local portions of the network to remain operating even while other stations are joining or leaving the network; and being adaptive to dynamic user traffic requirements.; In addition to the study of the algorithms and protocols, we also study the general issue of the effectiveness of broadcast scheduling in a multi-hop environment. In so doing, we utilize an embedded Markov-chain approach to determine the steady state throughput-delay characteristics for broadcast scheduling in multi-hop packet radio networks. We likewise take a Markov chain approach to find the steady state throughput-delay performance of an ALOHA based random access method that is adapted for use in a broadcast multi-hop PRN. This comparison study establishes that broadcast scheduling has superior throughput and delay performance than does the random access method when the network is moderately loaded.