An incremental algorithm for broadcast scheduling in packet radio networks

Packet radio networks hold great promise for providing easy to use, mobile military communications services. However, supporting mobility with packet radio networks poses many technical challenges. One of these challenges, to dynamically and quickly adjust schedules for fixed channel access by way of TDMA/FDMA/CDMA in a large dynamic network, is the focus of this paper. In such broadcast scheduling it is required that the transmission of a given station be received collision free by all of the stations that are within its transmission range. The goal in broadcast scheduling is to produce a conflict free static schedule of minimum length in which each station is given a chance, a time slot in TDMA for example, to broadcast its packets. Unfortunately, all of the existing broadcast scheduling algorithms are off-line. As such, whenever a change occurs in the topology of the network, these algorithms recompute the schedule for the entire network. As radio networks evolve in the direction of thousands of stations spread over a broad geographical area and operating in an unpredictable dynamic environment (imagine a battlefield) the cost of full schedule recomputation whenever the network topology changes (by even a single node) is unacceptable. In this situation, incremental algorithms are needed. Such algorithms accommodate topological changes by adapting the existing schedule, rather than rebuilding the schedule from scratch. The twin objectives of incremental algorithms are much faster execution (than an off-line algorithm) and the production of a high quality schedule. In this paper we establish the feasibility of simultaneously meeting these twin objectives, by presenting an incremental algorithm for broadcast scheduling