Combinatorial approaches to QoS scheduling in multichannel infrastructure wireless networks

We study the resource allocation problem in multi-tone frame based 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, and the number of channels m 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. Extensions of the basic formulation to scenarios where the clients use simple radios and to network scenarios where the clients can be multi-homed are presented. We discuss how the solution to the LP leads to a realizable schedule in all the above formulations. We also present a Mixed Integer Programming formulation for a scenario in which the signaling overhead incurred due to communication of these computed allocations is reduced, and provide initial directions on the joint power and slot assignment problem.