Learning the interference graph of a wireless network

Jing Yang, Stark C. Draper, Robert Nowak

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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. In this paper, we cast the task of estimating the wireless 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 (each a snapshot of a network traffic pattern) required to identify the interference graph reliably with high probability. Our main results are scaling laws that tell 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 (i.e., interference not detectable via carrier sensing) on the observation requirements are also quantified. We show that to identify the graph, it is necessary and sufficient that the observation period grows like d2 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.

Original languageEnglish (US)
Article number7752899
Pages (from-to)631-646
Number of pages16
JournalIEEE Transactions on Signal and Information Processing over Networks
Issue number3
StatePublished - Sep 2017

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Learning the interference graph of a wireless network'. Together they form a unique fingerprint.

Cite this