Recent trends suggest that cognitive radio based wireless networks will be frequency agile and the nodes will be equipped with multiple radios capable of tuning across large swaths of spectrum. The MAC scheduling problem in such networks refers to making intelligent decisions on which communication links to activate at which time instant and over which frequency band. The challenge in designing a low-complexity distributed MAC, that achieves low delay, is posed by two additional dimensions of cognitive radio networks: interference graphs and data rates that are frequency-band dependent, and explosion in number of feasible schedules due to large number of available frequency-bands. In this paper, we propose MAXIMAL-GAIN MAC, a distributed MAC scheduler for frequency agile multi-band networks that simultaneously achieves the following: (i) optimal network-delay scaling with respect to the number of communicating pairs, (ii) low computational complexity of O(log2(maximum degree of the interference graphs)) which is independent of the number of frequency bands, number of radios per node, and overall size of the network, and (iii) robustness, i.e., it can be adapted to a scenario where nodes are not synchronized and control packets could be lost. Our proposed MAC also achieves a throughput provably within a constant fraction (under isotropic propagation) of the maximum throughput. Due to a recent impossibility result, optimal delay-scaling could only be achieved with some amount of throughput loss . Extensive simulations using OMNeT++ network simulator shows that, compared to a multi-band extension of a state-of-art CSMA algorithm (namely, Q-CSMA), our asynchronous algorithm achieves a 2.5x reduction in delay while achieving at least 85 of the maximum achievable throughput. Our MAC algorithms are derived from a novel local search based technique.
The inspiration of our MAC comes from application of local search based techniques to develop approximation algorithms for NP-hard optimization problems. We refer the reader to @cite_35 for an excellent survey.
@cite_35
2142022499 2786209943 2057764247 2144926522
Random Medium-Access-Control (MAC) algorithms have played an increasingly important role in the development of wired and wireless Local Area Networks (LANs) and yet the performance of even the simplest of these algorithms, such as slotted-Aloha, are still not clearly understood. In this paper we provide a general and accurate method to analyze networks where interfering users share a resource using random MAC algorithms. We show that this method is asymptotically exact when the number of users grows large, and explain why it also provides extremely accurate performance estimates even for small systems. We apply this analysis to solve two open problems: (a) We address the stability region of non-adaptive Aloha-like systems. Specifically, we consider a fixed number of buffered users receiving packets from independent exogenous processes and accessing the resource using Aloha-like algorithms. We provide an explicit expression to approximate the stability region of this system, and prove its accuracy. (b) We outline how to apply the analysis to predict the performance of adaptive MAC algorithms, such as the exponential back-off algorithm, in a system where saturated users interact through interference. In general, our analysis may be used to quantify how far from optimality the simple MAC algorithms used in LANs today are, and to determine if more complicated (e.g. queue-based) algorithms proposed in the literature could provide significant improvement in performance. We present the MAC network, a novel fully differentiable neural network architecture, designed to facilitate explicit and expressive reasoning. MAC moves away from monolithic black-box neural architectures towards a design that encourages both transparency and versatility. The model approaches problems by decomposing them into a series of attention-based reasoning steps, each performed by a novel recurrent Memory, Attention, and Composition (MAC) cell that maintains a separation between control and memory. By stringing the cells together and imposing structural constraints that regulate their interaction, MAC effectively learns to perform iterative reasoning processes that are directly inferred from the data in an end-to-end approach. We demonstrate the model's strength, robustness and interpretability on the challenging CLEVR dataset for visual reasoning, achieving a new state-of-the-art 98.9 accuracy, halving the error rate of the previous best model. More importantly, we show that the model is computationally-efficient and data-efficient, in particular requiring 5x less data than existing models to achieve strong results. The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of 12, 23, and 34 the optimal number, at running time costs of O(n), O(nlogn), and O(nlog2n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items. The authors give the first constant factor approximation algorithm for the facility location problem with nonuniform, hard capacities. Facility location problems have received a great deal of attention in recent years. Approximation algorithms have been developed for many variants. Most of these algorithms are based on linear programming, but the LP techniques developed thus far have been unsuccessful in dealing with hard capacities. A local-search based approximation algorithm (M. , 1998; F.A. Chudak and D.P. Williamson, 1999) is known for the special case of hard but uniform capacities. We present a local-search heuristic that yields an approximation guarantee of 9 + spl epsi for the case of nonuniform hard capacities. To obtain this result, we introduce new operations that are natural in this context. Our proof is based on network flow techniques.