No description available.

Information on the location of mobile nodes in Mobile Ad-hoc Networks (MANETs) has the potential to significantly improve network performance. This thesis uses node location information to develop new techniques for route discovery in on-demand routing protocols such as the Ad-hoc On-Demand Distance Vector (AODV), thus making an important contribution to enhancing the experience of using mobile networks. A Candidate Neighbours to Rebroadcast the Route Request (CNRR) approach has been proposed to reduce the deleterious impact, known as the broadcast storm, of RREQ packets flooding in traditional on-demand routing protocols. The main concept behind CNRR is specifying a set of neighbours which will rebroadcast the received RREQ. This is a departure from the traditional approach of all receiving nodes rebroadcasting RREQs and has the effect of reducing the problem of redundancy from which mobile networks suffer. The proposed protocol has been developed in two phases: Closest-CNRR and Furthest-CNRR. The simulation results show that the proposed algorithms have a significant effect as they reduce the routing overhead of the AODV protocol by up to 28% compared to the C-CNRR, and by up to 17.5% compared to the F-CNRR. Notably, the proposed algorithms simultaneously achieve better throughput and less data dropping. The Link Stability and Energy Aware protocol (LSEA) has been developed to reduce the overhead while increasing network lifetimes. The LSEA helps to control the global dissemination of RREQs in the network by eliminating those nodes that have a residual energy level below a specific threshold value from participation in end-to-end routes. The proposed LSEA protocol significantly increases network lifetimes by up to 19% compared with other on-demand routing protocols while still managing to obtain the same packet delivery ratio and network throughput levels. Furthermore, merging the LSEA and CNRR concepts has the great advantage of reducing the dissemination of RREQs in the network without loss of reachability among the nodes. This increases network lifetimes, reduces the overhead and increases the amount of data sent and received. Accordingly, a Position-based Selective Neighbour (PSN) approach has been proposed which combines the advantages of zoning and link stability. The results show that the proposed technique has notable advantages over both the AODV and MAAODV as it improves delivery ratios by 24.6% and 18.8%, respectively.

Au cours de la dernière décennie, la conception des systèmes embarqués a évolué dans l'optique d'augmenter la puissance de calcul tout en conservant une faible consommation d'énergie. À titre d'exemple, les véhicules autonomes tels que les drones sont un domaine d'application représentatif qui combine de la vision, des communications sans fil avec d'autres noyaux de calculs intensifs, le tout avec un budget énergétique limité. Avec l'avènement des systèmes multicœurs sur puce (MpSoC), la simplification des processeurs a diminué la consommation d'énergie par opération, alors que leur multiplication a amélioré les performances. Cependant, l'apparition du phénomène de ''dark silicon'' a conduit à l'intégration d'accélérateurs matériels spécialisés au sein des systèmes multicœurs. C'est ainsi que sont nées les architectures massivement multicœurs hétérogènes (HMpSoC) combinant des processeurs généralistes (SW) et des accélérateurs matériels (HW). Pour ces architectures hétérogènes, les performances et la consommation d'énergie dépendent d'un large ensemble de paramètres tels que le partitionnement HW/SW, le type d'implémentation HW et le coût de communication entre les organes de calcul HW et SW conduisant ainsi à un immense espace de conception. Dans cette thèse, nous étudions des méthodes permettant la réduction de la complexité de développement et de mise en oeuvre d'applications efficaces en énergie sur HMpSoC. De nombreuses contributions sont proposées pour améliorer les outils d'exploration de l'espace de conception (DSE) avec des objectifs énergétiques. Tout d'abord, une définition formelle de la structure HMpSoC est introduite ainsi qu'une méthode de représentation générique axée sur la hiérarchie mémoire. Ensuite, un outil de modélisation rapide de l'énergie est proposé et validé sur plusieurs applications. Ce modèle énergétique sépare les sources d'énergie en trois catégories (calcul statique, dynamique et communications) et calcule leurs contributions sur la consommation globale de manière indépendante. Basée sur une étude précise des communications, cette approche calcule rapidement la consommation d'énergie pour une répartition donnée d'application sur un HMpSoC. Dans un deuxième temps, nous proposons une méthodologie permettant l'exploration énergétique d'accélérateurs sur HmpSoC. Cette méthode s'appuie sur le modèle de consommation précédent couplé à une formulation de programmation linéaire en nombre entier mixte (MILP). Cela permet de sélectionner efficacement les accélérateurs HW et le partitionnement HW/SW et ainsi d'obtenir une implémentation efficace en énergie pour une application tuilée. Les expériences réalisées ont montré la complexité du processus de validation d'outils/algorithmes de DSE sur une large gamme d'applications et d'architectures. Afin de résoudre ce problème, nous proposons un simulateur d'architectures HMpSoC intégrant un modèle de consommation permettant d'observer l'exécution d'applications. La structure de l'architecture cible est décrite à l'aide d'un fichier de configuration basé sur le modèle de représentation générique précédent. Ce fichier est chargé dynamiquement lors du démarrage du simulateur. De plus, ce simulateur est associé à un générateur d'applications permettant la création d'un large ensemble d'applications représentatives du domaine. Ce générateur se base sur un ensemble de schémas de calcul et de communication élémentaire qu'il combine pour obtenir une application complète. Les applications ainsi obtenues peuvent être enrichies par des informations de placement et automatiquement exécutées sur le simulateur. Cet ensemble d'outils a pour objectif de faciliter la validation de nouveaux algorithmes ciblant le placement efficace en énergie d'application sur une large gamme d'architectures HMpSoC. / During the last decade, the design of embedded systems was pushed to increase computational power while maintaining low energy consumption. As an example, autonomous vehicles such as drones are a representative application domain which combines vision, wireless communications and other computation intensive kernels constrained with a limited energy budget. With the advent of Multiprocessor System-on-Chip (MpSoC) architectures, simplification of processor cores decreased power consumption per operation, while the multiplication of cores brought performance improvement. However, the ''dark silicon'' issue led to the benefit of augmenting programmable processors with specialized hardware accelerators and to the rise of Heterogeneous MpSoC (HMpSoC) combining both software (SW) and hardware (HW) computational resources. For these heterogeneous architectures, performance and energy consumption depend on a large set of parameters such as the HW/SW partitioning, the type of HW implementation or the communication cost between HW and SW cores therefore leading to a huge design space. In this thesis, we study how to reduce the development and implementation complexity of energy-efficient applications on HMpSoC. Multiple contributions are proposed to enhance Design Space Exploration (DSE) tools with energy objectives. First, a formal definition of HMpSoC structure is introduced alongside with a generic representation focused on the memory hierarchy. Then, a fast power modelling tool is proposed and validated on several applications. This power model separates the power sources in three families (static, dynamic computation and dynamic communication) and computes their contributions on global consumption independently. With a fine grain communications study, this approach rapidly computes energy consumption for a given application mapping on a HMpSoC. In a second time, we propose a methodology for energy-driven accelerator exploration on HMpSoC. This method builds upon the previous power model coupled with an Mixed Integer Linear Programming (MILP) formulation and enables to efficiently select HW accelerators and HW/SW partitioning which achieve energy efficient-mapping of a tiled application. The experiments involved in these contributions show the complexity of DSE validation process on a wide range of applications and architectures. To address these issues, we introduce a HMpSoC simulator embedding a power model to monitor application execution. Properties of targeted architectures are described, at run-time with the previous generic representation model. Furthermore, this simulator is coupled with an application generator framework that could build an infinite set of representative applications following predefined computation models. The obtained applications could then be enriched with mapping directive and executed on the simulator. This combination enables to ease the research and validation of new DSE algorithms targeting energy-aware application mapping on a wide range of HMpSoC architectures.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / In clusters and virtualized data centers, the resources must be managed effectively by maximising the SLA fulfilment while minimising the cost. This work proposes a strategy for dynamic resource allocation in virtualized computing environments in order to reduce energy consumption without compromising performance requirements concerning availability and SLA violation. The proposed algorithms, based on classical heuristics, perform virtual machines migration between distinct hosts according to the variation in resources demand. These algorithms were evaluated from measurements in a real environment composed by heterogeneous virtualized hosts. We evaluate their performance in four different scenarios based on the CPU and memory utilization, number of migrations and energy consumption. In general, the results show that the algorithms responsible for consolidation and distribution of virtual machines between hosts are able to reduce energy consumption and dissipate the idle and overload points. / Em clusters e data centers virtualizados, os recursos precisam ser gerenciados com eficÃcia na busca de um trade-off entre a garantia de um atendimento satisfatÃrio à demanda por Qualidade de ServiÃo (QoS) e a reduÃÃo dos custos operacionais por parte dos provedores. Este trabalho propÃe uma estratÃgia para alocaÃÃo dinÃmica de recursos em ambientes computacionais virtualizados com vistas à reduÃÃo do consumo de energia, sem promover sobrecargas que podem comprometer o desempenho dos serviÃos ofertados. Os algoritmos propostos, baseados em heurÃsticas clÃssicas, realizam migraÃÃo de mÃquinas virtuais entre servidores distintos conforme variaÃÃo na demanda por recursos. Estes algoritmos foram verificados e validados por mediÃÃes em um ambiente real composto por servidores virtualizados heterogÃneos. O desempenho da proposta à avaliado em quatro cenÃrios distintos a partir das mÃtricas utilizaÃÃo de CPU, utilizaÃÃo de memÃria, nÃmero de migraÃÃes e consumo de energia. Os resultados mostraram que os algoritmos responsÃveis pela consolidaÃÃo e distribuiÃÃo das mÃquinas virtuais sÃo capazes de reduzir o consumo de energia e dissipar os pontos de Ãcio e sobrecarga do ambiente.

Cloud Computing presents a novel way for businesses to procure their IT needs. Its elasticity and on-demand provisioning enables a shift from capital expenditures to operating expenses, giving businesses the technological agility they need to respond to an ever-changing marketplace. The rapid adoption of Cloud Computing, however, poses a unique challenge to Cloud providers—their already very large electricity bill and carbon footprint will get larger as they expand; managing both costs is therefore essential to their growth. This thesis squarely addresses the above challenge. Recognizing the presence of Cloud data centers in multiple locations and the differences in electricity price and emission intensity among these locations and over time, we develop an optimization framework that couples workload distribution with time-varying signals on electricity price and emission intensity for financial and environmental benefits. The framework is comprised of an optimization model, an aggregate cost function, and 6 scheduling heuristics. To evaluate cost savings, we run simulations with 5 data centers located across North America over a period of 81 days. We use historical data on electricity price, emission intensity, and workload collected from market operators and research data archives. We find that our framework can produce substantial cost savings, especially when workloads are distributed both geographically and temporally—up to 53.35% on electricity cost, or 29.13% on carbon cost, or 51.44% on electricity cost and 13.14% on carbon cost simultaneously.

Dans cette thèse, nous étudions plusieurs modèles de routage efficaces en énergie. Pour chaque modèle, nous présentons une formulation en programmation linéaire mixte permettant de trouver une solution exacte. En outre, comme il s’agit de problèmes NP-Difficiles, nous proposons des heuristiques efficaces pour des réseaux de grande taille. Dans la première partie de cette thèse, nous étudions une solution de routage efficace en énergie dans laquelle nous ajoutons la possibilité d’éliminer des redondances dans les paquets transmis sur le réseau. Nous montrons premièrement que l’ajout de l’élimination des redondances permet d’améliorer l’efficacité énergétique des réseaux en éteignant plus de liens. Ensuite, nous étendons le modèle afin qu’il prenne en compte un certain niveau d’incertitudes dans le volume de trafic et le taux de redondances. La deuxième partie de cette thèse est consacrée aux problèmes qui se posent lors du déploiement de tels protocoles dans les réseaux. Plus particulièrement, nous proposons de minimiser les changements entre deux configurations réseaux consécutives lorsque plusieurs matrices de trafic sont considérées. Le routage des demandes étant alors assuré avec le protocole de routage OSPF (Open Shortest Path First). Ensuite, nous abordons le problème de la limitation du nombre de règles de routage dans les routeurs en utilisant une technologie de type SDN (Software Defined Networks). Enfin, nous présentons en annexe des travaux complémentaires réalisés au cours de cette thèse concernant le routage multicast et le contrôle de congestion TCP. / In this thesis, we study several models of energy-Aware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energy-Aware routing is NP-Hard problem, we also propose efficient heuristic algorithms for large scale networks. In the first part of this thesis, we deal with GreenRE - a new energy-Aware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energy-Aware routing and redundancy elimination to improve energy efficiency for backbone networks. Then, we extend the model in order to take into account uncertainties in traffic volumes and redundancy rates. The second part of this thesis is devoted to the deployment issues of energy- aware routing in practice. In detail, to avoid service deterioration for end-Users, we limit changes of network configurations in multi-Period traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energy-Aware routing configurations. Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm.

<p>As energy costs and energy used by server farms increase, so does the desire to implement energy-aware policies. Although under some cost functions, optimal policies for single as well as multiple server systems are known, large gaps in theoretical knowledge are present in the field. Specifically, there exists many widely used and non-trivial cost functions, where the corresponding optimal policy remains unknown. This work presents and leverages a model which allows for the exact analysis of these optimal policies with considerable generality, for on/off single server systems under a broad range of cost functions that are based on expected response time, energy usage and switching costs. Furthermore, from the results derived in the analysis, several applications and implications are presented and discussed. This includes the determination of routing probabilities to show a range of non-trivial optimal routing probabilities and server configurations when energy concerns are a factor.</p> / Master of Applied Science (MASc)

As increasing functionality in mobile devices leads to rapid battery drain, energy management has gained increasing importance. However, differences in user’s usage contexts and patterns can be leveraged for saving energy. On the other hand, the increasing sensitivity of users’ data, coupled with the need to ensure security in an energy-aware manner, demands careful analyses of trade-offs between energy and security. The research described in this thesis addresses this challenge by 1)modeling the problem of context-adaptive energy-aware security as a combinatorial optimization problem (Context-Sec); 2) proving that the decision version of this problem is NP-Complete, via a reduction from a variant of the well-known Knapsack problem; 3) developing three different algorithms to solve a related offline version of Context-Sec; and 4) implementing tests and compares the performance of the above three algorithms with data-sets derived from real-world smart-phones on wireless networks. The first algorithm presented is a pseudo-polynomial dynamic programming (DP)algorithm that computes an allocation with optimal user benefit using recurrence of the relations; the second algorithm is a greedy heuristic for allocation of security levels based on user benefit per unit of power consumption for each level; and the third algorithm is a Fully Polynomial Time Approximation Scheme (FPTAS) which has a polynomial time execution complexity as opposed to the pseudo-polynomialDP based approach. To the best of the researcher’s knowledge, this is the first work focused on modeling, design, implementation and experimental performance.

在傳統的DTN路由協定中，由於網路拓樸的快速變動，為了能將訊息封包傳送到目的地，通常是透過大量的複製，或是透過資訊的過濾與計算，將封包交由適合的節點來協助傳送。 然而在電池電源有限的條件之下，過於冗餘的封包複製傳遞，或CPU運算的大量使用，將使得節點容易因電量耗盡而失去傳遞的功能，不只是造成整體系統的存活時間(System Lifetime)降低，亦非常不利於維持整體網路的傳遞成功率(Delivery Ratio)。 在旅行的過程中，同行的人們通常具有相同的移動軌跡以及最終目的地，因而形成團體行動的模式；針對這樣的特性，我們採用每個團隊只留下一位領隊來統籌探索鄰居及封包傳遞的概念，透過GPS的資訊輔助來設計出組隊省電機制，延長節點存活時間，進而提升系統存活時間，並在運算複雜度較低且封包冗餘複製亦降低的狀況下，仍保有不錯的傳遞成功率以及較低的效能衰減。 / In traditional routing protocols of DTNs, most of them are using redundancy messages and information computing to make a good relay decision. Due to energy limitation, too many redundant message transmissions or high computing will make nodes die off quickly. It will decrease the system lifetime and diminish the delivery ratio of the whole system. When people go on a tour, friends always form a group due that members have a similar moving path and destination. Based on the features of moving patterns, we design a grouping scheme, namely, Energy-aware Grouping, with the concept that there is only one node awake in a group in charge of contact and message transmissions. With the assistance by GPS, our method has reduced the numbers of redundant message transmissions and information computing. Simulation results show that it can extend the system lifetime with maintaining still good delivery ratio

This work describes the design and implementation of a generic architecture to provide a collective solution for power-aware routing to a wide range of problems in wireless sensor network environments. Power aware-routing is integral to the proposed solutions for different problems. These solutions try to achieve power-efficient routing specific to the problem domain. This can lead to challenging technical problems and deployment barriers when attempting to integrate the solutions. This work extracts various factors to be considered for a range of problems in wireless sensor networks and provides a generic framework for efficient power-aware routing. The architecture aims to relieve researchers from considering power management in their design. We have identified coupling between sources and sinks as the main factor for different design choices for a range of problems. We developed a core-based hierarchical routing framework for efficient power-aware routing that is used to decouple the sources from sinks. The architecture uses only local interaction for scalability and stability in a dynamic network. The architecture provides core-based query forwarding and data dissemination. It uses data aggregation and query aggregation at core nodes to reduce the amount of data to be transmitted. The architecture can be easily extended to incorporate protocols to provide QoS and security to the applications. We use network simulations to evaluate the performance of cluster formation and energy efficiency of the algorithm. Our results show that energy efficiency of the algorithm is better when the transmission range is kept to a minimum for network connectivity as compared to adjustable transmission range.