Randomized algorithms for resource allocation indevice to device communication

Abstract

In device to device (D2D) communication, two users residing in close proximity candirectly communicate between them, through a common channel, without the needof a base station. A pair of D2D users forms a link and a channel needs to be allo-cated to it. The interference relationship among the active links at timetis modelledas an interference graphg(t). To establish interference-free communication, wehave to assign a channel vectorC(t)and a power vector corresponding to the activelinks such that the required signal to interference plus noise ratio (SINR) is satisfiedfor each link. Since channels are costly resources we have to minimizeY(t), themaximum channel used inC(t). Due to the movement of the D2D users, a channelallocated at time(t−1)may create interference at timet. Hence a link may requireto switch its channel to maintain its SINR. Channel switch itself produces delay andhence an additional overhead. Hence, to maintain quality of service,A(t), the totalnumber of channel switches or perturbations inC(t)fromC(t−1), should alsobe minimized. Since each transmitter has a limited battery power, minimizing thetotal powerP(t)used at timet, is also an objective of minimization. Note that if weallocate each link a different channel then each link has no interference from otherlinks. In that case,A(t)is zero and each link can operate with the minimum power,resultingP(t)to be the minimum. ButY(t)is huge in that case. ThusY(t)-A(t)andY(t)-P(t)have natural trade-offs among them. Due the hardness, optimizingY(t),A(t)andP(t)owing to their respective trade-offs is a challenging task. Inthis thesis, we developed a randomized algorithm as well as its parallel versionwhich can find minimumY(t)in expected polynomial time. To minimizeA(t),we developed a centralized and a decentralized differential coloring techniqueas well as a random coloring technique. We calculated expected perturbationsproduced by each of them. To minimize a cost defined as a linear combination ofY(t)andA(t), we proposed a geometric prediction based and a graph union basedapproach and calculated the expected cost produced by them. Finally to minimizea cost defined as a linear combination ofY(t)andP(t), we proposed a randomizedjoint channel and power allocation technique and calculated the expected cost andenergy efficiency produced by it theoretically as well as through simulations