Le projet scientifique dans lequel s’inscrit ma thèse a pour objectif l’élaboration d’algorithmes distribués et efficaces pour les réseaux informatiques. Ce projet vise une catégorie particulière des algorithmes distribués, dits auto-stabilisants. Il s’agit d’algorithmes ayant pour propriété de retrouver un comportement correct suite à une panne dans le réseau et ce, sans aucune intervention humaine. Le travail effectué en collaboration avec mes directeurs de thèse s’est concentré, plus précisément, autour des problèmes de couplage, de cliques et des paradigmes de publications-souscriptions dans ce domaine de l’informatique théorique. Dans un premier temps on a traité le problème du couplage maximal dans sa version anonyme, en fournissant un algorithme auto-stabilisant probabiliste et efficace. Ces travaux sont parus dans le journal PPL. De plus, on s’est intéressé au problème du couplage dans sa version maximum identifiée. Son travail améliore le dernier algorithme présent dans la littérature pour l’approximation de ce type de couplage au 2/3 de la solution optimale. Ces travaux sont parus dans une conférence internationale OPODIS. Par ailleurs, j'ai eu l’opportunité de collaborer en Allemagne avec Prof. Volker Turau au sein du groupe de télématique de l’Université technique de Hambourg. Le cadre de cette collaboration a été les algorithmes auto-stabilisants pour les paradigmes de publication-souscription. Cela a abouti à un algorithme efficace pour la version en canal de ce problème, introduisant la notion de raccourci pour le routage de messages dans ces paradigmes. Les résultats ont fait l’objet d’un Brief Announcement et d’un papier, publiés dans des conférences internationales, SSS et NetSyS. J'ai aussi bénéficié d’une collaboration avec Mr. Gerry Siegemund qui a été accueilli au laboratoire d’Informatique de l’École Polytechnique. Il a été question de trouver un algorithme efficace et auto-stabilisant pour la partition d’un réseau en cliques. Cette collaboration a eu pour résultat un algorithme pour le problème améliorant le dernier en date. Ce résultat est en cours de rédaction pour soumission à une conférence internationale. / The main focus of my thesis is the design of an efficient kind of distributed algorithms, known as: Self-stabilizing. These algorithms have the property to recover from faults in the environment they're executed in, and this without any human intervention. Recovering here, means converging toward a pre-defined, correct configuration. In this setting, I was mainly interested by the problems of matching in graphs, clique partitions and publication subscription paradigms. For the maximal version of the matching problem in anonymous graphs, we achieved a more efficient randomized, self-stabilizing algorithm. This work is published in a journal version in PPL. The maximum version of the same problem, but in an identified setting, led to the design of an efficient self-stabilizing algorithm that approximates the optimal solution up to the 2/3. This result was published at OPODIS. During a research visit at TUHH, Hamburg, Germany. Together with Pr. Volker Turau we tackled the problem of self-stabilizing publish/subscribe paradigms. This led to an algorithm introducing the new notion of short-cuts in this type of structures and was published under a brief announcement and a regular paper at SSS and NetSyS. In collaboration with Mr. Siegemund, then a visiting researcher at LIX, École Polytechnique, we worked on an efficient self-stabilizing algorithm for clique partitions. This work is still in progress and in preparation for an eventual publication.

No description available.

No description available.

Tesis por compendio / [EN] The long-lasting trend in the field of computation of stress and resource distribution has found its way into computer networks via the concept of peer-to-peer (P2P) connectivity. P2P is a symmetrical model, where each network node is enabled a comparable range of capacities and resources. It stands in a stark contrast to the classical, strongly asymmetrical client-server approach. P2P, originally considered only a complimentary, server-side structure to the straightforward client-server model, has been shown to have the substantial potential on its own, with multiple, widely known benefits: good fault tolerance and recovery, satisfactory scalability and intrinsic load distribution. However, contrary to client-server, P2P networks require sophisticated solutions on all levels, ranging from network organization, to resource location and managing. In this thesis we address one of the key issues of P2P networks: performing efficient resource searches of semantic nature under realistic, dynamic conditions. There have been numerous solutions to this matter, with evolutionary, stigmergy-based, and simple computational foci, but few attempt to resolve the full range of challenges this problem entails. To name a few: real-life P2P networks are rarely static, nodes disconnect, reconnect and change their content. In addition, a trivial incorporation of semantic searches into well-known algorithms causes significant decrease in search efficiency. In our research we build a solution incrementally, starting with the classic Ant Colony System (ACS) within the Ant Colony Optimization metaheuristic (ACO). ACO is an algorithmic framework used for solving combinatorial optimization problems that fits contractually the problem very well, albeit not providing an immediate solution to any of the aforementioned problems. First, we propose an efficient ACS variant in structured (hypercube structured) P2P networks, by enabling a path-post processing algorithm, which called Tabu Route Optimization (TRO). Next, we proceed to resolve the issue of network dynamism with an ACO-compatible information diffusion approach. Consequently, we attempt to incorporate the semantic component of the searches. This initial approximation to the problem was achieved by allowing ACS to differentiate between search types with the pheromone-per-concept idea. We called the outcome of this merger Routing Concept ACS (RC-ACS). RC-ACS is a robust, static multipheromone implementation of ACS. However, we were able to conclude from it that the pheromone-per-concept approach offers only limited scalability and cannot be considered a global solution. Thus, further progress was made in this respect when we introduced to RC-ACS our novel idea: dynamic pheromone creation, which replaces the static one-to-one assignment. We called the resulting algorithm Angry Ant Framework (AAF). In AAF new pheromone levels are created as needed and during the search, rather than prior to it. The final step was to enable AAF, not only to create pheromone levels, but to reassign them to optimize the pheromone usage. The resulting algorithm is called EntropicAAF and it has been evaluated as one of the top-performing algorithms for P2P semantic searches under all conditions. / [ES] La popular tendencia de distribución de carga y recursos en el ámbito de la computación se ha transmitido a las redes computacionales a través del concepto de la conectividad peer-to-peer (P2P). P2P es un modelo simétrico, en el cual a cada nodo de la red se le otorga un rango comparable de capacidades y recursos. Se trata de un fuerte contraste con el clásico y fuertemente asimétrico enfoque cliente-servidor. P2P, originalmente considerado solo como una estructura del lado del servidor complementaria al sencillo modelo cliente-servidor, ha demostrado tener un potencial considerable por sí mismo, con múltiples beneficios ampliamente conocidos: buena tolerancia a fallos y recuperación, escalabilidad satisfactoria y distribución de carga intrínseca. Sin embargo, al contrario que el modelo cliente-servidor, las redes P2P requieren de soluciones sofisticadas a todos los niveles, desde la organización de la red hasta la gestión y localización de recursos. Esta tesis aborda uno de los problemas principales de las redes P2P: la búsqueda eficiente de recursos de naturaleza semántica bajo condiciones dinámicas y realistas. Ha habido numerosas soluciones a este problema basadas en enfoques evolucionarios, estigmérgicos y simples, pero pocas han tratado de resolver el abanico completo de desafíos. En primer lugar, las redes P2P reales son raramente estáticas: los nodos se desconectan, reconectan y cambian de contenido. Además, la incorporación trivial de búsquedas semánticas en algoritmos conocidos causa un decremento significativo de la eficiencia de la búsqueda. En esta investigación se ha construido una solución de manera incremental, comenzando por el clásico Ant Colony System (ACS) basado en la metaheurística de Ant Colony Optimization (ACO). ACO es un framework algorítmico usado para búsquedas en grafos que encaja perfectamente con las condiciones del problema, aunque no provee una solución inmediata a las cuestiones mencionadas anteriormente. En primer lugar, se propone una variante eficiente de ACS para redes P2P estructuradas (con estructura de hipercubo) permitiendo el postprocesamiento de las rutas, al que hemos denominado Tabu Route Optimization (TRO). A continuación, se ha tratado de resolver el problema del dinamismo de la red mediante la difusión de la información a través de una estrategia compatible con ACO. En consecuencia, se ha tratado de incorporar el componente semántico de las búsquedas. Esta aproximación inicial al problema ha sido lograda permitiendo al ACS diferenciar entre tipos de búsquedas através de la idea de pheromone-per-concept. El resultado de esta fusión se ha denominado Routing Concept ACS (RC-ACS). RC-ACS es una implementación multiferomona estática y robusta de ACS. Sin embargo, a partir de esta implementación se ha podido concluir que el enfoque pheromone-per-concept ofrece solo escalabilidad limitada y que no puede ser considerado una solución global. Por lo tanto, para lograr una mejora a este respecto, se ha introducido al RC-ACS una novedosa idea: la creación dinámica de feromonas, que reemplaza la asignación estática uno a uno. En el algoritmo resultante, al que hemos denominado Angry Ant Framework (AAF), los nuevos niveles de feromona se crean conforme se necesitan y durante la búsqueda, en lugar de crearse antes de la misma. La mejora final se ha obtenido al permitir al AAF no solo crear niveles de feromona, sino también reasignarlos para optimizar el uso de la misma. El algoritmo resultante se denomina EntropicAAF y ha sido evaluado como uno de los algoritmos más exitosos para las búsquedas semánticas P2P bajo todas las condiciones. / [CA] La popular tendència de distribuir càrrega i recursos en el camp de la computació s'ha estès cap a les xarxes d'ordinadors a través del concepte de connexions d'igual a igual (de l'anglès, peer to peer o P2P). P2P és un model simètric on cada node de la xarxa disposa del mateix nombre de capacitats i recursos. P2P, considerat originàriament només una estructura situada al servidor complementària al model client-servidor simple, ha provat tindre el suficient potencial per ella mateixa, amb múltiples beneficis ben coneguts: una bona tolerància a errades i recuperació, una satisfactòria escalabilitat i una intrínseca distribució de càrrega. No obstant, contràriament al client-servidor, les xarxes P2P requereixen solucions sofisticades a tots els nivells, que varien des de l'organització de la xarxa a la localització de recursos i la seua gestió. En aquesta tesi s'adreça un dels problemes clau de les xarxes P2P: ser capaç de realitzar eficientment cerques de recursos de naturalesa semàntica sota condicions realistes i dinàmiques. Existeixen nombroses solucions a aquest tema basades en la computació simple, evolutiva i també basades en l'estimèrgia (de l'anglès, stigmergy), però pocs esforços s'han realitzat per intentar resoldre l'ampli conjunt de reptes existent. En primer lloc, les xarxes P2P reals són rarament estàtiques: els nodes es connecten, desconnecten i canvien els seus continguts. A més a més, la incorporació trivial de cerques semàntiques als algorismes existents causa una disminució significant de l'eficiència de la cerca. En aquesta recerca s'ha construït una solució incremental, començant pel sistema clàssic de colònia de formigues (de l'anglés, Ant Colony System o ACS) dins de la metaheurística d'optimització de colònies de formigues (de l'anglès, Ant Colony Optimization o ACO). ACO és un entorn algorísmic utilitzat per cercar en grafs i que aborda el problema de forma satisfactòria, tot i que no proveeix d'una solució immediata a cap dels problemes anteriorment mencionats. Primer, s'ha proposat una variant eficient d'ACS en xarxes P2P estructurades (en forma d'hipercub) a través d'un algorisme de processament post-camí el qual s'ha anomenat en anglès Tabu Route Optimization (TRO). A continuació, s'ha procedit a resoldre el problema del dinamisme de les xarxes amb un enfocament de difusió d'informació compatible amb ACO. Com a conseqüència, s'ha intentat incorporar la component semàntica de les cerques. Aquest enfocament inicial al problema s'ha realitzat permetent a ACS diferenciar entre tipus de cerques amb la idea de ''feromona per concepte'', i s'ha anomenat a aquest producte Routing Concept ACS o RC-ACS. RC-ACS és una implementació multi-feromona robusta i estàtica d'ACS. No obstant, s'ha pogut concloure que l'enfocament de feromona per concepte ofereix només una escalabilitat limitada i no pot ser considerada una solució global. En aquest respecte s'ha realitzat progrés posteriorment introduint una nova idea a RC-ACS: la creació dinàmica de feromones, la qual reemplaça a l'assignació un a un de les mateixes. A l'algorisme resultant se l'ha anomenat en anglès Angry Ant Framework (AAF). En AAF es creen nous nivells de feromones a mesura que es necessiten durant la cerca, i no abans d'aquesta. El progrés final s'ha aconseguit quan s'ha permès a AAF, no sols crear nivells de feromones, sinó reassignar-los per optimitzar la utilització de feromones. L'algorisme resultant s'ha anomenat EntropicAAF i ha sigut avaluat com un dels algorismes per a cerques semàntiques P2P amb millors prestacions. / Krynicki, KK. (2016). Ant Colony Algorithms for the Resolution of Semantic Searches in P2P Networks [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/61293 / Premios Extraordinarios de tesis doctorales / Compendio

Networks are a mathematical abstraction of the interactions between a set of entities, with extensive applications in social science, epidemiology, bioinformatics, and cybersecurity, among others. There are many fundamental problems when analyzing network data, such as anomaly detection, dense subgraph mining, motif finding, information diffusion, and epidemic spread. A common underlying task in all these problems is finding an "interesting subgraph"; that is, finding a part of the graph---usually small relative to the whole---that optimizes a score function and has some property of interest, such as connectivity or a minimum density. Finding subgraphs that satisfy common constraints of interest, such as the ones above, is computationally hard in general, and state-of-the-art algorithms for many problems in network analysis are heuristic in nature. These methods are fast and usually easy to implement. However, they come with no theoretical guarantees on the quality of the solution, which makes it difficult to assess how the discovered subgraphs compare to an optimal solution, which in turn affects the data mining task at hand. For instance, in anomaly detection, solutions with low anomaly score lead to sub-optimal detection power. On the other end of the spectrum, there have been significant advances on approximation algorithms for these challenging graph problems in the theoretical computer science community. However, these algorithms tend to be slow, difficult to implement, and they do not scale to the large datasets that are common nowadays. The goal of this dissertation is developing scalable algorithms with theoretical guarantees for various network analysis problems, where the underlying task is to find subgraphs with constraints. We find interesting subgraphs with guarantees by adapting techniques from parameterized complexity, convex optimization, and submodularity optimization. These techniques are well-known in the algorithm design literature, but they lead to slow and impractical algorithms. One unifying theme in the problems that we study is that our methods are scalable without sacrificing the theoretical guarantees of these algorithm design techniques. We accomplish this combination of scalability and rigorous bounds by exploiting properties of the problems we are trying to optimize, decomposing or compressing the input graph to a manageable size, and parallelization. We consider problems on network analysis for both static and dynamic network models. And we illustrate the power of our methods in applications, such as public health, sensor data analysis, and event detection using social media data. / Ph. D. / Networks are a mathematical abstraction of the interactions between a set of entities, with extensive applications in social science, epidemiology, bioinformatics, and cybersecurity, among others. There are many fundamental problems when analyzing network data, such as anomaly detection, dense subgraph mining, motif finding, information diffusion, and epidemic spread. A common underlying task in all these problems is finding an “interesting subgraph”; that is, finding a part of the graph—usually small relative to the whole—that optimizes a score function and has some property of interest, such as being connected. Finding subgraphs that satisfy common constraints of interest is computationally hard, and existing techniques for many problems of this kind are heuristic in nature. Heuristics are fast and usually easy to implement. However, they come with no theoretical guarantees on the quality of the solution, which makes it difficult to assess how the discovered subgraphs compare to an optimal solution, which in turn affects the data mining task at hand. For instance, in anomaly detection, solutions with low anomaly score lead to sub-optimal detection power. On the other end of the spectrum, there have been significant progress on these challenging graph problems in the theoretical computer science community. However, these techniques tend to be slow, difficult to implement, and they do not scale to the large datasets that are common nowadays. The goal of this dissertation is developing scalable algorithms with theoretical guarantees for various network analysis problems, where the underlying task is to find subgraphs with constraints. One unifying theme in the problems that we study is that our methods are scalable without sacrificing theoretical guarantees. We accomplish this combination of scalability and rigorous bounds by exploiting properties of the problems we are trying to optimize, decomposing or compressing the input graph to a manageable size, and parallelization. We consider problems on network analysis for both static and dynamic network models. And we illustrate the power of our methods in applications, such as public health, sensor data analysis, and event detection using social media data.

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

[pt] Neste trabalho propomos uma arquitetura para a verificação formal de protocolos e algoritmos distribuídos. Esta pode ser vista como uma camada mais abstrata sobre o processo tradicional de verificação formal, onde temos a especificação e propriedade a serem verificadas, o verificador e o resultado retornado por este. O objetivo é simplificar o processo de especificação e verificação formal de protocolos e algoritmos distribuídos através de um ambiente mais dedicado. A parte principal desta arquitetura é a linguagem de especificação LEP, que contém construções de domínio-especifíco para simplificar a especificação destes sistemas. Outra característica desta linguagem é separar as especificações da topologia e do protocolo propriamente dito. Acreditamos que esta separação é válida pois torna mais clara a intenção das partes e ainda permite, por exemplo, o reuso de uma topologia entre diferentes especificações de protocolos. Assim, visamos oferecer uma linguagem cujos exemplos de especificações devem se assemelhar às descrições de algoritmos encontradas nos livros didáticos. Além disso, de forma a se ter a entrada e a saída dos verificadores formais de forma a obter a saída no nível de abstração de LEP. / [en] In this work we propose an architecture for the formal verification of protocols and distribued algoritms. This can be see as a more abstract layer over the ordinary process of formal verification, where we have just the specification of the protocol and properties to be verified, and the formal tool. Our goal is to simplifu the specification and formal verification of protocols and distributed algorithms through a dedicated environment. The core of the architecture is its input specification language (Lep), which provides domain-specific constructions for simplifying the specification of those systems. With LEP the specification of the protocol and the specification of the topology to be referred to protocol are given separetely. We feel that this division improves the legibility of both and allows the reuse of the specification of a topology among distinct protocols. Using this approach we try to offer a language whose specifications should be similar to the descriptions of the algorithms found on the didactic books. Moreover, in order to have the input and output of the architecture compatible, we also propose a way of processing the result of the formal verification tool. Then we could have the result on the abstract level of LEP.

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-06-22T15:27:44Z No. of bitstreams: 1 Tese- Éfren Lopes de Souza.pdf: 7677745 bytes, checksum: 8fe25c4dfc5ccdc0ef44afb8837bd0e0 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-24T19:29:19Z (GMT) No. of bitstreams: 1 Tese- Éfren Lopes de Souza.pdf: 7677745 bytes, checksum: 8fe25c4dfc5ccdc0ef44afb8837bd0e0 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-24T20:11:47Z (GMT) No. of bitstreams: 1 Tese- Éfren Lopes de Souza.pdf: 7677745 bytes, checksum: 8fe25c4dfc5ccdc0ef44afb8837bd0e0 (MD5) / Made available in DSpace on 2015-06-24T20:11:47Z (GMT). No. of bitstreams: 1 Tese- Éfren Lopes de Souza.pdf: 7677745 bytes, checksum: 8fe25c4dfc5ccdc0ef44afb8837bd0e0 (MD5) Previous issue date: 2014-03-28 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Target tracking in Wireless Sensor Networks (WSNs) is an application in which the nodes cooperate to estimate the position of one or more objects of interest. In this context, the contributions of this work are fourfold. First, a survey the state-of-the-art about target tracking algorithms, in which we identified three formulations of tracking problem, and we classified them according to their characteristics. Furthermore, we divided the target tracking process in components to make the general understanding easier. Second, we propose and evaluate the PRATIQUE algorithm for tracking animals in forests. In this case, the nodes are organized into a grid to make feasible the use of sensor nodes in this kind of area in such a way that each cell of the grid is a region that can be occupied by the target. The algorithm estimates the cell where the target is, and uses predictions and hybrid clustering to reduce the communication cost and ensure the tracking accuracy. The results of the simulations show that prediction errors are approximately one cell. The third contribution is the TATI algorithm, this algorithm guides a tracker to approach the target. The sensor network is organized into faces to make the cooperation among the nodes easier, and reduce the path between the tracker and the target. The results show that energy consumption is reduced by 15%, and the tracker stays about 10m closer to the target, compared to the baseline. The fourth contribution is a scheme for performing localization and tracking tasks simultaneously in such a way that errors of range-based localization algorithms are reduced. This algorithm takes advantage of the messages sent to track the target to filter the noise in the distance estimation, reducing localization errors while tracking. The results show that the localization errors can be reduced by up to 70%. / Rastreamento de alvos em Redes de Sensores Sem Fio (RSSFs) é um tipo de aplicação em que os nós cooperam para estimar a posição de um ou mais objetos de interesse. Nesse contexto, este trabalho possui quatro contribuições. A primeira contribuição é um levantamento bibliográfico do estado-da-arte, em que identificamos três diferentes formulações de rastreamento e as classificamos de acordo com suas características. Além disso, dividimos o processo de rastreamento em componentes para facilitar o entendimento geral. A segunda contribuição é a elaboração e avaliação do algoritmo PRATIQUE para rastrear animais em florestas. Nesse caso, os nós são organizados em grade para viabilizar a utilização dos nós sensores nesse tipo de área, de forma que cada célula da grade é uma região que pode ser ocupada pelo alvo. O algoritmo estima a célula em que o alvo está, e usa previsão e um esquema híbrido de agrupamento para reduzir o custo de comunicação e garantir a precisão do rastreamento. Os resultados das simulações mostram que os erros de previsão são de aproximadamente uma célula. A terceira contribuição é o algoritmo TATI, esse algoritmo guia um objeto que visa alcançar o alvo. A rede é estruturada em faces para facilitar a cooperação entre os nós e reduzir o caminho entre o objeto guiado e o alvo. Os resultados mostram que o consumo de energia é reduzido em 15% e o objeto guiado fica cerca de 10m mais próximo do alvo, se comparado com a abordagem relacionada. A quarta contribuição é um esquema para executar as tarefas de localização e rastreamento simultaneamente para reduzir os erros dos algoritmos de localização baseados em alcance. As mensagens enviadas para rastrear o alvo são aproveitadas para filtrar os ruídos presentes nas estimativas de distância, reduzindo o erro de localização enquanto o rastreamento ocorre. Os resultados mostram que os erros de localização podem ser reduzidos em até 70%.

The subject of this thesis is the development of localization algorithms for target localization in wireless sensor networks using received signal strength (RSS) measurements or Quantized RSS (QRSS) measurements. In chapter 3 of the thesis, target localization using RSS measurements is investigated. Many existing works on RSS localization assumes that the shadowing components are uncorrelated. However, here, shadowing is assumed to be spatially correlated. It can be shown that localization accuracy can be improved with the consideration of correlation between pairs of RSS measurements. By linearizing the corresponding Maximum Likelihood (ML) objective function, a weighted least squares (WLS) algorithm is formulated to obtain the target location. An iterative technique based on Newtons method is utilized to give a solution. Numerical simulations show that the proposed algorithms achieves better performance than existing algorithms with reasonable complexity. In chapter 4, target localization with an unknown path loss model parameter is investigated. Most published work estimates location and these parameters jointly using iterative methods with a good initialization of path loss exponent (PLE). To avoid finding an initialization, a global optimization algorithm, particle swarm optimization (PSO) is employed to optimize the ML objective function. By combining PSO with a consensus algorithm, the centralized estimation problem is extended to a distributed version so that can be implemented in distributed WSN. Although suboptimal, the distributed approach is very suitable for implementation in real sensor networks, as it is scalable, robust against changing of network topology and requires only local communication. Numerical simulations show that the accuracy of centralized PSO can attain the Cramer Rao Lower Bound (CRLB). Also, as expected, there is some degradation in performance of the distributed PSO with respect to the centralized PSO. In chapter 5, a distributed gradient algorithm for RSS based target localization using only quantized data is proposed. The ML of the Quantized RSS is derived and PSO is used to provide an initial estimate for the gradient algorithm. A practical quantization threshold designer is presented for RSS data. To derive a distributed algorithm using only the quantized signal, the local estimate at each node is also quantized. The RSS measurements and the local estimate at each sensor node are quantized in different ways. By using a quantization elimination scheme, a quantized distributed gradient method is proposed. In the distributed algorithm, the quantization noise in the local estimate is gradually eliminated with each iteration. Simulations show that the performance of the centralized algorithm can reach the CRLB. The proposed distributed algorithm using a small number of bits can achieve the performance of the distributed gradient algorithm using unquantized data.

In this thesis we look at mobile agent solutions to black hole search and related problems. Mobile agents are computational entities that are autonomous, mobile, and can interact with their environment and each other. The black hole search problem is for a team of these agents to work together to map or explore a graph-like network environment where some elements of the network are dangerous to the agents. Most research into black hole search has focussed on finding a single dangerous node: a black hole. We look at the problem of finding multiple black holes and, in the case of dangerous graph exploration, multiple black links as well. We look at the dangerous graph exploration problem in the network model. The network model is based on a normal static computer network modelled as a simple graph. We give an optimal solution to the dangerous graph exploration problem using agents that start scattered on nodes throughout the network. We then make the problem more difficult by allowing an adversary to delete links during the execution of the algorithm and provide a solution using scattered agents. In the last decade or two, types of networks have emerged, such as ad hoc wireless networks, that are by their nature dynamic. These networks change quickly over time and can make distributed computations difficult. We look at black hole search in one type of dynamic network described by the subway model, which we base on urban subway systems. The model allows us to look at the cost of opportunistic movement by requiring the agents to move using carriers that follow routes among the network's sites, some of which are black holes. We show that there are basic limitations on any solution to black hole search in the subway model and prove lower bounds on any solution's complexity. We then provide two optimal solutions that differ in the agents' starting locations and how they communicate with one another. Our results provide a small window into the cost of deterministic distributed computing in networks that have dynamic elements, but which are not fully random.