2016/01/22 by Peruru Subrahmanya Swamy, Radha Krishna Ganti, Swamy, Peruru Subrahmanya +3
Computer Science · Engineering · #Advanced MIMO Systems Optimization #Advanced Wireless Network Optimization #Applications (stat.AP) #Cooperative Communication and Network Coding #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1601.06065
openalex publication_date 2016/01/22 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
We consider a Carrier Sense Multiple Access (CSMA) based scheduling algorithm\nfor a single-hop wireless network under a realistic\nSignal-to-interference-plus-noise ratio (SINR) model for the interference. We\npropose two local optimization based approximation algorithms to efficiently\nestimate certain attempt rate parameters of CSMA called fugacities. It is known\nthat adaptive CSMA can achieve throughput optimality by sampling feasible\nschedules from a Gibbs distribution, with appropriate fugacities.\nUnfortunately, obtaining these optimal fugacities is an NP-hard problem.\nFurther, the existing adaptive CSMA algorithms use a stochastic gradient\ndescent based method, which usually entails an impractically slow (exponential\nin the size of the network) convergence to the optimal fugacities. To address\nthis issue, we first propose an algorithm to estimate the fugacities, that can\nsupport a given set of desired service rates. The convergence rate and the\ncomplexity of this algorithm are independent of the network size, and depend\nonly on the neighborhood size of a link. Further, we show that the proposed\nalgorithm corresponds exactly to performing the well-known Bethe approximation\nto the underlying Gibbs distribution. Then, we propose another local algorithm\nto estimate the optimal fugacities under a utility maximization framework, and\ncharacterize its accuracy. Numerical results indicate that the proposed methods\nhave a good degree of accuracy, and achieve extremely fast convergence to\nnear-optimal fugacities, and often outperform the convergence rate of the\nstochastic gradient descent by a few orders of magnitude.\n