A Spectrum Allocation and Auction Mechanism With The Maximum Weighed Independent Set

The problem of spectrum allocation has become more pertinent in recent times, especially due to the rapid increase in demand for mobile data. The majority of spectrum now is being statically allocated according to usage functions. For example, 30-300MHz is reserved partly for radio and TV broadcasts, and 300-3000MHz is reserved partly for mobile phone usage and wireless LAN. Hence, there is high variance in the overall spectrum utilization, with certain frequencies being underutilized and others facing spectrum shortages. In order to improve utilization rates, dynamic spectrum access (DSA) methods are being used to match demand for spectrum with un-utilized spectrum dynamically, using cognitive radio technology. DSA methods are computationally efficient to ensure that spectrum allocation to users is updated on a timely basis, to maximize utilization rates.
The reusability property of radio spectrum allows a single channel to be allocated to multiple users at the same time, subject to interference constraints. In this thesis, we look at the scenario where the utility that different users derive from spectrum usage vary. The utility of each user is expressed by the user in the form of an auction bid, of which the truthfulness is ensured by the VCG pricing mechanism.
The allocation of radio spectrum to maximize social efficiency, subject to interference constraint, is the Maximum Weighted Independent Set (MWIS) problem. In this thesis, a new algorithm to the MWIS problem is introduced. The first part of the algorithm identifies vertices that belong to the MWIS using a O(N) complexity algorithm, where N is the number of vertices of the graph. And the second part is a new greedy heuristic algorithm that is applied to the rest of the graph to find the approximate MWIS. It computational complexity is O(ECN2Dlog(N2D)), where E is the maximum number of second degree neighbors of a vertex, C is the size of the allocated clusters, and D is the maximum degree of the graph. In the simulations ran, its performance was 89-97% for network sizes of 80 to 200 for bipartite graphs.