Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Η διπλωματική εργασία διαπραγματεύεται την εφαρμοσιμότητα του peer-to-peer υπολογισμού και τεχνικών στα ασύρματα κινητά ad-hoc δίκτυα και στα δίκτυα αισθητήρων. Παρουσιάζεται μια παραλλαγή ενός νέου P2P πρωτοκόλλου (Energy Level Distributed Tree) που σαν κύρια λειτουργία του έχει την αύξηση του προσδόκιμου λειτουργίας ενός δικτύου αισθητήρων. Επίσης, γίνεται αναφορά στα πιο δημοφιλή εργαλεία προσομοίωσης για P2P πρωτόκολλα δρομολόγησης και παρουσιάζεται ένα νέο εργαλείο, d-p2p-sim, με δυνατότητα προσομοίωσης εκατομμυρίων κόμβων. Τέλος, εξετάζουμε την απόδοση ενός νέου P2P πρωτοκόλλου δρομολόγησης, του Nested Balanced Distributed Tree, που απαντά με βέλτιστο τρόπο ερωτήμα ακριβούς ταιριάσματος και ερωτήματα διαστήματος παρουσιάζοντας παράλληλα δύο νέους αλγορίθμους αναζήτησης για αυτό. / In this master thesis we study the applicability of the peer-to-peer computing and techniques on wireless ad-hoc networks and sensor-nets. We propose a simplified mapping of an optimal P2P protocol (NBDT) onto sensor-nets, the so called Energy Level Distributed Tree (ELDT), which has one main operation: the life expectancy of a sensor-net. Furthermore, are examined the most popular Peer-to-Peer simulators and is presented a new distributed simulator for P2P routing algorithms. The key feature of the proposed simulator is the ability to simulate millions of peers. Finally, is presented a revised version of the NBDT protocol which is hot-spot free and achieves a better load distribution introducing a negligible routing overhead.

The notion of a fuzzy metric space due to George and Veeramani has many advantages in analysis since many notions and results from classical metric space theory can be extended and generalized to the setting of fuzzy metric spaces, for instance: the notion of completeness, completion of spaces as well as extension of maps. The layout of the dissertation is as follows: Chapter 1 provide the necessary background in the context of metric spaces, while chapter 2 presents some concepts and results from classical metric spaces in the setting of fuzzy metric spaces. In chapter 3 we continue with the study of fuzzy metric spaces, among others we show that: the product of two complete fuzzy metric spaces is also a complete fuzzy metric space. Our main contribution is in chapter 4. We introduce the concept of a standard fuzzy pseudo metric space and present some results on fuzzy metric identification. Furthermore, we discuss some properties of t-nonexpansive maps. / Mathematical Sciences / M. Sc. (Mathematics)

The focus of this thesis is models for non-parametric clustering of multivariate count data. While there has been significant work in Bayesian non-parametric modelling in the last decade, in the context of mixture models for real-valued data and some forms of discrete data such as multinomial-mixtures, there has been much less work on non-parametric clustering of Multi-variate Count Data. The main challenges in clustering multivariate counts include choosing a suitable multivariate distribution that adequately captures the properties of the data, for instance handling over-dispersed data or sparse multivariate data, at the same time leveraging the inherent dependency structure between dimensions and across instances to get meaningful clusters. As the first contribution, this thesis explores extensions to the Multivariate Poisson distribution, proposing efficient algorithms for non-parametric clustering of multivariate count data. While Poisson is the most popular distribution for count modelling, the Multivariate Poisson often leads to intractable inference and a suboptimal t of the data. To address this, we introduce a family of models based on the Sparse-Multivariate Poisson, that exploit the inherent sparsity in multivariate data, reducing the number of latent variables in the formulation of Multivariate Poisson leading to a better t and more efficient inference. We explore Dirichlet process mixture model extensions and temporal non-parametric extensions to models based on the Sparse Multivariate Poisson for practical use of Poisson based models for non-parametric clustering of multivariate counts in real-world applications. As a second contribution, this thesis addresses moving beyond the limitations of Poisson based models for non-parametric clustering, for instance in handling over dispersed data or data with negative correlations. We explore, for the first time, marginal independent inference techniques based on the Gaussian Copula for multivariate count data in the Dirichlet Process mixture model setting. This enables non-parametric clustering of multivariate counts without limiting assumptions that usually restrict the marginal to belong to a particular family, such as the Poisson or the negative-binomial. This inference technique can also work for mixed data (combination of counts, binary and continuous data) enabling Bayesian non-parametric modelling to be used for a wide variety of data types. As the third contribution, this thesis addresses modelling a wide range of more complex dependencies such as asymmetric and tail dependencies during non-parametric clustering of multivariate count data with Vine Copula based Dirichlet process mixtures. While vine copula inference has been well explored for continuous data, it is still a topic of active research for multivariate counts and mixed multivariate data. Inference for multivariate counts and mixed data is a hard problem owing to ties that arise with discrete marginal. An efficient marginal independent inference approach based on extended rank likelihood, based on recent work in the statistics literature, is proposed in this thesis, extending the use vines for multivariate counts and mixed data in practical clustering scenarios. This thesis also explores the novel systems application of Bulk Cache Preloading by analysing I/O traces though predictive models for temporal non-parametric clustering of multivariate count data. State of the art techniques in the caching domain are limited to exploiting short-range correlations in memory accesses at the milli-second granularity or smaller and cannot leverage long range correlations in traces. We explore for the first time, Bulk Cache Preloading, the process of pro-actively predicting data to load into cache, minutes or hours before the actual request from the application, by leveraging longer range correlation at the granularity of minutes or hours. This enables the development of machine learning techniques tailored for caching due to relaxed timing constraints. Our approach involves a data aggregation process, converting I/O traces into a temporal sequence of multivariate counts, that we analyse with the temporal non-parametric clustering models proposed in this thesis. While the focus of our thesis is models for non-parametric clustering for discrete data, particularly multivariate counts, we also hope our work on bulk cache preloading paves the way to more inter-disciplinary research for using data mining techniques in the systems domain. As an additional contribution, this thesis addresses multi-level non-parametric admixture modelling for discrete data in the form of grouped categorical data, such as document collections. Non-parametric clustering for topic modelling in document collections, where a document is as-associated with an unknown number of semantic themes or topics, is well explored with admixture models such as the Hierarchical Dirichlet Process. However, there exist scenarios, where a doc-ument requires being associated with themes at multiple levels, where each theme is itself an admixture over themes at the previous level, motivating the need for multilevel admixtures. Consider the example of non-parametric entity-topic modelling of simultaneously learning entities and topics from document collections. This can be realized by modelling a document as an admixture over entities while entities could themselves be modeled as admixtures over topics. We propose the nested Hierarchical Dirichlet Process to address this gap and apply a two level version of our model to automatically learn author entities and topics from research corpora.

Em ecologia, o comportamento dos animais é freqüentemente estudado para entender melhor suas preferências por diferentes tipos de alimento e habitat. O presente trabalho esta relacionado a este tópico, dividindo-se em três capítulos. O primeiro capitulo refere-se à estimação da função da probabilidade da seleção de recurso (RSPF) comparado com um modelo de escolha discreta (DCM) com uma escolha, usando as estatísticas qui-quadrado para obter as estimativas. As melhores estimativas foram obtidas pelo método DCM com uma escolha. No entanto, os animais não fazem a sua seleção baseados apenas em uma escolha. Com RSPF, as estimativas de máxima verossimilhança, usadas pela regressão logística ainda não atingiram os objetivos, já que os animais têm mais de uma escolha. R e o software Minitab e a linguagem de programação Fortran foram usados para obter os resultados deste capítulo. No segundo capítulo discutimos mais a verossimilhança do primeiro capítulo. Uma nova verossimilhança para a RSPF é apresentada, a qual considera as unidades usadas e não usadas, e métodos de bootstrapping paramétrico e não paramétrico são usados para estudar o viés e a variância dos estimadores dos parâmetros, usando o programa FORTRAN para obter os resultados. No terceiro capítulo, a nova verossimilhança apresentada no capítulo 2 é usada com um modelo de escolha discreta, para resolver parte do problema apresentado no primeiro capítulo. A estrutura de encaixe é proposta para modelar a seleção de habitat de 28 corujas manchadas (Strix occidentalis), assim como a uma generalização do modelo logit encaixado, usando a maximização da utilidade aleatória e a RSPF aleatória. Métodos de otimização numérica, e o sistema computacional SAS, são usados para estimar os parâmetros de estrutura de encaixe. / In ecology, the behavior of animals is often studied to better understand their preferences for different types of habitat and food. The present work is concerned with this topic. It is divided into three chapters. The first concerns the estimation of a resource selection probability function (RSPF) compared with a discrete choice model (DCM) using chi-squared to obtain estimates. The best estimates were obtained by the DCM method. Nevertheless, animals were not selected based on choice alone. With RSPF, the maximum likelihood estimates used with the logistic regression still did not reach the objectives, since the animals have more than one choice. R and Minitab software and the FORTRAN programming language were used for the computations in this chapter. The second chapter discusses further the likelihood presented in the first chapter. A new likelihood for a RSPF is presented, which takes into account the units used and not used, and parametric and non-parametric bootstrapping are employed to study the bias and variance of parameter estimators, using a FORTRAN program for the calculations. In the third chapter, the new likelihood presented in chapter 2, with a discrete choice model is used to resolve a part of the problem presented in the first chapter. A nested structure is proposed for modelling selection by 28 spotted owls (Strix occidentalis) as well as a generalized nested logit model using random utility maximization and a random RSPF. Numerical optimization methods and the SAS system were employed to estimate the nested structural parameters.

The context of this thesis is the numerical simulation of turbulent flows at moderate Reynolds numbers and the improvement of the capabilities of an in-house 3D unsteady and incompressible flow solver called SFELES to simulate such flows.<p>In addition to this abstract, this thesis includes five other chapters.<p><p>The second chapter of this thesis presents the numerical methods implemented in the two CFD solvers used as part of this work, namely SFELES and PHASTA.<p><p>The third chapter concentrates on the implementation of a new library called FlexMG. This library allows the use of various types of iterative solvers preconditioned by algebraic multigrid methods, which require much less memory to solve linear systems than a direct sparse LU solver available in SFELES. Multigrid is an iterative procedure that relies on a series of increasingly coarser approximations of the original 'fine' problem. The underlying concept is the following: low wavenumber errors on fine grids become high wavenumber errors on coarser levels, which can be effectively removed by applying fixed-point methods on coarser levels.<p>Two families of algebraic multigrid preconditioners have been implemented in FlexMG, namely smooth aggregation-type and non-nested finite element-type. Unlike pure gridless multigrid, both of these families use the information contained in the initial fine mesh. A hierarchy of coarse meshes is also needed for the non-nested finite element-type multigrid so that our approaches can be considered as hybrid. Our aggregation-type multigrid is smoothed with either a constant or a linear least square fitting function, whereas the non-nested finite element-type multigrid is already smooth by construction. All these multigrid preconditioners are tested as stand-alone solvers or coupled with a GMRES (Generalized Minimal RESidual) method. After analyzing the accuracy of the solutions obtained with our solvers on a typical test case in fluid mechanics (unsteady flow past a circular cylinder at low Reynolds number), their performance in terms of convergence rate, computational speed and memory consumption is compared with the performance of a direct sparse LU solver as a reference. Finally, the importance of using smooth interpolation operators is also underlined in this work.<p><p>The fourth chapter is devoted to the study of subgrid scale models for the large eddy simulation (LES) of turbulent flows.<p>It is well known that turbulence features a cascade process by which kinetic energy is transferred from the large turbulent scales to the smaller ones. Below a certain size, the smallest structures are dissipated into heat because of the effect of the viscous term in the Navier-Stokes equations.<p>In the classical formulation of LES models, all the resolved scales are used to model the contribution of the unresolved scales. However, most of the energy exchanges between scales are local, which means that the energy of the unresolved scales derives mainly from the energy of the small resolved scales.<p>In this fourth chapter, constant-coefficient-based Smagorinsky and WALE models are considered under different formulations. This includes a classical version of both the Smagorinsky and WALE models and several scale-separation formulations, where the resolved velocity field is filtered in order to separate the small turbulent scales from the large ones. From this separation of turbulent scales, the strain rate tensor and/or the eddy viscosity of the subgrid scale model is computed from the small resolved scales only. One important advantage of these scale-separation models is that the dissipation they introduce through their subgrid scale stress tensor is better controlled compared to their classical version, where all the scales are taken into account without any filtering. More precisely, the filtering operator (based on a top hat filter in this work) allows the decomposition u' = u - ubar, where u is the resolved velocity field (large and small resolved scales), ubar is the filtered velocity field (large resolved scales) and u' is the small resolved scales field. <p>At last, two variational multiscale (VMS) methods are also considered.<p>The philosophy of the variational multiscale methods differs significantly from the philosophy of the scale-separation models. Concretely, the discrete Navier-Stokes equations have to be projected into two disjoint spaces so that a set of equations characterizes the evolution of the large resolved scales of the flow, whereas another set governs the small resolved scales. <p>Once the Navier-Stokes equations have been projected into these two spaces associated with the large and small scales respectively, the variational multiscale method consists in adding an eddy viscosity model to the small scales equations only, leaving the large scales equations unchanged. This projection is obvious in the case of a full spectral discretization of the Navier-Stokes equations, where the evolution of the large and small scales is governed by the equations associated with the low and high wavenumber modes respectively. This projection is more complex to achieve in the context of a finite element discretization. <p>For that purpose, two variational multiscale concepts are examined in this work.<p>The first projector is based on the construction of aggregates, whereas the second projector relies on the implementation of hierarchical linear basis functions.<p>In order to gain some experience in the field of LES modeling, some of the above-mentioned models were implemented first in another code called PHASTA and presented along with SFELES in the second chapter.<p>Finally, the relevance of our models is assessed with the large eddy simulation of a fully developed turbulent channel flow at a low Reynolds number under statistical equilibrium. In addition to the analysis of the mean eddy viscosity computed for all our LES models, comparisons in terms of shear stress, root mean square velocity fluctuation and mean velocity are performed with a fully resolved direct numerical simulation as a reference.<p><p>The fifth chapter of the thesis focuses on the numerical simulation of the 3D turbulent flow over a re-entry Apollo-type capsule at low speed with SFELES. The Reynolds number based on the heat shield is set to Re=10^4 and the angle of attack is set to 180º, that is the heat shield facing the free stream. Only the final stage of the flight is considered in this work, before the splashdown or the landing, so that the incompressibility hypothesis in SFELES is still valid.<p>Two LES models are considered in this chapter, namely a classical and a scale-separation version of the WALE model. Although the capsule geometry is axisymmetric, the flow field in its wake is not and induces unsteady forces and moments acting on the capsule. The characterization of the phenomena occurring in the wake of the capsule and the determination of their main frequencies are essential to ensure the static and dynamic stability during the final stage of the flight. <p>Visualizations by means of 3D isosurfaces and 2D slices of the Q-criterion and the vorticity field confirm the presence of a large meandering recirculation zone characterized by a low Strouhal number, that is St≈0.15.<p>Due to the detachment of the flow at the shoulder of the capsule, a resulting annular shear layer appears. This shear layer is then affected by some Kelvin-Helmholtz instabilities and ends up rolling up, leading to the formation of vortex rings characterized by a high frequency. This vortex shedding depends on the Reynolds number so that a Strouhal number St≈3 is detected at Re=10^4.<p>Finally, the analysis of the force and moment coefficients reveals the existence of a lateral force perpendicular to the streamwise direction in the case of the scale-separation WALE model, which suggests that the wake of the capsule may have some <p>preferential orientations during the vortex shedding. In the case of the classical version of the WALE model, no lateral force has been observed so far so that the mean flow is thought to be still axisymmetric after 100 units of non-dimensional physical time.<p><p>Finally, the last chapter of this work recalls the main conclusions drawn from the previous chapters. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Cette thèse s'articule autour de deux thèmes : l'évaluation monétaire des biens environnementaux et l'innovation en environnement. Si ces deux volets sont traités séparément, ils s'attachent toutefois à contribuer à un objectif commun : la lutte contre le changement climatique. Cette thèse se décline en cinq chapitres. Le premier propose une introduction générale, qui présente les deux thèmes développés, ainsi que leur contribution au défi du changement climatique. En attribuant une valeur pécuniaire aux biens environnementaux, l'évaluation monétaire peut servir la décision publique, non seulement lors de la mise en œuvre de projets pro-environnementaux, mais aussi en aidant é évaluer les dommages causés à l'environnement. L'innovation environnementale peut encourager les transferts de technologies et une croissance plus verte, dans une volonté de développement durable. Les chapitres 2 et 3 s'intéressent aux expériences de choix, en vue d'évaluer le consentement-à-payer pour l'amélioration de la qualité de l'eau de rivières. A partir d'une enquête proposant aux résidents de choisir entre différentes options de gestion pour les rivières de leur voisinage, nous montrons dans le chapitre 2 que ces derniers sont disposés à payer pour une meilleure qualité de l'eau. Nous nous apercevons toutefois que plus de 20% des individus de notre échantillon adoptent un comportement de protestation, c'est-à-dire déclarent un consentement-à-payer nul alors même que leur valeur pour l'eau des rivières est positive. Dans le chapitre 3, nous recourons à un modèle logit emboîté, afin de prendre en compte ce type de comportement. Nous obtenons des consentements-à-payer plus élevés, signe que le modèle utilisé est mieux adapté pour traiter des données comportant des zéros de protestation. Les chapitres 4 et 5 étudient les déterminants de l'innovation en environnement. A partir de données sur les dépôts de brevets et de l'enquête d'opinion du forum économique mondial, le chapitre 4 s'intéresse à l'impact de politiques publiques sur l'innovation en matière de technologies propres dans les domaines de l'eau, de l'air et des déchets. Notre analyse met en évidence le rôle positif sur l'innovation en environnement de la capacité d'innovation globale d'un pays et de la rigueur de ses politiques environnementales. Le chapitre 5 étudie l'influence des collaborations pour la publication d'articles scientifiques sur l'innovation en matière d'énergie éolienne. Nous couplons notre base de données sur les brevets avec une base rassemblant de nombreuses références littéraires dans le domaine de la recherche scientifique. Nous montrons que les transferts de connaissance entre les pays membres et non membres de l'OCDE dans le domaine éolien contribuent à améliorer la capacité d'innovation des pays non membres de l'OCDE. / This dissertation is interested in two areas of the environmental economics field: monetary valuation of environmental goods and services and environmental innovation. Even if those two fields are studied separately in this dissertation, they both aim at contributing to a common objective: fight against climate change. This dissertation ranges into five chapters. The first one is a general introduction, which depicts the two fields of the dissertation and their relevance towards climate change. Environmental valuation serves public decision through monetary valuation of environmental goods. This is useful not only for the implementation of projects directed to environmental protection, but also for the quantification of environmental damages. Environmental innovation may encourage technological transfers, but also a greener growth, in a will that our societies develop themselves following a sustainable path. Chapters 2 and 3 are interested in the choice experiments method in order to value local residents’ willingness-to-pay for water quality improvements at a specific river basin in France. Using a choice experiment with different management regimes for the river basin, we find that residents are willing-to-pay for an improved water quality. Despite this positive result, we observe a significant proportion (20%) of protest bids in our sample. Protest bids are respondents that state a zero willingness-to-pay, even though their true value for the good is positive. In order to take into account the existence of protest bids, we estimate a cross-nested logit model in chapter 3. We then obtain larger willingness-to-pay, which proves that the cross-nested logit model best fits the peculiarity of our data. Chapters 4 and 5 try to identify the drivers of environmental innovation. Using world patent data and data from the world economic forum survey, we study the impact of environmental public policies on innovation in clean technologies directed to water and air pollution, and waste. We find that both general innovative capacity and environmental policy stringency have a positive role on environment-related innovation. Chapter 5 looks at the influence of co-authorship of scientific publications on wind energy-related innovation. We use both the world patent database and the “Scopus” database, which contains lots of scientific literature references. We highlight the existence of knowledge spillovers between OECD and NON-OECD countries. Therefore, we show that knowledge transfers, regarding wind energy-related innovation, between OECD and NON-OECD countries contribute to improve NON-OECD countries' innovative capacity.

Les écoulements en eau peu profonde se rencontrent dans de nombreuses situations d’intérêts : écoulements de rivières et dans les lacs, mais aussi dans les mers et océans (courants de marée, tsunami, etc.). Ils sont modélisés par un système d’équations aux dérivées partielles, où les inconnues sont la vitesse de l’écoulement et la hauteur d’eau. On peut supposer que la composante verticale de la vitesse est petite devant les composantes horizontales et que ces dernières sont indépendantes de la profondeur. Le modèle est alors donné par les équations de shallow water (SWEs). Cette thèse se concentre sur la conception d’une nouvelle technique d’interaction de plusieurs grilles imbriquées pour modèle en eau peu profonde en utilisant des méthodes numériques. La première partie de cette thèse comprend, La dérivation complète de ces équations à partir des équations de Navier- Stokes est expliquée. Etudier le développement et l’évaluation des méthodes numériques en utilisant des méthodes de différences finies et plusieurs exemples numériques sont appliqués utilisant la condition initiale du niveau gaussien pour 2DSWEs. Dans la deuxième partie de la thèse, nous sommes intéressés à proposer une nouvelle technique d’interaction de plusieurs grilles imbriquées pour résoudre les modèles océaniques en utilisant quatre choix des opérateurs de restriction avec des résultats de haute précision. Notre travail s’est concentré sur la résolution numérique de SWE par grilles imbriquées. A chaque niveau de résolution, nous avons utilisé une méthode classique de différences finies sur une grille C d’Arakawa, avec un schéma de leapfrog complété par un filtre d’Asselin. Afin de pouvoir affiner les calculs dans les régions perturbées et de les alléger dans les zones calmes, nous avons considéré plusieurs niveaux de résolution en utilisant des grilles imbriquées. Ceci permet d’augmenter considérablement le rapport performance de la méthode, à condition de régler efficacement les interactions (spatiales et temporelles) entre les grilles. Dans la troisième partie de cette thèse, plusieurs exemples numéériques sont testés pour 2DSWE avec imbriqués 3:1 et 5:1. Finalement, la quatrième partie de ce travail, certaines applications de grilles imbriquées pour le modèle tsunami sont présentées. / Most flows in the rivers, seas, and ocean are shallow water flow in which the horizontal length andvelocity scales are much larger than the vertical ones. The mathematical formulation of these flows, so called shallow water equations (SWEs). These equations are a system of hyperbolic partial differentialequations and they are effective for many physical phenomena in the oceans, coastal regions, riversand canals. This thesis focuses on the design of a new two-way interaction technique for multiple nested grids 2DSWEs using the numerical methods. The first part of this thesis includes, proposing several ways to develop the derivation of shallow water model. The complete derivation of this system from Navier-Stokes equations is explained. Studying the development and evaluation of numerical methods by suggesting new spatial and temporal discretization techniques in a standard C-grid using an explicit finite difference method in space and leapfrog with Robert-Asselin filter in time which are effective for modeling in oceanic and atmospheric flows. Several numerical examples for this model using Gaussian level initial condition are implemented in order to validate the efficiency of the proposed method. In the second part of our work, we are interested to propose a new two-way interaction technique for multiple nested grids to solve ocean models using four choices of higher restriction operators (update schemes) for the free surface elevation and velocities with high accuracy results. Our work focused on the numerical resolution of SWEs by nested grids. At each level of resolution, we used explicit finite differences methods on Arakawa C-grid. In order to be able to refine the calculations in troubled regions and move them into quiet areas, we have considered several levels of resolution using nested grids. This makes it possible to considerably increase the performance ratio of the method, provided that the interactions (spatial and temporal) between the grids are effectively controlled. In the third part of this thesis, several numerical examples are tested to show and verify twoway interaction technique for multiple nested grids of shallow water models can works efficiently over different periods of time with nesting 3:1 and 5:1 at multiple levels. Some examples for multiple nested grids of the tsunami model with nesting 5:1 using moving boundary conditions are tested in the fourth part of this work.

The master thesis deals with the techniques to prevent computer system from computational overloading due to excessive frequency of interruptions. The goal is to document the effect of interupts on a selected computing platform containing the ARM Cortex-M4 processor core. The work describes and implements possible software techniques that reduce the impact of consequences of overload due to excessive interruption frequency. At the same time the work verifies and compares the effectiveness of the particular implemented techniques by appropriate set of experiments.

No description available.