Athens University Economics and Business (AUEB)
Performance analysis of distributed control algorithms in queueing systems
Abstract
dc:descriptionIn this thesis we deal with the performance analysis of distributed control algorithms in two different areas where queues arise: a) wireless networks and b) ridesharing platforms.In the first part we consider the joint minimization of queueing cost and power consumption in a wireless network, over all power control policies at the transmitters. Approximately optimal policies are derived through a comparison to a single link system. The resulting policies are of a simple form: the total power consumed at any instant is a monotonic function of a linear combination of the queue backlogs at that instant, while the portions of power allocated to each transmitter are such that the resulting link speeds are proportional to the queue backlogs. What enables this sort of decomposition is the specific type of queueing cost considered and the fact that under the policy which minimizes this cost (under a fixed power budget), the system effectively becomes one-dimensional. As the structure of the optimal controls are known for this case, one can apply to optimize the performance of the“collapsed”one-dimensional system. Simulations show that the proposed policies offer significant performance gains as the average power approaches the lowest value for which stability is maintained. Moreover, these policies are shown to perform better than gradient projection -based power control schemes such as those resulting from network utility maximization. We apply these ideas in a CDMA (Code Division Multiple Access) wireless cell-based network and propose a concrete uplink power control scheme for low data packet queueing delay. The scheme can be seen as a simple extension to the Foschini-Miljanic algorithm which takes the transmit queue sizes at the mobile stations into account. The proposed scheme minimizes the draining time compared to all other policies with the same power consumption. This is because of resource pooling effects which arise when all queues empty at the same time. In its standard form the proposed scheme exploits resource pooling within a single cell and no communication is needed between cells. In an extension of the algorithm, resource pooling –and better performance– is achieved for the entire network by allowing limited messaging between the base stations of different cells. Simulations exhibit significant reductions in queueing delay compared to other power control schemes proposed in the literature, especially in the presence of slow fading. In the second part of the thesis, we study ridesharing platforms like Uber and Lyft. These platforms give monetary incentives to participating drivers, to share a ride with customers that also participate in the platform. When the supply of available drivers that exist in a certain location falls short of the demand for transport requested by the customers located at that location, the platforms increase the price for rides so as to counter the imbalance by attracting more available drivers and discouraging further passenger requests. In this setting, we study the effect that the type of information on which these dynamic prices are based on, has on the mobility patterns of available drivers and the resulting average pick-up delay. Based on a scalable discrete-time Markovian model for driver mobility and passenger queueing, we compare the performance of various policies which take into account such metrics as the number of the customers waiting in an area to be served and the ratio of the customers to drivers in an area. Simulation experiments show that customer queue and load information lead to superior performance compared to either prices calculated through tatonnement or driver behavior which do not take customer short-term demand fluctuations into account. Moreover, we find that dynamic information greatly reduces delay, a result which runs counter to recent findings in the literature which find that dynamic information does not increase the platform’s profits.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Papafragkos, Spyridon
- Παπαφράγκος, Σπυρίδων
Subjects
dc:subject × 12- Ασύρματα δίκτυα
- Θεωρία ουρών
- Βέλτιστος έλεγχος ουρών και δικτύων
- Πλατφόρμες διαμοιρασμού διαδρομών
- Wireless networks
- Queueing theory
- Optimal Control of Queues and Networks
- Ridesharing Platforms
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/42832