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.

Force constants and thermodynamic functions of iodine heptafluoride

Normal coordinate analysis of a molecule of the type XY7 (point group D5h) has been carried out using Wilson's FG, matrix method and the results have been utilized to calculate the force constants of IF7 from the available Raman and infrared data. Some of the assignments made previously by Lord and others have been revised and with the revised assignments the thermodynamic quantities of IF7 have been computed from 300°K to 1000°K under rigid rotator and harmonic oscillator approximation.

Potential functions for hydrogen bond interactions - III. Empirical Potential Function for the Peptide N-H...O=C Hydrogen Bond

A careful comparison of the distribution in the (R, θ)-plane of all NH ... O hydrogen bonds with that for bonds between neutral NH and neutral C=O groups indicated that the latter has a larger mean R and a wider range of θ and that the distribution was also broader than for the average case. Therefore, the potential function developed earlier for an average NH ... O hydrogen bond was modified to suit the peptide case. A three-parameter expression of the form {Mathematical expression}, with △ = R - Rmin, was found to be satisfactory. By comparing the theoretically expected distribution in R and θ with observed data (although limited), the best values were found to be p1 = 25, p3 = - 2 and q1 = 1 × 10-3, with Rmin = 2·95 Å and Vmin = - 4·5 kcal/mole. The procedure for obtaining a smooth transition from Vhb to the non-bonded potential Vnb for large R and θ is described, along with a flow chart useful for programming the formulae. Calculated values of ΔH, the enthalpy of formation of the hydrogen bond, using this function are in reasonable agreement with observation. When the atoms involved in the hydrogen bond occur in a five-membered ring as in the sequence[Figure not available: see fulltext.] a different formula for the potential function is needed, which is of the form Vhb = Vmin +p1△2 +q1x2 where x = θ - 50° for θ ≥ 50°, with p1 = 15, q1 = 0·002, Rmin = 2· Å and Vmin = - 2·5 kcal/mole. © 1971 Indian Academy of Sciences.

Potential functions for hydrogen bond interactions - IV. Minimum Energy Conformation of the α-Helical Structure of PoIy-L-Alanine

Making use of the empirical potential functions for peptide NH .. O bonds, developed in this laboratory, the relative stabilities of the rightand left-handed α-helical structures of poly-L-alanine have been investigated, by calculating their conformational energies (V). The value of Vmin of the right-handed helix (αP) is about - 10.4 kcal/mole, and that of the left-handed helix (αM) is about - 9.6 kcal/mole, showing that the former is lower in energy by 0.8 kcal/mole. The helical parameters of the stable conformation of αP are n ∼ 3.6 and h ∼ 1.5 Å. The hydrogen bond of length 2.85 Å and nonlinearity of about 10° adds about 4.0 kcal/ mole to the stabilising energy of the helix in the minimum enregy region. The energy minimum is not sharply defined, but occurs over a long valley, suggesting that a distribution of conformations (φ{symbol}, ψ) of nearly the same energy may occur for the individual residues in a helix. The experimental data of a-helical fibres of poly-L-alanine are in good agreement with the theoretical results for αP. In the case of proteins, the mean values of (φ{symbol}, ψ) for different helices are distributed, but they invariably occur within the contour for V = Vmin + 2 kcal/mole for αP.

On some integral properties of hypergeometric functions

In this note certain integrals involving hypergeometric functions have been evaluated in convenient and elegant forms. © 1971 Indian Academy of Sciences.

Synthesis of plane linkages to generate functions of two variables using point-position reduction—Part 1. Rotary inputs and output

The paper presents simple graphical procedures for position synthesis of plane linkage mechanisms to generate functions of two independent variables. The procedures are based on point-position reduction and permit synthesis of the linkage to satisfy up to six arbitrarily selected precision positions.

Synthesis of plane linkages to generate functions of two variables using point position reduction—II. Sliding inputs and outputs

The paper presents simple graphical procedures for the position synthesis of plane linkage mechanisms with sliding inputs and output to generate functions of two independent variables. The procedures are based on point position reduction and permit synthesis of the linkage to satisfy up to five arbitrarily selected precision positions.

Thermodynamic consistency of the ternary functions

A ternary thermodynamic function has been developed based on statistico-thermodynamic considerations, with a particular emphasis on the higher-order terms indicating the effects of truncation at the various stages of the treatment. Although the truncation of a series involved in the equation introduces inconsistency, the latter may be removed by imposing various thermodynamic boundary conditions. These conditions are discussed in the paper. The present equation with higher-order terms shows that the α function of a component reduces to a quadratic function of composition at constant compositional paths involving the other two components in the system. The form of the function has been found to be representative of various experimental observations.

Distributed Transmission of Functions of Correlated Sources over a Fading Multiple Access Channel

In this paper we address the problem of distributed transmission of functions of correlated sources over a fast fading multiple access channel (MAC). This is a basic building block in a hierarchical sensor network used in estimating a random field where the cluster head is interested only in estimating a function of the observations. The observations are transmitted to the cluster head through a fast fading MAC. We provide sufficient conditions for lossy transmission when the encoders and decoders are provided with partial information about the channel state. Furthermore signal side information maybe available at the encoders and the decoder. Various previous studies are shown as special cases. Efficient joint-source channel coding schemes are discussed for transmission of discrete and continuous alphabet sources to recover function values.

Thermal correlation functions of twisted quantum fields

We derive the thermal correlators for twisted quantum fields on noncommutative spacetime. We show that the thermal expectation value of the number operator is same as in commutative spacetime, but that higher correlators are sensitive to the noncommutativity parameters phi(mu nu).

Chronopotentiometry with power-law perturbation functions at an expanding plane electrode with and without a preceding blank period for systems with a coupled first-order homogeneous chemical reaction

The systems formalism is used to obtain the interfacial concentration transients for power-law current input at an expanding plane electrode. The explicit results for the concentration transients obtained here pertain to arbitrary homogeneous reaction schemes coupled to the oxidant and reductant of a single charge-transfer step and the power-law form without and with a preceding blank period (for two types of power-law current profile, say, (i) I(t) = I0(t−t0)q for t greater-or-equal, slanted t0, I(t) = 0 for t < t0; and (ii) I(t) = I0tq for t greater-or-equal, slanted t0, I(t) = 0 for t < t0). Finally the potential transients are obtained using Padé approximants. The results of Galvez et al. (for E, CE, EC, aC) (J. Electroanal. Chem., 132 (1982) 15; 146 (1983) 221, 233, 243), Molina et al. (for E) (J. Electroanal. Chem., 227 (1987) 1 and Kies (for E) (J. Electroanal. Chem., 45 (1973) 71) are obtained as special cases.

Non-Abelian chiral gauge theories in two dimensions

An anomalous multiflavor chiral theory, with the gauge group SU(N), is studied using non-Abelian bosonization. The theory can be made gauge invariant by introducing Wess-Zumino fields and it is particularly simple if the Jackiw-Rajaraman parameter equals 2. In the strong-coupling limit, the low-energy effective theory only contains light unconfined fermions which interact weakly.