Relay Selection in Wireless Networks as Restless Bandits

We consider a wireless network in which a source node needs to transmit a large file to a destination node. The direct wireless link between the source and the destination is assumed to be blocked. Multiple candidate relays are available to forward packets from the source to the destination. A holding cost is incurred for each packet stored at every relay in each time slot. The objective is to design a policy for selecting a relay in each time slot to which the source attempts to send a packet, so as to minimize the expected long-run time-averaged total packet holding cost at the relays. This problem is an instance of the restless multi-armed bandit (RMAB) problem, which is provably hard to solve. We establish the Whittle indexability of this relay selection problem and propose a computationally efficient policy to compute the Whittle index of each relay in every time slot. In each time slot, our relay selection policy transmits a packet to the relay with the smallest Whittle index. Using simulations, we show that our proposed policy outperforms several relay selection policies proposed in prior work in terms of the average cost, delay, as well as throughput.