Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper we study the online spectrum scheduling using a market driven approach. We assume that each new arrival spectrum request, when it arrives, requests for the exclusive usage of some channels for a certain time interval. The spectrum owner has to decide immediately whether to grant its exclusive usage or not. If it is granted, the secondary user will be charged a payment. We assume that existing running requests can be preempted with a penalty depending on its bid value, its requested time duration and the remaining unserved time. For various possible known information, we present efficient scheduling algorithms to schedule requests and prove that the competitive ratios of our methods are asymptotically optimum, i.e., within small constant factors of the optimum online methods. Our extensive simulations show that our algorithms perform almost optimum: most of our methods can get a total profit that is more than 80% of the optimum.

REFERENCES

• 1: Susanne Albers, Better bounds for online scheduling, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.130-139, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258566]
• 2: Yair Bartal , Stefano Leonardi , Alberto Marchetti-Spaccamela , Jiří Sgall , Leen Stougie, Multiprocessor scheduling with rejection, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.95-103, January 28-30, 1996, Atlanta, Georgia, United States
• 3: S. Baruah , G. Koren , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha, On-line scheduling in the presence of overload, Proceedings of the 32nd annual symposium on Foundations of computer science, p.100-110, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185354]
• 4: Fleischer, R., and Wahl, M. On-line scheduling revisited. J. of Scheduling 3, 343--353 (2000).
• 5: Michel X. Goemans, A Supermodular Relaxation for Scheduling with Release Dates, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.288-300, June 03-05, 1996
• 6: Goemans, M. X., Wein, J. M., and Williamson, D. P. A 1.47-approximation algorithm for a preemptive single-machine scheduling problem. Operations Research Letters 26, 4 (2004), 149--154.
• 7: Graham, R. Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45, 1563--1581 (1966).
• 8: Hoogeveen, H., Potts, C. N., and Woeginger, G. J. On-line scheduling on a single machine: maximizing the number of early jobs. Operations Research Letters 27, 5 (2000), 193--197.
• 9: Han Hoogeveen , Martin Skutella , Gerhard J. Woeginger, Preemptive Scheduling with Rejection, Proceedings of the 8th Annual European Symposium on Algorithms, p.268-277, September 05-08, 2000
• 10: John F. Rudin, III , R. Chandrasekaran, Improved Bounds for the Online Scheduling Problem, SIAM Journal on Computing, v.32 n.3, p.717-735, 2003 [doi>10.1137/S0097539702403438]
• 11: David R. Karger , Steven J. Phillips , Eric Torng, A better algorithm for an ancient scheduling problem, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.132-140, January 23-25, 1994, Arlington, Virginia, United States
• 12: Gilad Koren , Dennis Shasha, D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems, SIAM Journal on Computing, v.24 n.2, p.318-339, April 1995 [doi>10.1137/S0097539792236882]
• 13: Xiang-Yang Li , Ping Xu , Shaojie Tang , Xiaowen Chu, Spectrum Bidding in Wireless Networks and Related, Proceedings of the 14th annual international conference on Computing and Combinatorics, June 27-29, 2008, Dalian, China [doi>10.1007/978-3-540-69733-6_55]
• 14: Cynthia A. Phillips , Clifford Stein , Joel Wein, Scheduling Jobs that Arrive Over Time (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.86-97, August 16-18, 1995
• 15: Zheng, F., Xu, Y., and Zhang, E. On-line production order scheduling with preemption penalties. Journal of Combinatorial Optimization 13 (2007), 189--204.
• 16: Xia Zhou , Sorabh Gandhi , Subhash Suri , Haitao Zheng, eBay in the Sky: strategy-proof wireless spectrum auctions, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409947]
• 17: Yuan Yuan , Paramvir Bahl , Ranveer Chandra , Thomas Moscibroda , Yunnan Wu, Allocating dynamic time-spectrum blocks in cognitive radio networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288125]
• 18: Zhou, X., and Zheng, H. Trust: A general framework for truthful double spectrum auctions. In INFOCOM2009, pp. 999--1007

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
competitive ratio, online scheduling, penalty, preemption, spectrum, wireless networks