Recent advances in wireless communications along with developments in low-power circuit design and micro-electro mechanical systems (MEMS) have heralded the advent of compact and inexpensive wireless micro-sensor devices. A large network of such sensor nodes capable of communicating with each other provides significant new capabilities for automatically collecting and analyzing data from physical environments. A notable feature of these networks is that more nodes than are strictly necessary may be deployed to cover a given region. This permits the system to provide reliable information, tolerate many types of faults, and prolong the effective service time. Like most wireless systems, achieving low power consumption is a key consideration in the design of these networks. This thesis presents algorithms for managing power at the distributed system level, rather than just at the individual node level. These distributed algorithms allocate work based on user requests to the individual sensor nodes that comprise the network. The primary goal of the algorithms is to provide a robust and scalable approach for tasking nodes that prolongs the effective life of the network. Theoretical analysis and simulation results are presented to characterize the behavior of these algorithms. Results obtained from simulation experiments indicate that the algorithms can achieve a significant increase in the life of the network. In some cases this may be by an order of magnitude. The algorithms are also shown to ensure a good quality of sensor coverage while improving the network life. Finally, they are shown to be robust to faults and scale to large numbers of nodes. / Master of Science

Dans cette thèse, nous nous intéressons à diagnostiquer des systèmes intrinsèquement distribués (comme les systèmes pairs-à-pairs) où chaque pair n'a accès qu'à une sous partie de la description d'un système global. De plus, en raison d'une politique d'accès trop restrictive, il sera pourra qu'aucun pair ne puisse expliquer le comportement du système global. Dans ce contexte, le challenge du diagnostic distribué est le suivant: expliquer le comportement global d'un système distribué par un ensemble de pairs ayant chacun une vision limitée, tout comme l'aurait fait un unique pair diagnostiqueur ayant, lui, une vision globale du système.D'un point de vue théorique, nous montrons que tout nouveau système, logiquement équivalent au système pair-à-pairs initialement observé, garantit que tout diagnostic local d'un pair pourra être prolongé par un diagnostic global (dans ce cas, le nouveau système est dit correct pour le diagnostic distribué).Nous montrons aussi que si ce nouveau système est structuré (c-à-d: il contient un arbre couvrant pour lequel tous les pairs contenant une même variable forme un graphe connecté) alors il garantit que tout diagnostic global pourra être retrouvé à travers un ensemble de diagnostics locaux des pairs (dans ce cas le nouveau système est dit complet pour le diagnostic distribué).Dans un souci de représentation succincte et afin de respecter la politique de confidentialité du vocabulaire de chacun des pairs, nous présentons un nouvel algorithme Token Elimination (TE), qui décompose le système de pairs initial vers un système structuré.Nous montrons expérimentalement que TE produit des décompositions de meilleurs qualité (c-à-d: de plus petites largeurs arborescentes) que les méthodes envisagées dans un contexte distribué. À partir du système structuré construit par TE, nous transformons chaque description locale en une Forme Normale Disjonctive (FND) globalement cohérente.Nous montrons que ce dernier système garantit effectivement un diagnostic distribué correct et complet. En plus, nous exhibons un algorithme capable de vérifier efficacement que tout diagnostic local fait partie d'un diagnostic minimal global, faisant du système structuré de FNDs un système compilé pour le diagnostic distribué. / In this thesis, we focus on diagnosing inherently distributed systems such as peer-to-peer, where each peer has access to only a sub-part of the description of an overall system.In addition, due to a too restrictive access control policy, it can be possible that neither peer nor supervisor is able to explain the behaviour of the overall system.The goal of distributed diagnosis is to explain the behaviour of a distributed system by a set of peers (each having a limited local view) as a single diagnosis engine having a global view of the overall system.First, we show that any new system logically equivalent to the initially observed peer-to-peer setting ensures that all diagnosis of a peer may be extended to a global diagnosis (in this case the new system ensures correctness of the distributed diagnosis).Moreover, we prove that if the new system is structured (i.e.it contains a spanning tree for which all peers containing the same variable form a connected graph) then it ensures that any global diagnosis can be found through a set of local diagnoses (in this case the new system ensures the completeness of the distributed diagnoses).For a succinct representation and in order to comply with the privacy policy of the vocabulary of each peer, we present a new algorithm Token Elimination (TE), which decomposes the original peer system to a structured one.We experimentally show that TE produces better quality decompositions (i.e. smaller tree widths) than proposed methods in a distributed context.From the structured system built by TE, we transform each local description into globally consistent DNF.We demonstrate that the latter system is correct and complete for the distributed diagnosis.Finally, we present an algorithm that can effectively check that any local diagnosis is part of a global minimal diagnosis, turning the structured system of DNFs into a compiled system for distributed diagnosis.

The future of computing lies with distributed systems, i.e. a network of workstations controlled by a modern distributed operating system. By supporting load balancing and parallel execution, the overall performance of a distributed system can be improved dramatically. Process migration, the act of moving a running process from a highly loaded machine to a lightly loaded machine, could be used to support load balancing, parallel execution, reliability etc. This thesis identifies the problems past process migration facilities have had and determines the possible differing strategies that can be used to resolve these problems. The result of this analysis has led to a new design philosophy. This philosophy requires the design of a process migration facility and the design of an operating system to be conducted in parallel. Modern distributed operating systems follow the microkernel and client/server paradigms. Applying these design paradigms, in conjunction with the requirements of both process migration and a distributed operating system, results in a system where each resource is controlled by a separate server process. However, a process is a complex resource composed of simple resources such as data structures, an address space and communication state. For this reason, a process migration facility does not directly migrate the resources of a process. Instead, it requests the appropriate servers to transfer the resources. This novel solution yields a modular, high performance facility that is easy to create, debug and maintain. Furthermore, the design easily incorporates providing multiple migration strategies. In order to verify the validity of this design, a process migration facility was developed and tested within RHODOS (ResearcH Oriented Distributed Operating System). RHODOS is a modern microkernel and client/server based distributed operating system. In RHODOS, a process is composed of at least three separate resources: process state - maintained by a process manager, address space - maintained by a memory manager and communication state - maintained by an InterProcess Communication Manager (IPCM). The RHODOS multiple strategy migration manager utilises the services of the process, memory and IPC Managers to migrate the resources of a process. Performance testing of this facility indicates that this design is as fast or better than existing systems which use faster hardware. Furthermore, by studying the results of the performance test ing, the conditions under which a particular strategy should be employed have been identified. This thesis also addresses heterogeneous process migration. The current trend is to have islands of homogeneous workstations amid a sea of heterogeneity. From this situation and the current literature on the topic, heterogeneous process migration can be seen as too inefficient for general use. Instead, only homogeneous workstations should be used for process migration. This implies a need to locate homogeneous workstations. Entities called traders, which store and disseminate knowledge about the resources of several workstations, should be used to provide resource discovery. Resource discovery will enable the detection of homogeneous workstations to which processes can be migrated.

No description available.

Load distribution problems in distributed computing networks have attracted much attention in the literature. A major objective in these studies is to distribute the processing load so as to minimize the time of processing of the entire load. In general, the processing load can be indivisible or divisible. An indivisible load has to be processed in its entirety on a single processor. On the other hand, a divisible load can be partitioned and processed on more than one processor. Divisible loads are either modularly divisible or arbitrarily divisible. Modularly divisible loads can be divided into pre-defined modules and cannot be further sub-divided. Further, precedence relations between modules may exist. Arbitrarily divisible loads can be divided into several fractions of arbitrary lengths which usually do not have any precedence relations. Such type of loads are characterized by their large volume and the property that each data element requires an identical and independent processing. One of the important problems here is to obtain an optimal load distribution, which minimizes the processing time when the distribution is subject to communication delays in the interconnecting links. A specific application in which such loads are encountered is in edge-detection of images. Here the given image frame can be arbitrarily divided into many sub-frames and each of these can be independently processed. Other applications include processing of massive experimental data. The problems associated with the distribution of such arbitrarily divisible loads are usually analysed in the framework of what is known as divisible job theory. The research work reported in this thesis is a contribution in the area of distributing arbitrarily divisible loads in distributed computing systems subject to communication delays. The main objective in this work is to design and analyseload distribution strategies to minimize the processing time of the entire load in a given network. Two types of networks are considered, namely (i) single-level tree (or star) network and (ii) linear network. In both the networks we assume that there is a non-zero delay associated with load transfer. Further, the processors in the network may or may not be equipped with front-ends (Le., communication co-processors). The main contributions in this thesis are summarized below. First, a mathematical formulation of the load distribution problem in single-level tree and linear networks is presented. In both the networks, it is assumed that there are (m +1) processors and m communication links. In the case of single-level tree networks, the load to be processed is assumed to originate at the root processor, which divides the load into (m +1) fractions, keeps its own share of the load for processing, and distributes the rest to the child processors one at a time and in a fixed sequence. In all the earlier studies in the literature, it had been assumed that for a load distribution to be optimal, it should be such that all the processors must stop computing at the same time. In this thesis, it is shown that this assumption is in general not true, and holds only for a restricted class of single-level tree networks which satisfy a certain condition. The concept of an equivalent network is introduced to obtain a precise formulation of this condition in terms of the processor and link speed parameters. It is shown that this condition can be used to identify processor-link pairs which can be eliminated from a given network (i.e., these processors need not be given any computational load) without degrading its time performance. It is proved that the resultant reduced network (a network from which these inefficient processor-link pairs have been removed) gives the optimal time performance if and only if the load distribution is such that all the processors stop computing at the same time instant. These results are first proved for the case when the root processor is equipped with a front-end and then extended to the case when it is not. In the latter case, an additional condition, between the speed of the root processor and the speed of each of the links, to be satisfied by the network is specified. An optimal sequence for applying these conditions is also obtained. In the case of linear networks the processing load is assumed to originate at the processor situated at one end of the network. Each processor in the network keeps its own load fraction for computing and transmits the rest to its successor. Here too, in all the earlier studies in the literature, it has been assumed that for the processing time to be a minimum, the load distribution must be such that all the processors must stop computing at the same instant in time. Though this condition has been proved by others to be both necessary and sufficient, a different and more rigorous proof, similar to the case of single-level tree network, is presented here. Finally, the effect of inaccurate modelling on the processing time and on the above conditions are discussed through an illustrative example and it is shown that the model adopted in this thesis gives reasonably accurate results. In the case of single-level tree networks, so far it has been assumed that the root processor distributes the processing load in a fixed sequence. However, since there are m child processors, a total of m! different sequences of load distribution are possible. Using the closed-form derived for the processing time, it is proved here that the optimal sequence of load distribution follows the decreasing order of link speeds. Further, if physical rearrangement of processors and links is allowed, then it is shown that the optimal arrangement follows a decreasing order of link and processor speeds with the fastest processor at the root. The entire analysis is first done for the case when the root processor is equipped with a front-end, and then extended to the case when it is not. In the without front-end case, it is shown that the same optimal sequencing result holds. However, in an optimal arrangement, the root processor need not be the fastest. In this case an algorithm has been proposed for obtaining optimal arrangement. Illustrative examples are given for all the cases considered. Next, a new strategy of load distribution is proposed by which the processing time obtained in earlier studies can be further minimized. Here the load is distributed by the root processor to a child processor in more than one installment (instead of in a single installment) such that the processing time is further minimized. First; the case in which all the processors are equipped :tn front-ends is considered. Recursive equations are obtained for a heterogeneous network and these are solved for the special case of a homogeneous network (having identical processors and identical links). Using this closed-form solution, the ultimate limits of performance are explored through an asymptotic analysis with respect to the number of installments and number of processors in the network. Trade-off relationships between the number of installments and the number of processors in the network are also presented. These results are then extended to the case when the processors are not equipped with front-ends. Finally, the efficiency of this new strategy of load distribution is demonstrated by comparing it with the existing single-installment strategy in the literature. The multi-installment strategy explained above is then applied to linear net-As. Here, .the processing load is assumed to originate at one extreme end of the network, First the case when all the processors are equipped with front-ends is considered. Recursive equations for a heterogeneous network are obtained and these are solved for the special case of a homogeneous network. Using this closed form solution, an asymptotic analysis is performed with respect to the number of installments. However, the asymptotic results with respect to the number of processors was obtained computationally since analytical results could not be obtained. It is found that for a given network, once the number of installments is fixed, there is an optimum number of processors to be used in the network, beyond which the time performance degrades. Trade-off relationships between the number of installments and the number of processors is obtained. These results are then extended to the case when the processors are not equipped with front-ends. Comparisions with the existing single-installment strategy is also done. The single-installment strategy discussed in the literature has the disadvantage that the front-ends of the processors are not utilized efficiently in a linear network. This is due to the fact that a processor starts computing its own load fraction only after the entire load to be communicated through its front-end has been received. In this thesis, a new strategy is proposed in which a processor starts computing as soon as it receives its load fraction, simultaneously allowing its front-end to receive and transmit load to its successors. Recursive equations are developed and solved for the special case of a heterogeneous network in which the processors and links are arranged in the decreasing order of speeds. Further, it is shown that in this strategy, if the processing load originates in the interior of the network, the sequence of load distribution should- be such that the load should be first distributed to the side with a lesser number of processors. An expression for the optimal load origination point in the network is derived. A comparative study of this strategy with an earlier strategy is also presented. Finally, it is shown that even though the analysis is carried out for a special case of a heterogeneous network, this load distribution strategy can also be applied to a linear network in which the processors and links are arbitrarily arranged and still obtain a significant improvement in the time performance.

Automatic Global Data Partitioning for Distributed Memory Machines (DMMs) is a difficult problem. Distributed memory machines are scalable, but since the memory is distributed across processors, the scheme of placement of data (arrays) onto local memories of different processors become crucial since any communication between processors for non-local data access is an order of magnitude costlier than access to local memory. Researchers have given varied solutions to this problem, most of which work for uniform dependences in loops and they suggest HPF-like distributions only. For non-uniform dependences the loop was made to run sequentially. In this work, we present a partitioning strategy called Hyperplane Partitioning which works well with loops with non-uniform dependences also. In this method of partitioning, the iteration space is partitioned into as many number of partitions as there are number of logical processors, in such a way that the overall inter-processor communication will be minimum. The idea is to localize as many as dependences as possible so that overall communication both beacuse of non-local data as well as inter-processor synchronizations are reduced. These partitions are then induced into data spaces of the arrays referenced in the loop. Each processor then runs its part of iteration space keeping the data partition that it owns locally. Any non-local data access is implemented by inter-processor communication at run-time.The Hyperplane Partitioning is also extended to a sequence of loops. This is done by first finding Best Local Distribution (BLD) for every loop first and then finding the best way of grouping different adjacent loops (just for finding the data partition) which gives best global data partition. This sequence of distributions/redistributions is found by constructing a data structure called Data Distribution Tree (DDT) and finding the least cost path from the source to any of the leaf nodes in the DDT. The costs for the edges come from the communication cost incurred while running a loop with a particular distribution and redistribution to suit the requirement at the next loop. For this a communication cost estimator is developed which works well for fewer dimensions. To handle complete programs we use some heuristic to find the best global distribution for the entire program.Some optimizations like message optimization to reduce the number of messages sent across processors, time optimization which is done by uniform scheduling across processors, and space optimization to keep only the part of array space that any processor owns onto its local memory, are studied. Hyperplane Partitioning is also implemented using an algorithm for synchronization to handle non-local memory access as well as obeying data dependence constraints. The algorithm is also proved to be correct. The target machine is IBM-SP2 using PVM for the message passing library. The performance of the tool on some standard benchmarks (ADI and RHS) and also on some programs designed by us to show the specific merits of the tool. The results show that the loops which have non-uniform dependences also can be run on DMM with good speed-ups.

In this thesis, space-time block codes originally developed for multiple antenna systems are extended to cooperative multi-hop networks. The designs are applicable to any wireless network setting especially cellular, adhoc and sensor networks where space limitations preclude the use of multiple antennas. The thesis first investigates the design of distributed orthogonal and quasi-orthogonal space time block codes in cooperative networks with single and multiple antennas at the destination. Numerical and simulation results show that by employing multiple receive antennas the diversity performance of the network is further improved at the expense of slight modification of the detection scheme. The thesis then focuses on designing distributed space time block codes for cooperative networks in which the source node participates in cooperation. Based on this, a source-assisting strategy is proposed for distributed orthogonal and quasi-orthogonal space time block codes. Numerical and simulation results show that the source-assisting strategy exhibits improved diversity performance compared to the conventional distributed orthogonal and quasi-orthogonal designs.Motivated by the problem of channel state information acquisition in practical wireless network environments, the design of differential distributed space time block codes is investigated. Specifically, a co-efficient vector-based differential encoding and decoding scheme is proposed for cooperative networks. The thesis then explores the concatenation of differential strategies with several distributed space time block coding schemes namely; the Alamouti code, square-real orthogonal codes, complex-orthogonal codes, and quasiorthogonal codes, using cooperative networks with different number of relay nodes. In order to cater for high data rate transmission in non-coherent cooperative networks, differential distributed quasi-orthogonal space-time block codes which are capable of achieving full code-rate and full diversity are proposed. Simulation results demonstrate that the differential distributed quasi-orthogonal space-time block codes outperform existing distributed space time block coding schemes in terms of code rate and bit-error-rate performance. A multidifferential distributed quasi-orthogonal space-time block coding scheme is also proposed to exploit the additional diversity path provided by the source-destination link.A major challenge is how to construct full rate codes for non-coherent cooperative broadband networks with more than two relay nodes while exploiting the achievable spatial and frequency diversity. In this thesis, full rate quasi-orthogonal codes are designed for noncoherent cooperative broadband networks where channel state information is unavailable. From this, a generalized differential distributed quasi-orthogonal space-frequency coding scheme is proposed for cooperative broadband networks. The proposed scheme is able to achieve full rate and full spatial and frequency diversity in cooperative networks with any number of relays. Through pairwise error probability analysis we show that the diversity gain of the proposed scheme can be improved by appropriate code construction and sub-carrier allocation. Based on this, sufficient conditions are derived for the proposed code structure at the source node and relay nodes to achieve full spatial and frequency diversity. In order to exploit the additional diversity paths provided by the source-destination link, a novel multidifferential distributed quasi-orthogonal space-frequency coding scheme is proposed. The overall objective of the new scheme is to improve the quality of the detected signal at the destination with negligible increase in the computational complexity of the detector.Finally, a differential distributed quasi-orthogonal space-time-frequency coding scheme is proposed to cater for high data rate transmission and improve the performance of noncoherent cooperative broadband networks operating in highly mobile environments. The approach is to integrate the concept of distributed space-time-frequency coding with differential modulation, and employ rotated constellation quasi-orthogonal codes. From this, we design a scheme which is able to address the problem of performance degradation in highly selective fading environments while guaranteeing non-coherent signal recovery and full code rate in cooperative broadband networks. The coding scheme employed in this thesis relaxes the assumption of constant channel variation in the temporal and frequency dimensions over long symbol periods, thus performance degradation is reduced in frequencyselective and time-selective fading environments. Simulation results illustrate the performance of the proposed differential distributed quasi-orthogonal space-time-frequency coding scheme under different channel conditions.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2016-10-25T21:55:38Z No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-25T21:55:54Z (GMT) No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-25T21:56:04Z (GMT) No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) / Made available in DSpace on 2016-10-25T21:56:15Z (GMT). No. of bitstreams: 1 FACHINI_Elizeu_2016.pdf: 7355773 bytes, checksum: 57880fc3ade64c5d25c3ec2901d87e9b (MD5) Previous issue date: 2016-02-24 / Não recebi financiamento / Monitoring is the act of collecting information concerning the characteristics and status of resources of interest. It can be used to the management and allocation of resources, detection and correction of failures and also to the evaluation of performance parameters. To automatically accomplish the monitoring a tool is needed that has functionalities related the acquiring, processing, distributing and presenting of monitoring events. In this work we are interested in a monitoring system to give support to the experimental execution of distributed algorithms, with the objective of correlating the device status with the execution data and, this way, make possible an analysis of cluster resources used by the application. Then, it’s needed a tool with particular characteristics, such as the ability to collect data with a small time period, with low intrusiveness and making the full data available. As was not possible find in the literature a tool with the features required, we developed a new monitoring tool named MSPlus. The features of this tool were evaluated through experiments with the isolated tool and comparing it with other tool. Additionally, we apply the tool in a distribucted system to monitor a distribucted algorithm. / O monitoramento é o ato de coletar informações referentes às características e estado dos recursos de interesse. Ele pode ser utilizado para gerência e alocação de recursos, detec- ção e correção de falhas e também para avaliação de parâmetros de desempenho. Para realizar o monitoramento de modo automático é necessário a utilização de ferramentas, que tem funcionalidades referentes a captação, processamento, distribuição e apresentação dos eventos de monitoramento. Neste trabalho temos interesse em um sistema de monitoramento para dar suporte à execução experimental de algoritmos distribuídos, com o objetivo de relacionar o estado dos dispositivos com os dados da execução e, desta forma, permitir uma análise do uso de recursos do aglomerado pela aplicação. É necessário então uma ferramenta com características particulares como fazer a coleta de informações com pequeno intervalo de tempo, com baixa intrusividade e realizar o armazenamento total dos dados. Como não foi possível encontrar na literatura uma ferramenta com as características desejadas, desenvolvemos uma nova ferramenta de monitoramento chamada MSPlus. As características dessa nova ferramenta foram analisadas através de experimentos de forma isolada e em comparação a outra ferramenta. Adicionalmente, aplicamos a ferramenta em um sistema distribuído monitorando um algoritmo distribuído.

No description available.

In recent years, the power industry has experienced significant changes on the distribution power system primarily due to the implementation of smart-grid technology and the incremental implementation of distributed generation. Distributed Generation (DG) is simply defined as the decentralization of power plants by placing smaller generating units closer to the point of consumption, traditionally ten mega-watts or smaller. While DG is not a new concept, DG is gaining widespread interest primarily for the following reasons: increase in customer demand, advancements in technology, economics, deregulation, environmental and national security concerns. The distribution power system traditionally has been designed for radial power flow, but with the introduction of DG, the power flow becomes bidirectional. As a result, conventional power analysis tools and techniques are not able to properly assess the impact of DG on the electrical system. The presence of DG on the distribution system creates an array of potential problems related to safety, stability, reliability and security of the electrical system. Distributed generation on a power system affects the voltages, power flow, short circuit currents, losses and other power system analysis results. Whether the impact of the DG is positive or negative on the system will depend primarily on the location and size of the DG. The objective of this research is to develop indices and an effective technique to evaluate the impact of distributed generation on a distribution power system and to employ the particle swarm optimization technique to determine the optimal placement and size of the DG unit with an emphasis on improving system reliability while minimizing the following system parameters: power losses, voltage deviation and fault current contributions. This research utilizes the following programs to help solve the optimal DG placement problem: Distribution System Simulator (DSS) and MATLAB. The developed indices and PSO technique successfully solved the optimal DG sizing and placement problem for the I 13-Node, 34-Node and 123-Node Test Cases. The multi-objective index proved to be computational efficient and accurately evaluated the impact of distributed generation on the power system. The results provided valuable information about the system response to single and multiple DG units.