Distributed Extremum-Seeking Control with Applications to High-Altitude Balloons

The real-time optimization of large-scale systems is a difficult problem due to the need for complex models involving uncertain parameters and the high computational cost of solving such problems by a decentralized approach. Extremum-seeking control (ESC) is a model-free real-time optimization technique which can estimate unknown parameters and can optimize nonlinear time-varying systems using only a measurement of the cost function to be minimized. In this thesis, we develop a distributed version of extremum-seeking control which allows large-scale systems to be optimized without models and with minimal computing power. First, we develop a continuous-time distributed extremum-seeking controller. It has three main components: consensus, parameter estimation, and optimization. The consensus provides each local controller with an estimate of the cost to be minimized, allowing them to coordinate their actions. Using this cost estimate, parameters for a local input-output model are estimated, and the cost is minimized by following a gradient descent based on the estimate of the gradient. Next, a similar distributed extremum-seeking controller is developed in discrete-time. Finally, we consider an interesting application of distributed ESC: formation control of high-altitude balloons for high-speed wireless internet. These balloons must be steered into a favourable formation where they are spread out over the Earth and provide coverage to the entire planet. Distributed ESC is applied to this problem, and is shown to be effective for a system of 1200 ballons subjected to realistic wind currents. The approach does not require a wind model and uses a cost function based on a Voronoi partition of the sphere. Distributed ESC is able to steer balloons from a few initial launch sites into a formation which provides coverage to the entire Earth and can maintain a similar formation as the balloons move with the wind around the Earth.

Access Point Association Coordination in Densely Deployed 802.11 Wireless Networks

Dense deployment of wireless local area network (WLAN) access points (APs) is an important part of the next generation Wi-Fi and standardization (802.11ax) efforts are underway. Increasing demand for WLAN connectivity motivates such dense deployments, especially in geographical areas with large numbers of users, such as stadiums, large enterprises, multi-tenant buildings, and urban cities. Although densification of WLAN APs guarantees coverage, it is susceptible to increased interference and uncoordinated association of stations (STAs) to APs, which degrade network throughput. Therefore, to improve network throughput, algorithms are proposed in this thesis to optimally coordinate AP associations in the presence of interference. In essence, coordination of APs in dense WLANs (DWLANs) is achieved through coordination of STAs' associations with APs. While existing approaches suggest tuning of APs' beacon powers or using transmit power control (TPC) for association control, here, the signal-to-interference-plus-noise ratio (SINRs) of STAs and the clear channel assessment (CCA) threshold of the 802.11 MAC protocol are employed. The proposed algorithms in this thesis enhance throughput and minimize coverage holes inherent in cell breathing and TPC techniques by not altering the transmit powers of APs, which determine cell coverage. Besides uncoordinated AP associations, unnecessary frequent transmission deferment is envisaged as another problem in DWLANs due to the clear channel assessment aspect of the carrier sensing multiple access collision avoidance (CSMA/CA) scheme in 802.11 standards and the short spatial reuse distance between co-channel APs. To address this problem in addition to AP association coordination, an algorithm is proposed for CCA threshold adjustment in each AP cell, such that CCA threshold used in one cell mitigates transmission deferment in neighboring cells. Performance evaluation reveals that the proposed association optimization algorithms achieve significant gain in throughput when compared with the default strongest signal first (SSF) association scheme in the current 802.11 standard. Also, further gain in throughput is observed when the CCA threshold adjustment is combined with the optimized association. Results show that when STA-AP association is optimized and CCA threshold is adjusted in each cell, throughput improves. Finally, transmission delay and the number of packet re-transmissions due to collision and contention significantly decrease.

The Genetics of Postglacial Colonization and Peripherality in Northwestern Populations of the Spring Peeper, Pseudacris crucifer

Glaciation over the Pleistocene induced dramatic range fluctuations for species across North America such that postglacial recolonization by southern refugial lineages has characterized the genetic structure of northern North American species. Based on the leading edge model of postglacial range expansion, dispersal and rapid population growth in these northern taxa is expected to produce vast areas of genetic homogeneity. Previous work on the widely distributed spring peeper (Pseudacris crucifer) revealed six distinct mitochondrial lineages that diverged between 3-11 mya, expanding and contracting with glacial cycles. Beginning 16,000 yBP, receding glaciers permitted Eastern lineage refugia residing in the southern Appalachians to migrate northward into the St. Lawrence Valley then westward through most of central Canada. Peripheral populations at the northwestern range limit of P. crucifer in central Manitoba are likely descended from this westward expanding Eastern lineage. According to the central-marginal hypothesis, founder effects from colonization as well as limited gene flow is expected to reveal genetic differentiation and lower genetic diversity in peripheral populations. The goal of my study is to further our understanding of peripheral range dynamics in peripheral Manitoba populations of P. crucifer by determining their genetic affinity and diversity relative to more central populations in Ontario and Minnesota. In this study I amplified and aligned cytochrome b sequences from sample sites across central Manitoba to reconstruct a Bayesian phylogeny for P. crucifer; additionally, microsatellite loci were genotyped to estimate genetic diversity. Results from this study affirmed Eastern lineage descent for peripheral Manitoba sites by aligning with Ontario. Initial colonization by the Interior lineage between glacial retreat and the appearance of arid vicariance events may explain the apparent introgression of non-Eastern lineages in Manitoba. However, genetic diversity measured in expected heterozygosity (H¬e) was not found to be significantly different in Manitoba genotypes. Greater isolation by distance and inbreeding relative to Ontario and Minnesota is likely the primary driver of genetic variation in these sites. Further sampling is necessary to generate a more complete genetic population structure for P. crucifer.