Title :
A sequential approach for optimal broadcast scheduling in packet radio networks
Author_Institution :
Sch. of Manage., Univ. of Texas at Dallas, Richardson, TX
fDate :
3/1/2009 12:00:00 AM
Abstract :
An important problem that arises in the design of packet radio networks is that of scheduling access to the high speed communications channel in such a way as to avoid interference while keeping the frame length to a minimum. The broadcast scheduling problem is known to be NP-hard and to date, this problem has been formulated as a nonlinear discrete optimization problem for a given frame length, and solved via heuristic approaches by parametrically varying the length of the frame. This paper presents a linear integer programming formulation for the composite problem of maximizing channel utilization while minimizing the length of the frame. It then introduces a solution approach based on solving two relatively easier (though still NP-complete) integer programs in succession. Computational experiments are conducted on a set of benchmark cases and additional randomly generated problem instances. Results show that this sequential integer programming approach is very effective, solving all the problems optimally within a few seconds. These results imply that optimal solutions can be identified in very little time for problems of realistic size, and that heuristic approaches will be needed only when problems get much larger than those considered in the literature to date.
Keywords :
computational complexity; integer programming; interference suppression; optimisation; packet radio networks; radiofrequency interference; scheduling; wireless channels; NP-hard problem; broadcast scheduling problem; heuristic approaches; high speed communications channel; interference avoidance; linear integer programming formulation; nonlinear discrete optimization; optimal broadcast scheduling; packet radio networks; Communication channels; Genetic algorithms; Helium; Interference; Linear programming; Packet radio networks; Protocols; Radio broadcasting; Radio network; Scheduling algorithm; Broadcast scheduling, integer programming, sequential solution, decomposition, public radio networks;
Journal_Title :
Communications, IEEE Transactions on
DOI :
10.1109/TCOMM.2009.03.070082