Self-Calibration Methods for Uncontrolled Environments in Sensor Networks: A Reference Survey <s> Gossip Algorithms <s> Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model. <s> BIB001 </s> Self-Calibration Methods for Uncontrolled Environments in Sensor Networks: A Reference Survey <s> Gossip Algorithms <s> This paper considers the problem of blindly calibrating sensor response using routine sensor network measurements. We show that as long as the sensors slightly oversample the signals of interest, then unknown sensor gains can be perfectly recovered. Remarkably, neither a controlled stimulus nor a dense deployment is required. We also characterize necessary and sufficient conditions for the identification of unknown sensor offsets. Our results exploit incoherence conditions between the basis for the signals and the canonical or natural basis for the sensor measurements. Practical algorithms for gain and offset identification are proposed based on the singular value decomposition and standard least squares techniques. We investigate the robustness of the proposed algorithms to model mismatch and noise on both simulated data and on data from current sensor network deployments. <s> BIB002 </s> Self-Calibration Methods for Uncontrolled Environments in Sensor Networks: A Reference Survey <s> Gossip Algorithms <s> Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithm converges almost surely to a consensus. We prove that the random consensus value is, in expectation, the average of initial node measurements and that it can be made arbitrarily close to this value in mean squared error sense, under a balanced connectivity model and by trading off convergence speed with accuracy of the computation. We provide theoretical and numerical results on the mean square error performance, on the convergence rate and study the effect of the ldquomixing parameterrdquo on the convergence rate of the broadcast gossip algorithm. The results indicate that the mean squared error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithm to achieve a given distance to consensus through theoretical and numerical results. <s> BIB003 </s> Self-Calibration Methods for Uncontrolled Environments in Sensor Networks: A Reference Survey <s> Gossip Algorithms <s> We consider the problem of joint sensor calibration and target signature estimation using distributed measurements over a large-scale sensor network. Specifically, we develop a new Distributed Signature Learning and Node Calibration algorithm (D-SLANC) which simultaneously estimates source signal's signature and estimates calibration parameters local to each sensor node. We model the sensor network as a connected graph and make use of the gossip-based distributed consensus to update the estimates at each iteration of the algorithm. The algorithm is robust to link and node failures. We prove convergence of the algorithm to the centralized data pooling solution. We compare performance with the Cramer-Rao bound, and study the scaling performance of both the CR bound and the D-SLANC algorithm. The algorithm has application to classification, target signature estimation, and blind calibration in large sensor networks. <s> BIB004 </s> Self-Calibration Methods for Uncontrolled Environments in Sensor Networks: A Reference Survey <s> Gossip Algorithms <s> We introduce a control algorithm for automated calibration of sensor networks and fault compensation that reduces overall system error. Our approach uses a novel combination of models (for the spatial phenomena and sensor faults) and data-driven methods, and it works under novel conditions of dynamic sensor noise and bias in which the phenomenon of interest is both time- and space-variant. Our algorithm combines noise compensation using the EM (expectation-maximization) algorithm and a gossip-based protocol for sharing calibration information. We demonstrate its effectiveness in simulations that model real-world sensor fault scenarios. <s> BIB005
Average consensus gossiping BIB001 BIB003 is an asynchronous protocol where a node chosen uniformly at random wakes up, contacts a neighbor randomly within its connectivity radius, and exchanges a state variable to produce a computation update. The problem is having a network of n nodes that sample an area with initial values x(0)=[x 1 (0), ..., x n (0)] T and calculating the average of the entries of x(0),x = i x i (0) in a distributed manner. Although average gossip algorithms perform data fusion (e.g., achieving an average of the samples of the network), gossip algorithms allow distributing the computational burden and thus also apply to distributed calibration. Ramakrishnan et al. BIB004 presented a distributed signature learning and node calibration (D-SLANC) gossip algorithm for sensor calibration in WSNs. The algorithm relays on distributed measurements of sensors to estimate source signal's signature and to estimate calibration parameters using gossip-based distributed consensus. This is a special case of blind calibration in which there is no a priori knowledge of the signal subspace BIB002 . The mechanism can also be classified as micro-calibration, because although there is a network of sensors that collaborate to estimate the signal, each one of the sensors will have its own estimated calibration coefficients. In D-SLANC, N nodes measure a common signal of interest with different gains that are time-invariant. Each node n=1, ...N, has the following model: . . . where y i ∈R K is the noisy observation, i ∈R m is additive Gaussian noise with zero mean and covariance σ 2 I, and x∈R M is the common signal to be estimated. The whole network can be expressed as follows: The signature x and the calibration parameter β n are the unknown parameters to be estimated. Here, there are no groundtruth data, the sensor measurements act as y n , and the unknowns are both the calibration coefficients and the true sensing signal (signature estimation). Since the joint distribution of the unknowns is non-convex, D-SLANC splits the parameter space into two parts, the signature space and the calibration coefficients space, and then applies alternating minimization that consists of performing maximum likelihood (ML) estimation of one set while keeping the other one fixed. D-SLANC converges to a local maximum of the likelihood. To perform the signature estimation, a projected-gradient-based coordinate descent algorithm can be developed in which a distributed consensus algorithm forms the basis of each step of the coordinate algorithm BIB004 . Using the gradient descent algorithm, each node computes each one of the M components of the signature signal x. At each step of the algorithm it is necessary to calculate the gradient of the signature. This gradient is obtained using a distributed consensus mechanism. Ramakrishnan et al. BIB004 provided sufficient conditions to guarantee convergence of the coordinate descent for the exact consensus and with high probability for the approximate consensus algorithm. Finally, the local calibration factors are calculated given the current estimate of the signature. Buadhachain et al. BIB005 combined noise compensation using the EM (expectation-maximization) algorithm and a gossipbased protocol for sharing calibration information in a network of temperature sensors. The authors presented a state-space representation for the system and a control methodology that calibrates sensor nodes by modifying their output values given local sensors' outputs and the models.