Completely Uncoupled Algorithms for Network Utility Maximization

Topic_abstract: “The recent advances in wireless systems demands addressing the following resource allocation problems, viz channel selection, user association and power control. The solution to these problems should address the following objectives: (i) Network throughput optimality be ensured (ii) Users get a fair share of the network throughput. Also in a heterogeneous network, where multiple radio technologies coexists a distributed solution is preferable. In this talk, we present two fully distributed algorithms which provide solutions to the above problems with the stated objectives. We assume that the node’s decisions are based only on their past actions and payoffs which is popularly known as completely uncoupled. Prior work in this setup has focused mainly in maximizing the sum-rate. An important attribute to consider in radio resource allocation is fairness among nodes, i.e. every node should get a fair share of the network throughput. Fairness is taken care of by introducing a utility function of the average rate. Our first algorithm, which we call General Network Utility Maximization (G-NUM), maximizes general non-concave utilities. We show that G-NUM induces a perturbed Markov chain (perturbed by ε), whose stochastically stable states are the set of actions that maximize the network utility. Our second algorithm is motivated by adaptive CSMA algorithms based on Gibbs sampling, where we present an approximate sub-gradient algorithm for concave utilities, which we call Concave Network Utility Maximization (C-NUM). C-NUM is considerably faster and requires lesser memory. Our main contribution is the expansion of the achievable rate region, which the prior works incompletely uncoupled setup has ignored to consider. This expansion aids in allocating a fair share of resources to the nodes.”