deposit_your_work

Maximal Clique Scheduling: A Simple Algorithm to Bound Maximal Independent Graph Scheduling

Files in this item

Files Size Format View
SUTUNTIVORAKOON-THESIS.pdf 850.6Kb application/pdf Thumbnail

Show full item record

Item Metadata

Title: Maximal Clique Scheduling: A Simple Algorithm to Bound Maximal Independent Graph Scheduling
Author: Sutuntivorakoon, Kanes
Advisor: Sabharwal, Ashutosh
Degree: Master of Science thesis
Abstract: In this paper, we consider interference networks where the connectivity is known globally while the channel gains are known up to a particular distance from each node. In this setting, we provide a new achievability, called Maximal Clique Scheduling (MCS), which is a special case of Maximal Independent Graph Scheduling (MIG Scheduling) proposed earlier. The strategy is evaluated using the notion of normalized sum rate which is a metric to evaluate performance of networks with mismatched knowledge. The achievable normalized sum rate of the proposed MCS strategy is easier to analyze for certain classes of networks and can be used to bound the normalized sum rate of MIG Scheduling. We investigate the normalized sum rate achieved by MCS for two classes of networks. The first class is formed by interference networks where each link is connected with probability $p$. The second class is derived from Wyner 1-D model of placements of base stations and mobile nodes. We find that increasing knowledge about the network leads to increasing normalized sum-rate. However, in a random network, the increase is slower as compared to Wyner network because most nodes are far away from a node and hence learning more helps less until the whole network is known.
Citation: Sutuntivorakoon, Kanes. (2012) "Maximal Clique Scheduling: A Simple Algorithm to Bound Maximal Independent Graph Scheduling." Masters Thesis, Rice University. http://hdl.handle.net/1911/64702.
URI: http://hdl.handle.net/1911/64702
Date: 2012-09-05

This item appears in the following Collection(s)