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.

In situ transmission electron microscope study of single asperity sliding contacts

Direct observation of events taking place at the contacting interfaces is important to understand many tribological phenomena. Transmission electron microscope (TEM) has the ability to look through materials at very high magnifications. Most of the TEM observations are done long after the deforming loads and stresses have been relaxed and the material state is further disturbed during the specimen preparation. We have developed a specimen holder in which two electron transparent surfaces can be brought in contact and moved relative to each other in JEOL 2000FX microscope. This holder enables visualization of not only the contacting surfaces at nanoscale but also the subsurface deformation resulting from the contact interaction. Sliding experimentS have been carried out mimicking a single asperity sliding contact. A sharp tungsten probe is moved laterally against a tip mounted on a cantilever. Magnitude of the contact instability, when the contact is broken is found to be dependent on the local geometry of the contact.(C) 2009 Elsevier Ltd. All rights reserved.

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.

A new constraint programming approach for optimising a coal rail system

Because of the bottlenecking operations in a complex coal rail system, millions of dollars are costed by mining companies. To handle this issue, this paper investigates a real-world coal rail system and aims to optimise the coal railing operations under constraints of limited resources (e.g., limited number of locomotives and wagons). In the literature, most studies considered the train scheduling problem on a single-track railway network to be strongly NP-hard and thus developed metaheuristics as the main solution methods. In this paper, a new mathematical programming model is formulated and coded by optimization programming language based on a constraint programming (CP) approach. A new depth-first-search technique is developed and embedded inside the CP model to obtain the optimised coal railing timetable efficiently. Computational experiments demonstrate that high-quality solutions are obtainable in industry-scale applications. To provide insightful decisions, sensitivity analysis is conducted in terms of different scenarios and specific criteria. Keywords Train scheduling · Rail transportation · Coal mining · Constraint programming

Phase change on transmission of microwaves through metal disc delay dielectrics

Expressions for the phase change Φ suffered by microwaves when transmitted through an artificial dielectric composed of metallic discs arranged in a three-dimensional array have been derived with different approaches as follows (i) molecular theory, (ii) electromagnetic theory and (iii) transmission line theory. The phase change depends on the distance t that the wave traverses inside the dielectric and also the spacing d between centre to centre of any two adjacent discs in the three principal directions. Molecular theory indicates Φ as an increasing function of t, whereas, the other two theories indicate Φ as an oscillatory function of t. The transmission line theory also exhibits Φ to be real or imaginary depending on t. Experimental values of Φ as a function of t have been obtained with the help of a microwave (3·2 cms wavelength) interferometer for two dielectrics having d as 1·91 cms and 2·22 cms respectively.

Modern Societal Impulses and their Nordic Manifestations : On Emancipation and Constraint in Societal Development

The 1980s and the early 1990s have proved to be an important turning point in the history of the Nordic welfare states. After this breaking point, the Nordic social order has been built upon a new foundation. This study shows that the new order is mainly built upon new hierarchies and control mechanisms that have been developed consistently through economic and labour market policy measures. During the post-war period Nordic welfare states to an increasing extent created equality of opportunity and scope for agency among people. Public social services were available for all and the tax-benefit system maintained a level income distribution. During this golden era of Nordic welfare state, the scope for agency was, however, limited by social structures. Public institutions and law tended to categorize people according to their life circumstances ascribing them a predefined role. In the 1980s and 1990s this collectivist social order began to mature and it became subject to political renegotiation. Signs of a new social order in the Nordic countries have included the liberation of the financial markets, the privatizing of public functions and redefining the role of the public sector. It is now possible to reassess the ideological foundations of this new order. As a contrast to widely used political rhetoric, the foundation of the new order has not been the ideas of individual freedom or choice. Instead, the most important aim appears to have been to control and direct people to act in accordance with the rules of the market. The various levels of government and the social security system have been redirected to serve this goal. Instead of being a mechanism for redistributing income, the Nordic social security system has been geared towards creating new hierarchies on the Nordic labour markets. During the past decades, conditions for receiving income support and unemployment benefit have been tightened in all Nordic countries. As a consequence, people have been forced to accept deteriorating terms and conditions on the labour market. Country-specific variations exist, however: in sum Sweden has been most conservative, Denmark most innovative and Finland most radical in reforming labour market policy. The new hierarchies on the labour market have co-incided with slow or non-existent growth of real wages and with a strong growth of the share of capital income. Slow growth of real wages has kept inflation low and thus secured the value of capital. Societal development has thus progressed from equality of opportunity during the age of the welfare states towards a hierarchical social order where the majority of people face increasing constraints and where a fortunate minority enjoys prosperity and security.

Advanced transmission electron microscope triboprobe with automated closed-loop nanopositioning

Here the design and operation of a novel transmission electron microscope (TEM) triboprobe instrument with real-time vision control for advanced in situ electron microscopy is demonstrated. The NanoLAB triboprobe incorporates a new high stiffness coarse slider design for increased stability and positioning performance. This is linked with an advanced software control system which introduces both new and flexible in situ experimental functional testing modes, plus an automated vision control feedback system. This advancement in instrumentation design unlocks new possibilities of performing a range of new dynamical nanoscale materials tests, including novel friction and fatigue experiments inside the electron microscope.

Analysis of the performance characteristics of a two-inertia power transmission system with a plate clutch

The performance of a plate clutch in a two-inertia power transmission system is analysed assuming negligible compliance and using a piecewise linear function to represent the clutch torque characteristic. Expressions defining, for all linear segments of the clutch torque characteristic, dimensionless input and output velocities of the clutch and dimensionless slip period are presented. The use of these expressions in preparing design charts to aid analysis and design of the plate clutch is outlined.

A new approach for fault location identification in transmission system using stability analysis and SVMs

This paper presents a new approach to the location of fault in the high voltage power transmission system using Support Vector Machines (SVMs). A knowledge base is developed using transient stability studies for apparent impedance swing trajectory in the R-X plane. SVM technique is applied to identify the fault location in the system. Results are presented on sample 3-power station, a 9-bus system illustrate the implementation of the proposed method.

Comparative studies of transient and steady state analysis for a typical 765kV/400kV EHV transmission system in Indian power system

This paper describes an approach for the analysis and design of 765kV/400kV EHV transmission system which is a typical expansion in Indian power grid system, based on the analysis of steady state and transient over voltages. The approach for transmission system design is iterative in nature. The first step involves exhaustive power flow analysis, based on constraints such as right of way, power to be transmitted, power transfer capabilities of lines, existing interconnecting transformer capabilities etc. Acceptable bus voltage profiles and satisfactory equipment loadings during all foreseeable operating conditions for normal and contingency operation are the guiding criteria. Critical operating strategies are also evolved in this initial design phase. With the steady state over voltages obtained, comprehensive dynamic and transient studies are to be carried out including switching over voltages studies. This paper presents steady state and switching transient studies for alternative two typical configurations of 765kV/400 kV systems and the results are compared. Transient studies are carried out to obtain the peak values of 765 kV transmission systems and are compared with the alternative configurations of existing 400 kV systems.

An intelligent approach using support vector machines for monitoring and identification of faults on transmission systems

Power system disturbances are often caused by faults on transmission lines. When faults occur in a power system, the protective relays detect the fault and initiate tripping of appropriate circuit breakers, which isolate the affected part from the rest of the power system. Generally Extra High Voltage (EHV) transmission substations in power systems are connected with multiple transmission lines to neighboring substations. In some cases mal-operation of relays can happen under varying operating conditions, because of inappropriate coordination of relay settings. Due to these actions the power system margins for contingencies are decreasing. Hence, power system protective relaying reliability becomes increasingly important. In this paper an approach is presented using Support Vector Machine (SVM) as an intelligent tool for identifying the faulted line that is emanating from a substation and finding the distance from the substation. Results on 24-bus equivalent EHV system, part of Indian southern grid, are presented for illustration purpose. This approach is particularly important to avoid mal-operation of relays following a disturbance in the neighboring line connected to the same substation and assuring secure operation of the power systems.

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.

A New Structure Preserving Energy Function Incorporating Transmission Line Resistances

A novel method to account for the transmission line resistances in structure preserving energy functions (SPEF) is presented in this paper. The method exploits the equivalence of a lossy network having the same conductance to susceptance ratio for all its elements to a lossless network with a new set of power injections. The system equations and the energy function are developed using centre of inertia (COI) variables and the loads are modelled as arbitrary functions of respective bus voltages. The application of SPEF to direct transient stability evaluation is presented considering a realistic power system example.