Title

Combinatorial reverse auction-based scheduling in multirate wireless systems

Authors

Authors

S. Pal; S. R. Kundu; M. Chatterjee;S. K. Das

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

IEEE Trans. Comput.

Keywords

scheduling; multirate wireless system; reverse auction; performance; optimization; NETWORKS; Computer Science, Hardware & Architecture; Engineering, Electrical &; Electronic

Abstract

Opportunistic scheduling algorithms are effective in exploiting channel variations and maximizing system throughput in multirate wireless networks. However, most scheduling algorithms ignore the per-user quality-of-service ( QoS) requirements and try to allocate resources ( for example, the time slots) among multiple users. This leads to a phenomenon commonly referred to as the exposure problem, wherein the algorithms fail to satisfy the minimum slot requirements of the users due to substitutability and complementarity requirements of user slots. To eliminate this exposure problem, we propose a novel scheduling algorithm based on two-phase combinatorial reverse auction, with the primary objective of maximizing the number of satisfied users in the system. We also consider maximizing the system throughput as a secondary objective. In the proposed scheme, multiple users bid for the required number of time slots and the allocations are done to satisfy the two objectives in a sequential manner. We provide an approximate solution to the proposed scheduling problem, which is NP-complete. The proposed algorithm has an approximation ratio of (1 + log m) with respect to the optimal solution, where m is the number of slots in a schedule cycle. Simulation results are provided to compare the proposed scheduling algorithm with other competitive schemes.

Journal Title

Ieee Transactions on Computers

Volume

56

Issue/Number

10

Publication Date

1-1-2007

Document Type

Article

Language

English

First Page

1329

Last Page

1341

WOS Identifier

WOS:000248891000004

ISSN

0018-9340

Share

COinS