Correlation-aware Splitting Algorithms for Opportunistic Selection

Abstract

Opportunistic selection is a key technique to improve the performance of wireless systems. In it, the best set of users among the available ones is selected on the basis of their instantaneous channel gains or local parameters such as battery energy state. For example, in cellular systems, scheduling the user with the highest downlink signal-to-noise ratio improves the downlink throughput. Formally, the process of selection is as follows. Each user possesses a real-valued metric that only it knows, and the goal is to select the best user, which has the highest metric. While opportunistic selection is appealing, finding the best user is a challenge because the users are geographically separated and the metric of a user is known only to itself; no user knows who the best is. Moreover, the time taken for selecting the best user should be small so that more time is available for data transmission. In this thesis, we focus on the splitting algorithm, which is a popular distributed, fast, and scalable algorithm to implement opportunistic selection. We first show that this algorithm, which has thus far been designed assuming that the metrics are independent and identically distributed (i.i.d.), is no longer scalable in the practically important scenario in which the metrics are correlated. We make the following three contributions in this thesis. Firstly, we propose a novel correlation-aware splitting algorithm (CASA) that selects the best user when the metrics are correlated and non-identical. We show how it can be applied to several practically relevant probability distributions and correlation models. We present computationally feasible techniques for pre-computing the thresholds that CASA specifies, thereby ensuring that CASA can be implemented in practice. We benchmark its performance with conventional algorithms, and show that it reduces the average selection time significantly as the number of users or the correlation among them increase. We then extend CASA to CASA-m to select the best m users with the m largest metrics. We instantiate CASA-m for a generalized correlation model and benchmark its performance with conventional algorithms, and show that CASA-m reduces the average time of selecting multiple users as the number of users or the correlation among them increase. As an application, we then consider the example of a cooperative relay system that employs CASA-m to select multiple relays for cooperative beamforming. We study the system-level implications of correlation and selection using CASA-m for this system and benchmark its system throughput and energy efficiency with that of other selection algorithms. We find that in the presence of correlation, the average selection time, system throughput, and energy efficiency of the system is lower than that of the uncorrelated scenario. However, the percentage by which it is lower is less when CASA-m is used to select the relays compared to conventional algorithms. Lastly, we propose a novel and faster approach for computing multivariate probabilities for Rayleigh and exponential distributions with an arbitrary covariance matrix. Compared to the existing approaches in the literature, which seldom reported results on multivariate probabilities for more than 5 variates, our approach can accurately compute these for even 50 variates. This is due to its significantly lower computational complexity that does not scale with the number of variates. We also demonstrate the utility of the approach in the performance analysis of the selection combining diversity technique.