This research focuses on improving the efficiency of power market operations by providing system operators additional tools for managing the costs of supplying and delivering electricity. A transmission topology control (TC) framework for production cost reduction based on a shift factor (SF) representation of branch and breaker flows is proposed. The framework models topology changes endogenously while maintaining linearity in the overall Mixed Integer Linear Programming (MILP) formulation. This work develops the DC lossless, and loss-adjusted TC formulations that can be used in a Day Ahead or intra-day market framework as well as an AC-based model that can be used in operational settings. Practical implementation choices for the Shift Factor formulation are discussed as well as the locational marginal prices (LMPs) under the TC MIP setting and their relation to LMPs without TC. Compared to the standard B-theta alternative used so far in TC research, the shift factor framework has significant computational complexity advantages, particularly when a tractably small switchable set is optimized under a representative set of contingency constraints. These claims are supported and elaborated by numerical results.

This dissertation addresses the problem of channel assignment in multi-hop, multi-transceiver wireless networks. We investigate (1) how channels can be assigned throughout the network to ensure that the network is connected and (2) how the channel assignment can be adapted to suit the current traffic demands. We analyze a traffic-aware method for channel assignment that addresses both maintaining network connectivity and adapting the topology based on dynamic traffic demands. The traffic-aware approach has one component that assigns channels independently of traffic conditions and a second component that assigns channels in response to traffic conditions. The traffic-independent (TI) component is designed to allocate as few transceivers or radios as possible in order to maintain network connectivity, while limiting the aggregate interference induced by the topology. The traffic-driven (TD) component is then designed to maximize end-to-end flow rate using the resources remaining after the TI assignment is complete. By minimizing resources in the TI component, the TD component has more resources to adapt the topology to suit the traffic demands and support higher end-to-end flow rate. We investigate the fundamental tradeoff between how many resources are allocated to maintaining network connectivity versus how many resources are allocated to maximize flow rate. We show that the traffic-aware approach achieves an appropriately balanced resource allocation, maintaining a baseline network connectivity and adapting to achieve near the maximum theoretical flow rate in the scenarios evaluated. We develop a set of greedy, heuristic algorithms that address the problem of resource- minimized TI assignment, the first component of the traffic-aware assignment. We develop centralized and distributed schemes for nodes to assign channels to their transceivers. These schemes perform well as compared to the optimal approach in the evaluation. We show that both of these schemes perform within 2% of the optimum in terms of the maximum achievable flow rate. We develop a set of techniques for adapting the network's channel assignment based on traffic demands, the second component of the traffic-aware assignment. In our approach, nodes sense traffic conditions and adapt their own channel assignment independently to support a high flow rate and adapt when network demand changes. We demonstrate how our distributed TI and TD approaches complement each other in an event-driven simulation. / Ph. D.

In recent years, Software Defined and Cognitive Radios (SDRs and CRs) have become popular topics of research. Game theory has proven to be a useful set of tools for analyzing wireless networks, including Cognitive Networks (CNs). This thesis provides a game theoretic cross-layer mechanism that can be used to control SDRs and CRs. We have constructed an upper-layer Topology Control (TC) game, which decides which links each node uses. A TDMA algorithm which we have adapted is then run on these links. The links and the TDMA schedule are then passed to a lower-layer game, the Link Adaptation Game (LAG), where nodes adjust their transmit power and their link parameters, which in this case are modulation scheme and channel coding rate. It is shown that both the TC game and the LAG converge to a Nash Equilibrium (NE). It is also shown that the solution for the TC game approximates the topology that results from maximizing the utility function when appropriate link costs are used. Also seen is the increase in throughput provided by the LAG when compared to the results of Greedy Rate Packing (GRP). / Master of Science

Recently, many natural disasters have occurred (e.g., the 2011 tsunami in Japan). In response to those disasters, Wireless Sensor Networks have been proposed to improve their detection level. This new technology has two main challenges which are routing and topology control where their multi-dimensional dilations need to be improved/balanced. Related to those metrics, the packet delivery factor also needs to be improved/guaranteed. This thesis presents the design of new routing protocols, referred to as: 1) the 3-D Sensing Sphere close to the Line:Smallest Angle to the Line (SSL:SAL) protocol, 2) the 3-D Randomized Sensing Spheres (RSS) protocol, and 3) the SSL:SAL version 1 and version 2 (i.e., SSL:SALv1 and SSL:SALv2, respectively). Through simulations, these protocols are shown to balance/improve the multi-dimensional dilations metrics which also include new bandwidth metrics. The balance/improvement is achieved over some existing position-based protocols. In addition, packet delivery is guaranteed mathematically for new and existing protocols. Furthermore, some experimental evidences are gathered regarding the delivery rate impact on the multi-dimensional metrics. The thesis also proposes a new set of 2-D and 3-D graphs, so called: 1) the Derived Circle version 1 (DCv1) graphs and 2) the Derived Sphere (DSv1) graphs. The new approaches improve the multi-dimensional dilations over some existing graphs. In addition, connectivity, rotability, fault tolerance properties are achieved. Lastly, the thesis develops a framework that combines routing protocols and graphs in fully covered regions. Some experimental evidences demonstrate the improvement of the multi-dimensional metrics and the packet delivery rate for the routing protocols based on the DSv1. This is compared to the routing protocols based on an existing graph. Furthermore, based on either the proposed or existing graphs, some important findings are demonstrated for routing in terms of multi-dimensional metrics and packet delivery rate. Among those findings, the proposed protocol and an exiting protocol have higher delivery rates compared to another existing protocol. Furthermore, the proposed graph improves the multi-dimensional metrics for the proposed and existing protocols over another existing protocol for low communication ranges.

In this thesis we deal with the application of Network Coding to guarantee the Quality of Service (QoS) for wireless multi-hop networks. Since the medium is shared, wireless networks suffer from the negative interference impact on the bandwidth. It is thus interesting to propose a Network Coding based approach that takes into account this interference during the routing process. In this context, we first propose an algorithm minimizing the interference impact for unicast flows while respecting their required bandwidth. Then, we combine it with Network Coding to increase the number of admitted flows and with Topology Control to still improve the interference management. We show by simulation the benefit of combining the three fields: Network Coding, interference consideration and Topology Control. We also deal with delay management for multicast flows and use the Generation-Based Network Coding (GBNC) that combines the packets per blocks. Most of the works on GBNC consider a fixed generation size. Because of the network state variations, the delay of decoding and recovering a block of packets can vary accordingly degrading the QoS. To solve this problem, we propose a network-and content-aware method that adjusts the generation size dynamically to respect a certain decoding delay. We also enhance it to overcome the issue of acknowledgement loss. We then propose to apply our approach in a Home Area Network for Live TV and video streaming. Our solution provides QoS and Quality of Experience for the end user with no additional equipment. Finally, we focus on a more theoretical work in which we present a new Butterfly-based network for multi-source multi-destination flows. We characterize the source node buffer size using the queuing theory and show that it matches the simulation results.

abstract: Corrective transmission topology control schemes are an essential part of grid operations and are used to improve the reliability of the grid as well as the operational efficiency. However, topology control schemes are frequently established based on the operator's past knowledge of the system as well as other ad-hoc methods. This research presents robust corrective topology control, which is a transmission switching methodology used for system reliability as well as to facilitate renewable integration. This research presents three topology control (corrective transmission switching) methodologies along with the detailed formulation of robust corrective switching. The robust model can be solved off-line to suggest switching actions that can be used in a dynamic security assessment tool in real-time. The proposed robust topology control algorithm can also generate multiple corrective switching actions for a particular contingency. The solution obtained from the robust topology control algorithm is guaranteed to be feasible for the entire uncertainty set, i.e., a range of system operating states. Furthermore, this research extends the benefits of robust corrective topology control to renewable resource integration. In recent years, the penetration of renewable resources in electrical power systems has increased. These renewable resources add more complexities to power system operations, due to their intermittent nature. This research presents robust corrective topology control as a congestion management tool to manage power flows and the associated renewable uncertainty. The proposed day-ahead method determines the maximum uncertainty in renewable resources in terms of do-not-exceed limits combined with corrective topology control. The results obtained from the topology control algorithm are tested for system stability and AC feasibility. The scalability of do-not-exceed limits problem, from a smaller test case to a realistic test case, is also addressed in this research. The do-not-exceed limit problem is simplified by proposing a zonal do-not-exceed limit formulation over a detailed nodal do-not-exceed limit formulation. The simulation results show that the zonal approach is capable of addressing scalability of the do-not-exceed limit problem for a realistic test case. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2015

Ad hoc networks are emerging as a cost-effective, yet, powerful tool for communication. These systems, where networks can emerge and converge on-the-fly, are guided by the forward-looking goals of providing ubiquitous connectivity and constant access to information. Due to power and bandwidth constraints, the vulnerability of the wireless medium, and the multi-hop nature of ad hoc networks, these networks are becoming increasingly complex dynamic systems. Besides, modern radios are empowered to be reconfigurable, which harbors the temptation to exploit the system. To understand the implications of these issues, some of which pose significant challenges to efficient network design, we study topology control using game theory. We develop a game-theoretic framework of topology control that broadly captures the radio parameters, one or more of which can be tuned under the purview of topology control. In this dissertation, we consider two parameters, viz. transmit power and channel, and study the impact of controlling these on the emergent topologies. We first examine the impact of node selfishness on the network connectivity and energy efficiency under two levels of selfishness: (a) nodes cooperate and forward packets for one another, but selfishly minimize transmit power levels and; (b) nodes selectively forward packets and selfishly control transmit powers. In the former case, we characterize all the Nash Equilibria of the game and evaluate the energy efficiency of the induced topologies. We develop a better-response-based dynamic that guarantees convergence to the minimal maximum power topology. We extend our analysis to dynamic networks where nodes have limited knowledge about network connectivity, and examine the tradeoff between network performance and the cost of obtaining knowledge. Due to the high cost of maintaining knowledge in networks that are dynamic, mobility actually helps in information-constrained networks. In the latter case, nodes selfishly adapt their transmit powers to minimize their energy consumption, taking into account partial packet forwarding in the network. This work quantifies the energy efficiency gains obtained by cooperation and corroborates the need for incentivizing nodes to forward packets in decentralized, energy-limited networks. We then examine the impact of selfish behavior on spectral efficiency and interference minimization in multi-channel systems. We develop a distributed channel assignment algorithm to minimize the spectral footprint of a network while establishing an interference-free connected network. In spite of selfish channel selections, the network spectrum utilization is shown to be within 12% of the minimum on average. We then extend the analysis to dynamic networks where nodes have incomplete network state knowledge, and quantify the price of ignorance. Under the limitations on the number of available channels and radio interfaces, we analyze the channel assignment game with respect to interference minimization and network connectivity goals. By quantifying the interference in multi-channel networks, we illuminate the interference reduction that can be achieved by utilizing orthogonal channels and by distributing interference over multiple channels. In spite of the non-cooperative behavior of nodes, we observe that the selfish channel selection algorithm achieves load balancing. Distributing the network control to autonomous agents leaves open the possibility that nodes can act selfishly and the overall system is compromised. We advance the need for considering selfish behavior from the outset, during protocol design. To overcome the effects of selfishness, we show that the performance of a non-cooperative network can be enhanced by appropriately incentivizing selfish nodes. / Ph. D.

Dans cette thèse, nous nous intéressons à l’application du codage réseau pour garantir la qualité de service (QoS) dans les réseaux sans fil multi-sauts. Comme le support de transmission est partagé, les réseaux sans fil souffrent de l’impact négatif des interférences sur la bande passante. Il est alors intéressant de proposer une approche basée sur le codage réseau qui prenne en compte ces interférences durant le processus de routage. Dans ce contexte, nous proposons d’abord un algorithme minimisant l’impact des interférences pour des flux unicast tout en respectant la bande passante qu’ils exigent. Puis, nous le combinons avec le codage réseau afin d’augmenter le nombre des flux acceptés et avec le contrôle de topologie pour améliorer davantage la gestion des interférences. Nous montrons par simulation l’intérêt de combiner les trois domaines : codage réseau, gestion des interférences et contrôle de topologie. Nous abordons également la gestion du délai pour les flux multicast et utilisons le codage réseau basé sur les générations (GBNC) qui combine les paquets par bloc. La plupart des travaux portant sur le GBNC considèrent une taille de génération fixe mais à cause des variations de l’état du réseau le délai de décodage et de récupération du bloc de paquets peut varier, dégradant la QoS. Pour résoudre ce problème, nous proposons une méthode qui ajuste la taille de la génération de façon dynamique pour respecter un certain délai de décodage avec prise en compte des contextes réseau et contenu. De plus, nous améliorons notre approche pour contrecarrer les pertes des acquittements. Puis, nous proposons de l’utiliser dans un réseau de domicile pour la diffusion de vidéo à la demande. Notre solution améliore la QoS et la qualité d’expérience pour l’utilisateur final sans équipement additionnel. Finalement, nous abordons un sujet plus théorique dans lequel nous présentons un nouveau réseau basé sur le schéma Butterfly pour des flux multi-sources multi-destinations. Nous caractérisons la taille du buffer du nœud source en utilisant la théorie des files d’attente et montrons qu’elle correspond aux résultats de simulation. / In this thesis we deal with the application of Network Coding to guarantee the Quality of Service (QoS) for wireless multi-hop networks. Since the medium is shared, wireless networks suffer from the negative interference impact on the bandwidth. It is thus interesting to propose a Network Coding based approach that takes into account this interference during the routing process. In this context, we first propose an algorithm minimizing the interference impact for unicast flows while respecting their required bandwidth. Then, we combine it with Network Coding to increase the number of admitted flows and with Topology Control to still improve the interference management. We show by simulation the benefit of combining the three fields: Network Coding, interference consideration and Topology Control. We also deal with delay management for multicast flows and use the Generation-Based Network Coding (GBNC) that combines the packets per blocks. Most of the works on GBNC consider a fixed generation size. Because of the network state variations, the delay of decoding and recovering a block of packets can vary accordingly degrading the QoS. To solve this problem, we propose a network-and content-aware method that adjusts the generation size dynamically to respect a certain decoding delay. We also enhance it to overcome the issue of acknowledgement loss. We then propose to apply our approach in a Home Area Network for Live TV and video streaming. Our solution provides QoS and Quality of Experience for the end user with no additional equipment. Finally, we focus on a more theoretical work in which we present a new Butterfly-based network for multi-source multi-destination flows. We characterize the source node buffer size using the queuing theory and show that it matches the simulation results.

Au cours des dernières années, les communications inter-véhicule (IVC) sont devenues un domaine de recherche intensif, en particulier dans le cadre des systèmes de transport intelligents. Il suppose que la totalité ou une partie des véhicules est équipé de dispositifs radio permettant la communication entre eux. La norme IEEE 802.11p (normalisé pour la communication des véhicules) devrait être la technologie de facto pour ces communications. En utilisant son mode ad hoc, cette technologie radio permet aux véhicules d'étendre la portée de leur communication en formant un réseau multi-saut sans fil Ad - hoc, également appelé Vehicle ad hoc NETwork (VANET). Cette thèse aborde un problème fondamental des VANET : la capacité du réseau. Deux modèles théoriques simples ont été proposés dans cette thèse pour calculer cette capacité: un « packing problem » (la traduction française nous est inconnue) et un modèle Markovien. Ils offrent des formules simples et fermées sur le nombre maximum d'émetteurs simultanés, et sur la distribution de la distance entre eux. Une borne supérieure sur cette capacité a été proposée. De plus, le modèle Markovien a permis de proposer une formule analytique sur la distribution spatiale des émetteurs. Ces quantités nous permettent, entre autres, de paramétrer le mécanisme d’accès au medium du 802.11p, comme par exemple le seuil du CCA (Clear Channel Assessment), amenant à une optimisation de la capacité du réseau. Afin de valider les différentes contributions théoriques de cette thèse, les résultats des modèles analytiques ont été comparés à des simulations effectuées avec le simulateur de réseau NS-3. Les paramètres de simulations ont été estimés à partir d’expérimentations réelles. De plus, différentes distributions de trafic (trafic de véhicules) ont été considéré afin d’évaluer leur impact sur la capacité du réseau. L’une des applications de cette thèse est le dimensionnement des applications de sécurité routière vis-à-vis de la consommation des ressources réseau. Dans ce cadre, nous nous sommes intéressés aux reconstructions de cartes. Il faut comprendre ICI LA reconstitution de l’environnement d’un véhicule (perception map). Ces applications utilisent des informations provenant de capteurs locaux et distants afin d’offrir un système d’aide à la conduite (conduite autonome, alerte sur des collisions, annonce de situations accidentogènes, etc.). Ces applications nécessitent une bande passante élevée. Notre étude théorique a montré que cette bande passante ne sera sans doute pas disponible en pratique dans les réseaux IEEE 802.11p. Par conséquent, UN algorithme adaptatif de contrôle de puissance a été proposé et optimisé pour cette application particulière. Nous avons montré que notre algorithme, par le biais d'un modèle analytique et d'un grand nombre de simulations que la capacité du réseau est augmentée de manière significative. / In recent years, Inter Vehicle Communication (IVC) has become an intensive research area, as part of Intelligent Transportation Systems. It supposes that all, or a subset of the vehicles is equipped with radio devices, enabling communication between them. IEEE 802.11p (standardized for vehicular communication) shows a great deal of promise. By using ad hoc mode, this radio technology allows vehicles to extend their scopes of communication and thus forming a Multi-hop wireless Ad-hoc NETwork, also called Vehicular Ad-hoc NETwork (VANET). This thesis addresses a fundamental problem of VANET: the network capacity. Two simple theoretical models to estimate this capacity have been proposed: a packing model and a Markovian point process model. They offer simple and closed formulae on the maximum number of simultaneous transmitters, and on the distribution of the distance between them. An accurate upper bound on the maximum capacity had been derived. An analytical formula on distribution of the transmitters had been presented. This distribution allows us to optimize Clear Channel Assessment (CCA) parameters that leads to an optimization of the network capacity.In order to validate the approach of this thesis, results from the analytical models are compared to simulations performed with the network simulator NS-3. Simulation parameters was estimated from real experimentation. Impact of different traffic distributions (traffic of vehicles) on the network capacity is also studied. This thesis also focuses on extended perception map applications, which use information from local and distant sensors to offer driving assistance (autonomous driving, collision warning, etc.). Extended perception requires a high bandwidth that might not be available in practice in classical IEEE 802.11p ad hoc networks. Therefore, this thesis proposes an adaptive power control algorithm optimized for this particular application. It shows through an analytical model and a large set of simulations that the network capacity is then significantly increased.

In recent years, Inter Vehicle Communication (IVC) has become an intensive research area, as part of Intelligent Transportation Systems. It supposes that all, or a subset of the vehicles is equipped with radio devices, enabling communication between them. IEEE 802.11p (standardized for vehicular communication) shows a great deal of promise. By using ad hoc mode, this radio technology allows vehicles to extend their scopes of communication and thus forming a Multi-hop wireless Ad-hoc NETwork, also called Vehicular Ad-hoc NETwork (VANET). This thesis addresses a fundamental problem of VANET: the network capacity. Two simple theoretical models to estimate this capacity have been proposed: a packing model and a Markovian point process model. They offer simple and closed formulae on the maximum number of simultaneous transmitters, and on the distribution of the distance between them. An accurate upper bound on the maximum capacity had been derived. An analytical formula on distribution of the transmitters had been presented. This distribution allows us to optimize Clear Channel Assessment (CCA) parameters that leads to an optimization of the network capacity.In order to validate the approach of this thesis, results from the analytical models are compared to simulations performed with the network simulator NS-3. Simulation parameters was estimated from real experimentation. Impact of different traffic distributions (traffic of vehicles) on the network capacity is also studied. This thesis also focuses on extended perception map applications, which use information from local and distant sensors to offer driving assistance (autonomous driving, collision warning, etc.). Extended perception requires a high bandwidth that might not be available in practice in classical IEEE 802.11p ad hoc networks. Therefore, this thesis proposes an adaptive power control algorithm optimized for this particular application. It shows through an analytical model and a large set of simulations that the network capacity is then significantly increased.