Spectrum Allocation Mechanisms in Wireless Networks with Performance Guarantee
Yu-E Sun, He Huang, Xiang-Yang Li, Wei Yang, Hongli Xu, Fanzhang Li and Liusheng Huang
With the advent of wireless communications technology, the demand for limited spectrum resources is increased rapidly. Efficient spectrum allocation techniques have been regarded as a key step that enables effective high-throughput ad hoc networking with efficient spectrum usage. In this work we focus on spectrum allocation mechanisms in the secondary market to mitigate the spectrum scarcity. In a spectrum trading market, we assume that secondary users will bid for the usage of spectrums in: 1) some fixed time intervals (i.e. Fixed interval), 2) some continuous time intervals in particular time ranges (i.e. Timewindow), or 3) some time slices summed to a certain value within a time range (i.e. Time-window-slice). Our goal is to design spectrum allocation mechanisms that will maximize the social efficiency under these three possible bidding cases. As allocating the requests of secondary users optimally is an NP-hard problem, to this end, we propose a suboptimal spectrum allocation mechanism PVG, in which a greedy allocation method is designed to maximize the social efficiency (total valuation of the allocated spectra). We prove that the PVG allocation mechanism yields an approximation factor 6 + 4 √2 for the Time-windowslice case, an approximation factor 8 for the Time-window case, and an approximation factor 32 for the Fixed-interval case.We then conduct an extensive simulation on a real spectrum availability data to evaluate the performance of PVG. Our results show that the social efficiency ratio of PVG is always above 70% compared with the optimal allocation mechanism in these three request cases.
Keywords: Approximation mechanism, spectrum allocation, social efficiency, temporal reuse, spatial reuse, performance guarantee.