Timer-Based Selection Schemes for Wireless Networks

Abstract

Opportunistic selection is a practically appealing technique that is often used in multi-node wireless systems such as scheduling and rate adaptation in cellular systems and opportunistic wireless local area networks, wireless sensor networks, cooperative communications, and vehicular networks. In it, each node maintains a local preference number called metric that is function of its channel gains, and the best node with the highest metric is selected. Identifying the best node is challenging as the information about a node's metric is available only locally at each node. In our work, we focus on the popular, simple, and low feedback timer scheme for selection. In it, each node sets a timer as a function of its metric and transmits a packet when the timer expires. The metric-to-timer mapping maps larger metric values to smaller timer values, which ensures that the best node's timer expires first. However, it can fail to select the best node if another node transmits a packet within D s of the transmission by the best node. In this thesis, we make three contributions to the design and understanding of the timer-based selection scheme. Firstly, we introduce feedback overhead-aware contention resolution in the timer-based selection scheme. The outcome is a novel selection scheme that is faster than the splitting scheme and more reliable than the timer-based selection scheme. We analyze and minimize the average time required by the scheme to select the best node. Secondly, we characterize the optimal metric-to-timer mapping when the number of nodes in the system is not known, as is the case in several practical deployments. When the prior distribution of the nodes is known, we propose an optimal mapping that maximizes the success probability averaged over the distribution on the number of nodes. When even the prior distribution is not known, we propose a robust mapping that maximizes the worst case average success probability over all possible probability distributions on the number of nodes. In both cases, we show that the timers can expire only at 0, D, 2D, ... in the optimal timer mapping. For the known prior case, we develop recursive techniques to effectively compute the optimal timer mapping for binomial and Poisson priors. Lastly, we consider a discrete rate adaptive system and design an optimal timer scheme to maximize the end-to-end performance measure of system throughput. We derive several novel, insightful results about the optimal mapping that culminate in an iterative algorithm to compute it. We show that the design of the selection scheme is intimately related to the rate adaptation rule and the selection policy used. In all cases, extensive benchmarking with several ad hoc schemes proposed in the literature shows the significant gains that the proposed designs can deliver.