Scheduling Algorithms for Point-to-Multipoint Operation in IEEE 802.16 Networks

We study the resource allocation problem in OFDMA based 802.16 broadband wireless access systems. Frequency and time resources must be allocated by a central controller (Base Station) to a number of users. We consider variations of a resource allocation problem, some of which are difficult to solve. Situations in which only the objective of the Base Station need to be maximized are easily dealt with as are cases where all the users perceive the same channel conditions. Scenarios where both the objectives of the BS as well as those of the end users must be met simultaneously require more complicated solutions since individual users experience different channel conditions. We present linear programming relaxations for the resource allocation problem. While solving the LP using standard techniques like ellipsoidal algorithm can provide optimal allocations for all users, it can be expensive in terms of computing overhead as the number of users in the system increase. Therefore we present an efficient algorithm which performs well even as the number of clients n in the system increases. We also present a heuristic based on the interpretation of the linear programming relaxation as a concurrent flow problem. We note that in numerical experiments, the performance of the heuristic closely matches the optimal solution to the linear programming relaxation.