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

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.


Motivation
Establishing connectivity in a wireless network can be a complex task for which various (sometimes conflicting) objectives may need to be optimized. To permit a packet to be routed from any origin node to any destination node in the network, the corresponding communication graph must be connected (or strongly connected if unidirectional communication links are permitted). In addition to requiring connectivity, various properties can be imposed on the network, including low power consumption [21,27], bounded average traffic load [9,14], small average hop distance between sender-receiver pairs [1], low dilation (t-spanner) [1,3,6,7,16,22,25], and minimal interference; this latter objective, minimizing interference (and, consequently, minimizing the required bandwidth), is the focus of much recent research [1, 2, 5, 12, 18-20, 23, 24, 27-31] and of this paper.
We adopt the interference model introduced by von Rickenbach et al. [30] (see Section 1.2). We model transmission in a wireless network by assigning to each wireless node p a radius of transmission r(p), such that every node within distance r(p) of p can receive a transmission from p, whereas no node a greater distance from p can. Consequently, the interference at node p is the number of nodes that have p within their respective radii of transmission. Given a set of wireless nodes whose positions are represented by a set of points P , we consider the problem of identifying a connected network on P that minimizes the maximum interference. The problem of constructing the network is equivalent to that of assigning a transmission radius to each node. That is, once the transmission radius of each node is fixed, the corresponding communication graph and its associated maximum interference are also fixed. Conversely, once a graph is fixed, the transmission radius of each node is determined by the distance to its furthest neighbour.
Given a set of points P in the plane, finding a connected graph on P that minimizes the maximum interference is NP-complete [5]. A polynomial-time algorithm exists that returns a solution with maximum interference O( √ n), where n = |P | [12]. Even in one dimension, for every n there exists a set of n points P such thta any graph on P has maximum interference Ω( √ n) [30]. All such known examples involve specific constructions (i.e., exponential chains). We are interested in investigating a more realistic class of wireless ad hoc networks: those whose node positions observe common random distributions that better model actual wireless ad hoc networks.
When nodes are positioned on a line (often called the highway model), a simple heuristic is to assign to each node a radius of transmission that corresponds to the maximum of the distances to its respective nearest neighbours to the left and right. In the worst case, such a strategy can result in Θ(n) maximum interference when an optimal solution has only Θ( √ n) maximum interference [30]. Recently, Kranakis et al. [20] showed that if n nodes are positioned uniformly at random on an interval, then the maximum interference provided by this heuristic is Θ( √ log n) with high probability. In this paper, we examine the corresponding problem in two and higher dimensions. We generalize the nearest-neighbour path used in the highway model to the Euclidean minimum spanning tree (MST), and show that with high probability, the maximum interference of the MST of a set of n points selected uniformly at random over a d-dimensional region [0, 1] d is O(log n), for any fixed d ≥ 1. Our techniques differ significantly from those used by Kranakis et al. to achieve their results in one dimension. As we show in Section 3, our results also apply to a broad class of random distributions, denoted D, that includes both the uniform random distribution and realistic distributions for modelling random motion in mobile wireless networks, as well as to a large class of connected spanning graphs that includes the MST.
In Section 3.4 we present a local algorithm that constructs a topology whose maximum interference is O(log n) with high probability when node positions are selected according to a distribution in D. Previous local algorithms for topology control (e.g., the cone-based local algorithm (CBTC) [21]) attempt to reduce transmission radii (i.e., power consumption), but not necessarily the maximum interference. Although reducing transmission radii at many nodes is often necessary to reduce the maximum interference, the two objectives differ; specifically, some nodes may require large transmission radii to minimize the maximum interference. Ours is the first local algorithm to provide a non-trivial upper bound on maximum interference. Our algorithm can be applied to any existing topology to refine it and further reduce its maximum interference. Consequently, our solution can be used either independently, or paired with another topology control strategy. Finally, we discuss an empirical evaluation of our algorithm with a suite of simulation results in Section 4.

Model and Definitions
We represent the position of a wireless node as a point in Euclidean space, R d , for some fixed 1 d ≥ 1. For simplicity, we refer to each node by its corresponding point. Similarly, we represent a wireless network by its communication graph, a geometric graph whose vertices are a set of points P ⊆ R d . Given a (simple and undirected) graph G, we employ standard graph-theoretic notation, where V (G) denotes the vertex set of G and E(G) denotes its edge set. We say vertices u and v are k-hop neighbours if there is a simple path of length k from u to v in G. When k = 1 we say u and v are neighbours.
We assume a uniform range of communication for each node and consider bidirectional communication links, each of which is represented by an undirected graph edge connecting two nodes. Specifically, each node p has some radius of transmission, denoted by the function r : P → R + , such that a node q receives a transmission from p if and only if dist(p, q) ≤ r(p), where dist(p, q) = ||p − q|| 2 denotes the Euclidean distance between points p and q in R d . For simplicity, suppose each node has an infinite radius of reception, regardless of its radius of transmission.
Definition 1 (Communication Graph) A graph G is a communication graph with respect to a point set P ⊆ R d and a function r : P → R + if 1. V (G) = P , and 2. for all vertices p and q in V (G), Together, set P and function r uniquely determine the corresponding communication graph G. Alternatively, a communication graph can be defined as the closure of a given embedded graph. Specifically, if instead of being given P and r, we are given an arbitrary graph H embedded in R d , then the set P is trivially determined by V (H) and a transmission radius for each node p ∈ V (H) can be assigned to satisfy (1) by where Adj(p) = {q | {q, p} ∈ E(H)} denotes the set of vertices adjacent to p in H. The communication graph determined by H is the unique edge-minimal supergraph of H that satisfies Definition 1. We denote this graph by H and refer to it as the closure of graph H. Therefore, a communication graph G can be defined either as a function of a set of points P and an associated mapping of transmission radii r : P → R + , or as the closure of a given embedded graph H (where G = H ). inter G (p).
In other words, the interference at node p, denoted inter G (p), is the number of nodes q such that node p lies within q's radius of transmission. This does not imply the existence of the edge {p, q} in the corresponding communication graph; such an edges exists if and only if the relationship is reciprocal, i.e., q also lies with p's radius of transmission. Given a point set P , let G(P ) denote the set of connected communication graphs on P . Let OPT(P ) denote the optimal maximum interference attainable over graphs in G(P ). That is, Thus, given a set of points P representing the positions of wireless nodes, the interference minimization problem is to find a connected communication graph G on P that spans P such that the maximum interference is minimized (i.e., its maximum interference is OPT(P )). In this paper we examine the maximum interference of the communication graph determined by the closure of MST(P ), where MST(P ) denotes the Euclidean minimum spanning tree of the point set P . Our results apply with high probability, which refers to probability at least 1 − n −c , where n = |P | denotes the number of networks nodes and c ≥ 1 is fixed.

Bidirectional Interference Model
In this paper we consider the bidirectional interference model (defined in Section 1.2). This model was introduced by von Rickenback et al. [30], who gave a polynomial-time approximation algorithm that finds a solution with maximum interference O(n 1/4 · OPT(P )) for any given set of points P on a line, and a one-dimensional construction showing that OPT(P ) ∈ Ω( √ n) in the worst case, where n = |P |. Halldórsson and Tokuyama [12] gave a polynomial-time algorithm that returns a solution with maximum interference O( √ n) for any given set of n points in the plane. Buchin [5] showed that finding an optimal solution (one whose maximum interference is exactly OPT(P )) is NP-complete in the plane. Tan et al. [29] gave an O(n 3 n O(OPT(P )) )-time algorithm for finding an optimal solution for any given set of points P on a line. Kranakis et al. [20] showed that for any set of points P selected uniformly at random from the unit interval, the maximum interference of the nearest-neighbour path (MST) has maximum interference Θ( √ log n) with high probability. Finally, Sharma et al. [28] consider heuristic solutions to the two-dimensional problem.

Unidirectional Interference Model
If communication links are not bidirectional (i.e., edges are directed) and the communication graph is required to be strongly connected, then the worst-case maximum interference decreases. Under this model, von Rickenback et al. [31] and Korman [18] give polynomial-time algorithms that return solutions with maximum interference O(log n) for any given set of points in the plane, and a one-dimensional construction showing that in the worst case OPT(P ) ∈ Ω(log n).

Minimizing Average Interference
In addition to results that examine the problem of minimizing the maximum interference, some work has addressed the problem of minimizing the average interference, e.g., Tan et al. [29] and Moscibroda and Wattenhofer [24].

Generalizing One-Dimensional Solutions
Before presenting our results on random sets of points, we begin with a brief discussion regarding the possibility of generalizing existing algorithms that provide approximate solutions for one-dimensional instances of the interference minimization problem (in an adversarial deterministic input setting).
Since the problem of identifying a graph that achieves the optimal (minimum) interference is NP-hard in two or more dimensions [5], it is natural to ask whether one can design a polynomial-time algorithm to return a good approximate solution. Although Rickenback et al. [30] give a Θ(n 1/4 )-approximate algorithm in one dimension [30], the current best polynomial-time algorithm in two (or more) dimensions by Halldórsson and Tokuyama [12] returns a solution whose maximum interference is O( √ n); as noted by Halldórsson and Tokuyama, this algorithm is not known to guarantee any approximation factor better than the immediate bound of O( √ n). The algorithm of Rickenback et al. uses two strategies for constructing respective communication graphs, and returns the graph with the lower maximum interference; an elegant argument that depends on Lemma 1 bounds the resulting worst-case maximum interference by Θ(n 1/4 · OPT(P )). The two strategies correspond roughly to a) MST(P ) and b) classifying every √ nth node as a hub, joining each hub to its left and right neighbouring hubs to form a network backbone, and connecting each remaining node to its closest hub. The algorithm of Halldórsson and Tokuyama applies -nets, resulting in a strategy that is loosely analogous to a generalization of the hub strategy of Rickenback et al. to higher dimensions. One might wonder whether the hybrid approach of Rickenback et al. might be applicable in higher dimensions. Specifically, can a good approximation factor be guaranteed by returning the better of the respective graphs returned by the -net algorithm of Halldórsson and Tokuyama and the communication graph determined by MST(P ) ? To apply this idea directly in two or more dimensions would require generalizing the following property established by von Rickenback et al.: Lemma 1 (von Rickenback et al. [30] (2005)) For any set of points P ⊆ R, However, von Rickenback et al. also show that for any n, there exists a set of n points P ⊆ R 2 such that OPT(P ) ∈ O(1) and inter(MST(P ) ) ∈ Θ(n), which implies that Lemma 1 does not hold in higher dimensions. Consequently, techniques such as those used by von Rickenback et al. to bound the approximation factor of their algorithm in one dimension do not immediately generalize to higher dimensions.

Randomized Point Sets
Although using the hybrid approach of von Rickenback et al. [30] directly may not be possible, Kranakis et al. [20] recently showed that if a set P of n points is selected uniformly at random from an interval, then the maximum interference of the communication graph determined by MST(P ) is Θ( √ log n) with high probability. Throughout this section, we assume general position of points; specifically, we assume that the distance between each pair of nodes is unique. This can be expressed formally as ∀{p 1 , p 2 , q 1 , q 2 } ⊆ P , We begin by introducing the following definitions: there is a path joining p and q in G consisting of at most three edges, each of which is of length less than dist(p, q).
Definition 5 (T (P )) Given a set of points P in R d , T (P ) is the set of all communication graphs G with V (G) = P such that no primitive edge {p, q} ∈ E(G) is bridged.
Let C(R, r, d) be the minimum number of d-dimensional balls of radius r required to cover a d-dimensional ball of radius R. The following property follows since R d is a doubling metric space for any constant d [13] (equivalently, R d and has constant doubling dimension [10,11]): We now bound the maximum interference of any graph in T (P ).
Theorem 3 Let P be a set of points in R d . For any graph G ∈ T (P ), Proof. We first normalize the scale of P to simplify the proof. Let Q = {p · α | p ∈ P } denote a uniform scaling of P by a factor of α = 1/d min (G) and let H denote the corresponding communication graph. That is, Similarly, scale transmission radii such that each node's transmission radius in Q is α times its corresponding node's transmission radius in P . Thus, We say an edge {q 1 , q 2 } ∈ E(H) causes interference at a node p if p is within the transmission range of either q 1 or q 2 . Let p be a node in V (H) that has interference inter(H). Let E(p) ⊆ E(H) be the set of all primitive edges that cause interference at p. Since there are inter(H) nodes whose transmission ranges cover p, we get that |E(p)| ≥ inter(H)/2. That is, there are at least inter(H)/2 primitive edges that cause interference at node p. Therefore, to prove the theorem it suffices to show that For each integer i, 0 ≤ i ≤ g, let V i be the set of all nodes in V (H) that are incident to an edge in E i and let V i ⊆ V i be the set of nodes in V i that have p in their transmission radii. By our assumption of general position, there is an injective function from the set of primitive edges in E i to nodes in V i , giving that By definition of E i , V i , and V i , every node in V i is contained in the ball with centre p and radius 2 i+1 . Furthermore, every node v in V i is contained in the ball with centre p and radius 2 i+2 , because either . Hence by (5), |E i |, |V i |, and |V i | are each ω(1). In particular, for a sufficiently large point set, Any ball of radius 2 i+1 can be covered with C(2 i+1 , 2 i−2 , d) balls of radius 2 i−2 . Therefore, by (6) and the pigeonhole principle, there must be a ball B i of radius 2 i−2 that contains a set of nodes V i , such that V i ⊆ V i and |V i | ≥ C(2 i+2 , 2 i−2 , d) + 1. Let W i be the set of nodes in V i that are adjacent to some node in V i by some edge in E i . Since the length of every edge in E i is at least 2 i and the ball B i has radius 2 i−2 , every node in W i must lie outside B i . Thus, We consider two cases: i) there is a node q in W i that is adjacent to at least two nodes in V i by edges in E i , and ii) every node in W i is adjacent to only one node in V i by some edge in E i , i.e., |W i | ≥ |V i |. Case i. Let p 1 and p 2 denote two nodes in V i such that edges {p 1 , q} and {p 2 , q} are in E i . Without loss of generality, assume that dist(p 1 , q) > dist(p 2 , q) (by our general position assumption). Consider the path p 1 , p 2 , q from p 1 to q. This path has two edges. Also, dist(p 2 , q) < dist(p 1 , q) and dist(p 1 , p 2 ) < dist(p 1 , q), because dist(p 1 , p 2 ) ≤ 2 i−1 (as p 1 and p 2 are within a ball of radius 2 i−2 ) and dist(p 1 , p 2 ) ≥ 2 i (as the edge {p 1 , q} is in E i ). Since {p 1 , q} is a primitive edge in H and H ∈ T (Q), {p 1 , q} cannot be bridged, deriving a contradiction.
Case ii. We have |W i | ≥ |V i | ≥ C(2 i+2 , 2 i−2 , d) + 1. Since every node in W i lies in a ball of radius 2 i+2 (as W i ⊆ V i ), and a ball of radius 2 i+2 can be covered with C(2 i+2 , 2 i−2 , d) + 1 balls of radius 2 i−2 , there must be a ball of radius 2 i−2 that contains at least two nodes q 1 and q 2 from W i . By (7), W i ∩ V i = ∅. By definition, there must be two edges in E i that connect q 1 and q 2 to two distinct nodes p 1 and p 2 in V i . Without loss of generality, assume that dist(p 1 , q 1 ) > dist(p 2 , q 2 ). The length of the edge {p 1 , q 1 } is greater than those of {p 1 , p 2 }, {p 2 , q 2 } and {q 2 , q 1 }, because dist(p 1 , p 2 ) ≤ 2 i−1 , dist(q 1 , q 2 ) ≤ 2 i−1 , and dist(p 1 , q 1 ) ≥ 2 i (as {p 1 , q 1 } ∈ E i ). Therefore, every edge of the path of length three p 1 , p 2 , q 2 , q 1 from p 1 to q 1 has length less than dist(p 1 , q 1 ). (Notice that {p 1 , p 2 } and, similarly, {q 1 , q 2 }, are in E(H) since both p 1 and p 2 are inside a ball of radius 2 i−2 and the transmission ranges of p 1 and p 2 is at least 2 i , as they are incident to edges in E i .) Since {p 1 , q 1 } is a primitive edge in H and H ∈ T (Q), {p 1 , q} cannot be bridged, deriving a contradiction.
A contradiction is derived in both cases. Therefore, (4) holds. The result follows by (3) and (4) since set P and graph G correspond to Q and H, respectively, upon scaling by 1/α = d min (G).
In the next lemma we show that MST(P ) is in T (P ). Consequently, T (P ) is always non-empty.
Lemma 4 For any set of points P ⊆ R d , MST(P ) ∈ T (P ).
Proof. The transmission range of each node p ∈ P is determined by the length of the longest edge adjacent to p in MST(P ). Suppose there is a primitive edge {p 1 , p 2 } ∈ MST(P ) that is bridged. Therefore, there is a path T from p 1 to p 2 in MST(P ) that contains at most three edges, each of which is of length less than dist(p 1 , p 2 ). Removing the edge {p 1 , p 2 } partitions MST(P ) into two connected components, where p 1 and p 2 are in different components. By definition, T contains an edge that spans the two components. The two components can be joined using this edge (of length less than dist(p 1 , p 2 )) to obtain a new spanning tree whose weight is less than that of MST(P ), deriving a contradiction. Therefore, no primitive edge {p 1 , p 2 } ∈ MST(P ) can be bridged, implying MST(P ) ∈ T (P ).
Theorem 3 implies that the interference of any graph G in T (P ) is bounded asymptotically by the logarithm of the ratio of the longest and shortest edges in G. While this ratio can be arbitrarily large in the worst case, we show that the ratio is bounded for many typical distributions of points. Specifically, if the ratio is O(n c ) for some constant c, then the maximum interference is O(log n).
Definition 6 (D) Let D denote the class of distributions over [0, 1] d such that for any D ∈ D and any set P of n ≥ 2 points selected independently at random according to D, the minimum distance between any two points in P is greater than n −c with high probability, for some constant c (independent of n).
Theorem 5 For any integers d ≥ 1 and n ≥ 2, any distribution D ∈ D, and any set P of n points, each of which is selected independently at random over [0, 1] d according to distribution D, with high probability, for all graphs G ∈ T (P ), inter(G) ∈ O(log n).
The result follows from (8) Proof. Let p 1 , p 2 , . . . , p n , be n ≥ 2 independent random points in [0, 1] d with distribution D. Let c = 1+ log c +2 d and let E i , 1 ≤ i ≤ n, denote the event that there is a point p j , j = i, such that dist(p i , p j ) ≤ n −c . Let the random variable d min be equal to min i =j dist(p i , p j ). We have where the inequality holds by the union bound. To establish an upper bound on Pr(E i ), consider a d-dimensional ball B i with centre p i and radius n −c . The probability that there is point p j , j = i, in that ball is at most c times the volume of Thus, by (9), we get Therefore, D ∈ D. Note, here c = c in Definition 6.

Corollary 7
The uniform distribution with domain [0, 1] d is in D.
By Corollary 7 and Theorem 5, we can conclude that if a set P of n ≥ 2 points is distributed uniformly in [0, 1] d , then with high probability, any communicaiton graph in G ∈ T (P ) will have maximum interference O(log n). This is expressed formally in the following corollary: Corollary 8 Choose any integers d ≥ 1 and n ≥ 2. Let P be a set of n points, each of which is selected independently and uniformly at random over [0, 1] d . With high probability, for all graphs G ∈ T (P ), inter(G) ∈ O(log n).

Mobility
Our results apply to the setting of mobility (e.g., mobile ad hoc wireless networks). Each node in a mobile network must periodically exchange information with its neighbours to update its local data storing positions and transmission radii of nodes within its local neighbourhood. The distribution of mobile nodes depends on the mobility model, which is not necessarily uniform. For example, when the network is distributed over a disc or a box-shaped region, the probability distribution associated with the random waypoint model achieves its maximum at the centre of the region, whereas the probability of finding a node close to the region's boundary approaches zero [14]. Since the maximum value of the probability distribution associated with the random waypoint model is constant [14], by Lemma 6 and Theorem 5, we can conclude that at any point in time, the maximum interference of the network is O(log n) with high probability. In general, this holds for any random mobility model whose corresponding probability distribution has a constant maximum value.

Local Algorithm
As discussed in Section 1.1, existing local algorithms for topology control attempt to reduce transmission radii, but not necessarily the maximum interference. By Lemma 4 and Theorem 5, if P is a set of n points selected according to a distribution in D, then with high probability inter(MST(P ) ) ∈ O(log n). Unfortunately, a minimum spanning tree cannot be generated using only local information [17]. Thus, an interesting question is whether each node can assign itself a transmission radius using only local information such that the resulting communication graph belongs to T (P ) while remaining connected. We answer this question affirmatively and present the first local algorithm (LocalRadiusReduction), that assigns a transmission radius to each node such that if the initial communication graph G max is connected, then the resulting communication graph is a connected spanning subgraph of G max that belongs to T (P ). Consequently, the resulting topology has maximum interference O(log n) with high probability when nodes are selected according to any distribution in D. Our algorithm can be applied to any existing topology to refine it and further reduce its maximum interference. Thus, our solution can be used either independently, or paired with another topology control strategy. The algorithm consists of three phases, which we now describe.
Let P be a set of n ≥ 2 points in R d and let r max : P → R + be a function that returns the maximum transmission radius allowable at each node. Let G max denote the communication graph determined by P and r max . Suppose G max is connected. Algorithm LocalRadiusReduction assumes that each node is initially aware of its maximum transmission radius, its spatial coordinates, and its unique identifier.
The algorithm begins with a local data acquisition phase, during which every node broadcasts its identity, maximum transmission radius, and coordinates in a node data message. Each message also specifies whether the data is associated with the sender or whether it is forwarded from a neighbour. Every node records the node data it receives and retransmits those messages that were not previously forwarded. Upon completing this phase, each node is aware of the corresponding data for all nodes within its 2-hop neighbourhood. The algorithm then proceeds to an asynchronous transmission radius reduction phase.
Consider a node u and let f denote its furthest neighbour. If u and f are bridged in G max , then u reduces its transmission radius to correspond to that of its next-furthest neighbour f , where dist(u, f ) < dist(u, f ). This process iterates until u is not bridged with its furthest neighbour within its reduced transmission radius. We formalize the local transmission radius reduction algorithm in the pseudocode in Table 1 that computes the new transmission radius r (u) at node u.
Clearly, Algorithm LocalRadiusReduction is 2-local. Since transmission radii are decreased monotonically (and never increased), the while loop iterates O(∆) times, where ∆ denotes the maximum vertex degree in G max . Consequently, since each call to the subroutine Bridged terminates in O(∆ 2 ) time, each node determines its reduced transmission radius r (u) in O(∆ 3 ) time.
After completing the transmission radius reduction phase, the algorithm concludes with one final adjustement in the transmission radius to remove asymmetric edges. In this third and final phase, each node u broadcasts its reduced transmission radius r (u). Consider the set of nodes {v 1 , . . . , v k } ⊆ Adj(u) such that dist(u, v i ) = r (u) for all i (when points are in general position, k = 1, and there is a unique such node v 1 ). If r (v i ) < r (u) for all i, then u can reduce its transmission radius to that of its furthest neighbour with which bidirectional communication is possible. Specifically, The new value of r (u) as defined in (10) is straightforward to compute in O(∆) time.

Lemma 9
The communication graph constructed by Algorithm LocalRadiusReduction is in T (P ) and is connected if the initial communication graph G max is connected.
Proof. Let G min denote the communication graph constructed by Algorithm LocalRadiusReduction. First, we prove that G min is connected if G max is connected. Let and u and v belong to different connected components of G min } Suppose that G max is connected and G min is not connected. Therefore, Since {u , v } ∈ E(G min ), then we have that either r (u ) < dist(u , v ) or r (v ) < dist(u , v ). Without loss of generality, assume r (u ) < dist(u , v ). This implies that edge {u , v } is bridged in G max since, otherwise, result ← true 8 return result Table 1: Algorithm LocalRadiusReduction u could not reduce its transmission radius to less than dist(u , v ). By Definition 4, there is a path T between u and v in G max that contains at most three edges, each of which is of length less than dist(u , v ). Since T spans two different connected components in G min , there is an edge {u , v } in T such that u and v belong to two different connected components. Therefore, {u , v } ∈ E dif , as {u , v } ∈ E(G max ) and {u , v } ∈ E(G min ). Thus, dist(u , v ) < dist(u , v ), contradicting (11). Therefore, G min is connected if and only if G max is connected.
It remains to show that G min ∈ T (P ). Let {u, v} be any primitive edge in E(G min ). It suffices to show that {u, v} is not bridged in G min . By Definition 3, we have that dist(u, v) = min{r (u), r (v)}. Without loss of generality, assume r (u) = dist(u, v). The edge {u, v} is not bridged in G max , otherwise the transmission radius of u could be further reduced, resulting in the removal of {u, v} at the end of the third phase (where asymmetric edges are removed). Consequently, {u, v} is not bridged in G min , as G min is a subgraph of G max and any edge that is bridged in G min is also bridged in G max .
More generally, since transmission radii are only decreased, it can be shown that G min and G max have the same number of connected components by applying Lemma 9 on every connected component of G max .

Simulation
We simulated our local interference minimization algorithm to evaluate its performance in static and mobile wireless networks. In both settings, each node collects the list of its 2-hop neighbours in two rounds, applies the algorithm to reduce its transmission radius, and then broadcasts its computed transmission radius so neighbouring nodes can eliminate asymmetric edges and possibly further reduce their transmission radii. By the end of this stage, all asymmetric edges are removed and no new asymmetric edges are generated. Consequently, a node need not broadcast its transmission radius again after it has been further reduced.
We applied two mobility models to simulate mobile networks: random walk and random waypoint [15]. In both models each node's initial position is a point selected uniformly at random over the simulation region.
In the random walk model, each node selects a new speed and direction uniformly at random over [v min , v max ] and [0, 2π), respectively, at regular intervals. When a node encounters the simulation region's boundary, its direction is reversed (a rotation of π) to remain within the simulation region with the same speed. In the random waypoint model, each node moves along a straight trajectory with constant speed toward a destination point selected uniformly at random over [v min , v max ] and the simulation region, respectively. Upon reaching its destination, the node stops for a random pause time, after which it selects a new random destination and speed, and the process repeats.

Simulation Parameters
We set the simulation region's dimensions to 1000 metres × 1000 metres. For both static and dynamic networks, we varied the number of nodes n from 50 to 1000 in increments of 50. We fixed the maximum transmission radius r max for each network to 100, 200, or 300 metres. To compute the average maximum interference for static networks, for each n and r max we generated 100,000 static networks, each with n nodes and maximum transmission radius r max , distributed uniformly at random in the simulation region. To compute the average maximum interference for mobile networks, for each n and r max we generated 100,000 snapshots for each mobility model, each with n nodes and maximum transmission radius r max . We set the speed interval to [0.2, 10] metres per second, and the pause time interval to [0, 10] seconds (in the waypoint model). A snapshot of the network was recorded once every second over a simulation of 100,000 seconds.

Simulation Results
We compared the average maximum interference of the topology constructed by the algorithm LocalRa-diusReduction against the corresponding average maximum interference achieved respectively by two local topology control algorithms: i) the local computation of the intersection of the Gabriel graph and the unit   Figure 1 displayed with a bounded y-axis to emphasize relative differences disc graph (with unit radius r max ) [4], and ii) the cone-based local topology control (CBTC) algorithm [21]. In addition, we evaluated the maximum interference achieved when each node uses a fixed radius of communication, i.e., the communication graph is a unit disc graph of radius r max (100, 200, or 300 metres, respectively). These results are displayed in Figures 1 and 2.  As shown, the average maximum inteference of the unit disc graph topologies increases linearly with n. Many of the unit disc graphs generated were disconnected when the transmission radius was set to 100 metres for small n. Since we require connectivity, we only considered values of n and r max for which at least half of the networks generated were connected. When r max = 100 metres, a higher average maximum interference was measured at n = 300 than at n = 400. This is because many networks generated for n = 300 were discarded due to being disconnected. Consequently, the density of networks simulated for n = 300 was higher than the average density of a random network with n = 300 nodes, resulting in higher maximum interference.
Although both the local Gabriel and CBTC algorithms performed significantly better than the unit disc graphs, the lowest average maximum interference was achieved by the LocalRadiusReduction algorithm, which is clearly seen to be logarithmic in n in Figures 3 and 4. Note that the LocalRadiusReduction algorithm reduces the maximum interference to O(log n) with high probability, irrespective of the initial maximum transmission radius r max . Figures 3 and 4 display the average maximum interference achieved by LocalRadiusReduction on mobile networks, plotting simulation results for both the random walk and random waypoint models, along with the corresponding results on a static network. Simulation results obtained using the random walk model closely match those obtained on a static network because the distribution of nodes at any time during a random walk is nearly uniform [8]. The average maximum interference increases slightly but remains logarithmic when the random waypoint model is used. The spatial distribution of nodes moving according to a random waypoint model is not uniform, and is maximized at the centre of the simulation region [14]. Consequently, the density of nodes is high near the centre, resulting in greater interference at these nodes.
Finally, we evaluated the algorithm LocalRadiusReduction using actual mobility trace data of Piorkowski et al. [26], consisting of GPS coordinates for trajectories of 537 taxi vehicles recorded between May 17 and June 10, 2008, driving throughout the San Fransisco Bay area. Each taxi's trace contains between 1000 and 20,000 sample points. We selected the 500 largest traces, each of which has over 8000 sample points. To implement our algorithm, we selected n taxis among the 500 uniformly at random, ranging from n = 50 to n = 500 in increments of 50. As seen in Figure 5, the resulting average maximum interference is similar to that measured in our simulation results.