Title

Combinatorial Reverse Auction Based Scheduling In Multirate Wireless Systems

Keywords

Multi-rate wireless system; Performance optimization; Reverse auction; Scheduling

Abstract

Opportunistic scheduling algorithms are effective in exploiting channel variations and maximizing system throughput in multi-rate wireless networks. However, most scheduling algorithms ignore the per-user quality of service (QoS) requirements and try to allocate resources (e.g., 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 to maximize 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. © 2007 IEEE.

Publication Date

10-1-2007

Publication Title

IEEE Transactions on Computers

Volume

56

Issue

10

Number of Pages

1329-1341

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TC.2007.1082

Socpus ID

34548797095 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/34548797095

This document is currently not available here.

Share

COinS