Channel Selection in Uncoordinated IEEE 802.11 Networks Using Graph Coloring

One of the big challenges in decentralized Wi-Fi networks is how to select channels for the different access points (APs) and their associated stations (STAs) in order to minimize interference and hence maximize throughput. Interestingly enough, de facto standards in terms of uncoordinated channel selection are quite simple, and in many cases result in fairly suboptimal channel allocations. Here, we explore how graph coloring can be used to evaluate and inform decisions on Wi-Fi channel selection in uncoordinated settings. Graph coloring, in its most basic form, is a classic mathematical problem where colors have to be assigned to nodes in a graph while avoiding assigning the same color to adjacent nodes. In this paper, we modeled Wi-Fi uncoordinated channel selection as a graph coloring problem and evaluated the performance of different uncoordinated channel selection techniques in a set of representative scenarios of residential buildings. The results confirm some of the widely accepted consensus regarding uncoordinated channel selection but also provide some new insights. For instance, in some settings, it would be better to delegate the decision on which channel to use to transmit the STAs, rather than having the AP make the decision on its own, which is the usual way.

Joint User Clustering and Graph Coloring Based Pilot Assignment for Cell-Free Massive MIMO Systems

Pilot contamination due to pilot reuse seriously mitigates the performance of the cell-free massive multiple-input multiple-output (MIMO) systems. In this paper, we propose a joint pilot assignment scheme that employs user clustering and graph coloring (UC-GC) to reduce pilot contamination. The proposed method consists of two steps: firstly, we utilize AP selection to classify all users; secondly, we assign pilots to users with more severe pilot contamination using the graph coloring algorithm and then assign pilots to the remaining users. The numerical simulation results show that the proposed scheme outperforms existing pilot assignment schemes and significantly improves throughout with low complexity.

Brain Tumor Segmentation Using Graph Coloring Approach in Magnetic Resonance Images

It is important to have an accurate and reliable brain tumor segmentation for cancer diagnosis and treatment planning. There are few unsupervised approaches for brain tumor segmentation. In this paper, a new unsupervised approach based on graph coloring for brain tumor segmentation is introduced. In this study, a graph coloring approach is used for brain tumor segmentation. For this aim, each pixel of brain image assumed as a node of graph and difference between brightness of a couple of pixels considered as edge. This method was applied on T1-enhanced magnetic resonance images of low-grade and high-grade patients. Since a rigid graph was needed for graph coloring, edges must be divided into existing or nonexisting edge using a threshold. The value of this threshold has affected the accuracy of image segmentation, so the choice of the optimal threshold was important. The optimal value for this threshold was 0.42 of maximum value of difference of brightness between pixels that caused the 83.62% of correlation accuracy. The results showed that graph coloring approach can be a reliable unsupervised approach for brain tumor segmentation. This approach, as an unsupervised approach, shows better accuracy in comparison with neural networks and neuro-fuzzy networks. However, as a limitation, the accuracy of this approach is dependent on the threshold of edges.

Approximations of the Aggregated Interference Statistics for Outage Analysis in Massive MTC

This paper presents several analytic closed-form approximations of the aggregated interference statistics within the framework of uplink massive machine-type-communications (mMTC), taking into account the random activity of the sensors. Given its discrete nature and the large number of devices involved, a continuous approximation based on the Gram-Charlier series expansion of a truncated Gaussian kernel is proposed. We use this approximation to derive an analytic closed-form expression for the outage probability, corresponding to the event of the signal-to-interference-and-noise ratio being below a detection threshold. This metric is useful since it can be used for evaluating the performance of mMTC systems. We analyze, as an illustrative application of the previous approximation, a scenario with several multi-antenna collector nodes, each equipped with a set of predefined spatial beams. We consider two setups, namely single- and multiple-resource, in reference to the number of resources that are allocated to each beam. A graph-based approach that minimizes the average outage probability, and that is based on the statistics approximation, is used as allocation strategy. Finally, we describe an access protocol where the resource identifiers are broadcast (distributed) through the beams. Numerical simulations prove the accuracy of the approximations and the benefits of the allocation strategy.

Structural Characteristics of Two-Sender Index Coding

This paper studies index coding with two senders. In this setup, source messages are distributed among the senders possibly with common messages. In addition, there are multiple receivers, with each receiver having some messages a priori, known as side-information, and requesting one unique message such that each message is requested by only one receiver. Index coding in this setup is called two-sender unicast index coding (TSUIC). The main goal is to find the shortest aggregate normalized codelength, which is expressed as the optimal broadcast rate. In this work, firstly, for a given TSUIC problem, we form three independent sub-problems each consisting of the only subset of the messages, based on whether the messages are available only in one of the senders or in both senders. Then, we express the optimal broadcast rate of the TSUIC problem as a function of the optimal broadcast rates of those independent sub-problems. In this way, we discover the structural characteristics of TSUIC. For the proofs of our results, we utilize confusion graphs and coding techniques used in single-sender index coding. To adapt the confusion graph technique in TSUIC, we introduce a new graph-coloring approach that is different from the normal graph coloring, which we call two-sender graph coloring, and propose a way of grouping the vertices to analyze the number of colors used. We further determine a class of TSUIC instances where a certain type of side-information can be removed without affecting their optimal broadcast rates. Finally, we generalize the results of a class of TSUIC problems to multiple senders.

Sampling Strategies for Fast Updating of Gaussian Markov Random Fields

Gaussian Markov random fields (GMRFs) are popular for modeling dependence in large areal datasets due to their ease of interpretation and computational convenience afforded by the sparse precision matrices needed for random variable generation. Typically in Bayesian computation, GMRFs are updated jointly in a block Gibbs sampler or componentwise in a single-site sampler via the full conditional distributions. The former approach can speed convergence by updating correlated variables all at once, while the latter avoids solving large matrices. We consider a sampling approach in which the underlying graph can be cut so that conditionally independent sites are updated simultaneously. This algorithm allows a practitioner to parallelize updates of subsets of locations or to take advantage of 'vectorized' calculations in a high-level language such as R. Through both simulated and real data, we demonstrate computational savings that can be achieved versus both single-site and block updating, regardless of whether the data are on a regular or an irregular lattice. The approach provides a good compromise between statistical and computational efficiency and is accessible to statisticians without expertise in numerical analysis or advanced computing.

Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks

Coded multicasting has been shown to be a promising approach to significantly improve the performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be partitioned into several packets that grows exponentially with the number of caches, leading to codes of exponential complexity that jeopardize their promising performance benefits. In this paper, we address this crucial performance-complexity tradeoff in a heterogeneous caching network setting, where edge caches with possibly different storage capacity collect multiple content requests that may follow distinct demand distributions. We extend the asymptotic (in the number of packets per file) analysis of shared link caching networks to heterogeneous network settings, and present novel coded multicast schemes, based on local graph coloring, that exhibit polynomial-time complexity in all the system parameters, while preserving the asymptotically proven multiplicative caching gain even for finite file packetization. We further demonstrate that the packetization order (the number of packets each file is split into) can be traded-off with the number of requests collected by each cache, while preserving the same multiplicative caching gain. Simulation results confirm the superiority of the proposed schemes and illustrate the interesting request aggregation vs. packetization order tradeoff within several practical settings. Our results provide a compelling step towards the practical achievability of the promising multiplicative caching gain in next generation access networks.

Graph coloring for extracting discriminative genes in cancer data

BACKGROUND AND OBJECTIVE

The major difficulty of the analysis of the input gene expression data in a microarray-based approach for an automated diagnosis of cancer is the large number of genes (high dimensionality) with many irrelevant genes (noise) compared to the very small number of samples. This research study tackles the dimensionality reduction challenge in this area.

METHODS

This research study introduces a dimension-reduction technique termed graph coloring approach (GCA) for microarray data-based cancer classification based on analyzing the absolute correlation between gene-gene pairs and partitioning genes into several hubs using graph coloring. GCA starts by a gene-selection step in which top relevant genes are selected using a biserial correlation. Each time, a gene from an ordered list of top relevant genes is selected as the hub gene (representative) and redundant genes are added to its group; the process is repeated recursively for the remaining genes. A gene is considered redundant if its absolute correlation with the hub gene is greater than a controlling threshold. A suitable range for the threshold is estimated by computing a percentage graph for the absolute correlation between gene-gene pairs. Each value in the estimated range for the threshold can efficiently produce a new feature subset.

RESULTS

GCA achieved significant improvement over several existing techniques in terms of higher accuracy and a smaller number of features. Also, genes selected by this method are relevant genes according to the information stored in scientific repositories.

CONCLUSIONS

The proposed dimension-reduction technique can help biologists accurately predict cancer in several areas of the body.

Computational design of RNAs with complex energy landscapes

RNA has become an integral building material in synthetic biology. Dominated by their secondary structures, which can be computed efficiently, RNA molecules are amenable not only to in vitro and in vivo selection, but also to rational, computation-based design. While the inverse folding problem of constructing an RNA sequence with a prescribed ground-state structure has received considerable attention for nearly two decades, there have been few efforts to design RNAs that can switch between distinct prescribed conformations. We introduce a user-friendly tool for designing RNA sequences that fold into multiple target structures. The underlying algorithm makes use of a combination of graph coloring and heuristic local optimization to find sequences whose energy landscapes are dominated by the prescribed conformations. A flexible interface allows the specification of a wide range of design goals. We demonstrate that bi- and tri-stable "switches" can be designed easily with moderate computational effort for the vast majority of compatible combinations of desired target structures. RNAdesign is freely available under the GPL-v3 license.

A Graph Coloring Algorithm for Large Scheduling Problems

A new graph coloring algorithm is presented and compared to a wide variety of known algorithms. The algorithm is shown to exhibit O(n 2) time behavior for most sparse graphs and thus is found to be particularly well suited for use with large-scale scheduling problems. In addition, a procedure for generating large random test graphs with known chromatic number is presented and is used to evaluate heuristically the capabilities of the algorithms discussed.