Interference in Wireless MobileNetworksbyAlireza HaghnegahdarB.A.Sc., Shiraz University, 2010A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)May 2014c© Alireza Haghnegahdar 2014AbstractGiven a set of positions for wireless nodes, the interference minimizationproblem is to assign a transmission radius (i.e., a power level) to each nodesuch that the resulting communication graph is connected, while minimizingthe maximum (respectively, average) interference. We consider the modelintroduced by von Rickenbach et al. (2005), in which each wireless node isrepresented by a point in Euclidean space on which is centered a transmis-sion range represented by a ball, and edges in the corresponding graph aresymmetric. The problem is NP-complete in two or more dimensions (Buchin2008) and no polynomial-time approximation algorithm is known. We showhow to solve the problem efficiently in settings typical for wireless ad hocnetworks. We show that if node positions are represented by a set P of npoints selected uniformly and independently at random over a d-dimensionalregion, then the topology given by the closure of the Euclidean minimumspanning tree of P has O(log n) maximum interference, O(1) average inter-ference with high probability and O(1) expected average interference. Thiswork is the first to examine average interference in random settings. Weextend the first bound to a general class of communication graphs over abroad set of probability distributions. We present a local algorithm thatconstructs a graph from this class; this is the first local algorithm to provideiiAbstractan upper bound on expected maximum interference. To verify our results,we perform an empirical evaluation using synthetic as well as real worldnode placements.iiiPrefacePart of Chapter 1 - 5 have been published in conferences and journals, asmentioned below.• M. Khabbazian, S. Durocher, A. Haghnegahdar, and F. Kuhn, Bound-ing interference in wireless ad hoc networks with nodes in random po-sition. Published in IEEE/ACM Transactions on Networking, 2014.• M. Khabbazian, S. Durocher, and A. Haghnegahdar, Bounding inter-ference in wireless ad hoc networks with nodes in random position. InProceedings of the 19th international conference on Structural Infor-mation and Communication Complexity (SIROCCO’12).The main problem was proposed and designed by Professor M. Khab-bazian and S. Durocher. The author has had the main responsibility in de-veloping the original ideas, analysis as well as writing the Chapter 3. Profes-sor S. Durocher, M. Khabbazian and the author helped with the manuscriptpreparation for these papers which is included in Chapter 2. The author hasimplemented the software to perform all the numerical analysis and com-puter simulations for all of the aforementioned papers. This results arerepresented in Chapter 4. Furthermore, Professor F. Kuhn helped us withthe proof of Theorem 2 presented in the journal paper.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . xiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 System Model and Definitions . . . . . . . . . . . . . . . . . 51.3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . 111.5 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . 13vTable of Contents2 Minimizing Maximum Interference in Random Networks 152.1 Generalizing One-Dimensional Solutions . . . . . . . . . . . . 152.2 Randomized Point Sets . . . . . . . . . . . . . . . . . . . . . 172.3 Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4 Local Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 253 Minimizing Average Interference in Random Networks . . 303.1 Expected Average Interference of Random Networks . . . . . 303.2 Average Interference of Random Networks . . . . . . . . . . 384 Empirical Evaluations . . . . . . . . . . . . . . . . . . . . . . . 504.1 Topology Control Algorithms . . . . . . . . . . . . . . . . . . 514.1.1 Cone Based Topology Control . . . . . . . . . . . . . 514.1.2 Gabriel Topology Control . . . . . . . . . . . . . . . . 524.1.3 k-neighbour Algorithm . . . . . . . . . . . . . . . . . 524.1.4 Local Radius Reduction Algorithm . . . . . . . . . . 534.1.5 Fixed Range Algorithm . . . . . . . . . . . . . . . . . 544.2 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . 544.3 Maximum Interference Results . . . . . . . . . . . . . . . . . 554.4 Average Interference Results . . . . . . . . . . . . . . . . . . 655 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 69Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71viList of Tables2.1 LocalRadiusReduction(u) . . . . . . . . . . . . . . . . . . 272.2 Redundant(a, b) . . . . . . . . . . . . . . . . . . . . . . . . . 28viiList of Figures1.1 A set of points P = {a, b, c, d, e} in R2 and two communicationgraphs on P , denoted G1 and G2, illustrating radii of trans-mission by their corresponding discs. Nodes b and c can com-municate in G1 and G2 because dist(b, c) ≤ min{r(b), r(c)}.Node b receives interference from node a inG1 andG2 becausedist(a, b) ≤ r(a), but the two nodes cannot communicate inG1 because dist(a, b) > r(b). The maximum interference inG1 is 4, achieved at node c. The maximum interference in G2is 3, achieved at nodes b, c, and d. G2 is an optimal solutionfor P , i.e., OPT(P ) = 3. . . . . . . . . . . . . . . . . . . . . . 63.1 The right side of above figure shows the entire network whichis divided into square cells by Gridηη2 ,η2(solid lines). The leftside shows a small part of both entire network and Gridηη4 ,η4(dotted lines). The highlighted cells in Gridηη4 ,η4illustrate thenon-complete cells which do not fall completely in [0, 1]2 region. 414.1 Maximum Interference in Static Networks . . . . . . . . . . . 564.2 Maximum Interference in Static Networks . . . . . . . . . . . 57viiiList of Figures4.3 Expected Average Interference in Static Networks . . . . . . . 574.4 Average Physical Degree in Static Networks . . . . . . . . . . 584.5 Average Energy Cost in Static Networks . . . . . . . . . . . . 584.6 Average Maximum Interference in Mobile Networks . . . . . . 604.7 Expected Average Interference in Mobile Networks . . . . . . 604.8 Average Physical Degree in Mobile Networks . . . . . . . . . 614.9 Average Energy Cost in Mobile Networks . . . . . . . . . . . 614.10 Average Maximum Interference in Real-world Networks . . . 634.11 Expected Average Interference in Real-world Networks . . . . 634.12 Average Physical Degree in Real-world Networks . . . . . . . 644.13 Average Energy Cost in Real-world Networks . . . . . . . . . 644.14 Average Interference . . . . . . . . . . . . . . . . . . . . . . . 664.15 Average interference histogram for a network with 500 nodes 664.16 Average Interference . . . . . . . . . . . . . . . . . . . . . . . 674.17 Average Interference histogram for 8000 snapshots and 50Vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68ixGlossarySINR Signal to Interference plus Noise RatioMST Minimum Spanning TreeGPS Global Positioning SystemCBTC Cone Based Topology ControlUDG Unit Disk GraphOPT Optimal Maximum InterferenceOPTAvg Optimal Average interferenceRWP Random Way PointRW Random WalkxAcknowledgmentsFirst and foremost, I would like to thank Prof. Majid Khabbazian for theguidance and support that he has provided and Prof. Vijay K. Bhargavafor being my supervisor. This thesis would not have been possible withouttheir suggestions, advice and constant encouragement.Furthermore, I would like to extend my gratitude to my colleagues inthe Information Theory and Systems laboratory and all of my friends inUBC, for creating a memorable and pleasant moments with their valuablesuggestions and constant support.Finally, a heartfelt and deep thanks go to my family, who have alwaysencouraged me and given their unconditional support through my studiesat the University of British Columbia. Without their support, I could nothave completed this thesis.xiDedicationTo my family...xiiChapter 1Introduction1.1 MotivationEstablishing connectivity in a wireless network can be a complex task forwhich various (sometimes conflicting) objectives must be optimized. Topermit a packet to be routed between any two nodes in a network, thecorresponding communication graph must be connected. In addition torequiring connectivity, various properties can be imposed on the network,including low power consumption [1, 2], bounded average traffic load [3, 4],small average hop distance between sender-receiver pairs [5], low dilation (t-spanner) [5–11], and minimal interference; this latter objective, minimizinginterference, is the focus of much recent research [2, 5, 12–28] and of thisresearch.The amplitude of a radio signal transmitted at a node p and received ata node q decreases as the distance between p and q increases. The signalfrom p must be sufficiently strong for q to receive it. That is, for a giventransmission power level at node p, there exists some threshold, say r(p),such that if q receives a message from p, then the distance from p to q canbe at most r(p). We model transmission in a wireless network by assigningto each wireless node p a radius of transmission r(p), such that every node11.1. Motivationwithin distance r(p) of p can receive a transmission from p, whereas no nodeat greater distance from p can. However, the distance between p and q aloneis not sufficient to determine successful communication between p and q;even if q is within distance r(p), signals sent from other nodes could interferewith the signal from p received at q. We adopt the interference modelintroduced by von Rickenbach et al. [12] which is related to the geometricradio network model of Dessmark and Pelc [29] and other early geometricmodels for wireless networks [30, 31].We measure interference at node p by the number of nodes that have pwithin their respective radii of transmission. Given a set of wireless nodeswhose positions are represented by a set of points P , we consider the prob-lem of identifying a connected network on P that minimizes the maximum(respectively, average) interference. The problem of constructing the net-work is equivalent to that of assigning a transmission radius to each node(in general, Θ(n) distinct radii are assigned to a set of n nodes); once thetransmission radius of each node is fixed, the corresponding communicationgraph and its associated maximum interference are also determined. Con-versely, once a graph is fixed, each node’s transmission radius is determinedby the distance to its furthest neighbour.In contrast to the algorithmic community which focuses on protocol mod-els, the communication networks researchers are working with models whereinterference accumulation, attenuation, antenna height and orientation, ter-rain, surface reflection and absorption, and so forth is also taken into ac-count [32, 33]. Physical model is one of the standard models for wirelessnetworks. In this model, the energy of a signal fades with the power of the21.1. Motivationpath-loss parameter. If the signal strength received at the receiver side di-vided by the strength of interference caused by concurrent transmitters plusnoise (SINR) is above some threshold the receiver can decode the messagesuccessfully.Beside the interference, channel (the link between nodes of our network)characteristics such as small scale fading and large scale shadowing will affectthe signal quality at the receiver side. Small scale fading is often handledwith diversity schemes and retransmit. Large scale shadowing on the otherhand is very dependent on the location of receiver and cannot always befixed. Considering these models for the links between the nodes will affectthe shape of uniform disk that we consider earlier. For instance, in theexistence of shadowing the uniform disk might have some holes dependingon the location with respect to obstacles.Clearly, every study does not need to use the detailed radio model andalso explore every variation in the wide parameter space. The level of detailfor a given study depends closely on the characteristics of that study. Diskmodel and, in particular, the interference minimization problem appliedto this model are the focus of numerous publications and have generatedsignificant recent research interest [5, 12, 13, 16–27]. Furthermore, a numberof important algorithmic questions remain open with respect to interferenceminimization in this model. While models such as SINR arguably providea more realistic physical representation of interference in a wireless network(e.g., [34–38]), algorithmic problems such as interference minimization aresignificantly more difficult to solve in the SINR model, motivating continuedexamination of interference minimization under both models. Finally, in31.1. Motivationsome cases, a solution to a problem set in the model used in this work leadsto an approximate solution to the corresponding problem under the SINRmodel (e.g., [23]). See Section 1.2 for a formal definition of the model andsee Figure 1.1 for an example.Given a set of points P in the plane, finding a connected graph on P thatminimizes the maximum interference is NP-complete [17]. A polynomial-time algorithm exists that returns a solution with maximum interferenceO(√n), where n = |P | [16]. Even in one dimension, for every n there existsa set of n points P such that any graph on P has maximum interferenceΩ(√n) [12]. All such known examples involve specific constructions (i.e.,exponential chains). We are interested in investigating a more realistic classof wireless networks: those whose node positions observe common randomdistributions that better model actual wireless ad hoc networks.When nodes are positioned on a line (sometimes called the highwaymodel), a simple heuristic is to assign to each node a radius of transmis-sion that corresponds to the maximum of the distances to its respectivenearest neighbours to the left and right. In the worst case, such a strategycan result in Θ(n) maximum interference when an optimal solution has onlyΘ(√n) maximum interference [12]. Recently, Kranakis et al. [21] showedthat if n nodes are positioned uniformly at random on an interval, thenthe maximum interference provided by this heuristic is Θ(√log n) with highprobability.41.2. System Model and Definitions1.2 System Model and DefinitionsWe represent the position of a wireless node as a point in Euclidean space,Rd, for some fixed1 d ≥ 1.For simplicity, we refer to each node by its corresponding point. Sim-ilarly, we represent a wireless network by its communication graph, a geo-metric graph whose vertices are a set of points P ⊆ Rd. Given a (simple andundirected) graph G, we employ standard graph-theoretic notation, whereV (G) denotes the vertex set of G and E(G) denotes2 its edge set.We say vertices u and v are k-hop neighbours if there is a simple pathof length k from u to v in G. When k = 1 we say u and v are neighbours.The k-hop neighbourhood of a node u is the union of the sets of its k′-hopneighbours for all k′ ≤ k.We assume each node has a range of communication that is equal in everydirection (i.e., a radius of transmission), that different nodes can have differ-ent transmission radii, and we consider bidirectional communication links,each of which is represented by an undirected graph edge connecting twonodes. Specifically, each node p has some radius of transmission, denoted bythe function r : P → R+, such that a node q receives a signal from p (possi-bly interference) if and only if dist(p, q) ≤ r(p), where dist(p, q) = ‖p− q‖2denotes the Euclidean distance between points p and q in Rd. Similarly, anode q can communicate with p if and only if dist(p, q) ≤ min{r(p), r(q)}.1In the majority of instances, two or three dimensions suffice to model an actual wirelessnetwork. Our results are presented in terms of an arbitrary d since this permits expressinga more general result without increasing the complexity of the corresponding notation.2Note, E(G) denotes the edge set of a graph G, whereas E[X] denotes the expectedvalue of the random variable X.51.2. System Model and Definitions2ar(a)cbd eaG1 Gcbd eFigure 1.1: A set of points P = {a, b, c, d, e} in R2 and two communicationgraphs on P , denoted G1 and G2, illustrating radii of transmission by theircorresponding discs. Nodes b and c can communicate in G1 and G2 becausedist(b, c) ≤ min{r(b), r(c)}. Node b receives interference from node a in G1and G2 because dist(a, b) ≤ r(a), but the two nodes cannot communicate inG1 because dist(a, b) > r(b). The maximum interference in G1 is 4, achievedat node c. The maximum interference in G2 is 3, achieved at nodes b, c, andd. G2 is an optimal solution for P , i.e., OPT(P ) = 3.Interference at a node q is defined by the number of nodes from whichit can receive a signal, whereas connectivity in the communication graphis determined by the nodes with which q can communicate. For simplicity,suppose each node has an infinite radius of reception, regardless of its radiusof transmission; that is, a node q can receive interference from any node p ifr(p) is sufficiently large, regardless of r(q). See Figure 1.1 for an example.Definition 1 (Communication Graph). A graph G is a communicationgraph with respect to a point set P ⊆ Rd and a function r : P → R+if1. V (G) = P , and2. for all vertices p and q in V (G),61.2. System Model and Definitions{p, q} ∈ E(G)⇔ dist(p, q) ≤ min{r(p), r(q)}. (1.1)Together, set P and function r uniquely determine the correspondingcommunication graph G. Alternatively, a communication graph can be de-fined as the closure of a given embedded graph. Specifically, if instead ofbeing given P and r, we are given an arbitrary graph H embedded in Rd,then the set P is trivially determined by V (H) and a transmission radiusfor each node p ∈ V (H) can be assigned to satisfy (1.1) byr(p) = maxq∈Adj(p)dist(p, q), (1.2)where Adj(p) = {q | {q, p} ∈ E(H)} denotes the set of vertices adjacent top in H. The communication graph determined by H is the unique edge-minimal supergraph of H that satisfies Definition 1. We denote this graphby H ′ and refer to it as the closure of graph H. Therefore, a communicationgraph G can be defined either as a function of a set of points P and anassociated mapping of transmission radii r : P → R+, or as the closure of agiven embedded graph H (where G = H ′).Definition 2 (Interference). Given a communication graph G, the interfer-ence at a node p ∈ V (G) or at a point p ∈ Rd isinterG(p) = |{q | q ∈ V (G), dist(q, p) ≤ r(q)}| ,the maximum interference of G isinter(G) = maxp∈V (G)interG(p),71.2. System Model and Definitionsand the average interference of G isinterAvg(G) =1|V (G)|∑p∈V (G)interG(p).In other words, the interference at p, denoted interG(p), is the numberof nodes q such that p lies within q’s radius of transmission3. This does notimply the existence of the edge {p, q} in the corresponding communicationgraph G; such an edge exists if and only if the relationship is reciprocal, i.e.,q also lies within p’s radius of transmission.Given a point set P , let G(P ) denote the set of connected communica-tion graphs on P . Let OPT(P ) denote the optimal maximum interferenceattainable over graphs in G(P ). That is,OPT(P ) = minG∈G(P )inter(G)= minG∈G(P )maxp∈V (G)interG(p).Similarly, let OPTAvg(P ) denote the optimal average interference attainableover graphs in G(P ). That is,OPTAvg(P ) = minG∈G(P )interAvg(G).Thus, given a set of points P representing the positions of wireless nodes,3In some definitions of interference a node cannot cause interference with itself. Whenp is a node in V (G), the respective values of interference for the two definitions differby an additive factor of one. We include p in the tally to allow a more general measureof interference whose definition applies consistently at any point p in Rd, regardless ofwhether p coincides with a node in V (G).81.3. Literature Reviewthe maximum interference minimization problem is to find a connected com-munication graph G on P that spans P such that the maximum interferenceis minimized (i.e., its maximum interference is OPT(P )). Similarly, theaverage interference minimization problem is to find a connected commu-nication graph G on P that spans P such that the average interference isminimized (i.e., its average interference is OPTAvg(P )).We examine the maximum and average interference of the communica-tion graph determined by the closure of MST(P ), where MST(P ) denotesthe Euclidean minimum spanning tree of the point set P . Our results applywith high probability, which refers to probability at least 1 − n−c, wheren = |P | denotes the number of network nodes and c ≥ 1 is an arbitraryfixed constant.1.3 Literature ReviewSelecting a proper interference and network model can affect analysis of wire-less networks in terms of performance, accuracy and scalability. Burkhart etal. [39] proposed a sender centric measure for the graph-based interferencemodel which evaluates the interference as the number of nodes affected bythe communication over a particular edge in the network. Alternatively,receiver centric interference model, presented by von Rickenbach et al. [40],focuses on the interference at the receiving node. In this model, interferenceat node p is defined as the number of nodes disturbing the reception of amessage at p. Our work is examining a node interference model similar to[40]. To analyze the network interference, existing articles typically consider91.3. Literature Reviewthe worst possible node placement. However, such node placements may bevery infrequent or never appear in real world. Therefore, instead of theworst case analysis, we perform an average case analysis, where nodes arerandomly placed in the network.considering the receiver centric interference model, the network’s inter-ference is defined either as the maximum interference [40, 41] or the av-erage interference [42, 43] over all the nodes in the network. Given a setof points P in the plane, finding a connected graph on P that minimizesthe maximum interference is known to be NP-complete problem [44]. vonRickenbach et al. [40] proposed a polynomial time approximation algorithmto solve this problem with maximum interference Θ(n1/4) for nodes locatedon a line. Another polynomial-time algorithm exists that returns a solu-tion with maximum interference O(√n), where n = |P | in two (or more)dimensions [45]. Kranakis et al. [46] showed that if n nodes are positioneduniformly at random on an interval, then the maximum interference of Mini-mum Spanning Tree (MST) is Θ(√log n) with high probability. Khabbazianet al. [47] generalized this result to higher dimensions by showing that themaximum interference of a set of n points selected uniformly at random ina d-dimensional Euclidian space is O(log n), w.h.p. Devroye and Morin [26]strengthened this results by proving that the maximum interference of a setof n points selected uniformly at random is Θ(√log n), w.h.p.The average interference minimization problem has also been studied inthe literature. Moscibroda and Wattenhofer [48] showed that, when nodesare in general metric space, there is no approximation algorithm having anapproximation ratio better than Ω(log n) that can find the minimum average101.4. Thesis Organizationinterference, unless it holds that NP ∈ DTIME(nlog logn). Lou et al. [49]proposed a polynomial-time, O(n3∆), algorithm to find the minimum aver-age interference in one-dimensional line network, where ∆ is the maximumnode degree when each node is connected to every other node within itsmaximum transmission range. Later, they developed a more efficient algo-rithm that finds the minimum interference of a line network in time O(n∆2)[18]. For two-dimensional networks, Tan et al. [18] proposed an algorithmto compute minimum average interference in time nO(m log λ), where m is theminimum number of parallel lines so that all the nodes are located on thelines. However, in general, the minimum number of parallel lines to coverall the nodes is linear in n, that is m = Ω(n). Therefore, the time com-plexity of this algorithm is exponential in general. Finally, Khabbazian etal. [43] studied the problem of minimizing the average interference in two-dimensional networks when nodes are distributed uniformly at random andshowed that the expected average interference is O(1). We strengthen thisresult in Chapter 3 by showing that when nodes are distributed uniformlyat random the average interference is O(1), with high probability.1.4 Thesis OrganizationIn this thesis, we examine the corresponding interference minimization prob-lems in two and higher dimensions. In Chapter 2, we generalize the nearest-neighbour path used in the highway model to the Euclidean minimum span-ning tree (MST), and show that with high probability, the maximum inter-ference of the MST of a set of n points selected uniformly at random over a111.4. Thesis Organizationd-dimensional region [0, 1]d is O(log n), for any fixed d ≥ 1. As we show inChapter 2, our results also apply to a broad class of random distributions,denoted D, that includes both the uniform random distribution and realisticdistributions for modeling random motion in mobile wireless networks, aswell as to a large class of connected spanning graphs that includes the MST.In Section 2.4 we present a local algorithm that constructs a topologywhose maximum interference is O(log n) with high probability when nodepositions are selected according to a distribution in D. Previous local al-gorithms for topology control (e.g., the cone-based local algorithm (CBTC)[1]) attempt to reduce transmission radii (i.e., power consumption), but notnecessarily the maximum interference. Similarly, others attempt to mini-mize interference but do not guarantee connectivity (e.g., the k-neighboursalgorithm [28]). Although reducing transmission radii at many nodes is of-ten necessary to reduce the maximum interference, the two objectives differ;specifically, some nodes may require large transmission radii to minimizethe maximum interference. Ours is the first local algorithm to provide anon-trivial upper bound on maximum interference. Our algorithm can beapplied to any existing topology to refine it and further reduce its maximuminterference. Consequently, our solution can be used either independently,or paired with another topology control strategy.In Chapter 3 we consider the problem of minimizing the average inter-ference and show that the expected interference of the MST over a set ofn points selected uniformly at random in a d-dimensional region [0, 1]d isO(1). We also show that for any network size n, there exists a power levelassignment such that the average interference of the resulting communica-121.5. Publicationstion graph is O(1), with high probability. In other words, irrespective of thenumber of nodes in the network, with high probability, the average interfer-ence is smaller than a constant when nodes are uniformly distributed in thenetwork.Chapter 4 presents the analysis of an empirical evaluation of our algo-rithm with a suite of simulation results on static, mobile, and real GPStrack data. We consider the uniform distribution as the points random dis-tribution and generate 100, 000 snapshot of this network. For the dynamicnetworks, we use the node distribution probability function resulted fromRandom Way Point mobility model to generate the node distribution. Toanalysis the performance of our network in a real world scenario, we use theGPS location of 500 moving vehicle and considered them as the location ofnodes in our network. Finally, Chapter 5 concludes the thesis and presentspossible directions for future work.1.5 Publications• A. Haghnegahdar, M. Khabbazian, Average Interference in WirelessAd Hoc Networks with Nodes in Random Position. Submitted to TheInternational Symposium on DIStributed Computing (DISC), 2014.• M. Khabbazian, S. Durocher, A. Haghnegahdar, and F. Kuhn, Bound-ing interference in wireless ad hoc networks with nodes in random po-sition. Published in IEEE/ACM Transactions on Networking, 2014.• M. Khabbazian, S. Durocher, and A. Haghnegahdar, Bounding inter-131.5. Publicationsference in wireless ad hoc networks with nodes in random position. InProceedings of the 19th international conference on Structural Infor-mation and Communication Complexity (SIROCCO’12).• A. Haghnegahdar, M. Khabbazian, and V.K. Bhargava, ”Privacy Risksin Publishing Mobile Device Trajectories,” IEEE Wireless Communi-cations Letters, 2014.• R. Ramamonjison, A. Haghnegahdar , V.K. Bhargava, ”Joint opti-mization of clustering and cooperative beamforming in green cognitivewireless networks,” IEEE Transactions On Wireless Communications, 2014.14Chapter 2Minimizing MaximumInterference in RandomNetworks42.1 Generalizing One-Dimensional SolutionsBefore presenting our results on random sets of points, we begin with a briefdiscussion regarding the possibility of generalizing existing algorithms thatprovide approximate solutions for one-dimensional instances of the max-imum interference minimization problem (in an adversarial deterministicinput setting).Since the problem of identifying a graph that achieves the optimal (min-imum) interference is NP-hard in two or more dimensions [17], it is natu-ral to ask whether one can design a polynomial-time algorithm to returna good approximate solution. Although von Rickenbach et al. [12] give4Part of this chapter has been published in M. Khabbazian, S. Durocher, A. Haghne-gahdar, and F. Kuhn, Bounding interference in wireless ad hoc networks with nodes inrandom position. IEEE/ACM Transactions on Networking, 2014. And M. Khabbazian, S.Durocher, and A. Haghnegahdar, Bounding interference in wireless ad hoc networks withnodes in random position. (SIROCCO’12).152.1. Generalizing One-Dimensional Solutionsa Θ(n1/4)-approximate algorithm in one dimension [12], the current bestpolynomial-time algorithm in two (or more) dimensions by Halldo´rsson andTokuyama [16] returns a solution with maximum interference O(√n); asnoted by Halldo´rsson and Tokuyama, this algorithm is not known to guar-antee any approximation factor better than the immediate bound of O(√n).The algorithm of von Rickenbach et al. uses two strategies for constructingrespective communication graphs, and returns the graph with the lower max-imum interference; an elegant argument that depends on Lemma 1 boundsthe resulting worst-case maximum interference by Θ(n1/4 · OPT(P )). Thetwo strategies correspond roughly to a) MST(P )′ and b) classifying every√nth node as a hub, joining each hub to its left and right neighbouringhubs to form a network backbone, and connecting each remaining node toits closest hub. The algorithm of Halldo´rsson and Tokuyama applies -nets,resulting in a strategy that is loosely analogous to a generalization of the hubstrategy of von Rickenbach et al. to higher dimensions. One might wonderwhether the hybrid approach of von Rickenbach et al. might be applicable inhigher dimensions by returning MST(P )′ or the communication graph con-structed by the algorithm of Halldo´rsson and Tokuyama, whichever has lowermaximum interference. To apply this idea directly would require general-izing the following property established by von Rickenbach et al. to higherdimensions:Lemma 1 (von Rickenbach et al. [12] (2005)). For any set of points P ⊆ R,OPT(P ) ∈ Ω(√inter(MST(P )′)).162.2. Randomized Point SetsHowever, von Rickenbach et al. also show that for any n, there exists aset of n points P ⊆ R2 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 Rickenbach et al. donot immediately generalize to higher dimensions.2.2 Randomized Point SetsAlthough using the hybrid approach of von Rickenbach et al. [12] directlymay not be possible, Kranakis et al. [21] recently showed that if a set P ofn points is selected uniformly at random from an interval, then the maxi-mum interference of the communication graph determined by MST(P )′ isΘ(√log n) with high probability. Here we show that if points are selectedrandomly from O(1)-dimensional Euclidean space, with high probability, themaximum interference of MST(P )′ is O(log n). We start with some basicdefinitions.Definition 3 (Primitive Edge). Assume that a communication graph G isthe closure of some embedded graph H. An edge {p, q} ∈ E(G) is calledprimitive w.r.t. H if {p, q} ∈ E(H) and min {r(p), r(q)} = dist(p, q).Observe that because G is the closure of H, the radius of any node uis equal to the distance to its farthest neighbour in H and therefore, everynode is incident to at least one primitive edge.Definition 4 (Bridge). An edge {p, q} ∈ E(G) in a communication graphG is bridged if there is a path joining p and q in G consisting of at most172.2. Randomized Point Setsthree edges distinct from {p, q} such that for each of the three edges {x, y},dist(x, y) < dist(p, q), or dist(x, y) = dist(p, q) and {x, y} is primitive.Given a set of points P in Rd, let T (P ) denote the set of all communica-tion graphs G with V (G) = P such that G is the closure of some embeddedgraph H and such that no primitive edge in E(G) is bridged.Further, let C(R, r, d) be the minimum number of d-dimensional balls ofradius r required to cover a d-dimensional ball of radius R. The followingproperty holds since Rd is a doubling metric space for any constant d [50](equivalently, Rd has constant doubling dimension [51, 52]):Proposition 1. If d ∈ Θ(1) and R/r ∈ Θ(1), then C(R, r, d) ∈ Θ(1).For a given communication graph G, we define dmax(G) and dmin(G) asthe lengths of the longest and shortest edges of G, respectively. That is,dmax(G) := max{s,t}∈E(G) dist(s, t) and dmin(G) = min{s,t}∈E(G) dist(s, t).Halldo´rsson and Tokuyama [16], Maheshwari et al. [27], and Lou et al.[18] give centralized algorithms for constructing graphs G, each with maxi-mum interference O(log(dmax(G)/dmin(G))). As we show in Theorem 2, thisbound holds for any graph G in the class T (P ). In Section 2.4 we describea local algorithm for constructing a connected graph in T (P ) on any givenpoint set P .Theorem 2. Let P be a set of points in Rd. For any graph G ∈ T (P ),inter(G) ∈ O(log(dmax(G)dmin(G))).Proof. We first normalize the scale of P to simplify the proof. Let Q =182.2. Randomized Point Sets{p · α | p ∈ P} denote a uniform scaling of P by a factor of α = 1/dmin(G)and let H denote the corresponding communication graph. That is, {u, v} ∈E(G)⇔ {u · α, v · α} ∈ E(H). Similarly, scale transmission radii such thateach node’s transmission radius in Q is α times its corresponding node’stransmission radius in P . Thus,dmin(H) = 1 and dmax(H) =dmax(G)dmin(G). (2.1)Consider some node p and let U be the set of nodes that cause interference atp, i.e., U = {u ∈ V : dist(u, p) ≤ r(u)}. Let g = dlog dmax(H)e. We partitionthe set U into g + 1 subsets U0, U1, . . . , Ug, such that for each 0 ≤ i ≤ g,Ui ={u ∈ U : r(u) ∈ [2i, 2i+1)}. We will show that for all i ∈ {0, . . . , g},|Ui| ≤ C(2i+1, 2i−2, d) · C(2i+2, 2i−2, d). (2.2)Applying Proposition 1, this implies |Ui| = O(1) and thus |U | = O(log(dmax(H))),from which the claim of the theorem follows.Let us therefore fix some i ∈ {0, . . . , g} and assume for the sake ofcontradiction that (2.2) does not hold. First recall that every node v ∈ Vis adjacent to some primitive edge of length r(v). Hence, every node u ∈ Uiis adjacent to some primitive edge of length r(u) ∈ [2i, 2i+1). We can thusdefine a mapping ω : Ui → V such that for every u ∈ Ui, {u, ω(u)} is aprimitive edge of length r(u) ∈ [2i, 2i+1). Also note that all nodes in Ui arecontained in a ball with centre p and radius 2i+1. By Proposition 1, thisball can be covered with C(2i+1, 2i−2, d) balls of radius 2i−2. Thus, because192.2. Randomized Point Setswe assume (for contradiction) that (2.2) does not hold, by the pigeonholeprinciple, there must be a ball Bi of radius 2i−2 that contains a set U ′i of atleast C(2i+2, 2i−2, d) + 1 nodes from Ui. We define Wi := {ω(u) : u ∈ U ′i}.Because nodes in U ′i are in ball Bi (of radius 2i−2) and for all u ∈ U ′i ⊆ Ui,dist(u, ω(u)) ≥ 2i, we haveWi ∩ U′i = ∅. (2.3)We consider two cases: i) there are two nodes u1, u2 ∈ U ′i such thatω(u1) = ω(u2), and ii) for any two nodes u1, u2 ∈ U ′i , ω(u1) 6= ω(u2).Case i. We define w := ω(u1) = ω(u2). Without loss of generality, assumethat dist(u1, w) ≤ dist(u2, w). Because u1 and u2 are both in ball Bi,dist(u1, u2) ≤ 2i−1 and therefore dist(u1, u2) < dist(u1, w) ≤ dist(u2, w).Since {u1, w} is a primitive edge, the edge {u2, w} is bridged. Because also{u2, w} is a primitive edge, this is a contradiction to the assumption thatG ∈ T (P ).Case ii. We have |Wi| = |U ′i | ≥ C(2i+2, 2i−2, d) + 1. Since every node in Wilies in a ball of radius 2i−2+2i+1 < 2i+2, and because a ball of radius 2i+2 canbe covered with C(2i+2, 2i−2, d) + 1 balls of radius 2i−2, there must be a ballof radius 2i−2 that contains at least two nodes w1 and w2 from Wi. Assumethat u1, u2 ∈ U ′i such that ω(u1) = w1 and ω(u2) = w2. Without lossof generality, assume that either dist(u2, w2) ≥ dist(u1, w1) ≥ 2i. Becausedist(u1, u2) ≤ 2i−1, dist(w1, w2) ≤ 2i−1, and because {u1, w1} is primitive,this implies that {u2, w2} is bridged. Because {u2, w2} is a primitive edgetoo, this is a contradiction to the assumption that G ∈ T (P ).202.2. Randomized Point SetsA contradiction is derived in both cases. Therefore, (2.2) holds and thusthe claim of the theorem follows.In the next lemma, we show that MST(P )′ is in T (P ). Consequently,in particular T (P ) always includes a connected communication graph. Inorder to make MST(P ) unique, assume that there is a global order ≺ on allthe possible edges such that for any four nodes a, b, c, and d, dist(a, b) <dist(c, d) ⇒ {a, b} ≺ {c, d}. We assume that MST(P ) is the minimumspanning tree which is also minimal w.r.t. the global order ≺. Note that forevery MST, there is such a global order ≺ such that this is the case.Lemma 2. For any set of points P ⊆ Rd, MST(P )′ ∈ T (P ).Proof. By definition, all primitive edges are edges of MST(P ). Suppose thereis a primitive edge {p, q} ∈ E(MST(P )) that is bridged. Therefore, there isa path T from p to q in MST(P )′ that contains at most three edges, suchthat for each edge {x, y} 6= {p, q} of T , dist(x, y) < dist(p, q) or dist(x, y) =dist(p, q) and {x, y} is primitive and thus also {x, y} ∈ E(MST(P )). Assumethat {p′, q′} is the largest edge in T w.r.t. the global order ≺. We must havedist(p′, q′) = dist(p, q), as otherwise all edges in T will be smaller than {p, q}w.r.t. the order ≺, hence a smaller MST can be constructed by replacing{p, q} with one of edges of T . Since {p, q} is bridged by T , the edge {p′, q′}has to be a primitive edge and therefore {p′, q′} ∈ E(MST(P )). However,this is a contradiction to the assumption that MST(P ) is the minimal MSTw.r.t. the order ≺ as it is possible to get a smaller MST by replacing {p′, q′}with another edge of T .212.2. Randomized Point SetsTheorem 2 implies that the interference of any graph G in T (P ) isbounded asymptotically by the logarithm of the ratio of the longest andshortest edges in G. While this ratio can be arbitrarily large in the worstcase, we show that the ratio is bounded for many typical distributions ofpoints. Specifically, if the ratio is O(nc) for some constant c, then the max-imum interference is O(log n).Definition 5 (D). Let D denote the class of distributions over [0, 1]d suchthat for any D ∈ D and any set P of n ≥ 2 points selected independently atrandom according to D, the minimum distance between any two points in Pis greater than n−c with high probability, for some constant c (independentof n).Theorem 3. 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 randomover [0, 1]d according to distribution D, with high probability, for all graphsG ∈ T (P ), inter(G) ∈ O(log n).Proof. Let dmin(G) = min{s,t}∈E(G) dist(s, t) and dmax(G) = max{s,t}∈E(G) dist(s, t).Since points are contained in [0, 1]d, dmax(G) ≤√d. Points in P are dis-tributed according to a distribution D ∈ D. By Definition 5, with highprobability, dmin(G) ≥ n−c for some constant c. Thus, with high probabil-ity, we havelog(dmax(G)dmin(G))≤ log(√dn−c). (2.4)The result follows from (2.4), Theorem 2, and the fact that log(nc√d) ∈O(log n) when d and c are constant.222.2. Randomized Point SetsLemma 3. Let D be a distribution with domain [0, 1]d, for which there isa constant c′ such that for any point x ∈ [0, 1]d, we have D(x) ≤ c′, whereD(x) denotes the probability density function of D at x ∈ [0, 1]d. ThenD ∈ D.Proof. Let p1, p2, . . . , pn, be n ≥ 2 independent random points in [0, 1]d withdistribution D. Let c′′ = 1 + log c′+2d and let Ei, 1 ≤ i ≤ n, denote the eventthat there is a point pj , j 6= i, such that dist(pi, pj) ≤ n−c′′. Let the randomvariable dmin be equal to mini 6=j dist(pi, pj). We havePr(dmin ≤ n−c′′) = Pr∨1≤i≤nEi≤∑1≤i≤nPr(Ei), (2.5)where the inequality holds by the union bound. To establish an upper boundon Pr(Ei), consider a d-dimensional ball Bi with centre pi and radius n−c′′.The probability that there is point pj , j 6= i, in that ball is at most c′ timesthe volume of Bi ∩ [0, 1]d. The volume of Bi ∩ [0, 1]d is at most (2n−c′′)d.232.3. MobilityTherefore, Pr(Ei) ≤ c′(2n−c′′)d for every 1 ≤ i ≤ n. Thus, by (2.5), we getPr(dmin > n−c′′) ≥ 1−∑1≤i≤nPr(Ei)≥ 1− n · c′(2n−c′′)d= 1−c′2dnd+log c′+1≥ 1−c′2dn · 2d+log c′= 1−1n.Therefore, D ∈ D. Note, here c = c′′ in Definition 5.Corollary 4. The uniform distribution with domain [0, 1]d is in D.By Corollary 4 and Theorem 3, we can conclude that if a set P of n ≥ 2points is distributed uniformly in [0, 1]d, then with high probability, any com-munication graph in G ∈ T (P ) will have maximum interference O(log n).This is expressed formally in the following corollary:Corollary 5. Choose any integers d ≥ 1 and n ≥ 2. Let P be a set of npoints, 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).2.3 MobilityOur results apply to the setting of mobility (e.g., mobile ad hoc wirelessnetworks). Each node in a mobile network must periodically exchange in-formation with its neighbours to update its local data storing positions and242.4. Local Algorithmtransmission radii of nodes within its local neighbourhood. The distributionof mobile nodes depends on the mobility model, which is not necessarilyuniform. For example, when the network is distributed over a disc or abox-shaped region, the probability distribution associated with the randomwaypoint model achieves its maximum at the centre of the region, whereasthe probability of finding a node close to the region’s boundary approacheszero [4]. Since the maximum value of the probability distribution associatedwith the random waypoint model is constant [4], by Lemma 3 and Theo-rem 3, we can conclude that at any point in time, the maximum interferenceof the network is O(log n) with high probability. In general, this holds forany random mobility model whose corresponding probability distributionhas a constant maximum value.2.4 Local AlgorithmAs discussed in Section 1.1, existing distributed algorithms for topology con-trol attempt to reduce transmission radii, but not necessarily the maximuminterference. By Lemma 2 and Theorem 3, if P is a set of n points selected ac-cording to a distribution in D, then with high probability inter(MST(P )′) ∈O(log n). Unfortunately, a minimum spanning tree cannot be generatedusing only local information [53]. Thus, an interesting question is whethereach node can assign itself a transmission radius using only local informationsuch that the resulting communication graph belongs to T (P ) while remain-ing connected. We answer this question affirmatively by presenting a localalgorithm (LocalRadiusReduction), that assigns a transmission radius252.4. Local Algorithmto each node such that if an initial communication graph Gmax is connected,then the resulting communication graph is a connected spanning subgraphof Gmax that belongs to T (P ). Consequently, the resulting topology hasmaximum interference O(log n) with high probability when nodes are se-lected according to any distribution in D. Our algorithm can be appliedto any existing topology to refine it and reduce its maximum interference.Thus, our solution can be used either independently, or paired with anothertopology control strategy.For the distributed algorithm, we assume that each edge e has a uniqueidentifier ID(e). Such IDs can for example be obtained (locally) by usingunique node identifiers. The edge IDs allow to define a global order ≺ onall the possible edges of the communication graph as follows. For any twoedges {u1, v1} , {u2, v2} ∈ E(Gmax), we have {u1, v1} ≺ {u2, v2} if and onlyif dist(u1, v1) < dist(u2, v2) or dist(u1, v1) = dist(u2, v2) and ID({u1, v1}) <ID({u2, v2}).Let P be a set of n ≥ 2 points in Rd and let rmax : P → R+ be a functionthat returns the maximum transmission radius allowable at each node. LetGmax denote the communication graph determined by P and rmax. We sup-pose that Gmax is connected. Further, assume that Adjmax(u) is the set ofneighbours of a node u in Gmax. Algorithm LocalRadiusReduction as-sumes 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 whichevery node broadcasts its identity, maximum transmission radius, and co-ordinates in a node data message. Each message also specifies whether the262.4. Local AlgorithmLocalRadiusReduction(u)1 r′(u)← 02 for each v ∈ Adjmax(u) do5 if dist(u, v) > r′(u) and ¬Redundant(u, v) then6 r′(u)← dist(u, v)17 return r′(u)Table 2.1: LocalRadiusReduction(u)data is associated with the sender or whether it is forwarded from a neigh-bour. Every node records the node data it receives and retransmits thosemessages that were not previously forwarded. Upon completing this phase,each node is aware of the corresponding data for all nodes within its 2-hopneighbourhood. The algorithm then proceeds to a local transmission radiusreduction phase, which does not require any additional communication.We say that an edge {u, v} of Gmax is redundant iff there is a path atmost 3 connecting u and v such that for every edge {x, y} of the path, wehave {x, y} ≺ {u, v}. Let H be the graph consisting of all edges of Gmax thatare not redundant. The communication graph G is defined as the closureof graph H, i.e., G = H ′. Consequently, each node u chooses r(u) to bethe largest distance to a neighbour v ∈ Adjmax(u) such that {u, v} is notredundant. The details are given in Algorithm 2.1.Algorithm LocalRadiusReduction is 2-local, that is, each node onlyneeds to learn about the initial state of nodes at distance at most 2 inGmax. Further, the local computation time at each node is bounded byO(∆3), where ∆ is the maximum vertex degree in Gmax. Each call to thesubroutine Bridge costs at most O(∆2) time and there are at most ∆ callsto Bridge from each node.272.4. Local AlgorithmRedundant(a, b)1 result← false2 for each v ∈ Adjmax(a) do3 if v ∈ Adjmax(b) and{a, v} ≺ {a, b} and {v, b} ≺ {a, b} then4 result← true5 for each w ∈ Adjmax(v) do3 if w ∈ Adjmax(b) and {a, v} ≺ {a, b} and{v, w} ≺ {a, b} and {w, b} ≺ {a, b} then7 result← true8 return resultTable 2.2: Redundant(a, b)Theorem 6. The communication graph constructed by Algorithm Local-RadiusReduction is in T (P ) and it is connected if the initial communi-cation graph Gmax is connected.Proof. Let G denote the communication graph constructed by AlgorithmLocalRadiusReduction. We first prove that G is in T (P ). By construc-tion, G is the closure of the graph H consisting of all edges of Gmax that arenot redundant. An edge {u, v} is redundant if it is the largest w.r.t. globalorder ≺ in some cycle of length at most 4 in Gmax. Consequently, H has nocycles of length less than 5. For contradiction, assume that there is an edge{u, v} ∈ E(G) which is bridged and which is primitive (w.r.t. H). Then,there is a path T of length at most 3 that connects u and v such that foreach edge {x, y} of T , either dist(x, y) < dist(u, v) or dist(x, y) = dist(u, v)and {x, y} is primitive (w.r.t. H). Hence, G contains a cycle of length atmost 4 such that the longest edges of the cycle are all primitive (and thusalso edges of H). This cannot be because from each such cycle of Gmax thelargest edge w.r.t. ≺ is not included in H.282.4. Local AlgorithmIt remains to prove that G is connected if Gmax is connected. For contra-diction, assume that G and therefore also H is not connected and considera set S ⊂ V, S 6= ∅ such that H does not contain an edge between S andV \ S. Let e = {u, v} be the smallest edge of Gmax (w.r.t. ≺) over the cut(S, V \ S). Edge {u, v} cannot be redundant because every cycle of Gmaxthat contains {u, v} has to contain at least one other edge {u′, v′} across thecut (S, V \ S) and by assumption {u, v} ≺ {u′, v′}.More generally, since transmission radii are only decreased, it can beshown that Gmin and Gmax have the same number of connected componentsby applying Theorem 6 on every connected component of Gmax.29Chapter 3Minimizing AverageInterference in RandomNetworks53.1 Expected Average Interference of RandomNetworksWe now examine the problem of minimizing the average interference in aset of points whose positions are selected uniformly and independently atrandom over the unit square in the plane. This work is the first to examineaverage interference in a random setting.We refer to the following lemma by Wan et al., where the radius of a setP ⊆ Rd isradP = minp∈Pmaxq∈Pdist(p, q).Consequently, there exists a point p ∈ P such that a disc of radius radP5Part of this chapter will be published in A. Haghnegahdar, M. Khabbazian, Aver-age Interference in Wireless Ad Hoc Networks with Nodes in Random Position. To besubmitted to The International Symposium on DIStributed Computing (DISC), 2014.303.1. Expected Average Interference of Random Networkscentred at p covers P [54].Lemma 4 (Wan et al. [54] (2002)). For any set P ⊆ R2 of points withradius one,∑e∈E(MST(P ))‖e‖2 ≤ 12.In this section, we show that for any set P of points selected uniformlyand independently at random in a unit square, E[interAvg(MST′(P ))] ∈O(1). Interestingly, this result does not hold for every distribution in D (seeDefinition 5). For clarity of the proofs, throughout this section, we assumethat the distance between each pair of nodes is unique, i.e., that points inP are in general position.Lemma 5. For any set P ⊆ [0, 1]2 of n points selected uniformly and inde-pendently at random, with high probability, the longest edge in MST(P ) haslength lmax ∈ O(√(log n)/n).Proof. Choose any real number c ≥ 2. We divide [0, 1]2 into a square gridwith⌊√n/(c log n)⌋2square cells, each with side length⌊√c log n/n⌋≥√c log n/n. We say two distinct cells are adjacent if they share a side. Thedistance between any two points in adjacent cells is at mostl =√5⌊√c log n/n⌋∈ Θ(√log n/n).Assume each cell contains at least one node. If we select one representativenode in each cell, connect every node in each cell to its representative node,and connect representative nodes in adjacent cells, the resulting graph willbe connected with a maximum edge length of l. If every cell contains a node,313.1. Expected Average Interference of Random Networksthen the longest edge in MST(P ) has length at most l. Therefore, to provethe lemma it suffices to show that every cell contains at least one node withhigh probability.The probability that a given cell does not contain any node is at most(1−⌊√nc log n⌋−2)n≤(1−c log nn)n≤ exp(−c log nn· n)= n−c.By a union bound, the probability that every cell contains at least a nodeis at least 1− n1−c, which completes the proof.Definition 6 (Communication Coverage). Given a communication graphG and any node p ∈ V (G), the communication coverage of p is the regionwithin the transmission range of node p, which we denote covG(p). That iscovG(p) is the disc of radius r(p) centred at p. We define the communicationcoverage of G ascov(G) =⋃p∈V (G)covG(p).The following lemma shows that for any set of points P , the averageinterference within cov(MST′(P )) is constant. Note that this result appliesto a continuum of points in the plane, and not only to interference at discretepoints in P .Lemma 6. For any set of points P ⊆ R2, the average interference in323.1. Expected Average Interference of Random Networkscov(MST′(P )) is O(1), i.e.,1| cov(MST′(P ))|∫∫cov(MST′(P ))interMST′(P )(x, y) dx dy ∈ O(1).Proof. Choose any set of points P = {p1, . . . , pn} in R2. Let q be a pointselected uniformly at random in cov(MST′(P )). It suffices to show thatE[interMST′(P )(q)] ∈ O(1). Without loss of generality, suppose that P hasradius one. We partition cov(MST′(P )) into n disjoint regions R1, . . . ,Rnsuch that for each i, Ri includes all the points in R2 that are within thetransmission ranges of exactly i nodes in P . For each i, let ei denote thelongest edge in E(MST(P )) incident to the point pi ∈ P . Note that ei andej are not necessarily distinct for i 6= j. However, for every i, there is atmost one j 6= i such that ei = ej .E[interMST′(P )(q)] =∑ni=1 i|Ri|| cov(MST′(P ))|=∑ni=1 i|Ri|∑ni=1 |Ri|=∑ni=1 | covMST′(P )(pi)|∑ni=1 |Ri|=∑ni=1 pi‖ei‖2∑ni=1 |Ri|≤2∑e∈E(MST(P )) pi‖e‖2∑ni=1 |Ri|(3.1)≤2∑e∈E(MST(P )) pi‖e‖2∑e∈E(MST(P ))‖e‖24√3(3.2)= 8pi√3.333.1. Expected Average Interference of Random Networks(3.2) follows from (3.1) by the fact that the lozenges with ei as theirlargest diameters (with angles pi/3− ) do not overlap [54].Lemma 7. Let l be a positive real number, let S be a square of size l×l, andlet P a set of n points in S. If the transmission range of nodes is determinedby MST(P ), then the average interference in S is O(1), that is1l2∫∫SinterMST′(P )(x, y) dx dy ∈ O(1).Proof. Choose any set of points P = {p1, . . . , pn} in S. Let q be a point se-lected uniformly at random in S. It suffices to show that E[interMST′(P )(q)] ∈O(1). Without loss of generality, suppose l = 1/√2. Note that the radius ofP is at most one as the diameter of S is one. We partition S into n disjointregions R1, . . . ,Rn such that for each i, Ri includes all the points in R2 thatare within the transmission ranges of exactly i nodes in P . For each i, letei denote the longest edge in E(MST(P )) incident to the point pi ∈ P . We343.1. Expected Average Interference of Random NetworkshaveE[interMST′(P )(q)] =∑ni=1 i|Ri||S|= 2n∑i=1i|Ri|= 2n∑i=1| covMST′(P )(pi) ∩ S|≤ 2n∑i=1| covMST′(P )(pi)|= 2n∑i=1pi‖ei‖2≤ 4∑e∈E(MST(P ))pi‖e‖2≤ 4 · 12 (3.3)= 48,where (3.3) is by Lemma 4.Lemma 8. For any set of points P = {p1, . . . , pn} ⊆ R2 and any px ∈ P ,interMST′(P )(px) ≤ interMST′(P\{px})(px) + 6. (3.4)Proof. Without loss of generality, we show (3.4) holds when px = pi. For anypair {pi, pj} ⊆ {p2, . . . , pn}, we show that if the edge {pi, pj} ∈ E(MST(P )),then {pi, pj} ∈ E(MST(P \ {p1})). By contradiction, suppose there ex-ists a pair {pi, pj} ⊆ {p2, . . . , pn} such that {pi, pj} ∈ E(MST(P )) and353.1. Expected Average Interference of Random Networks{pi, pj} /∈ E(MST(P \{p1})). By removing {pi, pj}, MST(P ) is divided intotwo connected components, C1 and C2. Since MST(P \ {p1}) is connected,there must an edge {pk, pl} such that pk ∈ C1 and pl ∈ C2. Note that{pk, pl} 6= {pi, pj} by our assumption that {pi, pj} /∈ E(MST(P \ {p1})).Also, k 6= 1 and l 6= 1 since p1 is not in V (MST(P \ {p1})). Furthermore,dist(pk, pl) < dist(pi, pj) because otherwise by replacing the edge {pk, pl}with {pi, pj} we can reduce the sum of the lengths of edges in MST(P \{p1}).This derives a contradiction, however, as we can reduce the sum of length ofedges in MST(P ) by replacing {pi, pj} with {pk, pl}. The above argumentshows that the transmission range of any non-neighbour of p1 determinedby MST(P \ {p1}) is not more than its transmission range determined byMST(P ). We conclude the proof by noting that for any set of points Q,the maximum degree of MST(Q) is at most six, hence p1 has at most sixneighbours in MST(P ).Theorem 7. Let n be a positive integer. Let interAvg(MST′(P )) be a ran-dom variable equal to the average interference of a set P of n points dis-tributed uniformly and independently at random in [0, 1]2. ThenE[interAvg(MST′(P ))] ∈ O(1).Proof. Let P = {p1, . . . , pn} be a set of n points selected uniformly at ran-363.1. Expected Average Interference of Random Networksdom in [0, 1]2.E[interAvg(MST′(P ))] = E[1nn∑i=1interMST′(P )(pi)](3.5)=1nn∑i=1E[interMST′(P )(pi)](3.6)= E[interMST′(P )(p1)],where (3.5) holds because the expected value of a sum of random variables(independent or not) is equal to the sum of the individual expectations,and (3.6) holds by the fact that, due to symmetry, for every {pi, pj} ⊆{p1, . . . , pn},E[interMST′(P )(pi)]= E[interMST′(P )(pj)].Since p1 is selected uniformly and independently at random, by Lemma 7,we getE[interMST′(P\{p1})(p1)] ∈ O(1).Furthermore, by Lemma 8, we haveinterMST′(P )(p1) ≤ interMST′(P\{p1})(p1) + 6.Thus,E[interMST′(P )(p1)] ≤ E[interMST′(P\{p1})(p1)] + 6∈ O(1),373.2. Average Interference of Random Networkswhich completes the proof.3.2 Average Interference of Random NetworksBefore delving into the details of our proof, in this section, we provide someintuition about our approach and the main ideas used. We divide the net-work (a unit square) into a square grid with c · nlogn square cells, for someconstant c. We carefully select c such that, with high probability, i) everysquare cell contains θ(log n) points, and ii) the cell side is at least a fewtimes of the length of the largest edge of MST (P ).Next, we focus on the “local interference” at each cell C, that is interAvg(H ′C),where HC = MST (P )[PC ], PC ⊆ P is the set of points in the cell C, andMST (P )[PC ] is the subgraph of MST (P ) induced by PC . We show that,for every cell C,interAvg(H ′C) ≤ interAvg(MST′(PC)).Therefore, by [43] we conclude that the expected local average interferencein any cell is constant,E[interAvg(H ′C)] = O(1). Assume that there is thesame number of nodes in each cell. In this case, each cell has a fix numberof nodes distributed uniformly at random. Therefore, all cells have thesame average interference distribution. Also, by [43], the expected averageinterference in each cell is constant. Therefore, by the law of large numbers,for large enough n, the mean of average interferences over all cells is almostsurely constant.383.2. Average Interference of Random NetworksThere are two major problems to achieve the desired final result: 1)although the order of the number of nodes in each cell is the same, the exactnumber can differ from one cell to the other, hence we cannot directly applythe law of large numbers. 2) we have not accounted all the inferences asthere are crossing edges between cells that have not been considered.To deal with the first problem, we divide cells into O(log n) groups suchthat, in each group, every cell contains the same number of nodes. If thereis large enough number of cells in a group, we can apply the law of largenumbers on that group individually. For other groups (with lower numberof cells), we show that their effect on the overall average interference ofnetwork is limited by an additive constant.We approach the second problem by considering 16 different square gridsand show that any edge in MST (P ) causing interference at a node, togetherwith that node, will fall into one cell in at least one of these 16 grids.Since for each grid, the average of all local interferences is constant, withhigh probability, using a union bound, we conclude that the average of allinterferences occurred in at least one of these grids is constant, w.h.p., hencethe overall average interference of network is constant, w.h.p.Let Lmax denote the length of the largest edge in MST (P ). When npoints are distributed uniformly at random in a unit square, it was shownin [43] thatLmax ∈ O(√lognn),with high probability.Definition 7. (Gridda,b) We define the grid Gridda,b as the set of all squares393.2. Average Interference of Random Networks(simply called cells) with side length d centred at points (id+a, jd+b), wherei, j ∈ Z and 0 ≤ a, b < d.Definition 8. (Non-complete/complete cell) A cell C in a gird Gridda,b iscalled non-complete if C ∩ [0, 1]2 6= C. Otherwise, it is called complete. Inother words, a cell is complete if it entirely falls inside the network, and isnon-complete, otherwise.Definition 9. (Gridda,b) We define Gridda,b asGridda,b = {C|C ∈ Gridda,b ∧ C ∩ [0, 1]2 = C},that is, the set of all complete cells in Gridda,b.Let η = θ(√lognn)be a real number such that i) η ≥ 21−√24Lmax,and ii) 1η is an integer. Note that we can always find such a number ηas Lmax = O(√lognn). Also, the network is fully covered by the grid,Gridηη2 ,η2. Figure 3.1 illustrates two examples of these grids.The following lemma shows that when η is large enough, every cell inGridηη2 ,η2will contain θ(log n) nodes, w.h.p.Lemma 9. Let us divide the network into a gird such that the side length ofeach cell of the grid is√2c lognn , for some constant c ≥ 1. Fix any cell, andlet X be a random variable equal to the number of nodes in that cell. Then,we havePr(c log n ≤ X ≤ 3c log n) ≥ 1− n−c5 − n−c4 .Proof. Since nodes are distributed uniformly at random, the probabilitythat a node falls into a given cell is equal to the area of the cell, which is403.2. Average Interference of Random Networks {= 2c lognnGrid 2,2( 2 , 2 ){4Grid4,4{Figure 3.1: The right side of above figure shows the entire network which isdivided into square cells by Gridηη2 ,η2(solid lines). The left side shows a smallpart of both entire network and Gridηη4 ,η4(dotted lines). The highlighted cellsin Gridηη4 ,η4illustrate the non-complete cells which do not fall completely in[0, 1]2 region.413.2. Average Interference of Random Networks(√2c lognn)2= 2c lognn . Let fix a cell C. LetXi, 1 ≤ i ≤ n, be a {0, 1} randomvariable such that Xi = 1 if node i falls into C. Note that X1, X2, . . . , Xn isa set of independent Bernoulli variables with Pr(Xi = 1) =2c lognn for every1 ≤ i ≤ n. Let X =∑ni=1 xi. Therefore, we get E[X] = µ = 2c log n. By aChernoff bound, we havePr(X < (1− δ)µ) <(e−δ(1− δ)(1−δ))µ,andPr(X > (1 + δ)µ) <(eδ(1 + δ)(1+δ))µ.where µ is the expectation of X and δ > 0. Therefore, setting δ = 0.5, wegetPr(X < c log n) < n−c(1+ln(1/2)) < n−c4 ,andPr(X > 3c log n) < n−c(3 ln(3/2)−1) < n−c5 .Hence,Pr(c log n ≤ X ≤ 3c log n) ≥ 1− n−c5 − n−c4 .Using Lemma 9 and a union bound, we get that, when c is large enough,every cell of resulting grid will contain θ(log n) nodes, w.h.p.Lemma 10. Let P be a finite set of points in R2, and Q ⊆ P be a non-emptysubset of P . Let G = MST(Q), and H = MST(P )[Q] be the sub-graph of423.2. Average Interference of Random NetworksMST(P ) induced by Q. TheninterAvg(H ′) ≤ interAvg(G′)Proof. To prove the lemma, we show that for every point q ∈ Q, we haverH(q) ≤ rG(q)that is the transmission range of every node q ∈ Q determined by H is notmore that that determined by G. By contradiction, suppose that there is aq ∈ Q such that rH(q) > rG(q). Let e = {q, p} ∈ E(H) be the link deter-mining the transmission range of q. We must have e /∈ E(G) as otherwiserH(q) ≤ rG(q). Since G is connected, there is a sequence of distinct edgesei ∈ E(G), 1 ≤ i ≤ m, connecting q to p. We have,∀1 ≤ i ≤ m : ‖ei‖ ≤ ‖e‖because e /∈ E(G), and G is a minimum spanning tree. Since size of everyedge is assumed to be unique we get∀1 ≤ i ≤ m : ‖ei‖ < ‖e‖Since e ∈ H, we get e ∈ MST(P ) since H is a subgraph of MST(P ). Thisis a contradiction, because there is a sequence of edges from q to p (i.e. ,{e1, ..., em}) with edges whose size is less than ‖e‖.Consider a cell C and assume that Q = PC is the set of points in C.433.2. Average Interference of Random NetworksBy [43], we know that E[interAvg(MST (Q)′)] = O(1). Therefore, usingLemma 10, we get E[interAvg(H ′)] = O(1), where H = MST(P )[Q] and Pis the set of all nodes in the network.Note that, although every cell contains the same order of nodes w.h.p.,the actual number of nodes may differ from one cell to anther. Next, wedivide cells into groups Si, 1 ≤ i ≤ θ(log n), such that each group consists ofall cells that contain the same number of nodes. Formally, Si = {C | |PC | =i}, where |PC | denotes the number of nodes in cell C.We further classify groups Si into two partitions. First partition, P1,includes all groups that have at most nlog3 ncells, and the second partition,P2, includes the rest of groups. For any cell C, let HC = MST(P )[PC ], wherePC is the set of nodes in C. The following two lemmas show that the sum ofinterferences of nodes in each partition is O(n).Lemma 11. For groups in the first partition, P1, we have∑S∈P1∑C∈S∑p∈PCinterH′C(p) = O(n),w.h.p.Proof. The average interference in each cell is at most equal to the numberof nodes in that cell, which is θ(log n) w.h.p. Therefore, the sum of allinferences in a cell is θ(log2 n), that is, for any cell C,∑p∈PCinterH′C(p) = |PC | · θ(log n) = θ(log2 n),w.h.p. Note that the total number of groups is θ(log n), thus there are443.2. Average Interference of Random NetworksO(log n) groups in the first partition P1, w.h.p. Also, by definition eachgroup in the first partition has O( nlog3 n) cells in it. Consequently, the sumof interferences of all cells in the union of groups of the first partition is∑S∈P1∑C∈S∑p∈PCinterH′C(p) =nlog3 n·O(log n) · θ(log2 n)= O(n),w.h.p.Lemma 12. For groups in the second partition, P2, we have∑S∈P2∑C∈S∑p∈PCinterH′C(p) = O(n),w.h.p.Proof. Let S be any group in P2. By definition, all the cells in S contain thesame number of nodes. Also, nodes are distributed uniformly in each cell.Therefore, interAvg(H ′C), C ∈ S, is a collection of i.i.d random variables,whose expected value is O(1) by [43]. Thus, using the strong law of largenumbers, we almost surely have∑C∈S interAvg(H′C)|S|= O(1)when |S| is sufficiently large (or, equivalently, when n is sufficiently large).In other words, when n is sufficiently large, we almost surely have∑C∈SinterAvg(H ′C) = O(|S|),453.2. Average Interference of Random Networksthus∑C∈S∑p∈PCinterH′C(p) = Λ(S) ·O(|S|), (3.7)where Λ(S) denotes the number of nodes in any cell C ∈ S (by definition,every cell in group S contains the same number of nodes). Since (3.7) holdsfor any group S ∈ P2, we almost surely have∑S∈P2∑C∈S∑p∈PCinterH′C(p) =∑S∈P2(Λ(S) ·O(|S|))= O(n),when n is sufficiently large, which completes the proof.The next lemma simply combines the results of Lemma 11 and 12.Lemma 13. We have∑S∈P1∪P2∑C∈S∑p∈PCinterH′C(p) = O(n),w.h.p.An interference at node p caused by node q can be represented bya (not necessarily unique) tuple (p, q, r) such that i) p = q = r, or ii){q, r} ∈ E (MST(P )) and dist(p, q) ≤ dist(q, r). Considering this represen-tation of interference, for a given node p ∈ PC , so far we have consideredonly interferences at p that can be represented by a tuple (p, q, r) such thatq, r ∈ PC . To count all the inferences at p at least once, we consider a set of16 different grids Q = {Gridηi′ η4 ,j′ η4|0 ≤ i′, j′ ≤ 3}. We show that, with highprobability, for every pair of points p and q such that q causes interference463.2. Average Interference of Random Networksat p, there exists an interference representation tuple (p, q, r), and a cell Cin at least one of the grids in Q that contains p, q, and r. Since the numberof grids is constant, by applying Lemma 13 on every grid, and using a unionbound, we get that the sum of all interferences is still O(n), w.h.p. Thisimplies that the average interference in the entire network is O(1), with highprobability.Lemma 14. Let p, q, r be three points in R2, and m = (px+qx+rx3 ,py+qy+ry3 )be their average.Then, dist(m, p) ≤ L, dist(m, q) ≤ L, and dist(m, r) ≤ L, whereL = max(dist(p, q), dist(p, r),dist(q, r)).Proof. The proof is straight forward. Let consider a triangle with verticesp, q, r. The average of vertices, m, always falls inside triangle. Let Selectone of the vertices, for instance p, then the distance between p and m canbe at most equal to the longest edge that is incident to p. Therefore, by theabove definition, we have dist(m, p) ≤ max{dist(p, r), dist(p, q)} ≤ L. Thesame result applies to q and r.We use the following lemma to show that if η is large enough, thenamong the cells in grids Gridηi′ η4 ,j′ η4, 0 ≤ i′, j′ ≤ 3, the one that has theclosest centre to the average of p, q, r, contains all the points p, q, r.Lemma 15. Let p, q, r be three points in R2, and L = max(dist(p, q), dist(p, r),dist(q, r)).Let d be a real number and Qd = {(id, jd)|i, j ∈ Z}. Then, there is a pointt ∈ Qd such that the square with side length of√2d + 2L centered at t473.2. Average Interference of Random Networkscontains all three points p, q, r.Proof. Let m = (px+qx+rx3 ,py+qy+ry3 ), s = ([mxd ]d, [myd ]d). We havedist(m, s) =√(mx − [mxd]d)2 + (my − [myd]d)2≤√(d2)2+(d2)2=√22d. (3.8)By triangle inequality, we have dist(s, p) ≤ dist(s,m)+dist(m, p). Therefore,by Lemma 14 and inequality (3.8), we get dist(s, p) ≤√22 d + L. Similarly,we can show that dist(s, q) ≤√22 d + L. Therefore, any square centered ats with side length of at least 2(√22 d+ L)contains all three points p, q,andr. Note that by the definition of Qd, s ∈ Qd.Theorem 8. Let P be a set of n random points selected independently anduniformly at random in the unit square [0, 1]2. Then the average interferenceof the communication graph MST (P )′ is O(1), with high probability.Proof. Let p and q be two distinct points in P such q causes interference atp. Let (p, q, r) be tuple representing this interference. Since (p, q, r) is aninterference representative tuple, and p and q are distinct, by definition, wehave {q, r} ∈ E(MST (P )) and dist(p, q) ≤ dist(q, r). Therefore, dist(q, r) ≤Lmax and dist(p, q) ≤ dist(q, r) ≤ Lmax.Let us set d = η4 , and L = Lmax in Lemma 15. By the assumption inSection 3.2, we have η ≥ 21−√24Lmax, thus η ≥√2η4 + 2Lmax. Therefore,by Lemma 15, there is a square S with side length η centred at a point483.2. Average Interference of Random Networkss = (iη4 , jη4 ) for some i, j ∈ Z, that contains all three points p, q, r. Let usdefineE(x) =η2 if x <η2x if η2 ≤ x ≤ 1−η21− η2 if x > 1−η2 .Since 1η is an integer, then for every integer i, E(iη4 ) = kη4 for some integerk, because 1− η2 = (4η −2)η4 . Let s′ = (E(sx), E(sy)) = (E(iη4 ), E(jη4 )), wheresx and sy denote the x-coordinate and y-coordinate of point s. Note thats′ = (k η4 , hη4 ) for some integers k and h. Also, sinceη2 ≤ E(x) ≤ 1 −η2 forevery x, the square S ′ with side length η centred at s′ falls entirely in [0, 1]2.Every point in S ∩ [0, 1]2 is also in S ′. Therefore, S ′ contains all three pointsp, q, r. The square S ′ is a cell in the grid Gridηk′ η4 ,h′ η4, where k′ = k mod 4and h′ = h mod 4. This implies that for every interference representativetuple (p, q, r), there is a cell in a grid from Q containing points p, q, r.We proved Lemma 13 when Gridηη2 ,η2∈ Q is used. However, the lemmaessentially holds for any grid in Q. Consequently,interAvg(MST ′(P ))≤∑Grd∈Q∑C∈Grd∑p∈PCinterH′C(p)n=O(n)n= O(1),with high probability.49Chapter 4Empirical Evaluations6We evaluated the performance of Algorithm LocalRadiusReduction inthree settings (simulated static wireless networks, simulated mobile wirelessnetworks, and real GPS track data) and compared it against four topol-ogy control algorithms: i) the cone-based local topology control (CBTC)algorithm [1], ii) the k-neighbour algorithm [28], iii) local computation ofthe intersection of the Gabriel graph and the unit disc graph (with unitradius rmax) [55], and iv) fixed-radius topologies (unit disk graphs of radiusrmax ∈ {100, 200, 300}). Performance was evaluated by comparing averagemaximum interference, expected average interference, average physical de-gree, and average energy cost (the sum of the squares of the transmissionradii [28]).6Part of this chapter will be published in A. Haghnegahdar, M. Khabbazian, AverageInterference in Wireless Ad Hoc Networks with Nodes in Random Position. To be sub-mitted to The International Symposium on DIStributed Computing (DISC), 2014., andM. Khabbazian, S. Durocher, A. Haghnegahdar, and F. Kuhn, Bounding interference inwireless ad hoc networks with nodes in random position. IEEE/ACM Transactions onNetworking, 2014.504.1. Topology Control Algorithms4.1 Topology Control Algorithms4.1.1 Cone Based Topology ControlThis algorithm is presented in [1]. Each node u tries to find at least oneneighbor in every cone of degree α centered at u. In our Simulations, weset α = 2pi3 to ensure a connected resulting network [1]. Node u graduallyincreases it’s transmission power starting from 0 to discover more neighbors.It checks whether each cone of degree α contains a node marked as neighbor.This process is as follows:1. The nodes labeled as neighbor of node u are sorted according to theirangles relative to the closest neighbor of u.2. If there is a gap of more than α between the angles of two consecutivesorted nodes then u increases the transmission power to reach the nextnode surrounding it and considers that as a neighbor node.3. This continues until no-gap larger than α is found or u broadcasts withit’s maximum power which is 300 here.Finally as described in [1], we optimized the CBTC algorithm by con-sidering the following optimization procedure : If there is an edge form u tov and from u to w such that d(v, w) < max(d(u, v), d(u,w)), then removethe longer edge. Then update the transmission range again based on a newneighbor’s list.514.1. Topology Control Algorithms4.1.2 Gabriel Topology ControlFormally, Gabriel graph is a graph with vertex of point set P in which anypoints p and q in P are adjacent if a disc of which line pq is a diametercontains no other elements of P . For each node u, algorithm finds all thepossible neighbors of u that fall on the disc with diameter equal to thedistance of neighbor node and u and contains no other nodes. Algorithmfor each node will stop the search after it checks all the possible neighborsor reaches the maximum possible transmission range of current node.4.1.3 k-neighbour AlgorithmThis algorithm is based on the research conducted in [28]. In this paper au-thors study the topology control problem with the goal of limiting interfer-ence as much as possible, while keeping the communication graph connectedwith high probability. Their method maintains the the number of physicalneighbors of every node equal to or slightly below a specific value k.The paper has two sections. First, they estimated the value of k thatguarantees connectivity of communication graph with high probability. Inthe other section, they proposed k-neighbour protocol that “guarantees log-arithmically bounded physical degree at every node”.In our simulations, for each node number, the value of k is selected from[28] such that guarantees the connectivity with probability greater than 0.95.The k-neighbour Algorithm is :1. Node u finds it’s neighbors based on it’s maximum transmission rangeand then sort them based on their distance.524.1. Topology Control Algorithms2. u keeps the list of k nearest neighbors, Lu (if it has less than k neighborLu is the list of all neighbors of u.3. Then nodes calculate the set of symmetric neighbors (Two nodes i ,jare symmetric iff i ∈ Lj and j ∈ Li) and store them in Lsu. Afterthis step we have a undirected graph and for any (i, j) ∈ E let P (i, j)denote the transmission power that i needs to reach j,P (i, j) = d(i, j)α=2.4. Node u sorts the list Lsu according to increasing value of P (u, j). Letj1, ..., jk be the sorted list.5. For l = 2, ..., k do the following :(a) Check if jl can be reached using a transmission range lower thanP (u, jl) by routing through some jq, q < l.(b) If P (i, jq) + P (jq, jl) ≤ P (i, jl) delete the link P (i, jl).6. Set the transmission range equal to the power needed to reach thefarthest immediate neighbor node in Lsu.4.1.4 Local Radius Reduction AlgorithmAll the nodes start with the same maximum transmission range.1. Each node u finds its one-hop neighbors ( symmetric links ) (the onecan be reached by the max transmission range of node u) and sortthem based on their distance534.2. Simulation Parameters2. Node u picks it’s furthest neighbor f and check the following steps(a) For all the other neighbor nodes v ∈ Adj(u), if there exists v suchthat max{d(u, v), d(v, f)} < d(u, f) and v ∈ Adj(f) then node uremoves the f from it’s neighbors and reduces the transmissionrange to it’s new furthest neighbor. It then jumps to step 2. (skip(b , c) ) if not check step (b) with the selected v.(b) For w ∈ Adj(v) if max{d(u, v), d(v, w), d(w, f)} < d(u, f) andw ∈ Adj(f) then u removes f from its neighbor list, reduces thetransmission range and jumps to step 2.(c) If no w and v found terminate the algorithm for the current nodeu and set the maximum transmission range equal to the distanceto it’s furthest neighbor in the updated list of neighbors.4.1.5 Fixed Range AlgorithmThis algorithm assumes a fixed transmission range for all the nodes in thenetwork. Using this basic algorithm, we assigned fixed transmission rangeof 100 m, 200 m, and 300 m to nodes and evaluated it’s performance.4.2 Simulation ParametersWe set the simulation region’s dimensions to 1000 metres × 1000 metres.For both static and dynamic networks, we varied the number of nodes nfrom 50 to 1000 in increments of 50. We fixed the maximum transmissionradius rmax for each network to 100, 200, or 300 metres. To compute the av-erage maximum interference and the expected average interference for static544.3. Maximum Interference Resultsnetworks, for each n and rmax we generated 100,000 static networks, eachwith n nodes and maximum transmission radius rmax, distributed uniformlyat random in the simulation region. In the RWP model, for each n and rmax,we randomly generated 100,000 independent networks using the followingapproximation for nodes’ spatial distribution [56]:f(x, y) ≈916x3my3m(x2 − x2m)(y2 − y2m),where xm = 500, ym = 500, x ∈ [−xm, xm], and y ∈ [−ym, ym] . For a betterapproximation, we refer readers to [4]. To use the real mobility trace dataof Piorkowski et al. [57], which includes GPS coordinates for trajectories of537 taxi vehicles, we selected 500 vehicles with the largest trace samples,each has over 8000 sample points. We varied the number of nodes from 50to 500 in increments of 50.4.3 Maximum Interference ResultsWhen simulating Algorithm LocalRadiusReduction, in both the staticand mobile settings, each node collects the list of nodes in its 2-hop neigh-bourhood in two rounds, applies the algorithm to reduce its transmission ra-dius and then broadcasts its computed transmission radius, allowing neigh-bouring nodes a final opportunity to eliminate asymmetric edges and fur-ther reduce their transmission radii while maintaining connectivity in thenetwork.We used the random waypoint model (RWP) [58] and real mobility trace554.3. Maximum Interference Resultsdata to simulate mobile networks. For the RWP model we applied theapproximated probability distribution described by Bettstetter and Wag-ner [56] to position nodes independently at random across the network andgenerate independent snapshots in each simulation iteration. Using the mo-bility trace data, we estimated a probability density distribution which wasused to generate independent snapshots.Comparing the LocalRadiusReduction algorithm against other localtopology control algorithms on a simulated static wireless network. Plotsfor the fixed-radius algorithm are omitted from Figures 4.2–4.13 to allowthe remaining plots to be more easily differentiated.0 200 400 600 800 1000050100150200250300350Average Max InterferenceNumber of Nodes UDG 100UDG 200UDG 300GabrielCBTCK−NeighLocalRadiusRedFigure 4.1: Maximum Interference in Static Networks564.3. Maximum Interference Results0 200 400 600 800 10005101520253035Average Max InterferenceNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.2: Maximum Interference in Static Networks0 200 400 600 800 10003.544.555.566.577.588.5Expected Average InterferenceNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.3: Expected Average Interference in Static Networks574.3. Maximum Interference Results0 200 400 600 800 100022.533.544.555.566.57Average Physical DegreeNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.4: Average Physical Degree in Static Networks0 200 400 600 800 100011.21.41.61.822.22.4 x 106Average Energy CostNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.5: Average Energy Cost in Static Networks584.3. Maximum Interference ResultsAs shown, the average maximum interference of unit disc graph topolo-gies increases linearly with n (see Figure 4.1). Since these plots are signif-icantly larger (i.e., they correspond to worse performance) than the otherplots in all four evaluation criteria, unit disc graph plots are excluded fromsubsequent figures to permit more detailed comparison.Although both the local Gabriel and CBTC algorithms performed sig-nificantly better than the unit disc graphs, the lowest average maximum in-terference was achieved by the LocalRadiusReduction and k-neighbouralgorithms, for which the corresponding plots grow logarithmically with n, asseen in Figures 4.2, 4.3, and 4.10. Note that the LocalRadiusReductionalgorithm reduces the maximum interference to O(log n) with high proba-bility, irrespective of the initial maximum transmission radius rmax. Local-RadiusReduction has average maximum interference slightly greater thank-neighbour (Figures 4.2, 4.3, and 4.10), but lower expected average inter-ference, average physical degree, and average energy cost (Figures 4.3–4.5,4.7–4.9, and 4.11–4.13).Simulation results obtained using a RW model closely match those ob-tained on a static network because the distribution of nodes at any timeduring a random walk is nearly uniform [59]. The spatial distribution ofnodes moving according to a RWP model is not uniform, and is maximizedat the centre of the simulation region [4]. Consequently, the density of nodesis high near the centre, resulting in greater interference at these nodes. Fig-ures 4.3–4.9 are comparing the LocalRadiusReduction algorithm againstother local topology control algorithms on a simulated mobile network.594.3. Maximum Interference Results0 200 400 600 800 100010152025303540455055Average Max InterferenceNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.6: Average Maximum Interference in Mobile Networks0 200 400 600 800 100045678910Expected Average InterferenceNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.7: Expected Average Interference in Mobile Networks604.3. Maximum Interference Results0 200 400 600 800 100023456789Average Physical DegreeNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.8: Average Physical Degree in Mobile Networks0 200 400 600 800 10000.511.522.53 x 106Average Energy CostNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.9: Average Energy Cost in Mobile Networks614.3. Maximum Interference ResultsFinally, we evaluated the algorithm LocalRadiusReduction usingreal mobility trace data of Piorkowski et al. [57], consisting of GPS co-ordinates for trajectories of 537 taxi vehicles recorded over one month in2008, driving throughout the San Fransisco Bay area. We selected the 500largest traces, each of which has over 8000 sample points. To implement ouralgorithm, we selected n taxis among the 500 uniformly at random, rangingfrom n = 50 to n = 500 in increments of 50. As seen in Figure 4.10, theresults are similar to those measured in our simulation. The k-neighboursalgorithm produced disconnected communication graphs (containing mul-tiple connected components) in 2.5% of instances, even when the value ofk was increased significantly (e.g., up to k = 30). This is likely explainedby the highly non-uniform distribution of nodes in the track data. Thisdifference is significant, however, because the k-neighbours algorithm doesnot guarantee that the returned topology is connected, failing to satisfy theprimary objective of the interference minimization problem for some inputinstances.Figures 4.10–4.13 are comparing the LocalRadiusReduction algo-rithm against other local topology control algorithms on recorded mobilevehicular GPS tracks.624.3. Maximum Interference Results0 100 200 300 400 500020406080100120140160180Average Max InterferenceNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.10: Average Maximum Interference in Real-world Networks0 100 200 300 400 50046810121416Expected Average InterferenceNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.11: Expected Average Interference in Real-world Networks634.3. Maximum Interference Results0 100 200 300 400 5002468101214Average Physical DegreeNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.12: Average Physical Degree in Real-world Networks0 100 200 300 400 50000.050.10.150.20.250.30.35Average Energy CostNumber of Nodes GabrielCBTCK−NeighLocalRadiusRedFigure 4.13: Average Energy Cost in Real-world Networks644.4. Average Interference Results4.4 Average Interference ResultsIn this section, we present the result of a simulation study carried out to ver-ify our theoretical results over a network with nodes randomly distributed,and one with a real world node placement. For the first case, the simula-tion region is considered to be a square with the edge size of 1000 meters.The number of nodes, n, deployed randomly inside region varies from 100to 1000 in increments of size 100. As the starting step, we construct a MSTgraph, and determine the transmission range of every node deployed insidethe network plane. Then, we measure the corresponding interference at eachnode, and by that we compute the average interference of the entire networkas defined earlier.To have a better average case analysis, for each n, we generated onemillion networks, each with n nodes distributed uniformly at random inthe region. For each generated network, we store the average interference.Figure 4.14 shows the mean, the maximum, and the minimum of theseaverage interferences for each n.As shown in figure 4.14, the average interference is bounded by a constantvalue as predicted by the theoretical analysis. To have a better insight aboutthe distribution of the average interference, we plot its histogram for thecase where n = 500 in Figure 4.15. This figure also suggests that, with highprobability, the average interference is bounded by a constant value (e.g.,here it is equal to 4).We also evaluated the average interference using actual mobility tracedata provided by Piorkowski et al. [60]. This data set consists of GPS654.4. Average Interference Results100 200 300 400 500 600 700 800 900 10002.533.544.5Number of NodesAverage Interference MeanMaxMinFigure 4.14: Average Interference3.3 3.4 3.5 3.6 3.7 3.800.511.52x 104Figure 4.15: Average interference histogram for a network with 500 nodes664.4. Average Interference Results50 100 150 200 250 300 350 400 450 500024681012Number of VehiclesAverage Interference MeanMaxMinFigure 4.16: Average Interferencecoordinates for 537 taxi vehicles recorded over one month in 2008, drivingthroughout the San Fransisco Bay area. We first select 500 vehicles with thelargest trace samples, each of which has over 8000 sample points. To measurethe average interference, we selected n taxis among the 500 uniformly atrandom, ranging from n = 50 to n = 500 in increments of 50. We consideredeach snapshot of vehicles placement (totally 8000 snapshots) and assigneda transmission range to each node using MST algorithm.Next, we calculated the average interference for the nodes in each snap-shot. Figure 4.16 shows the mean, the maximum and the minimum of theaverage interference over all snapshots for every given n. Note that the av-erage interference is slightly higher when our real world placement is usedinstead of a uniform distribution.Similar to Figure 4.15, we show the histogram of the average interferencefor n = 50 when real world data traces are used. This is an indication that,674.4. Average Interference Results2 3 4 5 6 7 8 90100200300400500Figure 4.17: Average Interference histogram for 8000 snapshots and 50 Ve-hiclesin real world scenarios, the average interference can be very small.68Chapter 5Conclusions and FutureWorkWe first studied the maximum interference problem in wireless ad hoc net-works. Considering a broad set of probability distributions (called classT (P )), we derived a bound for the maximum interference of resulting com-munication graphs. we also showed that, irrespective of the network size,the average interference in the communication graph corresponding to theminimum spanning tree of the nodes is smaller than a constant, with highprobability. This is in contrast to the existing worst case analysis resultsin which the average interference can be arbitrarily large when nodes areartificially placed in the network.Using Algorithm LocalRadiusReduction, each node determines itstransmission radius as a function of its 2-hop neighbourhood. Alternatively,suppose each node could select its transmission radius at random using asuitable distribution over [dmin(G), dmax(G)]. Can such a strategy for assign-ing transmission radii ensure connectivity and low maximum interferencewith high probability? Similarly, additional topologies and local algorithmsfor constructing them might achieve O(log n) expected maximum interfer-69Chapter 5. Conclusions and Future Workence. For example, our experimental results suggest that both the Gabrielgraph and CBTC local topology control algorithms may provide O(log n)expected maximum interference. Since neither the Gabriel graph nor theCBTC topology of a set of points P is in T (P ) in general, whether thesebounds hold remains to be proved.Several questions remain open related to the algorithmic problem offinding an optimal solution (one whose maximum interference is exactlyOPT(P )) when node positions may be selected adversarially. The com-plexity of the interference minimization problem in one dimension remainsopen; at present, it is unknown whether the problem is polynomial-timesolvable or NP-hard [19]. While the problem is known to be NP-complete intwo dimensions [17], no polynomial-time approximation algorithm nor anyinapproximability hardness results are known. Another interesting futurework is to analytically prove this using the existing distributions suggestedfor dynamic mobile networks. Extending the result of this work to three-dimensional networks, and finding an algorithm that can locally constructa communication graph with small expected average interference are otherfuture work that we intend to study.70Bibliography[1] L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer, “Acone-based distributed topology-control algorithm for wireless multi-hop networks,” IEEE/ACM Transactions on Networking, vol. 13, no. 1,pp. 147–159, 2005.[2] P. Santi, “Topology control in wireless ad hoc and sensor networks,”ACM Computing Surveys, vol. 37, no. 2, pp. 164–194, 2005.[3] S. Durocher, E. Kranakis, D. Krizanc, and L. Narayanan, “Balancingtraffic load using one-turn rectilinear routing,” Journal of Interconnec-tion Networks, vol. 10, no. 1–2, pp. 93–120, 2009.[4] E. Hyytia¨, P. Lassila, and J. Virtamo, “Spatial node distribution of therandom waypoint mobility model with applications,” IEEE Transac-tions on Mobile Computing, vol. 6, no. 5, pp. 680–694, 2006.[5] M. Benkert, J. Gudmundsson, H. Haverkort, and A. Wolff, “Construct-ing minimum-interference networks,” Computational Geometry: The-ory and Applications, vol. 40, no. 3, pp. 179–194, 2008.[6] G. Narasimhan and M. Smid, Geometric Spanner Networks. Cam-bridge University Press, 2007.71Bibliography[7] M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger,“Does topology control reduce interference?” in Proceedings of theACM International Symposium on Mobile Ad Hoc Networking andComputing (MobiHoc), 2004, pp. 9–19.[8] X.-Y. Li, G. Calinescu, and P.-J. Wan, “Distributed construction ofa planar spanner and routing for ad hoc wireless networks,” in Pro-ceedings of the Annual Joint Conference of the IEEE Computer andCommunications Societies, 2002, pp. 1268–1277.[9] I. Kanj, L. Perkovic´, and G. Xia, “Computing lightweight spannerslocally,” in Proceedings of the Symposium on Distributed Computing(DISC), ser. Lecture Notes in Computer Science, vol. 5218. Springer,2008, pp. 365–378.[10] P. Bose, J. Gudmundsson, and M. Smid, “Constructing plane spannersof bounded degree and low weight,” Algorithmica, vol. 42, no. 3–4, pp.249–264, 2005.[11] M. Damian, S. Pandit, and S. V. Pemmaraju, “Local approximationschemes for topology control,” in Proceedings of the ACM Symposiumon Principles of Distributed Computing (PODC), 2006, pp. 208–218.[12] P. von Rickenbach, S. Schmid, R. Wattenhofer, and A. Zollinger, “Arobust interference model for wireless ad hoc networks,” in Proceedingsof the IEEE Parallel and Distributed Processing Symposium (IPDPS),2005, pp. 1–8.72Bibliography[13] P. von Rickenbach, R. Wattenhofer, and A. Zollinger, “Algorith-mic models of interference in wireless ad hoc and sensor networks,”IEEE/ACM Transactions on Networking, vol. 17, no. 1, pp. 172–185,2009.[14] T. Locher, P. von Rickenbach, and R. Wattenhofer, “Sensor networkscontinue to puzzle: Selected open problems,” in Proceedings of theInternational Conference on Distributed Computing and Networking(ICDCN), ser. Lecture Notes in Computer Science, vol. 4904. Springer,2008, pp. 25–38.[15] T. Moscibroda and R. Wattenhofer, “Minimizing interference in ad hocand sensor networks,” in Proceedings of the ACM Joint Workshop onFoundations of Mobile Computing (DIALM-POMC), 2005, pp. 24–33.[16] M. M. Halldo´rsson and T. Tokuyama, “Minimizing interference of awireless ad-hoc network in a plane,” Theoretical Computer Science, vol.402, no. 1, pp. 29–42, 2008.[17] K. Buchin, “Minimizing the maximum interference is hard,” CoRR, vol.abs/0802.2134, 2008.[18] T. Lou, H. Tan, Y. Wang, and F. Lau, “Minimizing average interferencethrough topology control,” in Proceedings of the International Sympo-sium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks andAutonomous Mobile Entities (ALGOSENSORS), ser. Lecture Notes inComputer Science. Springer, 2012, vol. 7111, pp. 115–129.73Bibliography[19] H. Tan, T. Lou, F. Lau, Y. Wang, and S. Chen, “Minimizing interfer-ence for the highway model in wireless ad-hoc and sensor networks,” inProceedings of the Conference on Current Trends in Theory and Prac-tice of Computer Science (SOFSEM), ser. Lecture Notes in ComputerScience. Springer, 2011, vol. 6543, pp. 520–532.[20] M. Khabbazian, S. Durocher, and A. Haghnegahdar, “Bounding inter-ference in wireless ad hoc networks with nodes in random position,”in Proceedings of the International Colloquium on Structural Informa-tion and Communication Complexity (SIROCCO), ser. Lecture Notesin Computer Science, vol. 7355. Springer, 2012, pp. 85–98.[21] E. Kranakis, D. Krizanc, P. Morin, L. Narayanan, and L. Stacho, “Atight bound on the maximum interference of random sensors in thehighway model,” CoRR, vol. abs/1007.2120, 2010.[22] M. Korman, “Minimizing interference in ad hoc networks with boundedcommunication radius,” Information Processing Letters, vol. 112,no. 19, pp. 748–752, 2012.[23] D. Kowalski and M. Rokicki, “Connectivity problem in wireless net-works,” in Proceedings of the International Symposium on DistributedComputing (DISC), ser. Lecture Notes in Computer Science. Springer,2010, vol. 6343, pp. 344–358.[24] D. Bilo` and G. Proietti, “On the complexity of minimizing interferencein ad-hoc and sensor networks,” Theoretical Computer Science, vol. 402,no. 1, pp. 42–55, 2008.74Bibliography[25] A. Sharma, N. Thakral, S. Udgata, and A. Pujari, “Heuristics for min-imizing interference in sensor networks,” in Proceedings of the Interna-tional Conference on Distributed Computing and Networking (ICDCN),ser. Lecture Notes in Computer Science. Springer, 2009, vol. 5408, pp.49–54.[26] L. Devroye and P. Morin, “A note on interference in random point sets,”in Proceedings of the Canadian Conference on Computational Geometry(CCCG), vol. 24, 2012, pp. 201–206.[27] A. Maheshwari, M. Smid, and N. Zeh, “Low-interference networks inmetric spaces with bounded doubling dimension,” Information Process-ing Letters, vol. 111, no. 23–24, pp. 1120–1123, 2011.[28] D. Blough, M. Leoncini, G. Resta, and P. Santi, “The k-neighborsapproach to interference bounded and symmetric topology control inad hoc networks,” IEEE Trans. Mob. Comp., vol. 5, no. 9, pp. 1267–1282, 2006.[29] A. Dessmark and A. Pelc, “Tradeoffs between knowledge and time ofcommunication in geometric radio networks,” in Proc. SPAA, 2001, pp.59–66.[30] E. Gilbert, “Random plane networks,” J. SIAM, vol. 9, no. 4, pp. 533–543, 1961.[31] W. K. Hale, “Frequency assignment: Theory and applications,” Proc.IEEE, vol. 68, no. 12, pp. 1497–1514, 1980.75Bibliography[32] D. Kotz, C. Newport, R. S. Gray, J. Liu, Y. Yuan, and C. Elliott,“Experimental evaluation of wireless simulation assumptions,” in Pro-ceedings of the 7th ACM International Symposium on Modeling, Anal-ysis and Simulation of Wireless and Mobile Systems, ser. MSWiM ’04.ACM, 2004, pp. 78–82.[33] D. Kotz, C. Newport, and C. Elliott, “The mistaken axioms of wireless-network research,” 2003.[34] C. Avin, Y. Emek, E. Kantor, Z. Lotker, D. Peleg, and L. Roditty,“SINR diagrams: Convexity and its applications in wireless networks,”J. ACM, vol. 59, no. 4, p. 18, 2012.[35] O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer, “Complexity ingeometric SINR,” in Proc. MOBIHOC, 2007, pp. 100–109.[36] Z. Lotker and D. Peleg, “Structure and algorithms in the SINR wirelessmodel,” SIGACT News, vol. 41, no. 2, pp. 74–84, 2010.[37] T. Moscibroda, R. Wattenhofer, and A. Zollinger, “Topology controlmeets SINR: the scheduling complexity of arbitrary topologies,” inProc. MOBIHOC, 2006, pp. 310–321.[38] T. N. Nguyen, M. K. An, N. X. Lam, and D. T. Huynh, “The complex-ity of minimizing receiver-based and SINR edge interference,” in Proc.ICCCN, 2011, pp. 1–7.[39] M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger,“Does topology control reduce interference?” in Proceedings of the 5th76BibliographyACM international symposium on Mobile ad hoc networking and com-puting, ser. MobiHoc ’04, 2004, pp. 9–19.[40] P. V. Rickenbach, S. Schmid, R. Wattenhofer, and A. Zollinger, “Arobust interference model for wireless ad-hoc networks,” in In Proc. 5th IEEE International Workshop on Algorithms for Wireless, Mobile,Ad-Hoc and Sensor Networks (WMAN, 2005.[41] M. Fussen, R. Wattenhofer, and A. Zollinger, “Interference arises at thereceiver,” in Wireless Networks, Communications and Mobile Comput-ing, 2005 International Conference on, vol. 1, 2005, pp. 427–432 vol.1.[42] M. Li, K. Moaveni-Nejad, W.-Z. Song, and W.-Z. Wang, “Interference-aware topology control for wireless sensor networks,” in Sensor and AdHoc Communications and Networks, 2005. IEEE SECON 2005. 2005Second Annual IEEE Communications Society Conference on, 2005,pp. 263–274.[43] M. Khabbazian, S. Durocher, A. Haghnegahdar, and F. Kuhn, “Bound-ing interference in wireless ad hoc networks with nodes in random po-sition,” submitted to Networking, IEEE/ACM Transactions on.[44] K. Buchin, “Minimizing the Maximum Interference is Hard,” ArXive-prints, Feb. 2008.[45] M. M. Halldo´rsson and T. Tokuyama, “Minimizing interference of awireless ad-hoc network in a plane,” Theor. Comput. Sci., vol. 402,no. 1, pp. 29–42, Jul. 2008.77Bibliography[46] E. Kranakis, D. Krizanc, P. Morin, L. Narayanan, and L. Stacho, “ATight Bound on the Maximum Interference of Random Sensors in theHighway Model,” ArXiv e-prints, Jul. 2010.[47] M. Khabbazian, S. Durocher, and A. Haghnegahdar, “Bounding inter-ference in wireless ad hoc networks with nodes in random position,” inSIROCCO’12, 2012, pp. 85–98.[48] T. Moscibroda and R. Wattenhofer, “Minimizing interference in ad hocand sensor networks,” in Proceedings of the ACM Joint Workshop onFoundations of Mobile Computing (DIALM-POMC), 2005, pp. 24–33.[49] H. Tan, T. Lou, F. C. M. Lau, Y. Wang, and S. Chen, “Minimizinginterference for the highway model in wireless ad-hoc and sensor net-works,” in Proceedings of the 37th international conference on Currenttrends in theory and practice of computer science, ser. SOFSEM’11.Springer-Verlag, 2011, pp. 520–532.[50] J. Heinonen, Lectures on analysis on metric spaces. New York:Springer-Verlag, 2001.[51] A. Gupta, R. Krauthgamer, and J. Lee, “Bounded geometries, fractals,and low-distortion embeddings,” in Proceedings of the IEEE Symposiumon Foundations of Computer Science (FOCS), 2003, pp. 534–543.[52] P. Fraigniaud, E. Lebhar, and Z. Lotker, “A doubling dimension thresh-old θ(log log n) for augmented graph navigability,” in Proceedings of theEuropean Symposium on Algorithms (ESA), ser. Lecture Notes in Com-puter Science, vol. 4168. Springer, 2006, pp. 376–386.78Bibliography[53] M. Khan, G. Pandurangan, and V. S. A. Kumar, “Distributed algo-rithms for constructing approximate minimum spanning trees in wire-less sensor networks,” IEEE Transactions on Parallel and DistributedSystems, vol. 20, no. 1, pp. 124–139, 2009.[54] P. Wan, G. Ca˘linescu, X. Li, and O. Frieder, “Minimum-energy broad-casting in static ad hoc wireless networks,” Wireless Networks, vol. 8,no. 6, pp. 607–617, 2002.[55] P. Bose, P. Morin, I. Stojmenovic´, and J. Urrutia, “Routing with guar-anteed delivery in ad hoc wireless networks,” Wireless Networks, vol. 7,no. 6, pp. 609–616, 2001.[56] C. Bettstetter and C. Wagner, “The node distribution of the randomwaypoint mobility model for wireless ad hoc networks,” IEEE Trans.Mob. Comp., vol. 2, pp. 257–269, 2003.[57] M. Piorkowski, N. Sarafijanovic-Djukic, and M. Gross-glauser, “CRAWDAD data set epfl/mobility (v. 2009-02-24),”http://crawdad.cs.dartmouth.edu/epfl/mobility, 2009.[58] D. B. Johnson and D. A. Maltz, “Dynamic source routing in ad hocwireless networks,” in Mobile Computing, T. Imielinski and H. Korth,Eds. Kluwer Academic Publishers, 1996, vol. 353.[59] A. Das Sarma, D. Nanongkai, and G. Pandurangan, “Fast distributedrandom walks,” in Proceedings of the ACM Symposium on Principlesof Distributed Computing (PODC), 2009, pp. 161–170.79Bibliography[60] M. Piorkowski, N. Sarafijanovic-Djukic, and M. Gross-glauser, “CRAWDAD data set epfl/mobility (v. 2009-02-24),”http://crawdad.cs.dartmouth.edu/epfl/mobility, 2009.80
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Interference in wireless mobile networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Interference in wireless mobile networks Haghnegahdar, Alireza 2014
pdf
Page Metadata
Item Metadata
Title | Interference in wireless mobile networks |
Creator |
Haghnegahdar, Alireza |
Publisher | University of British Columbia |
Date Issued | 2014 |
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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-05-09 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
IsShownAt | 10.14288/1.0167450 |
URI | http://hdl.handle.net/2429/46713 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2014-09 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2014_september_haghnegahdar_alireza.pdf [ 664.74kB ]
- Metadata
- JSON: 24-1.0167450.json
- JSON-LD: 24-1.0167450-ld.json
- RDF/XML (Pretty): 24-1.0167450-rdf.xml
- RDF/JSON: 24-1.0167450-rdf.json
- Turtle: 24-1.0167450-turtle.txt
- N-Triples: 24-1.0167450-rdf-ntriples.txt
- Original Record: 24-1.0167450-source.json
- Full Text
- 24-1.0167450-fulltext.txt
- Citation
- 24-1.0167450.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0167450/manifest