Sound source localization with microphone arrays has received considerable attention as a means for the automated tracking of individuals in an enclosed space and as a necessary component of any general-purpose speech capture and automated camera pointing system. A novel computationally efficient method compared to traditional source localization techniques is proposed and is both theoretically and experimentally investigated in this research. This thesis first reviews the previous work in this area. The evolution of a new localization algorithm accompanied by an array structure for audio signal localization in three dimensional space is then presented. This method, which has similarities to the structure of the eye, consists of a novel hemispherical microphone array with microphones on the shell and one microphone in the center of the sphere. The hemispherical array provides such benefits as 3D coverage, simple signal processing and low computational complexity. The signal processing scheme utilizes parallel computation of a special and novel closeness function for each microphone direction on the shell. The closeness functions have output values that are linearly proportional to the spatial angular difference between the sound source direction and each of the shell microphone directions. Finally by choosing directions corresponding to the highest closeness function values and implementing linear weighted spatial averaging in those directions we estimate the sound source direction. The experimental tests validate the method with less than 3.10 of error in a small office room. Contrary to traditional algorithmic sound source localization techniques, the proposed method is based on parallel mathematical calculations in the time domain. Consequently, it can be easily implemented on a custom designed integrated circuit.

Sound source localization with microphone arrays has received considerable attention as a means for the automated tracking of individuals in an enclosed space and as a necessary component of any general-purpose speech capture and automated camera pointing system. A novel computationally efficient method compared to traditional source localization techniques is proposed and is both theoretically and experimentally investigated in this research. This thesis first reviews the previous work in this area. The evolution of a new localization algorithm accompanied by an array structure for audio signal localization in three dimensional space is then presented. This method, which has similarities to the structure of the eye, consists of a novel hemispherical microphone array with microphones on the shell and one microphone in the center of the sphere. The hemispherical array provides such benefits as 3D coverage, simple signal processing and low computational complexity. The signal processing scheme utilizes parallel computation of a special and novel closeness function for each microphone direction on the shell. The closeness functions have output values that are linearly proportional to the spatial angular difference between the sound source direction and each of the shell microphone directions. Finally by choosing directions corresponding to the highest closeness function values and implementing linear weighted spatial averaging in those directions we estimate the sound source direction. The experimental tests validate the method with less than 3.10 of error in a small office room. Contrary to traditional algorithmic sound source localization techniques, the proposed method is based on parallel mathematical calculations in the time domain. Consequently, it can be easily implemented on a custom designed integrated circuit.

Sound source localization with microphone arrays has received considerable attention as a means for the automated tracking of individuals in an enclosed space and as a necessary component of any general-purpose speech capture and automated camera pointing system. A novel computationally efficient method compared to traditional source localization techniques is proposed and is both theoretically and experimentally investigated in this research. This thesis first reviews the previous work in this area. The evolution of a new localization algorithm accompanied by an array structure for audio signal localization in three dimensional space is then presented. This method, which has similarities to the structure of the eye, consists of a novel hemispherical microphone array with microphones on the shell and one microphone in the center of the sphere. The hemispherical array provides such benefits as 3D coverage, simple signal processing and low computational complexity. The signal processing scheme utilizes parallel computation of a special and novel closeness function for each microphone direction on the shell. The closeness functions have output values that are linearly proportional to the spatial angular difference between the sound source direction and each of the shell microphone directions. Finally by choosing directions corresponding to the highest closeness function values and implementing linear weighted spatial averaging in those directions we estimate the sound source direction. The experimental tests validate the method with less than 3.10 of error in a small office room. Contrary to traditional algorithmic sound source localization techniques, the proposed method is based on parallel mathematical calculations in the time domain. Consequently, it can be easily implemented on a custom designed integrated circuit. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

In this thesis, a complete localization system using asynchronous time difference of arrival (A-TDOA) technique has been thoroughly studied from concept to implementation. The work spans from a proposal of a new A-TDOA system deployment and modeling, through a derivation of the achievable estimation bound, to estimation algorithms development, to a hardware realization, and ultimately to measurements conducted in realistic radio environments. The research begins with a new deployment of an A-TDOA localization system. Compared to the conventional time of arrival (TOA) and time difference of arrival (TDOA) systems, it does not require clock synchronization within the network, which enables a flexible and fast deployment. When deployed in the simplest form, it can effectively reduce system complexity and cost, whereas if all anchor nodes are equipped with full transmit and receive capability, the A-TDOA system can achieve superior performance using a novel receiver re-selection technique. Determining the physical position of a target node in a noisy environment is critical. In this thesis, two novel algorithms, namely, a two-step and a constrained least squares (CLS) algorithms, are proposed offering excellent accuracy and the best trade-off between complexity and precision respectively. The two-step algorithm exploits the advantages of the semi-definite programming (SDP) and the Taylor method, i.e., global convergence and high precision, to achieve superior performance. The CLS algorithm significantly reduces the computation complexity while achieving good accuracy. Despite extensive research efforts on ranging and localization modeling and simulation, knowledge about practical implementations is limited. For the first time, a complete prototype based on A-TDOA technique is implemented in hardware. All sub-systems are developed from scratch and undergone significant modifications for improved reliability. The design objective is low cost and low complexity, and therefore a non-coherent receiver architecture was adopted. The target node design is based on receive and re-transmit technique and is prototyped in analog domain to avoid clock offset and skews. The implemented system has been extensively tested in an outdoor and indoor radio environments. The accuracy obtained are 20.7 cm and 15.2 cm respectively. Comparison with the literature published up to date proves the excellent quality of the design and implementation. To better understand the localization accuracy, the error sources due to thermal noise, hardware limitation, radio propagation channel and clock jitter are identified and investigated. Mitigation methods are proposed to reduce errors. / Graduate

This thesis presents contributions to node localization in mobile sensor networks. Considering the importance of localization algorithms in identifying the location of an event in order to better determine the action to be taken by the user, a new localization algorithm to operate in mobile networks was designed, assuming an uncontrollable movement of the nodes. This algorithm, which we call CentroidM, has the Centroid method as a stand. Positive features of the Centroid algorithm were kept while their limitations due to the dynamic characteristcs of the network movement were mitigated. Besides the concern regarding the accuracy of the method, the power consumption of the algorithm was addressed too. The design of an dedicated integrated circuit to deal with the localization task in a mobile network is justified given the high activity of such a subsystem in the given scenario. This way, the focus of this Thesis relies on a low power localization algorithm for mobile networks, with characteristics to allow raising calculated coordinates accuracy in both static and mobile scenarios. The results show that the CentroidM is 30% more accurate than the Centroid on a static scenario, and 40% when we consider a node movement without actuators. These benefits have some computational overhead, increasing 2.76 times the time spent by the CentroidM to run a localization process. However, simulation results showed it is possible to remove such overhead and still keep the achieved estimation gains near 10%. The implementation of the localization method was accomplished through an integrated circuit, which reduced the energy expended during the computation of the coordinates by an order of magnitude when comparing with the execution of the algorithm in a low power commercial microcontroller. / Esta Tese apresenta contribuições ao processo de localização de nodos em redes de sensores móveis. Considerando a importância de algoritmos de localização em uma rede para identificar o local do evento sob estudo e determinar a ação a ser tomada pelo usuário, é desenvolvido um novo algoritmo de localização para operar em redes de sensores móveis, focando o aspecto da mobilidade não controlada dos nodos. Este algoritmo, ao qual denominamos CentroidM, teve como base de desenvolvimento o método Centroid. Foram mantidas as características positivas do Centroid e exploradas as limitações do método para a sua execução em uma rede que considera o movimento. Além do objetivo em reduzir o erro das estimativas de posicionamento calculadas pelo algoritmo, o consumo de potência do método apresentado neste trabalho é enfatizado. O projeto de um circuito integrado dedicado que desempenhe o processo de localização em uma rede móvel é justificado pela intensa utilização de tal subsistema neste tipo de rede, além dos benefícios que um hardware dedicado traz face à redução da energia gasta nesta operação. Desta forma, o foco deste trabalho recai sobre um algoritmo de localização para redes móveis e as características desta abordagem que permitiram aumentar a precisão das estimativas de posicionamento tanto em um cenário com ausência de movimento dos nodos, quanto em outro onde o aspecto da mobilidade sem atuadores foi considerada. Os resultados obtidos nesta Tese demostraram que o CentroidM é 30% mais preciso que o Centroid para um cenário estático e 40% considerando a mobilidade da rede. O ganho alcançado em precisão teve um custo computacional que elevou em 2, 76 vezes o tempo gasto pelo CentroidM para realizar um procedimento de localização. Contudo, os resultados de simulação mostraram que é possível eliminar a sobrecarga computacional e ainda assim atingir ganhos em precisão próximos a 10%. O desenvolvimento do método de localização é complementado pela sua implementação em um circuito integrado dedicado, reduzindo a energia gasta no processo de estimativa da posição em uma ordem da magnitude face à execução do algoritmo em um microcontrolador comercial de baixo consumo.

Context: Wireless Sensor Networks (WSN) are applied to collect information by distributed sensor nodes (anchors) that are usually in fixed positions. Localization (estimating the location of objects) of moving sensors, devices or people which recognizes the location’s information of a moving object is one of the essential WSN services and main requirement. To find the location of a moving object, some of algorithms are based on RSSI (Received Signal Strength Indication). Since very accurate localization is not always feasible (cost, complexity and energy issues) requirement, RSSI-based method is a solution. This method has two specific features: it does not require extra hardware (cost and energy aspects) and theoretically RSSI is a function of distance. Objectives: In this thesis firstly, we develop an RSSI-based localization algorithm (server side application) to find the position of a moving object (target node) in different situations. These situations are defined in different experiments so that we observe and compare the results (finding accurate positioning). Secondly, since RSSI characteristic is highly related to the environment that an experiment is done in (moving, obstacles, temperature, humidity …) the importance and contribution of “environmental condition” in the empirical papers is studied. Methods: The first method which is a common LR (Literature Review) is carried out to find out general information about localization algorithms in (WSN) with focus on the RSSI-based method. This LR is based on papers and literature that are prepared by the collaborating company, the supervisor and also ad-hoc search in scientific IEEE database. By this method as well as relevant information, theoretical algorithm (mathematical function) and different effective parameters of the RSSI-based algorithm are defined. The second method is experimentation that is based on development of the mentioned algorithm (since experiment is usually performed in development, evaluation and problem solving research). Now, because we want to compare and evaluate results of the experiments with respect to environmental condition effect, the third method starts. The third method is SMS (Systematic mapping Study) that essentially focuses on the contribution of “environmental condition” effect in the empirical papers. Results: The results of 30 experiments and their analyses show a highly correlation between the RSSI values and environmental conditions. Also, the results of the experiments indicate that a direct signal path between a target node and anchors can improve the localization’s accuracy. Finally, the experiments’ results present that the target node’s antenna type has a clear effect on the RSSI values and in consequence distance measurement error. Our findings in the mapping study reveal that although there are a lot of studies about accuracy requirement in the context of the RSSI-based localization, there is a lack of research on the other localization requirements such as performance, reliability and stability. Also, there are a few studies which considered the RSSI localization in a real world condition. Conclusion: This thesis studies various localization methods and techniques in WSNs. Then, the thesis focuses on the RSSI-based localization by implementing one algorithm and analyzing the experiments’ results. In our experiments, we mostly focus on environmental parameters that affect localization’s accuracy. Moreover, we indicate some areas of research in this context which need more studies.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / Applications that use sensor networks depends on knowing which position where each node is arranged in a particular geographic area. For this, there are algorithms that perform location calculations to estimate the exact position of each node. These algorithms use a different techniques and metrics to make it, for example: the measure of intensity of signal transmission between two nodes. In a sensor network with high density, it becomes infeasible to manually configuring each node positioning. To optimize this task, was developed different types of localization algorithms, with application in several areas, such as tracking, routing protocols, network density control, self organizing, monitoring remote areas, precision agriculture, among others. The basis for localization algorithms is to have a number of reference points, where from these, is calculated the position of each node. A network of sensors with a greater number of reference points, one can consider a network with higher accuracy for calculating the position of its nodes. This is due to being closer to the reference points. However, may result in a higher processing, thereby having a higher energy consumption. Developing a location algorithm with fewer reference points is not a trivial problem. This, because will increase the distance between the node and the reference point and may thereby inserting errors in the measurement of the criteria for the calculation of positioning. For calculation purposes, there are two types of algorithms, algorithms for centralized processing and distributed processing algorithms. Each with its advantages and disadvantages that will be discussed in this paper. The location algorithm is based on a calculation according to data coordinates in a coordinate system, which is raised according to the technique used to denote the distance between the sensor node and the reference points. The importance of knowing the location of each node, there is the need to know exactly where a particular event is occurring. For example, a forest that occupies a large geographic area is to principles of fire at different locations. / Aplicações que utilizam redes de sensores dependem de saber qual a posição onde cada nó encontra-se disposto em uma determinada área geográfica. Para isto, existem algoritmos de localização que efetuam cálculos a fim de estimar a posição exata de cada nó. Estes algoritmos utilizam-se de diferentes técnicas e medidas para realizar tal tarefa, como por exemplo: a medida de intensidade de sinal de transmissão entre dois nós. Em uma rede de sensores com alta densidade, torna-se inviável a configuração manual do posicionamento de cada nó. Para otimizar esta tarefa, foram desenvolvidos diferentes tipos de algoritmos de localização, com aplicação nas mais diversas áreas, como: rastreamento, protocolos de roteamento, controle de densidade da rede, auto organização, monitoramento de áreas remotas, agricultura de precisão, entre outros. A base para algoritmos de localização é possuir um número de pontos de referência, onde a partir destes, será calculado a posição de cada nó. Uma rede de sensores com maior número de pontos de referência, pode-se considerar uma rede com maior precisão para o cálculo de posição de seus nós. Isso, é devido aos nós estarem mais próximos aos pontos de referência. Porém, pode acarretar em um maior processamento, assim, tendo um maior consumo de energia. Projetar um algoritmo de localização com um menor número de pontos de referência não é um problema trivial. Isto porque irá aumentar a distância entre o nó e o ponto de referência, podendo desta forma, inserir erros na medição dos critérios para o cálculo de posicionamento. Para fins de cálculo, existem dois tipos de algoritmos, os algoritmos de processamento centralizado e os algoritmos de processamento distribuído. Cada um com suas vantagens e desvantagens que serão abordadas no decorrer deste trabalho. O algoritmo de localização baseia-se em um cálculo de acordo com as coordenadas em um dado sistema de coordenadas, que será levantada de acordo com a técnica utilizada para estipular a distância entre o nó sensor e os pontos de referência. A importância de conhecer a localização de cada nó, dá-se a necessidade de saber exatamente onde está ocorrendo determinado evento. Por exemplo, uma floresta que ocupa uma grande área geográfica está com princípios de incêndio em diferentes locais. É preciso avaliar quais são estes locais e qual significa um maior risco de destruição, para isto, é preciso saber a posição exata de cada local e assim tomar as devidas decisões de qual princípio deverá ser combatido primeiro. Neste caso, os nós sensores estariam estáticos, porém seria uma rede de sensores de alta densidade para cobrir uma área significativa de floresta. Pode-se também ter uma rede de sensores com nós móveis, onde então o objetivo é realizar o rastreamento da locomoção destes nós. A partir deste rastreamento, pode-se identificar o comportamento de um rebanho de animais por exemplo, verificando seu deslocamento, velocidade e direção. Com estes dados de comportamento, dependendo do animal pode-se deduzir se ele está doente, alimentando-se ou até mesmo morto se imóvel por um longo período de tempo.

Networks with hundreds of ad hoc nodes equipped with communication and position finding abilities are conceivable with recent advancements in technology. Methods are presented in this thesis to assess the communicative capabilities and node position estimation of mobile ad hoc networks. Specifically, we investigate techniques for providing communication and geolocation with specific characteristics in wireless ad hoc networks. The material presented in this thesis, communication and geolocation, may initially seem a collection of disconnected topics related only distantly under the banner of ad hoc networks. However, systems currently in development combining these techniques into single integrated systems. In this thesis first, we investigate the effect of multilayer interaction, including fading and path loss, on ad hoc routing protocol performance, and present a procedure for deploying an ad hoc network based on extensive simulations. Our first goal is to test the routing protocols with parameters that can be used to characterize the environment in which they might be deployed. Second, we analyze the location discovery problem in ad hoc networks and propose a fully distributed, infrastructure-free positioning algorithm that does not rely on the Global Positioning System (GPS). The algorithm uses the approximate distances between the nodes to build a relative coordinate system in which the node positions are computed in three-dimensions. However, in reconstructing three-dimensional positions from approximate distances, we need to consider error threshold, graph connectivity, and graph rigidity. We also statistically evaluate the location discovery procedure with respect to a number of parameters, such as error propagation and the relative positions of the nodes.

This thesis deals with regularization parameter selection methods in the context of Tikhonov-type regularization with Poisson distributed data, in particular the reconstruction of images, as well as with the identification of the volatility surface from observed option prices. In Part I we examine the choice of the regularization parameter when reconstructing an image, which is disturbed by Poisson noise, with Tikhonov-type regularization. This type of regularization is a generalization of the classical Tikhonov regularization in the Banach space setting and often called variational regularization. After a general consideration of Tikhonov-type regularization for data corrupted by Poisson noise, we examine the methods for choosing the regularization parameter numerically on the basis of two test images and real PET data. In Part II we consider the estimation of the volatility function from observed call option prices with the explicit formula which has been derived by Dupire using the Black-Scholes partial differential equation. The option prices are only available as discrete noisy observations so that the main difficulty is the ill-posedness of the numerical differentiation. Finite difference schemes, as regularization by discretization of the inverse and ill-posed problem, do not overcome these difficulties when they are used to evaluate the partial derivatives. Therefore we construct an alternative algorithm based on the weak formulation of the dual Black-Scholes partial differential equation and evaluate the performance of the finite difference schemes and the new algorithm for synthetic and real option prices.

This thesis deals with regularization parameter selection methods in the context of Tikhonov-type regularization with Poisson distributed data, in particular the reconstruction of images, as well as with the identification of the volatility surface from observed option prices. In Part I we examine the choice of the regularization parameter when reconstructing an image, which is disturbed by Poisson noise, with Tikhonov-type regularization. This type of regularization is a generalization of the classical Tikhonov regularization in the Banach space setting and often called variational regularization. After a general consideration of Tikhonov-type regularization for data corrupted by Poisson noise, we examine the methods for choosing the regularization parameter numerically on the basis of two test images and real PET data. In Part II we consider the estimation of the volatility function from observed call option prices with the explicit formula which has been derived by Dupire using the Black-Scholes partial differential equation. The option prices are only available as discrete noisy observations so that the main difficulty is the ill-posedness of the numerical differentiation. Finite difference schemes, as regularization by discretization of the inverse and ill-posed problem, do not overcome these difficulties when they are used to evaluate the partial derivatives. Therefore we construct an alternative algorithm based on the weak formulation of the dual Black-Scholes partial differential equation and evaluate the performance of the finite difference schemes and the new algorithm for synthetic and real option prices.