Randomized algorithms for resource allocation in device to device communication/ Subhankar Ghosal

Thesis (Ph.D.) - Indian Statistical Institute, 2021

Introduction -- Minimizing the maximum channel -- Minimizing the total perturbation -- Minimizing the total perturbation -- Minimizing both maximum channel and total power -- Conclusion and Future Scope

Guided by Prof. Sasthi Charan Ghosh

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