Distributed Resource Allocation with Local Information
Doctor of Philosophy
Making distributed decisions based on incomplete information is inevitable in dynamic wireless networks due to a multitude of constraints. We study the effects of incomplete information on system performance in two parts. We first analyze the effect of incomplete topology information on network capacity and then the effect of partial traffic information on the capacity of a two-flow interference network. In the first part of the thesis, we study the effect of local topology information based resource allocation on the number of conflicts (called defects) produced in the network. First we show its equivalence to sum rate maximization of the network. Then we prove the non-existence of an universal local coloring protocol that can produce defect-free coloring. Next we find the optimal protocol with no information and a local coloring protocol for path graphs that can achieve Nash equilibrium. We develop a general framework to analyze any local coloring protocol based on a randomized starting point that can be applied to any graph. Finally we develop a graph decomposition method to apply it to any graph with non-overlapping cliques and cycles. In the second part of the thesis, we study a two-user cognitive channel, where the primary flow is sporadic, cannot be re-designed and operating below its link capacity. To study the impact of primary traffic uncertainty, we propose a block activity model that captures the random on-off periods of primary's transmissions. Each block in the model can be split into parallel Gaussian-mixture channels, such that each channel resembles a multiple user channel from the point of view of the secondary user. The secondary senses the current state of the primary at the start of each block. We show that the optimal power transmitted depends on the sensed state and the optimal power profile is either growing or decaying in power as a function of time. We show that such a scheme achieves capacity when there is no noise in the sensing. The optimal transmission for the secondary performs rate splitting and follows a layered water-filling power allocation for each parallel channel to achieve capacity.
Channel capacity; Game theory; Cognitive radio; Graph coloring; Information theory