On the Average Case Communication Complexity for Detection in Sensor Networks

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A signal-space viewpoint is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces $\mathcal{S_I}$ and $\mathcal{S_C}$ and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating $\mathcal{S_I}$ and $\mathcal{S_C}$ is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. The average case CC of the relevant greater-than (GT) function is characterized within two bits. In the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm.

Distributed intrusion detection in the presence of correlated sensor readings: Signal-space and communication-complexity view-point

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A signal-space view-point is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces f(s) and f(g) and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating f(s) and f(g) is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication-complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. Extensions to the multi-party case is straightforward and is briefly discussed. The average case CC of the relevant greaterthan (CT) function is characterized within two bits. Under the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm. 2010 Elsevier B.V. All rights reserved.

Understanding How the Brain Changes Its Mind: Microstimulation in the Macaque Frontal Eye Field Reveals How Saccade Plans Are Changed

Accumulator models that integrate incoming sensory information into motor plans provide a robust framework to understand decision making. However, their applicability to situations that demand a change of plan raises an interesting problem for the brain. This is because interruption of the current motor plan must occur by a competing motor plan, which is necessarily weaker in strength. To understand how changes of mind get expressed in behavior, we used a version of the double-step task called the redirect task, in which monkeys were trained to modify a saccade plan. We microstimulated the frontal eye fields during redirect behavior and systematically measured the deviation of the evoked saccade from the response field to causally track the changing saccade plan. Further, to identify the underlying mechanisms, eight different computational models of redirect behavior were assessed. It was observed that the model that included an independent, spatially specific inhibitory process, in addition to the two accumulators representing the preparatory processes of initial and final motor plans, best predicted the performance and the pattern of saccade deviation profile in the task. Such an inhibitory process suppressed the preparation of the initial motor plan, allowing the final motor plan to proceed unhindered. Thus, changes of mind are consistent with the notion of a spatially specific, inhibitory process that inhibits the current inappropriate plan, allowing expression of the new plan.

Impacts of climate change and management responses in tropical forests depend on complex frugivore-mediated seed dispersal

AimBiodiversity outcomes under global change will be influenced by a range of ecological processes, and these processes are increasingly being considered in models of biodiversity change. However, the level of model complexity required to adequately account for important ecological processes often remains unclear. Here we assess how considering realistically complex frugivore-mediated seed dispersal influences the projected climate change outcomes for plant diversity in the Australian Wet Tropics (all 4313 species). LocationThe Australian Wet Tropics, Queensland, Australia. MethodsWe applied a metacommunity model (M-SET) to project biodiversity outcomes using seed dispersal models that varied in complexity, combined with alternative climate change scenarios and habitat restoration scenarios. ResultsWe found that the complexity of the dispersal model had a larger effect on projected biodiversity outcomes than did dramatically different climate change scenarios. Applying a simple dispersal model that ignored spatial, temporal and taxonomic variation due to frugivore-mediated seed dispersal underestimated the reduction in the area of occurrence of plant species under climate change and overestimated the loss of diversity in fragmented tropical forest remnants. The complexity of the dispersal model also changed the habitat restoration approach identified as the best for promoting persistence of biodiversity under climate change. Main conclusionsThe consideration of complex processes such as frugivore-mediated seed dispersal can make an important difference in how we understand and respond to the influence of climate change on biodiversity.

Change in Mesoherbivore Browsing Is Mediated by Elephant and Hillslope Position

Elephant are considered major drivers of ecosystems, but their effects within small-scale landscape features and on other herbivores still remain unclear. Elephant impact on vegetation has been widely studied in areas where elephant have been present for many years. We therefore examined the combined effect of short-term elephant presence (< 4 years) and hillslope position on tree species assemblages, resource availability, browsing intensity and soil properties. Short-term elephant presence did not affect woody species assemblages, but did affect height distribution, with greater sapling densities in elephant access areas. Overall tree and stem densities were also not affected by elephant. By contrast, slope position affected woody species assemblages, but not height distributions and densities. Variation in species assemblages was statistically best explained by levels of total cations, Zinc, sand and clay. Although elephant and mesoherbivore browsing intensities were unaffected by slope position, we found lower mesoherbivore browsing intensity on crests with high elephant browsing intensity. Thus, elephant appear to indirectly facilitate the survival of saplings, via the displacement of mesoherbivores, providing a window of opportunity for saplings to grow into taller trees. In the short-term, effects of elephant can be minor and in the opposite direction of expectation. In addition, such behavioural displacement promotes recruitment of saplings into larger height classes. The interaction between slope position and elephant effect found here is in contrast with other studies, and illustrates the importance of examining ecosystem complexity as a function of variation in species presence and topography. The absence of a direct effect of elephant on vegetation, but the presence of an effect on mesoherbivore browsing, is relevant for conservation areas especially where both herbivore groups are actively managed.

Climate change and forests in India

Forests play a critical role in addressing climate change concerns in the broader context of global change and sustainable development. Forests are linked to climate change in three ways. i) Forests are a source of greenhouse gas (GHG) emissions: ii) Forests offer mitigation opportunities to stabilise GHG concentrations: iii) Forests are impacted by climate change. This paper reviews studies related to climate change and forests in India: first, the studies estimating carbon inventory for the Indian land use change and forestry sector (LUCF), then the different models and mitigation potential estimates for the LUCF sector in India. Finally it reviews the studies on the impact of climate change on forest ecosystems in India, identifying the implications for net primary productivity and bio-diversity. The paper highlights data, modelling and research gaps relevant to the GHG inventory, mitigation potential and vulnerability and impact assessments for the forest sector in India.

A comparative social network analysis of wasp colonies and classrooms: Linking network structure to functioning

A major question in current network science is how to understand the relationship between structure and functioning of real networks. Here we present a comparative network analysis of 48 wasp and 36 human social networks. We have compared the centralisation and small world character of these interaction networks and have studied how these properties change over time. We compared the interaction networks of (1) two congeneric wasp species (Ropalidia marginata and Ropalidia cyathiformis), (2) the queen-right (with the queen) and queen-less (without the queen) networks of wasps, (3) the four network types obtained by combining (1) and (2) above, and (4) wasp networks with the social networks of children in 36 classrooms. We have found perfect (100%) centralisation in a queen-less wasp colony and nearly perfect centralisation in several other queen-less wasp colonies. Note that the perfectly centralised interaction network is quite unique in the literature of real-world networks. Differences between the interaction networks of the two wasp species are smaller than differences between the networks describing their different colony conditions. Also, the differences between different colony conditions are larger than the differences between wasp and children networks. For example, the structure of queen-right R. marginata colonies is more similar to children social networks than to that of their queen-less colonies. We conclude that network architecture depends more on the functioning of the particular community than on taxonomic differences (either between two wasp species or between wasps and humans).

Problems with geoengineering schemes to combat climate change

The accelerated rate of increase in atmospheric CO2 concentration in recent years has revived the idea of stabilizing the global climate through geoengineering schemes. Majority of the proposed geoengineering schemes will attempt to reduce the amount of solar radiation absorbed by our planet. Climate modelling studies of these so called 'sunshade geoengineering schemes' show that global warming from increasing concentrations of CO2 can be mitigated by intentionally manipulating the amount of sunlight absorbed by the climate system. These studies also suggest that the residual changes could be large on regional scales, so that climate change may not be mitigated on a local basis. More recent modelling studies have shown that these schemes could lead to a slow-down in the global hydrological cycle. Other problems such as changes in the terrestrial carbon cycle and ocean acidification remain unsolved by sunshade geoengineering schemes. In this article, I review the proposed geoengineering schemes, results from climate models and discuss why geoengineering is not the best option to deal with climate change.

Equivariant Birch-Swinnerton-Dyer Conjecture for the Base Change of Elliptic Curves: An Example

Let E be an elliptic curve defined over Q and let K/Q be a finite Galois extension with Galois group G. The equivariant Birch-Swinnerton-Dyer conjecture for h(1)(E x(Q) K)(1) viewed as amotive over Q with coefficients in Q[G] relates the twisted L-values associated with E with the arithmetic invariants of the same. In this paper I prescribe an approach to verify this conjecture for a given data. Using this approach, we verify the conjecture for an elliptic curve of conductor 11 and an S-3-extension of Q.

The Parallel Complexity Of Propagation In Boolean Circuits

We consider the problem of deciding whether the output of a boolean circuit is determined by a partial assignment to its inputs. This problem is easily shown to be hard, i.e., co-Image Image -complete. However, many of the consequences of a partial input assignment may be determined in linear time, by iterating the following step: if we know the values of some inputs to a gate, we can deduce the values of some outputs of that gate. This process of iteratively deducing some of the consequences of a partial assignment is called propagation. This paper explores the parallel complexity of propagation, i.e., the complexity of determining whether the output of a given boolean circuit is determined by propagating a given partial input assignment. We give a complete classification of the problem into those cases that are Image -complete and those that are unlikely to be Image complete.

Unsteady Natural Convection Flow in a Square Cavity Filled with a Porous Medium Due to Impulsive Change in Wall Temperature

Unsteady natural convection flow in a two- dimensional square cavity filled with a porous material has been studied. The flow is initially steady where the left- hand vertical wall has temperature T-h and the right- hand vertical wall is maintained at temperature T-c ( T-h > T-c) and the horizontal walls are insulated. At time t > 0, the left- hand vertical wall temperature is suddenly raised to (T-h) over bar ((T-h) over bar > T-h) which introduces unsteadiness in the flow field. The partial differential equations governing the unsteady natural convection flow have been solved numerically using a finite control volume method. The computation has been carried out until the final steady state is reached. It is found that the average Nusselt number attains a minimum during the transient period and that the time required to reach the final steady state is longer for low Rayleigh number and shorter for high Rayleigh number.

Reduced complexity two stage vector quantization

We address the issue of complexity for vector quantization (VQ) of wide-band speech LSF (line spectrum frequency) parameters. The recently proposed switched split VQ (SSVQ) method provides better rate-distortion (R/D) performance than the traditional split VQ (SVQ) method, even at the requirement of lower computational complexity. but at the expense of much higher memory. We develop the two stage SVQ (TsSVQ) method, by which we gain both the memory and computational advantages and still retain good R/D performance. The proposed TsSVQ method uses a full dimensional quantizer in its first stage for exploiting all the higher dimensional coding advantages and then, uses an SVQ method for quantizing the residual vector in the second stage so as to reduce the complexity. We also develop a transform domain residual coding method in this two stage architecture such that it further reduces the computational complexity. To design an effective residual codebook in the second stage, variance normalization of Voronoi regions is carried out which leads to the design of two new methods, referred to as normalized two stage SVQ (NTsSVQ) and normalized two stage transform domain SVQ (NTsTrSVQ). These two new methods have complimentary strengths and hence, they are combined in a switched VQ mode which leads to the further improvement in R/D performance, but retaining the low complexity requirement. We evaluate the performances of new methods for wide-band speech LSF parameter quantization and show their advantages over established SVQ and SSVQ methods.

Role of Melt Convection on the Thermal Performance of Heat Sinks with Phase Change Material

The role of melt convection oil the performance of beat sinks with Phase Change Material (PCM) is presented in this paper. The beat sink consists of aluminum plate fins embedded in PCM and heat flux is supplied from the bottom. The design of such a heat sink requires optimization with respect to its geometrical parameters. The objective of the optimization is to maximize the heat sink operation time for the prescribed heat flux and the critical chip temperature. The parameters considered for optimization are fin number and fill thickness. The height and base plate thickness of heat sink are kept constant in the present analysis. An enthalpy based CFD model is developed, which is capable Of Simulating phase change and associated melt convection. The CFD model is Coupled with Genetic Algorithm (GA) for carrying out the optimization. Two cases are considered, one without melt convection (conduction regime) and the other with convection. It is found that the geometrical optimizations of heat sinks are different for the two cases, indicating the importance of inch convection in the design of heat sinks with PCMs.

A measure of logical complexity of programs

The research in software science has so far been concentrated on three measures of program complexity: (a) software effort; (b) cyclomatic complexity; and (c) program knots. In this paper we propose a measure of the logical complexity of programs in terms of the variable dependency of sequence of computations, inductive effort in writing loops and complexity of data structures. The proposed complexity mensure is described with the aid of a graph which exhibits diagrammatically the dependence of a computation at a node upon the computation of other (earlier) nodes. Complexity measures of several example programs have been computed and the related issues have been discussed. The paper also describes the role played by data structures in deciding the program complexity.

Multiresolution Area-based Fractal Dimension Estimation of Signals Applied to EEG Data

In this paper, we present an approach to estimate fractal complexity of discrete time signal waveforms based on computation of area bounded by sample points of the signal at different time resolutions. The slope of best straight line fit to the graph of log(A(rk)A / rk(2)) versus log(l/rk) is estimated, where A(rk) is the area computed at different time resolutions and rk time resolutions at which the area have been computed. The slope quantifies complexity of the signal and it is taken as an estimate of the fractal dimension (FD). The proposed approach is used to estimate the fractal dimension of parametric fractal signals with known fractal dimensions and the method has given accurate results. The estimation accuracy of the method is compared with that of Higuchi's and Sevcik's methods. The proposed method has given more accurate results when compared with that of Sevcik's method and the results are comparable to that of the Higuchi's method. The practical application of the complexity measure in detecting change in complexity of signals is discussed using real sleep electroencephalogram recordings from eight different subjects. The FD-based approach has shown good performance in discriminating different stages of sleep.