A major issue in distributed wireless sensor networks (WSNs) is the design of efficient distributed algorithms for network-wide dissemination of information acquired by individual sensors, where each sensor, by itself, is unable to access enough data for reliable decision making. Without a centralized fusion center, network-wide reliable inferencing can be accomplished by recovering meaningful global statistics at each sensor through iterative inter-sensor message passing. In this dissertation, we first consider the problem of distributed estimation of an unknown deterministic scalar parameter (the target signal) in a WSN, where each sensor receives a single snapshot of the field. An iterative distributed least-squares (DLS) algorithm is investigated with and without the consideration of node failures. In particular, without sensor node failures it is shown that every instantiation of the DLS algorithm converges, i.e., consensus is reached among the sensors, with the limiting agreement value being the centralized least-squares estimate. With node failures during the iterative exchange process, the convergence of the DLS algorithm is still guaranteed; however, an error exists be- tween the limiting agreement value and the centralized least-squares estimate. In order to reduce this error, a modified DLS scheme, the M-DLS, is provided. The M-DLS algorithm involves an additional weight compensation step, in which a sensor performs a one-time weight compensation procedure whenever it detects the failure of a neighbor. Through analytical arguments and simulations, it is shown that the M-DLS algorithm leads to a smaller error than the DLS algorithm, where the magnitude of the improvement dependents on the network topology. We then investigate the case when the observation or sensing mode is only partially known at the corresponding nodes, perhaps, due to their limited sensing capabilities or other unpredictable physical factors. Specifically, it is assumed that the observation validity at a node switches stochastically between two modes, with mode I corresponding to the desired signal plus noise observation mode (a valid observation), and mode II corresponding to pure noise with no signal information (an invalid observation). With no prior information on the local sensing modes (valid or invalid), we introduce a learning-based distributed estimation procedure, the mixed detection-estimation (MDE) algorithm, based on closed-loop interactions between the iterative distributed mode learning and the target estimation. The online learning (or sensing mode detection) step re-assesses the validity of the local observations at each iteration, thus refining the ongoing estimation update process. The convergence of the MDE algorithm is established analytically, and the asymptotic performance analysis studies shows that, in the high signal-to-noise ratio (SNR) regime, the MDE estimation error converges to that of an ideal (centralized) estimator with perfect information about the node sensing modes. This is in contrast with the estimation performance of a naive average consensus based distributed estimator (with no mode learning), whose estimation error blows up with an increasing SNR.

As redes de sensores sem fio (RSSF) são uma tecnologia que ganhou muita importância nos últimos anos. Dentro das diversas aplicações para essas redes, o rastreamento de alvos é considerado essencial. Nessa aplicação, a RSSF deve determinar, de forma colaborativa, a trajetória de um ou mais alvos que se encontrem dentro de sua área de cobertura. O presente trabalho apresenta um algoritmo colaborativo baseado na fatoração multifrontal QR para estimação de trajetórias de alvos com RSSF. A solução proposta está inserida no âmbito da estimação por lotes, na qual os dados são coletados pelos sensores durante a aplicação e só no final é realizada a estimativa da trajetória do alvo. Uma vez coletados os dados, o problema pode ser modelado como um sistema de equações sobredeterminado Ax = b cuja característica principal é ser esparso. A solução desse sistema é dada mediante o método de mínimos quadrados, no qual o sistema é transformado num sistema triangular superior, que é solucionado mediante substituição inversa. A fatoração multifrontal QR é ideal neste contexto devido à natureza esparsa da matriz principal do sistema. A fatoração multifrontal QR utiliza um grafo denominado árvore de eliminação para dividir o processo de fatoração de uma matriz esparsa em fatorações densas de pequenas submatrizes denominadas matrizes frontais. Mapeando a árvore de eliminação na RSSF consegue-se que essas fatorações densas sejam executadas pelos nós sensoriais que detectaram o alvo durante seu trajeto pela rede. Dessa maneira, o algoritmo consegue realizar a fatoração da matriz principal do problema de forma colaborativa, dividindo essa tarefa em pequenas tarefas que os nós de sensoriais da rede possam realizar. / Wireless Sensor Networks (WSN) is a technology that have gained a lot of importance in the last few years. From all the possible applications for WSN, target tracking is considered essential. In this application, the WSN has to determine, in a collaborative way, the trajectory of one or more targets that are within the sensing area of the network. The aim of this document is to present a collaborative algorithm based on multifrontal QR factorization for the solution of the target trajectory estimation problem with WSN. This algorithm uses a batch estimation approach, which assumes that all sensing data are available before the estimation of the target trajectory. If all the observations of the target trajectory is available, the problem can be modeled as an overdetermined system of equations Ax = b where A is sparse. This system of equations is solved by least squares method. The multifrontal QR factorization uses a tree graph called elimination tree to reorganize the overall factorization of a sparse matrix into a sequence of partial factorizations of dense smaller matrices named frontal matrices. By mapping the elimination tree into the WSN, the sensor nodes that observed the target can factorize the frontal matrices. In this manner, the WSN factorizes the matrix A in a collaborative way, dividing the work in small tasks that the sensor nodes could execute.

As redes de sensores sem fio (RSSF) são uma tecnologia que ganhou muita importância nos últimos anos. Dentro das diversas aplicações para essas redes, o rastreamento de alvos é considerado essencial. Nessa aplicação, a RSSF deve determinar, de forma colaborativa, a trajetória de um ou mais alvos que se encontrem dentro de sua área de cobertura. O presente trabalho apresenta um algoritmo colaborativo baseado na fatoração multifrontal QR para estimação de trajetórias de alvos com RSSF. A solução proposta está inserida no âmbito da estimação por lotes, na qual os dados são coletados pelos sensores durante a aplicação e só no final é realizada a estimativa da trajetória do alvo. Uma vez coletados os dados, o problema pode ser modelado como um sistema de equações sobredeterminado Ax = b cuja característica principal é ser esparso. A solução desse sistema é dada mediante o método de mínimos quadrados, no qual o sistema é transformado num sistema triangular superior, que é solucionado mediante substituição inversa. A fatoração multifrontal QR é ideal neste contexto devido à natureza esparsa da matriz principal do sistema. A fatoração multifrontal QR utiliza um grafo denominado árvore de eliminação para dividir o processo de fatoração de uma matriz esparsa em fatorações densas de pequenas submatrizes denominadas matrizes frontais. Mapeando a árvore de eliminação na RSSF consegue-se que essas fatorações densas sejam executadas pelos nós sensoriais que detectaram o alvo durante seu trajeto pela rede. Dessa maneira, o algoritmo consegue realizar a fatoração da matriz principal do problema de forma colaborativa, dividindo essa tarefa em pequenas tarefas que os nós de sensoriais da rede possam realizar. / Wireless Sensor Networks (WSN) is a technology that have gained a lot of importance in the last few years. From all the possible applications for WSN, target tracking is considered essential. In this application, the WSN has to determine, in a collaborative way, the trajectory of one or more targets that are within the sensing area of the network. The aim of this document is to present a collaborative algorithm based on multifrontal QR factorization for the solution of the target trajectory estimation problem with WSN. This algorithm uses a batch estimation approach, which assumes that all sensing data are available before the estimation of the target trajectory. If all the observations of the target trajectory is available, the problem can be modeled as an overdetermined system of equations Ax = b where A is sparse. This system of equations is solved by least squares method. The multifrontal QR factorization uses a tree graph called elimination tree to reorganize the overall factorization of a sparse matrix into a sequence of partial factorizations of dense smaller matrices named frontal matrices. By mapping the elimination tree into the WSN, the sensor nodes that observed the target can factorize the frontal matrices. In this manner, the WSN factorizes the matrix A in a collaborative way, dividing the work in small tasks that the sensor nodes could execute.

The problem of distributed state estimation over a sensor network in which a set of nodes collaboratively estimates the state of continuous-time linear systems is considered. Distributed estimation strategies improve estimation and robustness of the sensors to environmental obstacles and sensor failures in a sensor network. In particular, this dissertation focuses on the benefits of weight adaptation of the interconnection gains in distributed Kalman filters, distributed unknown input observers, and distributed functional observers. To this end, an adaptation strategy is proposed with the adaptive laws derived via a Lyapunov-redesign approach. The justification for the gain adaptation stems from a desire to adapt the pairwise difference of estimates as a function of their agreement, thereby enforcing an interconnection-dependent gain. In the proposed scheme, an adaptive gain for each pairwise difference of the interconnection terms is used in order to address edge-dependent differences in the estimates. Accounting for node-specific differences, a special case of the scheme is presented where it uses a single adaptive gain in each node estimate and which uniformly penalizes all pairwise differences of estimates in the interconnection term. In the case of distributed Kalman filters, the filter gains can be designed either by standard Kalman or Luenberger observers to construct the adaptive distributed Kalman filter or adaptive distributed Luenberger observer. Stability of the schemes has been shown and it is independent of the graph topology and therefore the schemes are applicable to both directed and undirected graphs. The proposed algorithms offer a significant reduction in communication costs associated with information flow by the nodes compared to other distributed Kalman filters. Finally, numerical studies are presented to illustrate the performance and effectiveness of the proposed adaptive distributed Kalman filters, adaptive distributed unknown input observers, and adaptive distributed functional observers.

We design, analyze, and optimize distributed detection and estimation algorithms in a large, shared-channel, single-hop wireless sensor network (WSN). The fusion center (FC) is allocated a shared transmission channel to collect local decisions/estimates but cannot collect all of them because of limited energy, bandwidth, or time. We propose a strategy called reliability-based splitting algorithm that enables the FC to collect local decisions/estimates in descending order of their reliabilities through a shared collision channel. The algorithm divides the transmission channel into time frames and the sensor nodes into groups based on their observation reliabilities. Only nodes with a specified range of reliabilities compete for the channel using slotted ALOHA within each frame. Nodes with the most reliable decisions/estimates attempt transmission in the first frame; nodes with the next most reliable set of decisions/estimates attempt in the next frame; etc. The reliability-based splitting algorithm is applied in three scenarios: time-constrained distributed detection; sequential distributed detection; and time-constrained estimation. Performance measures of interest - including detection error probability, efficacy, asymptotic relative efficiency, and estimator variance - are derived. In addition, we propose and analyze algorithms that exploit information from the occurrence of collisions to improve the performance of both time-constrained distributed detection and sequential distributed detection.

abstract: Distributed estimation uses many inexpensive sensors to compose an accurate estimate of a given parameter. It is frequently implemented using wireless sensor networks. There have been several studies on optimizing power allocation in wireless sensor networks used for distributed estimation, the vast majority of which assume linear radio-frequency amplifiers. Linear amplifiers are inherently inefficient, so in this dissertation nonlinear amplifiers are examined to gain efficiency while operating distributed sensor networks. This research presents a method to boost efficiency by operating the amplifiers in the nonlinear region of operation. Operating amplifiers nonlinearly presents new challenges. First, nonlinear amplifier characteristics change across manufacturing process variation, temperature, operating voltage, and aging. Secondly, the equations conventionally used for estimators and performance expectations in linear amplify-and-forward systems fail. To compensate for the first challenge, predistortion is utilized not to linearize amplifiers but rather to force them to fit a common nonlinear limiting amplifier model close to the inherent amplifier performance. This minimizes the power impact and the training requirements for predistortion. Second, new estimators are required that account for transmitter nonlinearity. This research derives analytically and confirms via simulation new estimators and performance expectation equations for use in nonlinear distributed estimation. An additional complication when operating nonlinear amplifiers in a wireless environment is the influence of varied and potentially unknown channel gains. The impact of these varied gains and both measurement and channel noise sources on estimation performance are analyzed in this paper. Techniques for minimizing the estimate variance are developed. It is shown that optimizing transmitter power allocation to minimize estimate variance for the most-compressed parameter measurement is equivalent to the problem for linear sensors. Finally, a method for operating distributed estimation in a multipath environment is presented that is capable of developing robust estimates for a wide range of Rician K-factors. This dissertation demonstrates that implementing distributed estimation using nonlinear sensors can boost system efficiency and is compatible with existing techniques from the literature for boosting efficiency at the system level via sensor power allocation. Nonlinear transmitters work best when channel gains are known and channel noise and receiver noise levels are low. / Dissertation/Thesis / Ph.D. Electrical Engineering 2013

Cette thèse s’intéresse au problème d’estimation et d’optimisation distribuée dans les réseaux asynchrones, c’est à dire en n’utilisant que des communication locales et asynchrones. A partir de multiples applications allant de l’apprentissage automatique aux réseaux de capteurs sans-fils, nous concevons et analysons théoriquement de nouveaux algorithmes résolvant trois problèmes de nature très différentes : la propagation de la plus grande des valeurs initiales, l’estimation de leur moyenne et enfin l’optimisation distribuée. / This thesis addresses the distributed estimation and optimization of a global value of interest over a network using only local and asynchronous (sometimes wireless) communications. Motivated by many different applications ranging from cloud computing to wireless sensor networks via machine learning, we design new algorithms and theoretically study three problems of very different nature : the propagation of the maximal initial value, the estimation of their average and finally distributed optimization.

<p>The main theme of this dissertation is statistical estimation and information theory. There are three related topics including "distributed estimation", "an information geometric approach to ML estimation with incomplete data" and "joint identification and estimation in non-linear state space using Bayesian filters". The expectationmaximization (EM) algorithm, as an iterative estimation technique for dealing with incomplete data is the common bond that binds these three topics together.</p> <p>1. <em>Distributed estimation</em></p> <p>Distributed estimation involves the study of estimation theory in an information theoretic framework. This field concerns the following question: "What if the purpose of communications in a distributed environment is parameter estimation rather than source reconstruction?" The first part of this thesis is dedicated to designing low-complexity iterative algorithms for distributed estimation. The algorithm design, in this case, involves transmission of statistics via communication systems. Therefore, the first question raised is "whether the code rates in distributed estimation are different from those in conventional communications?" Surprisingly, under certain conditions, the answer is found to be negative. It is shown that for fixed parameters, the achievable rates coincide with rates in conventional distributed coding of correlated sources (i.e. Slepian-Wolf region). In order to prove the main theorem, we also devise a novel distributed binning scheme and a new theorem in Large deviation theory that are used for proving our distributed coding theorem. The proof of the converse is implemented by a generalized <em>Fano's inequality</em> for distributed estimation.</p> <p>Determination of the region of achievable rates for efficient estimation of a general source is an extremely difficult problem. This fact is the motivation for proving a theorem that provides a method for determining the region of achievable rates for a large class of sources with a convex mutual information with respect to the unknown parameters.</p> <p>With a given set of rates, an efficient implementation of universal coding schemes for distributed estimation based on the expectation maximization (EM) technique is presented. Since the correlation channel between the sources is assumed to be unknown at the joint decoder, previously proposed distributed coding schemes are not useful for this purpose. Therefore, LDPC-based coset-coding schemes are extended to the case where the correlation channel is unknown at the decoder. The basic idea is to implement a low-complexity version of the EM algorithm on a factor~graph that includes an LDPC decoding mechanism.</p> <p>2. <em>Information geometric approach to ML estimation with incomplete data</em></p> <p>The stochastic maximum likelihood estimation of parameters with incomplete data is cast in an information geometric framework. In this vein we develop the information geometric identification (IGID) algorithm, that provides an alternative iterative solution to the incomplete-data estimation problem. The algorithm consists of iterative alternating projections on two sets of probability distributions (PD); i.e., likelihood PD's and data empirical distributions. A Gaussian assumption on the source distribution permits a closed form lowcomplexity solution for these projections. The method is applicable to a wide range of problems; however the emphasis is on semi-blind identification of unknown parameters in a multi-input multi-output (MIMO) communications system.</p> <p>3. <em>Joint identification and estimation in non-linear state space using Bayesian filters</em></p> <p>There are situations in estimation where nonlinear state-space models where the model parameters or the model structure itself are not known a priori or are known only partially. In these scenarios, standard estimation algorithms like the extended Kalman Filter (EKF), which assume perfect knowledge of the model parameters, are not accurate. The nonlinear state estimation problem with possibly non-Gaussian noise in the presence of measurement model uncertainty is modeled as a special case of maximum likelihood estimation with incomplete data. The EM algorithm is used to solve the problem. The expectation (E) step is implemented by a particle filter that is initialized by a Monte-Carlo Markov chain algorithm. In the maximization (M) step, a nonlinear regression method, here using a mixture of Gaussians (MoG), is used to approximate (identify) the uncertain model equations. The proposed procedure is used to solve a highly nonlinear bearing-only tracking problem, as well as the sensor registration problem in a multi-sensor fusion scenario.</p> / Doctor of Philosophy (PhD)

Doctor of Philosophy / Department of Electrical and Computer Engineering / Balasubramaniam Natarajan / In recent years, there has been a rapid expansion in the development and use of low-power, low-cost wireless modules with sensing, computing, and communication functionality. A wireless sensor network (WSN) is a group of these devices networked together wirelessly. Wireless sensor networks have found widespread application in infrastructure, environmental, and human health monitoring, surveillance, and disaster management. While there are many interesting problems within the WSN framework, we address the challenge of energy availability in a WSN tasked with a cooperative objective. We develop approximation algorithms and execute an analysis of concave utility maximization in resource constrained systems. Our analysis motivates a unique algorithm which we apply to resource management in WSNs. We also investigate energy harvesting as a way of improving system lifetime. We then analyze the effect of using these limited and stochastically available communication resources on the convergence of decentralized optimization techniques. The main contributions of this research are: (1) new optimization formulations which explicitly consider the energy states of a WSN executing a cooperative task; (2) several analytical insights regarding the distributed optimization of resource constrained systems; (3) a varied set of algorithmic solutions, some novel to this work and others based on extensions of existing techniques; and (4) an analysis of the effect of using stochastic resources (e.g., energy harvesting) on the performance of decentralized optimization methods. Throughout this work, we apply our developments to distribution estimation and rate maximization. The simulation results obtained help to provide verification of algorithm performance. This research provides valuable intuition concerning the trade-offs between energy-conservation and system performance in WSNs.

This thesis is concerned with distributed estimation in a wireless sensor network (WSN) with analog transmission. For a scenario in which a large number of sensors are deployed under a limited bandwidth constraint, a semi-orthogonal multiple-access channelization (MAC) approach is proposed to provide transmission of observations from K sensors to a fusion center (FC) via N orthogonal channels, where K≥N. The proposed semi-orthogonal MAC can be implemented with either fixed sensor grouping or adaptive sensor grouping. The mean squared error (MSE) is adopted as the performance criterion and it is first studied under equal power allocation. The MSE can be expressed in terms of two indicators: the channel noise suppression capability and the observation noise suppression capability. The fixed version of the semi-orthogonal MAC is shown to have the same channel noise suppression capability and two times the observation noise suppression capability when compared to the orthogonal MAC under the same bandwidth resource. For the adaptive version, the performance improvement of the semi-orthogonal MAC over the orthogonal MAC is even more significant. In fact, the semi-orthogonal MAC with adaptive sensor grouping is shown to perform very close to that of the hybrid MAC, while requiring a much smaller amount of feedback. Another contribution of this thesis is an analysis of the behavior of the average MSE in terms of the number of sensors, namely the scaling law, under equal power allocation. It is shown that the proposed semi-orthogonal MAC with adaptive sensor grouping can achieve the optimal scaling law of the analog WSN studied in this thesis. Finally, improved power allocations for the proposed semi-orthogonal MAC are investigated. First, the improved power allocations in each sensor group for different scenarios are provided. Then an optimal solution of power allocation among sensor groups is obtained by the convex optimization theory, and shown to outperform equal power allocation. The issue of balancing between the performance improvement and extra feedback required by the improved power allocation is also thoroughly discussed.