Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Dissertation Dongyue XUE.pdf (2.76 MB)

ETD Abstract Container

Abstract Header

Delay-Oriented Analysis and Design of Optimal Scheduling Algorithms

Xue, Dongyue
http://rave.ohiolink.edu/etdc/view?acc_num=osu1386065185

Abstract Details

2013, Doctor of Philosophy, Ohio State University, Electrical and Computer Engineering.
The main focus of this research is in the area of optimal cross-layer scheduling in wireless networks. In the literature, back-pressure-based scheduling algorithms (e.g., maximal weight matching algorithm) have been developed typically focusing on the throughput/utility optimality, while little emphasis is given to delay constraints or queuing delay analysis. However, in practical implementations, delay is an important metric for wireless multimedia applications such as Video-on-Demand (VoD), Voice-over-IP (VoIP), IPTV, etc. In this research, delay-oriented scheduling with optimal throughput/utility is studied. An important delay-related factor is finite buffer property. By Little's Law, finite buffer sizes lead to upper-bounded end-to-end delay on a per-flow basis. In addition, the finite buffer property is also an important factor for Quality of Service (QoS) sensitive wireless network applications. Algorithms with finite buffer property can find their application in resource-limited wireless networks such as wireless sensor networks. In this research, to improve delay performance and ensure finite buffer sizes, a novel virtual queue is first proposed that acts as a weight on the actual queue when scheduling link rates. Specifically, the product of the virtual and actual queue backlogs has been employed as a weight in the maximal weight matching schedules and as a weight on the random access probability in the CSMA algorithm. The network stability is achieved by shifting the burden from actual queues to the proposed virtual queues, while the actual queues are upper-bounded by a finite buffer size. As a direct result, the delay performance is significantly improved. In the proof of the stability and throughput/utility optimality, a novel type of Lyapunov function is employed which multiplies the virtual queue backlog to the quadratic term of actual queue backlogs. This particular structure of Lyapunov function leads to the product form of virtual and actual queue backlogs in the proposed algorithms. The scheduling algorithms with finite buffers are proposed and analyzed in both centralized and distributed settings. Specifically, in multi-hop wireless networks, a centralized cross-layer scheduling algorithm is designed with a novel concept of virtual queues to achieve a throughput ``epsilon-close'' to the optimality with a tradeoff of O(1/epsilon) in average end-to-end delay guarantees. The structure of this algorithm is also employed to design centralized optimal power control algorithms with finite buffers. Distributed cross-layer CSMA algorithms are proposed in a single-hop setting to guarantee finite buffer sizes. The algorithm is shown to achieve a utility arbitrarily close to the optimal value with a tradeoff in the finite buffer sizes. Both implementation and numerical results show a far better delay performance for comparable utility levels in comparison with recent optimal CSMA algorithms (e.g., Q-CSMA). In practical wireless scenarios (i.e., IEEE 802.11 standards and OFDM systems), the entire bandwidth is usually partitioned into multiple channels. While a single-channel setting has been studied for throughput-optimal CSMA algorithms, the queueing behavior and delay performance of these algorithms have not been addressed in a multi-channel scenario. To fill in the gap, the queuing behavior and the closed-form queuing delay of general CSMA algorithms are studied in a many-channel regime. Law-of-Large-Numbers convergence results and a steady state queuing analysis have been carried out theoretically and confirmed via numerical results. Furthermore, the queue backlog in steady state has been approximated in closed-form in a many-channel regime. This many-channel regime analysis is further extended to a cognitive radio scenario, where a distributed scheduling algorithm is proposed to achieve at least a guaranteed fraction of the optimal throughput.
Eylem Ekici (Advisor)
Ness Shroff (Committee Member)
Atilla Eryilmaz (Committee Member)
Rebecca Kim (Committee Member)
276 p.
Electrical Engineering
Wireless networking; optimal scheduling; delay-oriented analysis; distributed implementation

Recommended Citations

Citations

  • Xue, D. (2013). Delay-Oriented Analysis and Design of Optimal Scheduling Algorithms [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1386065185

    APA Style (7th edition)

  • Xue, Dongyue. Delay-Oriented Analysis and Design of Optimal Scheduling Algorithms. 2013. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1386065185.

    MLA Style (8th edition)

  • Xue, Dongyue. "Delay-Oriented Analysis and Design of Optimal Scheduling Algorithms." Doctoral dissertation, Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1386065185

    Chicago Manual of Style (17th edition)

osu1386065185
579
© 2013, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.