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.

Visual Analysis of Biomolecular Surfaces

Surface models of biomolecules have become crucially important for the study and understanding of interaction between biomolecules and their environment. We argue for the need for a detailed understanding of biomolecular surfaces by describing several applications in computational and structural biology. We review methods used to model, represent, characterize, and visualize biomolecular surfaces focusing on the role that geometry and topology play in identifying features on the surface. These methods enable the development of efficient computational and visualization tools for studying the function of biomolecules.

New measures for estimating surface complementarity and packing at protein-protein interfaces

A number of methods exist that use different approaches to assess geometric properties like the surface complementarity and atom packing at the protein-protein interface. We have developed two new and conceptually different measures using the Delaunay tessellation and interface slice selection to compute the surface complementarity and atom packing at the protein-protein interface in a straightforward manner. Our measures show a strong correlation among themselves and with other existing measures, and can be calculated in a highly time-efficient manner. The measures are discriminative for evaluating biological, as well as non-biological protein-protein contacts, especially from large protein complexes and large-scale structural studies(http://pallab.serc. iisc.ernet.in/nip_nsc). (C) 201 Federation of European Biochemical Societies. Published by Elsevier B. V. All rights reserved.

A network representation of protein structures: Implications for protein stability

This study views each protein structure as a network of noncovalent connections between amino acid side chains. Each amino acid in a protein structure is a node, and the strength of the noncovalent interactions between two amino acids is evaluated for edge determination. The protein structure graphs (PSGs) for 232 proteins have been constructed as a function of the cutoff of the amino acid interaction strength at a few carefully chosen values. Analysis of such PSGs constructed on the basis of edge weights has shown the following: 1), The PSGs exhibit a complex topological network behavior, which is dependent on the interaction cutoff chosen for PSG construction. 2), A transition is observed at a critical interaction cutoff, in all the proteins, as monitored by the size of the largest cluster (giant component) in the graph. Amazingly, this transition occurs within a narrow range of interaction cutoff for all the proteins, irrespective of the size or the fold topology. And 3), the amino acid preferences to be highly connected (hub frequency) have been evaluated as a function of the interaction cutoff. We observe that the aromatic residues along with arginine, histidine, and methionine act as strong hubs at high interaction cutoffs, whereas the hydrophobic leucine and isoleucine residues get added to these hubs at low interaction cutoffs, forming weak hubs. The hubs identified are found to play a role in bringing together different secondary structural elements in the tertiary structure of the proteins. They are also found to contribute to the additional stability of the thermophilic proteins when compared to their mesophilic counterparts and hence could be crucial for the folding and stability of the unique three-dimensional structure of proteins. Based on these results, we also predict a few residues in the thermophilic and mesophilic proteins that can be mutated to alter their thermal stability.

Neutral-point balancing of neutral-point-clamped three-level inverter with a front end switched rectifier DC source for the full modulationn range

A switched rectifier DC voltage source three-level neutral-point-clamped (NPC) converter topology is proposed here to alleviate the inverter from capacitor voltage balancing in three-level drive systems. The proposed configuration requires only one DC link with a voltage of half of that needed in a conventional NPC inverter. To obtain a rated DC link voltage, the rectifier DC source is alternately connected in parallel to one of the two series capacitors using two switches and two diodes with device voltage ratings of half the total DC bus voltage. The frequency at which the voltage source is switched is independent of the inverter and will not affect its operation since the switched voltage source in this configuration balances the capacitors automatically. The proposed configuration can also be used as a conventional two-level inverter in the lower modulation index range, thereby increasing the reliability of the drivesystem. A space-vector-based PWM scheme is used to verify this proposed topology on a laboratory system.

A Proportional plus Multiresonant Controller for Three-Phase Four-Wire High-Frequency Link Inverter

A new solution for unbalanced and nonlinear loads in terms of power circuit topology and controller structure is proposed in this paper. A three-phase four-wire high-frequency ac-link inverter is adopted to cater to such loads. Use of high-frequency transformer results in compact and light-weight systems. The fourth wire is taken out from the midpoint of the isolation transformer in order to avoid the necessity of an extra leg. This makes the converter suitable for unbalanced loads and eliminates the requirements of bulky capacitor in half-bridge inverter. The closed-loop control is carried out in stationary reference frame using proportional + multiresonant controller (three separate resonant controller for fundamental, fifth and seventh harmonic components). The limitations on improving steady-state response of harmonic resonance controllers is investigated and mitigated using a lead-lag compensator. The proposed voltage controller is used along with an inner current loop to ensure excellent performance of the power converter. Simulation studies and experimental results with 1 kVA prototype under nonlinear and unbalanced loading conditions validate the proposed scheme.

High-Throughput Flexible Constraint Length Viterbi Decoders on De Bruijn, Shuffle-Exchange and Butterfly Connected Architectures

Flexible constraint length channel decoders are required for software defined radios. This paper presents a novel scalable scheme for realizing flexible constraint length Viterbi decoders on a de Bruijn interconnection network. Architectures for flexible decoders using the flattened butterfly and shuffle-exchange networks are also described. It is shown that these networks provide favourable substrates for realizing flexible convolutional decoders. Synthesis results for the three networks are provided and a comparison is performed. An architecture based on a 2D-mesh, which is a topology having a nominally lesser silicon area requirement, is also considered as a fourth point for comparison. It is found that of all the networks considered, the de Bruijn network offers the best tradeoff in terms of area versus throughput.

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.

Molten globule-like state of peanut lectin monomer retains its carbohydrate specificity - Implications in protein folding and legume lectin oligomerization

A central question in biological chemistry is the minimal structural requirement of a protein that would determine its specificity and activity, the underlying basis being the importance of the entire structural element of a protein with regards to its activity vis a vis the overall integrity and stability of the protein. Although there are many reports on the characterization of protein folding/ unfolding intermediates, with considerable secondary structural elements but substantial loss of tertiary structure, none of them have been reported to show any activity toward their respective ligands. This may be a result of the conditions under which such intermediates have been isolated or due to the importance of specific structural elements for the activity. In this paper we report such an intermediate in the unfolding of peanut agglutinin that seems to retain, to a considerable degree, its carbohydrate binding specificity and activity. This result has significant implications on the molten globule state during the folding pathway(s) of proteins in general and the quaternary association in legume lectins in particular, where precise subunit topology is required for their biologic activities.

Local structure in LaMnO3 and CaMnO3 perovskites: A quantitative structural refinement of mn K-edge XANES data

Hole-doped perovskites such as La1-xCaxMnO3 present special magnetic and magnetotransport properties, and it is commonly accepted that the local atomic structure around Mn ions plays a crucial role in determining these peculiar features. Therefore experimental techniques directly probing the local atomic structure, like x-ray absorption spectroscopy (XAS), have been widely exploited to deeply understand the physics of these compounds. Quantitative XAS analysis usually concerns the extended region [extended x-ray absorption fine structure (EXAFS)] of the absorption spectra. The near-edge region [x-ray absorption near-edge spectroscopy (XANES)] of XAS spectra can provide detailed complementary information on the electronic structure and local atomic topology around the absorber. However, the complexity of the XANES analysis usually prevents a quantitative understanding of the data. This work exploits the recently developed MXAN code to achieve a quantitative structural refinement of the Mn K-edge XANES of LaMnO3 and CaMnO3 compounds; they are the end compounds of the doped manganite series LaxCa1-xMnO3. The results derived from the EXAFS and XANES analyses are in good agreement, demonstrating that a quantitative picture of the local structure can be obtained from XANES in these crystalline compounds. Moreover, the quantitative XANES analysis provides topological information not directly achievable from EXAFS data analysis. This work demonstrates that combining the analysis of extended and near-edge regions of Mn K-edge XAS spectra could provide a complete and accurate description of Mn local atomic environment in these compounds.

Observation of single top quark production and measurement of |Vtb| with CDF

We report the observation of electroweak single top quark production in 3.2  fb-1 of pp̅ collision data collected by the Collider Detector at Fermilab at √s=1.96  TeV. Candidate events in the W+jets topology with a leptonically decaying W boson are classified as signal-like by four parallel analyses based on likelihood functions, matrix elements, neural networks, and boosted decision trees. These results are combined using a super discriminant analysis based on genetically evolved neural networks in order to improve the sensitivity. This combined result is further combined with that of a search for a single top quark signal in an orthogonal sample of events with missing transverse energy plus jets and no charged lepton. We observe a signal consistent with the standard model prediction but inconsistent with the background-only model by 5.0 standard deviations, with a median expected sensitivity in excess of 5.9 standard deviations. We measure a production cross section of 2.3-0.5+0.6(stat+sys)  pb, extract the value of the Cabibbo-Kobayashi-Maskawa matrix element |Vtb|=0.91-0.11+0.11(stat+sys)±0.07  (theory), and set a lower limit |Vtb|>0.71 at the 95% C.L., assuming mt=175  GeV/c2.

Observation of single top quark production and measurement of |Vtb| with CDF

We report the observation of electroweak single top quark production in 3.2 fb-1 of ppbar collision data collected by the Collider Detector at Fermilab at sqrt{s}=1.96 TeV. Candidate events in the W+jets topology with a leptonically decaying W boson are classified as signal-like by four parallel analyses based on likelihood functions, matrix elements, neural networks, and boosted decision trees. These results are combined using a super discriminant analysis based on genetically evolved neural networks in order to improve the sensitivity. This combined result is further combined with that of a search for a single top quark signal in an orthogonal sample of events with missing transverse energy plus jets and no charged lepton. We observe a signal consistent with the standard model prediction but inconsistent with the background-only model by 5.0 standard deviations, with a median expected sensitivity in excess of 5.9 standard deviations. We measure a production cross section of 2.3+0.6-0.5(stat+sys) pb, extract the CKM matrix element value |Vtb|=0.91+0.11-0.11 (stat+sys)+-0.07(theory), and set a lower limit |Vtb|>0.71 at the 95% confidence level, assuming m_t=175 GeVc^2.

Generic Routing Rules and a Scalable Access Enhancement for the Network-on-Chip RECONNECT

RECONNECT is a Network-on-Chip using a honeycomb topology. In this paper we focus on properties of general rules applicable to a variety of routing algorithms for the NoC which take into account the missing links of the honeycomb topology when compared to a mesh. We also extend the original proposal [5] and show a method to insert and extract data to and from the network. Access Routers at the boundary of the execution fabric establish connections to multiple periphery modules and create a torus to decrease the node distances. Our approach is scalable and ensures homogeneity among the compute elements in the NoC. We synthesized and evaluated the proposed enhancement in terms of power dissipation and area. Our results indicate that the impact of necessary alterations to the fabric is negligible and effects the data transfer between the fabric and the periphery only marginally.

Spatial ecology of food webs : herbivore-parasitoid communities on the pedunculate oak

Herbivorous insects, their host plants and natural enemies form the largest and most species-rich communities on earth. But what forces structure such communities? Do they represent random collections of species, or are they assembled by given rules? To address these questions, food webs offer excellent tools. As a result of their versatile information content, such webs have become the focus of intensive research over the last few decades. In this thesis, I study herbivore-parasitoid food webs from a new perspective: I construct multiple, quantitative food webs in a spatially explicit setting, at two different scales. Focusing on food webs consisting of specialist herbivores and their natural enemies on the pedunculate oak, Quercus robur, I examine consistency in food web structure across space and time, and how landscape context affects this structure. As an important methodological development, I use DNA barcoding to resolve potential cryptic species in the food webs, and to examine their effect on food web structure. I find that DNA barcoding changes our perception of species identity for as many as a third of the individuals, by reducing misidentifications and by resolving several cryptic species. In terms of the variation detected in food web structure, I find surprising consistency in both space and time. From a spatial perspective, landscape context leaves no detectable imprint on food web structure, while species richness declines significantly with decreasing connectivity. From a temporal perspective, food web structure remains predictable from year to year, despite considerable species turnover in local communities. The rate of such turnover varies between guilds and species within guilds. The factors best explaining these observations are abundant and common species, which have a quantitatively dominant imprint on overall structure, and suffer the lowest turnover. By contrast, rare species with little impact on food web structure exhibit the highest turnover rates. These patterns reveal important limitations of modern metrics of quantitative food web structure. While they accurately describe the overall topology of the web and its most significant interactions, they are disproportionately affected by species with given traits, and insensitive to the specific identity of species. As rare species have been shown to be important for food web stability, metrics depicting quantitative food web structure should then not be used as the sole descriptors of communities in a changing world. To detect and resolve the versatile imprint of global environmental change, one should rather use these metrics as one tool among several.

Design and analysis of rate aware ad hoc 802.11 networks

802.11 WLANs are characterized by high bit error rate and frequent changes in network topology. The key feature that distinguishes WLANs from wired networks is the multi-rate transmission capability, which helps to accommodate a wide range of channel conditions. This has a significant impact on higher layers such as routing and transport levels. While many WLAN products provide rate control at the hardware level to adapt to the channel conditions, some chipsets like Atheros do not have support for automatic rate control. We first present a design and implementation of an FER-based automatic rate control state machine, which utilizes the statistics available at the device driver to find the optimal rate. The results show that the proposed rate switching mechanism adapts quite fast to the channel conditions. The hop count metric used by current routing protocols has proven itself for single rate networks. But it fails to take into account other important factors in a multi-rate network environment. We propose transmission time as a better path quality metric to guide routing decisions. It incorporates the effects of contention for the channel, the air time to send the data and the asymmetry of links. In this paper, we present a new design for a multi-rate mechanism as well as a new routing metric that is responsive to the rate. We address the issues involved in using transmission time as a metric and presents a comparison of the performance of different metrics for dynamic routing.