Computer science colloquium
| Date/Time: | Tuesday, 31 Mar 2009 at 3:40 pm |
|---|---|
| Location: | B29 Atanasoff |
| Cost: | Free |
| Phone: | 515-294-6516 |
| Channel: | Groups, governance |
| Categories: | Lectures |
| Actions: | Download iCal/vCal | Email Reminder |
Wireless technology is expected to play a bigger and more fundamental role in the new Internet than it does today. The radio frequency spectrum has been chronically regulated with static spectrum allocation policies since the early 20th century. With the recent fast growing spectrum-based services and devices, the remaining spectrum available for future wireless services is being exhausted, known as the spectrum scarcity problem. The current fixed spectrum allocation scheme leads to significant spectrum white spaces, where many allocated spectrum blocks are used only in certain geographical areas and/or in brief periods of time. A huge amount of precious spectrum (below 5GHz), perfect for wireless communications that is worth billions of dollars, sit there silently. Recognizing that the traditional spectrum management process can stifle innovation, and it is difficult to provide a certain quality of service (QoS) for systems operated in unlicensed spectrum, the FCC has proposed new spectrum management models, such as cognitive radio, and short term spectrum leasing.
In this talk, we discuss both efficient offline and online spectrum scheduling in wireless networks. For online spectrum leasing, we assume that each new arrival job, when it arrives, requests for the exclusive usage of the channel for a certain time interval. The scheduler has to decide immediately whether to grant its exclusive usage or not. If it is granted, the job will be charged a payment. We assume that existing running job can be preempted with a penalty depending on its bid value, its requested time duration and the remaining unserved time. We first prove that the competitive ratio of any scheduling algorithm could be arbitrarily bad in most cases if no distributions on the possible bid values, the duration of the requested service times are known. For some possibly known information, we present efficient scheduling algorithms to schedule jobs and prove that the competitive ratios of our methods are asymptotically optimum, i.e., within a small constant factor of the best that we can do. We also conduct extensive simulations to study the performances of our proposed methods and our simulation results show that they perform almost optimum: most of our methods can get a total profit that is more than 80% of the optimum. To the best of our knowledge, the online spectrum allocation and auction has not been studied before in the literature.
Biography
Xiang-Yang Li is an associate professor of the department of computer science at Illinois Institute of Technology (IIT). Li graduated (2000) with Ph.D from the department of computer science at University of Illinois at Urbana-Champaign, and he joined the department of computer science at the Illinois Institute of Technology.
Li has been working in the fields of theoretical computer science, particularly in the areas of algorithm design and analysis, and scientific computing. Topics of his research projects include wireless networks; computational geometry; applications of computational geometry to computer graphics, robotics, and mesh generation; scientific computing; cryptography and network security, and combinatorial optimization.