QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that the number of hops in the path from each sensor to its BS is bounded by h(max), and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.

COMPLEX GEODESICS, THEIR BOUNDARY REGULARITY, AND A HARDY-LITTLEWOOD-TYPE LEMMA

We begin by giving an example of a smoothly bounded convex domain that has complex geodesics that do not extend continuously up to partial derivative D. This example suggests that continuity at the boundary of the complex geodesics of a convex domain Omega (sic) C-n, n >= 2, is affected by the extent to which partial derivative Omega curves or bends at each boundary point. We provide a sufficient condition to this effect (on C-1-smoothly bounded convex domains), which admits domains having boundary points at which the boundary is infinitely flat. Along the way, we establish a Hardy-Littlewood-type lemma that might be of independent interest.

Explicit and Unique Construction of Tetrablock Unitary Dilation in a Certain Case

Consider the domain E in defined by This is called the tetrablock. This paper constructs explicit boundary normal dilation for a triple (A, B, P) of commuting bounded operators which has as a spectral set. We show that the dilation is minimal and unique under a certain natural condition. As is well-known, uniqueness of minimal dilation usually does not hold good in several variables, e.g., Ando's dilation is known to be not unique, see Li and Timotin (J Funct Anal 154:1-16, 1998). However, in the case of the tetrablock, the third component of the dilation can be chosen in such a way as to ensure uniqueness.

Modal scattering at an impedance transition in a lined flow duct

An explicit Wiener-Hopf solution is derived to describe the scattering of duct modes at a hard-soft wall impedance transition in a circular duct with uniform mean flow. Specifically, we have a circular duct r = 1, - ∞ < x < ∞ with mean flow Mach number M > 0 and a hard wall along x < 0 and a wall of impedance Z along x > 0. A minimum edge condition at x = 0 requires a continuous wall streamline r = 1 + h(x, t), no more singular than h = Ο(x1/2) for x ↓ 0. A mode, incident from x < 0, scatters at x = 0 into a series of reflected modes and a series of transmitted modes. Of particular interest is the role of a possible instability along the lined wall in combination with the edge singularity. If one of the "upstream" running modes is to be interpreted as a downstream-running instability, we have an extra degree of freedom in the Wiener-Hopf analysis that can be resolved by application of some form of Kutta condition at x = 0, for example a more stringent edge condition where h = Ο(x3/2) at the downstream side. The question of the instability requires an investigation of the modes in the complex frequency plane and therefore depends on the chosen impedance model, since Z = Z (ω) is essentially frequency dependent. The usual causality condition by Briggs and Bers appears to be not applicable here because it requires a temporal growth rate bounded for all real axial wave numbers. The alternative Crighton-Leppington criterion, however, is applicable and confirms that the suspected mode is usually unstable. In general, the effect of this Kutta condition is significant, but it is particularly large for the plane wave at low frequencies and should therefore be easily measurable. For ω → 0, the modulus fends to |R001| → (1 + M)/(1 -M) without and to 1 with Kutta condition, while the end correction tends to ∞ without and to a finite value with Kutta condition. This is exactly the same behaviour as found for reflection at a pipe exit with flow, irrespective if this is uniform or jet flow.

Hierarchical approach to timing verification in CMOS VLSI design

This paper describes a novel hierarchical approach to timing verification. Four types of relationship existing among signal paths are distinguished, based on a classification of the degree of interdependency in the circuit. In this way, irrelevant path delays can be excluded through consideration of the interaction between critical paths and others. Furthermore, under suitable conditions, bounded delay values for large hierarchical systems can be deduced using bounded delays determined for their constituent cells. Finally, we discuss the impact on design strategy of the hierarchical delay model presented in this paper.

Uniform stability of a particle approximation of the optimal filter derivative

Sequential Monte Carlo methods, also known as particle methods, are a widely used set of computational tools for inference in non-linear non-Gaussian state-space models. In many applications it may be necessary to compute the sensitivity, or derivative, of the optimal filter with respect to the static parameters of the state-space model; for instance, in order to obtain maximum likelihood model parameters of interest, or to compute the optimal controller in an optimal control problem. In Poyiadjis et al. [2011] an original particle algorithm to compute the filter derivative was proposed and it was shown using numerical examples that the particle estimate was numerically stable in the sense that it did not deteriorate over time. In this paper we substantiate this claim with a detailed theoretical study. Lp bounds and a central limit theorem for this particle approximation of the filter derivative are presented. It is further shown that under mixing conditions these Lp bounds and the asymptotic variance characterized by the central limit theorem are uniformly bounded with respect to the time index. We demon- strate the performance predicted by theory with several numerical examples. We also use the particle approximation of the filter derivative to perform online maximum likelihood parameter estimation for a stochastic volatility model.

Influence Of Free Surface Curvature Of A Liquid Layer On The Critical Marangoni Convection

The Pearson instability was suggested to discuss the onset of Marangoni convection in a liquid layer of large Prandtl number under an applied temperature difference perpendicular to the free surface in the microgravity environment. In this case, the temperature distribution on the curved free surface is nonuniform, and the thermocapillary convection is induced and coupled with the Marangoni convection. In the present paper the effect of volume ratio of the liquid layer on the critical Marangoni convection and the corresponding spatial variation of the convection structure in zero-gravity condition were numerically investigated by two-dimensional model. (C) 2008 Elsevier Ltd. All rights reserved.

Rigorous finite-time guarantees for optimization on continuous domains by simulated annealing

Simulated annealing is a popular method for approaching the solution of a global optimization problem. Existing results on its performance apply to discrete combinatorial optimization where the optimization variables can assume only a finite set of possible values. We introduce a new general formulation of simulated annealing which allows one to guarantee finite-time performance in the optimization of functions of continuous variables. The results hold universally for any optimization problem on a bounded domain and establish a connection between simulated annealing and up-to-date theory of convergence of Markov chain Monte Carlo methods on continuous domains. This work is inspired by the concept of finite-time learning with known accuracy and confidence developed in statistical learning theory.

Robust multiplexed model predictive control

This paper extends the recently developed multiplexed model predictive control (MMPC) concept to ensure satisfaction of hard constraints despite the action of persistent, unknown but bounded disturbances. MMPC uses asynchronous control moves on each input channel instead of synchronised moves on all channels. It offers reduced computation, by dividing the online optimisation into a smaller problem for each channel, and potential performance improvements, as the response to a disturbance is quicker, albeit via only one channel. Robustness to disturbances is introduced using the constraint tightening approach, tailored to suit the asynchronous updates of MMPC and the resulting time-varying optimisations. Numerical results are presented, involving a simple mechanical example and an aircraft control example, showing the potential computational and performance benefits of the new robust MMPC.

The annular crack in a nonhomogeneous matrix surrounding a fiber under torsional loading .2. The crack going through the bimaterial interface into the fiber

The axisymmetric problem of an elastic fiber perfectly bonded to a nonhomogeneous elastic matrix which contains an annular crack going through the interface into the fiber under axially symmetric shear stress is considered. The nature of the stress singularity is studied. It is shown that at the irregular point on the interface, whether the shear modulus is continuous or discontinuous the stresses are bounded. The problem is formulated in terms of a singular integral equation and can be solved by a regular method. The stress intensity factors and crack surface displacement are given.

Approximate knowledge of rationality and correlated equilibria

We extend Aumann's [3] theorem deriving correlated equilibria as a consequence of common priors and common knowledge of rationality by explicitly allowing for non-rational behavior. We replace the assumption of common knowledge of rationality with a substantially weaker notion, joint p-belief of rationality, where agents believe the other agents are rational with probabilities p = (pi)i2I or more. We show that behavior in this case constitutes a constrained correlated equilibrium of a doubled game satisfying certain p-belief constraints and characterize the topological structure of the resulting set of p-rational outcomes. We establish continuity in the parameters p and show that, for p su ciently close to one, the p-rational outcomes are close to the correlated equilibria and, with high probability, supported on strategies that survive the iterated elimination of strictly dominated strategies. Finally, we extend Aumann and Dreze's [4] theorem on rational expectations of interim types to the broader p-rational belief systems, and also discuss the case of non-common priors.

Stability of Switched Feedback Time-Varying Dynamic Systems Based on the Properties of the Gap Metric for Operators

The stabilization of dynamic switched control systems is focused on and based on an operator-based formulation. It is assumed that the controlled object and the controller are described by sequences of closed operator pairs (L, C) on a Hilbert space H of the input and output spaces and it is related to the existence of the inverse of the resulting input-output operator being admissible and bounded. The technical mechanism addressed to get the results is the appropriate use of the fact that closed operators being sufficiently close to bounded operators, in terms of the gap metric, are also bounded. That philosophy is followed for the operators describing the input-output relations in switched feedback control systems so as to guarantee the closed-loop stabilization.

Fixed Points of Closed and Compact Composite Sequences of Operators and Projectors in a Class of Banach Spaces

Some results on fixed points related to the contractive compositions of bounded operators in a class of complete metric spaces which can be also considered as Banach's spaces are discussed through the paper. The class of composite operators under study can include, in particular, sequences of projection operators under, in general, oblique projective operators. In this paper we are concerned with composite operators which include sequences of pairs of contractive operators involving, in general, oblique projection operators. The results are generalized to sequences of, in general, nonconstant bounded closed operators which can have bounded, closed, and compact limit operators, such that the relevant composite sequences are also compact operators. It is proven that in both cases, Banach contraction principle guarantees the existence of unique fixed points under contractive conditions.

Some Results on Fixed and Best Proximity Points of Multivalued

This paper is devoted to investigate the fixed points and best proximity points of multivalued cyclic self-mappings on a set of subsets of complete metric spaces endowed with a partial order under a generalized contractive condition involving a Hausdorff distance. The existence and uniqueness of fixed points of both the cyclic self-mapping and its associate composite self-mappings on each of the subsets are investigated, if the subsets in the cyclic disposal are nonempty, bounded and of nonempty convex intersection. The obtained results are extended to the existence of unique best proximity points in uniformly convex Banach spaces.