Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

Details Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

2011-11-29

arxiv.org/abs/1111.6689v1

Computer Science

Computational Geometry

Scientific paper

The interference at a wireless node s can be modelled by the number of wireless nodes whose transmission ranges cover s. Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (equivalently, a power level) to each node such that the resulting communication graph is connected, while minimizing the maximum interference. We consider the model introduced by von Rickenback et al. (2005), in which each transmission range is represented by a ball and edges in the communication graph are symmetric. The problem is NP-complete in two dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known. Furthermore, even in one dimension (the highway model), the problem's complexity is unknown and the maximum interference of a set of n wireless nodes can be as high as Theta(sqrt(n)) (von Rickenback et al. 2005). In this paper we show how to solve the problem efficiently in settings typical for wireless ad hoc networks. In particular, 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 rectangular region, for any fixed d, then the topology given by the closure of the Euclidean minimum spanning tree of P has maximum interference O(log n) with high probability. We extend this bound to a general class of communication graphs over a broad set of probability distributions. Next we present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on the expected maximum interference. Finally, we discuss an empirical evaluation of our algorithm with a suite of simulation results.

Affiliated with

Also associated with

No associations

Rating

Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14791