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.

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one-dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008.

Detection of a periodic structure hidden in random background: the role of signal amplitude in the matched filter detection method

The matched filter method for detecting a periodic structure on a surface hidden behind randomness is known to detect up to (r(0)/Lambda) gt;= 0.11, where r(0) is the coherence length of light on scattering from the rough part and 3 is the wavelength of the periodic part of the surface-the above limit being much lower than what is allowed by conventional detection methods. The primary goal of this technique is the detection and characterization of the periodic structure hidden behind randomness without the use of any complicated experimental or computational procedures. This paper examines this detection procedure for various values of the amplitude a of the periodic part beginning from a = 0 to small finite values of a. We thus address the importance of the following quantities: `(a)lambda) `, which scales the amplitude of the periodic part with the wavelength of light, and (r(0))Lambda),in determining the detectability of the intensity peaks.

Some pulse characteristics of atmospheric radio noise bursts at 3 MHz

An atmospheric radio noise burst represents the radiation received from one complete lightning flash at the frequency to which a receiver is tuned and within the receiver bandwidth. At tropical latitudes, the principal source of interference in the frequency range from 0.1 to 10 MHz is the burst form of atmospheric radio noise. The structure of a burst shows several approximately rectangular pulses of random amplitude, duration and frequency of recurrence. The influence of the noise on data communication can only be examined when the value of the number of pulses crossing a certain amplitude threshold per unit time of the noise burst is known. A pulse rate counter designed for this purpose has been used at Bangalore (12°58′N, 77°35′E) to investigate the pulse characteristics of noise bursts at 3 MHz with a receiver bandwidth of 3.3 kHz/6d B. The results show that the number of pulses lying in the amplitude range between peak and quasi-peak values of the noise bursts and the burst duration corresponding to these pulses follow log normal distributions. The pulse rates deduced therefrom show certain correlation between the number of pulses and the duration of the noise burst. The results are discussed with a view to furnish necessary information for data communication.

An instantaneous pulse frequency meter for random pulses

Counting-rate meters normally used for finding pulse frequencies are sluggish in their response to any rapid change in the pulse repetition frequency (P.R.F.). An instrument is described which measures each pulse interval and provides immediately afterwards an output voltage proportional to the reciprocal of interval duration. A response to a change in the P.R.F. as rapidly as is physically possible is obtained. The instrument has wide application in low level radiation detection and in several other fields especially for rapidly varying counting-rates.

Moment-Matched Lognormal Modeling of Uplink Interference with Power Control and Cell Selection

We develop an alternate characterization of the statistical distribution of the inter-cell interference power observed in the uplink of CDMA systems. We show that the lognormal distribution better matches the cumulative distribution and complementary cumulative distribution functions of the uplink interference than the conventionally assumed Gaussian distribution and variants based on it. This is in spite of the fact that many users together contribute to uplink interference, with the number of users and their locations both being random. Our observations hold even in the presence of power control and cell selection, which have hitherto been used to justify the Gaussian distribution approximation. The parameters of the lognormal are obtained by matching moments, for which detailed analytical expressions that incorporate wireless propagation, cellular layout, power control, and cell selection parameters are developed. The moment-matched lognormal model, while not perfect, is an order of magnitude better in modeling the interference power distribution.

Nonlinear vibration analysis of composite laminated and sandwich plates with random material properties

Nonlinear vibration analysis is performed using a C-0 assumed strain interpolated finite element plate model based on Reddy's third order theory. An earlier model is modified to include the effect of transverse shear variation along the plate thickness and Von-Karman nonlinear strain terms. Monte Carlo Simulation with Latin Hypercube Sampling technique is used to obtain the variance of linear and nonlinear natural frequencies of the plate due to randomness in its material properties. Numerical results are obtained for composite plates with different aspect ratio, stacking sequence and oscillation amplitude ratio. The numerical results are validated with the available literature. It is found that the nonlinear frequencies show increasing non-Gaussian probability density function with increasing amplitude of vibration and show dual peaks at high amplitude ratios. This chaotic nature of the dispersion of nonlinear eigenvalues is also r

A cost effective pipelined divider for double precision floating point number

he growth of high-performance application in computer graphics, signal processing and scientific computing is a key driver for high performance, fixed latency; pipelined floating point dividers. Solutions available in the literature use large lookup table for double precision floating point operations.In this paper, we propose a cost effective, fixed latency pipelined divider using modified Taylor-series expansion for double precision floating point operations. We reduce chip area by using a smaller lookup table. We show that the latency of the proposed divider is 49.4 times the latency of a full-adder. The proposed divider reduces chip area by about 81% than the pipelined divider in [9] which is based on modified Taylor-series.

Analysis Of The Hvdc Turbine Generator Torsional Interactions

In the recent past it has been found that HVDC transmission systems and turbine-generator shaft torsional dynamics can interact in an unfavourable manner. This paper presents a detailed linearised state space model of AC/DC system to study this torsional interaction. The model developed is used to study the effect of various system parameters, such as, dc line loading, converter firing angle, the firing scheme employed. The results obtained are compared with those given in[3].

Evidence of ferromagnetic domains in the La0.67Ca0.33Mn0.9Fe0.1O3 perovskite

The nature of the low-temperature magnetic state of polycrystalline La0.67Ca0.33Mn0.9Fe0.1O3 has been studied by magnetization, neutron diffraction, and neutron depolarization measurements. Neutron depolarization measurements indicate the existence of ferromagnetic domains with low net magnetic moments below 108 K. The substitution of Mn3+ by Fe3+ reduces the number of available hopping sites for the Mn e(g) (up) electron and suppresses the double exchange, resulting in the reduction of ferromagnetic exchange. The competition between the ferromagnetic double-exchange interactions and the coexisting antiferromagnetic superexchange interactions and its randomness due to random substitutions of Mn3+ with Fe3+ drive the system into a randomly canted ferromagnetic state at low temperatures.

Transient Momentum and Enthalpy Transfer in Packed Beds at High Reynolds Numbers

An experimental study for transient temperature response and pressure drop in a randomly packed bed at high Reynolds numbers is presented.The packed bed is used as a compact heat exchanger along with a solid-propellant gas generator, to generate room-temperature gases for use in control actuation, air bottle pressurization, etc. Packed beds of lengths 200 and 300 mm were characterized for packing-sphere-based Reynolds numbers ranging from 0.8 x 10(4) to 8.5 x 10(4).The solid packing used in the bed consisted of phi 9.5 mm steel spheres. The bed-to-particle diameter ratio was with the average packed-bed porosity around 0.43. The inlet flow temperature was unsteady and a mesh of spheres was used at either end to eliminate flow entrance and exit effects. Gas temperature and pressure were measured at the entry, exit,and at three axial locations along centerline in the packed beds. The solid packing temperature was measured at three axial locations in the packed bed. A correlation based on the ratio of pressure drop and inlet-flow momentum (Euler number) exhibited an asymptotically decreasing trend with increasing Reynolds number. Axial conduction across the packed bed was found to he negligible in the investigated Reynolds number range. The enthalpy absorption rate to solid packing from hot gases is plotted as a function of a nondimensional time constant for different Reynolds numbers. A longer packed bed had high enthalpy absorption rate at Reynolds number similar to 10(4), which decreased at Reynolds number similar to 10(5). The enthalpy absorption plots can be used for estimating enthalpy drop across packed bed with different material, but for a geometrically similar packing.

Belief Propagation Based Decoding of Large Non-Orthogonal STBCs

In this paper,we present a belief propagation (BP) based algorithm for decoding non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) having large dimensions. The proposed approachinvolves message passing on Markov random field (MRF) representation of the STBC MIMO system. Adoption of BP approach to decode non-orthogonal STBCs of large dimensions has not been reported so far. Our simulation results show that the proposed BP-based decoding achieves increasingly closer to SISO AWGN performance for increased number of dimensions. In addition, it also achieves near-capacity turbo coded BER performance; for e.g., with BP decoding of 24 x 24 STBC from CDA using BPSK (i.e.,n576 real dimensions) and rate-1/2 turbo code (i.e., 12 bps/Hz spectral efficiency), coded BER performance close to within just about 2.5 dB from the theoretical MIMO capacity is achieved.