Open Collections

Interference in wireless mobile networks

University of British Columbia

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.

Text

2014-05-09

Attribution-NonCommercial-NoDerivs 2.5 Canada

http://hdl.handle.net/2429/46713

Electrical and Computer Engineering

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/