We study the minimum radius required for connectivity (CTR Critical Transmission Range) within homogeneous stationary Wireless Sensor Networks (WSN) topology control, considering different levels of attractivity within the sensors. Due to the complexity of dealing with this problem from a theoretical viewpoint, a Monte Carlo experience is devised for estimating the CTR distribution. With this information, we propose optimization procedures that, using as additional input a few known parameters (overall available budget, sensor cost, maximum available transmission radius, minimum probability of connectivity, environmental path loss and deployment cost) leads to the decision of the number and type of sensors to be acquired, their optimal communication radius and the ideal deployment strategy that maximize the WSN lifetime. As a previous result, the accuracy of several computational platforms for statistical computing was assessed, being the main conclusion that R (http://www.r-project.org) is the best choice / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Apresentamos a caracterização do raio de transmissão mínimo necessário para garantir conectividade, CTR (Critical Transmission Range), num cenário de controle de topologia em RSSF homogêneas e estacionárias. Dada a complexidade de se trabalhar com modelos analíticos, por meio de experiências Monte Carlo obtemos um estimador da distribuição do CTR sobre processos pontuais espaciais que descrevem o posicionamento dos nós sensores no ambiente para diferentes níveis de atratividade. Propomos modelos de otimização práticos que consideram diversos fatores conhecidos a priori pelo projetista como, por exemplo, os preços de diversos sensores, o raio de transmissão máximo disponível pelo sensor, os custos de posicionamento no ambiente (função da atratividade), o orçamento total do projeto, a probabilidade de conectividade mínima admissível e o exponente de path loss do ambiente. O modelo determina quais e quantos sensores devem ser comprados, com que raio de transmissão devem ser configurados e qual o preço conveniente a pagar pelo posicionamento (função da atratividade), para maximizar o tempo de vida de uma RSSF. Para guiar a escolha da plataforma de simulação e análise de dados, vários resultados a respeito de precisão numérica são apresentados, obtidos aplicando protocolos de avaliação já consolidados. Desta análise, determinamos que R (http://www.r-project.org) é a melhor escolha

Un réseau mobile ad hoc (Mobile Ad hoc Network, MANET) est un réseau sans fil, formé dynamiquement par un ensemble d'utilisateurs équipés de terminaux mobiles, sans l'utilisation d'une infrastructure préexistante, ou d'une administration centralisée. Les équipements utilisés dans les MANETs sont limités par la capacité de la batterie, la puissance de calcul et la bande passante. Les utilisateurs des MANETs sont libres de se déplacer, ce qui induit à des topologies dynamiques dans le temps. Toutes ces contraintes ajoutent plus de challenges aux protocoles et services de communications afin de fonctionner dans les MANETs. L'évolution des réseaux de 4ème génération (4G) est appelée à intégrer les MANETs avec les autres types de réseaux afin d'étendre leurs portées. Nous nous sommes intéressés dans la première partie de cette thèse à quelques challenges connus dans les MANETs en proposant des solutions novatrices utilisant des propriétés intéressantes des topologies de graphes. Dans un premier temps, nous avons effectué une étude sur la prédiction de la mobilité afin de maintenir une topologie d'ensemble dominant connecté dans les MANETs. Nous avons proposé dans un autre travail comment construire des topologies de graphes ayant des propriétés globales en se basant seulement sur des informations locales des nœuds mobiles. Ces topologies servent comme overlay aux MANETs. Nous avons proposé des algorithmes distribués pour construire des alliances offensives et défensives globales minimales. Nous avons aussi défini des heuristiques pour ces algorithmes afin de réduire les tailles des alliances obtenues. La première partie de cette thèse est achevée par la proposition d'un framework pour la conception et l'analyse des protocoles de contrôle de topologie dans les MANETs. Nous avons identifié les points communs des algorithmes de contrôle de topologie conçus pour les réseaux mobiles ad hoc et nous avons enrichi le simulateur NS-2 avec un ensemble d'extensions pour supporter le contrôle de topologie / We are interested in this thesis to graph-based approaches to deal with some challenges in networking, namely, graph topologies of mobile ad hoc networks (MANETs) and process model matchmaking in large scale web service. We propose in the first part: (1) a generic mechanism using mobility information of nodes to maintain a graph topology of the network. We show particularly, how to use the prediction of future emplacements of nodes to maintain a connected dominating set of a given MANET. (2) distributed algorithms to construct minimal global offensive alliance and global defensive alliance sets in MANETs. We also introduce several heuristics to get a better approximation of the cardinality of the alliance sets which is a desirable property for practical considerations. (3) a framework to facilitate the design and evaluation of topology control protocols in MANETs. We propose in the framework, a common schema for topology control based on NS-2 simulator and inspired from the commonalities between the components of the topology control algorithms in MANETs. In the second part, we focus on process model matchmaking. We propose two graph-based solutions for process model inexact matching to deal with high computational time of existing work in the literature. In the first solution, we decompose the process models into their possible execution sequences. After, we propose generic graph techniques using string comparator metrics for process model matchmaking based on this decomposition. In order to get better optimization of the execution time and to deal with process model matching in large scale web services, the second solution combines a spectral graph matching with structural and semantic proposed approaches. This solution uses an eigen-decomposition projection technique that makes the runtime faster

In this dissertation, we introduce and study robust optimization models and decomposition algorithms in order to deal with the uncertainties such as terrorist attacks, natural disasters, and uncertain demand that are becoming more and more signicant in power systems operation and planning. An optimal power grid hardening problem is presented as a defender-attacker-defender (DAD) sequential game and solved by an exact decomposition algorithm. Network topology control, which is an eective corrective measure in power systems, is then incorporated into the defender-attacker-defender model as a recourse operation for the power system operator after a terrorist attack. Computational results validate the cost-eectiveness of the novel model. In addition, a resilient distribution network planning problem (RDNP) is proposed in order to coordinate the hardening and distributed generation resource placement with the objective of minimizing the distribution system damage under uncertain natural disaster events. A multi-stage and multi-zone based uncertainty set is designed to capture the spatial and temporal dynamics of a natural disaster as an extension to the N-K worst-case network interdiction approach. Finally, a power market day-ahead generation scheduling problem, i.e., robust unit commitment (RUC) problem, that takes account of uncertain demand is analyzed. Improvements have been made in achieving a fast

Wireless sensor networks are used in several multi-disciplinary areas covering a wide variety of applications. They provide distributed computing, sensing and communication in a powerful integration of capabilities. They have great long-term economic potential and have the ability to transform our lives. At the same time however, they pose several challenges – mostly as a result of their random deployment and non-renewable energy sources.Among the most important issues in wireless sensor networks are energy efficiency and radio interference. Topology control plays an important role in the design of wireless ad hoc and sensor networks; it is capable of constructing networks that have desirable characteristics such as sparser connectivity, lower transmission power and a smaller node degree.In this research a distributed topology control technique is presented that enhances energy efficiency and reduces radio interference in wireless sensor networks. Each node in the network makes local decisions about its transmission power and the culmination of these local decisions produces a network topology that preserves global connectivity. The topology that is produced consists of a planar graph that is a power spanner, it has lower node degrees and can be constructed using local information. The network lifetime is increased by reducing transmission power and the use of low node degrees reduces traffic interference. The approach to topology control that is presented in this document has an advantage over previously developed approaches in that it focuses not only on reducing either energy consumption or radio interference, but on reducing both of these obstacles. Results are presented of simulations that demonstrate improvements in performance. AFRIKAANS : Draadlose sensor netwerke word gebruik in verskeie multi-dissiplinêre areas wat 'n wye verskeidenheid toepassings dek. Hulle voorsien verspreide berekening, bespeuring en kommunikasie in 'n kragtige integrate van vermoëns. Hulle het goeie langtermyn ekonomiese potentiaal en die vermoë om ons lewens te herskep. Terselfdertyd lewer dit egter verskeie uitdagings op as gevolg van hul lukrake ontplooiing en nie-hernubare energie bronne. Van die belangrikste kwessies in draadlose sensor netwerke is energie-doeltreffendheid en radiosteuring. Topologie-beheer speel 'n belangrike rol in die ontwerp van draadlose informele netwerke en sensor netwerke en dit is geskik om netwerke aan te bring wat gewenste eienskappe het soos verspreide koppeling, laer transmissiekrag en kleiner nodus graad.In hierdie ondersoek word 'n verspreide topologie beheertegniek voorgelê wat energie-doeltreffendheid verhoog en radiosteuring verminder in draadlose sensor netwerke. Elke nodus in die netwerk maak lokale besluite oor sy transmissiekrag en die hoogtepunt van hierdie lokale besluite lewer 'n netwerk-topologie op wat globale verbintenis behou.Die topologie wat gelewer word is 'n tweedimensionele grafiek en 'n kragsleutel; dit het laer nodus grade en kan gebou word met lokale inligting. Die netwerk-leeftyd word vermeerder deur transmissiekrag te verminder en verkeer-steuring word verminder deur lae nodus grade. Die benadering tot topologie-beheer wat voorgelê word in hierdie skrif het 'n voordeel oor benaderings wat vroeër ontwikkel is omdat dit nie net op die vermindering van net energie verbruik of net radiosteuring fokus nie, maar op albei. Resultate van simulasies word voorgelê wat die verbetering in werkverrigting demonstreer. / Dissertation (MEng)--University of Pretoria, 2010. / Electrical, Electronic and Computer Engineering / unrestricted

Fueled by the rapid advancement in digital and wireless technologies, the ever-increasing capabilities of wireless devices have placed upon us a tremendous challenge - how to put all of this capability to effective use. Individually, wireless devices have outpaced the ability of users to optimally configure them. Collectively, the complexity is far more daunting. Research in cognitive networks seeks to provide a solution to the diffculty of effectively using the expanding capabilities of wireless networks by embedding greater degrees of intelligence within the network itself. In this dissertation, we address some fundamental questions related to cognitive networks, such as "What is a cognitive network?" and "What methods may be used to design a cognitive network?" We relate cognitive networks to a common artificial intelligence (AI) framework, the multi-agent system (MAS). We also discuss the key elements of learning and reasoning, with the ability to learn being the primary differentiator for a cognitive network. Having discussed some of the fundamentals, we proceed to further illustrate the cognitive networking principle by applying it to two problems: multichannel topology control for dynamic spectrum access (DSA) and routing in a mobile ad hoc network (MANET). The multichannel topology control problem involves confguring secondary network parameters to minimize the probability that the secondary network will cause an outage to a primary user in the future. This requires the secondary network to estimate an outage potential map, essentially a spatial map of predicted primary user density, which must be learned using prior observations of spectral occupancy made by secondary nodes. Due to the complexity of the objective function, we provide a suboptimal heuristic and compare its performance against heuristics targeting power-based and interference-based topology control objectives. We also develop a genetic algorithm to provide reference solutions since obtaining optimal solutions is impractical. We show how our approach to this problem qualifies as a cognitive network. In presenting our second application, we address the role of network state observations in cognitive networking. Essentially, we need a way to quantify how much information is needed regarding the state of the network to achieve a desired level of performance. This question is applicable to networking in general, but becomes increasingly important in the cognitive network context because of the potential volume of information that may be desired for decision-making. In this case, the application is routing in MANETs. Current MANET routing protocols are largely adapted from routing algorithms developed for wired networks. Although optimal routing in wired networks is grounded in dynamic programming, the critical assumption, static link costs and states, that enables the use of dynamic programming for wired networks need not apply to MANETs. We present a link-level model of a MANET, which models the network as a stochastically varying graph that possesses the Markov property. We present the Markov decision process as the appropriate framework for computing optimal routing policies for such networks. We then proceed to analyze the relationship between optimal policy and link state information as a function of minimum distance from the forwarding node. The applications that we focus on are quite different, both in their models as well as their objectives. This difference is intentional and signficant because it disassociates the technology, i.e. cognitive networks, from the application of the technology. As a consequence, the versatility of the cognitive networks concept is demonstrated. Simultaneously, we are able to address two open problems and provide useful results, as well as new perspective, on both multichannel topology control and MANET routing. This material is posted here with permission from the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Virginia Tech library's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it. / Ph. D.

Dans cette thèse, de nouveaux systèmes macromoléculaires ont été conçus et synthétisés dans le but de former de nouvelles structures complexes basées sur des systèmes à chaîne polymère unique. Dans la première partie de ce projet, des chaînons contenant des groupements fonctionnels positionnés de manière précise ont été préparés avec succès dans le but de former des machines moléculaires de type rotaxane. Dans la seconde étude, des origamis macromoléculaires repliés ont été étudiés, et plus particulièrement des chaînes uniques à topologies complexes telles que des composés pseudocycliques ou noué. Ces topologies ont été obtenus en utilisant des ponts disulfures pouvant être positionnés à divers endroits de la chaîne polymère et grâce à des auto-associations intramoléculaires de type métal-ligand. Le placement des groupements fonctionnels et des ponts intramoléculaires dans les chaînes polymères a été rendu possible par le contrôle des séquences de monomères, en s’appuyant sur la cinétique de copolymérisation de monomères styrèniques (donneurs d’électrons) avec des monomères de type maléimides N-substitués (accepteurs). En effet, l’ajout de maléimides N-substitués à des temps contrôlés dans la chaîne de polystyrène en croissance, au moyen de techniques de polymérisations radicalaires contrôlées (vivantes) s’est avéré être une stratégie efficace et rapide pour la régulation de la séquence de monomères dans la chaîne polymère. / In this thesis, new macromolecular systems for single-chain technology were designed and synthesized. In the first study, tracks containing precisely positioned functional groups for single-chain rotaxane-based molecular machines were successfully prepared. In the second study, folded macromolecular origami were investigated, and specifically single-chain complex topologies such as pseudocyclic (Q-shaped) and knotted (α-shaped) using positionable disulfide bridges and intramolecular metal-ligand self-associations. The placement of functional moieties and intramolecular bridges in polymer chains was possible due to the monomer sequence control, by relying on the kinetics of copolymerization of donor styrenic monomer with acceptor N-substituted maleimide monomers. Indeed, time-controlled monomer additions of N-substituted maleimides into growing polystyrene chains by means of controlled/living radical polymerization techniques proved to be a convenient, rapid and scalable strategy for sequence regulation.

No description available.

Abstract Fading in wireless channels, the limited battery energy available in wireless handsets, the changing user demands and the increasing demand for high data rate and low delay pose serious design challenges in the future generations of mobile communication systems. It is necessary to develop efficient transmission policies that adapt to changes in network conditions and achieve the target delay and rate with minimum power consumption. In this thesis, a number of new paradigms in wireless networks are presented. Dynamic programming tools are used to provide dynamic network stabilizing resource allocation solutions for virtualized data centers with clouds, cooperative networks and heterogeneous networks. Exact dynamic programming is used to develop optimal resource allocation and topology control policies for these networks with queues and time varying channels. In addition, approximate dynamic programming is also considered to provide new sub-optimal solutions. Unified system models and unified control problems are also provided for both secondary service provider and primary service provider cognitive networks and for conventional wireless networks. The results show that by adapting to the changes in queue lengths and channel states, the dynamic policy mitigates the effects of primary service provider and secondary service provider cognitive networks on each other. We investigate the network stability and provide new unified stability regions for primary service provider and secondary service provider cognitive networks as well as for conventional wireless networks. The K-step Lyapunov drift is used to analyse the performance and stability of the proposed dynamic control policies, and new unified stability analysis and queuing bound are provided for both primary service provider and secondary service provider cognitive networks and for conventional wireless networks. By adapting to the changes in network conditions, the dynamic control policies are shown to stabilize the network and to minimize the bound for the average queue length. In addition, we prove that the previously proposed frame based does not minimize the bound for the average delay, when there are shared resources between the terminals with queues. / Tiivistelmä Langattomien kanavien häipyminen, langattomien laitteiden akkujen rajallinen koko, käyttäjien käyttötarpeiden muutokset sekä lisääntyvän tiedonsiirron ja lyhyemmän viiveen vaatimukset luovat suuria haasteita tulevaisuuden langattomien verkkojen suunnitteluun. On välttämätöntä kehittää tehokkaita resurssien allokointialgoritmeja, jotka sopeutuvat verkkojen muutoksiin ja saavuttavat sekä tavoiteviiveen että tavoitedatanopeuden mahdollisimman pienellä tehon kulutuksella. Tässä väitöskirjassa esitetään uusia paradigmoja langattomille tietoliikenneverkoille. Dynaamisen ohjelmoinnin välineitä käytetään luomaan dynaamisia verkon stabiloivia resurssien allokointiratkaisuja virtuaalisille pilvipalveludatakeskuksille, käyttäjien yhteistyöverkoille ja heterogeenisille verkoille. Tarkkoja dynaamisen ohjelmoinnin välineitä käytetään kehittämään optimaalisia resurssien allokointi ja topologian kontrollointialgoritmeja näille jonojen ja häipyvien kanavien verkoille. Tämän lisäksi, estimoituja dynaamisen ohjelmoinnin välineitä käytetään luomaan uusia alioptimaalisia ratkaisuja. Yhtenäisiä systeemimalleja ja yhtenäisiä kontrollointiongelmia luodaan sekä toissijaisen ja ensisijaisen palvelun tuottajan kognitiivisille verkoille että tavallisille langattomille verkoille. Tulokset osoittavat että sopeutumalla jonojen pituuksien ja kanavien muutoksiin dynaaminen tekniikka vaimentaa ensisijaisen ja toissijaisen palvelun tuottajien kognitiivisten verkkojen vaikutusta toisiinsa. Tutkimme myös verkon stabiiliutta ja luomme uusia stabiilisuusalueita sekä ensisijaisen ja toissijaisen palveluntuottajan kognitiivisille verkoille että tavallisille langattomille verkoille. K:n askeleen Lyapunovin driftiä käytetään analysoimaan dynaamisen kontrollointitekniikan suorituskykyä ja stabiiliutta. Lisäksi uusi yhtenäinen stabiiliusanalyysi ja jonon yläraja luodaan ensisijaisen ja toissijaisen palveluntuottajan kognitiivisille verkoille ja tavallisille langattomille verkoille. Dynaamisen algoritmin näytetään stabiloivan verkko ja minimoivan keskimääräisen jonon pituuden yläraja sopeutumalla verkon olosuhteiden muutoksiin. Tämän lisäksi todistamme että aiemmin esitetty frame-algoritmi ei minimoi keskimääräisen viiveen ylärajaa, kun käyttäjät jakavat keskenään resursseja.

Abstract The high increase in traffic and data rate for future generations of mobile communication systems, with simultaneous requirement for reduced power consumption, makes Multihop Cellular Networks (MCNs) an attractive technology. To exploit the potentials of MCNs a number of new network paradigms are proposed in this thesis. First, a new algorithm for efficient relaying topology control is presented to jointly optimize the relaying topology, routing and scheduling resulting in a two dimensional or space time routing protocol. The algorithm is aware of intercell interference (ICI), and requires coordinated action between the cells to jointly choose the relaying topology and scheduling to minimize the system performance degradation due to ICI. This framework is extended to include the optimization of power control. Both conventional and cooperative relaying schemes are considered. In addition, a novel sequential genetic algorithm (SGA) is proposed as a heuristic approximation to reconfigure the optimum relaying topology as the network traffic changes. Network coding is used to combine the uplink and downlink transmissions, and incorporate it into the optimum bidirectional relaying with ICI awareness. Seeking for a more tractable network model to effectively use context awareness and relying on the latest results on network information theory, we apply a hexagonal tessellation for inner partition of the cell into smaller subcells of radius r. By using only one single topology control parameter (r), we jointly optimize routing, scheduling and power control to obtain the optimum trade-off between throughput, delay and power consumption in multicast MCNs. This model enables high resolution optimization and motivates the further study of network protocols for MCNs. A new concept for route discovery protocols is developed and the trade-off between cooperative diversity and spatial reuse is analyzed by using this model. Finally, a new architecture for MCN is considered where multihop transmissions are performed by a Delay Tolerant Network, and new solutions to enhance the performance of multicast applications for multimedia content delivery are presented. Numerical results have shown that the algorithms suggested in this thesis provide significant improvement with respect to the existing results, and are expected to have significant impact in the analysis and design of future cellular networks. / Tiivistelmä Tiedonsiirron ja tiedonsiirtonopeuksien suuri kasvu sekä tehonkulutuksen pieneneminen tulevien sukupolvien matkapuhelinjärjestelmissä tekevät monihyppyiset matkapuhelinverkot houkutteleviksi vaihtoehdoiksi. Tässä työssä esitetään uusia tiedonsiirtoverkkojen paradigmoja monihyppyisten matkapuhelinverkkojen hyödyntämiseksi. Työssä esitellään uusi algoritmi tehokkaaseen releointitopologian hallintaan, joka optimoi yhtäaikaisesti topologian, reitityksen sekä lähetyshetkien ajoituksen ja mahdollistaa tila-aika-reititysprotokollan toteutuksen. Esitetty algoritmi huomioi solujen keskinäishäiriön ja vaaditulla solujen välisellä koordinoidulla hallinnalla saadaan yhdessä valittua topologia ja ajoitus, jotka minimoivat solujen keskinäisistä häiriöistä johtuvan suorituskyvyn heikentymisen. Myöhemmin tätä viitekehystä on laajennettu lisäämällä siihen tehonsäädön optimointi. Työssä on tutkittu sekä perinteisiä että kooperatiivisia releointimenetelmiä. Lisäksi työssä esitetään uusi geneettinen algoritmi heuristiseksi approksimaatioksi verkon liikenteen muutoksen vaatimaan releointitopologian uudelleen järjestelyyn. Työssä tarkastellaan lisäksi verkkokoodausta ylä- ja alasuuntaan tapahtuvan tiedonsiirron yhdistämiseksi sisällyttämällä se solujen keskinäishäiriön huomioivaan kahdensuuntaiseen releointiin. Etsittäessä paremmin mukautuvaa ja kontekstitietoisuutta hyödyntävää verkkomallia, joka käyttää hyväkseen viimeisimpiä verkkojen informaatioteoreettisia tuloksia, voidaan verkon solut pilkkoa pienempiin kuusikulmaisiin alisoluihin. Käyttämällä ainoastaan näiden alisolujen sädettä r voidaan puolestaan verkon reititys, ajoitus ja tehon säätö optimoida yhtäaikaisesti saavuttaen paras mahdollinen kompromissi verkon läpäisyn, viiveen ja tehonkulutuksen välillä. Kehitetty malli mahdollistaa korkean resoluution optimoinnin ja motivoi uusien verkkoprotokollien kehitystä monihyppyisissä matkapuhelinverkoissa. Tätä mallia käyttäen esitellään myös uusi konsepti reitinetsintäprotokollille sekä analysoidaan kooperatiivisen diversiteetin ja tila-avaruudessa tapahtuvan uudelleenkäytön välistä kompromissiratkaisua. Lopuksi työssä tarkastellaan monihyppyisen matkapuhelinverkon uutta arkkitehtuuria, jossa monihyppylähetykset suoritetaan viivesietoisella verkolla ja esitetään uusia ratkaisuja multimediasisällön monilähetysten tehokkuuden parantamiseksi. Työssä saadut tulokset osoittavat, että ehdotetut algoritmit parantavat järjestelmien suorituskykyä verrattuna aiemmin tiedossa olleisiin tuloksiin. Työn tuloksilla voidaan olettaa myös olevan suuri vaikutus tulevaisuuden matkapuhelinverkkojen analysointiin ja suunnitteluun.

在無線網狀網路(Wireless Mesh Network)中，每個節點須幫助相鄰節點轉送資料及提供使用者網路存取，例如WLAN(IEEE 802.11s)、WMAN(IEEE 802.16)等，皆可利用多跳接方式將資料轉送至通訊閘道器(Gateway)。在無線網狀網路中，常利用密集佈建的方式來解決通訊死角的問題。當網路節點的密度增加時，無線訊號的干擾也會增強，並且各節點的效能會顯著下降。 在本研究中，將利用幾何學概念，解決網路干擾問題，並提出拓樸重建演算法來重建路徑，使網路干擾達到最小化。我們試著最小化節點與節點間的干擾，以提升整體無線網狀網路效能。我們將網路問題轉換成幾何問題，並定義在幾何圖形中線段交錯問題，之後驗證在幾何圖形中是否有線段交錯的現象發生。若發生線段交錯時，則將此線段從幾何圖形中移除，並且利用三角化演算法將此區域線段重新規劃，使相鄰節點間的干擾最小。當網路拓樸建立完成後，我們利用標準差公式將干擾較大的連線移除，使得網路效能提升。上述測試線段交錯及三角化多邊形演算法可在時間複雜度O(n log n)內找到干擾最小的解。最後，我們將利用網路模擬器(Network Simulator)驗證所提出的方法是否能達到預期的系統效能指標。 / In wireless mesh networks, such as WLAN (IEEE 802.11s), WMAN (IEEE 802.16), etc., each node should forward packets of neighboring nodes toward gateway using multi-hop routing mechanism. In wireless mesh network, as the density of network nodes increases, the RF interference will increase and the throughput of each node will drop rapidly. In our research, we use the geometry to resolve the RF interference problem by rebuilding network topology. We try to minimize the interference between neighboring nodes and improve the throughput in wireless mesh network. We transform the network topology problem into geometry problem and define the line intersection problem in geometric graph, then check path intersection in the geometric graph. If line intersection occurs in the graph, we remove the intersection line from the graph and re-plan the region by triangulation algorithm. When the network topology is built up, we use a standard deviation formula to improve network performance by removing longer links. The line intersection algorithm and triangulation algorithm, both of time complexity O(n log n), are used to find the minimal interference solution. At the end of our research, we use network simulator to verify if the proposed methods can help to meet all those performance expectations.