Stabilizing swarm intelligence search via positive feedback resource allocation

A novel Swarm Intelligence method for best-fit search, Stochastic Diffusion Search, is presented capable of rapid location of the optimal solution in the search space. Population based search mechanisms employed by Swarm Intelligence methods can suffer lack of convergence resulting in ill defined stopping criteria and loss of the best solution. Conversely, as a result of its resource allocation mechanism, the solutions SDS discovers enjoy excellent stability.

Resource allocation analysis of the stochastic diffusion search

The Stochastic Diffusion Search (SDS) was developed as a solution to the best-fit search problem. Thus, as a special case it is capable of solving the transform invariant pattern recognition problem. SDS is efficient and, although inherently probabilistic, produces very reliable solutions in widely ranging search conditions. However, to date a systematic formal investigation of its properties has not been carried out. This thesis addresses this problem. The thesis reports results pertaining to the global convergence of SDS as well as characterising its time complexity. However, the main emphasis of the work, reports on the resource allocation aspect of the Stochastic Diffusion Search operations. The thesis introduces a novel model of the algorithm, generalising an Ehrenfest Urn Model from statistical physics. This approach makes it possible to obtain a thorough characterisation of the response of the algorithm in terms of the parameters describing the search conditions in case of a unique best-fit pattern in the search space. This model is further generalised in order to account for different search conditions: two solutions in the search space and search for a unique solution in a noisy search space. Also an approximate solution in the case of two alternative solutions is proposed and compared with predictions of the extended Ehrenfest Urn model. The analysis performed enabled a quantitative characterisation of the Stochastic Diffusion Search in terms of exploration and exploitation of the search space. It appeared that SDS is biased towards the latter mode of operation. This novel perspective on the Stochastic Diffusion Search lead to an investigation of extensions of the standard SDS, which would strike a different balance between these two modes of search space processing. Thus, two novel algorithms were derived from the standard Stochastic Diffusion Search, ‘context-free’ and ‘context-sensitive’ SDS, and their properties were analysed with respect to resource allocation. It appeared that they shared some of the desired features of their predecessor but also possessed some properties not present in the classic SDS. The theory developed in the thesis was illustrated throughout with carefully chosen simulations of a best-fit search for a string pattern, a simple but representative domain, enabling careful control of search conditions.

Multilayer optimization in radio resource allocation for the packet transmission in wireless networks

In the last decade mobile wireless communications have witnessed an explosive growth in the user’s penetration rate and their widespread deployment around the globe. It is expected that this tendency will continue to increase with the convergence of fixed Internet wired networks with mobile ones and with the evolution to the full IP architecture paradigm. Therefore mobile wireless communications will be of paramount importance on the development of the information society of the near future. In particular a research topic of particular relevance in telecommunications nowadays is related to the design and implementation of mobile communication systems of 4th generation. 4G networks will be characterized by the support of multiple radio access technologies in a core network fully compliant with the Internet Protocol (all IP paradigm). Such networks will sustain the stringent quality of service (QoS) requirements and the expected high data rates from the type of multimedia applications to be available in the near future. The approach followed in the design and implementation of the mobile wireless networks of current generation (2G and 3G) has been the stratification of the architecture into a communication protocol model composed by a set of layers, in which each one encompasses some set of functionalities. In such protocol layered model, communications is only allowed between adjacent layers and through specific interface service points. This modular concept eases the implementation of new functionalities as the behaviour of each layer in the protocol stack is not affected by the others. However, the fact that lower layers in the protocol stack model do not utilize information available from upper layers, and vice versa, downgrades the performance achieved. This is particularly relevant if multiple antenna systems, in a MIMO (Multiple Input Multiple Output) configuration, are implemented. MIMO schemes introduce another degree of freedom for radio resource allocation: the space domain. Contrary to the time and frequency domains, radio resources mapped into the spatial domain cannot be assumed as completely orthogonal, due to the amount of interference resulting from users transmitting in the same frequency sub-channel and/or time slots but in different spatial beams. Therefore, the availability of information regarding the state of radio resources, from lower to upper layers, is of fundamental importance in the prosecution of the levels of QoS expected from those multimedia applications. In order to match applications requirements and the constraints of the mobile radio channel, in the last few years researches have proposed a new paradigm for the layered architecture for communications: the cross-layer design framework. In a general way, the cross-layer design paradigm refers to a protocol design in which the dependence between protocol layers is actively exploited, by breaking out the stringent rules which restrict the communication only between adjacent layers in the original reference model, and allowing direct interaction among different layers of the stack. An efficient management of the set of available radio resources demand for the implementation of efficient and low complexity packet schedulers which prioritize user’s transmissions according to inputs provided from lower as well as upper layers in the protocol stack, fully compliant with the cross-layer design paradigm. Specifically, efficiently designed packet schedulers for 4G networks should result in the maximization of the capacity available, through the consideration of the limitations imposed by the mobile radio channel and comply with the set of QoS requirements from the application layer. IEEE 802.16e standard, also named as Mobile WiMAX, seems to comply with the specifications of 4G mobile networks. The scalable architecture, low cost implementation and high data throughput, enable efficient data multiplexing and low data latency, which are attributes essential to enable broadband data services. Also, the connection oriented approach of Its medium access layer is fully compliant with the quality of service demands from such applications. Therefore, Mobile WiMAX seems to be a promising 4G mobile wireless networks candidate. In this thesis it is proposed the investigation, design and implementation of packet scheduling algorithms for the efficient management of the set of available radio resources, in time, frequency and spatial domains of the Mobile WiMAX networks. The proposed algorithms combine input metrics from physical layer and QoS requirements from upper layers, according to the crosslayer design paradigm. Proposed schedulers are evaluated by means of system level simulations, conducted in a system level simulation platform implementing the physical and medium access control layers of the IEEE802.16e standard.

Retrievals of a size parameter for phytoplankton and spectral light absorption by colored detrital matter from water-leaving radiances at SeaWiFS channels in a continental shelf region off Brazil

Many efforts are currently oriented toward extracting more information from ocean color than the chlorophyll a concentration. Among biological parameters potentially accessible from space, estimates of phytoplankton cell size and light absorption by colored detrital matter (CDM) would lead to an indirect assessment of major components of the organic carbon pool in the ocean, which would benefit oceanic carbon budget models. We present here 2 procedures to retrieve simultaneously from ocean color measurements in a limited number of bands, magnitudes, and spectral shapes for both light absorption by CDM and phytoplankton, along with a size parameter for phytoplankton. The performance of the 2 procedures was evaluated using different data sets that correspond to increasing uncertainties: ( 1) measured absorption coefficients of phytoplankton, particulate detritus, and colored dissolved organic matter ( CDOM) and measured chlorophyll a concentrations and ( 2) SeaWiFS upwelling radiance measurements and chlorophyll a concentrations estimated from global algorithms. In situ data were acquired during 3 cruises, differing by their relative proportions in CDM and phytoplankton, over a continental shelf off Brazil. No local information was introduced in either procedure, to make them more generally applicable. Over the study area, the absorption coefficient of CDM at 443 nm was retrieved from SeaWiFS radiances with a relative root mean square error (RMSE) of 33%, and phytoplankton light absorption coefficients in SeaWiFS bands ( from 412 to 510 nm) were retrieved with RMSEs between 28% and 33%. These results are comparable to or better than those obtained by 3 published models. In addition, a size parameter of phytoplankton and the spectral slope of CDM absorption were retrieved with RMSEs of 17% and 22%, respectively. If these methods are applied at a regional scale, the performances could be substantially improved by locally tuning some empirical relationships.

Definition, realization and evaluation of a software reference architecture for use in space applications

A recent initiative of the European Space Agency (ESA) aims at the definition and adoption of a software reference architecture for use in on-board software of future space missions. Our PhD project placed in the context of that effort. At the outset of our work we gathered all the industrial needs relevant to ESA and all the main European space stakeholders and we were able to consolidate a set of technical high-level requirements for the fulfillment of them. The conclusion we reached from that phase confirmed that the adoption of a software reference architecture was indeed the best solution for the fulfillment of the high-level requirements. The software reference architecture we set on building rests on four constituents: (i) a component model, to design the software as a composition of individually verifiable and reusable software units; (ii) a computational model, to ensure that the architectural description of the software is statically analyzable; (iii) a programming model, to ensure that the implementation of the design entities conforms with the semantics, the assumptions and the constraints of the computational model; (iv) a conforming execution platform, to actively preserve at run time the properties asserted by static analysis. The nature, feasibility and fitness of constituents (ii), (iii) and (iv), were already proved by the author in an international project that preceded the commencement of the PhD work. The core of the PhD project was therefore centered on the design and prototype implementation of constituent (i), a component model. Our proposed component model is centered on: (i) rigorous separation of concerns, achieved with the support for design views and by careful allocation of concerns to the dedicated software entities; (ii) the support for specification and model-based analysis of extra-functional properties; (iii) the inclusion space-specific concerns.

Dissolved aluminium measured on water bottle samples during POLARSTERN cruise ARK-XXII/2 (SPACE)

Concentrations of dissolved (0.2 µm filtered) aluminium (Al) have been determined for the first time in the Eurasian part of the Arctic Ocean over the entire water column during expedition ARK XXII/2 aboard R.V. Polarstern (2007). An unprecedented number of 666 samples was analysed for 44 stations along 5 ocean transects. Dissolved Al in surface layer water (SLW) was very low, close to 1 nM, with lowest SLW concentrations towards the Canadian part of the Arctic Ocean and higher values adjacent to and in the shelf seas. The low SLW concentrations indicate no or little influence from aeolian dust input. Dissolved Al showed a nutrient-type increase with depth up to 28 nM, but large differences existed between the different deep Arctic basins. The differences in concentrations of Al between water masses and basins could largely be related to the different origins of the water masses. In the SLW and intermediate water layers, Atlantic and Pacific inflows were of importance. Deep shelf convection appeared to influence the Al distribution in the deep Eurasian Basin. The Al distribution of the deep Makarov Basin provides evidence for Eurasian Basin water inflow into the deep Makarov Basin. A strong correlation between Al and Silicon (Si) was observed in all basins. This correlation and the nutrient-like profile indicate a strong biological influence on the cycling and distribution of Al. The biological influence can be direct by the incorporation of Al in biogenic silica, indirect by preferential scavenging of Al onto biogenic siliceous particles, or by a combination of both processes. From the slope of the overall Al-Si relationship in the intermediate water layer (AIDW; ~ 200-2000 m depth), an Al/Si ratio of 2.2 atoms Al per 1000 atoms Si was derived. This ratio is consistent with the range of previously reported Al/Si uptake ratio in biogenic opal frustules of diatoms. In the deepest waters (>2000 m depth) a steeper slope of the Al-Si relationship of 7.4 to 13 atoms Al per 1000 atoms Si likely results from entrainment of cold shelf water into the deep basins, carrying the signal of dissolution of terrigenous particles with a much higher Al:Si ratio of crustal abundance. Only a small enrichment with such crustal Al and Si component may readily account for the higher Al:Si slope in the deepest waters.

Barium measured on water bottle samples during POLARSTERN cruise ARK-XXII/2 (SPACE)

Dissolved barium has been shown to have the potential to distinguish Eurasian from North American (NA) river runoff. As part of the ARK-XXII/2 Polarstern expedition in summer 2007, Ba was analyzed in the Barents, Kara, Laptev seas, and the Eurasian Basins as well as the Makarov Basin up to the Alpha and Mendeleyev Ridges. By combining salinity, d18O and initial phosphate corrected for mineralization with oxygen (PO4*) or N/P ratios we identified the water mass fractions of meteoric water, sea ice meltwater, and marine waters of Atlantic as well as Pacific origin in the upper water column. In all basins inside the lower halocline layer and the Arctic intermediate waters we find Ba concentrations close to those of the Fram Strait branch of the lower halocline (41-45 nM), reflecting the composition of the incoming Atlantic water. A layer of upper halocline water (UHW) with higher Ba concentrations (45-55 nM) is identified in the Makarov Basin. Atop of the UHW, the Surface Mixed Layer (SML), including the summer and winter mixed layers, has high concentrations of Ba (58-67 nM). In the SML of the investigated area of the central Arctic the meteoric fraction can be identified by assuming a conservative behavior of Ba to be primarily of Eurasian river origin. However, in productive coastal regions biological removal compromises the use of Ba to distinguish between Eurasian and NA rivers. As a consequence, the NA river water fraction is underestimated in productive surface waters or waters that have passed a productive region, whereas this fraction is overestimated in subsurface waters containing remineralised Ba, particularly when these waters have passed productive shelf regions. Especially in the Laptev Sea and small regions in the Barents Sea, Ba concentrations are low in surface waters. In the Laptev Sea exceptionally high Ba concentrations in shelf bottom waters indicate that Ba is removed from surface waters to deep waters by biological activity enhanced by increasing ice-free conditions as well as by scavenging by organic matter of terrestrial origin. We interpret high Ba concentrations in the UHW of the Makarov Basin to result from enrichment by remineralisation in bottom waters on the shelf of the Chukchi Sea and therefore the calculated NA runoff is an artefact. We conclude that no NA runoff can be demonstrated unequivocally anywhere during our expedition with the set of tracers considered here. Small contributions of NA runoff may have been masked by Ba depletion and could only be resolved by supportive tracers on the uptake history. We thus suggest that Ba has to be used with care as it can put limits but not yield quantitative water mass distributions. Only if the extra Ba inputs exceed the cumulative biological uptake the signal can be unequivocally attributed to NA runoff.

Dissolved iron measurements from 32 stations in the Central Arctic Ocean and Arctic Shelf Sea during POLARSTERN expedition ARK-XXII/2

Concentrations of dissolved (<0.2 µm) Fe (DFe) in the Arctic shelf seas and in the surface waters of the central Arctic Ocean are presented. In the Barents and Kara seas, near-surface DFe minima indicate depletion of DFe by phytoplankton growth. Below the surface, lower DFe concentrations in the Kara Sea (~0.4-0.6 nM) than in the Barents Sea (~0.6-0.8 nM) likely reflect scavenging removal or biological depletion of DFe. Very high DFe concentrations (>10 nM) in the bottom waters of the Laptev Sea shelf may be attributed to either sediment resuspension, sinking of brine or regeneration of DFe in the lower layers. A significant correlation (R2 = 0.60) between salinity and DFe is observed. Using d18O, salinity, nutrients and total alkalinity data, the main source for the high (>2 nM) DFe concentrations in the Amundsen and Makarov Basins is identified as (Eurasian) river water, transported with the Transpolar Drift (TPD). On the North American side of the TPD, the DFe concentrations are low (<0.8 nM) and variations are determined by the effects of sea-ice meltwater, biological depletion and remineralization and scavenging in halocline waters from the shelf. This distribution pattern of DFe is also supported by the ratio between unfiltered and dissolved Fe (high (>4) above the shelf and low (<4) off the shelf).

Quantifying ice-shelf basal melt and ice-stream dynamics using high-resolution DEM and GPS time series

Thesis (Ph.D.)--University of Washington, 2016-06

Application of the cross-entropy method to the buffer allocation problem in a simulation-based environment

The buffer allocation problem (BAP) is a well-known difficult problem in the design of production lines. We present a stochastic algorithm for solving the BAP, based on the cross-entropy method, a new paradigm for stochastic optimization. The algorithm involves the following iterative steps: (a) the generation of buffer allocations according to a certain random mechanism, followed by (b) the modification of this mechanism on the basis of cross-entropy minimization. Through various numerical experiments we demonstrate the efficiency of the proposed algorithm and show that the method can quickly generate (near-)optimal buffer allocations for fairly large production lines.

A framework for automated construction of resource space based on background knowledge

Resource Space Model is a kind of data model which can effectively and flexibly manage the digital resources in cyber-physical system from multidimensional and hierarchical perspectives. This paper focuses on constructing resource space automatically. We propose a framework that organizes a set of digital resources according to different semantic dimensions combining human background knowledge in WordNet and Wikipedia. The construction process includes four steps: extracting candidate keywords, building semantic graphs, detecting semantic communities and generating resource space. An unsupervised statistical language topic model (i.e., Latent Dirichlet Allocation) is applied to extract candidate keywords of the facets. To better interpret meanings of the facets found by LDA, we map the keywords to Wikipedia concepts, calculate word relatedness using WordNet's noun synsets and construct corresponding semantic graphs. Moreover, semantic communities are identified by GN algorithm. After extracting candidate axes based on Wikipedia concept hierarchy, the final axes of resource space are sorted and picked out through three different ranking strategies. The experimental results demonstrate that the proposed framework can organize resources automatically and effectively.©2013 Published by Elsevier Ltd. All rights reserved.

Space division multiple access for wireless sensor networks

This dissertation proposed a self-organizing medium access control protocol (MAC) for wireless sensor networks (WSNs). The proposed MAC protocol, space division multiple access (SDMA), relies on sensor node position information and provides sensor nodes access to the wireless channel based on their spatial locations. SDMA divides a geographical area into space divisions, where there is one-to-one map between the space divisions and the time slots. Therefore, the MAC protocol requirement is the sensor node information of its position and a prior knowledge of the one-to-one mapping function. The scheme is scalable, self-maintaining, and self-starting. It provides collision-free access to the wireless channel for the sensor nodes thereby, guarantees delay-bounded communication in real time for delay sensitive applications. This work was divided into two parts: the first part involved the design of the mapping function to map the space divisions to the time slots. The mapping function is based on a uniform Latin square. A Uniform Latin square of order k = m 2 is an k x k square matrix that consists of k symbols from 0 to k-1 such that no symbol appears more than once in any row, in any column, or in any m x in area of main subsquares. The uniqueness of each symbol in the main subsquares presents very attractive characteristic in applying a uniform Latin square to time slot allocation problem in WSNs. The second part of this research involved designing a GPS free positioning system for position information. The system is called time and power based localization scheme (TPLS). TPLS is based on time difference of arrival (TDoA) and received signal strength (RSS) using radio frequency and ultrasonic signals to measure and detect the range differences from a sensor node to three anchor nodes. TPLS requires low computation overhead and no time synchronization, as the location estimation algorithm involved only a simple algebraic operation.

Effect of Termination of Long-term Free Air CO2 Enrichment on Physiology and Carbon Allocation in a Loblolly Pine Dominated Forest

This dissertation examined the response to termination of CO2 enrichment of a forest ecosystem exposed to long-term elevated atmospheric CO2 condition, and aimed at investigating responses and their underlying mechanisms of two important factors of carbon cycle in the ecosystem, stomatal conductance and soil respiration. Because the contribution of understory vegetation to the entire ecosystem grew with time, we first investigated the effect of elevated CO2 on understory vegetation. Potential growth enhancing effect of elevated CO2 were not observed, and light seemed to be a limiting factor. Secondly, we examined the importance of aerodynamic conductance to determine canopy conductance, and found that its effect can be negligible. Responses of stomatal conductance and soil respiration were assessed using Bayesian state space model. In two years after the termination of CO2 enrichment, stomatal conductance in formerly elevated CO2 returned to ambient level, while soil respiration became smaller than ambient level and did not recovered to ambient in two years.

Dynamic Resource Allocation in Wireless Heterogeneous Networks

Deployment of low power basestations within cellular networks can potentially increase both capacity and coverage. However, such deployments require efficient resource allocation schemes for managing interference from the low power and macro basestations that are located within each other’s transmission range. In this dissertation, we propose novel and efficient dynamic resource allocation algorithms in the frequency, time and space domains. We show that the proposed algorithms perform better than the current state-of-art resource management algorithms. In the first part of the dissertation, we propose an interference management solution in the frequency domain. We introduce a distributed frequency allocation scheme that shares frequencies between macro and low power pico basestations, and guarantees a minimum average throughput to users. The scheme seeks to minimize the total number of frequencies needed to honor the minimum throughput requirements. We evaluate our scheme using detailed simulations and show that it performs on par with the centralized optimum allocation. Moreover, our proposed scheme outperforms a static frequency reuse scheme and the centralized optimal partitioning between the macro and picos. In the second part of the dissertation, we propose a time domain solution to the interference problem. We consider the problem of maximizing the alpha-fairness utility over heterogeneous wireless networks (HetNets) by jointly optimizing user association, wherein each user is associated to any one transmission point (TP) in the network, and activation fractions of all TPs. Activation fraction of a TP is the fraction of the frame duration for which it is active, and together these fractions influence the interference seen in the network. To address this joint optimization problem which we show is NP-hard, we propose an alternating optimization based approach wherein the activation fractions and the user association are optimized in an alternating manner. The subproblem of determining the optimal activation fractions is solved using a provably convergent auxiliary function method. On the other hand, the subproblem of determining the user association is solved via a simple combinatorial algorithm. Meaningful performance guarantees are derived in either case. Simulation results over a practical HetNet topology reveal the superior performance of the proposed algorithms and underscore the significant benefits of the joint optimization. In the final part of the dissertation, we propose a space domain solution to the interference problem. We consider the problem of maximizing system utility by optimizing over the set of user and TP pairs in each subframe, where each user can be served by multiple TPs. To address this optimization problem which is NP-hard, we propose a solution scheme based on difference of submodular function optimization approach. We evaluate our scheme using detailed simulations and show that it performs on par with a much more computationally demanding difference of convex function optimization scheme. Moreover, the proposed scheme performs within a reasonable percentage of the optimal solution. We further demonstrate the advantage of the proposed scheme by studying its performance with variation in different network topology parameters.