Time and Energy Complexity of Distributed Computation of a Class of Functions in Wireless Sensor Networks

We consider a scenario in which a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing a function of the measurements and communicating it to an operator station. We restrict ourselves to the class of type-threshold functions (as defined in the work of Giridhar and Kumar, 2005), of which max, min, and indicator functions are important examples: our discussions are couched in terms of the max function. We view the problem as one of message-passing distributed computation over a geometric random graph. The network is assumed to be synchronous, and the sensors synchronously measure values and then collaborate to compute and deliver the function computed with these values to the operator station. Computation algorithms differ in (1) the communication topology assumed and (2) the messages that the nodes need to exchange in order to carry out the computation. The focus of our paper is to establish (in probability) scaling laws for the time and energy complexity of the distributed function computation over random wireless networks, under the assumption of centralized contention-free scheduling of packet transmissions. First, without any constraint on the computation algorithm, we establish scaling laws for the computation time and energy expenditure for one-time maximum computation. We show that for an optimal algorithm, the computation time and energy expenditure scale, respectively, as Theta(radicn/log n) and Theta(n) asymptotically as the number of sensors n rarr infin. Second, we analyze the performance of three specific computation algorithms that may be used in specific practical situations, namely, the tree algorithm, multihop transmission, and the Ripple algorithm (a type of gossip algorithm), and obtain scaling laws for the computation time and energy expenditure as n rarr infin. In particular, we show that the computation time for these algorithms scales as Theta(radicn/lo- g n), Theta(n), and Theta(radicn log n), respectively, whereas the energy expended scales as , Theta(n), Theta(radicn/log n), and Theta(radicn log n), respectively. Finally, simulation results are provided to show that our analysis indeed captures the correct scaling. The simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized optimal scheduler, and hence, our results can be viewed as providing bounds for the performance with practical distributed schedulers.

Selective attention in a synchronising bushcricket: physiology, behaviour and ecology

Synchronising bushcricket males achieve synchrony by delaying their chirps in response to calling neighbours. In multi-male choruses, males that delay chirps in response to all their neighbours would remain silent most of the time and be unable to attract mates. This problem could be overcome if the afferent auditory system exhibited selective attention, and thus a male interacted only with a subset of neighbours. We investigated whether individuals of the bushcricket genus Mecopoda restricted their attention to louder chirps neurophysiologically, behaviourally and through spacing. We found that louder leading chirps were preferentially represented in the omega neuron but the representation of softer following chirps was not completely abolished. Following chirps that were 20 dB louder than leading chirps were better represented than leading chirps. During acoustic interactions, males synchronised with leading chirps even when the following chirps were 20 dB louder. Males did not restrict their attention to louder chirps during interactions but were affected by all chirps above a particular threshold. In the field, we found that males on average had only one or two neighbours whose calls were above this threshold. Selective attention is thus achieved in this bushcricket through spacing rather than neurophysiological filtering of softer signals.

A Simple Instrumentation Calibration Technique for Electrical Impedance Tomography (EIT) Using A 16-Electrode Phantom

A simple analog instrumentation for Electrical Impedance Tomography is developed and calibrated using the practical phantoms. A constant current injector consisting of a modified Howland voltage controlled current source fed by a voltage controlled oscillator is developed to inject a constant current to the phantom boundary. An instrumentation amplifier, 50 Hz notch filter and a narrow band pass filter are developed and used for signal conditioning. Practical biological phantoms are developed and the forward problem is studied to calibrate the EIT-instrumentation. An array of sixteen stainless steel electrodes is developed and placed inside the phantom tank filled with KCl solution. 1 mA, 50 kHz sinusoidal current is injected at the phantom boundary using adjacent current injection protocol. The differential potentials developed at the voltage electrodes are measured for sixteen current injections. Differential voltage signal is passed through an instrumentation amplifier and a filtering block and measured by a digital multimeter. A forward solver is developed using Finite Element Method in MATLAB7.0 for solving the EIT governing equation. Differential potentials are numerically calculated using the forward solver with a simulated current and bathing solution conductivity. Measured potential data is compared with the differential potentials calculated for calibrating the instrumentation to acquire the voltage data suitable for better image reconstruction.

Selective attention in a synchronising bushcricket: physiology, behaviour and ecology

Synchronising bushcricket males achieve synchrony by delaying their chirps in response to calling neighbours. In multi-male choruses, males that delay chirps in response to all their neighbours would remain silent most of the time and be unable to attract mates. This problem could be overcome if the afferent auditory system exhibited selective attention, and thus a male interacted only with a subset of neighbours. We investigated whether individuals of the bushcricket genus Mecopoda restricted their attention to louder chirps neurophysiologically, behaviourally and through spacing. We found that louder leading chirps were preferentially represented in the omega neuron but the representation of softer following chirps was not completely abolished. Following chirps that were 20 dB louder than leading chirps were better represented than leading chirps. During acoustic interactions, males synchronised with leading chirps even when the following chirps were 20 dB louder. Males did not restrict their attention to louder chirps during interactions but were affected by all chirps above a particular threshold. In the field, we found that males on average had only one or two neighbours whose calls were above this threshold. Selective attention is thus achieved in this bushcricket through spacing rather than neurophysiological filtering of softer signals.

Understanding Connectivity between Groundwater Chemistry Data and Geological Stratigraphy via 3D Sub-surface Visualization and Analysis

This paper describes the 3D Water Chemistry Atlas - an open source, Web-based system that enables the three-dimensional (3D) sub-surface visualization of ground water monitoring data, overlaid on the local geological model. Following a review of existing technologies, the system adopts Cesium (an open source Web-based 3D mapping and visualization interface) together with a PostGreSQL/PostGIS database, for the technical architecture. In addition a range of the search, filtering, browse and analysis tools were developed that enable users to interactively explore the groundwater monitoring data and interpret it spatially and temporally relative to the local geological formations and aquifers via the Cesium interface. The result is an integrated 3D visualization system that enables environmental managers and regulators to assess groundwater conditions, identify inconsistencies in the data, manage impacts and risks and make more informed decisions about activities such as coal seam gas extraction, waste water extraction and re-use.

Quality of support for multicasting over mobile ad-hoc networks

An ad hoc network is composed of mobile nodes without any infrastructure. Recent trends in applications of mobile ad hoc networks rely on increased group oriented services. Hence multicast support is critical for ad hoc networks. We also need to provide service differentiation schemes for different group of users. An efficient application layer multicast (APPMULTICAST) solution suitable for low mobility applications in MANET environment has been proposed in [10]. In this paper, we present an improved application layer multicast solution suitable for medium mobility applications in MANET environment. We define multicast groups with low priority and high priority and incorporate a two level service differentiation scheme. We use network layer support to build the overlay topology closer to the actual network topology. We try to maximize Packet Delivery Ratio. Through simulations we show that the control overhead for our algorithm is within acceptable limit and it achieves acceptable Packet Delivery Ratio for medium mobility applications.

Delay optimal control algorithm for a multiaccess fading channel with peak power constraint

We consider an optimal power and rate scheduling problem for a multiaccess fading wireless channel with the objective of minimising a weighted sum of mean packet transmission delay subject to a peak power constraint. The base station acts as a controller which, depending upon the buffer lengths and the channel state of each user, allocates transmission rate and power to individual users. We assume perfect channel state information at the transmitter and the receiver. We also assume a Markov model for the fading and packet arrival processes. The policy obtained represents a form of Indexability.

Maan magneettikentän dipolimallin toimivuus inklinaatiojakauman perusteella

The magnetic field of the Earth is 99 % of the internal origin and generated in the outer liquid core by the dynamo principle. In the 19th century, Carl Friedrich Gauss proved that the field can be described by a sum of spherical harmonic terms. Presently, this theory is the basis of e.g. IGRF models (International Geomagnetic Reference Field), which are the most accurate description available for the geomagnetic field. In average, dipole forms 3/4 and non-dipolar terms 1/4 of the instantaneous field, but the temporal mean of the field is assumed to be a pure geocentric axial dipolar field. The validity of this GAD (Geocentric Axial Dipole) hypothesis has been estimated by using several methods. In this work, the testing rests on the frequency dependence of inclination with respect to latitude. Each combination of dipole (GAD), quadrupole (G2) and octupole (G3) produces a distinct inclination distribution. These theoretical distributions have been compared with those calculated from empirical observations from different continents, and last, from the entire globe. Only data from Precambrian rocks (over 542 million years old) has been used in this work. The basic assumption is that during the long-term course of drifting continents, the globe is sampled adequately. There were 2823 observations altogether in the paleomagnetic database of the University of Helsinki. The effect of the quality of observations, as well as the age and rocktype, has been tested. For comparison between theoretical and empirical distributions, chi-square testing has been applied. In addition, spatiotemporal binning has effectively been used to remove the errors caused by multiple observations. The modelling from igneous rock data tells that the average magnetic field of the Earth is best described by a combination of a geocentric dipole and a very weak octupole (less than 10 % of GAD). Filtering and binning gave distributions a more GAD-like appearance, but deviation from GAD increased as a function of the age of rocks. The distribution calculated from so called keypoles, the most reliable determinations, behaves almost like GAD, having a zero quadrupole and an octupole 1 % of GAD. In no earlier study, past-400-Ma rocks have given a result so close to GAD, but low inclinations have been prominent especially in the sedimentary data. Despite these results, a greater deal of high-quality data and a proof of the long-term randomness of the Earth's continental motions are needed to make sure the dipole model holds true.

Chain of excitation spot generation by aperture engineering

An optical technique is proposed for obtaining multiple excitation spots. Phase-matched counter propagating extended depth-of-focus fields were superimposed along the optical axis for generating multiple localized excitation spots. Moreover, the filtering effect due to the optical mask increases the lateral resolution. Proposed technique introduces the concept of simultaneous multiplane excitation and improves three-dimensional resolution. (C) 2010 American Institute of Physics.

Self-regularized pseudo time-marching schemes for structural system identification with static measurements

We explore the application of pseudo time marching schemes, involving either deterministic integration or stochastic filtering, to solve the inverse problem of parameter identification of large dimensional structural systems from partial and noisy measurements of strictly static response. Solutions of such non-linear inverse problems could provide useful local stiffness variations and do not have to confront modeling uncertainties in damping, an important, yet inadequately understood, aspect in dynamic system identification problems. The usual method of least-square solution is through a regularized Gauss-Newton method (GNM) whose results are known to be sensitively dependent on the regularization parameter and data noise intensity. Finite time,recursive integration of the pseudo-dynamical GNM (PD-GNM) update equation addresses the major numerical difficulty associated with the near-zero singular values of the linearized operator and gives results that are not sensitive to the time step of integration. Therefore, we also propose a pseudo-dynamic stochastic filtering approach for the same problem using a parsimonious representation of states and specifically solve the linearized filtering equations through a pseudo-dynamic ensemble Kalman filter (PD-EnKF). For multiple sets of measurements involving various load cases, we expedite the speed of thePD-EnKF by proposing an inner iteration within every time step. Results using the pseudo-dynamic strategy obtained through PD-EnKF and recursive integration are compared with those from the conventional GNM, which prove that the PD-EnKF is the best performer showing little sensitivity to process noise covariance and yielding reconstructions with less artifacts even when the ensemble size is small.

Self-regularized pseudo time-marching schemes for structural system identification with static measurements

We explore the application of pseudo time marching schemes, involving either deterministic integration or stochastic filtering, to solve the inverse problem of parameter identification of large dimensional structural systems from partial and noisy measurements of strictly static response. Solutions of such non-linear inverse problems could provide useful local stiffness variations and do not have to confront modeling uncertainties in damping, an important, yet inadequately understood, aspect in dynamic system identification problems. The usual method of least-square solution is through a regularized Gauss-Newton method (GNM) whose results are known to be sensitively dependent on the regularization parameter and data noise intensity. Finite time, recursive integration of the pseudo-dynamical GNM (PD-GNM) update equation addresses the major numerical difficulty associated with the near-zero singular values of the linearized operator and gives results that are not sensitive to the time step of integration. Therefore, we also propose a pseudo-dynamic stochastic filtering approach for the same problem using a parsimonious representation of states and specifically solve the linearized filtering equations through apseudo-dynamic ensemble Kalman filter (PD-EnKF). For multiple sets ofmeasurements involving various load cases, we expedite the speed of the PD-EnKF by proposing an inner iteration within every time step. Results using the pseudo-dynamic strategy obtained through PD-EnKF and recursive integration are compared with those from the conventional GNM, which prove that the PD-EnKF is the best performer showing little sensitivity to process noise covariance and yielding reconstructions with less artifacts even when the ensemble size is small. Copyright (C) 2009 John Wiley & Sons, Ltd.

A Wavelet based Teager Energy Operator for Spike Detection in Microelectrode Array Recordings

Spike detection in neural recordings is the initial step in the creation of brain machine interfaces. The Teager energy operator (TEO) treats a spike as an increase in the `local' energy and detects this increase. The performance of TEO in detecting action potential spikes suffers due to its sensitivity to the frequency of spikes in the presence of noise which is present in microelectrode array (MEA) recordings. The multiresolution TEO (mTEO) method overcomes this shortcoming of the TEO by tuning the parameter k to an optimal value m so as to match to frequency of the spike. In this paper, we present an algorithm for the mTEO using the multiresolution structure of wavelets along with inbuilt lowpass filtering of the subband signals. The algorithm is efficient and can be implemented for real-time processing of neural signals for spike detection. The performance of the algorithm is tested on a simulated neural signal with 10 spike templates obtained from [14]. The background noise is modeled as a colored Gaussian random process. Using the noise standard deviation and autocorrelation functions obtained from recorded data, background noise was simulated by an autoregressive (AR(5)) filter. The simulations show a spike detection accuracy of 90%and above with less than 5% false positives at an SNR of 2.35 dB as compared to 80% accuracy and 10% false positives reported [6] on simulated neural signals.

Helical FDK Algorithms With No Backprojection Weight

In this paper, we present two new filtered backprojection (FBP) type algorithms for cylindrical detector helical cone-beam geometry with no position dependent backprojection weight. The algorithms are extension of the recent exact Hilbert filtering based 2D divergent beam reconstruction with no backprojection weight to the FDK type algorithm for reconstruction in 3D helical trajectory cone-beam tomography. The two algorithms named HFDK-W1 and HFDK-W2 result in better image quality, noise uniformity, lower noise and reduced cone-beam artifacts.

Estimation of signals in colored non gaussian noise based on Gaussian Mixture models

Non-Gaussianity of signals/noise often results in significant performance degradation for systems, which are designed using the Gaussian assumption. So non-Gaussian signals/noise require a different modelling and processing approach. In this paper, we discuss a new Bayesian estimation technique for non-Gaussian signals corrupted by colored non Gaussian noise. The method is based on using zero mean finite Gaussian Mixture Models (GMMs) for signal and noise. The estimation is done using an adaptive non-causal nonlinear filtering technique. The method involves deriving an estimator in terms of the GMM parameters, which are in turn estimated using the EM algorithm. The proposed filter is of finite length and offers computational feasibility. The simulations show that the proposed method gives a significant improvement compared to the linear filter for a wide variety of noise conditions, including impulsive noise. We also claim that the estimation of signal using the correlation with past and future samples leads to reduced mean squared error as compared to signal estimation based on past samples only.

An efficient pricing based protocol for broadcasting in wireless ad hoc networks

In many applications of wireless ad hoc networks, wireless nodes are owned by rational and intelligent users. In this paper, we call nodes selfish if they are owned by independent users and their only objective is to maximize their individual goals. In such situations, it may not be possible to use the existing protocols for wireless ad hoc networks as these protocols assume that nodes follow the prescribed protocol without deviation. Stimulating cooperation among these nodes is an interesting and challenging problem. Providing incentives and pricing the transactions are well known approaches to stimulate cooperation. In this paper, we present a game theoretic framework for truthful broadcast protocol and strategy proof pricing mechanism called Immediate Predecessor Node Pricing Mechanism (IPNPM). The phrase strategy proof here means that truth revelation of cost is a weakly dominant-strategy (in game theoretic terms) for each node. In order to steer our mechanism-design approach towards practical implementation, we compute the payments to nodes using a distributed algorithm. We also propose a new protocol for broadcast in wireless ad hoc network with selfish nodes based on IPNPM. The features of the proposed broadcast protocol are reliability and a significantly reduced number of packet forwards compared to the number of network nodes, which in turn leads to less system-wide power consumption to broadcast a single packet. Our simulation results show the efficacy of the proposed broadcast protocol.