Scheduling and resource allocation with incomplete information in wireless networks

2015-07-01In a wireless network, it is quite common that a transmitter needs to make decisions on scheduling and resource allocation with incomplete information. In this dissertation, we argue that efficient mechanisms can be designed even if some key information regarding to scheduling and resource allocation is unknown. We substantiate this thesis through three studies: ❧ • Transmission over a Markovian channel ❧ • Dynamic multi‐carrier selection ❧ • Transmission for random arrivals with energy‐delay tradeoff. ❧ First, we study the optimal transmission policy for a single transmitter in a 2‐state Markovian channel. The transmitter can either sending with high rate or low rate, with rewards depending on the action chosen and the underlying channel state. The aim is to compute the scheduling policy to determine which actions to choose at each time slot in order to maximize the expected total discounted reward. We first establish the threshold structure of the optimal policy when the underlying channel statistics are known. We then focus on the more challenging case when the statistics are unknown. For this problem, we map different threshold policies to arms of a suitably defined multi‐armed bandit problem. To tractably handle the complexity introduced by countably infinite arms and the infinite time horizon, we weaken our objective a little: finding a (1−(ε + δ))‐approximate policy instead. We present the UCB-P algorithm, which can achieve this objective with logarithmic‐time regret. ❧ Next, we study the transmission control problem where a transmitter is able to transmit data simultaneously over multiple i.i.d. channels owned by different carriers. The carriers send bids indicating their channel quality to the transmitter, and the transmitter allocates power and data rate accordingly. The transmitter pays the carriers to use the channel. To efficiently use its power and maximize the throughput, the transmitter requires the knowledge of the channel quality. However, such information is incomplete to the transmitter and its transmission control relies on the bids from the carriers. Carriers are self‐interested entities who compete with each other to get the payment from the transmitter. Hence, the transmitter also needs to have a strategic approach in order to deal with the self‐interested carriers' behavior. ❧ We first consider a simplified case in which there is one transmitter and two carriers, and the bid is binary. We analyze the Nash equilibrium of the carriers and use the price of anarchy (PoA) to analyze the efficiency of the game. We prove that there exists a bounded PoA if the penalties for unsuccessful transmissions are set carefully. The bound is 2, and we prove that this bound is the best considering all possible settings. We next extend the binary bids to be multi‐bit bids, and allow for an arbitrary number of carriers. The key aim of this latter study is to guarantee the truthfulness from the bidders. We propose a rewarding mechanism based on a convex piecewise linear function and prove that such a mechanism can ensure the truthfulness of the carriers. We also prove that with the number of bits per bid increases, the throughput obtained by the transmitter approaches the optimal. ❧ Finally, we study a scheduling problem on a time slotted channel to balance the tradeoff between a higher energy cost incurred by packing multiple packets on the same slot, and higher latency incurred by deferring some packets. The objective is to minimize the weighted sum of delay and energy cost from all nodes. We first analyze the offline scheduling problem, in which the traffic arrivals are given in advance, and prove that a greedy algorithm is optimal. We then focus on the scenario where the information of the arrivals is incomplete, and the scheduler can only see the traffic arrivals so far. We develop an efficient online algorithm, which we prove is O(1)‐competitive