Back to search

University of British Columbia

Interference in wireless mobile networks

Abstract

dc:description

Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (i.e., a power level) to each node such that the resulting communication graph is connected, while minimizing the maximum (respectively, average) interference. We consider the model introduced by von Rickenbach et al. (2005), in which each wireless node is represented by a point in Euclidean space on which is centered a transmis- sion range represented by a ball, and edges in the corresponding graph are symmetric. The problem is NP-complete in two or more dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known. We show how to solve the problem efficiently in settings typical for wireless ad hoc networks. We show that if node positions are represented by a set P of n points selected uniformly and independently at random over a d-dimensional region, then the topology given by the closure of the Euclidean minimum spanning tree of P has O(log n) maximum interference, O(1) average inter- ference with high probability and O(1) expected average interference. This work is the first to examine average interference in random settings. We extend the first bound to a general class of communication graphs over a broad set of probability distributions. We present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on expected maximum interference. To verify our results, we perform an empirical evaluation using synthetic as well as real world node placements.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Haghnegahdar, Alireza

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 2.5 Canada
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/46713

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Haghnegahdar, Alireza. Interference in wireless mobile networks. master's thesis, University of British Columbia, 2014. http://hdl.handle.net/2429/46713