Optimal broadcast scheduling in packet radio networks using mean field annealing

Packet radio (PR) is a technology that applies the packet switching technique to the broadcast radio environment In a PR network, a single high-speed wideband channel is shared by all PR stations. When a time-division multi-access protocol is used, the access to the channel by stations' transmissions must be properly scheduled in both time and space domains in order to avoid collisions or interferences. It is proven in this paper that such a scheduling problem is NP-complete. Therefore, an efficient polynomial algorithm rarely exists, and a mean field annealing-based algorithm is proposed to schedule the stations' transmissions in a frame consisting of certain number of time slots. Numerical examples and comparisons with some existing scheduling algorithms have shown that the proposed scheme can find near-optimal solutions with reasonable computational complexity. Both time delay and channel utilization are calculated based on the found schedules.