54
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Learning the Interference Graph of a Wireless Network

      Preprint
      , ,

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          A key challenge in wireless networking is the management of interference between transmissions. Identifying which transmitters interfere with each other is a crucial first step. Complicating the task is the fact that the topology of wireless networks changes with time, and so identification may need to be performed on a regular basis. Injecting probing traffic to assess interference can lead to unacceptable overhead, and so this paper focuses on interference estimation based on passive traffic monitoring. We concentrate on networks that use the CSMA/CA protocol, although our model is more general. We cast the task of estimating the interference environment as a graph learning problem. Nodes represent transmitters and edges represent the presence of interference between pairs of transmitters. We passively observe network traffic transmission patterns and collect information on transmission successes and failures. We establish bounds on the number of observations required to identify the interference graph reliably with high probability. Our main results are scaling laws telling us how the number of observations must grow in terms of the total number of nodes \(n\) in the network and the maximum number of interfering transmitters \(d\) per node (maximum node degree). The effects of hidden terminal interference on the observation requirements are also quantified. We show that it is necessary and sufficient that the observation period grows like \(d^2 \log n\), and we propose a practical algorithm that reliably identifies the graph from this length of observation. The observation requirements scale quite mildly with network size, and networks with sparse interference (small \(d\)) can be identified more rapidly. Computational experiments based on a realistic simulations of the traffic and protocol lend additional support to these conclusions.

          Related collections

          Most cited references10

          • Record: found
          • Abstract: not found
          • Article: not found

          Network Tomography: Recent Developments

            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Boolean Compressed Sensing and Noisy Group Testing

            , (2013)
            The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. The single letter characterization is shown to be order-wise tight for many interesting noisy group testing scenarios. Specifically, we consider an additive Bernoulli(\(q\)) noise model where we show that, for \(N\) items and \(K\) defectives, the number of tests \(T\) is \(O(\frac{K\log N}{1-q})\) for arbitrarily small average error probability and \(O(\frac{K^2\log N}{1-q})\) for a worst case error criterion. We also consider dilution effects whereby a defective item in a positive pool might get diluted with probability \(u\) and potentially missed. In this case, it is shown that \(T\) is \(O(\frac{K\log N}{(1-u)^2})\) and \(O(\frac{K^2\log N}{(1-u)^2})\) for the average and the worst case error criteria, respectively. Furthermore, our bounds allow us to verify existing known bounds for noiseless group testing including the deterministic noise-free case and approximate reconstruction with bounded distortion. Our proof of achievability is based on random coding and the analysis of a Maximum Likelihood Detector, and our information theoretic lower bound is based on Fano's inequality.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: found
              Is Open Access

              Optimizing User Association and Spectrum Allocation in HetNets: A Utility Perspective

              The joint user association and spectrum allocation problem is studied for multi-tier heterogeneous networks (HetNets) in both downlink and uplink in the interference-limited regime. Users are associated with base-stations (BSs) based on the biased downlink received power. Spectrum is either shared or orthogonally partitioned among the tiers. This paper models the placement of BSs in different tiers as spatial point processes and adopts stochastic geometry to derive the theoretical mean proportionally fair utility of the network based on the coverage rate. By formulating and solving the network utility maximization problem, the optimal user association bias factors and spectrum partition ratios are analytically obtained for the multi-tier network. The resulting analysis reveals that the downlink and uplink user associations do not have to be symmetric. For uplink under spectrum sharing, if all tiers have the same target signal-to-interference ratio (SIR), distance-based user association is shown to be optimal under a variety of path loss and power control settings. For both downlink and uplink, under orthogonal spectrum partition, it is shown that the optimal proportion of spectrum allocated to each tier should match the proportion of users associated with that tier. Simulations validate the analytical results. Under typical system parameters, simulation results suggest that spectrum partition performs better for downlink in terms of utility, while spectrum sharing performs better for uplink with power control.
                Bookmark

                Author and article information

                Journal
                2012-08-02
                Article
                10.1109/ISIT.2012.6284019
                1208.0562
                736b892f-5f18-436e-b1cf-2bbce1f08e39

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                submitted to IEEE Trans. Information Theory
                cs.IT math.IT

                Numerical methods,Information systems & theory
                Numerical methods, Information systems & theory

                Comments

                Comment on this article