Abstract
dc:descriptionGiven 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