• ### Learning Equilibria of a Stochastic Game on Gaussian Interference Channels with Incomplete Information(1503.02839)

Feb. 3, 2016 cs.IT, math.IT
We consider a wireless communication system in which $N$ transmitter-receiver pairs want to communicate with each other. Each transmitter transmits data at a certain rate using a power that depends on the channel gain to its receiver. If a receiver can successfully receive the message, it sends an acknowledgment (ACK), else it sends a negative ACK (NACK). Each user aims to maximize its probability of successful transmission. We formulate this problem as a stochastic game and propose a fully distributed learning algorithm to find a correlated equilibrium (CE). In addition, we use a no regret algorithm to find a coarse correlated equilibrium (CCE) for our power allocation game. We also propose a fully distributed learning algorithm to find a Pareto optimal solution. In general Pareto points do not guarantee fairness among the users, therefore we also propose an algorithm to compute a Nash bargaining solution which is Pareto optimal and provides fairness among users. Finally, under the same game theoretic setup, we study these equilibria and Pareto points when each transmitter sends data at multiple rates rather than at a fixed rate. We compare the sum rate obtained at the CE, CCE, Nash bargaining solution and the Pareto point and also via some other well known recent algorithms.
• ### Distributed Algorithms for Complete and Partial Information Games on Interference Channels(1601.07976)

Jan. 29, 2016 cs.IT, math.IT
We consider a Gaussian interference channel with independent direct and cross link channel gains, each of which is independent and identically distributed across time. Each transmitter-receiver user pair aims to maximize its long-term average transmission rate subject to an average power constraint. We formulate a stochastic game for this system in three different scenarios. First, we assume that each user knows all direct and cross link channel gains. Later, we assume that each user knows channel gains of only the links that are incident on its receiver. Lastly, we assume that each user knows only its own direct link channel gain. In all cases, we formulate the problem of finding a Nash equilibrium (NE) as a variational inequality (VI) problem. We present a novel heuristic for solving a VI. We use this heuristic to solve for a NE of power allocation games with partial information. We also present a lower bound on the utility for each user at any NE in the case of the games with partial information. We obtain this lower bound using a water-filling like power allocation that requires only knowledge of the distribution of a user's own channel gains and average power constraints of all the users. We also provide a distributed algorithm to compute Pareto optimal solutions for the proposed games. Finally, we use Bayesian learning to obtain an algorithm that converges to an $\epsilon$-Nash equilibrium for the incomplete information game with direct link channel gain knowledge only without requiring the knowledge of the power policies of the other users.
• ### Algorithms for Stochastic Games on Interference Channels(1409.7551)

Sept. 26, 2014 cs.IT, math.IT, cs.GT
We consider a wireless channel shared by multiple transmitter-receiver pairs. Their transmissions interfere with each other. Each transmitter-receiver pair aims to maximize its long-term average transmission rate subject to an average power constraint. This scenario is modeled as a stochastic game. We provide sufficient conditions for existence and uniqueness of a Nash equilibrium (NE). We then formulate the problem of finding NE as a variational inequality (VI) problem and present an algorithm to solve the VI using regularization. We also provide distributed algorithms to compute Pareto optimal solutions for the proposed game.
• ### On the optimal tradeoff of average service cost rate, average utility rate, and average delay for the state dependent M/M/1 queue(1311.0486)

Nov. 3, 2013 cs.NI, cs.PF, math.OC
The optimal tradeoff between average service cost rate, average utility rate, and average delay is addressed for a state dependent M/M/1 queueing model, with controllable queue length dependent service rates and arrival rates. For a model with a constant arrival rate $\lambda$ for all queue lengths, we obtain an asymptotic characterization of the minimum average delay, when the average service cost rate is a small positive quantity, $V$, more than the minimum average service cost rate required for queue stability. We show that depending on the value of the arrival rate $\lambda$, the assumed service cost rate function, and the possible values of the service rates, the minimum average delay either: a) increases only to a finite value, b) increases without bound as $\log\frac{1}{V}$, c) increases without bound as $\frac{1}{V}$, or d) increases without bound as $\frac{1}{\sqrt{V}}$, when $V \downarrow 0$. We then extend our analysis to (i) a complementary problem, where the tradeoff of average utility rate and average delay is analysed for a M/M/1 queueing model, with controllable queue length dependent arrival rates, but a constant service rate $\mu$ for all queue lengths, and (ii) a M/M/1 queueing model, with controllable queue length dependent service rates and arrival rates, for which we obtain an asymptotic characterization of the minimum average delay under constraints on both the average service cost rate as well as the average utility rate. The results that we obtain are useful in obtaining intuition as well guidance for the derivation of similar asymptotic lower bounds, such as the Berry-Gallager asymptotic lower bound, for discrete time queueing models.
• ### On the tradeoff of average delay and average power for fading point-to-point links with monotone policies(1309.5686)

Sept. 23, 2013 cs.IT, math.IT, cs.NI, cs.PF
We consider a fading point-to-point link with packets arriving randomly at rate $\lambda$ per slot to the transmitter queue. We assume that the transmitter can control the number of packets served in a slot by varying the transmit power for the slot. We restrict to transmitter scheduling policies that are monotone and stationary, i.e., the number of packets served is a non-decreasing function of the queue length at the beginning of the slot for every slot fade state. For such policies, we obtain asymptotic lower bounds for the minimum average delay of the packets, when average transmitter power is a small positive quantity $V$ more than the minimum average power required for transmitter queue stability. We show that the minimum average delay grows either to a finite value or as $\Omega\brap{\log(1/V)}$ or $\Omega\brap{1/V}$ when $V \downarrow 0$, for certain sets of values of $\lambda$. These sets are determined by the distribution of fading gain, the maximum number of packets which can be transmitted in a slot, and the transmit power function of the fading gain and the number of packets transmitted that is assumed. We identify a case where the above behaviour of the tradeoff differs from that obtained from a previously considered approximate model, in which the random queue length process is assumed to evolve on the non-negative real line, and the transmit power function is strictly convex. We also consider a fading point-to-point link, where the transmitter, in addition to controlling the number of packets served, can also control the number of packets admitted in every slot. Our approach, which uses bounds on the stationary probability distribution of the queue length, also leads to an intuitive explanation of the asymptotic behaviour of average delay in the regime where $V \downarrow 0$.
• ### Efficient Energy Management Policies for Networks with Energy Harvesting Sensor Nodes(0811.0273)

Nov. 3, 2008 cs.NI
We study sensor networks with energy harvesting nodes. The generated energy at a node can be stored in a buffer. A sensor node periodically senses a random field and generates a packet. These packets are stored in a queue and transmitted using the energy available at that time at the node. For such networks we develop efficient energy management policies. First, for a single node, we obtain policies that are throughput optimal, i.e., the data queue stays stable for the largest possible data rate. Next we obtain energy management policies which minimize the mean delay in the queue. We also compare performance of several easily implementable suboptimal policies. A greedy policy is identified which, in low SNR regime, is throughput optimal and also minimizes mean delay. Next using the results for a single node, we develop efficient MAC policies.
• ### Optimal Energy Management Policies for Energy Harvesting Sensor Nodes(0809.3908)

Sept. 23, 2008 cs.NI
We study a sensor node with an energy harvesting source. The generated energy can be stored in a buffer. The sensor node periodically senses a random field and generates a packet. These packets are stored in a queue and transmitted using the energy available at that time. We obtain energy management policies that are throughput optimal, i.e., the data queue stays stable for the largest possible data rate. Next we obtain energy management policies which minimize the mean delay in the queue.We also compare performance of several easily implementable sub-optimal energy management policies. A greedy policy is identified which, in low SNR regime, is throughput optimal and also minimizes mean delay.
• ### Stability of Scheduled Multi-access Communication over Quasi-static Flat Fading Channels with Random Coding and Joint Maximum Likelihood Decoding(cs/0601093)

Jan. 22, 2006 cs.IT, math.IT
We consider stability of scheduled multiaccess message communication with random coding and joint maximum-likehood decoding of messages. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. The number of messages that may be scheduled for simultaneous transmission is limited to a given maximum value, and the channels from transmitters to receiver are quasi-static, flat, and have independent fades. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, (i) we derive an outer bound to the region of message arrival rate vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival rate vector that satisfies the outerbound, that there exists a stationary state-independent policy that results in a stable system for the corresponding message arrival process, and (iii) in the limit of large message lengths, we show that the stability region of message nat arrival rate vectors has information-theoretic capacity region interpretation.
• ### Stability of Scheduled Message Communication over Degraded Broadcast Channels(cs/0601094)

Jan. 22, 2006 cs.IT, math.IT
We consider scheduled message communication over a discrete memoryless degraded broadcast channel. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. The channel from the transmitter to each of the receivers is quasi-static, flat, and with independent fades across the receivers. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, (i) we derive an outer bound to the region of message arrival vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival vector that satisfies the outerbound, that there exists a stationary state-independent'' policy that results in a stable system for the corresponding message arrival process, and (iii) under two asymptotic regimes, we show that the stability region of nat arrival rate vectors has information-theoretic capacity region interpretation.
• ### Stability of Scheduled Multi-access Communication over Quasi-static Flat Fading Channels with Random Coding and Independent Decoding(cs/0506077)

July 26, 2005 cs.IT, math.IT
The stability of scheduled multiaccess communication with random coding and independent decoding of messages is investigated. The number of messages that may be scheduled for simultaneous transmission is limited to a given maximum value, and the channels from transmitters to receiver are quasi-static, flat, and have independent fades. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, we show the following: (1) in the limit of large message alphabet size, the stability region has an interference limited information-theoretic capacity interpretation, (2) state-independent scheduling policies achieve this asymptotic stability region, and (3) in the asymptotic limit corresponding to immediate access, the stability region for non-idling scheduling policies is shown to be identical irrespective of received signal powers.