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.

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

Delay optimal control algorithm for a multiaccess fading channel with peak power constraint

We consider an optimal power and rate scheduling problem for a multiaccess fading wireless channel with the objective of minimising a weighted sum of mean packet transmission delay subject to a peak power constraint. The base station acts as a controller which, depending upon the buffer lengths and the channel state of each user, allocates transmission rate and power to individual users. We assume perfect channel state information at the transmitter and the receiver. We also assume a Markov model for the fading and packet arrival processes. The policy obtained represents a form of Indexability.

Encouragement and discouragement : Essays on taxation and government expenditure

This thesis consists of an introduction to a topic of optimal use of taxes and government expenditure and three chapters analysing these themes more in depth. Chapter 2 analyses to what extent a given amount of subsidies affects the labour supply of parents. Municipal supplement to the Finnish home care allowance provides exogenous variation to labour supply decision of a parent. This kind of subsidy that is tied to staying at home instead of working is found to have fairly large effect on labour supply decisions of parents. Chapter 3 studies theoretically when it is optimal to provide publicly private goods. In the set up of the model government sets income taxes optimally and provides a private good, if it is beneficial to do so. The analysis results in an optimal provision rule according to which the good should be provided when it lowers the participation threshold into labour force. Chapter 4 investigates what happened to prices and demand when hairdressers value added tax was cut in Finland from 22 per cent to 8 per cent. The pass-through to prices was about half of the full pass-through and no clear indication of increased demand for the services or better employment situation in the sector is found.

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.

An Expenditure-Based Estimation of Self-Employment Income Underreporting in Finland

This paper estimates the extent of income underreporting by the self-employed in Finland using the expenditure based approach developed by Pissarides & Weber (1989). Household spending data are for the years 1994 to 1996. The results suggest that self-employment income in Finland is underreported by some 27% on average. Since income for the self-employed is about 8 % of all incomes in Finland, the size of this part of the black economy in Finland is estimated to be about 2,3% of GDP.

A note on resolving infeasibility in linear programs by constraint relaxation

We study the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. We show the problem is NP-hard even when the constraint matrix is totally unimodular and prove polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.

An Efficient Constraint Grammar Parser based on Inward Deterministic Automata

Pappret conceptualizes parsning med Constraint Grammar på ett nytt sätt som en process med två viktiga representationer. En representation innehåller lokala tvetydighet och den andra sammanfattar egenskaperna hos den lokala tvetydighet klasser. Båda representationer manipuleras med ren finite-state metoder, men deras samtrafik är en ad hoc -tillämpning av rationella potensserier. Den nya tolkningen av parsning systemet har flera praktiska fördelar, bland annat det inåt deterministiska sättet att beräkna, representera och räkna om alla potentiella tillämpningar av reglerna i meningen.

Influence of crack tip constraint on void growth in ductile FCC single crystals

Effect of constraint (stress triaxiality) on void growth near a notch tip in a FCC single crystal is investigated. Finite element simulations within the modified boundary layer framework are conducted using crystal plasticity constitutive equations and neglecting elastic anisotropy. Displacement boundary conditions based on model, elastic, two term K-T field are applied on the outer boundary of a large circular domain. A pre-nucleated void is considered ahead of a stationary notch tip. The interaction between the notch tip and the void is studied under different constraints (T-stress levels) and crystal orientations. It is found that negative T-stress retards the mechanisms of ductile fracture. However, the extent of retardation depends on the crystal orientation. Further, it is found that there exists a particular orientation which delays the ductile fracture processes and hence can potentially improve ductility. This optimal orientation depends on the constraint level. (C) 2010 Published by Elsevier B.V.

Effect of the valine-threonine constraint on the dynamics of the proline helix — A molecular dynamics study

Proline residues in helices play an important role in the structure of proteins. The proline residue introduces a kink in the helix which varies from about 5-degrees to 50-degrees. The presence of other residues such as threonine or valine near the proline region can influence the flexibility exhibited by the kinked helix, which can have an important biological role. In the present paper, the constraint introduced by threonine and valine on a proline helix is investigated by molecular dynamics studies. The systems considered am (1) a poly-alanine helix with threonine-proline residues (TP) and (2) a poly-alanine helix with valine-threonine-proline residues (VTP), in the middle. Molecular dynamics simulations are carried out on these two systems for 500 ps. The results are analyzed in terms of structural transitions, bend-related parameters and sidechain orientations.

Suboptimal Midcourse Guidance of Interceptors for High-Speed Targets with Alignment Angle Constraint

Using the recently developed computationally efficient model predictive static programming and a closely related model predictive spread control concept, two nonlinear suboptimal midcourse guidance laws are presented in this paper for interceptors engaging against incoming high-speed ballistic missiles. The guidance laws are primarily based on nonlinear optimal control theory, and hence imbed effective trajectory optimization concepts into the guidance laws. Apart from being energy efficient by minimizing the control usage throughout the trajectory (minimum control usage leads to minimum turning, and hence leads to minimum induced drag), both of these laws enforce desired alignment constraints in both elevation and azimuth in a hard-constraint sense. This good alignment during midcourse is expected to enhance the effectiveness of the terminal guidance substantially. Both point mass as well as six-degree-of-freedom simulation results (with a realistic inner-loop autopilot based on dynamic inversion) are presented in this paper, which clearly shows the effectiveness of the proposed guidance laws. It has also been observed that, even with different perturbations of missile parameters, the performance of guidance is satisfactory. A comparison study, with the vector explicit guidance scheme proposed earlier in the literature, also shows that the newly proposed model-predictive-static-programming-based and model-predictive-spread-control-based guidance schemes lead to lesser lateral acceleration demand and lesser velocity loss during engagement.

Unified approach to the constraint counting theory of glasses

An approach to the constraint counting theory of glasses is applied to many glass systems which include an oxide, chalcohalide, and chalcogenides. In this, shifting of the percolation threshold due to noncovalent bonding interactions in a basically covalent network and other recent extensions of the theory appear natural. This is particularly insightful and reveals that the chemical threshold signifies another structural transition along with the rigidity percolation threshold, thus unifying these two seemingly disparate toplogical concepts. [S0163-1829(99)11441-3].

Implications of the half-duplex constraint on relay-aided cooperation using rateless codes

The half-duplex constraint, which mandates that a cooperative relay cannot transmit and receive simultaneously, considerably simplifies the demands made on the hardware and signal processing capabilities of a relay. However, the very inability of a relay to transmit and receive simultaneously leads to a potential under-utilization of time and bandwidth resources available to the system. We analyze the impact of the half-duplex constraint on the throughput of a cooperative relay system that uses rateless codes to harness spatial diversity and efficiently transmit information from a source to a destination. We derive closed-form expressions for the throughput of the system, and show that as the number of relays increases, the throughput approaches that of a system that uses more sophisticated full-duplex nodes. Thus, half-duplex nodes are well suited for cooperation using rateless codes despite the simplicity of both the cooperation protocol and the relays.